SISTEME DE OPERARE-  Procese

1 Conceptul de proces

Un proces reprezinta o entitate dinamica ce corespunde unui program in executie. Mai precis, un proces este un program a carui executie a fost initiata, dar nu s-a incheiat inca. Uneori, notiunea de proces este asociata conceptului de lucrare. O lucrare se defineste ca o secventa de pasi de lucru. Fiecare pas consta dintr-un modul al sistemului de operare sau al utilizatorului.

Totusi, conceptul de lucrare nu poate ingloba aspectele dinamice ale comportarii reale in sistem. De aceea, conceptul de lucrare i se asociaza notiunea de proces. Conceptual, fiecare proces are un procesor virtual propriu. In realitate, procesorul real comuta de la un proces la altul. Pentru a intelege mecanismul de tratare a proceselor, este mai usor sa ne gandim la o colectie de procese ce se executa in (pseudo) paralel.

In timp, un proces solicita diverse resurse (procesor, memorie principala, dispozitive periferice). Cum alocarea acestor resurse poate varia in timp, rezulta un comportament dinamic al programului ce le utilizeaza. In cazul sistemelor de tip secvential (pe loturi), aspectul dinamic nu exista, deoarece toate resursele sistemului, cu exceptia celor utilizate in exclusivitate de sistemul de operare, sunt alocate pe rand fiecarei lucrari. Alocarea se face inainte de lansarea in executie, care dupa initiere, se deruleaza fara intrerupere. In sistemele cu multiprogramare, multitasking sau multiprocesare, exista mai multe procese ce concureaza pentru obtinerea sistemului de calcul. Acestea pot solicita simultan la o resursa partajabila sau pot coopera la realizarea aceleiasi sarcini. Cererile de resurse ale acestor procese se rezolva in funcie de resursele disponibile ce urmeaza a fi impartite.

Evolutia unui proces este conditionata de prezenta a trei factori:

un set de instructiuni (subprogram sau program);

un procesor capabil sa execute aceste instructiuni;

un context sau mediu (memorie, fisier etc.) asupra caruia sa actioneze procesul conform celor prezentate in setul de instructiuni.

Rezulta ca trebuie distins intre un proces si un program. Procesul are caracter dinamic (precizeaza o secventa de activitati in executie), iar programul are un caracter static (el descrie activitatile de executat).

O aceeasi secventa de cod poate fi executata, la un moment dat, de mai multe procese numite instante. Pentru acesta, secventa de cod trebuie sa fie reentranta.

O secventa de cod este reetranta daca satisface urmatoarele conditii:

nu isi modifica instructiunile/constantele pe care le va executa/utiliza;

nu isi modifica instructiunile/constantele pe care deja le-a executat/utilizat (si de care nu mai are nevoie);

dispune de o zona de memorie (numita zona de reetranta) pentru fiecare proces care executa la un moment dat acea secventa de cod;

asigura accesul la resursele critice prin gestionarea unui fir de asteptare (se mai spune ca accesul la resursele critice este serializat).

O secventa de cod care nu respecta prima conditie este o secventa seriala reutilizabila, adica poate fi executata de un nou proces numai dupa ce procesul anterior a terminat-o. O secventa de cod ce nu respecta conditia a doua este nereutilizabila, adica dupa ce a fost executata de un proces nu mai poate fi executata si de alt proces. Zona de reetranta pastreaza informatii depsre fiecare instanta.

Procesele sunt fie procese sistem, fie procese utilizator. Procesele sistem sunt asociate unro module ale sistemului de operare, iar procesele utilizator sunt asociate unor programe utilizator care pot sa creeze alte procese utilizator sau sa lanseze module sistem.

Starile unui proces

Cum resursele unui sistem de calcul sunt, in cele mai multe cazuri, in cantitati limitate, este imposibila alocarea tuturor resurselor necesare unui proces la crearea acestuia. Astfel, la un moment dat, este posibil ca un proces sa nu poata continua. Imposibilitatea continuarii apare si atunci cand un proces trebuie sa astepte producerea unui eveniment. De exemplu, daca un proces trebuie sa genereze date necesare altui proces, acesta din urma va astepta pana cand datele necesare vor fi disponibile.

