|
|
|
Sisteme de operare
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 ecaluare performantelor , se considera un sistem cu „n” procesoare independete 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 fiinf 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 realizar
accesul, doar un singur proces o acapareaza, probabilitatea de elibereare in
urmatorul interval de timp fiind: 1 dt = ct
L
In starea S0
un numar de „n” procesoare pot avea acces la baza de date , deci probabilitatea
fiind de ndt etc.
E
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 dt 2/E dt 1/E dt
S0 S1 S2 Sn-1 Sn
..
P (0) P(1) P(2) P(n-1) Pn
1/L dt 1/L dt 1/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 SiSi+1 este egal cu numarul de tranzatii de
laSi+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 * 1 dtP1 = L * P0 n!
ELE (n-1)!
2
P1 * n-1
dt= P2 * 1 dtP2 =
L * P0 n!
E L
E (n-2)!
3
P2 * n-2
dt= P3 * 1 dtP3 =
L * P0 n!(2)
E L
E (n-3)!
i
Pi = n!*L * P0 (3)
(n-i)! E
Din relatiile (1) si (3) 1
P0
=ni
1+∑ n! *L
i=1 (n-i)!E
Sau
1 (4)
P0
= ni
∑ 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
Nr de
procesoare cu
configuratie
4 5 12
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.
Deadlock-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 imprimante, blocuri de memorie etc.) sau temporare (cozi de mesaje etc. ). De asemenea , resursele pot fi de 2 tipuri:
a) ce se pot preleva fortat (resurse care pot fi luate procesului care le detine, fara efecte negative)
b) ce nu se pot prelua fortat (care nu pot fi luate de la proces fara a determina esecul executiei aplicatiei)
Utilizarea acestor resurse presupune o anume 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 patru conditii:
Prevenirea deadblock-ului este esential imposibila, deoarece necesita informatii despre cereri viitoare, care nu sunt cunoscute, dar , ce pot face sistemele reale exsitente pentru prevenirea deadblock-ului?Revenind la cele patru 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) Atacarea Conditiei de Excludere Mutuala
Daca nici o resursa nu va fi asignata exclusiv unui singur proces, nu vom avea deadblock-uri.De asemenea , este evident ca a permite la doua procese sa scrie la aceasi imprimanta, in acelasi timp, va aduce 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 care 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 elibereza toate resursele pe care le detine. Si apoi incearca sa acapareze toate resursele de care are nevoie inapoi.
c) Atacarea conditiei de planificare fara prelevarea 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 circulare 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 mai 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:
12 3 4 5
scaner imprimanta plotter unitate de banda CD-ROM
Procesele pot cere orice resursa doresc , dar cererile trebuie facute cu ordine numerica. Un proces poate cere intai o imprimanta si apoi o unitate de banda si nu invers.
