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).[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 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1024K | ||||||||||||||||
A-64K | 64K | 128K | 256K | 512K | ||||||||||||
A-64K | 64K | B-128K | 256K | 512K | ||||||||||||
A-64K | C-64K | B-128K | 256K | 512K | ||||||||||||
A-64K | C-64K | B-128K | D-128K | 128K | 512K | |||||||||||
A-64K | 64K | B-128K | D-128K | 128K | 512K | |||||||||||
128K | B-128K | D-128K | 128K | 512K | ||||||||||||
256K | D-128K | 128K | 512K | |||||||||||||
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 2k 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.
Referências
- ↑ 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]