Atunci cand un proces se afla in imposibilitatea de a continua deoarece nu dispune de resursele necesare, se spune ca se afla in starea BLOCAT. In general un proces ajunge in aceasta stare atunci cand din punct de vedere logic el nu mai poate continua. Totusi este posbil ca un proces sa fie conceptual gata pentru executie, dar sa fie stopat deoarece sistemul de operare a decis alocarea procesorului unui alt proces (cu prioritate mai mare). In aceasta situatie se spune ca procesul este INTRERUPT. Cele doua conditii sunt complet diferite. In primul caz, suspendarea este inerenta (de exemplu, se asteapta introducerea unei linii de la tastatura). A doua situatie este de natura tehnica (nu poate avea fiecare proces procesorul sau). Daca procesul este in curs de executie si deci in mod implicit dispune de toate resursele necesare, se spune ca procesorul se afla in starea ACTIV. In sistemele de calcul cu un singur procesor, la un moment dat, numai un singur proces poate fi activ. In sistemele de calcul multiprocesor pot fi active cel mult atatea procese cate procesoare exista in configuratie.

Din punct de vedere practic, un proces consta dintr-un program si contextul acestuia. Contextul procesului cuprinde toate informatiile externe programului, ce pot fi adresate de acesta si care uneori sunt strict necesare evolutiei procesului. Aceste informatii sunt grupate intr-o structura numita teoretic, vector de stare al procesului, iar practic blocul de control al procesului. Acest bloc de control contine informatii precum: identificatorul procesului starea procesorului (contorul program, continutul registrelor, controlul intreruperilor etc.) - cand procesul nu este activ, starea procesului (ACTIV, INTRERUPT, BLOCAT etc.), prioritatea procesului la obtinerea resurselor, codurile de protectie, tabela de translatare a memoriei virtuale, informatii despre alte resurse (fisiere, dispozitive periferice etc.) alocate procesului si informatii privind contabilizarea resurselor (timpul de utilizare al procesorului, memoria ocupata, numarul operatiilor de intrare-iesire). Multimea campurilor continute in tabela de procese diferita de la un sistem de operare la altul.

3 Operatii cu procese

Un proces asociat unei lucrari este creat cu lansarea in executie a lucrarii si este distrus (eliminat) la terminarea executiei acestei. Crearea unui proces inseamna: alocarea unui vector de stare, initializarea componentelor vectorului de stare si inregistrarea procesului intr-o structura de date numita tabela proceselor. Astfel fiecare proces are un descriptor unic si anume: pozitia in tabela proceselor. Prin acest identificator sistemul de operare si alte procese il pot referi pe toata durata lui de viata. Un proces creat la cerearea altui proces utilizator sau sistem (numit proces tata), se numeste proces fiu si se spune ca este un descendent al procesului creator. Daca doua procese B si C sunt create de acelasi proces A, atunci B si C se numesc procese frati. Daca un proces fiu creaza un alt proces, acesta din urma este si descendent al parintelui procesului care l-a creat. Multimea proceselor create de un proces A, a proceselor create de aceste procese s.a.m.d. descendenta procesului A. In acest fel toate procesele sistemului alcatuiesc o structura arborescenta.

Exemple: Structuri arborescente de procese

1. In figura 1.1, procesorul A a creat doua procese fiu: B si C. Procesul B este fratele procesului C. Procesorul C este proces tata pentru procesele D, E si F.

Fig.1.1

Fig.1.2

Consideram activitatile S1-S7 cu urmatoarele dependente (fig.1.2): (S1, S2), (S1, S3), (S2, S4), (S4, S5), (S4, S6), (S5, S7), (S6, S7), (S3, S7). Prin notatia (A, B), se intelege ca activitatea B se poate executa numai dupa ce s-a incheiat executia activitatii A. Sistemului de activitati prezentat ii pot fi asociate procesele A, B si C, unde.

procesul C executa activitatea S5;

procesul B executa activitatile S2 si S4, creeaza procesul C si in paralel cu procesul C executa activitatea S6;

procesul A executa activitatea S1, creeaza procesul B si in paralel cu acesta executa activitatea S3. Dupa ce procesele B si C s-au incheiat, procesul A executa activitatea S7.

Distrugerea sau stergerea unui proces inseamna eliberarea resurselor ce i-au fost stocate, eliberarea memoriei corespunzatoare vectorului de stare, precum si eliminarea acestuia din tabela proceselor.Un proces se poate autodistruge, atunci cand ajunge la sfarsitul executiei sale sau poate fi distrus la cererea unui alt proces utilizator

Alte operatii asupra proceselor sunt: semnalizarea, intarzierea, planificarea, schimbarea prioritatii, suspensarea si reluarea. Un proces poate fi semnalizat in legatura cu aparitia unui eveniment sau poate fi intarziat pana la aparitia unui eveniment. Pentru a obtine controlul unui procesor, procesele sunt planificate. Schimbarea prioritatii unui proces influenteaza modul de alocare a resurselor necesare procesului. Un proces INTRERUPT (respectiv BLOCAT) poate fi INTRERUPT-SUSPENDAT (respectiv BLOCAT-SUSPENDAT). Prin reluare, un proces BLOCAT-SUSPENDAT (respectiv INTRERUPT-SUSPENDAT) devine BLOCAT (respectiv INTRERUPT). Tranzitiile posibile ale unui proces pe timpul duratei sale de viata sunt (figura 1.3):

