Interactinea taskurilor concurente

Interactinea taskurilor concurente

1. Consideratii generale

Exploatarea avantajelor aduse de considerarea unei aplicatii ca fiind compusa din mai multe taskuri ce se executa in paralel sau concurent impune, asa cum a rezultat si din exemplele prezentate in capitolul anterior, folosirea unor mecanisme care sa asigure interactiunea corecta a taskurilor pentru ca programul in ansamblu sa aiba evolutia dorita. S-a demonstrat ca interactiunea taskurilor poate fi redusa la trei tipuri de operatii multitasking: comunicarea intre taskuri, sincronizarea taskurilor si excluderea mutuala a taskurilor.

Comunicarea intre taskuri este operatia multitasking prin care se permite taskurilor sa schimbe date intre ele. Datele comune (utilizate de mai multe taskuri) sunt memorate in memoria interna a calculatorului in anumite zone declarate ca zone comune (pentru datele comune) si la care vor avea acces toate taskurile. Deoarece zonele de date comune organizate in memoria interna au o capacitate mica si limiteaza la un volum mic datele comune, in cazul unui volum mare de date, acestea se organizeaza in fisiere plasate pe un suport de memorie externa (de obicei disc magnetic).

Majoritatea sistemelor de operare actuale ofera un sistem de lucru cu fisierele prin intermediul unui SGF (sistem de gestiune a fisierelor). Dezavantajul acestei metode este legat de timpii relativ mari pentru accesarea datelor din fisiere, dar metoda este utilizata datorita capacitatii mari de memorare a acestor sisteme.

Sincronizarea este operatia multitasking care asigura esalonarea corecta a executiei taskurilor in timp sau, altfel spus, care stabileste o relatie de ordine intre instructiunile executate de acestea, independent de vitezele relative ale lor.

Scopul unei metode de sincronizare este de a oferi unui task Ti aflat in executie mijloacele care sa-i permita, in primul rand, sa blocheze un alt task activ Tj sau sa se blocheze el insusi in asteptarea producerii unui eveniment extern sau expirarii unui interval de timp si, in al doilea rand, sa deblocheze un task Tk caruia sa-i transmita eventual si unele informatii. In evolutia lor doua sau mai multe taskuri se pot sincroniza fie in functie de o conditie de timp, fie in functie de un eveniment exterior. Mai exact, in cadrul unei aplicatii, se poate intalni situatia ca un task Tk pentru a-si putea continua executia sa fie nevoit sa astepte trecerea unui anumit interval de timp sau realizarea unui eveniment din proces, eveniment controlat de regula de un alt task Ti. In cazul sincronizarii pe o conditie de timp, taskul Tk se va bloca pana la expirarea intervalului de timp mentionat dupa care va trece in starea READY si isi va putea continua executia. In cazul sincronizarii pe un eveniment exterior, taskul Tk se va bloca daca evenimentul nu a avut loc. De regula, acest eveniment este supravegheat de un alt task Ti care va debloca taskul Tk in momentul in care evenimentul s-a indeplinit.

Operatiile de sincronizare pot fi:

- explicite (directe), caz in care un task actioneaza direct asupra altui task, primitivele de blocare si deblocare trebuind sa fie astfel concepute incat sa accepte ca parametru numele taskului asupra caruia se actioneaza;

- implicite (indirecte), caz in care un task actioneaza asupra altui task prin declansarea unor mecanisme intermediare; primitivele de blocare si deblocare nu mai folosesc explicit numele taskului asupra caruia se actioneaza, ci folosesc o serie de variabile special-create in acest scop (semafoare, variabile eveniment etc.).

Restrictiile care determina sincronizarea taskurilor pot fi concentrate sub forma:

- operatia A nu se poate executa inaintea trecerii intervalului de timp ΔT;

- operatia A nu se poate executa inaintea operatiei B.

Excluderea mutuala este operatia multitasking prin care se exclude accesul simultan al mai multor taskuri la una si aceeasi resursa (zona de date din memorie, fisier, periferic etc.). Restrictiile, in acest caz, sunt de tipul: operatiile A, B, C, , X nu pot avea loc simultan.

