Administrarea memoriei

Administrarea memoriei

Pentru planificarea pe termen scurt este necesara pastrarea proceselor in memorie. De asemenea, procesorul si sistemul de I/O (intrare/iesire) interactioneaza cu memorie, deoarece pentru a putea fi executat un program trebuie sa fie incarcat in memorie. Programele trebuie sa contina buffere pentru a putea oferi spatiul in care se vor primi rezultatele operatiilor de I/O. Deoarece un program poate fi evacuat pe disc urmand sa fie reincarcat in zona de unde a plecat sau in alta zona, suferind o noua relocare, problema care cade in sarcina modulului de administrare a memoriei interne din cadrul sistemului de operare. Problema care se pune este ca memoria este insuficienta (programele nu dispun de intreaga memorie necesara). Deoarece dimensiunea memoriei influenteaza pretul sistemului de calcul, se utilizeaza ierarhiile de memorie. Un element foarte important al memoriilor este viteza de acces, astfel ca daca timpul de acces este foarte bun, memoria este scumpa si mica, in timp ce o memorie cu timp de acces mare este ieftina si de dimensiune mai mare. Ierarhia de memorie se bazeaza pe diferenta de viteza intre mai multe tipuri de memorie, astfel cand se plaseaza mai multe dispozitive de memorie intr-o ierarhie, memoriile mai rapide sunt situate mai aproape de procesor.

Modelul unitatii de control al memoriei este urmatorul:

Informatia, pe masura ce se apropie momentul utilizarii ei, se apropie de procesor trecand prin toata ierarhia de memorie.

Memoria cache prezinta avantaje in utilizare deoarece programele au proprietatea de localitate spatiala sau temporala.

Localitatea spatiala – daca la un moment dat un program a adresat locatia A_i , exista o probabilitate f mare ca la momentul urmator sa se acceseze A_i+1.

Localitatea temporala – daca o locatie de memorie a fost adresata la un moment dat, exista o probabilitate mare ca ea sa fie adresata din nou in momentul urmator de timp.

Memoria ierarhizata bazata se localizeaza spatial la intersectia unei linii cu o coloana, obtinandu-se blocuri de 32 de octeti.

Memoria cache contine un bloc pentru fiecare coloana.

Vectorul indexat indica pe fiecare coloana indicele liniei corespunzatoare blocului adus in memoria cache.

Daca informatia ceruta se gaseste in memoria cache (M1), ea este accesata rapid, avand de-aface cu 'ciclul hit'. Daca informatia ceruta se afla in memoria principala M2, va trebui adusa in M1 (eventual salvand blocul aflat initial in M1), avand de-aface cu 'ciclul miss'.

Continutul unui bloc de 32 de octeti de memorie este urmatorul:

Pot exista: 2¹² – linii; 2⁷ coloane;

Transferul de informatie intre cele doua tipuri de memorie se face dupa urmatorul algoritm:

procesorul genereaza o cerere pentru adresa A;

adresa A este convertita in adresa de linie r, adusa de coloana c si nr. de octet b

if IA [c] != r then (blocul nu se gaseste in memoria cache)

o      se aduce blocul M[r,c] si se depune in M1[c];

o      se seteaza IA[c] = r ;

extrage octetul b din blocul M1[c];

se trimite octetul cerut de procesor.

Schema de mai sus functioneaza pentru programele cu localitate spatiala, aceasta nefiind valabila pentru localitate temporala.

Cand memoria cache e plina si trebuie adusa o informatie, trebuie sa se renunte de la o inf. aflata in memorie (alegandu-se cea mai veche existenta – FIFO sau cea mai recent utilizata –LRU).

Daca programele au o buna localitate, utilizand o ierarhie de memorii ieftine, se pot obtine performante comparabile cu sisteme avand memorii mici, scumpe si rapide.

Fie: S- marimea efectiva a memoriei

C- costul efectiv al unui octet de memorie

T- timpul efectiv de acces pe octet

S₁ – marimea totala a lui M1 (mica)

S₂ – marimea totala a lui M2 (mare)

C₁ – costul pe octet in M1 (mare)

C₂ – costul pe octet in M2 (mic)

T₁ – timp mediu de acces pt M1 (mic)

T₂ – timp mediu de acces pt M2 (mare)

f₁ – functia de frecventa a succeselor pt M1 (ciclu hit)

f₂ = 1- f₁ – functia de frecventa a succeselor pt M2 (ciclu miss)

Procesorul vede o memorie M' cu urmatoarele caracteristici:

S' = S₂ ; M'- memoria echivalenta

C' = ((S₁*C₁)+(S₂*C₂))/S₂ = costul efectiv al unui octet din memoria totala ;

T' = f₁*T₁ + f₂*T₂ .

Daca S₁ << S₂ atunci C₁>C₂ dar apropiat de C₂. Deoarece f₁ >> f₂, de regula T' > T₁, dar apropiat de T₁.

Tehnici de alocare singulara a memoriei

Cea mai simpla schema de management al memoriei este de a avea un singur proces in memorie la un moment dat si sa permita acelui proces sa utilizeze intreaga memorie.

Tehnicile uzuale utilizate pe cele mai simple microcalculatoare sunt prezentate in figura urmatoare:

Memoria este impartita intre sistemul de operare si un singur proces utilizator. Sistemul de operare poate fi localizat in RAM (Random Access Memory) ca in fig (a), sau in ROM (Read Only Memory) la inceputul memoriei ca in fig. (b), sau ca in fig. (c), unde driverele dispozitivelor de I/O se afla in ROM, sistemul de operare in RAM. De exemplu IBM PC foloseste modelul (c), cu driverele dispozitiv ROM localizate in cei 8K superiori din spatiul de adrese de 1M (BIOS). Cand sistemul este organizat in acest mod, poate fi rulat un singur proces la un moment dat. Utilizatorul scrie o comanda la terminal, sistemul de operare incarca programul cerut de pe disc in memorie si il executa. Cand procesul se termina, sistemul de operare afiseaza prompter-ul la terminal si asteapta o alta comanda pentru a incarca un alt proces, scriind peste primul.

Swapping

Intr-un sistem ce poate rula mai multe programe simultan, procesele trebuie tinute in memorie pt ca procesorul sa le poata rula. In sistemele time-sharing situatia este diferita: sunt mai multi utilizatori si mai multe procese decat pot fi tinute in memorie.

Pentru a putea rula aceste procese, acestea trebuie sa se afle in memorie. Mutarea proceselor din memoria principala pe disc se numeste swapping.

Exista variante de sistem in care, in momentul expirarii cuantei de timp asociate unui program, intreg spatiul de adrese e trimis pe disc si in loc se incarca un altul pentru a fi rulat (din spatiul de pe disc).

Eficienta in acest caz este foarte scazuta.

Imbunatatirea variantei de mai sus prezentata se face prin suprapunerea operatiilor de I/O cu cele de calcul. In timp ce un program se executa, un altul sufera operatia de swapout (cel care a pierdut procesorul), iar un altul executa swapin (cel care va primi procesorul in cuanta urmatoare).

Cele doua buffere au rolul de a permite schimbul informatiei cu discul, in momentul in care procesorul ruleaza un program utilizator. Aceasta tehnica s-a aplicat in sist. cu resurse sarace cu mecanisme insuficiente de protectie a memoriei ceea ce a determinat ca bufferele sa fie puse in zona sistemului de operare. Daca acesta are . [d1] operare user si kernell, se realizeaza astfel o protectie minimala.

In varianta prezentata anterior, memoria este uneori subutilizata deoarece se construiesc programe care au nevoie de multa memorie si apoi se ruleaza programe mici in zone mari de memorie. Astfel memoria ramane neutilizata ceea ce este ineficient. Pentru a incarca in memorie mai multe lucrari simultan memoria se partitioneaza in mai multe partitii (intr-un numar fix egal cu nr. de lucrari din sistem sau intr-un numar variabil). Exista partitii fixe, a caror dimensiune si adrese de inceput nu se schimba niciodata, si partitii dinamice.

1. Partitionarea memoriei cu specificare fixa a partitiei

Memoria se imparte in parti fixe in nucleul sistemului de operare.

Pentru fiecare partitie s-a incarcat cate un proces ce apartine aceluiasi job. Este posibil ca procesul sa nu ocupe intreaga partitie care i-a fost alocata (zonele gri = memorie neutilizata). Schema conduce la fenomenul de fragmentare al memoriei, de asemenea se pune problema asigurarii protectiei datelor, astfel ca un proces sa nu acceseze spatiul altui proces.

Cea mai simpla metoda de protectie este cea in care se folosesc doi registrii: registrul limita inferioara si registrul limita superioara.

Programul aflat in executie nu are voie sa genereze adrese fizice mai mici decat continutul registrului limita inferioara sau mai mare decat continutul registrului limita superioara. Intr-o astfel de schema programul se executa de la inceput pana la sfarsit in cadrul partitiei in care a fost creat.

Exista si alte scheme mai bune de protectie. Se pot asocia zonelor de memorie chei de protectie. O intreaga partitie primeste aceleasi chei de protectie, programelor li se asociaza chei de acces. La orice accesare se verifica identitatea cheilor si se permite adresarea.

Exista doua exceptii: - cheie de acces 0 (permite acces general, apartine S.O.), cheie de protectie 0 (zona de memorie neprotejata).

La sosirea in sistem, fiecare lucrare este pusa intr-o coada asociata fiecarei partitii (suficient de mare pentru a primi lucrarea respectiva).

La o partitie mai mica, coada contine mai multe lucrari, iar la o partitie mai mare se poate sa nu existe nici o cerere. Pentru a se evita situatia neutilizarii unor partitii mari de memorie, se poate adopta varianta in care toate lucrarile se pun intr-o singura coada, iar la aparitia unor partitii libere se parcurge de la inceput si primul job care incape in partitie este incarcat.

Schema partitiilor fixe poate fi combinata cu o schema de swapping: cand si-a terminat cuanta, jobul e dus pe disc si este adusa o alta lucrare in acea partitie.

2. Scheme de partitionare dinamica (MVT)

In acest caz partitiile nu sunt precizate la incarcarea sistemului.

Cade in sarcina sistemului de a tine evidenta spatiului ocupat din memorie si a spatiului liber. De cate ori apare o cerere pentru memorie, se cauta o zona libera suficient de mare pentru a fi alocata si se face alocarea, creand dinamic noua partitie. De ex.:

a)     Soseste procesul 1 care cere 36 K – se incarca

b)    Soseste procesul 2 care cere 100K – se incarca

c)     Soseste procesul 3 care cere 256K – se incarca

d)    Procesul 2 face swap-out si e trimis pe disc

e)    Se incarca procesul 4 care gaseste libera zona procesului 2

f)      Procesul 1 se termina, se elibereaza 36K

Prin evacuarea proceselor si incarcarea altora apare fragmentarea memoriei (fragmentare externa).

Intr-o astfel de schema, daca exista un nr de zone libere si apare o cerere, alocarea de memorie se poate face dupa mai multi algoritmi:

First fit (prima potrivire) – se parcurg zonele libere si se alege prima suficient de mare pentru a fi alocata. In urma alocarii pot aparea zone libere mici care nu mai au sanse sa fie alocate (daca sunt mici se aloca cu sp liber alocat)

Best fit – se alege acea zona libera care lasa cel mai mic spatiu neocupat. Dezavantaj: se parcurg toate zonele de memorie. Avantaj: nu raman spatiu mare neocupat.

Worst fit – se alege zona care lasa cel mai mare spatiu liber, presupunand ca acesta e suficient de mare pentru a fi alocata ulterior.

La eliberarea memoriei, zona libera trebuie gestionata de sistem (de ex. Daca este adiacenta cu una sau 2 zone libere, trebuie formate zonele libere mari pt a se evita fragmentarea);

Ex. : se termina B

In schema MVT trebuie facuta atat gestiunea zonelor ocupate cat si a celor libere. Pentru zonele libere de memorie se pot tine 2 informatii (lungimea si pointer la urmatoarea zona). Se poate pastra o lista inlantuita cu spatiile libere si cele ocupate.

Daca lista spatiilor libere e sortata in ordinea adreselor, se aplica usor first fit. Astfel alocarile se fac la inceput, generand la sfarsitul memoriei aparitia unor zone de memorie mare.

Daca lista e ordonata dupa lungimea zonelor se face usor alocarea best fit, iar la sortarea descrescatoare a listei se face usor worst fit.

Compactarea memoriei

Revenind la exemplul e) prezentat anterior, se presupune ca lucrarea 5 vrea 100K care nu se pot aloca deoarece nu exista nici o zona de 100K libera. Solutia in acest caz este realizarea compactarii memoriei, adica mutarea tuturor lucrarilor catre adrese mici astfel incat la sfarsitul memoriei sa se obtina o zona libera mare.

Solutia de mai sus este ineficienta deoarece se pierde f mult timp, in timpul mutarii nimeni nu mai ruleaza. O solutie mai eficienta este prezentata in cazul (b) in care este suficienta mutarea unui singur bloc, dar apar complicatii la lucrul cu pointeri. Se poate insa folosi swappingul, ducand pe disc 1,2 lucrari: apare spatiu iber.

Exista situtii in care unele programe au tendinra de a-si mari spatiul de memorie in timpul rularii. Exista mai multe solutii prin care alocarea de spatii sa permita cresterea programelor:

a)     Fiecarui proces, cand i se aloca spatii, primeste un spatiu suplimentar pentru crestere. Procesele 1 si 2 au spatiu liber intre ele. Dupa ocuparea extra-spatiului (ptr proc 1) se poate trece la proc 2 altfel acesta trebuie dus pe disc

