1

CAP. 6. NIVELUL SISTEMULUI DE OPERARE

Poziţionarea nivelului sistemului de operare în structura stratificată a nivelurilor unui calculator

Memoria:

fizică:

o liniile fizice de adresă externe ale procesorului (lăţimea magistralei de adrese, m);

o spaţiul de memorie fizic instalată în sistemul de calcul (capacitatea de adresare fizică, 2m);

virtuală:

o spaţiu de memorie creat de SO, care conţine un model al memoriei şi al adreselor de

memorie pe care un program le are la dispoziţie (este mai mare decât memoria fizică);

o suportul fizic (HDD) pe care SO salvează zone din memoria totală disponibilă pentru

a asigura spaţii libere în zona de memorie fizică, destinate porţiunilor de cod sau de

date cu care programul lucrează la momentul respectiv.

2

Fig. 6.2. Legătura între memoria fizică şi memoria virtuală.

3

Conceptul de paginare

Paginarea = procedeul de realizare în memorie a unor blocuri fixe, numite pagini, care pot fi utilizate

în mecanismul interschimbării proceselor (transferul blocurilor între memoria internă şi externă).

Este un mecanism transparent utilizatorului, apanaj al sistemului de operare/proiectantului.

Fig. 6.1. Exemplu simplu de paginare.

4

Sistemul de gestiune al memoriei virtuale, prin blocul MMU (Memory Management Unit) al

procesorului, parcurge următoarele operaţii la execuţia unei instrucţiuni din pagina următoare:

1. salvează conţinutul memoriei principale (MP) în memoria secundară;

2. localizează pagina respectivă în memoria secundară;

3. încarcă această pagină în MP;

4. asociază adreselor absolute adresa de memorie fizică (în ex. din fig. 6.1, de la 0 la 4095);

5. continuă execuţia programului.

Tabelul 6.1

Comparaţie între capacităţile de adresare a memoriei fizice şi a memoriei virtuale

Procesor Memoria fizică maximă Memoria virtuală maximă

8086 1 MB (20 linii) –

80286 16 MB (24 linii) 1 GB

80386 4 GB (32 linii) 64 TB

80486 4 GB (32 linii) 64 TB

Pentium 4 GB (32 linii) 64 TB

post-Pentium (Pro/II/III/4/...) 64 GB (36 linii) 64 TB

Core i7 1 TB (40 linii) 256 TB

5

Implementarea paginării

Fig. 6.3. Exemplu de paginare, cu 16 pagini în memoria virtuală (de 64 KB, 16 linii de adresă), 8

cadre de pagină în memoria fizică (de 32 KB, 15 linii de adresă) şi dimensiunea paginii de 4 KB.

6

Fig. 6.4. Gestiunea memoriei fizice folosind tabelul de pagini (adresa completă pe 32 de biţi).

Caracteristicile & avantajele paginării:

mărimea fixă a paginilor intră corect într-un sector al unui disc;

un obiect în memorie nu trebuie să fie continuu: pagina este o nouă cuantă de informaţie;

mecanismul paginării nu este vizibil pentru utilizator;

două niveluri de adresare indirectă a memoriei: o referinţă într-un director, din care se

selectează o tabelă a paginilor (TLB optimizează translaţia adresei virtuale în adresă fizică);

directorul şi tabelele de pagini au o structură uniformă, fiind tratate ca nişte pagini speciale;

prin bitul absent/prezent (0/1), MMU verifică prezenţa unei pagini în memoria fizică.

7

Paginarea la cerere vs. modelul setului de lucru

O posibilă mapare a primelor 16 pagini virtuale în memoria principală, cu 8 cadre de pagină

8

Eroare de pagină (page fault) = situaţia în care se face o referire la o adresă dintr-o pagină care

nu se află în memoria principală SO trebuie să citească în pagina cerută de pe disc, să

introducă noua sa adresă fizică în tabelul de pagini şi să repete instrucţiunea care a provocat eroarea.

Reducerea numărului de erori de pagină se poate face în două moduri:

paginarea la cerere – o pagină este adusă în memorie numai când este solicitată, nu în avans;

