Planificarea pentru executie a proceselor in sistemele cu mai multe procesoare

Planificarea pentru executie a proceselor in sistemele cu mai multe procesoare

In cazul in care sistemele de calcul dispun de mai multe procesoare, politica de planificare a proceselor este mult mai complexa. In acest caz nu este vorba despre retelele de calculatoare in care fiecare proces ruleaza pe masina proprie si planificarea acestora e locala, ci despre sisteme distribuite cand procesele pot migra de pe o masina pe alta. In cazul sistemelor omogene, orice proces din cadrul sistemelor poate fi rulat pe oricare procesor.

Cand sistemele au mai multe procesoare identice se pot folosi mai multe metode de planificare.

1)           planificarea master-slave. Procesele pregatite pentru executie sunt puse intr-o coada. Exista un procesor specializat care are acces la lista proceselor pregatite pentru executie si care face planificarea pentru toate celelalte procesoare. De oricate ori un procesor care este disponibil printr-un apel sistem corespunzator, face o cerere catre master si acesta alege, incarca si lanseaza in executie un proces. Masterul trebuie sa transfere in memoria locala a procesorului care trebuie sa execute un anumit proces, intreaga informatie asociata acelui proces.

Aceasta politica de planificare depinde de master, putand aparea situatii de "gatuire" a sistemului, asa ca unele procesoare vor fi refolosite in momentul in care ele asteapta ca masterul sa raspunda.

2)           planificarea omogena. In acest caz functia de planificare este distribuita, fiecare procesor care devine liber, disponibil ruleaza procesul de planificare, acceseaza lista proceselor pregatite pentru executite, alege un proces si il executa folosind acelasi algoritm de planificare. Daca un procesor se defecteaza, procesul current va fi rulat in continuare pe unul din celelalte procesoare. Este necesara stabilirea unei coordonari corespunzatoare accesului la lista comuna de procese pregatite pentru executie.

Problema sincronizarii proceselor

Problema sincronizarii se pune atat pe sistemele cu un singur processor cat si pe sistemele multiprocessor in care se pune problema utilizarii partajate a resurselor, ceea ce presupune o coordonare si o cooperare intre procese pentru o operare corecta. In unele cazuri coordonarea este impusa de catre sistemul de operare, datorita saraciei resurselor. Un program poate sa fie alcatuit din mai multe procese, fiecare execuand prelucrari particulare, fiind insa necesar sa schimbe informatia intre ele din timp in timp.

Se pot pune doua probleme de sincronizare:

a)           conditia de cursa

b)           blocaj reciproc (deadlock)

In unele sisteme de operare, procesele care coopereaza pot uneori partaja unele elemente de stocare comune, ce pot fi accesate pentru citire sau scriere. Aceste elemente de stocare partajate se pot afla in memoria principala sau in fisiere partajate ; localizarea acestor elemente de memorie  partajata nu schimba natura modului de comunicare intre procese sau problemele care pot aparea. Pentru a vedea practic modul in care se desfasoara comunicarea intre procese putem sa consideram un spooler de imprimanta. Cand un proces doreste sa imprime un fisier, va introduce numele fisierului intr-un "director de spooler". Un alt proces, "daemon-ul"(eng) de printare, verifica in mod periodic daca se afla vreun fisier, pentru a fi printat, iar daca exista il printeaza si apoi sterge numele fisierului din director.

Sa consideram cazul in care directorul de spooler are un numar foarte mare de locatii numerotate 0, 1, 2 , fiecare putand sa memoreze un nume de fisier. De asemenea, sa consideram ca sunt doua variabile partajate, out, care identifica urmatorul fisier ce va fi printat si in care identifica urmatoarea locatie libera din director. Aceste doua variabile pot fi tinute intr-un fisier de doua cuvinte, disponibil pentru toate procesele.

La un moment dat locatiile de la 0 la 3 sunt libere (fisierele au fost deja printate) si locatiile de la 4 la 6 sunt ocupate (cu numele de fisiere pregatite pentru printare). Mai mult sau mai putin simultan procesele A si B se hotarasc sa introduca cate un fisier in coada pentru printare. Aceasta situatie este prezentata in figura urmatoare:

Poate aparea urmatoarea situatie: procesul A citeste variabila in si memoreaza valoarea 7 intr-o variabila locala numita "urmatoarea locatie libera". Imediat ce apare o intrerupere de ceas si CPU, se decide ca procesul A a rulat suficient si ca va fi rulat procesul B.

Procesul B citeste variabila in, preia valoarea si va stoca numele fisierului sau in locatia 7, apoi actualizeaza variabila in, aceasta devenind 8. Procesul se opreste.

Sa presupunem ca procesul A ruleaza din nou, de la punctul de la care a fost oprit. Va citi variabila "urmatoarea locatie libera", va gasi valoarea 7 si va scrie numele fisierului sau in locatia 7, stergand numele fisierului pe care procesul B tocmai l-a pus. Apoi va calcula "urmatoarea locatie libera" + 1, care devine 8 si va actualiza variabila in la 8. Acum directorul de spooler este consistent asa ca "demonul" de printare nu va anunta nimic gresit dar nu va apare tiparit fisierul procesului B. Situatii asemanatoare acesteia, cand doua sau mai multe procese citesc sau scriu informatii partajate si rezultatul final depinde de ordinea de rulare a proceselor, se numesc conditii de cursa.

Exemplul arata ca in momentul in care sunt utilizate in comun structuri de date, este necesara o sincronizare. Se poate impune un anumit tip de sincronizare, numita excludere mutuala.

Daca un proces utilizeaza o variabila comuna (aflata de ex intr-un fisier), toate celelalte procese care vor sa utilizeze variabila trebuie sa fie impiedicate sa o faca. Conditia poate fi formulata si astfel: o parte din timp un proces e ocupat executand operatii interne, din cand in cand accesand insa regiuni de memorie partajata, regiuni de date comune care determina aparitia conditiei de cursa. Aceasta portiune program se numeste sectiune critica. Evitarea cursei se face actionand astfel incat sa nu se afle simultan doua procese in sectiunea critica. Structurilor de date utilizate in comun li s-a asociat un zavor (1 bit). Inainte de a accesa structura de date comune, procesul trebuie sa verifice daca structurile sunt libere, zavorul este deschis, blocheaza zavorul si le va folosi.

Revenind la exemplul nostru, Procesul A utilizeaza structura de date si Procesul B nu, zavorul fiind blocat, iar cand s-a terminat utilizarea structurilor procesul va elibera resursa si va deschide zavorul.

Mecanisme de sincronizare

1. Mecanismul TEST - AND - SET foloseste un bit de zavorare (x).

Cele 2 primitive sunt:

LOCK (x)

Aceasta primitiva trebuie sa fie executata de catre fiecare proces inainte de utilizarea resursei.

Modalitatea de implementare a primitivei este urmatoarea:

1. Examineaza valoarea octetului x

2. Seteaza octetul la valoarea 1

3. if valoarea initiala a fost = 1 then goto 1

Dupa utilizarea resursei se utilizeaza primitiva:

UNLOCK (x)

Aceasta primitiva trebuie sa fie executata de catre fiecare proces dupa utilizarea resursei, pentru eliberarea zavorului.

In acest caz se va reseat valoarea octetului la 0.

Operatiile 1 si 2 de mai sus trebuie sa fie executate simultan, fara a fi intrerupte (utilizand eventual mecanisme hardware).

Sectiunea critica pentru n procese se poate realiza astfel:

Proces 1            Proces 2. Proces n

Lock (x) Lock (x) Lock (x)

sect critica        sect critica sect critica

Unlock (x) Unlock (x) Unlock (x)

Dezavantajul acestui mecanism este ca se blocheaza procesul in tot acest timp de asteptare pentru a intra in sectiunea critica (se executa busy-waiting = asteptare ocupata)

O alta varianta imbunatatita este: ASLEEP - AWAKE

Cele 2 primitive sunt:

a) Lock (x)  , a carei varianta de implementare este:

1. Examineaza valoarea octetului x

2. Seteaza octetul x la valoarea 1

3. if valoarea initiala a fost = 1 then ASLEEP (x)

Operatiile 1 si 2 sunt operatii TEST - AND - SET neintreruptibile.

In acest caz exista si o coada de procese asociata, daca procesul nu poate folosi resursa, el va fi blocat si trecut in aceasta coada.

b) Unlock (x)  , a carei varianta de implementare este:

1. Resetarea octetului x la 0

2. AWAKE (x)

Primitiva AWAKE verifica lista de procese blocate la octetul x si daca sunt procese, il extrage pe primul si il duce in lista proceselor pregatite pentru executie.

In acest caz, avantajul este ca procesorul nu mai este utilizat pe timpul asteptarii.

In cazul utilizarii unor resurse echivalente (mai multe resurse de acelasi tip, acestea putand fi alocate in orice ordine), sunt necesare mecanisme de sincrinizare mai evoluate decat cele prezentate pana acum.

Semafoare numaratoare (introduse de Dykstra in 1978)

In acest caz in locul uni bit (0-liber, 1-ocupat) se folosteste un octet (sem) cu valori cuprinse intre 0 si numarul de resurse. Valoarea lui 'sem' arata numarul de resurse libere.

Operatiile elementare ce se pot executa asupra lui 'sem' sunt:

P (sem) - se executa la ocuparea resursei (sau WAIT (sem)), a carei implementare este:

1. sem=sem-1;

2. if sem<0 then ASLEEP (sem)

V (sem) - se executa la eliberarea resursei (sau SIGNAL (sem)) a carei implementare este:

1.     sem=sem+1;

2.     if sem>0 then AWAKE (sem)

Excluderea mutuala in cazul resurselor controlate prin aceste semafoare numaratoare se poate face astfel:

P(sem)

utilizare resursa

V(sem)

In exemplul urmator se implementeaza mecanismul producator-consumator. Producatorul produce elemente pe care le pune in buffer, de unde vor fi consumate de consumator. Bufferul este folosit pentru comunicatia dintre producator si consumator.

var mutex, plin, gol:semaphore,

Daca bufferul este infinit, producatorul nu se blocheaza niciodata; daca este finit, se va bloca atunci cand se umple bufferul. Daca bufferul este gol, consumatorul se blocheaza.

Pentru cazul finit:

plin=0;

gol=n;

Bufferul nu este introdus de catre mecanismul de sincronizare, ci de modalitatea de rezolvare a problemei. Accesul la buffer se face in regim de excludere mutuala (resursa utilizata in comun atat de producator, cat si de consumator).