Do strony głównej

4.8   Zarządzanie ramkami



Wstęp

              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.


Struktury danych

              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.


Zajmowanie ramek

       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.


Zwalnianie ramek

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.


Uwagi


Bibliografia


Autor: Maciej Kwiatkowski