dezavantaj: în cazul operării prin diviziune în timp, schimbarea repetată a paginilor devine critică:

principiul localizării – la orice moment de timp, t, există un set al tuturor paginilor folosite de

cele mai recente k referiri la memorie se presupune că setul de lucru (working set), w(k, t),

variază lent în timp şi poate fi păstrat în memorie ca bază de pornire pentru reducerea erorilor.

Politici de înlocuire a paginilor

Dacă memoria este complet ocupată, la apariţia unei erori de pagină, politicile de înlocuire stabilesc

care pagini trebuie să fie înlocuite. Paşii parcurşi pentru tratarea excepţiei page fault:

1. aplicaţia accesează o pagină care nu este prezentă în memoria fizică;

2. blocul MMU (Memory Management Unit) generează excepţia page fault;

3. este aleasă o pagină goală (un cadru de pagină neocupat);

4. dacă nu este găsită nicio pagină goală, este aleasă una care urmează a fi evacuată din

memoria virtuală, această alegere fiind făcută pe baza unor algoritmi de înlocuire;

5. dacă pagina a fost modificată, această pagină este mai întâi scrisă pe disc;

6. pagina necesară este citită de pe disc;

7. pagina este mapată în spaţiul de adrese al aplicaţiei;

8. este reluată execuţia aplicaţiei.

9

Algoritmi de înlocuire a paginilor

1. Algoritmul optimal (Belady)

Fiecare pagină se etichetează cu numărul de instrucţiuni care se vor executa până când pagina

este referită pentru prima dată se elimină pagina cu cea mai mare valoare a etichetei.

Dezavantaj: nu poate fi implementat deoarece SO nu poate determina exact momentele referirilor.

Exemplu:

şir de referiri

cadre de pagină

Rata de page fault (pagini invalide) = 9

2. Algoritmul NRU (Not Recently Used)

Pentru fiecare pagină existentă în memorie, intrarea din tabelul de pagini conţine doi biţi de stare:

R (referred) – este pus în 1 ori de câte ori pagina este referită (la citire sau la scriere);

M (modified): – este pus în 1 atunci când pagina este modificată.

Aceşti biţi trebuie actualizaţi la fiecare referire a memoriei. Iniţial, sunt puşi în 0. Odată pus în 1,

un bit rămâne în aceeaşi valoare până când este resetat explicit de către SO. Periodic, R este pus în 0.

10

Sistemul de operare distinge 4 clase de pagini:

clasa 0: nereferite, nemodificate (R = 0, M = 0);

clasa 1: nereferite, modificate (R = 0, M = 1);

clasa 2: referite, nemodificate (R = 1, M = 0);

clasa 3: referite, modificate (R = 1, M = 1).

Pagina eliminată este selectată aleator din clasa având cel mai mic indice.

3. Algoritmul FIFO (First-In, First-Out)

Asociază fiecărei pagini momentul intrării în memorie se înlocuieşte pagina cea mai veche.

Exemplul 1:

şir de referiri

cadre de pagină

Rata de page fault (pagini invalide) = 15

11

Exemplul 2:

Anomalia lui Belady:

Pentru unii algoritmi de înlocuire, numărul

erorilor de page fault creşte dacă se măreşte

numărul de frame-uri (cadre de pagină).

12

4. Algoritmul celei de-a două şanse (Second Chance)

Este o combinaţie între FIFO şi NRU, care evită neajunsul algoritmului FIFO de a elimina din

memorie o pagină utilizată intens: caută o pagină veche, nereferită în perioada anterioară de ceas.

Se verifică bitul R al celei mai vechi pagini:

dacă R = 0 – pagina este veche şi neutilizată este înlocuită imediat;

dacă R = 1 – se pune R = 0, pagina este mutată la sfârşitul listei şi procesul de căutare continuă.

Exemplu:

Numerele reprezintă momentele la care paginile au fost aduse în memorie.

13

5. Algoritmul Clock

Este o optimizare a algoritmului Second Chance, bazată tot pe FIFO, care înlocuieşte lista de

pagini cu o coadă circulară, în care se verifică bitul R cu ajutorul unui pointer, nemaifiind nevoie

