Opis





Opis

Wiele struktur jÄ…dra jest strukturami dynamicznymi,
dlatego jądro nie jest w stanie przewidzieć jak dużo pamięci operacyjnej
będzie potrzebować w przyszłości.Nie może podczas startu systemu zarezerwować
sobie wystarczającej ilości pamięci, gdyż każda stała ilość może okazać
się w pewnym momencie niewystarczająca.Jądro dynamicznie, w czasie działania
systemu, zgłasza zapotrzebowanie na przydział określonej ilości pamięci
operacyjnej .

Pamieć operacyjna w Linuxłie dzielona jest logicznie na bloki stałej
wielkości rozmiaru 4 lub 8 kB zwane ramkami.Cóż to znaczy? Otóż w dużym
uproszczeniu, jeśli ktośś w systemie zgłasza zapotrzebowanie na pamieć
operacyjną, czy to bedzie jądro czy proces użytkownika, moduł zarządzający
ramkami przydziela odpowiednią ilość ramek.Jeśli np. jądro w pewnym momencie
potrzebuje 100 bajtów pamięci nie odwołuje się ono bezpośrednio do modułu
zarządzającego ramkami prosząc o przydział ramki, gdyż byłoby wielkim marnotrastwem
przydzielać komuśś kto potrzebuje 100 bajtów od razu 4 lub 8 kB. Tak więc
jÄ…dro odwoÅ‚uje siÄ™ do struktury poÅ›redniej (jest to tablica o nazwie “SIZES"
opisana w punkcie poświęconym pamięci
dla jÄ…dra), “ta struktura prosi" moduÅ‚ zarzÄ…dzajÄ…cy ramkami o przydziaÅ‚
ramki, nastÄ™pnie “wycina" z niej potrzebny kawaÅ‚ek pamiÄ™ci, a informacje
o pozostałej części zapamiętuje.Podczas kolejnego żądania przydziału pamięci
tablica “SIZES" (a dokÅ‚adnie funkcje operujÄ…ce na niej) bÄ™dzie siÄ™ staraÅ‚a
przydzielić niewykorzystany obszar ramek, które już dostała od modułu zarządzającego
ramkami.


Zadanie

Zadaniem studentów jest zmiana strategii zarządzania przydziałem niewykorzystywanych
obszarów ramek, o których informacje przechowywane sÄ… w tablicy “SIZES.W
katalogu ../source/mm znajduje siÄ™ plik o nazwie “ kmalloc.c
.Zawiera on definicjÄ™ tablicy “SIZES" oraz dwóch funkcji operujÄ…cych na
niej: funkcja void* kmalloc( size_t size, int priority)
przydziela obszar
pamięci rozmiaru size, natomiast funkcja int kfree(void*__ptr)
zwalnia
obszar pamiÄ™ci wskazywany przez argument “__ptr". W jaki sposób tablica
“SIZES" zarzÄ…dza wolnymi obszarami? Otóż każdÄ… ramkÄ™ (lub spójny obszar
pamięci złożony z kilku ramek), którą otrzymuje od modułu zarządzającego
ramkami dzieli na równe bloki rozmiaru 2^i (tj. dzieli tyle razy na pół
tak, aby pojedynczy blok był wiekszy-równy od obszaru pamięci, który chcemy
przydzielić i taki, że gdybyśmy chcieli go jeszcze raz złamać na pół to
otrzymalibyśmy blok mniejszy od obszaru, który chcemy przydzielić).Minusem
tej strategii jest to, iż zawsze przydziela się blok rozmiaru 2^i , a nie
rozmiaru takiego jaki akurat jÄ…dro potrzebuje. Zadanie polega na zaimplementowaniu
strategii, w której przydziela się dokładnie tyle pamięci, ile jądro w
danej chwili potrzebuje.Oczywiście przy takim podejściu mamy problemy z
fragmentacją pamięci tzn. powstają tak małe wolne obszary pamięci, których
nie jesteśmy w stanie przydzielić.Celem zadania jest przekonanie się, czy
taka strategia jest lepsza, jeśli chodzi o wykorzystanie pamięci operacyjnej,
niż strategia obecnie zaimplementowana w Linuxie.Przy czym możemy nie kłopotać
się o złożoność czasową, ta może być dużo gorsza niż złożoność mechanizmu
zaimplementowanego dotychczas w Linuxie.Oczywiście studenci, którzy zadbają,
aby funkcje przydzielania i zwalniania obszaru pamiÄ™ci byÅ‚y “dość szybkie"
zostaną wyżej ocenieni.


Szczegóły:

W pliku “ kmalloc.c zostawiamy
deklaracje plików nagłówkowych, możemy również pozostawić deklaracje niektórych
staÅ‚ych oraz nagłówki funkcji “kmalloc" i “kfree".W miejsce deklaracji
tablicy “SIZES deklarujemy wÅ‚asnÄ… strukturÄ™.W najprostszym przypadku może
to być lista niewykorzystanych obszarów ramek, które dostaliśmy od modułu
zarządzającego ramkami. Każdy element listy pamięta adres początku wolnego
obszaru i jego rozmiar. Aby otrzymać wolną ramkę od modułu zarządzającego
ramkami wywołujemy funkcje __get_free_pages()
, aby zwolnić __free_pages()
. Funkcje “kmalloc" i “kfree" powinny zawierać implementacjÄ™ algorytmu
przydziału i zwalniania obszaru pamięci operującego na wcześniej zdefiniowanej
strukturze.W przypadku listy możemy np. dbać oto, aby obszary, które przechowywane
są w liście były zawsze posortowane względem ich rozmiaru.Możemy potrzebny
obszar odcinać od największego kawałka, który przechowujemy na liście lub
szukać kawałka najlepiej pasującego i od niego odcinać potrzebny obszar.



Testy:

Aby móc porównać wykorzystanie pamięci i złożoność czasową zaimplementowanego
przez nas mechanizmu z mechanizmem zastosowanym w Linuxie, należy w oryginalnym
pliku kmalloc.c i w stworzonym przez
nas zamieÅ›cić zmiennÄ… “RAM", której wartoÅ›ciÄ… bÄ™dzie liczba wykorzystywanych
aktualnie przez algorytm ramek pamiÄ™ci, jak również zmiennÄ… “TIME", której
wartoÅ›ciÄ… bÄ™dzie czas wykonania funkcji.Przy wyjÅ›ciu z funkcji “kmalloc"
i “kfree" wartoÅ›ci tych zmiennych zapisywalibyÅ›my w jakimśś pliku tekstowym.


StosujÄ…c wzory:

zÅ‚ożoność pamiÄ™ciowa = max z wartoÅ›ci “RAM"

zÅ‚ożoność czasowa = (suma z wartoÅ›ci “TIME") / ilość wywoÅ‚aÅ„

możemy porównać oba mechanizmy.Bardzo ważne jest, aby testować mechanizmy
na jednym tak samo skonfigurowanym komputerze, na tym samym zadaniu i na
systemie śświeżo zainicjowanym (jest to poważne ograniczenie, lecz nie
mamy innego sposobu, aby mieć pewność, że testy odbywają się w tych samych
warunkach). Oczywiście, aby móc porównać nasz mechanizm z mechanizmem Linuxa,
należy po zmodyfikowaniu kodu źródłowego zrekompilować
jÄ…dro
.




Autor: Jacek Korkuć