Zarządzanie pamięcią wewnętrzną. Pamięć wirtualna

Systemy operacyjne

wykład 6

Podstawowe funkcje dotyczące zarządzania pamięcią wewnętrzną

Podstawowe funkcje dotyczące zarządzania pamięcią wewnętrzną (RAM) realizowane przez S.O.:

1. Śledzenie stanu pamięci,

2. Określenie strategii podziału pamięci,

3. Metody przydziału pamięci,

4. Metody i strategie zwalniania pamięci.

Sposoby podziału pamięci

1. Pamięć przydzielona w całości dla jednego zadania (procesu),

2. Przydzielanie wielu obszarów (stref),

3. Stronicowanie,

4. Segmentacja,

5. Segmentacja stronicowana.

Przydzielanie wielu obszarów (stref)

• Zarządzanie pamięcią w systemie wieloprogramowym polega na przydzielaniu pamięci rozmaitym procesom pozostającym w kolejce wejściowej (w oczekiwaniu na wprowadzenie do pamięci).

• Na początku pamięć stanowi jeden wielki blok - dziurę. Potrzebującemu procesowi przydziela się odpowiednią ilość pamięci z dziury. Kolejnym procesom - kolejne ilości. W efekcie powstaje zbiór dziur o różnych wymiarach, rozproszonych po całej pamięci. Gdy proces nadchodzi i zamawia pamięć, wtedy przegląda się ten zbiór w poszukiwaniu wystarczająco dużej dziury. (Przyległe dziury są łączone w jedną większą).

Przydzielanie wielu obszarów (stref) cd.

Problem - jak na podstawie listy wolnych dziur spełnić zamówienie na obszar o danym rozmiarze?

Przegląda się zbiór dziur, aby określić, która najlepiej nadaje się do przydziału.

Strategie wyboru dziury:

• pierwsza pasująca (pierwsza o wystarczającym rozmiarze)- jest to najszybszy przydział,

• najlepiej pasująca (najmniejsza z pasujących),

• najgorzej pasująca (największa).

Dwa pierwsze przydziały nie są najlepsze pod względem wykorzystania pamięci.

Opisany algorytm obarczony jest zewnętrzną fragmentacją (nie ma odpowiednio dużych, spójnych obszarów w pamięci).

Prostą przestrzeń adresową zastosowano w procesorze Motorola 68000.

Stronicowanie

• Pamięć fizyczna podzielona jest na bloki o stałej długości, zwane ramkami. Pamięć logiczna jest podzielona na bloki takiego samego rozmiaru, zwane stronami. Gdy ma nastąpić wykonanie procesu, wówczas jego strony z pamięci pomocniczej są wprowadzane w dowolne ramki.

• Każdy adres wygenerowany przez procesor dzieli się na dwie części: numer strony i odległość na stronie. Numer strony jest używany jako indeks w tablicy stron. Rozmiar strony jest określony przez sprzęt (np. od 512 do 2048 słów na stronę).

Stronicowanie cd.

Zaleta:

• Stronicowanie eliminuje zewnętrzną fragmentację. Pozostaje jedynie fragmentacja wewnętrzna. Tablica stron najczęściej jest przydzielana do każdego procesu. W bloku kontrolnym procesu (obok zawartości innych rejestrów) przechowuje się wskaźnik do tablicy stron.

Stronicowanie cd.

Stronicowanie cd.

Zastosowanie:

Strony dzielone - umożliwiają współdzielenie stron kodu programu. (Gdy np. kilku użytkowników korzysta z tego samego edytora tekstu w pamięci jest przechowywana jedna jego kopia).

Stronicowanie cd.

Stronicowanie. Dzielenie kodu w środowisku stronicowanym

[Źródło: Silberschatz, Peterson, Galvin "Podstawy systemów operacyjnych"]

Segmentacja

• Segmentacja jest schematem zarządzania pamięcią, w którym przestrzeń adresów logicznych jest zbiorem segmentów. Każdy segment ma nazwę i długość. Adresy określają nazwę segmentu i odległość wewnątrz segmentu.

• Segmentacja jest blisko związana z modelem zarządzania obszarami pamięci. Różnica polega na tym, że program może składać się z kilku segmentów.

