\documentclass[12pt,a4paper,twoside,titlepage]{article}
\RequirePackage[T1]{fontenc}
\RequirePackage{times}
\RequirePackage[latin2]{inputenc}
\RequirePackage[polish]{babel}
\RequirePackage[dvips]{graphicx}
\RequirePackage{comment}
%\RequirePackage{a4wide}
%\RequirePackage{longtable}
%\RequirePackage{multicol}
%\RequirePackage{url}
\title{PAMIĘĆ : Przydzielanie i zwalnianie bloków pamięci w systemie Linux}
\author{Jakub Górski}
\date{17.01.2001}
\begin{document}
\maketitle
\section{Algorytm alokowania spójnych bloków pamięci\\
\texttt{\_\_get\_free\_pages()}}
\subsection{Wstęp}


Rozdział ten poświęcony jest algorytmowi przydziału bloków wolnej pamięci. W systemie
Linux\footnote{wersja jądra 2.7.4} przydzielane bloki są obszarem spójnej pamięci o wielkości $2^i$ stron.
(rozmiar strony jest zdefiniowany dla każdej architektury, z reguły jest to
$2^{12}$ bajtów).


Do tego celu wykorzystywany jest prosty, ale \textsl{ciężko} zaimplementowany
algorytm bliźniaków - \texttt{Buddy}, o którym szerzej powiemy za chwilę.

\subsection{Algorytm Buddy}
\subsubsection{Wstęp}
Algorytm ten stara się zaalokować najmniejszy możliwy blok pamięci
będący potęgą dwójki nie mniejszy od zamówienia (które jest też
potęgą dwójki). Kluczowym pojęciem niezbędnym do zrozumienia alogrytmu
jest \textit{bliźniak} bloku pamięci, czyli blok o tym samym rozmiarze
leżący bezpośrednio przed albo za badanym blokiem. To czy nasz bliźniak
leży z lewej czy z prawej strony zależy od naszej pozycji. Zakładając, że
początkowy adres wynosi 0 wzór na wyznaczenie pozycji 
bliźniaka możemy przedstawić następująco:

b = \textit{adres\_naszego\_bloku} mod (2 * \textit{rozmiar\_bloku}) \\
jeśli \textit{b} równa się 0 oznacza to, że jesteśmy lewym bliźniakiem, czyli
szukamy swojego brata z prawej strony, wpp. analogicznie odwrotnie. Najłatwiej
to zrozumieć na podstawie przykładu :
\includegraphics[width=0.6\textwidth,height=0.2\textheight]{ryc1.eps}

Algorytm bliźniaków pozwala na utrzymanie niskiej fragmentacji pamięci
przy niewielkim obciążeniu procesora.
\subsubsection{Wejście}
Algorytm na wejściu potrzebuje :
\begin{itemize}
\item rozmiar zamówienia - \textit{k} (zapotrzebowanie na $2^k$ ramek)
\item tablicę rozmiaru \texttt{MAX\_ORDER}, której i-tym elementem
jest lista wolnych bloków pamięci o rozmiarze $2^i$ ramek oraz
dla każdej takiej listy mapa bitowa opisująca stan bliźniaków
(jeśli bit jest zapalony oznacza to że dokładnie jeden z bliźniaków
jest wolnym blokiem pamięci). Mapa bitowa jest przydatna podczas procesu
zwalniania pamięci i łączenia bliźniaków. Więcej informacji o mapie bitowej
(także przykład) podane są w opisie struktury \texttt{free\_area\_struct}.
\end{itemize}
\subsubsection{Wyjście}
Zwracany jest adres bloku spójnej pamięci lub błąd w przypadku braku
wolnej pamięci
\subsubsection{Działanie}
\begin{itemize}
\item przeszukaj listę zawierającą wolne bloki pamięci wielkości $2^k$ (czyli
k-ty element tablicy).
\item jeśli znaleziony został wolny spójny blok pamięci to :
\begin{itemize}
\item (*) jeśli rozmiar bloku jest taki jak zamówienie - przydzielamy go,
wyrzucamy z listy wolnych, odświeżamy mapę bitową - zwracamy zaalokowany fragment
\item jeśli rozmiar bloku jest większy od zamówienia - wyrzucamy go z
listy wolnych, dzielimy blok na dwie połówki (bliźniaków) jedna z nich
staje się wolnym blokiem o mniejszym rozmiarze (dodajemy ją na początek listy, aktualizujemy mapę bitową)
i zaczynamy zajmować się drugą połówką tak jakby był to dopiero co znaleziony blok pamięci
(skaczemy do (*))
\end{itemize}
\item jeśli nie ma wolnego bloku tej wielkości to :
\begin{itemize}
\item jeśli \textit{k} osiągnęło już maksymalną wartość (\texttt{MAX\_ORDER}
\footnote{\texttt{MAX\_ORDER} ma wartość 10, co przy wielkości ramki $2^{12}$ bajtów limituje rozmiar maksymalnego zamówienia na pamięć do 4 megabajtów})
to kończymy - nie ma wystrczająco dużo wolnej pamięci
\item wpp. zwiększamy \textit{k} i zaczynamy zabawę od początku
\end{itemize}
\end{itemize}
\subsubsection{Przykład}
\begin{itemize}
\item Początkowy stan pamięci (szare kwadraciki oznaczają pamięć zajętą):\\
\includegraphics[width=0.7\textwidth,height=0.2\textheight]{prz1_1.eps}
\item Stan po zaalokowaniu 2 jednostek pamięci\\
\includegraphics[width=0.7\textwidth,height=0.2\textheight]{prz1_2.eps}
\end{itemize}