INTRERUPT ACTIV: Aceasta tranzitie este realizata prin operatia de planificare in urmatoarele conditii: procesul are prioritatea maxima, procesorul (sau unul dintre procesoarele) este liber si procesorul are alocate toate resursele sale necesare intrarii in executie.

ACTIV INTRERUPT: Tranzitia are loc cand un proces cu prioritate mai mare decat procesul in executie a ajuns in starea INTRERUPT si are nevoie de procesor. Operatia ce cauzeaza tranzitia este cea de planificare.

ACTIV BLOCAT: Aceasta tranzitie are loc procesul ACTIV asteapta aparitia unui eveniment. Astfel, procesorul ocupat de procesul ACTIV devine disponibil pentru un alt proces aflat in starea INTRERUPT.

Fig.1.3 Tranzitiile posibile ale unui proces

BLOCAT INTRERUPT Trecerea in starea INTRERUPT are loc cand evenimentul asteptat de procesul BLOCAT se produce. Aceasta tranzitie se produce in urma operatiei de semnalizare.

INTRERUPT INTRERUPT - SUSPENDAT: Tranzitia este realizata cand asupra unui proces INTRERUPT se executa operatia de suspendare.

INTRERUPT - SUSPENDAT INTRERUPT: Asupra unui proces intrerupt si suspendat se efectueaza operatia de reluare.

BLOCAT BLOCAT - SUSPENDAT: Asupra unui proces ce asteapta producerea unui eveniment este executata operatia de suspendare.

ACTIV INTRERUPT - SUSPENDAT: Tranzitia are loc la suspendarea unui proces activ. Se executa operatia de suspendare.

BLOCAT-SUSPENDAT INTRERUPT - SUSPENDAT: Pentru a avea loc aceasta tranzitie trebuie indeplinita urmatoarele conditii:

procesul asteapta producerea unui eveniment;

procesul a fost suspendat;

evenimentul asteptat se produce.

Tranzitia are loc in urma operatiei de semnalizare.

BLOCAT-SUSPENDAT BLOCAT: Tranzitia se executa asupra unui proces ce asteapta un eveniment, iar dupa aceea a fost suspendat. Se executa operatia de reluare.

Prin operatia de distrugere, procesele trec din oricare din starile ACTIV, INTRERUPT, BLOCAT, INTRERUPT-SUSPENDAT si BLOCAT-SUSPENDAT in starea numita generic. INEXISTENT. In urma operatiei de creare procesele trec direct in starea INTRERUPT.

In general, daca sistemul de operare pastreaza o evidenta a fiilor fiecarui proces, este posibil sa se execute operatii de tip distrugere, suspendare, reluare nu numai asupra unui proces specificat ci si asupra unei descendente a sa.

Comentariu. Comportamentul sistemului poate fi usor inteles folosind conceptul de proces. Sistemul de operare executa atat programe pentru a raspunde comenzilor utilizatorului cat si programe pentru gestiunea fisierelor, lucrul cu discul sau cu alte echipamente periferice. In momentul aparitiei unei intreruperi, procesul curent este INTRERUPT si este lansat un proces pentru a rezolva cererea semnalata prin intrerupere. Astfel, activitatilor petrecute intr-un sistem de calcul le corespund procese utilizator, procese pentru gestiunea discurilor, procese pentru controlul terminalelor s.a.m.d. aflate in starea BLOCAT pentru producerea evenimentelor de care raspund. Acest model arata ca la baza sistemului de operare trebuie sa se afle planificatorul proceselor, iar restul componentelor este structurat in procese secventiale.

Exemple: Procese in sistemele de operare UNIX

Procese UNIX

Un proces UNIX este un proces secvential care la un moment dat executa un singur program si are un singur antet de control, adica are un singur contor program care indica instructiunea ce urmeaza a fi executata. Pentru un program dat pot exista la un anumit moment, una sau mai multe instante. Deoarece sistemul de operare UNIX este un sistem cu multiprogramare, la un moment dat pot fi active mai multe procese independente. Cum in sistem pot fi mai multi utilizatori (fiind si sistem multiutilizator), iar fiecare utilizator poate avea mai multe procese in sistem (in diverse stari), sistemul de operare gestioneaza sute sau chiar mii de procese. Chiar daca sistem nu e nici un utilizator, foarte multe procese background (demoni) sunt lansate la incarcarea sistemului de operare.

Executia proceselor utilizator in UNIX se face pe doua nivele: utilizator si nucleu, asociate nivelelor de functionare ale procesorului sistemului de calcul. In mod utilizator, procesele isi pot accesa numai propriile zone de instructiuni si date, pe cand in mod nucleu ele pot accesa si spatiul de adrese al nucleului. Nucleul sistemului de operare este partea integranta a oricarui proces in executie.

Trecerea de la un nivel la altul se realizeaza prin intermediul apelurilor sistem. Dupa un apel sistem procesul apelant va fi in mod nucleu, iar la intoarcerea din apelul sistem, procesul revine in modul utilizator.

Relativ la starile proceselor, sistemul de operare UNIX distinge urmatoarele stari de baza:

executia in mod utilizator;

executia in mod nucleu;

gata de executie (intrerupt);

in asteptare (blocat);

zombie.

In starea intrerupt, la un moment dat se pot afla mai multe procese. Ele sunt gestionate de catre nucleu prin intermediul unui fir de asteptare, fiind ordonate in functie de prioritatea acestora. Planificatorul alege procesul cu prioritatea maxima si il lanseaza in executie.

In starea blocat, un proces poate trece benevol cand asteapta terminarea unei operatii de intrare/iesire. De asemenea, un proces este blocat in urma plnificarii unui proces prioritar. La un moment dat un proces blocat se poate afla pe disc (proces evacuat) sau in memorie.

Starea zombie caracterizeaza toate procesele fiu in momentul terminarii lor. Intrarea din tabela de procese este eliminata numai de catre procesul parinte. Prin urmare, procesele fiu nu sunt distruse imediat dupa terminarea executiei lor.

Informatiile referitoare la procese sunt memorate intr-o tabela de procese, rezidenta in memorie. Cele mai importante caracteristici ale procesului sunt: localizarea in memorie (adresa de memorie si adresa de evacuare), dimensiunea, starea procesului, identificatorul procesului, identificatorului ce a creat procesul, descriptorii fisierelor deschise de proces, catalogul curent, catalogul radacina asociat procesului etc. Informatiile legate de fisiere, catal. si utilizatori, fac parte din regiunea de date asociata procesului ce va insoti procesul chiar si la evacuarea acestuia pe disc.

In UNIX procesele sunt create folosind apelul sistem fork. Procesul apelant se numeste proces parinte, iar procesul nou rezultat in urma apelului se numeste proces fiu. Initial, imaginile celor doua procese sunt identice, apoi ele pot avea propria lor imagine in memorie. Astfel, daca parintele asi modifica o variabila a sa, aceasta modificare nu este vizibila si pentru fiu, si reciproc. Fisierele deschise inainte de apelul fork, sunt partajate intre parinte si fiu. Prin urmare, daca un fisier a fost deschis de procesul parinte inainte de apelul fork, atunci el va fi descris si pentru procesul fiu.

Pe langa posibilitatea de creare a unui proces nou, un proces poate lansa in executie un program continut intr-un fisier executabil folosind unul din apelurile numite generic exec. Aceastea determina, in diverse variante, incarcarea unui program peste procesul curent si lansarea acestuia in lucrul. Prin apelurile exec se pot lansa in executie programe care sa foloseasca fisierele oferite de catre procesul parinte.

Operatiile cele mai importante, efectuate de catre nucleu pentru realizarea unui apel fork sunt (fig.1.4):-aloca o intrare noua in tabela de proces;

- asociaza un descriptor unic procesorului fiu;

- realizeaza o copie logica a imaginii memoriei parintelui;

- intoarce in procesul parinte descriptorului fiului iar in procesul fiu valoarea zero;

- trece procesul fiu in starea intrerupt (in memorie sau evacuat pe disc).

	Fig.1.2.4

Dupa crearea unui proces fiu, acesta poate executa cod precum parintele sau, sau un alt cod. Acest lucru este posibil prin verificarea valorii returnate de apel fork. Sa presupunem ca variabila care retine valoarea returnata de apel fork este cod_fiu. Atunci secventa (pseudocod) urmatoare descrie situatia in care cele doua procese, dupa apelul fork, executa coduri diferite:

cod_fiu: integer;

cod_fiu: = fork;

if cod_fiu = 0 then begin/codul fiului/end

else begin/cod parintelui/end;

Procesul fiu isi poate afla propriul descriptor folosind apelul getpid. Un proces parinte ce are mai multi fii va cunoaste descriptorii fiilor lui (creati prin apelul fork), iar la terminarea unuia dintre fii, nucleul sistemului de operare ii va semnaliza trecerea in starea zombie a acestuia fiu.

