Cresterea puterii de calcul si a spatiului adreselor la microprocesoarele moderne a condus la extinderea gamei de aplicatii, incluzind cimpuri de tipul sistemelor multiutilizator cu functionare in timp real, pe timpuri rezervate doar calculatoarelor mari sau minicalculatoarelor. Realizarea acestor aplicatii sofisticate nu se poate face lasind gestionarea memoriei in sarcina unui singur programator, fie el foarte bun, asa cum se intimpla in cazul microprocesoarelor de 8 biti. In schimb, se impune realizarea gestionarii automate a resurselor de memorie de catre un sistem de operare adecvat, fapt ce are ca efect o mai buna utilizare a spatiului disponibil.

Ideile ce stau la baza implementarii mecanismelor de gestiune a memoriei nu sint noi, ci sint imprumutate din solutiile folosite in calculatoare mari sau minicalculatoare. Totusi, aceste idei sint noi in lumea microprocesoarelor, fapt ce a determinat descrierea in acest capitol a celor mai frecvent utilizate metode pentru utilizarea eficienta a memoriei, ca si pentru protectia impotriva accesului neautorizat, voit sau eronat.

Utilizarea rationala a memoriei se realizeaza prin luarea in considerare a urmatoarelor :

- exista mai multe tipuri de memorie, cu diverse viteze si costuri pe bit (cum sint cele cu semiconductoare si cele magnetice). In general, capacitatea memoriilor rapide este limitata de cost sau posibilitati tehnologice, in timp ce memoriile ieftine au timpuri lungi de acces;

- intr-un sistem complex, asa cum este calculatorul multipro- gramat functionind prin divizarea timpului,nu este necesar a pastra simultan toate programele in memoria primara, deoarece numai o submultime a acestora este gata de rulare, in timp ce altele pot astepta terminarea unor operatii I/O sau pot fi temporar blocate.

In general este convenabil a considera sistemul de memorie drept constind din mai multe subsisteme, cu capacitati diferite si timpi de acces diferiti. Intr-o astfel de configurare mecanismele de gestiune a memoriei vor distribui informatia intre diversele tipuri de memorie, incercind a pastra datele si programele la care accesul este mai frecvent in memoriile mai rapide, restul informatiilor fiind plasat in memoriile mai lente.

Desigur, alocarea memoriei nu este statica, intrucit, in cele din urma, sistemul va prelucra toate informatiile memorate. Deci, datele si programele vor fi mutate dintr-o zona de memorie in alta. Fluxul acestor informatii poate fi controlat de catre programator, sistemul de operare, hardware sau o combinatie a tuturor acestor factori. Fiecare din ei poate gestiona un anumit subsistem al memoriei, asa cum se va vedea mai tirziu.

4.2. Localitatea programelor

Un exemplu de alocare a informatiei sub comanda explicita a programului este constituit de gestiunea registrelor efectuata de catre un programator in limbajul de asamblare. Registrele CPU reprezinta cea mai rapida forma de memorie din sistem, dar capacitatea lor nu este suficient de mare pentru a memora toate datele manipulate de catre un program. Deci, un programator experimentat foloseste registrele pentru a memora datele la care frecventa de acces este cea mai mare. Mai mult, intrucit multimea acestor variabile se poate schimba pe durata executiei unui program, programatorul va modifica modul de utilizare a registrelor asa incit variabilele care nu mai sint intens utilizate de catre sectiunea urmatoare de cod sa fie mutate inapoi in memoria primara, de unde se aduc in registre cele frecvent apelate.

In cadrul acestui exemplu gestiunea unei zone de memorie unica si rapida se bazeaza pe cunoasterea structurii programului. Deci, o astfel de tehnica nu este adecvata pentru gestionarea memoriei prin mecanisme hardware sau de catre sistemul de operare, pentru ca lor le lipsesc cunostintele despre program. Un numar de experimente si masurari efectuate asupra sistemelor a evidentiat existenta unui principiu, numit principiul localitatii programelor (program locality). El se poate enunta astfel:

- daca la momentul t se face acces la adresa de memorie x, exista o probabilitate ridicata ca, la momentul t+dt,sa se efectueze accesul la adresa de memorie x+dx, unde dt si dx sint valori mici ale lui t si x.

Cu alte cuvinte, principiul arata ca procesul de acces la memorie al unui program in executie se poate diviza in faze. Pe durata fiecarei faze referirile la memorie au loc doar in cadrul unui unic subspatiu al spatiului de memorie disponibil, accesul la memorie fiind concentrat in jurul citorva blocuri contigue de memorie. Doar cind programul se muta de la o faza la alta modelul de acces la memorie devine neuniform, pina la atingerea noii faze, dupa care referirile la memorie se centreaza pe o aglomerare diferita de blocuri.

Mecanismele de gestiune automata a spatiului de memorie pot folosi localitatea programelor pentru a pastra in memoria rapida subspatiul de memorie cu cele mai frecvente accese in cadrul programului curent. Un element esential consta in detectarea tranzitiei intre faze si identificarea locatiilor de memorie utilizate de catre fiecare faza. In cele ce urmeaza se vor ilustra solutiile cele mai des folosite ale acestor probleme.

In final, combinarea gestionarii automate a memoriei cu cea efectuata de catre utilizator presupune oferirea de catre programator a unor informatii privind structura programului, ceea ce permite mecanismului automat sa mute informatiile intre diferitele subsisteme de memorie corespunzator informatiilor furnizate de catre programator.

4.3. Adrese fizice si virtuale

Organizarea memoriei in citeva subsisteme diferite are implicatii importante asupra adresarii. Intrucit alocarea memoriei este dinamica, este mai bine ca programul (deci CPU) sa nu utilizeze direct adresele efective ale locatiilor de memorie in care sint stocate informatiile la care se face accesul, intrucit ar fi necesara relocarea programului ori de cite ori un subset al sau este mutat in cadrul memoriei. Solutia adoptata in mod curent consta in a aloca programului propriul sau spatiu de adresare, care difera de spatiul efectiv de adresare implementat in cadrul sistemului. In consecinta este necesara transformarea, la momentul rularii, a adresei in program (adresa virtuala) in adresa de memorie (adresa fizica), transformare ce utilizeaza un suport hardware adecvat. Intrucit spatiile de adresare virtual si fizic sint independente, este normal ca si dimensiunile lor sa difere. Deci, spatiul de memorie virtuala poate fi mai mare decit dimensiunea memoriei primare, in care caz sectiuni de program pot fi memorate pe dispozitivele de memorare de masa. Totusi, localitatea programului permite ca aceste programe sa ruleze eficient daca in memoria program se stocheaza sectiuni adecvate ale programului.

Este posibila existenta unor functii diferite de transformare a adreselor virtuale in adrese fizice pentru un anumit program, deci pot exista multiple spatii virtuale de adresare. Aceasta solutie complica operatia de transformare, dar evita conflicte de adresare cu alte programe, care ar putea aparea in cazul unicitatii spatiului virtual.

4.4. Ierarhizarea memoriei

Principiile de gestiune a memoriei evidentiate in paragraful 4.1. conduc la organizarea ierarhizata a diferitelor subsisteme de memorie. La virful ierarhiei se gaseste memoria cea mai mica si cea mai rapida, in timp ce baza este constituita din memoria cea mai lenta si cu cel mai mare volum. In general transferul de date are loc doar intre niveluri adiacente ale ierarhiei.

Intrucit organizarea memoriei bazata pe localitatea programelor ofera valori bune pentru raportul cost/performanta, ideea este larg folosita in noile microprocesoare. Trebuie remarcat ca ierarhia memoriei pentru aceste sisteme are un numar mai mare de niveluri decit in modelele anterioare.

Fig. 4.1. indica o organizare posibila a ierarhizarii memoriei pentru un sistem bazat pe un microprocesor evoluat. Aceasta organizare a memoriei include nivelurile cele mai obisnuite. Nu orice sistem contine nivelurile din figura, desi ar fi posibil.

Principiul localitatii programelor este valabil pentru orice tip de referire la memorie. Totusi, diferitele niveluri ale ierarhiei necesita modalitati diferite de manipulare a instructiunilor, datelor si informatiilor in scopul gestionarii memoriei, ceea ce rezulta si din figura 4.1.

Este important de remarcat ca, in timp ce termenul "adresa virtuala " poate fi utilizat pentru a indica adresa manipulata de catre programele utilizatorului, notiunea "adresa fizica" este folosita pentru a indica zone de memorie de masa rapida in care este memorata o parte a programului ce se executa, indiferent de celelalte niveluri ale ierarhizarii memoriei.

Registre

Registrele interne 121d34b ale CPU reprezinta cea mai rapida si cea mai mica memorie din sistem, deoarece ele sint direct conectate la diversele subunitati de prelucrare din cadrul CPU, cum sint unitatea aritmetica si logica (ALU), decodificatorul instructiunii sau unitatea aritmetica de evaluare a adresei.

Registrele de uz general constituie nivelul 0 al memoriei pentru date (incluzind adresele programului) si registrul instructiunii este nivelul 0 al memoriei pentru cod. Caracteristica noua a unor procesoare de 16 si 32 biti, cum este iAPX286 (ce se va discuta in urmatorul capitol), consta in faptul ca ele dispun de citeva registre dedicate pastrarii de informatii temporare necesare gestiunii memoriei. Aceste registre se pot afla, partial, sub controlul programului (privilegiat) dar, in general, sint gestionate de catre CPU.

4.4.2. Memorie cache pe circuit

Cresterea continua a vitezei de prelucrare a noilor microprocesoare necesita si sisteme mai rapide de memorie. Intrucit timpul de acces al circuitelor de memorie descreste in mod constant, timpul total de raspuns este afectat intr-o masura importanta de intirzierile de interfatare, incluzind penalizarea de timp a transferului prin frontierele circuitului.

Avind in vedere aceste conditii tehnologice, devine rationala introducerea unui nou nivel de ierarhizare compus din memoria care nu este direct conectata la subunitatile de prelucrare, dar implementata pe aceeasi placheta de siliciu ca si CPU. Desi acest nivel, nivelul 1 al memoriei, este mai lent decit registrele, el necesita unele circuite de interfata; totusi ea este mai rapida decit memoria realizata in exteriorul circuitului. La acest nivel inca persista distinctia intre date, cod si informatii de gestiune a memoriei. Memoria cache pe circuit destinata programului este, uneori, organizata ca stivele de tip FIFO, al carui virf este constituit de registrul instructiunii. Aceasta organizare simpla devine posibila ca urmare a modului aproape liniar al extragerii instructiunilor, cu perturbari create de executia instructiunilor de salt. Deciexista o probabilitate ridicata ca urmatorul cuvint de cod ce trebuie sa fie extras sa se afle la adresa urmatoare.

Instructiunile de salt videaza stiva FIFO, deoarece distrug traseul liniar prin spatiul de adresare. Deci, pentru un scurt timp, efectul favorabil al memoriei cache pe circuit dispare, ca urmare a necesitatii de a aduce noi cuvinte de cod din memoria externa. Dar instructiunile necesita un anumit timp pentru executia lor in interiorul CPU, ceea ce permite unitatii de gestiune a tamponului de memorie sa umple rapid stiva FIFO mai rapid decit are loc vidarea ei de catre CPU, care extrage instructiuni. Deci, dupa executia unei instructiuni de salt, sirul de asteptare in interiorul circuitului a instructiunilor se reface.

Poate aparea un conflict intre CPU, care trebuie sa execute un ciclu de citire/inscriere a memoriei externe, si unitatea de gestiune a stivei FIFO, care trebuie sa execute un ciclu de citire din memorie pentru a completa sirul de instructiuni. In astfel de situatii ciclul necesar prelucrarii de date este prioritar.

Referirile necesare accesului la date se fac dupa un model mai putin predictibil decit cel pentru acces la cod, motiv pentru care memoria cache pe circuit este organizata ca o memorie cu acces aleator, compusa dintr-o parte de date si o alta de eticheta (tag), asa cum se vede in figura 4.2. In general, atit componenta DATA, cit si cea TAG, au acelasi numar de cuvinte. DATA pastreaza valorile datelor, iar TAG pastreaza informatia corespunzatoare despre adresa CPU utilizata pentru acces la date. Cind CPU emite o adresa, unitatea de comanda a memoriei cache efectueaza operatiile din figura 4.3. Acest tip de organizare cache, folosita pentru memoria cache pe circuit, este numit "complet asociativ", deoarece memoria TAG este adresata prin continutul sau.

Adresa CPU

Fig. 4.2. Organizarea generala a memoriei cache

Implementarea memoriei cache pe circuit indica un numar de probleme arhitecturale. In primul rind, memoria TAG este mare comparativ cu memoria DATA, deci se consuma o mare arie de siliciu pentru gestiunea memoriei. In al doilea rind unele studii efectuate prin simulare [17] au aratat ca introducerea memoriei cache pe circuit creste, in loc sa descreasca, viteza ceruta pentru transferul prin frontiera circuitului. Exista un mic numar de implementari cache pe circuit, cum este cazul microprocesorului Zilog Z8000 [18]. Memoriile cache pe circuit, in adevaratul inteles al notiunii, sint, in prezent, limitate la instructiuni, intrucit ele nu ridica mari probleme si reprezinta o imbunatatire fata de sirurile de instructiuni, fiind posibila memorarea intregului cod pentru o mica bucla in memoria circuitului microprocesorului, ceea ce elimina necesitatea reincarcarii codului buclei la fiecare noua executie, asa cum este cazul sirului de instructiuni. Pe de alta parte, costul implementarii sirului de instructiuni este mai mic decit cel pentru implementarea mecanismului cache pentru instructiuni.

In fine, tehnica de tip cache este folosita si pentru a memora informatiile cu cea mai ridicata fracventa de utilizare, destinate gestiunii memoriei in acelasi circuit cu CPU sau intr-un circuit destinat special gestiunii memoriei (memory management

Fig. 4.3. Operarea unitatii de comanda a memoriei cache (pe chip)

unit - MMU). O astfel de unica memorie cache este comandata pe baza principiului LRU (least recently used - cea mai veche informatie folosita), care inlocuieste cea mai veche informatie folosita cu noile date cerute de catre CPU si copiate din memoria externa acesteia. Nu toate mecanismele de comanda a memoriei cache pe circuit sint necontrolabile prin program, dar ele sint implementate prin mijloace hardware si prezenta lor tinde sa fie transparenta fata de programator.

4.4.3. Memorii cache pe placheta

Aceleasi motive care justifica introducerea de memorii cache pe circuit recomanda realizarea lor pe aceeasi placheta cu a CPU. Intr-adevar, intirzierea introdusa de circuitele de interfatare, ca si de transmisia si regimurile tranzitorii ale informatiilor pe magistrala sistemului necesita, adesea, introducerea unei stari de asteptare (wait state), mai ales pentru microprocesoa- rele foarte rapide, atunci cind se adreseaza memoriei care nu se afla pe aceeasi placheta. Mai mult, desi memoria cache pe placheta este realizata utilizind circuite cu semiconductoare ca memorie pe urmatorul nivel de ierarhizare (memorie primara), exista intotdeauna memorii cu semiconductoare avind diferite viteze. Deci, memoria cache pe aceeasi placheta permite obtinerea de timpi de acces la sistemul de memorie apropiati de cei oferiti de memoria cache de mare viteza, dar la un pret apropiat de cel al memoriei mai mari si mai lente (memorie primara).

In sistemele multiprocesor apare un motiv suplimentar de introducere a memoriei cache. In acest sistem, concurenta intre diferitele CPU pentru accesul la memorie conduce la intirzieri care au ca efect cresterea timpului mediu de acces la memorie.

Gestiunea memoriei de tip cache presupune existenta unui anumit tip de hardware. Organizarea din fig. 4.2. ramine valabila si pentru memoria cache pe aceeasi placheta cu CPU, dar, intrucit memoria cache in acest caz este mai mare, sint necesare alte mecanisme de gestionare pentru a mentine diversiunea memoriei TAG cit mai mica posibila.

S-au studiat cerintele pentru asemenea mecanisme suplimentare. Pentru ilustrarea lor este necesara introducerea urmatorilor parametri:

- dimensiunea cache: dimensiunea memoriei DATA, exprimata in numar de unitati adresabile de catre CPU;

- dimensiunea blocului: dimensiunea celei mai mici unitati de memorie care poate fi manipulata de mecanismul de gestiune cache. Fiecare acces la alocatie de memorie in cadrul unui bloc este privit ca o referinta la bloc. Mai mult,orice transfer in conjunctie cu memoria primara se face printr-un bloc intreg (in general, dimensiunea blocului este o putere a lui 2);

- dimensiunea multimii (set size): numarul de locuri diferite in memoria DATA unde organizarea cache permite stocarea oricarui bloc citit din memoria primara (si dimensiunea multimii este, in general, o putere a lui 2).

Fig. 4.4 indica un mod posibil de a converti adresele emise de catre CPU in adrese ale memoriei DATA. Fie n numarul de biti de adresa a CPU si k < n numarul de biti necesari pentru a adresa memoria DATA.

Dindu-se dimensiunea blocului B=2^b, cei mai putini semnificativi b biti de adresa ai CPU sint copiati in adresa memoriei DATA, deoarece offsetul in cadrul blocului nu este luat in considerare de catre mecanismul de conversie a adreselor.

Fig. 4.4. Mecanismul de conversie a adresei pentru memoria cache cu S=2^s

Daca se noteaza cu S dimensiunea multimii, adresa CPU poate fi transformata in una din cele S adrese folosite pentru memoria DATA. Deci bitii s ai adresei cache sint obtinuti prin transformarea prin intermediul memoriei TAG, in timp ce bitii ramasi x = k-s-b sint determinati in mod unic din adresa CPU, apoi sint copiati. Intrucit bitii x, ilustrati in fig. 4.4., determina setul de blocuri posibile in cadrul memoriei de date, iar localizarea exacta in cadrul multimii nu este supusa la restrictiii din partea altor biti de adresa, transformarea celor mai semnificativi n-b-x biti ai adresei emise de catre CPU in cei mai semnificativi s biti ai adresei de memorie cache ar trebui efectuata, in mod ideal, de un set de memorii asociative (cite una pentru fiecare set).

O alta solutie este cea din figura 4.5., unde se folosesc doar memorii RAM. In acest caz, numarul de biti utilizati pentru memoria TAG sint dati de

2^k-b * (n-k+s),

care realizeaza corespondenta intre dimensiunea memoriei cache (2^k), dimensiunea blocului (2^b), dimensiunea multimii (2^s) si dimensiunea spatiului adreselor CPU (2ⁿ). Prin modificarea valorii lui s se obtin urmatoarele trei organizari clasice:

a) s=0 (organizarea indexata): fiecare bloc din memoria primara este transformat intr-un unic bloc al memoriei cache;

b)0 < s < h-b (organizarea partial asociativa de seturi): orice bloc din memoria primara poate fi transformat intr-un numar limitat de seturi ale blocurilor memoriei cache;

Fig. 4.5 Implementarea memoriei TAG pentru scheme de tip set cache, fara a utiliza memorie asociativa

c)s = h-b (organizarea complet asociativa): orice bloc al memoriei primare poate fi transformat in orice bloc al memoriei cache.

Din relatia data mai sus rezulta ca valorile mari ale lui s conduc la dimensiuni mari ale memoriei TAG. Pe de alta parte, unele rezultate experimentale [19] au evidentiat in mod clar ca, prin cresterea dimensiunii setului, creste probabilitatea de acces in memoria cache. In acelasi timp, aceleasi studii au aratat ca dimensiunea de 2 sau 4 a setului conduce la performante foarte apropiate de cele ale organizarii complet asociative.

Din cele de mai sus decurge preferinta proiectantului pentru memorii cu organizare partial asociativa, cu o dimensiune mica a setului. De exemplu, VAX 11/780 are o memorie cache de 8 kocteti cu dimensiunea setului 2 si dimensiunea blocului 8.

Realizari de memorie cache - 1

4.4.4. Memoria primara

Memoria primara constituie cel mai mare subsistem de memorie adresabil direct de catre CPU. Toate programele ce se ruleaza (cod si date) trebuie memorate in memoria primara, ca si informatiile necesare gestionarii memoriei. Totusi, nu toate programele sint gata de a rula in paralel si, chiar cind un program este executat, el foloseste doar un subset al spatiului sau virtual de adresare pe durata unei anumite faze.

Tehnicile de gestiune a continutului memoriei primare necesita un anumit suport hardware, dar algoritmii sint implementati prin software. De aici decurge o varietate de solutii posibile.

Trebuie remarcat ca memoria primara si registrele sint doua niveluri ierarhice prezente intotdeauna intr-un sistem, in timp ce celelalte niveluri s-ar putea sa lipseasca.

4.4.5.Memoria de masa

Informatia care nu este imediat necesara CPU (programe care nu sint gata de rulare sau subspatii de adresare care nu sint necesare in faza curenta) este memorata in dispozitive cu mediu magnetic de stocare, care ofera un mare volum de memorare la costuri unitare mici, dar cu timpi de acces cu cel putin trei ordine de marime mai mari decit cei ai memoriei primare.

4.4.6. Consideratii privind costul si performanta

Succesul organizarii ierarhizate a memoriei este datorat bunelor performante si costuri implicate, deoarece costul pe bit este apropiat de cel al celei mai lente memorii din sistem, in timp ce performantele obtinute sint comparabile cu cele ale celor mai rapide memorii din ierarhie.

In tabelul 4.1. sint indicate caracteristicile memoriilor folosite la diferitele niveluri ale ierarhiei; ele permit evaluarea costurilor si performantelor unui sistem de memorie. Costul pe bit de memorie este dat de formula:

unde m_i reprezinta dimensiunea nivelului i al ierarhiei, iar c_i este costul corespunzator pe bit. Din acelasi tabel se poate vedea ca dimensiunea intregii memorii este dominata de cea a novelurilor celor mai lente, fapt ce justifica afirmatia privind costul global pe bit.

Tabelul 4.1. Caracteristicile diferitelor niveluri ale unui sistem ierarhic de memorie

NUME	DIMENSIUNE	TIMP ACCES

Registre		0.1 ns
Cache pe circuit	16 kB - 256 kB	1 - 2 ns
Cache pe placheta	265 kB - 1 MB	8 - 10 ns
Memorie principala	128 MB - 1 GB	50 - 70 ns
Memorie secundara	8 GB - 128 GB	10 ms

Performantele depind de localizarea adresei memoriei la care se face acces in cadrul ierarhiei. Intrucit fiecare nivel are proprii timpi de acces si de transfer, timpul de acces la memorie poate fi evaluat doar ca valoare medie, sau probabila, folosind urmatoarea expresie:

Prin p_i s-a notat probabilitatea ca adresa de acces sa se afle in nivelul i, iar T_i este timpul de acces la datele implicate. Nivelurile ridicate sint gestionate la nivel de bloc, indeosebi pentru memoriile pe medii magnetice. De aceea valoarea lui T_i trebuie sa ia in consideratie timpul necesar pentru transferul intregului bloc.

Valoarea lui T depinde in masura esentiala de probabilitatile p_i. Ar fi de dorit ca p_i sa fie cu atit mai mare cu cit i este mai mic. Experienta arata ca valorile lui T_i sint apropiate de timpul de acces pentru memoriile cache pe aceeasi placheta cu CPU. Pentru memoriile cache pe circuit nu se dispune de date concludente, deoarece numarul de microprocesoare folosind aceasta structura este foarte mic.

4.4.7. Ierarhizarea memoriei in sistemele multiprocesor.

Organizarea ierarhizata a memoriei are mai multe avantaje, dar poate genera probleme in sistemele multiprocesor, deoarece structura ierarhizata intra in conflict cu necesitatea de a efectua, in mod corect, multiple operatii de citire/inscriere. Problema majora in utilizarea unui sistem ierarhizat de memorie in sisteme mutliprocesor consta in existenta mai multor copii ale acelorasi date in mai multe niveluri, fapt ce impune acualizarea tuturor acestor copii pentru a pastra integritatea datelor.

Pentru mai multa claritate se considera un exemplu. Se presupune ca un sistem este compus din mai multe plachete cu microprocesoare si cu memorie proprie, fiecare placheta fiind conectata, prin intermediul unei magistrale multiprocesor la o memorie comuna (fig. 4.6.). Memoria are o structura ierarhica ale caror niveluri cu numar mic (0,1,2) sint implementate in memoria locala, in timp ce nivelurile cu numar mare (3 si 4) sint realizate in memoria comuna. S-au folosit aceleasi numere de niveluri ca in fig. 4.1.

Daca programul rulat de procesorul i realizeaza accesul la locatia x, continutul acesteia este copiat in memoria cache proprie la adresa x'; apoi are loc modificarea continutului lui x', asa ca valorile continute in x si x' nu mai sint identice. Daca un al doilea program, rulat de procesorul j, are nevoie de continutul aceleiasi locatii x, el va folosi o valoare diferita de cea curent utilizata in procesorul i, in pofida faptului ca este vorba de aceeasi adresa virtuala.

Solutia acestui tip de probleme depinde de ierarhizarea nivelurilor implicate. Problema memoriei cache proprii a fost intens studiata [20],[21],[22]. De asemenea ramine deschisa aceeasi problema pentru memoria cache pe circuit. Ca urmare, introducerea tehnicii de tip cache la microprocesoarele evoluate intirzie, folosindu-se doar pentru operatia de tip read-only, adica pentru operatii implicind programe.

Fig. 4.6. Exemplu de organizare ierarhizata a memoriei intr-un sistem multiprocesor

4.5. Mecanisme simple de gestiune

In acest subcapitol sint comentate tehnici simple de gestiune a memoriei, care nu necesita suport hardware, dar ofera un grad redus de flexibilitate pentru gestionarea spatiului aflat la dispozitia utilizatorului. Aceste metode ofera exemple de gestiune sub controlul deplin sau partial al programului si ilustreaza avantajele altor tehnici, devenite posibile in urma disponibilitatii microprocesoarelor moderne.

4.5.1. Memorii cu bancuri suplimentare

Aceasta tehnica este specifica sistemelor cu microprocesoare din perioada de inceput, ea fiind conceputa pentru extinderea memoriei adresate dincolo de limitele impuse de numarul de linii de adresa (de regula 16) ale microprocesoarelor de 8 biti. Ideea de baza este aceea a extinde cimpul de adrese prin adaugarea de biti suplimentari. Ca urmare a limitarilor CPU, acesti biti suplimentari trebuie produsi de catre microprocesor intr-o operatie separata fata de cea de adresare normala.

In figura 4.7. se indica organizarea hardware a memoriei. Selectarea unuia din mai multele bancuri de memorie se face pe baza continutului unui unic registru R, care contine bitii cei mai semnificativi ai adresei, partea cea mai putin semnificativa a acesteia fiind produsa de catre CPU. Dupa inscrierea registrului R cu informatia necesara selectarii unui anumit banc, accesul la datele si codul din acesta se face doar cu ajutorul submultimii de adrese emise de catre CPU. Cind apare necesitatea referirii la o locatie dintr-un alt banc are loc modificarea continutului lui R, ceea ce rezulta in comutarea bancurilor.

Fig. 4.7. Memorie sub forma de bancuri comutabile.

Tehnica descrisa nu necesita un suport hardware special, toate functiile de gestiune fiind efectuate de catre programator. Aceste operatii sint:

- partitionarea datelor si codului programului astfel incit fiecarecomponenta sa incapa intr-un alt banc, iar comutarea intre bancuri sa nu fie prea frecventa;

- scrierea programelor prin considerarea operatiilor posibile de comutare a bancurilor pentru accesul la operanzi, scriere care necesita inserarea de cod necesar modificarii continutului registrului exterior R.

Trebuie notat ca a doua din operatiile mai sus descrise poate fi efectuata daca programul este scris in limbaj de asamblare; programele in limbaje de nivel inalt necesita compilatoare si editoare de legaturi speciale care sa poata face fata problemei comutarii bancurilor. Astfel de instrumente de dezvoltare a programelor nu sint disponibile in mod curent, fapt ce complica elaborarea programelor pentru sistemele ce adopta solutia mentionata.

Un alt dezavantaj al metodei consta in alocarea statica, rezultat al necesitatii gestionarii prin program a datelor si codului. In felul acesta se suprima orice posibilitate de realocare automata, cu scopul folosirii mai eficiente atunci cind starea sistemului necesita reasignarea memoriei.

4.5.2. Overlay

A doua tehnica discutata a fost larg utilizata in minicalculatoare, indeosebi in modelele PDP 11 ale firmei DEC la care nu se folosea paginarea la cerere. Ea mai este utilizata pentru rularea de programe mari pe microcalculatoare personale. Tehnica presupune ca programul este partial rezident in memoria principala, restul fiind memorat pe disc. Cind o parte a programului stocat pe disc devine necesara unitatii centrale, aceasta parte este adusa in memoria principala in locul altei parti a programului, care nu este necesara la acel moment. Intrucit diferitele subspatii ale spatiului programului se pot incarca in aceeasi zona de memorie, apare suprapunerea acestor subspatii; de aici decurge si numele tehnicii de gestiune a memoriei: overlay (suprapunere).

Este esentiala evitarea situatiilor cind doua parti distincte si care se pot suprapune ale programului sa fie simultan necesare in memorie pentru executarea programului. Singurul care poate face aranjamentele cerute de tehnica overlay este programatorul, pentru ca el cunoaste modul de evolutie a programului si care anume sectiuni ale lui trebuie sa fie rezidente in memorie la un anumit moment de timp.

Aceasta partitionare se poate efectua prin structurarea intregului program intr-un arbore de module, pentru care toate modulele de pe un nivel se pot suprapune. Arborele de suprapunere se poate construi urmarind arborele apelarii procedurilor. Radacina este reprezentata de programul principal, care este permanent rezident in memoria principala, iar toate procedurile apelate direct de catre programul principal se pot suprapune, pentru ca ele sint apelate una cite una, nici una din ele ne necesitind prezenta alteia.

Din nefericire, un numar de motive fac realizarea arborelui de suprapunere o problema netriviala. In primul rind, modulele superpozabile trebuie sa aiba, aproximativ, aceeasi dimensiune,ca sa poata fi continute in acelasi spatiu de memorie. Pentru exemplificare se poate considera fig. 4.8. O a doua problema este generata de minimizarea operatiilor de instalare in si evacuarea din memoria principala a modulelor (swapping). Cu cit numarul acestor operatii este mai mare, cu atit eficienta de ansamblu este mai mica. Aceasta cerinta conduce la recomandarea realizarii de module de mari dimensiuni. Pe de alta parte, gestionarea memoriei se face cu mai buna eficienta daca modulele superpozabile sint de mici dimensiuni. Deci, la realizarea arborelui de suprapuneri, programatorul trebuie sa realizeze compromisul intre cerintele privind memoria si cele referitoare la eficienta executiei.

Fig. 4.8. Exemplu de alocare a memoriei in tehnica overlay.

a) arbore de suprapuneri; b) alocarea initiala a memoriei; c) alocarea dupa apelarea modulului E; d) alocarea dupa apelarea modulului C; e)alocarea dupa apelarea modulului F; f) alocarea dupa apelarea modulului G.

O data solutionate problemele referitoare la elaborarea arborelui de suprapuneri, programatorul se poate baza pe instrumente software de dezvoltare necesare elaborarii taskului final, intrucit exista editoare de legaturi care se preteaza utilizarii tehnicii overlay. La executie, cu program construit conform tehnicii mentionate efectueaza apelari ale sistemului de operare ori de cite ori este necesar a folosi o procedura care, la acel moment, nu este rezidenta in memoria principala. Se poate vedea ca implementarea tehnicii overlay nu necesita mijloace hardware speciale, cu exceptia unor unitati rapide de disc, care sa permita incarcarea cu mare viteza in memoria principala a sectiunii cerute a programului. Adresele de program generate de compilatoare nu depind de structura arborelui de suprapunere, intrucit apelurile la procedurile externe sint solutionate de catre editorul de legaturi, fie in modul normal, fie prin inserarea de apeluri catre sistemul de operare.

Tehnica overlay este un exemplu tipic pentru metodele care combina cunostintele programatorului despre comportarea programului cu comutarea automata a sectiunilor de program, cu scopul implementarii mecanismului de gestiune a memoriei. Principalul dezavantaj al metodei este legat de pregatirea arborelui de suprapuneri si necesitatea de a incarca in memorie un intreg modul, chiar daca doar o parte a lui este necesara. Ca efect se pot obtine performante mai slabe decit cele oferite de alte tehnici de gestiune, complet automate. Pe de alta parte, este perfect posibila rularea unor programe cu dimensiuni superiore celei a memoriei fizice disponibile.

4.6. Swapping

Intr-o masina functionind in regim de multiprogramare este posibila executia concurenta a mai multor programe. De aceea, este salutara ideea de a pastra in memoria principala doar programele care sint gata de rulare.

Conform politicii de swapping (comutare intre memoria principala si cea secundara), un program care asteapta terminarea unei operatii I/O (care poate dura citeva milisecunde),este evacuat din memorie (swapped out). Cind el devine din nou gata de rulare, sistemul incearca sa gaseasca un spatiu adecvat in memoria primara, in care sa incarce programul in discutie. Daca nu exista spatiul disponibil, programul este inscris intr-o lista de asteptare, in vederea sosirii momentului la care se creeaza spatiul necesar de memorie. La fiecare evacuare de program in memoria secundara, rutinele de implementare a mecanismului de gestiune a memoriei incearca sa incarce in memoria principala un program din lista de asteptare.

Conversia adresei virtuale in adresa fizica de memorie principala se face prin adunarea adresei virtuale la adresa de inceput a zonei de memorie in care s-a efectuat incarcarea. Deoarece aceasta operatie de relocare trebuie efectuata la fiecare ciclu de memorie, apare necesitatea de hardware specializat, care sa efectueze relocarea intr-un mod care sa nu conduca la lungirea timpului de executie drept consecinta a aplicarii tehnicii swapping. Acest hardware specializat, implementat adesea intr-un singur circuit, se numeste unitate de gestiune a memoriei (MMU-memory management unit) si poate fi considerat drept o extensie a CPU, care efectueaza cu mai mare viteza functii asociate gestiunii memoriei. Fiecare tehnica de gestiune a memoriei necesita propriul tip de MMU. Totusi, sistemele cu multiprogramare au intotdeauna nevoie de o astfel de unitate hardware.

Ori de cite ori un program este lansat sau relansat in executie, adresa de baza a zonei dee memorie in care se afla stocat un program este incarcata intr-un registru special al MMU. Un alt registru contine dimensiunea programului, fapt ce permite ca, pe durata executiei acestuia, sa se poata detecta tentativa de adresare intr-un spatiu exterior celui al programului curent. Acest test simplu permite protejarea fiecarui program impotriva unor actiuni periculoase - involuntare sau nu - efectuate de catre alte programe.

Fig. 4.9 Situatie in care tehnica swapping nu foloseste in mod optim memoria

Tehnica swapping de gestiune a memoriei este simplu de implementat, dar are si dezavantaje ce nu se pot neglija. In situatia din fig. 4.9. programul PROG2 trebuie evacuat, eliberind spatiul de memorie pe care il ocupa. Totusi, actiunea nu creeaza suficient spatiu pentru a incarca in memorie nici unul din programele aflate in lista de asteptare, chiar daca volumul total de memorie disponibila (1000 + 2000 = 3000 cuvinte) ar permite incarcarea lui PROG7. Tehnica swapping considera un program drept un bloc a carui incarcare se poate face doar intr-o zona de locatii contigue de memorie, deci ea nu permite folosirea micilor fragmente de spatii libere de memorie, spatii a caror dimensiune totala devine importanta dupa un numar de operatii swapping. Acest efect este numit fragmentarea memoriei si urmarile sale se pot atenua,inlocuind tehnica swapping cu cea de segmentare.

4.7. Segmentarea

Procesul de segmentare presupune spargerea programelor in mai multe segmente pentru care nu este necesara stocarea in zone adiacente de memorie, desi fiecare din ele trebuie incarcat intr-un bloc compact de memorie. Acest lucru diminueaza efectele fenomenului de fragmentare, devenind posibila utilizarea si a unor zone de memorie de mai mici dimensiuni.

Segmentele corespund unor submultimi logice ale programului. Se poate considera, spre exemplificare, segmentul de cod si segmentul de date. Segmentarea poate fi mai pronuntata decit atit, putind exista mici segmente compuse din una sau mai multe rutine sau din una sau mai multe structuri de date.

Mecanismul de conversie a adreselor implicat de tehnica de segmentare este complex, deoarece sistemul de operare trebuie sa dispuna si sa intretina o tabela cu descriptorii segmentelor pentru fiecare program. Fiecare element al acestei tabele este compus din:

- adresa baza;

- dimensiunea segmentului;

- atribute (folosite pentru a verifica daca accesul efectuat este corect).

In figura 4.10. se prezinta algoritmul utilizat pentru conversia adreselor. Identificarea segmentului este facilitata de existenta unei submultimi de adrese virtuale. Descriptorul acestuia este extras din tabela de descriptori ai segmentelor. Dupa aceasta, conversia de adresa se face similar cazului tehnicii swapping.

Relocarea este critica din punctul de vedere al performantei sistemului, intrucit ea trebuie efectuata la fiecare ciclu memorie. Deci, daca tabela descriptorilor segmentului ar fi pastrata in memoria principala, apare necesitatea unui ciclu suplimentar de acces la memorie, ceea ce dubleaza timpul cerut de efectuarea unui ciclu memorie.

Depasirea acestei dificultati se face stocind tabela descriptorilor segmentelor intr-o, mica dar foarte rapida, memorie RAM cu care este prevazuta MMU. Dimensiunea limitata a acestei memorii speciale necesita folosirea tehnicii de swapping intre aceasta si memoria principala a sistemului.

Fig. 4.10. Schema de conversie a adresarii ceruta de segmentare. Mecanismul de segmentare

Un alt tip de problema apare in cazul in care numarul de segmente depaseste cantitatea ce poate fi stocata in memoria RAM a MMU. In acest caz, memoria rapida din cadrul MMU se poate utiliza ca memorie cache, in care se pastreaza cei mai recent utilizati descriptori de segment. Cind se initializeaza procesul de conversie a adreselor, MMU cauta in memoria sa interna descriptorul de segment; daca el nu este gasit, descriptorul este citit din memoria primara si copiat in memoria interna. Principiul localitatii programelor indica o probabilitate ridicata ca descriptorul sa se afle in memoria interna a MMU, cel de al doilea ciclu de memorie este doar arareori necesar , deci nu influenteaza intr-un mod important performanta de ansamblu.

Un alt punct important, referitor la intirzierea de relocare, este viteza cu care se face adunarea indicata in partea de jos a fig. 4.10. Adresa fizica de m biti se obtine prin adunarea portiunii de k biti (k =< m), adresa baza, cu offsetul de h biti (h =< m). h determina dimensiunea maxima a segmentului, intrucit nu este posibil, intr-un segment dat, sa se adreseze o informatie cu un offset mai mare decit 2^h-1. Cei mai semnificativi m-k biti nu sint adunati, de fapt, ci doar copiati din adresa virtuala in adresa fizica, asa ca adunarea are loc doar pentru k biti (daca h+k > m). Deci, cu cit numarul k este mai mare,cu atit intirzierea provocata de adunare creste, ceea ce recomanda utilizarea de valori mici pentru k. Pe de alta parte , adresa baza permite fixarea unui numar de 2^m-k frontiere de segment, asa ca valori mici ale lui k vor augmenta procesul de fragmentare. Valorile tipice pentru situatii practice ale diferentei m-k sint, adesea, intre 4 si 8.

4.7.1. Memorie virtuala segmentata

Cind s-a discutat despre localitatea programelor s-a aratat ca executia programelor evolueaza printr-o serie de faze, iar spatiul de adresare la care se face acces in cadrul unei faze este mai mic decit intregul spatiu de adresare al programului. Daca segmentele la care se face acces in cadrul unei faze sint stocate in memoria primara, programul este executat aproape la fel de repede ca in cazul in care toate segmentele sale s-ar gasi in memoria primara, deoarece -practic- toate operatiile de acces au loc la segmente existente in aceasta. Cind se genereaza o referire la un segment absent, el este adus in memoria principala, inlocuind, eventual, alte segmente continute de memoria amintita.

Implementarea mecanismului presupune ca MMU sa verifice prezenta segmentului adresat, ceea ce presupune testarea unui anumit bit in descriptorul segmentului: acest bit este 1 cind segmentul este incarcat si zero cind el este evacuat din memoria primara. Evacuarea se face mai rapid daca segmentul nu a fost modificat de la incarcarea in memorie, deoarece nu mai este necesara copierea sa in memoria de masa (de regula, acest lucru esteadevarat in cazul segmentelor de program). Acesta este motivul pentru care fiecare descriptor de segment are un fanion indicind starea de modificat / nemodificat a segmentului in discutie. Initial, fanionul are valoarea 0 si este inscris cu 1 la fiecare operatie de inscriere a unei locatii din codul segmentului.

O alta caracteristica importanta, chiar esentiala, pentru arhitectura hardware a unui sistem folosind tehnici de segmentare este data de posibilitatea intreruperii de catre CPU a executiei in mijlocul unei instructiuni si de reluare a instructiunii exact de la punctul la care a survenit intreruperea. In aceste cazuri mecanismele clasice pentru intreruperi si capcane nu mai sint necesare, deoarece ele sint activate doar la sfirsitul instructiunii, asa ca ele nu pot fi utilizate in tratarea unor defecte ale segmentelor , defecte care pot aparea oricind pe durata desfasurarii unei instructiuni. Instructiunea nu poate fi terminata daca a aparut un defect de segment , deoarece executia ei ar conduce la o eroare ireparabila.

Desi ultima varianta de tehnica de segmentare are mai multe avantaje (cum sint cele legate de posibilitatea de rulare a programelor al caror spatiu de adresare este mai mare decit cel al memoriei fizice disponibile), ea are si o serie de neajunsuri. Cel mai important este legat de dimensiunile neuniforme ale segmentelor, fapt ce complica gestionarea spatiului de memorie, deoarece, cind se pune problema incarcarii in memoria primara a unui segment de program, s-ar putea sa nu existe spatiul necesar, intrucit segmentul evacuat avea dimensiune mai mica, deci memoria eliberata este insuficienta. Rezulta fie necesitatea unor algoritmi complecsi de inlocuire a segmentelor,fie mentinerea permanenta a unui spatiu neutilizat de memorie. Una din tehnicile de rezolvare a acestei probleme este paginarea, care divizeaza spatiul programului in submultimi de aceleasi dimensiuni.

4.8. Paginarea

Pentru evitarea unor probleme de alocare specifice segmentelor de lungime variabila intregul spatiu de memorie se partitioneaza in blocuri de dimensiuni egale, numite pagini.

Solutia are importante consecinte in ceea ce priveste relatia programatorului cu spatiul de adrese, intrucit paginarea elimina legatura intre organizarea logica a programului si paginile de memorie. Singurele componente care iau in considerare partitionarea spatiului programului in pagini sint cele ale mecanismului de gestiune a memoriei. In mod analog, memoria fizica este privita ca un set de blocuri, fiecare din ele avind dimensiunea unei pagini, fapt ce permite stocarea unei pagini intr-un bloc de memorie. Ca si in cazul segmentarii, nu este necesara alocarea de blocuri contigue de memorie pentru pagini contigue ale programului.

Fig. 4.11 indica alocarea unui program in memoria unui sistem functionind in regim de multiprogramare. Paginile, ca si segmentele, pot fi partial stocate in memoria principala a sistemului. Cind se face o referire la o adresa virtuala dintr-o pagina ce nu se afla in memoria primara, mecanismul de paginare copiaza intr-un bloc intrega pagina continind adresa mentionata. Mecanismul se numeste "cerere de pagini" (demand paging), intrucit paginile sint aduse in memorie cind sint solicitate de catre program.

Fig. 4.11. Alocarea memoriei intr-un sistem cu paginare

In decursul timpului s-au dezvoltat mai multe tehnici de paginare, care pot fi grupate dupa cum urmeaza:

- mecanisme care determina momentul la care o pagina trebuie copiata in memoria principala. Cea mai des utilizata tehnica este cea bazata pe cererea de pagini, utilizata de catre MMU ale unor microprocesoare moderne. S-au elaborat si alte metode, care incearca predictia comportarii programului si incarca in memorie paginile presupuse a fi utilizate de catre acesta in viitorul apropiat;

- mecanisme (sau tehnici de inlocuire) care folosesc algoritmi de selectare a paginilor existente in memorie ce pot fi evacuate, eliberind, astfel, spatiul pentru alte pagini;

- mecanisme ce folosesc un algoritm de determinare a cresterii / descresterii numarului de blocuri de memorie folosite de un anumit program.

4.8.1. Suportul hardware al mecanismului de paginare.

Mecanismele hardware necesare pentru o implementare eficienta a paginarii sint foarte apropiate de cele folosite pentru segmentare. Principala caracteristica este legata de posibilitatea de testare a adresei virtuale emise de catre CPU pentru a determina daca pagina care o contine se afla sau nu in memoria principala.

Aceasta functie se poate realiza cu ajutorul descriptorilor de pagina,cu structura tipica din figura 4.12. Descriptorul de pagina este similar cu cele de segment, principala diferenta constind din absenta cimpului limita, deoarece paginile au o lungime fixa, egala, adesea, cu o putere a lui doi.

| | | | | |

| Numar bloc | * | * | Alte atribute | * |

|_____ _______ ______ _________|_|__|_|__|________________|__|__|

| | |

Fanion prezent/absent ____| | |

| Bit acces _____|

Bit modificare ___________|

Fig. 4.12. Exemplu de format al descriptorului de pagina

4.8.2. Tabele de pagina.

Testarea si conversia adreselor de pagina se poate face prin mecanismul din fig. 4.13. Adresa virtuala este compusa din numarul paginii si un offset in cadrul acesteia. Numarul paginii poate fi impartit in mai multe cimpuri, fiecare folosit drept index pentru adresarea unui descriptor intr-un tabel cu structura arborescenta, ale carui frunze corespund descriptorilor de pagina. Continutul descriptorului de pagina este folosit pentru a testa prezenta unei pagini in memorie si pentru a oferi bitii cei mai semnificativi ai adresei fizice de memorie, in timp ce offsetul ii ofera pe cei mai putin semnificativi.

Fig. 4.13. Conversia adresei pe baza unor tabele cu structura arborescenta

Numarul de niveluri ale arborelui de conversie a adresei constituie un parametru important. Cu cit acest numar de niveluri este mai mare, cu atit timpul consumat pentru obtinerea decriptorului de pagina este mai mare. In acelasi timp, tabela cu structura arborescenta permite sistemului sa implementeze strategii de alocare a memoriei puternice si flexibile. De exemplu devine comoda folosirea in comun a aceluiasi subarbore de catre diferite procese, deci implementarea structurilor de date comune si a procedurilor comune este imediata. Intrucit zonele comune au un descriptor unic pentru fiecare pagina, actualizarea continutului acestuia ca urmare a incarcarii sau evacuarii nu este mai complicata decit pentru paginile care nu sint comune. Desi corecta, schema necesita unele modificari care sa o faca apta pentru o implementare eficienta. Principala problema consta in stabilirea tabelului de paginare (PGT): daca pentru fiecare program se aloca un spatiu de adrese virtuale separat, este necesar un PGT pentru fiecare program. De regula, spatiul virtual este mult mai mare decit spatiul fizic, deci si numarul paginilor si al descriptorilor asociati este mare. In consecinta, nu este posibila implementarea unei memorii mari si rapide in acelasi circuit integrat in care se afla MMU, memorie ce ar servi efectuarii, fara o degradare marcata, a operatiilor descrise in fig. 4.13.

Si in acest caz solutia problemei consta in ierarhizarea memoriei. Pe placheta de siliciu a MMU se realizeaza o memorie mica, dar rapida, in care se pastreaza descriptorii celor mai recent utilizate pagini. Pe durata unei faze a programului referirile sint axate pe un mic grup de pagini, deci descriptorul de pagina corespunzator adresei emise de catre CPU se afla, de cele mai multe ori, in memoria MMU, si doar arareori este necesar a recurge la memoria principala pentru a prelua un descriptor de pagina din PGT.

Memoria cache de mici dimensiuni a MMU destinata stocarii descriptorului este organizata ca o memorie adresabila prin continut (CAM - content-addressable memory), deoarece adresele acestei memorii nu mai sint legate de numarul de pagina, intrucit ea memoreaza descriptorii de pagina cel mai recent utilizati.

O alta implementare, utilizata adesea in calculatoare mari, de tipul IBM 370, se bazeaza pe o memorie CAM mai mare, care are alocat un cuvint pentru fiecare bloc de memorie: fiecare bloc din CAM contine descriptorul paginii stocate in blocul corespunzator al memoriei sau o indicatie ca blocul este vid. Descriptorul de pagina are aspectul din fig. 4.14, in care cimpul adresei baza a fost inlocuit de cimpul numarului paginii. Numarul paginii, emis de catre CPU, este utilizat ca intrare in memoria CAM ce contine descriptorii paginilor continute in memoria principala. Iesirea este constituita de adresa cuvintului din CAM in care se gaseste descriptorul respectiv, sau o indicatie ca pagina nu este prezenta in memorie. Daca pagina se afla in memorie, iesirea memoriei CAM furnizeaza direct bitii cei mai semnificativi ai adresei fizice. Desi mai rapida, aceasta solutie necesita o memorie CAM mai mare. De asemenea, schema permite realizarea de spatii de adresare distincte pentru fiecare program doar daca, la fiecare comutare de procese, are loc salvarea/restaurarea continutului memoriei CAM. In cazul schemei anterior descrise, mecanismul de gestiune a memoriei cache aduce descriptorii in aceasta imediat ce ei devin necesari.

Fig. 4.14. Conversia de adrese utilizand memorie asociativa

4.8.3. Segmentarea cu paginare

S-au subliniat similaritatile intre segmenatre si paginare. De asemenea, este posibil de a dispune de o tehnica de gestiune a memoriei care combina caracteristicile celor doua metode, ceea ce conduce la o tehnica oferind alocarea simpla specifica paginarii, ca si calitatile de protectie a memoriei specifice segmentarii. In acest caz programatorul divizeaza intregul spatiu virtual in segmentele reflectind structura logica a programului, ca in cazul segmentarii, apoi, fiecare segment este considerat drept constind dintr-un numar de pagini, ca in cazul paginarii, asa ca alocarea memoriei continua sa opereze cu elemente de lungime fixa. Mecanismele hardware necesare sint aceleasi ca pentru paginarea pura. Totusi, se constata o crestere a fragmentarii, ca urmare a faptului ca, in cazul paginarii, numai ultima pagina ramine, eventual, incompleta. La combinatia segmentare-paginare numarul de pagini partial utilizate este egal cu numarul de segmente, intrucit se exclude folosirea in comun a unei pagini de catre diferite segmente.

4.9. Principii privind protectia memoriei

In mediile cu multiprogramare necesitatea protectiei obiectelor de memorie (segmente de cod, date sau combinatii) impotriva utilizarii incorecte este determinata de cresterea cerintelor privind siguranta si, in acelasi timp, caracterul privat al acestora. In cadrul sistemelor prevazute cu un mecanism corespunzator de protectie erorile datorate unor cauze hardware sau software se propaga doar in obiectele de memorie accesibile procesului in care a aparut eroarea. Tentativa de a realiza accesul la alte obiecte, cu amenintarea unui posibil export al erorii, este detectata si marcata ca ilegala si, in consecinta, blocata de mecanismele de protectie. In modul acesta, caderea unuia sau mai multor procese din sistem nu conduce, in final, la caderea intregului sistem. Mai mult, mentinerea in stare de izolare a erorilor constituie un important instrument de depanare, intrucit ajuta la localizarea punctului in care a aparut eroarea. Ea constituie si baza altor mecanisme intrebuintate in scopul cresterii fiablitatii, cum sint categorisirea (categorisation), recuperarea (recovery) si relansarea (restart). Acelasi mecanism de protectie utilizat pentru localizarea erorilor protejeaza si informatia din sistem impotriva utilizarii neautorizate, cu conditia ca sistemul de operare sa faca imposibil accesul unui proces la obiecte pentru care nu are autorizatie. Este posibila implementarea unui mecanism mai rafinat de protectie, permitind sistemului sa specifice setul de operatii legale asupra unui obiect accesibil.

4.10. Medii inchise

Problema izolarii procesului (process isolation) reprezinta un element cheie in localizarea efectelor erorilor. Ea impune ca nici un proces sa nu dispuna de posibilitati superioare celor cerute de executareasarcinilor sale. In modul acesta, toate operatille efectuate de un proces asupra obiectelor sint constrinse la a fi in concordanta cu drepturile alocate. Orice abatere de la aceste interactiuni predefinite este considerata ilegala. Deoarece insesi drepturile unui proces sint stocate in memorie, devine necesar ca tabelul ce le contine sa devina un obiect special protejat.

Cea mai buna cale de a implementa principiul izolarii proceselor consta in a dispune de un sistem cu mediu inchis (closed environment). Intr-un astfel de sistem un proces ce ar urma sa efectueze o operatie asupra unui obiect trebuie sa arate mecanismului de protectie a memoriei ca dispune de dreptul de a efectua acea operatie.

Situatia globala a drepturilor de acces acordate diferitelor procese in conjunctie cu diferitele obiecte poate fi reprezentata prin forma matriciala din fig. 4.15, in care fiecare coloana este asociata unui obiect si fiecare rind este asociat unui proces. Continutul elementului (i,j) reprezinta setul de operatii ce pot fi efectuate de catre procesul i asupra obiectului j.

acc(i) :codul dreptului de acces (access right code)

Diferitele seturi de drepturi de acces corespund diferitelor valori ale lui i

Fig. 4.15 Reprezentarea matriciala a drepturilor de acces

Exista doua metode de reprezentare a matricii din fig. 4.15: prin rinduri si prin coloane. In cadrul primei metode fiecarui proces ii este asociata o lista a drepturilor de acces, eliminind toate elementele vide (corespunzind obiectelor pentru care nu exista drept de acces). Lista se mai numeste si domeniu de acces (domain of access), deoarece fiecare proces cunoaste doar obiectele la care are drept de acces, toate celelalte obiecte din sistem fiindu-i ascunse. Cind se face o referire de catre CPU a memoriei asociate unui obiect, domeniul de acces poate fi utilizat pentru gasirea obiectului la care se face referirea. A doua metoda ataseaza fiecarui obiect o lista a dreptului de acces pentru fiecare proces. Cind se solicita o operatie asupra unui obiect se testeaza lista de acces asociata pentru a se vedea ca procesul solicitant detine dreptul de acces la acel obiect.

Cele doua metode sint asemanatoare. Diferenta principala intre ele este data de costurile diferite ale operatiilor tipice necesare modificarii continutului matricii din fig. 4.15.

4.10.1. Liste de drepturi

Drepturile sint considerate ca niste chei si proprietarul are dreptul de acces la datele protejate prin cheie prin faptul ca poseda cheia respectiva. Aceasta ide e conduce la teste simple pentru asigurarea protectiei si permite libera circulatie si copierea drepturilor (desi falsificarea unui drept sau augmentarea domeniului sau de actiune trebuie interzise). Desi transferul de drepturi este o caracteristica dezirabile intr-un sistem, ea devine o problema cind se impune revocarea unui drept. Acest lucru este generat de posibilitatea ca dreptul, acordat initial doar unui singur proces, sa fie copiat si transferat altor procese. Lucrurile se complica si mai mult cind se are in vedere ca procesele au, de regula, durate de viata mai mici decit drepturile. Pentru revoacrea unui drept sint necesare operatii complexe, constind din inspectarea tuturor proceselor, active sau nu, indiferent de mediul in care sint memorate.

Un argument important in favoarea listelor de drepturi este dat de posibilitatea de a stoca lista de drepturi a procesului in rulare intr-o memorie mica si rapida, ceea ce creste viteza de testare a dreptului de acces. Listele de acces (despre care se va discuta in paragraful urmator) sint mult mai voluminoase si necesita o memorie rapida mai mare.

4.10.2. Liste de acces

Metoda bazata pe liste de acces ofera un fel de directory centralizat, asociat fiecarui obiect, continind drepturile de acces ale procesului: cind un proces realizeaza accesul la un obiect, mecanismul asociat de testare examineaza drepturile procesului solicitant si accepta sau refuza acestuia accesul la obiect. Fiecare operatie implicind fie un obiect, fie drepturile de acces asociate, trebuie efectuata prin intermediul unui administrator al obiectului (object manager), care testeaza validitatea operatiei. Deci, toate operatiile, incluzind transferul de drepturi, trebuie sa urmeze aceeasi ruta, ceea ce poate conduce la congestionarea ei. Pe de alta parte, drepturile de acces pentru un anumit obiect sint pastrate intr-un singur loc, fapt ce simplifica mult problema revocarii unui drept. Intrucit legitimitatea accesului este verificata de catre obiecte, un proces cunoaste toate obiectele din sistem, intrucit simpla cunoastere nu are nici un fel de implicatie asupra dreptului de acces. Un element caracteristic al metodei bazate pe liste de acces este necesitatea ca orice proces sa insoteasca cererea de acces cu un identificator, cerut de catre mecanismul de protectie pentru stabilirea dreptului de acces. De aceea, testarea listelor de acces este, in mod inerent, mai complicata si mai consumatoare de timp decit testarea listelor de drepturi.

Intrucit ambele tipuri de liste constituie reprezentari diferite ale aceleiasi baze de date, ele sint echivalente din punctul de vedere functional si ofera acelasi grad de protectie. Totusi, metoda bazata pe lista de drepturi ridica un numar mai mic de probleme de implementare, ceea ce a facut ca microprocesoarele moderne sa o foloseasca, in defavoarea metodei bazate pe lista de acces.

4.11. Domenii multiple

Uneori este necesara alocarea unor seturi diferite de drepturi procedurilor aceluiasi proces. Un exemplu este oferit de invocarea unei functii a sistemului de operare: procedura invocata are drepturi mai mari decit cea care o invoca, intrucit poate manipula date interioare sistemului de operare.

In acest caz nu mai este posibil a asocia unui proces un domeniu de acces, data fiind necesitatea unor domenii multiple. Fiecare procedura are drepturi permanente asupra obiectelor sale locale (obiectele proprii acelei proceduri). Suplimentar, in momentul apelarii, o procedura primeste un set de drepturi asupra unor obiecte nelocale, drepturi conferite de catre chemator sub forma unor parametri ai procedurii. Operatia se numeste validarea inidicatorilor (pointer validation), deoarece dreptul poate fi utilizat pentru adresarea obiectelor, deci ele au un cimp care memoreaza un indicator catre obiect.

Mijloacele hardware ce ofera suport pentru domenii multiple de acces trebuie sa poate recunoaste necesitatea de a modifica lista drepturilorasociate programului in rulare si ar trebui sa verifice ca drepturile transferate de catre chemator reprezinta un subset al multimii drepturilor posedate. Acest test este necesar pentru prevenirea cresterii necorespunzatoare a multimii drepturilor, rezultata din transferul spre o subrutina a unei copii a listei drepturilor augmentata, fapt ce ar permite subrutinei sa efectueze operatii interzise programului chemator.

Cu mici exceptii, unitatile de gestiune a memoriei din familiile microprocesoarelor moderne nu dispun de mijloace hardware speciale pentru pentru implementarea domeniilor multiple de acces in forma pura. In schimb, MMU sint proiectate pentru sprijinirea eficienta a domeniilor de acces asociate proceselor. Acelasi hardware poate fi folosit pentru implementarea domeniilor multiple, cu o anumita degradare a performantei, deoarece este necesara modificarea continutului memoriei interne a MMU la fiecare apel de procedura.

4.12. Stari masina privilegiate

O alta metoda de implementare a domeniilor multiple se bazeaza pe utilizarea starilor privilegiate ale masinii. Pe baza acestei abordari CPU isi poate asuma, la fiecare moment, una dintre cele n stari privilegiate. Fiecare procedura este asociata cu o stare privilegiata, asa ca, atunci cind una din ele isi incepe executia, CPU isi modifica starea in concordanta cu numarul privilegiului asociat procedurii. De asemenea, oricarui obiect i se asigneaza un numar de privilegiu.

Domeniul de acces al unei proceduri este constituit de catre toate obiectele din spatiul virtual al procedurii, alecaror numere de privilegiu sint mai mari sau egale cu starea actuala a CPU (daca numerele mai mici indica privilegii de grade superioare). Acest mecanism este usor de implementat, deoarece numarul privilegiului este memorat, in mod normal, in registrul intern de stare a CPU, care este stocat in stiva cind se apeleaza o procedura si este automat restaurat la terminarea executiei acesteia. Numarul de privilegiu se poate determina fie prin specificarea lui in instructiunea de apelare, fie prin citirea lui dintr-un descriptor adecvat al procesului. Prima metoda presupune existenta unei instructiuni care sa permita implementarea ei; a doua metoda se utilizeaza in sistemele care poseda modurile de lucru kernel (nucleu) si user (utilizator), in care o instructiune de apel sistem produce modificarea starii nucleului.

Un alt mecanism hardware cerut de implementarea unei masini cu stari privilegiate consta in posibilitatea de a testa daca referirile sint facute la obiecte cu numarul privilegiului egal sau mai mare cu cel al CPU. Desi toate microprocesoarele moderne implementeaza diferite stari pentru CPU care sint recunoscute de mijloacele hardware disponibile, doar putine din ele, cum este cazul microprocesorului iAPX286, ofera mecanismele hardware pentru compararea starii CPU cu numarul privilegiului obiectului adresat. Deci mecanismul starilor priviilegiate ofera protectie doar pentru un subset de instructiuni speciale si pentru registrele interne.

Trebuie subliniat ca mecanismul bazat pe stari privilegiate, chiar in cazul implementarii complete, violeaza principiul mediului inchis. Acest lucru se datoreaza faptului ca procedurile cu numar mic al privilegiului au, adesea, mai multe drepturi de acces decit cele strict necesare pentru a-si indeplini functia, facind mai dificila detectarea erorilor produse de defecte hardware, deoarece nivelul lor de privilegiu le permite manipularea de obiecte la care accesul nu ar fi necesar. Mai mult, devine posibila cresterea multimii drepturilor prin transferul unor parametri neadecvati spre procedurile privilegiate. De exemplu, daca un proces invoca o primitiva sendmessage, care transfera un numar unei cutii postale care, in mod normal, nu ii este accesibila, s-ar putea ca rezultatul sa constea in atasarea unui mesaj la acea cutie postala, fara a poseda dreptul de a o face.

Un alt pericol pentru securitatea sistemului este dat de posibilitatea de apelare a unei proceduri mai putin privilegiate. In acest caz devine posibil a apela o rutina bine testata si a obtine rezultate eronate, deoarece rutina a apelat o procedura mai putin meticulos testata, procedura ce a indus eroarea. In final, credibilitatea rezultatelor obtinute de utilizator este inferioara nivelului dorit, ceea ce faciliteaza deteriorarea programelor de nivel superior. Deci, in timp ce obiectele accesibile sint doar cele cu numar de privilegiu mai mare sau egal, procedurile apelabile sint cele cu numar de privilegiu mai mic sau egal.

4.13. Mijloace de sprijin pentru testarea drepturilor

Cea mai des folosita metoda de a atasa drepturi obiectelor de memorie in sisteme cu microprocesoare consta in a atasa un set de fanioane, numite "drepturi", aceluiasi descriptor al obictului utilizat pentru conversia adreselor virtuale in adrese fizice. Aceasta tehnica permite MMU sa gaseasca drepturile asociate obiectului de memorie adresat in descriptorul pe care l-a identificat in vederea conversiei de adrese, asa ca ambele operatii se pt efectua in paralel. In consecinta, drepturile se asociaza segmentelor sau paginilor, dupa cum se foloseste segmentarea sau paginarea ca tehnica de gestiune a memoriei. Totusi, din punctul de vedere al protectiei memoriei, intre cele doua moduri de gestiune exista o importanta deosebire.

Segmentele sint subdiviziuni ale programului vizibile de catre programator, cel care decide modul de organizare a programelor in segmente; deci, fiecare segment poate fi ales astfel incit sa i se poata asocia un anumit drept. Pe de alta parte, metoda paginarii nu permite programatorului sa structureze programul pe pagini, asa ca nu eista nici o relatie intre continutul paginii si semantica programului, o pagina putind contine un conglomerat de informatii care necesita - in scopuri legate de protectie - diferite tipuri de drepturi. De exemplu, o aceeasi pagina poate contine cod si date, accesul la cod facindu-se prin operatii de citire/inscriere. Rezulta ca nu este posibila protejarea codului impotriva inscrierilor eronate, deoarece este necesar a permite inscrierea in conjunctie cu datele din pagina. De aceea, segmentarea este de preferat pentru o implementare eficienta a meccanismelor de protectie bazate pe drepturi. Pe de alta parte, intrucit sistemele de paginare au avantaje importante privind alocarea memoriei, segmentarea cu paginare pare a fi o buna metoda, combinind avantajele atit ale segmentarii, cit si ale paginarii.

Desi drepturile au o durata lunga de viata, aceasta caracteristica este dificil de implementat in sistemele cu microprocesoare, in cadrul carora drepturile sint stocate in descriptorii folositi pentru gestiunea memoriei. Apar probleme cind programele se afla partial in memoria principala si partial pe disc. In acest caz, cimpurile fiecarui descriptor folosit pentru evaluarea adresei fizice isi schimba continutul de fiecare data cind pagina sau segmentul al care se face referire este adus din memoria secundara. Este dificil a transfera drepturile prin transferul descriptorului de segment sau de pagina, deoarece continuturile cimpurilor acestuia s-ar putea sa nu fie corecte. Mai mult, proliferarea descriptorilor da nastere unor probleme legate de concordanta intre diferite copii, care trebuie anulate cind un segment sau o pagina sint evacuate si actualizate cind acelasi segment sau pagina sint incarcate in memorie.

In continuare se indica o lista a celor mai des utilizate drepturi de acces. Trebuie mentionat ca unele din acestea pot fi atribuite simultan, intrucit se exclud reciproc:

- executie (execute only): cind fanionul asociat este 1, singurul drept posibil este acela de a extrage instructiuni. Fanionul este folosit pentru protectia zonelor de cod;

-citire (read only): cind fanionul asociat este 1, drepturile posibile sint citirea de date si extragerea de instructiuni. Fanionul este folosit pentru protectia obiectelor de memorie ce nu pot fi modificate;

-acces exclusiv la date (no CPU): cind fanionul asociat este 1, etragerea de instructiuni este considerata ilegala. Fanionul este folosit pentru identificarea obiectelor de date.

4.14. Protectia prin mijloace hardwarw a memoriei

Listele de drepturi si listele de acces ofera un grad limitat de protectie impotriva alterarii datelor si programelor pastrate in memorie, deoarece actiunea lor este limitata la evitarea propagarii erorilor dincolo de transmiterea domeniului de acces. Pentru detectarea rapida si,eventual, corectarea erorilor se utilizeaza frecvent mijloace de protectie hardware. Necesitatea unui astfel de test provine din cresterea constanta a dimensiunii memoriei, fapt ce contribuie la cresterea la circa 60 - 70% a ponderii erorilor de memorie in totalul erorilor sistem [23]. In favoarea protectiei prin mijloace hardware pledeaza si faptul ca, din punctul de vedere al volumului suplimentar de memorie si a circuitelor necesare implementarii, metodele folosite pentru detectarea si corectare a erorilor nu ridica probleme deosebite. In prezent exista mai multe circuite integrate care efectueaza codificarea/decodificarea in vederea detectiei si corectiei erorilor, ceea ce reduce costurile de implementare.

In cele ce urmeaza se vor ilustra solutii curent utilizate in acest domeniu.

4.14.1. Detectia erorilor de memorie

Cea mai simpla tehnica de detectare a erorilor este bazata pe bitul de paritate. Ea foloseste un singur bit suplimentar pentru fiecare cuvint de memorie, in care se memoreaza valoarea functiei "sau exclusiv" sau a functiei "si exclusiv" avind la intrare bitii cuvintului de date asociat. In cazul functiei "sau exclusiv" paritatea este cu sot, in celelalt caz ea fiind fara sot.

Inscrierea in memorie a unui cuvint este insotita de evaluarea bitului de paritate si el se memoreaza simultan cu datele. La citirea aceluiasi cuvint de memorie sint extrasi bitii de date si cel de paritate. Un circuit hardware evalueaza paritatea bitilor de date extrasi si o compara cu bitul de paritate evaluat la memorare. In cazul coincidentei paritatii calculate cu cea memorata, se considera ca informatia citita este corecta. In caz contrar se emita un semnal catre CPU, indicind detectarea unei erori de memorie. Evident, paritatea cuvintului de date citit se calculeaza in acelasi mod ca la memorarea cuvintului de date.

Mecanismul de testare a paritatii descris mai sus permite detectarea erorilor care afecteaza un numar impar de biti ai cuvintului de date. Eronarea unui numar par de biti trece nedetectata. Intrucit capacitatea de detectie/corectie a erorilor de catre un cod este data de numarul maxim de erori detectate/corectate in cazul cel mai nefavorabil, controlul paritatii permite evidentierea erorilor simple.

In fig. 4.16. s-a reprezentat o schema folosind circuite "sau exclusiv" pentru evaluarea paritatii (cu sot) a unui cuvint de date de 8 biti. Schema poate folosi atit la testarea paritatii cuvintului citit (in acest caz semnalul Bit de paritate are valoarea citita din bitul de paritate asociat cuvintului si Eroare este semnal catre CPU), cit si la generarea paritatii la inscrierea unui cuvint in memorie (Bit de paritate = 0 si iesirea schemei furnizeaza informatia pentru bitul de paritate asociat cuvintului).

Daca un cuvint de date de n biti este folosit ca entitate pentru tehnica de detectie bazata pe paritate, capacitatea de memorie ceruta de aceast a tehnica este de 1/n din capacitatea memoriei propriu-zise. In practica, valoarea normala pentru n este 8.

4.14.2. Coduri detectoare/corectoare de erori

Tehnologiia memoriilor RAM dinamice a permis realizarea unor mari volume de memorie pe o placheta cu cablaj imprimat, fapt ce a dus la larga utilizare a acestui tip de memorii in sistemele cu microprocesoare. Din pacate, memoriile dinamice nu sint numai dense, ci si mai intens supuse erorilor decit memoriile statice. Din cauzele obisnuite ale erorilor sint de remarcat radiatiile (in special particulele alfa) si virfurile de tensiune. Deci, chiar daca memoria dinamica functioneaza normal, este posibila aparitia erorilor.

