1

Zarządzanie pamięcią

wewnętrzną. Pamięć

wirtualna

Systemy operacyjne

wykład 6

2

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.

3

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.

4

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ą).

5

• Rysunek – przydzielanie pamięci

6

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).

7

Prostą przestrzeń adresową

zastosowano w procesorze Motorola
68000.

8

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ę).

9

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.

10

Stronicowanie cd.

Stronicowanie. Model stronicowania pamięci logicznej i fizycznej.

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

11

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).

12

Stronicowanie cd.

Stronicowanie. Dzielenie kodu w środowisku stronicowanym
[Źródło: Silberschatz, Peterson, Galvin "Podstawy systemów operacyjnych"]

13

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.

14

Podprog
-ram
Segmen
t 0

Program
główny

Segment
2

Tablica
symbol
i

Segme
nt 4

Proce-
dura

Seg-
ment

1

Stos
Segment

3

Pamięć fizyczna

Tablica
segmentów

Pamięć
fizyczna

Pamięć
logiczna

Przykład segmentacji

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

15

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.

16

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).

17

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.

18

PAMIĘĆ WIRTUALNA

19

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

20

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.

21

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).

22

Stronicowanie na

żądanie cd.

• 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.

23

Stronicowanie na

żądanie cd.

Aby zrealizować stronicowanie na

żądanie trzeba opracować

- algorytm przydziału ramek,
- algorytm zastępowania stron.

24

Stronicowanie na

żądanie cd.

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.

25

Stronicowanie na

żądanie cd.

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.

26

Stronicowanie na

żądanie cd.

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.

27

Stronicowanie na

żądanie cd.

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).

28

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).

29

Segmentacja na żądanie

cd.

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) .