La incarcarea sistemului de operare UNIX, procesul sistem init este initiat de catre nucleu. Acest proces citeste fisierul /etc/ttys pentru a determina numarul terminalelor active din configuratie. Apoi, va crea cate un proces fiu pentru fiecare terminal, dupa care trece in starea blocat pana la terminarea unuia din procesele fiu. Fiecare proces fiu executa programul login care solicita introducerea de la tastatura a numelui si parolei utilizatorului. Datele introduse sunt verificate pentru potrivire cu cele din fisierul /etc/passwd. Daca utilizatorul are acces in sistem, atunci acest proces fiu lanseaza interpretorul de comenzi ales de utilizator. In caz contrar, programul login solicita reintroducerea numelui si a parolei.

4 Sincronizarea proceselor

Problema generala a sincronizarii consta in gasirea unui mecanism prin care un proces ACTIV sa devina BLOCAT sau sa determine BLOCAREA altui proces, pentru a astepta producerea unui eveniment.

Procesele pot interactiona in doua feluri: indirect, prin concurarea pentru aceeasi resursa si direct, prin utilizarea simultana a aceleiasi resurse si transmiterea unor informatii. Daca procesele sunt independente din punct de vedere logic, ele interactioneaza indirect, controlul concurentei fiind asigurat de nucleu. Cand procesele concureaza direct, controlul concurentei trebuie specificat la implementarea acestora. Activitatea de coordonare a proceselor impune gasirea de solutii eficiente privind: determinarea proceselor, interblocarea proceselor, excluderea mutuala a proceselor precum si sincronizarea acestora.

Un sistem de activitatii este nedeterminat daca rezultatele generate depind de viteza si ordinea de executie a activitatilor. In caz contrar se spune ca sistemul de activitati este unic determinat.

Interblocarea proceselor apare atunci cand acestea asteapta indefinit pentru evenimente ce nu se vor produce. Un astfel de eveniment poate fi, de exemplu, eliberarea unei resurse(fisier de date, zone de memorie, etc.).

Interactiunea proceselor conduce uneori la restrictii in care doua operatii nu pot fi niciodata executate in acelasi timp. Cel mai important exemplu il constituie utilizarea in comun, pentru scriere/citire, a aceleiasi resurse(fisier, zona de memorie, etc.). Resursa utilizata in comun este o resura critica. In aceasta situatie este necesara excluderea mutuala, adica un mecanism prin care, daca un proces utilizeaza resursa, celelalte procese sunt blocate. Partea unui program care solicita resursa partajata se numeste sectiune critica.

Solutia corecta a problemei excluderii mutuale trebuie sa satisfaca urmatoarele conditii:

a)exclusivitate: cel mult un proces, sa fie la un moment dat in sectiunea sa critica pentru aceeasi resursa;

b)evitarea blocajului reciproc: un proces nu trebuie sa astepte nelimitat pentru a intra in sectiunea sa critica;

c)uniformitetea solutiei: nu trebuie facuta nici o presupunere asupra vitezei de executie a proceselor;

d)evitarea dependentelor inutile: in afara sectiunii critice, un proces nu trebuie sa suspende alte procese.

Din punct de vedere hardware, dezactivarea intreruperilor la intrarea in sectiunea critica si activarea acestora la parasirea sectiunii critice constituie o solutie pentru rezolvarea problemei excluderii mutuale. Aceasta tehnica este folosita uneori de nucleul sistemului de operare, dar pentru procesele utilizator folosirea acestei tehnici nu este recomandata. In domeniul solutiilor software, au fost propuse mai multe metode: utilizarea variabilei poarta, metoda alternarii, metoda lui Peterson, metoda semafoarelor, etc.

1. Metoda variabilei poarta

Fie A si B doua procese ciclice. Metoda variabilei poarta presupune utilizarea unei variabile comune, initial permitand accesul oricarui proces in sectiunea sa critica. La intrarea in sectiunea critica procesul va verifica daca accesul este permis, iar in caz afirmativ va modifica valoarea variabilei pentru a indica intrarea sa in sectiunea critica. Mai precis, textul sursa al aplicatiei va fi:

Var poarta: (inchis, deschis); // variabila comuna//

Poarta:=deschis; //initial accesul este permis//

// procesul A// // procesul B//

repeat repeat

until poarta = deschis; until poarta = deschis;

porta:=inchis; porta:=inchis;

// cod sectiune critica A // // cod sectiune critica B //

porta:=deschis; porta:=deschis;

