*Managementul memorieiCurs 71 Concepte2 Swapping3 Memoria virtual4 Algoritmi paginare

*Managementul memorieiProgramatorii i doresc memorie:De dimensiune mareRapidNon volatilIerarhia memoriilor Memorie de dimensiune mic, vitez mare i scump cache Memorie de vitez medie i ponderat ca pre memoria principalMemorie de dimensiune mare, vitez mic dar ieftin hard diskUna din principalele funcii ale SO este de a administra memoria (ierarhia acesteia), care presupune ncrcarea i evacuarea blocurilor de date n/din memoria secundar.

*Monoprogramare fr swapping sau paginareTrei modaliti simple de organizare a memoriei pentru un SO cu un singur proces aflat n execuie.

*Multiprogramare cu partiii fixe de memorie Partiii de memorie fixCozi de ateptare separate pentru fiecare partiieO singur coad de ateptare pentru toate partiiile

*MultiprogramareUtilizarea UCP este dependent de numrul de procese ncrcate n memorieDegree of multiprogramming

*Relocare i protecieRelocare:Adresele nu pot fi absolute. ntr-un sistem multiprogramat, memoria principal este n general mprit de mai multe procese. Odat ce un proces a fost evacuat pe disc, nu putem cere ca atunci cnd acest proces este readus n memorie s fie ncrcat n aceiai regiune. Trebuie s permitem ca un program s fie relocat n memoria principal.Protecie:Prin relocare dinamic, un proces are un spaiu de adresare propriu care nu l partajeaz cu alte procese (exist excepii). Soluia mapeaz spaiul de adresare a fiecrui proces ntr-o alt zona fizic de memorie utiliznd base register i limit register.Fiecare proces este astfel izolat i protejat de accesul nedorit al altor procese.

*Translatarea adreselor logice n adrese fizice

*Swapping (1)Alocarea memoriei se schimb Procesele acceseaz zona de memoriePrsesc zona de memorieRegiunile haurate reprezint zone de memorie neutilizat

*Swapping (2)Alocarea de spaiu n memorie pentru un segment de date ce crete n dimensiuneAlocarea de spaiu n memorie pentru un segment de date i segment de stiv care cresc n dimensiune

*Managementul memoriei cu bitmap (harta de bii)Alocarea memoriei pentru 5 procese, trei zone liberei harta de bii corespondentAceiai informaie dar sub form de list

*Managementul memoriei cu listePatru combinaii posibile pentru procesul X care i ncheie execuia

*Memoria virtualPaginare (1)Poziionarea i modalitatea de funcionare a MMU

*Paginare (2)Relaia dintre adresele virtuale i adresele fizice din memorie oferite de tabela de pagini

*Tabela de pagini (1)Funcionarea MMU cu 16 pagini virtuale de dimensiune 4 KB

*Tabela de pagini (3)O nregistrare a tabelei de pagini

*Memorii asociative (TLB)

*Algoritmi de nlocuire a paginilorPage fault foreaz luarea unei deciziiCare pagin s fie evacuatObinerea de spaiu n memorie pentru ncrcarea unei alte paginiPaginile modificate trebuie salvate nainte de evacuarea pe discPaginile nemodificate pot fi rescriseNu este indicat s se selecteze pentru evacuare pagini des referiteDeoarece vor trebui rencrcate n memorie ntr-un timp scurt

*Algoritmi optimi de nlocuire a paginilornlocuirea unor pagini care nu vor fi utilizate n viitorul apropiatUn algoritm optimal dar irealizabilEstimare dupIstoricul paginilor accesate n cazul execuiei unui anumit procesNu este un algoritm practic

*Algorimul NRU - Not Recently UsedFiecare pagin are biii de stare Reference bit (R) i Modified bit (M)Biii sunt setai cnd pagina este referit(read) sau modificat (write)Paginile sunt clasificate astfel:Clasa 0 : nereferite, nemodificateClasa 1: nereferite, modificateClasa 2: referite, nemodificateClasa 3 : referite, modificateNRU evacueaz pagini selectate aleatorDin clasa cu cel mai mic ordin care deine pagini

*Algoritmul FIFOSe bazeaz pe o list de pagini corelate ntre elen ordinea n care au intrat n memoriePagina aflat la nceputul listei va fi evacuat din memorieDezavantajul este c Pagina aflat n memorie o perioad mai lung de timp poate fi de fapt cel mai des referit

*Algoritmul second chanceCum se ofer a doua ansPaginile sunt sortate n ordine FIFODac la momentul 20, se genereaz page fault iar pagina A are bitul de stare R setat, pagina A va fi reaezat n list iar bitul R va fi desetat.

*Algoritmul clock

*Algoritmul LRU- Least Recently UsedSe bazeaz pe prezumia c paginile utilizate recent vor fi utilizate n viitorul apropiatEvacueaz pagina care nu a fost utilizat un timp ndelungatPstreaz o list corelat de paginiSe actualizeaz aceast list la fiecare referire a zonei de memorieExist un contor pentru fiecare pagin selectat Se alege pagina cu cea mai mic valoare a contoruluiContor se seteaz pe 0 periodic

*Algoritmul de nlocuire a paginilor din setul de lucruSetul de lucru reprezint un set de pagini utilizate n cele mai recente k referine la zona de memoriew(k,t) este dimensiunea setului de lucru la momentul t

*Algoritmul de nlocuire a paginilor din setul de lucru

*Algoritmul WSClock

*Recapitulare algoritmi de nlocuire a paginilor

