(Microsoft PowerPoint - SO-W6-Zarz\271dzanie pami\352ci\271 w systemach operacyjnych, v1.2.3)

ZARZ DZANIE

PAMI CI W

SYSTEMACH

OPERACYJNYCH

Jerzy Peja

Politechnika Szczeci ska

Wydział Informatyki

ul. ołnierska 49, 71-210 Szczecin

Agenda

Wprowadzenie
Wymiana (ang. swapping)
Przydzielenie ci głego obszaru
Stronicowanie
Segmentacja
Segmentacja ze stronicowaniem

Deklaracja

Przy opracowywaniu niniejszego wykładu korzystano

z ogólnodost pnych slajdów do ksi ki

Podstawy

systemów operacyjnych (A. Silberschatz, P.B. Galvin,

G. Gagne) oraz do wykładów

Systemy operacyjne

(Jerzy Brzezi ski i Dariusz Wawrzyniak),

udost pnionych w ramach

Uczelni On-line

Pami jako zasób systemu komputerowego

Pami jest zasobem słu cy do przechowywania danych i

programów.
Z punktu widzenia systemu pami jest zasobem o strukturze

hierarchicznej (pocz wszy od rejestrów procesora, przez pami

podr czn , pami główn , sko czywszy na pami ci masowej), w

której na wy szym poziomie przechowywane s dane, stanowi ce

fragment zawarto ci poziomu ni szego.
Z punktu widzenia procesu (równie procesora) pami jest

zbiorem bajtów identyfikowanych przez adresy, czyli tablic

bajtów, w której adresy s indeksami.

Hierarchia urz dze przechowywania danych

Wprowadzenie

Program musi by pobrany do pami ci głównej i przekształcony w

proces, który mo na wykona .
Kolejka wej cia – zbiór procesów na dysku, które oczekuj na

umieszczenie w pami ci i uruchomienie.
Jeden z procesów zostaje wybrany i załadowany do pami ci; podczas

wykonywania pobiera

rozkazy i dane z pami ci, a po zako czeniu

zwalnia zajmowan pami .
Wi kszo systemów pozwala procesowi u ytkownika przebywa w

dowolnej cz ci pami ci fizycznej – wpływa to na zakres adresów

dost pnych dla procesu.
Program u ytkownika przechodzi kilka faz zanim zostanie wykonany –

podczas tych faz reprezentacja adresów mo e ulega zmianie.
W programie ródłowym adresy wyra one s w sposób

symboliczny

(np.

licznik) – kompilator na ogół wi e je z adresami wzgl dnymi, a

konsolidator wi e dalej te adresy wzgl dne z adresami

bezwzgl dnymi.

Translacja

W wyniku translacji (kompilacja, asemblacja) powstaje

przemieszczalny moduł wynikowy (ang. relocatable object

module), w którym wszystkie adresy liczone s wzgl dem adresu

pocz tku modułu.

Na tym etapie mo na wyliczy adresy obiektów i kodu znajduj cych

si w tym module wzgl dem pocz tku modułu.
Adresy odnosz ce si do obiektów i kodu w innych modułach mog

zosta zwi zane dopiero na etapie

ł czenia (nazywanym tak e

konsolidacj ).

Gdyby program składał si z jednego modułu, a jego docelowa

lokalizacja w pami ci była z góry znana, na etapie translacji

mogłyby zosta wygenerowane

adresy fizyczne.

Wielokrokowe przetwarzanie programu

u ytkownika

Wi zanie instrukcji i danych z pami ci

Fazie kompilacji (ł czenie statyczne): Je li a priori znane jest miejsce,

w którym proces b dzie przebywał w pami ci, to mo na wygenerowa

kod bezwzgl dny (absolute code); zmiana poło enia kodu w pami ci

wymaga jego rekompilacji.
Fazie ładowania (ł czenie dynamiczne w czasie ładowania): Je li

przyszłe poło enie procesu w pami ci nie jest znane podczas kompilacji,

to kompilator musi generowa

kod przemieszczalny (relocatable code);

wi zanie adresów nast puje w czasie ładowania kodu.
Fazie wykonania ł czenie dynamiczne w czasie wykonania): Je eli

proces podczas wykonania mo e by przemieszczany w pami ci, to

wi zanie adresów musi by opó nione do czasu wykonania – wymaga to

specjalnego sprz tu (stosowane w wi kszo ci systemów), np. rejestr

bazowy i graniczny.

Wi zanie instrukcji i danych z adresami w pami ci mo e si

odbywa w:

Wi zanie adresów

Ł czenie statyczne

W czasie ł czenia modułów przemieszczalnych w jeden program

ładowalny zwany te

modułem absolutnym (ang. absolute

module), do adresów przemieszczalnych dodawane s warto ci,

wynikaj ce z przesuni cia danego modułu przemieszczalnego

wzgl dem pocz tku modułu absolutnego.
Gdyby docelowa lokalizacja programu w pami ci była z góry

znana, na etapie tym mogłyby zosta wygenerowane adresy

fizyczne.
Systemowe biblioteki j zyków programowania s traktowane jak

ka dy inny moduł wynikowy i doł czane przez program ładuj cy

do binarnego obrazu programu.

Marnotrawstwo pami ci operacyjnej oraz przestrzeni dyskowej.

Przestrze adresów fizycznych i logicznych

Koncepcja przestrzeni adresów logicznych, która jest

powi zana z oddzielon od niej fizyczna przestrzeni

adresów jest podstaw wła ciwego zarz dzania pami ci .

adresy logiczne: generowane przez CPU w kontek cie

aktualnie wykonywanego; nazywane s tak e adresami

wirtualnymi
adresy fizyczne: zbiór adresów przekazywanych do

układów pami ci głównej (fizycznej); adresy widziane

przez jednostk pami ci

Adresy logiczne i fizyczne s :

takie same, gdy adresy s wi zane w czasie kompilacji i

ładowania
ró ne, gdy adresy wi e si w czasie wykonania

Jednostka zarz dzaj ca pami ci (ang.

Memory-Management Unit (MMU))

Urz dzenie sprz towe, które odwzorowuje adresy wirtualne

na fizyczne

W schemacie MMU warto zawarta w rejestrze relokacji

jest dodawana do adresu generowanego przez proces

u ytkownika w momencie, gdy jest przesyłany do pami ci.

Program u ytkownika operuje na poziomie adresów

logicznych; nigdy nie widzi rzeczywistego adresu fizycznego.

Adres logiczny i fizyczny

Dynamiczna relokacja za pomoc rejestru

relokacji

Ł czenie dynamiczne

Ł czenie dynamiczne - ł czenie opó nione do czasu wykonania;

zazwyczaj dotyczy bibliotek systemowych

W miejscu odwołania bibliotecznego w obrazie binarnym znajduje si

zakładka (ang. stub) (namiastka procedury) – mały fragment kodu

wskazuj cy jak odnale w pami ci lub załadowa z dysku odpowiedni

podprogram.
Zakładka wprowadza na swoje miejsce adres potrzebnego

podprogramu i powoduje jego wykonanie.
Wymaga wsparcia ze strony sytemu operacyjnego – sprawdzanie

czy podprogram biblioteczny jest w obszarach pami ci procesów oraz

zezwalanie by wiele procesów miało dost p do tych samych adresów

pami ci.

•

Lepsze wykorzystanie pami ci operacyjnej oraz przestrzeni dyskowej.

•

Szczególnie u yteczna dla bibliotek, np. aktualizacja biblioteki nie

wymaga ponownej konsolidacji korzystaj cych z niej programów

biblioteki dzielone (shared libraries).

Nakładki

Nakładki - w pami ci przechowuje si tylko te cz ci przestrzeni

adresowej, które s niezb dne w danej chwili.
Umo liwia wykonywanie programów wi kszych od

przydzielonego im obszaru pami ci.
Implementowana przez u ytkownika, nie jest wymagane wsparcie

ze strony systemu operacyjnego, projektowanie programu jest

przez to bardzo zło one

Nakładki asemblera dwuprzebiegowego

Wymiana (ang. swapping)

Proces mo e zosta czasowo wysłany z pami ci głównej do

zewn trznej, a po jakim czasie sprowadzony ponownie do

pami ci głównej
Jako pami zewn trzna na potrzeby wymiany słu y du y szybki

dysk z dost pem bezpo rednim.
Zwijanie i rozwijanie – wariant wymiany stosowany w

algorytmach planowania priorytetowego; procesy o wy szym

priorytecie daj cy obsługi mo e spowodowa usuni cie procesu

o ni szym priorytecie.
Główny narzut: czas transmisji
Ró ne wersje wymiany s realizowane w wielu systemach, np. w

Unixie czy Microsoft Windows

Schematyczna ilustracja wymiany

Podział pami ci

Podział stały, w którym przydzielane jednostki s odgórnie

wyznaczone

partycje o równym rozmiarze
partycje o ró nych rozmiarach

Podział dynamiczny, w którym jednostki definiowane s z pewn

dokładno ci stosownie do potrzeb
Podział na bloki bli niacze (zwany te metod s siedzkich stert),

który jest rozwi zaniem po rednim pomi dzy podziałem

statycznym a dynamicznym i polega na połowieniu wi kszych

obszarów (zbyt du ych) na dwa mniejsze (o równej wielko ci).

Fragmentacja

Fragmentacja zewn trzna: suma wolnych obszarów w pami ci

wystarcza na spełnienie dania, lecz nie stanowi spójnego

obszaru
Fragmentacja wewn trzna: przydzielona pami mo e by nieco

wi ksza ni dana. Ró nica mi dzy tymi wielko ciami znajduje

si wewn trz przydzielonego obszaru, lecz nie jest

wykorzystywana
Redukowanie fragmentacji zewn trznej poprzez upakowanie

(przemieszczanie): umieszczenie całej wolnej pami ci w jednym

bloku; mo liwe tylko w przypadku, gdy adresy s wi zane w

czasie wykonania; ró ne strategie upakowania

Ogólny obraz pami ci fizycznej

Ci gła alokacja pami ci

Pami dzielona jest na dwa obszary:

dla

rezyduj cego systemu operacyjnego (trzymany zwykle w

ni szych obszarach pami ci ł cznie z wektorem przerwa ) i dla

u ytkownika (wy sze obszary pami ci),
np. IBM PC: BIOS (programy steruj ce urz dze ) w ROMie (górne

adresy), SO w RAMie (dolne adresy)

Alokacja pojedynczego obszaru

Rejestr bazowy (relokacji) i graniczny słu do wzajemnej ochrony

procesów u ytkownika oraz przed zmian danych i kodu samego

systemu operacyjnego
Rejestr relokacji zawiera warto najmniejszego adresu fizycznego.

System z jednym u ytkownikiem

Alokacja ci gła

Przydział wielu obszarów - w systemach wieloprogramowych w

pami ci równocze nie przebywa wiele programów, ka dy we

własnym obszarze.

Dziura (ang. hole) – wolny obszar pami ci; dziury ró nych

rozmiarów s rozrzucone po pami ci.
Gdy przybywa nowy proces, to przydzielana jest mu pami w

obszarze dziury o wielko ci wystarczaj cej do załadowania procesu.
System operacyjny zarz dza informacja o :

a) przydzielonych obszarach b) obszarach wolnych (dziurach)

process 5

process 8

process 2

process 5

process 2

process 5

process 2

process 5
process 9

process 2

process 9

process 10

Podział stały

Podział pami ci na stałe obszary (strefy, partycje), których

rozmiar i poło enie ustalane s na etapie konfiguracji systemu.
Przydział całego obszaru o rozmiarze wi kszym lub równym

zapotrzebowaniu, okre lonym w  daniu.
Zalety: łatwo  implementacji i zarz dzania
Wady: słaba efektywno  wykorzystania pami ci (fragmentacja

wewn trzna, ograniczona odgórnie liczba jednocze nie

przydzielonych partycji).

Podział stały — partycje o równym rozmiarze