Definitie: Secventa de program a fiecarui task in care se apeleaza o resursa comuna partajata se numeste sectiune critica a taskului. (Din aceasta cauza, de multe ori, excluderea mutuala a taskurilor se mai intalneste si sub denumirea de problema sectiunii critice).

Plecand de la ipoteza ca intervalele de timp de executie ale taskurilor sunt diferite si necunoscute si ca orice task iese din sectiunea sa critica dupa un interval finit de timp, solutia unei probleme de acest tip trebuie sa satisfaca urmatoarele conditii:

a) - utilizarea exclusiva: la un moment dat un singur task si numai unul se poate afla in sectiunea sa critica corespunzatoare unei resurse;

b) - evitarea blocajului reciproc: daca mai multe taskuri sunt blocate in asteptarea aceleiasi resurse critice si aceasta nu este ocupata, atunci unul dintre aceste taskuri (de regula cel mai prioritar), trebuie sa poata sa intre in sectiunea sa critica la capatul unui interval finit de timp;

c) - evitarea dependentelor inutile: daca un task este blocat in afara sectiunii sale critice, acest blocaj nu trebuie sa impiedice intrarea unui alt task in sectiunea sa critica.

Datorita conditiilor restrictive similare, problemele sincronizarii si excluderii mutuale pot fi tratate cu procedee comune. In prezent exista o mare varietate de procedee puse la dispozitia utilizatorului pentru rezolvarea acestor operatii multitasking si anume:

- folosirea unor variabile de tip intreg numite semafoare

- folosirea unor variabile logice numite variabile eveniment

- cu ajutorul unor structuri de date numite mesaje si a unor zone de memorie unde se depun

aceste mesaje numite celule mesaj sau cutii postale - cu ajutorul conceptului de monitor

- cu ajutorul conceptului de rendezvous .

Observatie: Ultimele trei procedee au avantajul de a rezolva in mod unitar si problema comunicarii

intre taskuri.

Utilizarea semafoarelor pentru excluderea mutuala a taskurilor si pentru sincronizarea

lor indirecta

Un semafor SEM este definit de perechea [v(SEM), q(SEM)], unde:

- v(SEM) = valoarea semaforului;

- q(SEM) = o coada de asteptare destinata sa primeasca taskurile care esueaza in incercarea lor de a

trece de acest semafor.

Variabila v(SEM) este de tip intreg, iar valoarea sa initiala v₀(SEM) este fixata in momentul crearii semaforului.

Administrarea cozii q(SEM) este la latitudinea sistemului de operare, iar continutul sau inaintea primei utilizari a semaforului este vid.

Semafoarele pot fi impartite in doua categorii:

- semafoare care pot lua numai doua valori, de obicei 0 si 1, numite, din acest motiv, semafoare binare;

- semafoare care pot lua orice valoare intreaga, numite semafoare generale sau contorizate.

Pentru manipularea semafoarelor s-au creat doua primitive speciale, neintreruptibile, notate cu P si V implementate in software-ul EXECUTIVULUI. Primitiva P apare ca o cerere de depasire a semaforului, iar primitiva V are semnificatia eliberarii, in anumite conditii, a unei autorizatii de trecere.

Observatie: Mentionam ca, semafoarele binare sunt suficiente pentru rezolvarea operatiilor

multitasking mentionate, astfel incat in continuare se vor face referiri numai la acestea.

Pentru semafoarele binare, primitivele P si V au urmatoarea structura:

Primitiva P(SEM):

daca v(SEM) = 0 atunci

q(SEM) ← Ti /* Blocheaza taskul Ti, adica taskul care a lansat primitiva, */

/* introducandu-l in coada de asteptare a semaforului q(SEM) */

altfel

v(SEM) = v(SEM) - 1

Primitiva V(SEM):

daca    v(SEM) ≠ 0     atunci