\subsection{Ważniejsze struktury}
\subsubsection{\texttt{struct page}}
Jest to z naszego punktu widzenia podstawowa struktura, przechowywane są w
niej informacje o ramkach. Oto jak ona się prezentuje :
\begin{flushleft}
\verb%typedef struct page {%
\\* \verb%        struct list_head list;          %
\\* \verb%        struct address_space *mapping;  %
\\* \verb%        unsigned long index;            %
\\* \verb%        struct page *next_hash;         %
\\* \verb%        atomic_t count;%
\\* \verb%        unsigned long flags;%
\\* \verb%        struct list_head lru;%
\\* \verb%        unsigned long age;%
\\* \verb%        wait_queue_head_t wait;%
\\* \verb%        struct page **pprev_hash;%
\\* \verb%        struct buffer_head * buffers;%
\\* \verb%        void *virtual;%
\\* \verb%        struct zone_struct *zone;%
\\* \verb%} mem_map_t;%
\end{flushleft}
\textup{Znaczenie :}
\begin{itemize}
%\parskip = 0 pt
\item \texttt{list}\footnote{w omawianej wersji jądra 2.4.7 pojawił się
nowy sposób reprezentowania list - poprzez strukturę \texttt{list\_head},
a nie jak porzednio przez dwa wskaźniki do poprzedniego i następnego elementu
listy} - lista zmapowaych do i-węzła ramek lub wolnych ramek
tworzących spójny blok pamięci
\item \texttt{mapping} - i-węzeł, do którego należymy 
\item \texttt{index} - przesunięcie (offest)
\item \texttt{next\_hash} - wskaźnik do następnej ramki o tej samej wartości haszującej. Aby
przyspieszyć wyszukiwanie ramek Linux używa funkcji haszującej
\texttt{page\_hash()}.
\item \texttt{count} - atomowy licznik mówiący ile procesów, buforów jest związanych z ramką 
\item \texttt{flags} - flagi
\item \texttt{lru} - lista ułatwiająca wybór mniej używanych ramek
\item \texttt{age} - określa wiek ramki 
\item \texttt{wait} - kolejka procesów czekających na operacje wejścia wyjścia
\item \texttt{pprev\_hash} - adekwatne do \texttt{next\_hash }
%\item \texttt{buffers} - bufory zmapowane do bloku na dysku 
\item \texttt{virtual} - wirtualny adres jądra
\item \texttt{zone} - strefa pamięci, do której należy ramka
\end{itemize}
Większość z tych pól używana jest tylko gdy ramka jest zmapowana. (Jeżeli
nie jest zmapowana te pola mają wartość NULL lub 0).\\
\textup{Ciekawsze flagi:}
\begin{itemize}
\item \texttt{PG\_lock} (0) - blokada podczas operacji wejścia wyjścia
\item \texttt{PG\_referenced} (2) - bit pomocny przy wyborze ramki do przeniesienia na
dysk. Jest ustawiony za każdym razem, gdy następuje odwołanie do ramki z tablicy
haszującej. Ten bit wraz z bitem o podobnym znaczeniu w tablicy stron służy do
ustalenia wieku strony, czy strona jest \textit{active} czy \textit{inactive}
\item \texttt{PG\_reserved} (31) - ustawiona dla ramek, które nie mogą być zeswapowane
\end{itemize}
\subsubsection{\texttt{free\_area\_struct}}
Struktura przechowująca informacje o obszarach wolnej pamięci.
\begin{flushleft}
\verb%typedef struct free_area_struct {%
\\* \verb%        struct list_head        free_list;%
\\* \verb%        unsigned long           *map;%
\\* \verb%} free_area_t;%
\end{flushleft}
\textup{Znaczenie :}
\begin{itemize}
\item \texttt{free\_list} - lista wolnych bloków pamięci o tym samym rozmiarze
\item \texttt{map} - wskaźnik do mapy bitowej opisującej stan bliźniaków danego rozmiaru.
I-ty bit jest jest zapalony jeśli \textup{dokładnie} jeden z i-tej pary bliźniaków leżących obok
siebie jest wolnym blokiem pamięci. Ta mapa bardzo ułatwia działanie algorytmu Buddy
\footnote{Mówiac mniej ściśle - jeżeli zwalniamy blok pamięci, a bit jego opisujący
jest zapalony oznacza to, że można połączyć zwolniony blok ze swoim bliźniakiem.
Tą informację zdobywamy w czasie stałym.}
.\\
Przykładowy obraz pamięci wraz z mapą bitową\\
\includegraphics[width=0.8\textwidth,height=0.35\textheight]{ryc2.eps}\\
\end{itemize}
\subsubsection{\texttt{zone\_struct}}
W większości komputerów pamięć fizyczna dzieli się na kilka fizycznych stref.
Komputery klasy PC posiadają 3 strefy (z ang. zone) :
\begin{itemize}
\item \texttt{ZONE\_DMA} (0) - < 16 MB
\item \texttt{ZONE\_NORMAL} (1) - 16-896 MB
\item \texttt{ZONE\_HIGHMEM} (2) - > 896 MB
\end{itemize}
Liczbę stref określa stałą \texttt{MAX\_NR\_ZONES}\\
\begin{flushleft}
\verb%typedef struct zone_struct {%
\\* \verb%        spinlock_t              lock;%
\\* \verb%        unsigned long           free_pages;%
\\* \verb%        unsigned long           inactive_clean_pages;%
\\* \verb%        unsigned long           inactive_dirty_pages;%
\\* \verb%        unsigned long           pages_min, pages_low, %
\\* \verb%                                pages_high;%
\end{flushleft}
\begin{flushleft}
\verb%        %\mbox{
         }\verb%%
\\* \verb%        struct list_head        inactive_clean_list;%
\\* \verb%        free_area_t             free_area[MAX_ORDER];%
\end{flushleft}
\begin{flushleft}
\verb%        %\mbox{
         }\verb%%
\\* \verb%        struct pglist_data      *zone_pgdat;%
\\* \verb%        struct page             *zone_mem_map;%
\\* \verb%        unsigned long           zone_start_paddr;%
\\* \verb%        unsigned long           zone_start_mapnr;%
\end{flushleft}
\begin{flushleft}
\verb%        %\mbox{
         }\verb%%
\\* \verb%        char                    *name;%
\\* \verb%        unsigned long           size;%
\\* \verb%} zone_t;%
\end{flushleft}
\textup{Znaczenie niektórych pól :}
\begin{itemize}
\item \texttt{free\_pages} - liczba wolnych ramek w tej strefie
\item \texttt{inactive\_clean\_pages} - liczba \textit{czystych nieaktywnych} ramek
w strefie, czyli ramek, które przez dłuższy czas nie były używane i ich
zawartość nie jest zmieniona w stosunku do kopii na dysku\footnote{
jeżeli nie ma wolnych ramek te ramki są pierwszymi kandydatami do
wymazania z pamięci - ich zawartość na dysku jest prawidłowa, nie tracimy
czasu na ponowne zapisanie}.
\item \texttt{inactive\_dirty\_pages} - ilość \textit{brudnych nieaktywnych} ramek w
strefie - jw., ale nie są zgodne z kopią
\item \texttt{pages\_min, pages\_low, pages\_high} - są to limity określające pewne pule
wolnych (+nieaktywnych czystych) ramek, które powinny być w strefie, aby
system mógł sprawnie funkcjonować. Więcej informacji będzie
w podczas owówienia \texttt{\_\_get\_free\_pages()}
\item \texttt{inactive\_clean\_list} - cykliczna lista nieaktywnych czystych ramek
\item \texttt{free\_area} - tablica wielkości \texttt{MAX\_ORDER} struktur 
\texttt{free\_area\_struct}, i-ty element tablicy mówi nam o wolnych blokach
pamięci wieklości $2^i$ ramek
\end{itemize}
\subsubsection{\texttt{zonelist\_struct}}
Istnieje struktura, która przetrzymuje tablicę stref, oto ona :
\begin{flushleft}
\verb%typedef struct zonelist_struct {%
\\* \verb%        zone_t * zones [MAX_NR_ZONES+1];%
\\* \verb%} zonelist_t;%
\end{flushleft}
Elementy - strefy w tej tablicy są uporządkowane według priorytetu. Na pierwszym
miejscu w tablicy jest strefa, z której najlepiej korzystać (DMA) - najlepsze czasy
dostępu. Na dalszych miejscach są coraz wolniejsze strefy.
\subsection{Funkcja \texttt{\_\_get\_free\_pages()}}
\subsubsection{Wstęp}
Teraz zobaczymy jak to wygląda od kuchni. Przydział bloku pamięci w Linuksie
realizuje funkcja \texttt{\_\_get\_free\_pages()}. Oto jej nagłówek :
\subsubsection{Nagłówek}
\begin{flushleft}
\verb%unsigned long __get_free_pages(int gfp_mask, unsigned long order)%
\end{flushleft}
\subsubsection{Wejście}
Jako argumenty funkcja bierze rozmiar zamówienia - $2^{order}$ oraz maskę.
Ciekawsze flagi :
\begin{itemize}
\item \texttt{\_\_GFP\_WAIT} - mówi czy proces może czekać przy alokacji,
oddać procesor itp.
\item \texttt{\_\_GFP\_FS} - czy można zmapować na dysk
\end{itemize}
Funkcja zwraca adres zaalokowanego bloku pamięci lub 0 w przypadku
niepowodzenia.
Funkcja ta nic ciekawego nie robi - wywołuje inną funkcję, która
robi całą brudną robotę. Tą interesującą funkcją jest 
\subsection{\texttt{\_\_alloc\_pages()}}
Stara się ona zrealizować zamówienie na $2^k$ ramek. Oto jak to ona robi 
(kod źródłowy omawianych funkcji dostępny w \textit{mm/page\_alloc.c}). Gdy będę mówił o przeszukiwaniu
stref w poszukiwaniu wolnej pamięci będę miał na myśli przeszukiwanie
stref od tej o najmniejszym numerze wzwyż.
\begin{enumerate}
\item przeszukaj strefy w poszukiwaniu dużej\footnote{każda strefa ma określony limit 
\textit{pages\_min} mówiący ile powinno być wolnych ramek w systemie aby ten sprawnie działał} 
ilości wolnej pamięci, jeżeli
znaleziono takową spróbuj w niej zaalokować potrzebną pamięć wykorzystująca algorytm Buddy wywołując
funkcję \texttt{rmqueue()}. Jeżeli znaleziono odpowiedzni blok - zwracamy
wskaźnik do zaalokowanej ramki i kończymy
\item przeszukaj i spróbuj zaalokować pamięć w strefach o dużej\footnote{
każda strefa ma ustawiony \textit{pages\_high} określający wysoki limit
na ilość wolnych ramek + nieaktywnych czystych ramek} ilości
wolnych stron + nieaktywnych czystych stron (funkcja 
\texttt{\_\_alloc\_pages\_limit()}). Jeśli sukces - kończymy
\item powtórz powyższy krok, ale z małym\footnote{
w strefie zmienna \textit{pages\_low} określa niski limit na ilość wolnych
ramek + czystych nieaktywnych w systemie} limitem wolnych + nieaktywnych czystych
stron
\item budzimy \textit{kswapd} w nadzieji, że poprawi sytuację. Oddajemy
przy tym procesor
\item przeszukujemy i próbujemy zaalokować pamięć w strefach o minimalnej
ilości wolnych + nieaktywnych czystych ramek. Jeśli znaleźliśmy blok - wychodzimy
\item jeżeli dotarliśmy do tego momentu to jesteśmy rzeczywiście ubodzy w pamięć
albo zamówienie jest duże. Teraz czyścimy brudne strony i staramy się przydzielić
pamięć. Jeśli sukces - kończymy
\item teraz już praktycznie ostatnia szansa. Wykorzystywana jest m.in. funkcja
\texttt{try\_to\_free\_pages()}, jeżeli są jeszcze jakieś szanse na wolną
pamięć to próbujemy powtórzyć cały proces alokacji raz jeszcze jeśli nie
ma już nic wolnego - kończymy z błędem
\end{enumerate}
\subsection{Zadania}
\begin{enumerate}
\item Zasymuluj działanie algorytmu alokowania bloków pamięci Buddy. Początkowy
pamięci opisuje poniższy rysunek. Po koleji alokujemy bloki
rozmiaru 1, 4, 2 jednostki. Utrzymaj odpowiednie struktury.\\
\includegraphics[width=0.7\textwidth,height=0.2\textheight]{prz1_1.eps}
\item Do alokowania pamięci Linux używa m.in. funkcji \texttt{\_\_alloc\_pages}. 
Jakż rolę odgrywa oddawanie procesora po obudzeniu \texttt{kswabd} ? Co może się
stać gdy go nie oddamy ?
\end{enumerate}
\subsection{Proponowane rozwiązania zadań}
\begin{enumerate}
\item
\begin{itemize}
\item po zaalokowaniu 1 jednostki pamięci\\
\includegraphics[width=0.7\textwidth,height=0.2\textheight]{zad1_2.eps}
\item po zaalokowaniu 4 jednostek pamięci\\
\includegraphics[width=0.7\textwidth,height=0.2\textheight]{zad1_3.eps}
\item stan końcowy - po zaalokowaniu 2 jednostek pamięci\\
\includegraphics[width=0.7\textwidth,height=0.2\textheight]{zad1_4.eps}
\end{itemize}
\item
Gdy budzimy \texttt{kswabd} oznacza to, że mamy problemy ze znalezieniem
wolnej pamięci.
Oddanie procesora daje więcej czasu dla \textit{dobrego duszka}\footnote{terminologia
zaciągnięta z opracaowań z lat wcześniejszych}, aby zwolnił
trochę pamięci.
Ponadto spowalnia to proces alokacji, a co za tym idzie daje nam większe szanse
na znalezienie żądanego bloku pamięci. Jezeli funkcja nie była wywołana z ustawioną
flagą \texttt{\_\_GFP\_IO} \texttt{kswapd} może dodatkowo zwolnić część pamięci, 
której my nie mogliśmy zwolnić samemu. Nie oddanie procesora może się
walnie przyczynić do niepowodzenia podczas alokacji pamięci.
\end{enumerate}
%
%
%free_pages()
%
%
\section{Algorytm zwalniania bloków pamięci \texttt{free\_pages}}
\subsection{Wstęp}