de mutarea la sfârşitul listei a primei pagini întâlnite cu R = 1 se înlocuieşte pagina cea mai veche.

Exemplu:

14

6. Algoritmul LRU (Least Recently Used)

Asemănător NRU, urmăreşte paginile într-un interval de timp mai scurt decât o perioadă de ceas.

Idee: paginile intens utilizate în ultimele câteva instrucţiuni vor fi, probabil, intens utilizate şi în

următoarele câteva instrucţiuni (principiul localizării temporale) elimină pagina neutilizată de

cel mai mult timp, fiind o bună aproximare a algoritmului optimal (Belady).

Moduri de implementare:

tip coadă – se construieşte o listă înlănţuită cu toate paginile din memorie, la sfârşitul căreia

se află paginile nereferite de cel mai mult timp, iar, la vârf, se află cele referite recent,

intrările din listă trebuind rearanjate la fiecare referire metodă foarte lentă.

tip contor (counter) – un contor incrementat la fiecare instrucţiune atribuie paginii accesate

valoarea sa curentă elimină pagina cu valoarea cea mai mică a contorului cost ridicat.

Avantaj: algoritmul LRU nu suferă de anomalia lui Belady.

şir de referiri

cadre de pagină

Rata de page fault (pagini invalide) = 12

15

Dezavantaj: în anumite situaţii (folosirea ciclurilor întinse pe mai multe pagini) eşuează lamentabil.

Eşec al algoritmului LRU – o buclă extinsă

peste 9 pagini virtuale cu 8 cadre de pagină:

(a) moment: intră pagina 7;

(b) moment: intră pagina 8 (out 0);

(c) moment: intră pagina 0 (out 1) etc.

În aceste situaţii, algoritmul MRU (Most

Recently Used) sau alte variante derivate ale

LRU sunt mai eficiente.

7. Algoritmul Random

Elimină paginile din memorie în mod aleator.

Avantaj: de obicei, are rezultate mai bune decât FIFO.

Dezavantaj: se descurcă mai bine decât LRU doar în cazul ciclurilor.

Exemplu: IBM OS/390 foloseşte comutarea între LRU şi Random (când performanţele LRU scad).

8. Algoritmul NFU (Not Frequently Used)

Este o optimizare a LRU, în cazul în care tabelul de pagini conţine mulţi pointer-i cu valori nule.

Atribuie fiecărei pagini câte un contor independent, incrementat cu 1 pentru toate paginile referite

într-o perioadă de ceas, eliminând pagina cu valoarea cea mai mică a contorului viteză redusă.

16

9. Algoritmul Aging

Este o optimizare a NFU, luând în considerare şi factorul interval de timp: ţine evidenţa apelurilor

în ultimele n intervale de timp (n = numărul de biţi pe care lucrează procesorul: 16/32/64).

Contorul unei pagini este întâi deplasat spre dreapta, înainte ca bitul de referinţă să fie adăugat în

partea stângă a numărului binar. Paginile apelate mai rar, dar mai recent, au prioritate mai mare decât

paginile apelate des, dar în trecut se elimină pagina cu contorul cel mai scăzut.

Exemplu: R = 1, dacă pagina a fost referită în ultimul interval se elimină o pagină cu R = 0.

17

10. Algoritmul WS (Working Set)

Este un algoritm cu un grad mare de generalitate, la care, pentru fiecare pagină, se ţine evidenţa

biţilor R şi M + un câmp al momentului ultimei accesări (time of last use).

18

t

Fig. 6.5. Dimensiunea setului de pagini utilizate de cele mai recente k apeluri de memorie,

în funcţie de timp (t).

19

11. Algoritmul WSClock (Working Set Clock)

Este o optimizare a algoritmului Working Set, care foloseşte o listă de pagini circulară (Clock).

20

Comparaţie între algoritmii de înlocuire a paginilor

Algoritm Comentariu

Optimal (Belady) Nu se poate implementa, dar e util ca test de comparaţie

NRU Foarte rudimentar

FIFO Posibil să elimine pagini importante

Second Chance Optimizare majoră faţă de FIFO

