Pamiec wirtualna.pdf

Ó Janina Mincer

Systemy Operacyjne

PamiŒ æ wirtualna

• Umo¿liwia wykonywanie proces ó w, pomimo ¿e nie s„ one

w ca‡o œ ci przechowywane w pamiŒci operacyjnej

• Logiczna przestrzeæ adresowa mo¿e by æ du¿o wiŒksza od

fizycznej przestrzeni adresowej

• Tworzy iluzjŒ du¿ej, jednorodnej i szybkiej pamiŒci

• Techniki realizacji pamiŒci wirtualnej: stronicowanie na

¿„danie, segmentacja na ¿„danie, segmentacja ze

stronicowaniem

strona 0

strona 1

strona 2

strona 3

•

odwzorowanie

pamiŒci

strona n

pamiŒ æ fizyczna

dysk

pamiŒ æ wirtualna

Stronicowanie na ¿„danie

• Strona jest sprowadzana do pamiŒci dopiero wtedy, gdy

jest potrzebna:

mniej wej œ cia-wyj œ cia, mniejsze zapotrzebowanie na

pamiŒ æ , wiŒcej u¿ytkownik ó w

• Strona jest potrzebna, gdy pojawia siŒ do niej odwo‡anie

• Z ka¿d„ pozycj„ w tablicy stron jest zwi„zany bit

poprawno œ ci odwo‡ania (1 - strona w pamiŒci, 0 - strona

poza pamiŒci„)

PamiŒ æ wirtualna

str. 1

Ó Janina Mincer

Systemy Operacyjne

• Odwo‡anie do strony z bitem poprawno œ ci odwo‡ania

r ó wnym 0 powoduje b‡„d braku strony (ang. page fault).

System operacyjny:

- znajduje woln„ ramkŒ

- sprowadza stronŒ z dysku do pamiŒci

- uaktualnia bit poprawno œ ci odwo‡ania (:= 1)

- restartuje instrukcjŒ, kt ó ra spowodowa‡a b‡„d

• Co siŒ dzieje, gdy nie ma wolnej ramki:

wymiana stron (ang. page replacement) - SO znajduje w

pamiŒci stronŒ (najmniej u¿ywan„) i usuwa j„ na dysk

• Niekt ó re strony mog„ by æ sprowadzane do pamiŒci

wielokrotnie

Wydajno œæ stronicowania na ¿„danie:

p = wsp ó ‡czynnik b‡Œd ó w braku strony 0 £ p £1.0

p =0 Þ nie ma b‡Œd ó w braku strony

p =1 Þ ka¿de odwo‡anie powoduje b‡„d braku strony

efektywny czas dostŒpu =

(1 - p) · czas dostŒpu do pamiŒci

+ p · czas obs‡ugi b‡Œdu braku strony

obs‡uga b‡Œdu braku strony = czas obs‡ugi przerwania

+[czas wys‡ania strony na dysk]+czas sprowadzenia

strony z dysku + czas wznowienia obliczeæ

Algorytmy wymiany stron:

• Bit modyfikacji umo¿liwia zmniejszenie liczby transmisji

dyskowych - tylko modyfikowane strony trzeba zapisywa æ

z powrotem na dysk

• Algorytm powinien minimalizowa æ liczbŒ b‡Œd ó w strony

PamiŒ æ wirtualna

str. 2

Ó Janina Mincer

Systemy Operacyjne

• Ci„g odwo‡aæ: ci„g numer ó w stron, np.

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

• Algorytm FIFO

3 ramki pamiŒci Þ 9 przerwaæ braku strony

4 ramki pamiŒci Þ 10 przerwaæ braku strony

(anomalia FIFO; FIFO nie jest algorytmem stosowym)

• Algorytm optymalny: usuæ stronŒ, do kt ó rej najd‡u¿ej

nie bŒdzie odwo‡ania (alg. stosowy: M(m,r) ˝ M(m+1,r))

3 ramki pamiŒci Þ 7 przerwaæ braku strony

4 ramki pamiŒci Þ 6 przerwaæ braku strony

Nierealizowalny w praktyce, stosowany do por ó wnaæ

• Algorytm LRU ( „ najd‡u¿ej nieu¿ywany najpierw ” )

3 ramki pamiŒci Þ 10 przerwaæ braku strony

4 ramki pamiŒci Þ 8 przerwaæ braku strony

Implementacja z licznikiem: z ka¿d„ pozycj„ w tablicy

stron jest zwi„zany licznik, podczas ka¿dego odwo‡ania

zawarto œæ zegara kopiuje siŒ do licznika

Implementacja ze stosem: numery stron przechowuje siŒ

na stosie, po ka¿dym odwo‡aniu do strony przesuwa siŒ jej