Segmentacja cd.

Zalety:

Powiązanie ochrony pamięci z jej segmentami. Pozwala to np. segmenty rozkazów zdefiniować jako przeznaczone tylko do czytania lub wykonywania,

dzielenie kodu i danych.

Wady:

Zewnętrzna fragmentacja pamięci.

Przykład

Segmentację pamięci zastosowano już w procesorze Intel 8086.

Programy w tym środowisku były zwykle dzielone na segmenty kodu (CODE), danych (DATA) i stosu (STACK).

Segmentacja stronicowana

Stronicowanie usuwa zewnętrzną fragmentację i upraszcza problem przydziału - każda pusta ramka może być użyta na potrzebną stronę. Stronicuje się segmenty. Każdy segment ma osobną tablicę stron.

PAMIĘĆ WIRTUALNA

Poprzednio omówione strategie zarządzania pamięcią miały na celu utrzymanie wielu procesów w pamięci operacyjnej i umożliwienie wieloprogramowości. Każda z tych strategii wymagała, aby w pamięci znajdował się cały proces przed jego wykonaniem. Pamięć wirtualna jest techniką, która umożliwia wykonywanie procesów, pomimo że nie są one w całości przechowywane w pamięci operacyjnej. Zatem np. programy mogą być większe niż pamięć fizyczna.

W wielu przypadkach programy nie wykorzystują w całości swojego kodu. Często zawierają fragmenty, które mogą być niezmiernie rzadko używane.

Sposoby implementacji pamięci wirtualnej:

1. Stronicowanie na żądanie

2. Segmentacja na żądanie

Stronicowanie na żądanie

• Procesy rezydują w pamięci pomocniczej (na dysku), natomiast proces do wykonania jest wprowadzany do pamięci operacyjnej.

• Proces jest traktowany jako ciąg stron. Program zmieniania stron sprowadza do pamięci tylko strony niezbędne. Takie rozwiązanie wymaga środków sprzętowych (rozszerza się tablicę stron).

• Dopóki proces działa na stronach pozostających w pamięci, jego wykonanie przebiega normalnie. Gdy proces chce sięgnąć po informacje na stronie nie sprowadzonej to powstaje pułapka systemowa nazywana błędem strony. Sprzęt stronicujący spowoduje wtedy awaryjne przerwanie w S.O. S.O. musi wczytać żądaną stronę do pamięci i wznowić proces tak, jakby ta strona zawsze była w pamięci.

• Stronicowanie powinno być całkowicie przezroczyste dla procesu użytkownika.

Stronicowanie na żądanie cd.

• Problem:

• Co się stanie jeśli zajdzie potrzeba załadowania strony, a na liście wolnych ramek nie ma ani jednej wolnej ramki? Stosuje się wtedy zastępowanie stron.

• Zastępowanie stron

• Jeśli wszystkie ramki są zajęte znajduje się taką, która nie jest bieżąco używana i zwalnia się ją (zapisuje się jej zawartość na dysku i uaktualnia tablicę stron).

• Procedura obsługi błędów strony:

• 1. Odnalezienie lokalizacji potrzebnej strony na dysku,

• 2. Odnalezienie wolnej ramki:

• • gdy istnieje wolna - zostaje użyta

• • gdy nie ma wolnej ramki stosuje się algorytm zastępowania stron w celu wytypowania ramki-ofiary.

• • Stronę - ofiarę zapisuje się na dysku, zmieniając odpowiednie tablice stron i ramek.

• 3. Do zwolnionej (ew. wolnej) właśnie ramki wczytuje się potrzebną stronę i znowu zmienia tablice stron i ramek

• 4. Wznawia się działanie procesu.

• Aby zrealizować stronicowanie na żądanie trzeba opracować

• - algorytm przydziału ramek,

• - algorytm zastępowania stron.

Algorytmy zastępowania stron

Przy wyborze tego algorytmu należy kierować się tym, aby częstość błędów strony była

najmniejsza.

• Algorytm FIFO - każda strona ma zapisany czas wprowadzenia lub określone miejsce w kolejce FIFO. Do zastąpienia wybiera się najstarszą.

