Buddy memory allocation

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

A técnica buddy memory allocation é baseada em um algoritmo de alocação de memória que divide a memória em partições para tentar satisfazer uma requisição de memória da forma mais adequada possível. Este sistema utiliza a divisão da memória em metades para tentar proporcionar um best-fit. De acordo com Donald Knuth, o sistema buddy foi inventado em 1963 por Harry Markowitz, que ganhou em 1990 o Prêmio de Ciências Econômicas em Memória de Alfred Nobel, e foi descrito pela primeira vez por Kenneth C. Knowlton (publicado em 1965).[1]

Como funciona[editar | editar código-fonte]

A técnica de alocação de memória buddy aloca memória em potências de 2, ou seja 2x , onde x é um inteiro positivo. Assim, o programador tem que decidir em como obter o limite superior de x. Por exemplo, se o sistema tem 2000K de memória física, o limite superior de x seria 10, sendo 210K (1024K) o maior bloco possível de alocar. Isto tem como resultado a impossibilidade de alocar toda a memória em um único pedaço, os restantes 976K de memória deverão ser alocados em blocos menores.

Depois de decidir o limite superior (vamos chamar de u), o programador tem que decidir o limite inferior, ou seja o menor bloco de memória que pode ser alocado. Este limite inferior é necessário para que o overhead de armazenar localizações de memória usada e livre seja minimizada. Se este limite não existe e muitos programas requisitam blocos pequenos de memória de 1K ou 2K, o sistema gastará muito espaço tentando lembrar quais blocos estão alocados e livres. Tipicamente este numero deveria ser um numero moderado (tipo 2, neste caso a memória é alocada em 2² K = blocos de 4K ), pequeno o suficiente para minimizar o espaço gasto, mas grande o suficiente para evitar excessivo overhead. Vamos chamar o limite inferior de l.

Estabelecidos nossos limites, vamos apresentar um exemplo de funcionamento do sistema quando um programa faz requisições de memória. No exemplo, vamos considerar o limite inferior l = 6, cujo resultado são blocos de 26K = 64K de tamanho, e o limite superior u = 10, que resulta no tamanho do maior bloco que pode ser alocado, 210K = 1024K de tamanho.

A figura a seguir mostra um estado possível de alocação da memória (mapa de alocação) depois das seguintes requisições/liberações de memória:

64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K
t=0 1024K
t=1 A-64K 64K 128K 256K 512K
t=2 A-64K 64K B-128K 256K 512K
t=3 A-64K C-64K B-128K 256K 512K
t=4 A-64K C-64K B-128K D-128K 128K 512K
t=5 A-64K 64K B-128K D-128K 128K 512K
t=6 128K B-128K D-128K 128K 512K
t=7 256K D-128K 128K 512K
t=8 1024K

Esta alocação poderia ocorrer na seguinte maneira:

  1. Processo A requisita memoria 34K..64K é alocado
  2. Processo B requisita memoria 66K..128K é alocado
  3. Processo C requisita memoria 35K..64K é alocado
  4. Processo D requisita memoria 67K..128K é alocado
  5. Processo C libera sua memória
  6. Processo A libera sua memória
  7. Processo B libera sua memória
  8. Processo D libera sua memória

A partir do exemplo, é possível verificar que o que acontece quando uma requisição de memória é feita é o seguinte:

  • Quando a memória é alocada
  1. Procura um bloco de memória de tamanho adequado (o menor 2k bloco que é maior ou igual a memória requisitada)
    1. Se encontrado, o mesmo é alocado para o Processo
    2. Senão, ele tenta fazer um bloco de memória que seja adequado. O sistema faz isto tentando o seguinte:
      1. Divide um bloco livre de memória, maior que a memória solicitada, pela metade.
      2. Se o limite inferior é encontrado, então aloca aquela quantidade de memória
      3. Volte para o passo 1
      4. Repita este processo até encontrar um bloco de memória adequado
  • Quando a memória é liberada
  1. Libera o bloco de memória
  2. Verifica se o bloco vizinho é livre também?
  3. Se é , combina os dois e volta para o passo 2, repetindo este processo até encontrar o limite superior (toda memória esta liberada) ou até encontrar um vizinho que não está livre.

Referências

  1. Kenneth C. Knowlton. A Fast storage allocator. Communications of the ACM 8(10):623-625, Oct 1965. also Kenneth C Knowlton. A programmer's description of L6. Communications of the ACM, 9(8):616-625, Aug. 1966 [see also : Google books [1] page 85]