Clock Realist

LRU Excelent, dar dificil de implementat cu precizie

NFU Aproximare rudimentară a algoritmului LRU

Aging Algoritm eficient, bună aproximare a LRU

Working Set Costisitor de implementat în unele situaţii

WSClock Eficienţă bună

Fig. 6.6. Performanţa algoritmilor FIFO, Clock, LRU şi Optimal/Belady (raportată la numărul de

excepţii page fault apărute la 1000 de referiri), în funcţie de numărul de cadre de pagină apelate.

21

Segmentarea

Segmentarea = procedura de a furniza mai multe spaţii de adrese independente, de lungimi diferite

şi variabile (mai mari decât dimensiunea paginilor), accesibile programatorului, care se referă la:

un singur program – tabele de adrese LDT (Local Descriptor Table),

mai multe programe – tabele de adrese GDT (Global Descriptor Table),

şi care furnizează în memoria segmentată o adresă cu două componente (spaţiu bidimensional):

un număr de segment / base (segmentul conţine, de obicei, elemente de acelaşi tip),

o adresă în cadrul segmentului / limit.

Într-un spaţiu de adrese unidimensional, tabelele cu dimensiuni crescătoare se pot suprapune

22

Segmentarea oferă spatii independente de dezvoltare pentru tabele, stive, arbori, surse text etc.

Fig. 6.7. Nivelurile de protecţie / privilege ale segmentelor.

23

Memoria virtuală la Intel Core i7

Fig. 6.8. Registrul selector la Core i7 (index = nr. de intrări într-unul din tabelele LDT/GDT).

Fig. 6.9. Descriptorul de segment la Intel Core i7.

24

Fig. 6.10. Conversia perechii (selector, deplasament) în adresă liniară.

Gestionarea memoriei virtuale:

paginare pură

segmentare pură

segmentare paginată

25

Maparea adresei liniare în adresă fizică, folosind directorul de pagini şi tabelul de pagini

26

Fig. 6.12. Exemplu de paginare segmentată, cu avantajul eliminării fragmentării externe prin paginare.

27

Implementarea segmentării

Fig. 6.13

28

Algoritmi de înlocuire a segmentelor:

first fit - parcurge circular lista de găuri şi alege prima gaură suficient de mare;

next fit – parcurge lista de găuri începând de la ultima potrivire;

best fit – parcurge întreaga listă şi alege cea mai mică gaură în care va încăpea segmentul dorit;

worst fit – alege cea mai mare gaură în care va încăpea segmentul;

random – alege aleator o gaură suficient de mare.

Compactarea = comasarea tuturor găurilor într-una singură (defragmentarea externă la HDD)

Memoria virtuală în sisteme de operare Unix

Spaţiul de adresă la un proces Unix singular, fiecare proces având trei segmente: cod, date şi stivă

29

Memoria virtuală la Motorola

Fig. 6.19. Structura adresei liniare la Motorola 68×××: paginare pură, separarea pe 3 niveluri de tabele.

30

Memoria virtuală la CPU ARM OMAP4430

Tabelul de translaţie al adreselor şi structura blocului TLB la CPU ARM OMAP4430

TLB = Transl. Lookaside Buff. (mapează rapid nr. de pagini virtuale în nr. de cadre de pagină fizică)

TTBR = Translation Table Base Register (pentru adresa de bază a primului nivel de tabele)

ASID = Address Space IDentifier (compară simultan nr. cadrului de pagină cu toate intrările TLB)

31

Maparea adresei virtuale în adresă fizică la CPU ARM OMAP4430 (32 biţi adresă fizică/virtuală)

Tabelul 6.2

Comparaţie între paginare şi segmentare

Considerente Paginare Segmentare

Programatorul ştie de existenţa sa? nu da

Câte spaţii liniare de adresă există? 1 mai multe

Spaţiul de adrese virtuale poate depăşi

dimensiunea memoriei fizic instalate? da da

Tabelele de dimensiune variabilă

pot fi gestionate uşor? nu da

De ce a fost inventată tehnica? pentru simularea

memoriilor mari

pentru a furniza mai

multe spaţii de adrese