6. NIVELUL SISTEMULUI DE OPERARE

Acest nivel are un caracter hibrid, cea mai mare parte a instruc?iunilor caredefinesc limbajul fiind de tip ma?in?. Exist???i instruc?iuni specifice, care necesit?interpretare pentru a fi trecute pe nivelul 2. Nivelul sistemului de exploatare are sarcini particulare n ceea ce prive?tegestionarea memoriei (lucrul cu memoria virtual? prin conceptele de paginare ?isegmentare) ?i organizarea execu?iei n paralel a mai multor programe. Att nivelulmicroprogramat ct ?i nivelul sistemului de operare (exploatare) sunt necesarepentru interpretarea nivelurilor inferioare. Acestea sunt scrise de speciali?ti ?i suntorientate c?tre numeric. ncepnd cu nivelul imediat superior (limbajul deasamblare) apare orientarea c?tre simboluri, cuvinte, toate acestea avnd o anumit?sintax?.

6.1. Conceptul de paginare

Paginarea este procedeul de realizare n memorie a unor blocuri fixenumite pagini, care pot fi utilizate n mecanismul interschimb?rii proceselor(transferul blocurilor ntre memoria intern???i cea extern?). Tehnica pagin?rii estelarg folosit?? ?i poate fi independent? de gestionarea memoriei. Exist? procesoarecare creeaz? pagini n memoria fizic?, sau, ca n cazul familiei Intel, n memoriavirtual?. Ideea este de a face distinc?ia ntre capacitatea de adresare fizic? asistemului care define?te un spa?iu de memorie (denumit memorie virtual?) ?icapacitatea de memorie instalat? n sistem (denumit? memorie fizic? sau real?).

Exemplu. Fie un sistem cu 16 linii (64 KB) ?i o memorie instalat? de 4linii (fig. 6.1). n prezent, denumirea de memorie virtual? se folose?te cu dou? accep?iuni:

a) spa?iu virtual care poate fi accesat (ini?ial);b) zon? de memorie plasat? nu n memoria principal?, ci pe un dispozitiv de

memorare secundar sau extern, cel mai adesea pe hard disk. O singur? pagin? de 4 KB se poate afla la un moment dat n memoriaprincipal? (MP) sau fizic?. Dac? programul con?ine mai multe pagini, restulpaginilor se afl? undeva n memoria secundar? (pe floppy disk sau pe hard disk).

245

Cnd programul trebuie s? execute o instruc?iune din pagina urm?toare,sistemul de gestiune al memoriei virtuale (care face parte din sistemul de operare)execut? urm?toarele opera?ii:

1. salveaz? con?inutul memoriei periferice n memoria secundar?;2. localizeaz? pagina respectiv? n memoria secundar?;3. ncarc? aceast? pagin? n MP;4. asociaz? adreselor absolute adresa de memorie fizic? de la 0 la 4095;5. continu? execu?ia programului.

Fig. 6.1. Exemplu de paginare.

Observa?ie. Spre deosebire de procesul de segmentare, paginarea este transparent?programatorului, fiind realizat? de sistemul de operare.

Memorie fizic???i memorie virtual? (fig. 6.2). Accep?iunile termenului de memorie fizic? sunt urm?toarele:

1. linii fizice de adresare pe care le are procesorul n afar?;2. spa?iu de memorie fizic? instalat? (existent?) n sistemul de calcul.Accep?iunile termenului de memorie virtual? sunt urm?toarele:1. prima defini?ie de la memoria fizic?;2. spa?iu de memorie pe care l creeaz? sistemul de operare ?i care con?ine

un model al memoriei ?i al adreselor de memorie pe care le are programulla dispozi?ie (poate fi mai mare dect 1);

3. suportul fizic, de obicei hard disk-ul, pe care sistemul de operare salveaz?zone din memoria total? disponibil? programului pentru a asigura spa?iilibere n zona de memorie fizic?, destinate zonelor de cod sau de date cucare programul lucreaz? la momentul respectiv.

0

4096

8192

12287

65536

0

15

spa?iul virtual o pagin? de 4 KB

0

4095

spa?iul fizic

246

Tabelul 6.1Compara?ie ntre capacit??ile de adresare a memoriei fizice ?i a memoriei virtuale

Procesor Memoria maxim? fizic adresabil? 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

Fig. 6.2. Leg?tura ntre memoria fizic???i memoria virtual?.

6.1.1 Realizarea unei pagin?ri simple

n mod normal, n memoria fizic? instalat? se pot afla mai multe paginiactive (fig. 6.3.) Dimensiunea paginii cu care opereaz? procesorul Intel, echivalent?de fapt cu dimensiunea blocurilor de memorie cu care se lucreaz?, este de obicei de4 KB. Se presupune c? exist? o capacitate de adresare fizic? de 64 KB (adic? 16linii de adres?). Se mparte acest spa?iu n pagini de cte 4 KB (blocuri), rezultndastfel 16 pagini. Se mai presupune c? memoria fizic? instalat? este de 32 KB.

Program careutilizeaz?memoriavirtual?

Disc carestocheaz?

????i din memoriavirtual?

Memoriavirtual?

Memoria real? care p?streaz? p???i din memoria virtual?

247

Fig. 6.3. Exemplu de paginare simpl?.

Adresa fizic? este pe 16 bi?i ?i dac? se urm?re?te folosirea memoriei paginatese poate considera c? cei mai semnificativi 4 bi?i reprezint? num?rul paginii, iar ceimai pu?in semnificativi 12 bi?i reprezint? deplasamentul n cadrul paginii. Pentru a realiza gestiunea memoriei fizice instalate se va folosi un tabel depagini cu 16 intr?ri a cte 4 bi?i fiecare (fig. 6.4.). Din cei 4 bi?i, un bit va indicadac? pagina fizic? adresabil? se afl? sau nu n memoria principal?, restul de 3 bi?i(acest num?r este dat de fapt de num?rul de bi?i cu care poate fi codificat num?rulde pagini aflate n memoria instalat?) indic? pagina din memoria instalat? n care seafl? pagina din memoria fizic? adresabil? la care se face referire.

1 1 1 0

Fig. 6.4. Gestiunea memoriei fizice folosind tabelul de pagini.

0

4096

8192

61440

65536

pagina 0 pagina 1

pagina 15

pagina 0 pagina 1

pagina 5 pagina 7

0

4096

8192

28672

32678

64 KB (16 linii)

memoria fizicadresabil?

32 KB

memoria fizicinstalat?

4 KB4 KB

0123

15

memorie fizic adresabil? deplasament

124

0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0

1 1 0 0 0 0 0 0 0 0 1 0 1 1 0

248

Avantajele pagin?rii pot fi rezumate astfel: ??rimea fix? a paginilor intr? corect ntr-un sector al unui disc; un obiect n memorie nu trebuie s? fie continuu: pagina poate constitui o

nou? cuant? de informa?ie; mecanismul pagin?rii ?i, implicit, ntreaga tehnic? de a schimba continuu

blocuri fixe de informa?ii ntre memoria intern?? ?i cea extern? nu suntvizibile utilizatorului.

n concluzie, mecanismul pagin?rii are urm?toarele elemente esen?iale: se realizeaz? dou? niveluri de adresare indirect? a memoriei, astfel nct

pn? s? se ajung? la pagina propriu-zis? se face o referin?? ntr-undirector din care se selecteaz? o tabel? a paginilor;

toate obiectele din memorie implicate (directorul ?i tabelele) sunt tratatela rndul lor ca ni?te pagini speciale; deci toate au m?rimea fix? de 4 KB.Se p?streaz? astfel principiul coeren?ei informa?iei n memorie (ca ?i ncazul segmentelor);

att directorul ct ?i tabelele de pagini au structura uniform?, fiindformate din 1 K elemente a cte 4 octe?i. Aici se g?se?te adresa bazeitabelei ?i respectiv a paginii selectate;

orice adres? a bazei unei tabele sau a unei pagini este dat? pe un num?r de20 bi?i, ace?tia constituind partea mai semnificativ? a adresei fizicevizate. Blocurile n memorie sunt aliniate din 4 KB n 4 KB, deci automatcei mai pu?in semnificativi 12 bi?i ai adreselor fizice ale bazelor sunt 0;

adresa fizic? a bazei directorului se afl? n unul din cele patru registre decontrol al microprocesoarelor.

6.1.2. Politica de nlocuire a paginilor

ntr-un sistem care folose?te memoria virtual?, sistemul de operare trebuie s?stabileasc? urm?toarele politici de gestionare:

politica fetch: stabile?te cnd o pagin? trebuie adus? n memorie; paginarea la cerere: aduce o pagin? n memorie doar ca rezultat al

excep?iei page fault; pre-paginarea: ncearc? s? anticipeze ?abloane de utilizare a memoriei n

viitor ?i s? aduc? paginile n memorie nainte ca cererile de accesare s?fie emise. Scopul pre-pagin?rii este de a reduce consecin?ele opera?iilorde citire/scriere, programnd ca acestea s? se desf??oare n paralel cuprocesarea desf??urat? de unitatea central?.

politica de plasament: unde s? fie puse paginile sau segmentele aduse nmemorie. Aceast? politic? este folosit? n cazul segmentelor f???paginare. n caz contrar, o pagin? nu conteaz? unde este plasat?(excep?ia este reprezentat? de arhitecturile NUMA, unde este avantajosca o pagin? s? fie stocat? ct mai aproape de procesorul care o va folosi).

249

politica de nlocuire: dac? memoria este complet ocupat?, cnd intervineo excep?ie page fault, o pagin? sau un segment de memorie trebuie s? fieevacuate. Politicile de nlocuire stabilesc care pagini sau segmente s? fienlocuite.

Algoritmii de nlocuire intr? n ac?iune atunci cnd sistemul de operareprime?te semnalul de page fault, prin care se n?elege c? pagina solicitat? nu se afl?n memoria fizic?, ci pe disc. La primirea acestui semnal, algoritmul de nlocuire apaginii are sarcina de a muta o pagin? existent? n memoria fizic? pentru a face locpaginii care va fi copiat? de pe disc.

Decizia corect? asupra paginii care va fi mutat? este crucial? pentru viteza cucare va rula aplica?ia. Deoarece lucrul cu discul este lent, este de preferat s? serealizeze ct mai pu?ine opera?ii cu acesta. Cu ct un algoritm p?streaz? paginile decare va fi nevoie n memorie mai mult timp, cu att acesta este mai eficient.

Obiectivul unei politici de nlocuire este de a determina o rat? de apari?ie aexcep?iei page fault ct mai mic?. Situa?ia ideal? ar fi ca o pagin? care esteeliminat? s? fie o pagin? care nu va mai fi folosit? niciodat?. Dac? acest lucru nueste posibil, urm?toarea op?iune este ca pagina nlocuit? s? fie una care nu va mai fifolosit? pentru o lung? perioad? de timp. ntrebarea care se pune este: ce factori potfi folosi?i pentru a stabili ce pagin? trebuie nlocuit?? C?iva dintre ace?ti factorisunt urm?torii:

durata perioadei n care o pagin? a fost situat? n memorie: principiullocalit??ii temporale enun?? faptul c? o pagin? aflat? de mult timp nmemorie poate s? nu mai fie necesar?;

ct de recent a fost apelat? o pagin?: acela?i principiu al localit??iitemporale enun?? faptul c? probabilitatea ca o pagin? care a fostapelat? de curnd s? fie apelat? din nou n viitorul apropiat este mare;

frecven?a cu care a fost apelat? o pagin?: acest factor nu este la fel deimportant ca cei doi descri?i mai sus, dar exist? totu?i o probabilitaterelativ ridicat? ca o pagin? care a fost des apelat? s? fie apelat? din noudestul de curnd;

proprietatea unei pagini de a fi fost modificat? sau nu: dac? to?i factoriisunt egali, se alege a fi nlocuit? o pagin? care nu a fost modificat?.Acest fapt nu va cauza o opera?ie de citire/scriere;

eventualitatea ca un cadru s? fie blocat: unele cadre sunt blocate aceasta nseamn? c? paginile din interiorul lor nu pot fi nlocuite,aceast? proprietate prevenind situa?ia ca pagini din kernel sau dinbuffer-ele I/O sa fie evacuate.

Pa?ii care sunt parcur?i pentru tratarea excep?iei page fault sunt:1. aplica?ia acceseaz? o pagin? care nu este prezent? n memoria virtual?;2. apare excep?ia page fault;3. este aleas? o pagin? goal?;4. dac? nu este g?sita nicio pagin? goal?, este aleas? una care urmeaz? a

fi evacuat? din memoria virtual?, aceast? alegere fiind f?cut? n bazaunor politici de nlocuire;

250

5. dac? pagina a fost modificat?, aceast? pagin? este nti scris? pe disc;6. pagina necesar? este citit? de pe disc;7. pagina este mapat? spa?iului de adrese al aplica?iei;8. este reluat? execu?ia aplica?iei.

Algoritmii de nlocuire pot fi locali sau globali. Cnd apare semnalul depage fault, algoritmii de nlocuire locali selecteaz? pagini care apar?in aceluia?iproces, n timp ce algoritmii globali pot selecta orice pagin? din memorie.

Algoritmul optim de nlocuire (Belady)

Algoritmul optim de nlocuire, cunoscut ?i sub numele de algoritmul luiBelady, este un algoritm de nlocuire ce func?ioneaz? dup? urm?torul principiul:cnd o pagin? trebuie copiat? de pe disc n memorie, sistemul de operare mut?con?inutul paginii care va fi folosit? n proces cel mai trziu, din memorie pe disc,??cndu-i loc noii pagini. De exemplu, o pagin? care nu va fi folosit? nurm?toarele 10 secunde va fi mutat? din memorie pe disc naintea unei pagini careva fi folosit? n urm?toarele 2 secunde. Acest algoritm este unul teoretic, el neputnd fi implementat pe sistemelede operare deoarece nu se poate ?ti exact ct va dur? pn? cnd o pagin? dinmemorie va fi folosit?.

Not Recently Used (NRU)

Algoritmul NRU (nefolosit recent) este un procedeu de nlocuire apaginilor care au fost folosite recent. Acest algoritm func?ioneaz? pe urm?torulprincipiu: cnd o pagin? este referit?, un bit de referin?? este setat la valoarea 1pentru acea pagin?, aceasta este acum marcat? ca fiind referit?. Cnd o pagin? estescris?, un alt bit, de scriere a paginii, este setat la valoarea 1. La un anumit intervalde timp se reseteaz? bi?ii de referin?? a paginilor folosite recent. Sistemul de operare distinge 4 clase de pagini:

clasa 0: nereferite, nemodificate; clasa 1: nereferite, modificate; clasa 2: referite, nemodificate; clasa 3: referite, modificate.

First-In First-Out (FIFO)

