Fire de executie paralele - Procese si subprocese concurente

Fire de executie paralele

Procese si subprocese concurente

In anumite aplicatii este necesar ca mai multe activitati sa progreseze in paralel, astfel incat se creeaza aparenta ca un acelasi program (calculator) se poate ocupa in paralel de mai multe sarcini. Un exemplu tipic este un program de tip "server" care trebuie sa raspunda cererilor adresate de mai multi "clienti" (programe client) independenti unii de altii.

La nivelul sistemului de operare activitatile paralele se numesc procese (in sisteme de tip Unix) sau "taskuri" (in sisteme Microsoft Windows ).

Se spune ca doua procese (fire) P1 si P2 (lansate in ordinea P1,P2) sunt concurente sau paralele atunci cand executia lui P2 incepe inainte de terminarea completa a lui P1. Altfel spus, cele doua procese pot evolua in paralel, chiar pe un singur procesor care executa alternativ secvente de intructiuni din P1 si din P2. Paralelismul proceselor nu implica neaparat mai multe procesoare care lucreaza simultan, ci este o alternativa la executia strict secventiala a celor doua procese : se executa complet P1 si apoi se excuta complet P2 (fara intreruperi).

Este posibil ca in doua procese (fire) paralele sa se execute aceeasi secventa de instructiuni sau secvente de instructiuni complet diferite.

Procesele paralele isi disputa timpul procesorului si trebuie sa existe un planificator de procese (numit si dispecer), care sa decida ce proces primeste controlul procesorului, la producerea anumitor evenimente cu efect asupra starii poceselor.

Paralelismul unor activitati se poate realiza la nivelul sistemului de operare pentru activitati ce rezulta din executarea unor programe independente (nu neaparat distincte), fiecare cu spatiul sa de memorie si de nume (dar care pot comunica intr-un fel sau altul).

Ulterior a fost adaugat un alt nivel de paralelism, in cadrul fiecarui program (aplicatie), sub forma unor fire de executie ("threads"). Un proces poate contine mai multe fire (subprocese). Comutarea intre fire paralele este mai rapida decat comutarea intre aplicatii (procese).

In Java paralelismul (aparent) are loc in cadrul unui singur program (sau aplet), iar numele folosit pentru o astfel de activitate este acela de "thread" (fir de executie) sau "subtask" sau "proces de categorie usoara" ("ligthweight process"), deoarece foloseste acelasi spatiu de memorie (si de nume) cu celelalte fire de executie din acelasi program.

In Java planificatorul la executie a firelor este parte componenta a masinii virtuale Java (JVM). Cedarea controlului procesorului de catre firul activ (in executie) se poate face voluntar (la cererea sa) sau ca urmare a lansarii unei operatii de intrare-iesire.

Firele paralele pot evolua complet independent unele de altele (asincron) sau pot utiliza anumite resurse comune (zone de memorie, fisiere etc) si atunci este necesara sincronizarea lor in incercarea de acces la o resursa comuna.

Dupa crearea sa si inainte de terminare, un fir poate trece ciclic prin cateva stari, iar schimbarea starii sale este cauzata fie de evenimente interne ( o actiune a procesului activ), fie de evenimente externe, cum ar fi o decizie a planificatorului.

Principalele stari in care se poate afla un fir sunt:

- In executie, cand firul este activ (detine controlul procesorului).

- Suspendat ( in asteptare), cand firul asteapta producerea unui eveniment.

- Gata de executie dar inactiv, pentru ca exista un alt fir gata mai important.

In general exista o coada a proceselor "gata" si o coada a proceselor care asteapta; dintre procesele gata planificatorul alege pe cel cu prioritate maxima si care este primul in coada (daca sunt mai multe procese gata cu aceeasi prioritate).

Procesele paralele (concurente) isi pot disputa anumite resurse comune (un fisier de date, de exemplu) sau isi pot transmite reciproc date (procese producator-consumator).

Interactiunile dintre procese (sau subprocese) paralele nu se fac prin apeluri directe intre procese ci prin intermediul dispecerului. Coordonarea si sincronizarea proceselor paralele necesita existenta unor operatii specifice, prin care procesele se adreseaza planificatorului.

Fire de executie in Java

In Java exista intotdeauna un fir de executie implicit (cu numele "main"), creat automat si in care se executa functia "main" cu rol de program principal.

