SISTEME DE OPERARE I. Introducere I.1. Sistem de operare Sistemul de operare este un program care acţionează ca o interfaţă între utilizatorul unui sistem de calcul şi hardware-ul acestuia. Menirea sistemului de operare este de a crea un mediu în care utilizatorul să poată executa programe cu mai multă usurinţă, iar pe de altă parte, de a asigura utilizarea eficientă a hardware-ului. În principiu, cele mai importante componente ale aproape oricărui sistem de calcul sunt: hardware, sistem de operare, programe de aplicaţii, utilizatori ( Figura 1 ).

Figura 1

Hardware-ul furnizează resursele de bază pentru efectuarea calculelor. Programele de aplicaţii definesc modul în care vor fi folosite aceste resurse pentru a rezolva problemele de calcul ale utilizatorilor. Sistemul de operare ( SO ) controlează şi coordonează utilizarea hardware-ului între diferite programe de aplicaţii ale utilizatorilor. SO furnizează instrumentele cu ajutorul cărora sa fie folosite în mod corespunzător resursele de bază ale sistemului de calcul ( hardware, software ). Din acest punct de vedere, sistemul de operare poate fi privit ca administrator al resurselor pe care le alocă în funcţie de necesităţile programelor şi utilizatorilor astfel încat exploatarea sistemului de calcul să fie corectă şi eficientă. O altă definiţie a SO pune accentul pe necesitatea controlului asupra dispozitivelor de intrare / ieşire (I/O) şi a programelor utilizatorilor. Astfel, un SO poate fi privit ca un program de control care urmăreşte efectuarea programelor utilizatorilor pentru a putea preveni eventualele erori, precum şi folosirea necorespunzătoare a sistemului de calcul, şi are deci ca principală sarcină operarea şi controlul cu / şi asupra dispozitivelor de I/O.

În concluzie, funcţiile comune de control şi alocare a resurselor ce sunt necesare programelor de aplicaţii sunt cumulate într-o singură componentă software: sistemul de operare. Cele mai vechi sisteme de calcul erau formate uneori din hardware şi puteau fi utilizate prin intermediul unei console: programatorul scria liniile de program şi apoi opera programul direct de la această consolă. Încarcarea programului în memorie, precizarea adresei de început şi lansarea în execuţie se realizau manual, cu ajutorul comutatoarelor panoului frontal. Evoluţia programului putea fi urmarită de către operator prin intermediul semnalelor luminoase ale consolei. Datele de ieşire se tipăreau sau erau perforate pe bandă de hârtie sau cartele pentru a fi tipărite ulterior. Programatorul îndeplinea şi funcţia de operator. Alocarea timpului de lucru în sistem se planifică de cele mai multe ori cu ajutorul unei scheme de rezervare în care fiecare utilizator îşi scria numele şi zona de timp pe care dorea să o foloseasca pentru propriile programe. În cazul în care un utilizator nu reuşea să execute şi să depaneze programul în perioada de timp pe care şi-o rezervase, era nevoit să abandoneze lucrul, deoarece zona de timp următoare era alocată altui utilizator. Cu trecerea timpului, o atenţie deosebită a fost acordată rutinelor care realizau operaţii de intrare şi de ieşire, deoarece fiecare dispozitiv de I/O avea caracteristici aparte, necesitând o programare adecvată. Pentru fiecare astfel de dispozitiv a fost scrisă câte o subrutină specială, numită driver, care să "ştie" cum trebuie să fie folosite buffer-ele, flag-urile, regiştrii, biţii de control şi biţii de stare proprii dispozitivului. Pentru realizarea operaţiilor de I/O utilizatorul nu mai era nevoit să includă în program codul necesar, ci putea sa apeleze doar driver-ul corespunzător din bibliotecă. Apariţia compilatoarelor destinate limbajelor de nivel înalt a determinat o nouă creştere a complexităţii operării în sistemele de calcul, uşurând în acelaşi timp munca programatorilor. Pregătirea execuţiei unui program scris în limbaj de nivel înalt presupune încărcarea compilatorului în memorie de pe banda magnetică, citirea programului sursă de pe un cititor de cartele şi depanarea programului executabîl direct prin intermediul consolei. I.2. Monitorizare simplă Timpii de pregătire a operaţiilor în cadrul unui sistem de calcul constituiau o adevarată problemă. Ca remediu, s-a adăugat o dublă soluţie: s-a creat postul de operator calificat, astfel încât programatorul nu mai avea acces direct la sistemul de calcul şi s-a hotărât gruparea job-urilor în funcţie de resursele necesare, astfel încât acestea să fie executate în grup ( prelucrarea pe loturi sau de tip "batch" ). Astfel, programatorîi furnizează cartelele perforate sau benzile ce conţineau programele, precum şi o scurtă descriere a job-urilor, operatorul grupa aceste job-uri şi le lansa în execuţie, colecta rezultatele şi le transmitea înapoi fiecărui utilizator. Operatorul nu putea depana un program pe care nu îl cunoştea, de aceea era necesară furnizarea unor informaţii de control programatorului. Pentru eliminarea timpilor morţi a fost introdusă secvenţierea automată a job-urilor, luând astfel naştere primul sistem de operare rudimentar. Cu ajutorul unui mic program numit monitor rezident, care se află permanent în memorie, s-a putut realiza transferarea automată a controlului de la un job la cel care îl urma şi de la un program la altul în cadrul

aceluiaşi job. Succesiunea etapelor de transfer era: monitor - program1 - monitor - program2 - monitor

