|
|
|
Comunicatia intre procese
In afara luptei pentru acaparera procesorului care se desfasoara intre procese, pot apare si elemente de cooperare (schimb de informatie). De exemplu, modularizarea programelor: un program mare e bine sa fie spart in mai multe module program ce interactioneaza facand schimb de informatii prin:
a) zone de memorie partajata
b) schimb de mesaje
a) In acest caz , cade in sarcina proceselor sa se ocupe de comunicatii, sincronizare, sistemul oferind numai suportul pentru memoria partajata.
b) In acest caz, procesele schimba date prin mesaje. Responsabilitatea revine sistemului de operare care implementeaza primitivele SEND si RECEIVE:
SEND (proces_destinatie, &mesaj);
RECEIVE (proces_sursa, &mesaj);
Comunicatia se realizeaza intre 2 procese: procesul _sursa si procesul_destinatie.
O alta varianta pentru comunicatia prin mesaje, destinatarul poate primi mesaje de la oricine, in acest caz primind identificatorul sursei:
SEND (proces _destinatie, &mesaj);
RECEIVE (id, &mesaj);
De asemenea , mesajele schimbate intre procese se pot pune intr-un buffer numit cutie postala (mailbox).
SEND (m_box, &mesaj);
RECEIVE (m_box, &mesaj);
Mesajele se primesc in ordinea sosirii. Problema producator-consumator este rezolvata de catre sistem, in spatele functiilor SEND, RECEIVE fiind implementat mecanismul de excludere mutuala la accesarea bufferului, blocare la buffer plin sau gol.
Procesul destinatie este pus in coada de asteptare daca nu i-a sosit nici un mesaj. La fel , procesul sursa, daca bufferul este plin se va bloca pana la eliberarea unui loc in buffer. Copierea mesajelor din spatiul utilizator in buffer, din buffer in spatiul destinatie este consumatoare de timp. Solutia ar fi utilizarea zonelor de memorie partajata, evitandu-se consumul de timp si memorie (se transmit doar adresele mesajelor).
SEND_BY_REFERENCE();
RECEIVE_BY_REFERENCE();
Evaluarea performantelor sincronizarii
In sistemele cu mai multe procese si procesoare, apare o crestere a perioadelor de timp in care unele procese sunt blocate, astfel incat, desi am "n" procese, unele stau nefolosite, avand procese in asteptare datorita sincronizarii.
Ex1.
In cazul accesului la o resursa nepartajabila, un proces cere accesul la ea si daca acesta este ocupata, procesul se blocheaza suspendandu-si executia.
Ex2.
In cazul sistemelor cu mai multe procesoare, unele dintre ele ruleaza procesul de planificare (scheduler). Restul procesoarelor care doresc sa execute procese se blocheaza, asteptand accesul la lista de procese in asteptare (acces ce se realizeaza cu regim de excludere mutuala). In acest caz vom avea blocare cu buclare.
Pentru evaluare performantelor , se considera un sistem cu "n" procesoare independente si identice. In acest sistem exista structuri de date "stranse" intr-o baza de date partajata (controler global, cu un singur zavor). Se presupune ca sistemul se afla in regim stationar (nu se creaza procese, nu dispar , in sistem existand doar cele "n" procese).
Dupa ce ruleaza un timp (distribuit probabilistic dupa o functie exponentiala, proportionala cu 1/E, E fiind timpul mediu de rulare), procesul face acces la acea structura de date. Cand structura respectiva de date nu este blocata , procesul blocheaza structura si lucreaza cu ea un timp. Un procesor se poate afla in una din starile:
1. Executa un proces
2. Realizeaza accesul la structura de date comuna
3. Blocare cu ciclare pentru accesarea bazei de date
Acest sistem se poate gasi in "n+1" stari, S0, , Sn, fiecareia dintre aceste stari asociindu-se o probabilitate P0, .., Pn.
Starea Si a sistemului este starea in care unu numar de "i
"procesoare fac asteptarea ciclata la baza de date mai sus amintita. Indiferent
cate procese au realizat accesul, doar un singur proces o acapareaza,
probabilitatea de elibereare in urmatorul interval de timp fiind: 
In starea S0 un numar de "n" procesoare pot avea acces la baza
de date , deci probabilitatea fiind de 
etc.
Prin asocierile acestor probabilitati intre tranzitiile diferitelor stari, se poate utiliza modelul Markov pentru evaluarea performantelor sincronizarii.
n/E dt
(n-1)/E dt (n-2)/E dt2/E dt1/E dt
S0S1 S2 Sn-1Sn
..
P (0) P(1) P(2) P(n-1) Pn
1/L dt 1/L dt1/L dt1/L dt 1/L dt
Am presupus ca procesoarele au un comportament identic si am etichetat fiecare sageata cu probabilitatea ca tranzitia respectiva sa se produca intr-un interval de timp dt.
Se iau in considerare urmatoarele aspecte:
a) Starea sistemului este stabila:
n
∑ Pi = 1 (1)
i=0
b) Numarul de tranzatii Si 
Si+1este
egal cu numarul de tranzatii de la Si+1 Si . Tinand
cont de acest aspect si considerand ca numarul de tranzitii dintr-o stare in
alta este egal cu produsul probabilitatilor ca sistemul sa se gaseasca in prima
stare si probabilitatea ca el sa se tranziteze in urmatorul interval de timp,
putem scrie relatiile:
1
P0 * n dt= P1 * 1dtP1 = L * P0n!
E L E(n-1)!
2
P1 * n-1
dt= P2 * 1dt P2 = L * P0n!
E L E(n-2)!
3
P2 * n-2
dt= P3 * 1dt P3 = L * P0n!(2)
E L E(n-3)!
i
Pi = n! * L* P0 (3)
(n-i)! E
Din relatiile (1) si (3) 1
P0 = n i
1+ ∑ n! * L
i=1 (n-i)! E
Sau
1(4)
P0 = n i
∑ n! * L
i=0 (n-i)! E
Se pune problema numarului de procesoare care stau nefolosite la un moment dat. Apar in starile de la S2 la Sn.(in starile S0 si S1 nu pot fi procesoare nefolosite)
Pentru analiza criteriilor de performanta trebuie sa avem in vedere ca :
n
E(gol)= ∑ (i-1)Pi (5)
i=2
In relatia de mai sus , inlocuind valoare lui Pi din (3) si a lui P0 din (4) se obtine ca:
n
∑ i-1
E=i=2 (E/L)i
* (n-i)! (6)
n
∑ 1
i=0 (E/L)i * (n-i)!
Din aceasta formula, se pot obtine curbe care descriu numarul de procesoare blocate in functie de numarul de procesoare din configuratia sistemului, si anume:
Nr probabil de procese blocate cu ciclare
0.7
L/E=0.2
0.4
L/E=0.05
L/E=0.1
0.2 L/E= 0.025
4 512
Nr de procesoare cu configuratie
Observatie:
Asa cum se observa din grafic, la un numar de 40 de procesoare 19 sunt blocate si 21 merg, la 41 de procesoare, 20 sunt blocate si 21 merg deci nu e eficienta adaugarea celui de al 41 procesor. Pentru un nr mic de procesoare, se pot adauga noi procesoare,crescand performantele dar apare un timp de overhead pentru testare.
Dead-lock (blocajul reciproc)
Sistemele de calcul contin un numar mare de resurse care pot fi folosite de catre un singur proces la un moment dat (de exemplu: imprimante, unitati de banda etc). In acest caz in sistemele cu multiprogramare pot apare probleme serioase. Sa consideram, de exemplu, doua procese, fiecare dorind sa tipareasca cate un fisier foarte mare de pe unitatea de banda. Procesul A cere permisiunea de a utiliza imprimanta si o primeste. Procesul B cere permisiunea de a utiliza unitatea de banda si o primeste. Acum procesul A cere permisiunea pentru unitatea de banda, dar nu o primeste pana cand B-ul nu permite. Inainte de a elibera unitatea de banda, procesul B cere permisiunea de a utiliza imprimanta. In acest punct ambele procese sunt blocate si asa vor ramane in continuare.
Dead-lock-ul poate apare atunci cand procesele au asigurat accesul exclusiv la dispozitive, fisiere etc. Sa consideram aceste obiecte ca resurse. Ele pot fi permanente (resurse fizice ca imprimanta, blocuri de memorie etc) sau temporare (cozi de mesaje etc). De asemenea, resursele pot fi de doua tipuri:
a) ce se pot preleva fortat (resurse care pot fi luate procesului ce le detine, fara efecte negative)
b) ce nu pot preleva fortat (care nu pot fi luate de la proces fara a determina esecul executiei aplicatiei)
Utilizarea acestor resurse presupune o anumita disciplina:
Daca resursa nu este disponibila cand este facuta cererea, procesul este fortat sa astepte.
Definitie: O multime de procese se afla in dead-lock daca toate asteapta producerea unui eveniment de catre un proces din acea multime (blocat si el la randul lui). Evenimentul asteptat de obicei este eliberarea unei resurse detinute de catre un alt procesor. Cu alte cuvinte, fiecare membru din multimea de procese aflate in dead-lock asteapta o resursa pe care o are un proces blocat. Nici unul din procese nu poate rula, nici unul nu poate elibera resurse si nici unul nu se poate debloca.
Conditii de producere a blocarii
Pentru a se putea produce dead-lock-ul trebuie indeplinite 4 conditii:
Prevenirea dead-lock-ului este esential imposibila, deoarece necesita informatii despre cereri viitoare, care nu sunt cunoscute, dar, ce pot face sistemele reale existente pentru prevenirea dead-lock-ului? Revenind la cele 4 conditii enuntate mai inainte, daca ne asiguram ca cel putin una din aceste conditii nu este satisfacuta. Atunci blocajul reciproc va fi structural imposibil.
a) Alocarea Conditiei de Excludere Mutuala
Daca nici o resursa nu va fi asignata exclusiv unui singur proces, nu vom avea dead-lock-uri. De asemenea, este evident ca a permite la 2 procese sa scrie la aceeasi imprimanta in acelasi timp va duce la rezultate imprevizibile. Prin virtualizarea iesirii imprimantei, procesele pot scrie la imprimanta in acelasi timp. Din pacate, nu toate dispozitivele pot fi virtualizate. Practic, aceasta conditie nu se poate ataca. Evitarea asignarii unei resurse cand aceasta nu este absolut necesara, precum si asigurarea unui numar minim de procese care urmaresc acapararea acelei resurse sunt conditii care trebuiesc realizate in cadrul fiecarui sistem.
b) Atacarea conditiei de alocare partiala (HOLD & WAIT)
Daca se poate preveni ca procesele ce detin resurse sa astepte pentru mai multe resurse, se pot elimina blocajele.
O modalitate pentru a realiza acest scop, este de a cere ca procesele sa incerce acapararea tuturor resurselor inainte de a incepe executia. Daca toate resursele sunt disponibile, procesul va putea rula pana la completarea sa. Daca una sau mai multe resurse sunt disponibile iar celelalte ocupate, nu se va aloca nici o resursa, iar procesul va astepta.
O problema imediata este aceea in care procesele nu stiu cate resurse sunt necesare pana ce incep sa ruleze. De asemenea, resursele nu sunt utilizate in mod optim. De exemplu, daca un proces citeste date de pe o banda magnetica, face prelucrari 2 ore si apoi scrie datele la un plotter facand rezervarea resurselor in avans, procesul va tine blocate unitatea de banda si plotter-ul.
O alta modalitate de a ataca aceasta conditie este aceea ca un proces care urmareste acapararea unei resurse sa elibereze toate resursele pe care le detine. Si apoi incearca sa acapareze toate resursele de care are nevoie inapoi.
c) Atacarea conditiei de planificare fara prelevare fortata
Atacarea acestei conditii este chiar mai putin promitatoare decat atacarea conditiei anterioare. Daca un proces detine o imprimanta si este in mijlocul imprimarii, nu este deloc optima pierderea brusca a imprimantei din cauza unui plotter care este necesar
d) Atacarea Conditiei de asteptare circulara
Asteptarea circulara poate fi eliminata in cateva moduri. O modalitate este de a impune regula ca un proces sa detina o singura resursa la un moment dat. Daca doreste o a doua resursa, trebuie sa o elibereze mai intai pe prima. Daca un proces doreste copierea la imprimanta a unui fisier foarte mare de pe unitatea de banda, aceasta conditie este inacceptabila. O alta cale de a evita asteptarea circulara, este de a asigura o numerotare globala a tuturor resurselor
1 2 3 45
Scanner imprimanta plotter unit banda CD-ROM
Procesele pot cere orice resursa doresc, dar cererile trebuie facute cu ordine numerica. Un proces poate cere mai intai o imprimanta si apoi unit de banda si nu invers.
