Pamięć wirtualna
Na podstawie: Silberschatz, Galvin, i Gagne
Systemy operacyjne, 2008
Wykład: Pamięć wirtualna
Podstawy
Stronicowanie na żądanie
Tworzenie procesu
Zastępowanie stron
Alokacja ramek
Szamotanie
Przykłady rozwiązań w wybranych SO
Systemy operacyjne Z. Zieliński 14.2 Na podstawie: Silberschatz, Galvin and Gagne �2007
Motywacje
Pamięć wirtualna  oddzielenie pamięci logicznej
użytkownika od pamięci fizycznej.
Jedynie niewielka część programu musi znajdować
się w pamięci w czasie wykonywania.
Logiczna przestrzeń adresowa może więc być
znacznie większa niż dostępna pamięć fizyczna.
Pozwala na współdzielenie przestrzeni adresowej
przez szereg procesów.
Bardziej efektywne tworzenie procesu.
Pamięć wirtualna może być implementowana poprzez:
Stronicowanie na żądania
Segmentację na żądanie
Systemy operacyjne Z. Zieliński 14.3 Na podstawie: Silberschatz, Galvin and Gagne �2007
Pamięć wirtualna - znacznie większa niż fizyczna
Systemy operacyjne Z. Zieliński 14.4 Na podstawie: Silberschatz, Galvin and Gagne �2007
Stronicowanie na żądanie
Wprowadzanie strony do pamięci tylko wtedy gdy jest
potrzebna.
Mniej operacji WE/WY
Mniejsza zajętość pamięci
Szybsza odpowiedz

