System bliźniaków

Kod jądra może zażyczyć sobie ,,ciągłego'' bloku stron (dokładnie ramek) o zadanej długości (nie za długi $2^n$ gdzie n jest co najwyżej 9, czyli bloki mogą mieć maksymalnie 512 stron, np. 2MB na x86 w jądrze 2.4.18). Może też zwracać (zwalniać) ramki blokami. Z pomocą przychodzi algorytm bliźniaków.

Wewnątrz każdej strefy do obsługi przydziału stron używany jest system bliźniaków. Jest on bardzo szybki dzięki prostym operacjom ,,bitowym'' i odpowiednio do tego skonstruowanym strukturom (rozmiary bloków to potęgi dwójki). Istotą tego systemu jest minimalizacja fragmentacji zewnętrznej i duża wydajność.

Najwięcej przydziałów i zwolnień stron jest wykonywanych dla wirtualnej przestrzeni adresowej procesu. Ze względu na to, że najczęściej allokacje te występują podczas obsługi błędu braku strony, większość przydziałów stron dotyczy pojedynczej strony.

Pewne części jądra, szczególnie sterowniki urządzeń, mają specjalne potrzeby w stosunku do pamięci fizycznej. Mogą na przykład potrzebować czterech ciągłych ramek pamięci obsługującej DMA. System bliźniaków pozwala na szybką obsługę takich przydziałów.

System bliźniaków traktuje fizyczną pamięć jak zbiory $2^n$ stron zaczynających się na granicach adresów podzielnych przez $2^n$. System łączy sąsiadujące bloki w pojedyncze bloki wyższego rzędu. Każdy blok rozmiaru $2^n$ jest ,,kumplem'' (ang. buddy) drugiej połowy bloku wyższego rzędu ($2^{n+1}$), który go zawiera. Alokator trzyma listy wolnych bloków dwustronowych (zaczynających się na granicy dwóch stron) , czterostronowych (zaczynających się na granicy czterech stron) itd. W celu przydzielenia bloku pewnego rzędu (n) sprawdzamy najpierw listę wolnych bloków danego rzędu i (w przypadku niepowodzenia) kolejno wyższych rzędów. Po znalezieniu wolnego bloku następuje przydział. Jeżeli znaleziono blok wyższego rzędu niż wymagany to dzieli się go na dwa bloki o rozmiarze $2^{rzad-1}$, pierwsza część jest dodawana do listy wolnych bloków, a druga część jest przydzielana, chyba, że jeszcze jest za duża to postępujemy rekurencyjnie.

Kiedy zwalniamy pamięć sprawdzamy, czy zwracany blok ma wolnego ,,kumpla'' (na liście wolnych bloków danego rzędu). Jeżeli tak to sklejamy te dwa bloki usuwając ,,kumpla'' z listy i zwalniając rekurencyjnie dwa razy większy blok.