Podział stały — partycje o ró nych rozmiarach

Podział dynamiczny

Podział pami ci tworzony jest w czasie pracy systemu stosownie

do da procesów
Proces ładowany jest w obszar o rozmiarze dosy dokładnie

odpowiadaj cym jego wymaganiom.
Zalety: lepsze wykorzystanie pami ci (brak fragmentacji

wewn trznej)
Wady: skomplikowane zarz dzanie, wynikaj ce z konieczno ci

utrzymywania odpowiednich struktur danych w celu identyfikacji

obszarów zaj tych oraz wolnych.

Problem dynamicznej alokacji pami ci

Pierwszy pasuj cy (ang. first fit): przydziela si pierwszy obszar

o wystarczaj cej wielko ci (nast pny pasuj cy: szukanie

rozpoczyna si od miejsca, w którym ostatnio zako czono

szukanie); z reguły krótszy czas szukania
Najlepiej pasuj cy (ang. best fit): przydziela si najmniejszy z

dostatecznie du ych obszarów; wymaga przeszukania całej listy (o

ile nie jest uporz dkowana wg rozmiaru); pozostaj ca cz

obszaru jest najmniejsza
Najgorzej pasuj cy (ang. worst fit): przydziela si najwi kszy

obszar; wymaga przeszukania całej listy; pozostaj ca cz

obszaru jest najwi ksza.
Nast pne dopasowanie — podobnie jak pierwszy pasuj cy, ale

poszukiwania rozpoczyna si od miejsca ostatniego przydziału.
Pierwszy pasuj cy i najlepszy pasuj cy lepsze ze wzgl du na czas

i wykorzystania pami ci.

Przykład planowania

Porównanie ró nych sposobów upakowania

pami ci

System bloków bli niaczych (ang.

buddy

)

Metoda bloków bli niaczych polega na sukcesywnym dzieleniu

dost pnego obszaru pami ci na połowy i przydziale najlepiej

dopasowanego bloku, którego rozmiar jest pot g przy podstawie

Jest przy tym ustalony minimalny rozmiar przydzielanego bloku

(wykładnik L).

Jest to metoda po rednia pomi dzy przydziałem stałym a

dynamicznym
Pami dost pna dla procesów u ytkownika ma rozmiar 2

Przydzielany blok ma rozmiar 2

, gdzie L K U.

Pocz tkowo dost pny jest jeden blok o rozmiarze 2

Realizacja przydziału obszaru o rozmiarze

s polega na znalezieniu

lub utworzeniu (przez połowienie) bloku o rozmiarze 2

takim, e

i−1

< s 2

System bloków bli niaczych — przykład

Stronicowanie

Przestrze adresów logicznych procesu mo e by nieci gła; procesowi

przydzielana process fizyczna ilekro jest to pó niej konieczne.
Pami fizyczna jest podzielona na bloki jednakowego rozmiaru, zwane

ramkami (rozmiar jest pot g 2, mi dzy 0.5 K bajtów a 8 Kbajtów)
Logiczna przestrze adresowa procesu jest podzielona na bloki o

rozmiarze takim jak ramki, zwane

stronami

Strony przebywaj w pami ci pomocniczej, s sprowadzane do pami ci

głównej i umieszczane w wolnych ramkach (program o n stronach

potrzebuje n ramek); strony nie musz zajmowa ci głego obszaru

fizycznego
Fragmentacja wewn trzna, brak fragmentacji zewn trznej (małe ramki to

mniejsza fragmentacja wewn trzna, ale wi kszy narzut na tablice stron)
System przechowuje informacje o wolnych ramkach

Tablica stron

procesu słu y do odwzorowywania adresów logicznych w

adresy fizyczne.

Schemat translacji adresów

Adres logiczny składa si z dwóch cz ci:

numer strony (p) - słu y jako indeks w tablicy stron, która zawiera

adres bazowy ka dej strony w pami ci fizycznej
przesuni cie w stronie (d) - numer bajtu w stronie w poł czeniu z

adresem bazowym definiuje adres w pami ci fizycznej, wysyłany do