Więcej użytkowników
Strona jest potrzebna �! następuje odwołanie
Niepoprawne odwołanie �! zaniechanie
Brak strony w pamięci �! załadowanie strony do
pamięci
Systemy operacyjne Z. Zieliński 14.5 Na podstawie: Silberschatz, Galvin and Gagne �2007
Przesłanie stron do spójnego obszaru pamięci
dyskowej
Systemy operacyjne Z. Zieliński 14.6 Na podstawie: Silberschatz, Galvin and Gagne �2007
Bit poprawności odniesienia
Z każda pozycją tablicy stron związany jest bit
poprawności odniesienia
(1 �! w pamięci, 0 �! brak w pamięci)
Początkowo wszystkie bity odniesienia
ustawione na 0.
Chwilowy stan tablicy stron:
Ramka #
Bit poprawności odniesienia
1
1
1
1
0
M
0
0
Tablica stron
Systemy operacyjne Z. Zieliński 14.7 Na podstawie: Silberschatz, Galvin and Gagne �2007
Przykład tablicy stron  nie wszystkie strony w PAO
Systemy operacyjne Z. Zieliński 14.8 Na podstawie: Silberschatz, Galvin and Gagne �2007
Błąd strony
Jeżeli wystąpi odwołanie do strony po raz pierwszy,
spowoduje to awaryjne przerwanie (błąd adresu)
SO �! błąd strony
SO sprawdza (w PCB) czy odwołanie było dozwolone:
Niepoprawne odwołanie �! zakończenie procesu
Brak strony w pamięci.
SO znajduje wolną ramkę.
Sprowadzenie żądanej strony do wyznaczonej ramki.
Modyfikacja tablicy stron, bit odniesienia = 1.
Wznowienie wykonania instrukcji (przerwanej)
Systemy operacyjne Z. Zieliński 14.9 Na podstawie: Silberschatz, Galvin and Gagne �2007
Obsługa błędu strony
Systemy operacyjne Z. Zieliński 14.10 Na podstawie: Silberschatz, Galvin and Gagne �2007
Co się dzieje gdy nie ma wolnej ramki?
Zastępowanie stron  znalezienie ramki w pamięci, która
nie jest aktualnie wykorzystywana, przeniesienie strony
do obszaru wymiany.
algorytm
wydajność  potrzebny jest algorytm, który w efekcie
minimalizuje liczbę błędów strony.
Niektóre strony mogą być sprowadzane do pamięci
wielokrotnie.
Systemy operacyjne Z. Zieliński 14.11 Na podstawie: Silberschatz, Galvin and Gagne �2007
Efektywność stronicowania na żądanie
Prawdopodobieństwo błędu strony p : 0 d" p d" 1.0
jeżeli p = 0 błędy strony nie występują
jeżeli p = 1, każde odwołanie powoduje błąd strony
Efektywny czas dostępu (ECD)
ECD = (1  p) x czas dostępu do pamięci
+ p (czas obsługi błędu strony:
+ [czas wymiany strony na dysk]
+ czas na wprowadzenie strony
+ czas wznowienia procesu)
Systemy operacyjne Z. Zieliński 14.12 Na podstawie: Silberschatz, Galvin and Gagne �2007
Przykład
Czas dostępu do pamięci = 1 ns
Czas wymiany strony = 10 [msek] = 10 000 000 [ns]
ECD = (1  p) x 1 + p (10000000) H"
10 000 000p [ns]
Systemy operacyjne Z. Zieliński 14.13 Na podstawie: Silberschatz, Galvin and Gagne �2007
Tworzenie procesu
Pamięć wirtualna daje nam szereg korzyści w czasie
tworzenia procesu:
- Kopiowanie przy zapisie (Copy-on-Write)
- Pliki odwzorowywane w pamięci operacyjnej (Memory-
Mapped Files)
Systemy operacyjne Z. Zieliński 14.14 Na podstawie: Silberschatz, Galvin and Gagne �2007
Kopiowanie przy zapisie
Kopiowanie przy zapisie - pozwala obu
procesom (macierzystemu i potomnemu) na
początkowe współdzielenie tych samych stron w
pamięci.
Jeżeli którykolwiek proces dokonuje modyfikacji
współdzielonej strony, wtedy strona jest powielana.
Kopiowanie przy zapisie pozwala na bardziej
efektywne tworzenie procesu ponieważ jedynie
zmodyfikowane strony są powielane.
Systemy operacyjne Z. Zieliński 14.15 Na podstawie: Silberschatz, Galvin and Gagne �2007
Pliki odwzorowywane w pamięci operacyjnej
(Memory-Mapped Files)
Mapowanie bloków dyskowych na strony pamięci.
Początkowo plik jest odczytywany z wykorzystaniem metody
stronicowania na żądanie. Sekwencje operacji reads/writes do/z
określonego pliku są traktowane na zasadzie zwykłego dostępu
do pamięci.
Uproszczenie dostępu do pliku poprzez traktowanie operacji
plikowych (WE/WY) jako dostęp do pamięci zamiast faktycznych
wywołań systemowych read() write().
Pozwala także na współdzielenie pliku przez wiele procesów
(współdzielenie stron w pamięci).
Systemy operacyjne Z. Zieliński 14.16 Na podstawie: Silberschatz, Galvin and Gagne �2007
Pliki odwzorowywane w pamięci operacyjnej
Systemy operacyjne Z. Zieliński 14.17 Na podstawie: Silberschatz, Galvin and Gagne �2007
Zastępowanie stron
Ochrona nadprzydziału pamięci poprzez modyfikację
procedury obsługi włączającej zastępowanie stron.
Zastosowanie bitu modyfikacji - modify (dirty) bit - do
zredukowania narzutu związanego z dwukrotnym
przesyłaniem stron  jedynie strony zmodyfikowane
będą zapisywane na dysk.
Zastępowanie stron zapewnia pełne oddzielenie pamięci
logicznej i fizycznej  duża pamięć wirtualna może
funkcjonować przy znacznie mniejszej pamięci fizycznej.
Systemy operacyjne Z. Zieliński 14.18 Na podstawie: Silberschatz, Galvin and Gagne �2007
Potrzeba zastępowania stron
Systemy operacyjne Z. Zieliński 14.19 Na podstawie: Silberschatz, Galvin and Gagne �2007
Bazowa procedura wymiany stron
1. Odnalezienie lokalizacji potrzebnej strony na dysku.
2. Odnalezienie wolnej ramki:
- Jeżeli istnieje wolna ramka, wykorzystanie jej.
- Jeżeli nie ma wolnej ramki, zastosuj algorytm
zastępowania stron aby wybrać ramkę ofiarę.
3. Wczytanie żądanej strony do nowo zwolnionej ramki.
Aktualizacja tablic stron i ramek.
4. Wznowienie procesu.
Systemy operacyjne Z. Zieliński 14.20 Na podstawie: Silberschatz, Galvin and Gagne �2007
Zastępowanie stron
Systemy operacyjne Z. Zieliński 14.21 Na podstawie: Silberschatz, Galvin and Gagne �2007
Algorytmy zastępowania stron
Potrzebny jest algorytm o najniższej częstości błędów
strony.
Algorytm ocenia się na podstawie wykonania go na
pewnym ciągu odniesień do pamięci i zsumowania liczby
błędów strony.
W rozpatrywanych przykładach ciąg odwołań będzie
następujący:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
Systemy operacyjne Z. Zieliński 14.22 Na podstawie: Silberschatz, Galvin and Gagne �2007
Wykres zależności liczby błędów strony od liczby
ramek pamięci
Systemy operacyjne Z. Zieliński 14.23 Na podstawie: Silberschatz, Galvin and Gagne �2007
Algorytm First-In-First-Out (FIFO)
Ciąg odwołań: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
3 ramki (3 strony procesu w pamięci)
1
1
4 5
2
2
1 3 9 błędów strony
3 3
2 4
4 ramki 1
1
5 4
2
2
1 10 błędów strony
5
3
3
2
4
4 3
Zastępowanie wg metody FIFO  Anomalia Belady ego
Więcej ramek �! mniej błędów stron
Systemy operacyjne Z. Zieliński 14.24 Na podstawie: Silberschatz, Galvin and Gagne �2007
Zastępowanie FIFO
Systemy operacyjne Z. Zieliński 14.25 Na podstawie: Silberschatz, Galvin and Gagne �2007
Ilustracja anomalii Belady ego
Systemy operacyjne Z. Zieliński 14.26 Na podstawie: Silberschatz, Galvin and Gagne �2007
Algorytm optymalny
Zastąp tę stronę, która najdłużej nie będzie
używana.
4 ramki
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1
4
2
6 błędów strony
3
4
5
Skąd wiadomo jaki będzie przyszły ciąg odwołań?
Algorytm ten jest używany do porównywania
innych algorytmów, jako algorytm odniesienia.
Systemy operacyjne Z. Zieliński 14.27 Na podstawie: Silberschatz, Galvin and Gagne �2007
Optymalne zastępowanie stron
Systemy operacyjne Z. Zieliński 14.28 Na podstawie: Silberschatz, Galvin and Gagne �2007
Algorytm Least Recently Used (LRU)
Ciąg odwołań: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1
5
2
3
5 4
4
3
Zastępujemy stronę, która nie była używana najdłużej.
Implementacja za pomocą liczników
Każda pozycja strony posiada rejestr czasu użycia;
każdorazowy dostęp do strony powoduje kopiowanie
zegara do rejestru.
Gdy konieczne jest zastąpienie strony, sprawdzane są
rejestry.
Systemy operacyjne Z. Zieliński 14.29 Na podstawie: Silberschatz, Galvin and Gagne �2007
Zastępowanie LRU
Systemy operacyjne Z. Zieliński 14.30 Na podstawie: Silberschatz, Galvin and Gagne �2007
LRU
Implementacja za pomocą stosu  utrzymanie stosu
numeru stron z listą dwukierunkową:
Odwołanie do strony:
Wyjęcie numeru strony i ulokowanie jej na
szczycie
Wymagana jest w najgorszym przypadku zmiana 6
wskaz
ników
Brak wyszukiwania przy zastępowaniu
Systemy operacyjne Z. Zieliński 14.31 Na podstawie: Silberschatz, Galvin and Gagne �2007
Użycie stosu do zapisywania ostatnich odwołań do stron
Systemy operacyjne Z. Zieliński 14.32 Na podstawie: Silberschatz, Galvin and Gagne �2007
Algorytmy przybliżające metodę LRU
Bit odniesienia
Z każda stroną wiązany jest bit, początkowo = 0
Gdy do strony następuje odwołanie bit jest ustawiony na 1.
Zastępowana jest strona z bitem odniesienia = 0 (jeżeli taka
istnieje). Jednak, nie można poznać porządku użycia stron.
Algorytm drugiej szansy
Podstawą algorytmu jest FIFO, po wybraniu strony sprawdza się bit
odniesienia (bit=0  strona zastąpiona).
Zmiana czasu pobrania strony.
Jeżeli strona, która ma być zastąpiona (w porządku czasu pobrania)
ma bit odniesienia = 1 to:
Bit odniesienia zmieniany jest na 0.
Strona pozostaje w pamięci.
Bierze się pod uwagę następną stronę (wynikającą z porządku
FIFO), stosując te same reguły.
Systemy operacyjne Z. Zieliński 14.33 Na podstawie: Silberschatz, Galvin and Gagne �2007
Algorytm zastępowania stron na zasadzie drugiej
szansy
Systemy operacyjne Z. Zieliński 14.34 Na podstawie: Silberschatz, Galvin and Gagne �2007
Algorytmy działające na podstawie liczników
Utrzymywanie liczników odwołań do każdej strony.
Algorytm LFU : zastąpieniu ulega strona z najmniejsza
liczbą odwołań.
Algorytm MFU : zastępowanie strony najczęściej
używanej.
Systemy operacyjne Z. Zieliński 14.35 Na podstawie: Silberschatz, Galvin and Gagne �2007
Przydział ramek
Minimalna liczba ramek przypadająca na proces
jest zdefiniowana przez architekturę komputera.
Przykład: IBM 370  6 stron do obsługi rozkazu
przesyłania znaków typu  pamięć  pamięć
(MOVE) :
instrukcja 6 bajtowa, może znajdować się na 2 stronach.
Blok znaków do przesłania (skąd)  2strony.
Obszar przesłania (dokąd)  2strony.
Dwa główne schematy alokacji:
Stała alokacja
Alokacja priorytetowa
Systemy operacyjne Z. Zieliński 14.36 Na podstawie: Silberschatz, Galvin and Gagne �2007
Stała alokacja
Przydział równy  na przykład, mając 100
ramek i 5 procesów, przydzielamy każdemu po
20 ramek.
Przydział proporcjonalny  każdemu procesowi
przydziela się dostępną pamięć odpowiednio do
jego rozmiaru.
si = rozmiar procesu pim = 64
si = 10
S =
"s
i
s2 = 127
m = ogólna liczba ramek
10
a1 = � 64 H" 5
si
137
ai = przydzial dla procesu pi = � m
S
127
a2 = � 64 H" 59
137
Systemy operacyjne Z. Zieliński 14.37 Na podstawie: Silberschatz, Galvin and Gagne �2007
Alokacja priorytetowa
Wykorzystanie schematu proporcjonalnego w
odniesieniu do priorytetu zamiast rozmiaru.
Jeżeli proces Pi generuje błąd strony,
wybierz do zastąpienia jedną z jego ramek.
wybierz do zastąpienia ramkę procesu o najniższym priorytecie.
Systemy operacyjne Z. Zieliński 14.38 Na podstawie: Silberschatz, Galvin and Gagne �2007
Alokacja lokalna czy globalna
Zastępowanie globalne  wybierana jest ramka ze
zbioru wszystkich ramek; jeden proces może uzyskać
ramkę przydzieloną uprzednio innemu procesowi.
Zastępowanie lokalne  wybór ramki do zastąpienia
jedynie spośród zbioru własnych zaalokowanych ramek.
Systemy operacyjne Z. Zieliński 14.39 Na podstawie: Silberschatz, Galvin and Gagne �2007
Szamotanie
Jeżeli proces nie posiada  wystarczającej liczby ramek,
częstość występowania błędu strony jest bardzo wysoka.
Prowadzi to do:
niskiego wykorzystania procesora.
planista długoterminowy dostrzega spadek
wykorzystania CPU i zwiększa stopień
wieloprogramowości.
nowy proces zabiera ramki wykonywanym procesom,
powodując dalsze zwiększenie błędów strony.
Szamotanie a" proces zajęty jest głównie wymianą stron.
Systemy operacyjne Z. Zieliński 14.40 Na podstawie: Silberschatz, Galvin and Gagne �2007
Szamotanie
Dlaczego jednak stronicowanie działa?
Model lokalności
Proces przemieszcza się z jednej strefy do innej.
Strefy mogą zachodzić na siebie.
Kiedy szamotanie może wystąpić?
Ł rozmiaru stref lokalnych > ogólny rozmiar pamięci
Systemy operacyjne Z. Zieliński 14.41 Na podstawie: Silberschatz, Galvin and Gagne �2007
Lokalność odwołań do pamięci (przykład)
Systemy operacyjne Z. Zieliński 14.42 Na podstawie: Silberschatz, Galvin and Gagne �2007
Model zbioru roboczego
"a"okno zbioru roboczego a" zbiór stron, do których
nastąpiło " odniesień
Przykład: 10,000 rozkazów
WSSi (zbiór roboczy procesu Pi) =
(zmienny w czasie)
jeżeli parametr " jest za mały nie obejmie całego zbioru
roboczego.
jeżeli " jest za duży zbiór roboczy może zachodzić na kilka
stref.
ijeżeli " = "�!zbiór roboczy obejmuje cały program.
D = Ł WSSi a" ogólne zapotrzebowanie na ramki
jeżeli D > m �! szamotanie
Reguła jeżeli D > m, system operacyjny wybiera
proces, którego wykonanie trzeba wstrzymać.
Systemy operacyjne Z. Zieliński 14.43 Na podstawie: Silberschatz, Galvin and Gagne �2007
Model zbioru roboczego
Systemy operacyjne Z. Zieliński 14.44 Na podstawie: Silberschatz, Galvin and Gagne �2007
Utrzymanie śladu zbioru roboczego
Model zbioru roboczego można przybliżyć za pomocą
zegara generującego przerwania w stałych odstępach
czasu i bitu odniesienia
Przykład: " = 10,000
Przerwania zegarowe co 5000 odniesień.
Utrzymywanie w pamięci po 2 bity dla każdej strony.
Po wystąpieniu przerwania następuje kopiowanie
bitów odniesienia i ustawienie bitów odniesień na 0.
Jeżeli przynajmniej jeden z bitów odniesienia dla
danej strony = 1 �! strona włączana do zbioru
roboczego.
Czy takie postępowanie jest całkowicie dokładne?
Ulepszenie => 10 bitów przechowujących bity odniesień i
przerwanie co 1000 odniesień.
Systemy operacyjne Z. Zieliński 14.45 Na podstawie: Silberschatz, Galvin and Gagne �2007
Częstość błędów braku strony
Ustalenie akceptowalnego poziomu (przedziału)
błędów braku strony.
jeżeli aktualny poziom jest za niski, proces traci
ramkę.
jeżeli aktualny poziom jest za wysoki, procesowi
przydziela się dodatkową ramkę
Systemy operacyjne Z. Zieliński 14.46 Na podstawie: Silberschatz, Galvin and Gagne �2007
Inne rozważania
Stronicowanie wstępne
Dobór rozmiaru strony
fragmentacja
rozmiar tablicy stron
narzut I/O
strefy lokalne
Systemy operacyjne Z. Zieliński 14.47 Na podstawie: Silberschatz, Galvin and Gagne �2007
Dalsze rozważania
TLB Reach  Wielkość pamięci dostępnej poprzez TLB.
TLB Reach = (Rozmiar TLB) X (Rozmiar strony)
Idealnie, zbiór roboczy procesu jest zapamiętany w TLB.
W przeciwnym przypadku mamy wysoki stopień błędów
strony.
Systemy operacyjne Z. Zieliński 14.48 Na podstawie: Silberschatz, Galvin and Gagne �2007
Wpływ struktury programu
Program
int A[ ][ ] = new int[1024][1024];
Każdy wiersz jest zapamiętany w jednej stronie
Program 1 for (j = 0; j < A.length; j++)
for (i = 0; i < A.length; i++)
A[i,j] = 0;
liczba błędów strony=?
Program 2 for (i = 0; i < A.length; i++)
for (j = 0; j < A.length; j++)
A[i,j] = 0;
liczba błędów strony=?
Systemy operacyjne Z. Zieliński 14.50 Na podstawie: Silberschatz, Galvin and Gagne �2007
Inne rozważania
Blokowanie  Strony muszą czasami być blokowane w
pamięci.
Rozważmy WE/WY.
Systemy operacyjne Z. Zieliński 14.51 Na podstawie: Silberschatz, Galvin and Gagne �2007
Strony wykorzystywane do transmisji WE/WY muszą
znajdować się w pamięci
Systemy operacyjne Z. Zieliński 14.52 Na podstawie: Silberschatz, Galvin and Gagne �2007
Przykłady systemów operacyjnych
Windows NT/2000/XP
Solaris
Systemy operacyjne Z. Zieliński 14.53 Na podstawie: Silberschatz, Galvin and Gagne �2007
Windows NT/2000/XP
Wykorzystuje stronicowanie na żądanie z grupowaniem
(clustering). Grupowanie stron wywołujących najwięcej
błędów strony.
Procesom przypisuje się minimalny i maksymalny zbiór
roboczy.
Minimalny zbiór roboczy określa gwarantowaną minimalną
liczbę stron, którą proces będzie miał w pamięci.
Procesowi można przydzielić dowolną liczbę ramek do
wartości określonej przez maksymalny zbiór roboczy.
Gdy wielkość wolnej pamięci w systemie spada poniżej
wartości progowej, wykonuje się proces automatic working set
trimming (automatyczne przycinanie zbioru roboczego)
w celu odzyskania wolnej pamięci systemu.
Proces odzyskiwania usuwa strony procesów, których
liczba stron wykracza poza minimalny zbiór roboczy.
Systemy operacyjne Z. Zieliński 14.54 Na podstawie: Silberschatz, Galvin and Gagne �2007
Solaris
Kiedy proces powoduje brak strony, wtedy jądro przydziela
stronę wątkowi procesu, w którym wystąpił błąd strony.
Lotsfree  parametr, związany z wykazem wolnych stron,
reprezentujący próg rozpoczynania wymiany stronicowania
(zwykle 1/64 rozmiaru pamięci fizycznej).
Gdy liczba wolnych ramek spadnie poniżej lotsfree, wówczas
podejmuje działanie proces wymiatania (pageout process).
Pageout  stosuje algorytm zegara dwuwskazówkowego
(przypominający algorytm drugiej szansy).
W algorytmie wymiatania stron używa się kilku parametrów do
sterowania szybkością analizowania stron (scanrate) 
szybkość analizowania stron waha się od slowscan do
fastscan.
Proces pageout wywoływany jest z częstością zależną od
wielkości dostępnej wolnej pamięci.
Systemy operacyjne Z. Zieliński 14.55 Na podstawie: Silberschatz, Galvin and Gagne �2007
Solar Page Scanner
Systemy operacyjne Z. Zieliński 14.56 Na podstawie: Silberschatz, Galvin and Gagne �2007
Koniec
Na podstawie: Silberschatz, Galvin, i Gagne
Systemy operacyjne, 2008