Alte fire de executie pot fi create de programator ca obiecte ale unor subclase a clasei JDK numita Thread. Clasa Thread contine cateva metode, unele apelate de dispecer iar altele care apeleaza dispecerul. Efectul metodei "run" (apelata de dispecer) depind de rolul pe care il are firul de executie in cadrul unei aplicatii. In clasa Thread metoda "run" nu are nici un efect si de aceea trebuie definita o subclasa, cu metoda "run" redefinita:

class T extends Thread

Crearea unui nou fir de executie inseamna crearea unui nou obiect si se face intr-un fir activ (care poate fi cel implicit, pentru functia "main"). Exemplu:

Thread fir1 = new T();

Firul parinte apeleaza de obicei o singura metoda a firului "fiu" (metoda "start"), pentru lansarea sa in competitie cu celelalte fire; de aceea nici nu se mai creeaza uneori variabile de tipul subclasei. Exemplu:

new T( ).start(); // obiect anonim de tipul T

Firele din clase ce extind clasa Thread pot avea un constructor cu parametru de tip String, prin care se poate da un nume firului creat.

Principalele metode ale clasei Thread sunt :

start : Permite lansarea unui fir dintr-un alt fiu (parinte). Noul fir este pus in competitie cu alte fire prin plasarea lui in starea "gata de executie" (eventual urmata imediat de activarea lui).

run : Este apelata de catre planificator la activarea firului de excutie

sleep : Este apelata de firul activ pentru a se autosuspenda pentru un timp dat.

yield : Este apelata de firul activ pentru cedarea controlului altor fire gata de executie.

getName : Obtine numele firului in curs de executie

isAlive : Apelata din firul activ pentru a verifica daca un alt fir s-a terminat definitiv sau nu.

Metodele urmatoare sunt mostenite de la clasa Object dar se folosesc numai in obiecte de un tip derivat din Thread sau Runnable :

wait : Este apelata de firul activ pentru a se autosuspenda in asteaptarea unui semnal de la un alt fir paralel (care detine o resursa comuna)

notify, notifyAll : Firul activ notifica (anunta) firele in asteptare ca pot continua.

Metoda "run" din Thread se redefineste in fiecare fir definit de utilizatori si determina efectul executarii acestui fir. De obicei metoda "run" contine un ciclu in care se executa anumite operatii (afisare, desenare, operatii cu fisiere etc.) si se apeleaza una din metodele prin care se cedeaza controlul celorlalte fire concurente ("yield", "sleep", "wait" etc.).

Este posibil ca mai multe fire concurente sa execute aceleasi operatii. Exemplu:

class T extends Thread

public void run () // doarme un timp

catch (InterruptedException e)

}

System.out.println (getName()+ ' terminat'); // la terminarea procesului

}

private int time (int i)

// creare si lansare procese paralele

public static void main (String [] arg)

}

Succesiunea de afisare depinde de secventa de numere aleatoare generate, dar si de alte evenimente din sistem (pentru un sistem de operare multi-tasking care aloca cuante de timp fiecarui task, cum este Microsoft Windows ).

Metoda "run", asa cum este definita in interfata Runnable (pe care o implementeaza si clasa Thread), nu poate arunca mai departe exceptia InterruptedException si de aceea exceptia trebuie "prinsa" si tratata in metoda "run".

Metoda "main" este si ea parte dintr-un fir de executie creat automat la activarea masinii virtuale Java pentru interpretarea unui program. Fiecare fir de executie primeste automat un nume, daca nu primeste explicit un nume la construirea obiectului de un subtip al tipului Thread .

Cedarea controlului de catre un fir se face si automat, dupa initierea unei operatii de I/E si pana la terminarea operatiei respective. Exemplul urmator pune in evidenta aceasta situatie:

// proces de citire de la tastatura

class Fir extends Thread // asteapta tastarea unei clape

catch (IOException e)

}

public static void main (String [] arg) catch (Exception e)

}

}

}

Definirea unei subclase a clasei Thread nu mai este posibila pentru procese paralele din cadrul unui aplet, deoarece un aplet este o subclasa a clasei Applet si in Java nu este permis ca o clasa sa extinda mai mult de o singura clasa. De aceea a fost creata si o interfata numita Runnable, care contine numai metoda "run". Metodele "wait", "notify" si "notifyAll" nu puteau face parte din aceata interfata deoarece ele nu pot fi implementate de orice utilizator si de aceea fac parte din clasa Object, ca metode native si finale.

Crearea unui fir de executie folosind interfata Runnable necesita definirea unei clase care implementeaza aceasta interfata si definirea metodei "run" din aceasta clasa. In aceasta clasa se pot folosi cateva metode statice din clasa Thread :