daca    q(SEM) ≠ ф atunci

Tj ← q(SEM)     /* Deblocheaza taskul Tj, care poate fi fie primul task */

/* din coada de asteptare a semaforului, fie taskul cel */

/* mai prioritar din aceasta */

altfel

v(SEM) = v(SEM) + 1

daca q(SEM) ≠ ф   atunci

Tk ← q(SEM) /* Deblocheaza toate taskurile Tk din coada */

/* de asteptare q(SEM) a semaforului SEM */

Prin utilizarea semafoarelor binare si a primitivelor P si V care actioneaza asupra lor asa cum s-a aratat mai sus, se poate rezolva eficient problema excluderii mutuale a resurselor critice partajate. Pentru aceasta, fiecarei resurse critice i se asociaza cate un semafor avand initial valoarea 1. Pentru claritate consideram:

Exemplul 1. Consideram n taskuri T1,T2, , Tn, care in executia lor pot apela simultan o aceeasi resursa. Pentru realizarea excluderii mutuale asociem acestei resurse critice un semafor binar SEM avand valoarea initiala v0(SEM) = 1. Inainte de a intra in propria sectiune critica, fiecare task este obligat sa execute primitiva P(SEM), iar dupa parasirea sectiunii critice trebuie sa execute operatia V(SEM). Astfel, secventa de program care incadreaza sectiunea critica a fiecarui task arata

ca in Figura 21.

Taskul Ti aflat in executie care efectueaza operatia P(SEM) se blocheaza daca v(SEM) = 0 si isi continua executia daca v(SEM) = 1. In cazul blocarii taskului Ti pe operatia P(SEM), sistemul de operare va da controlul unui alt task Tj din coada de asteptare q(SEM) a semaforului, aflat in starea READY. Daca taskul Ti intra in propria sa sectiune critica, atunci v(SEM) = 0 si nici o alta operatie P(SEM) nu mai poate avea loc, deci nici un alt task Tj, j ≠ i nu mai poate intra in sectiunea critica a programului sau, pana cand taskul Ti nu o paraseste pe a lui, moment in care executand primitiva V(SEM), face v(SEM) = 1. In acest moment are loc deblocarea taskurilor care asteptau sa intre in propria lor sectiune critica pentru aceeasi resursa.

Fig. 1.

Exista si situatii nedorite si care trebuie eliminate. De exemplu, daca taskul aflat in executie

este blocat in propria sa sectiune critica, atunci intrucat v(SEM) a ramas 0 (dupa executia primitivei

P(SEM)) se realizeaza blocajul infinit al tuturor celorlalte taskuri care utilizau aceeasi resursa. Din

aceasta cauza trebuie luate masuri pentru eliminarea acestei situatii, sau de eliberare a resursei. Pentru a-i garanta fiecarui task introducerea in sectiunea sa critica dupa un interval de timp finit, trebuie acordata o atentie deosebita administrarii cozilor de asteptare a semafoarelor. Cea mai

simpla metoda din acest punct de vedere este metoda FIFO, dar, in multe situatii, metoda dupa

prioritati (utilizata in multe EXECUTIVE de timp real) poate prezenta avantaje evidente.

Semafoarele binare impreuna cu primitivele P si V pot constitui un mijloc de solutionare a problemelor de sincronizare indirecta a taskurilor cu evenimente exterioare. Primitiva P actioneaza

ca o operatie de blocare a unui task, in timp ce primitiva V poate fi privita ca un semnal de deblocare al acestuia. Valoarea semaforului v(SEM) se asociaza cu starea evenimentului exterior

astfel:

v(SEM) = 0 - evenimentul nu a avut loc;

v(SEM) = 1     - evenimentul a avut loc.

In aceste conditii, valoarea initiala a semaforului va fi totdeauna zero (v0(SEM) = 0). In cazul a

doua sau mai multe taskuri sincronizate pe un singur eveniment exterior, procedeul este foarte

eficient si se desfasoara ca in exemplul