Algoritmul de nlocuire FIFO (primul intrat, primul ie?it) elimin? paginacare a fost nc?rcat? prima, indiferent de momentul n care aceast? pagin? a fostreferit? ultima dat?. Fiecare pagin? are un contor care este ini?ial egal cu 0 pentrufiecare cadru de pagin?. Pagina care tocmai a fost adus? n memorie va aveavaloarea contorului egal? mereu cu 0, urm?toarea va avea valoarea 1 (nainte capagina cu indexul 0 s? fie adus? n memorie pagina aceasta avea contorul egal cuzero, dar a fost incrementat cu 1) ?.a.m.d. Practic, se creeaz? un fenomen demb?trnire a paginilor, cea mai tn??? pagin? avnd contorul cu valoarea 0.Cnd o pagin? trebuie eliminat?, se va alege mereu cea cu contorul cel mai mare.

251

Algoritmul FIFO este foarte ieftin, ns? are performan?e slabe comparativcu al?i algoritmi. Din aceast? cauz? este rar folosit. Un exemplu de sistem deoperare care folose?te algoritmul FIFO este VAX/VMS.

Second Chance (SC)

Second Chance (a doua ?ans?) este un algoritm de nlocuire a paginilorinspirat din FIFO, dar care are performan?e mult mai bune dect acesta din urm?,diferen?a de pre? fiind una foarte mic?. Func?ioneaz? verificnd pagina cu contorulavnd cea mai mare valoare (cea mai b?trn? pagin?), dar n loc de a o extrage can algoritmul FIFO, Second Chance i acord? o a doua ?ans? paginii verificnd dac?are sau nu fixat bitul de referin??. Dac? acesta nu este setat, algoritmul func?ioneaz?ca ?i FIFO n continuare, mutnd pagina din memorie. Dac? bitul de referin?? estesetat, atunci contorul paginii este resetat la valoarea 0, pagina fiind practic inserat?din nou n coad? ca ?i cum ar fi o pagin? nou?.

Clock (C)

Clock este un algoritm cu performan?e mai bune dect Second Change,care merge tot pe principiul FIFO. La fel ca ?i Second Change, Clock folose?te bi?ide referin?? pentru a da o a doua ?ans? paginii. mbun????irea adus? de Clockconst? n faptul c? nu mai este nevoit s? mping? paginile n coad?, algoritmulfolosind un pointer (indicator) ?i un sistem circulat al paginilor n loc de o coad?.Pointer-ul arat? care pagin? este cea mai veche ?i poate fi nlocuit?

Least Recently Used (LRU)

Algoritmul Least Recently Used (LRU) cel mai pu?in frecvent utilizat?pagin?, de?i similar n terminologie cu NRU, difer? prin faptul c? LRU urm?re?tepaginile ntr-o perioad? scurt? de timp, n timp ce NRU urm?re?te paginile ntr-uninterval de ceas. LRU func?ioneaz? pe ideea c? paginile folosite cel mai mult ntrecutul apropiat vor fi cel mai probabil folosite ?i n viitorul apropiat, n cadrulurm?toarelor ctorva instruc?iuni. De?i n teorie LRU se descurc? foarte bine,acesta este foarte scump de implementat. Exist? cteva implement?ri ale LRU carencearc? s? reduc? costul acestuia dar s? men?in? n acela?i timp performan?eleridicate. Cea mai costisitoare variant? a LRU este cea de tip coad?. Aceasta implic?realizarea unei liste cu toate paginile din memorie. La sfr?itul listei se afl? cea maipu?in utilizat? recent pagin? iar n vrful listei se afl? cea mai des recent utilizat?pagin?. Intr?rile din list? trebuie rearanjate la fiecare accesare a listei, ceea ce faceaceast? metod? foarte lent?. O alt? metod? are nevoie de suport hardware ?i func?ioneaz? pe baza unuicounter (num???tor). De fiecare dat? cnd o pagin? este accesat? prime?te ovaloarea egal? cu a counter-ului la momentul acces?rii. Cnd o pagin? trebuiemutat? sistemul de operare selecteaz? pagina cu counter-ul cel mai mic ?i o mut?.Costul implement?rii acestei metode este unul foarte ridicat datorit? tehnologieinecesare realiz?rii counter-ului.

252

Din cauza costurilor mari se folosesc de obicei algoritmii similari cu LRU,care ofer? o implementare mai ieftin?. n unele situa?ii, LRU e?ueaz? lamentabil. De exemplu, n cazul folosiriiciclurilor care se ntind pe mai multe pagini. n aceste cazuri, algoritmul MRU(Most Recently Used) este mult mai eficient. Majoritatea implement?rilor LRUncearc? s? detecteze aceste cicluri ?i s? le trateze corespunz?tor cu algoritmulMRU. Variante ale LRU sunt:

LRU-K, cunoscut ?i sub numele de LRU-2, LRU-1 fiind identic cu LRU; ARC.

Random (R)

Algoritmul de tip Random nlocuie?te aleator o pagin? din memorie cu unade pe disc. Acest procedeu elimin? costurile suplimentare legate de realizarea unuisistem de monitorizare a referin?elor c?tre o pagin?. De obicei, are rezultate maibune dect FIFO ?i n cazul ciclurilor chiar rezultate mai bune dect LRU, de?i ngeneral n practic? LRU se descurc? mai bine. Sistemul de operare OS/390construit pentru mainframe-urile de la IBM folose?te, de exemplu, algoritmul LRU,iar cnd performan?ele acestuia scad trece la algoritmul Random.

Not Frequently Used (NFU) Algoritmul NFU (pagini nefolosite frecvent) genereaz? mai pu?ine semnalede tip eroare de pagin? (page fault) dect algoritmul LRU cnd tabelul de paginicon?ine mul?i pointer-i cu valori nule. Acest algoritm folose?te un counter(num???tor), fiecare pagin? avnd un astfel de counter de sine st???tor. La fiecareinterval de ceas toate paginile referite n acel interval vor avea counter-ulincrementat cu 1. Astfel, cu ajutorul counter-ului se poate determina ct de frecventa fost folosit? o anumit? pagin?. Pagina cu valoarea cea mai mic? a counter-ului vafi selectat? pentru a fi mutat? pe disc. Viteza acestui algoritm este mic? datorit?num???torului.

Aging (A) Algoritmul Aging (mb?trnire) este o versiune mbun????it? a NFU, avnd

o vitez? de lucru mult mai mare. Modific?rile care l fac s???in? cont ?i de factorulinterval de timp. n loc ca doar s? incrementeze contoarele paginilor apelate,nef?cnd nici o discriminare din punct de vedere al intervalului de timp n carenum?rul de apeluri a contribuit la contorul de frecven??, contorul de apel al uneipagini este nti deplasat c?tre dreapta (mp???it la 2), nainte ca bitul de referin?? s?fie ad?ugat n partea stng? a num?rului binar. De exemplu, dac? o pagin? are bi?iide referin??: 1, 0, 0, 1, 1, 0 cu 6 perioade de ceas nainte, contorul de referin?? vaar?ta n modul urm?tor: 10000000, 01000000, 00100000, 10010000, 11001000,01100100. Dup? cum se poate observa, apelurile mai apropiate de momentulprezent au un impact mai mare dect apelurile care au avut loc mai demult. Aceastaasigur? faptul c? paginile care au fost apelate mai pu?in, dar mai recent, s? aib? o

253

prioritate mai mare dect paginile care au fost apelate mai mult, dar n trecut. nacest fel, cnd o pagin? trebuie s? fie nlocuit?, vor fi alese paginile cu contorul celmai sc?zut.

