4.8 Zarządzanie ramkami
Pamięć w systemie Linux jest zorganizowana przez stronicowanie . Wynika z tego , że najmniejszy kawałek pamięci , który może zostać zajęty lub zwolniony jest ustalonych rozmiarów. Taki kawałek pamięci logicznej (wirtualnej) nazywa się "stroną" , a pamięci fizycznej (rzeczywistej - mieszczącej się w pamięci operacyjnej komputera lub przechowywanej na dysku) - "ramką". Rozmiar tego kawalka pamięci definiuje stała PAGE_SIZE równa 4096 (bajtow, czyli 4 kB). Oczywiście każda zajęta (używana przez jakiś proces) strona musi mieć odpowiadającą jej ramkę. Tłumaczeniem adresu strony (logicznego) na adres ramki (fizyczny) zajmuje się MMU- Memory Menagement Unit , czyli sprzętowy system zarządzania pamięcią. Ponieważ zajmowanie i zwalnianie ramek są jednymi z najczęstszych operacji , które wykonuje jądro systemu rozsądne jest aby były one wykonywane efektywnie (szybko) , a jednocześnie na niezbyt skomplikowanych strukturach danych i algorytmach. Tak też zostało to zaimplementowane. Zarządzaniem ramkami zajmuje się jedna struktura danych opisana poniżej.
Informacje o ramkach zawierających wolne obszary pamięci fizycznej (wolne t.z.n. gotowe do użycia) są przechowywane w strukturze free_area , a informacje o ramkach zajętych w tablicach stron procesów i w tablicy stron jądra. Tablice stron zostały opisane w rozdziale dotyczącym stronicowania , więc tu zajmę się tylko opisem przechowywania wolnych bloków pamięci.
Struktura free_area została zaprojektowana z myślą o algorytmie "buddy" . Jest to tablica cyklicznych list wolnych obszarów pamięci fizycznej o różnych rozmiarach. Wielkość tablicy określa stała NR_MEM_LISTS równa 6. Do i - tego pola tablicy free_area dowiązana jest lista wolnych i spójnych kawałków pamięci o wielkości : (2 ^ i) * PAGE_SIZE , gdzie i = 0..NR_MEM_LISTS - 1. Czyli pierwsza lista zawiera kawałki pamięci wielkości jednej strony , a ostatnia kawałki wielkości 32 stron. Każdy taki kawałek pamięci , mimo że może składać się z wielu stron jest spójnym blokiem pamięci fizycznej:
Pole tablicy free_area zawiera strukturę typu free_area_struct
struct free_area_struct { struct page * next; struct page * prev; unsigned int * map; };
Sześć takich struktur jest głowami sześciu list cyklicznych. Wskaźniki prev i next do innych elementów list nieprzypadkowo nazywają się tak samo jak odpowiednie wskaźniki w strukturze page, która jest elementem list i zawiera informacje o ramkach. Musi tak być aby początek listy traktować jak każdy inny element listy (algorytmy obsługujące listę nie muszą się różnić w przypadku gdy zmieniają początek listy i w przypadku gdy zmieniają dalszą jej część). Pole map jest bardzo ważnuym polem używanym przez algorytm "buddy" opisany dalej.
unsigned long __get_free_pages (int priority, unsigned long order, int dma)
Funkcja ta żąda przydzielenia wolnego obszaru pamięci zwracając adres fizyczny przydzielonego obszaru ( parametr order mówi w której kolejce obszarów zacząć szukać gdyż jest żądaniem bloku wielkości (2 ^ order) * PAGE_SIZE. Wywołuje ona makro RMQUEUE wykonujące niżej opisany algorytm przydziału obszaru. Szukanie obszaru do przydzielenia zaczyna się od kolejki o numerze order . Jeśli nie jest ona pusta to wyjmuje się jeden element i zwraca jego adres jako wynik funkcji. Jeśli kolejka jest pusta to szuka się pierwszej niepustej kolejki na prawo (t.z.n. jednej z kolejek zawierających większe obszary pamięci). W momencie gdy taka się znajdzie wyjmuje się jeden jej element. Jest on oczywiście za duży więc trzeba go podzielić. Do tąd dzieli się go na połowy , aż otrzymany fragment jest żądanej wielkości. Pozostałe po dzieleniu polówki wstawia się do odpowiednich kolejek jako obszary gotowe do przydzielenia.
PRZYKŁAD :
Potrzeba obszaru wielkości 2 ramek (8kB). Niech pierwszą niepustą kolejką będzie kolejka zawierająca obszary wielkości 16 ramek. Pobrany zostaje jeden jej element i dzieli się go na kawałki :
A - wielkości 2 ramek B - wielkości 2 ramek C - wielkości 4 ramek D - wielkości 8 ramek
Obszar A zostaje zwrócony jako wynik funkcji , a obszary : B, C, D dołączone do kolejek: drugiej, trzeciej, czwartej.
Poza tym zmieniane są pola map w strukturach free_area_struct (te struktury to początki kolejek). W kolejce obszrów wielkości 'i' w polu map każdemu kolejnemu obszarowi wielkości 'i' pamięci fizycznej odpowiada jeden bit mówiący o tym , czy obszar jest wolny, czy zajęty. Znaczy to , że w kolejce pierwszej map wskazuje tyle bitów ile jest ramek w systemie. W opisanym wyżej przykładzie w kolejce piątej bit odpowiadający dzielonemu obszarowi wielkości 16 ramek jest zmieniany na przeciwny, a w kolejkach : drugiej, trzeciej, czwartej zmieniane są bity odpowiadające obszarom : B, C, D (poniważ z zajętych stają się wolne). Obszar A nie wymaga zmiany bitu gdyż nadal pozostaje zajęty ( wcześniej był zajęty w tym sensie , że wchodził w skład obszaru więkzsego i sam był niedostępny). Czemu to ma służyć ? Pola map są wykorzystywane dopiero w funkcji free_pages_ok gdzie wolne obszary łączy się w większe.
void free_pages_ok ( unsigned long map_nr, unsigned long order)
Funkcja ta zwalnia obszar wskazany przez map_nr o wielkości : (2 ^ order) * PAGE_SIZE i wstawia go do jednej z kolejek w tablicy free_area. Działa ona według strategii 'kumpla' (ang. ' buddy' ) . Obszar zwalniany musiał być kiedyś przydzielony. Skoro był przydzielony, to musiał być wydzielony z bloku dwa razy większego ( na początku był Jeden Wielki Obszar) . Byc może jego kumpel (czyli druga połowa tego większego bloku) też jest wolny i można je będzie połączyć z powrotem w jeden większy spójny obszar ? Jeśli to się uda, to można szukać kumpla dla tego większego kawałka itd. Wykonuje się to w pętli dotąd, aż szukany kumpel okaże się być zajęty. Dodaje się wtedy blok do odpowiedniej kolejki, a także zmienia bity w polach map zmienionych kolejek ( w praktyce bity te zmienia się w momencie sklejania obszarów ze sobą).
PRZYKŁAD :
Niech w poprzednim przykładzie kolejnym żądaniem będzie zwolnienie właśnie utworzonego obszaru A wielkości dwóch ramek, a w międzyczasie nie było innych operacji na strukturze free_area ( nic się nie zmieniło). Dla obszaru A zostaje znaleziony jego kumpel w postaci bloku B w drugiej kolejce. B zostaje usunięty z kolejki, zostaje zmieniony bit odpowiadający B w polu map tej kolejki, a z A i B zostaje utworzony spójny obszar AB. W podobny sposób dla 4-ramkowego obszaru AB zostaje znaleziony kumpel - obszar C i oba są sklejane w obszar ABC wielkości ośmiu ramek. Do tego obszaru zostaje dołączony blok D z czwartej kolejki. Dla obszaru ABCD wielkości 16 ramek nie da się znaleźć kumpla gdyż wcześniej obszar ten występował pojedyńczo , więc jego kumpel był zajęty . ABCD zostaje więc dołączony do piątej listy (przedostatniej) i zmienia się bit dotyczący tego obszaru.