Sisteme de operare

1.INTRODUCERE

Informatica este o tiin recent i nu a avut nc timp s se structureze pe capitole strict delimitate i bine definite. Dezvoltarea exploziv din ultimele dou decenii a fcut ca ordonarea materialului s urmreasc cu greu abundena de noi informaii att n domeniul tehnicii de calcul ct i n privina numeroaselor probleme n rezolvarea crora aceasta poate fi utilizat.

Nu exist o teorie unic a informaticii ci multe teorii care se suprapun parial: arhitectura ordinatoarelor i evaluarea performanelor lor, conceperea i verificarea circuitelor, algoritmic i analiza algoritmilor, concepia i semantica limbajelor de programare, structuri i baze de date, principiile sistemelor de operare, limbaje formale i compilare, calcul formal, coduri i criptografie, demonstraie automatic, verificarea i validarea programelor, timp real i logici temporale, tratarea imaginilor, sinteza imaginilor, robotica etc. Fiecare dintre aceste domenii are problemele sale deschise, unele celebre, de exemplu gsirea unei semantici pentru limbajele de programare obiectual.

Pe plan didactic, ns, s-au conturat anumite discipline care s asigure studenilor posibilitatea de a accede la problematica vast a informaticii. Printre altele se studiaz i SISTEMELE DE OPERARE care intervin ntr-un sistem de calcul.

3

compilator asamblor editor texte sistem de baze de date Programe sistem de aplicaie

Sistem de operare

Hardware calculator

Sorin Adrian Ciureanu

1.1 SISTEME DE OPERARE. DEFINIIE

Un sistem de operare (SO) este un set de programe care are dou roluri primordiale:

-asigur o interfa ntre utilizator i sistemul de calcul, extinznd dar i simplificnd setul de operaii disponibile;

-asigur gestionarea resurselor fizice (procesor, memorie intern, echipamente periferice) i logice (procese, fiiere, proceduri, semafoare), implementnd algoritmi destinai s optimizeze performanele.

De exemplu, cele dou componente ale definiiei pot fi: publicitatea (interfaa) i valoarea produsului (gestionarea resurselor). Exemple de SO sunt sistemele MS-DOS, WINDOWS i UNIX.

1.2. LOCUL SISTEMULUI DE OPERARE NTR-UN SISTEM DE CALCUL

Componentele unui sistem de calcul sunt:

1.-Hardware - care furnizeaz resursele de baz (UC, memorie, dispozitive I/O).

2.-Sistem de operare - care controleaz i coordoneaz utilizarea hardware-ului pentru diferite programe de aplicaii i diferii utilizatori.

3.-Programe de aplicaie - care definesc cile prin care resursele sistemului sunt utilizate pentru a rezolva problemele de calcul ale utilizatorilor (compilare, sisteme de baze de date, jocuri video, programe business etc.).

4.-Utilizatori care pot fi persoane, maini, alte calculatoare etc.

4

compilator asamblor editor texte sistem de baze de date Programe sistem de aplicaie

Sistem de operare

Hardware calculator

Sisteme de operare

Fig.1.1. Schema componentelor unui sistem de calcul.

Acum zece ani, un sistem de operare era doar o pies de baz a softului care rula pe o main i permitea manipularea fiierelor, conversa cu orice periferic i lansa programe. Acum sistemele de operare au devenit mai complexe, funcionnd ca intermediari ntre utilizator i hardware, realiznd executarea programelor utilizator cu mai mare uurin i utiliznd eficient hardware-l calculatorului.

n concepia lui A. Tanenbaum, un calculator este organizat pe mai multe niveluri. Trecerea de pe un nivel pe altul se poate face prin interpretare sau prin traducere.

Dac avem dou limbaje de programare Li i Li+1 , se poate trece din Li+1 n Li prin interpretare sau prin traducere.

Interpretare. Programul scris n Li+1 este executat pas cu pas, n sensul c instruciunile din Li+1 se execut pe rnd, fiecare instruciune din Li+1 fiind o dat de intrare pentru Li . Instruciunea din Li+1 are o secven echivalent de instruciuni care se execut n Li . Nu se genereaz un nou program n Li .

Traducere. ntreg programul din Li+1 se nlocuiete cu un nou program n Li , generat prin nlocuirea fiecrei instruciuni din Li+1 cu o secven echivalent n Li .

5

Utilizator 1 Utilizator 2 Utilizator 3 Utilizator n

compilator asamblor editor texte sistem de baze de date Programe sistem de aplicaie

Sistem de operare

Hardware calculator

Sorin Adrian CiureanuConsidernd un sistem de calcul cu 6 niveluri, SO se

plaseaz ca n urmtoarea schem:

Nivel 5 NIVELUL LIMBAJULUI ORIENTAT PE PROBLEM Traducere (compilator)

Nivel 4 NIVELUL LIMBAJULUI DE ASAMBLARE Traducere(asamblor)

Nivel 3 NIVELUL SISTEMULUI DE OPERARE Interpretare parial

Nivel 2 NIVELUL ARHITECTURII SETULUI DE INSTRUCIUNI (ISA)

Interpretare(microprogram) sau executare directNivel 1 NIVELUL MICROARHITECTURII

HardNivel 0 NIVELUL LOGIC DIGITAL

Dup Tanenbaum, calculatorul este foarte flexibil iar hardul i softul sunt echivalente sau, aa cum spunea Lenz, hardul este soft pietrificat. n schema de mai sus, numai nivelul 0 (nivelul circuitelor) este hard pur. Celelalte niveluri pot fi implementate hard sau soft n funcie de optimul planificat.

Observm c, n schem, SO este pe nivelul 3. SO conine toate instruciunile ISA (Instructions Set Architecture),de pe nivelul 2, plus apelurile sistem (system calls). Un apel sistem invoc un serviciu predefinit al SO, de fapt una din instruciunile acestuia. Noile faciliti (apelurile sistem) adugate pe nivelul 3 sunt realizate de un interpretor care le execut pe nivelul 2 i care, din motive istorice, se numete SO. Instruciunile de pe nivelul 3 care sunt identice cu cele de pe nivelul 2 sunt executate direct de microprogram. Spunem c nivelul 3 este un nivel hibrid deoarece unele instruciuni de pe nivelul 3 sunt interpretate de SO (apelurile sistem) iar altele sunt interpretate direct de microprogram.

6

Sisteme de operare

1.3. SARCINILE SISTEMULUI DE OPERARE

Pornind de la definiia unui SO, se pot identifica responsabilitile sale, prezentate n continuare.

1.3.1. Asigurarea interfeei cu utilizatorul

Trebuie precizat c interfaa SO utilizator este constituit din orice instrument care permite comunicarea ntre un SO i un operator (utilizator), indiferent dac este hard sau soft. n cvasitotalitate, interfeele n SO sunt soft i pot lua urmtoarele forme.

1.3.1.1. Monitoare

Unele calculatoare conin, stocat ntr-o memorie ROM intern, un program numit monitor care se lanseaz automat la pornirea calculatorului i i permite operatorului s efectueze operaii simple asupra sistemului de calcul, cum ar fi: inspectarea i modificarea registrelor procesorului, vizualizarea coninutului memoriei etc. De obicei, monitorul este un complementar al SO, n sensul c pornete cnd nu a putut fi ncrcat SO. Este specific sistemelor de calcul mai vechi, actualmente existnd puine sisteme de calcul care nglobeaz un monitor.

1.3.1.2. Interfee n linie de comand (interfee text)

Interfeele n linie de comand sunt reprezentate, n general, de un program numit interpretor de comenzi, care afieaz pe ecran un prompter, primete comanda introdus de operator i o execut. Comenzile se scriu folosind tastatura i pot fi nsoite de parametri. Aproape toate sistemele de operare

7

Sorin Adrian Ciureanuinclud o interfa n linie de comand, unele foarte bine puse la punct (UNIX) iar altele destul de primitive (MSDOS, WINDOWS).

1.3.1.3 Interfee grafice

Interfeele grafice sunt cele mai populare. Se prezint sub forma unui set de obiecte grafice (de regul suprafee rectangulare) prin intermediul crora operatorul poate comunica cu SO, lansnd operaii, setnd diferite opiuni contextuale etc.

Vom prezenta, comparativ, caracteristicile celor dou tipuri de interfee cu calculatorul.

Interfa n linie de comand.Avantaje:

-Permite scrierea clar i explicit a comenzilor, cu toi parametrii bine definii.-Ofer flexibilitate n utilizare.-Comunicarea cu SO se face mai rapid i eficient.

Dezavantaje:-Operatorul trebuie s cunoasc bine comenzile i efectele lor.-Este mai greu de utilizat de ctre neprofesioniti.Interfa graficAvantaje:-Este intuitiv i uor de folosit.-Poate fi utilizat de neprofesioniti.-Creeaz un mediu de lucru ordonat.-Permite crearea i utilizarea unor aplicaii complexe, precum i integrarea acestora n medii de lucru unitare.Dezavantaje:-Anumite operaii legate, de exemplu, de configuraia sistemului pot s nu fie accesibile din menuurile i ferestrele interfeei.-Interfaa ascunde anumite detalii legate de preluarea

8

Sisteme de operarei execuia comenzilor.-Folosete mai multe resurse i este mai puin flexibil.

In general, exist dou componente principale: -comenzi, care sunt introduse de utilizator i prelucrate de

interpretorul de comenzi nainte de a ajunge la SO; -apeluri sistem, care sunt folosite direct de ctre

programatorii de sistem i indirect de ctre programatorii de aplicaii, apar n programe i se declaneaz n timpul execuiei acestor programe, fiind asemntoare cu procedurile.

Apelurile sistem definesc propriu zis arhitectura unui SO, adic aparena sa ctre exterior, aspectul funcional al sistemului. Se poate considera c ele ndeplinesc acelai rol pentru SO ca i lista de instruciuni pentru procesor.

Un aspect care devine tot mai important este acela al standardizrii interfeelor unui SO. Asigurarea unei interfee uniforme ( att la nivel de comenzi ct i la apeluri sistem) ar permite portabilitatea aplicaiilor, adic posibilitatea de a trece un program de aplicaii de sub un SO sub altul, fr modificri.

1.3.2. Gestiunea proceselor i a procesoarelor

Un program n execuie sub controlul unui SO este un proces. Pentru a-i ndeplini sarcinile, procesele au nevoie de resurse, cum ar fi: timpul de lucru al UC (unitatea central), memorii, fiiere, dispozitive I/O. Apare evident necesitatea ca resursele s fie utilizate n comun. O serie de mecanisme speciale au fost introduse n SO pentru a servi la gestionarea proceselor la diferite niveluri de detaliu. In practic exist o legtur strns i cu nivelul de ntrerupere al calculatorului. Gestiunea procesorului este privit ca o parte component a gestionrii proceselor.

1.3.3. Gestionarea memoriei

9

Sorin Adrian CiureanuAcest modul controleaz, n primul rnd, utilizarea

memoriei interne. ntotdeauna o poriune a acestei memorii este necesar pentru nsui SO, iar restul este necesar pentru programele utilizator. Frecvent, mai multe programe utilizator se afl simultan n memorie, ceea ce presupune rezolvarea unor probleme de protecie a lor, de cooperare intre aceste programe sau ntre programe i SO, precum i a unor probleme de mprire a memoriei disponibile ntre programele solicitante.

Memoria extern este implicat n activitatea modulului de gestionare a memoriei. Mecanismele swapping i de memorie virtual folosesc memorie extern pentru a extinde capacitatea memoriei interne.

1.3.4. Gestionarea perifericelor

Modul de gestionare a perifericelor cuprinde toate aspectele operaiilor de introducere i extragere a informaiei: pregtirea operaiei, lansarea cererilor de transfer de informaie, controlul transferului propriu zis, tratarea erorilor.

La majoritatea echipamentelor periferice actuale transferurile de intrare/ieire (I/O=input/output) se desfoar indiferent de procesor, rolul SO fiind acela de a asigura aceste transferuri cu ajutorul sistemului de ntreruperi.

1.3.5. Gestionarea fiierelor

Fiierul este entitatea de baz a unui SO, cea care pstreaz informaia. Toate operaiile legate de fiiere (creare, tergere, atribute, copiere, colecie de fiiere, securitatea informaiei) sunt coordonate de SO cruia i revine un rol important n acest caz.

1.3.6. Tratarea erorilor

10

Sisteme de operareSO este acela care trateaz erorile aprute att la nivel hard

ct i la nivel soft. Tratarea unei erori nseamn mai nti detectarea ei, apoi modul de revenire din eroare pentru continuarea lucrului, mod care depinde de cauza erorii i de complexitatea SO. Unele erori sunt transparente utilizatorului, altele trebuiesc neaprat semnalate. De asemenea unele erori sunt fatale i duc la oprirea SO. Mecanismul principal de tratare a erorilor este ca SO s repete de un numr definit de ori operaia euat pn la desfurarea ei cu succes sau pn la apariia erorii fatale. La ora actual SO moderne acord un rol foarte important conceptului de siguran n funcionare i de protecie a informaiei.

1.4. CARACTERISICILE SISTEMELOR DE OPERARE

Formulm n continuare cele mai importante caracteristici ale sistemelor de operare.

1.4.1. Modul de introducere a programelor n sistem

Din acest punct de vedere sistemele de operare pot fi:-SO seriale, n care se accept introducerea lucrrilor de la

un singur dispozitiv de intrare;-SO paralele, n care introducerea lucrrilor se face de la

mai multe dispozitive de intrare;-SO cu introducerea lucrrilor la distan.De exemplu, sistemele UNIX i WINDOWS sunt paralele

i cu introducere la distan, pe cnd sistemul MS-DOS este serial.

1.4.2. Modul de planificare a lucrrilor pentru execuie

11

Sorin Adrian Ciureanu

Exist:-SO orientate pe lucrri, care admit ca unitate de

planificare lucrarea, alctuit din unul sau mai multe programe succesive ale aceluiai utilizator;

-SO orientate pe proces, care admit ca unitate de planificare procesul.

SO moderne sunt orientate pe proces.

1.4.3. Numrul de programe prezente simultan n memorie

Sistemele pot fi:-SO cu monoprogramare (cu un singur program n

memoria principal);-SO cu multiprogramare (cu mai multe programe

existente, la un moment dat, n memoria principal).De exemplu, sistemele UNIX i WINDOWS sunt cu

multiprogramare. Sistemul MS-DOS este ceva ntre monoprogramare i multiprogramare.

1.4.4. Gradul de comunicare a proceselor n multiprogramare

Sistemele de operare cu multiprogramare pot fi:-SO monotasking, n care programele existente n memorie

nu au un obiectiv comun, nu comunic i nu-i pot sincroniza activitile;

SO multitasking, n care programele existente n memorie au un obiectiv comun i i sincronizeaz activitile.

UNIX i WINDOWS sunt multitasking. MS-DOS este un hibrid; prin operaiile de redirectare i indirectare MS-DOS nu este monotasking pur (redirectare - sort

Sisteme de operare

1.4.5. Numrul de utilizatori simultani ai SO

-SO monouser ( cu un singur utilizator) ;-SO multiuser (cu mai muli utilizatori).

UNIX i WINDOWS sunt multiuser, MS-DOS este monouser.

1.4.6. Modul de utilizare a resurselor

Dup modul se utilizare a resurselor, sistemele de operare pot fi :

-SO cu resurse alocate (resursele alocate proceselor sunt alocate acestora pe toat desfurarea execuiei) ;

-SO n timp real (permit controlul executrii proceselor n interiorul unui interval de timp specificat);

-SO cu resurse partajate (resursele necesare proceselor sunt afectate acestora periodic, pe durata unor cuante de timp).

Dac resursa partajat este timpul unitii centrale, SO devine partajat.

SO n timp real sunt utilizate pentru conducerea direct, interactiv, a unui proces tehnologic sau a altei aplicaii. Procesul va transmite ctre SO n timp real parametrii procesului iar SO va transmite ctre proces deciziile luate. Informaiile despre proces sunt luate n considerare n momentul comunicrii lor iar rspunsul sistemului trebuie s fie extrem de rapid, deci timpii de execuie a programelor trebuie s fie mici.

Accesul la resursele sistemului poate fi :-direct (caz particular SO n timp real, cnd se cere o

valoare partajabil maxim a timpului de rspuns) ;-multiplu (acces la resursele sistemului pentru un mare

numr de utilizatori) ;-time sharing (alocarea timpului se face pe o cuant de

timp) ;

13

Sorin Adrian Ciureanu-la distan (prelucrarea se face asupra unor date

distribuite i dispersate geografic).

1.4.7. SO pentru arhitecturi paralele

SO paralele, folosite n multe procesoareSO distribuite , folosite n multe calculatoare.

1.5. COMPONENTELE SISTEMELOR DE OPERARE

Majoritatea sistemelor de operare, pentru a rspunde rolului de interfa cu utilizatorii, sunt organizate pe dou niveluri:

-nivelul fizic, care este mai apropiat de partea hardware a sistemului de calcul, interfernd cu aceasta printr-un sistem de ntreruperi;

-nivelul logic, care este mai apropiat de utilizator, interfernd cu acesta prin intermediul unor comenzi, limbaje de programare, utilitare etc.

Potrivit acestor dou niveluri, sistemele de operare cuprind n principal dou categorii de programe:

-programe de control i comand, cu rolul de coordonare i control al tuturor funciilor sistemelor de operare, cum ar fi procese de intrare ieire, execuia ntreruperilor, comunicaia hardware-utilizator etc.;

-programe de servicii (prelucrri), care sunt executate sub supravegherea programelor de comand i control, fiind utilizate de programator pentru dezvoltarea programelor sale de aplicaie.

In general, putem considera c un SO este format din dou pri: partea de control i partea de serviciu.

1.5.1. Partea de control

14

Sisteme de operare

Partea de control realizeaz interfaa direct cu hardul. Ea conine proceduri pentru:

-gestiunea ntreruperilor;-gestiunea proceselor;-gestiunea memoriei;-gestiunea operaiilor de intrare/ieire;-gestiunea fiierelor;-planificarea lucrrilor i alocarea resurselor.

1.5.2. Partea de serviciu

Partea de serviciu conine instrumente de lucru aflate la dispoziia utilizatorului. Ea exploateaz partea de control, dar transparent pentru utilizator.

Partea de serviciu cuprinde soft aplicativ. Dup destinaia lor, serviciile pot fi de :

-birotic ;-baze de date ;-dezvoltare de aplicaii/programe ;-reele de calculatoare ;-produse soft pentru prelucrarea informaiilor din diverse

domenii.

1.6. STRUCTURA SISTEMELOR DE OPERARE

n sistemele de operare apar, n general, dou aspecte structurale:

-kernel (nucleu);i-user (utilizator).Nucleul (kernel) are urmtoarele principale funcii:-asigurarea unui mecanism pentru crearea i distrugerea

proceselor;

15

Sorin Adrian Ciureanu-realizarea gestionrii proceselor, procesoarelor, memoriei

i perifericelor;-furnizarea unor instrumente pentru mecanismele de

sincronizare a proceselor;-furnizarea unor instrumente de comunicaie care s

permit proceselor s i transmit informaii.Trebuie fcut diferena ntre procesele sistem, care au

privilegii mari, i procesele utilizator, cu un grad de privilegii mult mai mic.

Dup structura lor, sistemele de operare se clasific n :-SO modulare , formate din entiti cu roluri bine definite ;-SO ierarhizate, n care o entitate poate folosi componente

de nivel inferior (de exemplu, partea de serviciu poate folosi partea de control);

-SO portabile, pentru care efortul de a trece SO de pe un calculator pe altul este mic, mai mic dect cel de a-l rescrie .

Sistemele UNIX i WINDOWS sunt portabile. Cele mai vechi, de exemplu RSX, nu erau portabile.

1.7. DEZVOLTAREA ISTORIC A SISTEMELOR DE OPERARE

n dezvoltarea istoric a sistemelor de operare, dup apariia lor, s-au adus multe mbuntiri, att n strategia SO ct i n implementarea SO. (De exemplu; multiprogramare, multitasking, timesharing etc.). Un lucru este acum evident: puternica interdependen hardsoft, adic ntre arhitectura sistemului de calcul i arhitectura SO.

Au existat perioade n care sistemul de calcul avea performane mai sczute iar SO venea s suplineasc aceste neajunsuri (ex. procesoare 8bii, 8080, i sisteme de operare CP/M); n alte perioade situaia este invers, adic un sistem de calcul are performane puternice iar sistemul de operare nu reuete s utilizeze la maxim toate facilitile hard (de exemplu

16

Sisteme de operaresituaia actual, cnd sistemele de operare, att WINDOWS ct i UNIX, nu reuesc s utilizeze n modul cel mau eficient toate facilitile procesoarelor PENTIUM).

Interdependena ntre arhitectura sistemelor de calcul i structura sistemelor de operare const i n faptul c, cel mai adesea, s-a implementat n hard o parte a funciilor SO. Exemple:

a) Actuala component BIOS (Basic I/Osystem) dintr-un PC era o component a sistemului de operare CP/M.

b) Managementul de memorie este actualmente implementat ca modul hard n procesor. Pentru generaiile trecute era o component a sistemului de gestiune a memoriei dintr-un SO.

c) Memoria CACHE, foarte utilizat astzi i implementat exclusiv n memoria intern, n hard discuri etc, era o component a sistemului de operare UNIX n administrarea fiierelor.

n noile sisteme de operare, a aprut o nou noiune, aceea de micronucleu (microkernel). n sistemele clasice cu kernel, acesta era o component rezident permanent n memorie, n sensul c era o parte indivizibil a SO. Ins un astfel de nucleu este foarte mare i greu de controlat. De aceea, constructorii de SO au nlocuit nucleul cu un micronucleu, o component de dimensiuni mai mici, rezident n memorie i indivizibil. n micronucleu au rmas serviciile eseniale, cum ar fi : repornirea unui proces, facilitile de comunicare ntre procese prin mesaje, rudimente de management de memorie, cteva componente de intrare-ieire de nivel foarte jos. Restul serviciilor, inclusiv driverele, au fost mutate n afara micronucleului, n zona de aplicaii utilizator .

SO cu micronucleu funcioneaz pe principiul client/server prin intermediul mesajelor. De exemplu, dac un proces vrea s citeasc un fiier, el va trimite un mesaj cu ajutorul micronucleului ctre o alt aplicaie care ruleaz n spaiul

17

Sorin Adrian Ciureanuutilizator i care acioneaz ca un server de fiiere. Aceast aplicaie va efectua comanda iar rezultatul ei va ajunge napoi la procesul apelant, tot prin intermediul unor mesaje. n acest fel se poate crea o interfa bine definit pentru fiecare serviciu, adic un set de mesaje pe care serverul le nelege. Se pot instala uor noi servicii n sistem, servicii care pot fi pornite fr a fi necesar reformarea nucleului. Se pot crea n mod simplu servicii proprii de ctre utilizatori.

n concluzie, SO cu micronucleu au avantajul unei viteze mai mari, obinute prin eliberarea unei pri de memorie, i dezavantajul unui timp pierdut cu schimbul de mesaje. Se pare, ns, c viteza mare va duce la nlocuirea sistemelor clasice cu sisteme cu micronucleu.

n SO UNIX, un exemplu de micronucleu este ONX al firmei Quantum Software. ONX respect standardele POSIX 1003.1, care se refer la interfaa dintre aplicaiile C i serviciile nucleului, POSIX 1003.2, care se refer la interfaa la nivel de SHELL i POSIX 1003.4, care se refer la SO n timp real.

ONX conine un micronucleu de 8KO n care sunt implementate planificarea i inter-schimbarea proceselor, tratarea ntreruperilor, servicii de reea de nivel sczut. Un sistem minimal ONX adaug la acest micronucleu un controlor de procese care creeaz i controleaz procesele n memorie. Micronucleul conine 14 apeluri sistem.

18

Sisteme de operare

2. PLANIFICAREA PROCESOARELOR (UC)

Multiprogramarea reprezint cel mai important concept folosit n cadrul sistemelor de operare moderne. Existena n memorie a mai multor procese face posibil ca, printr-un mecanism de planificare a unitii centrale (UC), s se mbunteasc eficiena global a sistemului de calcul, realizndu-se o cantitate mai mare de lucru ntr-un timp mai scurt.

Exist procese:-limitate UC, cnd procesul are componente cu timp

majoritar de desfurare n I/O;-limitate I/O, cnd procesul are componente cu timp

majoritar de desfurare n UC.

2.1. SCHEMA GENERAL DE PLANIFICAREA PROCESOARELOR

Procesele stau n memorie grupate ntr-un ir de ateptare n vederea alocrii n UC. Implementarea acestui ir, numit coadde ateptare, se realizeaz de obicei sub forma unei liste nlnuite.

Planificatorul pe termen lung (planificator de joburi) stabilete care sunt procesele ce vor fi ncrcate n memorie. El controleaz gradul de multiprogramare. Frecvena sa este mic.

PLANIFICARE DE PLANIFICARE DISPECER PERSPECTIV IR READY IMEDIAT NCHEIEREA EXECUIEI

19

P1 P

2 P

3.P

n UC

P1 P

2 P

3..P

n

I/O

Sorin Adrian Ciureanu

SIR DE ATEPTARE I/O

Fig. 2.1. Schema general de planificare a proceselor.

Dispecerul realizeaz efectiv transferarea controlului UC asupra procesului selectat de planificatorul UC. Trebuie s fie rapid pentru a putea realiza eficient operaiile necesare: ncrcarea registrelor, comutarea n mod utilizator etc.

Planificatorul pe termen scurt (planificator UC) selecteaz unul din procesele gata de execuie, aflate deja n memoria intern, i l aloc UC. Are o frecven de execuie foarte mare i trebuie proiectat foarte rapid.

2.2. CRITERII DE PERFORMAN APLANIFICRII UC

Cnd se dorete un algoritm de planificare, se pot lua n considerare mai multe criterii :

-gradul de utilizare UC (aproximativ 40% pentru un sistem cu grad de ncrcare redus, 90% pentru un sistem cu grad mare de ncrcare ) ;

-throughput (numrul de procese executate ntr-un interval de timp precizat);

-turnaround time (durata total a execuiei unui proces) reprezint timpul scurs intre momentul introducerii procesului n memorie i momentul ncheierii execuiei sale; se exprim ca suma perioadelor de timp de ateptare pentru a intra n memorie, de ateptare n irul READY, de execuie (n UC) i de realizare a operaiilor I/O ;

20

Sisteme de operare-durata de ateptare ( algoritmul de ateptare influeneaz

numai durata de ateptare n irul READY i nu afecteaz durata de execuie a procesului sau timpul destinat operaiilor I/O) ;

-durata de rspuns (timpul scurs ntre formularea unei cereri i iniierea rspunsului corespunztor).

Prin alegerea unui algoritm de planificare se urmrete optimizarea criteriului luat n consideraie i anume maximizare pentru primele dou i minimizare pentru ultimele trei.

2.3. ALGORITMI DE PLANIFICARE UC

n prezentarea algoritmilor de planificare UC performanele sunt apreciate cu ajutorul mrimii DMA (durata medie de ateptare).

2.3.1. Algoritmul FCFS (First Come First Served)

irul READY este de tip FIFO (First Inpout First Output= Primul Intrat Primul Ieit).

Exemplu:Proces Durata

UC

Durata de

ateptare1 10 02 29 103 3 394 7 425 12 49

Durata medie de ateptare va fi :DMA=(0+10+39+42+47)/5=140/5 =28Dezavantaje : DMA nu este minimal i poate varia n

limite foarte largi n funcie de caracteristicile procesului. n plus DMA depinde de ordinea proceselor.

21

Sorin Adrian Ciureanu

2.3.2. Algoritmul SJF (Shortest Job First)

Aa cum arat denumirea, se execut mai nti cel mai scurt job. La egalitate, se aplic regula FCFS (First Come First Served).

Exemplu:

Proces Durata UC

Proces Durata UC

Durata de ateptare

1 10 3 3 02 29 4 7 33 3 1 10 104 7 5 12 205 12 2 29 32

Durata medie de ateptare va fi : DMA =(3+10+20+32)/5=65/5=13

Dac se cunosc cu precizie ciclurile UC (ca timp), SJF este optimal. Problema principal este cunoaterea duratei ciclului UC.

2.3.3. Algoritmi bazai pe prioritate

n cadrul unui astfel de algoritm, fiecrui proces i se asociaz o prioritate, UC fiind alocat procesului cu cea mai mare prioritate din irul READY. Se poate defini o prioritate intern i o prioritate extern.

Prioritatea intern se calculeaz pe baza unei entiti msurabile :

-limita de timp ;-necesarul de memorie ;-numrul fiierelor deschise ;

22

Sisteme de operare-raportul dintre numrul de cicluri rafal I/O i numrul de cicluri rafal UC.Pentru prioritatea extern, criteriile folosite sunt din afara

sistemului de operare :-departamentul care sponsorizeaz lucrrile ;-factori politici ;-factori financiari.Principala problem a algoritmilor bazai pe prioriti este

posibilitatea blocrii la infinit ( a nfometrii) proceselor care sunt gata de execuie, dar deoarece au prioritate redus, nu reuesc s obin accesul la UC. O astfel de situaie poate s apar ntr-un sistem cu ncrcare mare, n care se execut un numr considerabil de procese cu prioritate ridicat ; acestea vor obine accesul la UC n detrimentul proceselor cu prioritate redus care pot s nu fie executate niciodat. O soluie a acestei probleme este mbtrnirea proceselor, o tehnic prin care se mrete treptat prioritatea proceselor remanente timp ndelungat n sistem.

2.3.4. Algoritmi preemptivi

Un algoritm preemptiv permite ntreruperea execuiei unui proces n momentul cnd n irul READY apare un alt proces cu drept prioritar de execuie.

Dintre algoritmii prezentai anterior :-FCFS este prin definiie nepreemptiv ;-SJF poate fi realizat preemptiv; dac n irul READY

sosete un proces al crui ciclu rafal UC urmtor este mai scurt dect ce a mai rmas de executat din ciclul curent, se ntrerupe execuia ciclului curent i se aloc UC noului proces;

-algoritmii bazai pe prioritate, de asemenea, pot fi realizai preemptiv ; la fel ca la SJF, timpul rmas poate fi nlocuit cu mrimea prioritii.

23

Sorin Adrian Ciureanu Exemplu:

Proces Momentul sosirii n irul READY

Durata ciclului rafal

1 0 122 3 33 4 6

n SJF fr preempie :

Ordine AteptareP1(12) 0P2(3) 9P3(6) 8+3

DMA = (9+8+3 )/3=6,67

n SJF cu preempie :

Ordine AteptareP1 3 P1 ateapt 3+6=9P2 3 P2 ateapt 0P3 6 P3 ateapt 3-1P1 9

DMA = (9+0+2)/3 =3,67

2.3.5. Algoritmul Round-Robin

24

Sisteme de operareEste un algoritm de tip time-sharing. Fiecrui proces i se

aloc numai o cuant de timp (10ms 100ms) iar irul READY se trateaz ca FIFO circular.

Exemplu:

Proces Durata ciclului rafal

1 10 P1 ateapt2 293 34 75 12

Dac cuanta de timp este de 10 ms, atunci ordinea n UC este urmtoarea:

P1(0) P2(19) P3(0) P4(0) P5(2) P2(9) P5(0) P2(0)n parantez este dat timpul care a mai rmas.Observaii :-planificatorul aloc UC fiecrui proces pe durata a cel

mult o cuant ; dac durata procesului este mai mic dect aceast cuant, procesul elibereaz UC prin comunicarea ncheierii execuiei ;

-mrime cuantei afecteaz performanele algoritmului Round-Robin ; dac cuanta este foarte mare, comportarea este asemntoare FCFS ; dac cuanta este foarte mic, frecvena comutrii se mrete foarte mult i performanele scad deoarece se consum mult timp pentru salvare/restaurare registre ;

-se poate spune c algoritmul Round-Robin este un algoritm preemptiv care asigur un timp aproape egal de ateptare pentru toate procesele din sistem.

2.3.6. Ali algoritmi de planificare

25

Sorin Adrian CiureanuExist unii algoritmi cu iruri de procese multinivel. irul

READY este format din mai multe subiruri. Fiecare susbir are propriul algoritm de planificare. n schema de planificare apar iruri READY multiple :

26

P1 P

2..P

n

P1 P

2..P

n

P1(n) P

2 (n)P

n(n)

(..Pn

UC

Sisteme de operare

3. GESTIUNEA PROCESELOR

3.1.NOIUNI GENERALE DE PROCESE I THREADURI

3.1.1. Definiia procesului

ntr-un sistem de calcul, un proces este un program n execuie; este deci o entitate activ (dinamic) a sistemului de operare i constituie unitatea de lucru a sistemului.

nelegerea diferenei ntre un program i un proces este important. Andrew Tannenbaum, al crui tratat este baza documentrii pentru specialitii n SO, folosete o analogie pentru sesizarea acestei diferene. S considerm un savant care coace un tort pentru aniversarea fiicei sale. Are reeta tortului i o buctrie utilat i aprovizionat cu tot ce trebuie s intre n tort: ou, zahr, vanilie etc. n aceast analogie, savantul este procesorul (CPU=Central Processing Unit), reeta este programul ( ex. un algoritm exprimat ntr-o notaie potrivit), ingredientele sunt datele de intrare. Procesul este activitatea savantului de a citi reeta, de a introduce ingredientele , de a coace tortul.

S ne nchipuim acum c fiul savantului vine plngnd c l-a nepat o albin. Savantul ntrerupe coacerea tortului nregistrnd repede unde a ajuns n reet (starea procesului curent este salvat), caut o carte de prim ajutor (trece la un proces prioritar cu alt program), i aplic instruciunile gsite n ea. Cnd primul ajutor a fost dat, savantul se ntoarce la coacerea tortului i o continu de unde a ntrerupt-o.

Ideea este c un proces este o activitate de un anumit fel, cu un program, intrare, ieire, stare etc. Este posibil ca un singur procesor s fie mprit la mai multe procese, cu ajutorul unui

27

In sistem

Pregtit

Blocat Rulare

Terminat

HARD

Sorin Adrian Ciureanualgoritm care s determine cnd s fie oprit procesul curent i s fie derulat altul.

Un proces este instana de execuie a unui cod. Se utilizeaz i denumirea englez de task (sarcin).

Spaiul de adres a unui proces cuprinde:-segmentul de cod care conine imaginea executabil a

programului i este de tip RO (Read Only) i partajat de mai multe procese;

-segmentul de date care conine date alocate dinamic sau static de ctre proces; nu este partajat i nici accesibil altor procese; const din:

-zona de date-zona de rezervri (date neiniializate)-zona de alocare dinamic;

-segmentul de stiv care nu este partajat i crete antrenat n momentul epuizrii cantitii de memorie pe care o are la dispoziie.

Threadul, numit i fir de execuie, este o subunitate a procesului, utilizat n unele SO.

3.1.2. Starea procesului

ntr-un sistem de calcul, un proces poate fi n diferite stri: pregtit, rulare, blocat, terminat

Cnd procesul este introdus n calculator, este n SISTEM (de obicei fiier sau un grup de fiiere pe un disc). Apoi planificatorul pe termen lung l ia i-l introduce n coada de ateptare READY i atunci procesul este PREGTIT. Planificatorul pe termen scurt UC, conform unui algoritm de planificare , l introduce n UC. Procesul este n RULARE. De aici, exist trei posibiliti:

-procesul s-a sfrit i, dup rularea n UC, trece n starea TERMINAT;

28

In sistem

Pregtit

Blocat Rulare

Terminat

HARD

Sisteme de operare-dac algoritmul folosit este preemptiv (de exemplu time-

sharing , cu timp partajat), dac dup o cuant de timp el mai are de rulat, este trecut din nou n coada de ateptare READY n starea PREGTIT;

-dac n timpul rulrii are nevoie de o resurs extern (de obicei I/O), procesul este trecut n starea BLOCAT. Dup ce i s-a alocat resursa, trece din nou n starea PREGTIT.

1 Planificatorul pe termen lung

5 3 2 Planificatorul pe termen scurt (UC)

4

6

Fig. 3.1. Diagrama strilor unui proces.

Dac un proces este blocat temporar, el va trebui repornit mai trziu din exact aceeai stare n care se gsea cnd a fost oprit. n acest scop, toate informaiile despre proces trebuiesc salvate.

Unui proces i se asociaz de obicei o structur numit BCP (Bloc Control Proces), un descriptor de proces.

n mod frecvent, descriptorii tuturor proceselor aflate n aceeai stare sunt nlnuii n cte o list. Vom avea o list de procese n starea PREGTIT, una n starea BLOCAT etc.

29

In sistem

Pregtit

Blocat Rulare

Terminat

Identificator al procesului (PID)

Program Counter

Stack Pointer

Pregtire UC

Prioritate

Zon pentru salvarea strii la prelevarea resursei procesor

Pointer spre lista procselor aflate n aceeai stare

HARD

Sorin Adrian Ciureanu

Fig 3.2. Structura BCP a unui proces.

3.1.3. Comutarea proceselor

Tranziia ntre dou procese active ntr-un SO multitasking se numete comutarea proceselor (proces switch) i are loc ca rspuns la un eveniment din sistem. Comutarea proceselor implic un cost (overhead) important datorit frecvenei cu care are loc n sistem i poate influena performanele acestuia.

Eficiena operaiei de comutare a proceselor poate fi crescut prin prevederea unor faciliti hard (seturi de registre multiple) sau printr-o modalitate de structurare a procesului (thread). Un thread (fir de execuie) este o subunitate a procesului, o diviziunea a sa. Fiecare thread reprezint un flux separat de execuie i este caracterizat prin propria sa stiv i prin stri hard (registre, flaguri).

Scopul principal al crerii threadului este reducerea costului de comutare a proceselor. De vreme ce toate celelalte resurse, cu excepia procesorului, sunt gestionate de procesul care le nglobeaz, comutarea ntre threadurile care aparin aceluiai proces implic doar salvarea strii hard i restaurarea

30

Sisteme de operarestivei. Bineneles, comutarea ntre threadurile care aparin unor procese diferite implic acelai cost de comutare.

Threadurile sunt un mecanism eficient de exploatare a concurenei programelor.

Un program poate fi mprit n mai multe pri.

Spaiu utilizator

Execuie proces PX Eveniment ce duce la comutare Salvarea strii hard n BCPX i actualizarea strii procesului PX n BCPX .

[ SCRIEREA EVENIMENTULUI]

Planificarea urmtorului Proces PY. Restaurarea strii hard din BCPY . Execuie proces PY

Fig.3.3 Schem de comutare a proceselor.

3.1.4. Crearea i terminarea proceselor

31

Mod de comutare

Mod de comutare

Sorin Adrian Ciureanun marea majoritate a sistemelor de operare un proces

poate fi creat, n mod dinamic, de ctre alt proces. De obicei un proces printe creeaz un proces fiu. n aceast modalitate de creare, exist mai multe posibiliti n dualitatea printe-fiu:

-cele dou procese execut, n mod independent, nesincronizat, acelai cod, avnd aceeai stiv i acelai segment de date;

-fiul execut alt segment de cod dect cel al printelui, nesincronizat;

-printele i fiul i sincronizeaz activitatea n sensul ei ori se execut nti printele i apoi fiul sau invers.

3.2. PROCESE I THREADURI N UNIX

3.2.1. Procese n UNIX

n sistemul de operare UNIX fiecare proces are un identificator numeric, numit identificator de proces PID. Acest identificator este folosit atunci cnd se face referire la procesul respectiv din interiorul programelor sau prin intermediul interpretorului de comenzi.

Dou apeluri simple permit aflarea PID-ului procesului curent i al printelui acestuia:

getpid(void) pentru procesul curent;getppid(void) pentru procesul printe.Creerea unui proces se face prin apelul sistem:fork()Prin aceast funcie sistem, procesul apelant, numit printe,

creeaz un nou proces, numit fiu, care va fi o copie fidel a printelui. Procesul fiu va avea:

-propria lui zon de date,-propria lui stiv,-propriul su cod executabil,

toate fiind copiate de la printe, n cele mai mici detalii.

32

Proces iniial

1 2 3

2 3 3

3

Sisteme de operareO modalitate de utilizare a apelului fork() este de a

mpri codul unui proces n dou sau mai multe procese care se vor executa n paralel. Acest lucru este utilizat n proiectarea i rularea proceselor i programelor paralele.

Exemplul 1.Proces printei1i2i3..ik momentul apelului fork() Proces fiuik+1 ik+1ik+2 ik+2. .. .

in in Exemplul 2Se d urmtoarea secven de program:fork();printf(A\n);fork();printf(B\n);fork();printf(C\n);Presupunnd c toate apelurile funciei fork() se execut

cu succes, se cere:-Cte procese sunt create ?-S se traseze arborele printe - fiu al proceselor create.-Cte linii de text vor fi afiate la ieirea standard ?-Este posibil ca linia cu textul B s fie afiat naintea

liniei cu textul A ?Sunt create 7 procese, plus procesul iniial, vor fi 8

procese. Cifrele arat dup al ctelea fork() au fost create.

33

Proces iniial

1 2 3

2 3 3

3

Sorin Adrian CiureanuDup primul fork()se creeaz procesul cu cifra 1. Se va scrie A att n procesul iniial ct i n cel final. Dup al doilea fork(), se creeaz procesul fiu notat cu cifra 2, adic fiecare proces creat pn acum va avea cte un fiu, notat cu 2. Dup al treilea fork(), fiecare proces creat pn acum va crea cte un nou fiu, notat cu 3. n general dup n fork() ,se produc 2n-1 fii.

A B C

A B B C C C

B C C C

C

Fig.3.4.Structura arborescent a proceselor.

Fiecare proces afieaz liniile de text care urmeaz momentului crerii sale:

linia care scrie A este afiat de 21 ori;linia care scrie B este afiat de 22 ori;linia care scrie C este afiat de 23 ori.Numrul total de linii afiate este 21+22+23=14n ceea ce privete ordinea de afiare a celor 14 linii,

intervine nedeterminarea provenit din faptul c nu se tie cine va fi executat primul, printele sau noul fiu creat. Valoarea returnat de fork() este: -1, eroare, operaia nu s-a putut executa;

0, n codul fiului;

34

Proces iniial

1 2 3

2 3 3

3

Sisteme de operare pidf, n codul printelui, unde pidf este identificatorul de

proces al fiului nou creat.Pn acum am vzut c prin simplul apel al funciei

fork() se creeaz un proces identic cu procesul printe. Pentru a crea un nou proces care s ruleze un program diferit de cel al printelui, se vor folosi funciile de tipul exec(), execl(), execlp(), execv(), execvp(), execll(), execvl(). Toate aceste funcii primesc ca parametru un nume de fiier care reprezint un program executabil i recicleaz lansarea n execuie a programului. Programul va fi lansat astfel nct se va suprascrie codul, datele i stiva procesului care apeleaz exec(), aa ca, imediat dup acest apel, programul iniial s nu mai existe n memorie. Procesul va rmne, ns, identificat prin acelai PID i va moteni toate eventualele redirectri fcute n prealabil asupra descriptorilor de fiier.

n concluzie, lansarea ntr-un proces separat a unui program se face apelnd fork()pentru crearea noului proces, dup care, n poriunea de cod executat de fiu, se va apela una din funciile exec().

n UNIX un proces se poate termina n mod normal sau anormal.

Terminarea normal poate fi realizat prin:-revenire natural;-apelul sistem de tip exit().Terminarea anormal se produce cnd:-se apeleaz abort();-procesul primete un semnal.n marea majoritate a versiunilor UNIX, exist dou

apeluri de terminare normal: exit(), _exit().Principalul rol al apelului exit() este s asigure la terminarea procesului tratarea corespunztoare a operaiilor de introducere /extragere , golirea tampoanelor utilizate pentru acest proces i nchiderea tuturor fiierelor deschise. _exit() produce direct revenirea n nucleu, fr operaiile de la funcia exit().

35

Sorin Adrian CiureanuDin cele prezentate pn acum, nu se poate spune nimic

despre sincronizarea printe-fiu, adic despre cine termin primul sau cine se execut primul. Apelurile wait() i waitpid() vin n ntmpinarea acestui neajuns. wait() este folosit pentru ateptarea de ctre printe a fiului, deci se execut mai nti fiul i apoi printele. waitpid() este folosit pentru ateptarea unui proces oarecare.

n UNIX procesele au un caracter dinamic. Ele se nasc, evolueaz n sistem putnd da natere altor sisteme, i dispar. n felul acesta se creeaz o ierarhie dinamic de procese n sistem, care ncepe cu procesul 0 (swapper), continu cu procesul 1 (init), proces ce d natere unor procese fiu. Procesul cu identificatorul 2, proces sistem, apare la unele implementri sub denumirea de pagedaemon i este responsabil de suportul pentru memorie virtual. Terminarea forat a execuiei unui proces se realizeaz cu comanda kill(opiuni)(pid).

n general, n execuia printe fiu, exist dou situaii:-a) fiul se termin naintea printelui;-b) printele se termin naintea fiului.n primul caz, ntre momentul n care se termin fiul i

momentul n care el este distrus, procesul fiu este n starea zombie. De obicei, dup terminarea execuiei fiului, printele execut un wait() i scoate fiul din starea zombie.

n al doilea caz, n momentul terminrii printelui, nucleul SO este acela care examineaz dac printele a avut copii. Dac da, printele nou al acestor fii va fi procesul init(), nelsnd fiii n starea zombie.

Revenind la strile unui proces, sistemul de operare UNIX distruge urmtoarele stri de baz:

-execuie n mod utilizator (USER);-execuie n mod nucleu (KERNEL);-gata de execuie (READY);-n ateptare (BLOCAT)-zombie.

36

Sisteme de operare

3.2.2. Threaduri n UNIX

n UNIX-ul tradiional nu sunt definite threadurile. Ele au aprut odat cu standardul POSIX care asigur portabilitatea ntre platforme hard diferite. Iat o comparaie ntre procesele UNIX i threadurile POSIX (pthread):

Caracteristica Procese UNIX Pthreaduri POSIXportabilitate fork()standard interfa standard

portabilitateCost de creare Mare Relativ micCost de comutare Mare Foarte micSpaiu de aches Separat PartajatMemorie partajat Partajare explicit Partajare implicitObiecte de excludere mutual

Semafoare, mutexuri UNIX

Semafoare, mutexuri POSIX

Fiiere i stringuri de I/O

Tabele de fiiere separate

Tabele de fiiere unice

Un pthread se creeaz cu ajutorul funciei int pthread create (list de parametri).

3.3. PROCESE I THREADURI N WINDOWS

n sistemele WINDOWS, entitatea de alocare a timpului procesoarelor este threadul. Fiecare proces conine cel puin un thread de execuie, numit i threadul principal, i poate crea threaduri noi. Un proces WINDOWS are o dualitate de identificare i anume are dou entiti de identificare:

-handle, care este o intrare n tabelul de resurse al sistemului;

-identificator (id), un numr unic atribuit unui proces (asemntor PID-ului din UNIX).

37

Sorin Adrian CiureanuAceast dualitate de identificare ngreuneaz lucrul cu

procesele WINDOWS, n sensul c unele funcii cer ca parametru handle-ul procesului , altele identificatorul acestuia.

3.3.1. Procese n WINDOWS

Accesul programatorului la funciile SO este posibil prin intermediul unei interfee, numit API (Aplication Programming Interface) care conine definiia tipurilor de date i funciile de apel ale sistemului.

Un proces tat creeaz un proces fiu prin intermediul apelului funciei bool create process(lista parametri). Se poate considera c, n mare, aceast funcie are funcionalitatea combinaiei de apeluri fork exec din UNIX. Se creeaz un proces nou, mpreun cu threadul primar, care execut un segment de cod specificat prin numele fiierului ce conine acest segment. Valoarea returnat de funcia createprocess este de tip booleean i nsemn TRUE (succes) i FALSE (eroare).

Crearea threadurilor WINDOWS. Crearea unui thread nou ntr-un proces necesit definirea unei funcii pe care threadul s o execute, urmat de apelul unei funcii createthread cu sintaxa handle create thread (lista de parametri). Aceast funcie returneaz handle-ul threadului nou creat.

38

Sisteme de operare

4. COMUNICAIA I SINCRONIZAREA NTRE PROCESE

Procesele dintr-un SO pot fi:-a) procese independente;-b) procese cooperante.a) Dac execuia unui proces nu poate afecta sau nu este

afectat de ctre execuia altor procese din sistem, atunci procesul este independent. Procesele independente au urmtoarele caracteristici:

-pot fi oprite i repornite fr a genera efecte nedorite;-sunt deterministe, adic rezultatele depind numai de starea

de intrare;-nu se afl niciodat n aceeai stare ca i alte procese din

sistem;-nu folosesc date, variabile, n comun cu alte procese;-sunt reproductibile, rezultatele sunt aceleai pentru

aceleai condiii de intrare.b) n caz contrar, procesele sunt cooperante; au toate

caracteristicile de mai sus negate.

4.1. PROBLEMA SECIUNII CRITICE I A EXCLUDERII MUTUALE

Cazul cel mai frecvent n care mai multe procese comunic ntre ele este acela prin intermediul variabilelor partajate. Dar accesul nerestricionat a dou sau mai multe procese la resurse partajate poate produce erori de execuie.

39

Sorin Adrian CiureanuExemplu:Un proces execut o operaie de incrementare a variabilei

partajate x dup secvena cod:LOAD R x /ncrcarea lui x n registrul R;INC R /incrementarea lui R;STORE x R /memorarea valorii n X.Presupunem c arhitectura calculatorului este cea de

load/store, specific procesoarelor de mare vitez cum sunt i cele din arhitectura RISC.

Variabila local x, n arhitecturi paralele, se numete temporar inconsistent, ntre variabila local i variabila global corespunztoare. Acest tip de inconsisten temporar este frecvent ntlnit n execuia programelor la arhitecturi secveniale (Neumann), dar nu prezint nici un pericol pentru execuia programelor secveniale normale ale cror variabile nu sunt partajate ntre procese concurente.

Este important de observat c inconsistena temporar ntre o variabil global i copia ei local reprezint una din principalele cauze care produce erori atunci cnd o astfel de variabil este accesat concurent de procese concurente.

Din acest exemplu reies dou condiii necesare pentru eliminarea erorilor datorate execuiei concurente a mai multor procese:

1) Secvena de instruciuni din care este alctuit operaia de actualizare a unei variabile partajate trebuie s fie executat de un proces ca o operaie atomic, nentreruptibil de ctre alte procese sau chiar de SO.

2) Operaia de actualizare a unei variabile partajate executat de un proces trebuie s inhibe execuia unei alte operaii asupra aceleai variabile executate de alt proces. Este deci necesar serializarea operaiilor asupra variabilelor partajate, serializare care se obine prin excludere mutual a acceselor la variabila partajat.

n acest sens actualizarea unei variabile partajate poate fi privit ca o seciune critic. O seciune critic este o secven de

40

Sisteme de operareinstruciuni care actualizeaz n siguran una sau mai multe variabile partajate. Cnd un proces intr ntr-o seciune critic, el trebuie s execute complet toate instruciunile seciunii critice, nainte ca alt proces s o poat accesa. Numai procesului care execut o seciune critic i este permis accesul la variabila partajat, n timp ce tuturor celorlalte procese le este interzis accesul. Acest mecanism est denumit excludere mutual , deoarece un proces exclude temporar accesul altor procese la o variabil partajat.

Soluionarea problemei excluderii mutuale trebuie s ndeplineasc urmtoarele cerine:

-s nu presupun nici o condiie privind viteza de execuie sau prioritatea proceselor care acceseaz resursa partajat;

-s asigure c terminarea sau blocarea unui proces n afara seciunii critice nu afecteaz n nici un fel toate celelalte procese care acceseaz resursa partajat corespunztoare seciunii critice respective;

-atunci cnd unul sau mai multe procese doresc s intre ntr-o seciune critic, unul din ele trebuie s obin accesul n timp finit.

Mecanismul de baz pe care-l urmrete un proces este:-protocol de negociere / nvingtorul continu execuia;-seciune critic / utilizarea exclusiv a resursei;-protocol de cedare / proprietarul se deconecteaz. Soluionarea corect a excluderii mutuale nu este o

problem trivial. Primul care a soluionat aceast problem a fost matematicianul olandez Decker. Soluia lui, ns, nu este valabil dect pentru dou procese. Soluii de excludere mutual au mai dat Peterson i Lampert, soluii pur soft, dar a cror eficien este discutabil cci nu rezolv n ntregime toate cerinele. Implementarea eficient a excluderii mutuale se poate realiza prin suport hard (validare/invalidare de ntreruperi sau instruciuni Test and Set). Aceste faciliti hard sunt utilizate

41

Sorin Adrian Ciureanupentru implementarea unor mecanisme de sincronizare (obiecte de sincronizare) ca semafoare, mutexuri, bariere, monitoare etc.

4.1.1. Suportul hardware pentru implementarea excluderii mutuale

4.1.1.1. Invalidarea / validarea ntreruperilor

Instruciunile de invalidare/validare a ntreruperilor (DI/EI) sunt disponibile n toate procesoarele. Secvena care asigur accesul exclusiv al unui singur proces la o resurs este:

DI / invalidare ntreruperi;Seciune critic;EI / validare ntreruperi.Prin invalidarea ntreruperilor se ajunge la blocarea

celorlalte procese. Este un mecanism prea dur, un model pesimist de control al concurenei, cu urmtoarele dezavantaje:

-se blocheaz i activitatea altor procese (numite victime inocente) care nu au nici o legtur cu seciunea critic respectiv;

-dac se execut de ctre useri, se poate bloca sistemul iar dac sunt executate din kernel, apare un cost de timp suplimentar (overhead) de comutare a modului de execuie kernel/user.

4.1.1.2. Instruciunea Test and Set (TS)

n principiu, instruciunea TS are ca operand adresa unei variabile de control i execut urmtorii pai:

-compar valoarea operandului cu o valoare constant (de exemplu 0 pentru BUSY) i seteaz flagurile de condiie ale procesorului;

-seteaz operandul la valoarea BUSY .Aceti pai sunt executai ca o operaiune unic,

indivizibil, numit operaie atomic.

42

Sisteme de operareSubinstruciunea cod, TS, poate fi scris astfel:LOAD R, operandCMP R, BUSY flag ZERO=1 dac R=BUSSYSTORE operand,BUSY

4.1.1.3. Protocoale de ateptare n excluderea mutual

Avem dou tipuri de protocoale:a) (busy-wait)b) (sleep-wait)a) BUSY-WAIT (ateptare ocupat) Folosind instruciunea TS acest model are urmtoarea

implementare: ADRL TS (acces)

JZ ADRL/ateptare ct variabila acces=BUSY BUSY-WAIT este simplu de implementat dar are

dezavantajul unei eficiene sczute, datorit faptului c se consum timp de execuie al procesorului de ctre un proces care nu avanseaz.

b) SLEEP-WAIT (ateptare dormant) n acest tip de protocol, procesul care nu are resurs

disponibil este suspendat (adormit) i introdus ntr-o coad de ateptare. Apoi este trezit, cnd resursa devine disponibil.

n sistemul uniprocesor este folosit totdeauna SLEEP-WAIT, deoarece nu se consum timp procesor inutil.

n sistemul multiprocesor se folosesc amndou protocoalele i chiar o combinaie ntre ele.

4.1.1.4. Mecanisme de sincronizare ntre procese (obiecte de sincronizare)a) Semafoare. Semafoarele sunt obiectele de sincronizare cele mai des i

mai mult folosite. Ele au fost introduse de Dijkstra n 1968.

43

Sorin Adrian CiureanuUn semafor este de fapt o variabil partajat care poate

primi numai valori nenegative. Asupra unui semafor se pot executa dou operaii de baz:

-decrementarea variabilei semafor cu 1 (DOWN);-incrementarea variabilei semafor cu 1 (UP).Dac o operaie DOWN este efectuat asupra unui semafor

care este mai mare dect zero, semaforul este decrementat cu 1 i procesul care l-a apelat poate continua. Dac, din contra, semaforul este zero, operaia DOWN nu poate fi efectuat i spunem c procesul ateapt la semafor, ntr-o coad de ateptare, pn cnd un alt proces efectueaz operaia UP asupra semaforului, incrementndu-l.

Exemplu.Avem un complex cu terenuri de handbal i 20 echipe care

joac 10 meciuri. 1meci = 1proces. ntr-un co mare (semafor) exist 7 mingi. Semaforul ia valori ntre 0-7. Fiecare 2 echipe iau cte o minge din co, efectund 7 operaii DOWN. Semaforul este 0 ( nu mai sunt mingi n co) i celelalte 6 echipe ateapt o minge n co, deci o operaie UP.

Pentru implementare, operaiile DOWN i UP vor fi nlocuite cu dou primitive wait(s) i signal(s) , n felul urmtor:

wait(s) - ncearc s decrementeze valoarea variabilei semafor s cu 1 i dac variabila este 0 procesul rmne n ateptare pn cnd s 0.

signal(s) incrementeaz cu 1 semaforul s.

Implementarea semafoarelor n protocolul BUSY-WAIT

wait(s){while (s==0);s--;}signal(s++);}

Operaia signal(s) este atomic (indivizibil).

44

Sisteme de operareOperaia wait(s) are dou regimuri: atomic, dac s 0; neatomic, dac s=0.Este normal ca, dac semaforul este ocupat (s=0), operaia

wait(s) s nu fie atomic; n caz contrar ar mpiedica alte operaii, inclusiv signal(s), executate de un alt proces care s acceseze variabila s pentru a o elibera.

Implementarea cu BUSY-WAIT a semafoarelor are dezavantajul unui consum de timp procesor de ctre procesele aflate n ateptare. Un alt dezavantaj este posibilitatea ca un proces s fie amnat un timp nedefinit (indefinit, postponement) n obinerea unui semafor, datorit faptului c nu este nici o ordonare ntre procesele care ateapt la semafor. Astfel exist posibilitatea ca un proces s fie mpiedicat un timp nedefinit de a obine un semafor datorit aglomerrii provocate de alte procese. Un astfel de fenomen de blocare se numete livelock iar procesul afectat este numit strivit (starved).

Implementarea semafoarelor n protocolul SLEEP-WAIT Procesele care ateapt la semafor stau ntr-o coad de

ateptare (FIFO).

wait(s){if(s==0) procesul trece ]n starea suspendat;else s--;}signal(s){if(coada nu este goal) planific un proces

din coad ;else s++ ;}

n loc s intre n ateptare ocupat, atunci cnd semaforul este ocupat, procesul apelant este suspendat i trecut ntr-o coad de ateptare asociat semaforului apelat. Trebuie ns ca i procesul dormant (suspendat) s afle cnd semaforul a devenit liber. Acest lucru se realizeaz prin intermediul operaiei signal. Aceast operaie ncearc mai nti s trezeasc un proces din

45

Sorin Adrian Ciureanucoada de ateptare i s-l treac n starea de execuie (suspendatrun). Numai dac coada de ateptare este goal, incrementaz semaforul.

b) Mutex-uriDenumirea MUTEX vine de la mutual exclusion. Mutex-ul

este un caz particular de semafor i este utilizat pentru accesul mai multor procese la o singur resurs partajat. Operaiile care se execut asupra unui mutex sunt :

-operaia de acces i obinere a mutex-ului, notat cu ocupare (mutex) sau lock(mutex) ;

-operaia de eliberare a mutex-ului, notat cu eliberare (mutex) sau unlock(mutex).

c) Evenimente (semnale)Unul dintre primele mecanisme de comunicare ntre

procese este reprezentat de semnale sau evenimente. n UNIX se numesc semnale iar n WINDOWS se numesc evenimente. Ele anun apariia unui eveniment i pot fi trimise de un proces altui proces, de un proces aceluiai proces sau pot fi trimise de kernel. Momentul apariiei unui semnal este neprecizat, el aprnd asincron.

Semnale UNIXn sistemul de operare UNIX, semnalele pot proveni de la

nucleu sistemului, prin care se notific evenimente hardware, sau pot fi generate soft, de unele procese, pentru a notifica un eveniment asincron. Un semnal este reprezentat printr-un numr i un nume. n UNIX semnalele dintre procese au denumiri simbolice, SIGUSR 1 i SIGUSR 2.

Un proces care primete un semnal poate s acioneze n mai multe moduri:

-s ignore semnalul;-s blocheze semnalul; n acest caz semnalul este trecut

ntr-o coad de ateptare pn cnd este deblocat;-s recepioneze efectiv semnalul.

46

Date accesate n comun

Proceduri Variabile partajate

Sisteme de operareProcesul stabilete ce semnale sunt blocate, folosind o

mas de semnale, n care fiecare bit corespunde unui numr de semnal. n standardul POSIX exist numere ntre 33 i 64, deci 31 semnale. Un semnal poate s apar n urmtoarele cazuri:

-la acionarea unei taste a terminalului;-la apariia unei ntreruperi hardware (mprire prin zero,

adres inexistent etc);-atunci cnd un proces trimite un semnal altui proces sau

thread, folosind funciile:a)sigqueue() se transmite un semnal unui proces;b)kill() se transmite un semnal de terminare a unui

proces;c)pthread se transmite semnal de terminare a unui

thread. Evenimente WINDOWSn SO WINDOWS, un eveniment este un obiect de

sincronizare care poate fi semnalat sau nesemnalat.Exist dou tipuri de evenimente:-evenimente cu resetare manual (evenimente care trecute

n stare semnalat rmn n aceast stare pn cnd sunt trecute n mod explicit n starea nesemnalat);

-evenimente cu autoresetare.n WINDOWS un proces poate crea un eveniment folosind

funcia CREATE EVENT.Un proces n ateptarea unui eveniment poate executa una

din funciile de ateptare WAIT FOR SINGLE OBJECT sau WAIT FOR MULTIPLE OBJECT.

Evenimentele sunt utilizate pentru notificarea unui proces sau thread despre apariia unui alt eveniment.

Evenimentele creeaz puncte de sincronizare ntre procese sau threaduri.

d) Monitoare. Monitoarele sunt mecanisme de sincronizare ntre procese concurente care pot suporta abstractizarea datelor.

47

Date accesate n comun

Proceduri Variabile partajate

Sorin Adrian CiureanuPrin apariia monitoarelor (HOARE, 1976), se reuete s

se acopere unul din neajunsurile principale ale celor mai utilizate mecanisme de sincronizare, semafoarele, care nu suport abstractizarea datelor.

Sintaxa monitorului este asemntoare cu cea a unei clase, cuvntul CLASS fiind nlocuit cu MONITOR.

Este de remarcat faptul c ntr-un monitor se asigur excluderea mutual, astfel c la un moment dat un singur proces poate fi activ.

Un monitor este bazat pe modularitate i ncapsulare.

Coad de intrare n monitor

Fig. 4.1.Structura unui monitor.

Structura unui monitor const n trei pri:-n prima parte se declar numele monitorului i variabilele

locale;-n a doua parte se declar toate procedurile;-n cea de a treia parte se iniializeaz toate variabilele

acestui monitor.n general, procedurile unui monitor sunt constituite din

principalele funcii care se ntlnesc ntr-un sistem de operare. De exemplu, o procedur tipic este intrarea ntr-o seciune critic.

48

Date accesate n comun

Proceduri

Proc 1

Proc 2

Proc n

Variabile partajate

P1 P2 Pn

Sisteme de operare4.2. INTERBLOCAREA (DEADLOCK)

Alturi de problema seciunii critice, interblocarea reprezint una din principalele probleme ce trebuiesc soluionate n funcionarea unui SO. Mecanismul principal al interbocrii const n faptul c o resurs cerut de un proces este deinut de alt proces. Pn cnd procesul care deine resursa o va elibera, apare o situaie tipic de interblocare.

Deoarece interblocarea este strns legat de resursele sistemului de operare, vom prezenta, mai nti, cteva noiuni referitoare la aceste resurse.

4.2.1. Resurse

4.2.1.1. Clasificarea resurselor din punct de vedere al interblocrii

Cea mai important clasificare din punct de vedere al interblocrii este:

a) resurse partajabile ;b) resurse nepartajabile.O resurs partajabil poate fi utilizat n comun de mai

muli utilizatori. Un exemplu clasic n acest sens este citirea unui fiier de ctre mai muli utilizatori.

O resurs nepartajabil nu poate fi folosit n acelai timp de ctre mai muli utilizatori. Un exemplu este imprimanta. Evident, mai muli utilizatori nu pot tipri n acelai timp pe aceeai imprimant. Numai resursele nepartajabile conduc la situaii de interblocare; cele partajabile nu pun probleme din acest punct de vedere. Sistemul de operare, n procesul de control al interblocrii, trebuie s aib o gestiune doar a resurselor nepartajabile.

O alt clasificare a resurselor, important pentru interblocare, este:

49

Ri

Sorin Adrian Ciureanua) resurse cu un singur element;b) resurse cu mai multe elemente.Pentru situaii diferite de interblocare, aceast clasificare

este foarte important, ea ducnd la decizii diferite. Un exemplu tipic unde intervine aceast clasificare este graful de alocare a resurselor.

4.2.1.2. Etapele parcurse de un proces pentru utilizarea unei resurse

n vederea utilizrii unei resurse, un proces trebuie s execute urmtoarele etape:

a)Cererea de acces la resurs. Procesul formuleaz o cerere de acces la resursa respectiv. Dac nu i este repartizat imediat, intr ntr-o coad de ateptare i va atepta pn cnd poate dobndi resursa.

b)Utilizarea resursei. Este etapa n care procesul a primit permisiunea de utilizare a resursei, iese din coada de ateptare i utilizeaz efectiv resursa.

c)Eliberarea resursei. Se elibereaz resursa i se ncheie utilizarea resursei de ctre proces.

Pentru implementarea de ctre SO a acestei operaii, exist tabele ale SO n care fiecrei resurse i este asociat procesul ce o utilizeaz i, de asemenea, fiecare resurs are asociat o coad de ateptare cu toate procesele care au fcut cerere de utilizare a resursei. De obicei, sistemele de operare implementeaz, pentru fiecare din etapele de mai sus, apeluri sistem sau semafoare.

4.2.2. Condiii necesare pentru apariia interblocrii

n anul 1971, Cofman a identificat patru condiii necesare care, dac sunt ndeplinite simultan, pot conduce la apariia interblocrii. Aceste condiii sunt:

50

Ri

Ri

P2

2

2

Sisteme de operarea)Excluderea mutual. Existena excluderii mutuale

presupune c un proces a obinut resursa i exist o coad de ateptare a altor procese la aceeai resurs.

b)Ocupare i ateptare. Exist cel puin un proces care a obinut resursa dar care ateapt i alte resurse suplimentare care, la rndul lor, sunt ocupate de alte resurse.

c)Imposibilitatea achiziionrii forate. Un proces nu poate achiziiona forat o resurs aferent altui proces dect dup eliberarea resursei de ctre acel proces.

d)Ateptare circular. Exist un ir de procese P1, P2, Pn, toate n ateptare, n aa fel nct P1 ateapt eliberarea resurse de ctre P2, P2 ateapt eliberarea resursei de ctre P3.Pn ateapt eliberarea resursei de ctre P1.

P1P2P3Pn-1Pn

4.2.3. Graful de alocare a resurselor

Pentru descrierea strii de interblocare este folosit un graf orientat, numit graful de alocare a resurselor. Nodurile grafului sunt alctuite din procese i resurse. Vom nota procesele cu P i resursele cu R.

Resursa cu indice i : Procesul cu indice j :

Arcele grafului sunt orientate i sunt de dou feluri:a) arce cerere, care reprezint faptul c procesul Pj fcut

o cerere de alocare a resursei Ri i ateapt dobndirea ei;

51

Ri

P

j

P

j R

i

Ri

P2

2

2

R

1

R

2

P2

2

2

Sorin Adrian Ciureanuc) arce alocare, care reprezint faptul c procesului Pj i-a

fost alocat resursa Ri .

Cea mai important aplicaie a acestui graf este legat de detecia strii de interblocare. Pentru un graf alctuit numai din resurse simple, existena unei bucle n graf nseamn c n sistem a aprut o interblocare. De exemplu, n graful urmtor.

Fig.4.2. Graf de resurse.

n graful de mai sus, procesului P1 i este alocat resursa R1 i procesului P2 resursa R2 . Procesul P1 a fcut o cerere de alocare a resursei R2 deinut de P2 iar P2 a fcut o cerere de alocare a resursei R1 deinut de P1 . Este o situaie clar de interblocare. n graful din figura 4.2. aceast interblocare este vizibil prin existena buclei.

De menionat c pentru grafurile cu resurse multiple existena buclei nu nseamn o situaie de interblocare.

De exemplu, n cazul din figura 4.3., existena buclei nu nseamn interblocare.

52

P

j R

i

P1

R1

R2

P2

2

2

R

1

R

2

P2

2

2

Sisteme de operare

Fig. 4.3. Graf fr situaie de interblocare.

4.2.4. Rezolvarea problemei interblocrii

Exist dou tipuri de metode pentru rezolvarea interblocrii:

a) metod n care nu i se permite niciodat sistemului de operare s intre n interblocare;

b) metod n care se permite sistemului de operare s intre n interblocare i apoi se ncearc scoaterea sa din aceast stare

n cadrul primei metode se face prevenirea sau evitarea interblocrii.

n cadrul celei de-a doua metode se utilizeaz un mecanism de detecie a interblocrii i revenire din aceast stare.

4.2.4.1. Prevenirea interblocrii

Pentru a putea preveni interblocarea este suficient ca una din condiiile de apariie a acesteia s nu fie ndeplinit. S vedem cum poate fi mpiedecat ndeplinirea fiecrei din cele patru condiii.

a) Excluderea mutual Pentru o resurs nepartajabil nu este posibil prevenirea

interblocrii prin nendeplinirea condiiei de excludere mutual.b) Ocupare i ateptare

53

P1

R

1

R

2

P2

2

2

Sorin Adrian CiureanuPentru nendeplinirea condiiei de ocupare i ateptare sunt

posibile dou protocoale:-un protocol n care fiecare proces i poate ncepe execuia

numai dup ce i-a achiziionat toate resursele necesare;-un protocol n care unui proces nu i se permite s

achiziioneze dect o resurs, achiziionarea resurselor suplimentare fcndu-se cu eliberarea resurselor deja angajate.

Dei prin ambele protocoale se asigur nendeplinirea condiiei de ateptare i ateptare, totui ele prezint dou mari dezavantaje:

-utilizarea resurselor este destul de redus, n sensul c timpul ct o resurs este alocat unui proces i neutilizat este foarte mare;

-apare un proces de nfometare, deoarece un proces nu poate s atepte la infinit alocarea unei resurse.

c) Imposibilitatea achiziionrii forate Nendeplinirea acestei condiii nseamn de fapt ca un

proces s poat lua o resurs alocat altui proces n orice moment. Desigur, aceast achiziionare forat a resurselor unui alt proces nu trebuie fcut haotic, ci n cadrul unui protocol de achiziionare forat. Un exemplu de astfel de protocol este urmtorul : un proces care i achiziioneaz resurse n vederea execuiei va putea lua forat resurse de la alt proces numai dac procesul respectiv este n ateptare. Acest protocol se aplic frecvent n cazul resurselor a cror stare poate fi uor salvat i refcut (ex. registrele procesorului, spaiul de memorie).

d) Ateptare circular Un algoritm simplu pentru eliminarea ateptrii circulare

este dat n continuare.Se creeaz o coresponden biunivoc ntre toate resursele

nepartajabile ale sistemului i muimea numerelor naturale, astfel nct fiecare resurs este identificat orintr-un numr natural. De exemplu:

hard disc .1

54

Sisteme de operareCD ROM.2imprimant..3MODEM.4scaner..5Apoi, un proces poate cere resursa cu numr de ordine k ,

cu condiia ca s elibereze toate resursele cu indice mai mare dect k, adic k+1, k+2,.n. n felul acesta se elimin posibilitatea de ateptare circular.

n concluzie, pentru prevenirea interblocrii se utilizeaz algoritmi care impun ca cel puin una din condiiile necesare s nu fie ndeplinite. Aceti algoritmi acioneaz prin stabilirea unor restricii asupra modului n care se pot formula cererile de acces. Principalele dezavantaje ale acestei metode sunt gradul redus de utilizare a resurselor i timpul mare de ateptare a unui proces pentru o resurs.

4.2.4.2. Evitarea interblocrii

Dac pentru prevenirea interblocrii se folosesc restricii asupra modurilor de formulare a cererilor pentru resurse, n evitarea interblocrii se utilizeaz informaii suplimentare referitoare la modul n care se face cererea de acces. Algoritmii de evitare difer prin tipul i cantitatea acestor informaii.

Se definesc dou noiuni: stare sigur i secven sigur.n cazul acestor algoritmi, fiecare proces trebuie s declare

numrul maxim de resurse de fiecare tip de care ar putea avea nevoie. Algoritmul examineaz mereu starea alocrii resurselor pentru a avea certitudinea c nu va exista ateptare circular.

Secven sigurFie un ir de procese P1 , P2 , ..Pn exact n aceast

ordine. Spunem c aceast secven este sigur dac pentru orice proces Pi cu (1 i n) s-ar cere numrul maxim de resurse, declarat iniial, atunci diferena intre numrul maxim de resurse i numrul de resurse al procesului n acel moment nu depete

55

Sorin Adrian Ciureanunumrul resurselor obinute din nsumarea resurselor disponibile cu resursele eliberate de procesele Pj cu j i. Dac nu se ndeplinete aceast condiie, atunci secvena este nesigur.

Stare sigurSistemul este ntr-o stare sigur dac conine cel puin o

secven sigur. De exemplu, fie secvena de procese:P1 P2 P3 P4 P5

P1 P2 P3 P4 P5Maxim resurse cerute 10 15 20 25 30Cerere iniial 5 5 10 10 20

Total resurse = 60Resurse disponibile = 60-5-5-10-10-20 = 10S analizm secvena P1 P2 P3 P4 P5 .

P1 la cerere maxim de resurse ar avea nevoie de 10-5 = 5 resurse < 10 resurse disponibileP2 15-5 = 10 resurse < 5(eliberate de P1 ) + 10(disponibile)P3 20-10=10 resurse < 5(P1 ) + 5(P2) +10(disponibile)P4 25-10=15 resurse < 5(P1) + 5(P2) + 10(P3) + 10 (disponibile)P5 30-20=10 resurse < 5(P1)+5(P2)+10(P3)+10(P4)+10(dispon.)Deci aceast secven este sigur.

S analizm secvena P4 P5 P1 P2 P3 .P4 25-10 = 15 > 10 (resurse disponibile) secven nesigur.

a) Algoritmul bancheruluiUn algoritm clasic de evitare a interblocrii, bazat pe

noiunea de secven sigur, este algoritmul bancherului. Se numete aa deoarece poate fi folosit n sistemul bancar la plata unor sume ctre diferii clieni ai bncii, plat care trebuie s lase mereu banii ntr-o stare sigur.

Pentru a putea aplica acest algoritm trebuie s se cunoasc de la nceput numrul maxim de resurse cerute de fiecare proces. Apoi, la fiecare cerere a unor resurse noi, se aplic algoritmul pentru a vedea dac aceast cerere duce la o stare sigur sau nesigur. Dac e sigur, cererea este acceptat, dac nu e sigur, cererea nu este acceptat i procesul rmne n ateptare.

56

Sisteme de operareStructurile de date folosite de algoritm sunt:n - numrul de procese din sistemm - numrul de tipuri resurs-disponibil[m] un vector care indic numrul de

resurse disponibile pentru fiecare tip n parte;-maxim [n][m] o matrice care arat numrul maxim de

cereri ce pot fi formulate de ctre fiecare proces; -alocare[n][m]- o matrice care arat numrul de resurse

din fiecare tip de resurse care este alocat fiecrui proces;-necesar[n][m] o matrice care arat numrul de

resurse care ar mai putea fi necesare fiecrui proces.Dac necesar[i][j] = t , atunci procesul Pi ar mai avea nevoie de t elemente din resursa rj .Avem relaia:

necesar[i][j] = maxim[i][j] alocare[i][j]

-cerere[n][m]matricea cererilor formulate de un procesDac cerere[i][j]= t, atunci procesul Pi dorete t elemente din resursa rj .

Algoritmul banchetului are urmtorii pai:

Pas 1 Procesul Pi formuleaz o cerere de resurse. Dac linia i din matricea cerere este mai mare dect linia i din matricea necesar, atunci este eroare, deci nu se trece la pasul 2.Precizm c V1[n] < V2[n] , dac V1[i] < V2[i] pentru oricare i=1.nif cerere[i][x]

Sorin Adrian CiureanuPas 3

Se simuleaz alocarea resurselor cerute de procesul Pi , strile modificndu-se astfel:disponibil[x]=disponibil[x]cerere]i][x];alocare[i][x]=alocare[i][x]+cerere[i][x]; x=1.mnecesar[i][x]=necesar[i][x]-cerere[i][x];

Pas 4n acest moment se testeaz dac noua stare este sigur sau nu. n acest scop se mai utilizeaz doi vectori: lucru[m] terminat[n]

Subpasul 1Se iniializeaz aceti vectori astfel:lucru[i]=disponibil[i]; terminat[i]=falspentru i=1,2,3..nSubpasul 2Se caut o valoare i astfel nct:terminat[i]=fals;necesar[i][x]

Sisteme de operareb) Folosirea grafului de alocare a resurselorO alt metod pentru determinarea unei stri sigure este

folosirea grafului de alocare a resurselor. Fa de graful prezentat anterior, elementul nou este arcul revendicare. Acest arc arat c este posibil ca procesul Pi s revendice n viitor resursa Rj . Ca mod grafic de reprezentare , el este trasat cu linie ntrerupt. Cnd procesul Pi cere resursa Rj , arcul revendicare (PiRj) se transform n arc cerere (PiRj). Cnd resursa Rj este eliberat de procesul Pj ,arcul alocare (PiRj) este transformat n arc revendicare (PiRj). Pentru a determina strile nesigure, se caut n graf bucle n care intr arcuri revendicare. O astfel de bucl reprezint o stare nesigur. Exemplu:

Fig. 4.4. Graf de alocare cu arcuri revendicative.

n graful de mai sus, procesului P1 i este alocat resursa R1, iar procesului P2 i este alocat resursa R2 . n acelai timp procesul P1 poate s cear n viitor resursa R2 ceea ce n graf se concretizeaz prin arcul revendicare (P1R2). La fel, Procesul P2 poate revendica resursa R1 prin arcul (P2R1). Se observ c exist o bucl (P1R2P2R1), ceea ce face ca aceste revendicri s conduc la o stare nesigur.

4.2.4.3.Detectarea interblocrii i revenirea din eaAtunci cnd, din diverse motive, nu se pot aplica algoritmii

de prevenire i evitare a interblocrii, se intr n aceast stare. n acest caz trebuie s se execute alte dou tipuri de algoritmi:

59

P1

R1

R2

P2

2 2

P1

2

2

P2

2

2

P3

2

2

P4

2

2

P5

2

2

R1

R2

R3

R4

R5

P1

2

2

P2

2

2

P3

2

2

P4

2

2

P5

2

2

Sorin Adrian Ciureanu-algoritmi de detecie care s informeze sistemul asupra

momentului n care s-a ajuns la aceast stare;-algoritmi de revenire din starea de interblocare.c)Detecia interblocriin acest scop se folosesc doi algoritmi:-un algoritm foarte asemntor cu algoritmul bancherului;-un graf de alocare a resurselor de tip WAIT FOR.Deoarece algoritmul bancherului a fost discutat n

amnunt, ne vom ocupa doar de graful WAIT FOR. Acest graf se obine din graful de alocare a resurselor prin eliminarea nodurilor de tip resurs (Rj) i contopirea arcelor corespunztoare. n acest caz, un arc (PiPj) arat c Pi ateapt ca Pj s elibereze resursa care i este necesar.

Fig. 4.5.Graf de alocare a resurselor.

n acest caz, existena buclei nu nseamn interblocare.

Fig.4.6.Graf WAIT FOR.

Algoritmul WAIT FOR se poate aplica numai pentru resurse simple.

60

P1

2

2

P2

2

2

P3

2

2

P4

2

2

P5

2

2

R1

R2

R3

R4

R5

P1

2

2

P2

2

2

P3

2

2

P4

2

2

P5

2

2

Sisteme de operareSe observ c bucla existent n graful de alocare a

resurselor este mai bine pus n eviden n graful WAIT FOR. Dar avantajul principal al utilizrii grafului WAIT FOR const n costurile mai mici pentru detecia unei bucle, deci a interblocrii.

Indiferent de tipul algoritmului de detecie a interblocrii, se pune problema ct de des trebuie s fie acesta apelat. Exist, n general, dou modaliti de apelare:

a)apelarea algoritmului ori de cte ori se formuleaz o cerere de resurse;

b)apelarea algoritmului la intervale regulate de timp.Prima modalitate detecteaz rapid interblocarea dar

presupune un substanial consum suplimentar de timp de calcul.n a doua modalitate , se alege un interval de timp la care

se apeleaz algoritmul de detectare. Desigur, un interval scurt va introduce costuri suplimentare iar la un interval lung este posibil ca starea de interblocare s fie detectat foarte trziu, cu consecine nedorite n funcionarea sistemului.

d) Revenirea din interblocareRevenirea din interblocare se poate face n dou moduri:-manual, fcut de ctre operatorul sistemului;-automat, executat de anumite programe ale sistemului de

operare.n general, exist dou metode de revenire din starea de

interblocare:1)-Prin dispariia ateptrii circulare; n acest caz se

foreaz terminarea unor procese.2)-Prin negarea achiziiei forate; n acest caz procesele

pot s achiziioneze resurse de la alte procese.1)Folosirea metodei de dispariie a ateptrii circulare are

dou forme:-ncheierea forat a tuturor proceselor interblocate; n

acest fel se revine sigur din starea de interblocare dar se pierd toate rezultatele fiecrui proces implicat n interblocare.

61

Sorin Adrian Ciureanu-ncheierea forat a cte unui singur proces implicat n

interblocare; n acest caz se ncheie forat un proces i apoi se apeleaz algoritmul de detecie a interblocrii pentru a vedea dac mai persist starea de interblocare; dac da, se ncheie forat alt proces i se apeleaz di nou algoritmul de detecie, operaia continund pn la dispariia strii de interblocare. Avantajul fa de prima metod este c nu se pierd rezultatele de la toate procesele. Dezavantajul const n timpul suplimentar, pentru c, dup terminarea forat a unui proces, trebuie apelat algoritmul de detecie.

O alt problem a acestei metode este determinarea procesului sau proceselor care trebuiesc terminate forat. Pot intra n discuie mai muli factori:

-prioritatea procesului;-numrul resurselor care ar mai fi necesare procesului pentru a-i ncheia normal execuia;-numrul resurselor care au fost deja folosite de un proces;-timpul necesar pn la terminarea normal a procesului.Din enumerarea acestor factori, se observ c este necesar

un algoritm pentru alegerea procesului sau proceselor care vor fi terminate forat. De obicei se alege factorul ce necesit un timp minim. Cel mai frecvent se utilizeaz alegerea dup prioritate, cu att mai mult cu ct prioritatea proceselor este deja calculat din algoritmii de planificare a procesorului.

2)Permiterea achiziionrii forate a resurselor de la procese este a doua metod de revenire din interblocare. Problemele care apar n acest caz sunt:

-alegerea victimelor, ceea ce nseamn i selectarea resurselor care vor fi achiziionate forat;

-continuarea procesului cruia i s-au preluat forat resursele;

-prevenirea nfometrii, adic evitarea faptului ca un acelai proces s fie ales mereu victim.

62

Sisteme de operare4.2.4.4. Rezolvarea interblocrii n practic

De obicei, n mod practic, interblocarea poate fi tratat n dou moduri:

a)-prin ignorarea ei;b)-printr-o metod