Observa?ie. Algoritmul Aging difer? de algoritmul LRU, n sensul n carepoate ?ine eviden?a apelurilor n ultimele 16/32/64 intervale de timp (depinznd denum?rul de bi?i pe care poate lucra procesorul). n consecin??, se poate spune c?modul n care au decurs apelurile n memorie n ultimele 16 intervale de ceas estesuficient pentru a lua o decizie corect? asupra c?rei pagini trebuie nlocuite.??adar, algoritmul Aging poate oferi performan?e foarte apropiate de cele alealgoritmului optim (Belady), la un pre? moderat.

Algoritmul Working Set

Fig. 6.5. Dimensiunea setului de pagini utilizate de ultimele k apeluri de memorie n func?iede timp (t).

Este un algoritm cu grad mare de generalitate. Working Set reprezint? setulde pagini utilizate de ultimele k apeluri de memorie, iar func?ia w(k,t) estedimensiunea acestui set la momentul de timp t.

Compara?ie ntre algoritmin figura 6.6 este reprezentat un grafic care red? comparativ performan?a

(raportat? la num?rul de excep?ii page fault ap?rute la 1000 de referin?e) n func?iede num?rul de cadre apelate, pentru 4 dintre algoritmi: FIFO, Clock, optim ?i LRU.

Fig. 6.6. Compara?ie ntre algoritmi.

254

6.2 Conceptul de segmentare

Fie, de exemplu, un compilator care poate avea mai multe tabele,construite pe m?sur? ce decurge compilarea, incluznd:

tabela de simboluri, con?innd numele ?i atributele variabilelor; textul surs?, memorat pentru tip?rirea unui listing; o tabel? cu toate constantele ntregi ?i n virgul? mobil? folosite; arborele de analiz? sintactic? a programului; stiva folosit? pentru apelurile de func?ii ale compilatorului.

Se analizeaz? ce se ntmpl? dac? un program are un num?r deosebit demare de variabile. Por?iunea din spa?iul de adrese alocat? pentru tabela desimboluri se va umple, chiar dac? mai este suficient spa?iu n celelalte tabele.Compilatorul ar putea, fire?te, s? afi?eze un mesaj prin care s? anun?eimposibilitatea continu?rii compil?rii din cauza num?rului mare de variabile, lucrucare nu este corect atunci cnd mai exist? spa?iu nefolosit n celelalte tabele. O solu?ie imediat? este de a furniza mai multe spa?ii de adreseindependente, numite segmente. Fiecare segment const? dintr-o secven?? liniar? deadrese, de la valoarea 0 la valoarea maxim?. Lungimea fiec?rui segment poate fiorict de mare ntre 0 ?i valoarea maxim?. Segmente diferite pot s? aib?, ?i, deregul?, au lungimi diferite. Mai mult chiar, lungimea unui segment se poatemodifica n timpul execu?iei. Lungimea unui segment de stiv? poate cre?te ori decte ori se pune ceva n stiv???i poate sc?dea ori de cte ori se ia ceva din stiv?. Deoarece fiecare segment reprezint? un spa?iu de adrese separat, segmentediferite vor cre?te ?i vor sc?dea independent, f??? s? se influen?eze reciproc. Dac? ostiv? dintr-un anumit segment are nevoie de un spa?iu suplimentar pentru a cre?te,l poate avea, neexistnd nimic peste care s? se suprapun?. Evident, un segment sepoate umple, dar deoarece segmentele sunt de obicei mari, aceast? situa?ie estedeosebit de rar?. Pentru a preciza o adres? n aceast? memorie segmentat? saubidimensional?, programul trebuie s? furnizeze o adres? cu dou? componente: unnum?r de segment??i o adres? n cadrul segmentului. Un segment este, deci, o entitate logic? unic? de care programatorul estecon?tient ?i pe care o folose?te ca atare. Un segment poate con?ine:

procedur?, un vector, o stiv?, o colec?ie de variabile scalare.

Observa?ie. n general, un segment nu con?ine elemente de tip diferit. Segmentarea permite ?i partajarea de date sau cod ntre diferite programe.Dac? un calculator are mai multe programe care ruleaz? n paralel ?i care folosescanumite proceduri de bibliotec?, ar fi o risip? de memorie dac? fiecare program aravea copia sa proprie. Segmentele pot avea diferite niveluri de protec?ie:

255

un segment procedur? poate fi marcat ca accesibil doar pentru execu?ie,interzicnd accesul pentru citirea din sau scrierea n el;

un segment care con?ine un vector de numere n virgul? mobil? poate fimarcat ca accesibil pentru citire/scriere, dar nu pentru execu?ie, oricencercare de a fi executat fiind interceptat? (o astfel de protec?ie ajut? deobicei la depistarea erorilor de programare).

Exemplu. Procesorul 80286 utilizeaz? 16 linii de adresare, putnd s?lucreze fie n modul real, ceea ce nseamn? c? func?ioneaz? cu un spa?iu deadresare liniar de 1 MB, fie n modul protejat. Pentru procesorul 80386, n modulde lucru protejat pot fi adresate 16 K segmente, fie de 64 KB (286), fie de 4 GB(386) fiecare. Spre deosebire de cazul lui 80286, registrele segment pentru 80386 nu maispecific? adresa unui segment, ci indic? o intrare ntr-unul din cele dou? tabele deadrese n care se afl? zone ce con?in descriptorii segmentului. Memoria virtual? este gestionat? cu ajutorul a dou? tabele:

1. LDT (Local Descriptor Table) de 8 K intr?ri fiecare;2. GDT (Global Descriptor Table).

Fiecare program are propriul s?u tabel LDT, n timp ce tabelul GDT esteutilizat n comun de toate programele prin intermediul sistemului de operare. LDT descrie segmentele locale ale fiec?rui program, cum ar fi cele de cod,date, stiv? etc., n timp ce GDT descrie segmentele utilizate de sistemul de operare. Registrul segment obi?nuit este nlocuit n acest caz de un registru selectorpe 16 bi?i, care con?ine urm?toarele informa?ii (fig. 6.7).

Fig. 6.7. Informa?iile con?inute n registrul selector.

Descriptorul este format din 4 octe?i (fig. 6.8).

Fig. 6.8. Structura descriptorului.

index 0/1

13 1 2

num?rul de intr?ri ntr-unul dintablourile GDT ?i LDT

GDTsau

LDT

0 3 nivelul deprotec?ie alsegmentului

respectiv

32 bi?i

adresa de baz? m?rime adresa de segment 24 31 G D 0 X segment 16 19 P Pr Tip baz? 16 23

adresa de baz? segment 0 15 m?rimea segmentului 0 15

256

Semnifica?iile nota?iilor folosite sunt: G = bit care indic? dac? m?rimea segmentului este dat? n octe?i sau n pagini:

G = 0 f??? paginare, m?rimea este dat? n octe?i ?i rezult?dimensiunea maxim? de 8 MB;

G = 1 m?rimea este dat? n pagini de cte 4 octe?i ?i rezult?dimensiunea maxim? de 4 MB;

D = indicator al tipului de cuvinte cu care se lucreaz? n interiorul segmentului:D = 0 cuvinte de 16 bi?i; D = 1 cuvinte de 32 bi?i;

P = bit care indic? prezen?a n memoria principal? (MP): P = 0 segmentul nu se g?se?te n MP; P = 1 segmentul se g?se?te n MP;

Pr = 2 bi?i care indic? nivelul de prioritate n execu?ie al programului dincare face parte segmentul (ntre 0 ?i 3);

Tip = 5 bi?i care indic? tipul segmentului (cod, date, stiv?, extra segmentetc.) ?i nivelul s?u de protec?ie n modul protejat.