• Algorytm optymalny - idealne, właściwe nie stosowane w praktyce - zastępuje te stronę, która najdłużej nie będzie używana. Wymaga się wiedzy o przyszłych odniesieniach. Trudny do realizacji.

• Algorytm LRU - zastępowanie najdawniej używanych stron (least recently used) - zastępowana jest strona, która nie była używana od najdłuższego czasu. Z każda stroną kojarzony jest czas jej ostatniego użycia. Jest to realizowane przez dodanie do każdej pozycji w tablicy stron rejestru czasu użycia, a do procesora dodawany jest zegar logiczny lub licznik. Wskazania zegara są zwiększane za każdym odniesieniem do pamięci. Zastępowana jest strona z najmniejszą wartością odwołań. Żadnej implementacji metody LRU nie można wykonać bez odpowiedniego wyposażenia sprzętowego.

Algorytmy przybliżające metodę LRU - stosowane w przypadku braku odpowiedniego sprzętu do realizacji LRU:

- algorytm LFU - zastępowanie najmniej używanej strony,

- algorytm MFU - zastępowanie strony najczęściej używanej.

Przydział ramek

Problem do rozwiązania : jak rozdzielać stałą ilość wolnej pamięci między różne procesy?

Minimalna liczba ramek przypadających na proces jest zdefiniowana przez architekturę logiczną komputera, natomiast maksymalna ich liczba wynika z dostępnej pamięci fizycznej.

Algorytmy przydziału:

• przydział równy,

• przydział proporcjonalny w zależności od rozmiaru,

• przydział proporcjonalny w zależności od priorytetu procesu.

Problemy:

• Gdy proces otrzymuje bardzo małą ilość ramek - poniżej minimum wymaganego przez architekturę komputera wtedy wystąpi szybko brak strony, wtedy trzeba będzie zastąpić jakąś stronę, która za chwilę okaże się potrzebna.

• Dużą aktywność stronicowania określa się terminem szamotania. Proces szamoce się gdy spędza więcej czasu na stronicowaniu niż na wykonaniu.

• Zagadnienia związane ze stronicowaniem:

• - globalny a lokalny przydział ramek- zastępowanie w obrębie ramek przydzielonych do jednego procesu lub wśród wszystkich ramek. Przy zastępowaniu lokalnym - liczba ramek przydzielona do procesu nie zmienia się. Przy zastępowaniu globalnym proces nie może kontrolować własnej częstotliwości występowania błędów stron. Jego wykonanie zależy ponadto od tego jak zachowują się inne procesy. Z reguły większa przepustowość daje zastępowanie globalne.

• - stronicowanie wstępne- polega na jednorazowym wprowadzeniu do pamięci wszystkich stron procesu, o których wiadomo, że będą potrzebne.

• - rozmiar strony- ustalany przy projektowaniu maszyny(np. od 512 do 16384 bajtów).

Segmentacja na żądanie

• Wykonywany proces nie musi mieć w pamięci wszystkich swoich segmentów. Gdy proces odniesie się do segmentu zawierającego kod lub dane - sprzęt sprawdzi bit poprawności (w deskryptorze segmentu zawierającym informację o długości danego segmentu, trybie jego ochrony i umiejscowieniu) wskazujący czy żądany segment znajduje się w pamięci czy nie. Gdy nie ma to wywołuje pułapkę systemową (błąd segmentu). (Wtedy sprowadzany jest żądany segment (na miejsce innego wysłanego do pamięci), a przerwany rozkaz jest kontynuowany).

• Problem: Który segment ma być zastąpiony przy błędzie segmentu?

• Można np. odczytywać z deskryptora segmentu bit udostępnienia, który sygnalizuje, że dany segment był już używany. Korzystając z tych bitów ustawia się kolejkę segmentów i stąd bierze segmenty do zastąpienia.

• Segmentacja na żądanie nie jest optymalnym środkiem na użytkowanie zasobów systemu komputerowego, ale jest rozsądnym kompromisem na rzecz funkcjonalności w sytuacji ograniczeń sprzętowych, uniemożliwiających stronicowanie na żądanie. (Np. Intel 80286 operuje segmentami, nie ma możliwości stronicowania) .