<<<<<<<<<<           >>>>>>>>>>

Algorytm "Bliźniaków"

 
 
 
 
 
 
 
 
 

Do zarządzania wolnymi ramkami linuks wykorzystuje algorytm bliźniaków (ang. buddy). Istotą algorytmu jest to, że można alokować bloki rozmiarów 1, 2, 4, 8, ... ramek. Bloki mają adresy podzielne przez swój rozmiar. Najmniejsze bloki, wielkości jednej ramki zaczynają się od 0, 1, 2, 3, ... ramki. Bloki rozmiaru 2 od 0, 2, 4, 6 ... ramki, rozmiaru 4 od 0, 4, 8, ... ramki, itd.. Wolne bloki są powiązane w listy, oddzielne dla różnych rozmiarów bloków. Tak więc mamy listę wolnych bloków rozmiaru 1, rozmiaru 2, 4, itd.

Blok rozmiaru większego niż 1 ramka można podzielić na dwa równe bloki. Te dwa mniejsze bloki nazywamy bliźniakami. Przykładowo bloki rozmiaru 2 zaczynające się w ramkach 0 i 2 są bliźniakami, ale takie same bloki, ale zaczynające się w 2 i 4 ramce już nie.

Aby nie dublować informacji, na listach nie pamiętamy bliźniaków, jeśli oba są wolne (ale pamiętamy jednego z nich, jeśli jest on wolny, a jego bliźniak jest zajęty). Jest tak dlatego, że bliźniaki wolne bliźniaki razem tworzą większy blok, który również jest w całości wolny. Wystarczy, że ten większy blok będziemy pamiętać na liście. Chyba, że on też ma wolnego bliźniaka...
Na liście wolnych bloków największego rozmiaru mogą pojawić się dwa bliźniaki.

Ilość różnych rozmiarów bloków jest wyznaczona przez stałą MAX_ORDER równą 10. Dlatego maksymalny rozmiar alokowanego bloku to 512 ramek. Dla architektury x86 daje to bloki od 4096 bajtów do 2 MB.