Do zrozumienia tego algorytmu potrzebna jest wiedza z rozdziału poprzedniego.
Zwalanianie bloków pamięci będących potęgą dwójki realizowane 
jest przez algorytm bliźniaków - Buddy.
\subsection{Struktury}
Algorytm używa tych samych struktur co \texttt{get\_free\_pages()} z poprzedniego
rozdziału.
\subsubsection{struct page}
Patrz poprzedni rozdział.
\subsubsection{free\_area\_struct}
Patrz poprzedni rozdział.
\subsection{Algorytm Buddy}
\subsubsection{Wejście}
\begin{itemize}
\item rozmiar zwalnianego bloku pamięci \textit{k} - zwalniamy blok 
o rozmiarze $2^k$ ramek
\item adres początku zwalnianego bloku \textit{a}
\item tablica rozmiaru \texttt{MAX\_ORDER}, której i-tym elementem
jest lista wolnych bloków pamięci o rozmiarze $2^i$ ramek oraz
dla każdej takiej listy mapa bitowa opisująca stan bliźniaków
\end{itemize}
\subsubsection{Działanie}
\begin{itemize}
\item zwalniamy blok pamięci wielkości $2^k$ zaczynający się w \textit{a}
\item (*) patrzymy w mapie bitowej czy bliźniak zwolnionego bloku jest wolny
(wtedy bit powinien być zapalony)
\item jeśli tak to :
\begin{itemize}
\item łączymy dwóch bliźniaków w jeden spójny blok wieklości $2^{k+1}$ -
usuwamy bliźniaka z listy wolnych bloków pamięci, odświerzamy mapę bitową
\item jeżeli blok nie ma maksymalnej wielkości poszukujemy możliwości dalszego łączenia bloków skacząc do (*).
Teraz adresem początku bloku będzie adres do lewego bliźniaka
\end{itemize}
\item bliźniak nie jest wolny - nie można już dalej łączyć - kończymy działanie
\end{itemize}
\subsubsection{Przykład}
\begin{itemize}
\item Początkowy stan pamięci :\\
\includegraphics[width=0.7\textwidth,height=0.2\textheight]{prz2_1.eps}
\item Stan po zwolnieniu 1 j. pamięci pod adresem 4\\
\includegraphics[width=0.7\textwidth,height=0.2\textheight]{prz2_2.eps}
\item Stan po zwolnieniu 2 j. pamięci pod adresem 6\\
\includegraphics[width=0.7\textwidth,height=0.2\textheight]{prz2_3.eps}
\end{itemize}

