Buddy memory allocation

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).

Como funciona

A técnica de alocação de memória buddy aloca memória em potências de 2, ou seja 2^x , 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 2¹⁰K (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 2⁶K = 64K de tamanho, e o limite superior u = 10, que resulta no tamanho do maior bloco que pode ser alocado, 2¹⁰K = 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 2^k 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.