Acest tabel de descriptori folose?te la ob?inerea adresei fizice (fig. 6.9),respectnd urm?torul algoritm:

1. se pleac? de la registrul selector ?i se ajunge ntr-unul din tabelele unde??sesc descriptorii de segment (care joac? rolul tabelei de paginare):adres?, m?rime ?i alte cmpuri;

2. folosind aceast? informa?ie, sistemul de operare utilizeaz? o zon? MSBpentru adres? la care adaug? deplasamentul din program;

3. rezult? 32 de bi?i (o adres? liniar? folosit? ca adres? fizic?).

Fig. 6.9. Utilizarea tabelului de descriptori n ob?inerea adresei fizice.

Adresa liniar? poate fi interpretat? n dou? feluri:a) dac? nu exist? paginare, adresa liniar? este interpretat? ca adres? fizic?,

spunndu-se n acest caz c? se folose?te o schem? de memorie cu segmentare pur?; Observa?ie. Segmentele se pot suprapune spa?iul de adresare liniar dac?programatorul nu ?ine o eviden?? clar? a lor la scrierea programului. Ar fi fost preacomplicat pentru sistemul de operare s? verifice dac? aceste segmente sunt disjuncte.

adresa liniar? 32 bi?i

Selector

Adresa de baz?

??rimea

Altecmpuri

MSB LSB

Deplasament

LDT(GDT)

257

Fig. 6.10. Separarea nivelurilor de tabele.

b) dac? exist? paginare, adresa liniar? este folosit? pentru tabelele depaginare (nc? o treapt?) ?i de abia apoi ajung la adresa fizic?. A?adar, dac? exist?paginare adresa liniar? este interpretat? ca adres? virtual? (adres? din spa?iul fizicadresabil) ?i transformat? n adres? fizic? (real?) prin intermediul tabelei de pagini(vezi figura 6.10). Deoarece un segment poate avea 1 M de pagini de 4 K, metodade paginare la microprocesorul 80386 ?i urm?toarele cuprinde dou? niveluri detabele pentru a reduce din aceste tabele. Observa?ie. Pot exista 1024 de tabele de tip Page. Nivelurile de protec?ie (03) sunt reprezentate n figura 6.11.

Fig. 6.11. Nivelurile de protec?ie.

1024linii

1024linii

0/1 0/1

121010

Dir Page Deplasament

MSB Deplasament

Adresa deintrare ntabelulPage

258

Dac? toate registrele selector trimit c?tre un acela?i descriptor (aflat nLDT sau n GDT) cu adresa de baz? 0 ?i m?rimea maxim? (1 M sau 4 G), se vaob?ine un sistem numit cu paginare pur?, care face adresare liniar? pe 32 de bi?i. n concluzie, procesoarele Intel ncepnd cu 80386 asigur? trei scheme defolosire a memoriei:

1. cu segmentare pur?;2. cu paginare pur?;3. superpozi?ie ntre segmentare ?i paginare (paginare segmentat?).

Exemplu. Paginarea segmentelor folose?te avantajul elimin?rii fragment?riiexterne creat de c?tre paginare (pentru alocare poate fi folosit oricare dintre cadreledisponibile). Deosebirea dintre aceast? metod???i segmentare este aceea c? intrareatabelei de segment nu con?ine adresa de baz? a segmentului ci adresa de baz? a uneitabele de pagin? asociat? acestui segment.

Segmentul este format dintr-un num?r de pagini de aceea?i dimensiune.Deplasarea n cadrul segmentului se exprim? prin num?r de pagin???i deplasare npagin?. Cu num?rul de pagin? folosit ca index n tabela de pagin? a segmentului, seob?ine num?rul cadrului care, n final, se combin? cu deplasarea n pagin?? ?iformeaz? adresa fizic? (vezi figura 6.12). Deoarece ultima pagin? a fiec?ruisegment nu este ntotdeauna complet ocupat?, metoda introduce totu?i o cantitateredus? de fragmentare extern? (n realitate, atunci cnd se lucreaz? cu tabele desegment de dimensiuni mari, mecanismul este ceva mai complicat).

Fig. 6.12. Exemplu de paginare segmentat?.

259

6.2.1 Implementarea segment?rii

Implementarea segment?rii difer? ntr-un mod esen?ial de paginare:paginile au dimensiuni fixe, pe cnd segmentele nu. Exemplu. Se consider? o memorie fizic? care con?ine ini?ial 5 segmente(fig. 6.12.a). Se analizeaz? ce se ntmpl? dac? segmentul 1 este eliminat ?i nlocuitcu segmentul 7, care este mai mic.

Se ob?ine configura?ia de memorie prezentat? n figura 6.12.b. ntresegmentul 7 ?i segmentul 2 exist? o zon? nefolosit?, adic? o gaur?. Apoi segmentul4 este nlocuit cu segmentul 5, ca n figura 6.12.c, iar segmentul 3 este nlocuit desegmentul 6, ca n figura 6.10.d. Dup? ce sistemul ruleaz? o vreme, memoria va fimp???it? ntr-un num?r de por?iuni, unele con?innd segmente, unele g?uri. Acestfenomen se nume?te fragmentare extern?. Se analizeaz? ce s-ar ntmpla dac? programul ar referi segmentul 3 dup?ce a ap?rut fragmentarea extern?, ca n figura 6.10., d. Spa?iul total disponibil n??uri este de 10 K, mai mult dect suficient pentru segmentul 3, dar deoarece??urile sunt distribuite n buc??ele mici, nefolositoare, segmentul 3 pur ?i simplu nupoate fi nc?rcat. Pentru a o face totu?i, trebuie mai nti eliminat din memorie unalt segment.

6.2.2 Algoritmi de nlocuire a segmentelor

I. O modalitate de a elimina fragmentarea extern? este compactarea: ori decte ori apare o gaur?, toate segmentele de dup? ea vor fi mutate ct mai aproape deloca?ia de memorie 0, eliminnd acea gaur?? ?i l?snd o singur? gaur?, mare, lasfr?itul memoriei. Alternativ, se poate a?tepta ca fragmentarea extern? s? devin?serioas? (adic? mai mult de un anume procent din memorie este pierdut n g?uri),nainte de a se face compactarea (eliminarea g?urilor).

Figura 6.10.e prezint? memoria din figura 6.10.d dup? compactare(defragmentare). Scopul compact?rii este colectarea tuturor g?urilor mici ?i inutilizabilentr-una singur?, mare, n care pot fi plasate unul sau mai multe segmente. Compactareaare dezavantajul evident al pierderii de timp cu realizarea ei. Compactarea dup? apari?iafiec?rei g?uri este de obicei mult prea cronofag?. Dac? timpul necesar compact?rii memoriei este inacceptabil de mare, estenevoie de un algoritm care s? stabileasc? ce gaur? se va folosi pentru un anumitsegment. Aceast? gestiune a g?urilor necesit? men?inerea unei liste cu adresele ?idimensiunile g?urilor. II. Un algoritm des ntlnit, numit best fit (cea mai bun? potrivire) alegecea mai mic? gaur? n care segmentul dorit va nc?pea. Ideea este de a g?si potrivirintre segmente ?i g?uri, evitndu-se astfel preluarea unei por?iuni dintr-o gaur?mare, care ar putea fi necesar? ulterior pentru un segment mare. III. Alt algoritm frecvent utilizat este first fit (prima potrivire), careparcurge circular lista de g?uri ?i alege prima gaur? suficient de mare pentru a??stra segmentul.

260

Segment 4(7k)

Segment 4(7k)

Gaur?(3 k)

Segment 3(8 k)

Segment 3(8 k)

Segment 5(4 k)