Exemplul  Consideram 2 taskuri T1 si T2 care trebuie sincronizate pe un eveniment exterior, eveniment de indeplinirea caruia este conditionata la un moment dat executia taskului T1.

Pentru aceasta procedam astfel. Asociem acestui eveniment un semafor SEM. Valoarea semaforului

v(SEM) se asociaza cu starea evenimentului exterior asa cum s-a aratat mai sus. Realizarea evenimentului respectiv este supravegheat de taskul T Atat timp cat evenimentul nu a avut loc,

semaforul SEM are valoarea v(SEM) = 0. Taskul T1 fiind in executie si ajungand la momentul

critic al programului, va incerca sa execute operatia P(SEM) si se va bloca deoarece v(SEM) = 0.

Taskul T2 va debloca taskul T1 executand primitiva V(SEM) care va face v(SEM) = 1 cand va

sesiza indeplinirea evenimentului. Structura programelor celor doua taskuri in vederea sincronizarii

pe un eveniment exterior este prezentata in Figura

Precizam ca acest procedeu devine ineficient in cazul unor taskuri sincronizate pe mai multe

evenimente externe. De asemenea, prin intermediul acestor variabile (semafoare binare), nu este

posibila realizarea sincronizarii taskurilor pe o conditie de timp. Semafoarele raman insa foarte

eficiente in rezolvarea problemei sectiunii critice.

Fig.

3. Utilizarea variabilelor eveniment pentru sincronizarea indirecta si excluderea mutuala a taskurilor

Variabilele tip eveniment sunt variabile logice speciale, partajate care pot fi manipulate numai cu ajutorul unor primitive special-compuse in acest scop. Aceste variabile pot fi declarate prin program sau pot fi parte constituenta a EXECUTIVULUI, caz in care acestea se cunosc si pot fi numai apelate prin program.

Operatiile posibile asociate unei variabile eveniment sunt, de regula, DECLAN§AREA provocata de un task supraveghetor si A§TEPTAREA si/sau CONSUMAREA (sau ambele), executate de un task a carei executie este conditionata de realizarea respectivului eveniment.

Efectul acestor operatii depinde de natura evenimentului. In acest sens se definesc evenimente nememorate si evenimente memorate. In cazul evenimentelor nememorate, o conditie esentiala pentru ca acestea sa fie exploatate consta in aceea ca sosirea lor sa fie asteptata. Astfel, daca unul sau mai multe taskuri a caror executie depinde de un astfel de eveniment se afla, in momentul sosirii evenimentului, in starea BLOCKED, ele vor fi trecute imediat in starea READY. Altfel, declansarea evenimentului ramane fara efect si, in plus, el este pierdut. Justificarea unui astfel de mod de tratare se explica prin faptul ca in anumite aplicatii, anumite evenimente sunt semnificative numai in anumite momente ale derularii procesului si, in cosecinta, daca nu sunt asteptate acestea nu mai prezinta nici un interes.

Evenimentul memorat este obtinut prin extensia celui nememorat si este reprezentat printr-o variabila logica notata 'EV' care poate lua valorile FALS (asociat cu valoarea 0) sau ADEVARAT (asociat cu valoarea 1), indicand cele doua alternative posibile: nedeclansarea, respectiv declansarea acestui eveniment.

Cand un task ajunge intr-un punct in care continuarea executiei lui este conditionata de sosirea unui eveniment asociat cu variabila EV, el se va bloca numai daca evenimentul asteptat nu s-a produs (EV = FALS). Sosirea evenimentului (EV = ADEVARAT) provoaca trecerea taskului care il astepta in starea READY. Acum este necesara exprimarea faptului ca respectivul eveniment a fost consumat. Consumarea sau anularea unui eveniment se face prin atribuirea variabilei EV a valorii FALS.

De regula, in aplicatiile de conducere a proceselor se opereaza cu conceptul de eveniment memorat, primitivele care pot actiona asupra variabilelor eveniment asociate fiind:

ASTEAPTA(expresie logica formata cu variabile eveniment) : blocheaza taskul pana cand