b)    Se foloseste o tehnica ce utilizeaza 2 structuri de date care au tendinta de crestere (stiva si heap-ul). Se foloseste spatiul liber prin compensatie: una creste in detrimentul celeilalte:

Tehnici de relocare a programelor

In cazul relocarii dinamice, programul nu se schimba indiferent de locatia la care se incarca in memorie, adica fiecare adresare facuta trebuie sa fie insotita de calculul corect al adresei.

Cand se construieste programul de catre editorul de legaturi, se genereaza adrese de la 0, in realitate programele nu se incarca niciodata de la 0. Toate adresele din program nu sunt absolute ci deplasate fata de inceputul lui. Pentru ca programul sa fie executat trebuie incarcat in memorie (in spatiul 100K-150K, de ex).

In faza de executie, sa presupunem ca se genereaza adresa 4000 (din punct de vedere al procesorului). Maparea spatiului de adrese in memoria fizica se face utilizand registrul de relocare (contine adresa de inceput a programului). Registrul limita impune sa nu se depaseasca spatiu alocat.

O alta tehnica de gestiune a memoriei care incearca sa rezolve fragmentarea este paginarea (transportul containerizat). Spatiul de adrese al programului se imparte in mod transparent pentru utilizator in zone de lungime fixe numite pagini. Spatiul de memorie fizica se imparte in zone de dimensiune fixa egale cu paginile numite blocuri, astfel ca orice pagina se poate incarca in orice bloc. Daca se dispune de un mecanism de mapare (pagina-bloc) atunci se poate distribui orice program in orice memorie (incarc orice pagina in orice loc liber). Din punct de vedere logic, programul e continu, insa fizic e distribuit. Sunt necesare mecanismele hardware care sa realizaza maparea. Procesorul genereaza o adresa efectiva (formata din nr de pagina si deplasament in pagina). Nr de pagina reprezinta un index intr-o tabela de mapare a paginilor.

La intrarea p, registrul contine adresa din memorie a blocului in care e incarcata pagina, astfel:

Algoritmi de inlocuire de pagina

Reprezinta metode de alegere a paginilor care se scot din memorie pt a crea spatiu pentru o alta pagina ce trebuie incarcata in memorie.

Se considera urmatoarele instructiuni dintr-un program:

100 LOADR1, [1124]

104 ADDR1, [2448]

Scriind adresele generate de executia programului: 100, 1124, 104, 2448 si presupunand ca o pagina are 1K adresele vor fi: 0,1,0,2.

Se vor considera ca pagina de inceput este 1 si nu 0: 1,2,1,3.

Se obtine „urma de pagina”=P folosita in compararea algoritmilor.

Ce ne intereseaza la un algoritm: frecventa cu care un program nu isi gaseste pagina necesara.

Daca intr-o urma de pagina se fac adrese succesive la aceeasi pagina, acele pagini trebuie sa fie indepartate: 1 1 1 1 2 1 3 2 4

|P|= dimensiunea multimii de pagini

O coloana in tabelele urmatoare reprezinta situatia la un moment dat a paginilor incarcate in blocurile de memorie. Modificarea continutului coloanelor nu inseamna ca o pagina se muta de la un bloc la altul.

F=nr de erori de pagina

S=nr de succese

frecventele pt F si S sunt:

f=F/|P|  sis=S/|P|, cu s+f=1

Clasificare:

Algoritmi cu valoare teoretica – care da rezultate optime pt ca inlocuiesc pagina care se va utiliza cel mai tarziu in viitor (a)

Cu valoare practica (b)

a)     Fie urma de pagina

P =

1 23 45  6 789 10 1112

|P|=12

b)    Algoritmul FIFO – alege drept victima si se indeparteaza din memorie pagina cea mai veche incarcata

A=FIFO (algoritm folosit)

M= nr de blocuri din memorie

P=urma

F_4FIFO = 10; f₄ =10/12 > f₃

S_4FIFO = 2; s₄ =2/12

LRU-Last recently Used

Alege si inlocuieste pagina care nu s-a mai folosit de cel mai mult timp.

MRU=Most Recently Used

Alege pagina cea mai veche nefolosita

|P|=12

P=

M=3

F₃=10; f3=10/12

M=4

S=4

F=8

Ce se intampla daca se modifica dimensiunea paginii?

Fie o pagina p □ care se sparge in doua p' □ si p' □. Se constata ca micsorand paginile se obtin rezultate mai bune:

F_A=6; f_A=6/6.

Injumatatind paginile obtinem:

F_B=3; f_B=3/6

In cazul metodei dubletilor, nu se scoate din memorie o jumatate de pagina decat daca si cealalta jumatate (daca e incarcata in memorie) e in situatia de a fi evacuata