Segment 2(5 k)

Segm. 1 Segm. 7

Segment 2(5 k)

Segm. 4 Segm. 5

Segment 3(8 k)

Segment 1(8 k)

Gaur?(3 k)

Segment 2(5 k)

Segment 0(4 k)

Segment 7(5 k)

Gaur?(3 k)

Segment 0(4 k)

Segment 7(5 k)

(a) (b) (c) Segment 0(4 k)

Gaur?(3 k)

Gaur? unic?(10 k)

Segment 5(4 k)

Segment 5(4 k)

Segm. 3 Segm. 6

Gaur?(4 k)

Compactare

Segment 6(4 k)

Segment 6(4 k)

Segment 2(5 k)

Segment 2(5 k)

Segment 7(5 k)

Gaur?(4 k)

Segment 0(4 k)

Segment 7(5 k)

Segment 0(4 k)(d) (e)

Fig. 6.12. Exemplu de implementare a segment?rii.

Procednd astfel, este evident c? timpul de c?utare necesar este mai micdect n cazul c?ut?rii n ntreaga list? a celei mai bune potriviri, ceea ce reprezint?un avantaj al acestui algoritm. Ace?ti ultimi doi algoritmi au tendin?a de a reducedimensiunea medie a g?urilor. Ori de cte ori un segment este plasat ntr-o gaur? maimare dect dimensiunea sa, ceea ce se ntmpl? aproape ntotdeauna (potrivirile exactefiind rare), gaura este divizat? n dou? p???i. O parte este ocupat? de segment, cealalt?devine noua gaur?, care binen?eles este mai mic? dect gaura ini?ial?. Dac? nu exist? un proces de compensare care s? creeze g?uri mai mari prinunificarea celor mici, ace?ti ultimi doi algoritmi vor duce n cele din urm?, laumplerea memoriei cu g?uri mici, nefolositoare. n concluzie, ace?ti algoritmitrebuie utiliza?i n conjunc?ie cu compactarea, aplicat? rar.

261

6.3. Exemple de gestionare a memoriei

Se define?te gestionarea memoriei ca fiind translatarea adreselor virtuale(folosite de programator) n adrese fizice identificabile n structura fizic?, concret?,a calculatorului. Primul reprezentant al familiei Intel care folose?te acest mecanismeste 80286. De remarcat este faptul c? Intel 80286 ?i succesorii s?i au mecanismulde gestionare implementat pe cip. Gestionarea memoriei bazate pe principiile segment?rii ncurajeaz?multiprocesarea, protec?ia adreselor, protec?ia proceselor a c?ror izolare rezult? nmod natural din definirea segmentelor ?i atributelor, precum ?i interschimbarealocului proceselor ntre memoria intern???i cea extern?.

Tabelul 6.2Compara?ie ntre paginare ?i segmentare

Considera?ie Paginare Segmentare

Programatorul ?tie de existen?a sa? Nu DaCte spa?ii liniare de adres? exist?? 1 Mai multe

Spa?iul de adrese virtuale poate dep??idimensiunea memoriei?

Da Da

Tabelele de dimensiune variabil? potfi gestionate u?or?

Nu Da

De ce a fost inventat? tehnica? Pentru simulareamemoriilor mariPentru a furniza mai

multe spa?ii de adrese

Paginarea introduce ?i o nou? no?iune legat? de adrese: adresa liniar?.Acest tip de adres? rezult? n urma translat?rii adresei virtuale ?i urmeaz?, la rndulei, s? fie translatat? n adresa fizic?. n cazul familiei Intel, adresa liniar? coincidecu cea fizic? dac? G = 0 (vezi figura 6.8). Se impun cteva observa?ii preliminare:

pentru familia Intel, mecanismul pagin?rii se aplic? numai ncepnd de la80386 ?i apoi la descenden?ii familiei (80486, familia Pentium). PentruIntel 386/486 paginarea este op?ional?, n func?ie de bitul de granularitatedin descriptorii de segmente;

adresa virtual?, alc?tuit? din selector ?i adresa efectiv?, este translatat? nadresa liniar???i apoi n cea fizic?. La fel ca adresa fizic?, adresa liniar?(AL) este de 32 de bi?i;

Intel 386/486 adaug? modurilor de adresare cunoscute de la ascenden?iifamiliei un nou tip: adresarea la care, al?turi de baz?? ?i deplasament,exist? un index care poate fi nmul?it cu un factor de scal? 1, 2, 4 sau 8;

dimensiunea maxim? a unui segment n memoria virtual? se ob?ine numaipentru G = 1. n acest caz, un segment poate avea:

220 pagini 212 B/pagin? = 232 B = 4 GB.

262

6.3.1. Memoria virtual? la Multics

Sistemul de operare Multics rula pe ma?inile Honeywell 6000 ?i pe urma?iiacesteia si asigura fiec?rui program o memorie de pn? la 218 segmente, fiecaredintre ele putnd avea o lungime de pn? la 65.536 cuvinte (de 36 bi?i).

Pentru a combina avantajele pagin?rii (dimensiunea uniform? a paginii sineobligativatea ?inerii n memorie a unui segment ntreg dac? numai o parte dinacesta este folosit) cu avantajele segment?rii (u?urin?a n programare, modularitate,protec?ia si partajarea), sistemul de operare Multics trateaz? fiecare segment ca pe omemorie virtual???i astfel fiecare segment se pagineaz?.

Fiecare program Multics are un tabel de segmente, cu cte un descriptorpentru fiecare segment. Deoarece exist? mai bine de un sfert de milion de intr?ri ntabel, acesta este el nsu?i un segment ?i este paginat la rndul lui. Descriptorul desegment con?ine o indica?ie care atest?, sau nu, apartenen?a segmentului lamemoria principal?. Dac? vreo parte din segment se afl? n memorie, atunci seconsider? c? segmentul ?i tabelul s?u de pagini se afl? n memorie. Daca segmentuleste n memorie, descriptorul s?u con?ine un pointer de 18 bi?i c?tre tabelul s?u depagini dup? cum se poate vedea din figura 6.13.

Fig. 6.13. Descriptorul de segment ?i indicarea tabelelor de pagini.

Deoarece adresele fizice au 24 de bi?i ?i paginile sunt aliniate la limite de 64de octe?i sunt necesari numai 18 bi?i n descriptor pentru a stoca adresa tabelului depagini. Descriptorul con?ine de asemenea dimensiunea segmentului, bi?ii deprotec?ie ?i alte cteva elemente. n figura 6.14 se poate observa un descriptor desegment Multics.

Adresa segmentului n memoria secundar? nu este n descriptorul desegment, ci ntr-un alt tabel care este folosit de agentul de tratare a defectelor alsegmentului.

263

Fig. 6.14. Ilustrarea unui descriptor de sistem.

Trebuie specificat c? fiecare segment este un spa?iu de adrese obi?nuit ?iastfel ?i paginarea se face la fel ca la paginarea memoriei nesegmentate.Dimensiunea normal? a paginii este de 1024 de cuvinte. O observa?ie pertinent?este c? exist? segmente nepaginate sau paginate n unit??i de 64 de cuvinte deobicei segmente mici ?i astfel se economise?te memorie fizic?.

O adres? n Multics const? din dou? p???i: segmentul ?i adresa n cadrulsegmentului. Adresa din cadrul segmentului este mai departe divizat? ntre un num?rde pagin???i un cuvnt n cadrul paginii. n figura 6.15 se observ? aceast? divizare.

Fig. 6.15. O adres? virtual? Multics de 34 de bi?i.