Pentru ca monitorul să ştie ce program trebuia lansat în execuţie, operatorul îi furniza o scurtă descriere a programelor, precum şi a datelor cu care se executa rularea. Pentru a deosebi cartelele de comandă de cartelele ce conţineau programul sau datele, se foloseau caractere speciale în diferite coloane ($ sau //). Cele mai importante componente ale unui monitor rezident erau:

• interpretorul cartelelor de comandă ( în momentul execuţiei traduce fiecare comandă în limbaj maşină );

• modulul ce realizează încărcarea în memorie a programelor de sistem şi a programelor de aplicaţie ( leader );

• diverse dispozitive. I.3. Operare off-line şi operare on-line simultan cu mai multe periferice ( spooling ) Diferenţa considerabilă de viteză a operărîi existentă între unitatea centrală şi dispozitivele mecanice de I/O contribuia substanţial la scăderea eficienţei sistemului de calcul. A început să fie folosită aşa-numita operare off-line a cititoarelor de cartele şi a imprimantelor. Cartelele erau copiate pe bandă magnetică până în momentul în care aceasta se completa, după care informaţiile puteau fi citite în memoria calculatorului cu ajutorul unităţilor de bandă magnetică. În mod asemănator se realiza şi scrierea rezultatelor pe o bandă magnetică. Principalul avantaj al acestui mod de operare era posibilitatea ca o aceeaşi UC ( unitate centrală ) să folosească mai multe sisteme de cititor de cartele-banda şi bandă-imprimantă care să lucreze simultan şi să furnizeze suficientă bandă magnetică pentru ca timpul de lucru al UC să fie utilizat aproape complet. Odată cu operarea off-line, a apărut şi noţiunea de independenţă faţă de dispozitiv a programelor ( necesitatea ca o aceeaşi operaţie de I/O să poată fi realizată pe diferite dispozitive de I/O ); programele au fost scrise astfel încât să utilizeze dispozitive logice de I/O, corespondenţa dintre acestea şi dispozitivele fizice fiind indicată de către cartelele de comandă. Odată cu apariţţa discurilor magnetice, pregătirea off-line a job-urilor a fost abandonată. Discurile magnetice au permis operarea on-line, simultan, cu mai multe periferice ( spooling: Simultaneous Peripheral Operation On-Line ). Discul magnetic, privit ca un buffer de dimensiuni mari, poate fi folosit în scopul citirîi a cât mai multor informaţii de la dispozitivele de intrare şi al stocării fişierelor de ieşire, până în mometul în care dispozitivele de ieşire devîn disponibile şi le pot prelua. Discul are capacitatea de a înmagazina informaţii referitoare la mai multe job-uri, a căror evidenţă este ţinută cu ajutorul unui tabel gestionat de către SO. Deoarece pe disc pot exista şi job-uri gata de a fi executate, această structură de date purtând denumirea de rezerva de job-uri ( job pool ), SO poate să decidă ordinea în care vor fi lansate în execuţie, astfel încât să fie îmbunătăţit timpul de ocupare a UC. Devine deci posibilă planificarea job-urilor ( job scheduling ) şi este abandonată metoda de lucru ce se baza pe regula "primul sosit - primul servit". Metoda de operare a on-line, simultan, cu mai multe periferice, asigură utilizarea la

viteză foarte mare atât a UC, cât şi a dispozitivelor de I/O. I.4. Lucrul cu zone tampon ( buffering ) Lucrul cu zone tampon este strict legat de lucrul cu întreruperi şi reprezintă o funcţie a SO. Pentru fiecare dispozitiv de I/O, monitorul rezident sau driver-ele dispozitiv includ buffere sistem pentru intrări/ieşiri. În cazul lucrului cu întreruperi fiecare controller este dedicat unui anumit tip de dispozitiv şi gestionează o zonă buffer locală, precum şi un set de regiştri speciali, având ca sarcină transferarea datelor între dispozitiv şi zona sa de buffer ( Figura 2 ).

Figura 2 În momentul iniţierîi unei operaţii de I/O, UC înscrie regiştrii controller-ului şi apoi îşi reia secvenţa normală de lucru. Controller-ul examinează conţinutul regiştrilor, află ce operaţie trebuie efectuată ( citire sau scriere ), dă comanda începerîi transferului de date, pentru ca în momentul terminării să informeze UC prin emiterea unei întreruperi. În momentul primirii întreruperîi, UC îşi opreşte activitatea curentă şi transferă controlul la o locaţie fixă de memorie în care, de obicei, este înscrisă adresa de început a rutinei de tratare a întreruperii. Rutina transferă datele din buffer-ul local al dispozitivului în memoria principală. La terminarea acestei operaţii, UC îşi reia activitatea întreruptă anterior, în acest mod putându-se realiza operarea concurentă cu UC şi cu dispozitivele de I/O. Principalele funcţii ale sistemului de întreruperi sunt:

• transferarea controlului rutinei de tratare a întreruperîi; această funcţie se realizează prin rezervarea unui set de locaţii în zona adreselor mici de memorie ( primele 100, de exemplu ) în care să se afle adresele tuturor rutinelor de tratare a întreruperilor;

• salvarea adresei instrucţiunii pe care o execută UC în momentul în care a primit întreruperea, precum şi salvarea contextului ( de exemplu, starea unor regiştri ). Aceasta se poate face într-o locaţie fixă, într-o locaţie indexată prin numărul

dispozitivului sau în stivă. Scopul metodei de lucru cu zone tampon este creşterea eficienţei sistemului de calcul prin folosirea cât mai completă a timpului de lucrual UC şi al dispozitivelor periferice. După ce informaţia fost citită şi UC este gata să înceapă să o prelucreze, se dă comanda dispozitivului de intrare să iniţieze imediat următoarea citire, realizându-se astfel ocuparea simultană a UC şi a dispozitivului de intrare. În mod asemănător se realizează scrierea datelor. UC creează datele care sunt stocate într-un buffer până în momentul în care vor putea fi preluate de către dispozitivul de ieşire. Dacă viteza medie ( în înregistrări / sec) a UC şi a dispozitivelor de I/O este aceeaşi, UC trece puţin înaintea sau puţin în urma dispozitivelor de I/O, toate fiind folosite aproape de capacitatea maximă. Dacă UC este, în medie, mai rapidă decât un dispozitiv de intrare, metoda de lucru cu zone tampon nu este de mare ajutor. Dacă UC este totdeauna mai rapidă, ea va gaşi mereu un buffer gol şi va trebui să aştepte acţiunea dispozitivului de intrare. Pentru scriere, UC va putea funcţiona la puterea maximă, dar va trebui să aştepte intervenţia dispozitivului de ieşire în cazul în care toate buffer-ele sunt pline. Această situaţie apare la job-urile limitate I/O, pentru care numărul total de operaţii de I/O este foarte mare în comparaţie cu numărul calculelor efectuate şi, deoarece UC este mai rapidă decât dispozitivele de I/O, viteza de execuţie este limitată de viteza dispozitivelor şi nu de cea a UC. La cealaltă extremă, în cazul job-urilor limitate din punctul de vedere al UC, volumul calculelor este atât de mare încât buffer-ele de intrare sunt totdeauna pline, iar cele de ieşire sunt totdeauna goale; UC nu poate ţine pasul cu dispozitivele de I/O. Prin urmare, lucrul cu zone tampon este folositor, dar nu este suficient. I.5. Multiprogramare În general, un singur program utilizator nu poate să asigure ocuparea permanentă atât a UC cât şi a dispozitivelor de I/O. Posibilitatea de a stoca pe disc magnetic o rezervă de job-uri şi planificarea corespunzătoare a acestora în vederea execuţiei permit folosirea multiprogramării, o tehnică ce are drept scop îmbunătăţirea timpului de ocupare a UC. Într-un sistem multiprogramat, dacă job-ul aflat în execuţie trebuie să aştepte la un moment dat realizarea unei operaţii de I/O, UC nu va sta nefolosită, ci va fi alocată altui job în acest scop de către sistemul de operare. Atâta vreme cât rezerva de job-uri nu este vidă, UC lucrează din plin. I.6. Sisteme de tip time-sharing În cazul sistemelor cu prelucrare pe loturi ( de tip batch ), accesul la programe şi date se făcea în mod secvenţial, astfel încât, la un moment dat se putea executa un singur program de aplicaţie. O caracteristică a sistemelor de tip batch este lipsa de interacţiune între utilizator şi job în timpul execuţiei. Job-ul este pregătit şi prezentat pentru a fi executat iar, după un anumit timp, numit "turnaround time", se vizualizează rezultatul. Utilizarea sistemelor de tip batch este indicată în cazul job-urilor cu durată de execuţie mare şi care nu necesită prea multă comunicare utilizator-sistem.

Sistemele de calcul conventionale, interactive, permit comunicarea între utilizator şi sistem: utilizatorul transmite comenzi sistemului de operare sau, direct, unui program ( de obicei prin intermediul tastaturîi) şi primeşte răspunsul imediat. Sistemele interactive sunt folosite de obicei atunci când se doreşte executarea unor job-uri compuse din mai multe secvenţe de scurtă durată şi al căror rezultat nu poate fi prevazut.

SO de tip time-sharing au apărut din dorinţa de a realiza utilizarea interactivă a sistemelor de calcul la un preţ de cost rezonabil. Datorită planificării UC şi multiprogramării, un acelaşi sistem de calcul poate fi folosit simultan de către mai mulţi utilizatori, deserviţi în ferestre de timp diferite, dar suficient de mici pentru a da impreşia unei execuţii neîntrerupte a programelor. Ideea de bază este destul de simpla: în memoria sistemului, fiecare utilizator are un program separat a cărui execuţie necesită o perioadă de timp scurtă până în momentul încheierii sau până în momentul în care este necesară realizarea unei operaţii de I/O ce poate fi de tip interactiv. Deoarece aceste operaţii se realizează la nivelul vitezei umane de operare, ele necesită o perioadă de timp destul de lungă. De exemplu, operaţia de intrare este condiţionată de viteza cu care sunt apăsate tastele. Pe durata unor astfel de operaţii, pentru a elimina timpii de nefolosire a UC, SO va comuta rapid controlul UC asupra programului unui alt utilizator. Deoarece pentru fiecare utilizator este necesară numai o mica perioadă din timpul de lucru al UC şi controlul este comutat rapid de la un utilizator la altul, fiecare dintre aceştia are impreşia că lucrează singur în sistem, în timp ce, de fapt, sistemul de clcul este folosit în comul de către mai mulţi utilizatori. I.7. Mecanisme de protecţie Un SO este bine proiectat numai atunci când poate asigura execuţia corectă a programelor, chiar în cazul existenţei unui program scris incorect. Multe dintre erorile de programare pot fi detectate de către hardware şi sunt controlate în mod normal de către monitorul rezident. Dacă într-un program apare o instrucţiune nepermisă sau o greşeală de eroare a memoriei, hardware-ul va genera o întrerupere către monitorul rezident, numită capcană ( trap ). Termenul de capcană este folosit pentru a desemna o întrerupere internă, generată de obicei ca urmare a apariţiei unei erori în program. Acţionând ca o întrerupere, aceasta va determina memorarea contorului program asociat ultimei instrucţiuni şi va da controlul unei rutine a monitorului rezident. Înainte de a se aborda următorul job, monitorul execută în mod automat un vidaj de memorie şi registri, care poate fi utilizat în depanarea programului abandonat. Pentru a realiza protejarea tuturor programelor, datelor şi resurselor faţă de toate erorile ce pot să apară în funcţionare, sunt necesare 3 tipuri de protecţie: protejarea operaţiilor de I/O, protejarea memoriei şi protejarea UC.

Protejarea operaţiilor de I/O - pentru ca sistemul de calcul să se comporte diferit faţă de SO, pe de-o parte, şi faţă de programele utilizator, pe de alta parte, au fost adăugate două moduri de operare distincte: modul utilizator şi modul monitor ( numit şi mod supervizor sau mod sistem). Pentru indicarea modului curent de operare a fost adăugat hardware-ului un bit cu următoarea semnificaţie: 0=monitor; 1=utilizator. Atunci când monitorul rezident cedează controlul unui program utilizator, se trece în mod utilizator, bitul de mod primind valoarea 1. Dacă însă apare o capcană sau o întrerupere, hardware-ul comută modul de operare de la mod utilizator la mod monitor, dând bitului valoare 0.

Instrucţiunile de I/O pot fi definite ca instrucţiuni privilegiate, a căror execuţie este permisă de către hardware numai în mod monitor, de către driver-ele dispozitiv ( care fac parte din monitorul rezident). Dispare deci pericolul ca un program să citească/înscrie datele aferente altui program. Programul utilizator poate realiza operaţii de intrare/ieşire numai prin intermediul monitorului căruia îi cere să execute aceste operaţii în locul său cu ajutorul unei instrucţiuni speciale, numită apelare a monitorului sau apel de sistem ( system call ). Apelul sistem este tratat de către hardware ca o întrerupere software: prin intermediul vectorului de întreruperi se transferă controlul unei rutine a monitorului rezident, iar bitul de mod primeste valoarea corespunzătoare modului monitor.

Protejarea memoriei - în general, se doreşte protejarea monitorului rezident faţă de eventualele acţiuni ale programelor utilizator, precum şi protejarea programelor utilizator unul faţă de altul. Toate aceste sarcini revîn hardware-ului. Protejarea conţinutului memoriei situate înainte şi după zona ocupată de un program executabîl se poate realiza folosind doi registrîi limita, care să stocheze valorile limitelor superioară şi inferioară ale adreselor fizice ce pot fi generate de un anumit program utilizator ( Figura 3 ).

Figura 3 Regiştrii limită pot fi înscrîşi numai de către SO cu ajutorul unei instrucţiuni privilegiate speciale, deci nu pot fi accesate în nici un fel de către programele utilizator, execuţia instrucţiunilor privilegiate făcându-se numai în mod monitor. În timpul execuţiei, fiecare adresă generată în mod utilizator este comparată cu valorile conţinute în registrîi limită, astfel încât dacă un program care se execută în mod utilizator încearcă să acceseze memoria rezervată monitorului sau altui utilizator, se genereaza o capcană spre monitor ce va fi tratată ca eroare fatală ( Figura 4 ).

Acest mecanism împiedică programul utilizator să modifice ( accidental sau intenţionat ) codul sau structurile de date destinate monitorului sau altor programe utilizator.

Figura 4

Protejarea UC - pentru ca UC să nu fie monopolizată de către un singur utilizator, în arhitectura sistemelor de calcul a fost inclus un temporizator ( timer ) ce poate fi programat pentru a întrerupe funcţionarea calculatorului după o anumită perioadă de timp cu durată fixă sau variabilă. Implementarea unui temporizator cu durată variabilă se realizează, de obicei, cu ajutorul unui ceas şi a unui numărator: SO setează număratorul şi apoi, la fiecare tact de ceas, număratorul este decrementat, până când, ajungând la valoarea 0, se generează o întrerupere. Instrucţiunile cu ajutorul cărora poate fi modificat modul de operare al timer-ului sunt privilegiate. II. Structura sistemelor de operare II.1. Componentele sistemelor de operare În general, crearea unui software complex, aşa cum este un SO, este posibilă numai prin modularizare, fiecare componentă fiind bine definită şi având intrări, ieşiri şi funcţionalitate bine precizate. Gestionarea proceselor Menirea UC este atât de a asigura execuţia programelor utilizator, cât şi de a realiza alte activităţi, toate acestea purtând numele generic de procese. Un proces poate fi definit ca un program aflat în execuţie şi poate crea, la rândul său, subprocese cu execuţie de tip concurent. Un program constituie o entitate paşivă, în timp ce procesul este o entitate activă. Procesul se execută în mod secvenţial şi are nevoie de anumite resurse care i se alocă în momentul creărîi sale ( UC, memorie, fişiere, dispozitive de I/O etc. ), şi de nişte informaţii de iniţializare pentru a şti ce şi cum să prelucreze. Procesele pot fi atât de tip utilizator, cât şi de tip sistem. Din punctul de vedere al gestionării programelor aflate în execuţie, SO are

următoarele funcţii: • crearea şi desfiinţarea proceselor; • suspendarea şi reluarea proceselor; • asigurarea mecanismelor necesare sincronizării proceselor • asigurarea mecanismelor necesare comunicaţiei între procese • asigurarea mecanismelor pentru asigurarea interblocărilor

Gestionarea memoriei

Memoria reprezintă o colecţie de cuvinte sau de octeţi care pot fi accesate prin precizarea adresei ce le este asociată. Interacţiunea dintre UC şi memorie se realizează prin scrieri/citiri la/de la adresele de memorie specificate. Execuţia unui program presupune încărcarea sa în memorie, după ce au fost stabilite adresele absolute; în timpul execuţiei, programul accesează instrucţiunile şi datele din memorie prin intermediul adreselor, iar în momentul încheierii, spaţiul ocupat este eventual declarat disponibil, în el putând fi încarcat şi executat un alt program. Din punctul de vedere al gestionării memoriei, sistemul de operare are următoarele funcţii:

• păstrarea evidenţei partiţiilor de memorie folosite la un moment dat, precum şi a utilizatorilor acestora

• selectarea procesului ce va fi încarcat în memorie atunci când spaţiul devine disponibil

• alocarea spaţiului de memorie, precum şi operaţia inversă

Gestionarea memoriei auxiliare În timpul execuţiei, atât programele cât şi datele aferente trebuie să se afle în memoria principală. Deoarece aceasta are o dimensiune prea mică pentru a putea găzdui toate proramele împreună cu datele corespunzătoare, apare necesitatea ca sistemul de calcul să realizeze o memorare secundară cu ajutorul căreia să "descarce" memoria principală. Marea majoritate a sistemelor de calcul moderne utilizează pentru această operaţie discurile magnetice. Programele utilitare sunt păstrate pe disc până în momentul în care este necesară încărcarea lor în memoria principală şi apoi folosesc discul atât ca sursă, cât şi ca destinaţie a procesului.

Din punctul de vedere al gestionării discului magnetic, SO are următoarele funcţii: • gestionarea spaţiului liber pe disc; • alocarea memoriei pe disc; • planificarea lucrului cu discul.

Sistemul de intrări/ieşiri ( I/O ) Unul dintre scopurile SO este să uşureze munca utilizatorului uman şi prin preluarea sarcinii de "dialogare" cu dispozitivele de I/O. În general, sistemul de I/O are în componenţă:

• un sistem de buffere; • un cod general driver de dispozitiv; • direver-e pentru dispozitivele hardware specifice.

Gestionarea fişierelor Din punctul de vedere al gestionării fişierelor, sistemul de operare îndeplineşte următoarele funcţii:

• crearea şi stergerea fişierelor; • crearea şi ştergerea directoarelor; • funcţia de suport al primitivelor ce manipulează fişiere şi directoare ; • memorarea ordonată a fişierelor pe discurile magnetice; • salvarea fişierelor pe suporturi magnetice stabile ( nevolatile ).

Sistemul de protecţie Protecţia reprezintă mecanismul definit de către SO cu ajutorul căruia poate fi controlat accesul programelor, proceselor sau utilizatorilor la resurse. Un sistem de operare prevăzut cu mecanisme de protecţie poate asigura mijloacele necesare pentru a face distincţia între o utilizare permisă şi o utilizare neautorizată . Legarea în reţea Un sistem distribuit reprezintă un ansamblu de procesoare care nu folosesc în comun aceeaşi memorie sau un acelaşi ceas. Fiecare procesor are o memorie locală, iar comunicaţia între procesoare se realizează prin intermediul magistralelor de mare viteză sau prin linii telefonice. Legătura între procesoarele ce compun sistemul se realizează cu ajutorul unei reţele de comunicaţie ce poate avea diverse configuraţîi şi care poate fi conectată complet sau parţial. Sistemele distribuite asigură o viteză de calcul sporită, o bună disponibilitate a datelor, precum şi o fiabilitate ridicată, necesitând SO cu caracteristici speciale. Sistemul de interpretare a comenzilor Una dintre cele mai importante componente ale SO este interpretorul de comenzi, care se execută iniţial la începerea rulărîi unui job sau atunci când unul dintre utilizatorîi

unui sistem de tip time-sharing cere pentru prima dată permisiunea de intrare în sistem. O altă funcţie importantă a acestui modul software este citirea şi interpretarea instrucţiunilor de comandă prin intermediul cărora utilizatorul furnizează comenzi sistemului şi care se referă la gestionarea proceselor, a operaţiilor de I/O, a memoriei auxiliare, a memoriei principale, accesarea sistemului de fişiere, protecţia şi conectarea prin intermediul reţelei. II.2. Sarcinile sistemelor de operare O primă categorie de funcţii existente în cadrul oricărui SO are drept scop crearea mediului în care să se execute în mod corespunzător progamele, urmărind în acelaşi timp uşurarea sarcinii programatorului uman. Dintre acestea pot fi menţionate:

• executarea programelor; • realizarea operaţiilor de I/O; • manevrarea sistemelor de fişiere; • detectarea erorilor.

O altă categorie de funcţii este cea destinată realizării unei operaţii eficiente în cadrul sistemului de calcul. Apeluri de sistem

Apelurile de sistem reprezintă interfaţa dintre un program aflat în execuţie şi SO. Ele sunt disponibile atât sub forma de instrucţiuni scrise în limbaje de asamblare, cât şi ca funcţii sau subrutine apelabile în cadrul programelor scrise în limbaj de nivel înalt. Apelul de sistem poate fi generat prin intermediul unei rutine specializate, sau direct. Realizarea unui apel de sistem presupune existenţa mai multor informaţii al căror număr şi tip depinde de tipul sistemului de calcul, al sistemului de operare şi al apelului propriu-zis. În general, transmiterea parametrilor către SO se realizează în două moduri. Cea mai simplă metodă este folosirea regiştrilor. Totuşi, de multe ori, se întamplă ca numărul parametrilor să fie mai mare decât numărul regiştrilor, caz în care se preferă cea de-a doua metodă care presupune stocarea parametrilor în memorie, într-un bloc sau tabel, adresa blocului fiind înscrisă ca parametru într-un registru. Proiectanţii SO preferă această ultimă metodă, uneori chiar în cazul în care numărul parametrilor nu depăşeşte numărul regiştrilor. Apelurile de sistem pot fi clasificate în trei mari categorii:

• apeluri de sistem destinate controlului proceselor sau al job-urilor; • apeluri de sistem destinate gestionării dispozitivelor şi a fişierelor; • apeluri de sistem destinate gestionării informaţiilor.

Apeluri de sistem destinate controlului proceselor sau al job-urilor Execuţia unui program se poate încheia normal ( end ) sau forţat ( abort ). În cazul

terminării normale, prin intermediul apelului de sistem, SO transferă controlul interpretorului de comenzi care citeşte următoarea comandă. Dacă însă programul detectează o eroare în timpul execuţiei sau în datele utilzate şi decide să se încheie forţat, poate fi necesară mai întâi efectuarea unui vidaj de memorie şi afişarea unui mesaj de eroare, după care se apelează interpretorul de comenzi. Într-un sistem de tip interactiv, utilizatorul va furniza o nouă comandă, corespunzătoare erorîi depistate. Într-un sistem de tip batch, în mod obişnuit, interpretorul de comenzi încheie întregul job şi trece la tratarea următorului. Un proces sau un job care a lansat în execuţie un program, poate dori să încarce şi să lanseze în execuţie un alt program. Dacă la încheierea noului program controlul este returnat programului iniţial, trebuie ca imaginea acestuia să fie salvată în memorie şi să existe efectiv un mecanism care să permită apelarea unui program din cadrul altui program. Dacă ambele programe se execută în mod concurent, se consideră că a fost creat un nou job multiprogramat. De cele mai multe ori, în acest scop se foloseşte un apel de sistem special, numit create process sau submit job. Crearea unui nou job sau a unui nou proces presupune şi existenţa controlului asupra execuţiei sale, adică posibilitatea determinării şi resetărîi atributelor ( caracteristicilor ) job-ului sau ale altui proces: prioritatea, timpul maxim de execuţie permis etc ( get process attributes şi set process attributes). În cazul în care se doreşte forţarea încheierii unui job sau a unui proces creat anterior, se foloseşte un apel de sistem numit terminate process. Dacă însă nu se doreşte terminarea forţată a unui job sau a unui proces nou creat, se aşteaptă încheierea normală a execuţiei. Această aşteptare durează un anumit interval de timp ( wait time ), sau, de cele mai multe ori, durează până în momentul apariţiei unui anumit eveniment ( wait event ), care va fi semnalată de către job-ul sau procesul respectiv ( şignal event ). Apeluri de sistem destinate gestionării dispozitivelor şi a fişierelor În cadrul categoriei de apeluri de sistem care au ca obiect fişierele pot fi menţionate: crearea ( create ) şi ştergerea fişierelor ( delete ), pentru care este necesar să se cunoască numele şi unele dintre atributele fişierelor; deschiderea fişierelor ( open ); citirea ( read ), scrierea ( write ) şi repoziţionarea ( repoşition ) în fişier; închiderea fişierului ( close ) care indică închiderea seşiunii de lucru cu fişierul respectiv. Atunci când sistemul de fişiere este structurat în directoare, este necesar ca acelaşi set de operaţii să se poată aplica şi asupra directoarelor. În plus, atât pentru fişiere, cât şi pentru directoare, este bine să se poată determina valoarea diferitelor atribute ( get file attribute ) şi, eventual, acestea să poată fi resetate ( set file attribute ). Atributele fişierului includ numele său, tipul, codurile de protecţie etc. Fişierele pot fi considerate dispozitive aleatoare sau virtuale şi, de aceea, multe dintre apelurile de sistem folosite în cazul fişierelor sunt folosite şi în cazul dispozitivelor. Totuşi, în cazul sistemelor multi-utilizator, trebuie facută mai întâi o cerere către dispozitiv ( request ), pentru a asigura folosirea sa exclusivă, iar la încheierea seşiunii de lucru este necesar ca acesta să fie disponibilizat ( release ). Funcţiile descrise sunt similare cu open/close folosite în cazul fişierelor.

Apeluri de sistem destinate gestionării informaţiilor O mare parte dintre apelurile de sistem au fost create cu scopul de a asigura transferarea informaţiilor între programul utilizator şi sistemul de operare ( de exemplu, cele care furnizeaza ora <time> şi data curentă <date>). Alte apeluri furnizează informaţii despre sistem: numărul curent de utilizatori, numărul de verşiune al sistemului de operare, spaţiul total al memoriei neocupate sau spaţiul total disponibil pe discul magnetic etc. Programe de sistem În funcţie de operaţiile pe care le realizează, programele de sistem pot fi grupate în câteva mari categorii:

• gestionarea fişierelor: crearea, ştergerea, copierea, schimbarea numelui, tipărirea, listarea şi, în general, toate operaţiile care au ca obiect fiţiere şi directoare;

• informaţii de stare: programele respective cer sistemului data, ora, totalul spaţiului de memorie sau totalul spaţiului de pe disc, numărul de utilizatori sau alte informaţii de stare de acest tip care apoi sunt formatâte şi tipărite la terminal, pe un alt dispozitiv de ieşire sau sunt memorate într-un fişier;

• modificarea fişierelor: operaţie ce poate fi efectuată de către editoarele de texte, care pot crea sau modifica fişiere memorate pe disc magnetic;

• accesorii ale limbajelor de programare: de multe ori, odată cu sistemul de operare sunt furnizate şi compilatoare, asambloare şi interpretoare pentru limbajele de programare uzuale;

• încărcarea şi executarea programelor: pentru a fi executat, un program care a fost asamblat sau compilat, trebuie încărcat în memorie. În acest scop, au fost create programe ce realizează încărcarea la adresa absolută ( absolute loaders ), la adresa relocatabilă ( relocatable loaders ), editoare de legături ( linkage editors ) şi programe pentru încărcare cu suprapunere ( overlay loaders ). Depanarea unui program se poate realiza cu ajutorul unor programe specializate;

• programe de aplicaţii: odată cu SO sunt furnizate uneori programe ce au ca scop rezolvarea unor probleme uzuale, cum ar fi formatarea textelor, realizarea reprezentărilor grafice, gestionarea bazelor de date, analiză statistică etc.

Unul dintre cele mai importante programe de sistem este interpretorul de comenzi, a cărui principală funcţie este de a afla umătoarea comandă furnizată de utilizator şi de a o executa. Există două modalităţi de implementare a comenzilor. Prima presupune ca interpretorul de comenzi să conţină codul pentru execuţia comenzîi. În acest caz mărimea interpretorului depinde direct de numărul de comenzi, deoarece pentru fiecare comandă este necesar un cod propriu de implementare. Cea de-a doua modalitate presupune existenţa unor programe de sistem speciale, astfel încât nu mai este nevoie ca interpretorul de comenzi să înţeleagă comanda, ci o foloseşte pentru a indentifica un fişier care să fie încărcat în memorie şi executat.

II.3. Structura sistemelor de operare Cea mai răspândită tehnică de creare a unui SO modern este modularizarea, adică elaborarea unor subansamble software de dimensiune redusă, bine definite din punctul de vedere al intrărilor, al ieşirilor şi al funcţiilor pe care le îndeplinesc. Organizarea sistemului pe niveluri Cea mai utilizată metodă de modularizare a unui SO este organizarea sistemului pe niveluri, fiecare nivel fiind construit deasupra celor de rang inferior. Hardware-ul reprezintă nivelul de baza ( nivelul 0 ), în timp ce interfaţa utilizator reprezintă nivelul de ordin maxim ( nivelul N ). Un nivel reprezintă implementarea unui obiect abstract care grupează atât datele, cât şi operaţiile ce pot utiliza aceste date. Fiecare nivel foloseşte numai operaţiile furnizate de către nivelurile inferioare, necunoscând modul în care sunt implementate aceste operaţii, ci numai ceea ce fac ele. Existenţa structurilor de date şi a operaţiilor aparţinând nivelurilor inferioare este "ascunsă" nivelurilor superioare. Proiectarea nivelurilor se face astfel încât un nivel poate folosi numai operaţii şi servicîi ale nivelurilor inferioare, ceea ce uşureaza mult munca de depanare şi verificare a sistemului. Primul nivel poate fi depanat independent de restul sistemului deoarece, comform definiţiei, foloseşte pentru implementarea funcţiilor sale numai hardware-ului de bază, care se presupune că e proiectat şi implementat corect. Depanarea celui de-al doilea nivel se face pe baza bunei funcţionari a primului nivel. Localizarea unei erori se face uşor, la nivelul curent, deoarece toate celelalte niveluri ( de ordin inferior ) au fost depanate anterior. Nucleul sistemului Partea centrala a unui SO este nucleul ( kernel ). Principale sale funcţii sunt:

• asigurarea unui mecanism pentru crearea şi distrugerea proceselor; • furnizarea unor instrumente care să permită proceselor să-şi sincronizeze acţiunile; • realizarea planificării UC, gestionării memoriei şi a dispozitivelor pentru procesele

create; • furnizarea unor instrumente de comunicaţie care să permită proceselor să îşi

transmită informaţii. II.4. Proiectarea şi implementarea sistemelor de operare Obiectivele proiectării Prima problemp care apare în proiectarea unui SO este definirea obiectivelor şi a specificaţiilor sistemului. La nivelul superior, proiectarea este determinată de alegerea hardware-ului şi de tipul sistemului: cu prelucrare pe loturi, time-sharing, mono-utilizator, multi-utilizator, distribuit, în timp real sau de interes general. Utilizatorul doreşte ca

sistemul să poată fi folosit şi învăţat cu uşurintă, sa fie fiabil, sigur şi rapid. În mod asemănător, cei care proiectează, creează, întreţîn sistemul şi operează asupra lui doresc ca sistemul să fie uşor de proiectat, de implementat şi întreţinut, flexibil, fiabil, lipsit de erori şi eficient. Mecanisme şi strategii Un principiu extrem de important în proiectarea SO este separarea strategiei ( policy ), care decide ce anume trebuie făcut, de mecanism ( mechanism ) care arată cum trebuie făcut. Deciziile de tip strategic au un rol deosebit în toate problemele de alocare a resurselor, precum şi în cele referitoare la planificare. Separarea strategiilor de mecanisme asigură şi o buna flexibilitate a sistemelor, deoarece, în cazul trecerii pe un alt sistem, pot fi modificate doar strategiile, fără a mai fi nevoie să se modifice şi mecanismul de bază. Implementarea SO În mod tradiţional, etapa de implementare se realiza prin scrierea sistemului cu ajutorul limbajului de asamblare. În prezent, se pot folosi în acelaşi scop şi limbajele de nivel înalt. Avantajele utilizării limbajelor de nivel înalt pentru implementarea sistemelor de operare sunt aceleaşi ca şi în cazul scrierîi programelor utilizator: codul poate fi scris mai repede, este mai compact, mai uşor de înţeles şi de depanat. Principalul dezavantaj se referă la viteză şi la necesarul de memorie. Un compilator, oricât de performant, nu poate produce cod mai bun decât un limbaj de asamblare expert, dar este foarte probabîl ca un compilator să produca un cod cel puţin tot atât de bun ca şi cel scris într-un limbaj de asamblare obişnuit. Cu toate că dimensiunea unui SO e foarte mare, numai o mică parte a codului poate fi considerată ca fiind critică din punctul de vedere al performanţelor. Generarea sistemului De cele mai multe ori, SO sunt proiectate în aşa fel încât să poată lucra pe orice tip de calculator, într-o mare varietate de configuraţîi periferice. Din acest motiv, pentru fiecare tip de calculator este necesar ca SO să fie configurat sau generat, operaţie cunoscută sub numele de generarea sistemului. Deoarece SO este furnizat de obicei pe suport magnetic, pentru generare se foloseşte un program special, care citeşte dintr-un fişier sau cere operatorului informaţii referitoare la configuraţia hardware specifică a sistemului:

• tipul de UC şi opţiunile instalate; • cantitatea de memorie disponibilă; • dispozitivele existente în sistem; • opţiunile alese pentru SO sau valorile parametrilor ce vor fi folosiţi pentru

configurare.

Odată definite, informaţiile pot fi utilizate în moduri diferite.

III. Procese concurent Noţiunea de proces. Definiţii În cadrul sistemelor de operare moderne, se consideră ca unitate de lucru procesul secvenţial, definit ca entitate activă: un program aflat în execuţie ale cărui instrucţiuni sunt parcurse una câte una, la momente de timp diferite. Pentru a-şi îndeplini sarcinile, procesele au nevoie de anumite resurse ( timpul de lucru al UC, memorie, fişiere, dispozitive de I/O etc. ) care le sunt alocate în momentul creărîi. Dar, deoarece în sistem numărul resurselor hardware şi al celor logice este limitat, apare ca evidentă necesitatea ca resursele să fie utilizate în comun, în context multi-utilizator. De asemenea, dacă într-un sistem de calcul dotat cu mai multe procesoare se doreşte mărirea vitezei de lucru al unui program, se poate fragmenta acest program în subtask-uri care să se execute în paralel. În plus, sistemul de operare poate fi construit modular, funcţiile sale realizându-se prin intermediul unor procese distincte, a căror execuţie se desfăşoara la concurenţă cu cea a proceselor de tip utilizator. Există deci argumente care justifică existenţa proceselor concurente şi, implicit, necesitatea includerîi în cadrul sistemelor de operare a unor mecanisme destinate asigurărîi sincronizării şi comunicării între acestea. În timpul execuţiei, procesul îşi schimbă starea ( definită ca activitate curentă a procesului ) care poate fi: nou ( new ), activ ( active ), în aşteptarea unui eveniment ( waiting ) sau oprit ( halted ). În sistemele cu multiprogramare procesele active pot aştepta alocarea UC ( adică pot fi gata de execuţie ( ready ) ) sau pot să fie deja în posesia acesteia ( în execuţie ( running ) ) ( Figura 5 ).

Figura 5 În cadrul sistemului de operare, procesul este reprezentat prin blocul de control al procesului ( BCP ), un bloc de date care conţine informaţii specifice procesului la care se referă: starea procesului, valoare contorului program şi a regiştrilor UC ( utilizaţi în cazul apariţiei unei întreruperi), informaţii despre gestionarea memoriei ( valorile regiştrilor bază şi a regiştrilor limită sau a tabelei de paginare ), informaţii referitoare la sistemul de conturi utilizator, informaţii de stare referitoare la operaţiile de I/O ( cererile de I/O, dispozitivele de I/O alocate procesului, lista fişierelor deschise etc.), informaţii de planificare a UC ( prioritatea procesului, indicatori către "cozile" de planificare etc.).

Sistemul de operare poate crea sau poate şterge ( desfiinţa ) procese. În timpul execuţiei, prin intermediul apelurilor de sistem specializate, un proces ( numit "părinte" ) poate crea unul sau mai multe procese noi ( numite "copii" ), fiecare dintre acestea putând crea, la rândul lor, alte noi procese. Pentru a-şi îndeplini rolul, subprocesul nou creat are nevoie, în general, de anumite resurse ( timp de lucru al UC, memorie, fişiere, dispozitive de I/O ) pe care le poate obţine fie direct de la sistemul de operare, fie ca subset al resurselor procesului "părinte". "Părînţele" îşi poate împărţi în totalitate resursele "copiilor" săi sau poate disponibiliza, pentru a fi folosită în comun de către unii dintre aceştia, numai o parte a resurselor, cum ar fi memoria sau fişierele. Ultima metodă are avantajul de a preveni supraîncarcarea sistemului datorită creărîi prea multor subprocese. Odată create, procesele "copil" se execută la concurenţă cu "părînţele" sau, ca alternativă, "părînţele" se suspendă până în momentul încheierii execuţiei tuturor "copiilor" săi şi abia după aceea îşi reia funcţionarea. Terminarea normală a unui proces are loc după executarea ultimei sale instrucţiuni, moment în care se transmit şi anumite date ( de informare, de exemplu ) către procesul "părinte". Terminarea forţată a unui proces ( încheierea execuţiei sale înainte de parcurgerea tuturor instrucţiunilor componente ) poate fi impusă prin intermediul unui apel de sistem ( abort ) generat de către procesul "părinte" care trebuie să cunoască identitatea "copiilor" săi, pentru ai putea referi. Există mai multe situaţii în care procesul "părinte" poate cere încheierea forţată a execuţiei unuia dintre "copiii" săi: "copilul" a depăşit limita de folosire a resurselor ce i-au fost alocate ( caz în care este necesară existenţa unui mecanism care să permită "părintelui" să inspecteze starea "copilului" ), "copilul" nu mai este util, din punctul de vedere al funcţiei pe care o realiza etc. Există şi sisteme în care se interzice continuarea existenţei proceselor "copil" după momentul încheierii normale sau forţate a execuţiei procesului "părinte". În acest caz, sistemul de operare iniţiaza terminarea forţată a tuturor proceselor "copil" implicate ( terminare în cascadă ). Dacă execuţia unui proces nu poate afecta sau nu poate fi afectată de către execuţia altor procese din sistem, se spune ca procesul este independent. El poate fi oprit şi repornit fără a genera efecte nedorite, este determinist ( rezultatele depind numai de starea de intrare), nu se află niciodată în aceeaşi stare ca şi alte procese din sistem şi, evident, nu foloseşte în comun date ( temporare sau permanente ) cu acestea. Dacă însă execuţia procesului poate afecta sau poate fi afectată de către execuţia altor procese din sistem, se spune ca procesul este cooperant. În acest caz, procesul nu este determinist ( rezultatele depind de secvenţa relativă de execuţie, nu pot fi prevăzute cu anticipaţie ), nu este reproductibîl ( rezultatele nu sunt întotdeauna aceleaşi pentru aceleaşi condiţîi de intrare), se poate afla în aceeaşi stare ca şi alte procese din sistem şi, de cele mai multe ori, foloseşte în comun date cu acestea. IV. Planificarea unităţii centrale ( UC ) IV.1. Definiţii

Multiprogramarea reprezintă cel mai important concept folosit în cadrul sistemelor de operare moderne. Existenţa simultană în memorie a mai multor procese face ca, prin intermediul unui mecanism de planificare a UC, să se îmbunătăţească eficienţa globală a

sistemului de calcul, realizându-se o cantitate mai mare de lucru în timp mai puţin ( în general, un proces foloseşte UC până în momentul în care trebuie să aştepte, de exemplu, realizarea unei operaţii de I/O. Fără multiprogramare, pe durata realizării acestei operaţii UC rămâne inactivă. Altfel însă, sistemul de operare permite imediat unui alt proces să folosească UC, eliminând timpul de aşteptare din primul caz ). Deoarece în cadrul sistemului de calcul unităţii centrale îi revine sarcina complexă de a executa un mare număr de procese ( sau job-uri ) atât de tip utilizator cât şi de tip sistem, planificarea UC reprezintă o funcţie fundamentală a sistemului de operare. Acest mecanism se bazează în principal pe proprietatea proceselor de a se executa în forma unei succeşiuni de cicluri "rafală" alternative de folosire a UC ( ciclu "rafală" UC) şi de aşteptare a realizării unor I/O ( ciclu "rafală" I/O). Prin măsurarea duratei ciclurilor "rafală" UC s-a constatât că, deşi variază destul de mult în funcţie de proces şi de sistemul de calcul folosit, reprezentarea grafică a frecvenţei lor de apariţie este de tip exponenţial sau hiper-exponenţial ( Figura 6 ).

Figura 6

Atunci când un program conţine în mod predominant cicluri "rafală" UC de scurtă durată, se spune că el este limitat I/O; în mod analog, dacă programul include mai ales cicluri "rafală" UC foarte lungi, se spune că este limitat UC. Clasificarea programelor în funcţie de proprietatea menţionată influenţează deseori în mod hotărâtor alegerea algoritmului de planificare a UC. Procesele încarcate în memorie şi gata de a fi lansate în execuţie sunt grupate într-un şir de aşteptare ( şir ready ) în vederea alocării UC. Implementarea acestui şir ( numit de multe ori "coadă" de aşteptare) se realizează de obicei sub forma unei liste înlanţuite ale cărei elemente sunt blocurile de control asociate proceselor ( BCP ), fiecare BCP incluzând un indicator ( un pointer ) către procesul care îi urmează în şirul ready. Antetul listei conţine indicatorîi primului, respectiv, ultimului BCP.

Deoarece, pe lângă UC, procesele folosesc şi alte resurse ale sistemului de calcul, pentru fiecare din aceste resurse pot exista şiruri de aşteptare ( "cozi" ), numite de exemplu

şiruri dispozitiv sau şiruri I/O dacă este vorba de procesele ce aşteaptă eliberarea unui dispozitiv de I/O. În mod schematic, comportarea proceselor în raport cu resursele ce le sunt necesare poate fi reprezentate ca în Figura 7, în care se folosesc dreptunghiuri pentru şiruri de aşteptare şi cercuri pentru resursele ce deservesc şirurile, iar săgeţile arată evoluţia proceselor în cadrul sistemului.

Figura 7 Ori de câte ori UC devine inactivă, sistemul de operare, prin intermediul unei componente numite planificator, selectează pentru execuţie unul dintre procesele aflate în şirul ready. Planificatorul UC poate fi planificator pe termen lung ( de perspectivă ) sau planificator pe termen scurt ( imediat ) ( Figura 8 ).

Figura 8 Planificatorul pe termen scurt ( numit şi planificator UC ) selectează unul dintre procesele gata de execuţie aflate deja în memoria interna şi îi alocă UC. Deoarece multe procese conţin cicluri "rafală" UC foarte scurte ( câteva milisecunde ), planificatorul pe termen scurt are o frecvenţă de execuţie foarte mare şi, prin urmare, trebuie sa fie foarte rapid pentru a nu irosi timpul de lucru al UC.

Planificatorul pe termen lung ( numit şi planificator de job-uri ) stabileşte care sunt procesele ce vor fi încărcate în memoria internă a sistemului pentru a fi executate atunci când există mai multe cereri decât posibilităţi imediate de execuţie. De obicei, în astfel de situaţii, procesele se află memorate pe disc magnetic, de unde planificatorul pe termen lung controlează gradul multiprogramarii ( numărul proceselor din memorie ). În mod evident, frecvenţa de execuţie a acestui tip de planificator este mult mai mică şi el poate fi folosit mai mult timp decât planificatorul pe termen scurt pentru a selecta procesele. Deoarece în sistem pot exista atât procese limitate I/O, cât şi procese limitate UC, este important ca planificatorul pe termen lung să aleagă o proporţie optimă de procese aparţinând ambelor categorii, altfel şirul ready va fi aproape întotdeauna gol şi UC va fi folosită ineficient ( numai procese limitate I/O ) sau şirurile I/O şi respectiv dispozitivele asociate vor fi în aceeaşi situatie ( numai procese limitate UC ). Există şi sisteme care folosesc un nivel suplimentar de planificare prin intermediul unui planificator pe termen mediu ( Figura 9). Rolul acestuia este de a modifica gradul de multiprogramare atunci când este necesar, evacuând din memorie anumite procese ( care altfel ar concura pentru dobândirea UC ) şi reintroducându-le în momentul în care încărcarea sistemului permite reluarea execuţiei din punctul în care fusese întrerupta. Pentru aceasta metodă se foloseşte în limbajul de specialitate denumirea de swapping, ceea ce într-o traducere aproximativă ar însemna interschimbare sau, mai sugestiv, evacuare şi introducere din/în memorie a procesului. Planificatoarele pe termen mediu sunt incluse mai ales în cadrul sistemelor de tip time-sharing şi a celor cu memorie virtuală.

Figura 9 O altă componentă deosebit de importantă a sistemului de operare este dispecerul, care realizează efectiv transferarea controlului UC asupra procesului selectat de către planificatorul pe termen scurt, şi la fel ca şi acesta, trebuie sa fie foarte rapid pentru a putea executa în mod eficient operaţiile necesare: încărcarea regiştrilor procesului, comutarea în

mod utilizator, efectuarea saltului la locaţia corespunzătoare din programul utilizator pentru începerea/reluarea execuţiei acestuia. IV.2. Criterii de performanţă Atunci când se doreşte alegerea unui algoritm de planificare se pot lua în considerare mai multe criterii:

• gradul de utilizare al UC: teoretic, poate lua valori între 0% şi 100%, în practică însă, valorile variază între 40% ( pentru un sistem cu încărcare redusă ) şi 90% ( pentru un sistem cu încărcare mare );

• numărul de procese executate într-un interval de timp precizat ( throughput ): dacă procesele au durata mare de execuţie, se poate vorbi despre un proces pe oră, în timp ce dacă se lucrează cu procese scurte, valorile pot fi, de exemplu, de 15 procese pe secundă;

• durata totală de execuţie unui proces ( turnaround time ): reprezintă timpul scurs între momentul introducerii procesului în memorie şi momentul încheierii execuţiei sale; se exprimă ca suma perioadelor de timp de aşteptare pentru a intra în memorie, de aşteptare în şirul ready, de execuţie ( având alocată UC ) şi de realizare a operaţiilor de I/O;

• durata de aşteptare: algoritmul de planificare a UC influenţează numai mărimea duratei de timp pe care procesul o petrece în aşteptare în cadrul şirului ready; el nu afectează în nici un fel durata de execuţie a procesului sau volumul de timp destinat operaţiilor de I/O. Acesta este motivul pentru care criteriul enunţat este folosit deseori în locul celui anterior;

• durata de răspuns: reprezintă timpul scurs între formularea unei cereri şi iniţierea comunicării răspunsului corespunzător, fără a include durata comunicării propriu-zise ( se obţine astfel o apreciere a performanţelor independentă de performanţele dispozitivelor de I/O ). Criteriul este sugestiv, de exemplu, în sistemele interactive în care, la un moment dat, un proces poate produce date de ieşire, continuând să calculeze noi rezultate în timp ce rezultatele anterioare sunt prezentate utilizatorului.

Prin alegerea unui anumit algoritm de planificare a UC se doreşte în general optimizarea criteriului luat în considerare ( maximizarea în cazul primelor două şi, respectiv, minimizarea în cazul ultimelor trei ). Deseori se recurge însă la optimizarea valorii medii sau se urmăreşte minimizarea variaţiei duratei de răspuns asa cum se întamplă în cazul sistemelor de tip time-sharing ( se consideră că un sistem cu durata de răspuns moderată şi aproximativ constantă este mai performant decât unul a cărui durată de răspuns este mult mai scurtă, dar variază foarte mult ). IV.3. Algoritmi de planificare a UC Prezentarea cât mai fidela a funcţionarii algoritmilor de planificare a UC ar presupune utilizarea unor exemple care să includă un număr mare de procese, fiecare dintre ele fiind o secvenţă de sute de cicluri "rafală" UC şi I/O. Pentru ca toate acestea să nu afecteze întelegerea elementelor esenţiale, s-a preferat folosirea unei variante simplificate în

care fiecare proces conţine un singur ciclu "rafală" UC, iar performanţele sunt apreciate cu ajutorul Duratei Medii de Aşteptare ( notată DMA ). Algoritmul FCFS Algoritmul FCFS ( Firs Come First Served, cu înţelesul aproximativ "primul sosit-primul servit" ) este cel mai simplu algoritm de planificare a UC: primul proces care cere alocarea UC este cel care o obţine. Şirul ready este de tip FIFO ( First În First Out, adică "primul intrat-primul ieşit"): atunci când un nou proces devine gata de execuţie, blocul său de control se adaugă la sfarşitul şirului ready; ori de cate ori devine disponibilă, UC este alocată procesului aflat pe prima poziţie a şirului. Algoritmul SJF Algoritmul SJF ( Shortest Job First, cu înţelesul aproximativ de "se execută mai întâi cel mai scurt job" ) ia în considerare pentru fiecare proces următorul ciclu "rafală" UC pe care îl conţine şi alocă UC ( atunci când ea devine disponibilă ) procesului cu cel mai scurt ciclu "rafală" UC următor existent în şirul ready. În cazul în care există două procese cu aceeaşi durată a ciclului "rafală" UC următor, între ele se aplică regula FCFS. Se poate demonstra că planificând un proces scurt înaintea unui lung, durata de aşteptare a procesului lung ( Figura 11 ) şi, prin urmare, durata medie de aşteptare se reduce în mod substanţial. Din acest motiv, algoritmul SJF este optimal, asigurând o durată medie de aşteptare minimă, oricare ar fi setul de procese luat în considerare. Singura problema care apare este legată de cunoaşterea duratei ciclului "rafală" UC următor asociat fiecărui proces analizat.

Figura 11 Dacă se doreşte planificarea pe termen lung într-un sistem de tip batch, se foloseşte ca valoare durata limită a job-ului precizată de către fiecare utilizator în parte ( în cazul în care utilizatorul estimează şi precizează o valoare prea mică, poate să apară eroare de depaşire a limitei de timp, fiind necesară replanificarea job-ului ). Dacă însă se doreşte folosirea algoritmului pentru planificarea pe termen scurt, deorece nu se cunoaşte cu

exactitate durata ciclurilor "rafală" următoare ale proceselor implicate, se poate realiza doar o aproximare a funcţionării reale ( de exemplu, se poate predicta valoare unui ciclu "rafală" UC următor pe baza valorilor ciclurilor anterioare ). Algoritmi bazaţi pe priorităţi În cadrul acestui tip de algoritm, fiecărui proces i se asociază o prioritate ( reprezentată, în general, ca un număr cuprins într-o gama fixată de valori ), UC fiind alocată ( în momentul în care devine disponibilă ) procesului cu cea mai mare prioritate din şirul ready. SJF este un caz particular de algoritm bazat pe priorităţi în care prioritatea fiecărui proces este un număr invers proporţional cu mărimea ciclului "rafală" UC următor. Prioritatea se poate defini intern sau extern. Atunci când definirea este de tip intern, prioritatea procesului se calculează pe baza unei entităţi măsurabile cum ar fi, de exemplu, limita de timp, necesarul de memorie, numărul fişierelor deschise sau raportul dintre numărul mediu de cicluri "rafală" I/O şi numărul mediu de cicluri "rafală" UC. Dacă definirea este de tip extern, criteriile folosite sunt din afara sistemului de operare: tipul şi mărimea fondurilor rambursate pentru utilizarea calculatorului, departamentul care sponsorizeaza lucrarea, factorii politici etc. Principala problemă a algoritmilor bazaţi pe priorităţi este posibilitatea apariţiei blocării la infinit ( "înfometării" ) a proceselor care sunt gata de execuţie, dar, deoarece au prioritate redusă nu reuşesc sa obţină accesul la UC. O astfel de situaţie poate să apară într-un sistem cu încaracare mare în care se execută un număr considerabil de procese cu prioritate ridicată; acestea vor obţine mereu accesul la UC în detrimentul proceselor cu prioritate redusă care este posibil să nu se mai execute niciodată. O metodă de rezolvare a acestei probleme este "îmbătrânirea" proceselor, o tehnică prin care se măreşte treptat prioritatea proceselor care se constată că rămân în sistem un timp mai îndelungat. De exemplu, dacă priorităţile sunt cuprinse în domeniul 0 până la 64, se poate stabili ca la fiecare 10 minute să fie incrementată cu câte o unitate prioritatea proceselor rămase în aşteptare. În acest fel, chiar şi un proces cu prioritate iniţiala 0 va reuşi ca într-un timp destul de scurt să ajungă cel mai prioritar şi, prin urmare, să obţină accesul la UC ( să se execute ). Algoritmi preemptivi Toti algoritmii de planificare a UC descrişi anterior ( FCFS, SJF şi algoritmii bazaţi pe priorităţi ) sunt algoritmi ne-preemptivi: odată alocată, UC este folosită de către proces până în momentul în care acesta doreşte să o elibereze ( îşi încheie execuţia sau urmează să efectueze o operaţie de I/O ). Un algoritm preemptiv permite însă întreruperea execuţiei unui proces în momentul în care în şirul ready apare un alt proces cu drept prioritar de execuţie, sistemul de operare alocându-i imediat acestuia UC. Algoritmul FCFS este prin definiţie ne-preemtiv; ceilalţi doi algoritmi prezentaţi pot fi modificaţi, astfel încât sa devină preemptivi. SJF preemptiv se formuleaza astfel: dacă în şirul ready soseşte un proces al cărui ciclu "rafală" UC următor este mai scurt decât ceea ce a mai rămas de executat din ciclul "rafală" UC al procesului curent, se întrerupe execuţia celui din urma şi se alocă UC noului proces. Un algoritm preemptiv bazat pe priorităţi funcţionează într-un mod similar: ori de câte ori soseşte în şirul ready un nou proces,

prioritatea sa este comparată cu a procesului curent; dacă se constată că este mai mare, se întrerupe execuţia procesului curent şi se alocă UC procesului nou ( dacă algoritmul bazat pe priorităţi este de tip ne-preemptiv, execuţia nu se întrerupe, noul proces fiind pus la începutul şirului ready, comform priorităţiipe care o are şi aşteptând eliberarea UC ). Algoritmul Round-Robin Round-Robin este un algoritm de planificare a UC proiectat special pentru sistemele de tip time-sharing. Principalele sale caracteristici sunt definirea şi folosirea unei cuante temporale ( cu valori cuprinse între 10 ms până la 100 ms) şi tratarea şirului ready ca şir FIFO circular. Planificatorul alocă pe rând UC fiecărui proces din şir pe o durată egală cu cel puţin o cuantă ( se foloseşte un timer setat în mod corespunzător). Durata ciclului "rafală" UC al procesului curent este mai mică decât durata cuantei, însuşi procesul eliberează UC prin emiterea unei cereri de I/O sau prin comunicarea încheierii execuţiei. Dacă însă durata ciclului "rafală" UC depaşeste durata cuantei, timer-ul va genera o întrerupere şi procesul va fi inclus la sfârşitul şirului ready, după ce în prealabil contextul său a fost salvat în blocul de control asociat. Se poate spune deci ca algoritmul Round-Robin este un algoritm preemptiv, care asigură un timp aproape egal de aşteptare pentru toate procesele din sistem. Într-adevăr, dacă în şirul ready există N procese şi se lucrează cu o cuantă de valoare C, fiecare proces va folosi în total 1/N din timpul UC, fiecare alocare durând cel mult C unităţi de timp. Între doua alocări succesive către acelaşi proces durata de aşteptare va fi de cel mult (N-1)*C unităţi de timp. Şiruri de procese multnivel Atunci când procesele existente în sistem pot fi clasate în grupe diferite, în funcţie de anumite caracteristici ( de exemplu, valori ale timpului de răspuns, prioritate definită extern, necesar de memorie etc. ), se utilizează un algoritm de planificare pentru şiruri multinivel. Şirul ready este format din mai multe subşiruri, fiecare dintre acestea conţinând câte o categorie de procese şi având propriul algoritm de planificare. De exemplu, se pot crea două subşiruri: unul pentru procese interactive ( foreground ) şi altul pentru procese de tip batch ( background ); pentru primul se poate folosi un algoritm de tip Round-Robin, iar pentru cel de-al doilea un algoritm FCFS. Este important de reţinut faptul că şi între subşiruri trebuie să existe un algoritm de planificare ( de cele mai multe ori un algoritm preemptiv bazat pe priorităţi nemodificabile ). De exemplu, se poate stabili ca subşirul proceselor interactive sa aibă prioritate mai mare decât cel al proceselor de tip batch, ceea ce va face ca procesele din al doilea subşir să se poată executa numai atunci când primul şir este vid; dacă între timp apare un proces în primul şir, se întrerupe execuţia procesului curent şi UC este alocată noului sosit. O altă variantă de planificare între subşiruri este stabilirea câte unei perioade de timp în care fiecare dintre acestea să deţina UC în mod exclusiv. De exemplu, pentru subşirul proceselor interactive se poate acorda 80% din timpul total al UC, iar pentru subşirul proceselor de tip batch restul de 20%. Şiruri de procese multinivel cu feedback

Spre deosebire de algoritmul prezentat anterior, în care procesele, odată introduse într-un subşir, rămâneau în cadrul acestuia până la încheierea execuţiei, în cazul unui algoritm de planificare pentru şiruri multinivel cu feedback, se permite mutarea unui proces dintr-un subşir în altul, în funcţie de anumite caracteristici dinamice. Metoda favorizează procesele interactive şi procesele limitate I/O care sunt plasate în subşiruri cu prioritate ridicată, "retrogradând" procesele care folosesc UC un timp prea îndelungat în subşiruri cu prioritate redusă. De asemenea, previne apariţia fenomenului de "înfometare" ( blocare la infinit ) printr-o formă de "îmbătrânire": permite proceselor care asteaptă de prea mult timp în şirurile de prioritate redusă să "promoveze" în cadrul şirurilor de prioritate ridicată. Pentru a putea defini complet un algoritm de planificare pentru şiruri multinivel cu feedback este necesară precizarea mai multor parametri:

• numărul de subşiruri; • algoritmul de planificare asociat fiecărui subşir; • metoda de stabilire a subşirului în care intra procesul atunci când doreşte să se

execute; • criteriul şi metoda de "promovare" a unui proces într-un subşir cu prioritate ridicată; • criteriul şi metoda de "retrogradare" a unui proces într-un subşir cu prioritate redusă.

Având un înalt grad de generalitate, algoritmul de planificare pentru şiruri multinivel cu feedback este şi cel mai complex, oferind avantajul unor performanţe ridicate, dar necesitând în acelaşi timp un număr mare de informaţii pentru stabilirea valorilor optime în cazul parametrilor de configurare menţionaţi anterior.

V. Starea de interblocare Într-un sistem cu multiprogramare se întâmplă frecvent ca mai multe procese să concureze pentru folosirea unui număr finit de resurse. În cazul în care resursa cerută de către un proces nu este disponibilă, procesul va intra în starea de aşteptare. Dacă resursa cerută este menţinută în starea ocupat de către alt proces aflat la rândul său în aşteptare, apare interblocarea ( deadlock ), o situaţie nedorită în care procesele implicate nu reuşesc să-şi încheie execuţia, menţinând ocupate resursele sistemului şi împiedicând astfel celelalte procese să-şi înceapă la rândul lor execuţia. Resursele pot fi: resurse fizice ( imprimate, spaţiu de memorie, cicluri UC etc. ) sau resurse logice ( fişiere, semafoare, monitoare ). În general, se consideră că resursele sistemului sunt grupate în tipuri de resurse, fiecare dintre acestea fiind format dintr-un anumit număr de elemente identice. Ca exemple de tipuri de resursă pot fi enumerate: cicluri de UC, spaţiu de memorie, fişiere şi dispozitive de I/O ( în cazul în care sistemul conţine două UC, se spune că tipul resursă UC conţine două elemente.) Înainte de a putea utiliza o resursă, procesul formulează o cerere de acces, iar după terminarea operaţiei eliberează resursa respectivă. Atunci când un proces formulează o cerere de acces la un element al unui tip resursă, cererea va fi satisfacuta prin alocarea oricărui element aparţinand tipului precizat. Pe scurt, etapele parcurse de un proces în cursul utilizării unei resurse sunt:

• cerere de acces: dacă cererea nu poate fi satisfacută imediat, procesul care a

formulat-o va fi nevoit să aştepte până în momentul în care poate dobândi resursa; • utilizare: procesul poate folosi resursa; • eliberare: procesul elibereaza resursa.

Cererea şi eliberarea resurselor se realizează prin apeluri de sistem cum ar fi, de exemplu, apelurile de sistem pentru cerere/eliberare dispozitiv, deschidere/închidere fişier şi alocare/eliberare memorie sau prin intermediul operaţiilor cu semafoare, Wait şi Signal. Tot cu ajutorul apelurilor de sistem se poate realiza şi utilizarea resurselor ( de exemplu, pentru citirea sau scrierea unui fişier ). De aceea, sistemul verifică de fiecare dată dacă procesul a formulat cererea şi dacă i-a fost alocată resursa cerută, folosind un tabel de sistem în care se specifică pentru fiecare resursă faptul că este liberă sau este deja alocată, în aceasta ultimă situaţie fiind precizat şi procesul asociat. În cazul în care un proces cere o resursa deja alocată altui proces, procesul care a formulat cererea va fi adăugat la şirul de aşteptare asociat resursei în cauza. Se spune că un set de procese se află în starea de interblocare atunci când oricare proces din set se află în aşteptarea unui eveniment ce poate fi produs numai de către un alt proces din setul respectiv, principalele evenimente luate în discutie fiind dobândirea şi eliberarea resurselor ( desigur, interblocarea poate fi provocată şi de alte tipuri de evenimente ). Interblocările pot sa apară atât în cazul în care procesele concurează pentru dobândirea unui acelaşi tip de resursa, cât şi în cazul în care se cere acces la resurse de tip diferit. Pentru rezolvarea problemei interblocării se folosesc, în principiu, două metode. Prima metoda constă în utilizarea unui protocol care sa nu permită niciodată sistemului să intre în starea de interblocare. Acest deziderat se realizează fie prin prevenirea interblocării, fie prin evitarea interblocării. Cea de-a doua metoda permite sistemului intrarea în starea de interblocare şi rezolvă apoi această situaţie, reprezentând de multe ori o soluţie destul de dificilă şi costisitoare. V.1. Condiţii necesare pentru apariţia interblocării Interblocarea apare dacă şi numai dacă în sistem sunt îndeplinite simultan următoarele 4 condiţii:

• excluderea mutuală: există cel puţin o resursă ocupată în mod exclusiv ( adică fără a putea fi folosită în comun ) de către un singur proces; dacă un alt proces formulează cerere pentru aceeaşi resursă, va fi nevoit să aştepte până în momentul eliberării ei;

• ocupare şi aşteptare: există cel puţin un proces care menţine ocupată cel puţin o resursă şi asteaptă să obţină resurse suplimentare ocupate în acel moment de către alte procese;

• imposibilitatea achiziţionării forţate: resursele nu pot fi achiziţionate forţat, adică nu pot fi dobândite în mod "abuziv" de către un proces de la procesul care le ocupă la momentul considerat; resursele pot fi eliberate numai de către procesele care le ocupă, după ce acestea şi-au îndeplinit sarcinile;

• aşteptarea circulară: în sistem există un set de procese aflate în starea de aşteptare, ( P0, P1, ... Pn ), astfel încât P0 aşteaptă eliberarea unei resurse ocupate de către P1, P1 aşteaptă eliberarea unei resurse ocupate de către P2, ..., Pn aşteaptă eliberarea unei

resurse ocupate de către P0. Se observă că ultima condiţie implică şi condiţia de ocupare şi aşteptare, astfel încât cele patru condiţii nu sunt complet independente; cu toate acestea este util ca fiecare condiţie sa fie discutată şi tratată separat. V.2. Prevenirea interblocării Starea de interblocare poate fi prevenită dacă cel puţin una dintre condiţiile necesare şi suficiente pentru apariţia sa nu este îndeplinită. Excluderea mutuală În cazul tipurilor de resurse nepartajabile ( care nu pot fi folosite în comun ) această condiţie trebuie neaparat îndeplinită. De exemplu, o imprimantă nu poate fi folosită simultan de către mai multe procese. Pe de altă parte, deoarece resursele partajabile nu necesită acces mutual exclusiv, ele nu vor fi niciodată implicate într-o interblocare. Un exemplu edificator de resursă partajabilă sunt fişierele ce pot fi accesate doar pentru citire ( read only ). Dacă mai multe procese încearcă în acelaşi moment de timp să deschidă un fişier de acelaşi tip, li se poate acorda accesul simultan. În cazul unei resurse partajabile procesul nu va fi niciodată nevoit să aştepte. Totuşi, în general, nu este posibilă prevenirea interblocărilor prin neîmplinirea condiţiei de excludere mutuala, deoarece anumite resurse sunt în mod intrinsec nepartajabile. Ocupare şi aşteptare Pentru ca în sistem să nu fie îndeplinită niciodată condiţia de ocupare şi aşteptare trebuie să existe certitudinea că în momentul în care un proces cere o resursă el nu mai are alocate şi alte resurse. În acest scop se poate utiliza un protocol prin care, înainte de a-şi începe execuţia, fiecare proces să ceară şi să i se aloce toate resursele de care are nevoie. Implementarea se poate realiza impunând condiţia ca apelurile de sistem ce formulează cereri de acces la resurse să se produca înaintea altor apeluri de sistem. Un alt protocol care poate fi utilizat este cel ce permite unui proces să ceară resurse numai în cazul în care nu deţine niciuna; procesul poate să ceară anumite resurse şi să le utilizeze dar, înainte de a cere resurse suplimentare, trebuie să le elibereze pe cele care îi sunt deja alocate. Tipurile de protocol prezentate au două mari dezavantaje:

• gradul de utilizare a resurselor poate fi foarte redus deoarece multe dintre acestea pot fi alocate dar neutilizate o lungă perioada de timp;

• pericolul apariţiei "înfometării" ( starvation ): procesul care doreşte să obţină acces la mai multe resurse publice poate fi nevoit sa aştepte la infinit, în timp ce cel puţin una dintre resursele cerute este alocată permanent altor procese.

Imposibilitatea achiziţionării forţate

Cea de-a treia condiţie necesară pentru apariţia stării de interblocare este ca resursele deja alocate să nu poată fi achiziţionate forţat. Pentru a avea certitudinea că această condiţie nu va fi îndeplinită se poata folosi următorul protocol: dacă un proces care ocupă anumite resurse formulează cerere pentru o altă resursă ce nu îi poate fi alocată imediat ( adică procesul trebuie să aştepte), atunci toate resursele deţinute în mod curent vor fi "achiziţionate forţat" ( în mod implicit, toate vor fi eliberate ). Ele vor fi adăugate în lista de resurse a căror eliberare este aşteptată de către proces, iar acesta îşi va relua execuţia numai în momentul în care va reuşi sa dobândească atât vechile resurse, cât şi noua resursă pe care o ceruse. Ca alternativă se poate folosi următorul protocol: se verifică dacă resursele cerute de către un proces sunt disponibile. Dacă da, îi sunt alocate. Dacă nu, se verifică dacă nu cumva îi sunt alocate altui proces care se află în aşteptare de resurse suplimentare. Dacă da, resursele dorite vor fi achiziţionate de la procesul aflat în aşteptare şi vor fi alocate procesului care a formulat cererea. Dacă resursele nu sunt disponibile, sau sunt ocupate de către un proces aflat în aşteptare, procesul care a formulat cererea e nevoit sa aştepte. În acest timp este posibil ca unele dintre resursele sale să fie achiziţionate forţat, dar aceasta se întâmplă numai dacă sunt cerute de către un alt proces. Procesul îşi poate relua execuţia numai în momentul în care a obţinut atât alocarea noii resurse pentru care formulase cererea, cât şi a tuturor resurselor care îi fuseseră achiziţionate forţat în timp ce se afla în starea de aşteptare. Acest protocol se aplică frecvent în cazul resurselor a căror stare poate fi uşor salvataă şi apoi refacută, aşa cum sunt regiştri UC şi spaţiul de memorie ( celulele de memorie ), dar, în general, nu se poate aplica unor resurse ca imprimatele, de exemplu. Aşteptare circulară Pentru a împiedica îndeplinirea condiţiei de aşteptare circulara se poate impune o ordonare completă a tuturor tipurilor de resursă, asociind fiecărui tip de resursa un unic număr întreg care să permită compararea a două resurse şi să precizeze ordinea în care acestea sunt înscrise în şir. Fir R=(r1,r2,...,rn) setul de tipuri resursă. Se poate defini o funcţie de tip unu-la-unu, F:R→N, în care N reprezintă mulţimea numerelor naturale. Funcţia F poate fi definită în deplin acord cu ordonarea firească a folosirii resurselor în cadrul sistemului. De exemplu, dacă setul R conţine drivere de disc flexibil, drivere de hard disc şi imprimante, atunci funcţia F se poate defini astfel: F(driver_floppy) = 1 F(driver_disc) = 2 F(imprimanta) = 3 Pentru prevenirea interblocării se poate utiliza un protocol conform căruia fiecre proces poate cere resurse numai în ordinea crescătoare a enumerării. De exemplu, dacă un proces poate cere iniţial oricâte elemente de tip resursă ri, după aceea el poate cere elemente de tip resursă rk, dacă şi numai dacă F(rk)>F(ri). În cazul în care sunt necesare mai multe elemente aparţinând aceluiaşi tip resursă, trebuie formulată o singură cerere pentru toate. Ca alternativă se poate impune ca un proces să nu poată cere un element al tipului tipului resursă rk înainte de a fi eliberat deja toate resursele ri cu proprietatea F(ri)>F(rk).

V.3. Evitarea interblocării Algoritmii prezentaţi anterior realizează prevenirea interblocării prin stabilirea unor restricţii asupra modului în care se pot formula cererile de acces. Restricţiile impun cel puţin una dintre condiţiile necesare să nu fie îndeplinită, ceea ce conduce la imposibilitatea apariţiei interblocării. Această metodă are însă un dezavantaj: poate genera un grad redus de utilizare a dispozitivelor şi un volum de lucru în unitatea de timp destul de mic. O altă metodă, pentru evitarea interblocării, este folosirea de informaţii suplimentare referitoare la modul în care se va face cererea de acces la resurse. Cunoscând toată secvenţa de cereri şi eliberări de resurse pentru fiecare dintre procese se poate hotărî pentru fiecare cerere în parte dacă procesul va trebui sau nu să aştepte. În cazul fiecărei formulări de cerere se impune ca sistemul să ia în considerare resursele disponibile în momentul respectiv, resursele alocate deja, precum şi viitoarele cereri şi eliberări de resurse corespunzătoare fiecărui proces, pentru a putea decide dacă cererea curentă poate fi satisfacută sau trebuie să aştepte în vederea evitării apariţiei unei interblocări. Pentru implementarea acestei metode se folosesc în prezent mai mulţi algoritmi care diferă între ei prin tipul şi cantitatea de informaţie necesară. În cazul celui mai simplu şi mai des utilizat, fiecare proces trebuie să declare numărul maxim de resurse din fiecare tip de care ar putea avea nevoie. Dispunând apriori de o astfel de informaţie, se poate construi un algoritm prin intermediul căruia să se evite complet apariţia unei interblocări. Algoritmul examinează în mod dinamic starea alocării resurselor pentru a avea certitudinea că nu va aparea niciodată o condiţie de aşteptare circulară. Starea alocării resurselor este definită de numărul de resurse disponibile şi alocate şi de numărul maxim de cereri de resurse formulate de către procese. Se spune ca o stare este singură dacă sistemul poate aloca fiecărui proces resursele cerute ( până la numărul maxim ), într-o anumită ordine şi evitând apariţia interblocării. Mai exact, sistemul se afla într-o stare sigura numai dacă există o secvenţa sigură. Se spune că o secvenţă de procese <p1,p2,..,pn>este o secvenţă sigură pentru starea de alocare curentă dacă, pentru fiecare pi, resursele pe care pi le-ar mai putea cere pot fi alocate din resursele disponibile, la care se adăugă resursele deţinute de către toate celelalte pk, cu k<i. În acest caz, dacă resursele dorite de către procesul pi nu sunt imediat disponibile, pi trebuie să aştepte până când toate pk îşi încheie execuţia. În acel moment pi poate obţine toate resursele de care are nevoie, îşi completează sarcina, eliberează resursele şi se încheie, după care pi+1 poate obţine resursele pe care le doreşte şi asa mai departe. În cazul în care nu exista o astfel de secvenţă se spune ca starea sistemului este nesigură. O stare de interblocare este o stare nesigura. Totuşi, nu toate stările nesigure reprezintă interblocări ( Figura 12 ). O stare nesigură poate însă conduce la o interblocare. Atâta timp cât starea este sigură, sistemul de operare poate evita stările nesigure ( şi stările de interblocare ). Într-o stare nesigură sistemul de operare nu poate împiedica procesele să formuleze în aşa fel cererile de alocare a resurselor încât să nu apară interblocare: comportarea proceselor este cea care controlează stările nesigure.

Figura 12 Ca exemplu se poate utiliza un sistem în care patru procese, notate p0, p1, p2, p3, folosesc în comun un număr de 20 de resurse de acelaşi tip. Pe durata întregii execuţii procesele au nevoie de maximum 14, 6, 10 şi respectiv 9 resurse fecare. Iniţial procesele formulează carere pentru 7, 3, 4 şi respectiv 2 resurse. Analizând situaţia sistemului la momentul iniţial se constată că el se află într-o stare sigură deoarece, de exemplu, secvenţa <p1, p0, p2, p3> este o secvenţă sigură. Primind încă trei resurse din cele 4 rămase nealocate, procesul p1 îşi poate încheia execuţia, eliberând la rândul său 6 resurse. Procesul p0 primeşte aceste 6 resurse la care se adaugă resursa ramasă nealocată şi se încheie, eliberând în total 14 resurse care pot satisface necesarul celorlalte procese din sistem ( p2 şi p3 ). Se observă însă că este posibil ca dintr-o stare sigură să se ajungă într-o stare nesigură. Dacă, de exemplu, din starea iniţială a sistemului prezentat anterior, procesul p3 formulează cerere pentru încă două resurse şi acestea îi sunt alocate, se trece nu numai într-o stare nesigură ci, în mod evident, în stare de interblocare: numărul de resurse libere ( 2 ) este insuficient pentru oricare dintre procesele implicate în aşteptare ( 7 pentru p0, 3 pentru p1, 6 pentru p2 şi 5 pentru p3 ). Situaţia ar fi putut fi evitată numai dacă cererea formulată de procesul p2 ar fi putut fi respinsă, urmând a fi acceptată mai târziu, după încheierea execuţiei altor procese şi eliberarea resurselor ocupate de acestea. Ideea de bază în jurul căreia se construiesc algoritmii destinaţi evitării apariţiei interblocării este necesitatea ca în urma oricărei operaţii de alocare a resurselor, sistemul să rămână întotdeauna într-o stare sigură. Deoarece iniţial sistemul se afla într-o astfel de stare, ori de câte ori unul dintre procese formulează cerere pentru resursă disponibilă, sistemul trebuie să hotărască dacă resursa va fi alocată imediat sau dacă procesul trebuie să aştepte, cererea fiind satisfăcută numai în cazul în care prin alocarea resursei sistemul rămâne într-o stare sigură. V.4. Detectarea interblocării Atunci când sistemul nu utilizeză nici algoritmi de prevenire şi nici algoritmi de evitare, interblocarea poate să apară. În acest caz sistemul trebuie să furnizeze un algoritm

care să examineze starea sistemului pentru a afla dacă a apărut o interblocare şi un algoritm care să realizeze revenirea din starea de interblocare. Metodele de detectare şi revenire necesită însă cheltuieli suplimentare care includ nu numai costurile implicate de păstrarea informaţiei necesare şi executarea algoritmului de detectare, dar şi posibile pierderi inerente revenirii din starea de interblocare. Decizia de folosire a algoritmilor de detectare a interblocării este influenţată în principiu de frecvenţa apariţiei stării de interblocare şi de numărul proceselor implicate. Starea de interblocare poate să apară în momentul în care un proces oarecare formulează o cerere ce nu poate fi acceptată imediat. Algoritmul de detectare a interblocării se poate apela ori de câte ori se întâmplă ca o cerere de alocare să nu poată fi permisă imediat, caz în care poate fi identificat nu numai setul de procese interblocate, ci şi procesul care a determinat apariţia interblocări ( în realitate, fiecare dintre procesele interblocate face parte din bucla apărută în graful alocării resurselor şi, deci, se poate spune că toate aceste procese colaborează la apariţia interblocării ). Dacă în sistem există mai multe tipuri de resursă, o singură cerere poate determina apariţia mai multor bucle în cadrul grafului, fiecare buclă fiind completată de către cea mai recentă cerere şi "cauzată" de către un anumit proces ce poate fi identificat. Apelarea algoritmului de detectare a interblocării, ori de câte ori se formulează o cerere de resurse, poate avea ca efect un substanţial consum suplimentar de timp şi calcul. O variantă mai puţin costisitoare este apelarea algoritmului la intervale mai mari de timp, de exemplu la o oră sau ori de câte ori gradul de utilizare a UC scade sub 40% ( o interblocare poate conduce la "paralizarea" funcţionării sistemului şi deci la o scădere a gradului de utilizare a UC ). În cazul în care algoritmul de detectarea a interblocării este apelat la momente de timp alese în mod arbitrar, în graful resurselor pot exista simultan mai multe bucle şi, de aceea, în general, nu se va putea preciza care dintre procesele interblocate a "cauzat" interblocarea. V.5. Revenirea din starea de interblocare

În cazul în care algoritmul de detectare a interblocării a semnalat apariţia unei astfel de stări în sistem, revenirea poate fi realizată de către operatorul uman ( în mod manual ) sau de către sistemul de operare ( în mod automat ). Oricare ar fi varianta aleasă, se poate folosi una dintre următoarele două metode: încheierea forţată a execuţiei unuia sau a mai multor procese pentru a face să dispară aşteptarea circulară şi, respectiv, achiziţionarea forţată a unor resurse de la unul sau de la mai multe dintre procesele interblocate.

Încheierea execuţiei procesului

Această metodă pune la dispoziţia sistemului toate resursele ce fuseseră alocate până în acel moment proceselor care se încheie; se aplică sub una dintre următoarele forme:

• încheierea forţată a execuţiei tuturor proceselor interblocate: asigură eliminarea buclei de interblocare, dar este o metodă foarte costisitoare deoarece toate rezultatele obţinute prin execuţia proceselor până la momentul considerat trebuie abandonate, urmând a fi recalculate ulterior;

• încheierea forţată a execuţiei câte unui singur proces până în momentul în care se elimină bucla de interblocare: necesită un timp de calcul suplimentar destul de mare deoarece, după încheierea forţată a fiecărui proces, trebuie apelat un algoritm de detectare a interblocării pentru a constata dacă mai există sau nu procese interblocate.

Atunci când pentru revenirea din starea de interblocare se foloseşte cea de-a doua metodă, este necesar să se determine care proces ( sau care procese ) trebuie încheiat ( sau încheiate ), pentru ca interblocarea să fie eliminată. Această decizie, asemănătoare problemelor ce apar în planificarea UC, este de natură economică: vor fi încheiate forţat procesele care implică un cost minim. Din păcate însă, termenul de cost minim nu este foarte precis, procesele care vor fi încheiate forţat sunt alese în funcţie de mai mulţi factori, dintre care se pot enumera: prioritatea procesului, perioada de timp pe parcursul căreia s-a executat procesul şi cea care i-ar mai fi necesară pentru a-şi încheia execuţia într-un mod normal, numărul şi tipul resurselor ce au fost deja utilizate de către proces, numărul resurselor ce i-ar mai fi necesare procesului pentru a-şi încheia normal execuţia, numărul proceselor a căror execuţie ar trebui încheiată forţat etc. Achiziţionarea forţată a resurselor Această metodă asigură eliminarea stării de interblocare prin achiziţionarea succesivă a resurselor ocupate de anumite procese şi alocarea acestora altor procese până în momentul în care se realizează eliminarea buclei de interblocare. Principalele probleme care trebuie rezolvate în acest caz sunt:

• alegerea unei "victime": adică selectarea resurselor care vor fi achiziţionate forţat şi a proceselor implicate, urmărindu-se, evident, asigurarea unui "cost" minim; factorul cost poate să includă ca parametri, de exemplu, numărul resurselor ocupate de către procesul interblocat şi mărimea duratei de timp de execuţie consumate deja de către aceasta;

• reluarea execuţiei: un proces căruia i sa achiziţionat forţat o resursă nu-şi mai poate continua execuţia normală, ci trebuie "întors în timp" până când ajunge într-o stare sigură şi abia apoi, pornind din acea stare, execuţia procesului poate fi reluată; cea mai simplă soluţie este o revenire totală, adică încheierea forţată a procesului şi apoi reînceperea execuţiei; totuşi, "întoarcerea în timp" numai până acolo unde este necesar pentru a ieşi din interblocare este o metodă mai eficientă, cu toate că impune sistemului păstrarea mai multor informaţii despre starea tuturor proceselor aflate în execuţie;

• "înfometarea": în cazul unui sistem în care alegerea "victimei" se bazează, în principal, pe factorul cost, se poate întâmpla ca de fiecare dată să fie desemnat ca "victimă" acela;i proces, astfel încât el nu va putea niciodată să-şi încheie normal execuţia, pentru evitarea unei asemenea situaţii ("înfometare"), este necesar să se impună o limitare a numărului de alegeri ca "victimă" ale procesului, de exemplu prin includerea în factorul cost a numărului de "întoarceri în timp" ale acestuia.

V.6. Metode mixte de tratare a interblocărilor Practica a demonstrat că nici una dintre metodele de bază pentru tratarea interblocării

( adică prevenirea, evitarea şi detectarea ) nu poate acoperi întregul spectru de probleme de alocare a resurselor ce apar în cadrul sistemelor de operare. O posibilitate de rezolvare a acestor probleme este combinarea algoritmilor de bază descrişi anterior, ceea ce permite folosirea abordării optime a fiecărei clase de resurse din sistem. Metoda propusă are la bază ideea că resursele pot fi grupate în clase ordonate ierarhic, cărora li se aplică o tehnică de ordonare a resurselor, în interiorul fiecărei clase fiind utilizată pentru gestionarea interblocărilor cea mai potrivită metodă. Datorită folosirii tehnicii de ordonare a resurselor, o interblocare nu poate implica mai mult decât o clasă de resurse şi, cum în interiorul fiecărei clase se foloseşte una dintre abordările de bază, în sistem nu pot să apară interblocări. Ca exemplu, se poate considera un sistem format din 4 clase de resurse:

• resurse interne: resursele utilizate de către sistem ( de exemplu, blocul de control al procesului );

• memoria centrală; • resursele job-ului: dispozitive ( de exemplu un driver de disc flexibil ) şi fişiere ; • spaţiul din memoria auxiliară alocat fiecărui utilizator.

O metodă mixtă pentru rezolvarea interblocării în cazul acestui sistem ordonează clasele descrise anterior, folosind în cadrul fiecărei clase următoarele abordări:

• prevenirea interblocării prin ordonarea resurselor interne deoarece, în timpul execuţiei, nu este necesară alegerea uneia dintre cererile nerezolvate;

• prevenirea interblocării prin achiziţie forţată a memoriei centrale, deoarece se poate evacua oricând un job în memoria auxiliară, astfel încât memoria centrală aferentă acestuia să fie folosită în alt scop;

• evitarea interblocării în cazul resurselor job-ului, deoarece informaţiile necesare despre formularea cererilor de resurse pot fi obţinute din liniile de comandă;

• alocarea prealabilă a spaţiului din memoria auxiliară asociat fiecărui job utilizator deoarece, în general, se cunoaşte necesarul maxim de memorie al fiecărui job.

VI. Gestionarea memoriei VI.1. Suprapuneri ( Overlays ) În cazul în care este necesar ca întreg spaţiul logic de adrese al procesului să se afle în memoria fizică înainte ca acesta să fie lansat în execuţie, dimensiunea programului va fi limitată de dimensiunea memoriei fizice. Pentru a permite unui program să aibă o dimensiune mai mare decât a memoriei ce îi poate fi alocată se foloseşte uneori o tehnică numită suprapunere ( overlay ). Ideea de bază este de a păstra în memorie numai acele instrucţiuni şi date de care este nevoie permanent. Celelalte grupuri de instrucţiuni sunt încărcate şi evacuate în/din o zonă de memorie folosită în comun, numai atunci când această operaţie este necesară. Ca exemplu, se consideră cazul 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 trecerii 1, codul asociat trecerii 2, tabela de simboluri şi rutinele utilizate în comun de către ambele treceri. Trecerea 1 8 k Trecerea 2 10 k Tabela de simboluri 14 k Rutine comune 5 k Încărcarea tuturor acestor elemente necesită 37 k de memorie şi dacă, de exemplu, nu avem la dispoziţie decât 32k, programul nu va putea fi lansat în acelaşi timp. Poate fi deci definit un driver de suprapuneri ( 2k ) care să gestioneze memoria cu referire la existenţa a două module de program, încărcate succesiv, în acelaşi spaţiu: ( A ) tabela de simboluri, rutinele comune, trecerea 1 şi ( B ) tabela de simboluri, rutinele comune şi trecerea 2. În momentul încheierii execuţiei trecerii 1 ( modulul A ) are loc un salt la adresa drive-ului care determină aducerea în memorie a modulului B, supraînscrîind A şi apoi transferă controlul trecerii 2. Modulul A ocupă 29 K, în timp ce B are nevoie de 31 K, deoarece spaţiul de memorie disponibil este de 32K, execuţia asamblorului este posibilă. Codurile asociate lui A şi B pot fi păstrate pe disc magnetic sub formă de imagine memorie absolută şi sunt citite de către driverul de suprapuneri ori de câte ori este necesar ( execuţia va fi mai lentă datorită operaţiilor de I/O suplimentare ). Pentru realizarea suprapunerilor nu este necesar ca sistemele de operare să conţină funcţii speciale, implementarea acestor metode de gestiune a memoriei, care presupune folosirea unor algoritmi specializaţi pentru relocare şi înlănţuire, poate fi realizată complet de către utilizator cu ajutorul fişierelor. Cu toate acestea, proiectarea şi programarea corectă a structurii modulelor ce vor fi suprapuse în memorie rămâne o sarcină destul de complexă, care prespune o bună cunoaştere a întregului program. Fiind vorba de programe de dimensiuni foarte mari ( programele de dimensiuni reduse nu necesită suprapuneri ), acest deziderat este destul de greu de realizat, motiv pentru care se preferă ca în locul metodei ce foloseşte suprapuneri să se utilizeze tehnici automate care să permită executarea programelor mari în cadrul unui spaţiu de memorie limitat. VI.2 Încărcarea dinamică Modulele de program ( rutinele, de exemplu ) sunt stocate în format relocatabil pe disc magnetic, programul principal se reîncarcă în memorie şi se lansează în execuţie. Î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ă, reactualizeză tabelele în scopul înregistrării acestei modificări şi apoi cedează controlul noii rutine. Avantajul încărcării dinamice este că rutinele sunt aduse în memorie numai în momentul în care sunt apelate, rutinele neutilizate nu vor fi încărcate niciodată. Această metodă poate fi folosită, de exemplu, în cazul programelor de dimensiune mare care conţin module voluminoase destinate tratării unor situaţii de eroare mai puţin frecvente. Ca şi în cazul metodei suprapunerilor, încărcarea dinamică nu impune existenţa unor facilităţi suplimentare în cadrul sistemelor de operare, întreaga răspundere a corectitudinii

funcţionării revenind utilizatorului. VI.3. Gestionarea memoriei de către sistemul de operare Pentru un sistem dat, alegerea unei anumite metode de gestiune a memoriei depinde de mai mulţi factori, dintre care proiectarea hardware a sistemului ocupă un loc foarte important. Algoritmii de gestionare a memoriei descrişi în cele ce urmează îndeplinesc o aceeaşi cerinţă de bază: pentru ca un proces să poată fi lansat în execuţie trebuie ca mai întâi să fie încărcat în memorie întregul său spaţiu de adresare logică, restricţie care limitează dimensiunea unui progaram la dimensiunea memoriei fizice.

VI.3.1. Monitor rezident

Una dintre primele metode de gestionare a memoriei folosite în cadrul sistemelor de operare timpurii este cea care grupează memoria în două zone: una pentru utilizator şi una pentru monitorul rezident al sistemului de operare. Monitorul rezident poate fi plasat în zona inferioară a memoriei, sau în cea superioară ( cu referire la valoarea adreselor ). Principalul factor care influenţează această decizie este în general localizarea vectorului întreruperilor; deoarece acesta se află, de cele mai multe ori, în zona inferioară a memoriei, se preferă ca şi monitorul rezident să fie plasat în aceeaşi zonă. Dacă în sistem există un singur program utilizator, protejarea codului şi a datelor monitorului faţă de modificările accidentale sau intenţionate pe care acesta i le-ar putea produce se poate realiza prin hardware, implementându-se cu ajutorul unei scheme cu registru limită inferioară; folosirea unui registru limită superioară nu este necesară, deoarece în memorie nu există decât un singur utilizator. În situaţia în care se doreşte modificarea dinamică a dimensiunii monitorului ( şi deci a locaţiei limită inferioară ) în timpul execuţiei unui program, se pot folosi două alternative ale schemei de bază.

Prima metodă constă în încărcarea programului utilizator începând din zona superioară a memoriei, spre zona limită inferioară ( în loc de a se realiza încărcarea în sens invers ( Figura 13 ) ); principalul avantaj este că spaţiul neutilizat va rămâne în zona din mijloc a memoriei, unde, dacă este necesar, atât programul utilizator, cât şi monitorul se vor putea extinde.

A doua metodă, mai generală, constă în amânarea operaţiei de asociere a adreselor până în momentul execuţiei; schema de relocare dinamică necesită un suport hardware uşor diferit ( Figura 14 ). În acest caz, registrul limită inferioară se numeşte registru de relocare sau de bază; modificarea adresei de început a memoriei ce găzduieşte programul utilizator se poate realiza în orice moment şi constă în schimbarea valorii registrului de bază şi deplasarea întregii zone utilizator la locaţiile corecte în raport cu noua valoare. Programul utilizator lucrează cu adrese logice cuprinse în domeniul „0” – „maxim”, conversia acestora în adrese fizice din domeniul „R + 0” – „R + maxim”, în care R este valoarea limită inferioară, fiind realizată de către hardware-ul folosit pentru asocierea tabelată a adreselor de memorie.

Figura 13 Figura 14

VI.3.2. Multiprogramare cu partiţii fixate Într-un sistem cu multiprogramare, este necesar ca memoria să poată fi alocată în mod eficient numeroaselor programe aflate în rezerva de job-uri. Gestionarea cu partiţii fixate fragmentează memoria într-un număr de zone de dimensiune fixată, fiecare dintre acestea putând fi alocată câte unui program selectat dintre cele ce urmează a fi executate ( numărul de partiţii limitează deci gradul de multiprogramare). În momentul încheierii execuţiei, partiţia devine disponibilă pentru încărcarea altui program.

Figura 15

Deoarece în memorie pot exista în acelaşi timp mai multe programe, trebuie prevăzute şi mecanisme de protecţie. Pentru fiecare partiţie se pot folosi cîte doi regiştri limită ( va fi necesară o relocare statică în momentul asamblării sau al încărcării) sau câte o pereche registru bază – registru limită ( soluţia permite alocarea dinamică în momentul execuţiei ); registrul de bază conţine valoarea celei mai mici adrese fizice, în timp ce registrul limită conţine valoarea domeniului de adrese logice ( Figura 15 ).

Metode de planificare Selectarea de către planificator a unor job-uri aflate în rezervă pentru a fi încărcate în memorie se face în funcţie de necesarul de memorie declarat de acestea şi de partiţiile disponibile. În continuare vor fi prezentate câteva dintre strategiile folosite în acest scop. O primă metodă este clasificarea tuturor job-urilor în funcţie de necesităţile de memorie, în momentul apariţiei lor în sistem; se crează astfel câte o „coadă” de job-uri pentru fiecare partiţie. Clasificarea poate fi realizată pe baza informaţiilor referitoare la necesarul maxim de memorie furnizate de către utilizator sau determinate automat de către sistem. Fiecare „coadă” are propria partiţie de memorie şi va fi planificată separat ( nu apare concurenţa între „cozi” pentru accesarea memoriei). De exemplu, dacă există patru partiţii de memorie utilizator, de dimensiune 3K, 7K, 12K şi 20K, vor exista patru „cozi”, notate C3, C7, C12 şi C20 în care ar putea fi adăugat câte un job de dimensiune 2K, 7K, 10K şi respectiv 19K. O altă metodă este gruparea tuturor job-urilor într-o singură „coadă” din care planificatorul va selecta job-ul ce urmează a fi încărcat şi apoi, pentru a realiza alocarea, va aştepta până în momentul în care devine disponibilă o partiţie de memorie cu dimensiune corespunzătoare. Dacă planificatorul foloseşte o strategie de tip FCFS ( First Come First Served ), este posibil ca un job să fie nevoit să aştepte în „coadă” chiar dacă partiţia ce-i este necesară este disponibilă, numai pentru că înaintea lui se află job-uri cu necesar de memorie ce depăşeşte dimensiunile acesteia. Ca o consecinţă firească a acestei operaţii a apărut o variantă de palnificare ce nu permite partiţiilor de memorie să stea nefolosite. Atunci când o partiţie devine disponibilă se parcurge „coada” până la ultimul job care ar putea fi cuprins în ea şi se realizează alocarea, chiar dacă în „coadă” există alte joburi mai prioritare, dar cu dimensiune mult mai mare. Acordarea permisiunii de alocare a unui job mai mic ( dar mai puţin prioritar ) nu împiedică evoluţia acestor job-uri care, oricum, nu puteau folosi partiţia disponibilă din cauza dimensiunii necorespunzătoare. Metoda prezentată poate să apară şi în alte variante, în funcţie de strategiile de alocare a memoriei folosite:

• Best Fit Only ( cea mai bună potrivire ); se alocă partiţia cu dimensiunea cea mai apropiată de necesarul de memorie al job-ului; dacă nu este disponibilă, job-ul aşteaptă eliberarea ei;

• Best Available Fit ( cea mai bună potrivire disponibilă ); job-ului i se alocă prima partiţie disponibilă cu dimensiune suficient de mare ca să îl poată cuprinde.

Interschimbarea job-urilor ( Job Swapping ) Atunci când în sistem există mai multe job-uri cu dimensiune corespunzătoare unei aceleaşi partiţii, ele pot fi interschimbate ( introduse/evacuate în/din partiţia respectivă ). Presupunând, de exemplu, că se lucrează cu trei partiţii, pentru fiecare fiind folosit un algoritm de planificare de tip Round-Robin, în momentul epuizării unei cuante programul de gestionare a memoriei va evacua job-ul curent şi va introduce un alt job în partiţia respectivă ( Figura 16 ) În timpul desfăşurării acestor operaţii, planificatorul UC poate permite

executarea unui job din altă partiţie. Pentru ca în memorie să existe job-uri gata de execuţie ori de câte ori acţionează planificatorul UC, este de dorit ca programul de gestionare a memorie prin mecanismul descris anterior ( swapping ) să lucreze cu o viteză adecvată.

Figura 16

În cazul algoritmilor de planificare bazaţi pe priorităţi se foloseşte o variantă a metodei prezentate anterior, numită Roll Out / Roll In: dacă în şirul de planificare apare un job cu prioritate ridicată, programul de gestionare poate evacua un job mai puţin prioritar, care va fi reintrodus în memorie şi îşi va continua execuţia numai după ce job-ul prioritar s-a încheiat. În mod normal, un job care a fost evacuat va fi readus în aceeaşi partiţie, restricţie impusă atât de strategia de alocare, cât şi de metoda de relocare. Dacă relocarea se realizează în momentul asamblării sau în momentul încărcării ( relocare statică ), job-ul nu poate fi transferat într-o altă partiţie, dacă însă se lucreză cu relocare dinamică ( cu registru bază şi registru limită, de exemplu ) acest lucru este posibil. Interschimbarea job-urilor necesită o memorie externă cu acces direct, rapid, care să fie suficient de încăpătoare pentru a putea îngloba copii ale tuturor imaginilor memorie utilizator (de obicei se foloseşte în acest scop un disc magnetic performant). Toate procesele ale căror imagini memorie se află pe disc şi care sunt gata să între în execuţie se grupează într-o „coadă”, în timp ce procesele existente în memorie la momentul respectiv formează o „coadă” sistem separată. Atunci când planificatorul UC doreşte să lanseze în execuţie un proces, el apelează dispecerul care verifică dacă procesul se află în memorie. Dacă nu, şi dacă nu există nici o partiţie liberă, dispecerul evacuează din memorie unul dintre procese, introduce în locul său procesul dorit, reîncarcă regiştrile şi transferă controlul procesului selectat. Este important ca procesul ales pentru a fi evacuat să fie inactiv, altfel pot să apară eroări severe. Într-un sistem ce foloseşte interschimbarea job-urilor timpul de comutare a contextului este ridicat. Pentru creşterea eficienţei este de dorit ca timpul de execuţie al fiecărui proces să fie mare în comparaţie cu timpul necesar interschimbării.

Job-uri cu dimensiune variabilă Există situaţii în care un program aflat în execuţie generează pe baza datelor de intrare cereri suplimentare de memorie. Dacă datorită acestor cereri se depăşeşte dimensiunea partiţiei alocate deja job-ului, sistemul de operare trebuie să intervină. Există trei posibilităţi:

• încheierea forţată a job-ului: se consideră că formularea unei cereri suplimentare faţă de maximul necesar declarat înainte de alocarea partiţiei reprezintă o eroare de execuţie;

• returnarea controlului programului utilizator cu un indicator de stare care să specifice că nu există memorie în plus ; programul utilizator va decide apoi dacă se încheie imediat sau îşi modifică modul de operare, astfel încât să lucreze în spaţiul disponibil;

• atunci când există hardware de relocare dinamică, se evacuează job-ul, se aşteaptă eliberarea unei partiţii cu dimensiune mai mare, se încarcă job-ul în această partiţie ( relocându-l dacă este necesar ) şi se continuă execuţia; este o soluţie destul de costisitoare, dar asigură flexibilitate maximă programelor care doresc să-şi modifice cerinţele de memorie în funcţie de necesităţi.

Stabilirea dimensiunii partiţiilor Principala problemă a metodei de gestionare a memoriei ce utilizează partiţii de dimensiune fixată este găsirea unei bune corespondenţe între dimensiunile partiţiilor şi necesarul real de memorie al job-urilor. În proiectare, decizia iniţială se bazează pe un calcul probabilistic. Din momentul în care sistemul devine operaţional se pot obţine informaţii despre numărul şi dimensiunea job-urilor ce se execută, pe baza cărora să se stabilească apoi o structură a partiţiilor mult mai apropiată de necesităţile reale. În general, nivelul de performanţă al unui sistem de calcul depinde proporţional de nivelul de multiprogramare care, la rândul său, este direct afectat de modul în care este gestionată memoria: dacă, de exemplu, jumătate din spaţiul total de memorie rămâne neutilizat, înseamnă că folosind o metodă de gestionare mai bună ar fi posibil să se execute de două ori mai multe job-uri.

Fragmentarea memorie Un job cu un necesar de memorie de x cuvinte se poate executa într-o partiţie de dimensiune y cuvinte, dacă y>=x. Diferenţa de ( y-x ) cuvinte reprezintă o fragmentare internă, adică o cantitate de memorie conţinută în partiţia alocată, dar neutilizată. În cazul în care o partiţie este disponibilă, dar prea mică pentru oricare dintre job-urile aflate în aşteptare se spune că în sistem există fragmentare externă. Ambele tipuri de fragmentare generează risipă de memorie. De exemplu, dacă se separă o zonă de 44K în trei partiţii de câte 8K şi o partiţie de 20K, iar „coada” de planificare conţine job-uri ce necesită 15K, 6K, 10K, 10K, partiţia de 20K şi una dintre partiţiile de 8K pot fi alocate job-ului de 15K ( producând o fragmentare internă de 5K ) şi respectiv, job-ului de 6K ( producând fragmentare internă de 2K ). Deoarece restul job-urilor sunt prea mari pentru cele două partiţii disponibile ( fiecare având

câte 8K ), acestea rămân neutilizate, generând o fragmentare externă de 16K. Fragmentarea totală, atât internă cât şi externă, va fi de 23K, adică mai mult decât jumătate din întreaga memorie folosită în exemplu. Dacă memoria este grupată în partiţii de 20K, 8K, şi 16K, job-ul de 15K se poate executa în partiţia de 20K, job-ul de 6K în partiţia de 8K, iar unul dintre job-urile de 10K în partiţia de 16K, producând o fragmentare internă totală de 13K, dar eliminând fragmentarea externă. În cazul ideal în care dimensiunile părţilor se potrivesc exact dimensiunilor job-urilor se pot executa toate cele patru job-uri fără fragmentare internă sau externă. VI.3.3. Multiprogramare cu partiţii variabile În cazul utilizării metodei de multiprogramare cu partiţii de dimensiune fixată, cea mai dificilă problemă este optimizarea dimensiunii partiţiilor, astfel încât să se minimizeze fragmentarea memoriei ( internă şi externă ). Problema poate fi rezolvată dacă se permite modificarea dinamică a mărimii partiţiilor. Iniţial, programele utilizator au la dispoziţie întreaga memorie, considerată ca un bloc de dimensiune mare. Sistemul de operare generează şi apoi reactualizează un tabel în care păstrează informaţii despre zonele libere şi zonele ocupate ale memoriei. În momentul apariţiei unui job, se caută o zonă de memorie suficient de mare şi, dacă este găsită, se alocă job-ului numai dimensiunea cerută, restul de memorie disponibilă fiind păstrată pentru satisfacerea altor eventuale cereri. În general, în memorie se află “risipite” mai multe zone nealocate, de diferite dimensiuni. Atunci când apare un job care necesită memorie, este aleasă una dintre acestea, cu dimensiune suficient de mare pentru a satisface cerinţele job-ului. Dacă zona este prea mare, o parte se alocă job-ului, iar restul se reintegrează setului de zone disponibile. În momentul terminării execuţiei, job-ul eliberează memoria aferentă, care va fi şi ea inclusă în set. Dacă zona de memorie disponibilizată este adiacentă celorlalte, ele se pot contopi pentru a forma o zonă d dimensiune mare, moment în care se poate verifica dacă nu cumva există job-uri aflate în aşteptare care ar putea folosi această nouă hartă a memoriei. Această situaţie reprezintă un caz particular al problemei de alocare dinamică a memoriei ( care are ca obiect modul în care se poate satisface o cerere de dimensiune precizată având la dispoziţie o listă de zone de memorie disponibile ), pentru care există mai multe variante de rezolvare. Cele mai utilizate strategii de selectare a zonei de memorie ce urmează a fi alocată sunt:

• First Fit ( prima potrivire ): se alocă prima zonă de memorie disponibilă cu dimensiune suficient de mare pentru a satisface cerinţele job-ului;

• Best Fit ( cea mai bună potrivire ): dintre toate zonele de memorie disponibile a căror dimensiune permite alocarea job-ului, se alege zona cu cea mai mică dimensiune ( se minimizează fragmentarea internă );

• Worst Fit ( cea mai proastă potrivire ): se alocă zona de memorie disponibilă care are cea mai mare dimensiune.

La fel ca şi în cazul utilizării partiţiilor fixate, metoda care foloseşte partiţii de dimensiune variabilă se află într-o strânsă interacţiune cu planificarea job-urilor: există o listă a dimensiunii zonelor de memorie disponibile şi o „coadă” în care se plasează job-urile

ce formulează cereri de memorie, ordonată conform algoritmului folosit de către planificatorul de job-uri. Alocarea memoriei de desfăşoară normal până în momentul în care cerinţele de memorie ale unui jub nu mai pot fi satisfăcute doarece nu mai este disponibilă nici o zonă de memorie cu dimensiune suficient de mare. Planificatorul de job-uri va trebui să aştepte eliberarea unei astfel de zone sau să inspecteze „coada” pentru a găsi un job mai puţin prioritar, al cărui necesar de memorie să poată fi satisfăcut.

Suporul hardware minim necesar pentru implementarea metodei de gestiune a

memoriei folosind partiţii de dimensiune variabilă este aceeaşi ca şi în cazul metodei ce utilizează partiţii cu dimensiune fixă: doi regiştri în care să se păstreze valorile adreselor limită superioară şi inferioară ale partiţiei de memorie alocate job-ului. Atunci când planificatorul UC selectează procesul în vederea execuţiei, dispecerul încarcă în regiştri valorile corespunzătoare şi, deoarece fiecare adresă generată de către UC este verificată prin comparaţie cu conţinutul acestor regiştri, se asigură astfel protecţia celorlalte programe utilizator şi a datelor aferente faţă de modificările ce ar putea fi generate d către procesul curent. De fapt, deosebirea dintre metoda cu partiţii fixate şi cea cu partiţii variabile este determinată de către software, hardware-ul fiind acelaşi. Fragmentarea memoriei Metoda gestionării memoriei prin folosirea partiţiilor de dimensiune variabilă prezintă dezavantajul existenţei fragmentării externe, apărute în momentul în care cantitatea totală de memorie disponibilă este suficient de mare pentru a satisface o anumită cerere, dar nu formează o zonă contiguă, ci este risipită în mai multe zone de mică dimensiune. Metoda gestionării memoriei prin folosirea partiţiilor de dimensiune variabilă elimină însă aproape complet fragmentarea internă ( se alocă numai atâta memorie câtă are nevoie job-ul ce trebuie planificat ). Cu toate acestea, dacă zona disponibilă este doar puţin mai mare decât cea necesară, păstrarea evidenţei celor câţiva octeţi rămaşi nealocaţi ocupă mai multă memorie decât s-ar pierde prin alocarea şi neutilizarea lor. De aceea, se preferă ca în acest caz să se aloce întreaga zonă, introducându-se astfel, într-o mică măsură, fragmentare internă. Compactarea Compactarea reprezintă o metodă folosită pentru rezolvarea problemei fragmentării şi constă în deplasarea conţinutului zonelor de memorie astfel încît să se grupeze toate zonele libere într-un bloc de dimensiune mare. Pentru ca programele ce formau conţinutul zonelor de memorie să poată lucra la noile locaţii trebuie relocate toate adresele interne. Dacă este vorba despre o relocare statică, compactarea nu poate fi făcută; ea este posibilă numai dacă se foloseşte relocare dinamică, la momentul execuţiei, folosind regiştri limită şi de bază ( în acest caz va fi necesară doar mutarea programului şi a datelor şi apoi înscrierea noii adrese în registrul de bază ).

VI.3.4. Paginarea memorie

Paginarea este o metodă care rezolvă problema fragmentării în alt mod decât compactarea ei: ea permite ca memoria alocată unui program să nu fie contiguă, ceea ce înseamnă că programului îi poate fi alocată memorie oriunde există şi este disponibilă.

Suportul hardware Se consideră că memoria fizică ( atât cea internă cât şi cea auxiliară ) este separată în blocuri de mărime fixă numite cadre. Memoria logică este împărţită în blocuri de aceeaşi dimensiune numite pagini. Atunci când se doreşte lansarea în execuţie a unui program se transferă paginile sale din memoria auxiliară ( de obicei un disc magnetic cu acces rapid ) în oricare dintre cadrele disponibile ale memoriei interne. Fiecare dintre adresele generate de către UC este formată prin alipirea a două informaţii: numnărul paginii ( p ) şi deplasarea în pagină ( d ). Numărul paginii este utilizat ca index într-o tabelă de pagină care conţine adresele de bază ale cadrelor asociate paginilor programului respectiv. Adresa de bază împreună cu deplasarea în pagină definesc adresa fizică de memorie ce corespunde adresei logice generate de UC. Figurile 17 şi 18 ilustrează suportul hardware şi respectiv modelul de memorie cu paginare ( paginarea memoriei logice şi fizice ).

Figura 17

Figura 18

Dimensiunea în număr de cuvinte a paginii ( şi a cadrului ) este definită prin hardware. Dimensiunea paginii este de obicei o putere a lui 2, ceea ce uşurează separarea adresei logice în cele două componente: număr de pagină şi deplasare. Dacă mărimea unei pagini este de 2n unităţi de adresare ( octeţi sau cuvinte ), atunci cei mai puţini semnificativi n biţi ai adresei logice reprezintă deplasarea în pagină iar ceilalţi biţi, mai semnificativi, reprezintă numărul paginii. Planificarea job-urilor O particularitate deosebit de importantă a paginării este distincţia foarte netă între percepţia utilizatorului asupra memoriei şi realitatea fizică a acesteia. Programul utilizator consideră că este unicul beneficiar al unui spaţiu contiguu de memorie, în timp ce, de fapt, el este risipit în mai multe zone distincte, alături de alte programe. Corespondenţa între spaţiul de adresă utilizator ( logic ) şi cel real ( fizic ) este realizată de către hardware-ul de translatare a adresei ( de tabelare ), operaţie controlată de către sistemul de operare şi invizibilă pentru utilizator. Pentru a putea gestiona memoria, sistemul de operare trebuie să aibă la dispoziţie informaţii despre numărul total de cadre, cadrele alocate, cadrele disponibile etc., toate fiind păstrate într-o structură de date numită tabela de cadre. Fiecare intrare a acestei tabele corespunde câte unui cadru al memoriei fizice, înglobând principalele sale caracteristici: este liber sau este alocat, procesul căruia îi este alocată şi pagina asociată. La fel ca şi în celelalte cazuri, planificatorul de job-uri este influenţat în mod direct de către metoda de gestionare a memoriei. Planificatorul de job-uri examinează mărimea job-ului ce urmează a fi executat ( exprimată în număr de pagini), după care inspectează lista de cadre disponibile, ţinând cont de faptul că pentru memorarea fiecărei pagini utilizator este necesar un cadru în memoria internă. În urma alocării realizate de către planificator, paginile se încarcă pe rând în cadrele alocate, al căror număr va fi memorat în tabela de pagină al job-ului ( Figura 19-a – alocarea cadrelor libere înainte şi Figura 19-b – alocarea cadrelor libere după ). Tabela de pagină asociată fiecărui job se păstrează alături de alte valori semnificative în blocul de control al job-ului. Sistemul de operare păstrează câte o copie a tabelei de pagină, a contorului program şi a conţinutului regiştrilor fiecărui program utilizator, informaţii folosite şi de către dispecer în momentul comutării UC de la un proces la altul.

Figura 19 – a

Figura 19 - b

Fragmentarea memoriei Paginarea elimină fragmentarea externă: unui job îi poate fi alocat orice cadru, cu condiţia ca acesta să fie disponibil. Deoarece cadrele nu sunt considerate unuităţi de alocare a memoriei ( se alocă în întregime, nu parţial ), este însă posibilă apariţia fragmentării interne. Un exemplu în acest sens este situaţia în care dimensiunea job-ului nu este un

multiplu exact al dimensiunii paginii şi, prin urmare, ultimul cadru alocat nu este complet ocupat. În cel mai defavorabil caz un job poate fi format din N pagini şi 1 cuvânt, implicând alocarea a N+1 cadre, ceea ce va genera o fragmentare internă aproape egală cu dimensiunea cadrului. Implementarea tabelei de pagină În cazul în care dimensiunea tabelei de pagină este destul de redusă, se poate utiliza pentru implementare un set de regiştri specializaţi, foarte rapizi, care să asigure o eficienţă ridicată a translatării adreselor ( eficienţa este o cerinţă foarte importantă deoarece orice acces la memorie se face numai prin intermediul tabelei de pagină ). Instrucţiunile destinate încărcării sau modificării acestor regiştri sunt privilegiate, putând fi realizate numai de către sistemul de operare. Dacă însă dimensiunea tabelei de pagină este mare, se preferă ca ea să fie păstrată în memoria principală, într-o zonă indicată de valoarea unui Registru de Bază al Tabelei de Pagină ( RBTP ). Atunci când se doreşte să se lucreze cu altă tabelă de pagină decât cea curentă, este suficient să se încarce registrul cu o altă valoare, reducându-se astfel în mod substanţial timpul de comutare a contextului. O particularitate a acestei variante de implementare este faptul că accesarea unui cuvânt de memorie utilizator necesită două operaţii de acces la memorie ( unul pentru tabela de pagină şi altul pentru cuvântul propriu-zis ), viteza de operare fiind micşorată de două ori. Folosind valoarea din RBTP deplasată cu numărul de pagină – p ( conţinut în adresa logică ), se determină mai întâi numărul de cadru – c asociat paginii ( pe durata unui prim acces la memoria ce conţine tabela de pagină ). Numărul de cadru – c împreună cu deplasarea de pagină – d ( conţinută în adresa logică ) furnizează apoi adresa fizică reală, cu ajutorul căreia se poate accesa cuvântul utilizator dorit. O a treia variantă de implementare, care rezolvă şi problema expusă anterior, constă în utilizarea unei memorii hardware speciale, rapide şi de mică dimensiune ( set de regiştri asociativi ) cu următoarele proprietăţi: fiecare registru are două componente, numite cheie, şi respectiv, valoare; precizându-se un anumit element, el este comparat simultan cu toate cheile şi, dacă se depistează o coincidenţă, se extrage câmpul valoare corespunzător. Dacă regiştri asociativi se folosesc împreună cu tabelele de pagină, în cadrul câmpului cheie se memorează numărul de pagină iar în câmpul valoare, numărul cadrului asociat. Deoarece acest tip de hardware este destul de costisitor, numărul regiştrilor asociativi nu poate fi prea mare şi, prin urmare, setul conţine numai câteva dintre intrările tabelei de pagină. Atunci când UC generează o adresă logică, dacă numărul de pagină coincide cu una dintre chei, numărul de cadru devine imediat disponibil şi este folosit pentru a accesa memoria; timpul necesar pentru realizarea întregii operaţii este cu cel mult 10% mai mare decât cel aferent unui acces direct la memorie. Dacă însă numărul paginii nu coincide cu nici una dintre chei, pentru obţinerea numărului cadrului asociat trebuie efectuat un acces la tabela de pagină aflată în memoria internă. Informaţia astfel obţinută va fi folosită atât pentru accesarea memoriei utilizator, cât şi pentru a fi adăugată în cadrul regiştrilor asociativi ( împreună cu numărul de pagină asociat ), ca să poată să fie regăsită rapid în cadrul unei referiri ulterioare. Din punctul de vedere al timpului efectiv de acces la memorie, s-a demonstrat că folosirea a 8 până la 10 regiştri asociativi asigură o încetinire a operaţiilor de memorie cu aproximativ 20% până la 10% faţă de accesul direct, ceea ce constituie un avantaj în raport

cu performanţele celei de-a doua variante de implementare prezentate.

Paginarea în sisteme de time-sharing Unul dintre avantajele paginării ( important mai ales în cazul sistemelor de tip time-sharing ) este posibilitatea folosirii în comun de către job-uri diferite a unui acelaşi cadru al memoriei fizice. Singura condiţie este ca în acel cadru ( sau în acele cadre ) să fie memorat cod reentrent ( numit şi cod pur ), adică un cod care nu se poate modifica în timpul execuţiei. Datorită proprietăţii de reentranţă, este posibil ca două sau mai multe procese să execute simultan acelaşi cod, fiecare proces păstrând o copie a regiştrilor şi a datelor proprii ( care sunt diferite ). În memoria fizică este deci necesar să se păstreze o singură copie a codului comun ( fiecare tabelă de pagină indică spre acelaşi/aceleaşi cadru/cadre ), în timp ce paginile corespunzătoare datelor proceselor sunt memorate în cadre diferite. Exemplele de utilizare sunt numeroase: editoarele de texte, compilatoarele, asambloarele, sistemele de baze de date, sunt numai câteva dintre produsele software ce pot constitui cod folosit în comun, simultan, de către mai mulţi utilizatori a unui sistem de tip time-sharing. Principalul avantaj al acestei metode este eliminarea risipei de memorie ( Figura 20 – accesarea în comun a codului în cazul paginării ).

Figura 20 Cerinţa de reentranţă fiind strictă, codul folosit în comun trebuie să fie accesibil numai pentru citire ( read only ), asigurarea acestei protecţii fiind o sarcină a sistemului de operare. În general, protejarea paginilor se realizează prin asocierea unor biţi de protecţie,

incluşi în tabela de pagină. De exemplu, cu un singur bit se poate permite acces de citire/scriere sau doar de citire. Deoarece pentru fiecare referire a memoriei se foloseşte tabela de pagină, odată cu calcularea adresei fizice se pot verifica şi biţii de protecţie. O încercare de scriere într-o pagină marcată numai pentru citire, de exemplu, va genera o „capcană” ( trap ) hardware către sistemul de operare, având semnificaţia de a semnaliza violarea protecţiei memoriei.

VI.3.5. Segmentarea memoriei De cele mai multe ori utilizatorul unui sistem percepe memoria nu ca pe o succesiune de cuvinte ( aşa cum este ea în realitate ), ci mai curând ca pe o colecţie de zone contigue ( nu neapărat ordonate ) în care sunt stocate modulele componente ale programelor ( proceduri, funcţii, etc. ) şi structurile de date aferente ( tabele, matrici, vectori, stive, variabile etc. ). Deoarece fiecare dintre module are o anumită funcţionalitate, de cele mai multe ori zonele de memorie în care sunt stocate ( numite şi segmente ) diferă ca dimensiune şi pot fi identificate prin nume: „funcţia pondere”, „programul principal”, „matricea A”, etc. În cadrul unui segment, un anumit element poate fi referit prin precizarea deplasării faţă de începutul segmentului: „a treia instrucţiune a funcţiei Pondere”, „prima instrucţiune a programului principal”, „al doilea element al vectorului V”, etc. Segmentarea reprezintă o metodă de gestionare care acceptă şi foloseşte această viziune a utilizatorului asupra memoriei. Ea tratează programul utilizator ( spaţiul de adrese logice ) ca pe o colecţie de segmente, fiecare segment fiind caracterizat prin nume şi lungime. În consecinţă, utilizatorul are obligaţia de a preciza fiecare adresă logică prin două elemente: un nume de segment şi o deplasare ( în cazul paginării, utilizatorul specifică adresa logică, separată apoi de către hardware într-un număr de pagină şi o deplasare! ). De obicei, pentru simplificarea implementării, se preferă numerotarea segmentelor şi apelarea lor prin număr, nu prin nume. De cele mai multe ori, segmentele sunt create în mod automat, în urma asamblării, compilării, etc. De exemplu, un compilator Pascal poate crea segmente distincte pentru: variabile globale, stiva cu care lucrează procedurile, codul fiecărei funcţii sau proceduri, variabilele locale ale fiecărei funcţii sau proceduri. Programul de încărcare va asocia numere tuturor segmentelor astfel create.

Suportul hardware Segmentarea implică existenţa unei corespondenţe între adresa logică bidimensională definită de utilizator ( numărul de segmente – s şi deplasarea în cadrul segmentului – d ) şi adresa fizică unidimensională ce îi este asociată în memorie. Această corespondenţă este realizată prin intermediul tabelei de segment ( Figura 21 ) care conţine un număr de intrări egal cu numărul de segmente din programul respectiv. Fiecare intrare a tabelei conţine informaţii despre adresa de bază a segmentului ( notată „bază” în figură ) şi despre dimensiunea acestuia ( notată „dim” în figură ) şi poate fi accesată prin folosirea ca index a numărului de segment. Dacă deplasarea precizată în cadrul adresei logice nu satisface relaţia 0<d<dim, sistemul de operare va fi sesizat printr-o “capcană” cu semnificaţia „încercare de adresare în afară segmentului”. Dacă însă deplasare se încadrează între limitele permise, valoarea ei se adaugă la valoarea adresei de bază a segmentului, formându-se astfel adresa din memoria fizică a cuvântului dorit ( se poate afirma deci, prin analogie, că tabela de segment este o colecţie de perechi de regiştri bază/limită).

Figura 21

Figura 22 Pentru exemplificare se poate folosi situaţia prezentată în Figura 22, care ilustrează

dispunerea în memorie a unui program format din patru segmente ( numerotate de la 0 la 3 ). Pentru fiecare dintre acestea , tabela de segment conţine câte o intrare separată, în care se păstrează adresa de început a segmentului în memoria fizică ( bază ) şi dimensiunea segmentului ( dim ). Astfel, deoarece segmentul 1 începe la locaţia 1500 şi are dimensiunea 500 de cuvinte, referirea cuvântului 25 al segmentului 1 corespunde în memoria fizică locaţiei 1500+25=1525, în timp ce referirea cuvântului 630 al aceluiaşi segment va genera o „capcană” către sistemul de operare.

Implementarea tabelei de segment Soluţiile de implementare a tabelei de segment sunt asemănătoare celor folosite în cazul tabelei de pagină. O primă variantă ( preferată pentru tabelele de segment de mici dimensiuni ) este utilizarea unor regiştri rapizi care să asigure o viteză de acces foarte mare şi, eventual, efectuarea simultană a operaţiilor de comparare a deplasării cu dimensiunea segmentului şi respectiv a însumării deplasării cu adresa de bază a segmentului. Atunci când programul este format dintr-un număr mare de segmente se preferă ca tabela de segment să fie păstrată în memorie. Pentru a putea fi accesată, se foloseşte un registru bază al tabelei segment ( RBTS ) şi, deorece programele nu conţin acelaşi număr de segmente, se utilizează în plus un registru lungime al tabelei de segment ( RLTS ). În acest caz, pentru fiecare adresă logică ( s,d ) se verifică mai întâi corectitudinea numărului de segment ( 0<s<RLTS ) şi apoi se însumează numărul segmentului cu conţinutul RBTS, rezultând astfel adresa din memorie a intrării tabelei de segment ce va fi citită. După aceea se procedează în mod obişnuit: se compară deplasarea cu dimensiunea segmentului şi se calculează adresa fizică a cuvântului dorit ca sumă a deplasării şi a adresei de bază a segmentului. La fel ca şi în cazul paginării, cea dea doua variantă de implementare a tabelei de segment necesită două accese de memorie pentru o singură adresă logică, obligând sistemul de calcul să funcţioneze de două ori mai încet. Soluţionarea acestei probleme presupune folosirea unui set de regiştri asociativi în care să se păstreze cele mei recent utilizate intrări ale tabelei de segment. Un set destul de redus de regiştri asociativi ( 8 sau 16 ) poate asigura rezultate destul de performante: timpul de acces la memorie va fi doar cu cel mult 15% până la 10% mai mare decât în cazul accesului direct.

Segmentarea în sisteme de time-sharing La fel ca şi în cazul paginării, segmentarea oferă atât posibilitatea folosirii în comun de către mai mulţi utilizatori a aceluiaşi ( sau aceloraşi ) segment(e) cât şi asigurarea protecţiei segmentelor cu ajutorul unor biţi dedicaţi, incluşi în tabela de segment. Ca exemplu, se poate folosi situaţia în care un program conţine segmente de instrucţiuni şi segmente de date. Deoarece, în general, într-o arhitectură modernă de calcul nu este permis ca instrucţinile să se automodifice, segmentelor de instrucţini li se pot asocia protecţii care să permită accesul doar pentru citire sau doar pentru execuţie. Verificarea biţilor de protecţie este realizată de către hardware în momentul efectuării operaţiilor de punere în corespondenţă a adresei logice cu cea fizică. Se pot detecta astfel multe dintre erorile de programare uzuale, înainte ca ele să provoace neplăceri semnificative.

Pentru fiecare job, blocul de control ( folosit de către dispecer în momentul comutării UC între procese ) conţine alături de alte informaţii şi tabela de segment. Atunci când intrările în tabelele de segment aparţinând unor job-uri diferite indică aceeaşi locaţie fizică, segmentul respectiv va fi folosit în comun ( mecanismul este asemănător cu cel prezentat în cazul paginării ). Consecinţa firească este că orice informaţie poate fi folosită în comun dacă este definită ca segment. Deoarece acest mecanism funcţionează şi pentru mai multe segmente, rezultă că şi programele ( colecţii de segmente) pot fi la rândul lor, folosite în comun de către mai mulţi utilizatori ( aparenta simplitate a mecanismului ascunde şi anumite subtilităţi pe care programatorul este bine să le cunoască ).

Fragmentarea memoriei Sarcina de a găsi şi de a aloca memorie pentru toate segmentele programului utilizator revine planificatorului de job-uri. Situaţia este asemănătoare cu cea apărută în cazul paginării, cu excepţia faptului că aici lungimea segmentului este variabilă ( paginile aveau toate acceaşi dimensiune ). Aceasta înseamnă că este vorba despre o problemă de alocare dinamică, la fel ca şi în cazul metodei de gestionare a memoriei prin partiţii cu dimensiune variabilă, pentru a cărei soluţionare se pot folosi algoritmi de tip Best Fit sau First Fit. Dacă nici una dintre zonele contigue de memorie, disponibile la momentul considerat, nu este suficient de mare pentru a cuprinde un anumit segment, poate să apară fragmentarea esternă. În general, dacă dimensiunea medie a segmentelor este redusă, fragmentarea externă nu va fi semnificativă. Rezolvarea acestei probleme se realizeză cu aceleaşi metode ca şi în cazul gestionării memoriei prin partiţii cu dimensiune variabilă. Paginarea segmentelor Atât paginarea cât şi segmentarea au avantaje şi dezavantaje. Acesta este motivul pentru care, uneori, s-a preferat combinarea celor două metode de gestionare a memoriei prezentate anterior. Un exemplu în acest sens este şi paginarea segmentelor ( Figura 23 ), în cadrul căreia se foloseşte avantajul eliminării fragmentării externe oferit de către paginare ( pentru alocare poate fi folosit oricare dintre cadrele disponibile ). Deosebirea dintre această metodă şi segmentare este aceea că intrare tabelei de segment nu conţine adresa de bază a segmentului ci adresa de bază a unei tabele de pagină asociată acestui segment. Segmentul este format dintr-un număr de pagini de aceeaşi dimensiune. Deplasarea în cadrul segmentului se exprimă prin număr de pagină şi deplasare în pagină. Cu numărul de pagină folosit ca index în tabela de pagină a segmentului, se obţine numărul cadrului care, în final, se combină cu deplasarea în pagină şi formează adresa fizică. Deoarece ultima pagină a fiecărui segment nu este întotdeauna complet ocupată, metoda introduce totuşi o cantitate redusă de fragmentare externă ( în realitate, atunci când se lucrează cu tabele de segment de dimensiuni mari, mecanismul este ceva mai complicat ).

Figura 23 VII. Sistemul de fişiere

Sistemul de fişiere are ca principală sarcină gestionarea în mod transparent pentru utilizator a accesului la entităţile de stocare a datelor - numite fişiere – care sunt memorate pe medii nevolatile.

Operaţiile realizate de către un sistem de fişiere se referă la: • denumirea şi manipularea fişierelor, acestea fiind accesibile utilizatorilor ca

entităţi cu nume şi asupra cărora se pot efectua operaţii ( citire, scriere, execuţie ); • asigurarea persistenţei datelor, care presupune pe de o parte independenţa

acestora faţă de crearea sau distrugerea proceselor din sistem, şi pe de altă parte posibilitatea refacerii structurii şi a conţinutului lor în caz de accident;

• asigurarea mecanismelor de acces concurent al proceselor din sistem la datele stocate.

VII.1. Structuri şi tipuri de fişiere

Din punctul de vedere al structurii, există mai multe categorii de fişiere: • secvenţa de octeţi: fişierul se prezintă ca o secvenţă de octeţi a cărei interpretare este

lăsată la latitudinea programelor utilizator. Acest tip oferă maximum de flexibilitate în reprezentarea datelor, fiind utilizat în sisteme de operare precum UNIX, Windows etc.;

• secvenţa de înregistrări: fişierul este organizat ca succesiune de înregistrări de lungime fixă, operaţiile de citire şi scriere realizându-se la nivel de înregistrare. În prezent, această structură nu mai este utilizată;

• structura arborescentă: fişierul este format din înregistrări care conţin atât informaţia propriu-zisă, cât şi un câmp cheie ( situat pe o poziţie prestabilită în cadrul fiecărei înregistrări ). Valoarea câmpului cheie este folosită de către sistemul de operare pentru gestionarea unei structuri logice interne de tip arbore a fişierelor. O astfel de structură este utilizată în calculatoare de mare capacitate dedicate procesării masive de date.

Din punctul de vedere al tipului, fişierele pot fi:

• fişiere normale: conţin informaţie utilizator; • directoare: fişiere sistem destinate gestionării structurii sistemului de fişiere; • fişiere speciale de tip caracter/bloc: destinate utilizării în conjuncţie cu dispozitivele

periferice; • legături simbolice: furnizează posibilitatea accesării unui acelaşi fişier fizic pe căi

logice multiple.

Fişierele normale sunt la rândul lor de două tipuri: • tipul ASCII: fişierul este format din linii de text terminate cu caracterele de control

return şi/sau line feed; • tipul binar: fişierul este organizat ca o secvenţă de octeţi, dar totuşi sistemul de

operare îi asociază o anumită structură internă ( cum este de exemplu cazul fiţierelor executabile sau al arhivelor ).

VII.2. Operaţii cu fişiere

Deşi alocarea spaţiului pe discul magnetic pentru un fişier se face la nivel de blocuri ( având dimensiune fixă, cuprinsă între 512 octeţi şi 4K octeşi ), de regulă neadiacente, utilizatorul manipulează un fişier ca pe o secvenţă contiguă de octeţi în cadrul căreia se poate poziţiona oriunde şi de unde poate citi sau înscrie numărul dorit de octeţi. Setul de operaţii pentru care sistemul de operare asigură primitive destinate lucrului cu fişiere cuprinde următoarele funcţii de bibliotecă:

• create – crearea unui nou fişier; • open – intenţia unui proces de a accesa date conţinute într-un fişier existent; • delete – ştergerea unui fişier; • read – citirea din fişier a unui număr specificat de octeţi, începând de la poziţia

curentă, în spaţiul de adresare al procesului care a iniţiat operaţia; • write – scrierea într-un fişier a unui număr specificat de octeţi, începând de la poziţia

curentă, cu date conţinute în spaţiul de adresare al procesului care a iniţait operaţia; • append – adăugarea de date la sfârşitul unui fişier existent;

• close – eliberarea structurilor de date sistem, ca urmare a terminării operaţiilor pe care un proces le-a executat asupra unui fişier;

• seek – setează poziţia curentă în fişier; • rename – redenumeşte un fişier existent; • setattribute, getattribute – operaţii de setare, respectiv de citire a atribuitelor asociate

unui fişier.

Accesarea fişierelor urmează secvenţa de operaţii open – read – write – close. Acestor operaţii le corespund funcţii de bibliotecă pe care utilizatorul le poate apela din program. La rândul lor, aceste funcţii iniţiază apeluri sistem. VII.3. Directoare

Directoarele realizează legătura între numele atribuit de utilizator unui fişier şi localizarea fizică pe disc a informaţiei asociate fişierului respectiv, operaţie numită în mod uzual mapare.

Structura unui director poate fi asimilată cu aceaa a unei tabele în care fiecare intrare este asociată unui fişier şi conţine numele fişierului şi adresa unei structuri de date sistem. Acestă structură de date conţine la rândul ei atributele fişierului şi informaţii despre localizarea acestuia pe disc. Principalele atribute ce pot caracteriza un fişier sunt:

• tipul fişierului – normal, director, special sau legătură simbolică; • informaţii suplimentare legate de fişier ( ASCII/binar, tipul dispozitivului periferic

asociat ); • informaţie pentru controlul accesului la fişier ( cine poate accesa fişierul şi ce

operaţii se pot efectua asupra fişierului ); • momentul creării, al ultimului acces şi al ultimei modificări a fişierului; • contor indicând numărul de legături către fişierul respectiv; • dimensiunea fişierului; • identificatorul utilizatorulu care a creat fişierului ( proprietarul fişierului ).

Într-un context mai general, o intrare într-un director poate indica un alt director, ceea ce conduce la o organizare arborescentă a sistemului de fişiere, în care “frunzele” sunt fişierele propriu-zise, iar nodurile intermediare şi nodul rădăcină sunt directoare. În acest caz, identificarea unui anumit fişier se va face enumerând directoarele ce trebuie parcurse de la nodul rădăcină şi până la fişierul respectiv.

Setul de operaţii asigurate de către sistemul de operare pentru lucrul cu directoare cuprinde:

• create – creare director; • open – deschidere director ( de exemplu, în scopul citirii şi afisării intrărilor ); • delete – ştergere director; • close – eliberare structuri de date sistem care au fost alocate unui director ca urmare a

unei operaţii open;

• readdir – returnează următoarea intrare într-un director; conţinutul directoarelor poate fi citit şi prin intermediul operaţiei read ( definită pentru fişiere ), dar aceasta returnează întreaga tabelă asociată directorului respectiv, obligând utilizatorul să cunoască structura acesteia în scopul regăsirii informaţiilor căutate;

• rename – redenumire director; • link – stabilirea unei legături simbolice care are ca efect apariţia numelui unui acelaşi

fişier în mai multe locuri în cadrul sistemului de fişiere; • unlink – ştergerea unei intrări într-un director.

VII.4. Implementarea sistemului de fişiere VII.4.1. Implementarea fişierelor Cea mai simplă modalitate de implementare a fişierelor este aceea de stocare a acestora în blocuri cotigue pe disc. Dezavantajul unei astfel de metode constă în faptul că nu poate modela în mod eficient modificarea dinamică a dimensiunii fişierelor decât cu riscul introducerii unei fragmentări a discului magnetic ( zone nealocate însumând dimensiuni importante, dar imposibil de folosit deoarece nu sunt adiacente ). De aceea, în general, fişierele se memorează sub forma unor blocuri răspândite pe întraga suprafaţă a discului, gestionarea lor constituind una dintre sarcinile sistemului de operare. În UNIX, implementarea fişierelor se bazează pe o structură de date numită i-nod ( index node ) care conţine ( fiecărui fişier îi corespunde un i-nod ):

• atributele fişierului respectiv; • adresele pe disc ale blocurilor care stochează informaţia din fişierul respectiv.

I-nodurile sunt la rândul lor stocate pe disc ca intrări într-o tabelă de i-noduri, într-o zonă dedicată de sistem acestui scop, şi pot fi referite precizând indexul lor în această tabelă.

O altă implementare destul de răspândită este cea de tipul FAT ( File Allocation Table ) care foloseşte un mecanism de alocare cu listă înlănţuită de indecşi ( Figura 24 ).

Figura 24

VII.4.2. Implementarea directoarelor În UNIX, structura unei intrări de director are forma ( Figura 25 ):

Figura 25

În momentul deschiderii unui fişier este necesar ca, pornind de la numele său, sistemul de fişiere să-i poată localiza blocurile de date de pe disc. Sistemul de fişiere caută mai întâi directorul rădăcină al cărui i-nod se află la o adresă predefinită pe disc. Organizarea pe disc a diferitelor componente ale sistemului de fişiere în UNIX este redată în Figura 26:

Figura 26 Blocul de boot conţine proceduri utilizate de sistem la iniţializare. Superblocul conţine informaţii esenţiale legate de sistemul de fişiere ( numărul de i-noduri, numărul de blocuri, o listă a blocurilor libere de pe disc ). Lista de i-noduri conţine toate i-nodurile definite în sistem. Primul i-nod din listă este destinat gestiunii blocurilor defecte, în timp ce al doilea este i-nodul asociat directorului rădăcină. Urmează zona alocată blocurilor de date care conţin atât date utilizator, cât şi date utilizte de sistemul de fişiere. În sistemele care utilizează mecanisme de implementare de tip FAT, structura unei intrări de director are forma din Figura 27:

Figura 27

Principalul dezavantaj al acestei metode este absenţa mecanismului de creare a legăturilor la fişiere. Pentru realizarea unor legături ar fi necesar ca o aceeaşi intrare să figureze în două sau mai multe directoare, având drept consecinţă duplicarea unor date legate de poziţionarea pe disc, de timpul şi dimensiunea fişierului respectiv ( ceea ce poate conduce la inconsistenţe ).

VII.5. Acces concurent la nivel de proces Fiecare proces în UNIX are asociat o tabelă de descriptori ( descriptor table ). De fiecare dată când un proces deschide un fişier, apelul sistem open îi va returna un descriptor de fişier pe care procesul îl va memora în tabela de descriptori şi pe care îl va folosi la toate referirile ulterioare pe care le va face la fişierul respectiv, până când acesta va fi închis. Descriptorul de fişier este un întreg care reprezintă un index în tabela fişierelor deschise ( open-file table ), tabelă pe care sistemul de operare o întreţine, şi care memorează informaţii despre toate fişierele deschise în sistem. O intrare în acestă tabelă conţine următoarele informaţii:

• un pointer ( indicator ) în cadrul fişierului care indică locaţia în fişier unde se va face următoarea operaţie citire/scriere;

• un câmp care indică dacă fişierul a fost deschis pentru citire, scriere sau citire/scriere; • un contor pentru numărul de descriptori care adresează intrarea respectivă.

O altă structură de date utilizată de sistem este tabela rezidentă de i-noduri ( in-

memory i-node table ) în care se păstrează atât informaţiile conţinute în cadrul i-nodului, cât şi date strict necesare pentru controlul concurenţei accesului, cum ar fi:

• un câmp de blocare ( lock ) ce asigură accesul exclusiv la i-nod ( la un moment dat se permite unui singur proces să modifice conţinutul i-nodului );

• un contor al numărului de intrări în tabela fişierelor deschise care adresează i-nodul respectiv;

• numărul i-nodului la care se referă ( din tabela de i-noduri de pe disc ); • numărul dispozitivului de I/O căruia îi este asociat fişierul; • pointeri către alte i-noduri din tabela rezidentă care implementează tabele de

dispersie ( hash table ) utilizate de sistem pentru a micşora timpul de căutare în tabela rezidentă; tabelele de dispersie sunt utilizate atât în conjuncţie cu i-nodurile libere, cât şi cu cele active.

În cazul în care mai multe procese folosesc în mod concurent un acelaşi fişier apare

necesitatea implementării unor mecanisme suplimentare bazate pe secţiuni critice ( secţiunea critică este un segment de cod al unui proces în care se citesc variabile comune, se reactualizează tabele, se scriu fişiere etc.; mai mult, fiecare proces trebuie să ceară permisiunea de a intra în propria secţiune critică şi să anunţe celelalte procese atunci când părăseşte această secţiune ) sau/şi semafoare ( semaforul este o variabilă de tip întreg care, în afară de iniţializare, poate fi accesată numai prin intermediul a două operaţii standard de tip atomic, şi anume wait ( aşteaptă ) şi signal ( semnalizează ); semafoarele se utilizează în rezolvarea unor probleme de sincronizare ) care să gestioneze accesul la date, în scopul păstrării consistenţei acestora. Astfel de mecanisme asigură accesul exclusiv la fişier al procesului care realizează în mod curent o anumită operaţie, blocând fişierul pentru toate celelalte procese. Blocarea se face la nivel de componentă a fişierului ( înregistrare ), cu respectarea unor condiţii mai restrictive pentru operaţia de scrire.

Sistemele care se conformează standardului POSIX definesc un mecanism eficient şi

flexibil ce asigură blocarea unor zone în cadrul unui fişier, definite cu ajutorul a doi parametri: deplasament faţă de începutul fişierului şi dimensiune. Mecanismul foloseşte zăvoare comune ( shared locks ) şi zăvoare exclusive ( exclusive locks ). Zăvoarele comune se pot asocia unor zone, chiar dacă părţi ale acestei zone sunt deja blocate prin intermediul altor zăvoare comune. Zonele blocate cu zăvoare comune se pot suprapune, spre deosebire de zăvoarele exclusive care se pot asocia numai unor zone libere. Primitivele utilizate de mecanismul de “zăvorâre/blocare” pot fi primitive cu blocare ( un proces care încearcă punerea unui zăvor exclusiv pe ozonă care nu este liberă este blocat pînă în momentul în care zone se eliberează ) sau fără blocare ( returnează imediat cu un cod ce indică succesul sau insuccesul operaţiei, în caz de insucces procesul apelant putând face o nouă tentativă la un moment ulterior ). VII.6. Protecţia fişierelor Într-un sistem multi-utilzator este imortant ca fiecare utilizator să poată defini drepturile de acces asupra propriilor fişiere, precizând cine le poate accesa şi ce operaţii poate efectua asupta lor. Una dintre metodele folosite în acest scop este implementată în sistemele UNIX şi constă în asocierea cu fiecare fişier sau director a unui grup de 9 biţi ( cunoscuţi sub numele de biţii rwx ), care indică permisiunea de citire, scriere sau execuţie pentru proprietarul fişierului, pentru grupul de utilizatori din care face parte proprietarul şi pentru ceilalţi utilizatori din sistem ( Figura 28 ).

Figura 28 Grupul de 9 biţi ( rwx rwx rwx ) este conţinut în unul dintre atributele care se regăsesc în i-nodul asociat, atribut reprezentat printr-o variabilă întreagă ce codifică “modul” de acces asociat fişierului sau directorului respectiv. În cazul directoarelor, drepturile de acces au o semnificaţie uşor diferită: permisiunea de citire indică dreptul de a crea un fişier nou sau modifică numele sau atributele unui fişier deja existent în cadrul directorului respectiv, iar permisiunea de execuţie permite căutarea în cadrul directorului

respectiv. O altă metodă de protecţie a fişierelor ( utilizată de sistemele Windows ) asociază fiecărui fişier o listă de control al accesului ( access control list – ACL ) care conţine mai multe intrări de control al accesului ( access control entries – ACE ). Fiecare ACE specifică drepturile de acces pentru un utilizator sau un grup de utilizatori, conţinând un identificator al utilizatorului sau grupului de utilizatori la care se referă, o descriere a drepturilor pe care le conferă asupra fişierului şi alte opţiuni, cum ar fi cea legată de posibilitatea ca un fişier creat în cadrul unui director să moştenească drepturile de acces ale acestuia. În momentul în care un utilizator încearcă să acceseze fişierul, se verifică automat în cadrul listei de control asociate fişierului ( ACL ) dacă este vorba de un acces corect sau nepermis. VII.7. Performanţele sistemelor de fişiere Deoarece operaţii de genul căutarea unui fişier necesită accesuri multiple la disc, îmbunătăţirea timpilor de acces se realizează prin păstrarea în memoria principală a informaţiilor cel mai des utilizate, minimizând pe cât posibil numărul de accesuri la disc. Această funcţie poate fi implementată sub forma unui mecanism de tipul cache care constă în alocarea şi gestionarea de către sistem a unei zone în memoria principală unde vor fi stocate atât structurile de date utilizate pentru administrarea sistemului de fişiere ( i-noduri, blocuri ce conţin directoare ) cât şi blocurile ce conţin informaţie utilizator ( care sunt cel mai frecvent accesate ). Astfel, operaţiile efectuate asupra datelor din zona cache se realizează în conjuncţie cu cópiile din memoria principală ale datelor originale ( care au fost preluate de pe disc ). Utilizarea mecanismului descris anterior asigură performanţe în domeniul timp, dar, pentru a nu crea probleme legate de consistenţa informaţiilor ( modificările făcute asupra datelor din memoria principală nu se reflectă în mod implicit şi asupra datelor de pe disc ), este necesar să se folosească una dintre următoarele politici de actualizare a informaţiilor de pe disc:

• politica write-through – constă în actualizarea informaţiilor pe disc după fiecare modificare a cópiei lor din memoria principală; această politică se aplică de obicei datelor cu importanţă foarte mare pentru sistem, a căror pierdere ar lăsa sistemul într-o stare inconsistentă;

• politica lazy writing – reduce accesul la disc prin întârzierea operaţiilor de actualizare uneori chiar până în momentul în care informaţia modificată trebuie evacuată din zona de cache ca urmare a umplerii acestei zone; în comparaţie cu politica write-through, această politică asigură performanţe superioare în domeniul timp, dar implică riscuri mărite în privinţa consistenţei informaţiei.

O primă componentă a mecanismului de cache-ing o constituie lista rezidentă de i-

noduri care conţine integral informaţiile stocate în cadrul i-nodurilor din tabela de i-noduri. În UNIX funcţionează un mecanism de block-buffering care constă în alocarea de

către sistem în memoria principală a unei zone ce conţine buffere ( buffer pool ) utilizabile pentru implementarea unui mecanism de cache-ing în conjuncţie cu dispozitivele periferice structurate bloc. Aceste buffere sunt organizate în structuri de date ( de exemplu, tabele de

dispersie ) menite să mărească performanţele operaţiilor de regăsire a cópiei unui anume bloc de pe disc sau a unui buffer liber.

Un alt mecanism ce poate asigura reducerea timpului de acces la informaţiile păstrate pe discul magnetic este acela de mapare în memorie a unui fişier, operaţie care asociază fişierului vizat un segment din spaţiul virtual de adresare al procesului care a iniţiat operaţia. Citirile/scrierile din/în fişier vor fi transpuse în citiri/scrieri din/în segmentul corespunzător, iat în final fişierul poate fi de-mapat din memorie.

Deşi pare o soluţie convenabilă, maparea fişierelor în memorie creează o serie de probleme:

• dacă în sistem se utilizează paginarea segmentelor, dimensiunea fişierului se va modifica dinamic cu câte o pagină, ceea ce face dificilă precizarea lungimii reale a fişierului;

• deoarece fişierele pot avea dimensiuni oricât de mari ( teoretic, chiar mai mari decât întregul spaţiu virtual de adresare ) se impune a fi prevăzută posibilitatea mapării în memorie a unor regiuni aparţinând fişierului şi nu a fişierului în întregime;

• dacă un proces mapează în memorie un fişier accesat în mod concurent de către un al doilea proces, modificările realizate de primul proces afectează un segment din propriul spaţiu de adresare, fiind invizibile celui de-al doilea proces.

VIII. Sistemul de intrare/ieşire ( I/O ) Una dintre cele mai importante funcţii ale sistemului de operare este gestionarea dispozitivelor periferice ale sistemului de calcul, funcţie care presupune pe de o parte generarea de comenzi către dispozitive, tratarea întreruperilor şi a posibilelor erori, iar pe de altă parte furnizarea unei interfeţe utilizator cât mai uşor de folosit şi cu un grad cât mai ridicat de standardizare. Componenta sistemului de operare dedicată acestei funcţii este sistemul de intrare/ieşire. Obiectivele urmărite în proiectarea unui sistem I/O sunt:

• independenţa faţă de codul de caractere – sistemul I/O trebuie să fie capabil să recunoască diversele coduri de caractere utilizate de dispozitivele periferice şi să prezinte utilizatorului datele într-un format standard;

• independenţa faţă de dispozitivele periferice – presupune posibilitatea scrierii programelor într-o manieră standard care să nu necesite modificări la nivelul codului atunci când tipul dispozitivului periferic utilizat este altul decât cel prevăzut iniţial. Acest obiectiv se transpune în necesitatea furnizării unor operaţii a căror sintaxă şi semantică să fie cât mai asemănătoare pentru o clasă cât mai largă de dipozitive periferice. Mai mult, se vizează şi denumirea uniformă a dispozitivelor periferice ( de obicei, fiecărui dispozitiv periferic îi este asociat un fişier, dispozitivele fiind denumite prin intermediul numelui fişierului asociat );

• eficienţa operaţiilor – există situaţii în care dispozitivele periferice introduc întârzieri de acces datorate pe de o parte diferenţei mari dintre viteza de calcul a unităţii centrale şi viteza de transfer a datelor şi, pe de altă parte, diferenţei mari dintre viteza de transfer a datelor şi viteza ansamblurilor mecanice mobile ce intră în componenţa

multora dintre dispozitivele periferice. Aceste încetiniri ce pot să apară în fluxul execuţiei impun utilizarea unor mecanisme care să conducă la asigurarea creşterii eficienţei: spooling, DMA etc.

VIII.1. Structura sistemului I/O VIII.1.1. Structura hardware Dispozitivele I/O Dispozitivele periferice pot fi clasificate în două categorii: dispozitive bloc şi dispozitive caracter. Dispozitivele bloc ( discul magnetic ) stochează informaţia sub forma unor blocuri de dimensiune fixă, fiecare dintre acestea având asociată o adresă cu ajutorul căreia poate fi accesat individual. Dispozitivele caracter lucrează cu şiruri de caractere cărora nu le conferă o structurare pe blocuri. Acestea pot fi adresate individual şi deci nu pot constitui obiectul unor opearţii de căutare. Din această categorie fac parte imprimantele, adaptoarele de reţea, mouse-ul, terminalele etc. La graniţa dintre cele două categorii menţionate se găsesc dispozitive ca unităţile de bandă magnetică în cazul cărora nu se poate implementa în mod eficient accesul aleatoriu, deşi pot fi structurate bloc şi pot furniza operaţii de căutare. Controllere Dispozitivele periferice sunt în general formate dintr-o componentă mecanică şi o componentă electronică. Componenta electronică este denumită controller, în timp ce componenta mecanică este dispozitivul propriu-zis. În cazul unei operaţii de citire de pe un disc magnetic, controller-ul este cel care poziţionează capetele de citire/scriere şi citeşte de pe suportul magnetic un şir de biţi care cuprinde:

• un antet care conţine informaţii înscrise la momentul formatării discului magnetic, cum ar fi numărul cilindrului, al sectorului, dimensiunea unui sector etc.;

• biţii de informaţie stocaţi în sectorul respectiv; • un cod de corecţie a erorilor.

Controller-ele asamblează bit cu bit un bloc de date, căruia îi calculează suma de control ce trebuie să coincidă cu codul citit de pe disc. Abia după aceea blocul de date respectiv poate fi transferat în memoria principală.

Comunicaţia dintre controller şi unitatea centrală se realizează prin intermediul unui număr de regiştri care de cele mai multe ori fac parte din spaţiul de adrese de memorie ( sunt mapaţi în memorie – memory mapped I/O ). Regiştri mapaţi în memorie se adresează la fel ca orice altă locaţie de memorie, singura diferenţă fiind legată de timpul de acces care este mai redus. Aceşti regiştri sunt utilizaţi de sistemul de operare pentru a înscrie parametri şi comenzi şi pentru a citi starea dispozitivului respectiv şi codurile de eroare. O comandă odată acceptată de către controller, sistemul de operare lasă dispozitivul să o execute în timp

ce el palnifică alte sarcini. În moemtul terminării operaţiei controller-ul generează o întrerupere care permite sistemului de operare să preia controlul şi să analizeze rezultatul. Acces direct la memorie ( Direct Memory Access – DMA ) Mecanismul DMA presupune ca operaţia de copiere în memorie ( în cadrul procesului de comunicare/transfer realizat cu un dispozitiv periferic ) să fie efectuată de către controller şi nu de către unitatea centrală, ceea ce conduce la o mai eficientă utilizare a acesteia din urmă. Utilizarea acestui mecanism este justificată de necesitatea transferării unui volum mare de date. Astfel, după ce conţinutul blocului este stocat în buffer-ul său intern şi verificat, controller-ul aşteaptă eliberarea magistralei sistemului şi transferă întregul bloc în memorie. Abia după efectuarea transferului, controller-ul semnalează terminarea operaţiei printr-o întrerupere. Buffer-ul intern al controller-ului acţionează în sensul preluării vitezei relative între operaţia de citire a cuvintelor de pe disc ( se consideră exemplul unei operaţii de citire de pe discul magnetic ), pe de o parte, şi operaţia de transfer a acestora în memoria principală, pe de altă parte. Această viteză relativă se datorează în principal faptului că magistrala locală a sistemului, fiind o resursă comună pe care se desfăşoară toate operaţiile de transfer de date din cadrul sistemului, nu este de aşteptat să fie liberă de fiecare dată când un controller intenţionează să efectueze un transfer. În cazul utilizării DMA trebuie furnizaţi controller-ului doi parametri suplimentari: adresa fizică a zonei de memorie în care trebuie copiate datele şi numărul de octeţi care se copiază. VIII.1.2. Structura software

Software-ul destinat gestiunii dispozitivelor periferice este structurat pe patru niveluri:

• rutinele de tratare a întreruperilor; • driver-ele asociate dispozitivelor periferice; • programe sistem independente de dispozitive; • primitive de nivel utilizator.

Rutine de tratare a întreruperilor În scopul utilizării eficiente a unităţii centrale în sistemele care lucrează în regim multitasking, un proces care iniţiază o operaţie de I/O va fi blocat, urmând să fie trecut în starea ready de îndată ce operaţia va fi încheiată. Rolul rutinelor de tratare a întreruperilor este de a identifica sursa întreruperii ( adică dispozitivul care a generat-o ), de a reiniţializa linia de întrerupere respectivă, de a memora starea dispozitivului şi de a „trezi” procesul care a iniţiat operaţia de I/O.

Drivere Un driver acceptă cereri de la nivelul software superior şi le transpune în comenzi pe care le transmite controller-ului înscriind valori corespunzătoare în regiştrii acestuia din urmă. Driver-ele înglobează în totalitate acea parte a codului care este dependentă de dispozitivele periferice asociate, fiind totuşi, în general, capabile să gestioneze mai multe tipuri de dispozitive periferice înrudite. Programe sistem independente de dispozitive

Sarcinile ce revin acestui nivel software sunt: • asigurarea unei interfaţări uniforme a tuturor driver-elor; • realizarea corespondenţei dintre numele simbolice ale dispozitivelor ( numele

fişierelor asociate ) şi driver-ele corespunzătoare; • utilizarea unor buffere sistem. În cazul dispozitivelor bloc această necesitate este

dictată de faptul că datele cunt citite/scrise în forma unor blocuri de dimensiune fixă, în condiţiile în care utilizatorul e liber să manipuleze date de orice dimensiune. În situaţia dispozitivelor caracter, necesitatea provine din faptul că achiziţionarea datelor de intrare/producerea datelor de ieşire pot avea uneori viteze mai mari decât procesarea datelor de intrare/listarea ( afişarea ) datelor de ieşire. Astfel, se impune utilizarea unor buffere care să preia aceste viteze relative;

• raportarea erorilor care pot apărea în conjuncţie cu operaţiile de I/O. Aceste erori sunt în general dependente de dispozitivele periferice şi în consecinţă sunt manipulate de drivere-ele asociate dispozitivelor. În acest context, sarcina acestui nivel este aceea de raportare a erorilor, în cazul în care acestea nu au putut fi remediate.

Primitive de nivel utilizator Deşi cea mai mare parte a sistemului I/O este înglobat în sistemul de operare, există şi o paret a acestuia formată din biblioteci ce includ proceduri prin intermediul cărora programele utilizator pot iniţia operaţii în conjuncţie cu dispozitivele periferice. Aceste proceduri au rolul de a transfera parametrii lor apelurilor de sistem pe care la iniţiază, iar uneori oferă în plus posibilitatea formatării datelor de intrare/ieşire. Un aspect important este legat de faptul că aceste primitive pot lucra în mod sincron sau asincron. O primitivă sinvronă returnează parametrii numai după ce operaţia de I/O a fost efectiv realizată, ceea ce o recomandă pentru a fi utilizată în cazul operaţilor cu durată redusă sau care poate fi estimată. O primitivă asincronă are doar rolul de iniţiere a operaţiei, ea returnând imediat cu un cod de eroare în cazul în care operaţia nu poate fi efectuată sau zero dacă operaţia poate fi realizată. În consecinţă, procesul îşi poate continua execuţia în paralel cu efectuarea operaţiei, putând eventual testa periodic starea de evoluţie a acesteia. Momentul în care operaţia se încheie este marcat printr-o notificare ( o procedură definită de utilizator şi

asociată acestui eveniment ) pe care sistemul de operare o lansează automat. O problemă esenţială legată de acest tip de primitive este dată de disponibilitatea buffer-ului ce defineşte zona de memorie în care se află datele ce urmează a fi transferate: procesul iniţiator trebuie să evite citirea/scrierea conţinutului acestei zone atâta timp cât operaţia nu afost încă terminată. Această sarcină revine în general programatorului. Primitivele asincrone sunt în general utilizate în cazul operaţiilor având o durată mare sau greu de estimat. BIBLIOGRAFIE

1. Ionescu, T., Saru, D., Floroiu, J. – SISTEME DE OPERARE. Pricnipii şi funcţionare, Editura Tehnică, Bucureşti, 1997

2. Stallings, W. – Operating Systems: Internals and Design Principles ( 5th Edition ), Prentice Hall, 2004

3. Silberschatz, A., Gagne, G., Galvin, P. B. – Operating System Concepts ( 6 Edition ), Willey, 2002