Ludzie pragną czasami się rozstawać, żeby móc tęsknić, czekać i cieszyć się z powrotem.

Może to wpłynąć na podniesienie stopnia wielopro-
tem operacyjny, gdy wystąpi brak strony.
gramowości (bo umożliwia dopuszczenie do działania większej liczby proce-
9.2 Załóżmy, że dysponujemy ciągiem odniesień dla procesu z m ramkami sów w tym samym czasie) i - przynajmniej w teorii - na polepszenie wykorzy-
(początkowo wszystkie są puste). Ciąg odniesień ma długość p i wystę-
stania procesora przez system. Pozwala ono również na wykonywanie proce-
puje w nim n różnych numerów stron. Dla dowolnego algorytmu zastę-
sów nawet wtedy, gdy ich wymagania pamięciowe przekraczają całkowitą ilość
powania stron określ:
pamięci dostępnej fizycznie. Procesy takie działają w pamięci wirtualnej.
Jeśli łączne zapotrzebowanie na pamięć jest większe niż obszar pamięci
(a) dolną granicę braków stron;
fizycznej, to staje się niezbędne zastępowanie stron w pamięci, tj. zwalnianie (b) górną granicę braków stron.
ramek na nowe strony. Stosuje się rozmaite algorytmy zastępowania stron.
Algorytm FIFO zastępowania stron jest łatwy do zaprogramowania, lecz jest
9.3 Pewien komputer dostarcza swoim użytkownikom pamięć wirtualną
obciążony anomalią Belady'ego. Optymalne zastępowanie stron wymaga
wielkości 232 B. Komputer ten ma 2IH B pamięci fizycznej. Pamięć wir-
wiedzy o przyszłości. Algorytm LRU zastępowania stron jest przybliżeniem
tualna jest zrealizowana za pomocą stronicowania, a rozmiar strony wy-
algorytmu optymalnego, ale i on może być trudny do zrealizowania. Więk-
nosi 4096 B. Proces użytkownika wytworzył adres wirtualny 11123456.
szość algorytmów zastępowania stron, jak na przykład algorytm drugiej szan-
Wyjaśnij, w jaki sposób system ustala odpowiadający temu adresowi
sy, stanowi przybliżenie algorytmu LRU.
wirtualnemu adres fizyczny. Dokonaj rozróżnienia między operacjami
Algorytm zastępowania stron wymaga uzupełnienia o jakąś politykę
programowymi a sprzętowymi.
przydziału ramek. Przydział może być ustalony, polegający raczej na lokal-
nym zastępowaniu stron, lub dynamiczny - umożliwiający zastępowanie glo-
9.4 Które z następujących technik i struktur są „dobre" dla środowiska stro-balne. W modelu zbioru roboczego zakłada się, że wykonywanie procesów
nicowania na żądanie, które zaś są „niedobre":
charakteryzuje się strefowością. Zbiór roboczy tworzą strony należące do
(a) stos;
bieżącej strefy. Każdy proces powinien mieć przydzieloną liczbę ramek wy-
starczającą dla bieżącego zbioru roboczego.
(b) haszowana tablica symboli (ang. hashedsymbol table);
386 Rozdział 9 Famięć wirtualna
Ćwi
wiczema
387
(c) przeszukiwanie sekwencyjne;
• Spośród rozkazów dotyczących innych stron 80% odnajdywało stro-
(d) przeszukiwanie binarne;
nę wprost w pamięci operacyjnej.
(e) czysty kod;
• Gdy była potrzebna nowa strona, wówczas w 50% przypadków oka-
zywało się, że strona zastępowana była zmieniona.
(f) operacje wektorowe;
Oblicz efektywny czas rozkazu w tym systemie, przy założeniu że sys-
(g) adresowanie pośrednie.
tem wykonuje tylko jeden proces, a procesor pozostaje bezczynny pod-
9.5 Załóżmy, że mamy pamięć stronicowaną na żądanie. Tablica stron jest
czas operacji bębnowych.
przechowywana w rejestrach. Obsługa braku strony zabiera 8 ms wtedy,
9.9 Rozważ system stronicowania na żądanie, w którym zmierzone w czasie
kiedy jest dostępna pusta strona lub strona zastępowana jest nie zmie-
parametry użytkowania przedstawiają się następująco:
niona, oraz 20 ms, jeśli zastępowana strona jest zmieniona. Czas dostę-
pu do pamięci wynosi 100 ns.
wykorzystanie procesora 20%
Przyjmijmy, że strona do zastąpienia jest zmieniona w 70 przypad-
dysk stronicujący 97,7%
kach na 100. Ile wynosi maksymalna akceptowalna częstość braków
inne urządzenia wejścia-wyjścia 5%
stron, jeśli efektywny czas dostępu ma nie być dłuższy niż 200 ns?
Które (jeśli w ogóle) z następujących propozycji poprawiłyby (prawdo-9.6 Rozważ następujące algorytmy zastępowania stron. Ustaw je w kolejno-
podobnie) wykorzystanie procesora? Odpowiedź uzasadnij.
ści od „złego" do „znakomitego" według ich częstości braków stron.
(a) zainstalowanie szybszego procesora;
Oddziel algorytmy podatne na anomalię Belady'ego od tych, które jej
nie ulegają:
(b) zainstalowanie większego dysku do stronicowania;
(a) algorytm LRU;
(c) zwiększenie stopnia wieloprogramowości;
(b) algorytm FIFO;
(d) zmniejszenie stopnia wieloprogramowości;
(c) zastępowanie optymalne;
(e) zainstalowanie większej ilości pamięci operacyjnej;
(d) zastępowanie metodą drugiej szansy.
(f) zainstalowanie szybszego dysku twardego lub kilku sterowników
kilku dysków twardych;
9.7 Zaimplementowanie w systemie komputerowym techniki pamięci wir-
(g) dodanie stronicowania wstępnego do algorytmów sprowadzania stron;
tualnej pociąga za sobą pewne koszty i pewne korzyści. Wymień owe
koszty i korzyści. Czy jest możliwe, aby koszty przewyższyły korzyści?
(h) zwiększenie rozmiaru strony.
Jeśli tak, to jakie zastosować miary, żeby do tego nie dopuścić?
9.10 Rozważmy dwuwymiarową tablicę A:
9.8 W pewnym systemie operacyjnym zaimplementowano stronicowaną
varA: array [1 ..100] of array [1..100] ofinteger;
pamięć wirtualną przy użyciu procesora z czasem cyklu wynoszącym
1 fis. Dostęp do strony innej niż bieżąca zabiera dodatkowo 1 u,s. Stro-
gdzie .4[1][I] znajduje się w komórce 200 systemu stronicowanej pa-