Thread.currentThread( ) : are ca rezultat o variabila de tip Thread ce se refera la firul de executie activ (in executie).

Thread.sleep ( milisec) : are ca efect punerea in asteptare pentru un timp specificat a firului activ, cu cedarea controlului catre planificatorul de procese Java.

Lansarea in executie a unui fir se poate face numai prin apelul metodei "start" din clasa Thread , fie in functia "main", fie intr-o alta metoda (dintr-un alt fir, de exemplu). De aceea trebuie creat cate un obiect Thread pe baza fiecarui obiect Runnable, folosind un constructor al clasei Thread care admite un parametru de tip Runnable. Exemplu:

class Proces implements Runnable catch (InterruptedException e)

}

}

// creare si lansare procese paralele

public static void main (String [] arg)

}

De observat ca pentru terminarea unui fir de executie nu este necesara o metoda speciala; ea se produce la terminarea tuturor actiunilor prevazute in metoda "run" a firului. Un program cu mai multe fire paralele se termina atunci cand s-au terminat toate firele (mai pot ramane fire de tip "daemon" dupa terminarea unui program).

Un fir este terminat definitiv (mort) fie prin terminarea instructiunilor din metoda "run", fie prin apelarea metodelor "stop" sau "destroy". Metoda "isAlive" are rezultat true daca obiectul (de un subtip al lui Thread) pentru care este apelata este un fir "viu" (neterminat).

Fiecare fir are o prioritate asociata (un intreg intre 1 si 10), care arata importanta relativa a acelui fir fata de alte fire. La creare un fir primeste prioritatea implicita 5, dar aceasa prioritate poate fi modificata prin metoda "setPriority".Daca mai multe fire sunt gata de executie, atunci cand planificatorul preia controlul ( la apelul unei metode sau la terminarea unei operatii de I/E), este ales firul cu prioritate maxima pentru a fi activat.

Un proces poate fi blocat definitiv in urmatoarele situatii :

- Procesul asteapta eliberarea unei resurse de catre un alt proces (prin "wait"), iar procesul care detine resursa fie nu poate fi activat, fie nu transmite semnal de eliberare a resursei (prin "notify" sau "notifyAll"). Acest tip de blocare (numit "starvation") poate fi evitat prin programarea corecta a proceselor cu resurse comune.

- Un proces P1 asteapta eliberarea unei resurse (asteapta un semnal) de la un alt proces P2, iar P2 asteapta eliberarea unei alte resurse detinute de P1 (asteapta semnal de la P1). Acest tip de blocare reciproca (numit "deadlock") poate fi evitat prin impunerea unei discipline de acces la resursele comune (o a numita ordine de ocupare si eliberare a resurselor comune).

Fire de executie sincronizate

Firele paralele pot evolua un timp independent unele de altele, dar in anumite momente pot sa-si dispute resurse comune sau doresc sa-si transmita date prin variabile comune. In ambele situatii trebuie reglementat accesul la resursele comune, deoarece in caz contrar pot apare fie situatii de blocare definitiva a unor procese, fie situatii de transmitere incorecta a unor date intre fire de executie. Sincronizarea firelor paralele trebuie sa asigure rezultate corecte si reproductibile pentru aceste fire, indiferent de momentul activarii si de succesiunea in timp a reactivarii fiecarui fir.

Sectiunile de cod din fiecare proces care acceseaza resursa comuna se numesc sectiuni critice sau regiuni critice. Este important ca instructiunile dintr-o sectiune critica sa se execute neintrerupt pentru un anumit proces si pentru un anumit obiect, fara ca un alt proces sa poata executa si el aceleasi operatii pentru un acelasi obiect.

In Java o sectiune critica este fie o metoda, fie un bloc de instructiuni precedate de cuvantul cheie synchronized. Sincronizarea se face la nivel de obiect si nu la nivel de functie.

Pentru a ilustra efectele nesincronizarii a doua procese cu o resursa comuna vom considera exemplul a doua procese care actualizeaza periodic un acelasi contor. Contorul este un obiect dintr-o clasa "Contor" definita de noi, cu doua metode publice: "get" care citeste valoarea curenta a variabilei contor (de tip private) si "incr" care mareste cu 1 valoarea variabilei contor.

Ideea este ca incrementarea se realizeaza prin mai multe operatii (instructiuni masina) si ca aceasta secventa de operatii poate fi intrerupta (de planificatorul de procese) iar un alt proces reactivat poate dori sa execute aceeasi secventa de incrementare a aceluiasi contor (cazul a doua oficii din localitati diferite de la care se cere simultan rezervarea unui loc la un zbor sau la un tren). Pentru a forta transferul controlului de la un fir la altul am detaliat incrementarea in trei instructiuni de atribuire si am suspendat procesul intre fiecare dintre aceste operatii (prin "sleep").

