Ćwiczenie 1
Wskazać ciąg zadań, dla którego byłby najwłaściwszy tylko jeden z podanych algorytmów podziału na strefy:
Każde zadanie powinno być opisane przez podanie zapotrzebowania na pamięć główną oraz określenie czasu wykonania.
Porównać 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. Zadanie powinno być jedynie pretekstem do bardziej szczegółowego przyjrzenia się wadom i zaletom poszczególnych strategii. W tym kontekście należy również rozważyć narzut systemowy każdej z nich (np. sposób przechowywania informacji o wolnych obszarach pamięci i czas przeglądania tych danych).
Rozwiązanie
Przykład, gdy najwłaściwszy jest przydział metodą stref statycznych: 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.
Przykład ciągu żądań, dla którego najbardziej odpowiedni jest przydział metodą pierwszy pasujący. Zakładam, że 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ą, w przypadku metody najlepszy pasujący ostatnie żądanie nie zostanie wykonane od razu.
Przykład ciągu żądań, dla którego najwłaściwszy jest przydział metodą najlepszy pasujący. Zakładamy jak poprzednio, że 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 najlepszy pasujący ten ciąg zostanie obsłużony bez czekania. Ze względu na fragmentację zewnętrzną, w przypadku metody pierwszy pasujący ostatnie żądanie nie zostanie wykonane od razu.
Ćwiczenie 2
Wyjaśnić pojęcie fragmentacji wewnętrznej i zewnętrznej. Znaleźć optymalny rozmiar strony minimalizujący fragmentację wewnętrzną.
Rozwiązanie
Np. wg Brinch Hansena, str. 182.
Niech p - 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)' = 0 => p = sqrt(2s) => f(sqrt(2s)) = sqrt(2/s)
Wniosek: duża strona to 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).
Ćwiczenie 3
Rozważmy system z pamięcią wirtualną ze stronicowaniem. Załóżmy również, że tablica stron jest przechowywana w pamięci głównej, a czas dostępu do tej pamięci wynosi 1.2 mikrosekundę.
Rozwiązanie
Ćwiczenie 4
Załóżmy, że w pewnym systemie z pamięcią wirtualną i stronicowaniem strona ma rozmiar 512 bajtów, pozycja w tablicy stron zajmuje 4 bajty, a tablica stron dowolnego poziomu zajmuje 1 stronę.
Ile poziomów stronicowania musi zapewnić mechanizm adresacji, aby było możliwe zarządzanie pamięcią o rozmiarze:
Ile potrzeba bitów do zaadresowania 1 komórki pamięci i w jaki sposob zależy ona od liczby poziomów stronicowania?
Załóżmy, że funkcja mem(x) przekazuje liczbę 32-bitową, znajdującą się pod adresem x, wyrażoną w bajtach. Napisz funkcję f(x), która dla podanych założeń przekształca adres liniowy w adres fizyczny.
Rozwiązanie
Odpowiedź na pytanie 1:
Liczba pozycji w tablicy stron to 512/4 = 128.
Stronicowanie 1-poziomowe: 128*512B = 64KB > 8KB, czyli do zarządzania pamięcią o rozmiarze 8KB wystarczy stronicowanie 1-poziomowe.
Stronicowanie 3-poziomowe: (128^3)*512B = 1GB czyli aby zarządzać pamięcią o rozmiarze 1GB konieczne są 3 poziomy stronicowania.
Odpowiedź na pytanie 2:
Do zaadresowania pamięci o rozmiarze 2^k potrzeba k bitów i nie zależy to od liczby poziomów stronicowania. Jeśli n to liczba poziomów adresowania, to dla podanych założeń adres liniowy ma postać (7*n + 9) bitów i pozwala zaadresować 2^(7*n + 9) bajtów (bo 512 = 2^9, 128 = 2^7).
Odpowiedź na pytanie 3:
Zakładam, że są 3 poziomy stronicowania.
Struktura adresu liniowego
| 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 PAGE_CATALOG_BITS 7 #define PAGE_DIRECTORY_BITS 7 #define PAGE_TABLE_BITS 7 #define PAGE_OFFSET_BITS 9 #define PAGE_CATALOG_FIRST_BIT \ (PAGE_DIRECTORY_BITS+PAGE_TABLE_BITS+PAGE_OFFSET_BITS) #define PAGE_DIRECTORY_FIRST_BIT \ (PAGE_TABLE_BITS+PAGE_OFFSET_BITS) #define PAGE_TABLE_FIRST_BIT \ (PAGE_OFFSET_BITS) #define SIZE_OF_PAGE_CATALOG_ENTRY 4 #define SIZE_OF_PAGE_DIRECTORY_ENTRY 4 #define SIZE_OF_PAGE_TABLE_ENTRY 4 #define PAGE_OFFSET_MASK \ ~(~0 << PAGE_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 tu ż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, PAGE_CATALOG_FIRST_BIT, PAGE_CATALOG_BITS);
/* wyznaczam adres katalogu stron drugiego poziomu */
/* zakładam, że zmienna R przechowuje adres bazowy katalogu 3ciego poziomu */
address = mem(R + SIZE_OF_PAGE_DIRECTORY_ENTRY*offset);
/* wyznaczam indeks w katalogu stron drugiego poziomu */
offset = getbits(lin_addr, PAGE_DIRECTORY_FIRST_BIT, PAGE_DIRECTORY_BITS);
/* wyznaczam adres tablicy stron */
address = mem(address + SIZE_OF_PAGE_DIRECTORY_ENTRY*offset);
/* wyznaczam indeks w tablicy stron */
offset = getbits(lin_addr, PAGE_TABLE_FIRST_BIT, PAGE_TABLE_BITS);
/* wyznaczam adres strony */
address = mem(address + SIZE_OF_PAGE_TABLE_ENTRY*offset);
address *= PAGE_SIZE;
return address + (lin_addr & PAGE_OFFSET_MASK);
}
Ćwiczenie 5
Przedstaw interpretację adresu liniowego 2e97a01c (szesnastkowo) w procesorze i386.
Oto zawartość tablicy stron dla aktualnie wykonywanego procesu (wszystkie liczby są dziesiętne, wszystko jest numerowane od zera i wszystkie adresy są adresami bajtów w pamięci; strona ma rozmiar 1024 bajty):
| Numer strony | Bit poprawności odwołania | Bit odwołania | Bit modyfikacji | Numer ramki |
| 0 | ? | 1 | 1 | - |
| 1 | ? | 0 | 0 | 4 |
| 2 | ? | 0 | 0 | - |
| 3 | ? | 0 | 0 | 2 |
| 4 | ? | 0 | 0 | 1 |
| 5 | ? | 0 | 1 | 0 |
Zadania 6-7 są podobne, na ćwiczeniach wystarczy zrobić przynajmniej jedno z nich (do wyboru).
Ćwiczenie 6
W pewnym komputerze pamięć operacyjna dostępna dla użytkownika składa się z ramek o numerach 0..15. Zarządzanie przydziałem i zwalnianiem wolnych ramek oparte jest na metodzie bliźniaków stosowanej w Linuksie. Załóżmy, że początkowo cała pamięć była wolna, a następnie wykonane zostały żądania:
Opisz zawartość list wolnych bloków po każdym kroku. Zakładamy, że listy wolnych bloków są uporządkowane wg adresów początkowych bloków. Jaka będzie stan bitu PG_BUDDY i rozmiar ('order') pamiętany w polu private dla ramek w tej pamięci przed pierwszą i po ostatniej operacji?
Jaka będzie odpowiedź, jeżeli zmienimy kolejność kroków (4) i (5)?
Rozwiązanie ćwiczenia nr 6
Sytuacja początkowa:
| 4 | -> 0
| 3 |
| 2 |
| 1 |
| 0 |
indeks: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
order: 4 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0
PG_BUDDY: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
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 |
Sytuacja po operacji D:=allocate(2) :
| 4 |
| 3 | -> 8
| 2 |
| 1 | -> 6
| 0 |
indeks: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
order: 1 0 3 0 1 0 2 0 1 0
PG_BUDDY: 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
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 |
Ćwiczenie 7
W pewnym systemie operacyjnym alokacja pamięci w obrębie strony o wielkości 1 KB opiera się na algorytmie bliźniaków. W ten sposób mogą być przydzielone bufory o wielkościach 32, 64, ..., 512 bajtów. Alokator utrzymuje mapę pamięci przeznaczając 1 bit na każdy 32-bajtowy fragment (0 = wolny, 1 = zajęty). Mając daną mapę strony:
1111 1111 0000 1100 1111 0000 0000 0000
odtwórz stan listy wolnych buforów (dla każdego bufora podaj przesunięcie na stronie). Co stanie się po wykonaniu polecenia release(a+384, 64), gdzie a jest adresem początkowym strony?
Ćwiczenie 7b (egz. 2002/03)
W pewnym systemie operacyjnym alokacja pamięci w obrębie strony o wielkości 1 KB opiera się na algorytmie bliźniaków. W ten sposób mogą być przydzielone bloki o wielkościach 32, 64, ..., 512 bajtów. Oto mapa strony opisująca stan każdego bloku o rozmiarze 32-bajtów (0 = wolny, 1 = zajęty):
1111 0100 1100 1100 0000 0000 0000 0000
Odtwórz szczegółowo stan struktur danych utrzymywanych przez alokator pamięci (listy wolnych bloków i pola w tablicy ramek). Wskaż zmiany jakie zajdą w tych strukturach po wykonaniu każdego z następujących żądań (adresy są podawane w odniesieniu do początku strony, release(adres, rozmiar), allocate(rozmiar)):
allocate(128)
release(160, 32)
release(256, 64)
allocate(64)
Ćwiczenie 8
W systemie Linux stosuje się metodę bliźniaków do zarządzania wolnymi ramkami pamięci. Ramki mogą być przydzielane i zwalniane w blokach o rozmiarze 2i ramek (i=0..N-1). Zakładając, że N=6 i początkowo cała wolna pamięć tworzy spójny obszar o rozmiarze 32 ramki, opisz stan pamięci (tj. zawartość tablicy list wolnych bloków i odpowiednich pól w tablicy ramek) po wykonaniu nast. 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.
Ćwiczenie 9a
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 stron. 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
Rozwiązanie
Indeks bliźniaka wylicza się za pomocą formuły: index_of_buddy = index_of_page XOR (1 << order).
Ćwiczenie 9b
Napisz kod funkcji, która przekazuje ramkę będącą początkiem bliźniaka.
Rozwiązanie
static inline struct page *
__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
{
unsigned long buddy_idx = page_idx ^ (1 << order);
return page + (buddy_idx - page_idx);
}
Ćwiczenie 10
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. Napisz funkcję wyliczającą wartość formuły.
Rozwiązanie
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
static inline unsigned long
__find_combined_index(unsigned long page_idx, unsigned int order)
{
return (page_idx & ~(1 << order));
}
Ćwiczenie 11
Mając dane treści pomocniczych makr i funkcji napisać funkcję __free_one_page(struct page *page, struct zone *zone, unsigned int order), która powoduje zwolnienie obszaru zaczynającego się od ramki page rzędu order w strefie zone.
Obsługa flagi PG_BUDDY we wskazanej ramce.
#define PageBuddy(page) test_bit(PG_buddy, &(page)->flags)
#define __SetPageBuddy(page) __set_bit(PG_buddy, &(page)->flags)
#define __ClearPageBuddy(page) __clear_bit(PG_buddy, &(page)->flags)
Obsługa pola private we wskazanej ramce, określającego rząd wolnego obszaru (czyli jego rozmiar w liczbie ramek).
static inline unsigned long page_order(struct page *page)
{
return page->private;
}
static inline void set_page_order(struct page *page, int order)
{
page->private = order;
__SetPageBuddy(page);
}
static inline void rmv_page_order(struct page *page)
{
__ClearPageBuddy(page);
page->private = 0;
}
Czy mój bliźniak jest wolny i mogę się z nim połączyć w większy obszar?
static inline int page_is_buddy(struct page *page, int order)
{
if (PageBuddy(page) && page_order(page) == order) {
BUG_ON(page_count(page) != 0);
return 1;
}
return 0;
}
Rozwiązanie
Jest to oczywiście wersja lekko uproszczona.
static inline void __free_one_page(struct page *page,
struct zone *zone, unsigned int order)
{
unsigned long page_idx;
int order_size = 1 << order;
page_idx = page & ((1 << MAX_ORDER) - 1);
// zwiększa się liczba wolnych ramek w strefie
zone->free_pages += order_size;
// przeglądamy listy wolnych obszarów
while (order < MAX_ORDER-1) {
unsigned long combined_idx;
struct free_area *area;
struct page *buddy;
// ustalamy adres bliźniaka
buddy = __page_find_buddy(page, page_idx, order);
// czy to faktycznie bliźniak (ma taki sam order) i czy jest wolny
// (ma ustawiony bit PG_BUDDY)
if (!page_is_buddy(buddy, order))
// jeśli nie, to trzeba go dołączyć do aktualnej listy
break; /* Move the buddy up one level. */
// jeśli tak, to można połączyć dwa bliźniaki w obszar o wyższym rzędzie
list_del(&buddy->lru);
area = zone->free_area + order;
area->nr_free--;
rmv_page_order(buddy);
// wyznacz adres bliźniaka rzędu order + 1
combined_idx = __find_combined_index(page_idx, order);
page = page + (combined_idx - page_idx);
page_idx = combined_idx;
order++;
}
set_page_order(page, order);
list_add(&page->lru, &zone->free_area[order].free_list);
zone->free_area[order].nr_free++;
}
| ©Janina Mincer-Daszkiewicz |