1

1

ZARZĄDZANIE ZASOBAMI PAMIĘCI

PAMIĘĆ WIRTUALNA

„

Wiadomości wstępne

„

Stronicowanie na żądanie

„

Algorytmy realizacji

„

Segmentacja na żądanie

„

Podsumowanie

2

PAMIĘĆ WIRTUALNA

Dlaczego?

Klasyczne podejście polegające na umieszczeniu całej

logicznej przestrzeni adresowej w pamięci fizycznej jest

często niepotrzebne:

„

Programy najczęściej posiadają fragmenty do obsługi błędów lub

wyjątków – wykonywane bardzo rzadko.

„

Dla tablic, list czy wykazów często przydziela się więcej pamięci,

niż w rzeczywistości potrzebują

„

Pewne możliwości lub moduły programów mogą być

wykorzystywane w wyjątkowych przypadkach

2

3

PAMIĘĆ WIRTUALNA

Dlaczego?

Zdolność wykonania programu, który tylko częściowo

znajduje się w pamięci ma następujące korzyści:

„

Program nie jest ograniczany wielkością dostępnej

pamięci fizycznej

„

Można w tym samym czasie wykonywać więcej

programów w tym samym czasie

„

Zmniejsza się liczba operacji we-wy koniecznych do

załadowania lub wymiany programu w pamięci

4

PAMIĘĆ WIRTUALNA

Pamięć wirtualna polega na odseparowaniu pamięci logicznej

użytkownika od pamięci fizycznej oraz umożliwia kilku

różnym procesom dzielenie plików i pamięci operacyjnej

Odseparowanie pamięci logicznej o fizycznej umożliwia programistom

posługiwanie się olbrzymią pamięcią wirtualną nawet wtedy, gdy w

pamięci fizycznej jest mało miejsca. Pamięć wirtualna znacznie ułatwia

proces programowania, gdyż programista nie musi kontrolować

zasobów pamięci fizycznej

3

5

PAMIĘĆ WIRTUALNA

Zalety stosowania

„

Umożliwia wykonywanie procesów, pomimo że nie są

one w całości przechowywane w pamięci

„

Programy mogą być większe niż pamięć fizyczna

„

Logiczna przestrzeń adresowa może być dużo większa

niż fizyczna przestrzeń adresowa

„

Tworzy iluzję dużej, jednorodnej i szybkiej pamięci

„

Umożliwia procesom łatwe dzielenie przestrzeni

adresowych

„

Udostępnia wydajny mechanizm tworzenia procesów

„

Podniesienie stopnia wieloprogramowości

6

PAMIĘĆ WIRTUALNA

Wady stosowania

„

Trudności w realizacji pamięci wirtualnej

„

Konieczność opracowania złożonych algorytmów

„

Konieczność realizacji na poziomie sprzętowym

„

Może wystąpić znaczne obniżenie wydajności programów

„

Występowanie niekorzystnych zjawisk (np. szamotanie)

4

7

PAMIĘĆ WIRTUALNA

Realizacja

Techniki realizacji pamięci wirtualnej:

„

Stronicowanie na żądanie

„

Segmentacja na żądanie

8

STRONICOWANIE W SYSTEMIE

PAMIĘCI WIRTUALNEJ

„

Stronicowanie z wymianą stron pomiędzy pamięcią

pierwszego i drugiego rzędu.

„

Zalety w porównaniu z prostym stronicowaniem:

rozszerzenie przestrzeni adresowej (wirtualnej) i tym

samym zwiększony stopień wieloprogramowości.

„

Wady: złożoność zarządzania i narzut czasowy

związany z dostępem.

5

9

MECHANIZM STRONICOWANIA

NA ŻĄDANIE

„

Działanie mechanizmu — strony są sprowadzane do

pamięci tylko wówczas, gdy jest to konieczne, czyli gdy

następuje odniesienie do komórki o adresie, znajdującym

się na tej stronie (leniwa wymiana, ang. lazy swapping).

„

Wymaganie sprzętowe

„

tablica stron z bitem poprawności (ang. valid-invalid bit) dla każdej

pozycji (dodatkowo z bitem modyfikacji i odniesienia),

„

mechanizm reakcji na odniesienie do strony niepoprawnej,

„

urządzenie wymiany (ang. swap device) — pamięć pomocnicza.

10

MECHANIZM STRONICOWANIA

NA ŻĄDANIE

„

Z każdą pozycją w tablicy stron jest związany tzw.

bit poprawności odwołania

(1 – strona w pamięci, 0 – strona poza pamięcią)

„

Odwołanie do strony z bitem poprawności równym 0 powoduje

błąd braku strony (ang. page fault)

„

W tym wypadku system operacyjny:

„

Znajduje wolną ramkę

„

Sprowadza stronę z dysku do pamięci

„

Uaktualnia bit poprawności odwołania (na 1)

„

Restartuje instrukcję, która spowodowała błąd

„

Gdy nie ma wolnej ramki w pamięci fizycznej SO dokonuje

wymiany stron (ang. page replacement)

SO znajduje w pamięci stronę (np. najmniej używaną) i zapisuje ją na

dysk a w miejsce zwolnionej ramki ładuje nową stronę

6

11

OBSŁUGA BŁĘDU BRAKU STRONY

12

POWTÓRNE WYKONANIE ROZKAZU

7

13

ZASTĘPOWANIE STRON

„

Problem zastępowania (wymiany) stron pojawia się, gdy w