MMU.

Schemat translacji adresów

Przykład stronicowania

Pami logiczna:

16 bajtów (4 bity)

Roz.strony

: 4 bajty (potrzebne 2 bity)

Stron:

4 (potrzebne 2 bity)

Pami fizyczna:

32 bajty (8 ramek)

Roz.ramki

: 4 bajty (potrzebne 2 bity)

Ramek:

: 8

8 (potrzebne 3 bity)

0000

5X4 = 20

20 + 0 = 20

1110

2X4 = 8

8 + 2 = 10

Schemat translacji adresów

Załó my, e

rozmiar strony

(w przestrzeni adresów logicznych)

wynosi 2

Załó my, e

przestrze adresów logicznych

ma rozmiar 2

St d (dla m> n) m - n bitów

wy szego rz du

logicznej przestrzeni

adresowej przypada na numer strony – poniewa w logicznej

przestrzeni adresowej mamy 2

m-n

stron.

Bity

ni szego rz du

definiuj przesuni cie (ang. offset) w ramach

strony.

Numer strony

Offset

m - n

Schemat translacji adresów

Adresy logiczne

00 00

00 01

00 10

00 11

01 00

01 01

01 10

01 11

10 00

10 01

10 10

10 11

11 00

11 01

11 10

11 11

strona 0

strona 1

strona 2

strona 3

Tabela stron

Schemat translacji adresów

Bity

ni szego rz du

opisuj offset.

Poniewa wielko ci strony i ramki s takie same, wi c liczba bitów

pola offset nie zmienia sie.

Nr strony

offset

m - n

Tabela

stron

Nr ramki

Offset

k - n

Przyj ta fizyczna

przestrze adresów 2

Schemat translacji adresów - przykład

Nr strony

offset

010

Nr ramki

Offset

010

Przestrze logiczna: 2

Przestrze

fizyczna: 2

Schemat translacji adresów

Adresy logiczne

00 00

00 01

00 10

00 11

01 00

01 01

01 10

01 11

10 00

10 01

10 10

10 11

11 00

11 01

11 10

11 11

strona 0

strona 1

strona 2

strona 3

Tabela stron

000 00

000 01

000 10

000 11

001 00

001 01

001 10

001 11

010 00

010 01

010 10

010 11

011 00

011 01

011 10

011 11

ramka 0

ramka 1

ramka 2

ramka 3

011 01

Wolne ramki

Before allocation

After allocation

Implementacja tabeli stron

Tablica stron jest przechowywana w pami ci głównej
Rejestr bazowy tablicy stron (ang. Page-table base register, PTBR)

wskazuje jej pocz tek
Rejestr długo ci tablicy stron (Page-table length register, PRLR)

okre la rozmiar tabeli stron
Ka dy dost p do danych/instrukcji programu wymaga dwóch

dost pów do pami ci głównej – jednego do tabeli stron, drugiego

do danych/kodu.
Przy pieszenie translacji adresu jest mo liwe dzi ki zastosowaniu

rejestrów asocjacyjnych (zwanych tak e buforami translacji

bliskiego otoczenia, ang. TLB).

Pami asocjacyjna

Pami asocjacyjna – przeszukiwanie równoległe

Translacja adresu (A´, A´´)

Je li A´ znajduje si w rejestrze asocjacyjnym, to pobierz ramk #.
W przeciwnym przypadku pobierz ramk # z tablicy stron, znajduj cej

si w pami ci

Strona #

Ramka #

Bufory translacji adresów stron (TLB) -

stronicowanie sprz towe

Efektywny czas dost pu

Współczynnik trafie (ang. hit ratio) - procent numerów stron

znajdowanych w rejestrach asocjacyjnych (zale y od liczby

rejestrów).
Na przykład, niech:

współczynnik trafie =

czas przegl dania TLB =

czas dost pu do pami ci = 1 mikrosekunda

to efektywny czas dost pu:

EAT = (1 +

ε) α + (2 + ε)(1 – α) = 2 + ε – α

Ochrona pami ci