numer na wierzcho‡ek stosu

Algorytmy przybli¿aj„ce LRU:

1. Bit odwo‡ania: z ka¿d„ stron„ zwi„zuje siŒ bit

odwo‡ania (inicjalnie = 0); w chwili odwo‡ania do strony

ustawia siŒ bit na 1; usuwa siŒ stronŒ z bitem 0; kt ó r„?

2. Algorytm drugiej szansy: przegl„da siŒ strony zgodnie z

porz„dkiem FIFO, cyklicznie; gdy bit=0, to stronŒ mo¿na

wymieni æ ; gdy bit=1; to zeruje siŒ bit, a stronie daje

„ drug„ szansŒ ” (czas sprow. do pamiŒci:=czas bie¿„cy)

3. Algorytm zegarowy: jak w 2, lecz cykliczna lista stron

• Algorytm LFU ( „ najmniej u¿ywana ” )

• Algorytm MFU ( „ najwiŒcej u¿ywana ” )

PamiŒ æ wirtualna

str. 3

Ó Janina Mincer

Systemy Operacyjne

Przydzia‡ ramek:

• Minimalna liczba ramek zale¿y od architektury komputera

• Przydzia‡ r ó wny: ka¿dy proces dostaje tyle samo

• Przydzia‡ proporcjonalny: ka¿dy proces dostaje

proporcjonalnie do swojego rozmiaru

• Przydzia‡ priorytetowy:proces o wy¿szym priorytecie

mo¿e wybra æ stronŒ do usuniŒcia spo œ r ó d swoich stron

lub stron proces ó w o ni¿szym priorytecie

Algorytmy lokalne (wyb ó r strony do usuniŒcia spo œ r ó d

w‡asnych stron) i globalne (wyb ó r strony do usuniŒcia

spo œ r ó d wszystkich stron)

Migotanie

Proces jest zajŒty g‡ ó wnie przesy‡aniem stron z dysku do

pamiŒci i z pamiŒci na dysk

Brak wystarczaj„cej liczby stron jest powodem wysokiego

wsp ó ‡czynnika b‡Œd ó w braku strony:

Þ niskie wykorzystanie CPU

Þ system operacyjny my œ li, ¿e trzeba zwiŒkszy æ poziom

wieloprogramowo œ ci

Þ do systemu dodaje siŒ nowy proces

Wykres zale¿no œ ci wykorzystania procesora od poziomu

wieloprogramowo œ ci

Model pola roboczego (ang. working-set)

Zasada lokalno œ ci odwo‡aæ: w ka¿dej fazie wykonania

program korzysta jedynie z drobnej czŒ œ ci ca‡ego zbioru

stron (lokalno œæ czasowa, przestrzenna)

T = parametr Þ okienko (ustalona liczba odwo‡aæ do stron)

PamiŒ æ wirtualna

str. 4

Ó Janina Mincer

Systemy Operacyjne

Pole robocze procesu P i (WS i ): ca‡kowita liczba stron, do

kt ó rych proces odwo‡a‡ siŒ podczas ostatnich T odwo‡aæ

Je œ li T za ma‡e, to zbi ó r roboczy nie obejmie ca‡ej

lokalno œ ci procesu

Je œ li T za du¿e, to zbi ó r roboczy obejmie kilka lokalno œ ci

Je œ li T = ¥, to zbi ó r roboczy obejmie wszystkie strony

Zasada pola roboczego a r ó wnowa¿enie obci„¿enia

Je œ li s„ jeszcze wolne ramki Þ mo¿na zainicjowa æ nowy

proces

Je œ li å WS i > liczba dostŒpnych ramek Þ migotanie Þ

wstrzymanie jednego z proces ó w

Jak aproksymowa æ zawarto œæ pola roboczego:

zegar + bit odniesienia

Przyk‡ad: T = 10,000

- zegar generuje przerwanie co 5,000 jednostek czasu

- na ka¿d„ stronŒ przeznacza siŒ w pamiŒci dwa bity

- z nadej œ ciem przerwania kopiuje siŒ wszystkie bity

odniesienia, a nastŒpnie zeruje

- je œ li jeden z bit ó w w pamiŒci =1 Þ strona nale¿y do WS

Inne zagadnienia:

1.Sprowadzanie wstŒpne; OBL (ang. one block lookahead)

2.Wyb ó r rozmiaru strony: fragmentacja, rozmiar tablicy

stron, narzut na wej œ cie-wyj œ cie, lokalno œæ

3.Struktura programu: przyk‡ad dostŒpu do macierzy

kwadratowej wierszami vs. kolumnami

Restrukturyzacja programu: zwiŒkszenie lokalno œ ci

odwo‡aæ

PamiŒ æ wirtualna

str. 5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: