Capitolul 2 - Gestiunea memoriei interne

Obiective

In acest capitol sint prezentate principalele tehnici de gestiune a memoriei folosite de sistemele de operare. Acestea sint: alocarea singulara contigua, partitionarea, paginarea (simpla si la cerere), segmentarea (simpla sau cu paginare la cerere), swapping-ul, overlay-ul si ierarhiile de memorii (cache). In ultimul modul al acestui curs, este prezentat succint felul in care SO Unix administreaza memoria interna, combinind doua tehnici: swapping-ul si paginarea la cerere.

Continut

Alocare singulara contiguaGestiunea memoriei cu partitionarePaginarea memorieiPaginarea la cerereSegmentareSegmentare cu paginare la cerereAlte tehnici de gestiune a memorieiGestiunea memoriei in Unix

Cuvinte cheie: alocarea memoriei, partitionare, paginare (la cerere), segmentare, swapping, overlay, cache

Modul1 - Alocare singulara contigua

Acesta tehnica presupune ca intreaga memorie interna (exclusiv desigur, zona alocata SO) este alocata job-ului sau procesului care o solicita. In fapt, spatiul de adrese al programului (totalitatea adreselor dintr-un program) se map-eaza pe spatiul fizic de adrese al memoriei principale, dupa cum se poate vedea si din figura urmatoare:

Fig.6. Alocare singulara contigua a memoriei

ObservatieDe obicei, spatiul de adrese al SO este mai mare decit zona rezervata lui din memorie - ca urmare, doar o parte a SO este rezidenta in memoria interna.

In ceea ce priveste cele patru functii ale unui modul de gestiune a resurselor, in cazul acestei tehnici, se pot spune urmatoarele:SR. Modulul de gestiune a memoriei interne (MGM) trebuie sa determine de unde pina unde se intinde spatiul ocupat de SO; deasemenea el trebuie sa determine care este zona in care se pot incarca programele utilizator;

13

PA. In acest caz nu se poate pune problema existentei unei politici de alocare;AR. Alocarea spatiului de memorie este totala catre job-ul sau procesul respectiv;ER. Eliberarea spatiului de memorie este automata, la terminarea job-ului (procesului).

Dupa cum se poate observa, este necesar ca MGM se determine intre ce adrese se poate rula job-ul (proces-ul) utilizator; mecanismul hardware de control al acestei executii este realizat cu ajutorul a doi registri: un registru de baza RB si un registru limita RL. SO este acela care nu va executa eventualele instructiuni care vor genera adrese in afara acestor limite. Ca urmare a acestei restrictionari asupra adreselor pe care le pot accesa programele, se impune existenta a doua moduri de lucru:

utilizator: in care nu se poate face acces la zona rezervata SO; sistem: in care se permite accesul la orice locatie de memorie.

Avantajele acestei tehnici constau in:

simplitatea ei necesitatea unui suport de memorie redus (SO-ul folosit fiind simplu, o mare parte

din spatiul de memorie va putea fi folosit direct de programele utilizator); folosirea unor elemente hardware suplimentare ieftine (doi registri).

Dezavantajele prezentate de tehnica de alocare singulara sint:

memoria este incomplet utilizata exista momente in care unicul proces din memorie executa operatii de I/O, el

nefolosind procesorul - s-a constatat ca, din acest motiv, procesorul sta nefolosit cam 65-70% din timp, ceea ce este deigur extrem de ineficient!

in memorie se incarca tabloul static al programelor si, cum acesta poate contine rutine care nu se executa niciodata, are loc o ocupare inutila a memoriei;

nu se pot rula programe mai mari decit memoria fizica.Modul2 - Gestiunea memoriei cu partitionare

Solutia gasita de proiectantii de SO pentru a depasi unele din neajunsurile prezentate de tehnica prezentata anterior este multi-programarea. Aceasta tehnica consta, dupa cum stim, in incarcarea in memoria interna, a spatiului de memorie al mai multor

programe. Pentru a se putea realiza acest lucru trebuie ca , unde n este gradul

de multi-programare.

Observatie

Folosind aceasta multi-programarea creste gradul de utilizare a memoriei, dar ea nu se poate folosi integral datorita fragmentarii care se produce; Deasemenea, si in acest caz procesorul poate sta nefolosit daca toate procesele fac la un moment dat operatii de I/O.

