# 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$^{10}$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$^6$K = 64K de tamanho, e o limite superior u = 10, que resulta no tamanho do maior bloco que pode ser alocado, 2$^{10}$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 | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K |
| $t=1$ | A-64K | 64K | 128K | 128K | 256K | 256K | 256K | 256K | 512K | 512K | 512K | 512K | 512K | 512K | 512K | 512K |
| $t=2$ | A-64K | 64K | B-128K | B-128K | 256K | 256K | 256K | 256K | 512K | 512K | 512K | 512K | 512K | 512K | 512K | 512K |
| $t=3$ | A-64K | C-64K | B-128K | B-128K | 256K | 256K | 256K | 256K | 512K | 512K | 512K | 512K | 512K | 512K | 512K | 512K |
| $t=4$ | A-64K | C-64K | B-128K | B-128K | D-128K | D-128K | 128K | 128K | 512K | 512K | 512K | 512K | 512K | 512K | 512K | 512K |
| $t=5$ | A-64K | 64K | B-128K | B-128K | D-128K | D-128K | 128K | 128K | 512K | 512K | 512K | 512K | 512K | 512K | 512K | 512K |
| $t=6$ | 128K | 128K | B-128K | B-128K | D-128K | D-128K | 128K | 128K | 512K | 512K | 512K | 512K | 512K | 512K | 512K | 512K |
| $t=7$ | 256K | 256K | 256K | 256K | D-128K | D-128K | 128K | 128K | 512K | 512K | 512K | 512K | 512K | 512K | 512K | 512K |
| $t=8$ | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K | 1024K |
Esta alocação poderia ocorrer na seguinte maneira:
* Processo A requisita memoria 34K..64K é alocado
* Processo B requisita memoria 66K..128K é alocado
* Processo C requisita memoria 35K..64K é alocado
* Processo D requisita memoria 67K..128K é alocado
* Processo C libera sua memória
* Processo A libera sua memória
* Processo B libera sua memória
* 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
* Procura um bloco de memória de tamanho adequado (o menor 2$^k$ bloco que é maior ou igual a memória requisitada)
** Se encontrado, o mesmo é alocado para o Processo
** Senão, ele tenta fazer um bloco de memória que seja adequado. O sistema faz isto tentando o seguinte:
*** Divide um bloco livre de memória, maior que a memória solicitada, pela metade.
*** Se o limite inferior é encontrado, então aloca aquela quantidade de memória
*** Volte para o passo 1
*** Repita este processo até encontrar um bloco de memória adequado
* Quando a memória é liberada
* Libera o bloco de memória
* Verifica se o bloco vizinho é livre também?
* 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.