. Sisteme de Operare Si Metode de Alocare a Memoriei Principale
Introducere
Una din cele mai faimoase gafe ale lui Bill Gates, patronul firmei Microsoft, pronunțată cândva pe la începutul anilor ’80 suna cam așa: “640 de kiloocteți trebuie să fie îndeajuns pentru oricine“. Enunțul este cu atât mai amuzant cu cât compania Microsoft produce niște programe uriașe, pentru care resursele calculatoarelor contemporane, care au evoluat într-o rată greu de imaginat, nu sunt suficiente.
Dacă lucrurile ar fi stat așa cum prevedea Gates, atunci sistemele de operare însele ar fi dispărut, sau ar fi arătat substanțial diferit de cele din ziua de azi. De ce spun că sistemele de operare ar fi dispărut ? Pentru că rolul principal al unui sistem de operare este cel de management al resurselor unui calculator, în particular de management al memoriei. Dacă resursele ar fi prezente din abundență, atunci necesitatea unui manager ar fi mai puțin stringentă.
Lucrarea de față prezintă și analizează mecanismele de alocare a memoriei de către sistemele de operare.
Lucrarea poate fi împărțită în trei părți. Prima parte (capitolele I și II) prezintă mecanismele generale de alocare a memoriei. Această parte este organizată evolutiv începând cu tehnicile de gestionare a suprapunerilor și încărcare dinamică a modulelor, tehnici aplicabile de către programator explicit. Apoi sunt prezentate pe larg tehnicile moderne de organizare a memoriei: paginarea și segmentarea cu exemple și scurte studii de caz.
A doua parte este o privire comparativă a modului în care cel mai cunoscute sisteme de operare își organizează memoria. Pentru capitolul dedicat sistemului de operare UNIX am consultat o lucrare de marcă editată sub patronajul firmei AT&T firmă cu o mare contribuție la dezvoltarea acestui sistem de operare. Aici sunt analizate detaliat atât aspecte general întâlnite la alocarea memoriei cât și particularități ale sistemului UNIX în acest domeniu. Este analizat apoi sistemul de operare Windows cu variantele sale de la Windows 3.1 la Windows NT.
În încheiere într-un capitol mai practic sunt prezentate câteva implementări ale alocatorului de memorie din nucleul sistemelor de tip UNIX și nu numai.
Caracteristicile și performanțele memoriei și procesului de memorare influențează în mare măsură funcționarea și performanțele sistemului de calcul respectiv.
Activitatea de gestiune a memoriei are în vedere fie memoria organizată pe două nivele, memoria principală și memoria auxiliară, fie memoria privită sub forma unui singur nivel în conceptul de memorie virtuală. Obiectivul principal al activității de gestiune a memoriei este de a furniza o viteză de execuție foarte mare a unui program prin menținerea în memoria principală a acelor părți din program care sunt referite cu o frecvență mare de către procesor, restul părților din program putând fi memorate în memoria auxiliară și încărcate în momentul solicitării de către procesor.
Capitolul I
Alocarea memoriei principale
Vom analiza cum putem organiza memoria principală (numită și random-access-memory (RAM)). În general organizarea memoriei presupune două operații:
Address allocate(int size);
void deallocate(Address block);
Procedura allocate primește o cerere pentru un bloc alocat contiguu de dimensiunea size octeți de memorie și întoarce un pointer la un astfel de bloc. Procedura dealocate eliberează blocul indicat el putând fi refolosit. Câteodată avem la dispoziție și o a treia procedură
Address reallocate(Address block, int new_size);
care ia un bloc alocat și îi modifică dimensiunea fie întorcând o parte din el memoriei disponibile fie extinzându-l la un bloc mai mare. Nu întotdeauna este posibil să se mărească dimensiunea blocului fără a îl copia la o nouă locație.
Alocatoarele de memorie sunt folosite în diferite situații. În UNIX fiecare proces are un segment de date. Există un apel sistem pentru a mări dimensiunea segmentului de date dar nu există nici unul care să îl facă mai mic. De asemenea apelul sistem este destul de costisitor. Prin urmare există biblioteci cu proceduri pentru a gestiona acest spațiu (funcțiile malloc, free și realloc). Doar când malloc sau realloc nu mai au spațiu este necesar să se facă un apel sistem. Operatorii C++ new și delete sunt variante mai noi ale funcțiilor malloc și free. Operatorul Java new folosește de asemenea malloc, și împreună cu rutina java free când un obiect este găsit ca inaccesibil la colectarea gunoaielor.
Sistemul de operare folosește de asemenea un alocator de memorie pentru a gestiona spațiul folosit de structurile de date ale sistemului de operare și procesele utilizator. După cum am văzut mai devreme sunt câteva motive pentru care am putea dori mai multe procese cum ar fi satisfacerea mai multor utilizatori sau pentru a controla mai multe periferice. Mai este și un motiv mai “egoist” pentru care SO vrea să aibă mai multe procese în memorie în același timp: pentru a ține ocupat CPU ocupat. Presupunând că sunt n procese în memorie (ceea ce se numește nivelul de multiprogramare) și fiecare proces este blocat așteptând (pentru I/O) o fracțiune de timp p. În cel mai bun caz CPU ar putea fi 100% ocupat .
De exemplu dacă fiecare proces este gata de rulare 20% din timp p=0,8 și CPU poate fi ținut complet ocupat cu 5 procese. Bineînțeles procesele reale nu sunt așa de cooperative. În cel mai rău caz ele pot toate să blocheze în același timp (fracția de timp în care CPU este ocupat va fi doar de 1-p (20% în exemplul nostru). Dacă fiecare proces se decide la întâmplare și independent când să se blocheze șansa ca toate procesele să fie blocate în același timp este doar pn, așa că utilizarea CPU este doar de 1-pn. Continuând exemplul pentru cazul n=5 și p=0.8, rata de utilizare așteptată este de 1-0.85=1-0.32768=0.67232. Cu alte cuvinte CPU va fi ocupat în medie 67%.
I.1 Algoritmi pentru gestionarea memoriei
Clienții gestionarului de memorie (procesele care cer memorie) păstrează informații despre blocurile alocate. Gestionarul de memorie trebuie să țină minte golurile dintre blocurile alocate de obicei într-o listă dublu înlănțuită. Această structură este numită lista blocurilor libere. Această listă nu ocupă spațiu decât pentru pointerii cap și coadă deoarece legăturile dintre goluri pot fi păstrate chiar în aceste goluri (presupunând că fiecare gol are dimensiunea de cel puțin de două ori mai mare decât a spațiului necesar pentru un pionter).Pentru a satisface o cerere allocate(n) gestionarul de memorie găsește un gol de dimensiune cel puțin n și îl înlătură din lista blocurilor libere. Dacă golul este mai mare de n byți poate să despartă blocul în două părți și returnând partea rămasă în listă. Pentru a satisface o cere deallocate gestionarul de memorie transformă blocul într-o structură de “gol” și îl inserează în lista blocurilor libere. Dacă noul gol este urmat sau precedat de alt gol cele două blocuri pot fi comasate în unul singur cum se va explica mai jos.
Cum știe gestionarul de memorie cât de mare este un bloc? Metoda uzuală este să pună un header mai mic în blocul alocat care să conțină dimensiunea blocului și eventual alte informații despre bloc. Procedura allocate întoarce un pointer spre corpul blocului nu spre nu spre header astfel clientul nu trebuie să știe nimic despre aceasta. Procedura deallocate extrage dimensiunea headerului din argumentul său(adresa blocului de eliberat) pentru a afla adresa headerului. Clientul crede că dimensiunea blocului este puțin mai mică decât este în realitate. Atât timp cât clientul nu modifică headerul blocului alocat este totul în ordine dar dacă aceasta se întâmplă gestionarul de memorie va fi derutat. Aceasta este o problemă întâlnită frecvent la malloc în programele scrise în C sau C++ sub UNIX. Sistemul Java folosește o serie de rutine pentru a verifica și preveni această eroare. Pentru a fi mai ușor de comasat golurile adiacente gestionarul de memorie adaugă o etichetă la începutul și la sfârșitul fiecărui gol sau bloc alocat și înregistrează dimensiunea blocului la ambele capete ale sale.
Figura 1. Listă de blocuri
Când blocul este dealocat gestionarul de memorie adaugă dimensiunea blocului (care este păstrată în headerul său) la adresa începutului blocului pentru a afla adresa primului cuvânt de după sfârșitul blocului. Se uită la etichetă pentru a vedea dacă spațiul ce urmează este un gol sau este un bloc alocat. Dacă este un gol atunci este eliminat din lista blocurilor libere și unit cu blocul care va fi eliberat pentru a face un gol mai mare. De asemenea dacă eticheta de la sfârșitul blocului precedent arată că spațiul următor este un gol putem afla adresa de început a golului scăzând dimensiunea sa din adresa blocului ce va fi eliberat (de aceea dimensiunea este păstrată la ambele capete), îl elimină din lista blocurilor libere și îl unește cu blocul ce va fi eliminat. În final adăugăm noul gol în lista blocurilor libere. Golurile sunt reținute în listă dublu înlănțuită pentru a fi mai ușor de eliminat din listă când trebuiesc comasate cu blocurile care sunt eliberate.
Cum alege gestionarul de memorie un bloc liber pentru a satisface o cerere allocate ? La început poate părea că ar trebui aleasă cel mai mic gol destul de mare pentru a satisface cererea. Această strategie se cheamă best fit. Aceasta are două inconveniente. Primul este că presupune o căutare costisitoare a întregii liste de blocuri libere pentru a o găsi pe cea mai potrivită (pot fi folosite alte structuri de date mai sofisticate pentru a face căutarea mai rapidă). Dezavantajul mai important este că duce la crearea a mai multe goluri de dimensiune prea redusă pentru a mai putea satisface vreo cerere. Această situație este numită fragmentare, și este o problemă care apare la toate strategiile de alocare a memoriei cu toate că nu este de dorit. O modalitate de a evita apariția acestor goluri mici este să se dea clientului un bloc mai mare decât cel cerut. De exemplu putem aproxima toate cererile prin primul multiplu de 64 octeți mai mare decât cel cerut. Aceasta nu elimină fragmentarea ci doar o ascunde. Spațiul nefolosit ce se găsește sub formă de goluri se numește fragmentare externă în timp ce spațiul nefolosit din interiorul blocurilor alocate se numește fragmentare internă.
Altă metodă de alocare este prima potrivire (first fit) care parcurge pur și simplu lista blocurilor libere până când găsește un bloc suficient de mare. În ciuda denumirii first fit este în general mai bună decât best fit deoarece reduce fragmentarea. Mai apare însă o altă problemă: golurile mici tind să se adune la începutul listei iar alocatorul trebuie să caute de fiecare dată mai mult în listă. Această problemă este rezolvată cu metoda următoarei potriviri (next fit) care începe fiecare căutare de acolo de unde s-a terminat ultima luând-o de fiecare dată de la capăt când se ajunge la sfârșit.
O altă strategie este să se mențină liste separate fiecare conținând blocuri libere de dimensiuni diferite. Această abordare lucrează bine la nivel de aplicații când sunt doar câteva tipuri de obiecte (altfel ar putea fi multe instanțe de fiecare tip). Această metodă poate fi folosită într-un cadru mai general aproximând toate cererile prin adaos la câteva valori predeterminate. De exemplu gestionarul de memorie poate aproxima toate cererile prin următoarea putere de 2 octeți (cu un minim de 64) și memorează liste pentru golurile de 64, 128, 256,…,etc. Presupunând că cea mai mare cerere poate fi de 1Mb aceasta cere doar 14 liste. Această abordare este folosită de cele mai multe implementări ale funcției malloc. Astfel se elimină complet fragmentarea externă dar fragmentarea internă poate fi chiar de 50% în cel mai rău caz (acesta apare când toate cererile sunt cu un octet mai mari de o putere a lui 2). O altă problemă a acestei metode este gruparea spațiilor libere adiacente. O posibilitate ar fi să nu facem această compactare. La inițializarea sistemului memoria este împărțită în blocuri libere de dimensiune fixă (de aceeași di libere de dimensiune fixă (de aceeași dimensiune sau de dimensiune variabilă). Fiecare cerere este satisfăcută cu un bloc potrivit astfel: dacă cererea este mai mică decât dimensiunea blocului liber este alocat întregul bloc. Când blocul este eliberat este pur și simplu întors în lista potrivită. Cele mai multe implementări ale funcției malloc folosesc o variantă a acestei metode (în unele implementări golurile sunt sparte dar nu mai sunt comasate la loc).
O metodă interesantă de a comasa blocurile libere când sunt mai multe liste de goluri este sistemul de camarazi (buddy system). Să presupunem că toate blocurile libere sau alocate au dimensiuni puteri ale lui 2 (deci cererile sunt întotdeauna aproximate cu următoarea putere a lui 2) și fiecare bloc liber sau ocupat începe la o adresă care este multiplu al dimensiunii sale. Atunci fiecare bloc are un “camarad” de aceeași dimensiune adiacent lui și astfel comasând un bloc de dimensiune 2n cu camaradul său se obține un bloc de dimensiune 2n+1 aliniat corespunzător. De exemplu blocurile de dimensiune 4 pot începe la adresele 0, 4, 8, 12, 16, 20 etc. Blocurile de la adresele 0 și 4 sunt camarazi; unindu-le vom obține un bloc începând la adresa 0 și de dimensiune 8. La fel blocurile de la adresele 8 și 12 și cele de la adresele 16 și 20 sunt camarazi. Blocurile de la adresele 4 și 8 nu sunt camarazi chiar dacă sunt vecine deoarece unindu-le obținem un bloc de dimensiune 8 începând la adresa 4, care nu este multiplu de 8. Adresa camaradului unui bloc poate fi calculată ușor făcând 1 al n–lea bit din dreapta din reprezentarea binară a adresei blocului (numărătoarea biților începe de la 0). De exemplu perechile de camarazi: (0,4), (8,12), (16,20) se reprezintă în binar (00000, 00100), (01000,01100), (10000,10100). În fiecare caz cele două adrese pereche diferă doar prin bitul de pe a treia poziție din dreapta (4=22). Pe scurt se poate găsi adresa camaradului unui bloc făcând XOR între adresa blocului și dimensiunea sa. Pentru a aloca un bloc de dimensiune dată întâi se aproximează dimensiunea cu următoarea putere a lui 2 și se caută în lista blocurilor de această dimensiune. Dacă lista este vidă se sparge un bloc din lista cu blocurile de dimensiune imediat următoare (dacă și această listă este vidă i se adaugă întâi două blocuri obținute din spargerea unui bloc din lista imediat următoare și tot așa). Când se eliberează un bloc, se verifică mai întâi dacă este liber camaradul său. Dacă da comasează blocul cu camaradul său și rezultă un bloc care va fi trecut în lista celor de dimensiune mai mare. La fel ca alocarea și dealocarea poate trece la liste cu blocuri de dimensiuni din ce în ce mai mari.
I.3 Compactarea și colectarea gunoaielor
Ce se întâmplă când nu este suficientă memorie? Toate aceste metode pot eșua deoarece toată memoria este alocată sau deoarece este prea mare fragmentarea. Malloc, care este folosit pentru a aloca segmentul de date al unui proces UNIX, renunță și face un apel de sistem (costisitor) pentru a mări segmentul de date. Un manager de memorie care alocă memorie fizică reală nu poate face acest lucru și alocarea eșuează. Sunt două metode de a evita acest pericol: compactarea și colectarea gunoaielor.
Compactarea încearcă să rezolve problema fragmentării mutând toate blocurile alocare la sfârșitul memoriei combinând astfel golurile din memorie. Pe lângă costul evident mare al tuturor acestor copieri mai există o limitare a compactării: orice pointer la un bloc trebuie să fie actualizat când un bloc este mutat. Dacă nu se pot găsi toți acești pointeri compactarea este imposibilă. Pointeri pot fi păstrați chiar în blocurile alocate, dar la fel de bine pot fi reținuți de clientul managerului de memorie. În unele situați pointerii pot indica nu numai spre începutul blocului ci și spre corpul lor. De exemplu dacă un bloc conține cod executabil o instrucțiune poate fi pointer spre altă locație din același bloc. Compactarea se face în trei faze. În prima se va calcula noua locație a fiecărui bloc pentru a determina distanța cu care va fi mutat blocul. Apoi fiecare pointer este actualizat adăgându-i-se distanța cu care este mutat blocul spre care pointează. În final blocul este efectiv mutat. Sunt mai multe posibilități de a combina aceste operații.
Prin colectarea gunoaielor se caută blocurile inaccesibile și sunt adăugate în lista blocurilor libere. La fel ac și compactare și colectarea gunoaielor presupune găsirea tuturor pointerilor la blocuri și din blocul însuși și din alte blocuri. Dacă acest lucru nu este posibil putem face totuși o colectare mai conservativă a gunoaielor în care fiecare cuvânt din memorie care conține o valoare ce pare a fi pointer este tratat drept pointer. Abordarea conservatoare poate da greș în colectare blocurilor “gunoaie” dar nu va colecta niciodată din greșeală blocuri accesibile. Sunt trei metode principale pentru colectarea gunoaielor: numărarea referințelor (reference count), marcare și ștergere (mark-and-sweep) și algoritmi pe generații.
Numărarea referințelor păstrează în fiecare bloc numărul pointerilor către acel bloc. Când contorul scade la zero blocul poate fi eliberat. Această abordare este practică atunci când există software de nivel înalt pentru a face numărarea referințelor (este mult prea greu să fie făcută din programe) și chiar și așa nu se vor detecta structurile ciclice. Să considerăm un ciclu de blocuri fiecare dintre acestea pointând doar spre predecesorul său din ciclu. Fiecare bloc are contorul referințelor 1 dar întregul ciclu este inaccesibil (gunoi).
Mark- and-sweep lucrează în două etape: întâi se marchează toate blocurile accesibile (non-garbage) făcând o căutare în adâncime începând cu fiecare din afara blocului.
void mark(Address b) {
mark block b;
for (fiecare pointer p din blocul b) {
if (blocul spre care pointează p nu este marcat)
mark(p);
}
}
Pasul al doilea trece prin toate blocurile și le returnează pe cele nemarcate în lista blocurilor libere. Pasul de ștergere face de asemenea o compactare după cum se va descrie în continuare. Sunt două probleme cu metoda mark-and-sweep. În primul rând dificultatea pasului de marcare este proporțională cu cantitatea de non- gunoaie. Astfel dacă memoria este aproape plină va fi foarte mult de lucru. Apoi pasul de marcare face multe salturi în memorie ceea ce este rău pentru memoria virtuală a sistemului după cum se va vedea.
O a treia metodă de colectare a gunoaielor este numită generational collection deci colectare pe generații. Memoria este împărțită în spații. Când un spațiu este ales pentru a fi colectat de colectorul de gunoaie toate referirile următoare la obiecte din acest spațiu fac ca obiectul să fie mutat într-un spațiu nou. După o vreme vechiul spațiu ori devine liber și poate fi returnat în lista blocurilor libere ori cel puțin devine atât de risipit încât o colectare mark-and-sweep va fi destul de puțin costisitoare. În mod empiric observăm că obiectele tind să aibă ori o viață foarte scurtă ori una foarte lungă. Cu alte cuvinte un obiect care a supraviețuit o vreme este foarte posibil că va mai supraviețui foarte mult timp. Alegând cu grijă locul unde mutăm obiectele atunci când sunt referite putem face în așa fel încât să avem un spațiu unde să se găsească doar obiecte cu viață lungă care este puțin probabil să devină gunoaie. Colectorul de gunoaie va prelua aceste spații rareori sau niciodată.
I.4 Suprapunere
Tehnica suprapunerii este un mijloc de folosire a unui spațiu de adresă fizică mai mic decât spațiul de adresă logică a codului sursă. Pentru aceasta programul este împărțit în module logice și subrutine. Doar acele subdiviziuni cerute pentru execuție la un moment de timp sunt încărcate. Există de asemenea un modul de control care va fi tot timpul în memorie. Restul modulelor vor fi alternativ în memorie și în afară după cum cere execuția programului. Când execuția cere ca altă subdiviziune să fie încărcată din memoria de rezervă sistemul de operare suprascrie una sau mai multe subdiviziuni neesențiale cu cea cerută. Dacă vreo subdiviziune ce trebuie evacuată a fost modificată în timpul execuției ea trebuie copiată înapoi în memoria secundară înainte de a fi suprascrisă.
Figura 2. Organizarea suprapunerilor
Considerăm exemplul unui asamblor în două treceri. Pe durata primei treceri se construiește o tabelă de simboluri, iar pe durata celei de-a doua treceri se generează cod în limbaj mașină. Gruparea instrucțiunilor se poate realiza astfel: codul asociat primei treceri (8K), codul asociat trecerii a II-a (10K), tabela de simboluri (14K) și rutinele utilizate în comun de ambele treceri (5K).
Încărcarea tuturor acestor elemente necesită 37K de memorie și dacă de exemplu nu avem la dispoziție decât 33K, programul nu va putea fi lansat în execuție. Putem scrie însă un driver de suprapuneri (2K) care să joace rolul modului de control. Programul va fi împărțit în 2 module: primul (29K) cuprinzând tabela de simboluri, rutinele comune și trecerea I și al doilea (31K) tabela de simboluri, rutinele comune și trecerea II. Astfel cererea maximă de memorie va fi de 33K deci programul va putea fi rulat.
Gestionarea suprapunerilor poate fi complicată și a lăsat locul memoriei virtuale. Cu tehnica suprapunerilor programatorul trebuie să gestioneze el însuși memoria, ce parte trebuie să fie în memoria principală la fiecare moment de timp, ce parte trebuie încărcată și cât timp să dureze fiecare operație de suprapunere, operații care ar fi mai eficient să fie realizate de către sistemul de operare.
I.5 Încărcarea dinamică
O tehnică asemănătoare este cea a înlănțuirii sau încărcării dinamice. Programatorul împarte programul în mai multe subprograme independente. Primul subprogram este încărcat și executat apoi următorul subprogram îl înlocuiește pe primul și este executat folosind datele oferite de primul subprogram. Acest ciclu este repetat până când ultimul subprogram este executat. Cheia acestui ciclu este de a păstra datele de la un subprogram la celălalt. În momentul în care se dorește apelarea unei rutine, se verifică mai întâi (cu ajutorul unor tabele de evidență) dacă ea se află în memorie. Dacă nu, se apelează un program specializat de încărcare cu relocatare și înlănțuire care aduce în memorie rutina apelată, reactualizează tabelele în scopul înregistrării acestei modificări și apoi cedează controlul noii rutine.
Dacă cum am văzut mai devreme tehnica suprapunerii cerea folosirea unui program de control iar segmentelor opționale li se făcea swap după cum era necesar. Înlănțuirea folosește o secvență de programe independente fiecare punând la dispoziție datele pentru programul următor.
I.6 Swapping
Când toate metodele eșuează și allocate eșuează. În cazul unei aplicații este mai simplu să se afișeze un mesaj de eroare și să se încheie execuția programului. Un sistem de operare trebuie însă să lucreze mai bine.
Gestionarea memoriei se face din dorința de a avea mai multe procese în memorie în același timp. Într-un sistem cu multiprogramare dacă sistemul de operare nu poate aloca memorie pentru a începe un nou job el poate amâna începerea jobului. Dacă există o coadă de joburi care așteaptă să fie executate sistemul poate căuta în jos în coadă un job mai mic care poate fi executat imediat. Această metodă crește utilizarea memoriei dar poate lăsa foarte mult să aștepte joburile mari. Situația este asemănătoare cu programarea CPU pe termen scurt unde SJF dă o utilizare optimă a CPU dar nu poate satisfece joburile mari. Aceeași metodă merge și aici: îmbătrânirea. Pe măsură ce un job așteaptă mai mult cu atât prioritatea sa crește până când sistemul de operare nu mai poate să îl ignore căutând un job sosit recent de dimensiune mai mică.
O alternativă pentru a evita lipsa memoriei este să se folosească o schemă de alocare a memoriei cu partiții fixate (porțiunile libere de memorie nu sunt sparte sau combinate). Presupunând că nici un job nu este mai mare decât cea mai mare partiție, nu vor mai exista joburi care să nu poată fi executate dacă de fiecare dată când o partiție este eliberată se începe primul job care este mai mic decât partiția. Mai avem încă o variantă asemănător cu diferența dintre first-fit și best fit. Desigur vrem să folosim cea mai potrivită partiție liberă pentru fiecare job (cea mai mică partiție liberă care este cel puțin la fel de mare ca dimensiunea jobului), dar să presupunem că următorul job în listă este mic și toate partițiile mici sunt deja folosite. Am prefera poate să întârziem începerea jobului și să căutăm în lista joburilor unul care ar folosi mai bine partiția care acum este liberă. Această politică reintroduce pericolul lipsei memoriei care este combătut prin îmbătrânire cum am descris mai sus.
Dacă discul este liber putem de asemenea transfera joburile blocate pe disc. Când un job se termină întâi se transferă înapoi joburile de pe disc înainte de a începe un nou job. Când un job este blocat (fie din cauza că vrea să facă de I/O fie din cauză că algoritmul de programare pe termen scurt al CPU obligă să se treacă la alt job) putem alege să îl lăsăm în memorie sau să îl transferăm pe disc. Un avantaj al acestei scheme este că mărește nivelul de multiprogramare (numărul joburilor aflate la un moment dat în memorie) chiar dacă crește (cu mult) costul interschimbării între joburi. Pentru rezolvarea acestei situații este potrivit un algoritm de programare al CPU cu cozi pentru nivelel de multiprogramare. Cozile sunt numerotate de la 0 la o valoare maximă. Când un job este gata de rulare el intră în coada 0. CPU rulează întotdeauna un job din coada nevidă cu cel mai mic număr (prioritatea se calculează prin înmulțirea cu –1 a numărului cozii). Acesta rulează un job pentru o anumită cuantă de timp. Dacă jobul nu se blochează și nu atinge această limită de timp el este adăugat la următoarea coadă.
Capitolul II Memoria virtuală
II. 1 Paginare
Cele mai multe calculatoare moderne au o unitate hardware specială numită “unitate de organizare a memoriei“ (MMU). Această unitate se găsește între CPU și unitatea de memorie. Când CPU vrea să acceseze memoria (când trebuie încărcată o instrucțiune sau trebuiesc depuse sau încărcate date), acesta trimite adresa de memorie dorită MMU care o transformă în altă adresă înainte de a o transmite unității de memorie. Adresa generată de CPU în urma indexărilor și altor operații aritmetice se numește adresă virtuală. Această adresă este translatată de MMU în adresa fizică.
Figura 3. Rolul MMU între memorie și CPU
În mod obișnuit translatarea se face la nivel de pagină. Fiecare pagină este de dimensiune o putere a lui 2 de obicei între 1024 și 8192 octeți. Dacă adresa virtuală p este tradusă în adresa fizică f (unde p este multiplu de dimensiunea paginii), atunci adresa p+o este tradusă în adresa fizică f+o pentru orice deplasament mai mic decât mărimea unei pagini. Cu alte cuvinte fiecare pagină este translatată într-o într-o regiune contiguă de memorie fizică numită cadru de pagină.
Figura 4. Translatarea adreselor de către MMU
MMU permite ca o regiune contiguă de memorie virtuală să fie translatată în cadre de pagină răspândite în memoria fizică ușurând sarcina sistemului de operare atunci când alocă memorie. Dar, mai important este că permite paginilor mai rar folosite să fie păstrate pe disc. Iată cum se întâmplă aceasta: Tabelele folosite de MMU au un bit de validitate pentru fiecare pagină din spațiu de adresă virtuală. Dacă acest bit este setat translatarea adresei virtuale într-o pagină decurge normal. Dacă nu orice încercare a CPU de accesa o adresă de pe acea pagină provoacă o întrerupere numită eroare de pagină (page fault trap). Sistemul de operare are un handler pentru fiecare fel de întrerupere. Sarcina acestui handler este să aducă pagina cerută în memorie. Mai detaliat, când este generată o eroare de pagină pentru pagina p1, handlerul întreruperii face următoarele:
Află unde este păstrat pe disc conținutul paginii p1. Sistemul de operare își păstrează informațiile într-o tabelă. Este posibil ca pagina respectivă să nu existe deloc în care caz referința la memorie este o eroare. În acest caz sistemul face câteva acțiuni de corectare a erorii cum ar fi omorârea procesului care a făcut referința (aceasta este cauza celebrului mesaj “memory fault – core dumped). Presupunând că pagina este pe disc :
găsește altă pagină p2 translatată într-un cadru f al memoriei fizice care nu este utilizat mult.
Copiază conținutul cadrului f pe disc.
Șterge bitul de validitate al paginii p2 astfel încât orice referire ulterioară la pagina p2 va crea o eroare de pagină.
Copiază datele din pagina p1 de pe disc în cadrul f.
Actualizeză tabelele MMU astfel încât pagina p1 să fie translatată în cadrul f.
Se întoarce din întrerupere permițând CPU să reia instrucțiunea care a provocat intreruperea.
II.1.1 Tabelele de pagină
Teoretic MMU conține un tabel de pagină care este un vector de intrări indexat de un număr de pagină. Fiecare intrare în pagină conține niște semafoare (precum bitul de validitate menționat anterior)
și un număr de cadru. Adresa fizică se formează prin concatenarea numărului de cadru cu deplasamentul care înseamnă primii biți ai adresei virtuale.
Figura 5. Formarea adresei fizice
Există două probleme legate de acest fel de abordare. În primul rând căutarea în tabelul de pagină trebuie să fie rapidă deoarece aceasta se efectuează pe fiecare referință de memorie, cel puțin o dată pentru fiecare instrucțiune executată ( pentru a aduce singură instrucțiunea ) și adesea de două sau mai multe ori pe instrucțiune. Astfel căutarea este efectuată întotdeauna de către un mecanism hardware specializat. Chiar și cu acest mecanism dacă tabela de pagină este păstrată în memorie căutarea în tabel face ca fiecare referință de memorie generată de CPU să provoace două referințe de memorie. Deoarece în cazul computerelor moderne viteza memoriei este adesea un obstacol (procesoarele au devenit atât de rapide încât consumă mare parte din timp așteptând memoria), memoria virtuală ar putea să facă programele să ruleze de două ori mai încet decât ar face-o fără ea. Vom analiza imediat cum putem evita această problemă. Dar mai întâi vom urmări întâi cealaltă problemă: tabele de pagină se pot mări.
Să presupunem că mărimea paginii este de 4Kb și adresa virtuală are o lungime de 32biți (acestea sunt valorile tipice pentru mașinile actuale). Atunci adresa virtuală ar trebui să fie împărțită într-un număr de pagini de 20 biți și un deplasament de 12biți (deoarece 212=4096=4K), astfel încât tabelul de pagină ar trebui să aibă 220=1.048.576 intrări. Dacă fiecare intrare ar avea o lungime de 4biți aceasta ar folosi 4Mb de memorie. În plus fiecare proces are propriul tabel de pagină. O astfel de mașină ar avea nevoie de un tabel de pagină cu 4.503.599.627.370.496 intrări!
Din fericire marea majoritate a intrărilor în tabelul de pagină sunt în mod normal marcate ca invalide. Cu toate că adresa virtuală poate avea 32biți lungime putând astfel să adreseze un spațiu de adresă virtuală de 4Gb, un proces obișnuit este cel mult de câțiva Mb mărime și fiecare Mb al memoriei virtuale folosește numai 256 intrări în tabelul de pagină (pentru 4K pagini).
La computerele actuale sunt folosite mai multe organizări diferite ale tabelelor de pagină. O variantă este punerea intrărilor în tabelul de pagină în registre speciale. Această variantă a fost folosită de minicomputerul PDP-11 introdus în anii ’70. Adresa virtuală era de 16 biți iar mărimea paginii era de 8K biți. Astfel adresa virtuală conținea 3 biți de număr de pagină și 13biți de deplasament pentru un total de pagini pe proces. Cele 8 intrări în tabelul de pagină au fost depozitate în registre speciale. [Ca o paranteză, niște adrese virtuale de 16biți înseamnă că orice proces ar putea să acceseze numai 64K biți de memorie. Chiar și pentru acea vreme era considerat prea puțin așa că versiunile ulterioare ale PDP-11 au folosit un artificiu. Fiecare referință de memorie generată de CPU avea un bit suplimentar care arăta dacă era o aducere de instrucțiune (I) sau o referință de date (D) permițând astfel 64K biți pentru program și 64K biți pentru date.] Punerea intrărilor în tabelul de pagină în regiștrii face ca MMU să ruleze mai repede (regiștrii erau mai rapizi decât memoria principală), dar această variantă are și o parte negativă. Regiștrii sunt costisitori așa că soluția este bună doar pentru tabele de pagină de dimensiuni reduse. De asemenea de fiecare dată când sistemul de operare vrea să interschimbe procesele trebuie să reîncarce registrele cu intrările în tabelul de pagină ale noului proces.
O a doua variantă este punerea tabelului de pagină în memoria principală. Adresa (fizică) a tabelului de pagină este păstrată într-un registru. Câmpul de pagină al adresei virtuale se adaugă la acest registru pentru a găsi intrarea în tabelul de pagină în memoria fizică. Această variantă are avantajul că interschimbarea proceselor este ușoară (tot ce trebuie făcut este să se schimbe conținutul unui registru) dar înseamnă că fiecare referință de memorie generată de CPU cere două drumuri la memorie. Poate folosi de asemenea prea multă memorie după cum am văzut mai sus.
O a treia variantă este punerea tabelului de pagină în memoria virtuală. Numărul de pagină extras din adresa virtuală este folosit ca adresă virtuală pentru a găsi intrarea în tabelul de pagină. Pentru a împiedica o recursie infinită această adresă virtuală este căutată folosindu-se un tabel de pagină stocat în memoria fizică. Ca exemplu concret să analizăm computerul VAX introdus la sfârșitul anilor ’70. Adresa virtuală la calculatoarele VAX este de 30 biți lungime cu pagini de 512 biți (probabil prea mici chiar și pentru acea vreme). Adresa virtuală este alcătuită dintr-un număr de pagină p de 21biți și un deplasament o de 9 biți. Numărul de pagină se înmulțește cu 4 (mărimea unei intrări în tabelul de pagină) și se adaugă conținutului registrului MMU ce include adresa tabelului de pagină. Aceasta dă o adresă virtuală care este rezolvată prin folosirea unui tabel de pagină în memoria fizică pentru a da un număr de cadre f1. Mai exact cei mai puțin semnificativi biți din p sunt indexați într-un tabel pentru a găsi un număr de cadru fizic care atunci când este concatenat cu biții mai semnificativi dau adresa fizică a unui cuvânt ce conține f. Concatenarea f cu o este adresa fizică dorită.
Figura 6. Memoria virtuală
După cum se vede un alt mod de a privi acești algoritmi este acela că adresa virtuală este împărțită în câmpuri care sunt folosite pentru a parcurge un arbore de tabele de pagină. Procesorul SPARC folosește o tehnică similară, dar care are un nivel în plus. Adresa virtuală de 32biți este împărțită în 3 câmpuri de index și un deplasament pe 12 biți. Rădăcina acestui arbore este îndreptată către o intrare într-un tabel de context care are câte o intrare pentru fiecare proces. Să luăm spre exemplu un proces VAX care folosește numai primul megabit al spațiului său de adresare (2048 pagini de 512 biți). Deoarece fiecare al doilea nivel al tabelului de pagină are 128 de intrări se vor folosi 16 dintre ele.
Adăugând la aceasta cei 64Kbiți necesari pentru tabelul de pagină de pe primul nivel spațiul total folosit pentru tabelele de pagină este de numai 72Kbiți față de cei 8Mbiți care ar fi necesari pentru un tabel de pagină cu un singur nivel. Dezavantajul este că fiecare nivel al tabelului de pagină adaugă o nouă căutare în memorie pentru fiecare referință generată de CPU.
O a patra variantă este folosirea așa numitului tabel de pagină inversat (de fapt primul computer cu memorie virtuală, Atlas proiectat în Anglia la sfârșitul anilor ’50 folosea această variantă așa că într-un fel toate tabelele de pagină descrise mai sus sunt inversate). Un tabel de pagină obișnuit are câte o intrare pentru fiecare pagină care conține adresa cadrului de pagină corespunzător (dacă există vreunul).
Un tabel de pagină inversat are o intrare pentru fiecare cadru de pagină care conține numărul de pagină corespunzător. Pentru a rezolva o adresă de pagină virtuală se caută în tabel o intrare care conține numărul de pagină. Avantajul este că un tabel de pagină inversat folosește numai o parte fixată din memorie. De exemplu dacă o pagină are 4Kb și o intrare în tabelul de pagină este de 4Kb vor fi exact 4biți de tabel de pagină pentru fiecare 4096biți de memorie fizică. Cu alte cuvinte mai puțin de 0,1% din memorie va fi folosită pentru tabele de pagină. Dezavantajul este că aceasta reprezintă de departe cea mai înceată dintre metode deoarece cere căutarea în tabelul de pagină pentru fiecare referință. Mașina Atlas originală avea un hardware special pentru a căuta în tabel în paralel, ceea ce era rezonabil deoarece tabelul avea numai 2048 de intrări.
Toate metodele analizate până acum pot fi făcute mai rapide prin folosirea unui artificiu numit “caching“. Vom observa mai multe exemple de caching folosit pentru a mări viteza proceselor. În acest caz mecanismul specific este numit “translation lookaside buffer“ (buffer de translatare) (TLB). Acest TLB conține un set de intrări, fiecare dintre acestea conținând un număr de pagină, numărul de cadru de pagină corespunzător și biții de protecție. Există un mecanism hardware special care să caute în TLB o intrare care să se potrivească cu un număr de pagină dat. Dacă TLB conține o intrare care se potrivește aceasta este găsită foarte rapid. Altfel avem de-a face cu o scăpare a TLB și trebuie să se recurgă la una dintre celelalte tehnici pentru a găsi translatarea. Totuși se poate lua translatarea găsită pe calea mai dificilă și să se pună în TLB pentru a o găsi mai repede data viitoare. TLB are o mărime limitată așa că pentru a adăuga o nouă intrare de obicei trebuie să se renunțe la o intrare mai veche. Tehnica obișnuită este să se elimine intrarea care nu a fost folosită cel mai mult timp. Această strategie numită înlocuirea LRU (least recently used) este de asemenea implementată în hardware. Motivul pentru care această variantă funcționează atât de bine este că cele mai multe programe consumă cea mai mare parte din timp prin accesarea repetată a unui set mic de pagini. De exemplu un program consumă adesea mult timp ciclând într-o singură procedură. Chiar dacă procedura respectivă, procedurile pe care le apelează, ș.a.m.d. ocupă peste 40Kb, 10 intrări TLB vor fi suficiente pentru a descrie toate aceste pagini și nu vor exista scăpări TLB dacă TLB-ul are cel puțin 10 intrări. Acest fenomen este denumit principiul de localitate. În practică procentul scăpărilor din TLB pentru referințele la instrucțiuni este foarte redus. Procentul scăpărilor pentru referințele la date este de asemenea redus dar poate varia mult pentru programe diferite. Dacă TLB operează destul de bine, aproape că nu contează cum sunt rezolvate scăpările TLB. Calculatoarele IBM Power PC și HP Spectrum folosesc tabele de pagină inversate organizate ca tabele de dispersie împreună cu TLB. Computerele MIPS renunță cu totul la tabelele de pagină hardware.
O scăpare TLB produce o întrerupere și ține de sistemul de operare ca acesta să caute în tabelul de pagină și să încarce intrarea corespunzătoare în TLB. Sistemul de operare folosește de obicei un tabel de pagină inversat implementat ca tabel de dispersie software.
Două procese pot traslata același număr de pagină către cadre de pagină diferite. Deoarece hardware-ul TLB caută o intrare prin numărul de pagină s-ar produce o confuzie dacă intrările corespunzând celor două procese s-ar afla în TLB în același timp.
Sunt două moduri de a rezolva această problemă. Unele sisteme elimină pur și simplu TLB-ul (stabilesc un bit în toate intrările marcându-le ca nefolosite) ori de câte ori interschimbă procesele. Acest lucru este foarte costisitor nu din cauza costului eliminării TLB-ului, ci din cauza scăpărilor TLB care se vor produce când noul proces va începe să ruleze. O variantă alternativă este de a adăuga un identificator de proces la fiecare intrare. Hardware-ul caută apoi în continuare să concateneze numărul de pagină și identificatorul procesului curent.
Am menționat mai înainte faptul că fiecare intrare în tabelul de pagină conține un bit de validitate și de asemenea alți biți. Acești alți biți includ:
Protecție Cel puțin un bit pentru a eticheta pagina ca read-only sau read/write. Câteodată sunt folosiți mai mulți biți pentru a arăta că pagina poate fi executată conform instrucțiunilor.
Modificare Acest bit numit de obicei “dirty bit“ este stabilit ori de câte ori pagina este adresată de o operație de scriere (stocare).
Referință Acest bit este de obicei stabilit ori de câte ori pagina este adresată pentru orice motiv, fie încărcare, fie stocare.
În următoarea secțiune vom vedea cum sunt folosiți acești biți.
II.1.2 Înlocuirea paginii
Toate aceste metode hardware pentru implementarea paginării au un lucru în comun: când CPU generează o adresă virtuală pentru care intrarea corespunzătoare în tabelul de pagină este marcată ca invalidă, MMU generează o întrerupere pentru eroarea de pagină iar sistemul de operare trebuie să rezolve eroarea după cum s-a explicat mai sus. Sistemul de operare verifică tabelele pentru a vedea de ce a marcat paginile ca invalide. Sunt cel puțin trei motive posibile:
Există un bug în programul care rulează. În acest caz sistemul de operare omoară programul (memory fault – core dumped“)
Unix tratează o referință aflată chiar în vârful stivei unui proces ca o cerere de creștere a stivei. În acest caz sistemul de operare alocă un cadru de pagină, îl șterge și actualizează tabelele de pagină MMU astfel încât numărul de pagină cerut pointează către cadrul alocat.
Pagina cerută se află pe disc, dar nu se află în memorie. În acest caz sistemul de operare alocă un cadru de pagină, copiază pagina de pe disc în cadru și actualizează tabelele de pagină ale MMU astfel ca numărul de pagină cerut să pointează către cadrul alocat.
În toate cazurile cu excepția primului sistemul de operare se confruntă cu problema alegerii unui cadru. Dacă există cadre nealocate alegerea este ușoară, dar acest caz este rar. Când memoria este folosită intens alegerea cadrului este vitală pentru o operare bună.
Vom analiza mai întâi algoritmii de înlocuire a paginii pentru un singur proces iar apoi algoritmii care trebuie folosiți în cazul unor procese multiple, toate concurând pentru aceeași mulțime de cadre.
II.1.3 Alocare de cadre pentru un singur proces
FIFO (First-in, first-out)
Se păstrează cadrele de pagină într-o coadă obișnuită, mutând un cadru la sfârșitul cozii când este încărcat cu o nouă pagină și se alege întotdeauna cadrul de la începutul cozii pentru a fi înlocuit. Cu alte cuvinte se folosește cadrul a cărui pagină a fost cel mai mult în memorie. Cu toate că acest algoritm pare rezonabil la prima vedere de fapt este cel mai rău. Problema este că o pagină care a fost în memorie mai mult timp ar putea fi folosită recent sau nefolosită în egală măsură. Dar FIFO le tratează în același fel. De fapt FIFO nu este mai bun și poate fi chiar mai slab decât RAND.
RAND (Random)
Alege la întâmplare un cadru. Acest algoritm este de asemenea destul de prost.
OPT (optimum)
Alege cadrul a cărui pagină nu va fi folosită cel mai mult timp în viitor. Dacă există în memorie o pagină care nu va mai folosită niciodată, cadrul acesteia este evident cea mai bună alegere pentru înlocuire. Altfel dacă de exemplu o pagină A va fi referită în 8 milioane de instrucțiuni și pagina B va fi referită de 6 milioane de instrucțiuni alege pagina A. Acest algoritm este uneori denumit algoritmul Belady după numele inventatorului său. Se poate demonstra că OPT este cel mai bun algoritm posibil în sensul că pentru orice șir de referințe (secvență de numere de pagină folosite de proces), OPT dă cel mai mic număr de erori de pagină. Din păcate OPT nu este implementabil pentru că cere cunoștințe despre viitor. Singura sa utilizare este teoretică. Dacă avem un algoritm care arată promițător îl vom compara cu OPT pe câteva șiruri de referințe de probă.
LRU (Least Recently Used)
Acest algoritm alege cadrul a cărui pagină nu a fost referită de cel mai mult timp. Ideea din spatele lui este că referințele de pagină nu sunt la întâmplare. Procesele tind să aibă câteva pagini foarte folosite pe care le adresează în mod repetat. Este probabil că o pagină care a fost adresată curând va fi adresată din nou în viitorul apropiat. Astfel LRU este posibil să aproximeze OPT.
LRU esteun algoritm destul de bun. Există două moduri de a găsi pagina cel mai puțin folosită recent. Unul este de a alcătui o listă. De fiecare dată când o pagină este adresată este mutată în capătul listei. Când se produce o eroare de pagină cadrul cel mai puțin folosit recent este cel de la coada listei.
Din păcate această abordare cere o listă de operații pe fiecare referință de memorie și chiar dacă este o listă de operații destul de simple nici nu intră în discuție efectuarea lor la fiecare referință chiar dacă aceasta s-ar face prin mijloace hardware. O alternativă este menținerea unui contor sau cronometru și stocarea contorului la fiecare referință într-o intrare în tabel pentru cea mai mică intrare. Această variantă cere căutarea în întreg tabelul la fiecare eroare de pagină, dar deoarece se așteaptă ca erorile de pagină să apară de zeci de mii de ori mai puțin frecvent decât referințele de memorie, aceasta nu reprezintă o problemă. O variantă mai bună a acestei scheme este să se mențină un vector de n biți inițializat cu 0, unde n este numărul cadrelor de pagină. În cazul unei referințe la pagina k mai întâi stabilește toți biții în șir de la k la 1 și apoi stabilește toți biții într-o coloană de la k la 0. Rezultă că dacă șirul k are cea mai mică valoare (când este tratat ca număr binar) atunci cadrul k este cel mai nefolosit recent.
Din păcate toate aceste tehnici cer mecanisme hardware și nimeni nu produce astfel de mecanisme hardware. Astfel LRU în formă pură este la fel de impracticabil ca OPT. Din fericire este posibil să se obțină o aproximare destul de bună a LRU (acesta fiind probabil motivul pentru care nimeni nu produce hardware care să sprijine LRU)
NRU (Not Recently Used)
Acesta constituie o formă de ajutor furnizată aproape întotdeauna de hardware. Fiecare intrare în tabelul de pagină are un bit de referință care este stabilit la 1 de către hardware ori de câte ori intrarea este folosită într-o translatare. Hardware-ul nu șterge niciodată acest bit, dar sitemul de operare software îl poate șterge oricând vrea. Cu NRU sistemul de operare programează întreruperi periodice ale cronometrului (să zicem o dată la fiecare milisecundă) și de fiecare dată trece prin tabelul de pagină și șterge toți biții de referință. În cazul unei erori de pagină sistemul de operare preferă cadrele ale căror biți de referință sunt încă șterși deoarece conțin pagini care nu au fost referite de la ultima întrerupere de ceas. Problema cu această tehnică este că dacă ultima întrerupere a cronometrului a fost recentă toți biții vor fi șterși și nu va mai rămâne nici un fel de informație care să distingă cadrele unele de altele.
SLRU (Sampled LRU)
Acest algoritm este asemănător cu NRU dar înainte ca bitul de referință pentru un cadru să fie curățat este salvat într-un contor asociat cu cadrul și menținut prin software de către sistemul de operare. O variantă este să se adauge bitul la contor. Cadrul cu cea mai mică valoare de contor va fi acela care a fost referit în cel mai mic număr de momente recente. Această variantă se numește NFU (Not Frequently Used). O variantă mai bună este să se transfere bitul în contor (de la dreapta). Cadrul care nu a fost adresat cele mai multe momente va fi asociat cu contorul care are cel mai mare număr de zerouri pe primele poziții. Astfel putem aproxima cel mai puțin folosit recent cadru prin selectarea cadrului care corespunde celei mai mici valori (în binar).( Aceasta va selecta cadrul care nu a fost referit cele mai multe momente și va decide în favoarea cadrului care nu a fost referit cel mai mult timp înainte de aceasta). Aceasta doar aproximează LRU din două motive: numai înregistrează dacă o pagină a fost adresată la vreun moment nu în ce perioadă din cuanta de timp a fost adresată și păstrează înregistrate doar cele mai recente n cuante de timp, unde n este numrul de biți din contor. Putem să obținem o aproximare apropiată de LRU cu prețul instabilității scurtând cuantele de timp și lungind foarte mult contorii.
II.1.4 A doua șansă
Când apare o eroare de pagină sunt analizate cadrele de pagină pe rând în ordinea adreselor fizice. Dacă bitul de referință este zero se alege cadrul pentru înlocuire. Dacă bitul de referință este setat i se dă cadrului o “a doua șansă“ anulând bitul său de referință și trecând la următorul cadru (trecând de mai multe ori de la cadrul zero până la ultimul din memorie). În cele din urmă un cadru cu bitul de referință zero trebuie să fie găsit deoarece în cel mai rău caz se va întoarce de unde a început. De fiecare dată când acest algoritm este apelat începe să caute de unde a rămas ultima dată. Acest algoritm este de obicei numit ceas deoarece cadrele pot fi vizualizate ca fiind în jurul unui ceas, cu locația curentă indicată de limba ceasului.
Am spus că dacă un cadru este selectat pentru înlocuire trebuie să copiem conținutul său pe disc. Evident, putem sări peste acest pas dacă acest cadru nu era folosit. Putem de asemenea sări acest pas dacă pagina este “curată“ aceasta însemnând că nu a fost modificată de când a fost citită în memorie. Cele mai multe MMU au un câte bit asociat fiecărei pagini care va reține dacă s-a scris sau nu pe pagina respectivă. Când MMU setează bitul de referință pentru o pagină setează de asemenea acest bit dacă referința este pentru scriere. Aproape toți algoritmii descriși pot fi modificați astfel încât să prefere paginile curate (pe care nu s-a scris) celorlalte. De exemplu o versiune de NRU preferă întotdeauna paginile nereferențiate celor referențiate și preferă paginile nescrise celor scrise. Algoritmul ceas sare cadrele cu bitul de referință sau cu acest bit de curățenie setat. Oricum când este întâlnit un cadru pe care s-a scris începe o operație de scriere pe disc pentru a elibera pagina.
Cu această modificare, trebuie să fim atenți să nu se intre într-un ciclu infinit. Dacă se face un circuit complet și nu se găsesc decât pagini scrise sistemul de operare așteaptă până când o pagină este curățată. Din fericire aceasta se întâmplă foarte rar. Este un fenomen ciudat numit anomalia Belady care apare în unii algoritmi. Să considerăm un șir de referințe (o secvență de numere de pagini) 0 1 2 3 0 1 4 0 1 2 3 4. Dacă folosim algoritmul FIFO cu trei cadre de pagini vom avea 9 erori de pagină, incluzând primele trei erori provocate în primele trei pagini, dar cu mai multă memorie (patru cadre de pagină) am avea mai multe erori.
II.1.5 Alocarea cadrelor pentru procese multiple
Până aici am presupus că este un singur proces activ. Când sunt mai multe procese active lucrurile se complică. Algoritmi care lucrează forte bine pentru un singur proces pot să nu funcționeze bine când se trece la mai multe procese. Algoritmul LRU dă rezultate foarte bune pentru un singur proces dar toți algoritmii buni pot fi văzuți ca aproximări ale LRU. O extensie imediată a algoritmului LRU pentru mai multe procese alege tot cadrul de pagină care nu a mai fost adresat de mult timp. Această idee nu este bună. Să considerăm un grup de două procese. Procesul A copiază date dintr-un fișier în altul în timp ce procesul B face un calcul pe o matrice de dimensiuni mari și folosește intensiv CPU. Oricând procesul A așteaptă o operație I/O el nu își mai adresează paginile. După o vreme procesul B îi fură toate paginile procesului A. Când A termină o operație I/O apare o serie de erori până când A își capătă paginile înapoi apoi calculează foarte puțin și apoi așteaptă o nouă operație de I/O.
Aici apar două probleme. Mai întâi, calculăm timpul trecut de la ultima referință incorectă la o pagină. Ideea LRU este “folosește sau pierzi“. Dacă un proces nu a referit o pagină mult timp se va considera că procesul nu are nevoie de această pagină și cadrul va fi refolosit în alte scopuri. Dar în sistemele cu multiprogramare pot exista două motive pentru care un proces nu folosește o pagină: deoarece este folosită de alt proces sau deoarece este blocată. Desigur un proces trebuie să fie penalizat pentru că nu folosește o pagină doar când este în curs de rulare. Pentru a ilustra mai bine acestea vom introduce noțiunea de timp virtual. Timpul virtual al unui proces reprezintă timpul cât a folosit CPU până în momentul curent. Putem să considerăm că fiecare proces are propriul său ceas care funcționează doar când procesul folosește CPU. Este ușor pentru CPU să contorizeze timpul virtual al proceselor. Când pornește un proces, CPU înregistrează timpul curent real. Când se produce o întrerupere, calculează dimensiunea procesului care tocmai s-a terminat și adună această valoare timpului virtual al procesului care rula. Există o implementare a LRU care să înregistreze ce proces deține fiecare pagină și înregistrează timpul virtual de când proprietarul ei nu a folosit-o. Astfel, când se alege o pagină pentru înlocuire trebuie ținută seama de diferența între timpul cât a rulat un program și timpul virtual curent virtual al proprietarului paginii. Așa ar trebui să funcționeze algoritmii care încearcă să aproximeze LRU.
Mai este o altă problemă cu LRU aplicat pentru mai multe procese. Procesul B care folosește mai mult CPU are nevoie de foarte pagini pe când procesul A care folosește mai mult operații I/O folosește foarte puține pagini. Chiar dacă folosim LRU și calculăm timpul virtual al proceselor procesul B poate totuși fura pagini procesului A. Dându-i procesului B posibilitate a de a avea mai multe pagini aceasta nu îl va ajuta să ruleze mai rapid dar luând de la procesul A pagini de care are nevoie l-ar putea afecta grav. Observăm că un algoritm ideal de înlocuire a paginii s-ar divide în două părți. Procesul A ar obține cât de multe pagini are nevoie iar B ar obține restul. Fiecare parte ar fi controlată separat de LRU. Atunci când pagina B comite o eroare acesta ar înlocui pagina cu partea care nu a fost adresată cel mai mult timp. În general fiecare proces are o mulțime de pagini pe care o folosește în mod activ. Această mulțime este denumită mulțimea de lucru a unui proces. Dacă unui proces nu i se alocă destulă memorie pentru a memora mulțimea sa de lucru acesta va provoca un număr excesiv de erori de pagină. Dar odată ce un proces are destule cadre pentru a memora mulțimea sa de lucru faptul că i s-ar da mai multă memorie nu ar avea nici un efect.
Figura 7. Rata erorilor de pagină în raport cu numărul de cadre de pagini alocate
Mai formal, dându-se un număr t, mulțimea de lucru cu parametrul t notată Wt este mulțimea paginilor folosite de proces în ultimele sale adresări de memorie. Din cauză că cele mai multe procese au un grad mare de localitate, mărimea lui t nu este foarte importantă dacă este destul de mare. O alegere obișnuită este numărul de instrucțiuni executate în ½ secunde. Cu alte cuvinte, vom considera mulțimea de lucru a unui proces ca fiind mulțimea paginilor folosite în ultima ½ secundă din timpul virtual. Modelul mulțimii de lucru spune că sistemul va rula eficient dacă fiecărui proces îi sunt date destule cadre de pagină pentru a-și păstra mulțimea de lucru. Dacă nu sunt destule cadre care să memoreze mulțimile de lucru ale tuturor proceselor atunci memoria este suprasolicitată și nu există nici o șansă să se ruleze toate procesele în mod eficient. Ar fi mai bine să oprim pur și simplu un proces și să dăm paginile sale altora.
Alt mod de a privi acest fenomen este să considerăm utilizarea CPU ca funcție de nivelul de multiprogramare (numărul de procese). Dacă avem prea puține procese nu putem ține CPU ocupat. Astfel am vrea ca mărind numărul de procese procentul de utilizare al CPU să crească eventual aproape de 100%. Practic, nu vom obține chiar așa mari performanțe dar se va obține totuși o îmbunătățire a performanțelor când vom adăuga mai multe procese.
Figura 8. Utilizarea reală și ideală CPU în funcție de nivelul de multiprogramare
Din păcate, dacă permitem ca memoria să fie suprasolicitată se poate întâmpla ceva foarte diferit:
Figura 9. Utilizarea CPU actuală în funcție de nivelul de multiprogramare.
Dincolo de o limită adăugarea mai multor procese nu va mai fi de folos deoarece acestea nu vor avea suficientă memorie să ruleze eficient. Acestea ar pierde foarte mult timp cu erorile de pagină în loc să execute ceea ce trebuie. De fapt aceste erori de pagină vor încetini atât de mult celelalte procese încât se va ajunge la un moment dat să nu se mai execute nimic și să se facă doar trafic pe disc. Acest fenomen se numește thrashing. Deci nu are rost să încercăm să rulăm mai multe procese decât au loc în memorie. Un proces “are loc în memorie“ dacă i-au fost alocate suficiente cadre de pagină pentru a-și păstra mulțimea de lucru. Ce se va întâmpla dacă avem mai multe procese decât încap în memorie? Într-un sistem cu sarcini (unde fiecare utilizator lansează o sarcină și așteaptă să fie rulată cândva în viitor) putem întârzia începerea unei noi sarcini până când va fi suficientă memorie pentru ea. Într-un sistem interactiv s-ar putea să nu avem această opțiune.
Utilizatorii pot lansa procese oricând doresc. Avem și opțiunea de a schimba planificarea oricând. Dacă vedem că sunt prea multe procese putem opri unul sau mai multe. Cadrele de pagină destinate acestor procese pot fi luate și date altor procese. Se spune de obicei că procesele au fost transferate din memorie prin analogie cu sistemul cu transfer (swapping) deoarece toate paginile proceselor oprite au fost mutate din memoria principală pe disc. Când se mai eliberează memorie (deoarece un proces și-a terminat execuția sau pentru că mulțimea sa de lucru a devenit mai mică) putem aduce din nou în memorie unul din procesele oprite. Putem să aducem explicit mulțimea sa de lucru înapoi în memorie făcând procesul rulabil. Acest lucru va aduce imediat mulțimea sa de lucru înapoi în memorie deoarece se provoacă o eroare de pagină. Acest control al numărului proceselor active se numește controlul încărcării proceselor sau programare pe termen mediu în contrast cu programarea pe termen lung care decide când să pornească un nou job și programarea pe termen scurt care determină cum alocă CPU resurse în timpul jobului activ.
Este esențial să amintim că acest control al încărcării proceselor este o componentă de bază al oricărui algoritm bun de înlocuire a paginii. Când apare o eroare de pagină vrem să luăm o decizie cât mai bună asupra paginii de înlocuit. Dar câteodată nici o decizie nu este foarte bună deoarece nu mai sunt suficiente cadre de pagină. Atunci este mai dine să decidem să rulăm doar câteva procese decât să ruleze toate greoi.
Acesta este un model foarte bun dar care nu se traduce imediat într-un algoritm. Au fost propuși mai mulți algoritmi. Ca și în cazul unui singur proces, unii algoritmi sunt teoretic foarte buni dar nu se pot implementa în timp ce alții foarte ușor de implementat nu sunt buni deloc. Ideea este să se găsească un compromis rezonabil.
II.1.6 Alocarea cu partiții fixate
Această metodă de alocare dă fiecărui proces un număr fix de cadre de pagină. Când apare o eroare de pagină se folosește LRU sau o aproximare a acestuia dar se consideră doar cadrele care aparțin procesului care a comis eroarea. Problema cu această abordare este că nu este întotdeauna evident câte pagini trebuiesc alocate fiecărui proces. Dacă îi vom da unui proces prea puține pagini se va ajunge la thrashing. Dacă îi dăm prea multe pagini cele suplimentare sunt irosite și ar putea fi mai bine folosite de alt proces sau ar putea fi pornit un nou job (într-un sistem cu joburi). În unele medii ar fi posibil să estimăm cererea de memorie a fiecărui job. De exemplu un sistem care lucrează în timp real tinde să ruleze o anumită mulțime de procese pentru mult timp. Caracteristicile fiecărui proces pot fi măsurate și se poate da fiecărui proces atâta memorie câtă îi este necesară. S-a încercat alocarea cu partiții fixate și pentru sistemule cu sarcini (batch). Fiecare utilizator i se cere să declare alocarea memoriei unui job atunci când îl lansează. Clientul plătește și pentru memoria alocată și pentru traficul I/O incluzând traficul cauzat de erorile de pagină. Ideea este că clientul este încurajat să declare mărimea optimă pentru jobul său. Din păcate chiar dacă presupunem bunăvoință din partea utilizatorului este destul de greu să se estimeze cererile de memorie pentru un job. Pe lângă aceasta mărimea mulțimii de lucru se poate schimba de-a lungul duratei job-ului.
II.1.7 Frecvența erorii de pagină (PFF)
Această metodă este asemănătoare alocării cu partiții fixate dar alocările sunt ajustate în mod dinamic. Sistemul de operare monitorizează continuu rata erorilor pentru fiecare proces în erori pe secundă în timp virtual. Dacă rata erorilor unui proces este prea mare fie i se dau mai multe pagini fie este transferat pe disc. Dacă rata erorilor este prea mică procesului i se mai iau pagini. Când se obțin suficiente pagini fie este pornit un nou job (în sistemele cu joburi) fie repornesc unele care au fost transferate pe disc. Această tehnică este folosit în unele sisteme existente. Problema o constituie alegerea alegerea pragului minim de erori și al celui maxim. Trebuie să se evite de asemenea instabilitatea sistemului atunci când unui proces i se fură mereu pagini și se poate ajunge la thrashing și să îi fie date paginile înapoi.
II.1.8 Mulțime de lucru
Algoritmul mulțimii de lucru (spre deosebire de modelul cu mulțime de lucru) este următorul: Se monitorizează continuu mulțimea de lucru (cum a fost definită mai devreme) a fiecărui proces. Când o pagină părăsește mulțimea de lucru și cadrul său este adăugat unei mulțimi de pagini libere. Când un proces generează o eroare de pagină i se alocă o pagină din un cadru din mulțimea paginilor libere. Dacă mulțimea devine vidă avem o situați de supraîncărcare–suma dimensiunilor mulțimilor de lucru ale proceselor active depășește dimensiunea memoriei fizice – astfel unul dintre procese este oprit. Problema este că algoritmul cu mulțime de lucru ca și LRU de altfel nu este implementabil. O pagină poate părăsi mulțimea de lucru a unui proces oricând astfel că acest algoritm cere ca mulțimea de lucru să fie monitorizată la fiecare adresare de memorie. Acest lucru nu se poate face prin metode software și nu este practic să se construiască mecanisme specializate pentru aceasta. Astfel toți algoritmii buni de paginare pentru procese multiple sunt aproximări ale WS.
II.2 Segmentare
Paginarea face ca memoria calculatorului să funcționeze mai eficient în mai multe moduri:
Dă fiecărui proces propria sa memorie virtuală care arată ca o versiune proprie a memoriei principale a calculatorului. În acest sens paginarea face pentru memorie ceea ce abstractizarea prin procese face pentru CPU. Chiar dacă în sistem există un singur procesor fiecare utilizator poate avea propriul său CPU virtual (de fapt un proces). La fel paginarea dă fiecărui proces propria sa memorie virtuală care este separată de memoria altor procese și protejată de acestea.
Fiecare memorie virtuală arată ca un șir de octeți a cărui adresă începe la 0. Acest lucru simplifică realocarea: fiecare program poate fi compilat presupunând că va începe de la adresa 0.
Aceasta face ca memoria să pară mai mare păstrând părțile mai puțin folosite mai bine în memoria virtuală decât în memoria principală. Acest lucru permite o mai bună împărțire a memoriei între procese și permite fiecărui proces să trateze memoria ca fiind nemărginită. Procesele nu trebuie să țină seama că anumite operații ar putea bloca CPU deoarece acesta poate rula alte procese în timp ce procesul inițial este în stare de așteptare. La fel se poate aloca memorie într-o zonă necontiguă deoarece sistemul de operare va aloca memorie reală doar părților din proces care rulează efectiv.
Segmentarea poate duce acest lucru mai departe permițând fiecărui proces să aibă mai multe simulări de memorie (segmente). Fiecare segment începe la adresa zero este independent și segmentele unui proces pot fi în pagini diferite. Într-un sistem cu segmentare o adresă are două părți: un număr de segment și un deplasament în cadrul segmentului. Cele mai multe sisteme folosesc segmentarea dar într-o versiune limitată. UNIX-ul folosește exact trei segmente pentru fiecare proces. Un segment (segmentul text) unde se află codul executabil al procesului. Acesta este în general read-only, de dimensiune fixată când începe să se execute procesul și împărțit de toate procesele care execută același program. Câteodată datele read-only sunt de asemenea plasate tot în acest segment. Alt segment (segmentul de date) păstrează memoria folosită pentru variabilele globale. El este read/write (se poate scrie și citi) dar nu și executabil și în mod normal nu este împărțit de procese.Există un apel sistem special pentru a crește dimensiunea segmentului de adate al unui proces. Al treilea segment este segmentul de stivă. După cum spune și numele, este folosit pentru stiva procesului pentru a păstra informații folosite la apelurile de proceduri și la întoarcerea din acestea la fel ca variabilele locale ale procedurilor. Ca și segmentul de date stiva este read /write dar de obicei nu și executabilă. Stiva este extinsă automat de sistemul de operare oricând procesul produce o eroare făcând referire la o adresă dincolo de dimensiunea actuală a stivei. Segmentul de date nu este împărțit de procese. Unele variante de UNIX au un al patrulea segment care conține structuri de date ale sistemului de operare. Acesta este read-only și împărțit de toate procesele.
Multe aplicații ar fi mai ușor de scris dacă ar putea avea atât de multe segmente câte ar dori. Un exemplu de asemenea program este un compilator. În plus față de segmentele text, de stivă și de date ar fi folositor și un segment pentru sursa programului de compilat, unul pentru tabela de simboluri etc. De exemplu multe programe în UNIX folosesc biblioteca printf . Dacă codul executabil pentru printf ar fi într-un segment separat acesta ar putea fi ușor împărțit de mai multe procese care împart memoria fizică.
Dacă privim adresa virtuală ca fiind concatenarea numărului segmentului cu deplasamentul segmentarea arată cam la fel ca paginarea. Principala diferență este că în aplicațiile programatorilor se ține seama de limitele segmentului dar se poate ignora faptul că spațiul de adresă este împărțit în pagini.
Implementarea segmentării este de asemenea la nivel superficial asemănătoare cu implementarea paginării. Numărul segmentului este folosit ca index într-o tabelă de descriptori de segment, fiecare dintre aceștia conținând lungimea și adresa de start a segmentului și informații despre protecția acestuia. Dacă deplasamentul segmentului nu este mai mic decât lungimea MMU tratează aceasta ca o violare a segmentului. Altfel deplasamentul segmentului se adună la adresa de start în descriptor pentru a obține adresa fizică. Sunt câteva diferențe între implementarea segmentării și a paginării care derivă din faptul că dimensiunea segmentului este variabilă iar cea a paginii este prestabilită. Dimensiunea segmentului este reținută în descriptorul segmentului și comparată cu deplasamentul. Dimensiunea unei pagini nu trebuie să fie reținută nicăieri deoarece este întotdeauna aceeași. Aceasta este întotdeauna o putere a lui 2 și pentru deplasamentul în pagină sunt întotdeauna suficienți biți astfel că este imposibil ca deplasamentul paginii să depășească limitele admise. De exemplu dacă pagina are 4K (4096 biți) deplasamentul paginii este reținut într-un câmp de 12 biți care poate conține numere doar între 0 și 4095.
Descriptorul segmentului conține adresa fizică a începutului segmentului. Deoarece toate cadrele de pagină trebuie să înceapă la o adresă care este multiplu de dimensiunea paginii, care este o putere a lui 2 biții mai puțin semnificativi ai adresei fizice a cadrului sunt totdeauna zero. De exemplu dacă paginile au 4Kb adresa fizică a fiecărui cadru de pagină se termină cu 12 zerouri. Astfel o intrare în tabela de pagină conține un număr de cadru care reprezintă doar cei mai semnificativi biți din adresa fizică a cadrului și MMU concatenează numărul cadrului cu deplasamentul paginii și adaugă adresa fizică a segmentului la deplasamentul acestuia.
II.2.1 Segmentarea în sistemul de operare MULTICS
Unul din avantajele segmentării este că fiecare segment poate fi mărit în mod dinamic. Pentru a avea acest efect va trebui să paginăm fiecare segment. O modalitate de a face aceasta este ca fiecare descriptor să conțină adresa fizică a tabelului de pagină pentru segment în loc să conțină chiar adresa segmentului. Acesta este modul de implementare al segmentării în Multics strămoșul sistemelor moderne de operare și primul care implementa segmentarea. Multics rula pe computere General Electric (sau mai târziu Honeywell) 635, care era o mașină cu 36 biți adresabili ceea ce înseamnă că memoria era împărțită în cuvinte de 36 biți și cuvintele consecutive difereau prin 1 (nu erau octeți). O adresă virtuală era de 36 biți cu cei mai semnificativi 18 biți interpretați ca număr de segment și cei mai puțin semnificativi 18 biți ca deplasament. 18 biți permit o dimensiune maximă de 218=262 144 cuvinte, iar prin metode software putem obține o dimensiune de segment maximă de 216 =65 536 cuvinte. Astfel deplasamentul segmentului este efectiv de 16 biți lungime. Fiecărui proces îi este asociat un tabel numit descriptor de segment și un registru indicând numărul intrărilor în descriptorul segmentului. Întâi numărul segmentului din adresa virtuală este folosit ca index pentru a afla descriptorul segmentului. (dacă numărul segmentului este prea mare apare o eroare). Descriptorul conține informații de protecție care sunt verificate pentru a se vedea dacă procesul curent are dreptul să acceseze segmentul conform cererii. Dacă această verificare se termină cu succes adresa din memorie a unui tabel de pagină pentru segment este găsită în descriptor. deoarece fiecare pagină este de 1024 octeți deplasamentul pe 16 biți este interpretat ca număr de pagină de 10 biți și deplasament în cadrul paginii de 10 biți. Numărul paginii este folosit ca index în tabelul de pagină pentru a obține intrarea conținând un număr de cadru cu bitul de validitate setat. Dacă bitul de validitate este setat adresa fizică a cuvântului căutat se află concatenând numărul cadrului cu deplasamentul de 10 biți din adresa virtuală.
Pentru a simplifica descrierea am lăsat la urmă un amănunt. Descriptorul de segment este și el un segment ceea ce înseamnă că este și el paginat ca orice alt segment. Există de asemenea și un tabel de pagină pentru descriptorul segmentului. Numărul segmentului din adresa virtuală format din 18 biți este împărțit într-un număr de pagină de 8 biți și un deplasament de 10 biți Numărul de pagină este folosit pentru a selecta o intrare din tabelul de pagină al segmentului descriptor. Acea intrare conține adresa (fizică) a paginii segmentului descriptor iar câmpul de deplasament al paginii al numărului de segment este folosit pentru a indexa acea pagină ca să obțină descriptorul. Restul translatării se petrece cum am descris în paragraful anterior. În total fiecare adresare de memorie face patru apeluri la memorie:
Una pentru a primi intrarea din tabelă pentru segmentul dorit.
Una pentru a primi chiar descriptorul
Una pentru a primi o intrare din tabelul de pagină pentru segmentul dorit
Una pentru a încărca sau depozita datele dorite.
Multics folosește o translatare a numărului de segment și al celui de pagină într-un cadru de pagină pentru a evita în cele mai multe din cazuri trei dintre aceste accese la memorie.
II.2.2 Intel x86
Microprocesoarele Intel 386 (și celelalte membre ale familiei x86 folosite pe calculatoare personale) folosesc o altă metodă de combinare a paginării cu segmentarea. O adresă virtuală constă dintr-un selector de segment pe 16 biți și un deplasament de segment pe 16 sau 32 biți. Selectorul este folosit pentru a aduce descriptorul segmentului dintr-o tabelă (de fapt sunt două tabele și unul din biții selectorului sunt folosiți pentru a alege tabela). Descriptorul pe 64 biți conține adresa segmentului pe 32 biți (numită baza segmentului) din care 21 biți indică lungimea sa și restul biților indicând protecția și alte opțiuni. Lungimea segmentului este dată de 20 biți (limita segmentului) plus unul care indică dacă limita este exprimată în octeți sau în pagini. Dacă deplasamentul din adresa virtuală originală nu depășește lungimea segmentului acesta este adăugat la bază pentru a obține adresa fizică numită adresă liniară. Dacă nu se face paginarea adresa liniară este chiar adresa fizică. Altfel, ea este translatată de un tabel de pagină pe două nivele cu adresa pe 32 biți în două numere de pagină de câte 10 biți și un deplasament pe 12 biți. (o pagină este de 4K pe acest tip de mașini).
Capitolul III.
Organizarea memoriei în sistemul de operare UNIX
Sistemul de management a memoriei decide ce proces ar trebui să se găsească (cel puțin parțial) în memoria principală și se ocupă de părțile procesului care sunt în memoria virtuală și nu sunt rezidente în memoria principală. Tot acesta monitorizează și cantitatea disponibilă de memorie principală și poate să scrie periodic procesele într-o memorie secundară numită spațiu de swap pentru a elibera spațiul din memoria principală. La un moment ulterior nucleul sistemului de operare aduce din nou datele din spațiul de swap înapoi în memoria principală.
La începuturi sistemul UNIX transfera întregul proces între memoria principală și spațiul de swap dar nu transfera părți separate ale unui proces cu excepția celor partajabile. O astfel de politică de organizare a memoriei se numește swapping. Era firesc să se implementeze această tehnică pe PDP11 unde dimensiunea maximă a unui proces era de 64Kb. Prin această tehnică dimensiunea unui proces este limitată de cantitatea de memorie fizică disponibilă în sistem. Sistemul BSD (versiunea 4.0) a fost prima implementare importantă a tehnicii de paginare la cerere transferând pagini de memorie în loc să transfere procese către și de la un mecanism secundar; Versiunile mai noi ale UNIX System V suportă de asemenea paginare la cerere. Astfel nu este necesar să se găsească întregul proces în memoria principală pentru a se executa ci nucleul încarcă pagini pentru un proces la cerere atunci când se face o referință la acele pagini. Avantajul tehnicii cu pagină la cerere este că permite o mai mare flexibilitate transferând printr-o funcție spațiul de adresă virtuală al unui proces în memoria fizică a unei mașini permițând de obicei ca dimensiunea unui proces să fie mai mare decât cantitatea de memorie fizică disponibilă și permițând să existe simultan mai multe procese în memoria principală. Avantajul swapping-ului este că este mai ușor de implementat și are ca rezultat o stabilitate mai mare a sistemului,
III.1 Swapping (transfer)
Sunt trei părți în descrierea algoritmului de transfer: gestionarea spațiului de swap, transferul proceselor afară din memoria principală și transferul proceselor în memoria principală.
III.1.1 Alocarea spațiului de swap
Spațiul de swap are o organizare la nivel de bloc și se găsește într-o secțiune a discului. În timp ce nucleul alocă spațiu pentru fișiere câte un bloc pe rând spațiul de swap îl alocă sub formă de grupuri contigue de blocuri. Spațiul alocat pentru fișiere este folosit static; deoarece fișierele există mult timp schema de alocare este flexibilă pentru a se reduce fragmentarea și de aici risipa de spațiu în sistemul de fișiere. Dar alocarea spațiului de swap este temporară depinzând de schema de programare a proceselor. Un proces care se găsește în spațiul de swap va fi transferat eventual înapoi în memoria principală eliberând spațiul pe care l-a ocupat pe discul de swap. Deoarece viteza este foarte importantă și sistemul poate face operațiile I/O mai rapid într-o operație multibloc decât în mai multe operații pe câte un bloc, nucleul alocă spațiul de swap contiguu fără a ține seama de fragmentare.
Din cauză că schema de alocare pentru spațiul de swap este diferită de schema de alocare pentru sistemul de fișiere și structurile de date care gestionează spațiul liber diferă. Nucleul păstrează spațiul liber pentru sistemul de fișiere într-o listă înlănțuită a blocurilor libere accesibilă din superblocul sistemului de fișiere, dar păstrează spațiul liber din zona de swap într-un tabel aflat în memoria principală numit harta memoriei. Hărțile folosite pentru alte resurse în afară de spațiul de swap permit alocare first fit a blocurilor contigue a unei resurse. O hartă este un vector unde fiecare intrare este alcătuită din adresa unei resurse alocabile și numărul de unități de resursă care sunt disponibile acolo. Inițial o hartă conține o intrare care indică adresa și numărul total de resurse. De exemplu nucleul tratează fiecare unitate a hărții de swap ca pe un grup de blocuri de pe disc și tratează adresa ca pe un deplasament de bloc de la începutul zonei de swap.
Algoritm pentru a aloca spațiul prin hărți:
Algoritm malloc /* alocă spațiul liber folosind hărți */
Input: (1) adresa hărții /* pentru a ști ce hartă se folosește */
(2) numărul de unități de resursă solicitat
Output : adresa, dacă s-a reușit alocarea
0, altfel
{
for ( fiecare intrare în hartă)
{
if (intrarea curentă poate să satisfacă cererea)
{
if (numărul de unități solicitate = =
numărul de unități din intrare)
șterge intrarea din hartă;
else
modifică adresa de start din intrare;
return (adresa originală a intrării)
}
}
return 0;
}
Pe măsură ce nucleul alocă și eliberează resursele actualizează harta astfel încât aceasta să conțină informații valabile despre resursele libere. După cum vedem în algoritm nucleul caută în hartă prima intrare care conține suficient spațiu pentru a răspunde cererii. Dacă cererea consumă toate resursele unei intrări în hartă nucleul elimină intrarea din vector și condensează harta (adică harta are cu o intrare mai puțin). Altfel ajustează adresa și câmpul ce dă numărul unităților din intrare în conformitate cu cantitatea de resurse alocate.
Figura 10 arată secvența de configurații a hărții de swap după alocarea a 100 unități, 50 unități și apoi 100 de unități din nou. Nucleul ajustează harta de swap pentru a se vedea că primele 250 unități au fost alocate și că acum conține 9750 unități libere începând de la adresa 251.
Adrese nr. unități adrese nr. unități
Adrese nr. unități adrese nr. unități
Figura 10. Alocarea spațiului de swap
La eliberarea resurselor nucleul găsește pozițiile lor potrivite pe hartă prin adresă. Sunt posibile 3 cazuri:
Resursele eliberate umplu în totalitate un gol din hartă; ele sunt contigue cu intrările ale căror adrese le preced imediat și cele care urmează după ele în hartă. În acest caz nucleul combină resursele proaspăt eliberate și cele două intrări existente într-o singură intrare în hartă.
Resursele eliberate umplu parțial un gol în hartă. Dacă adresele resurselor eliberate sunt contigue cu intrarea în hartă care le precede imediat sau cu intrarea care urmează imediat după ele dar nu cu amândouă, nucleul ajustează adresa și unește câmpurile intrării respective pentru a completa resursele eliberate. Numărul intrărilor în hartă rămâne același.
Resursele eliberate umplu parțial un gol dar nu sunt contigue cu nici o resursă din hartă. Nucleul creează o nouă intrare pentru hartă și o introduce în poziția potrivită.
Întorcându-ne la exemplul anterior, dacă nucleul eliberează 50 unități ale resursei swap pornind de la adresa 101, harta de swap conține o nouă intrare pentru resursele eliberate, deoarece resursele înapoiate nu sunt contigue cu intrările în hartă existente. Dacă nucleul eliberează apoi 100 unități de spațiu de swap pornind de la adresa 1 ajustează prima intrare a hărții de swap deoarece resursele eliberate sunt contigue cu acelea din prima intrare. Figura 11 arată secvența configurațiilor hărții de swap care corespund acelor evenimente.
Adresă nr. unități adresă nr. unități
Adresă nr .unități
Figura 11. Eliberarea spațiului de swap
Să presupunem că nucleul cere acum 200 unități de spațiu de swap. Deoarece prima intrare în harta spațiului de swap conține numai 150 unități nucleul satisface cererea din a doua intrare.
În fine să presupunem că nucleul eliberează 350 unități de swap pornind de la adresa 151. Cu toate că cele 350 unități au fost alocate separat nu există nici un motiv pentru care nucleul să nu le poată elibera deodată. Deoarece resursele eliberate se potrivesc exact în golul dintre prima și a doua intrare în harta spațiului de swap nucleul creează o singură intrare pentru primele două și resursele eliberate. Implementările tradiționale ale sistemului UNIX foloseau un singur spațiu de swap dar cele mai noi implementări System V permit existența mai multor discuri de swap (regiuni de disc). Nucleul alege discul de swap printr-o schemă round robin dacă conține destulă memorie contiguă. Administratorii de sistem pot crea și elimina în mod dinamic discurile de swap. Dacă un disc de swap este eliminat nucleul nu îi transferă date. Pe măsură ce datele sunt transferate din el se golește până ce este liber și poate fi eliminat.
III.1.2 Transferarea proceselor din memoria principală
Nucleul transferă un proces afară din memoria principală dacă are nevoie de spațiu în memorie ceea ce se poate întâmpla în următoarele cazuri:
Apelul sistem fork trebuie să aloce spațiu pentru un proces fiu.
Apelul sistem brk mărește dimensiunea unui proces.
Un proces devine mai mare prin creșterea normală a stivei.
Nucleul vrea să elibereze spațiu în memorie pentru procesele pe car le-a transferat afară și acum trebuiesc transferate înapoi în memoria principală.
Instrucțiunea fork se remarcă prin faptul că este singurul caz în care memoria internă ocupată anterior de proces nu este abandonată.
Când nucleul decide că un proces poate fi ales pentru transfer din memoria principală, decrementează contorul de referințe al fiecărei regiuni din proces și transferă regiunea afară dacă contorul său este zero. Nucleul alocă spațiu pe un disc de swap și blochează procesul în memorie (pentru cazurile 1-3) prevenind transferul lui afară în timp ce operația de transfer curentă este în derulare. Nucleul salvează adresa de pe discul de swap a regiunii într-o intrare în tabela regiunilor. Programul responsabil de swap pe care îl vom numi în continuare swapper așteaptă ca fiecare operație I/O să fie completă înainte de a transfera alte date.
Nu este necesar ca nucleul să scrie întregul spațiu de adresă virtuală al unui proces pe un disc de swap. În loc de aceasta copiază memoria fizică alocată unui proces pe spațiul de swap alocat de swapper ignorând adresele virtuale. Când nucleul transferă procesul înapoi în memorie cunoaște harta adreselor virtuale ale procesului așa că poate să realoce procesul la adresele virtuale corecte. Nucleul transferă o copie suplimentară dintr-un buffer de date în memoria fizică citind datele din locațiile memoriei fizice care au fost anterior planificate conform cu locațiile adresei virtuale
Teoretic toată memoria ocupată de un proces incluzând “u area” și stiva nucleului poate fi transferată cu toate că nucleul poate bloca o regiune în memorie în timp ce o operație critică este în curs de desfășurare. Cu toate acestea în practică implementările nucleului nu transferă “u area” dacă aceasta conține tabelele cu adresele de translatare pentru procesul respectiv. În funcție de implementare un proces poate să se transfere pe sine afară din memorie sau un alt proces să îl elimine.
1.2.1 Transferul în cazul apelului sistem fork
În cazul apelului de sistem fork se presupune că procesul părinte găsește destulă memorie pentru a crea un context fiu. Altfel nucleul transferă procesul fără a elibera memoria ocupată de copia din memoria principală. Când transferul este complet procesul fiu se află pe discul de swap. Părintele plasează fiul în starea “gata de rulare” și se întoarce la modul utilizator. Deoarece fiul este în starea “gata de rulare” swapperul îl va transfera eventual în memorie unde nucleul îl va programa. Fiul își va îndeplini rolul în apelul sistem fork și se va întoarce în modul utilizator.
1.2.2 Transferul extins
Dacă un proces cere mai multă memorie fizică decât îi este în mod curent alocată ca rezultat al creșterii stivei utilizator sau al invocării apelului de sistem brk și dacă necesită mai multă memorie decât este disponibilă nucleul procedează la un transfer extins al procesului. El își rezervă destul spațiu pe discul de swap pentru a conține spațiul de memorie al procesului incluzând spațiul nou cerut. Apoi ajustează harta de swap a adreselor procesului dar nu alocă memorie fizică (deoarece nu mai este disponibilă). În final transferă procesul din memorie printr-o operație normală de transfer marcând ca disponibil spațiul nou alocat pe discul de swap. Când nucleul transferă procesul înapoi în memorie va aloca memoria fizică în conformitate cu noua hartă de translatare a adresei (extinsă). Când procesul își reia execuția va avea memorie suficientă.
III.1.3 Transferul proceselor în memoria principală
Procesul 0, swapperul este singurul proces care poate transfera procese în memorie de pe discul de swap. După inițializarea sistemului swapperul intră într-un ciclu infinit unde singura sa sarcină este să realizeze transferul proceselor. El transferă procesele în memorie de pe discul de swap și le transferă de pe discul de swap în memorie dacă are nevoie de spațiu în memoria principală. Swapperul trece în starea de așteptare dacă nu are nimic de făcut (de exemplu dacă nu este nici un proces de adus în memorie) sau dacă nu poate să facă nimic (nici un proces nu poate fi transferat pe discul de swap). Nucleul îl activează periodic așa cum vom vedea. Nucleul programează swapperul așa cum programează orice proces dar swapperul lucrează doar în mod nucleu. Swapperul nu face nici un apel sistem dar folosește funcțiile interne ale nucleului pentru a face transferul; acesta este arhetipul unui proces nucleu.
Ceasul sistemului măsoară timpul în care fiecare proces a fost în memorie sau pe discul de swap. Când swapperul trebuie să transfere un proces în memorie examinează toate procesele care sunt în starea ’’gata de rulare’’ și selectează dintre acestea pe cel care a stat cel mai mult timp pe discul de swap. Dacă este destulă memorie liberă swapperul transferă procesul în memorie realizând inversa operației de eliminare din memorie. El alocă memoria fizică, citește procesul de pe discul de swap și eliberează spațiul de swap.
Dacă swapperul reușește să aducă în memorie un proces el caută în mulțimea proceselor ’’gata de rulare’’ alte procese pentru a le aduce în memoria principală și repetă procedura. Aici poate apărea una din următoarele situații:
Nu există nici u proces în starea “gata de rulare“ pe discul de swap: Swapperul trece din nou în starea de așteptare până când un proces de pe discul de swap este gata de rulare sau până nucleul elimină un proces care este “gata de rulare“.
Swapperul găsește un proces potrivit pentru a fi adus în memoria principală dar sistemul nu are suficientă memorie: Swapperul încearcă să elimine alt proces și dacă reușește repornește algoritmul căutând un proces pentru transfer în memorie.
Dacă swapperul trebuie să transfere un proces din memorie cercetează fiecare proces din memorie: procesele zombie nu sunt eliminate deoarece ele nu consumă memorie fizică; procesele blocate în memorie nu sunt nici ele eliminate. Nucleul elimină mai degrabă procesele în stare de așteptare decât cele “gata de rulare“ deoarece ultimele au șanse mai mari de a fi programate curând. Alegerea pentru eliminare a proceselor în stare de așteptare se face în funcție de prioritatea procesului și de timpul cât a stat acesta în memorie. Dacă nu sunt procese în stare de așteptare în memorie alegerea procesului gata de rulare pentru transfer este funcție de valoarea “nice“ a procesului și de timpul cât a stat acesta în memorie.
Algoritm pentru swapper /* transfera in memorie procesele evacuate
* elimina alte procese pentru a face loc */
input: nimic
output: nimic
{
loop:
for ( toate procesele evacuate care sunt gata de rulare)
alege procesul evacuat de cel mai mult timp;
if (nu exista un astfel de proces)
{
sleep (pana apare un astfel de proces)
goto loop;
}
if (este loc suficient in memoria principala pentru proces)
{
transfera procesul in memorie;
goto loop;
}
/* loop 2*/
for (toate procesele in afara de cele zombie si de cele blocate in memorie)
{
if (exista un proces in stare de asteptare)
alege procesul pentru care prioritatea + timpul petrecut in memorie e cel mai mare;
else /* nu este nici un proces in tare de asteptare*/
alege procesul pentru care timpul petrecut in memorie + valoarea nice
este cea mai mare
}
if (nici un proces nu indeplineste conditiile cerute)
sleep (pana va apare un astfel de proces);
else
evacueaza procesul din memorie;
goto loop;
}
Un proces gata de rulare trebuie să fie în memorie de cel puțin 2 secunde înainte de a fi eliminat și trebuie să fi fost eliminat de cel puțin 2 secunde înainte de a fi readus în memorie. Dacă swapperul nu găsește nici un proces de eliminat și nici unul de adus în memorie sau procesul evacuat nu a acumulat mai mult de 2 secunde atunci swapperul trece în starea de așteptare dacă nu are loc să aducă nici un proces. Ceasul va trezi swapperul după o secundă. De asemenea nucleul activează swapperul dacă alt proces trece în starea de așteptare deoarece acesta poate fi mai potrivit pentru transfer decât procesul desemnat anterior.
Dacă swapperul transferă din memorie un proces sau dacă este în stare de așteptare deoarece nu poate să transfere nici un proces din memorie își va relua activitatea de la începutul algoritmului de swap încercând să transfere un proces.
Swapperul alege procesele pentru transfer în memoria principală pe baza perioadei de timp cât procesele au fost pe discul de swap. Alt criteriu ar putea fi să transfere în memorie procesele cu cea mai mare prioritate care sunt gata de rulare deoarece aceste procese au șanse mai bune să se execute. S-a demonstrat că această strategie are ca rezultat încetinirea sistemului la sarcini mai grele.
Algoritmul pentru alegerea unui proces pentru transfer din memorie pentru a elibera memorie are câteva dezavantaje serioase.
În primul rând swapperul transferă un proces din memorie în funcție de prioritatea sa, de timpul petrecut în memorie și de valoarea sa “nice“. Cu toate că transferă afară un proces pentru a face loc altui proces el poate să transfere un proces care nu furnizează suficientă memorie pentru procesul de transferat în memorie. De exemplu dacă swapperul încearcă să transfere un proces care ocupă 1Mb de memorie și sistemul nu dispune de memorie liberă nu are rost să elimine un proces care ocupă numai 2Kb de memorie. O alternativă ar fi să elimine grupuri de procese dar numai dacă acestea eliberează suficientă memorie pentru procesul ce trebuie adus în memorie. Experimentele folosind un computer PDP 11/23 au arătat că o asemenea strategie ar putea crește rezultatele sistemului cu circa 10% la o solicitare mare.
Apoi swapperul trece în așteptare deoarece nu găsește memorie suficientă să aducă în memorie un proces, caută din nou în un proces pentru a-l transfera în memorie cu toate că alesese deja unul. Motivul este că celelalte procese transferate anterior pe discul de swap ar fi putut fi activate și să fie mai potrivite pentru a fi aduse în memorie decât cel desemnat la momentul anterior Dar acesta este un avantaj prea mic față de faptul că procesul original încă încearcă să fie transferat din memorie. În unele implementări swapperul încearcă să transfere din memorie mai multe procese mai mici pentru a face loc unui proces mai mare să fie transferat în memorie înainte de a căuta alte procese ce ar putea fi aduse în memorie în afară de cel mare.
În al treilea rând alege un proces “gata de rulare“ pentru a fi eliminat; este posibil ca procesul să nu se fi executat de când a fost adus în memorie. Asemenea situații nu sunt de dorit.
Un ultim pericol ce trebuie menționat este următorul : Dacă swapperul încearcă să elimină un proces dar nu are spațiu pe discul de swap poate apărea o blocare a sistemului dacă următoarele 4 condiții sunt îndeplinite: toate procesele din memoria principală sunt în stare de așteptare, toate procesele gata de rulare sunt pe discul de swap, nu mai este loc pe discul de swap pentru procese noi și nu este spațiu nici în memoria principală pentru a aduce procese. Interesul de a rezolva problemele apar în swapping a scăzut în ultimii ani când au fot implementați algoritmii de paginare la cerere în sistemele UNIX.
III.2 Pagină la cerere
Mașinile a căror arhitectură a memoriei nu se bazează pe pagini și al căror CPU are instrucțiuni de repornire pot sprijini un nucleu care implementează un algoritm de pagină la cerere, transferând paginile de memorie între memoria principală și discul de swap. Sistemele cu pagină la cerere eliberează procesele de limitările mărimii care sunt altfel impuse prin cantitatea de memorie fizică disponibilă pe o mașină. Nucleul încă mai impune o limită asupra mărimii virtuale a unui proces în funcție de cantitatea de memorie virtuală pe care mașina o poate adresa. Deoarece un proces poate să nu aibă loc în memoria fizică nucleul trebuie să încarce în mod dinamic în memorie porțiunile relevante ale acestuia și să îl execute chiar dacă alte părți nu sunt încărcate. Pagina la cerere este transparentă pentru programele utilizatorilor cu excepția mărimii virtuale care este permisă unui proces.
Procesele tind să execute instrucțiunile în porțiuni mici ale spațiului lor de text ca părțile repetitive din program și subrutine iar referințele lor la date tind să se grupeze în submulțimi mici ale spațiului total de date al procesului. Acest lucru este cunoscut drept principiul de localitate. Denning a formalizat noțiunea de mulțime de lucru (working set) a unui proces care înseamnă mulțimea paginilor la care procesul s-a referit în ultimele n adresări ale memoriei. Numărul n este numit fereastra mulțimii de lucru. Deoarece fereastra de lucru este o componentă dintr-un întreg proces mai multe procese pot încăpea simultan în memoria principală decât în decât în sistemul de swapping mărind potențial rezultatele sistemului datorită traficului redus de swapping. Când un proces adresează o pagină care nu este în mulțimea sa de lucru creează o eroare de pagină. Pentru a rezolva eroarea nucleul actualizează mulțimea de lucru citind din paginile de pe un mecanism secundar dacă acest lucru este necesar. Pe măsură ce procesul este executat mulțimea sa de lucru se schimbă în funcție de modelul referințelor de memorie pe care le face un proces. O fereastră mai mare produce o mulțime de lucru mai mare aceasta însemnând că un proces nu va mai avea erori de pagină atât de des.
Nu este practic să se implementeze un model pur de mulțime de lucru pentru că presupune costuri prea mari pentru a ține minte ordinea adresărilor de pagină. În loc de aceasta sistemele construiesc cu aproximație un model de mulțime de lucru setând un bit de adresare ori de câte ori un proces adresează o pagină sau luând periodic probe din adresările de memorie: dacă o pagină a fost adresată recent ea face parte dintr-o mulțime de lucru, dacă nu, “imbătrânește în memorie“ până ce devine potrivită pentru transferare.
Când un proces accesează o pagină care nu face parte din mulțimea sa de lucru creează o eroare de validitate de pagină. Nucleul oprește executarea procesului până ce citește pagina în memorie și o face accesibilă procesului. Când pagina este încărcată în memorie procesul reîncepe instrucțiunea pe care o executa când a apărut eroarea. Astfel implementarea unui subsistem de paginare are două părți: transferul paginilor rar folosite pe un disc de swap și rezolvarea erorilor de pagină. Această descriere generală a schemelor de paginare se extinde și la sistemele non-UNIX. Restul acestui capitol examinează în detaliu schema de paginare pentru UNIX System V.
III.2.1 Structuri de date pentru paginarea la cerere
Nucleul conține 4 structuri majore de date care sprijină funcțiile low-level de gestionare a memoriei și paginare la cerere: intrările tabelelor de pagină, descriptorii blocurilor de disc, tabelele de date pentru cadrele de pagină (pe scurt denumite pfdata) și tabelele de folosire a spațiului de swap. Nucleul alocă spațiu pentru tabelul pfdata odată pentru toată durata sistemului dar alocă pagini de memorie pentru celelalte structuri în mod dinamic.
O regiune conține tabelele de pagină pentru a accesa memoria fizică fiecare. Fiecare intrare într-un tabel de pagină conține adresa fizică a paginii, biții de protecție (care arată dacă procesul poate citi, scrie sau executa din pagina respectivă) și următoarele câmpuri de biți pentru a sprijini paginarea la cerere:
Valid
Referință (adresare)
Modificare
Copiere
Vârstă
Nucleul activează bitul de validitate pentru a indica faptul că conținutul paginii este valid dar adresarea paginii nu este în mod necesar invalidă dacă bitul de validitate nu este activat după cum se va vedea. Bitul de adresare arată dacă un proces a adresat recent o pagină iar bitul de modificare arată dacă un proces a modificat recent conținutul unei pagini. Bitul de copiere folosit în apelul de sistem fork indică faptul că nucleul trebuie să creeze o nouă copie a paginii când un proces modifică conținutul acesteia. În sfârșit nucleul folosește biții de vârstă pentru a indica cât timp o pagină a aparținut de mulțimea de lucru a unui proces. Secțiunea 2.4 va trata tipul de hardware care nu are astfel de capacități. Fiecare intrare în tabelul de pagină este asociată cu un descriptor al blocului de disc care descrie copia pe disc a unei pagini virtuale. Prin urmare procesele care își împart o regiune accesează intrările în tabelele de pagină comune și descriptorii blocurilor de disc.
Conținutul unei pagini virtuale se află într-un anumit bloc de pe discul de swap într-un fișier executabil sau nu se află pe discul de swap. Dacă pagina este pe un disc de swap descriptorul de disc conține numărul de disc logic și numărul de bloc care include conținutul unei pagini. Dacă pagina este inclusă într-un fișier executabil descriptorul blocului de disc conține numărul blocului logic în care se află pagina. Nucleul poate transfera acest număr rapid la adresa lui de pe disc. Descriptorul blocului de disc indică de asemenea 2 condiții speciale stabilite în timpul apelului sistem “exec“: o pagină este “demand fill“ sau este “demand zero“. Secțiunea 2.1.2 va explica aceste condiții. Tabelul pfdata descrie fiecare pagină a memoriei fizice și este indexat printr-un număr de pagină. Câmpurile unei intrări sunt:
Starea paginii, care indică faptul că o pagină este pe un disc de swap sau într-un fișier executabil, că DMA este în desfășurare pentru pagină (citește de pe un disc de swap) sau că pagina poate fi realocată.
Numărul proceselor care adresează pagina. Contorul de adresare este egal cu numărul de intrări valide în tabelul de pagină care adresează pagina. Acest număr poate fi diferit de numărul proceselor care își împart regiunile ce conțin pagina după cum va fi descris mai jos atunci când algoritmul pentru apelul de sistem fork va fi reanalizat.
Mecanismul logic (spațiul de swap sau sistemul de fișiere) și numărul de bloc care conține o copie a paginilor.
Pointeri către alte intrări în tabelele pfdata pe o listă a paginilor libere și pe o coadă de dispersie a pagilor.
Nucleul înlănțuie intrările tabelului pfdata într-o listă a paginilor libere și o listă de dispersie. Lista paginilor libere este un cache de pagini care sunt disponibile pentru realocare dar un proces poate greși o adresă și totuși să găsească pagina corespunzătoare pe lista liberă. Lista pagilor libere permite astfel nucleului să evite operațiunile de citire de pe discul de swap care nu sunt necesare. Nucleul alocă pagini noi din listă în ordinea celor mai puțin folosite. Nucleul împrăștie de asemenea intrările în tabelul pfdata conform cu numărul discului lor de swap și cu numărul de bloc. Astfel dându-se un disc de swap și un număr de bloc nucleul poate localiza imediat o pagină dacă aceasta se găsește în memorie. Pentru a aloca o pagină fizică într-o regiune nucleul înlătură o intrare liberă în cadrul de pagină din capătul listei libere, actualizează discul de swap și numerele de bloc și o așează în coada de dispersie corectă.
Tabelul de folosire al spațiului de swap conține o intrare pentru fiecare pagină de pe discul de swap. Intrarea constă într-un contor care arată cât de multe intrări din tabelul de pagină pointează către o pagină de pe discul de swap.
III.2.1.1 Apelul de sistem fork în sistemul de paginare
Nucleul duplică fiecare regiune a procesului părinte în timpul apelului de sistem fork și îl atașează procesului fiu. În mod tradițional nucleul unui sistem cu swapping face o copie fizică a spațiului de adresă a părintelui care este de obicei o operație inutilă deoarece procesele apelează “exec“ la scurt timp după apelul sistem fork și eliberează imediat memoria care tocmai a fost copiată. În sistemul de paginare al UNIX System V nucleul evită să copieze pagina prin manipularea tabelelor de regiune, intrărilor în tabelele de pagină și intrările în tabelele pfdata. Mărește pur și simplu contorul de referințe al regiunilor partajate. Pentru regiunile private precum cea de date și cea de stivă alocă o nouă intrare în tabelul de regiune și un tabel de pagină și apoi examinează fiecare intrare părinte în tabelul de pagină: dacă o pagină este validă mărește contorul de referințe al tabelului de folosire a spațiului de swap pentru acea pagină.
Pagina poate fi adresată acum prin ambele regiuni care își împart pagina până ce un proces scrie pe ea. Nucleul copiază apoi pagina astfel încât fiecare regiune să aibă o versiune privată. Pentru a face asta nucleul activează bitul de copiere pentru fiecare intrare în tabelul de pagină din regiunile private ale proceselor părinte și fiu în timpul apelului de sistem fork.
Dacă unul din procese scrie pagina creează o eroare de protecție și pentru rezolvarea erorii nucleul face o nouă copie a paginii pentru procesul care conține greșeala. Copierea fizică a programului este astfel amânată până ce un proces are nevoie de ea.
Implementarea apelului de sistem fork în sistemul BSD face o copie fizică a paginilor procesului părinte. Recunoscând îmbunătățirea performanțelor câștigată prin faptul că nu a trebuit să fie făcută copia sistemul BSD conține totuși și un apel de sistem vfork care presupune că un proces fiu va invoca imediat exec la întoarcerea din apelul vfork. Vfork nu copiază tabelele de pagină astfel încât este mai rapid decât apelul sistem fork din SystemV. Dar procesul fiu execută în același spațiu de adresă fizică ca și procesul părinte (până la exec sau exit) și poate astfel suprascrie tabelele și stiva părintelui. O situație periculoasă se poate ivi dacă un programator folosește incorect vfork deoarece răspundere pentru corectitudinea apelului vfork este a programatorului. Diferența dintre abordarea System V și cea din sistemul BSD este filosofică: ar trebui nucleul să ascundă de utilizatori particularitățile implementării sale sau ar trebui să le ofere utilizatorilor avizați șansa de a profita de implementare pentru a realiza funcții mai eficiente ?
Să considerăm exemplul programului de mai sus. După apelul vfork procesul nu apelează exec ci resetează variabilele globale și locale și ieșirile. Sistemul garantează că procesul părinte este suspendat până ce procesul fiu apelează exec sau exit. Când procesul părinte își reia execuția descoperă că valorile celor 2 variabile nu sunt aceleași ca cele de dinainte de vfork. Mai multe efecte spectaculoase pot apărea dacă procesul fiu se întoarce din funcția care a apelat vfork.
III.2.1.2 Apelul exec într-un sistem cu paginare
Când un proces invocă apelul sistem exec nucleul citește fișierul executabil în memorie din sistemul fișiere. Pe un sistem cu pagina la cerere fișierul executabil poate fi prea mare pentru a încăpea în memoria principală disponibilă. Prin urmare nucleul nu alocă dinainte memorie pentru fișierul executabil ci îl introduce prin “eroare“ alocând memorie după cum este necesar. Mai întâi tabelele de pagină și descriptorii de disc pentru fișierul executabil marcând intrările din tabelele de pagină “demand fill“ sau “demand zero“. Urmând o variantă a algoritmului de citire pentru citirea fișierului din memorie procesul creează câte o eroare de validitate pe măsură ce citește fiecare pagină. Handlerul care rezolvă eroarea observă dacă pagina este “demand fill“ aceasta însemnând că conținutul său va fi imediat suprascris cu conținutul fișierului executabil astfel încât nu este nevoie să fie șters sau dacă este “demand zero“ aceasta însemnând că conținutul ar trebui să fie șters. Descrierea handlerului erorii de validitate din secțiunea 1.2.3 va arăta cum se va face aceasta. Dacă procesul nu încape în memorie procesul care fură paginile transferă periodic pagini din memorie făcând loc pentru procesul care urmează.
Această schemă conține insuficiențe evidente. În primul rând un proces creează o eroare de pagină când citește fiecare pagină a procesului executabil chiar dacă poate să nu acceseze pagina respectivă niciodată. În al doilea rând procesul care fură pagini poate să transfere pagina din memorie înainte ca exec să fie executat rezultând de aici două operații de transferare suplimentare pe pagină dacă procesul are nevoie de pagini mai devreme. Pentru a face exec mai eficient nucleul poate cere pagina direct din fișierul executabil dacă datele sunt ordonate în mod corespunzător după cum este indicat printr-un număr magic special. Cu toate acestea folosirea algoritmilor standard precum bmap pentru a accesa un fișier ar face costisitoare cererea paginii din blocuri indirecte din cauza acceselor buffer cache multiple necesare pentru a citi un bloc. În plus s-ar putea ivi probleme de consistență deoarece bmap nu este reentrant. Nucleul stabilește diverși parametrii I/O în zona u în timpul apelului de sistem read. Dacă un proces creează o eroare de pagină în timpul unui apel de sistem read atunci când încearcă să copieze datele în spațiul utilizator ar suprascrie aceste câmpuri în zona u pentru a citi pagina din sistemul de fișiere. Prin urmare nucleul nu poate folosi algoritmi obișnuiți pentru a introduce paginile prin eroare din sistemul de fișiere. Algoritmii sunt desigur reentranți în cazurile obișnuite deoarece fiecare proces are o zonă u separată iar un proces nu poate executa simultan apeluri de sistem multiple.
Pentru a pagina direct dintr-un fișier executabil nucleul găsește toate numerele blocurilor de disc ale fișierului executabil când execută exec și atașează lista i-nodurilor fișierului. Când stabilește tabelele de pagină pentru un astfel de fișier executabil nucleul marchează descriptorul blocului de disc cu numărul logic de bloc (începând de la blocul 0 din fișier) care conține pagina. Handlerul erorii de validitate folosește mai târziu aceste informații pentru a încărca pagina din fișier.
III.2.2 Procesul care fură pagini (pfp)
Procesul care fură pagini este un proces al nucleului care transferă paginile de memorie care nu mai fac parte din mulțimea de lucru a unui proces. Nucleul creează procesul care fură pagini în timpul inițierii sistemului și face apel la el pe tot parcursul duratei unui sistem atunci când nu sunt suficiente pagini libere. Acesta examinează fiecare regiune activă neblocată sărind peste cele blocate, așteptând să le examineze pe acestea din urmă în timpul următoarei treceri prin lista regiunilor și mărește câmpul de vârstă al tuturor paginilor valide. Nucleul blochează o regiune când un proces comite o eroare pe o pagină din acea regiune astfel încât procesul care fură pagini nu poate să fure pagina în timp ce aceasta este introdusă prin eroare. Există două stări de paginare pentru o pagină din memorie: pagina îmbătrânește în memorie și nu este bună pentru transfer sau pagina este bună pentru transfer și este disponibilă pentru realocare către alte pagini virtuale. Prima stare indică faptul că un proces a accesat recent pagina și prin urmare aceasta este în memoria ei de lucru. Unele mașini stabilesc un bit de referință atunci când adresează o pagină dar acest lucru se poate face și prin metode software dacă hardware-ul nu are această trăsătură. Procesul care fură pagini anulează bitul de referință pentru asemenea pagini dar reține câte examinări au trecut de când pagina a fost adresată ultima dată. Prima stare este alcătuită astfel din mai multe substări care corespund numărului de treceri pe care procesul care fură pagini le face înainte ca pagina să fie bună pentru transfer (vezi figura 12). Când numărul depășește o valoare limită nucleul pune pagina în cea de-a doua stare gata de a fi transferată. Perioada maximă în care o pagină poate să îmbătrânească până este gata de transfer depinde de implementare și este constrânsă de numărul de biți disponibili în intrarea în tabelul de pagină
Adresări de pagină
Gata de
evacuare
Vârsta paginilor nereferențiate
Transfer în transfer
memorie din memorie
Figura 12. Diagrama îmbătrânirii paginilor
Dacă două sau mai multe procese își împart regiunea el își actualizează biții de referință ale acelorași intrări în tabelele de pagină. Paginile pot să fie astfel o parte din mulțimea de lucru a mai multor procese, dar aceasta nu contează pentru procesul care fură pagini. Dacă o pagină face parte din mulțimea de lucru a oricărui proces rămâne în memorie. Dacă nu face parte din mulțimea de lucru a vreunui proces este potrivită pentru transfer. Nu contează dacă o regiune are mai multe pagini în memorie decât alta. Procesul care fură pagini nu încearcă să transfere un număr egal de pagini din toate regiunile active. Nucleul activează procesul care fură pagini când memoria liberă disponibilă în sistem este sub un prag minim și procesul care fură pagini transferă pagini până când memoria liberă disponibilă în sistem depășește un prag maxim. Folosirea pragurilor minim și maxim elimină oscilările. Dacă nucleul ar folosi numai un prag limită ar transfera destule pagini încât să depășească limita de pagini libere dar ca rezultat al introducerii prin eroare a paginilor înapoi în memorie numărul ar scădea curând sub limită. Procesul care fură pagini ar oscila efectiv în jurul limitei. Prin transferarea paginilor până ce numărul de pagini libere depășește o limită superioară ia mai mult timp până ce numărul de pagini libere scade sub limita inferioară. Astfel că procesul care fură pagini nu este activat atât de des. Administratorii pot configura valorile pentru limitele inferioară și superioară pentru performanțe optime. Când procesul care fură pagini decide să transfere o pagină ia în considerare dacă o copie a paginii este pe discul de swap. Există trei posibilități:
Starea paginii timpul de când
nu a mai fost adresată
Pagina a fost
adresată
pagina adressată
pag. este
evacuată din
memorie
Figura 13. Exemplu de îmbătrânire a paginii
Dacă nici o copie a paginii nu se află pe un disc de swap nucleul planifică pagina pentru transfer. Procesul care fură pagini pune pagina pe o listă de pagini care urmează să fie transferate și continuă. Când lista de pagini care urmează a fi transferate atinge o limită (în funcție de capacitățile controler-ului de disc) nucleul scrie paginile pe discul de swap.
Dacă o copie a paginii se află deja pe un disc de swap și nici un proces nu a modificat alcătuirea sa (bitul de modificare al intrării în tabelul de pagină este setat 0) nucleul setează 0 bitul de validitate al intrării în tabelul de pagină, scade contorul de adresare din tabelul în intrarea pfdata și pune intrarea pe lista celor libere pentru a fi alocată ulterior.
Dacă o copie a paginii este pe discul de swap dar un proces a modificat conținutul memoriei nucleul planifică pagina pentru transfer ca mai sus și eliberează spațiul pe care îl ocupă în prezent pe discul de swap.
Pentru a ilustra diferențele dintre ultimele două cazuri să presupunem că o pagină este pe discul de swap și este transferată în memoria principală după ce un proces creează o eroare de validitate. Să presupunem că nucleul nu înlătură automat copia de pe disc. În cele din urmă procesul care fură pagini se decide să transfere din nou pagina afară din memorie. Dacă nici un proces nu a scris pagina de când a fost transferată în memoria principală copia din memorie este identică cu copia de pe disc și nu este nevoie să scrie pagina pe discul de swap. Totuși dacă un proces a scris pagina copia din memorie este diferită de cea de pe disc astfel că nucleul trebuie să scrie pagina pe discul de swap după ce eliberează spațiul de pe discul de swap ocupat anterior de pagină. Nu refolosește spațiul de pe discul de swap imediat astfel încât poate să păstreze spațiul de transfer contiguu pentru performanțe mai bune. Procesul care fură pagini completează o listă cu pagini care urmează să fie transferate din diferite regiuni și le transferă pe un disc de swap când lista este completă. Nu fiecare pagină a procesului trebuie să fie transferată. Unele pagini pot să nu fi îmbătrânit suficient. Aceasta diferă de politica de swapping care transferă fiecare pagină a unui proces din memorie dar metoda scrierii datelor pe discul de swap este identică cu aceea pentru un mecanism cu swapping. Dacă nici un disc de swap nu conține destul spațiu contiguu nucleul transferă din memorie blocuri de pagini dar transferă în memorie numai câte o pagină pe rând.
Când nucleul scrie o pagină pe un disc de swap anulează bitul de validitate în intrarea în tabelul de pagină și scade contorul de folosire a intrării în tabelul pfdata. Dacă contorul ajunge la 0 el plasează intrarea în tabelul pfdata la sfârșitul listei libere până ca aceasta să fie realocată. Dacă contorul nu este 0 înseamnă că mai multe procese își împart pagina ca rezultat a unui apel fork anterior însă nucleul tot mai transferă pagini din memorie. În final nucleul alocă spațiu de swap, salvează adresa de transfer în descriptorul blocului de disc și crește contorul tabelului de folosire a spațiului de swap pentru pagină. Dacă un proces creează o eroare de pagină când pagina nu este pe lista celor libere nucleul poate salva pagina din memorie în loc să o retragă de pe discul de swap. Cu toate acestea pagina este totuși transferată dacă se află pe lista de transfer.
De exemplu să presupunem că procesul care fură pagini transferă din memorie 30, 40, 50 și 20 de pagini din procesele A, B și C și respectiv D și că scrie 64 de pagini pe discul de swap într-o singură operație de scriere pe discProcesul care fură pagini alocă 64 de pagini pe discul de swap și transferă din memorie cele 30 pagini ale procesului A și 34 de pagini din procesul B. Alocă apoi mai mult spațiu pe discul de swap pentru alte 64 pagini și transferă din memorie cele 6 pagini care rămân din procesul B, cele 50 de pagini ale procesului C și 8 pagini din procesul D. Cele două zone de disc pentru cele 2 operații nu trebuie neapărat să fie contigue. Procesul care fură pagini păstrează cele 12 pagini care rămân din procesul D pe lista de pagini care urmează să fie transferate dar nu le transferă până ce lista nu e completă.
În concluzie există 2 faze de transfer a unei pagini din memorie. În prima procesul care fură pagini găsește pagina potrivită pentru a fi transferată și scrie numărul paginii într-o listă de pagini care urmează a fi transferate. În a doua nucleul copiază pagina pe un disc de swap atunci când îi convine, anulează bitul de validitate din intrarea în tabelul de pagină, scade contorul de referințe pentru intrarea în tabelul pfdata și așează intrarea în tabelul pfdata la sfârșitul listei celor libere dacă contorul de referințe al acesteia este 0.
Grupuri de câte 64 pagini pentru swap
Discul de swap
Figura 14. Alocarea spațiului de swap într-un sistem cu paginare
Conținutul paginii fizice din memorie este valid până ce pagina este realocată.
III.2.3 Erorile de pagină
Sistemul poate creea două tipuri de erori de pagină: erori de validitate și erori de protecție. Deoarece handlerii erorii pot să fie nevoiți să citească o pagină de pe disc în memorie și să aștepte în timpul operației I/O handlerii erorii sunt o excepție de la regula generală că handlerii de întrerupere nu pot să aștepte. Cu toate acestea, deoarece handlerii erorii așteaptă în contextul procesului care a provocat eroarea de memorie, eroarea este legată de procesul în desfășurare. De aici rezultă că procesele arbitrare nu sunt așteptate.
III.2.3.1 Handlerul erorii de validitate
Dacă un proces încearcă să acceseze o pagină al cărei bit de validitate nu este setat creează o eroare de validitate iar nucleul apelează la handlerul erorii de validitate. Bitul de validitate nu este setat pentru paginile din afara spațiului de adresă virtuală a unui proces și nici pentru paginile care fac parte din spațiul de adresă virtuală, dar care în prezent nu au alocată o pagină fizică. Hardware-ul îi furnizează nucleului adresa virtuală care a fost accesată pentru a provoca eroarea de memorie, iar nucleul găsește intrarea în tabelul de pagină și descriptorul blocului de disc pentru pagina respectivă. Nucleul blochează regiunea care conține intrarea în tabelul de pagină pentru a împiedica competiția care ar apărea dacă procesul care fură pagini ar încerca să transfere pagina din memorie.
Dacă descriptorul blocului de disc nu cunoaște pagina cu eroare adresarea memoriei care s-a încercat nu este validă, și nucleul transmite un semnal de “vidare a segmentării“ către procesul care a provocat eroarea. Aceasta este aceeași procedură cu aceea care este urmată în transferul cu swapping atunci când un proces accesează o adresă invalidă cu excepția faptului că recunoaște eroarea imediat deoarece toate paginile valide rezidă în memorie. Dacă adresarea memoriei a fost validă atunci nucleul alocă o pagină din memorie pentru a citi conținutul paginii de pe discul de swap sau din fișierul executabil.
Pagina care a cauzat eroarea se află în una din următoarele 5 stări:
Pe discul de swap și nu în memorie;
Pe lista paginilor libere din memorie;
Într-un fișier executabil;
Marcată “demand zero“
Marcată “demand fill“
Să luăm fiecare caz în parte.
Dacă o pagină se află pe discul de swap și nu în memorie ea s-a aflat odată în memoria principală dar procesul care fură pagini a transferat-o de acolo. Din descriptorul blocului de disc nucleul găsește discul de swap și numărul de bloc unde este stocată pagina și verifică dacă pagina nu se află în cache-ul paginii. Nucleul actualizează intrarea în tabelul de pagină astfel încât să pointeze către pagina care urmează să fie citită, așează intrarea în tabelul pfdata pe o listă de dispersie pentru a mări viteza operației următoare a handlerului erorii și citește pagina de pe mecanismul de swap. Procesul care a cauzat eroarea așteptă până ce I/O este completă atunci când nucleul activează alte procese care așteptau să fie citit conținutul paginii.
Nucleul nu trebuie întotdeauna să execute o operație I/O atunci când creează o eroare de validitate chiar dacă descriptorul blocului de disc indică faptul că o pagină este transferată. Este posibil ca nucleul să nu fi realocat niciodată pagina fizică după ce a transferat din memorie sau ca un alt proces să fi introdus prin eroare pagina virtuală într-o altă pagină fizică. În oricare din cazuri handlerul erorii găsește pagina în cache-ul de pagină blocând numărul de bloc în descriptorul de bloc. Realocă intrarea în tabelul de pagină pentru a pointa către pagina care tocmai a fost găsită, crește contorul referințelor către pagină și dacă este necesar înlătura pagina din lista celor libere.
Handlerul erorii nu trebuie să citească pagina în memorie dacă un alt proces a introdus-o din greșeală pe aceeași pagină dar încă nu a citit-o complet. Handlerul erorii găsește regiunea care conține intrarea în tabelul de pagină blocată de o altă instanță a handlerului erorii. Așteaptă până ce cealaltă instanță a handlerului erorii este completă, găsește pagina care este acum validă și se întoarce
Dacă nu se află o copie a paginii pe discul de swap dar se află în fișierul executabil original nucleul citește pagina din fișierul original. Handlerul erorii examinează descriptorul blocului de disc, găsește numărul logic de bloc în fișierul care conține pagina respectivă și găsește i-nodul asociat cu intrarea în tabela de regiune. Folosește numărul logic de bloc ca deplasament în șirul numerelor blocurilor de disc atașată i-nodului în timpul “exec“. Cunoscând numărul blocului de disc citește pagina în memorie. Dacă un proces creează o eroare de pagină pentru o pagină marcată “demand fill “sau “demand zero“ nucleul alocă o pagină liberă din memorie și actualizează intrarea corespunzătoare în tabelul de pagină. Pentru “demand zero“ eliberează de asemenea pagina până la 0. În final șterge și indicatorii “demand fill “ sau “demand zero“. Pagina este acum validă în memorie iar conținutul ei nu poate fi duplicat pe un disc de swap sau într-un sistem de fișiere. Un proces nu a accesat acele pagini de când a fost apelat “exec“ pentru fișierul respectiv. Handlerul erorii de validitate sfârșește prin a seta bitul de validitate al paginii și prin a șterge bitul de modificare. Recalculează prioritatea procesului deoarece acesta ar fi putut să aștepte handlerul erorii care acționează cu prioritate de nivel nucleu (prioritate maximă) dându-i acestuia un avantaj nedrept de programare la reîntoarcerea în mod utilizator. În sfârșit dacă se reîntoarce în mod utilizator verifică dacă a primit vreun semnal în timpul rezolvării erorii de pagină.
III.2.3.2 Handlerul erorii de protecție
Cel de al doilea tip de eroare de memorie pe care îl poate crea un proces este eroarea de protecție însemnând că procesul a accesat pagina validă dar biții de acces ai paginii nu au permis accesul. Un proces mai poate crea o eroare de protecție atunci când încearcă să scrie o pagină al cărei bit de copiere a fost setat în timpul apelului de sistem fork. Nucleul trebuie să afle dacă accesul a fost interzis deoarece procesul cere o copiere sau dacă s-a întâmplat ceva cu adevărat ilegal.
Hardware-ul îi furnizează handlerului erorii de protecție adresa virtuală unde a avut loc eroarea și handlerul erorii găsește regiunea corespunzătoare și intrarea în tabelul de pagină. El blochează regiunea astfel încât procesul care fură pagini să nu poată fura pagina în timp ce handlerul erorii de protecție operează pe ea. Dacă handlerul erorii decide că eroarea a fost cauzată deoarece a fost setat bitul de copiere și dacă pagina este împărțită și de alte procese, nucleul alocă o nouă pagină și copiază pe ea conținutul celei vechi. Celelalte procese își rețin referințele către vechea pagină. După ce copiază pagina și actualizează intrare în tabelul de pagină cu noul număr de pagină nucleul micșorează contorul de referințe al vechii intrări în tabelul pfdata.
Dacă bitul de copiere este setat dar nu își împart pagina și alte procese, nucleul îi permite procesului să refolosească pagina fizică. Pentru aceasta nucleul anulează bitul de copiere, disociază pagina de copia ei de pe disc dacă există una deoarece alte procese își pot împărți copia de pe disc apoi înlătură intrarea în tabelul pfdata din coada de pagină pentru că noua copie a pagini virtuale nu se află pe discul de swap. În final scade contorul de folosire a spațiului de swap și dacă contorul scade la zero eliberează spațiul de swap.
Dacă o intrare în tabelul de pagină este invalidă și bitul ei de copiere este setat pentru a provoca o eroare de protecție să presupunem că sistemul rezolvă mai întâi eroare de validitate atunci când un proces accesează pagina. Cu toate acestea handlerul erorii de protecție trebuia să verifice dacă o pagină este încă validă pentru că ar putea aștepta când blochează o regiune iar procesul care fură pagini ar putea între timp să transfere pagina din memorie. Dacă pagina este invalidă (bitul de validitate este anulat ) handlerul erorii se întoarce imediat iar procesul va crea o eroare de validitate. Nucleul rezolvă eroarea de validitate dar procesul va crea iar eroarea de protecție.
Intrarea în tabela de pagină pentru procesul A
Intrarea în tabela de pagină pentru procesul B
Intrarea în tabela de pagină pentru procesul C
înainte ca procesul B să provoace o eroare de pagină
Intrarea în tabela de pagină pentru procesul A
Intrarea în tabela de pagină pentru procesul B
Intrarea în tabela de pagină pentru procesul C
b) După ce a rulat handlerul erorii de protecție pentru procesul B
Figura 15. Eroare de protecție deoarece bitul de copiere este setat
În mod sigur, va rezolva ultima eroare de protecție fără nici o întrerupere pentru că va trece un timp îndelungat până ce pagina va îmbătrâni suficient pentru a fi transferată din memorie. Când handlerul erorii de protecție termină execuția setează biți de modificare și protecție dar șterge bitul de copiere. Recalculează apoi prioritatea procesului și verifică semnalele după cum se face și la sfârșitul erori de validitate.
III.2.4 Paginare la cerere pe hardware mai puțin sofisticat
Algoritmii pentru paginarea la cerere sunt foarte eficienți dacă hardware-ul setează biți de referință și modificare și provoacă o eroare de protecție atunci când un proces scrie o pagină al cărei bit de copiere este setat. Cu toate acestea este posibil să se implementeze algoritmii de paginare descriși aici dacă hardware-ul recunoaște numai biții de validitate și protecție. Dacă bitul de validitate este dublat de un bit de validitate software care indică dacă pagina este cu adevărat validă sau nu atunci nucleul poate anula bitul de validitate al hardware-ului și simula setarea celorlalți biți în software. De exemplu, hardware-ul VAX-11 nu are un bit de referință. Nucleul poate să anuleze bitul de validitate pentru pagină și să urmeze următorul scenariu: dacă un proces accesează pagina creează o eroare de pagină pentru că bitul de validitate al hard-ului este anulat iar handlerul de întrerupere al erorii de pagină examinează pagina. Deoarece bitul de validitate software este setat, nucleul știe că pagina este cu adevărat validă și se află în memorie setează bitul de referință software și activează bitul de validitate hardware dar va fi aflat deja că pagina a fost accesată. Adresările ulterioare către pagină nu vor crea vreo eroare pentru că bitul de validitate este activat. Când procesul care fură pagini examinează pagina anulează din nou bitul de validitate hardware forțând un proces să greșească când adresează pagina repetând astfel ciclul.
III.3 Un sistem hibrid cu swap și paginare la cerere
Cu toate că sistemele cu paginare la cerere tratează memoria cu mai multă flexibilitate decât sistemele cu swapping se pot ivi situații în care procesul care fură pagini și handlerul erorii de validitate oscilează din cauza lipsei de memorie. Dacă suma mulțimilor de lucru a tuturor proceselor este mai mare decât memoria fizică de pe o mașină, handlerul memoriei va aștepta de obicei pentru că nu poate aloca pagini pentru proces. Procesul care fură pagini nu poate să fure pagini destul de repede pentru că toate se află în mulțimea de lucru. Rezultatele sistemului au de suferit deoarece nucleul cheltuiește prea mult rearanjând memoria cu foarte mare viteză.
Nucleul System V nu rulează algoritmii de transfer și paginare la cerere pentru a evita problemele de oscilare atunci când un nucleu nu poate aloca pagini pentru un proces el activează swapperul și pune procesul care face apelul într-o stare echivalentă cu “ gata de rulare“ dar transferat. Mai multe procese se pot afla simultan în această stare. Swapperul transferă din memorie toate procesele până ce memoria disponibilă depășește limita superioară. Pentru fiecare proces transferat creează un proces “gata de rulare dar transferat“ care este gata de rulare. Nu transferă acel procese prin algoritmul normal de transfer dar le lasă să introducă pagina prin eroare după cum este necesar. Reluările următoare ale transferului vor permite altor procese să fie introduse prin eroare dacă există suficientă memorie în sistem. Această metodă încetinește rata de eroare a sistemului și reduce oscilarea. Este asemănătoare ca folosire metodelor folosite în sistemul de operare VAX/VMS.
Capitolul IV
Alocarea memoriei în sistemul de operare Windows
Windows 95 nu oferă doar o interfață complet nouă, ci și unele avantaje rezultate din modalitățile noi de gestionare a memoriei.
Există două modele de memorie în Windows. Windows 3.1 oferă posibilitatea de utilizare a aplicațiilor pe 16 biți. Un registru pe 16 biți nu poate avea acces decât la 65.536 octeți de memorie. Aceasta înseamnă că Windows nu poate avea acces la toată memoria calculatorului doar prin intermediul unui singur registru. Din acest motiv Windows 3.1 utilizează un model de memorie segmentată. Memoria segmentată este un model de memorie care utilizează două registre combinate pentru a avea acces la toată memoria calculatorului. Un model de memorie segmentată presupune o muncă suplimentară, deoarece programatorul trebuie să se ocupe atât de registrul care conține segmentul, cât și de registrul care conține deplasamentul.
Windows NT oferă posibilitatea utilizării aplicațiilor pe 32 de biți. Toate aceste aplicații utilizează registre pe 32 de biți. Deoarece Windows NT poate folosi toți cei 32 biți ai registrelor de la procesoarele 80386 (și superioare), înseamnă că el nu mai are nevoie de memorie segmentată. Un registru poate păstra toate adresele pentru un volum de până la 4.294.967.296 octeți de memorie. Drept urmare se obține un model de memorie nediferențiată. Deoarece programatorul nu trebuie să se ocupe decât de un registru, modelul de memorie nediferențiată este mai eficient decât modelul de memorie segmentată.
Windows 95 oferă posibilitatea utilizării ambelor modele de memorie. El utilizează modelul de memorie segmentată pe 16 biți pentru aplicațiile mai vechi, în timp ce aplicațiile recente folosesc modelul de memorie nediferențiată pe 32 biți.
IV.1 Modelul de memorie segmentată de la Windows 3.1
În secțiunea precedentă am prezentat pe scurt cele două modele de memorie Windows și diferențele dintre ele. A făcut afirmația că modelul de memorie segmentată este mai graeu de utilizat pentru programator decât modelul de memorie nediferențiată utilizat de Windows NT. Și totuși de ce compania Microsoft mai folosește modelele de memorie segmentată pentru modul de lucru îmbunătățit de la Windows 3.1? În definitiv, modul de lucru îmbunătățit este proiectat pentru procesorul 80386, despre care știm deja că acceptă și modelul de memorie nediferențiată. Există două motive bine determinate. În primul rând procesorul 80286 nu poate lucra cu modelul de memorie nediferențiată. Dacă firma Microsoft s-ar fi decis să utilizeze acest model de memorie, ar fi trebuit să includă două seturi de fișiere pentru fiecare aspect din Windows 3.1. Al doilea motiv este la fel de simplu. Windows 3.1 se află “deasupra “ sistemului de operare DOS, iar DOS utilizează cod pe 16 biți. Windows 3.xx face deja “jonglerii“ când trebuie să converseze cu DOS, așa că lucrul cu 32 biți ar fi deja prea mult. În acest fel, am sfârșit prin a avea un mediu de operare pe 16 biți, numit
Windows 3.1.
Modelul de memorie segmentată utilizează două registre de 16 biți pentru memorarea adreselor. În modul de operare real, procesorul utilizează un segment și un deplasament. Procesorul combină segmentul cu deplasamentul pentru a crea o adresă pe 20 de biți pentru procesorul 8086 sau o adresă pe 24 biți pentru procesorul 80286. Procesorul deplasează conținutul registrului de segment cu patru poziții la stânga pentru a calcula adresa. O adresă pe 20 biți produce un spațiu de adresare de 1M, tipic sistemului de operare DOS. Desigur, aceasta se traduce prin obligația ca aplicația(și nu sistemul de operare) să păstreze controlul asupra memoriei utilizate.
Windows nu operează în mod real, ci utilizează modul protejat. Nu se mai utilizează perechea segment:deplasament, ci o pereche de forma selector :deplasament. Există o mare diferență între un segment și un selector:segmentul reprezintă o poziție din memorie, în timp ce selectorul reprezintă o poziție din tabelul descriptorilor. Utilizarea selectorilor conferă sistemului de operare controlul asupra întregii zone de memorie a sistemului.
De fapt, selectorul conține și unele informații de securitate pentru sistemul de operare. Biții 0 și 1 ai selectorului comunică sistemului de operare nivelul său de acces. Valoarea 0(00 în binar) oferă accesul cel mai privilegiat, iar valoarea 3 (11 în binar) oferă accesul cel mai puțin privilegiat. Toate aplicațiile rulează sub Windows la nivelul de acces 3. Doar sistemul de operare rulează la nivelul de acces 0. Bitul 2 conține numărul tabelului utilizat de Windows pentru accesul la memorie.Există două tabele de descriptori, tabelul de descriptori globali(GDT) și tabelul de descriptori locali(LDT). Dacă bitul 2 are valoarea 1 este selectat tabelul LDT. Windows utilizează tabelul GDT pentru toate datele obișnuite. Nu există decât un singur GDT pentru întregul sistem. Fiecare aplicație dispune de câte un tabel LDT pentru datele sale private. În sfârșit, biții cuprinși între 3 și 15 specifică locația în cadrul tabelului.
Există mai multe probleme legate de modelul de memorie segmentată. Pentru programatori cea mai mare problemă este că nu se poate aloca memorie decât în blocul de 64K. Cum adresa este compusă din selector și deplasament și registrul de deplasament nu are decât 16 biți înseamnă că el poate gestiona doar 64K de memorie. Pentru programator, aceasta înseamnă că va trebui să scriem o aplicație care să controleze mai mulți selectori, fiecare selector indicând o zonă diferită de 64K de memorie. Șansa ca unul dintre selectori să indice o adresă greșită crește pe măsură ce aplicația utilizează mai multă memorie. De aceea nu este dificil de înțeles de ce o aplicație Windows pe 16 biți s-ar putea “zăpăci“, sfârșind prin a scrie într-o zonă greșită de memorie. Rezultatele sunt de obicei catastrofale și duc la blocarea calculatorului.
IV. 2 Modelul de memorie nediferențiată de la Windows NT
Când Microsoft a proiectat Windows NT, a decis să utilizeze un model de memorie diferit, acceptat de 80386 și de procesoarele mai rapide. Acest model de memorie este cunoscut sub numele de model de memorie nediferențiată. Atunci când sistemul de operare plasează procesul în acest mod, el spune în esență că toate resursele vor utiliza același segment. Procesorul nu rămâne fără mecanismul de segmentare, dar sistemul de operare ignoră această capacitate. Eliminarea segmentării simplifică simțitor viața programatorilor. Aceștia nu mai trebuie să se ocupe de registrele de segment, ci doar adresa este importantă.
În cazul memoriei segmentate procesorul menținea controlul prin intermediul unui tabel de selectori. Aplicația utiliza un selector ca pe o cheie pentru a “deschide“ blocul de memorie de 64 K. Și modul de adresare nediferențiat este prevăzut cu o metodă de protecție. De fapt, această metodă oferă chiar mai multă flexibilitate decât a modului segmentat. Figura următoare prezintă modelul de memorie nediferențiată.
Catalogul tabelului Tabelul de pagină Cadrul de pagină
de pagină
Figura 16. Modelul de adrese nediferențiate
Fiecare adresă de 32 biți este împărțită în 3 câmpuri. Fiecare câmp corespunde unui anumit nivel al protecției asigurate de procesor în cazul modelului de memorie nediferențiată. Chiar dacă programatorul nu trebuie să se ocupe de aceste câmpuri atunci când scrie o aplicație, sistemul de operare și procesorul o fac. Primul câmp este cuprins între biții 31-32 ai adresei și indică o intrare în catalogul tabelelor de pagină. Ca și modelul de memorie segmentată, modelul nediferențiat oferă aplicației o cheie pentru o anumită zonă de memorie, nu adresa reală a acesteia. Localizarea tabelului corespunzător al paginilor este primul pas în procesul de găsire a adresei.
Dacă în modelul de memorie segmentată era nevoie de o zonă de memorie mai mare de 64K atunci aplicația trebuia să solicite blocuri multiple. Tabelul paginilor evită această problemă. Aplicația solicită pur și simplu volumul total de memorie de care are nevoie, iar Windows i-l oferă. Numărul de pagini din tabel corespunde cu numărul de pagini de 4K alocat aplicației. Dacă o aplicație solicită 400K de memorie RAM, atunci tabelul va conține 100 de intrări. Deci, modelul de adresare nediferențiată e mai flexibil decât modelul segmentat.
După ce Windows a găsit un anumit tabel de pagini, el utilizează valoarea stocată în biții adresei cuprinși între 21-12 pentru a găsi o anumită pagină. Sunt 10 biți rezervați pentru pagini sub Windows și încă 10 biți rezervați pentru intrările catalogului de tabele de pagină. Înmulțind cele 210 intrări ale catalogului de intrări în tabelul de pagină și cu 4K (dimensiunea unei pagini) se obțin 4G. În concluzie fiecare aplicație poate utiliza până la 4G de memorie.
După ce Windows a găsit o anumită pagină în cadrul unui anumit tabel de pagină, va prelua adresa găsită acolo și o va aduna la deplasamentul specificat de biții 11-0 ai adresei de 32 biți. Acești 12 biți permit aplicației să aleagă orice octet din cadrul paginii de 4K.
În catalogul tabelelor de pagină biții cuprinși între 31-12 indică un tabel de pagină, iar în tabelul de pagină ei indică adresa fizică, ce trebuie combinată cu deplasamentul pentru a obține adresa originală. Bitul 6 este numit și “bitul murdar“ (dirty bit) sau “bitul D“. Ori de câte ori o aplicație modifică o pagină de memorie Windows modifică și bitul D. Aceasta amintește procesorului că nu a scris modificările pe disc. Dacă procesorul dorește să utilizeze această pagină de memorie fizică pentru alte scopuri, atunci trebuie să copieze ceea ce este scris pe pagina respectivă în fișierul de memorie virtuală Windows. Bitul 5 se numește bitul A sau bitul de acces. Ori de câte ori o aplicație citește sau scrie o pagină de memorie de 4K, Windows schimbă starea acestui bit. Windows poate utiliza acest bit pentru a determina dacă trebuie sau nu să elimine o pagină din memorie, pentru a face loc alteia. Bitul 2 se numește bitul U/S sau bitul utilizator/supervizor. Acest bit face parte din schema de protecție de la 80386. Dacă acest bit este “0“, atunci el indică o pagină supervizor. Aplicațiile nu pot avea niciodată acces la paginile supervizor, deoarece acestea aparțin sistemului de operare. Pe de altă parte, stabilirea bitului la valoarea “1“ înseamnă că pagina este pentru utilizator. Aplicațiile pot avea acces la orice pagină de utilizator care le aparține. Bitul 1 se numește bitul R/W sau bitul de citire/scriere. Nu este de dorit ca o aplicație să suprascrie codul dintr-o pagină. Acest lucru poate fi prevenit stabilind bitul la valoarea “0“. Pentru paginile de date, valoarea acestui bit este “1“, iar pentru paginile de cod, valoarea este “0“. Bitul 0 se numește P sau bitul de prezență. Windows trebuie să cunoască dacă o pagină se află sau nu în memoria fizică. Aplicația nu poate utiliza o pagină de memorie care se află pe disc în fișierul de memorie virtuală (swap file). Pagina trebuie să se afle în memoria fizică. Dacă aplicația solicită accesul la o pagină de memorie aflată pe disc, procesorul semnalează o excepție (care în esență este o alarmă). Această excepție spune mediului Windows că trebuie să scoată pagina din fișierul de memorie virtuală, astfel încât aplicația să poată avea acces la ea.
Aceste intrări de tabel ajută Windows să controleze memoria (poate muta paginile de 4K din memoria fizică). Alți biți protejează memoria corespunzătoare sistemului de operare de intervenția aplicației. Există și biți care ajută la protecția aplicației de ea însăși, împiedicând-o să-și suprascrie codul.
IV.3 Tipuri de memorie Windows
Windows utilizează mai multe tipuri de memorie pentru a îndeplini sarcini diverse. Unele dintre aceste tipuri sunt legate de Windows însuși; altele sunt legate de aplicațiile acceptate de Windows. Aceste tipuri de memorie sunt :
Memorie convențională. Aceasta este memoria originală de 640K pe care IBM a rezervat-o pentru aplicațiile DOS. Fiecare aplicație DOS are nevoie de memorie convențională pentru a rula.Și Windows utilizează o mică zonă de memorie convențională, chiar dacă există suficientă memorie superioară pentru a se ăncărca. Chiar dacă procesorul poate avea acces la memoria superioară, sistemul de operare DOS nu poate. Pentru ca Windows să se poată autoactiva, trebuie să încarce o secțiune proprie care să poată fi apelată de DOS.
Memoria superioară. IBM a rezervat 384K din spațiul de adresare de la 80386 pentru memoria ROM și cea video. În majoritatea cazurilor, un sistem nu utilizează în totalitate această memorie. Un manager de memorie poate umple această zonă de memorie RAM, permițând să se încarce aici unele di driverele de echipamente pentru a elibera memoria convențională necesară aplicațiilor. O parte din Windows 3.1 trebuie să se încarce atât în memoria convențională, cât și în cea superioară, pentru a putea lucra cu sistemul de fișiere și alte funcții legate de DOS. Cu cât volumul de memorie superioară utilizat de Windows este mai mare, cu atât volumul de memorie convențională disponibil pentru aplicațiile DOS va fi și el mai mare.
Memorie înaltă. Acesta este un bloc de 64K care apare de fapt asupra limitei de adresă de1.024K.Tehnicile speciale de segmentare au permis ca procesorul să adreseze această memorie în mod real. Majoritatea utilizatorilor plasează sistemul de operare DOS în această zonă . pentru a elibera un volum mai mare de memorie convențională.
Memorie extinsă. Această memorie este zona din afara capacității de adresare a lui 8086. Un calculator trebuie să ruleze în mod protejat pentru a avea acces la memoria extinsă.
Memorie expandată. Unele aplicații mai vechi necesită memorie expandată. Cândva, era nevoie de o placă specială EMS pentru a crea memorie expandată. În prezent, programele de gestiune a memoriei pot transforma memoria extinsă în memorie expandată “din mers“. Desigur, cea mai simplă modalitate este aceea de a specifica într-un fișier PIF volumul de memorie expandată necesară.
Capitolul V.
Alocatoare de memorie
V.1 Un alocator dinamic foarte simplu
Voi ilustra aici în scop pur didactic implementarea unui alocator extrem de ineficient si risipitor, dar totodată complet. Aceasta este schema de bază de funcționare a tuturor alocatoarelor de nucleu ; variațiunile constau in imbunătățiri. Acest alocator implementează funcția free() fără a face nimic! Memoria eliberată este pur și simplu pierdută. Alocatorul extrage zonele de memorie dintr-o memorie mare alocată static inițial, care are 16Mo.
/*implementarea unui alocator de memorie foarte simplu
funcția free() nu face absolut nimic . */
typedef unsigned int size_t ;
#define marime_memorie 16*1024*1024
char memorie[marime_memorie] ;
int memorie_consumata = 0 ;
void * malloc( size_t marime )
{
if(MARIME_MEMORIE < marime + memorie_consumata ) return 0;
memorie_consumata += marime ;
return (void*) &memorie( memorie_consumata + marime ) ;
}
void free( void * )
{}
Acest alocator este extrem de rapid, probabil că nici nu poate fi scris un alocator mai rapid. Prețul plătit este o enormă risipă de memorie : tot ce este dealocat se pierde complet.
Oricum, aceste funcții ilustrează cărămizile de bază cu care un alocator din noul nucleu trebuie să opereze. Alocatorul de pagini manipulează memoria fizică a mașinii ca un vector enorm de octeți, din care extrage porțiuni așa cum facem noi cu vetorul numit ‘memorie’.
V.2 Alocatorul cu hartă de resurse
Acesta este probabil cel mai simplu tip de alocator care implementează funcția free. Acest alocator menține un vector de structuri care descriu fiecare bloc liber. Figura “Alocatorul cu hartă” arată o posibilă reprezentare a situației la un moment dat :
Există o mica problemă pentru că alocatorul are nevoie el însuși de spațiu pentru a reprezenta tabela de resurse. Există câteva soluții:
Când malloc găsește un bloc, folosește primii 4 octeți pentru a memora lungimea sa și returnează adresa următorului octet. Aceasta lungime este folosită de free pentru a ști cât de mult trebuie dealocat (Nota : Valoarea 4 este plauzibilă pentru mașini pe 32 de biți ; lungimea ar putea avea nevoie de mai mulți biți pe mașini care suportă mai mult de 4 Go de spațiu de adrese.)
Putem memora informația despre blocurile libere în chiar spațiul ocupat blocurile libere! Astfel, putem ține blocurile libere într-o listă înlănăuită, ca în figura alocatorul cu listă. Când alocatorul vrea să găsească un bloc liber pleacă de la adresa primului bloc liber și parcurge lista de blocuri libere până găsește unul de dimensiune corespunzătoare.
Acest alocator este relativ simplu, dar foarte ineficient. Din cauza fragmentării complexitatea operațiilor este mare ( după o vreme lista de blocuri libere devine populată cu o sumedenie de blocuri mici, a căror traversare este costisitoare și inutilă ). Schema este de asemenea ușor risipitoare : 4 octeți sunt memorați în plus pentru fiecare bloc ocupat, iar faptul că un bloc liber trebuie să conțină două valori impune o lungime minimă de 8 octeți pentru un bloc.
Eliberarea unui bloc îl inserează la începutul listei de blocuri libere. Dacă vrem putem comasa și cu vecinul anterior, atunci când în fiecare bloc memorăm și în ultimii 4 octeți și lungimea sa ;
în acest fel, atunci când eliberăm un bloc ; putem ști exact unde începe cel dinainte. În orice caz eliberarea cere un număr constat de instrucțiuni (care nu depinde de numărul de zone deja alocate).
Harta resurselor
Memoria
Figura 17. Alocatorul cu hartă de resurse.
Primul bloc
liber
Memoria
Ly
Figura 18 . Alocatorul cu listă
V.3 Alocatorul cu puteri ale lui 2
Problema alocatorului de mai sus constă în faptul că trebuie să caute un bloc de dimensiune potrivită. Pentru a remedia acest lucru putem folosi o altă reprezentare : păstrăm o serie de liste de blocuri, toate blocurile de pe fiecare listă având o anumită dimensiune. Atunci când vrem un anumit bloc, returnăm un bloc de dimensiunea imediat superioară. Cele mai folosite dimensiuni sunt puteri ale lui 2, ca în figura alocatorul cu puteri ale lui 2.
Acest alocator suferă de fragmentare internă, pentru că alocă întotdeauna mai mult decât i se cere. Alocarea și dealocarea cere timp constant pe operațiune (calculul listei plus extragerea primului bloc din listă). Putem reprezenta listele de blocuri libere exact ca în schema cu harta de resurse ; comasarea este practic imposibilă am putea comasa numai vecini de dimensiuni egale, ca să obținem rezultate de mărime tot puteri ale lui doi). Pentru toate blocurile mai mici de o anumită limită și mai mari de o alta, putem avea niște liste separate, în care facem căutare exhaustivă, Dacă vrem să avem liste cu toate dimensiunile posibile de blocuri sunt suficiente 32 de liste, ceea ce e o valoare rezonabilă.
În momentul în care o listă este complet depopulată, putem scoate un bloc mai mare de pe lista imediat superioară, pe care îl putem sparge în două bucăți mai mici.
În interiorul nucleului există multe structuri de date care au ca dimensiuni exact puteri ale lui 2 ; pentru astfel de cereri se irosește o cantitate enormă de memorie, pentru că fiecare bloc alocat trebuie să conțină și cei 4 octeți suplimentari. Astfel, dacă vrem să alocăm 256 octeți, trebuie de fapt 260, care înseamnă că folosim un bloc de 512 ; risipa este de aproape 100% !
Alte dezavantaje ale metodei : în general blocurile mici nu se pot regrupa loaolaltă pentru a forma blocuri mari, și sistemul de paginare nu poate obține pagini nefolosite înapoi în caz de nevoie.
Blocuri ocupate Capete de listă Blocuri libere
Figura 19. Alocatorul cu puteri ale lui 2
V.4 Alocatorul Karels-McKusick
În 1998 Kirk McKusick și Michael Karels au construit o variantă îmbunătățită a alocatorului cu puteri ale lui 2, care este acum folosită în 4.4BSD UNIX și Digital UNIX. Metoda lor elimină risipa pentru cazul blocurilor care au exact puteri ale lui 2.
Listele de blocuri libere sunt înlănțuite exact ca în alocatorul cu puteri ale lui 2. Diferența principală constă în modul în care blocurile ocupate își reprezintă lungimea ; rezolvarea deficienței este foarte ingenioasă : alocatorul menține un vector mare de numere, câte unul pentru fiecare pagină. Elementul i din vector reprezintă marimea blocurilor din pagina 5. Figura alăturată arată un exemplu de structuri de date ale alocatorului.
#define lista(marime) \
(marime) > 128 \
? (marime) > 256 ? 4:3 \
: (marime) > 64 \
? 2 \
(marime) > 32 ? 1 : 0
Avantajul unei astfel de expresii în locul bucle este că. Atunci când marimea este cunoscută la compilare, întreaga expresie devine o constantă care poate fi calculată de compilator, deci codul executat devine mult mai rapid.
Acest alocator este mai eficient decât cel cu puteri ale lui 2, și risipește mult mai puțină memorie, pentu că toate cererile egale cu o putere a lui doi sunt satisfăcute cu un buffer de mărime potrivită. Celelalte dezavantaje rămân însă prezente.
Vectorul de dimensiuni
Memorie
etc.
Pagina 0 pagina 1 pagina 2 pagina 3
Figura 20 Alocatorul Karels-McKusick
V.5 Alocatorul “slab“
O schemă mult mai sofisticată de alocare, inspirată din limbajele orientate pe obiecte o fost introdusă de Sun în sistemul de operare Solaris 2.4. și este acum implementată și în Linux. “Slab“ înseamnă în engleză “lespede“; acest alocator are zone de memorie diferite pentru obiecte diferite, pe care le putem vedea ca niște mozaicuri de forme diferite; de aici și numele. Acest alocator tratează cu multă atenție o serie de aspecte importante pentru performanță care sunt complet ignorate de alte alocatoare:
Alocatorul încearcă atunci când caută noi zone să nu atingă prea multe locații de memorie, pentru a nu încărca cache-ul microprocesorului cu date care nu sunt utile. Se spune că alocatorul are o urmă mică (small footprint);
Alocatorul încearcă să aloce obiectele în memorie în așa fel încât două obiecte diferite să nu pice în aceeași linie din cache-ul de date; asta maximizează utilizarea cache-ului când obiectele sunt folosite simultan. De exemplu obiectul care reprezintă în nucleu un fișier are câteva câmpuri care sunt foarte des folosite, aflate să zicem la începutul structurii, și alte câteva câmpuri care sunt extrem de rar folosite. Să presupunem că obiectul “fișier“ are 256 octeți; în acest caz toate câmpurile des folosite din toate fișierele se vor afla la adrese multiplu de 256. Din cauza asta ele se vor lupta pentru un set restrâns de linii din cache, în vreme ce celelalte linii vor fi prost utilizate. Alocatorul slab va încerca să aloce fiecare obiect la o adresă care nu e multiplu de aceeași valoare.
Alocatorul încearcă să reducă numărul de operații de inițiale asupra noilor obiecte alocate. De exemplu multe obiecte din nucleu care pot fi folosite de mai multe procese au un câmp care indică numărul de utilizatori (de exemplu un fișier memorează numărul de procese care au deschis fișierul). Când acest număr ajunge 0, înseamnă că obiectul nu mai utilizat și poate fi dealocat. Asta înseamnă că avem certitudinea că orice fișier dealocat va avea valoarea 0 în acel câmp. Atunci când alocăm un nou fișier, dacă folosim vechea zonă de memorie, știm deci că nu mai trebuie să inițializăm acest câmp, pentru că are deja valoarea corectă. Practic nucleul conține un cache cu obiecte de curând dealocate, pe care le folosește atunci când i se cer noi alocări.
Alocatorul slab constă de fapt într-o rutină centrală (numită kmem_cache_create) care creează alocatoare pentru fiecare obiect. Rutina aceasta primește ca parametrii numele obiectului, mărimea unui obiect, constrângerile de aliniere (de exemplu, toate obiectele trebuie să fie la o adresă multiplu de 16) și pointeri spre o funcție constructor și spre o funcție destructor.
Fiecare alocator are propria lui zonă de memorie, în care menține numai obiecte de acel tip; va exista astfel o zonă de pagini în care se alocă numai fișiere, , o zonă în care se alocă numai i-noduri, etc. În acest fel toate obiectele dintr-o zonă au aceeași dimensiune.
Fiecare alocator menține de asemenea o listă cu obiectele care au fost de curând dealocate, și le refolosește atunci când i se cer noi obiecte. Pentru că obiectele au fost dealocate , ele nu mai trebuie să fie inițializate din nou. Atunci când un alocator epuizează toată memoria pe care o are la dispoziție, el cere de la alocatorul de pagini o nouă pagină pe care o umple cu obiecte noi. Pentru că aceste obiecte nu au fost niciodată inițializate, alocatorul cheamă funcția constructor care a fost indicată pentru fiecare obiect nou. Acest constructor este bineînțeles chemat numai prima dată când pagina este obținută; după ce un obiect a fost dealocat constructorul nu mai este chemat din nou.
Fiecare alocator folosește propriile lui pagini într-un mod similar cu alocatorul cu puteri ale lui 2. La sfârșitul fiecărei pagini alocatorul rezervă a zonă pentru o structură de date care descrie ocupația acelei pagini. Primul obiect în pagină este plasat la o distanță aleatoare de marginea paginii. Acest deplasament are efectul de a pune obiecte din pagini diferite la adrese diferite în cache, exact cum am indicat mai sus.
Alocatorul slab poate returna sistemului de paginare paginile în care toate obiectele sunt nefolosite. Alocatorul are o “ urmă“ mică, pentru că majoritatea cererilor adresează o singură pagină. Acest tip de alocator risipește ceva resurse datorită modului de plasare în pagină și pentru că are o zonă diferită pentru fiecare tip de obiect. Performanța lui este însă excelentă și rămâne unul din cele mai puternice alocatoare implementate.
Pagina nr. 0
cu obiecte fișier
Pagina nr. 1
cu obiecte fișier
spațiu irosit informații
despre pagină
Figura 21. Alocatorul “slab“
Bibliografie
[1] Abraham Silberschatz, James L. Peterson – Operating Systems Concepts Addison – Wesley Publishing Company, 1989
[2] Bach, J. Maurice – The design of the UNIX operating system – Prentice- Hall, Inc., 1986
[3] Ionescu Traian, Saru Daniela, Floroiu John – Sisteme de operare Principii și funcționare – Editura Tehnică, București, 1997
[4] Norton Peter – Secrete PC – Teora, București, 1998
[5] Colecția revistei PC Report 1995 – 1999
[6] Solomon Marvin – Cursul ținut la Berkley University San Francisco – www.cis.temple.edu/courses-os.html
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: . Sisteme de Operare Si Metode de Alocare a Memoriei Principale (ID: 148994)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.