La o examinare atenta a codului se observa ca este posibil ca, la un moment dat, ambele procese sa gaseasca variabila poarta cu valoarea deschis. Astfel, ambele procese vor fi simultan in sectiunea critica. Deci, aceasta solutie nu satisface conditia a).

Metoda alternarii

Daca procesele alterneaza in executie atunci se poate utiliza o variabila comuna care specifica indicele procesului ce are dreptul sa intre in sectiunea critica:

VAR are_dreptul:'A' . . 'B'; // variabila comuna //

are_dreptul:= 'A'; // initial i se permite accesul procesului A //

// procesul A // // procesul B //

repeat repeat

until are_dreptul = 'A'; until are_dreptul = 'B';

// cod sectiune critica A // // cod sectiune critica B //

are_dreptul: = 'B'; are_dreptul: = 'A';

In acest exemplu ordinea de executie este A, B, A, B, A, etc. Daca procesul A este lent atunci procesul B va raspunde si el greu. Aceasta solutie nu satisface conditia c). Ea presupune o ordine predefinita a executiei celor doua procese.

3. Metoda lui Peterson

O solutie software a problemei excluderii mutuale, in care procesele nu sunt strict alternate, a fost produsa de Peterson in 1981. Ideea metodei Peterson este prezentata prin urmatoarea secventa de cod.

const N=2;

var indicator: char;

cerere: array ['A' . . 'B'] of boolean;

procedure intra_in_sectiune_critica (proces:char);

var alt_proces:char;

begin

case proces of

'A': alt_proces:= 'A';

'B': alt_proces:= 'B';

end;

cerere[proces]:=true;

indicator:=proces;

while(indicator=proces) and (cerere[alt_proces]) do;

end;

procedure iesire_din_sectiune_critica(proces:char);

begin

cerere[proces]:=false;

end;

Inainte de intrarea in sectiunea critica fiecare proces apeleaza procedura intra_in_sectiunea_critica cu parametrul indicativul propriu. Procedura va intra in asteptare pana la celalalt proces a apelat procedura iesire_din_sectiune_critica.

4. Metoda semafoarelor

Prin tehnica anterioara, daca un proces incearca sa intre in sectiunea sa critica si nu o poate face, el va consuma timpul procesorului pe perioada timpului alocat, sperand sa intre in sectiunea sa critica. Acest tip de asteptare se numeste asteptare activa. Este de preferat ca un proces ce nu poate intra in sectiunea sa critica sa se autoblocheze in asteptarea eliberarii resursei critice. Astfel, timpul procesorului poate fi mult mai bine folosit. Un instrument util in tratarea acestei probleme este semaforul.

Un semafor boolean (sau binar) este o variabila intreaga care poate lua numai valorile 0 sau 1. Asupra unui semafor binar pot actiona urmatoarele operatii:

initializare;

operatiaP : determina decrementarea cu 1 a semaforului (daca nu este deja zero);

operatia V: determina incrementarea cu 1 a semaforului (daca nu este deja 1).

Operatiile P si V sunt presupuse invizibile, adica odata ce o astfel de operatie a fost initiata de un proces, ea nu poate fi intrerupta de un alt proces inainte de a fi executata complet.

Sectiunile critice ale unui program li se poate asocia un semafor (initial 1), iar un proces ce doreste intrarea in sectiunea critica va executa operatia P asupra acestui semafor. Aceasta operatie este posibila daca valoarea semaforului nu este deja zero. In caz contrar, procesul se autoblocheaza. Deci, un semafor are valoarea zero cand un proces este in sectiunea sa critica, altfel va avea valoarea 1. La iesirea din sectiunea critica, procesul va executa operatia V care determina cresterea valorii semaforului: daca exista un proces blocat atunci acesta este semnalizat (daca sunt mai multe, este ales unul la intamplare) si este trecut in starea INTRERUPT pentru a castiga controlul procesorului.

Operatiile primitive P si V pot fi implementate si in hardware, dar in mod normal sunt implementate in software, folosind tehnica dezactivarii intreruperilor. Gestionarea proceselor ce asteapta trecerea de un semafor se face cu ajutorul unei cozi de asteptare, operatiile de inserare in coada si eliminare din coada fiind realizate de asemenea cu intreruperile dezactivate.

Cele de mai sus pot fi descrise prin urmatoarea secventa:

var excl:semafor_binar;

excl:=1; // initializare //

// cod proces //

. . .

P(excl);

// cod sectiune critica //

V(excl);

. . .

unde P(excl) si V(excl) sunt definite prin:

P(excl): if excl=1 then excl = 0

else asteapta in coada asociata semaforului excl,

V(excl): if coada este nevidathen scoate un proces din coada

