[ Pobierz całość w formacie PDF ]
.Pobranyzostaje 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 ramekObszar A zostaje zwrócony jako wynik funkcji , a obszary : B, C, D dołączonedo 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 polumap każdemu kolejnemu obszarowi wielkości 'i' pamięci fizycznej odpowiadajeden 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 dzielonemuobszarowi 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 zmianybitu 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 gdziewolne obszary łączy się w większe.Zwalnianie ramekvoid 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 tablicyfree_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ł JedenWielki Obszar).Byc może jego kumpel (czyli druga połowa tego większegobloku) też jest wolny i można je będzie połączyć z powrotem w jeden większyspójny obszar ? Jeśli to się uda, to można szukać kumpla dla tego większegokawał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 zmieniabity 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 zwolnieniewłaśnie utworzonego obszaru A wielkości dwóch ramek, a w międzyczasie niebyło innych operacji na strukturze free_area ( nic się nie zmieniło).Dlaobszaru 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 polumap tej kolejki, a z A i B zostaje utworzony spójny obszar AB.W podobnysposób dla 4-ramkowego obszaru AB zostaje znaleziony kumpel - obszar Ci oba są sklejane w obszar ABC wielkości ośmiu ramek.Do tego obszaru zostajedołączony blok D z czwartej kolejki.Dla obszaru ABCD wielkości 16 rameknie 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 Czemu ma służyć struktura free_area skoro proces żądający kilkuramek pamięci i tak dostaje je po jednej, i to wcale nie w spójnym bloku( na tym polega zaleta stronicowania) ? Otóż struktura free_area powstałagłównie na użytek jądra, które musi mieć przydzielane spójne obszarypamięci i to w różnych rozmiarach. Algorytm "buddy" jest bardzo szybki , mimo że wyglądana skomplikowany.Wynika to z tego, że większość operacji arytmetycznychpolega na przesunięciu binarnym lub zamianie bitu.Dlatego właśnie tablicafree_area jest indeksowana potęgami dwójki. Każdy obszar dołączony do kolejki jest wstawiany na jej początek,natomiast pobieranie następuje z początku lub ze środka (jeśli chcemy wyjąćkumpla o danym adresie ).Bibliografia plik : page_alloc.c plik : page.h Maurice J.Bach "Budowa systemu operacyjnego UNIX" T.Gruźlewski, Z.Weiss "Programowanie współbieżne i rozproszone"Autor: Maciej Kwiatkowski
[ Pobierz całość w formacie PDF ]