Cnd are loc o referire la memorie, se urm?re?te urm?torul algoritm:1. Num?rul de segment este folosit pentru a g?si descriptorul de segment;2. Se verific? dac? tabelul de pagini al segmentului se afl? n memorie. Dac?

tabelul de pagini este n memorie, i se stabile?te loca?ia. Dac? nu este n memorie, areloc un defect de segment. Dac? are loc o nc?lcare a protec?iei, se genereaz? o capcan?.

3. Se examineaz? intrarea din tabelul de pagini pentru pagina virtual? cerut?.Dac? pagina nu este n memorie, are loc un defect de pagin?. Dac? este nmemorie, adresa de memorie principal? a nceputului paginii este extras? dinintrarea tabelului de pagini.

4. Se adaug? deplasarea la originea paginii pentru a furniza adresa dememorie principal? la care se afl? cuvntul.

5. Are loc citirea sau scrierea n memorie (vezi figura 6.16).

264

Fig. 6.16. Conversia unei adrese Multics.

Pentru simplitate, a fost omis faptul c? nsu?i descriptorul de segment estepaginat. De fapt, este folosit un registru (registrul de baz? al segmentului) pentru alocaliza descriptorul tabelului de pagini al segmentului, care la rndul s?u indic?spre paginile descriptorului de segment. ndat? ce este g?sit descriptorul pentrusegmentul dorit, se continu? adresarea dup? cum este ar?tat n figura 6.17.

Dac? algoritmul precedent ar fi fost rulat de c?tre sistemul de operare la fiecareinstruc?iune, evident programul nu ar fi rulat foarte rapid. Pentru a nu exista aceast?problem? hardul Multics con?ine o tabel? TLB de vitez? mare pe 16 cuvinte, carepoate c?uta n paralel o anumit? cheie prin toate intr?rile sale. Aceasta este ilustrat?n figura 6. Cnd o adres? este prezentat? calculatorului, hardul de adresare verific?nti dac? adresa virtual? se afl? n TLB. Dac? adresa se afl? n TLB, num?rulcadrului de pagin? se ob?ine direct din TLB ?i se formeaz? adresa efectiv? acuvntului referit f??? a se consulta descriptorul de segment sau tabelul de pagini.

Fig. 6.17. Tabela TLB Multics simplificat?.

265

Adresele celor 16 cele mai recent referite pagini sunt salvate n TLB.Programele ale c?ror seturi de lucru sunt mai mici dect dimensiunea tabelei TLBvor ajunge la echilibru cu adresele ntregului set de lucru din TLB ?i prin urmarevor rula eficient. Dac? pagina nu este n TLB, descriptorul ?i tabelele de pagini suntreferite efectiv pentru a se g?si adresa cadrului de pagin?? ?i tabela TLB esteactualizat? prin includerea acestei pagini, fiind eliminat? pagina utilizat? cel maipu?in recent. Cmpul de vrst???ine eviden?a intr?rilor utilizate cel mai pu?in recent.Tabela TLB este folosit? pentru a compara n paralel segmentele ?i numerele depagin? ale tuturor intr?rilor.

6.3.2. Memoria virtual? la Intel

Din multe puncte de vedere, memoria virtual? de la Pentium se aseam??? cucea de la MULTICS, incluznd prezen?a att a segment?rii ct ?i a pagin?rii. ntimp ce MULTICS are 256K segmente independente, fiecare de pn? la 64Kcuvinte de 36 de bi?i, Pentium are 16K segmente independente, fiecare ?innd pn?la 1 miliard de cuvinte de 32 de bi?i. Cu toate c? sunt mai pu?ine segmente,dimensiunea mai mare a segmentului este de departe mult mai important?, ntructpu?ine programe au nevoie de mai mult de 1000 de segmente ?i multe programenecesit? segmente mari.

Inima sistemului de memorie virtual? de Ia Pentium este format? din dou?tabele: LDT (tabela descriptorilor locali) ?i GDT (tabela descriptorilor globali).Fiecare program are propria sa tabel? LDT, ns? exist? o singur? copie a tabeleiGDT, partajat? de toate programele de pe calculator. Tabela LDT descrie segmentelelocale fiec?rui program, cuprinznd codul, datele, stiva ?i a?a mai departe, n timp ceGDT descrie segmentele sistem, inclusiv cele ale sistemului de operare.

Pentru a accesa un segment, un program de pe Pentium ncarc? mai nti unselector pentru segmentul respectiv, ntr-unul din cele 6 registre de segment alema?inii. n timpul execu?iei, CS p?streaz? selectorul pentru segmentul de cod ?i DSpentru cel de date. Celelalte registre de segment sunt mai pu?in importante. Fiecareselector este un num?r pe 16 bi?i, a?a cum se vede n figura 6.18.

Fig. 6.18. Selector Pentium.

266

Unul dintre bi?ii selectorului indic? dac? este vorba despre un segment localsau global (adic? segmentul este n LDT sau n GDT). Al?i treisprezece bi?iprecizeaz? num?rul intr?rii n LDT sau GDT, astfel nct aceste tabele nu pot p?stradect 8K descriptori de segmente. Ceilal?i doi bi?i se refer? la protec?ie ?i vor fidiscuta?i mai trziu. Descriptorul 0 este invalid. El poate fi ns? nc?rcat ntr-unuldin registrele de segment, pentru a indica faptul c? registrul segment nu estemomentan disponibil. Folosirea lui declan?eaz? o capcan?.

n momentul n care un selector este nc?rcat ntr-un registru de segment,descriptorul corespunz?tor este preluat din LDT sau GDT ?i memorat n registreleinterne ale MMU, pentru a putea fi accesat mai rapid. Un descriptor const? din 8octe?i, cuprinznd pe lng? alte informa?ii ?i adresa de baz? a segmentului, a?a cumse observ? n figura 6.19.

Fig. 6.19. Descriptor de segment de cod pentru Pentium.

Formatul selectorului a fost ales n mod inteligent, pentru a u?ura localizareadescriptorului. Se selecteaz? mai nti fie LDT, fie GDT, n func?ie de bitul 2 dinselector. Apoi selectorul este copiat ntr-un registru de lucru (scratch) intern alMMU, iar cei mai pu?in semnificativi 3 bi?i sunt seta?i la 0. n final, adresa LDTsau GDT este adunat?, ob?inndu-se un pointer direct spre descriptor. De exemplu,selectorul 72 se refer? la intrarea 9 n GDT, care se afl? la adresa GDT+72.

Sunt prezenta?i pa?ii prin care o pereche (selector, deplasare) este convertit?ntr-o adres? fizic?. De ndat? ce microprogramul ?tie ce registru de segment estefolosit, el poate g?si descriptorul complet al segmentului corespunz?tor selectoruluin registrele sale interne. Dac? segmentul nu exist? (selector 0) sau nu estemomentan n memorie, se declan?eaz? o capcan?.

Apoi se verific? dac? deplasarea este dincolo de grani?a segmentului, caz ncare se declan?eaz? alt? capcan?. Logic, n descriptor ar trebui s? existe un cmp de32 de bi?i, pentru a preciza dimensiunea segmentului, dar deoarece sunt disponibilidoar 20 de bi?i, trebuie folosit? o alt? metod?.

267

Dac? n cmpul G (granularitate) este valoarea 0, cmpul limit? (Limit)reprezint? atunci dimensiunea exact? a segmentului, pn? la valori de 1MB. Dac?valoarea este 1, atunci cmpul limit? con?ine dimensiunea segmentului n pagini ?inu n octe?i. Dimensiunea paginii la Pentium este fixat? la 4KB, astfel nct 20 debi?i ajung pentru segmente de pn? la 212 octe?i.