else excl:=1.

O generalizare a semaforului binar o constituie semaforul numarator. Acest semafor este o variabila intreaga luand numai valori negative, iar operatiile asupra semaforului numarator sunt initializarea, operatia PN si operatia VN. Operatiile PN si VN sunt considerate invizibile. Un semafor numarator este initializat cu o valoare x mai mare de 1, iar operatiile PN si VN actioneaza numai asupra unor valori din domeniul 0 . . x. Daca valoarea unui semafor este zero, procesul ce va incerca sa execute o operatie PN va fi suspendat si va astepta ca un alt proces sa execute o operatie VN. Aceasta operatie VN determina reluarea unui proces selectat arbitrar. Definitiile operatiilor PN si VN asupra unui semafor numarator N iau urmatoarea forma:

PN(N): if N>0 then N:=N-1 else se suspenda procesul crent;

VN(N): if exista un proces suspendat la acest semafor

then selecteaza un proces pentru executie

else N:=N+1;

Diferenta esentiala intre un semafor numarator si un semafor boolean este aceea ca mai multe procese pot executa o operatie PN asupra unui proces numarator dupa care continua executia. Totusi, efectul unui semafor numarator poate fi obtinut folosind doua semafoare binare si o variabila intreaga dupa cum urmeaza:

var excl, amana:semafor_binar;

k:integer; // semafor numarator //

excl:=1; amana:=0;

k:=x; // initializare //

PN(k):= begin

P(excl);

k:=k-1;

if k<0 then begin V(excl); P(amana) end

else V(excl)

VN(k):= begin

P(excl);

k:=k-1;

if k<0 then begin V(amana);

V(excl)

end;

Exemplu: Mecanismul de sincronizare in UNIX

Sincornizarea proceselor in UNIX poate fi controlata de sistemul de operare sau de utilizator. In primul caz, mecanismul clasic de sicronizare este conducta(pipe). Sicronizarea controlata de utilizator se realizeaza in principal prin intermediul evenimentelor. Un eveniment reprezinta modalitatea de indicare a momentului in care un proces, anterior BLOCT, poate trece in starea INTRERUPT (gata de rulare). Blocarea proceselor se realizeaza folosind functia sleep apelata cu un argument ce reprezinta evenimentul asteptat. La producerea evenimentului de deblocare, nucleul sistemului de operare, folosind functia wakeup, trece toate procesele ce asteptau producerea evenimentului in starea INTRERUPT. Din toate aceste procese numai unul singur va trece in starea ACTIV.

Un eveniment UNIX este un numar intreg, stabilit prin conventie, cunoscut de nucleul sistemului de operare UNIX si asociat unei adrese. De exemplu, terminarea unui proces este un eveniment asociat adresei parintelui procesului curent din tabela de procese.

Producerea unor evenimente in sistem este semnalata in sistemul UNIX, fie de catre nucleu, prin functia wakeup, fie prin intermediul semnalelor. Semnalele UNIX sunt implementate cu ajutorul unor biti, plasati in tabela de procese. Acestia pot fi activati (li se atribuie valoarea 1) fie de catre nucleu (la producerea unor evenimente privind resursele sistemului de calcul), fie de catre utilizator prin intermediul apelului kill. Verificarea primirii unui semnal este realizata de nucleu la trecerea procesului din starea in executie in mod nucleu la starea in executie in mod utilizator, precum si la blocarea unui proces (atat inainte cat si dupa blocare). Un proces poate memora semnale diferite, dar nu poate pastra mai multe semnale de acelasi tip.

Cele mai importante semnale recunoscute de sistemul de operare UNIX (versiunea System V) sunt: terminare proces; indicare exceptii (incercare de acces in afara limitelor permise); semnale sosite de la terminali; semnale sosite de la procese utilizator (prin functie kill si alrm); semnale pentru erori din directive;etc.

La primirea unui semnal, actiunea asociata este cea de terminare a procesului. Totusi exista posibilitatea de tratare, de catre utilizator, a anumitor semnale. Pentru aceasta se poate folosi functia signal. Asfel, prin apelul signal(semnal, proc); se indica numarul unui semnal si rutina de tratare a semnalului. Aceasta rutina trebuie definita de utilizator.