\subsection{\texttt{free\_pages()}}
\subsubsection{Wstęp}
Funkcja ta śłuży do zwalniania spójnego bloku pamięci wielkości $2^{order}$
ramek. Początek zwalnianej pamięci ma adres \textit{addr} - jest to adres
z wirtualnej pamięci jądra.
Jest to bardzo krótka funkcja więc zaprezentuję jej kod :
\subsubsection{Kod źródłowy}
\begin{flushleft}
\verb%void free_pages(unsigned long addr, unsigned long order)%
\\* \verb%{%
\\* \verb%        if (addr != 0)%
\\* \verb%                __free_pages(virt_to_page(addr), order);%
\\* \verb%}%
\end{flushleft}
\subsubsection{Działanie}
Jeżeli adres jest niezerowy funkcja wywołuje \texttt{\_\_free\_pages()}
podając jako wejście wskaźnik do ramki, która leży pod adresem \textit{addr}
i rozmiar zwalnianego bloku.
\subsection{\texttt{\_\_free\_pages()}}
\subsubsection{Kod źródłowy}
\begin{flushleft}
\verb%void __free_pages(struct page *page, unsigned long order)%
\\* \verb%{%
\\* \verb%        if (!PageReserved(page) && put_page_testzero(page))%
\\* \verb%                __free_pages_ok(page, order);%
\\* \verb%}%
\end{flushleft}
\subsubsection{Działanie}
\texttt{\_\_free\_pages()} sprawdza czy można zwolnić ramkę
wskazywaną przez \textit{page}
\begin{itemize}
\item jeśli można to wywołuje 
\texttt{\_\_free\_pages\_ok()}, która zrealizuje algorytm bliźniaków
\item wpp. kończy działanie
\end{itemize}
\subsection{\texttt{\_\_free\_pages\_ok()}}
\subsubsection{Wstęp}
%Nagłówek funkcji :
%\begin{flushleft}
%\verb%static void __free_pages_ok (struct page *page, unsigned long order)%
%\end{flushleft}
Czytanie kodu źródłowego tej funkcji
potrafi spędzić sen z powiek nie jednego programisty\footnote{zachęcają
do tego liczne komentarze w kodzie źródłowym m.in. 
"\textit{You really aren't expected to understand this}"}. Jak widąć funkcja
posiada takie samo wejście i wyjście jak funkcja ją wywołująca.
\subsubsection{Nagłówek}
\begin{flushleft}
\verb%static void __free_pages_ok (struct page *page, unsigned long order)%
\end{flushleft}
\subsubsection{Działanie}
Funkcja realizuje algorytm Buddy. Dodatkowo wykonuje pare innych
operacji jak np. zapewnienie atomowości operacji. Nie prezentuję
kodu źródłowego gdyź jest on duży i mało zrozumiały - nie to jest
celem tej pracy. Zainteresowanych odsyłam do pliku \texttt{mm/page\_alloc.c}.
Aby ułatwić zrozumienie kodu podam parę wskazówek :
\subsubsection{Wskazówki}
\begin{itemize}
\item \textit{page\_idx} - indeks ramki
\item \textit{index} - indeks badanego bloku pamięci w mapie bitowej
\item 
\verb%page_idx ^ - mask%
 = numer bliźniaka ramki o numerze