class Contor

public void incr () catch (InterruptedException e)

}

public int get ()

}

// pentru obiecte fir de executie

class Fir extends Thread

public void run () catch(InterruptedException e)

c.incr();

System.out.println (getName()+' '+c.get());

}

}

}

class ExFir catch (Exception e)

System.out.println (c.get()); // valoare finala contor

}

}

Fiecare din cele doua fire face cate 5 incrementari ale contorului comun, dar valoarea finala a contorului nu este 10, ci este o valoare mai mica ( 5 pentru programul anterior). Rezultatul final depinde in general de timpii de asteptare ai fiecarui fir (intre operatii), de ordinea lansarii si de alte procese din sistem.

Explicatia este simpla: firul f1 citeste in "aux" o valoare "m" a contorului, este intrerupt de firul f2 care citeste si el in variabila sa proprie "aux" aceeasi valoare "m"; fiecare proces incrementeaza apoi si scrie inapoi in "m" aceeasi valoare a variabilei sale "aux". Din aceasta cauza valoarea contorului creste cu 1 si nu cu 2 cum ar fi trebuit daca cele doua fire erau sincronizate fata de resursa comuna.

In general, cand un proces incepe sa modifice o resursa comuna trebuie interzis altor procese sa modifice aceeasi resursa inainte ca procesul care a obtinut primul resursa sa fi terminat operatiile de modificare a resursei. Altfel spus, trebuie serializat accesul la resursa comuna pentru procese (fire) concurente. Solutia Java pentru programul anterior este foarte simpla: se adauga cuvantul cheie synchronized in declaratia metodelor "incr" si "get", inainte de tipul metodei:

public synchronized void incr ()

Dupa ce firul f1 a intrat in executia metodei sincronizate "incr" pentru un obiect "c", nu se permite altui fir sa mai execute o metoda sincronizata pentru acelasi obiect, iar firul f2 care incearca acest lucru este pus in asteptare pana la terminarea metodei sincronizate.

O metoda sincronizata poate fi intrerupta, dar nu poate fi reapelata pentru acelasi obiect dintr-un alt fir concurent. De asemenea, nu este permisa apelarea din fire diferite a unor metode sincronizate diferite pentru acelasi obiect. De exemplu, nu este posibil ca doua fire sa adauge in paralel elemente la un acelasi vector ("addElement"). Toate metodele de acces la un vector (din clasa Vector) sunt sincronizate pentru a fi sigure la apelare din fire concurente.

Cuvantul synchronized ar trebui adaugat oricarei metode care modifica un obiect ce poate fi folosit in comun de mai multe fire de executie paralele. Multe din metodele claselor JDK sunt sincronizate (dar nu toate).

Dupa apelarea unei metode "sincronizate" pentru un obiect acest obiect este "blocat" cu un "zavor" sau "lacat" ("lock") si nu mai poate fi apelata o alta metoda sincronizata pentru acelasi obiect (dintr-un alt proces). Deblocarea obiectului are loc la terminarea executiei metodei sincronizate. Deoarece sincronizarea se face la nivel de obiecte, datele comune proceselor trebuie incapsulate in obiecte utilizate in comun. La crearea unui proces care foloseste o astfel de resursa comuna (variabila, colectie, fisier) se transmite adresa obiectului ce constituie resursa comuna.

O alta denumire folosita este cea de "monitor" : fiecare obiect poate avea un monitor asociat (creat efectiv numai atunci cand este necesar). Un monitor este un zavor initial deschis si care se inchide dupa ce un fir a apelat o metoda synchronized pentru obiectul respectiv; firul respectiv devine proprietarul monitorului pana la terminarea metodei.

Prin monitoare se asigura accesul strict secvential al firelor concurente la operatii critice asociate unui obiect. Un monitor este asociat unui obiect (sau unei clase) si nu unei metode.

Doua fire pot executa in paralel secvente din doua metode sincronizate, dar pentru obiecte diferite. De asemenea, un fir poate executa o metoda sincronizata si un alt fir o metoda nesincronizata pentru un acelasi obiect.

Exemplul urmator arata cand poate fi necesara sincronizarea unor secvente de instructiuni care opereaza asupra unui obiect, din fire concurente. Doua procese modifica un acelasi vector, prin adaugarea unui caracter la fiecare sir din vector. Desi fiecare metoda din clasa Vector este sincronizata, totusi o secventa de apeluri de metode nu este automat sincronizata, iar firul activ poate pierde controlul intre apeluri de metode sincronizate:

class Fir extends Thread catch(InterruptedException e)

}

}

}

public Fir ( Vector c)

}

class ModifyVector ;

Vector c= new Vector(Arrays.asList(s));

Fir f1 = new Fir ( c );

Fir f2 = new Fir ( c );

f1.start(); f2.start();

while ( f1.isAlive() && f2.isAlive() )

try catch (Exception e)

System.out.println (c); // continut final vector

}

}

Putem deosebi doua situatii de utilizare a unei resurse comune de catre doua fire concurente:

- Ordinea accesului la resursa nu este importanta, dar in timp ce un fir foloseste resursa nu rebuie permis celuilalt fir accesul la resursa.

- Ordinea in care firele acceseaza resursa este importanta, pentru ca ele isi transmit date prin intermediul resursei (fire de tip producator-consumator sau emitator-receptor).

O clasa este sigura intr-un context cu fire concurente ("thread-safe") daca rezultatele metodelor sale sunt aceleasi indiferent din cate fire paralele sunt apelate aceste metode pentru aceleasi obiecte. Practic, aceasta calitate a unei clase se obtine prin adaugarea atributului synchronized metodelor care modifica date din clasa. Metodele sincronizate au performante mai slabe decat metodele nesincronizate si de aceea nu toate clasele JDK sunt "thread-safe".

Primele clase colectie (Vector, Hashtable) au avut metode sincronizate, dar clasele colectie din Java 2 nu sunt implicit "thread-safe" din motive de performanta. Sunt prevazute insa metode de obtinere a unor clase colectie echivalente sincronizate. Exemplu:

List safelist = Collections.synchronizedList (new ArrayList());

Procese de tip producator-consumator

Situatia transmiterii de date intre doua procese paralele este schematizata de obicei sub forma unui cuplu de procese numite "producator" si "consumator" (de mesaje).

In exemplul urmator producatorul "produce" numere intregi consecutive (la intervale de timp generate aleator) si le depune intr-o variabila (dintr-un obiect), iar consumatorul preia aceste numere din variabila comuna si le afiseaza pentru a ne permite sa verificam daca toate numerele transmise au ajuns fara pierderi sau repetari si in ordinea corecta la consumator.

Sectiunile critice sunt metodele "get" si "put" din clasa "Buffer", care blocheaza si deblocheaza accesul altor procese la variabila comuna pe durata acestor operatii. Variabila "full" este necesara pentru a arata cand poate fi modificat (full=false) si cand poate fi folosit (full=true) continutul variabilei comune "contents".

class Producer extends Thread

public void run()

catch (InterruptedException e)

}

}

}

class Consumer extends Thread

public void run()

}

}

// clasa pentru obiecte cu date comune

class Buffer catch (InterruptedException e)

full = false;

notifyAll();

return contents;

}

// scrie o valoare in variabila comuna

public synchronized void put(int value) catch (InterruptedException e)

contents = value; full = true;

notifyAll();

}

}

Metodele "wait", "notify" si "notifyAll" pot fi apelate numai in metode sincronizate; in caz contrar apare o exceptie cauzata de efectul acestor metode: "wait" elibereaza monitorul asociat obiectului respectiv, pentru a permite altor fire sa modifice starea obiectului.

De obicei comunicarea intre procese (fire) se face printr-o coada (un "buffer"), dar ideea este ca operatiile de introducere in buffer si de extragere din buffer trebuie "sincronizate" pentru executarea lor strict secventiala in procese diferite.

Clasele PipedWriter (PipedOutputStream) si PipedReader (PipedInputStream) din pachetul "java.io" permit comunicarea simpla de date intre procese de tip producator si consumator printr-un "flux" de date. Operatiile de acces la date sunt sincronizate iar gestiunea zonei comune de date (o coada) nu cade in sarcina programatorului.

Cuplarea canalului de scriere (PipedWriter) cu canalul de citire (PipedReader) se poate face in doua feluri: la construirea obiectului PipedReader se transmite ca parametru o variabila de tip PipedWriter, sau se foloseste metoda "connect".

// Producator

class Producer implements Runnable

public void run() catch(IOException e) // pune caracter in flux

try catch (Exception e)

}

}

}

// Consumator

class Consumer implements Runnable

public void run() catch (Exception e)

try catch (IOException e)

}

}

// Program de test

class Pipes

}