Rozważmy następujące stategie przydziału pamięci w sposób ciągły:
Pokaż trzy przykłady ciągów działań, dla których każda z tych stategii okaże się lepsza od pozostałych. W każdym przykładzie podaj zapotrzebowanie na pamięć, określ kiedy pamięć jest zajmowana i zwalniana, a także podaj wielkość pamięci traconej w wyniku fragmentacji.
Przy okazji przyjrzyjmy się wadom i zaletom poszczególnych strategii. Porównajmy algorytmy, starając się dla każdego wskazać, w jakich sytuacjach będzie miał przewagę nad innymi, a w jakich będzie się zachowywał gorzej. Weźmy pod uwagę także narzut systemowy każdej z nich (np. sposób przechowywania informacji o wolnych obszarach pamięci i czas przeglądania tych danych).
Dostępna pamięć to spójny blok 2000B (2 kawałki po 1000B). Ciąg żądań:
X:=alloc(900B), Y:=alloc(900B), release(X), Z:=alloc(1000B)
Podany ciąg żądań zostanie bez czekania obsłużony tylko przez metodę stref statycznych. W przypadku stref dynamicznych - mimo, że pozostanie 1100B wolnej pamięci, to nie może ona być wykorzystana do spełnienia ostatniego żądania ze względu na fragmentację zewnętrzną.
Dostępna pamięć to spójny kawałek wielkości 400B. Ciąg żądań:
X:=alloc(200B), Y:=alloc(100B), release(X),
X:=alloc(50B), Z:=alloc(150B), W:=alloc(100B)
W przypadku metody pierwszy pasujący ten ciąg zostanie obsłużony bez czekania. Ze względu na fragmentację zewnętrzną (100B), w przypadku metody najlepszy pasujący ostatnie żądanie nie zostanie wykonane od razu. W strategii stref statycznych musielibyśmy mieć strefy wielkości 200B (żeby móc obsłużyć największe żądanie). W takiej sytuacji nie można przydzielić dwóch ostatnich fragmentów,
a fragmentacja wewnętrzna wynosi 250B.
Jak poprzednio dostępna pamięć to spójny blok wielkości 400B. Ciąg żądań:
X:=alloc(200B),Y:=alloc(100B), release(X),
X:=alloc(50B), Z:=alloc(50B), W:=alloc(200B)
W przypadku metody najlepiej pasujący ten ciąg zostanie obsłużony bez czekania. Ze względu na fragmentację zewnętrzną (200B) w przypadku metody pierwszy pasujący ostatnie żądanie nie zostanie wykonane od razu. Dla stref statycznych jest tak samo jak w poprzednim punkcie.
Rozważmy teraz system, w którym pamięć podzielona jest na strony. Załóżmy, że tablica stron jest przechowywana w pamięci głównej, czas dostępu do tej pamięci wynosi t.
Rozwiązanie
Przypuśćmy, że zawartość tablicy stron dla aktualnie wykonywanego procesu jest następująca:
| Numer strony | Numer ramki |
|---|---|
| 0 | - |
| 1 | 4 |
| 2 | - |
| 3 | 2 |
| 4 | 1 |
| 5 | 0 |
Strony i ramki są numerowane od zera, adresy są adresami bajtów w pamięci, a strona ma rozmiar 1024 bajty.
Jakim adresom fizycznym odpowiadają podane adresy wirtualne (nie należy obsługiwać błędów braku strony):
W pewnym systemie ze stronicowaniem: strona ma rozmiar 512 bajtów, pozycja w tablicy stron (adres) zajmuje 4 bajty, a tablica stron dowolnego poziomu zajmuje 1 stronę.
64KB > 8KB, czyli do zarządzania pamięcią o rozmiarze 8KB wystarczy stronicowanie 1-poziomowe.
Załóżmy, że funkcja mem(x) przekazuje liczbę 32-bitową, znajdującą się pod adresem x wyrażonym w bajtach. Napisz funkcję f(x), która dla założeń z poprzedniego zadania i 3 poziomów stronicowania przekształca adres liniowy w adres fizyczny. Przyjmij, że zmienna R przechowuje adres bazowy katalogu 3-ciego poziomu.
Struktura adresu liniowego dla podanych założeń
| 2 zarezerwowane bity | indeks 3 poziomu (7 bitów) |
indeks 2 poziomu (7 bitów) |
indeks 1 poziomu (7 bitów) |
przesunięcie (najmłodsze 9 bitów) |
Skorzystamy z poniższych makr:
#define PAGE_SIZE 512
#define CATALOG_BITS 7
#define DIRECTORY_BITS 7
#define TABLE_BITS 7
#define OFFSET_BITS 9
#define CATALOG_FIRST_BIT (DIRECTORY_BITS+TABLE_BITS+OFFSET_BITS)
#define DIRECTORY_FIRST_BIT (TABLE_BITS+OFFSET_BITS)
#define TABLE_FIRST_BIT (OFFSET_BITS)
#define SIZE_OF_CATALOG_ENTRY 4
#define SIZE_OF_DIRECTORY_ENTRY 4
#define SIZE_OF_TABLE_ENTRY 4
#define OFFSET_MASK ~(~0 << OFFSET_BITS)
#define getbits(x, start_position, field_size) ((x >> start_position) & (~(~0 << field_size)))
Makro getbits przekazuje pole o długości field_size wycięte z x od pozycji start_position, dosunięte to prawej strony. Przyjmujemy, że zerową pozycją bitu jest prawy koniec x.
Na przykład, getbits(x, 4, 3) przekazuje 3 bity - z pozycji 4, 5 i 6 dosunięte do prawej strony wyniku.
Oto funkcja f tłumacząca adres liniowy na adres fizyczny:
u32 f(u32 lin_addr) {
u32 address, offset;
/* wyznaczam indeks w katalogu stron najwyższego (tzn. trzeciego) poziomu */
offset = getbits(lin_addr, CATALOG_FIRST_BIT, CATALOG_BITS);
/* wyznaczam adres katalogu stron drugiego poziomu */
address = mem(R + SIZE_OF_DIRECTORY_ENTRY * offset);
/* wyznaczam indeks w katalogu stron drugiego poziomu */
offset = getbits(lin_addr, DIRECTORY_FIRST_BIT, DIRECTORY_BITS);
/* wyznaczam adres tablicy stron (pierwszy poziom) */
address = mem(address + SIZE_OF_DIRECTORY_ENTRY * offset);
/* wyznaczam indeks w tablicy stron */
offset = getbits(lin_addr, TABLE_FIRST_BIT, TABLE_BITS);
/* wyznaczam adres strony */
address = mem(address + SIZE_OF_TABLE_ENTRY * offset);
address *= PAGE_SIZE;
return address + (lin_addr & OFFSET_MASK);
}
Algorytm bliźniaków
Funkcja alloc_pages() (wykorzystywana między innymi przez kmalloc()) służy do przydzielania spójnych fragmentów pamięci na potrzeby jądra w systemach uniksowych.
Pamięć jest przydzielana i zwalniana w blokach o rozmiarze 2i ramek (i=0..MAX_ORDER-1).
Zarządzanie przydziałem i zwalnianiem wolnych fragmentów pamięci jest oparte na algorytmie bliźniaków (w literaturze angielskojęzycznej: buddy algorithm).
System przechowuje tablicę list adresów wolnych obszarów pamięci fizycznej o różnych
rozmiarach. Pierwsza lista zawiera obszary pamięci o wielkości jednej strony, a ostatnia o wielkości 2MAX_ORDER-1 stron. Każdy taki fragment pamięci, mimo że może składać się z wielu stron, jest spójnym blokiem pamięci fizycznej.
Zajmowanie obszaru o rozmiarze 2i
Szukanie obszaru do przydzielenia zaczyna się od listy i-tej. Jeśli nie jest ona pusta, to wyjmemy z niej jeden element i przekazujemy go
jako wynik funkcji. Jeśli lista jest pusta, to szukamy najbliższej niepustej listy zawierającej większe obszary pamięci i z niej wyjmujemy jeden element. Ponieważ znaleziony obszar jest większy od poszukiwanego, więc należy go podzielić. Dzielimy go zatem na połowy dopóty, dopóki otrzymany fragment jest żądanej wielkości. Pozostałe po dzieleniu obszary wstawanie są do odpowiednich list.
Zwalnianie obszaru o rozmiarze 2i
Zwalniany obszar musiał być kiedyś przydzielony, czyli musiał być wydzielony z bloku dwa razy większego. Być może jego bliźniak (czyli druga połowa tego większego bloku) też jest wolny i dwa bliźniacze obszary będzie można połączyć w jeden większy spójny obszar. Jeśli to się uda, to można szukać bliźniaka dla tego większego fragmentu itd. Postępuje się tak aż do momentu, kiedy szukany bliźniak okaże się być zajęty (lub cała dostępna pamięć jest wolna) i dodaje się utworzony blok do odpowiedniej listy, a także aktualizuje informacje o przynależności obszarów do pozostałych list.
Analiza
Zaletą algorytmu bliźniaków jest to, że jest on elastyczny i zapobiega fragmentacji, ponieważ te same fragmenty pamięci są wykorzystywane w obszarach o różnym rozmiarze. Jego wadą może wydawać się wydajność z uwagi na konieczność dzielenia i scalania obszarów.
Z drugiej strony dzięki indeksowaniu tablicy obszarów potęgami dwójki, większość operacji arytmetycznych polega na przesunięciu dwójkowym lub zamianie bitu, więc są one bardzo szybkie.
Zadanie
Przyjmiemy dla uproszczenia, że MAX_ORDER=5. W rzeczywistości jest to większa wartość: we współczesnych systemach Linux wynosi ona 11. Początkowo cała dostępna pamięć jest wolna i tworzy spójny obszar o rozmiarze 16 ramek o adresach od 0 do 15.
Jaka będzie odpowiedź, jeżeli zmienimy kolejność kroków (4) i (5)?
Jaki ciąg zleceń powoduje najgorsze możliwe zachowanie algorytmu bliźniaków?
| 4 | -> 0 | 3 | | 2 | | 1 | | 0 |
Sytuacja po operacji A:=allocate(1) :
| 4 | | 3 | -> 8 | 2 | -> 4 | 1 | -> 2 | 0 | -> 1
Sytuacja po operacji B:=allocate(2) :
| 4 | | 3 | -> 8 | 2 | -> 4 | 1 | | 0 | -> 1
Sytuacja po operacji C:=allocate(2) :
| 4 | | 3 | -> 8 | 2 | | 1 | -> 6 | 0 | -> 1
Sytuacja po operacji release(A) :
| 4 | | 3 | -> 8 | 2 | | 1 | -> 0, 6 | 0 |
Fragmenty o adresach 0 i 6 nie są bliźniakami, ponieważ nie tworzą spójnego obszaru.
Sytuacja po operacji D:=allocate(2) :
| 4 | | 3 | -> 8 | 2 | | 1 | -> 6 | 0 |
Jeśli zamienimy kolejność ostatnich 2 operacji, to otrzymamy:
Sytuacja po operacji D:=allocate(2) :
| 4 | | 3 | -> 8 | 2 | | 1 | | 0 | -> 1
Sytuacja po operacji release(A) :
| 4 | | 3 | -> 8 | 2 | | 1 | -> 0 | 0 |
Oblicz optymalny rozmiar strony minimalizujący fragmentację wewnętrzną.
(Wg. Brinch Hansena)
Niech p oznacza rozmiar strony (w słowach), a s przeciętny rozmiar programu (w słowach). Na każdą stronę potrzeba jednej pozycji w tablicy stron, a więc s/p pozycji. Średnio jest marnowana połowa (ostatniej) strony, a więc p/2. Optymalny rozmiar strony (minimalizujący fragmentację wewnętrzną) można zatem opisać wzorem:
f(p)=(p/2 + s/p)/s = p/2s + 1/p
f(p)' = 1/2s - 1/(p ^ 2)
f(p)' = 0 dla p = sqrt(2s), f(sqrt(2s)) = sqrt(2/s)
Wnioski: duża strona oznacza większe straty wynikające z niewykorzystania reszty ostatniej strony, ale mniejsze straty wynikające z rozmiaru tablicy stron. Warto też skomentować rozmiar strony w kontekście czasu poświęcanego na transmisje wejścia-wyjścia: im większa strona, tym narzuty w przeliczeniu na bajt są mniejsze) oraz w kontekście "fragmentacji logicznej" (ściągamy do pamięci większą stronę, potencjalnie ryzykujemy, że zawiera ona więcej niepotrzebnych bajtów).
(Jeszcze raz algorytm bliźniaków)
Zakładając, że MAX_ORDER=6 i początkowo cała wolna pamięć tworzy spójny obszar o rozmiarze 32 ramki, opisz stan pamięci po wykonaniu każdej z następujących operacji:
getpages(2); getpages(1); getpages(2); getpages(2);
freepages(8,2); freepages(4,1); freepages(0,2)Funkcja getpages(i) przydziela blok o rozmiarze i ramek, natomiast funkcja freepages(k,i) zwalnia blok rozpoczynający się od strony o numerze k i o rozmiarze i ramek. Ramki są numerowane od 0. Spośród dwóch obszarów uzyskanych w wyniku podziału zajmowany jest ten o mniejszym adresie.
Sytuacja początkowa:
| 5 | -> 0 | 4 | | 3 | | 2 | | 1 | | 0 |
Sytuacja po operacji getpages(2) :
| 5 | | 4 | -> 16 | 3 | -> 8 | 2 | -> 4 | 1 | -> 2 | 0 |
Sytuacja po operacji getpages(1) :
| 5 | | 4 | -> 16 | 3 | -> 8 | 2 | -> 4 | 1 | | 0 | -> 3
Sytuacja po operacji getpages(2) :
| 5 | | 4 | -> 16 | 3 | -> 8 | 2 | | 1 | -> 6 | 0 | -> 3
Sytuacja po operacji getpages(2) :
| 5 | | 4 | -> 16 | 3 | -> 8 | 2 | | 1 | | 0 | -> 3
Sytuacja po operacji freepages(6,2) :
| 5 | | 4 | -> 16 | 3 | -> 8 | 2 | | 1 | -> 6 | 0 | -> 3
Sytuacja po operacji freepages(4,1) :
| 5 | | 4 | -> 16 | 3 | -> 8 | 2 | | 1 | -> 6 | 0 | -> 3, 4
Fragmenty o adresach 3 i 4 nie są bliźniakami mimo, że tworzą spójnego obsza, ponieważ nie można z nich zbudować obszaru dwa razy większego o wyrównanym adresie.
Sytuacja po operacji freepages(0,2) :
| 5 | | 4 | -> 16 | 3 | -> 8 | 2 | | 1 | -> 0, 6 | 0 | -> 3, 4
Niech index_of_page oznacza indeks strony w tablicy ramek, index_of_buddy oznacza indeks bliźniaka, a order rząd, gdzie rozmiar wolnego obszaru w systemie bliźniaków to 2^order ramek. W jaki sposób obliczamy indeks bliźniaka? Wypełnij puste pola podanej tabeli:
index_of_page: 0 1 2 3 0 2 0 index_of_buddy: order: 0 0 0 0 1 1 2
Indeks bliźniaka wylicza się za pomocą formuły:
index_of_buddy = index_of_page XOR (1 << order).
index_of_page: 0 1 2 3 0 2 0 index_of_buddy: 1 0 3 2 2 0 4 order: 0 0 0 0 1 1 2
Zapisz formułę wyznaczającą dla obszaru o indeksie index_of_page rzędu order indeks zawierającego go bliźniaka rzędu order + 1. Sprawdź jej działanie dla przykładowych danych.
index_of_parent = index_of_page & ~(1 << order)
index_of_page: 0 1 2 3 0 2 0 index_of_parent: 0 0 2 2 0 0 0 order: 0 0 0 0 1 1 2