\textit{page\_idx}
\end{itemize}
\subsection{Zadania}
\begin{enumerate}
\item
Jeżeli maksymalny zamówienia wnosi $2^{MAX\_ORDER}$ ramek,
ilość pamięci w badanej strefie - $2^{MEM\_SIZE}$ ramek -
ile operacji łączenia bliźniaczych bloków moźe maksymalnie wystąpić przy
zwalnianiu bloku pamięci o rozmiarze $2^{k}$ ramek 
(0 <= \textit{k} <= min(\texttt{MAX\_ORDER}, \texttt{MEM\_SIZE}))?
\item
Algorytm bliźniakow podczas alokowania spójnego bloku pamięci wielkości $2^{order}$
rozpoczyna poszukiwania od blokow o wielkosci $2^{order}$, a gdy nie ma takowych wolnych
zaczyna poszukiwać bloków o podwojonej wielkości. Czy taka polityka jest
zawsze lepsza niż próba "wyrwania" zadanego bloku z maksymalnie dużego bloku
pamięci? Które rozwiazanie jest lepsze w średnim przypyadku? Jakie mogą być
konsekwencje zastosowania drugiego rozwiazania ?
\end{enumerate}
\subsection{Proponowane rozwiązania zadań}
\begin{enumerate}
\item
Wzór na maksymalną liczbę operacji łączenia bloków prezentuje się następująco:

\textit{liczba operacji} = min(\texttt{MAX\_ORDER}, \texttt{MEM\_SIZE}) - \textit{k}
\\
Największy spójny blok pamięci może mieć rozmiar $2^{min(\texttt{MAX\_ORDER}, \texttt{MEM\_SIZE})}$,
rozmiar zwalnianego bloku to $2^k$, przy każdym złączeniu rozmiar bloku
zwiększa się dwukrotnie tak więc, aby osiągnść maksymalny rozmiar potrzebuje
\textit{liczba operacji} łączeń.
\item 
Standardowy algorytm bliźniaków z reguły działa lepiej aniżeli wersja 
z szukaniem wolnych obszarów od największych "w dół". Istnieją jednak 
scenariusze kiedy proponowana wersja wypada lepiej. Początkowa stan
pamięci :\\
\includegraphics[width=0.7\textwidth,height=0.2\textheight]{zad3_1.eps}
\\
Do systemu zgłaszają się 3 procesy. Oto ich żądania dotyczące pamięci :
p1, p2, p3 żądają po 4j. pamięci, następnie procesy p1 i p2 oddają zaalokowaną
pamięć. W ostatecznym kroku proces p1 żąda 8j. pamięci. 
\begin{itemize}
\item stan pamięci, gdy wykorzystywano przeszukiwanie bloków "w dół" (niestandardowo)\\
\includegraphics[width=0.7\textwidth,height=0.2\textheight]{zad3_2.eps}
\item używamy standardowego algorytmu bliźniaków. System nie może zraelizować
ostaniego żądania - nie ma spójnego bloku tej wielkości, który można
zaalokować. Pamięć wygląda tak :\\
\includegraphics[width=0.7\textwidth,height=0.2\textheight]{zad3_3.eps}
\\
Wprawdzie w pamięci jest spójny blok wielkości 8, ale nie możemy zaalokować
jednym zamówieniem.
\end{itemize}
Konsekwencje stosowania 2. rozwiązania : szybko może dojść do dużej fragmentacji
pamięci, będzie bardzo ciężko znaleźć większy spójny blok.
\end{enumerate}
\end{document}