expresia logica continand una sau mai multe variabile eveniment capata valoarea ADEVARAT.

DECLANSAZA(EV) : face ca variabila eveniment EV sa capete valoarea ADEVARAT si

are semnificatia ca evenimentul asociat cu aceasta variabila logica a avut loc.

CONSUMA(EV) : face ca variabila eveniment mentionata EV sa capete valoarea FALS si

are semnificatia ca evenimentul asociat cu aceasta variabila logica s-a consumat.

Valoarea initiala a unei variabile eveniment este FALS. Variabilele eveniment sunt diferite de semafoare si prin aceea ca primitiva ASTEAPTA(⋅) nu le modifica valoarea.

Variabilele tip eveniment sunt adecvate pentru sincronizarea taskurilor in functie de evenimente.

Exemplul 3. Structura programelor a doua taskuri T1 si T2 sincronizate pe un eveniment exterior caruia i se asociaza variabila eveniment EV este prezentata in Figura 3.

Taskul T2 trebuie sa contina dupa directiva ASTEAPTA(EV) directiva CONSUMA(EV)

care semnifica fapul ca evenimentul a fost luat in considerare si care va permite o noua asteptare

din partea taskului T2 pe acelasi eveniment, in cazul functionarii celor doua taskuri in bucla infinita. De asemenea, taskul T1 trebuie sa aiba posibilitatea de a da controlul taskului T2 imediat dupa indeplinirea evenimentului. Aceasta se realizeaza fie prin introducerea dupa directiva DECLANSAZA(EV) a unei directive care sa declare eveniment semnificativ, fie prin construirea

directivei DECLANSAZA (EV) cu o optiune de acest fel.

Fig. 3

Exemplul 4. Consideram trei taskuri T1, T2, T3, primele doua urmarind indeplinirea a doua evenimente externe, asincrone, asociate cu variabilele EV1 si EV2, iar al treilea fiind conditionat in executia lui, la un moment dat, de indeplinirea ambelor evenimente. Ca atare, la momentul critic, taskul T3 va fi obligat sa execute primitiva ASTEAPTA(EV1 si EV2) si se va bloca daca cel putin una dintre variabile are valoarea FALS, ceea ce semnifica faptul ca cel putin unul dintre evenimente nu a avut loc. Pe masura ce evenimentele au loc, taskul T1, respectiv T2 vor

executa primitivele DECLANSAZA(EV1), respectiv DECLAN§AZA(EV2) care vor avea ca efect

deblocarea taskului T3 si aducerea lui in situatia de asi putea continua executia. Structura

programelor celor trei taskuri este prezentata in Figura 4.

Figura 4.

Variabilele tip eveniment pot fi utilizate si in realizarea operatiilor multitasking de excludere mutuala. Pentru evitarea accesului simultan a doua sau mai multe taskuri la o resursa partajata, acesteia i se asociaza o variabila eveniment EVM careia i se atribuie initial valoarea ADEVARAT. Directiva DECLAN§AZA(EVM) simuleaza primitiva V (de la semafoare), iar ansamblul de directive A§TEAPTA(EVM) urmata imediat de CONSUMA(EVM) poate simula primitiva P, daca secventa se executa neintreruptibil, ceea ce nu este greu de realizat. Structura a doua taskuri T1 si T2 in situatia de excludere mutuala este prezentata in Figura 5.

Primul task care intra in sectiunea critica ajunge in aceasta trecand de primitiva

A§TEAPTA(EVM) - posibil, deoarece initial EVM = ADEVARAT, executand apoi primitiva

CONSUMA(EVM) ceea ce duce la EVM = FALS. In acest moment orice alt task care doreste sa

patrunda in propria sa sectiune critica se va bloca pe primitiva ASTEAPTA(EVM) pana cand taskul

initial abandonand resursa comuna executa primitiva DECLANSAZA(EVM) in urma careia

variabila eveniment EVM capata valoarea ADEVARAT.

Fig. 5