Rozważmy pamięć wirtualną ze stronicowaniem na żądanie. Tablica stron jest przechowywana w rejestrach. Obsługa przerwania braku strony zajmuje 8 milisekund, gdy jest dostępna pusta ramka lub strona usuwana z pamięci nie była modyfikowana i 20 milisekund, gdy usuwana strona była modyfikowana. Czas dostępu do pamięci wynosi 1 mikrosekundę.
Załóżmy, że 70% usuwanych stron to strony, które były modyfikowane. Jaki jest maksymalny akceptowalny współczynnik przerwań braku strony, aby efektywny czas dostępu do pamięci nie przekraczał 2 mikrosekund?
Rozwiązanie
2 mikrosekundy >= (1 - p) * 1 mikrosekunda + p * (0.3 * 8 milisekund + 0.7 * 20 milisekund) p <= 0.00006
Rozważmy następujący ciąg odwołań do stron:
4, 5, 3, 1, 4, 5, 2, 4, 5, 3, 1, 2
Zakładając, że dostępna dla procesów pamięć fizyczna składa się z:
które początkowo są wolne, podaj, które strony i w jakiej kolejności zostaną usunięte oraz jaka jest w każdej chwili zawartość pamięci przy zastosowaniu następujących strategii usuwania stron:
Rozwiązanie
4 5 3 1 4 5 2 4 5 3 1 2
* * * * * * * * * *
4 5 3 1 4 5 2 4 5 3 1 2
4 5 3 1 4 5 2 4 5 3 1
4 5 3 1 4 5 2 4 5 3 4 5 3 1 4 5 2 4 5 3 1 2
* * * * * * * * *
4 4 4 1 1 1 2 2 2 2 2 2
5 5 5 4 4 4 4 4 3 3 3
3 3 3 5 5 5 5 5 1 1 4 5 3 1 4 5 2 4 5 3 1 2
* * * * * * *
4 4 4 4 4 4 4 4 4 4 1 1
5 5 5 5 5 5 5 5 3 3 3
3 1 1 1 2 2 2 2 2 2 4 5 3 1 4 5 2 4 5 3 1 2
* * * * * * * *
4 5 3 1 4 5 2 4 5 3 1 2
4 5 3 1 4 5 2 4 5 3 1
4 5 3 1 4 5 2 4 5 3
4 5 3 1 1 1 2 4 5 4 5 3 1 4 5 2 4 5 3 1 2
* * * * * * * * * *
4 4 4 4 4 4 2 2 2 2 1 1
5 5 5 5 5 5 4 4 4 4 2
3 3 3 3 3 3 5 5 5 5
1 1 1 1 1 1 3 3 3Anomalia Belady'ego: wystąpiło więcej błędów braku strony mimo, że jest więcej dostępnej pamięci.
4 5 3 1 4 5 2 4 5 3 1 2
* * * * * *
4 4 4 4 4 4 4 4 4 4 1 1
5 5 5 5 5 5 5 5 5 5 5
3 3 3 3 3 3 3 3 3 3
1 1 1 2 2 2 2 2 2Pewien proces wygenerował następujący ciąg odwołań do stron:
1, 4, 1, 2, 5, 3, 1, 2, 6, 4, 3, 2
Zakładając, że dostępna dla procesów pamięć fizyczna składa się z 4 ramek, które początkowo są wolne, podaj, które strony i w jakiej kolejności zostaną usunięte oraz jaka jest w każdej chwili zawartość pamięci przy zastosowaniu następujących strategii usuwania stron:
Rozwiązanie
1 4 1 2 5 3 1 2 6 4 3 2
* * * * * * * *
1 4 1 2 5 3 1 2 6 4 3 2
1 4 1 2 5 3 1 2 6 4 3
4 1 2 5 3 1 2 6 4
4 1 2 5 3 1 2 6 1 4 1 2 5 3 1 2 6 4 3 2
* * * * * * * * *
>1.>1.>1.>1.>1. 3. 3. 3.>3. 3 3. 3
4. 4. 4. 4.>4 1. 1. 1. 1 1 2.
2. 2. 2 >2 >2. 2 4. 4.>4.
5. 5 5 5 6.>6.>6. 6. oznacza ustawiony bit
Rozważmy następujący ciąg odwołań do stron:
2, 4, 3, 4, 4, 4, 3, 4, 2, 1, 5, 2, 5
Podaj zawartość pola roboczego oraz liczbę przerwań braku strony dla wskazanego ciągu odwołań w strategii pola roboczego z okienkiem o rozmiarze:
Rozwiązanie
2 4 3 4 4 4 3 4 2 1 5 2 5
* * * * * * *
2 2 2 4 4 4 4 4 3 4 2 1 5
4 4 3 3 3 3 4 2 1 5 2
3 2 1 5 2
2 4 3 4 4 4 3 4 2 1 5 2 5
* * * * * *
2 2 2 2 4 4 4 4 4 3 4 2 1
4 4 4 3 3 3 3 3 4 2 1 5
3 3 2 2 1 5 2
1 5Rozważmy dwuwymiarową tablicę A:
var A: array [1..page_size] of array [1..page_size] of byte;
Ile przerwań braku strony wygeneruje wykonanie każdego z podanych dwóch algorytmów zerowania tablicy A?
for i:= 1 to page_size do
for j:= 1 to page_size do
A[i, j] := 0;
for i:= 1 to page_size do
for j:= 1 to page_size do
A[j, i] := 0;Można założyć, że:
Rozwiązanie
Algorytm pierwszy wygeneruje page_size przerwań braku strony, a drugi: page_size2.
Wniosek: struktura programu może mieć istotny wpływ na efektywność wykonywania tego programu w systemie z pamięcią wirtualną.
Algorytm WSClock zarządzania pamięcią działa następująco. Jeśli są puste ramki, to przydziela pierwszą wolną.
Jeśli nie ma, to przegląda cyklicznie wszystkie ramki (począwszy od miejsca, w którym ostatnio zakończono przeglądanie). Jeśli do strony zapamiętanej w ramce było odwołanie od ostatniego sprawdzenia, to za czas tego odwołania przyjmuje się czas bieżący. Jeśli do strony nie było odwołania od ostatniego sprawdzenia, to można usunąć tę stronę, jeśli od czasu ostatniego sprawdzenia minęło co najmniej T jednostek czasu. Jeśli strona była modyfikowana podczas pobytu w pamięci operacyjnej, to inicjuje się usunięcie strony i szuka się dalej. Jeśli w wyniku przejrzenia wszystkich ramek nie znajdzie się żadnej wolnej, to:
Dane są następujące deklaracje:
const lramek = ...;
maxproc = ...;
T = ...;
type ramki = 0..lramek-1;
procesy = 0..maxproc;
function Zegar: real; (* wirtualny zegar *)
procedure UsuńStronę (nrramki: ramki);
(* inicjuje przesłanie strony z danej ramki z pamięci operacyjnej do pomocniczej *)
function CzekajNaRamkę: ramki;
(* wstrzymuje działanie procesu aż do chwili najbliższego zakończenia usuwania
strony z pamięci operacyjnej do pomocniczej - przekazuje numer zwolnionej ramki *)
function UsuńProces: procesy
(* przekazuje numer procesu wyznaczonego do usunięcia *)Należy zadeklarować wszystkie potrzebne struktury danych oraz napisać procedurę WSClock implementującą strategię zarządzania pamięcią WSClock i przekazującą numer wolnej ramki w pamięci operacyjnej.
Uwaga: jeśli na porządne zapisanie tego algorytmu nie wystarczy czasu, to należy przynajmniej dokładnie omówić działanie algorytmu WSClock.
Rozwiązanie
type wramki = -1 .. lramek -1; (* wolne ramki; -1 <=>; NIL *)
var PaO: array [ramki] of
record
było_odwołanie: boolean;
czas_odwołania: real;
modyfikowana: boolean;
trwa_transmisja: boolean; (* strona jest usuwana,
była modyfikowana *)
proces: procesy;
następna_wolna: wramki; (* następna wolna *)
end;
strzałka: ramki;
wolna: wramki; (* wskaźnik do listy wolnych *)
usuwane: integer; (* liczba usuwanych stron zmodyfikowanych;
transmisja mogła zostać zainicjowana podczas
poprzednich wywołań procedury WSClock *)
czekający: integer; (* liczba procesów czekających na stronę *)
bieżący_proces: integer; (* numer bieżącego procesu *)
procedure ZwolnijRamkę (nrramki: ramki);
begin
PaO[nrramki].następna_wolna := wolna; wolna := nrramki;
with PaO[nrramki] do
begin
proces := 0; trwa_transmisja := false; było_odwołanie := false
end
end;
procedure WSClock (var nrramki: ramki);
var znaleziono: boolean;
ostatni: nrramki;
nrproc: procesy;
begin
if wolna <> -1 then begin
nrramki := wolna; wolna := PaO[wolna].następna_wolna
end
else begin
znaleziono := false;
ostatni := strzałka;
repeat
strzałka := (strzałka + 1) mod lramek;
with PaO[strzałka] do
if not trwa_transmisja then
if było_odwołanie then begin
było_odwołanie := false; czas_odwołania := Zegar(bieżący_proces);
end
else if Zegar(bieżący_proces) - czas_odwołania > T then
if modyfikowana then begin
usuwane := usuwane + 1;
trwa_transmisja := true;
UsuńStronę(strzałka)
end else begin
znaleziono := true;
proces := bieżący_proces;
nrramki := strzałka;
end
until znaleziono or (strzałka = ostatni);
if not znaleziono then begin
if czekający >= usuwane then begin
nrproc := UsuńProces;
for ostatni:=0 to lramek-1 do
with PaO[ostatni] do
if proces = nrproc then
if modyfikowana then begin
trwa_transmisja:=true;
usuwane := usuwane + 1;
UsuńStronę(ostatni)
end
else ZwolnijRamkę(ostatni);
end;
if wolna <> -1 then begin
nrramki := wolna; wolna := PaO[wolna].następna_wolna
end
else begin czekający := czekający + 1; nrramki := CzekajNaRamkę end
end;
end
end (* WSClock *)Dodatkowe pytania: