29

Capitolul 3 Gestiunea proceselor si a procesoarelorCapitolul de fata abordeaza o serie de probleme legate de planificarea job-urilor si a proceselor (in sisteme mono- si multi-procesor), precum si de sincronizare intre procese. Sint ilustrate si citeva solutii de rezolvare a blocajului reciproc intre mai multe procese. Capitolul se incheie cu descrierea mecanismului de planificare de procese in Unix. Sint punctate deasemenea si principalele posibilitati de sincronizare si comunicare intre procese. Notiuni de baza Planificarea de job-uri Planificarea de procese. Comparatie intre sistemele de operare in timp partajat si sistemele de operare in timp real Interactiunea si sincronizarea proceselor. Mecanismul Producator-Consumator Resurse. Deadlock Sisteme multiprocesor Gestiunea proceselor in Unix. Sincronizare. Comunicatie job, proces, procesor, SO in timp partajat, SO in timp real, interactiunea si sincronizarea proceselor, mecanismul Producator-Consumator, resurse, deadlock, sisteme multiprocesor

Obiective

Continut

Cuvinte cheie:

Modul1 Notiuni de bazaIn continuare vor fi listate cite notiuni fundamentale referitoare la terminologia folosita si la notiunile conexe fenomenelor descrise: Program= un ansamblu ordonat de instructiuni; Instructiune= o operatie elementara executata de catre procesor, indivizibila (in sensul ca executia ei de catre un procesor nu poate fi intrerupta); Proces= o entitate dinamica reprezentind un program in stare de executie, alcatuita din: zone de cod, cum ar fi: programul principal, procedurile sau functiile; zone de date: zone care contin declaratiile si definitiile datelor folosite; resurse alocate procesului, care, desigur, sint variabile in timp; informatii utile pentru evaluarea starii procesului - de exemplu, numele procesului, starea sa, continutul registrilor procesorului si altele. Toate acestea pot fi privite ca programul propriu-zis alaturi de contextul sau de lucru (toate informatiile externe programului necesare evolutiei procesului corespunzator).

Vector de stare - pentru a putea administra procesele existente, SO trebuie sa pastreze o imagine a fiecarui proces (care sa contina informatiile de mai sus referitoare la procesul respectie), in orice moment de timp - aceasta imagine se numeste vector de stare al procesului. Starile unui proces - principalele stari in care se poate afla un proces sint: pregatit pentru executie, in executie sau in asteptare.

30

Fig.14. Starile principale ale unui proces intr-un SC Un proces se afla in starea pregatit pentru executie (ready) cind are alocate toate resursele, mai putin procesorul. El poate parasi acesta stare numai atunci cind i se aloca si procesorul (eliberat intre timp), moment in care trece in starea in executie (running). Din aceasta stare, un proces se poate intoarce in starea pregatit pentru executie la prelevarea fortata a procesorului. Deasemenea, el poate intra in starea in asteptare (blocked) daca este nevoit sa astepte producerea unui eveniment cum ar fi: sfirsitul unei operatii de I/O, aducerea unei pagini de pe disc, eliberarea unor resurse de care are nevoie etc. Ar mai trebui metionat ca atit timp cit procesul se afla in aceasta stare, i se pot dealoca unele resurse spre a fi date altor procese! Administrarea proceselor la nivelul SO presupune:

pastrarea unei evidente a starii curente a tuturor proceselor din sistem; schimbarea starii proceselor ori de cite ori este nevoie.

Ea este sustinuta de 3 liste existente la nivelul sistemului:

lista proceselor active (in rulare); lista proceselor blocate (in asteptare); lista proceselor intrerupte (pregatite pentru rulare).

Fig.15. Listele cu starile proceselor Crearea unui proces se face in timpul executiei unei lucrari si consta in constructia unui vector de stare si initializarea lui; inregistrarea vectorului de stare intabela de procese si in lista corespunzatoare;

Un proces este creat la initiativa altui proces utilizator sau sistem, numit proces tata. Toate procesele din sistem formeaza o arborescenta cu o radacina unica. Distrugerea unui proces consta in:

stergerea tuturor informatiilor despre el; eliberarea tuturor resurselor alocate lui.

Ea se poate face:

la sfirsitul executiei sale (autodistrugere);

31

la initiativa altui proces utilizator sau sistem (terminare normala) - de exemplu, in cazul in care el functioneaza defectuos.

In momentul distrugerii unui proces, creatorul sau este acela care va trebuie sa distruga si toate procesele sale descendente. Gestiunea proceselor se face pe 2 niveluri: pe termen mediu (planificarea de job-uri sau lucrari): consta in alegerea dintre toate job-urile prezentate a aceluia pentru care se va crea un proces; ea are prioritate mica la nivelul sistemului; pe termen scurt (planificarea de procese): care consta in a da de lucru procesorului ori de cite ori este liber; ea are prioritate mare.

32

Modul2 - Planificarea de job-uriIn acest modul vor fi prezentate mai intii citeva consideratii legate de functiile componentei de gestiune a job-urilor, in continuare fiind descrisi citiva algoritmi de mono-programare. In final, este prezentat si un algoritm de multi-programare. Sa incepem cu consideratiile privind sarcinile subsitemului de administrare a job-urilor: SR. Pentru a tine gestiunea job-urilor, la nivelul SO, exista cite un bloc de control al fiecarui job (JCB - Job Control Block) - toate aceste JCB-uri se afla in tabela de job-uri a sistemului. Un JCB contine identificatorul job-ului, timpul estimativ de executie, starea in care se gaseste acesta, memoria ocupata precum si prioritatea sa la nivelul sistemului. PA. Politica implementata de planificator se bazeaza pe:

disponibilitatea resurselor; cost ridicat pentru servicii prioritare; durata job-ului (se acorda, de exemplu, prioritate mare job-urilor scurte); echilibrul sistemului (intreteserea job-urilor limitate UCP cu cele limitate I/O; garantarea serviciilor (SO trebuie sa asigure executia oricarui job); garantarea termenelor (SO trebuie sa ruleze orice job intr-un anumit timp; dealtfel prioritatea job-urilor trebuie sa creasca prin imbatrinire).

Algoritmi de planificare de job-uri Pentru a intelege mai bine cum functioneaza algoritmii prezentati, ei vor fi descrisi pe un exemplu concret. Fie asadar urmatorul exemplu: presupunem ca vor fi supuse SO, spre executie, 3 job-uri, caracterizate de urmatorii timpi de sosire, respectiv executie: Numar 1 2 3 Nota Tsosire 10 10.10 10.25 Trulare 2 1 0.25

Timpii se dau in fractiuni de ore.

Daca presupunem ca sistemul lucreaza in mono-programare, sub diverse politici de planificare avem, respectiv, urmatoarele rezultate: FIFO (First In First Out) Numar Tsosire Tinceput 1 10 10 2 10.10 12 3 10.25 13 Nota Tterminare 12 13 13.25 Traspuns 2 2.9 3

Traspuns= Tterminare-Tsosire.

33

SXFS (Shortest eXecution First Service) Numar Tsosire Tinceput Tterminare 1 10 10 12 2 10.10 12.25 13.25 3 10.25 12 12.25

Traspuns 2 3.15 2

Daca se aplica o varianta a tehnicii de mai sus, in sensul ca sint asteptate toate job-urile inainte de alua o decizie, se obtin urmatoarele rezultate: SXFS(2) Numar 1 2 3 Tsosire 10 10.10 10.25 Tinceput 11.5 10.5 10.25 Tterminare 13.5 11.5 10.5 Traspuns 3.5 1.4 0.25

Pentru a putea evalua diversii algoritmi folositi, s-a calculat initial indicatorul numit timp de raspuns - o analiza mai profunda a evolutiei sale, vizavi de comportamentul general al sistemului, a condus la concluzia ca el nu descrie corect functionarea sistemului. Ca urmare s-a trecut la calcularea unui al doilea indicator, numit timp de raspuns ponderat, care se calculeaza astfel: wi=Traspuns/Trulare_in_monoprogramare= =(Tterminare - Tsosire)/(Tterminare - Tinceput). Pentru exemplul considerat valorile pentru timpul de raspuns ponderat sint: wi/FIFO 1 2.9 12 wi/SXFS(1) 1 3.15 8n

wi/SXFS(2) 1.75 1.4 1n

In continuare, pentru a ilustra functionarea sistemului, s-au calculat niste medii si anume: T= i =1

Traspunsi n

, respectiv w= i =1 n

wi

.

Pentru exemplul de mai sus s-au obtinut valorile: Strategia FIFO SXFS(1) SXFS(2) T 2.63 2.38 1.72 w 5.3 4.5 1.38

In cazul acestui exemplu, se observa ca atit T cit si w scad, ceea ce indica imbunatatirea performantelor din punctul de vedere al sistemului.

34

Sa consideram acum un alt exemplu, pe care sa-l analizam atit in mono-programare folosind algoritmul FIFO, cit si in multi-programare. Mono-programare/FIFO: Numar Tsosire Trulare 1 10 0.3 2 10.2 0.5 3 10.4 0.1 4 10.5 0.4 5 10.8 0.1 Tinceput 10 10.3 10.8 10.9 11.3 Tterminare 10.3 10.8 10.9 11.3 11.4 Traspuns 0.3 0.6 0.5 0.8 0.6 Traspuns_ponderat 1 1.2 5 2 6

Fig.16. Monoprogramare vs. multiprogramare Multi-programare Numar Tsosire 1 10 2 10.2 3 10.4 4 10.5 5 10.8 Trulare 0.3 0.5 0.1 0.4 0.1 Tinceput 10 10.2 10.5 10.6 10.9 Tterminare 10.4 11.3 10.6 11.4 11.0 Traspuns 0.4 1.2 0.2 0.9 0.3 Traspuns_ponderat 1.33 2.4 2 2.25 3

35

Observati e

Pentru multi-programare, s-a presupus ca: operatiile de I/O nu se suprapun cu cele de calcul; resursele sint nelimitate; multi-programarea se face FIFO (procesele primesc procesorul pentru o cuanta dt dupa care se asaza din nou la coada la el): Desigur ca in analizarea unei situatii reale trebuie sa se tina cont de toate aceste elemente!

Daca se calculeaza acum cei doi indicatori T si w pentru ambele situatii se obtin valorile: Strategie Mono/FIFO Multi/FIFO Observati e T 0.56 0.6 w 3.04 2.19

Se observa aici ca T fluctueaza, in sensul ca el creste, desi performantele globale ale sistemului au crescut - acesta este motivul concret petru care s-a trecut la folosirea lui w ca indicator pentru evolutia sistemului.

Modul3 Planificarea de proceseIn continuare sint considerate citeva aspecte referitoare la sarcinile modulului de gestiune a proceselor: SR. In vederea gestionarii proceselor, SO va mentine o structura de date asociata fiecarui proces numita bloc de control al procesului (Proces Control Block) care este totuna cu vectorul de stare al procesului. Diferitele stari in care se gasesc procesele sint inlantuite in listele corespunzatoare, inserarea facindu-se conform politicii de alocare utilizate (listele sint ordonate conform acestei politici). PA. Politici de alocare posibile pentru procese sint: Round-Robin:

procesele pregatite pentru executie sint organizate intr-o coada la procesor - cind acesta se elibereaza, primul proces din coada va primi procesorul pentru o cuanta de timp dt; daca dupa expirarea cuantei de timp, procesul inca nu s-a terminat, el va fi trecut din nou in coada, in ultima pozitie;

Fig.17. Round-Robin simplu Round-Robin

limitat: procesele nou venite sint introduse in coada principala de procese care asteapta la UCP numai pentru k treceri - daca nu se termina in k treceri, ele vor fi trecute intr-o coada secundara, de unde se iau cind nu mai este nici-un proces in coada principala; Round-Robin pe mai multe niveluri, cu reactie inversa: procesele nou venite vor fi inserate in prima coada - daca ele nu se termina in k1 cuante, ele vor fi trecute in coada

36

a 2-a samd. Cind in coada intii nu mai este nici-un proces, se va trece la aplicarea unui Round-Robin simplu in coada a 2-a, samd. Daca un anumit timp tau nu s-a facut nici-o planificare in coada i , primul proces din aceasta coada este promovat ultimul in coada i-1 (imbatrinirea proceselor le creste prioritatea);

Fig.18. Round-Robin pe mai multe niveluri Round-Robin

invers cu restul ramas din cuanta de timp: procesul curent primeste procesorul pentru o cuanta de timp dt - daca in timpul acesteia el face o operatie de I/O, atunci i se va lua procesorul (ca si in cazul Round-Robin-ului simplu), numai ca nu va fi inserat la sfirsitul cozii, ci intr-o pozitie invers proportionala cu partea ramasa din cuanta de timp - adica, daca i-a ramas , de exemplu, 75% din cuanta de timp, el va fi inserat la 25% (din lungimea cozii) "distanta" de procesor;

Fig.19. Round-Robin invers cu restul de timp ramas dupa

prioritati, care poti sa fie fixe sau variabile in timp (functie de resurse si de comportamentul job-ului); conforme cu echilibrul sistemului (cuantificat ca gradul de utilizare al UCP si al EP); politici favorizind procesele interactive (pentru impresia lasata utilizatorului, desigur :o))); politici corespunzatoare proprietatilor job-ului caruia ii apartine procesul. De obicei, politica de alocare a unui SO este reprezentata cu ajutorul unei diagrame de stare. Un exemplu in acest sens se afla in figura urmatoare:

Fig.20. Exemplu de diagrama de stare O incercare de citire a acestei diagrame ne arata ca SO folosit: favorizeaza

procesele interactive (dind prioritate mare proceselor blocate, care asteapta o intrare de la terminal, la terminarea operatiei de intrare de la terminal); incearca sa faca transparenta pentru utilizator lipsa paginii (dind prioritate mare proceselor la iesirea din starea "blocat pentru lipsa de pagina"); incearca sa realizeze echilibrul sistemului dind prioritate mica si cuante mari joburilor limitate UCP. Observati e In ceea ce priveste politicile de planificare pentru executie, exista si in acest caz o puternica formalizare cu ajutorului unui model matematic (cunoscut sub numele de modelul Markov).

37

Comparatie intre SO in timp partajat si SO in timp real Din punct de vedere al planificarii proceselor pentru executie, SO pot fi, in principal, in timp partajat (time-sharing) sau in timp real (real time). In continuare se va face o scurta comparatie a celor doua clase de sisteme, dupa diverse criterii de comparatie:1.

Planificarea pentru executie se face, pentru ambele clase de sisteme (timp real - TR, timp partajat - TP), functie de prioritati, dar prioritatile sint: TR: fixate de utilizator, rolul SO in modificarea lor fiind nul (evident, se va acorda prioritate mare proceselor al caror timp de raspuns este critic - de exemplu, cresterea presiunii peste o anumita limita intr-un recipient care poate exploda in cazul in care aceasta nu este redusa rapid); TP: calculate dinamic de catre sistem, in functie de obiectivele sale; Momentul planificarii este stabilit diferit astfel: TR: planificarea pentru executie este declansata de evenimente (din acest motiv aceste sisteme sint cunoscute sub numele de SO conduse de evenimente; TP: in acest caz, ceasul sistemului este acela care declanseaza planificarea pentru executie, fie la expirarea cuantei de timp, fie la realizarea unei operatii de I/O; Alocarea resurselor se face, indiferent de tipul SO, astfel incit performantele sa fie optimizate, insa elementul de referinta este diferit in functie de felul SO, astfel: TR: optimizarea se face in raport cu un utilizator (proces) individual; TP: optimizarea este globala, la nivelul intregului SO;

2.

3.

4. Prelevarea fortata functioneaza in ambele sisteme, insa ea actioneaza diferit astfel:a.

Prelevarea fortata a procesorului se face: TR: la aparitia unui proces de prioritate mai mare; TP: la sfirsitul cuantei alocate sau la realizarea unei operatii de I/O; Prelevarea fortata a celorlalte resurse se face diferit in cele doua feluri de SO, dupa cum urmeaza: TR: deoarece in aceste sisteme viteza de acaparare a resurselor este importanta, un proces care pierde procesorul nu va pierde si celelate resurse (deoarece el ar trebui sa lupte pentru mai multe ca sa intre din nou in executie; TP: viteza de alocare a resurselor nefiind critica din punctul de vedere al sistemului, un proces care pierde procesorul va pierde si celelalte resurse;

b.

5. Viteza operatiilor de I/O:

38

TR: este importanta in acest caz, ea trebuind sa fie mare. Pentru a se realiza acest obiectiv, operatiile de I/O vor fi declansate asincron fata de task-ul care le solicita (adica ele vor fi lansat anticipat, astfel ca atunci cind ele sint necesare pot fi gasite deja in buffer-ele SO; TP: nu este critica din punctul de vedere al SO;

6. Protectia este importanta in ambele clase de sisteme, insa:

TR: in acest caz, ea devine esentiala, deoarece procesele cu prioritate mare pot acapara resurse pe care sa nu le mai elibereze niciodata! TP: prelevarea fortata reuseste sa o asigure integral in aceast tip de SO.

Modul4 - Interactiunea si sincronizarea proceselorIn cadrul unui SC interactiunea proceselor are loc in doua directii: concurenta pentru acapararea resurselor; cooperarea pentru realizarea unui scop comun. O notiune strins legata de cea de interactiune a proceselor este sincronizarea. Aceasta consta in controlul vitezei cu care se desfasoara procesele, adica in oprirea unui anumit proces asteptind ca altul sa ajunga intr-un anumit punct. In principiu problema sincronizarii se pune in doua situatii posibile: privind folosirea resurselor: de exemplu, fie un sistem in care, in memoria interna, se afla incarcate doua procese Pr1 si Pr2, care, fiecare, va avea nevoie de imprimanta la un moment dat, astfel: Pr1 cere imprimanta, care libera fiind, ii este acordata; Pr2 solicita ulterior si el imprimanta si va fi blocat pina la eliberarea ei. In competitia pentru acaparea resurselor (in cazul acestui exemplu, imprimanta), SO trebuie sa marcheze 4 momente importante: cererea/asteptarea/utilizarea/eliberarea resursei; referitor la gestiunea mesajelor: si in acest caz, mecanismul de utilizare a "resursei" (in acest caz buffer-ul prin care are loc transferul mesajului de la un proces la celalalt) este asemanator, marcind cele patru momente precizate mai sus.

Putem conchide ca cele doua tipuri de interactiuni nu sint fundamental diferite, in sensul ca, in primul caz, imprimanta este caracterizata de o variabila booleana care descrie starea ei (libera sau ocupata), iar in cel de-al doilea, situatia buffer-uului intermediar este gestionata tot cu ajutorul unei astfel de variabile. In concluzie, putem spuna ca interactiunea proceselor poate fi vazuta ca abilitatea acestora de a utiliza in comun variabile (la care, evident, mai multe procese pot face acces concurent). In continuare vor fi prezentate diverse solutii de "modelare" acestei interactiuni in sistemele de operare. Pentru inceput sa presupunem cazul unui sistem multiprogramare cu planificare omogena, in care exista mai multe procesoare disponibile la un moment dat, dupa cum se poate vedea in figura urmatoare:

39

Fig.21. Sistem multiprocesor cu planificare omogena In momentul in care unul dintre procesoare se va elibera, fie el Pi, el va realiza urmatoarele actiuni: . salveaza starea procesului rulat anterior; . noteaza valoarea lui "n"; . incrementeaza valoarea lui "n"; . marcheaza procesul "n" ca fiind "in rulare", ca sa nu-l mai executa si alte procesoare; . incarca registrii procesului "n" si-l executa.

Sa ne imaginam acum ce se va intimpla daca doua procesoare (fie ele Pi si Pj) se elibereaza simultan - in acest caz, va avea loc o intretesere a operatiilor astfel: Pi Pj Pi Pj ... Pi Pj Evident o astfel de functionare este de nedorit, deoarece acelasi proces va fi rulat de doua ori pe doua procesoare diferite. Devine evident ca trebuie realizat un mecanism de sincronizare care sa preintimpine astfel de situatii. Practic trebuie asigurata excluderea mutuala privind accesul la anumite variabile, adica, daca un proces acceseaza variabila respectiva, nici-un altul nu va putea sa faca acelasi lucru. Prima solutie de implementare a excluderii mutuale la nivelul SO a fost "asteptarea ocupata". In acest caz, daca un proces face acces la anumite structuri de date, toate celelalte procese vor fi oprite s-o faca, ele ciclind pina la eliberarea structurilor de date respective. Este clar ca o astfel de rezolvare a problemei este ineficienta, deoarece ciclarea presupune ocuparea procesorului. Concret, asteptarea ocupata se realizeaza prin "zavorirea" structurilor de date utilizate in comun, adica prin asocierea cu fiecare astfel de structura a unei variabile booleene de tip zavor, fie ea z - daca z=0 atunci inseamna ca resursa (careia ii este asociata structura de date respectiva) este libera, iar daca z=1 inseamna ca este ocupata. Algoritmul de functionare a zavorului este urmatorul:

Fig.22. Algoritm de zavorire

40

Pentru a evita functionari defectuoase de tipul celei din exemplul precedent, se impune ca operatia de testare si setare a zavorului (TAS) sa fie neintreruptibila. O a doua solutie de realizare a excluderii mutuale, care evita asteptarea ocupata, s-au introdus in nucleul SO doua proceduri: WAIT(z): daca zavorul z este blocat atunci SO blocheaza procesul si-l pune in coada la zavorul z

SIGNAL(z): daca resursa se elibereaza atunci SO extrage primul proces din coada de asteptare si-i aloca resursa Astfel, secventele de lucru cu zavorul devin: LOCK(z): *examinare z *setare z1 daca zinitial=1 atunci WAIT(z) UNLOCK(z): *resetare z0 *SIGNAL(z) O a treia solutie folosita corespunde sistemelor in care exista mai multe resurse de acelasi tip. In acest caz, se folosesc asa numitele semafoare numaratoare (introduse de Dijkstra in 1965) - aceastea constau dintr-o valoare a semaforului v(s) - constind in numarul de resurse de acelasi tip - si o coada la acesta c(s). Pentru manipularea acestor semafoare au fost concepute doua primitive: P(s), care corespunde cererii de resursa, si V(s), corespunzind eliberarii acesteia: P(s): v(s)v(s)-1 daca v(s)