pamięci fizycznej brakuje wolnych ramek i konieczne jest

zwolnienie jakieś ramki poprzez usunięcie z niej strony.

„

Jeśli strona była modyfikowana

w pamięci, konieczne jest zapisanie

jej na dysku. Aby stwierdzić

konieczność zapisu wprowadzono

bitu modyfikacji (ang. Modify bit),

zwanego też bitem zabrudzenia

(ang. dirty bit).

14

PROBLEMY ZASTĘPOWANIA STRON

„

Problem wyboru ofiary — niewłaściwy wybór ramki ofiary

może prowadzić do zjawiska migotania, w którym często

dochodzi do wystąpienia odniesienia do właśnie usuniętej

strony, co w konsekwencji wymaga ponownego

sprowadzenie jej do pamięci. Dalszą konsekwencją takiego

zjawiska może być drastyczny spadek efektywności działania

systemu komputerowego.

„

Problem wznawiania rozkazów — w przypadku wielokrotnego

odniesienia do pamięci w jednym cyklu rozkazowym należy

zapewnić, że wszystkie adresowane strony są jednocześnie

dostępne w ramkach w pamięci fizycznej.

8

15

PROBLEM WYBORU OFIARY

„

Zakładając, że przyszły ciąg odniesień do pamięci nie

jest znany, na podstawie historii odniesień należy

wybrać taką ramkę, do której prawdopodobieństwo

odniesienia w przyszłości jest małe.

„

Podstawowa własność programów, na podstawie

której można szacować takie prawdopodobieństwo

nazywana jest

lokalnością

.

16

WŁASNOŚĆ LOKALNOŚCI

„

Lokalność jest określona jako tendencja procesów do

generowania w stosunkowo długich przedziałach czasu

odniesień do niewielkiego podzbioru stron wirtualnych

zwanego

zbiorem stron aktywnych

.

„

Rodzaje własność lokalności:

„

lokalność czasowa — tendencja procesu do generowania z

dużym prawdopodobieństwem w przedziale czasu (

t, t + τ)

odniesień do stron adresowanych w przedziale czasu (

t − τ, t);

„

lokalność przestrzenna — tendencja procesu do generowania z

dużym prawdopodobieństwem odniesień do stron o zbliżonych

numerach (stron sąsiednich).

9

17

PROBLEM EFEKTYWNOŚCI SYSTEMU

Z PAMIĘCIĄ WIRTUALNĄ

„

Efektywność działania systemu pamięci

wirtualnej zależy od precyzji identyfikacji zbioru

stron aktywnych i możliwości utrzymania ich w

pamięci fizycznej.

„

Wobec braku pełnego ciągu odniesień do stron

wirtualnych identyfikacja takiego zbioru może

wynikać z różnych przesłanek, czego skutkiem

jest duża różnorodność algorytmów wymiany.

18

ALGORYTMY

WYMIANY STRON

„

Zastępowanie lokalne (ang. local replacement) —

algorytm wymiany zastępuje tylko strony w ramkach

przydzielonych procesowi, który spowodował błąd strony
→ stronicowanie statyczne.

„

Zastępowanie globalne (ang. global replacement) —

algorytm wymiany zastępuje strony znajdujące się w

dostępnej puli ramek w całym systemie (w szczególności

zatem usuwa strony innych procesów)
→ stronicowanie dynamiczne.

10

19

PRZYKŁADY ALGORYTMÓW

WYMIANY STRON

„

Algorytm FIFO (ang. First In First Out) — zastępowana

jest strona najstarsza (najwcześniej wprowadzona do

pamięci)

„

Algorytm OPT (MIN) — zastępowana jest strona, która

najdłużej nie będzie używana

„

Algorytm LRU (ang. Least Recently Used) —

zastępowana jest najdawniej używana strona (najdłużej

nie używana)

„

Algorytm LFU (ang. Least Frequently Used) —

zastępowana jest najrzadziej używana strona

„

Algorytm MFU (ang. Most Frequently Used) —

zastępowana jest najczęściej używana strona

20

PRZYKŁADY DZIAŁANIA

ALGORYTMÓW WYMIANY STRON

„

W systemie pamięci wirtualnej są 4 ramki.

„

Wszystkie ramki są początkowo puste

„

W systemie pojawiają się następujące odniesień

(odwołań) do stron: 1, 2, 3, 4, 1, 4, 3, 4, 5, 2, 1, 4, 3, 4

11

21

PRZYKŁADY DZIAŁANIA

ALGORYTMÓW WYMIANY STRON

22

SEGMENTACJA W SYSTEMIE

Z PAMIĘCIĄ WIRTUALNĄ

„

Segmentacja z wymianą segmentów pomiędzy

pamięcią pierwszego i drugiego rzędu.

„

Zalety w porównaniu z prostą segmentacją:

zwiększony stopień wieloprogramowości.

„

Wady: złożoność zarządzania i narzut czasowy

związany z dostępem.

12

23

MECHANIZM SEGMENTACJI

NA ŻĄDANIE - PROBLEMY

„

Skomplikowana wymiana — segmenty mają

różne rozmiary.

„

Sprowadzenie segmentu do pamięci może

wymagać upakowania i/lub przesunięcia w

obszar wymiany jednego lub kilku segmentów

znajdujących się w pamięci fizycznej, co jest

procedurą czasochłonną.

„

Ze względu na zróżnicowany rozmiar czas

transmisji danych jest trudniej przewidywalny

(większy rozrzut w sensie statystycznym).

24