Fig. 4.16. Circuit de generare/testare a paritatii

Pentru a face fata acestor probleme se utilizeaza coduri cu redondanta, capabile nu numai sa detecteze, ci sa si corecteze eventualelel erori. Cind, la citirea unui cuvint de date, se constata o eroare, aceasta poate fi corectata si cuvintul reinscris in locatia corespunzatoare. Daca eroarea a fost produsa de o particula alfa, memoria isi recapata continutul normal. Daca eroarea este rezultatul unei defectari hardware, inscrierea nu poate corecta valoarea informatiei stocate, in schimb CPU va primi valoarea corecta pe care locatia adresata ar fi trebuit sa o contina.

Codul corector de erori cel mai des folosit pentru memorii dinamice este codul Hamming ce permite detectarea erorilor duble si corectia erorilor simple. Acest cod necesita un numar suplimentar de k biti pentru fiecare cuvint de date de n biti. asa incit eroarea unuia din cei k+n biti ai cuvintului de cod sa produca o combinatie binara unica si distincta de zero. Deci este necesara satisfacerea conditiei

k+n =< 2 ^k-1 - 1.

Inaintea stocarii in memmorie, fiecarui cuvint de n biti de date i se adauga cei k biti de control. La citirea memoriei se extrag cei n-k biti memorati si se calculeaza asa numitul sindrom. Daca valoarea sa este 0, se considera ca informatia citita este corecta. In caz contrar, valoarea lui identifica in mod unic bitul eronat sau semnaleaza prezenta erorii duble. Calculul bitilor de control necesita calcularea produsului intre o matrice A de dimensiune (k-1) x n si vectorul de date D de n biti. Rezulta primii k-1 biti de control ai vectorului C, conform formulei:

d₁*a_1,i+d₂*a_2,i + ... + d_n*a_n,i = c_i, i=1,2,...,k-1

Ultimul bit de control este bitul de paritate (cu sot) al celorlalti k+n-1 biti ai vectorului C.

Matricea A contine, pentru fiecare coloana, o combinatie unica de k-1 biti. Nu este posibila combinatia in care sa figureze un singur 1. Iata un exemplu:

d₁ d₂ d₃ d₄

1 1 1 0 c₁

1 0 1 1 c₂

0 1 1 1 c₃

c₁ = d₁ + d₂ + d₃

c₂ = d₁ + d₃ + d₄

c₃ = d₂ + d₃ + d₄

c₄ = d₁ + d₂ + d₃ + d₄ + c₁ + c₂ + c₃

Sindromul se obtine efectuind produsul intre o matrice A' de dimensiune (k+n) x n, si vectorul de date si biti de control. Matricea A' este obtinuta adaugind un rind de 1 matricii A si concatenind-o cu o matrice de dimensiuni k x k avind forma:

0 1 0 ... 0

0 0 1 ... 0

0 0 0 ... 1

1 1 1 ... 1

Pentru exemplul considerat se obtine

d₁ d₂ d₃ d₄ c₁ c₂ c₃ c₄

1 1 1 0 0 1 0 0 s₁

1 0 1 1 0 0 1 0 s₂

0 1 1 1 0 0 0 1 s₃

1 1 1 1 1 1 1 1 s₄

s₁ = d₁ + d₂ + d₃ + c₂

s₂ = d₁ + d₃ + d₄ + c₃

s₃ = d₂ + d₃ + d₄ + c₄

s₄ = d₁ + d₂ + d₃ + d₄ + c₁ + c₂ + c₃ + c₄

Cind continutul citit al locatiei de memorie este corect, sindromul este compus numai din 0. Daca apare o eroare simpla, atunci s_n = 1 si, de asemenea, devine 1 sindromul in al carui calcul s-a folosit bitul eronat. In coonsecinta, vectorul sindrom capata valoarea acelei coloane a matricii de control A' care contine bitul eronat. Daca s_n = 0 dar sindromul nu este nul, acest lucru semnifica aparitia a doua sau mai multe erori, dar nu se dispune de informatiile necesare corectarii lor. In concluzie, codul folosit permite detectia erorilor simple si duble, precum si detectia erorilor simple.

Alegerea elementelor matricii A, deci si ale matricii A', nu este nici pe departe atit de empirica pe cit pare din exemplul considerat. Exista o teorie a codurilor, bine pusa la punct, care ofera baze stiintifice de selectare a codului optim pentru o situatie data.

Costul suplimentar exprimat in consum de memorie este k/n. Ar parea ca este rentabil a folosi cuvinte cu numar n de biti mare, ceea ce ar duce la scaderea raportului k/n. Pe de alta parte, cu cit n este mai mare, creste si probabilitatea de aparitie a erorilor, sau, altfel spus, creste probabilitatea ca numarul erorilor care apar sa depaseasca numarul de erori corectabile sau detectabile de catre cod.

Din punctul de vedere al circuitelor secundare nu se ridica probleme deosebite, deoarece tehnologia integrarii pe scara larga a permis realizarea, in mai multe variante, a circuitelor care rezolva complet codificarea, detectia si corectia erorilor. Circuitele pot fi folosite in structuri de cuvinte de memorie de l, 2 sau 4 biti, ceea ce inlesneste munca proiectantului.

Bitii de control pot fi folositi si pentru protectia memoriei impotriva adresarii eronate. In acest caz bitii de control sint calculati prin luarea in considerare a bitilor atit de date cit si de adresa. Cind se face accesul unui cuvint in vederea citirii se face concatenarea bitilor de date si control cititi din memorie cu bitii de adresa, apoi se verifica sirul astfel rezultat.

4.14.3 Reconfigurarea memoriei.

Codurile corectoare de erori permit unui modul de memorie sa se comporte corect chiar in prezenta unui mic numar de erori in matricea memoriei, deoarece continuturile incorecte sint modificate asa incit, din exterior,ele sa apara corecte. Daca eroarea se datoreste unui defect permanent, ea poate fi corectata de catre mecanismul de corectie, dar nu poate fi indepartata pina la repararea defectului. Deci, numarul acestor erori creste in timp pina cind ele nu mai pot fi corectate folosind bitii redondanti.

Pentru cresterea fiabilitatii memoriei se pot folosi biti de rezerva. Memoria poate fi considerata ca o matrice in care liniile corespund cuvintelor, iar coloanele - bitilor de acelasi ordin din cuvintele memoriei.

Tehnica bitilor de rezerva foloseste un numar h de coloane suplimentare, asa ca fiecare cuvint are h biti de rezerva. Folosirea de coloane suplimentare in loc de rinduri suplimentare este dicatata de structura circuitelor de memorie, care tind sa aiba un mare numar de cuvinte foarte scurte, ceea ce face mai ieftina introducerea de coloane suplimentare. In favoarea acestei alegeri pledeaza si faptul ca, daca se defecteaza un circuit de memorie ce asigura o coloana, toate cuvintele vor prezenta erori in aceasta coloana. Este mai simplua substitui coloana defecta cu una de rezerva.

Utilizarea eficienta a bitilor de rezerva presupune existenta unui cod redondant, care sa localizeze coloana defecta, si un circuit de multiplexare, care sa reconfigureze conexiunile la magistrale ale memoriei intr-un mod care sa permita utilizarea coloanei de rezerva in locul celei defecte, asa cum se poate vedea in exemplul din fig. 4.17.

Fig. 4.17. Exemplu de implementare a tehnicii bazate pe biti de rezerva.

Desigur, erorile pot aparea in coloanele obisnuite, ca si in cele de rezerva. De aceea, codul folosit trebuie sa considere toate coloanele memoriei pentru a evita inlocuirea unei coloane defecte cu alta coloana defecta.

4.15. Concluzii

Complexitatea crescuta a aplicatiilor microprocesoarelor a facut ca organizarea memoriei in sistem cu microprocesoare sa se apropie de cea a minicalculatoarelor sau chiar a calculatoarelor puternice. De aceea, modelele de organizare a memoriei elaborate pentru sisteme mari se regasesc si in lumea microprocesoarelor.

In acest capitol au fost prezentate cele mai importante tehnici de gestiune si protectie a memoriei in sisteme cu microprocesoare. Datorita localitatii programelor devine posibila ierarhizarea memoriei. In consecinta se pot obtine viteze comparabile cu cele ale celei mai rapide componente a sistemului de memorie la preturi pe bit aproape egale cu cele ale celei mai ieftine componente.

Ierarhizarea subsistemelor de memorie permite separarea adreselor fizice de cele virtuale, fapt ce necesita existenta unui mecanism de conversie a adreselor.

S-au detaliat unele mecanisme de implementare si s-au prezentat mecanisme de protectie a memoriei, esentiale in evitarea folosirii incorecte a obiectelor pastrate in memorie.

In fine, s-au examinat mecanisme hardware de protejare a continutului locatiilor de memorie impotriva erorilor, mecanisme care pot fi simple (de tipul celor ce folosesc paritatea) sau complexe (utilizind codul Hamming).

R-read request; W-write request; G-grant request

Memorie_Multiport

Prioritati

o Fixate prin numarul dispozitivului

o Round robin

o Time multiplexed

Protocol al canalului (Channel protocol

DMA, canal DMA.

CPU creeaza program canal, il incarca in memorie la adresa P.

Emite o instructiune START I/O canalului si ii furnizeaza adresa P, dupa care CPU efectueaza alte task-uri, nelegate de canal, pana la pas 3.

Canalul isi incarca PC cu valoarea P si executa programul canal fara interventia CPU.

Programul canal controleaza dispozitivele I/O, care transfera datele direct in memorie.

La terminare, canalul intrerupe CPU pentru a-l informa despre terminare. CPU poate aloca un alt task canalului.

Organizarea Memoriei

Organizarea Memoriei:

Organizarea Memoriei - "High Order Interleave":

"Low Order Interleave"

Document Info

Accesari: 6127
Apreciat:

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta

Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site

Copiaza codul:
in pagina web a site-ului tau.

eCoduri.com - coduri postale, contabile, CAEN sau bancare

Politica de confidentialitate | Termenii si conditii de utilizare