*De tiut...Caracterizai cazul n care utilizm tehnica de multiprogramare pe partiii fixate de memorie.Cum se realizeaz translatarea adreselor logice n adrese fizice?Cum se realizeaz swapping-ul ?Descriei cum se realizeaz managementul memoriei utiliznd bitmap.Descriei cum se realizeaz managementul memoriei utiliznd liste.Caracterizai memoria virtual.Ce reprezint TLB.Prezentai algoritmii de nlocuire a paginilor.Care este diferena dintre o adres fizic i una virtual?

*De tiut...Un sistem are suficient spaiu n memoria sa principal pentru 4 programe. Aceste programe sunt inactive jumtate din timp ateptnd operaii de I/O. Ct timp UCP se irosete?S considerm un sistem de transfer al paginilor pe disc n care memoria const din urmtoarele dimensiuni de guri n ordinea memoriei: 10KB, 4KB, 20KB, 18KB, 7KB, (KB, 12 KB, i 15 KB. Care gaur este aleas n cazul unor cereri succesive de segmente de (a) 12 KB, (b) 10 KB, (c) 9 KB n cazul aplicrii algoritmului first fit? Aceiai ntrebare pentru best fit, worst fit, i next fit.Folosind imaginea din slide-ul 13 precizai care este adresa fizic corespunztoare urmtoarelor adrese virtuale (a) 20 (b)4100 (c) 8300

*De tiut...Un computer deine patru cadre de pagin. Timpul de ncrcare, timpul de acces, Biii R i M sunt precizai n tabel.Care pagin va fi nlocuit prin utilizarea algoritmului NRU?Care pagin va fi nlocuit prin utilizarea algoritmului FIFO?Care pagin va fi nlocuit prin utilizarea algoritmului LRU?Care pagin va fi nlocuit prin utilizarea algoritmului second chance?

PaginancrcareAccesRM012628010123026501214027000311028511

*BibliografieA. Silberschatz, P. Galvin, Operating System Concepts, John Wiley and Sons Inc., 2005, pag 275-297.A. Tanembaum, Modern Operating Systems, Prentice Hall, 2007, pag 175-216.Gh. Dodescu, Sisteme de operare, Ed. Economic, 2003, pag 129-195.

*****Cnd un proces se afl n starea ready base register se ncarc cu adresa de nceput a programului din memoria principal, iar limit register ncarc lungimea programului. n timpul execuiei procesului accesul la memorie se realizeaz prin intermediul adreselor relative astfel:Valoarea din base register se adug la adresa relativ i rezult o adres absolut Adresa absolut este comparat cu valoarea din limit register:se continu execuia dac nu se depete valoarea din limit registeraltfel se genereaz ntrerupere deoarece programul acceseaz o zon de memorie care nu i aparine.Un dezavantaj al acestei metode este faptul c relocarea presupune realizarea unei operaii de nsumare i de comparaie devenind astfel consumatoare de timp i deci ineficient.*******n figur este reprezentat modalitatea de funcionare a MMU.Se consider c se mapeaz utiliznd MMU adresa virtual 8196 reprezentat binar pe 16 bii astfel: 0010000000000100. Aceast adres virtual este separat n dou seciuni de respectiv 12 bii i 4 bii. Din cei patru bii se formeaz numrul paginii, iar din cei 12 bii se formeaz deplasamentul n interiorul paginii.Astfel, putem genera pe baza a 4 bii maxim 16 pagini, iar cu ajutorul deplasamentului format din cei 12 bii putem adresa 4096 bytes n cadrul unei pagini.Numrul de pagin este utilizat ca un index n tabela de pagini. Dac bitul care marcheaz prezena cadrului de pagin asociat paginii virtuale n memoria fizic este setat la valoarea 0 se realizeaz un trap ctre SO, altfel se copie numrul cadrului de pagin i deplasamentul. mpreun formeaz o adres fizic care va fi transmis pe magistral.********Dac se utilizeaz paginarea la cerere, paginile sunt ncrcate atunci cnd sunt cerute, acest lucru de obicei se realizeaz la generarea unui page fault. Dac utilizm paginarea la cerere riscm s generm de foarte multe ori page fault, astfel nct sistemul s nu le poat face fa. Ca atare procesele au fost create n aa fel nct la un moment dat s solicite numai o mic fracie din toate paginile de care au nevoie pentru finalizarea execuiei. Setul de pagini pe care un proces le utilizeaz la un moment dat ntr-o anumit faz de execuie a sa se numete set de lucru. Dac ntregul set de lucru este ncrcat n memorie procesul va rula un timp, fr s genereze page fault. Dac se ntmpl ca un poces s aib un set de lucru care s nu poat fi ncrcat n memorie acesta va genera numeroase page fault-uri. Un astfel de program care genereaz page fault dup execuia a puine instruciuni se numete thrashing sau blocare prin ncrcare. De aceea multe sisteme de paginare urmresc ca setul de lucru al unui proces s fie ncrcat n memorie odat cu lansarea n execuie a procesului n sine. Acesta este modelul setului de lucru. ncrcarea paginilor n memorie nainte ca procesul s fie lansat n execuie se numete prepaginare.n figur vizualizm dimensiunea w(k,t) a setului de lucru la momentul t, adic un set de pagini folosit la cele mai recente k accesri ale memoriei. Faptul c majoritatea programelor acceseaz aleator un numr mic de pagini, dar acest set se modific ncet n timp explic o cretere rapid a funciei w(k,t) la nceput i apoi creterea mai lent pentru valori mai mari ale lui k.********