Ochrona pami ci implementowana jest za pomoc bitu ochrony

skojarzonego z ka d ramk .

Bit wa na-niewa na (ang. valid-invalid) jest doł czany do

ka dego wpisu w tabeli stron:

“wa na” oznacza, e zwi zana z nim strona znajduje w przestrzeni

adresów logicznych procesu i st d jest to strona dozwolona.
“niewa na” oznacza, e zwi zana z nim strona nie znajduje w

przestrzeni adresów logicznych procesu i st d jest to strona

niedozwolona.

Bit „wa na” (v) lub „niewa na” (i) w tabeli stron

Schemat translacji adresów

Schemat translacji dla dwupoziomowej 32 bitowej architektury

stronicowania,

Podej cie takie zastosowano mi dzy innymi w architekturze Intel IA-32.

Zewn trzn tablic stron okre la si jako katalog stron, a wewn trzn po

prostu jako tablic stron.

Współdzielenie stron

Stronicowanie umo liwia dzielenie wspólnego kodu:

taki kod musi by wielowej ciowy, ang. reentrant, czyli nie mo e

modyfikowa sam siebie); edytory, kompilatory itp.
Współdzielony kod musi wyst powa w tym samej przestrzeni

adresów logicznych wszystkich procesów.

Prywatny kod i dane

Ka dy proces przechowuje oddzieln kopie kodu i danych
Strony przechowuj ce prywatny kod i dane mo e wyst pi w

dowolnym miejscu przestrzeni adresów logicznych ka dego z

procesów.

Do ochrony pami ci słu bity ochrony przypisane ka dej ramce i

zwykle umieszczone w tablicy stron

Przykład współdzielenia stron

Segmentacja

Schemat zarz dzania pami ci zgodny ze sposobem widzenia

pami ci przez u ytkownika
Program jest zbiorem segmentów. Segment jest jednostk logiczn

tak jak:

program główny,
procedura,
funkcja,
stos,
tablica symboli,
tablice,
zmienne lokalne i globalne

Program z punktu widzenia programisty

Logiczny obraz segmentacji

Przestrze u ytkownika

Przestrze pami ci fizycznej

Architektura segmentacji

Adres logiczny zwiera dwa elementy:

<numer-segmentu, offset>,

Tabela segmentów – odwzorowuje dwuwymiarowe adresy

fizyczne; ka dy wpis w tabeli zawiera:

baz - zawiera fizyczny adres pocz tku segmentu w pamieci,
ograniczenie - rozmiar segmentu:

Rejestr bazowy tabeli segmentów (ang. segment-table base

register, STBR) wskazuje na miejsce tabeli segmentów w pami ci.
Rejestr długosci tabeli segmentów (ang. segment-table length

register, STLR) wskazuje liczbe sementów wykorzystywanych

przez program;

numer segmentu s jest poprawny je li s < STLR.

Architektura segmentacji

Relokacja

dynamiczna,
za pomoc tabeli segmentów.

Współdzielenie

współdzielone segmenty,
te same numery segmentów.

Alokacja.

pierwszy pasuj cy/najlepiej pasuj cy
fragmentacja zewn trzna.

Architektura segmentacji

Ochrona - z ka d pozycj w tablicy segmentów s zwi zane bity

ochrony:

bit wa no ci = 0

niepoprawny segment

uprawnienia read/write/execute

Bity ochrony zwi zane z segmentem; współdzielenie kodu

wyst puje na poziomie segmentu.
Poniewa segmenty ró ni si rozmiarem, to alokacja pami ci jest

problemem dynamicznej alokacji pami ci..
Przykład segmentacji pokazany jest na jednym z nast pnych

slajdów.

Segmentacja sprz towa

Segmentacja ze stronicowaniem – MULTICS

Ka dy segment ma swoj tablic stron, znika problem

fragmentacji zewn trznej.

Deskryptor segmentu zawiera adres tablicy stron segmentu (w

pami ci), długo segmentu i pomocnicze bity; tablica segmentów

te jest stronicowana

Schemat translacji adresów w systemie

MULTICS