O prima tehnica utilizind multi-programarea este aceea de gestiune a memoriei principale cu partitionare. Aceasta tehnica a fost folosita in SO aparute in anii '60-'70, care erau de

14

tip batch-processing. In acele sisteme, memoria operativa era impartita in zone numite partitii. In fiecare partitie se putea incarca un job (sau proces).

Fig.7. Partitionarea memoriei

In acest caz cele patru functii ale unui modul de gestiune a resurselor sint realizate astfel:

SR. MGM trebuie sa determine care sint partitiile, de unde pina unde tine fiecare, daca o partitie este libera sau ocupata, cui ii este ea alocata - in acest din urma caz - si cit spatiu ocupa procesul respectiv din partitia in care a fost incarcat;PA. Politica de alocare se poate implementa fie la planificarea de job-uri, fie la planificarea de procese;AR. Alocarea unei partitii catre un anumit job se va face prin actualizarea structurilor de date corespunzatoare, urmata fiind de incarcarea efectiva a job-ului in partitia respectiva;ER. Eliberarea unei partii se face cu sau fara prelevare fortata, functie de tipul SO.

Este evident ca avind in memorie simultan mai multe procese, ele trebuie impiedicate sa se jeneze unele pe altele sau sa interactioneze nedorit cu SO - solutiile adoptate de proiectantii de SO pentru realizarea acestei protectii au fost, pe rind, urmatoarele:

initial s-a folosit o solutie in care existau cite doi registri (RB,RL) pentru fiecare program utilizator, acestia avind o functionalitate asemanatoare celor de la tehnica precedenta; depasirea adreselor aflate in acesti doi registri conducea la o eroare de violare a protectiei memoriei. S-a constatat insa ca, in cazul in care mai multe procese realizeaza operatii de I/O, este posibil ca datele citite de acestea sa se suprapuna, ceea ce este de nedorit desigur! Un exemplu simplu pentru a ilustra in ce fel se paote produce aceasta suprapunere este urmatorul: fie un proces Pi care face o cerere de I/O - el va fi nevoit sa cedeze procesorul altui proces, fie el Pj, care - daca nu se afla deja in memoria interna - va fi adus acolo. Este posibil ca el sa fi adus chiar in partitia ocupata anterior de P i, dupa ce acesta a fost salvat pe disc impreuna cu valorile proprii pentru RB si RL - noile valori pentru RB si RL vor fi cele corespunzatoare procesului Pj. Ca urmare a acestor noi valori pentru acesti registri delimitatori, este posibil ca datele citite pentru procesul P i sa fie suprapuse peste zona din partitie alocata procesului Pj;

a doua solutie folosita, care a inlaturat neajunsurile primei solutii, consta in folosirea unor chei de acces si protectie astfel: o partitie este impartita in zone mai mici, fiecarei astfel de zone atasindu-i-se o aceeasi valoare a cheii de protectie

15

(corespunzatoare partitiei respective). Cind o anumita partitie este alocata unui job, i se va asocia acestuia o cheie de acces egala ca valoare cu cheia de protectie a partitiei care i se aloca. In acest fel orice fel de suprapunere este eliminata. Ar mai fi de observat ca, deoarece este greu de pus cite o cheie pentru fiecare locatie de memorie - in fapt, se ataseaza cite o cheie de protectie pentru fiecare 2K; in consecinta memoria va fi alocata in incremente de 2K. Trebuie mentionat deasemenea faptul ca SO are cheia de acces 0 (echivalent cu faptul ca impotriva lui nu exista protectie!!).

Exista doua modalitati de specificare a partitiilor:

statica (partitii fixe): partitiile sint precizate inaintea inceperii executiei primului program; ele pot sa fie fixate la generarea SO sau precizate la incarcarea SO. In acest caz mai trebuie rezolvata o problema vizavi de dimensiunea partitiilor - daca acestea sint prea mari, ele sint usor de gestionat, insa memoria este prost folosita - daca ele insa sint prea mici, vor fi greu de gestionat si nu se vor putea rula job-uri mari;

dinamica (partitii variabile): din spatiul liber se creeaza partitii numai la cererea job-urilor (proceselor), partitiile formate avind dimensiunea job-uluui sau procesului

In cazul alocarii dinamice sint de interes doua structuri de date: tabela de partitii PARTITII si tabela de spatiu liber LIBER. Sa consideram urmatorul exemplu:

PARTITII

Numar Dimensiune Adresa_de_start Stare1 8 312 alocat2 32 320 alocat3 - - intrare libera4 120 384 alocat5 - - intrare libera

LIBER

Numar Dimensiune Adresa_de_start Stare1 32 352 disponibil2 520 504 disponibil3 - - intrare libera4 - - intrare libera

16

Fig.8. Exemplu de alocare a memoriei cu partitionare

Pentru crearea si alocarea unei partitii se pot folosi doua strategii:

first-fit (prima potrivire): se cauta in tabela de spatiu liber prima zona suficient de mare pentru a putea fi alocata job-ului care a cerut-o. In continuare se formeaza o partitie (de dimensiune egala cu cea a job-ului) in aceasta zona, restul zonei raminind libera. Aceasta tehnica are o viteza mare, dar strica zonele mari de memorie, producind fragmentare;

best-fit (cea mai buna potrivire): se parcurge toata tabela de spatiu liber, alocindu-se zona de memorie care are o dimensiune mai mare sau egala cu cea ceruta de job si este cea mai apropiata ca marime de dimensiunea job-ului. Aceasta tehnica are o viteza mai redusa, insa ea nu distruge zonele mari de memorie. Oricum si ea produce fragmentare.

In continuare va fi listat algoritmul first-fit de alocare a unei partitii pentru un job care solicita n K de memorie:

**algoritm Alocarea_a_n_K_in_tehnica_first_fit estegasitfalsl1 /* index de intrare in tabela de spatiu liber */cit timp (llmax) si not gasit executa /* lmax este numarul maxim deintrari in tabela LIBER */

daca LIBER[l].Dimensiunen atuncigasitadevaratlocatie_de_startLIBER[l].Adresa_de_start

altfel ll+1[]

[]daca gasit=fals atunci *alocare_imposibilaaltfel

daca LIBER[l].Dimensiune=n atunciLIBER[l].Stare'intrare libera'

altfel /* LIBER[l].Dimensiune>n */LIBER[l].DimensiuneLIBER[l].Dimensiune-n

17

LIBER[l].Adresa_de_startLIBER[l].Adresa_de_start+n[]* gaseste in PARTITII o intrare libera p

/* daca tabela este corect dimensionata, acest lucru este intotdeauna posibil */PARTITII[p].DimensiunenPARTITII[p].Adresa_de_startlocatie_de_startPARTITII[p].Stare'alocat'

[]** stop

Observatie

In practica, deoarece folosirea celor 2 tabele este ineficienta - ele avind multe intrari libere - se recurge la inlantuirea spatiului disponibil. Daca se foloseste tehnica first-fit, zonele libere se inlantuie in ordinea crecatoare a adreselor. In cazul alocarii best-fit, zonele libere se inlantuie in ordinea crescatoare a dimensiunilor. Ca urmare, in ambele cazuri, se va cauta - in medie - o jumatate de lista.

O problema serioasa cu care ne confruntam, in cazul partitiilor de lungime variabila, este

fragmentarea. Aceasta consta in faptul ca o_cerere_de_memorie, dar

oricare ar fi spatiu_liberi acesta este mai mic decit cererea_de_memorie. Solutia pentru rezolvarea problemei fragmentarii este relocarea, adica mutarea

programelor in memorie, astfel incit prin compactarea lor sa se obtina la sfirsitul memoriei fizice un spatiu suficient de mare. Problemele care apar in legatura cu acest proces sint:

mutarea in memorie a programelor consuma timp procesor, ceea ce conduce la cresterea overhead-ului;

in programe exista informatii dependente de adresa, care trebuie modificate corespunzator in cazul deplasarii lor in memorie. Sint doua abordari posibile: fie sa se scrie cod pur (numit si reentrant), independent de pozitie (PIC= position independent code), care isi pastreaza datele in registri, fie sa se calculeze noile adrese dinamic, folosind un registru de relocare (valoarea din acest registru va fi adunata la toate adresele din program, ea calculindu-se conform zonei unde programul va fi deplasat).

Exista doua modalitati practice de a face compactare:

orice creare de zona libera sa fie insotita de compactare - aceasta solutie este inacceptabila, deoarece este mare consumatoare de timp;

numai la nevoie, adica se fac alocari si, cind acest lucru nu mai este posibil, se va face compactare.

Principalul avantaj al gestionarii memoriei cu partitionare este faptul ca, folosind relocarea, se poate ajunge la un procent de folosire a memoriei de 100%, ceea ce conduce la un grad mare de multi-programare si de utilizare a procesorului si a celorlalte resurse.

Dezavantajele folosirii acestei tehnici sint:

18

existenta unui mecanism hardware suplimentar conduce la o crestre a costurilor;algoritmii care trebuie rulati pentru a face alocarea partitiilor maresc overhead-ul;structurile de date folosite consuma spatiul din cel rezervat SO;limitarea marimii programelor la marimea memoriei interne.

Modul3 - Paginarea memoriei

Este simplu de observat ca s-ar putea facilita gestiunea memoriei dca ea s-ar aloca in "portii" de lungime fixa. Deasemenea, ar fi bine daca nu ar fi necesar ca programul sa ocupe in memoriei bancuri consecutive (el putind ramine logic continuu, desi este distribuit in memorie). Plecind de la aceste doua considerente, s-a elaborat tehnica paginarii memoriei in care spatiul de adrese al programului se imparte in zone de lungime fixa numite pagini, iar memoria interna este impartita in zone de lungime egala cu pagina, numite blocuri. Orice astfel de pagina poate fi incarcata in orice bloc printr-un mecanism de map-are.

Fig.9. Paginarea memoriei

Observatii

Din necesitatea de a aloca un numar intreg de pagini unui program oarecare, in ultima pagina poate sa ramina un spatiu nefolosit (in medie, o jumatate de pagina rammine neutilizata) – acest fenomen se numeste fragmentare interna si este mult mai putin important decit fragmentarea;

Si in acest caz, ca si in cel al partitiilor, se pune problema dimensiunii paginilor – daca paginile sint mari, gestiunea lor este simpla, dar spatiul pierdut in ultima pagina este mare; daca ele au dimensiune mica, gestiunea devine dificila, insa fragmentarea interna se reduce;

Ca in multe alte situatii, s-a optat pentru o solutie de compromis, alegindu-se ca dimensiune pentru o pagina fie 2K, fie 4K.

Mecanismul de protectie consta in asocierea cu fiecare bloc a unei chei de protectie, toate blocurile asociate aceluiasi program avind aceeasi valoare a acestei chei; programul corespunzator va avea asociata o cheie de acces de aceeasi valoare cu cheia de protectie.

19

In ceea ce priveste implementarea mecanismului de map-are al paginilor in blocuri, fiecare pagina va avea asociat un registru de mapare (Page Map Register - PMR), care, in mod dinamic, va ajuta la adresarea in pagina respectiva. S-a optat pentru folosirea registrilor si nu a unor locatii de memorie, deoarece adresarea la registri este foarte rapida vizavi de cea la memorie. La nivelul sistemului, pentru fiecare job(proces), va exista o tabela de PMR-uri, fie ea Page_Map_Table i (PMTi). In sistem exista deasemenea o tabela care pastreaza starea tuturor blocurilor, fie ea Map Block Table (MBT). Un exemplu care sa ilustreze un posibil continut pentru aceste structuri de date, corespunzator unei stari a memoriei la un moment dat, este urmatorul:

Fig.10. Exemplu de paginare a memoriei

PMT2

Pagina Blocul_in_care_se_incarca_pagina0 31 5.. ..

MBTNumar Stare Cui_ii_este_alocat0 alocat SO1 alocat SO2 liber -3 alocat job24 alocat job15 alocat job2.. .. ..

20

Observatii

La nivelul sistemului exista deasemenea o tabela de job-uri, in care pentru fiecare job se pastreaza adresa primei pagini apartinind job-ului respectiv si numarul sau de pagini;

Daca ne gindim la paginarea unei memorii de numai 1M, in blocuri de 2K, rezulta ca ar fi necesari 512 registri pentru PMR-uri - in practica insa nu se va folosi decit un set de registri corespunzatori job-ului activ, restul de PMT-uri fiind tinute in memorie.

Referitor la cele 4 functii ale unui modul de gestiune de resurse, in cazul paginarii putem sublinia ca:SR. Starea memoriei se poate determina din MBT (pentru intreg sistemul) si PMTi (pentru fiecare job);PA. Este implementata de planificatorul din nucleul SO;AR. Consta in actualizarea PMT-urilor si a tabelei MBT si in incarcarea efectiva a paginilor in blocuri;ER. Este totala, la terminarea job-ului si consta in actualizarea corespunzatoare a MBT.

Avantajul principal al paginarii este gradul mare de utilizare a memoriei fara fragmentare. Dezavantajele acestei tehnici sint:

necesitatea existentei unui mecanism hardware suplimentar ceea ce se va reflecta in costuri;

structurile de date care trebuie sa se regaseasca in SO sint numeroase si voluminoase; algoritmii care implementeaza tehnica sint complicati; mecanismul de map-are, activ in executie, va duce la o incetinire a functionarii SO; nu se pot rula programe mai mari decit memoria fizica.

Modul4 – Paginarea la cerere

Neajunsul de nu putea rula programe mai mari decit memoria fizica, poate fi eliminat daca nu se incarca in memorie tot programul, ci numai parti din el care se executa la un moment dat. Tehnica prezentata in continuare, cunoscuta sub numele de paginare la cerere permite acest lucru. In cazul foolosirii ei programul isi poate incepe executia fara ca tot spatiul sau de adrese sa fie incarcat in memorie. Astfel, un program isi poate incepe executia fara ca spatiul sau de adrese sa fie incarcat in intregime in memoria interna. Cind un program va solicita o pagina care nu este inca incarcata in memorie, se va genera o eroare de lipsa de pagina - pentru a rezolva aceasta situatie de eroare fie:

daca exista vreun bloc liber se va incarca in el pagina ceruta; daca nu exista un astfel de bloc, se va elibera un bloc (pe baza unui algoritm

de paginare la cerere), trimitind pagina din el pe disc; in locul acestei pagini va fi incarcata pagina ceruta.

21

Observatie

Functionarea acestiu mecanism presupune swapping, adica presupune ca exista posibilitatea transferului de pagini spre (swap-out) si dinspre harddisk (swap-in); Daca pagina care va fi trimisa pe disc nu este bine aleasa, se va produce paginare continua (thrashing), adica o pagina care abia a fost trimisa pe harddisk, va fi necesara la un moment de timp imediat urmator si tot asa.

Privitor la cele 4sarcini de baza ale unui sistem de gestiune a resurselor, in acest caz, se poate preciza ca:

SR. Evidenta starii memoriei se tine cu ajutorul MBT, PMTi si o tabela suplimentara, File Map Table (FMT), care pastreaza adresa pe suportul extern a fiecarei pagini apartinind oricarui job;PA. Se implementeaza partial la planificarea de job-uri si dinamic, pe masura ce procesele isi cheama paginile. Ea presupune posibilitatea prelevarii fortate a unui bloc de memorie;AR. Presupune actualizarea MBT si a PMT-ului curent;ER. Se face fie prin prelevare fortata, fie la terminarea executiei unui job (sau proces); si ea presupune actualizarea SD corespunzatoare.

Pentru a putea face paginare la cerere sint necesare citeva elemente hardware suplimentare, cum ar fi:

un bit (pastrat in tabela PMTi) care sa indice prezenta sau absenta unei pagini din memorie; hardware pentru generarea unei intreruperi, cind are loc o eroare de lipsa de pagina; hardware pentru inregistrarea gradului de utilizare al fiecarei pagini, necesar deoarece decizia de a scoate o pagina din memorie se bazeaza pe istoria utilizarii ei).

Observatie

Paginarea la cerere nu s-a aplicat multa vreme, desi ea exista conceptual - s-a intimplat asa deoarece nu existau conditiile fizice necesare, mai precis nu exista mecanismul de intrerupere corespunzator erorii de lipsa de pagina. Acesta a devenit disponibil abia cu Intel 386/486.

Algoritmii de paginare la cerere care pot fi folositi pentru a face paginare sint:

1. FIFO (First In First Out) - elimina din memorie pagina cea mai veche, deci care se afla acolo de cel mai mult timp;2. LRU (Least Recently Used) - transfera pe disc pagina cel mai putin recent utilizata, adica pagina utilizata cel mai demult de catre un program in executie; din acest motiv el mai este cunoscut si sub numele de NUR (Not Used Recently);3. MRU (Most Recently Used) - duce pe disc pagina cel mai recent folosita, adica ultima;4. LFU (Least Frequently Used) - trimite pe disc pagina folosita cel mai putin frecvent;5. RAND (RANDom) - presupune ca toate paginile au aceeasi probabilitate de a fi adresate, asa ca alege una la intimplare pentru a o elimina din memoria interna;

22

6. Metoda Dubletilor - rafineaza mecansimul de paginare la cerere, eliminind o pagina numai daca ambele sale jumatati trebuie trimise pe disc;7. AO - se bazeaza pe cunoasterea comprtamentului viitor al programelor, el neavind valoare practica; se foloseste numai ca un etalon, comaprindu-se rezultatele sale cu cele obtinute aplicind unul din algoritmii de mai sus.

ObservatiePaginarea la cerere a fost formalizata intr-o masura foarte mare, astfel ca in spatele fiecarui algoritm enuntat mai sus sta un model matematic foarte bine pus la punct.

Algoritmii de paginare la cerere depind de comportamentul programelor. In acest sens, se poate constata ca:

programele au tendinta de a-si concentra adresarile (proprietate numita localitate spatiala), adica multe adrese se afla in aceeasi pagina, la parcurgerea secventiala a programelor - de exemplu in cazul secventelor de program sau al tablourilor de elemente;

deasemenea, o data adresata la un moment de timp t, o locatie va fi adresata cu o mare probabilitate la un moment de timp ulterior (proprietate cunoscuta sub numele de localitate temporala) - de exemplu in cazul ciclurilor.

Stilul de programare poate fi imbunatatit daca se cunoaste felul in care SO gestioneaza memoria - de exemplu, daca un tablou se memoreaza pe coloane, nu este recomandat sa facem acces la elementele lui pe linii, aceasta putind conduce la salturi dese si mari in alte pagini. Ar mai fi de mentionat ca incercarea de a aborda separat gestionarea memoriei de cea a procesorului duce la rezultate foarte proaste - de exemplu,

ar trebui eliminate paginile care ocupa memoria, fara a folosi procesorul; nu va fi eliminat din memorie un proces care solicita o pagina, pina cind nu-i va fi

adusa in memorie pagina ceruta.

Ca urmare se recomanda folosirea unor strategii globale de alocare a memoriei si procesorului, care trebuie aplicate astfel incit sa garanteze deplina siguranta pentru functionarea proceselor.

Modul5 - Segmentarea

Aceasta tehnica, asemanatoare intr-o oarecare masura paginarii, presupune impartirea programelor in unitati logice de lungime variabila, numite segmente, care nu vor fi aduse toate in memorie la un moment dat. Astfel de segmente pot fi: subrutinele, zonele de date, precum si programul principal.

Segmentele au nume simbolice (care vor fi convertite in numere la momentul executiei) si sint caracterizate de drepturi de acces pentru citire, scriere si executie.

Adresarea intr-un segment este bidimensionala, ea facindu-se dupa numele segmentului si un deplasament in cadrul acestuia. Mecanismul de adresare este dinamic, in sensul ca adresele nu se stabilesc la compilare sau la editarea de legaturi, ci la executie - astfel, la fiecare executie, un segment poate primi alt numar si poate fi incarcat la alta adresa de memorie.

23

Segmentarea este implicit la cerere, altfel ar insemna ca se limiteaza marimea programelor la marimea memoriei fizice. Fiecare segment este compilat separat si adresele sint generate in cadrul lui de la 0; o consecinta directa a acestui fapt este ca ele pot fi deplasate oriunde in memorie.

Utilizatorul este constient de existenta segmentarii, spre deosebire de paginare care era transparenta pentru utilizator.

In ceea ce priveste cele 4 functii ale unui sistem de gestiune a resurselor, in cazul segmentarii, se pot preciza urmatoarele:

SR. Structurile de date folosite sint o rtabela de spatiu liber, precum si cite o tabela Segment Map Table (SMTi) pentru fiecare job;PA. Se realizeaza in parte la planificarea de job-uri, cind se incarca unul sau doua segmente (cu compactarea memoriei, daca se impune acest lucru pentru a permite incarcarea acestor segmente) si in parte la cerere, in executie, cind se produce cite o intrerupere de segment lipsa. AR. Presupune aducerea segmentului in memorie, actualizindu-se totodata intrarea corespunzatoare lui din SMTi;ER. Se poate face fie total, la terminarea executiei, fie fortat, cind un segment este ales pentru a fi dealocat.

Printre avantajele segmentarii se pot enumera:

Eliminarea fragmentarii memoriei, datorita faptului ca segmentele pot avea orice dimensiune si pot fi supuse relocarii si compactarii;

Posibilitatea realizarii unui mecanism de memorie virtuala (segmentarea este implcit la cerere);

Transferurile de date se fac exact in cantitatile dorite - de exemplu, daca se doreste transferul unui tablou de 100 octeti se vor transfera exact 100 octeti, spre deosebire de cazul paginarii, cind s-ar fi transferat toata pagina in care se gaseau cei 100 de octeti;

Deasemenea, aceste transferuri de informatie se fac dintr-o data - adica, daca se doreste transferarea unui segment de 16K, se va produce o intrerupere de segment lipsa si se va transfera tot segmentul - in cazul paginarii, presupunind ca dimensiunea paginii ar fi fost de 4K, ar fi fost necesare 4 intreruperi, respectiv 4 transferuri de pe disc;

Utilizarea in comun de segmente (evident corelata cu drepturile de acces corespunzatoare) - de exemplu, procedurile apelate de mai multe job-uri (sau procese), sau unele segmente compilator, cum ar fi stiva, tabela de simboluri. Mai mult, daca segmentul respectiv este cod pur, se foloseste o singura copie pentru toate job-urile

24

Ca dezavantaje pot fi semnalate:

Necesitatea existentei unor elemente hardware pentru realizarea intreruperilor; Dificultatea gestionarii segmentelor de lungime variabila - si ar fi de mentionat,

