SYSTEMY OPERACYJNE (LAB)
Lista 4  Pamięć wirtualna/Algorytmy zastępowania stron
termin oddawania to 5 V 2016
Uwaga: Zadania 1-4 nie wymagają implementacji i ich rozwiązanie wystarczy na ocenę dst.
Zadanie 11 (1pkt)
Rozważmy następujący strumień odwołań do siedmiu różnych stron:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Załóżmy, że mamy jedną, dwie, trzy, cztery, pięć, cześć lub siedem ramek.
Wszystkie ramki są początkowo puste, co oznacza, że pierwsze kontakty z nowymi
stronami będą zawsze powodowały po jednym braku strony.
Wyznacz liczbę braków stron dla następujących algorytmów zastępowania (ang.
page replacement algorithms):
ć% zastępowanie algorytmem LRU (ang. least recently used);
ć% zastępowanie algorytmem FIFO (ang. First-In-First-Out);
ć% zastępowanie optymalne.
Zadanie 2 (2pkt)
Jednym z podstawowych algorytmów zastępowania stron jest algorytm
zegarowy (ang. clock policy), nazywany też algorytmem drugiej szansy.
W algorytmie tym najczęściej do realizacji zastępowania stron jest używany bufor
cykliczny (ang. circular buffer) składający się z n-1 ramek a każdej ramce przypisuje
się dodatkowy bit, nazywany bitem wykorzystania (ang. use bit). Zapoznaj się
z mechanizmem realizującym strategię zegarową.
Rozważ następujący strumień adresów stron:
2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2.
Ustaw w dowolny sposób bity odniesienia i przedstaw funkcjonowanie tej strategii.
Czym różni się ta strategia od algorytmu FIFO? Kiedy obie strategie są zgodne?
Czy ten algorytm można ulepszyć? Jak?
1 A. Silberschatz, J.L. Peterson, G. Gagne, Podstawy systemów operacyjnych. Wydanie VII, WNT, 2005, str. 426
minima punktowe na poszczególne oceny: dst - 5pkt, db - 7pkt, bdb - 9pkt
Zadanie 32 (1pkt)
Dowiedz się, na czym polega anomalia Belady'ego. Wskaż, które z poniższych
algorytmów są na nią podatne, a które jej nie ulegają:
" algorytm LRU;
" algorytm FIFO;
" zastępowanie optymalne;
" zastępowanie metodą zegarową (drugiej szansy).
Zadanie 43 (1pkt)
Proces zawiera osiem stron wirtualnych na dysku. Alokowano dla niego cztery
ramki stron w pamięci operacyjnej, które początkowo są puste. Oto ślady odwołań do
stron:
1, 0, 2, 2, 1, 7, 6, 7, 0, 1, 2, 0, 3, 0, 4, 5, 1, 5, 2, 4, 5, 6, 7, 6, 7, 2, 4, 2, 7, 3, 3, 2, 3
Pokaż ślady kolejnych stron znajdujących się w czterech ramkach, wyznacz
oraz porównaj współczynniki trafień (ang. hit ratio) w pamięci operacyjnej przy
zastosowaniu algorytmów:
" LRU;
" FIFO;
Zadanie 5 (5pkt) // https://www.ii.pwr.edu.pl/~juszczyszyn/so.htm
Należy samodzielnie sformułować założenia symulacji w zakresie:
ć% rozmiaru pamięci wirtualnej (ilości stron);
ć% rozmiaru pamięci fizycznej (ilości ramek).
Uwagi: długość ciągu odwołań n >= 1000;
należy uwzględnić zasadę lokalności odwołań.
Działanie programu:
I. Wygenerować losowy ciąg n odwołań do stron.
II. Dla wygenerowanego ciągu podać liczbę błędów strony (i/lub liczbę trafień
w pamięci operacyjnej) dla różnych algorytmów zastępowania stron:
" FIFO (usuwamy stronę najdłużej przebywającą w pamięci fizycznej);
" OPT (optymalny - usuwamy stronę, która nie będzie najdłużej używana);
" LRU (usuwamy stronę, do której najdłużej nie nastąpiło odwołanie);
" aproksymowany LRU (wiadomo);
" RAND (usuwamy losowo wybraną stronę).
Symulacje przeprowadzić (na tym samym ciągu testowym) dla różnej liczby
ramek (np. kilku (3, 5, 10?) wartości podanych przez użytkownika).
Zaobserwować anomalię Belady'ego, jeśli się pojawi.
2 A. Silberschatz, J.L. Peterson, G. Gagne, Podstawy systemów operacyjnych. Wydanie VII, WNT, 2005, str. 424
3 W. Stallings, Systemy operacyjne. Struktura i zasady budowy., Mikom 2005., str. 433
minima punktowe na poszczególne oceny: dst - 5pkt, db - 7pkt, bdb - 9pkt