Presupunnd c? segmentul este n memorie ?i c? deplasarea este corect?,Pentium adun? apoi la deplasare cmpul baz? (Base) de 32 de bi?i din descriptor,pentru a forma ceea ce se nume?te o adres? liniar? (linear address), a?a cum sevede ?i n figura 6.20. Cmpul baz? este divizat n trei componente ?i distribuit spredescriptor, pentru compatibilitate cu 286, care avea un cmp baz? de doar 24 de bi?i.Ca o consecin??, cmpul baz? permite fiec?rui segment s? nceap? n orice loc dinspa?iul liniar de adrese pe 32 de bi?i.

Fig. 6.20. Conversia unui selector ?i a unei deplas?ri ntr-o adres? liniar?.

Dac? paginarea este dezactivat? (printr-un bit ntr-un registru global decontrol), atunci adresa liniar? este interpretat? ca adres? fizic?? ?i trimis? sprememorie pentru citire sau scriere. De aceea, cu paginarea dezactivat? are o schem?de segmentare pur?, adresa de baz? a fiec?rui segment aflndu-se n descriptorulasociat. Segmentele se pot suprapune, din ntmplare, probabil deoarece ar fi preamare efortul ?i timpul pentru a verifica dac? ele sunt sau nu disjuncte.

Pe de alt? parte, dac? paginarea este activat?, adresa liniar? este interpretat?ca adres? virtual?? ?i pus? n coresponden?? cu o adres? fizic? folosind tabele depagini. Singura complica?ie ce poate ap?rea este c? o adres? virtual? pe 32 de bi?i ?io pagin? de 4K permit unui segment s? con?in? 1 milion de pagini, astfel nct sefolose?te o punere n coresponden?? pe dou? niveluri, pentru a reduce dimensiuneatabelei de pagini pentru segmente mici.

Fiecare program n rulare are asociat un catalog de pagini (page directory),format din 1024 intr?ri de 32 bi?i. El este localizat la o adres? memorat? ntr-unregistru global. Fiecare intrare n acest catalog indic? spre un tabel de pagini carecon?ine de asemenea 1024 intr?ri de 32 bi?i Intr?rile din tabelul de pagini indic?spre cadrele de pagin?.

Schema este prezentat? n figura 6.22.

268

Fig. 6.21. Adresa liniar?.

n figura 6.21 se prezint? o adres? liniar? divizat? n trei cmpuri: Dir(catalog), Pagin? (page) ?i Deplasare (offset). Cmpul Dir este utilizat primul caindex n catalogul de pagini, pentru a localiza pointer-ul c?tre tabelul de paginicorespunz?tor. Apoi cmpul Pagin? este folosit ca index n tabelul de pagini, pentrua afla adresa fizic? a cadrului de pagin?. Cmpul Deplasare este adunat la adresacadrului de pagin? pentru a ob?ine adresa fizic? a octetului sau cuvntului adresat.

Intr?rile n tabelul de pagini sunt de 32 de bi?i fiecare, din care 20 de bi?icon?in un num?r de cadru de pagin?. Ceilal?i bi?i reprezint? bi?i pentru controlulaccesului ?i bi?i pentru a indica modificarea regiunii, seta?i de c?tre hard pentrusistemul de operare, bi?i de protec?ie ?i al?i bi?i utilitari.

Fiecare tabel de pagini are 1024 de intr?ri pentru cadre de pagin? de 4K,astfel nct o singur? tabel? de pagini gestioneaz? 4MB de memorie. Un segmentmai mic de 4M va avea un catalog de pagini cu o singur? intrare, un pointer c?tresingura ?i unica lui tabel? de pagini. Astfel, consumul suplimentar de memorieindus de segmentele scurte este doar de dou? pagini, n loc de milioane de paginidac? s-ar fi folosit tabele de pagini pe un singur nivel.

Pentru a evita accesul repetat la memorie, Pentium, ca ?i Multics, are o mic?tabel? TLB pentru a reg?si repede cele mai recent folosite combina?ii Dir-Pagin???ia Ie pune n coresponden?? cu adresa fizic? corespunz?toare cadrului de pagin?.Doar pentru acele combina?ii care nu au fost folosite recent se urmeaz? pa?ii descri?in figura 6.22. Atta timp ct lipsurile TLB sunt rare, performan?a este bun?.

Fig. 6.22. Coresponden?a ntre o adres? liniar???i o adres? fizic?.

Este important de men?ionat c? dac? o anumit? aplica?ie nu necesit?segmentare, ci se mul?ume?te cu un spa?iu de adresare unic de 32 de bi?i, paginat,acest lucru se poate ob?ine foarte u?or. Toate registrele segment pot fi nc?rcate cuaceea?i valoare a selectorului, care are un descriptor cu baz? = 0 ?i limit? devaloare maxim? permis?. Deplasarea instruc?iunii va fi adresa liniar?, cu un singur

269

spa?iu de adrese folosit, adic? paginare tradi?ional?. De fapt, toate sistemele deoperare pentru Pentium func?ioneaz? n acest mod. OS/2 a fost singurul care s-afolosit de toat? puterea arhitecturii MMU de la Intel.

Proiectarea sistemului de memorie virtual? la Intel Pentium, date fiindscopurile contradictorii de implementare a pagin?rii pure, a segment?rii pure ?i asegmentelor paginate, este un real succes. Faptul c? s-a p?strat compatibilitatea cu286 ?i c? s-au reu?it toate acestea ntr-un mod att de eficient este un real succesdin punct de vedere al proiect?rii.

6.3.3. Memoria virtual? la Motorola

Din punct de vedere conceptual, utilizarea memoriei virtuale este mai simpl?la microprocesorul Motorola 68030, utiliznd doar scheme de paginare pur?. Cutoate acestea, datorit? faptului c? schemele Motorola folosesc un num?r variabil deniveluri de tabelare (ntre 0 ?i 4), sistemul de operare ar avea de ndeplinit opera?iidestul de elaborate, de aceea majoritatea sarcinilor de gestionare a memoriei suntpreluate de un controler de tip MMU (Memory Management Unit), care ncepndcu 68030, este integrat n aceea?i capsul? cu cipul care reprezint? nucleul procesor.

Observa?ie. La microprocesoarele Pentium exist? unitatea de pagin? (Page Unit).n locul mp???irii fixe a adreselor liniare n zonele Dir, Page ?i Deplasare (vezi

figura 6.21), num?rul zonelor de tabelare ?i num?rul de bi?i ai fiec?rui nivel sunt specificaten cmpurile unui registru global, denumit TCR (Translation Control Register).

12 4 3 2 11

Fig. 6.23. Structura adresei liniare la Motorola 68030.

C

ignora?i A B C deplasament

X 10 7 0 6

4 bi?i

MSB deplasament

B

8intr?ri

16intr?ri

A

32 bi?i (adres? liniar?)

270

Adresa liniar? va fi mp???it? conform figurii 6.23.Avnd n vedere c? majoritatea programelor utilizeaz? o memorie virtual?

mult mai mic? de 4 GB (232), n registrul TCR este prev?zut ?i un cmp n care sepoate preciza num?rul MSB al adresei la care se renun??.

Exemplu. Prin intermediul TCR, se poate preciza c?: 12 bi?i MSB sunt ignora?i; 4 bi?i reprezint? nivelul de tabelare A; 3 bi?i reprezint? nivelul de tabelare B; 2 bi?i reprezint? nivelul de tabelare C; 11 bi?i reprezint? deplasamentul (deplasament n pagin? de 2 K).