Buddy memory allocation

Il Buddy System o buddy memory allocation è una tecnica di allocazione dinamica della memoria che divide la memoria in partizioni per soddisfare una richiesta di memoria nel miglior modo possibile. Questo sistema suddivide ricorsivamente la memoria in due metà finché il blocco ottenuto è grande appena a sufficienza per l'uso, cioè quando un'ulteriore divisione lo renderebbe più piccolo della dimensione richiesta.

Secondo Donald Knuth, il buddy system è stato inventato nel 1963 da Harry Markowitz, che vinse il Premio Nobel nel 1990 in Economia e Commercio, ed è stato sviluppato indipendentemente da Knowlton negli anni sessanta.

Implementazione e conseguenze

Rispetto alle tecniche di allocazione dinamica della memoria (come il paging), nei moderni sistemi operativi, l'uso del buddy system è relativamente facile da realizzare, soprattutto perché non necessita di hardware apposito per la gestione della memoria (MMU). Pertanto può essere usato su Intel 80286 e precedenti.

Tutti i segmenti di memoria della stessa dimensione (quello che viene chiamato buddy in inglese) sono conservati in una lista concatenata ordinata oppure in un albero. Quando un blocco viene rilasciato viene confrontato con il suo vicino: se entrambi sono della stessa dimensione, allora sono combinati ed inseriti nella lista di buddy di dimensione appena più grande. Quando viene richiesto un blocco, l'allocatore comincerà la sua ricerca tra i blocchi di dimensione appena sufficiente, evitando divisioni non necessarie.

Rispetto ad altre semplici tecniche di allocazione dinamica della memoria, il buddy system genera alcune frammentazioni quando prova a compattare la memoria.

Inoltre il buddy system è soggetto anche a frammentazione interna quando viene assegnata una quantità di memoria maggiore a quella richiesta, ad esempio, se un processo richiede 66K di memoria gliene saranno assegnati 128K, il che si traduce in uno spreco di memoria pari a 62K.

Frammentazione esterna quando viene richiesta memoria maggiore alla dimensione del blocco disponibile più grande. In questo caso vi è la suddivisione dello spazio richiesto in due o più pezzi, nessuno dei quali grande abbastanza per soddisfare da solo la richiesta.

Come funziona

Il buddy system alloca memoria in potenze di 2, vale a dire 2^x, dove x è un numero intero. Così il programmatore può decidere in merito e scrivere codice per ottenere il limite superiore di x. Ad esempio, se il sistema ha 2000K di memoria fisica, il limite massimo sarebbe x=10, cioè 2¹⁰ (1024K) il più grande blocco allocabile. Ciò si traduce rendendo impossibile l'assegnazione in un unico blocco dei restanti 976K di memoria, mentre con 2048K (soli 48K in più) si potrebbe ottimizzare al massimo la dimensione e il numero dei blocchi portando il limite superiore a 2¹¹ (2048K) e utilizzando così tutta la memoria fisica.

Dopo aver deciso il limite superiore (che chiameremo il limite superiore u), il programmatore deve decidere il limite inferiore, vale a dire il più piccolo blocco di memoria che può essere allocato.

Quest'ultimo (che chiameremo limite inferiore l) serve a ridurre le ricerche di piccoli blocchi, impostandone la dimensione minima (solitamente 2², ovvero 4K), in modo da suddividere la memoria in blocchi abbastanza piccoli da ridurre al minimo lo spazio sprecato e grandi abbastanza da evitare ricerche eccessive.

Per capire l'importanza di questo limite in termini di prestazioni, basta pensare al funzionamento del buddy system senza di esso.

Nel caso in cui molti processi facessero richieste per blocchi di memoria come 1K o 2K, il sistema rifiuterebbe molti blocchi liberi cercandone a lungo il migliore ricordando man mano il miglior blocco scartato.

Ora che abbiamo i limiti, cerchiamo di capire cosa succede quando un processo richiede spazio in memoria.

Supponiamo il seguente sistema in cui l = 6, cioè blocchi di dimensione minima 2⁶ = 64K, e u = 10, cioè blocchi di dimensione massima pari a 2¹⁰ = 1024K. La tabella mostra un possibile stato del sistema, dopo alcune richieste di memoria.

	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

Tale ripartizione potrebbe essersi verificata nel seguente modo:

1. t = 1. Processo A richiede un blocco di memoria compreso tra 34K e 64K
2. t = 2. Processo B richiede un blocco di memoria compreso tra 66K e 128K
3. t = 3. Processo C richiede un blocco di memoria compreso tra 35K e 64K
4. t = 4. Processo D richiede un blocco di memoria compreso tra 67K e 128K
5. t = 5. Processo C rilascia la sua memoria
6. t = 6. Processo A rilascia la sua memoria
7. t = 7. Processo B rilascia la sua memoria
8. t = 8. Processo D rilascia la sua memoria

• Se la memoria è da allocare

1. Controlla se c'è in memoria un blocco di dimensioni adeguate (2K se la richiesta è inferiore)
   1. Se hai trovato il blocco cercato, assegnalo al processo che ne ha fatto richiesta
   2. Altrimenti, prova a crearne uno adeguato:
      1. Dividi il blocco di memoria più grande in due metà
      2. Se è stato raggiunto il limite inferiore, alloca il blocco al processo
      3. Torna al punto 1 (per la ricerca di uno slot di memoria di dimensioni adeguate)
      4. Ripetere questo processo fino a quando si trova uno slot di memoria adatto

• Se la memoria è da liberare

1. Libera il blocco di memoria
2. Controlla il blocco vicino - è libero?
3. Se si combina i due blocchi, e torna al punto 2. ripetere finché viene raggiunto il limite superiore, (cioè quando la memoria è stata totalmente liberata), o il blocco vicino è occupato

Questo metodo libera la memoria in maniera piuttosto efficace e, compatta la memoria in tempi relativamente brevi, con numero massimo di confronti pari a log2 (U / L) (vale a dire log2 (u) - log2 (l)).

Tuttavia, esiste ancora il problema della frammentazione interna. In molte situazioni, è essenziale ridurre al minimo la quantità di frammentazione interna. Questo problema può essere risolto tramite allocazione slab.