Un alt tip de sincronizare o reprezinta sincronizarea unui proces parinte cu fii sai.Pentru aceata sistemul de operare pune la dispozitie functia wait ce permite blocarea uni proces pana la terminarea unuia dintre fii sai, sau pana la primirea unui semnal. Daca la apelul functiei wait unul dintre fii se terminase deja, blocarea nu se va mai realiza. Functia primeste ca parametru adresa unei variabile de tip intreg in care procesul fiu va completa informatii despre modul in care s-a terminat si intoarce identificatorul procesului fiu ce s-a terminat. Un proces parinte cu descendenti ce nu apeleaza la functia wait nu poate cunoaste modul de terminare si momentul terminari fiilor sai. Daca se doreste sincronizarea cu un anumit fiu, se repeta apelul wait (blocarea procesului) pana la terminarea fiului specificat. Indicarea fiului se realizeaza prin intermediul descriptorului de proces. O functie imoprtanta utilizabila de procese este functia exit care provoaca terminarea procesului apelant. Prin aceasta sunt inchise toate fisierele deschise in proces ai se transmite controlul procesului parinte. Functia foloseste un parametru de tip intreg, prin intermediul caruia se transmite procesului parinte modul de terminare a procesului.

Alte functii ce permit sincronizarea controlatpa de utilizator sunt: kill, alarm, pause si sleep. Functia kill trimite un semnal unui proces. Ea utilizeaza doi parametrii: identificatorul procesului si numarul semnalului ce va fi transmis. Prin apelul functiei pause, un proces se autoblocheaza pana la primirea unui semnal. Aceasta functie nu are parametrii. Un proces ce utilizeaza functia alarm cere sistemului sa transmita un semnal special (SIGALARM)dupa un interval de timp specificat prin parametrul apelului. Functia sleep este o combinatie intre pause si alarm si realizeaza suspendarea procesului ce o apeleaza pentru un timp specificat prin argumentul de apel.

Unele din functiile prezentate sunt apeluri sistem, altele sunt functii din biblioteca pentru dezvoltare de programe.

Ultimele versiuni ale sistemului de operare contin si un pachet de primitive ce implementeaza conceptele de semafor, regiune de memorie partajata si coada de mesaje. Studiul acestor mecanisme depaseste cadrul manualului si nu vor fi prezentate.

5.Comunicare intre procese

Mecanismele de sincronizare prezentate asigura rezolvarea problemelor de interactiune intre procese, prin introducerea unei secvente logice de executie a acestora. Aceste mecanisme nu permit transmiterea de informatii intre procesele ce coopereaza la realizarea unui obiectiv comun. Transmiterea unui semnal nu este suficienta; mai trebuie cunoscut si procesul ce a transmis semnalul. De asemenea, un proces ce transmite un mesaj poate fi interesat de confirmarea primirii si utilizarii mesajului.

Un prin mecanism de comunicare se bazeaza pe utilizarea zonelor comune de memorie. Cum o zona de memorie utilizata in comun este o resursa critica, se ajunge la programarea de sectiuni critice si excludere mutuala. Datele comune pot fi interpretate ca mesaje transmise de un proces altui proces care fie le asteapta, fie le va gai la nevoie.

Cel mai utilizat mecanism de comunicare prin intermediul unei zone comune cu sincronizare este mecanismul producator-consumator. Fie procesele A si B ce comunica intre ele prin depunerea si respectiv extragerea de mesaje dintr-o zona comuna numita tampon. Presupunem ca zona de memorie poate contine maxim N mesaje de aceeasi lungime. De asemenea, presupunem ca cele doua procese au o evolutie ciclica ce cuprinde operatii de depunere si extragere de mesaje. Aceste operatii pot fi realizate daca sunt indeplinite uramatoarele conditii:

la nivel de mesaj, operatiile se vor executa in excludere mutuala;

nu se poate depune un mesaj atunci cand nu mai exista spatiu in tampon;

nu se poate extrage un mesaj daca zona tampon este vida.

6.Concluzii

Un proces este o rutina sau un program in excutie. Pe durata lui de viata un proces se poate afla in una din starile: ACTIV, INTRERUPT, BLOCAT, INTRERUPT-SUSPENDAT sau BLOCAT-SUSPENDAT. Asupra unui proces se pot efectua operatii de creare, eliminare, intarziere, suspendare, semnalizare, reluare si planificare.

Un proces poate crea mai multe procese fiu si isi poate sincroniza executia cu acestea. Doua sau mai multe procese pot comunica intre ele folosind diferite tehnici. Procesele care comunica folosind resurse in comun (zone de memorie, fisiere, etc.) trebuie sa aiba acces exclusiv la resursa comuna. Secventa de instructiuni prin care se acceseaza resursa critica, contine apeluri de primitive speciale (de exemplu, P si V) puse la dispozitie de sistemul de operare.

Sistemul de operare UNIX utilizeaza ca mecanisme de sincronizare si comunicare: semafoarele, cozile de mesaje, fisierele FIFO, zonele de memorie comuna si alte mecanisme.