de exemplu, faptul ca exista riscul de a iesi din segment, ceea ce nu se intimpla la paginare (pentru a rezolva aceasta problema trebuie ca, pentru fiecare adresa, sa se verifice - prin hardware - ca aceasta nu iese din limitele segmentului;

Marimea unui segment este limitata la marimea memoriei fizice.

Modul6 – Segmentarea cu paginare la cerere

Pentru a depasi faptul ca, in cazul segmentarii, marimea unui segment este limitata la marimea memoriei fizice, tehnica segmentarii a fost rafina astfel: segmentele vor fi impartite in pagini de lungime fixa (egala cu lungimea blocului de disc), care nu vor fi aduse toate in memorie atunci cind se va face acces la segmentul care le contine - ele vor fi aduse pe rind, in masura in care este nevoie de ele. Ca urmare a acestei abordari, segmentele pot fi oricit de mari.

In ceea ce priveste functionarea efectiva a acestei tehnici, ea este o imbina caracteristicile corespunzatoare de la segmentare si paginare.

Modul7 – Alte tehnici de gestiune a memoriei

In continuare vor fi listate, pe scurt, citeva tehnici complementare de gestiune a memoriei:

1. Swapping

Aceasta tehnica presupune faptul ca exista permanent un dute-vino intre programele care exista in memoria interna si cele care exista pe disc, primele fiind transferate pe disc, pentru ca ultimele sa poate fi incarcate in memoria interna spre a fi executate.

Fig.11. Swapping-ul memoriei

25

2. Overlay

Tehnica overlay-ului consta in faptul ca in memorie nu va fi incarcat un program in intregime, ci numai parti din el, astfel: se identifica in program zone mutual exclusive (atentie, acestea nu sint nici pagini, nici segmente, ele neavind proprietatile acestora) care sa se suprascrie unele pe altele prin suprapunere. De obicei, se construieste un arbore al programului, urmind ca fiecare cale din acest arbore sa fie incarcata, pe rind, in memorie. In mod obligatoriu, in memorie, trebuie sa existe o "radacina", care contine datele care nu trebuie distruse.

De exemplu, fie un program care va ocupa in executie 150K - el poate fi rulat intr-o memorie interna de 100K folosind aceasta tehnica astfel:

Fig.12. Exemplu de folosire a tehnicii overlay

3. Utilizarea ierarhiilor de memorii

Datorita faptului ca dizpozitivele de memorie de dimensiuni mari au un timp de acces relativ ridicat, adesea se folosesc ierarhii de memorie. Acestea constau din inserarea intre procesor si memoria interna principala a unei memorii rapide, numita memorie "cache", prin intermediul careia se vor face transferurile de informatie intre UCP si memoria principala.

Fig.13. Ierarhie de memorii

26

NotaIerarhia de memorii rezultata va avea capacitatea lui M2, costul apropiat de al lui M2 si timpul de acces al lui M1, ceea ce desigur este foarte atragator!

Ierarhia de memorii functioneaza pe principiul localitatii programelor. Se constata ca la programele cu o buna localitate, intre 65% si 95% dintre ciclurile de acces la memorie sint "hit" (succes), restul fiind "mis" (insucces). Un ciclu hit este un ciclu in care informatia ceruta de catre procesor a fost gasita in memoria cache, nemaifiind necesara aducerea ei din memoria principala.

4. Tendintele actuale in ceea ce priveste gestiunea memoriei sint:

Sa existe memorii interne din ce in ce mai mari. Aceasta tendinta este favorizata de tehnologie care a dus la producerea de circuite de memorare din ce in ce mai ieftine. Trebuie facuta insa observatia ca problemele de gestiune a memoriei nu dispar o data cu folosirea de dispozitive de memorie din ce in ce mai mari!

Sa se foloseasca ierarhii de memorii; Sa se deplaseze catre hardware mecanismele de gestiune a memoriei pentru a obtine o

crestere a vitezei.

Modul8 – Gestiunea memoriei in Unix

In continuare vor fi prezentate citeva considerente privind gestiunea memoriei in SO Unix System V Release 4(standard-ul Unix), gestiune care se face combinind doua tehnici: swapping-ul cu paginarea la cerere, pentru a evita situatii in care algoritmul de paginare ar duce la scaderea performantelor.

Deoarece memoria principala este o resursa limitata, apare necesitatea ca aceasta sa fie extinsa cu o zona pe disc (numita swap area - zona de swap) in care urmeaza sa fie transferate temporar procese sau parti ale acestora, prin swapping. Zona de swap este gestionata altfel decit sistemul de fisiere Unix. Pentru alocarea de spatiu aici se foloseste tehnica first-fit. De transfer se ocupa procesul numit Swapper - acesta se gaseste intr-o bucla infinita la dispozitia nucleului SO, el avind prioritate maxima in mod nucleu.Cind un proces cere o pagina care nu exista in memorie, nucleul SO suspenda executia procesului respectiv pina cind reuseste incarcarea paginii respective, dupa care va relua procesul. Algoritmul de paginare folosit este LRU. In cazurile in care continuarea aplicarii tehnicii de paginare ar conduce la scaderea performantelor, nucleul SO activeaza swapper-ul, care intrerupe procesul curent si il pune pe disc in stare gata de rulare (swapped) - el va continua sa transfere pe disc procese in intregime, pina cind se elibereaza suficienta memorie.

27

Sumar Memoria interna, fiind o resursa limitata, trebuie gestionata cu mare grija de catre SO. Acesta este acela care va asigura executarea oricarui job (proces), indiferent de caracteristicile acestuia, pe baza memoriei interne disponibile.Principalele tehnici de gestiune a memoriei folosite in diversele SO sint:

Alocare singulara contigua Gestiunea memoriei cu partitionare Paginarea memoriei Paginarea la cerere Segmentare Segmentare cu paginare la cerere Alte tehnici de gestiune a memoriei (swapping, overlay, cache).

ExercitiiSubiecte pentru dezbatere

1. Realizarea unui algoritm care sa implementeza tehnica best fit;2. Realizarea unui algoritm care sa elibereze o partitie, cu actualizarile

corespunzatoare in cele 2 tabele.3. Sa se schiteze un algoritm pentru alocarea a n K de memorie pentru un job.4. Care este conditia necesara pentru aplicarea tehnicii de gestiune overlay?5. Care sint tehnicile de gestiune a memoriei interne care permit rularea de

programe mai mari decit memoria fizica?6. Realizati o comparatie intre paginare si segmentare.7. Avantaje/dezavantaje la specificare statica/dinamica a partitiilor.

28