. Sisteme Concurente. Evolutia Concurentei la Nivelul Limbajelor de Programare

INTRODUCERE

Referatul de față își propune o abordare generală a tematicii sistemelor concurente, în contextul modern al dezvoltării sistemelor nesecvențiale (paralele, concurente, distribuite). Marea amploare pe care a luat-o dezvoltarea aplicațiilor distribuite în ultimul deceniu ne îndreptățește să considerăm această temă de actualitate și de interes pentru cercetarea românească.

Din punct de vedere logic, referatul face parte din stagiul de pregătire pentru elaborarea lucrării de doctorat care își propune să introducă un model formal pentru aplicații nesecvențiale. Acest prim referat este precedat de trei examene cu temele: limbaje formale, paradigme ale programării (paralel, concurent, distribuit), sisteme distribuite și va fi urmat de un referat care va trata aspecte referitoare la modelarea sistemelor nesecvențiale.

Din punct de vedere structural, referatul este organizat în două părți:

Partea I SISTEME CONCURENTE;

Partea a II-a IMPLEMENTAREA SISTEMELOR CONCURENTE.

Partea întâi abordează nivelul fizic al sistemelor concurente de o manieră bottom-up. Astfel, primele paragrafe introduc mai multe clasificări ale sistemelor concurente, împreună cu exemple de sisteme nesecvențiale pentru tipologiile introduse. O dată făcută legătura cu aplicabilitatea acestor tipuri de sisteme, în capitolul al treilea am propus o definiție a sistemelor concurente. Această definiție este completată în capitolele următoare de integrarea concurenței în tematica generală a sistemelor nesecvențiale (paralele, concurente, distribuite). Din capitolul al patrulea trebuie remarcată diversitatea opiniilor în ceea ce privește delimitarea celor trei concepte: paralel, concurent, distribuit.

Partea a doua abordează nivelul logic al sistemelor concurente, introducând o serie de mecanisme specifice de implementare a aplicațiilor concurente, mecanismele de comunicare între procese (IPC). Partea centrală este capitolul opt care ia în discuție principalele caracteristici ale concurenței, dezvoltate și detaliate în capitolele următoare. Astfel, mecanismele IPC sunt descrise la cele trei nivele fundamentale: (1) low-level, (2) mecanisme bazate pe partajarea memoriei și (3) transmitere de mesaje (mecanisme fără partajarea memoriei).

In capitolul al zecelea sunt enunțate o serie de probleme clasice (specifice) de concurență. Dintre acestea, cele mai reprezentative sunt tratate în detaliu: problema adunării concurente, problema producător-consumator și problema cititor-scriitor.

partea i

sisteme concurente

EVOLUȚIA SISTEMELOR DE CALCUL. APARIȚIA CARACTERISTICILOR SISTEMELOR CONCURENTE

Originea problematicii programării concurente se regăsește la începutul anilor ’80. Dar, înainte de aceasta, se poate vorbi de aspecte concurente la nivelul sistemului de operare, mai ales odată cu apariția calculatoarelor paralele și a rețelelor de calculatoare.

Cronologic vorbind, primele „simptome” de concurență s-au manifestat la începutul anilor ’50, odată cu apariția sistemelor seriale cu multiprogramare. Acestea au adus nou: (a) tehnica polling (prin care procesorul poate sonda periodic starea perifericelor), (b) lucrul cu întreruperi, (c) canalul de intrare- ieșire (un procesor specializat pe efectuarea operațiilor de intrare- ieșire) care poate lucra în paralel cu procesorul central.

Aceste mecanisme au permis introducerea unor tehnici noi de exploatare eficientă a unității centrale de prelucrare. Dintre acestea, s-au remarcat utilizarea zonelor de memorie de tip tampon (buffers) și dezvoltarea tehnicii spooling. Bufferele de memorie aveau rolul de a regla diferența de viteză între perifericele lente și procesoarele rapide. Tehnica spooling (Simultaneous Peripheral Operation On-Line) se referă pe de o parte la posibilitatea citirii în avans a programelor și pe de altă parte la posibilitatea afișării asincrone a rezultatelor. Aceste două direcții evidențiau un aspect nou de paralelism, concretizat în posibilitatea suprapunerii în timp a execuției operațiilor de intrare- ieșire și a calculelor aritmetice și logice.

Ca o extensie a sistemelor cu multiprogramare s-au impus sistemele interactive și sistemele multitasking. Principalele caracteristici specifice sistemelor interactive sunt: (a) tehnica de deservire a cererilor utilizatorilor în timp partajat (time-sharing), (b) redirectarea și (c) legarea în pipe.

Următoarea etapă a fost dezvoltarea sistemelor multiprocesor și a sistemelor multicalculator. Un sistem multiprocesor rezultă din interconectarea a două sau mai multor procesoare cu memorii și echipament de intrare- ieșire comune. Intr-un sistem multicalculator, calculatoarele sunt interconectate între ele prin linii de comunicare formând o rețea de calculatoare. Intr-o rețea avem mai multe calculatoare autonome (independente) care pot sau nu să comunice fiecare cu fiecare. Comparativ cu organizarea unei rețele de calculatoare, un sistem multiprocesor este controlat de un același sistem de operare, care asigură interconexiunea între procesoare și toate componentele care concură la realizarea sarcinilor.

Dacă două sau mai multe calculatoare sau procesoare cooperează într-o manieră oarecare atunci putem spune că totalitatea resurselor lor formează un sistem distribuit. De aici sistemele multicalculator, rețelele de calculatoare și și sistemele multiprocesor apar ca și cazuri particulare de sisteme distribuite. Rețelele locale sunt apreciate ca cele mai adecvate și răspândite organizări fizice pentru sistemele cu prelucrare distribuită.

Există numeroase asemănări între sistemele multiprocesor și sistemele multicalculator. Cele mai multe asemănări rezultă din faptul că ambele tipuri de sisteme suportă operații efectuate paralel și/sau concurent.

arhitecturi de sisteme concurente

In acest paragraf ne vom opri asupra unor clasificări ale sistemelor de calcul în general și ale sistemelor concurente, în special.

O proprietate specifică sistemelor paralele și concurente este granularitatea — care reprezintă numărul de procesoare din sistemul respectiv [Braunl, 1993]. Un sistem cu granularitate fină, fine-grained, conține procesoare multe și nu foarte puternice. Dacă proprietatea se referă la o aplicație paralelă sau concurentă, atunci granularitatea măsoară numărul de procese, respectiv numărul de operații elementare asociate unui proces. Astfel, o aplicație paralelă de granularitate fină va lucra cu multe procese, fiecare conținând puține operații elementare.

La nivelele inferioare, low-levels, paralelismul este mai mult fine-grained, în timp ce la nivelele superioare este coarse-grained.

Fiecare nivel lucrează cu aspecte diferite ale procesului de paralelizare. Metodele și constructorii de la un nivel au aplicabilitate limitată la acel nivel și, în general, nu se pot aplica la alte nivele.

In tabela următoare [Braunl, 1993] punem în evidență patru nivele de abstractizare pentru abordarea conceptului de paralelism. Dintre aceste nivele se remarcă nivelul procedură, care corespunde paralelismului asincron, de tip coarse-grained și nivelul expresie, care corespunde paralelismului sincron, de tip fine-grained.

Un element important în tratarea fiecărui nivel este entitatea de calcul care prelucrează datele. De acest element depinde ulterior programarea aplicației pe baza căreia funcționează sistemul paralel respectiv.

Nivelul program. La acest nivel se execută simultan programe complete, cosiderate indivizibile. Calculatorul nu trebuie să fie unul paralel, dar sistemul de operare trebuie să fie multitasking, de exemplu implementat în time-sharing.

Nivelul procedură. La acest nivel, secțiuni diferite ale aceluiași program sunt executate în paralel. Aceste secvențe de program în execuție sunt numite procese și corespund procedurilor din calculul secvențial. La acest nivel problemele sunt împărțite în subprobleme, care au între ele un grad mare de independență, astfel încât să se minimizeze schimbul de date între procese.

Tabel 1. Nivele de paralelism

Domeniile de aplicabilitate ale tratării paralelismului la nivel de proces, respectiv de procedură, ar fi: programarea în timp real, programarea sistemelor destinate controlului proceselor, procesarea paralelă cu scop general (general purpose parallel processing). Acest ultim domeniu cuprinde situațiile în care se caută îmbunătățirea performanțelor unui sistem/aplicație prin descompunerea unei probleme în subprobleme care pot fi distribuite surjectiv pe procesoare distincte.

Nivelul expresie. La acest nivel aplicația tratează expresiile aritmetice de evaluat în paralel, pe componente. Acestea pot fi executate în taskuri simple, sincrone. De exemplu, calcularea unei sume de matrici poate fi foarte ușor privită într-un paralelism sincron prin asignarea calculului fiecărui element al matricei sumă câte unui procesor.

Conceptele folosite la acest nivel sunt vectorizarea și paralelismul datelor.

Nivelul bit. La acest nivel apare execuția paralelă a operațiilor pe biți la nivel de cuvânt de memorie. Acest nivel de paralelism se găsește în orice microprocesor.

Clasificarea dată de Flynn pentru sistemele de calcul

O clasificare importantă și cuprinzătoare a sistemelor de calcul a fost dată de Flynn [Flynn, 1972] și poate fi deosebit de utilă și astăzi pentru prezentarea diferitelor modele de arhitecturi concurente. Această clasificare se bazează pe numărul de fluxuri independente de instrucțiuni și numărul de fluxuri independente de date din sistem.

Flynn a împărțit sistemele în patru tipuri: SISD, SIMD, MISD, MIMD. In continuare vom face câteva considerații pe marginea fiecărei clase de sisteme identificate de Flynn.

Un sistem SISD, Single Instruction stream Single Data stream, este modelul convențional pentru un calculator uniprocesor. Un astfel de sistem va executa o singură secvență de instrucțiuni la un moment dat, asupra unui unic set de date pe care îl primește la începutul execuției. Acesta este modelul original von Neumann pentru funcționarea calculatoarelor.

Practic, orice model serial de abordare a activităților unui sistem conduce către un exemplu de sistem SISD. Acesta poate fi: (1) determinist – dacă ordinea în care sunt executate instrucțiunile este unic determinată de starea variabilelor aplicației de executat sau (2) nedeterminist – dacă activitățile au la un moment dat mai multe variante de continuare a execuției.

Un sistem SIMD, Single Instruction stream Multiple Data stream, conține mai multe elemente de prelucrare, dar care sunt destinate să execute aceeași secvență de prelucrare la un moment dat. De aceea, modelele de procesoare inserate în astfel de sisteme pot fi unele simple: nu trebuie să preia instrucțiuni din memoria proprie ci numai să primească spre prelucrare instrucțiunile de la o unitate centrală (comună) de control. Totuși, aceste procesoare trebuie să poată opera pe date independente, cum ar fi elementele unui vector sau ale unei structuri multidimensionale liniarizată. Orice mașină care poate executa instrucțiuni pentru prelucrarea în paralel a elementelor unui vector poate fi considerată de tip SIMD. Componenta destinată prelucrării vectorilor poate fi un procesor specializat, atașat procesorului central, format din mii de procesoare mici și încărcat numai pentru a executa operațiile cu vectori.

Din punct de vedere practic, există o varietate mare de aplicații care solicită operații cu vectori sau cu matrici. Importanța unor astfel de aplicații poate să conducă la utilizarea unor sisteme de calcul extrem de scumpe și de performante, cum ar fi supercalculatoarele create exclusiv pentru executarea unor activități predefinite.

Sistemele MIMD, Multiple Instruction stream Multiple Data stream, sunt sistemele capabile să execute simultam mai multe preluări și prelucrări de instrucțiuni asupra a diferite seturi de date. Aceste instrucțiuni nu trebuie să fie dependente unele de altele și pot fi executate asincron. Aceasta este o categorie foarte largă de sisteme și include rețelele de calcde instrucțiuni asupra a diferite seturi de date. Aceste instrucțiuni nu trebuie să fie dependente unele de altele și pot fi executate asincron. Aceasta este o categorie foarte largă de sisteme și include rețelele de calculatoare și sistemele multiprocesor rezultate din calculatoare independente.

Observație. Este evident că din clasificarea anterioară lipsește combinația MISD, Multiple Instruction stream Single Data stream, care s-ar referi la un sistem care poate prelucra un același flux de date în mai multe fluxuri (secvențe) de instrucțiuni. La vremea la care Flynn a dat această organizare a sistemelor, categoria MISD se considera a fi vidă. Astăzi, ținând cont în special de posibilitățile oferite de prelucrarea paralelă, se poate constata că sunt suficiente modele care se pot încadra în tipologia MISD. Dintre acestea, probabil unul dintre cele mai reprezentative este execuția de tip pipeline. Chiar funcționarea procesorului poate fi privită ca o execuție în pipeline dacă se consideră următoarele unități funcționale ale procesorului ca fiind faze pipeline: (1) fetch – extragerea următoarei instrucțiuni din programul de executat, (2) decode – decodificarea codului de instrucțiune preluat anterior, (3) execute – executarea microoperațiilor corespunzătoare instrucțiunii decodificate anterior, (4) write-back – scrierea rezultatului în zona de memorie rezervată acestui scop.

Clasificarea dată de Flynn pentru sistemele de calcul poate fi sintetizată în următoarea tabelă [Braunl, 1993]:

Tabel 2. O clasificare a sistemelor concurente

Din această tabelă sintetică se poate observa că numai modelul SISD este ne-specific calculului nesecvențial, fiind asociat cu sistemul uniprocesor.

După interconexiunea dintre procesoare putem detalia clasele MIMD și SIMD astfel:

MIMD – sisteme multiprocesor = sisteme strâns cuplate și sisteme cu comunicare prin memorie partajată

sisteme distribuite = sisteme slab cuplate și sisteme cu comunicare prin schimb de mesaje

SIMD – sisteme vectoriale (vector computer) = sisteme necuplate sau cu „lanț” între elementele de prelucrare

sisteme scalare (array computer) = sisteme cuplate prin conexiuni de rețea.

O clasificare a sistemelor concurente

Concurent înseamnă „în același timp”. [Bacon, 1998]

Un sistem concurent trebuie să gestioneze activități separate, care se desfășoară simultan. Mai exact, vom considera că două activități sunt concurente dacă, la un același moment, fiecare activitate se află într-un punct situat între punctul de start și punctul final al desfășurării sale (ambele activități sunt în desfășurare).

După Bacon [1998], activitățile concurente pot fi privite din două puncte de vedere și anume: din punctul de vedere al structurii interne a sistemului, rezultând sisteme inerent concurente, sau din punctul de vedere al aplicațiilor care stau la baza funcționării sistemului respectiv, rezultând aplicații potențial concurente. In cele ce urmează vom lua în discuție caracteristici ale acestor entități delimitate de Bacon.

Un sistem este inerent concurent dacă gestionează activități care se pot întâmpla simultan în exteriorul sistemului de calcul, de exemplu utilizatori care doresc să execute programe sau clienți care vor să execute tranzacții.

O posibilitate de obținere a concurenței este determinarea soluției prin aplicarea unui algoritm concurent de divizare a problemei în părți care, la rândul lor, pot fi rezolvate prin activități desfășurate în paralel. Această variantă este recomandată pentru aplicațiile cu volum mare de calcule și de date și în care este importantă cerința de obținere a rezultatelor în timp real. Aplicațiile de acest sunt aplicații potențial concurente. Abordarea concurentă îmbunătățește rezolvarea secvențială cel puțin din două puncte de vedere: (1) un același răspuns poate fi obținut la același preț folosind un număr mai mare de calculatoare mai ieftine sau (2) un model mai performant (mai scump) de realizare a sistemului fizic poate conduce la rafinarea rezultatului problemei.

Sisteme inerent concurente

După cum am definit și anterior, sistemele care trebuie să gestioneze simultan activități care se desfășoară în mediul exterior lor sunt cunoscute ca sisteme inerent concurente. Din această categorie fac parte:

sistemele în timp real;

sistemele de gestiune a bazelor de date și de prelucrare a tranzacțiilor;

sistemele de operare.

In fiecare caz, implementarea sistemului este de preferat să fie distribuită pe mai multe sisteme de calcul (host-uri, noduri, site-uri) decât să abordeze o metodologie centralizată de organizare și gestionare.

Sisteme în timp real

Principala caracteristică a sistemelor în timp real constă în faptul că funcționarea lor trebuie să țină cont de anumite restricții de timp impuse de mediul înconjurător sistemului respectiv. Importanța restricțiilor temporale impuse împarte sistemele în timp real în (a) sisteme puternic dependente de timp și (b) sisteme slab dependente de timp.

Din alt punct de vedere, sistemele în timp real pot fi: (a) statice, respectiv (b) dinamice. Intr-un sistem static, analiza activităților pe care sistemul trebuie să le execute poate fi făcută în etapa de proiectare a sistemului. Intr-un sistem dinamic, cererile asupra sistemului pot fi adresate la orice moment de timp, neregulat și imprevizibil. Mai mult, un sistem dinamic trebuie să poată răspunde acestor cereri în timp real și respectând parametrii de performanță impuși de clientul care a adresat cererea.

Cele mai reprezentative exemple de sisteme în timp real sunt cele proiectate pentru controlul proceselor, de exemplu sisteme de monitorizare a pacienților unei unități sanitare, sisteme de monitorizare a zborurilor, a motoarelor vehiculelor, sisteme de control al traficului aerian, controlere pentru roboți, sisteme de procesare și vizualizare de imagini în timp real etc..

In astfel de sisteme de control la nivel de proces (process control) scenariul comun de funcționare se bazează pe faptul că datele sunt colectate – prin controlul (testarea) sistemelor care generează acele date – și apoi analizate prin algoritmi specifici. Atât colectarea cât și analiza acestor date sunt evenimente periodice și previzibile. Totuși, această activitate periodică de colectare și analiză trebuie să poată răspunde unor evenimente neprevăzute. Astfel, se remarcă două tipuri de activități: de monitorizare și de control. Monitorizarea implică colectarea datelor, în timp ce controlul implică corelarea periodică și eficientă a datelor, atât cu scopul funcționării sistemului, cât și cu cererea clientului care așteaptă un răspuns din partea sistemului.

Sistemele de control la nivel de proces sunt sisteme în timp real puternic dependente de timp și statice.

Proiectarea sistemelor în timp real trebuie să prevadă situațiile limită în care sistemul însuși trebuie să decidă importanța evenimentelor neprevăzute care apar. Astfel, sistemul trebuie să poată decide la un moment dat dacă este mai important să monitorizeze datele astfel încât rezultatele să fie de o precizie maximă sau este de preferat diminuarea preciziei și furnizarea răspunsului într-un timp minim posibil, eventual chiar în timp real.

Caracterul concurent al acestor sisteme rezultă cel mai adesea tocmai din faptul că mai multe calculatoare mici sunt corelate astfel încât să controleze un proces industrial sau experimental de dimensiune și/sau de importanță mare.

Nu toate sistemele în timp real sunt sisteme distribuite de tip multicalculator. De exemplu, o aplicație simplă, un robot, un motor de vehicul pot încapsula un singur calculator de control, pentru care partea de software va asigura singură atât monitorizarea cât și controlul întregului sistem. Mai mult, aplicațiile sunt distribuite dacă sunt scrise astfel încât să permită desfășurarea simultană a mai multor activități distincte.

O altă clasă de sisteme în timp real sunt sistemele multimedia. Spunem despre un sistem că este multimedia dacă are posibilitatea să îmbogățească afișarea clasică prin text și grafică cu imagini în mișcare și/sau voce. Presupunând că o stație de lucru are un sistem de navigare bazat pe ferestre, unele ferestre pot fi folosite pentru video. Multe aplicații, cum ar fi: telefonia-video, poșta-video sau videoconferințele trebuie să afișeze în timp real o persoană care vorbește. In acest caz partea video (imaginea) și partea audio (vocea) trebuie să se sincronizeze astfel încât, pe ecranul participanților la comunicare acestea să ajungă simultan (vocea trebuie sincronizată în special cu mișcarea buzelor vorbitorului filmat).

Videoconferințele și telefonia-video funcționează în timp real. Dacă sistemul nu memorează nici un fel de date, acestea sunt pierdute după încheierea transmisiei. Poșta-video presupune transmiterea de mesaje electronice care pot conține text, combinat cu voce și cu imagini în mișcare. Aici componentele acestea trebuiesc memorate și transmise la stația care va recepționa mesajul. O dată ce este declanșat procesul de citire a mesajului, sistemul trebuie să respecte anumite cerințe specifice caracterului de sistem în timp real cu privire la transmiterea sincronizată a componentelor și la minimizarea ratei de întârziere. Probleme de sincronizare în sistemele multimedia sunt dezbătute în [Bacon, 1998].

Stațiile multimedia sunt considerate sisteme în timp real cu atât mai mult cu cât, într-o transmisie de telefonie-video, de exemplu, datele alterate pot fi retransmise numai dacă intervine explicit o voce umană care să ceară repetarea lor. De aici rezultă că un sistem multimedia este unul slab dependent de timp.

Sistemele multimedia își au originea în sistemele cu timp partajat (timesharing). Diferența este una cantitativă deoarece un sistem multimedia solicită o putere de prelucrare mai mare, lățime de bandă de rețea, capacitate de memorare mai mare și aplicații soft care să poată valorifica aceste facilități.

Comparând un astfel de sistem slab dependent de timp cu un sistem de control se remarcă o diferență calitativă deoarece într-un sistem de control este mult mai restrictivă cerința ca răspunsul primit să fie în timp real, un sistem de control fiind unul puternic dependent de timp.

In concluzie, cerințele care se impun pentru realizarea unui sistem în timp real ar putea fi:

să suporte activități independente; dintre acestea, unele pot fi periodice (cum este colectarea de date) sau neprevizibile (cum este cerința de a răspunde la un semnal de tip alarmă);

să respecte cerințele fiecăreia dintre activitățile în desfășurare;

să aibă în vedere posibilitatea ca unele activități să poată coopera pentru satisfacerea unor scopuri comune.

Sisteme de gestiune a bazelor de date și de prelucrare a tranzacțiilor

Aplicațiile de baze de date vizează un volum mare de date, cum ar fi datele stocate pe medii permanente. Acțiunea specifică a unui utilizator de baze de date constă în interogări asupra datelor din acea bază de date. Spre deosebire de un utilizator, proprietarul bazei de date se preocupă de întreținerea bazei de date, astfel încât datele conținute să respecte caracteristicile unei baze de date consistente, actuale, sigure, corecte.

Prin sistem de gestiune a bazelor de date (DBMS DataBase Management System) ne referim la un sistem de date proiectat să interacționeze cu utilizatorii săi și să organizeze citirile și scrierile de date în sistem astfel încât să răspundă optim cerințelor utilizatorilor. Un sistem DBMS este unul concurent deoarece trebuie să satisfacă simultan cerințele mai multor utilizatori.

In cele ce urmează, prin tranzacție denumim generic o cerere a unui client adresată bazei de date. Cel mai simplu exemplu de sistem de prelucrare a tranzacțiilor este serviciul oferit de un automat bancar (ATM Automatic Teller Machine).

Considerente legate de proiectarea și organizarea sistemelor de tip DBMS se pot găsi în [Bacon, 1998]. O problemă importantă care apare în DBMS constă în soluționarea conflictelor generate la nivelul cererilor (interogărilor) adresate bazei de date. Accesul concurent este o soluție viabilă atât timp cât acesta reușește să scadă timpul de răspuns al DBMS la cererile utilizatorilor. Mai mult, din punctul de vedere al bazei de date, tranzacțiile care numai citesc date se pot executa în paralel, indiferent de numărul acestora.

In contextul celor prezentate anterior, un exemplu de aplicație reprezentativă este problema cititor-scriitor.

Pentru realizarea unui sistem de gestiune a bazelor de date și de prelucrare a tranzacțiilor se impun câteva cerințe importante cum ar fi:

să suporte activități independente;

să asigure posibilitatea ca activități diferite să poată accesa și actualiza date comune, dar numai în limitele păstrării consistenței și corectitudinii bazei de date;

să asigure că rezultatele tranzacțiilor au fost depozitate în zone de securitate maximă, înainte ca utilizatorul să fie anunțat că tranzacția s-a încheiat cu succes.

Sisteme de operare și sisteme de operare distribuite

In acest context este important să se deosebească un calculator destinat unui utilizator de un calculator multiuser. In prima categorie intră orice sistem de calcul de la calculatorele personale mici și relativ ieftine până la stațiile de lucru cuprinse în rețele de calculatoare. Sistemele multiuser sunt formate din mai multe minicalculatoare sau microcalculatoare performante, destinate fiecare unui număr mic de utilizatori, sau din mai multe sisteme multiprocesor de tip mainframe sau supercalculatoare. Fiecare dintre aceste structuri se bazează pe configurații hardware specifice, în concordanță cu caracterul concurent al aplicațiilor pe care le vor suporta.

Intr-un sistem singleuser tastatura și ecranul utilizatorului sunt „împachetate” împreună cu memoria și procesorul/procesoarele sistemului, rezultând astfel un singur sistem de calcul. Utilizatorii unui sistem multiuser accesează sistemul prin intermediul unui terminal. Terminalele sunt separate de memoria principală, de procesoarele centrale și de perifericele partajate în sistem. Funcțiile unui terminal sunt de obicei orientate pe anumite tipuri de activități, de exemplu un terminal poate dezvolta o aplicație de grafică sau un sistem de navigare bazat pe ferestre. Pentru executarea acestor funcțiuni, un terminal poate avea propria memorie internă și propriile procesoare. Se remarcă de aici că terminalul clasic format din monitor și tastatură este completat cu componente care să-l transforme într-un calculator cu destinație pre-fixată (special-purpose computer). Un sistem multiuser poate avea un număr mare de terminale, chiar situate la distanță față de un calculator central și care sunt gestionate în grup prin terminale speciale.

Un sistem de operare de interes general rulează pe calculatoare personale, pe stații de lucru monoutilizator sau pe sisteme partajate. Scopul unui astfel de sistem de aplicații este să execute programele utilizatorilor și să aloce acestor aplicații resursele hardware solicitate (memorie, discuri, procesoare etc.).

Pricipalele caracteristici ale unui sistem concurent se regăsesc bine reprezentate atât în sistemele singleuser cât și în sistemele multiuser moderne. Putem să dăm două argumente în susținerea acestei afirmații: pe de o parte faptul că perifericele tind spre o structură care le apropie de organizarea pe nivele a procesoarelor și, pe de altă parte, sistemul de operare, direct răspunzător de starea perifericelor, poate să execute programe- utilizator cât timp perifericele execută diverse operații de intrare-ieșire.

Mai mult, într-un sistem singleuser, cât timp se execută o activitate de durată mai lungă (de exemplu paginarea unui document foarte mare) utilizatorul poate lansa în paralel execuția altor taskuri (de exemplu, citirea ultimelor mesaje sosite prin e-mail). Pentru aceasta, sistemul de operare trebuie să poată suporta simultan astfel de activități distincte, concurente, prin rularea de aplicații diferite odată cu gestionarea diferitelor componente din sistem.

Caracterul de sistem concurent este mai puternic la nivelul sistemelor multiuser prin executarea simultană a mai multor aplicații utilizator, prin paralelizarea desfășurării taskurilor perifericelor cu satisfacerea comenzilor curente ale utilizatorilor sistemului.

Tinând cont de clasificarea anterioară a sistemelor concurente, putem spune că sistemele de operare gestionează evenimente care sunt mai degrabă neregulate și neprevizibile decât periodice, iar procesul de încărcare a datelor de intrare/ieșire este unul dinamic. In plus, considerațiile de timp în sistemele de operare sunt importante, dar nu de o importanță majoră și inflexibile ca în sistemele în timp real.

In plus față de considerațiile făcute la nivelul unui sistem singleuser, pentru un sistem multiuser sistemul de operare (1) trebuie să gestioneze partajarea resurselor sistemului între diverși utilizatori astfel încât să le ofere tuturor aceeași calitate a serviciilor, (2) trebuie să răspundă oricăror conflicte care pot să apară între cererile utilizatorilor asupra resurselor sistemului (memorii, timp de prelucrare, spațiu rezervat fișierelor). Cererile adresate sistemului de operare apar în mod dinamic și unele pot implica o serie de componente adiacente sistemului, pe care tot sistemul de operare trebuie să le gestioneze.

Dacă sistemul multi-utilizator este unul distribuit atunci se adaugă noi valențe sistemului de operare. De exemplu, apare posibilitatea ca mai mulți utilizatori să partajeze același sistem de fișiere. De aici, sistemul de operare trebuie să poată gestiona centralizat fișierele comune, trebuie să aibă prevăzute mecanisme specifice de protecție față de erorile de disc sau căderile soft. Pentru toate aceste motive este de preferat ca sistemul de fișiere să fie furnizat ca un serviciu de rețea (network-based service). De asemenea, este de preferat ca un număr rezonabil de servere de fișiere să poată furniza suficient spațiu de memorare și capacitate de prelucrare pentru toate calculatoarele din sistemul distribuit și nu numai pentru sistemele mici. Aceste servere partajate trebuie să răspundă cererilor simultane ale diferiților clienți, deci sunt sisteme concurente.

Sistemele de operare ale calculatoarelor care fac parte din sisteme distribuite trebuie să conțină soft pentru comunicare. La nivelul cel mai scăzut, gestionarea unei conexiuni de rețea este o acțiune similară cu gestionarea unui periferic de viteză foarte mare. Diferențele apar mai ales din faptul că datele care sunt lansate în rețea pot fi expediate de oricare dintre stațiile distribuite și nu numai de la un singur periferic. Calculatoarele pot trimite în sistem date sau mesaje de mare viteză, ceea ce face ca simultan pe canalele de comunicație să se transmită secvențe de date de la diferite surse. La nivelele înalte ale gestionării comunicării în sistemele distribuite se pune problema corectitudinii și completitudinii datelor transmise. Gestionarea acestor situații este un argument în favoarea afirmației că însuși subsistemul de comunicare din cadrul unui sistem de operare distribuit este un sistem concurent.

In concluzie, principalele cerințe pentru realizarea unui sistem de operare ar fi:

să suporte activități independente la nivelul aplicație (deci în exteriorul sistemului de operare), fie mai multe activități ale unui singur utilizator, fie diferite activități ale mai multor utilizatori; cererile pe care aplicațiile le adresează sistemului de operare sunt dinamice și neprevizibile;

să suporte activități diferite în interiorul aplicațiilor sale de tip: cereri simultane de la mai mulți clienți ai sistemului și diverse taskuri de gestionare a componentelor distribuite în sistem;

să permită diverselor activități să coopereze pentru obținerea unor scopuri comune;

să gestioneze conflictele care apar la alocarea resurselor din sistem;

să asigure păstrarea corectitudinii datelor din sistem în urma operațiilor de intrare/ieșire asupra acelorași zone de memorie;

să asigure corectitudinea execuției unei activități, chiar dacă aceasta a fost descompusă în mai multe taskuri care au fost executate paralel sau concurent cu taskurile altor activități.

Servere de informare

Serverele de informare sunt cazuri particulare de sisteme inerent concurente, cel mai bine fiind reprezentate de serverele de WEB.

In 1990 Tim Berners-Lee a dezvoltat un sistem standard de tip hipermedia, numit World Wide Web, pe scurt, WWW. Domeniul de aplicare inițial a fost fizica nucleară, la centrul CERN, Elveția. Esența sistemului consta în faptul că nucleul sistemului îl reprezenta partea de comunicare în rețea și astfel se crease posibilitatea transferului în sistem a paginilor hipermedia, fără restricții (world wide).

In 1993 centrul NCSA (National Center for Supercomputing), Universitatea din Illinois, a dezvoltat browserul Mosaic. Importanța și noutatea acestei aplicații era interfața comodă, orientată pe ferestre, care recunoștea transferul paginilor hipermedia într-un sistem de informare. Incepând cu Mosaic, amploarea pe care au luat-o sistemele de tip WWW a fost explozivă. Enorm de multe companii, universități și particulari și-au construit servere de informare care să poată fi citite (vizitate) de oricine are un browser de navigare.

Fiecare pagină hipermedia poate să conțină text, imagini și legături către alte pagini. O astfel de pagină este creată folosind un limbaj de marcare de tip HTML (HyperText Markup Language), care este similar cu limbajul standard SGML. In plus față de SGML, limbajul HTML are și instrucțiuni referitoare la modul de afișare a paginii create.

Intr-un server de informare cum este WWW fiecare pagină este identificată printr-un nume, adică o adresă URL (Universal Resource Locator), care se folosește ca legătură (link) către pagina respectivă. Dacă o pagină P-părinte trebuie să vadă (să conțină o legătură către) o altă pagină, P-copil, atunci în pagina P-părinte afișată vom avea un text de legătură (highlighted) către pagina P-copil. In același timp, codul HTML al paginii P-părinte va conține atât textul de legătură cât și adresa URL a lui P-copil. Deci, în pagina părinte nu apare obligatoriu adresa URL a paginii copil. Pentru a deschide pagina copil, este suficient un click de mouse pe textul de legătură (link) din pagina părinte. Pentru a localiza pagina copil, browserul contactează serverul care conține pagina identificată de linkul ales pe pagina părinte, transferă informația furnizată de acel server și o afișează în locul paginii părinte. Protocolul de comunicare respectat de browserul de web și de serverul de web implicate în secvența de operații anterioare este numit http, hypertext transfer protocol.

Fiecare client (browser) lucrează secvențial, putând să vizualizeze (să afișeze) la un moment dat o singură pagină. Un server oarecare poate să primească concurent oricâte cereri de furnizare de pagini de informații. Deci avem aici un alt exemplu în care serverul poate să aibă mai mulți clienți simultan.

O extindere recentă în tehnologia paginilor web este adăugarea de secvențe animate pe pagini, scrise de obicei în limbajul de programare Java. Aici prelucrarea concurentă poate fi făcută la nivelul clientului pentru a mări viteza de animare și pentru a permite animației să co-existe pe pagină în paralel cu acțiunile utilizatorului, de exemplu cu perioada de încărcare a unei forme pe pagina curentă.

Aplicații potențial concurente

Față de sistemele inerent concurente (concurente prin structura internă a componentelor lor), sistemele care funcționează pe baza aplicațiilor potențial concurente nu sunt sisteme concurente prin structura lor, ci dobândesc caracteristici de sisteme concurente prin natura aplicațiilor pe care le execută.

Caracterul concurent al unei aplicații poate să rezulte din unul dintre următoarele aspecte:

există un volum mare de calcule care trebuiesc efectuate;

există un volum mare de date care trebuiesc prelucrate;

se impune cerința ca rezultatul aplicației să fie furnizat în timp real;

echipamentele hardware permit o eventuală execuție în paralel a activităților concurente.

In cele ce urmează vom aborda câteva tehnici de obținere a unei soluții concurente pentru o problemă dată. Exemple concrete de utilizare și implementare a acestor metode se găsesc în [Bacon, 1998], [Quinn, 1994].

Replicarea codului. Partiționarea datelor

Replicarea (multiplicarea, copierea) codului și partiționarea (împărțirea) datelor sunt două metode prin care un algoritm secvențial poate primi caracteristici de algoritm concurent.

Prin partiționare, volumul mare de date pe care trebuie să le prelucreze aplicația concurentă se împarte în secvențe distincte, fiecare secvență fiind ulterior prelucrată de un alt proces/procesor. Programul de prelucrare poate să fie același sau se poate ca partiții diferite să fie prelucrate de programe diferite. In cazul în care programul de prelucrare este unic, se poate prevedea ca fiecare prelucrare să se execute pe baza unei copii a programului respectiv, adică să se aplice o replicare a codului programului de prelucrare.

In figura următoare este reprezentată situația în care soluția concurentă presupune atât partiționarea datelor, cât și replicarea codului.

Figura 1. Replicarea codului. Partiționarea datelor

Intr-o astfel de abordare, dacă toate componentele trebuie să funcționeze până la terminarea taskurilor proprii, atunci timpul total de funcționare este egal cu timpul de inițializare a execuției paralele, plus timpul maxim necesar componentei celei mai costisitoare de timp, plus timpul de sincronizare a rezultatelor componentelor. Un timp optim se obține dacă împărțirea pe componente se poate face astfel încât componentele să solicite timpi relativ egali de funcționare (astfel timpii de așteptare sunt reduși la minim). Această situație este cea care maximizează și concurența pentru execuția acelui algoritm.

Această metodă statică de partiționare este potrivită pentru probleme de găsire a unor clase particulare de puncte pentru funcții date (rădăcini, puncte de întoarcere).

Față de situația descrisă anterior, pentru unele probleme este important ca odată ce una din componente își încheie execuția, algoritmul să decidă încheierea execuției și pentru toate celelalte componente. In acest caz se modifică considerabil timpul total de execuție a algoritmului. Pentru aceeași clasă de probleme, această soluție este potrivită atunci când este suficient să se găsească o primă soluție a problemei.

Prelucrarea datelor în pipeline

O altă abordare simplă a concurenței este prelucrarea în pipeline. Aceasta presupune că ansamblul activităților care trebuie aplicate datelor poate fi împărțit în faze de prelucrare distincte, astfel încât diferite secvențe de date să treacă în flux de la o fază la alta.

Un exemplu clasic de prelucrare în pipeline este realizarea unui compilator pentru care fazele de lucru sunt: analiza lexicală, analiza semantică, verificarea tipurilor de date, generarea de cod s.a.m.d. Aici, imediat ce un modul a trecut de analiza lexicală el este trimis în faza de analiză semantică și automat un al doilea modul este încărcat pentru analiza lexicală.

In acest model este important că diferite activități sunt simultan în execuție în diferite faze ale lor și trebuie să se sincronizeze între ele: să aștepte ca noile date să devină disponibile sau, din contră, să aștepte ca faza următoare să-și termine procesul asupra datelor curente.

Algoritmi cu structură arborescentă a spațiului de soluții

Mulți algoritmi pot fi reprezentați într-o structură arborescentă a spațiului lor de soluții. In aceste cazuri oportunitatea procesării paralele este imediată dacă ramuri diferite ale arborelui de reprezentare sunt independente. Aplicațiile potrivite pentru acest model sunt problemele de căutare. Cazul cel mai nefavorabil (traversarea întregului spațiu de soluții) este atins numai dacă problema nu admite soluție. Altfel, algoritmul trebuie să decidă încheierea activităților ramurilor odată ce pe una din ramuri a fost găsită soluție.

Acest model este de asemenea potrivit pentru abordarea problemelor de recunoaștere a formelor. Aici fiecare ramură de executat în paralel va putea fi traversată în mod repetat deoarece există alternative diferite pentru atingerea unei soluții (cazuri nedeterministe). Mai mult, aici fiecare ramură poate avea asociată o probabilitate cu care să conducă la soluție. In acest caz, algoritmul trebuie să vizeze și selectarea combinației de ramuri care conduc la cea mai bună probabilitate de obținere a unei soluții.

O structură arborescentă de abordare introduce noi aspecte de paralelism față de caracteristicile simple, statice, de partiționare liniară descrise anterior. O problemă nouă care se ridică aici este cum să se construiască dinamic un număr rezonabil de activități paralele și pentru fiecare să se păstreze evidența proceselor proprii și a procesoarelor implicate.

Partajarea datelor

In sistemele de gestiune a tranzacțiilor se impune accesul diferitelor tranzacții la aceleași date comune. Există cazuri particulare de sisteme în care datele nu pot fi partiționate (într-un sistem de rezervare a biletelor nu este eficient să se distribuie pentru vânzare locuri diferite la case de bilete diferite). Caracterul concurent al unor astfel de aplicații poate fi atins nu prin simpla partiționare a datelor ci prin partajarea datelor între mai multe procese din sistem. O situație specifică pentru această abordare este următoarea: întreaga sarcină de efectuat este împărțită în activități și este reținută într-o zonă comună de memorie ca o structură de date care poate fi folosită în comun de diferite entități. Fiecare activitate citește o lucrare din structura comună de date, o marchează ca fiind luată spre execuție și o trimite spre execuție activității specifice.

O problemă care se ridică este evitarea deteriorării datelor odată cu accesul cocurent la zona comună.

Cerințe pentru realizarea aplicațiilor concurente

Aceste câteva abordări simple ale caracterului concurent la nivelul algoritmilor pun accent pe partiționarea datelor static sau dinamic, respectiv pe partiționarea codului într-o structură de tip pipeline. In general, acestea sunt opțiunile programatorului care are de abordat un sistem potențial concurent. Pentru sistemele inerent concurente, soluția cea mai potrivită folosește partajarea datelor.

La nivelul aplicațiilor, se pot enunța câteva cerințe prin care să se impună caracterul concurent al soluției problemei de rezolvat. Astfel, aplicațiile trebuie:

să suporte activități individuale;

să poată gestiona aceste activități de o manieră similară; aceste activități trebuie să poată fi create la cerere și întrerupte când nu mai sunt necesare;

să sincronizeze diferite activități care se desfășoară simultan; să asigure posibilitatea transferului de date între activitățile simultane;

să se adapteze fiecărei situații particulare de tip: activitățile pot partaja date sau, din contră, trebuiesc impuse restricții de acces comun la anumite date.

Aplicațiile vor fi scrise într-un limbaj de programare care, împreună cu sistemul de operare gazdă, să aibă facilități de implementare a condițiilor de mai sus.

O altă clasificare a sistemelor concurente

In acest paragraf vom aborda o clasificare a sistemelor concurente, [Bacon, 1998], care deosebește sistemele convenționale de cele experimentale. Din acest punct de vedere se remarcă trei categorii de sisteme: (1) sisteme pentru dirijarea controlului (control-driven), (2) sisteme pentru dirijarea fluxului de date (data-driven) și (3) sisteme interogative (demand-driven).

Modelul convențional von Neumann este unul de tip 1, de dirijare a controlului: procesorul preia și execută o secvență de instrucțiuni în timp ce un contor de program (program counter) joacă rol de controller de secvență. In astfel de sisteme, posibilitatea execuției în paralel a unor secvențe de instrucțiuni este o problemă care poate fi rezolvată numai ținând cont de specificul sistemului respectiv. Mai mult, se pune întrebarea cum se pot identifica instrucțiunile care, din punct de vedere al semanticii aplicației, se pot executa în paralel.

Alte modele de dirijare a controlului sunt sistemele convenționale uniprocesor, sistemele multiprocesor bazate pe memorie partajată și sistemele multiprocesor- multicalculator. O caracteristică majoră a acestor modele constă în faptul că permit mărirea numărului de componente ale sistemului.

Modelele bazate pe dirijarea fluxului de date și modelele interogative sunt reprezentate de arhitecturi specifice dintre care se remarcă mașinile suport pentru aplicațiile scrise în limbaje funcționale. [Bacon, 1998]

Realizarea sistemelor concurente rezultă și prin utilizarea unei structuri hardware specifice. Astfel, un model hard de bază care să suporte aplicații concurente ar putea fi cel din figura următoare. Săgețile din această reprezentare arată direcția în care crește caracterul concurent, pe măsură ce se dezvoltă noi componente în sistem.

Figura 2. Topologii de sisteme concurente

Din această figură se observă că arhitecturile bazate pe flux de date și aplicațiile funcționale sunt alternative pentru mașinile convenționale von Neumann. Este de așteptat ca acestea să exploateze toate aspectele de concurență ale sistemului și ale aplicațiilor corespunzătoare, mai mult decât este posibil în sistemele convenționale, în care concurența a apărut ca o completare oarecum forțată.

Pe axa centrală a reprezentării anterioare se pornește de la un sistem uniprocesor care se completează până la sistemele multiprocesor- multicalculator. Caracteristica esențială a arhitecturilor din această grupă rezultă din creșterea progresivă a puterii de calcul a sistemelor respective. Procesoarele dedicate pot gestiona diferite componente, dar un model consistent apare când sunt folosite procesoare diferite pentru a executa programe rezidente în același spațiu de memorie.

Rețelele de calculatoare apar ca o alternativă pentru structurile complexe de interconectare necesare în sistemele multicalculator și multiprocesor. O rețea medie de tip LAN poate fi folosită pentru conectarea completă a unui număr rezonabil de calculatoare în care comunicarea este realizată mai mult prin software specific, decât prin protocoale la nivel hardware. Pe măsură ce rețeaua LAN este completată cu noi resurse, calculatoarele astfel conectate pot fi folosite pentru prelucrări distribuite, permise (limitat numai) de softul de comunicare și de componentele sistemului de operare gazdă.

Ori de câte ori se pune problema creării unei arhitecturi noi de sisteme de calcul se va avea în vedere exploatarea unor resurse de prelucrare puternice și ieftine, a unor spații de memorare cu acces rapid și de capacitate mare, a unor medii de comunicare cu lărgime de bandă suficientă pentru a asigura o bună funcționare a întregului sistem. Pe de altă parte, se va căuta valorificarea structurilor existente, atât în ceea ce privește arhitecturile sistemelor deja recunoscute, cât și topologiile de interconectare cunoscute și verificate.

Pentru sisteme particulare, evident că se vor experimenta modele noi de arhitecturi interne și topologii de interconectare.

o definiȚie a sistemului concurent

In considerentele anterioare s-au evidențiat o serie de abordări intuitive ale noțiunii de concurență, rezultate în special din exemplificarea diferitelor tipuri de sisteme de calcul care recunosc activități care sunt simultan în execuție. Caracterul concurent a rezultat din două aspecte diferite: fie mai multe secvențe ale codului unui algoritm concurent sunt în curs de execuție în paralel, fie datorită faptului că mai mulți clienți pot interoga sistemul simultan. In oricare dintre situații, sistemul concurent este mai degrabă unul distribuit pe mai multe calculatoare decât unul centralizat pe un singur sistem de calcul.

Definirea conceptului de funcționare „în același timp” se poate da corect numai în contextul în care se consideră timpul ca element esențial în funcționarea unui sistem concurent.

In sistemele concurente sunt importante aplicațiile de sistem (software systems), implementate pe diverse configurații hardware, care suportă desfășurarea simultană a mai multor activități. Aceste activități sunt dependente în diferite sensuri și presupunem că, la nivelul lor, se poate defini un scop comun care devine obiectivul funcționării întregului sistem concurent. Acesta poate fi foarte general – de exemplu, sistemul să suporte activitățile independente ale diferiților utilizatori ai sistemului de operare – sau foarte precis – cum ar fi un sistem concurent realizat pentru a găsi cea mai frecventă parte de vorbire care apare într-o codificare de date lingvistice.

In situații diferite, relațiile dintre activitățile independente pot fi diferite. Pot apărea relații de cooperare pentru atingerea unui scop comun, de competiție pentru utilizarea resurselor, de interacțiune cu mediul exterior în sistemele interactive, de respectare a unor restricții temporale ș.a.m.d.

Din punctul de vedere al utilizării memoriei disponibile în sistem, activitățile pot folosi numai memoria principală a unui singur calculator (când activitatea este de tip „încarcă și mergi mai departe” – load and go) sau pot avea acces la memoriile principale ale mai multor stații din sistemul distribuit. Mai mult, sunt situații în care accesul activităților este permis atât la nivelul zonelor de memorie principală, cât și la memoriile permanente de tip disc (de exemplu într-un sistem de fișiere care gestionează discul fix).

Ansamblul tuturor acestor caracteristici ale activităților unui sistem asigură acelui sistem caracterul de sistem concurent.

Proprietățile de atomicitate și granularitate

Abordarea sistemelor concurente ridică o serie de probleme care pot fi rezolvate numai apelând la entități specifice. Din acest punct de vedere trebuie spus că tratarea concurenței trebuie să facă distincție între acțiuni concurente singulare (single concurrent actions) și acțiuni concurente compuse (concurrent composite actions). Putem defini o acțiune singulară ca fiind o operație de citire sau de scriere din/în memoria principală, dar problematica sistemelor concurente nu se poate folosi numai de acest tip de operații. Un motiv ar fi simplul fapt că procesele concurente sunt corect și complet descrise prin astfel de operații singulare numai dacă se poate presupune că orice operație este garantată de resursele hardware că este indivizibilă, adică atomică. Ori această condiție este prea restrictivă în condițiile unui sistem concurent general. De aceea, definiția unei acțiuni concurente singulare trebuie extinsă la operații de nivel mai înalt decât citirea/scrierea din memorie.

După Andrews [1991], o acțiune atomică este o secvență de una sau mai multe stări care apare ca fiind indivizibilă, în sensul că nici un proces extern ei nu are acces (nu vede) vreuna dintre stările intermediare. Detaliind, Andrews definește două tipuri de acțiuni atomice: (1) o acțiune atomică este de granularitate fină dacă poate fi implementată direct printr-o instrucțiune mașină unică sau (2) o acțiune atomică poate fi o secvență de acțiuni atomice de granularitate fină, indivizibilă.

O acțiune concurentă compusă rezultă prin combinarea acțiunilor singulare într-o operație de nivel înalt. Considerentele legate de aceste aspecte ale concurenței deschid două direcții distincte și anume: (1) legarea acestor noțiuni de structura modulară a softului unui sistem, în particular de tipurile abstracte de date recunoscute la nivelul sistemului respectiv și (2) stabilirea legăturilor între acțiunile singulare astfel încât să se poată decide dacă ele pot forma sau nu acțiuni compuse.

[Andrews, 1991] O acțiune atomică face o transformare de stare indivizibilă. Aceasta înseamnă că orice stare intermediară care ar putea să existe în implementarea acțiunii nu trebuie să fie vizibilă de alte procese.

Proprietatea de granularitate (definită și la începutul capitolului al doilea) reprezintă numărul de procesoare din sistem sau, dacă se referă la o aplicație, atunci granularitatea reprezintă numărul de procese care compun aplicația respectivă.

O acțiune atomică fine-grained este una care este implementată direct de hardware-ul sistemului pe care se execută programul concurent.

Uneori este nevoie să folosim un mecanism de sincronizare pentru a construi o acțiune atomică coarse-grained – care este o secvență de acțiuni atomice fine-grained care apare ca fiind indivizibilă.

Exemple.

presupunem că o bază de date conține două valori x și y și că aceste valori trebuie să fie în fiecare moment egale. Cu alte cuvinte, nici un proces nu are acces la baza de date dacă x y. Pentru a asigura această restricție, orice proces care modifică valoarea lui x trebuie să modifice și valoarea lui y, ca parte a aceleiași acțiuni atomice.

Fie un proces care inserează elemente într-o coadă reprezentată printr-o listă de legături. Un alt proces extrage (removed) elemente din listă, presupunând că există elemente în listă. Două variabile pointează la capul și, respectiv, la coada listei. Valorile acestor variabile sunt modificate o dată cu executarea operației de inserare, respectiv de extragere a elementelor din listă. Dacă lista conține un singur element atunci o inserare și o extragere simultane pot creea conflicte, lăsând lista într-o stare instabilă (unstable state). De aceea, inserarea și, respectiv, extragerea elementelor din listă trebuie să fie acțiuni atomice. Mai mult, dacă lista este vidă atunci trebuie să se întârzie executarea unei extrageri până când se va fi executat o inserare.

Toate aceste aspecte legate de caracterul concurent al unui sistem se regăsesc în capitolele următoare, tratate din diferite puncte de vedere.

Proprietățile de siguranȚĂ Și vivacitate

Un atribut adevărat pentru oricare execuție a unui program este o proprietate a programului respectiv. Orice proprietate se poate exprima pe baza a două proprietăți speciale și anume:

Siguranța (safety) și

Vivacitatea, viabilitatea (liveness) [Andrews, 1991], [Georgescu, 1996], [Bacon, 1998].

In general, un program este sigur dacă „nu se întâmplă nimic rău în timpul execuției“ și este viabil dacă „este de așteptat să apară un rezultat bun”.

Un program secvențial este sigur dacă starea finală este corectă și este viabil dacă execuția lui se termină.

Caracterul nedeterminist al programelor concurente nu ne permite să extindem cu ușurință aceste fomulări de la programele secvențiale la programele concurente. De aceea, pentru un program concurent, definițiile proprietăților de siguranță și viabilitate vor folosi conceptele specifice aplicațiilor concurente. Astfel, siguranța unui program concurent constă în asigurarea excluderii mutuale și absența interblocării (interblocarea apare când procesele așteaptă îndeplinirea unor condiții care nu pot fi satisfăcute), iar viabilitatea se exprimă prin faptul că un proces în așteptare va fi semnalizat în curând și astfel va putea să-și continue execuția.

Viabilitatea unui program concurent depinde de:

2a. corectitudinea alocării resurselor (fairness) – ceea ce se exprimă prin faptul că un proces va obține șansa de a intra în execuție, independent de starea altor procese;

2b. așteptarea activă (starvation) – adică faptul că un proces activ, care este blocat pe un timp nedefinit de unitatea de planificare (deși este teoretic capabil să se execute) va fi ales la un moment dat pentru a-și continua execuția. Această condiție este una esențială și pentru evitarea stării de blocare globală a sistemului (deadlock).

abordĂri comparative pentru paradigmele: concurent, paralel, distribuit

Din tot ceea ce s-a scris până acum în acest material nu se pot delimita noțiunile de concurent, paralel, distribuit. Explicăm aceasta prin caracterul dinamic al cercetărilor actuale în aceste domenii și, mai mult, prezentăm în continuare câteva opinii referitoare la diferențele și intersecțiile sferelor de cunoștințe ale celor trei concepte.

[Boian, 1994] Desfășurarea proceselor în sistemele de calcul poate fi făcută:

secvențial — când procesele folosesc resursele unul în urma celuilalt;

paralel — când procesele se pot desfășura în același timp folosind resurse diferite;

concurent — când procesele se desfășoară în paralel, dar folosesc resurse comune. Putem privi atunci concurența ca o îmbinare între paralelism și interacțiune.

O caracteristică a programării paralele poate fi exprimată astfel: procesele paralele nu sunt condiționate unul de celălalt, execuția unuia dintre ele nu este în nici un moment dependentă de rezultatele parțiale ale celuilalt. Față de aceasta, spunem că avem programare concurentă atunci când procesele paralele se intercondiționează reciproc.

Cu alte cuvinte, dacă procesele se desfășoară în același timp, pe resurse diferite atunci programarea este paralelă, iar dacă procesele se desfășoară în paralel, pe resurse comune atunci vorbim despre programare concurentă. De aici avem că programarea concurentă apare ca un caz particular de programare paralelă. Următoarele afirmații susțin această dependență.

Dacă un sistem dispune de mai multe procesoare care sunt capabile să coopereze între ele atunci îl vom numi sistem cu procesare paralelă. Prin cooperarea între procesoare înțelegem, pe de o parte că procesoarele execută sarcini de calcul diferite ale aceluiași program și, pe de altă parte, că lansarea unei anumite secvențe așteaptă până când toate secvențele care trebuie să-i preceadă logic s-au terminat. Pentru ca procesele să coopereze între ele, în sistem trebuiesc implementate mecanisme specifice de comunicare și sincronizare. In cadrul fiecărei secvențe dintre cele care se execută în paralel (care se lansează în execuție simultan), instrucțiunile componente se execută concurent. Cu alte cuvinte, execuția concurentă presupune paralelism și schimb de informații între procesele care se execută în paralel.

Se poate evidenția totuși o delimitare între paralelism și concurență în sensul că paralelismul pune accent pe execuția propriu-zisă, simultană a proceselor, în timp ce aspectele concurente se referă la rezolvarea interacțiunilor dintre procese.

Dacă în sistem există mai multe procesoare atunci paralelismul programat este efectiv. Altfel, execuția secvențelor paralele este simulată într-un paralelism abstract.

Dacă în sistem există un singur procesor atunci concurența poate apărea numai la nivelul logic al unei aplicații. Dacă însă sistemul este multiprocesor atunci concurența apare și la nivel fizic.

[Georgescu, 1996] Dezvoltarea calculului paralel este potrivită sistemelor multiprocesor cu comunicare prin zone de memorie comune. Dacă un sistem multiprocesor respectă un protocol de comunicare prin linii de comunicație atunci programarea impune utilizarea algoritmilor distribuiți.

Conform principiilor programării paralele, rezolvarea unei probleme presupune descompunerea acesteia în subprobleme independente rezolvabile în acelați timp, pe procesoare distincte. Dacă mai multe procese (programe în execuție) pot fi rulate simultan și nu neapărat pe procesoare distincte atunci vorbim de programarea concurentă a acelor procese. In acest caz comunicarea între procese se face prin memorie comună sau prin mecanisme specifice concurenței, dar se va evita comunicarea prin variabile globale.

Scopul programării paralele constă în elaborarea algoritmilor care să speculeze existența mai multor procesoare pentru a micșora timpul de calcul.

Intr-un sistem multiprocesor, algoritmul de comunicare între procese poate folosi zone de memorie comune sau linii de comunicație. In primul caz aplicația se încadrează mai bine în specificul calculului paralel, iar în al doilea caz suntem conduși spre algoritmi distribuiți.

[Ionescu, 1999] Sistemul paralel este o mașină cu procesoare multiple, capabilă să prelucreze informațiile prin manevrarea concurentă a datelor.

Sistemele cu procesare paralelă sunt sistemele cu interconectare strânsă și arhitecturile cu spațiul de adresă al memoriei partajat, în timp ce sistemele cu procesare distribuită sunt cele cu interconectare slabă și arhitecturile bazate pe transmitere de mesaje (se partajează canale de comunicație).

Paralelismul apare odată cu execuția simultană pe procesoare diferite a mai multor procese care comunică și se sincronizează între ele.

[Boian, 1999] Intr-un sistem distribuit, accesul utilizatorului la resursele depărtate se face ca și cum acele resurse s-ar afla pe mașina locală. Pentru aceasta, se impune ca, la nivelul sistemului de operare, să fie controlată migrarea datelor, calculelor și proceselor implicate în utilizarea resurselor la distanță. Detaliind, se poate spune că programarea paralelă trateză migrarea proceselor, în timp ce programarea distribuită tratează migrarea (distribuirea) calculelor.

[PC Report 40] Domeniile „calde” în programarea concurentă sunt în general legate de utilizarea sistemelor distribuite [I. Athanasiu].

Conform cu S. Williams [1990], nu există nici o delimitare clară între noțiunile concurent și paralel, prin urmare ele sunt folosite de diferiți autori după preferință. Datorită caracterului său mai general, însă, se preferă utilizarea termenului de paralel.

concurenȚa În sisteme distribuite

In sistemele distribuite execuția paralelă/concurentă a proceselor apare în mod natural în diverse situații de cooperare rezultate din: (a) activități individuale (separate) ale diferiților utilizatori, (b) independența resurselor sistemului, (c) localizarea proceselor server pe calculatoare diferite. Execuția paralelă este posibilă dacă specificul aplicației permite separarea activităților.

De exemplu, pentru cazul unui sistem distribuit bazat pe modelul resurselor partajate, pot apărea două situații care conduc la execuția paralelă: (1) din punctul de vedere al cererilor: mai mulți utilizatori lansează simultan comenzi independente sau interacționează simultan cu programele aplicații; (2) din punctul de vededre al răspunsurilor sistemului distribuit: mai multe servere de procese lucrează concurent, fiecare răspunzând diferitelor cereri primite prin procese client.

La nivelul sistemelor de operare sau al bazelor de date, probleme specifice ale cooperării între procese cum sunt sincronizarea, tratarea excluderii mutuale sau evitarea impasului/interblocării (deadlock), se rezolvă în contextul prelucrărilor multitasking sau multiuser. Pentru prelucrările de tip monoprocesor, soluțiile se dau prin intermediul structurilor de tip semafor sau monitor. Aceste soluții presupun existența în sistem a unei memorii comune, partajată de procesele care comunică.

Una dintre problemele care apar la nivelul cooperării între procese într-un sistem distribuit este rezultatul faptului că într-un sistem distribuit nu există o zonă de memorie comună tuturor componentelor sistemului. De aici, rezultă că rezolvarea problemelor de tip sincronizare și comunicare în sisteme distribuite trebuie să folosească algoritmi specifici, care să respecte caracterul distribuit al sistemului gazdă și al aplicației.

O altă caracteristică fundamentală a sistemelor distribuite constă în faptul că într-un sistem distribuit nu există un ceas global al întregului sistem și nu există nici măcar o sursă de obținere a unui timp global. Procesele își gestionează execuția bazându-se numai pe informația stocată pe mașina locală.

Soluțiile corecte care rezolvă problemele de comunicare și sincronizare în sisteme distribuite trebuie să țină cont de aceste două particularități (ne-existența unei zone de memorie comună și lipsa unui ceas global al întregului sistem). In plus, aceste sisteme trebuie să respecte un principiu fundamental al programării distribuite și anume: în sistemele distribuite trebuie evitată existența unui unic punct de blocare, adică trebuie eliminată posibilitatea ca, prin blocarea unui singur punct (calculator, proces), să se blocheze întreg sistemul. Soluții pentru rezolvarea problemei sincronizării temporale a cooperării într-un sistem distribuit se pot găsi în [Boian, 1999].

De asemenea, cele două particularități fundamentale ale sistemelor distribuite arată că, din punctul de vedere al tipului de conexiune între noduri, un sistem distribuit este un sistem slab-conectat (loosely coupled). Intr-un astfel de sistem nu există un procesor master ci toate relațiile dintre procesoare sunt decise pe bază de negocieri realizate prin schimburi de mesaje. Prin schimb de mesaje se va înțelege atât transmiterea mesajului cât și secvența necesară prelucrării lui.

In general, ipoteza excluderii mutuale sau a secțiunii (regiunii) critice cere ca accesul la o anumită resursă să fie exclusiv – dacă mai multe procese pot să o acceseze în același timp.

Așa cum am afirmat și anterior, în sistemele monoprocesor o resursă critică poate fi „protejată” prin semafoare, monitoare sau prin variabile cu acces exclusiv. Aceste mecanisme sunt posibile deoarece (a) procesele sunt coordonate de către același nucleu și (b) toate procesele au acces la memoria internă a sistemului și în această memorie internă ele partajează o zonă comună. Sistemele distribuite sunt lipsite tocmai de memoria comună partajabilă între procese. Deci și pentru implementarea regiunii critice și a excluderii mutuale se impun metode specifice caracterului distribuit, cum ar fi: (1) coordonarea centralizată, (2) coordonarea complet distribuită sau (3) coordonarea printr-o metodă de tip token–ring.

Coordonarea centralizată presupune că se alege un proces ca și coordonator al întregului sistem. Acesta va iniția un dialog cu celelalte procese prin mesaje de tip request, reply sau release. Printr-un mesaj request un proces oarecare cere coordonatorului intrarea în secțiunea critică. Acest mesaj trebuie să fie urmat de un mesaj reply prin care procesul coordonator aprobă ca procesul subordonat să intre în secțiunea critică. Execuția secțiunii critice se termină cu un mesaj release prin care procesul anunță coordonatorul că și-a încheiat execuția secțiunii critice.

In spiritul principiului fundamental al sistemelor distribuite enunțat anterior, trebuie spus că programarea coordonării centralizate trebuie să asigure că, în situația în care procesul coordonator cade, celelalte procese vor coopera pentru alegerea unui nou coordonator.

Coordonarea complet distribuită folosește sincronizarea cu ceasuri logice și rezolvă problema excluderii mutuale numai prin cooperarea proceselor distribuite, fără ca vreun proces să aibă atribuții speciale.

Coordonarea printr-o metodă token–ring presupune că procesele sunt „ordonate” într-un inel logic și identificate prin numărul lor de ordine în acest inel. Un token este un mesaj special de comunicare, transmis circular în inelul proceselor.

Pentru tratarea și a altor aspecte ale coordonării în sisteme distribuite cum ar fi: problema impasului, problema toleranței la erori sau problema consistenței deciziilor proceselor concurente se poate consulta [Boian, 1999], [Coulouris, 1999].

partea a ii a

implementarea sistemelor concurente

procese. fire de execuȚie

Conceptul de proces

Noțiunea de program în accepțiunea lui obișnuită se referă în special la aplicații simple, didactice. Când programăm probleme mai complexe, de multe ori folosim termenul de produs program. Dar, chiar și această terminologie este insuficientă în situațiile în care se impun detalii de implementare la nivel low-level.

De exemplu, dacă se dorește proiectarea unui sistem de operare, trebuie ținut cont de faptul că în funcționarea SO apare un anumit grad de nedeterminism. Acesta se referă mai ales la situațiile în care sunt solicitate răspunsuri la evenimente care apar la momente de timp imprevizibile și cu o frecvență, de asemenea, imprevizibilă. Avem trei nivele de astfel de evenimente, în funcție de frecvența lor de apariție:

cereri de schimb între memoria internă și suporturi de memorare externă (de care răspunde UCP);

cereri de ocupare, pentru o perioadă de timp nedeterminată, a unor periferice fizice sau a unor blocuri de memorie;

servicii oferite de sistemul de operare utilizatorilor de la terminale în cazul apariției unor erori hardware sau software.

Repetăm că, pentru a se putea satisface cererile de mai sus, nu este suficient conceptul de program în analiza proiectului. Este nevoie și de un alt concept, acela de proces, pe care îl vom prezenta în continuare.

Un proces sau task reprezintă o entitate dinamică ce corespunde unui program în execuție, fiind o abstractizare a activității procesorului. Această definiție va fi extinsă în paragrafele următoare.

Din alt punct de vedere, un proces este un calcul care poate fi executat concurent sau paralel cu alte calcule. Incă, aceste definiții vor fi completate în paragrafele următoare.

In acest paragraf detaliem prima definiție, insistând asupra caracterului dinamic al unui proces și precizând care este legătura proces – procesor.

Existența unui proces este condiționată de existența a trei factori:

procedură – un cod sursă, un set de instrucțiuni – care trebuie executată;

un procesor care să poată executa aceste instrucțiuni;

un mediu (memorie, periferice) asupra căruia să acționeze procesorul conform instrucțiunilor din procedură.

Trebuie deci făcută diferența dintre un proces și un program. Procesul are caracter dinamic deoarece precizează (se referă la) o secvență de activități aflate în curs de execuție, iar programul are un caracter static deoarece el numai descrie secvența de activități respectivă. Un proces „există”, un program „se execută”.

Un proces durează atât timp cât execuția programului a fost începută și nu este încheiată.

Un proces este format din: (1) codul programului, (2) stiva cu datele temporare necesare procesului (parametrii programului, variabilele locale, adresele de revenire) și (3) o secțiune de date.

Legătura logică pe care o putem stabili între un proces și un procesor constă în faptul că fiecare proces are un procesor virtual propriu, care îi este asociat pe durata existenței sale. Procesorul real (fizic) comută de la un proces la altul. Când un proces este în execuție se spune că a primit controlul procesorului.

Pentru a memora informațiilor legate de toate procesele pe care le are de gestionat, sistemul de operare își creează o structură de date numită tabelă de procese. Poziția unui proces în tabela de procese va fi identificatorul procesului deoarece îl determină în mod unic.

Din punct de vedere practic, un proces constă dintr-un program (un set de activități de executat) și din contextul programului (sau parametrii sistem care trebuie cunoscuți procesului pentru execuția sa).

Componentele programului unui proces pot să fie activități ale SO sau ale utilizatorului. Dacă procesul este asociat unor module ale sistemului de operare atunci avem procese sistem. Dacă procesul este asociat unui program utilizator atunci avem procese utilizator. Procesele pot să creeze, la rândul lor, alte procese utilizator sau să lanseze în execuție module sistem. In paragrafele următoare se va introduce și noțiunea de fir de execuție, care va detalia aceste aspecte.

Informațiile conținute în contextul programului procesului sunt memorate într-o structură, numită teoretic vector de stare al procesului și practic, bloc de control al procesului. Acesta se referă la: identificatorul procesului, starea procesorului când procesul nu este activ, pentru a se putea controla continuarea execuției procesului, starea procesului, prioritatea procesului, prioritatea procesului la obținerea resurselor, informații despre resursele alocate procesului.

Relații între procese

Din punctul de vedere al legăturilor care se pot stabili între activitățile a două procese, acestea pot fi: procese independente, dacă nu sunt influențate unul de execuția celuilat sau procese cooperante, în caz contrar.

Caracterizarea proceselor independente poate fi făcută astfel:

nu pot partaja aceleași resurse;

execuția lor este deterministă, adică constă dintr-o aceeași succesiune de pași la fiecare inițiere;

execuția depinde numai de datele de intrare, nu și de date sau evenimente care pot surveni pe parcurs;

execuția este reproductibilă, adică cu aceleași date de intrare se obțin aceleași rezultate;

execuția poate fi întreruptă și reluată fără efecte negative.

Caracterizarea proceselor cooperante se obține prin negarea proprietăților proceselor independente. In cele ce urmează se va vedea că particularitățile sistemelor concurente conduc îndeosebi spre programarea proceselor cooperante și mai puțin spre procesele independente. Astfel, procesele independente se dovedesc nespecifice sistemelor concurente.

Să considerăm un exemplu simplu pentru legătura dintre conceptele de proces, program, procesor. Dacă cineva citește o carte, această activitate este comparabilă cu execuția unui program de către un proces. Dacă o persoană x citește cartea și în timp ce acest proces este întrerupt, o altă persoană y citește aceeași carte atunci situația rezultată este comparabilă cu execuția aceluiași program de către două procese diferite. Intre aceste procese pot apărea relații de cooperare (cele două persoane schimbă impresii despre carte) sau de competiție (cele două persoane ajung să dorească să citească în acelașți timp, deci să-și partajeze resursa fizică, care este cartea). Mai mult, deoarece cartea este una singură, suntem în situația în care se impune restricția ca numai un proces să aibă acces la resursă la un moment dat. O soluție ar putea fi copierea cărții și astfel ambele persoane pot citi simultan (duplicarea datelor).

Spre deosebire de „resursa” carte, dacă considerăm cazul a doi muzicieni care interpretează simultan aceeași partitură atunci situația rezultată este comparabilă cu două procese care execută același program pe procesoare distincte. In plus, aici apare și condiția de sincronizare între procesele „interpretate”.

Dacă în timp ce persoana x citește să considerăm că sună telefonul. Atunci procesul „citire” va fi întrerupt, controlul va fi cedat procesului „convorbire telefonică” și după ce acesta se va încheia, va fi reluat procesul „citire” de unde a fost abandonat.

Stările unui proces

Pentru a se executa, un proces își alocă resurse fizice necesare desfășurării activităților sale. Cum resursele unui SC sunt adesea în cantități limitate, nu este recomandat ca un proces să-și rezerve la creare toate resursele necesare. In acest caz, se poate ca atunci când procesul ajunge să aibă nevoie de o anumită resursă fizică (memorie, dispozitiv periferic), aceasta să fie ocupată de alt proces. Astfel, procesul nu mai poate să-și continue execuția.

De asemenea, un proces intră într-o stare în care nu se mai poate derula dacă continuarea execuției lui depinde de producerea unui eveniment. De exemplu, dacă un proces trebuie să furnizeze date altui proces atunci acesta din urmă trebuie să aștepte până când primește datele respective.

Un proces care se află în imposibilitatea de a-și continua execuția deoarece nu dispune de resursele și/sau datele necesare, se spune că este în starea blocat.

Ordinea în care procesorul sistemului de calcul se dedică execuției proceselor depinde de o anumită prioritate a proceselor. Aceasta se asociază fiecărui proces la creare. Cu cât prioritatea unui proces este mai mare, cu atât acel proces va intra în execuție mai repede.

Dacă un proces P1 poate să se execute (adică dispune de toate resursele și datele necesare), dar procesorul a decis executarea unui alt proces, P2, de prioritate mai mare, atunci spunem despre procesul P1 că este în starea întrerupt.

Deși în ambele stări anterioare, blocat sau întrerupt, procesul nu-și mai poate continua execuția, există o deosebire esențială între ele. Starea blocat intervine din motive ce țin de logica după care se succed activitățile proceselor dependente, în timp ce starea întrerupt apare din motive fizice legate de imposibilitatea procesorului unic de a se dedica (de a ceda controlul) simultan execuției mai multor procese.

Dacă procesul este în curs de execuție atunci se spune că procesul se află în starea activ.

Dacă sistemul de calcul are un singur procesor atunci, în orice moment, un singur proces poate fi activ. Dacă avem mai multe procesoare atunci, la un moment dat, pot fi active cel mult atâtea procese câte procesoare avem.

Operații cu procese

Execuția unui proces durează între crearea procesului și distrugerea (eliminarea) lui.

Crearea unui proces constă din:

alocarea unui vector de stare;

inițializarea componentelor vectorului de stare;

înregistrarea procesului în tabela de procese.

Odată cu memorarea în tabelă, se fixează și identificatorul procesului (poziția din tabelă). Prin intermediul acestuia, sistemul de operare și orice alt proces vor putea referi procesul creat, pe toată durata existenței lui.

Un proces, Pt, (utilizator sau sistem) poate cere crearea unui proces, Pf. In acest caz spunem că Pt este proces tată, iar Pf este proces fiu sau descendent al lui Pt. Dacă două sau mai multe procese sunt descendenți ai aceluiași tată atunci ele se numesc procese frați.

Mulțimea tuturor proceselor create de un proces A și de descendenții acestuia formează descendența procesului A.

Cu aceste definiții putem spune că toate procesele sistemului alcătuiesc o structură arborescentă.

Distrugerea unui proces constă din:

eliberarea resurselor ce i-au fost alocate;

eliberarea memoriei corespunzătoare vectorului de stare;

eliminarea procesului din tabela proceselor.

Un proces se poate autodistruge atunci când ajunge la sfârșitul execuției sale sau poate fi distrus la cererea unui alt proces sistem sau utilizator.

Alte operații care se pot efectua asupra proceselor sunt: intârzierea, semnalizarea, planificarea, schimbarea priorității, suspendarea și reluarea. In urma aplicării uneia sau unora dintre aceste operații, un proces poate fi în diferite stări. Această dependență este prezentată în figura următoare.

Figura 3. Operații cu procese

Observație. Trebuie precizat că la creare, procesul trece automat în starea întrerupt, iar prin operația de distrugere, procesul trece din starea curentă (activ, întrerupt, blocat, întrerupt-suspendat sau blocat-suspendat) într-o stare generic numită inexistent.

Operația de întârziere (WAIT) apare când un proces nu-și poate continua execuția și așteaptă apariția unui eveniment. Prin operația de semnalizare (SIGNAL), un proces este informat că s-a produs un eveniment (de obicei, este vorba de evenimente pe care procesul le așteaptă pentru a-și putea continua execuția).

Planificarea este operația prin care se stabilește ordinea în care procesele primesc controlul procesorului pentru execuție. Schimbarea priorității unui proces influențează modul de alocare a resurselor necesare procesului.

Procese multi-thread

Cronologic vorbind, noțiunea abstracă de proces a fost introdusă pentru a numi execuția dinamică a unei entități de calcul pe un procesor. Incepând cu interfețele bazate pe ferestre, sistemele moderne trebuie să detalieze această definiție a noțiunii de proces. De multe ori, la nivelul unui program, este nevoie ca mai multe activități să se execute simultan. In timp, acest aspect a fost legat prima dată de posibilitățile de lucru multitasking.

Când se impune o precizie la nivelul noțiunilor folosite atunci se folosește termenul de proces pentru activitatea care inițializează un program. Resursele necesare execuției acelui program vor fi asociate logic procesului respectiv. Vom folosi termenul de thread, fir sau fir de execuție pentru a denumi fiecare dintre activitățile individuale din interiorul programului. Mai mult, termenul de thread va identifica entitatea care se execută pe un procesor.

Sistemele care recunosc lucrul cu fire de execuție creează automat un proces cu un singur thread atunci când se inițializează execuția unui program. Acest thread principal poate crea alte thread-uri copil (fiu). Toate threadurile curente partajează resursele procesului care le-a creat.

Dacă un sistem de operare trebuie să deservească un sistem multiprocesor cu memorie partajată, este important ca acel sistem să recunoască procesele cu mai multe fire de execuție (multi-threaded processes). In acest caz, threadurile distincte ale aceluiași proces pot fi planificate să se execute simultan pe procesoare distincte.

Sistemele de operare tradiționale, închise (closed OS) nu au facilități de lucru multiprocesor, în timp sistemele dezvoltate recent recunosc această facilitate. Noțiunile de proces și thread sunt specifice sistemelor de operare UNIX și Windows, în timp ce alte sisteme folosesc pentru aceleași concepte o altă terminologie. Astfel, procesul – ca entitate elementară la nivelul unui sistem de operare – este echivalent, pentru alte sisteme, cu un spațiu de adresă cu un thread sau cu un task cu un thread sau cu un proces cu un thread. Pentru exemplificare, preluăm din [Bacon, 1998] următoarea tabelă.

Intenționăm ca modelarea aplicațiilor concurente folosind diverse mecanisme de tip ACTOR, TEAM, CLUSTER etc., să se regăsească în tematica referatului următor.

Tabel 3. Conceptul de proces sub diverse sisteme de operare

Procesele din același spațiu de adrese sunt adesea numite lightweight threads, LWThreads. Termenul de thread arată că fiecare proces are un fir de execuție diferit. Caracteristica lightweight arată că, la schimbarea procesului în execuție, este necesar să se salveze informații puține despre contextul curent. Aceasta este situația opusă proceselor heavyweight care au propriul spațiu de adresă. Contextul de schimbare între procesele heavyweight cere atât salvarea și încărcarea tabelelor de gestionare a memoriei cât și a registrelor.

[Andrews, 1991] Când se execută un program secvențial, există un singur thread de control: PC (Program Counter) începe la prima acțiune atomică a procesului și se mută „prin proces” pe măsură ce sunt executate acțiuni atomice. Executarea unui program concurent constă în mai multe threaduri de control, câte unul pentru fiecare proces constituent.

Rolul proceselor în implementarea sistemelor concurente

In general, aplicațiile concurente sunt scrise în limbaje de programare de nivel foarte înalt. La nivelul unui limbaj de programare secvențial, fiecare proces de limbaj este gestionat de un proces al sistemului de operare. Față de această situație, când se scrie un program concurent, programatorul trebuie să aibă la îndemână mecanisme prin care să definească explicit sau implicit procesele concurente. Dacă aceste procese sunt aduse la cunoștința sistemului de operare printr-un apel de sistem, atunci suntem în situația în care sistemul de operare recunoaște și întreține execuția proceselor respective.

După Andrews [1991], executarea unui program concurent poate fi privită ca o interpătrundere (interleaving) de acțiuni atomice executate de procese individuale. Când procesele interacționeză, nu sunt acceptabile toate interschimbările. Rolul sincronizării este de a preveni interschimburile nepermise.

Dacă considerăm procesul ca fiind unitatea de alocare a resurselor atunci threadurile lui devin unitățile de planificare. Din acest punct de vedere, un thread este un subproces la nivel de limbaj de programare. Dacă astfel de subprocese sunt cunoscute sistemului de operare atunci ele pot fi planificate de SO independent unele de altele. Avantajele cresc atunci când sistemul este multiprocesor deoarece această configurație permite ca execuția concurentă planificată pe procesoare distincte să fie una efectivă.

Pentru ca un sistem în timp real să asigure respectarea restricțiilor temporale impuse de natura sistemului este imperios necesar ca planificarea threadurilor să se facă á-priori. Mai mult, sunt situații în care se impune ca planificarea să se bazeze pe un grafic de priorități ale proceselor sau pe un grafic de termene limită.

Când se implementează un sistem concurent într-un limbaj de programare concurent, programatorul trebuie să dețină informații despre structura hardware a sistemului concurent, precum și despre sistemul de operare gazdă.

Suportul sistemului de operare pentru gestionarea proceselor trebuie să includă operații de tip WAIT și SIGNAL care să asigure sincronizarea proceselor echipamentelor hardware ale sistemului de calcul. In acest context, vom folosi termenul de eveniment pentru a desemna apariția unui semnal de întrerupere de la o resursă fizică. Tratarea întreruperii pentru interacțiunea hardware care tocmai a apărut revine unui proces al sistemului de operare. Execuția rutinei de tratare a întreruperii dă totodată și răspunsul sistemului la cererea adresată de procesul utilizator prin întreruperea respectivă. In plus, într-un sistem concurent, este necesar să se aibă în vedere că procesele utilizator pot să interschimbe informații, deci trebuiesc corect sincronizate, conform cu logica lor internă.

Concret, o variantă de implementare a aplicațiilor concurente ar putea consta în programarea fiecărei unități a sistemului concurent ca un proces secvențial. In acest caz, sistemul de operare va comunica prin apeluri sistem pentru a permite interacțiunea între procese și pentru furnizarea serviciilor solicitate la nivelul său. Această soluție este potrivită pentru sistemele cu granularitate mare, slab cuplate ( sau cu conectare slabă, cum sunt sistemele distribuite), în care probabilitatea de interschimb de informații între procesele concurente este mică.

O problemă suplimentară în proiectarea și implementarea sistemelor concurente este portabilitatea. In majoritatea cazurilor, pentru a coordona interacțiunile dintre procese, codurile sursă folosesc resurse ale interfeței sistemului de operare gazdă (cum sunt și apelurile sistem). Dacă se schimbă configurația sistemului concurent atunci aplicația rămâne dependentă de platforma (interfața) anterioară. De aceea, problema portabilității aplicațiilor este una importantă, care trebuie luată în considerare încă din faza de proiectare a sistemului și a aplicațiilor lui.

EvoluȚia concurenȚei la nivelul limbajelor de programare

Multe dintre sistemele concurente funcționează pe baza unor aplicații scrise în limbaje de programare secvențiale (C, C++) care au facilități de implementare a concurenței.

Față de acest „compromis”, programatorii au la dispoziție și o serie de limbaje de programare pur concurente. Acestea permit ca întregul sistem să funcționeze pe baza unei aplicații concurente descrisă într-un singur program sursă. Astfel de sisteme sunt de obicei sisteme dedicate (special-purpose system) care, fie au integrate, fie numai folosesc un set minimal de funcții ale sistemului de operare.

Implementarea proceselor dezvoltate la nivelul sistemului de operare sau la nivelul sistemelor de limbaje de programare poate fi extinsă prin facilitățile oferite de comunicarea între procese, IPC – inter-process communication.

Concurența la nivelul limbajelor de programare secvențiale

Un limbaj de programare secvențial care recunoaște apelurile imbricate și recursive permite implicit ca mai multe proceduri să fie active simultan. Cu toate acestea, există un singur thread de control, o singură stivă și o singură zonă heap pentru gestionarea execuției programului secvențial.

De aceea, este dificil și nenatural ca un același program sursă să descrie codurile mai multor subsisteme independente (subsistem = colecție de proceduri dependente sau module) sau să se gestioneze accesul simultan al mai multor clienți la acest cod unic.

Deoarece există un singur thread de control și sistemul de operare lucrează cu un singur proces la un moment dat, este exclusă din start posibilitatea ca astfel de sisteme să poată răspunde rapid și promt tuturor evenimentelor din sistem. Dacă în sistemul secvențial apare o întrerupere, se salvează starea procesului (singurul existent), se înregistrează producerea unui eveniment și procesul curent este suspendat. Deci nu există posibilitatea de a transfera controlul programului unui alt proces, oricare ar fi efectele asupra sistemului concurent în ansamblu.

Mai mult, într-un limbaj secvențial nu există suport pentru implementarea unui subsistem care să poată aștepta într-un punct producerea unui eveniment. In orice punct în care se impune o așteptare, cade în sarcina programatorului să salveze contextul curent și să-l încarce corect ulterior, pentru reluarea execuției. In particular, nu există posibilitatea de a „îngheța” stiva de execuție pentru a putea relua execuția ulterior, din același punct. Există o singură stivă de execuție care oglindește toate calculele din sistem, chiar dacă unele sunt blocate și nu se pot debloca.

O variantă de reducere a acestor inconveniente ar putea consta în aplicarea tehnicii polling la nivelul programului secvențial al aplicației concurente. Pentru aceasta programatorul trebuie să dezvolte codul sursă astfel încât programul să testeze periodic apariția în sistem a unui eveniment și să interpreteze diferențiat evenimentele recunoscute.

Din aceste considerente se poate vedea că o aplicație concurentă scrisă într-un limbaj secvențial nu poate valorifica facilitățile unui sistem multiprocesor, existența unui unic procesor fiind necesară și suficientă pentru execuția aplicației respective.

Corutine

Unele limbaje de programare, cum ar fi: Modula-2 sau BCPL, folosesc entități elementare numite corutine cu ajutorul cărora se realizează descrierea subprogramelor independente ale aceluiași program. Deci un astfel de program poate avea mai multe corutine și fiecare corutină are propria stivă de execuție. Un astfel de limbaj are instrucțiuni elementare pentru crearea și ștergerea unei corutine, dar și instrucțiuni speciale, de exemplu cele care întrerup temporar execuția unei corutine sau cele care permit programului să reia execuția corutinei exact din starea în care a fost întreruptă. Când o corutină este întreruptă controlul programului trebuie cedat explicit altei corutine.

[Braunl, 1993] Corutinele sunt o formă restrictivă de paralelism implementată în Modula-2. Modelul fundamental, caracteristic de arhitectură este cel uniprocesor. Există un singur flux de instrucțiuni cu flux de control secvențial. Totuși, resursa „procesor” poate fi ocupată și eliberată de o mulțime de corutine, de o manieră ordonată.

Figura 4. Mecanismul de lucru cu corutine

In această reprezentare se observă o execuție pseudo-paralelă între corutine. Ele pot fi văzute ca un caz particular de proceduri (subrutine) ale căror date locale nu sunt pierdute între apeluri.

Execuția începe cu apelul uneia dintre corutine. Fiecare corutină poate conține oricâte propoziții (intrucțiuni) de TRANSFER care COMUTA fluxul de control între corutine. Un transfer NU este un apel de procedură deoarece nu presupune implicit că urmează un moment în care controlul programului să se transfere implicit procedurii (corutinei) apelante; la fiecare operație de TRANSFER se vor preciza explicit corutinele sursă și destinație ale schimbării fluxului de control.

Deoarece lucrul cu corutine este bazat pe existenșa unui singur procesor și nu se poate extinde la mai multe, se evită problematica prelucrărilor multitasking. Ramificarea fluxului de control trebuie să fie definită explicit de programatorul aplicației cu corutine.

Paranteze pentru execuȚie nesecvenȚialĂ

[Braunl, 1993] Construcțiile Fork și Join sunt unele dintre primele unelte ale paralelismului la nivelul limbajului de programare. In Unix este posibil să se declanșeze procese paralele prin operația Fork și să se impună așteptarea încheierii lor prin Wait (operația de tip Join de sub Unix).

Față de corutine, acesta este un exemplu de prelucrare paralelă efectivă. Execuția paralelă poate fi asigurată prin multitasking în cuante de timp pe un procesor (time-sharing), dacă nu sunt disponibile mai multe procesoare.

In acest tip de programare paralelă sunt importante două concepte fundamentale și anume:

declararea proceselor paralele și

sincronizarea proceselor.

Figura 5. Mecanismul Fork – Join

Din exemplul anterior se observă că există un interval de timp în care procesele A și B se execută în paralel.

O altă construcție specifică calculului paralel este ParBegin – ParEnd (sau CoBegin – CoEnd). Aceasta lucrează de o manieră similară cu parantezele Begin – End specifice programării secvențiale. Diferența esențială este faptul că în interiorul blocului ParBegin – ParEnd instrucțiunile sunt executate simultan. Limbajele de programare (AL, Algol 68) care au implementat acest mecanism folosesc pentru sincronizare semafoare.

Suportul proceselor pentru caracterizarea concurenței

Față de limbajele cu corutine, alte limbaje de programare creează aplicații concurente folosind suportul oferit de procese. Din această categorie amintim: Mesa, Concurrent Pascal, Pascal Plus, Occam.

Ca și în cazul corutinelor, un program poate conține mai multe subprograme, dar aici fiecare subprogram este executat de un proces separat care este definit prin limbajul de programare. O altă asemănare cu corutinele constă în faptul că și procesele au fiecare propria stivă de execuție, dar, există o mare deosebire în ceea ce privește controlul programului. Controlul proceselor este asigurat un „agent extern”, care nu este programat explicit printr-un subprogram al aplicației.

Un astfel de agent este un modul de gestionare a proceselor care face parte din mediul de programare respectiv, așa cum rezultă din figura următoare.

Figura 6. Suportul de limbaj pentru gestionarea proceselor

Un proces poate fi nevoit să aștepte eliberarea unei resurse partajate la nivelul limbajului de programare sau poate fi nevoit să aștepte ca alt proces să încheie o activitate de care depinde continuarea sa. In astfel de limbaje, o operație de întârziere de tip WAIT se regăsește ca un apel de procedură. Când un proces este suspendat în urma unei decizii de așteptare, agentul de control trebuie să selecteze un alt proces care să treacă în starea activ.

O problemă majoră în proiectarea sistemelor concurente bazate pe suportul proceselor de limbaj este stabilirea relațiilor dintre procesele de la nivelul limbajului de programare și procesele cunoscute de sistemul de operare. Se poate impune ca sistemul de operare să suporte numai câte un proces pentru fiecare program. In acest caz, procesul definit într-un limbaj de programare concurent, nu este un proces deplin (matur, fledged) al sistemului de operare. Subprocesele unui program sunt gestionate intern de limbaj prin planificarea proceselor, rezultând o dublură pentru planificarea proceselor făcută de gestionarul de procese de la nivelul sistemului de operare. Mediul limbajului de programare poate multiplexa un proces al sistemului de operare în mai multe subprocese cunoscute numai la nivelul său.

Scenariul de implementare este asemănător cu cel al corutinelor, dar aici programatorul nu trebuie să se ocupe de transferul controlului între procesele de la nivelul limbajului. Planificarea proceselor este asigurată de sistemul de execuție a programelor scrise în limbajul respectiv.

Există cel puțin un inconvenient al acestei abordări și anume faptul că interdependența proceselor coroborată cu blocarea procesului apelat poate bloca întreg sistemul. De exemplu, dacă un subproces creat de program cere sistemului de operare să execute o operație de intrare/ieșire și se blochează (dintr-un motiv oarecare) atunci nici un alt subproces al programului nu-și mai poate continua execuția. Aici am presupus un sistem de operare care execută toate operațiile I/O de o manieră sincronizată, de exemplu UNIX (Windows NT este un sistem de operare care poate prelua cererile atât sincron cât și asincron). Un alt exemplu pentru aceeași idee a blocării globale ar fi următorul: dacă un subproces folosește procesul de gestionare a proceselor limbajului (chiar și numai ca intermediar în intenția de a cere un apel de sistem) și acest proces manager se blochează, atunci se va bloca și procesul programului.

Toate aceste probleme sunt rezultatul ipotezei că sistemul de operare vede numai un proces la un moment dat. Dacă programul ar putea să facă cunoscute sistemului de operare toate subprocesele sale atunci ele ar deveni chiar procese ale sistemului de operare, adică threaduri. Mai mult, pentru accesul la procesoare, aceste threaduri ar fi planificate tot de sistemul de operare și astfel ar putea să se execute concurent cu alte procese pe procesoarele unui sistem multiprocesor. Fiecare dintre threaduri poate executa un apel sistem către sistemul de operare și blocarea lui nu va conduce la blocări în lanț. Sistemul de operare poate grupa aceste procese de limbaj prin atribuirea unui spațiu de adrese pentru un astfel de grup.

Tipuri de threaduri

Din considerentele anterioare rezultă două variante de recunoaștere a proceselor la nivelul sistemului de operare: [Bacon, 1998]

sistemul de operare poate vedea un thread pentru un spațiu de adrese – această variantă lucrează cu threaduri de nivel utilizator (user- level threads); exemple de sisteme care recunosc threaduri utilizator: DEC (Distributed Computing Environment) CMA, OSF, sistemul PCR (Portable Common Runtime) din Xerox PARC; la acest nivel programarea concurentă se face fără suportul sistemului de operare.

Figura 7. Implementarea proceselor concurente fără suportul sistemului de operare

sistemul de operare recunoaște mai multe threaduri – aici fiecare thread de limbaj va fi atribuit (asignat, asociat) surjectiv unui thread al sistemului de operare; această variantă lucrează cu threaduri de nucleu al sistemului de operare (kernel- level threads); exemple de sisteme care recunosc threaduri de nucleu: Windows NT, Mach, Chorus, OS/2; la acest nivel programarea concurentă se face cu suportul sistemului de operare pentru procesele interne (Figura 8).

Se poate prevedea o a treia variantă care să combine caracteristicile primelor două astfel încât să se mărească gradele de libertate ale programatorului pentru creșterea performanței aplicațiilor. Această opțiune constă în posibilitatea ca un thread utilizator să se execute într-unul din mai multe threaduri de nucleu. In figura următoare, în această situație sunt threadurilor utilizator u4 – u7 față de threadurile de nucleu k3 și k4 (Figura 9).

Figura 8. Implementarea proceselor interne bazată pe suportul sistemului de operare

Figura 9. Combinarea threadurilor utilizator și de nivel nucleu

Atunci când asignează threadurile utilizator la threaduri de nucleu, programatorul trebuie să țină cont de mai mulți factori, de exemplu: câte și care sunt procesoarele disponibile în sistem, care procese se pot desfășura în paralel pe procesoare distincte, care threaduri pot eventual să blocheze apelurile sistem și care sunt direcțiile în care pot fi exploatate fiecare dintre cele două tipuri de threaduri (utilizator și de nucleu). De asemenea, trebuie să țină cont de anumite situații conflictuale, cum ar fi: (a) când se blochează un thread de nucleu, nici unul dintre threadurile sale de tip utilizator nu mai poate continua sau (b) threadurile utilizator care se execută pe procesoare distincte trebuie să fi fost asignate la threaduri de nucleu diferite.

Exemplu de sistem care a adoptat această schemă este SunOS, care numește threadurile de nucleu LWP (lightweight process, procese ușoare) și threadurile utilizator chiar thread.

Ideal ar fi ca programatorul să poată folosi threadurile fără să facă distincția între threaduri utilizator și threaduri de nucleu.

problematica concurenȚei

Un program concurent poate fi privit ca un ansamblu de componente care pot fi executate simultan. La o primă abordare, aceste componente sunt procesele care comunică între ele. In acest context sunt corecte ambele definiții ale conceptului de proces și anume: un proces este un calcul care se poate executa paralel sau concurent cu alte calcule, respectiv un proces este o secvență de program în execuție.

O condiție fundamentală a execuției concurente a programelor se poate enunța astfel: pentru fiecare proces și pentru fiecare două instrucțiuni mașină consecutive ale sale, intervalul de timp între executarea lor este neprecizat, dar finit.

Execuția concurentă a proceselor poate crea o serie de surprize celui obișnuit cu programarea secvențială. Dintre acestea, poate cea mai mare surpriză este legată de caracterul nedeterminist al execuției concurente. Comportarea nedeterministă constă în faptul că un același program concurent, pe un același set de date de intrare poate furniza la ieșire „rezultate” diferite. De cele mai multe ori, diferența dintre ieșiri rezultă din ordinea în care intră în execuție procesele active, din diferențele care pot apărea între vitezele de execuție ale diferitelor entități fizice implicate în execuția programului curent.

De asemenea, un program concurent poate fi privit ca un program care, în timpul execuției sale, creează mai multe procese care se execută într-un paralelism abstract (nu neapărat pe procesoare distincte). Existența unui singur procesor fizic impune ca acesta să aloce cuante de timp pentru fiecare proces activ. Politica de alocare poate fi aleatoare sau poate respecta disciplina unei anumite structuri de date (coadă, coadă de priorități etc.).

Intre procesele unui program concurent apar interacțiuni determinate în special de nevoia proceselor de cooperare. Aceste interacțiuni sunt de tip comunicare și/sau sincronizare. In paragrafele care urmează se va vedea că cele două concepte, comunicare și sincronizare, sunt inter-dependente.

Interacțiunea proceselor

Interacțiunea proceselor depinde pe de o parte de aspecte legate de cooperarea și/sau competiția între procesele respective și, pe de altă parte, depinde de deosebirea arhitecturală, structurală între sistemele cu partajare de date și cele fără partajare de date. De aici se vede că interacțiunea proceselor este un subiect deosebit de important în tematica sistemelor concurente și, de aceea, el se va regăsi atât în paragrafele imediat următoare, cât și în tratarea comunicării și sincronizării proceselor concurente.

Localizarea proceselor în funcție de structura soft a sistemului

Așa cum anticipam în finalul Capitolului 3. O definiție a sistemului concurent, pentru înțelegerea contextului de lucru concurent este importantă structura modulară a softului sistemului gazdă.

Putem prezenta această structură soft ținând cont de proprietățile zonelor de memorie în care se execută procesele curente. Din acest punct de vedere se deosebesc următoarele situații:

procesele pot partaja spațiu de adresă sau

procesele se pot executa în spații de adresă separate, distincte și complet disjuncte de spațiile de adresă ale altor procese.

(1) Dacă procesele pot partaja spațiu de adresă atunci avem mai multe variante de organizare a execuției proceselor, în funcție de necesitatea cooperării între procesele curente și de interacțiunea între procesele care pot partaja simultan, prin acces direct, un spațiu de adresă. Astfel, se deosebesc două variante principale:

toate procesele partajează un același spațiu de adresă și, de aici, rezultă că se vor executa cu partajare de date sau

procesele se execută în spații de adresă diferite (fiecare proces poate avea spațiu de adresă propriu), dar este permisă partajarea unora dintre segmentele codurilor proceselor (segmentul de cod și/sau segmentul de date). Dacă segmentul de date este unul care nu poate fi partajat, atunci procesele cooperante urmează să stabilească alt protocol de comunicare, nu prin partajarea datelor. După localizarea fizică a spațiilor de adresă proprii proceselor, varianta (1b) poate deosebi procesele care se execută pe aceeași mașină de cele care se execută pe mașini distincte.

Un exemplu de sistem care implementează aceste variante de gestiune a proceselor este un sistem multi-user în care se impun cerințe de protecție a memoriei când unul dintre utilizatori are restricții de scriere sau de citire la nivelul zonelor de memorie ale altui utilizator. De asemenea, într-un sistem multi-user trebuie impuse restricții legate de protecția asupra segmentelor de cod comun ale softului sistemului, de exemplu la partajarea compilatorului unui limbaj.

Un alt exemplu îl constituie procesele distribuite care partajează date sau cod cu alte procese din sistem. Acestea sunt procese care ocupă spații de adresă distincte, chiar situate pe mașini diferite. Orice comunicare între procesele distribuite folosește mijloacele de comunicare din rețeaua mașinilor din sistem, prin intermediul interfețelor hardware și pe baza protocoalelor de comunicare recunoscute în sistemul distribuit respectiv.

Figurile următoare reprezintă trei variante de localizare a proceselor în interiorul unui sistem.

Prima dintre ele corespunde variantei anterioare (1a) în care procesele, adesea numite threaduri în acest context, pot partaja același spațiu de adresă. Pentru această situație sunt potrivite procesele multi-thread, în care procesul este unitatea de alocare a resurselor și threadurile sunt atât unitățile de execuție și planificare, cât și entitățile active care trebuie să comunice. O restricție suplimentară care trebuie impusă în acest caz se referă la faptul că un thread al unui proces multi-thread nu trebuie să interacționeze cu un thread al altui proces multi-thread.

Figura 10. Localizarea proceselor: mai multe procese în același spațiu de adresă

A doua figură corespunde variantei anterioare (1b) în care procesele se pot executa în spații de adresă diferite, dar pe aceeași mașină. În acest caz gestionarea se face la nivelul procesului și nu prin threadurile componente (heavyweight process model). Procesul devine atât unitate de alocare a resurselor, cât și unitate de planificare și execuție.

Figura 11. Localizarea proceselor: un proces – un spațiu de adresă, aceeași mașină

A treia figură corespunde tot variantei anterioare (1b), dar pentru sisteme în care procesele se pot executa în spații de adresă diferite, pe mașini distincte.

Figura 12. Localizarea proceselor: un proces – un spațiu de adresă, pe mașini diferite

(2) Dacă procesele se pot executa în spații de adresă separate, distincte și complet disjuncte de spațiile de adresă ale altor procese atunci putem deosebi două variante specifice și anume:

toate procesele se execută în spații disjuncte sau

sunt procese care se execută în spații disjuncte.

Cazul (2a) este în contradicție cu definiția concurenței, deci nu poate fi considerat pentru implementarea unui sistem concurent.

Detaliind cazul (2b), un proces care se execută într-un spațiu de adresă disjunct de cel al oricărui alt proces este un proces care nu va partaja nici segment de date, nici segment de cod cu alte procese din sistem. Un astfel de proces poate doar să intermedieze execuția unei instrucțiuni prin scrierea sau citirea unui operand din propriul spațiu de adresă. Acesta este cazul proceselor distribuite care se execută pe mașini diferite într-un sistem distribuit.

Toate aceste variante de comunicare între procese, grupate în situațiile (1) și (2), fac obiectul mecanismelor IPC, Inter Process Communication. In sistemele în care unitățile active sunt threadurile și sunt planificate de sistemul de operare, este mai corect să folosim terminologia de ITC, Inter Thread Communication.

Cerințe pentru interacțiunea proceselor

Cerințele pentru interacțiunea proceselor rezultă, pe de o parte, din necesitatea ca procesele să interacționeze între ele și, pe de altă parte, din felul în care aceste interacțiuni pot fi suportate de sistemul gazdă.

Procesele pot coopera pentru îndeplinirea unei sarcini comune. Concret, un proces se poate afla în poziția de a cere altui proces furnizarea unui serviciu și eventual, poate că trebuie chiar să aștepte să primească acel serviciu. Exemple pentru această situație ar putea fi: (1) aspectele cooperative care reies din diferite variante de implementare a localizării unui proces asociat unui anumit modul furnizor de servicii; (2) cazul în care procesul de gestionare a discurilor trebuie să se sincronizeze cu procesele discurilor respective; (3) prelucrarea proceselor în pipeline în care fiecare proces de fază trebuie să aștepte până când procesul fazei anterioare își încheie execuția.

Din aceste aspecte se vede că cooperarea între procese presupune sincronizarea lor. Cu alte cuvinte, un proces poate fi nevoit să execute o operație WAIT(PROCES) pentru a se sincroniza cu alte procese. Sincronizarea între procese poate fi privită ca o extindere a sincronizării proceselor cu funcționarea componentele hardware ale sistemului.

Comunicarea între procesele cooperante se realizează de obicei prin operații SIGNAL(PROCES), deci prin semnale sau întreruperi.

Procesele pot concura pentru acces exclusiv la servicii sau la resurse. Din acest punct de vedere se disting două aspecte diferite și anume: (a) mai mulți clienți adresează simultan cereri pentru anumite servicii sau (b) mai multe procese încearcă să acceseze simultan o resursă. Implementarea sistemului concurent trebuie să prevadă și să gestioneze astfel de situații conflictuale prin stabilirea unei ordini predefinite, prin întârzierea execuției unora dintre procese, prin stabilirea unor priorități de acces la resursele care pot deservi numai serial cererile pe care le primesc.

Procesele concurente pot să fie nevoite să execute operații WAIT(PROCES) până să acceseze o resursă partajată și trebuie să poată transmite semnale prin operații SIGNAL(PROCES) pentru a indica momentul în care au părăsit resursa partajată în sistem.

Procesele care se execută în spații de adrese distincte vor fi cunoscute sistemului de operare. De cele mai multe ori, codul acestor procese provine dintr-o sursă scrisă într-un limbaj de programare secvențial. In acest caz, operațiile WAIT și SIGNAL sunt recunoscute ca apeluri sistem.

Procesele care partajează spații de adrese de memorie devin părți ale aceluiași program concurent și pot să fie sau nu cunoscute la nivelul sistemului de operare. Dacă nu sunt cunoscute de sistemul de operare atunci operațiile WAIT(PROCES) și SIGNAL(PROCES) vor putea fi lansate numai de la nivelul limbajului de programare.

Dacă procesele cooperează atunci se pot dezvolta mecanisme bazate pe operațiile WAIT(PROCES) și SIGNAL(PROCES) care să asigure comunicarea și sincronizarea între procesele cooperante. Aceste tehnici pot fi elementare sau pot fi construcții specifice pentru dezvoltarea aplicațiilor concurente în limbaje de programare de nivel înalt.

In cele ce urmează se va vedea că numai aceste două operații elementare de tip WAIT(PROCES) și SIGNAL(PROCES) nu sunt suficiente pentru descrierea completă a unei scheme reale de comunicare între procese de tip IPC.

Comunicarea și sincronizarea în sisteme concurente

Fiecare limbaj paralel trebuie să adreseze (să recunoască) elemente specifice paralelismului, sau explicit sau implicit. [Quinn, 1994] Practic, sunt mai accesibile limbajele de programare care nu cer construcții de limbaj pentru paralelism, dar permit procesarea paralelă printr-un paralelism implicit. Această situație este mai ușor de realizat nu în limbajele procedurale ci în cele declarative, adică logice (Prolog) sau funcționale (Lisp), deoarece informația procedurală minimală (baza de cunoștințe, knowledge) trebuie paralelizată de un compilator „inteligent” care funcționează pe bază de reguli de deducere, cu o interacțiune foarte limitată cu programatorul. Reprezentarea declarativă a cunoștințelor sau a problemei de rezolvat poate specifica fără echivoc o soluție. Totuși, poate fi destul de dificil să se convertească aceste cunoștințe într-un program paralel imperativ (nu declarativ). [Braunl, 1993]

Indiferent dacă paralelismul este implicit sau explicit, trebuie să existe o cale de a crea procese paralele și o cale de a coordona activitatea acestor procese. Uneori, procesele lucrează asupra datelor proprii și nu interacționează. Dar, atunci când procesele interschimbă rezultate, ele trebuie să comunice și să se sincronizeze între ele. Comunicarea și sincronizarea pot fi realizate prin variabile partajate sau prin transfer de mesaje.

Comunicarea datelor în sisteme concurente

Comunicarea constă în schimbul de date (informații) între procesele care cooperează. Comunicarea se poate identifica cu transmiterea de mesaje între procesele concurente.

Se pot identifica trei criterii de clasificare a tipurilor de comunicare:

după mijlocul de comunicare;

după gradul de sincronizare;

după modul de precizare a sursei și destinației comunicării.

In continuare detaliem aceste clasificări.

după mijlocul de comunicare avem:

comunicare prin memorie comună;

comunicare prin mecanisme specifice de tip monitor, semafor, resursă, canal;

Observație. Deoarece o zonă de memorie utilizată în comun este o resursă critică, rezultă că, în acest caz, se impune programarea de secțiuni critice și implicit rezolvarea problemei excluderii mutuale.

după gradul de sincronizare avem cele două clase naturale de comunicare și anume:

comunicarea fără sincronizare, care se poate identifica cu transmiterea asincronă de mesaje, deci comunicare fără semnal de recepție și

comunicarea cu sincronizare, care se poate identifica cu transmiterea sincronă de mesaje. La rândul ei, comunicarea cu sincronizare poate fi făcută:

cu sincronizare simplă sau

prin invocare la distanță.

In categoria comunicare prin sincronizare simplă putem încadra emiterea mesajului cu semnal de recepție, comunicarea prin canale sau cu punct de întâlnire de tip rendez-vous.

In cazul invocării la distanță recepția mesajului înseamnă și semnal de recepție și un răspuns de la destinatar la expeditor. Chiar și în sintaxa unor limbaje de programare concurente, invocarea la distanță apare ca și generalizare a comunicării prin canale sau ca un rendez-vous extins. Pe de altă parte, invocarea la distanță reprezintă mecanismul RPC, Remote Procedure Call, de implementare a modelului Client-Server de interacțiune între procese: mai multe procese (active) acționează în calitate de clienți asupra unui proces server (pasiv) ce urmărește în principal satisfacerea cererilor clienților.

după modul de precizare a sursei și destinației, comunicarea se poate face prin precizarea

explicită sau

indirectă a partenerilor implicați în comunicare.

Prin precizare indirectă se va înțelege că se folosește un intermediar între procesele care comunică. De exemplu, un astfel de intermediar ar putea fi un canal de comunicare care preia mesajul de la procesul sursă, în timp ce procesul destinație așteaptă să preia mesajul de pe acel canal.

Toate aceste elemente vor fi reluate în paragrafele următoare.

Sincronizarea proceselor în sisteme concurente

Sincronizarea este o restricție impusă în evoluția în timp a proceselor.

Sincronizarea constă în planificarea a două procese, dacă continuarea unuia depinde de execuția celuilalt.

Pe de altă parte, conform [Ionescu, 1999], sincronizarea proceselor constă în serializarea accesului proceselor concurente la resursele partajate.

Reluând o idee din descrierea comunicării, avem că sincronizarea poate fi: (a) cu transmitere de mesaje, deci cu comunicare sau (b) fără transmitere de mesaje, adică fără comunicare. In situația (b) sincronizarea se realizează la nivelul zonelor de memorie comune proceselor concurente.

Modalitatea naturală pentru rezolvarea sincronizării se dovedește a fi cooperarea logică prin diverse structuri de date. Limbajele de programare oferă programatorului posibilitatea de a opta între utilizarea diverselor TAD-uri pentru sincronizare, cu sau fără comunicare.

Din punctul de vedere al nivelului de sincronizare, programatorul poate opta pentru: (a) sincronizare pe generație sau (b) sincronizare pe condiție.

Sincronizarea pe generație constă în întârzierea unui proces până când toate procesele din aceeași generație cu el și-au încheiat activitatea. Acest model se regăsește în rezolvarea problemei jocul vieții sau în soluțiile paralele/ concurente pentru calculul unopr valori numerice date de expresii sumă.

Sincronizarea pe condiție constă în întârzierea unui proces până când este îndeplinită o anumită condiție. Această variantă este mult mai des folosită în aplicațiile practice și datorită faptului că mecanismele de implementare a sincronizării pe condiție sunt mai bine reprezentate în majoritatea limbajelor de programare cu facilități pentru concurență.

După Quinn [1994], există două metode de sincronizare: (1) sincronizarea (pentru) de precedență și (2) sincronizarea pentru excludere mutuală. Sincronizarea de precedență asigură că un eveniment nu începe până când un altul nu s-a încheiat. Sincronizarea pentru excludere mutuală asigură că, la un moment dat, numai un proces intră în secțiunea critică a codului cu care se prelucrează datele partajate.

Excluderea reciprocă

Din considerente practice s-a ajuns la necesitatea ca, în contexte concrete, o secvență de instrucțiuni din programul de cod al unui proces să poată fi considerată ca fiind indivizibilă. Prin proprietatea de a fi indivizibilă înțelegem că odată începută execuția instrucțiunilor din această secvență, nu se va mai executa vreo acțiune, dintr-un alt proces, până la terminarea execuției instrucțiunilor din acea secvență. Aici trebuie să subliniem un aspect fundamental și anume că această secvență de instrucțiuni este o entitate logică care este accesată exclusiv de unul dintre procesele curente. O astfel de secvență de instrucțiuni este o secțiune critică logică. Deoarece procesul care a intrat în secțiunea sa critică exclude de la execuție orice alt proces curent, rezultă că are loc o excludere reciprocă (mutuală) a proceselor între ele. Dacă execuția secțiunii critice a unui proces impune existența unei zone de memorie pe care acel proces să o monopolizeze pe durata execuției secțiunii sale critice atunci acea zonă de memorie devine o secțiune critică fizică sau resursă critică. De cele mai multe ori, o astfel de secțiune critică fizică este o zonă comună de date partajate de mai multe procese.

Problema excluderii mutuale este legată de proprietatea secțiunii critice de a fi atomică, indivizibilă la nivelul de bază al execuției unui proces. Această atomicitate se poate atinge fie valorificând facilitățile primitivelor limbajului de programare gazdă, fie prin mecanisme controlate direct de programator (din această a doua categorie fac parte algoritmii specifici scriși pentru rezolvarea anumitor probleme concurente).

Problema excluderii mutuale apare deoarece în fiecare moment cel mult un proces poate să se afle în secțiunea lui critică. După Andrews [1991], excluderea mutuală este o primă formă de sincronizare, ca o alternativă pentru sincronizarea pe condiție.

Problema excluderii mutuale este una centrală în contextul programării concurente. Rezolvarea problemei excluderii mutuale depinde de îndeplinirea a trei cerințe fundamentale și anume:

excluderea reciprocă propriu-zisă – care constă în faptul că la fiecare moment de timp cel mult un proces se află în secțiunea sa critică;

competiția constructivă, neantagonistă – care se exprimă astfel: dacă nici un proces nu este în secțiunea critică și dacă există procese care doresc să intre în secțiunile lor critice atunci unul dintre acestea va intra efectiv;

conexiunea liberă între procese – care se exprimă astfel: dacă un proces „întârzie” în secțiunea sa necritică atunci această situație nu trebuie să împiedice alt proces să intre în secțiunea sa critică (dacă dorește acest lucru).

Indeplinirea condiției a doua asigură că procesele nu se împiedică unul pe altul să intre în secțiunea critică și nici nu se invită la nesfârșit unul pe altul să intre în secțiunile critice. In condiția a treia, dacă „întârzierea” este definitivă, aceasta nu trebuie să blocheze întregul sistem (cu alte cuvinte, blocarea locală nu trebuie să antreneze automat blocarea globală a sistemului).

Excluderea reciprocă (mutuală) fiind o un concept central, esențial al concurenței, în paragrafele următoare vom reveni asupra rezolvării acestei probleme la diferite nivele de abstractizare și folosind diferite primitive. Principalele abordări sunt:

folosind suportul hardware al sistemului gazdă: rezolvarea excluderii mutuale se face cu TAS-uri; aceste primitive testează și setează variabile booleene (o astfel de variabilă este asociată unei resurse critice); un TAS nu este o operație atomică;

folosind arbitrajul memoriei comune: soluția vizează secțiunile critice și nu resursele critice (cum s-a lucrat la nivelul TAS-urilor); la acest nivel aplicațiile folosesc semafoare;

folosind suportul software: rezolvarea excluderii mutuale se bazează pe facilitățile oferite de limbajele de programare pentru comunicarea și sincronizarea proceselor executate nesecvențial.

interblocarea

Un grup de procese concurente se spune că sunt interblocate dacă fiecare deține resurse comune care trebuie să fie alocate de alte procese pentru a-și continua execuția. [Quinn, 1994]

Interblocarea poate apărea ori de câte ori mai multe procese partajează resurse într-o manieră nesupervizată. De aici rezultă că interblocarea poate să apară atât în sisteme care operează în multiprogramare, cât și în sistemele multicalculator și multiprocesor.

Când un proces își alocă o resursă se spune că blochează acea resursă. Operațiile LOCK și UNLOCK corespund operatorilor P și V definiți de Dijkstra pentru semafoarele binare [Dijkstra, 1968].

Exemplul 1. Intr-un sistem multiprocesor poate apărea următoarea situație de interblocare în care sunt implicate două procese, Proces 1 și Proces 2 și două resurse, A și B:

Exemplul 2. Intr-un sistem multicalculator poate să apară un caz particular de interblocare și anume cea de tip buffer deadlock. Să considerăm un sistem multicalculator în care procesele comunică sincron. Aceasta înseamnă că atunci când un proces E trimite un mesaj către un alt proces, D, expeditorul E se blochează în așteptarea confirmării de la destinatarul D. In această situație, la expediere, mesajul este depus într-un buffer de mesaje ale destinatarului. Presupunem că mai multe procese au trimis mesaje către D, acesta nu le-a preluat la timp și bufferul este plin. Cât timp D nu citește mesaje (deci nu-și descarcă bufferul), nici un mesaj trimis către D nu va mai putea fi recepționat și toate procesele expeditor sunt blocate în așteptarea confirmării. Fie I un proces care încearcă să trimită mesaje către D cât timp bufferul este plin. Dacă D așteaptă să citească CU PRIORITATE mesaj de la I atunci procesul D se va bloca în așteptarea mesajului de la I. La rândul lui, procesul I este deja blocat în așteptarea confirmării de la D. Rezultă că cele două procese sunt interblocate datorită umplerii bufferului de recepționare a mesajelor.

In general, interblocarea poate apărea dacă:

sistemul trebuie să asigure excludere mutuală a proceselor la accesul pe resurse comune;

sistemul nu respectă condiția de preemption (previziune, prioritate): un proces nu eliberează resursele pe care le deține până când nu le-a utilizat pe toate;

sistemul trebuie să respecte condiția de resource waiting: fiecare proces deține resursele cât timp așteaptă ca alte procese să le elibereze pe ale lor;

există un lanț de procese în așteptare: fiecare proces așteaptă să se elibereze resursele pe care le deține un alt proces din lanț.

Indiferent de tipul de sistem nesecvențial, acesta trebuie să fie prevăzut cu mecanisme specifice pentru detectarea interblocării. Cu alte cuvinte, interblocarea este o stare curentă a sistemului care trebuie evitată.

Rezolvarea problemei interblocării poate fi privită în trei moduri:

prima abordare este să se detecteze apariția interblocării și să se încerce refacerea contextului anterior interblocării;

a doua abordare este să se evite interblocarea prin utilizarea IN AVANS a informațiilor referitoare la cererile de resurse, astfel încât să se realizeze un control al alocării resurselor care să PREÎNTÂMPINE apariția interblocării;

a treia abordare este să se prevină interblocarea prin a interzice apariția situațiilor 2, 3 sau 4 anterioare.

primitive pentru implementarea concurenȚei. mecanisme ipc

Diversitatea sistemelor concurente a impus dezvoltarea mecanismelor de lucru în astfel de sisteme, astfel încât fiecare sistem să-și poată impune și valorifica propriile caracteristici legate de comunicarea și sincronizarea elementelor componente.

Astfel, se pot deosebi o serie de sisteme potrivite din punct de vedere practic pentru a comunica prin memorie partajată, în timp ce altele, din contră, nu-și respectă caracteristicile dacă ar adopta comunicarea prin memorie partajată. Iată câteva exemple.

Aplicații care acceptă comunicarea prin memorie partajată:

aplicații pentru un sistem neprotejat, cum sunt cele dezvoltate pentru un grup de calculatoare distincte; aici toate procesele și sistemul de operare rulează într-un același spațiu de adresă sau folosesc adrese fizice, nemapate ale mașinilor;

un program care să ruleze într-un spațiu de adresă separat, peste un sistem de operare, în care (1) mecanismele de multi-thread sunt furnizate numai de limbaj sau (2) procesele multi-thread sunt cunoscute la nivelul sistemului de operare; un exemplu pentru această situație este un server care deservește mai mulți clienți;

un program care implementează un modul al sistemului de operare; aici exemplele frecvente sunt pentru UNIX.

O aplicație care recunoaște comunicarea prin memorie partajată va rula pe un sistem uniprocesor sau pe unul multiprocesor cu memorie partajată, dar este de așteptat să aibă diverse comportări și performanțe pe medii de lucru diferite.

Aplicații care sunt mai potrivite în sisteme fără memorie partajată:

aplicații pentru un sistem protejat, de exemplu un sistem multiutilizator, în care procesele se execută în spații de adresă distincte; aici sunt incluse sistemele cu comunicare client-server peste un micronucleu;

aplicațiile de comunicare între procese situate pe mașini distincte, de exemplu în sistemele de control la nivel de proces;

aplicații pentru sisteme în care este importantă menținerea flexibilității asupra locului în care se încarcă procesele. Procesele care folosesc mecanisme IPC cu memorie partajată sunt restricționate să se încarce pe aceeași mașină, în timp ce cele care folosesc mecanisme IPC nespecifice memoriei partajate se pot încărca atât pe mașina gazdă cât și pe mașini la distanță;

aplicații pentru sisteme care au facilități de migrare a proceselor pentru a asigura o încărcare echilibrată și corectă a proceselor pe diverse mașini.

Pentru programarea acestor clase de sisteme vom lua în discuție în paragrafele următoare o serie de mecanisme de implementare a concurenței la nivel low-level sau la nivelul limbajelor de programare de nivel înalt. Elementele discutate se vor axa pe prezentarea mecanismelor de comunicare între procese (IPC, Inter Process Communications), la diferite nivele de abordare.

In Figura 13 este reprezentată evoluția mecanismelor și primitivelor IPC.

Variantele IPC cu sau fără memorie partajată se regăsesc în două modalități duale de abordare a comunicării și anume: procesul activ fie apelează o procedură de interfață a unui modul pasiv (monitor), fie trimite un mesaj în care formulează o cerere specifică. Aceste alternative se încadrează într-o clasificare mai generală a mecanismelor IPC de nivel înalt care deosebește:

mecanisme IPC pentru transmiterea de mesaje (message passing)

transmitere asincronă sau cu zone tampon;

transmitere sincronă sau fără zone tampon;

mecanisme IPC procedurale

apel de procedură pentru obiecte pasive, lucrul cu monitoare;

apel de procedură pentru obiecte active, mecanismul cu rendez-vous.

Figura 13. Evoluția primitivelor IPC

In Figura 14 sunt descrise cele mai reprezentative mecanisme IPC de nivel înalt.

O clasă superioară de mecanisme IPC este dată de modalitățile de comunicare distribuită între procese (Distributed IPC). Acestea apar ca necesare în sistemele hard și/sau soft distribute și, implicit, trebuiesc privite și analizate prin prisma structurilor sistemelor pe care le deservesc. Din acest punct de vedere este de remarcat modelul client-server de implementare a aplicațiilor distribuite, care este în strânsă legătură atât cu suportul fizic și logic de comunicare disponibil în sistem, cât și cu limbajul pe care sistemul respectiv îl suportă. O alternativă la abordarea client-server este modelarea obiectuală a sistemelor. Aceasta aplică tehnologia programării orientate obiect, OOP, la nivelul sistemelor prin interpretarea fiecărei resurse partajate ca un obiect [Coulouris, 1999].

Transmitere de mesaje

asincronă sau cu buffer

mesaj

posibilă întârziere

Transmitere de mesaje

sincronă sau fără buffer

Structură procedurală

pasivă de tip monitor

Structură procedurală

activă de tip rendez-vous

Figura 14. Mecanisme IPC de nivel înalt

Primitive low – level pentru sincronizare

In cele ce urmează vom lua în discuție unele primitive low-level (de nivel de bază) utile pentru implementarea sistemelor concurente. Conform reprezentării din Figura 13, la acest nivel vom aborda sincronizarea prin evenimente și sincronizarea bazată pe semafoare.

Sincronizarea proceselor la nivel de eveniment

Odată cu descrierea rolului proceselor în implementarea sistemelor concurente, am adus în discuție un mecanism de implementare care permite unui proces cunoscut de sistemul de operare să se sincronizeze cu un eveniment hardware, de obicei recunoscut printr-un semnal de întrerupere. Ulterior, cerințele pentru interacțiunea proceselor au completat această necesitate de sincronizare a proceselor cu componentele hard cu oportunitatea de a considera cerința ca un proces să se sincronizeze cu un alt proces.

Coroborând cele două aspecte, se poate extinde sincronizarea între procese la sincronizarea la nivel de eveniment, pornind de la următoarele două soluții: (1) fiecărui eveniment hardware îi este asociat câte un proces dedicat; mai mult, se poate impune ca un proces să aștepte (să recepționeze) mai multe evenimente, dar unui eveniment să îi corespundă un proces unic; (2) un același eveniment hardware poate fi preluat spre interpretare de către mai multe procese.

In aceste cazuri operațiile WAIT și SIGNAL se vor aplica pe evenimente și nu pe procese. Astfel, un proces care încearcă alocarea pentru sine a unei resurse hardware trebuie să execute o operație WAIT(EVENT) prin care așteaptă producerea evenimentului EVENT pe care îl recunoaște că reprezintă disponibilizarea resursei solicitate. Procesul respectiv va fi blocat până la producerea evenimentului. Concret, disponibilizarea resursei constă în executarea unei operații SIGNAL(EVENT), în urma căreia, toate procesele care așteptau producerea evenimentului EVENT se vor debloca. Dintre toate procesele din lista de așteptare, numai unele își vor continua execuția prin alocarea resursei eliberate. Alegerea acestor procese cade în sarcina sistemului de planificare a proceselor.

Deoarece operațiile fundamentale WAIT și SIGNAL se execută pe evenimente, vom spune că în acest caz sincronizarea proceselor implicate este bazată pe evenimente.

Sincronizarea pentru acces exclusiv la zone partajate

O soluție primară, elementară pentru rezolvarea problemei excluderii mutuale ar putea consta în a asocia fiecărei resurse critice o variabilă booleană. Cele două stări posibile ale acestei variabile vor corespunde stărilor FREE, respectiv BUSY ale resursei critice. La intrarea în secțiunea sa critică, un proces care intenționează alocarea resursei va testa starea variabilei booleene asociate resursei și va intra în secțiunea critică numai dacă a găsit resursa FREE. Un astfel de mecanism este unul de tip Test And Set și constă într-o operație

TAS (BOOLEAN) == if BOOLEAN arată că regiunea este FREE

then SET regiunea pentru a arăta că este ocupată și execută prima instrucțiune din secțiunea critică

else execută instrucțiunea următoare secțiunii critice.

Cu acest mecanism se face un pas înainte de la sincronizarea proceselor cu componentele hardware la sincronizarea între procese, dar încă se apelează la elemente hard de tipul resurselor critice pentru realizarea sincronizării.

Deoarece un TAS( ) nu este o operație atomică, acest protocol poate conduce la situații incorecte. De exemplu, un proces A citește variabila booleană, o găsește FREE, o setează la valoarea corespunzătoare stării BUSY a resursei și intră în secțiunea lui critică. Un proces B poate să citească variabila booleană a aceleiași resurse între momentul în care A a citit și el variabila și cel în care A a apucat să modifice valoarea la BUSY. Atunci B găsește și el resursa FREE și poate intra în secțiunea lui critică. Astfel, atât A cât și B sunt simultan în execuția secțiunilor critice la nivelul resursei comune, ceea ce este incorect, conform cu definiția secțiunii critice (la un moment dat, cel mult un proces este în secțiunea sa critică).

Rezultă că simpla asociere a unei variabile booleene unei resurse partajate este încă insuficientă pentru rezolvarea problemei excluderii mutuale.

Rezolvarea excluderii mutuale folosind arbitrajul memoriei comune

In cele ce urmează admitem că componentele hardware ale sistemului nu oferă nici un suport pentru realizarea sincronizării proceselor, deci nu se mai poate vorbi de testarea stării unei resurse critice partajată de procesele care trebuie să se sincronizeze.

Specificul mecanismelor de sincronizare prezentate în continuare este faptul că se pune accentul pe secțiunea critică (secvența de cod care poate fi accesată în mod unic) și nu pe resursa critică partajată. Astfel, pentru execuția unui proces oarecare putem pune în evidență secțiunea sa critică enumerând etapele execuției după cum urmează:

execută secțiune ne-critică

execută un protocol de intrare în secțiunea critică

execută secțiunea critică

execută un protocol de ieșire din secțiunea critică

execută secțiune ne-critică.

In acest mecanism, sincronizarea se face la nivelul protocoalelor de intrare și ieșire din secțiunea critică. Este o sincronizare bazată pe partajarea memoriei comune deoarece, în general, protocoalele de intrare/ieșire sunt secvențe de instrucțiuni care gestionează memoria comună pentru îndeplinirea condițiilor fundamentale care asigură excluderea mutuală (excluderea mutuală propriu-zisă, competiția constructivă și conexiunea liberă a proceselor).

Pe baza acestui mecanism s-au dezvoltat o serie de algoritmi fundamentali pentru sincronizarea proceselor și, implicit, pentru rezolvarea problemei excluderii mutuale între procese. Câțiva dintre acești algoritmi se datorează lui Dijkstra, Dekker, Eisenberg și McGuire, Peterson, Lamport [Georgescu, 1996], [Bacon, 1998], [Andrews, 1991].

In general, protocoalele de intrare/ieșire din secțiunea critică introduc variabile de control cu diverse semnificații: (a) variabile globale întregului sistem, deci accesate de toate procesele active, (b) variabile asociate câte una pentru un proces, deci valoarea unei variabile poate fi modificată numai de procesul asociat ei, dar poate fi citită și interpretată și de alte procese, (c) situații combinate.

Aceste soluții bazate pe memoria comună au unele inconveniente care pot chiar să elimine posibilitatea folosirii unor astfel de algoritmi în sisteme concurente particulare. Astfel, soluțiile sunt complicate datorită faptului că presupun ca programatorul să gestioneze cu mare atenție valorile curente ale variabilelor de control, iar o utilizare incorectă poate conduce chiar la blocarea întregului sistem (deadlock). Mai mult, algoritmii care folosesc variabile comune ale căror valori pot fi actualizate de către mai multe procese devin inutilizabili în sistemele distribuite deoarece aici nu există o zonă de memorie comună tuturor nodurilor, zonă de memorie care să stocheze astfel de variabile.

Față de această modalitate de sincronizare prin memoria comună, în cele ce urmează se vor descrie mecanisme care folosesc facilitățile limbajelor de programare scrise tocmai pentru eliminarea acestor neajunsuri.

Tipul de date semafor. Facilități și limite

Noțiunea de semafor a fost introdusă în 1968 de Dijkstra [Dijkstra, 1968] o dată cu descrierea proiectului de sistem de operare numit THE (Technische Hogeschool Eindhoven). Sistemul THE proiectează o ierarhie de resurse virtuale gestionată de un sistem de procese strict organizate pe nivele. Sistemul THE este împărțit pe șapte nivele, fiecare nivel fiind compus dintr-o colecție de obiecte abstracte și o mulțime de reguli care le guvernează. Regulile sunt materializate în proceduri numite operații primitive. Structura internă a unui obiect la un nivel dat este invizibilă la alt nivel, dar poate fi exprimată folosind obiectele și operațiile de la nivelele inferioare.

Așa cum a fost introdus de Dijkstra, un semafor este un tip de date. Asupra unei variabile de tip semafor se pot executa operațiile WAIT(SEMAFOR) și SIGNAL(SEMAFOR) numite în acest context și primitive. Această denumire este justificată și de faptul că aceste operații sunt atomice la nivelul semafoarelor pe care sunt apelate. Mai mult, această proprietate permite semafoarelor să fie utilizate cu succes în rezolvarea problemei excluderii mutuale.

Se observă extinderea aplicării operațiilor elementare pentru sincronizare, WAIT și SIGNAL, de la nivelul proceselor și al evenimentelor la nivelul variabilelor semafor. Aplicarea acestor operații la nivel de proces presupune identificarea proceselor printr-un nume unic și, de aceea, apelurile WAIT și SIGNAL permit numai sincronizarea unor procese organizate de o manieră statică, în care comunicarea se face numai unu-la-unu. Aceste inconveniente sunt depășite de apelurile WAIT și SIGNAL pe semafoare deoarece un apel WAIT(SEMAFOR) poate fi executat de mai multe procese pentru a aștepta după unul sau mai multe procese de semnalizare, în timp ce un apel SIGNAL(SEMAFOR) poate fi executat de mai multe procese pentru a semnaliza un proces în așteptare.

Reprezentarea specifică a tipului semafor este dată printr-un număr natural (întreg pozitiv) și o coadă atașată operației WAIT(SEMAFOR), dar despre disciplina de coadă nu se precizează nimic [Georgescu, 1996]. Dacă valorile pe care le poate lua o variabilă semafor sunt numai 0 și 1 atunci semaforul este unul binar. Cele două tipuri de date, semafoarele generale și semafoarele binare, sunt echivalente [Georgescu, 1996].

Definițiile operațiilor cu semafoare sunt următoarele:

WAIT(SEMAFOR) == if valoarea lui SEMAFOR este nenulă (pozitivă)

then se micșorează cu o unitate această valoare și se trece la executarea instrucțiunii următoare

else procesul care execută această operație este blocat la semaforul SEMAFOR.

SIGNAL(SEMAFOR) == if există procese blocate la semaforul SEMAFOR

then se deblochează unul dintre ele

else se mărește valoarea lui SEMAFOR cu o unitate.

Atomicitatea primitivelor WAIT() și SIGNAL() constă în faptul că operațiile interne corespunzătoare acestor primitive sunt indivizibile. Astfel, pentru un apel WAIT(), succesiunea comparare + decrementare este indivizibilă, iar pentru un apel SIGNAL(), succesiunea comparare + deblocare sau comparare + incrementare sunt, de asemenea, indivizibile.

Este foarte important de subliniat că în timp ce două operații asupra aceluiași semafor se execută prin excludere mutuală, pentru două operații asupra unor semafoare distincte este posibilă suprapunerea executării lor.

Putem privi un modul de gestiune a semafoarelor ca un TAD manager care poate fi localizat la nivelul sistemului de operare – pentru semafoarele răspunzătoare de procesele sistem – sau la nivelul limbajului de programare – pentru celelalte semafoare.

Utilizarea semafoarelor este o modalitate de lucru folosită cu succes în rezolvarea excluderii mutuale a proceselor concurente, în sincronizarea proceselor cooperative, în instanțierea multiplă a unei resurse partajate.

In capitolele următoare vom reveni cu exemple pentru utilizarea semafoarelor.

Implementarea operațiilor cu semafoare trebuie să rezolve probleme legate de concurența la nivelul semafoarelor, planificarea cozii asociate operației WAIT prin metode specifice (inversarea priorității, moștenire).

Este de remarcat rolul semafoarelor în realizarea comunicării între procese. Astfel, semafoarele devin un mijloc real de implementare a mecanismelor IPC. Totuși, dacă considerăm că semaforul este singurul mecanism de tip IPC al unui limbaj de programare, atunci încă pot apare o serie de probleme specifice care pun în evidență dezavantaje ale folosirii semafoarelor, cum ar fi:

se poate greși ușor în programarea semafoarelor: dacă programatorul uită să folosească apelul WAIT atunci, accidental, poate să acceseze date partajate neprotejate; sau dacă programatorul uită să execute un apel SIGNAL atunci poate să lase o structură de date blocată indefinit;

nu este posibil să avem o listă de semafoare ca argument pentru WAIT; dacă aceasta ar fi acceptată atunci ar putea fi programate diferite variante de ordonare a acțiunilor, conform cu starea curentă a sosirii semnalelor de tip SIGNAL.

timpul cât un proces este blocat la un semafor nu este limitat;

nu există nici un mijloc prin care un proces să poată controla un alt proces;

dacă semafoarele sunt singurul mecanism IPC din sistem și este necesar să se transmită informații între procese atunci, pe lângă sincronizarea simplă, procesele ar trebui să partajeze măcar o parte a spațiului de adresă pentru a accesa direct zona de date partajate care poate fi scrisă; valoarea unui semafor poate fi folosită pentru a transmite informații primare, dar aceste informații nu sunt accesibile proceselor;

operațiile cu semafoare au un nivel foarte scăzut de abstractizare (primitive low-level) și este evidentă lipsa structurării, condiție obligatorie în programarea modernă;

valoarea semafoarelor nu poate fi controlată decât prin primitivele WAIT() și SIGNAL(). Astfel un semafor nu poate apărea în expresii logice.

Tinând cont de toate aceste probleme, se vede că un limbaj de programare destinat aplicațiilor concurente trebuie să dețină și mecanisme de tip IPC care să completeze facilitățile oferite de semafoare. Multe dintre aceste inconveniente se elimină dacă situațiile de blocare în așteptare sunt asociate cu posibilitatea de a crea procese-fii care să continue execuția în timp ce părintele rămâne în așteptare. După Bacon [1998], alternativele pentru semafoare sunt tipurile de date EVENTCOUNT și SEQUENCER, introduse în [Reed, Kanodia, 1979], precum și bibliotecile de lucru cu threaduri cum ar fi threadurile POSIX [IEEE, 1988]. In plus, putem aminti și tipurile abstracte de date mai evoluate cum este MONITORul (care va fi tratat în paragraful următor). Tipul monitor a fost introdus în [Hoare, 1974].

O variabilă de tip EVENTCOUNT numără aparițiile unui eveniment prin incrementarea indefinită a valorii sale. O astfel de variabilă este inițializată implicit la pornirea sistemului. Prin operații specifice, acest tip de date devine disponibil proceselor active din sistem. De exemplu, procesele pot dicta acțiuni de executat asupra variabilelor EVENTCOUNT.

O variabilă de tip SEQUENCER este folosită pentru a ordona acțiunile proceselor concurente. Tipul acesta de date recunoaște o singură operație specifică.

De-a lungul anilor, UNIX a fost subiectul mai multor încercări de standardizare, cea mai remarcabilă fiind cea a comitetului IEEE, POSIX. Aceștia au creat standardul IEEE 1003.1 pentru apelurile de sistem UNIX (biblioteca de funcții). Standardul POSIX a fost larg răspândit și adoptat. Pentru subiectul acestui material este important pachetul de lucru cu threaduri și suportul threadurilor POSIX pentru sincronizare. Detaliile acestea se găsesc în standardul POSIX 1003.4a despre pthreads [IEEE, 1988]. Threadurile POSIX se execută într-un singur spațiu de adresă, prin partajarea acestuia. Pentru sincronizare, sunt furnizate mecanisme bazate pe mutex-uri (mecanisme software de sincronizare a proceselor pentru excluderea mutuală a accesului la resurse partajate) și pe variabile de condiție. Un mutex poate fi privit ca un caz particular de semafor binar. O variabilă de condiție permite unui thread să-și blocheze propria execuție până când anumite date partajate intră într-o anumită stare.

Un MONITOR are structura unui obiect abstract de date. Datele încapsulate într-un monitor sunt partajate și fiecare operație este executată sub excludere mutuală. Implementarea monitoarelor trebuie să asigure că, în fiecare moment, numai un proces este activ în monitorul respectiv. Monitoarele au avantajul de a asigura excluderea mutuală la nivelul operațiilor interne, dar, acolo unde se impune sincronizarea pe condiție, monitoarele pot folosi și variabile de condiție. Asupra noțiunii de monitor vom reveni în paragrafele următoare.

Primitive de limbaj pentru cazul memoriei partajate

Operațiile cu primitive low-level descrise anterior se pot regăsi și în limbaje de nivel înalt care își propun să suporte aplicații concurente. Totuși, din limitele semafoarelor (enumerate mai sus) se poate vedea că numai aceste tipuri de operații elementare nu pot asigura corectitudinea programelor concurente. Un nivel superior de asistență ar putea fi asigurat dacă programatorul ar putea preciza compilatorului:

care sunt datele partajate de procese;

care primitivă (semafor, de exemplu) se asociază cu care date partajate;

unde sunt localizate în program zonele critice de acces la datele partajate.

In acest caz, compilatorul ar trebui să poată să verifice și să asigure că datele partajate sunt accesibile numai într-o anumită zonă critică, că zonele critice sunt accesate și părăsite de procese de o manieră corectă.

Principalele mecanisme IPC care valorifică proprietatea aplicației de a folosi memoria partajat sunt: secțiunile critice, expresiile de tip cale și mecanismele procedurale de tip monitor (obiect pasiv) sau rendez-vous procedural (entitate activă).

Pentru cazul memoriei partajate sunt necesare restricții suplimentare asupra limbajului de programare, de exemplu:

orice tip de dată să recunoască atributul shared (partajat);

limbajul să recunoască o declarație de secțiune, region¸ de forma:

region <shared_data> begin

…

end

Se delimitează astfel secțiunile critice la nivel logic, adică la nivelul limbajului de programare.

De exemplu, folosind această structură, compilatorul poate crea câte un semafor pentru fiecare declarație de date partajate și poate insera o operație WAIT(SEMAFOR) la începutul regiunii critice și o operație SIGNAL(SEMAFOR) la sfârșitul regiunii critice.

Pentru gestionarea proceselor care concură la alocarea unei resurse sau a proceselor care cooperează pentru îndeplinirea unei sarcini comune, limbajul concurent trebuie să beneficieze de operații suplimentare, cum ar fi accesul gardat (condiționat) la resursa partajată sau utilizarea secțiunilor critice condiționate. De exemplu, pentru sincronizare cu secțiuni critice condiționate, fiecărei secțiuni critice condiționate i se asociază logic o operație de tip AWAIT(CONDITIE).

Concret, primitivele de al nivelul limbajului de programare destinate sincronizării accesului la datele partajate sunt monitoarele și extinderile acestora.

Monitoare

Așa cum am arătat și anterior, un monitor are structura unui obiect de date abstract, care încapsulează date și operații [Hoare, 1974]. Datele încapsulate într-un monitor sunt partajabile, iar fiecare operație este executată sub excludere mutuală. Din aceste considerente rezultă imediat trei avantaje importante ale monitoarelor și anume: (1) monitoarele introduc posibilitatea modularizării aplicațiilor concurente, (2) executarea unei secțiuni critice la nivelul unui proces se poate lansa prin apelul unei metode a unui monitor și (3) monitoarele rezolvă prin definiția lor problema excluderii mutuale a accesului la secțiunile critice.

Pe lângă asigurarea excluderii mutuale, pentru rezolvarea problemelor ce apar în aplicațiile concurente mai trebuie completate mecanisme pentru sincronizarea pe condiție (sau condiționată). In limbajele cu monitoare această problemă este rezolvată prin introducerea unui tip de date special pentru variabilele de condiție. Programatorul declară o variabilă de condiție necesară aplicației și modulul de gestionare a monitoarelor va defini o coadă asociată variabilei respective. Mai mult, gestionarea monitoarelor se referă implicit și la gestionarea acestor cozi astfel încât, împreună cu protocolul de organizare a proceselor care solicită accesul la monitor, să se asigure sincronizarea proceselor între ele cu respectarea condițiilor asociate variabilelor de condiție definite.

Asupra variabilelor de condiție sunt recunoscute operațiile WAIT și SIGNAL cu următoarele semnificații: WAIT determină autoîntârzierea procesului care apelează WAIT(VAR_COND) prin depunerea lui în coada asociată lui VAR_COND; ulterior, acest proces este eliberat de către un alt proces care execută o operație SIGNAL(VAR_COND) asupra aceleiași variabile de condiție. Dacă există mai multe procese care așteaptă la VAR_COND atunci sigur unul este eliberat. Implicit, SIGNAL nu are efect dacă coada lui VAR_COND este vidă.

Observație. Un semafor se reprezintă printr-un întreg și o coadă, în timp ce o variabilă de condiție se reprezintă numai printr-o coadă de așteptare. De aici rezultă două îmbunătățiri ale limitelor semafoarelor: (1) nu se pune problema semnalelor SIGNAL de tip “wake-up waiting” și (2) procesul care execută WAIT este depus necondiționat în coada de așteptare a variabilei de condiție.

Monitoarele sunt structuri pasive care permit proceselor active care le apelează metodele să se succeadă pentru a obține cooperarea și/sau competiția cu alte procese. Prin mecanisme specifice, monitoarele organizează cozi pentru resursele partajate și gestionează buffere de comunicare între diferite tipuri particulare de procese active (de exemplu, producător – consumator, cititor – scriitor).

Monitoarele sunt modelul de sincronizare folosit în Java. Vom reveni asupra acestui aspect în paragraful Suportul Java pentru concurență.

Excludere pe obiect

Un monitor încapsulează o singură structură de date partajate. Pentru cazul în care există mai multe obiecte de un anumit tip de date partajate, lucrul cu monitoare impune ca odată cu blocarea accesului la datele partajate să se blocheze implicit accesul la toate obiectele de date partajate. Uneori această soluție este convenabilă, dar există și situațiii în care ea este prea restrictivă.

De exemplu, pentru un modul de gestionare a fișierelor, operațiile elementare open, close, read, write pot fi asociate cu tipul file. Fiecare fișier poate fi subiectul unei excluderi de tip mai mulți cititori – un scriitor. Dacă pentru implementarea acestui modul de gestionare a fișierelor se folosește un monitor pentru toate fișierele atunci apare o restricție prea puternică și anume: numai un proces poate executa codul monitorului la un moment dat, deci se interzice implicit accesul simultan a mai multor cititori la fișiere. Este de preferat următoarea soluție: în loc ca o singură blocare să protejeze intrarea în monitor, o blocare să fie asociată cu obiectul de date fișier.

Se obține astfel o generalizare și o îmbunătățire a lucrului cu monitoare, bazată pe excluderea pe obiect. Fiecare apel la managerul de obiecte partajate trebuie să aibă ca argument identificatorul objet_ID al obiectului care se dorește a fi alocat/blocat. Instanțierea fiecărui obiect trebuie să recunoască o metodă de blocare. Dacă implementarea blocării folosește un semafor atunci operațiile de la nivelul semaforului pot fi folosite pentru a asigura accesul exclusiv la obiecte. Blocarea poate fi transparentă sau nu programatorului.

Sincronizarea la nivelul operațiilor

Dacă sincronizarea proceselor se face cu monitoare atunci un proces care intenționează să execute o operație asupra unor date partajate trebuie să apeleze o metodă a unui monitor și abia după aceasta (eventual după un timp de așteptare) poate să intre în monitor. Odată intrat în monitor, procesul poate fi în continuare întârziat dacă nu este permisă prelucrarea datelor solicitate. O soluție pentru această situație sunt operațiile cu variabile condiționate, deci primitive low-level echivalente cu lucrul cu evenimente sau cu semafoare, care sunt dificil de programat corect și solicită o serie de restricții de lucru cu operațiile WAIT și SIGNAL.

O alternativă bună pentru această soluție este să se coboare problema sincronizării la nivelul operațiilor obiectelor. In acest caz se decide continuarea execuției unei operații numai dacă starea obiectului respectiv permite executarea acelei operații. Astfel, întârzierea începerii execuției operației ar putea acoperi atât întârzierea intrării în monitor a procesului de inițializare a operației, cât și întârzierile de sincronizare în interiorul monitorului.

Expresii de tip cale

O variantă de sincronizare la nivelul operațiilor este lucrul cu expresii de tip cale, path expressions [Campbell și Haberman, 1974]. O astfel de expresie specifică ordinea în care pot fi invocate operațiile la nivelul unui obiect și folosește numai numele operațiilor. Implicit operațiile nu sunt executate cu excludere mutuală, deci o expresie-cale trebuie să precizeze explicit această variantă de execuție a operațiilor ei. Implicit operațiile din listă pot fi executate în orice ordine și pentru oricâte instanțieri ale obiectului. Precizarea ordinii se poate face prin numerotarea operațiilor, conform cu sintaxa specifică limbajului cu care se lucrează. De exemplu, limbajul PathPascal recunoaște lucrul cu expresii de tip cale [Campbell și Kolstad, 1980].

Obiecte active

Așa cum a fost introdus anterior, monitorul este o structură pasivă de date al cărei cod este executat numai prin intermediul unui proces activ care apelează acel monitor. Dacă unui proces i se asociază în mod unic o anumită structură de tip monitor atunci acel proces va fi restricționat la a executa numai codul monitorului respectiv, indiferent care este procesul apelant.

Acest scenariu poate fi extins prin utilizarea obiectelor active, care coboară nivelul de luare a deciziilor la nivelul obiectului partajat. Se impune atunci existența unui gestionar de obiecte active, care să poată determina starea fiecăruia dintre obiectele partajate pe care le gestionează și care poate decide care este operația următoare care se execută asupra obiectului respectiv. Utilizatorii obiectului execută apeluri de procedură similare cu apelurile de metode ale monitorului.

Un avantaj al lucrului cu obiecte active constă în faptul că în acest fel se asigură sincronizarea la nivelul operațiilor și, în plus, operațiile exportate către procesul apelant sunt minimale, în sensul că ele întârzie procesul apelant un timp mult mai redus.

Când gestionarul de obiecte este gata să accepte un apel extern, el trebuie să decidă care set de operații este pregătit să preia acel apel. Dacă apar situații nedeterministe atunci și alegerea setului de operații va fi una nedeterministă. Acest stil de control al concurenței se bazează pe mecanismul de lucru cu comenzi gardate [Dijkstra, 1975]. O schemă de acest tip a fost propusă de Brinch Hansen [1978] pentru limbajul numit Distributed Processes și este folosită de limbajul ADA. Aici mecanismele de lucru specifice cu obiecte active sunt: ACCEPT, SELECT și RENDEZVOUS. [Welsh, Lister, 1981]

Primitive de limbaj fără partajarea memoriei. transmiterea de mesaje

In paragrafele anterioare s-au identificat diferite situații în care este de preferat ca procesele active să partajeze memoria. De exemplu, un server pentru mai mulți clienți este implementat convenabil prin mai multe procese server (sau threaduri) care partajează un același spațiu de adresă.

De asemenea, s-au remarcat o serie de primitive IPC (Inter Process Communications) folosite de procese pentru a impune caracterul concurent la nivelul low-level (semafoare, cozi de evenimente, numărătoare de evenimente, variabile de secvențiere) sau la nivelul limbajelor de programare de nivel înalt.

Chiar și procesele care alcătuiesc sistemele concurente și care rulează în spații de adresă distincte (nu partajează date) au nevoie să acceseze uneori informații comune. Cele mai frecvente situații de acest tip sunt cazurile în care procesele trebuie să coopereze pentru a atinge un scop comun sau, din contră, concură pentru acces la resurse comune în sistem. De aici se vede că mecanismele IPC se impun ca necesare și în sistemele de procese care nu partajează zone de memorie comune. Se deosebesc astfel două abordări IPC și anume:

datele sunt trecute („pasate”) de la un proces la altul conform cu mecanismul de legare în pipeline;

informația comună este gestionată de un proces dedicat. Aici, procesul gestionar va prelua operațiile asupra datelor pe care le încapsulează, conform cu cererile primite de la alte procese. Acest scenariu este specific modelului client – server de gestionare a proceselor, care suportă atât cooperarea cât și competiția între procese. Procesul server gestionează o resursă partajată pe care o alocă la cerere proceselor client.

Atât legarea proceselor în pipeline cât și modelul client-server suportă transferul datelor între procese, dar de o manieră fundamental diferită. Astfel, legarea în pipe transportă datele circular între procesele legate, în timp ce modelul client-server impune ca o primă acțiune să fie lansarea unei cereri care să conțină informații legate atât de operația de efectuat, cât și de datele asupra cărora se va executa operația respectivă.

Reanalizând Figura 13, se poate spune că abordarea cea mai generală a primitivelor de limbaj fără partajarea memoriei presupune atât sincronizare cât și transfer de date. Concret, avem două modalităși de exploatare: (1) flux de date sincron și (2) transfer de mesaje.

Mecanismul de lucru cu un flux de date sincron presupune că un proces poate trimite octeți într-un flux nestructurat și un alt proces poate citi octeți de pe fluxul respectiv. In acest caz, pe flux nu sunt puse informații despre structura octeților sau despre tipul de date transferate pe flux. O aplicație acare folosește un astfel de mecanism trebuie să poată interpreta datele de pe flux conform cu o structură definită a-priori, în timp ce sistemul însuși NU cunoaște această structură și nici nu oferă suport pentru aceasta.

Transferul de mesaje este un mecanism de lucru puternic înrudit cu transferul informațiilor care însoțește transmiterea parametrilor la apelul de procedură. Aici mesajul conține un antet și un corp, fiecare cu funcțiuni bine delimitate în structura mesajului. Astfel, antetul (header) conține destinația informației conținute de mesaj, iar corpul mesajului (body) conține informația propriu-zisă și argumentele de transfer. Aceste argumente pot să fie supuse sau nu unor etape de validare a mesajului.

In funcție de anumite condiții pe care le îndeplinesc procesele care comunică prin transfer de mesaje, acesta poate fi sincron sau asincron.

Programele concurente care angajează transfer de mesaje sunt numite programe distribuite. [Andrews, 1991]

Există patru tipuri de procese într-un program distribuit:

filtru – procese care preiau, prelucrează, depun date;

client – procese care solicită servicii;

server – procese care oferă servicii;

peer (egal, pereche, seamăn) – un proces peer este fiecare dintre procesele identice care interacționează pentru a furniza un serviciu sau pentru a rezolva o problemă.

O clasificare detaliată a proceselor de tip server se poate găsi în [Boian, 1999]

De exemplu, două procese peer ar putea fiecare să gestioneze o copie a unui fișier replicat și să interacționeze pentru a se păstra consistența datelor copiilor. Un alt exemplu de procese peer ar putea fi cele care interacționează pentru rezolvarea unei probleme de programare paralelă în care fiecare proces rezolvă o parte a problemei.

Atât transmiterea asincronă de mesaje cât și cea sincronă sunt mecanisme suficient de puternice pentru a programa toate tipurile de procese: filtre, clienți, servere, peers. Pentru comunicarea unidirecțională specifică filtrelor și proceselor peers, canalele se dovedesc un mijloc potrivit de realizare a comunicării. Mai mult, folosind două canale de mesaje diferite, se poate implementa corect și comunicarea între procese de tip client- server. Dacă, în plus, un client solicită mai multe răspunsuri atunci lui i se pot aloca mai multe canale de comunicare.

Detaliind clasificarea introdusă în paragraful Comunicarea datelor în sisteme concurente, principalele mecanisme IPC pentru transmiterea de mesaje sunt: porturile, canalele, mecanismele broadcast și multicast – pentru comunicarea asincronă și, respectiv, sincronizarea simplă (mecanismul rendez-vous) și invocarea la distanță (rendez-vous extins, Remote Procedure Call) – pentru comunicarea sincronă. In limbajele de programare moderne, implementarea se bazează pe suportul mecanismului de comunicare prin sockets.

Transmiterea asincronă de mesaje

Modalitatea asincronă de transmitere a mesajelor este varianta generală, care nu impune restricții de timp asupra sincronizării proceselor care comunică prin transfer de mesaje.

După cum am anticipat anterior, structura tipică a unui mesaj constă dintr-un antet și corpul mesajului. La rândul lui, antetul este format din informații referitoare la destinatarul mesajului, informații referitoare la expeditorul mesajului și informații referitoare la tipul mesajului. Aici, prin expeditor și destinatar ne referim la procesele care comunică printr-un mesaj oarecare, adică la procesul care trimite mesajul, respectiv la procesul care recepționează mesajul (sau procesul căruia îi este adresat mesajul).

Pentru ca transferul mesajelor să fie funcțional, în sistem trebuie să existe un serviciu direct răspunzător de lucrul cu mesaje. Acest serviciu de transport al mesajelor folosește antetul fiecărui mesaj pentru a identifica tipul mesajului și procesele partenere care comunică. In plus, acest serviciu poate stabili și urmări respectarea unor protocoale de comunicare între procese.

Primitivele specifice de lucru pentru transmiterea de mesaje sunt grupate în perechile: SEND și WAIT, respectiv SEND și RECEIVE.

Dacă considerăm cazul a două procese A și B care comunică la un moment dat prin transmitere de mesaje atunci acțiunile celor două procese sunt următoarele:

Procesul A – construiește și configurează mesajul, după care

– execută o operație SEND(destinatar, mesaj);

Procesul B – așteaptă la punctul de întâlnire cu A

– executând operații WAIT/RECEIVE(expeditor, spatiu_adresa), unde al doilea parametru reprezintă adresa de memorie la care să se depună mesajul.

Transmiterea este asincronă tocmai pentru că procesul A nu așteaptă de la procesul B vreun semnal prin care să i se confime recepționarea mesajului.

Acest scenariu presupune că procesele care comunică își cunosc reciproc identitatea (pot să se numească reciproc prin identificatorii transmiși ca parametri) și, în plus, există un protocol de transmitere de mesaje pe baza căruia expeditorul construiește mesajul de transmis și destinatarul interpretează mesajul primit.

Față de acest model de comunicare, din punctul de vedere al receptorului B, pot apărea cel puțin două cazuri particulare, care sunt frecvent întâlnite în practică și, de aceea, trebuiesc luate în considerare la proiectarea unui sistem de transmitere de mesaje. Acestea sunt:

dacă B nu este gata să primească mesajul (nu a executat încă o operație WAIT) atunci mesajele destinate lui B pot fi depuse într-un buffer intermediar;

dacă B a executat o operație WAIT, dar nu există mesaj atunci el poate să se blocheze în așteptarea unui mesaj sau poate să-și continue activitatea și să revină periodic cu executarea primitivei WAIT.

Uneori se impune precizarea timpului maxim de așteptare pentru a evita așteptarea indefinită a recepționării unui mesaj. Rezolvarea acestei probleme este cu atât mai necesară în sistemele distribuite în care astfel de situații de întârziere pot să apară frecvent din cauze obiective legate de faptul că mașina destinație nu este funcțională sau rețeaua de comunicație este supraîncărcată. De asemenea, această restricție se impune în mod deosebit în sistemele în timp real.

In oricare dintre situații, recepționarea mesajului coincide cu o operație DUBLĂ de copiere a mesajului: o copiere din spațiul de adresă al lui A într-o zonă intermediară de lucru și o a doua copiere din zona intermediară în spațiul de adresă al lui B. Se observă că în acest caz comunicarea se face prin intermediul unei entități suplimentare (canal, buffer s.a.), cu rol în colectarea mesajelor adresate lui B și gestionate de serviciul de transmitere de mesaje.

In funcție de restricțiile care se impun asupra proceselor partenere și asupra datelor transmise putem avea următoarele situații:

procesele care comunică nu vor sau nu trebuie să-și cunoască reciproc identitatea;

un proces trebuie să trimită un mesaj mai multor destinatari;

este necesar să existe un suport pentru deosebirea mesajelor între ele; de exemplu, să se deosebească mesajele prin care se adresează cereri de mesajele care reprezintă răspunsuri, reveniri (reply) la mesaje anterioare;

procesele sunt dispuse să aștepte mesaje pe mai multe căi;

în anumite condiții, un mesaj poate deveni „expirat” (depășit);

uneori este necesar să se răspundă la un mesaj nu numai expeditorului ci și altor procese.

Rezolvarea și implementarea acestor situații a condus la definirea unor noțiuni și concepte noi pe care le prezentăm în continuare. Implicit, aceste concepte se regăsesc în diverse primitive la nivelul fiecărui limbaj de prgramare care le recunoaște.

Comunicarea prin porturi și canale

In interiorul unui modul de program, un mesaj poate fi transmis la o anumită locație, de exemplu către o variabilă locală a programului respectiv. Dacă această locație este destinată comunicării programului cu exteriorul lui atunci limbajul programului poate să o recunoască ca pe un port de ieșire sau un canal de comunicare. In timp ce aceste entități pot fi stabilite la începutul programului, locația care preia mesajul la intrarea în program, adică portul de intrare, se poate stabili numai în timpul configurării mesajului. In plus, la configurare se stabilește și care este procesul asociat unui anumit port de ieșire, respectiv care este procesul care va prelua datele de pe un anumit canal.

Asocierile de tip

port <–> proces

nu sunt neapărat de tip unu-la-unu. Dacă procesul expeditor este la rândul lui un serviciu solicitat atunci este de evitat ca el să se blocheze între transmiterea mesajului și recepționarea răspunsului corespunzător. Mai mult, uneori este necesar ca un proces să poată să-și organizeze de o manieră proprie bufferul de mesaje (depunerea și preluarea mesajelor sosite). Pentru aceste aspecte, procesul poate să-și definească mai multe porturi de comunicare cu alte procese, porturi prin care transmite mesaje. Ulterior, procesul își va sonda periodic (polling) porturile de comunicare pentru a testa în timp util sosirea vreunui mesaj. Acest mecanism este echivalent cu comunicarea între obiecte active prin RENDEZ-VOUS implementat în limbajul ADA prin perechea de primitive SELECT – ACCEPT.

De asemenea, asocierile de tip

portIN <–> portOUT

nu sunt neapărat de tip unu-la-unu. De aici rezultă diferite scheme de transmitere de mesaje prin intermediul porturilor sau a canalelor, care conferă comunicării mai multă flexibilitate și totodată permit proiectarea unui sistem mai amplu de mesaje.

In plus, un anumit port poate fi dedicat unui anumit tip de mesaje, caz în care fiecare transfer prin acest port va fi precedat de o validare a tipului de mesaj asociat. Astfel, dacă se proiectează o comunicare între procese prin porturi „condiționate” atunci atât la ieșire, cât și la intrare, mesajele vor suporta etape de verificare a condițiilor impuse.

Un exemplu de restricție care se poate impune mesajelor este cea legată de oportunitatea preluării mesajului respectiv. Din acest punct de vedere, un mesaj poate să nu mai fie preluat dacă el este „depășit” de conținutul unui mesaj ulterior. Dacă se lucrează cu porturi dedicate atunci se poate defini dimensiunea bufferului asociat portului respectiv la 1 și politica de ocupare să fie suprascrierea. Astfel, în orice moment în buffer există un singur mesaj și anume cel mai recent pe subiectul pe care se comunică prin acel port.

Pentru aspectele legate de comunicarea condiționată, se poate folosi un limbaj de configurare a mesajelor astfel încât ele să îndeplinească structura impusă de canalele de comunicare. Un astfel de mecanism este folosit de sistemul CONIC dezvoltat de Imperial College UK. [Sloman, Kramer, 1987]

Un caz particular de comunicare este de tip (1 din n) la (1 din n). Pentru o astfel de transmitere de mesaje se pot folosi entități intermediare fără restricții (free-standing) cum ar fi porturile globale și cutiile poștale. Utilitatea acestor locații este similară cu rolul bufferului de tip bandă din comunicarea many-to-many între procese de tip producător-consumator.

O caracteristică a porturilor globale și a cutiilor poștale este faptul că, în timp ce mai mulți (n) expeditori și destinatari pot depune/prelua mesaje dintr-o astfel de locație, NUMAI unul (1 din n) execută cu succes operația la un moment dat. Această caracteristică deosebește comunicarea prin porturi globale și cutii poștale de tehnicile de comunicare de tip broadcast și multicast.

Broadcast și multicast

Un dezavantaj al transmiterii mesajelor prin porturi și canale este evident faptul că se folosesc aceste entități intermediare pentru comunicare, ceea ce este echivalent cu numirea indirectă a destinatarului (indirect naming).

Acest neajuns poate fi corectat prin broadcast – tehnică de difuzare de mesaje care constă în posibilitatea de a transmite mesaje „DE LA ORICINE” (“from anybody”) – conform cu comunicarea n la 1 – sau „CĂTRE TOȚI” (“to everyone”) – conform cu comunicarea 1 la n, fără a introduce numirea indirectă ci folosind un nume special în antetul mesajului. Astfel, comunicarea prin canal ar fi echivalentă cu posibilitatea de a primi mesaje de la un anumit grup de procese, selectat la configurarea serviciului de transmitere de mesaje, iar comunicarea prin port global ar fi echivalentă cu posibilitatea de a trimite (primi) mesaje către (de la) un grup de procese anonime, identice, dintre care NUMAI unul preia mesajul și îl interpretează (a transmis mesajul). O variantă de numire este atribuirea de nume pentru grupuri de procese în mod similar cu numirea unui proces individual.

Prin broadcast un nod al recțelei trimite un mesaj către TOATE celelalte noduri, indiferent dacă acestea sunt sau nu conectate direct cu nodul emițător. De la emițător la nodurile conectate indirect cu el, mesajul se va transmite prin FORWARD implicit. [Andrews, 1991]

In cele mai multe rețele LAN procesele partajează canale de comunicație comune. In acest caz, fiecare procesor este conectat direct cu toate celelalte procesoare. De fapt, adesea aceste rețele de comunicație suportă o primitivă specială de comunicare în rețea, numită broadcast, care transmite un mesaj de la un procesor la toate celelalte. Indiferent dacă transmiterea mesajelor de tip broadcast este sau nu suportată de partea hardware, aceasta furnizează o tehnică de programare foarte folositoare.

Se poate folosi tehnica broadcast pentru a distribui sau, din contră, pentru a grupa informații. Adesea, tehnica este folosită pentru ca procesoarele să interschimbe informații despre starea curentă a rețelei LAN. De asemenea, se poate folosi tehnica broadcast pentru a rezolva o serie de probleme de sincronizare în sisteme distribuite, de exemplu, apelând la o implementare distribuită care folosește semafoare. Ideea fundamentală pentru semafoarele distribuite, ca și pentru alte protocoale de sincronizare în sisteme distribuite, este ordonarea totală a evenimentelor care comunică. O tehnică curentă pentru ordonarea evenimentelor folosește ceasuri logice [Andrews, 1991], [Boian, 1999].

Implementarea tehnicii broadcast este îngreunată de faptul că, din păcate, în practică nu se poate considera că operația BROADCASTING este una atomică. Două mesaje trimise “to anyone” de către două procese diferite pot fi recepționate de alte procese în altă ordine (diferită de cea în care au fost trimise). Mai mult, un mesaj cu un timestamp mai mic poate fi recepționat după un mesaj cu un timestamp mai mare.

Executarea operației BROADCASTING cu transmitere asincronă de mesaje este echivalentă cu a transmite concurent același mesaj pe mai multe canale. Ca și SEND, operatorul BROADCAST este o primitivă non-blocking, adică procesul care o execută nu se blochează în așteptare după ce transmite mesajul “to anyone”. Toate copiile mesajului sunt depuse în coadă și fiecare copie poate fi preluată ulterior de unul dintre procesele implicate în comunicarea prin canalul respectiv.

Putem defini conceptul de broadcasting și pentru folosirea cu transmitere sincronă de mesaje. Pentru a păstra proprietatea de a bloca procesul care transmite, o operație BROADCAST sincronă trebuie să blocheze expeditorul până când TOTI receptorii preiau mesajul. Aceasta nu este o variantă practic recomandată pentru că, la rândul lui, procesul emițător poate fi receptor pentru alte mesaje pe care ar trebui să le confirme, s.a.m.d. Se pot defini totuși două moduri de a obține BROADCAST sincron:

utilizarea unui proces separat care să simuleze un canal de broadcast; în acest caz, clienții ar trebui să trimită și să primească mesaje prin broadcast numai pe acest canal;

utilizarea comunicării gardate: când un proces vrea atât să trimită cât și să primească mesaje de tip broadcast, el poate folosi comunicarea gardată cu două variabile poartă. In acest model fiecare variabilă poartă are un cuantificator pentru a enumera partenerii implicați în broadcast, în sensul următor: una dintre variabile are rolul de a transmite mesaj către toți partenerii (outputs), în timp ce cealaltă variabilă preia mesaj de la oricare dintre parteneri (inputs).

Prin multicast are loc o transmitere multiplă, prin care mesajul poate fi transmis „CĂTRE FIECARE” proces înscris în grup. In acest caz fiecare proces membru al grupului destinatar primește o copie a mesajului.

Primitive de cerere. Primitive de răspuns

Indiferent de mecanismul IPC folosit, operația de transmitere, respectiv de recepționare a unui mesaj se poate concretiza în primitive diferite în funcție de tipul mesajului.

Astfel, primitivele SEND și WAIT se pot regăsi în patru operații diferite:

SEND_REQUEST(destinatar, mesaj)

WAIT_REQUEST(expeditor, spatiu_adresa)

SEND_REPLY(expeditor_original, mesaj_de_raspuns)

WAIT_REPLY(destinatar_original, spatiu_adresa_mesaj_de_raspuns).

Un exemplu standard de comunicare conformă cu modelul client-server presupune o secvență de tipul:

clientul – execută SEND_REQUEST(…)

serverul – execută WAIT_REQUEST(…)

– prelucrează cererea recepționată

– execută SEND_REPLY(…)

clientul – execută WAIT_REPLY(…).

Transmiterea mesajelor este asincronă dacă clientul nu este blocat între SEND_REQUEST(…) și WAIT_REPLY(…).

De multe ori serviciul de transmitere a mesajelor furnizează utilizatorului și o primitivă REQUEST_SERVICE care înglobează pentru client întreaga secvență proprie de operații. In sistemul Amoeba, acesta este singurul mecanism oferit de nucleul de transmitere de mesaje.

In sistemele distribuite este posibil ca un client să adreseze o cerere unui server care nu o poate onora. In acest caz se poate adopta soluția retransmiterii cererii de la un server la altul până la unul care poate deservi cererea clientului. Această tehnică este cunoscută ca message forwarding (retransmitere). Retransmiterea se poate face cu REPLY către procesul client sau fără.

Transmiterea sincronă de mesaje

Reluând mecanismul de transmitere de mesaje între procesele A și B descris în primul paragraf, transmiterea este sincronă dacă procesul expeditor A este întârziat pe SEND până când destinatarul execută operația WAIT prin care confirmă disponibilitatea de a recepționa mesajul transmis de A.

Față de operațiile interne executate asupra mesajului la transmiterea asincronă, aici mesajul este copiat NUMAI O DATĂ și anume atunci când expeditorul și destinatarul s-au sincronizat (s-au întâlnit) și pot comunica. Deoarece condiția de sincronizare este implicită, rezultă că sistemele cu transmitere sincronă de mesaje sunt mai ușor de gestionat decât cele asincrone.

La transmiterea sincronă de mesaje rolul bufferului de mesaje este preluat de un proces care are rolul de a asigura o interfață între procesele care comunică. Acest proces execută o unică operație de tip WAIT(catre_oricine, orice) și asigură comunicarea prin următoarele acțiuni:

dacă un client transmite o cerere, o depozitează;

dacă serverul solicită o acțiune, o selectează din depozit și o transmite;

dacă serverul transmite un răspuns, îl depozitează;

dacă clientul solicită un răspuns, îl caută în depozit și îl transmite.

Când procesele interacționează folosind variabile partajate, fiecare proces accesează direct acele variabile de care are nevoie. La transmiterea de mesaje, numai canalele de comunicație sunt partajate, deci procesele trebuie să comunice pentru a interacționa. De aici, se impune discutarea unor tehnici de sincronizare a comunicării între procese, synchronizing IPC.

Transmiterea asincronă de mesaje, transmiterea sincronă de mesaje, comunicarea prin RPC și mecanismul rendez-vous sunt mecanisme echivalente pentru comunicarea și sincronizarea proceselor în sisteme concurente.

Invocarea la distanță. Mecanismul rendez-vous

Reluând ideile din paragraful Comunicarea datelor în sisteme concurente, avem că interacțiunile de tip client-server au stat la baza dezvoltării unor mecanisme de comunicare specifice și anume invocarea la distanță (RPC, Remote Procedure Call) și rendez-vous. Ambele metode combină aspecte întâlnite la monitoare și la transmiterea sincronă de mesaje. Ca și la monitoare, un modul sau un proces exportă operații și operațiile sunt invocate printr-un apel de tip call. Ca și o operație OUTPUT specifică transmiterii sincrone de mesaje, execuția unui apel call întârzie procesul care îl execută. [Andrews, 1991]

Noutatea pe care o aduc mecanismele RPC și rendez-vous este că o operație este un canal de comunicație bidirecțional, atât de la apelant la procesul care oferă serviciul solicitat de apel, cât și invers. In particular, apelantul întârzie până când primește un răspuns legat de încheierea execuției operației solicitate.

Diferența între RPC și rendez-vous constă în modul în care sunt deservite cererile invocate. Astfel, o primă abordare este să se declare o procedură pentru fiecare operație și să se creeze un proces nou pentru fiecare apel nou. Această abordare se numește RPC, Remote Procedure Call, deoarece apelantul și corpul procedurii apelate pot să se găsească pe mașini diferite (la distanță). O a doua abordare este ca procesul apelant „să se întâlnească” (să stabilească un rendez-vous) cu un proces existent. Un rendez-vous constă dintr-o operație de intrare, ACCEPT – prin care un proces așteaptă să fie invocat, o operația de prelucrare a cererii și operația de furnizare a rezultatului (răspunsului). Această situație este numită mai corect rendez-vous extins pentru a o deosebi de un rendez-vous simplu (sincronizare simplă). In cazul comunicării prin apel de procedură, mesajul constă în valorile parametrilor efectivi transmiși entității apelate, iar răspunsul este conținut de valorile parametrilor returnați prin referință entității apelante.

Deoarece, nici RPC, nici rendez-vous nu suportă comunicarea asincronă, rezultă că programarea proceselor filtre și peers cu aceste mecanisme NU este o abordare naturală.

Dezvoltarea programării concurente se poate face folosind numai procese și monitoare, care partajează același spațiu de adrese. Intr-un astfel de model, monitoarele încapsulează variabile partajate, în timp ce procesele comunică și se sincronizează prin apelarea metodelor monitoarelor.

Cu mecanismul RPC se poate folosi o singură componentă de programare, un modul, care să conțină atât procesele cât și procedurile (metodele). De asemenea, se permite modulelor să fie rezidente în spații de adresă diferite, eventual chiar în noduri diferite ale rețelei. Procesele interne ale unui modul pot partaja variabile și pot apela proceduri declarate în acel modul. Totuși, procesele dintr-un modul pot comunica cu procesele dintr-un alt modul numai prin apeluri de proceduri.

In esență, RPC furnizează numai un mecanism de comunicare între module. In interiorul unui modul încă trebuie programată explicit sincronizarea proceselor. In plus, programatorul trebuie să scrie procese pentru manipularea datelor communicate prin RPC.

Mecanismul rendez-vous combină acțiunea de deservire a unei cereri cu alte prelucrări solicitate de apel. Cu rendez-vous, un proces exportă operații (în sensul că operațiile sunt vizibile din afară) care pot fi apelate de alte procese.

Ca și la RPC, un proces invocă o operație prin intermediul unui apel call. La RPC apelul call numește un alt proces care să execute și o operație din acel proces care să se execute. Spre deosebire de RPC, la rendez-vous o operație este executată de același proces care o exportă.

Pentru a pune în evidență deosebirile dintre mecanismele folosite pentru transmiterea de mesaje, se pot face trei remarci comparative între comunicarea prin canal și invocarea la distanță și anume:

comunicarea prin canal se identifică cu transmiterea de mesaje între procesele care comunică, în timp ce invocarea la distanță constă în apelarea din cadrul unuia dintre procese a unei secvențe de instrucțiuni a celuilalt proces, urmând ca aceste instrucțiuni să se execute la punctul de întâlnire.

In cazul comunicării prin canal, sursa și destinația sunt univoc determinate, în timp ce pentru invocarea la distanță este precizată numai destinația. De aici rezultă că invocarea la distanță permite stabilirea unor legături de comunicare de tip n —>1.

Prin canal informația circulă de la sursă la destinație, în timp ce invocarea la distanță poate conduce mesajele în ambele sensuri.

Comparând comunicarea cu precizarea indirectă a partenerilor de comunicare cu invocarea la distanță putem spune că invocarea la distanță permite interacțiunea proceselor implicate ca entități active în comunicare, în timp ce comunicarea prin canal sau prin resurse trebuie să apeleze la entități intermediare, pasive.

Totuși, comunicarea prin canale și invocarea la distanță sunt mecanisme echivalente de realizare a aplicațiilor concurente. [Georgescu, 1996].

In Java, conceptul RPC este implementat ca un mecanism nou de programare distribuită, numit RMI, Remote Method Invocation. Acesta permite apelarea dintr-un program Java a unor metode executate pe alte mașini virtuale Java, situate chiar pe alte stații din sistemul distribuit. Acest subiect este reluat în paragraful Suportul Java pentru concurență și este abordat pe larg în [Boian, 1999], [Athanasiu s.a., 2000].

Implementarea transmiterii de mesaje

Din punctul de vedere al transpunerii în aplicații, transmiterea asincronă de mesaje presupune gestionarea ca timp și spațiu de memorie a bufferului de mesaje.

Intr-un sistem cu memorie partajată, procesele își gestionează de o manieră proprie transferurile de date prin procedeul bufferului de tip producător-consumator.

Intr-un sistem fără memorie partajată, așa cum s-a văzut și anterior, mesajele trebuiesc copiate de două ori: o dată din spațiul de adresă al expeditorului în bufferul de mesaje și apoi din bufferul de mesaje în spațiul de adresă al destinatarului. Aceste copieri pot să afecteze și alte procese din sistem, altele decât cele implicate în comunicarea curentă. Dacă în sistem există un singur buffer de mesaje atunci acesta devine o structură de date partajabilă și deci trebuie considerate metode de sincronizare a accesului la mesajele depuse într-un astfel de buffer.

Proiectarea unui sistem de transfer de mesaje trebuie să aibă în vedere:

structura mesajelor;

restricțiile impuse de mediile intermediare de transmitere a mesajelor;

gestionarea bufferului de mesaje;

tehnici de gestionare a zonelor de memorie: bufferul de mesaje, spațiile de adresă corespunzătoare mesajelor, porturile etc.

O posibilitate de implementare presupune unificarea mesajelor cu întreruperile transmise în sistem. In această abordare se va proiecta o manieră comună de transmitere și preluare a tuturor evenimentelor din sistem, indiferent dacă sunt semnale specifice lucrului cu mesaje sau întreruperi hard. Gestionarul de evenimente va interpreta ulterior fiecare eveniment și va determina tipul acestuia, urmând să fie tratat în continuare de o manieră specifică.

Canalele occam pentru comunicare sincronă

Limbajul de programare concurent occam este bazat pe comunicarea sincronă și pe faptul că procesele nu partajează memorie. [Bacon, 1998]

Limbajul occam își are originea în specificațiile CSP (Communicating Sequential Processes) [Hoare, 1985], cu deosebirea că în CSP sursa și destinația comunicării sunt procese identificate prin nume, în timp ce în occam comunicarea are loc prin intermediul unui canal identificat printr-un nume.

In occam mecanismele IPC constau în asignarea unui proces la altul. De exemplu, o atribuire de tipul

var <– expresie

trebuie interpretată astfel: procesul de evaluare a expresiei este asociat cu procesul care reține variabila. Valoarea calculată este transmisă pe canalul prin care comunică cele două procese prin : canal? var, respectiv canal! expresie.

Abstractizarea Linda

Linda a fost dezvoltat la începutul anilor ’80 [Gelernter, 1985] ca un model de programare concurentă care și-a propus să dea un nivel superior, abstract pentru IPC. Linda nu este un limbaj de programare complet nou ci este un set de primitive care pot fi folosite pentru a extinde posibilitățile unui limbaj de programare secvențial, cum ar fi: C, C++, ForTran.

In loc de mesaje, Linda folosește tuple pentru a comunica informații între procese. Un tuplu este o secvență de câmpuri cu tip predefinit. Față de mesaje, tuplele sunt obiecte de date, interne limbajului de programare gazdă.

Sockets

Un socket este un capăt de comunicație (punct final de comunicație), care poate fi numit și adresat în rețea. Un socket este caracterizat de un domeniu în care are loc comunicația și în care este numit socketul. Un socket operează într-un singur domeniu și formatul de adresă depinde direct de domeniul lui. Fiecare domeniu presupune un singur set de protocoale. Cele mai populare domenii sunt: AF_UNIX – pentru comunicații locale UNIX – și AF_INET – pentru comunicare în Internet.

Din punctul de vedere al nivelelor unei rețele, un socket este locul în care programul de aplicație se întâlnește cu furnizorul mediului de transport. Din punctul de vedere al programului de aplicație, un socket este o resursă alocată de sistemul de operare.

Din punctul de vedere al sistemului de operare, un socket este o structură de date întreținută de nucleul sistemului de operare. Această structură este referită în programul de aplicație printr-un întreg, numit descriptor de socket.

Concret, socketul este mijlocul de comunicare între parteneri. Comunicarea prin socket presupune că fiecare aplicație are alocat un socket de la sistemul de operare. Interfața de lucru cu socket ascunde utilizatorului detaliile fizice ale rețelei și este caracterizată numai prin serviciile pe care le asigură.

In funcție de entitățile transportate, se deosebesc două tipuri de sockets: socket stream și socket datagram. Corespunzător, interfața de lucru cu fiecare tip de socket va valorifica particularitățile comunicării prin flux de date, respectiv prin pachete (datagrame).

Este important de reținut că, comunicarea este posibilă numai dacă la ambele capete este utilizat același tip de socket. In funcție de tipul aplicației și de datele comunicate, programatorul va alege un anumit tip de socket și, implicit, un anumit protocol pentru transportul datelor comunicate (TCP/IP, pentru socket stream sau UDP, pentru socket datagram). Amănunte despre cele două scheme de implementare a mecanismului de lucru cu sockets se pot consulta în [Boian, 1999].

In mediile de programare care recunosc mecanismul de comunicare prin sockets (Java, Visual C++), clasele de lucru cu sockets creează o interfață elegantă și flexibilă, făcând programarea aplicațiilor pentru comunicare la fel de ușoară ca și lucrul cu fișiere. Mai mult, o interfață creată cu Java permite comunicarea cu alte programe care folosesc o interfață de același tip, dar scrisă în alt limbaj de programare, de exemplu în C++.

Printre noutățile introduse de JDK 1.1. este apariția unui nou tip de socket datagram și anume cel pentru trimiterea multiplă (multicast). Această nouă facilitate, împreună cu posibilitatea difuzării unui mesaj (broadcast) către toate stațiile dintr-o rețea sunt mecanisme puternice oferite de Java pentru comunicare în sisteme distribuite. Prin difuzare, mesajul este transmis către toate stațiile din sistem, în timp ce prin transmitere multiplă mesajul este transmis simultan către toate stațiile CARE s-au abonat la recepția mesajului. Programatorul precizează explicit tipul de comunicare prin valoarea câmpurilor adresei IP care se transmite o dată cu structura socket datagram definită pentru comunicarea respectivă. [Athanasiu, 2000], [Boian, 1999]

Suportul Java pentru concurenȚĂ

[Bacon, 1998] O cerință frecvent întâlnită la proiectarea sistemelor de comunicare este existența unui server care să poată deservi mai mulți clienți simultan. Chiar dacă un astfel de server preia cererile ca mesaje, este nevoie de mai multe threaduri de control interne care să execute acțiunile distincte prin care serverul prelucrează cererile primite de la clienți diferiți. Toate aceste threaduri trebuie să aibă acces la aceleași structuri de date, deci sunt necesare tehnici de gestionare a spațiilor comune, partajate. De aceea, un sistem cu un astfel de server trebuie să recunoască atât tehnici de partajare a memoriei, cât și transmiterea de mesaje între diferite spații de adresă.

Dacă unul dintre procesele care comunică este uni-thread atunci el se blochează până la primirea răspunsului. Dacă însă procesul respectiv este multi-thread și threadurile lui pot să se creeze dinamic atunci se poate destina un thread pentru a aștepta răspunsul de la procesul partener și threadul părinte își poate continua activitatea în paralel. Acest mecanism este specific sistemelor distribuite.

Un proces Java constă din segment de cod și segment de date mapate într-un spațiu virtual de adresare. Fiecare proces deține resurse alocate de sistemul de operare, de exemplu fișiere deschise, regiuni de memorie alocate dinamic, threaduri (fire de execuție). Aceste resurse sunt eliberate de sistemul de operare la terminarea procesului.

[Rotariu, 1999] Un thread Java este unitatea de execuție a unui proces. Fiecare fir de execuție, ca și procesul clasic, are propriul context (o secvență de instrucțiuni, un set de regiștri de prelucrare, o stivă) și rulează strict secvențial. Procesul nu execută instrucțiuni. Procesul este un spațiu de adresare COMUN pentru firele lui de execuție (unul sau mai multe). Execuția instrucțiunilor se face de către threaduri.

Având acces la același spațiu de adresare, threadurile pot să comunice prin variabile comune, ceea ce simplifică programarea. In afară de spațiul de adresă, firele de execuție accesează în comun și fișierele deschise, procesele copil, timere și semnale. Pentru situațiile în care se impune acces exclusiv la variabile trebuie implementat un mecanism de sincronizare recunoscut de platforma Java.

Mediul de execuție Java execută propriul control asupra threadurilor. Algoritmul de planificare a firelor, prioritățile și stările sunt specifice aplicației Java și sunt implementate identic pe toate platformele pe care a fost portat mediul Java. In plus, acest mediu știe să valorifice și resursele sistemului pe care lucrează (multitasking, multiprocesor). Ordinea execuției threadurilor de aceeași prioritate depinde de sistemul de operare gazdă. Pentru threaduri de priorități diferite, execuția este preemtivă (sistemul de operare poate să întrerupă execuția unui thread pentru a executa un alt thread de prioritate mai mare).

Diferența importantă între scrierea unei aplicații cu un fir de execuție principal, față de aceeași aplicație scrisă cu mai multe fire constă în necesitatea de a asigura sincronizarea threadurilor care aparțin aceluiași proces. Java oferă pentru aceasta mecanisme proprii de sincronizare, extrem de ușor de utilizat și înglobate în sintaxa de bază a limbajului. Cu ajutorul modificatorului synchronize se poate impune acces exclusiv la nivelul unui bloc (secvență) de instrucțiuni, a unei metode sau a unei instanțieri de clasă.

In favoarea argumentului că Java este un limbaj simplu spunem și că Java nu implementează complet primitivele de sincronizare prevăzute de standardul POSIX (ca în bibliotecile pthread). In același context trebuie menționat că Java nu permite determinarea în avans a posibilităților de blocare într-o regiune critică (prevedere deadlock). [Rotariu, 1999], [Athanasiu, 2000]

[Văduva, 2001] Limbajul Java gestionează sincronizarea threadurilor prin mecanisme de tip monitor. Fiecărui obiect (instanță de clasă) care are o metodă sincronizată (declarată cu synchronize pentru că trebuie accesată sub excludere mutuală) îi este asociat IMPLICIT un monitor. Obținerea și eliberarea monitorului se fac automat, atomic, de către mediul Java. Ca și în cazul lucrului cu procese, un monitor permite numai unui singur thread să apeleze o metodă a monitorului la un moment dat.

Este de remarcat că, în general, sub Java mecanismul de sincronizare este legat de un obiect și NU de o metodă sau de un bloc de instrucțiuni. In particular, dacă modificatorul synchronize este aplicat unei metode statice a unei clase, numai atunci monitorul se asociază clasei și nu obiectului.

[Athanasiu, 2000] In Java, threadurile se execută în același spațiu de adresă, deci pe aceeași mașină. Rezultă că numai programarea threadurilor nu este un mecanism suficient de puternic pentru aplicații distribuite. Odată cu dezvoltarea programării orientate obiect, s-a încercat extinderea conceptului de apel de procedură la apelul de metodă. Astfel, Java recunoaște mecanismul RMI (Remote Methods Invocation) pentru implementarea aplicațiilor client-server, ca echivalent pentru mecanismul de invocarea la distanță de tip RPC.

Arhitectura RMI este organizată pe trei nivele și anume:

nivelul obiectelor skeleton/stub;

nivelul referințelor la distanță (acțiuni diferite pentru client și server);

nivelul transport (comunicarea efectivă).

Un stub sau cotor [Boian, 1999] este obiectul care „reprezintă” serverul pe mașina clientului. Acesta are rolul de a împacheta parametrii de apel ai metodei la distanță într-un mesaj care va fi transmis prin rețea.

Un skeleton este obiectul care „reprezintă” clientul pe mașina serverului. Acesta despachetează mesajul recepționat (parametrii transmiși la apel), invocă metoda referită, obține rezultatul sau prinde o excepție generală și, în final, asamblează un mesaj de răspuns care va fi transmis clientului ca rezultat al apelului.

Obiectele skeleton și stub sunt generate automat pornind de la clasa care implementează serverul.

O dată cu JDK 1.2. s-a renunțat la skeleton și s-a implementat un mecanism de exportate bazat pe proprietatea serverului de a fi vizibil din exterior. La exportare sunt instanțiate fire de execuție care realizează transparent translatarea necesară apelului la distanță.

Probleme clasice de concurenȚĂ

Presupunând cunoscute mecanismele prezentate în paragrafele anterioare, ne propunem să luăm în discuție o serie de probleme clasice, specifice programării concurente.

Analiza cerințelor pentru obținerea soluției concurente este dirijată pe următoarele direcții:

care sunt structurile de date partajate și care pot fi modificate; cu alte cuvinte, care sunt elementele accesate prin excludere mutuală;

cum să se gestioneze așteptarea pentru acces la o resursă comună și cum să se realizeze „trezirea” proceselor în așteptare;

cum să se gestioneze diferite categorii de procese particulare de tip: producător, consumator, cititor, scriitor;

cum să se permită diferitelor procese să citească simultan, chiar dacă în același timp așteaptă acces exclusiv la un proces de scriere.

In cele ce urmează vom accepta că un buffer este o secvență oarecare de locații (sloturi), fiecare de dimensiune fixată și capabilă să memoreze date. Entitățile care au acces la conținutul bufferului sunt procesele active, atât cele de sistem, cât și cele utilizator.

In funcție de operația pe care un proces încearcă să o execute asupra bufferului, procesul respectiv devine producător, consumator, cititor sau scriitor. Deoarece procesele sunt concurente (folosesc în comun bufferul de date), rezultă că trebuie avute în vedere condiții de sincronizare a accesului la datele memorate în locațiile bufferului, cum ar fi:

dacă un proces consumator cere o preluare de date din buffer și acesta este gol atunci procesul trebuie blocat până la apariția unor date în buffer;

dacă un proces producător cere o depunere de date în buffer și acesta este plin atunci procesul trebuie blocat până la eliberarea unei locații a bufferului;

dacă un proces cititor cere să consulte conținutul bufferului atunci poate fi permis simultan accesul și altor cititori, dar trebuie restricționat accesul vreunui scriitor;

dacă un proces scriitor cere să scrie (să adauge sau să modifice) date în buffer atunci, pe durata scrierii, nici un alt cititor sau scriitor nu poate avea acces la buffer.

Gestionarea bufferului din perspectiva accesului diferitelor tipuri de procese a condus la definirea câtorva probleme specifice calculului concurent.

problema adunĂrii concurente

Problema adunării concurente constă în gestionarea mai multor procese concurente, care, fiecare, adună o unitate la valoarea curentă a unei variabile comune. [Scheiber, 1999]

Programatorul obișnuit cu calculul secvențial se așteaptă ca o rezolvare naturală a problemei să inițializeze valoarea variabilei comune cu zero, să permită fiecărui proces să incrementeze valoarea curentă și rezultatul să fie egal cu numărul proceselor care au rulat.

Dacă soluția este abordată de o manieră secvențială atunci nedeterminismul execuției concurente a proceselor și, în același timp, lipsa atomicității operației de incrementare sunt motivele pentru care rezultatul este foarte rar egal cu numărul proceselor lansate în execuție concurent.

Operația de incrementare constă în trei microoperații, și anume: (1) se încarcă valoarea curentă a variabilei într-un registru acumulator, (2) se incrementează valoarea curentă în registru și (3) se salvează valoarea din registru în variabilă. Prin definiție, concurența nu presupune că această secvență de microoperații este atomică. Astfel, procesele pot să interfere în preluarea și interpretarea valorii curente a variabilei și, mai departe, două procese active să preia aceeași valoare a variabilei, să o incrementeze independent și să depună succesiv ACEEAȘI valoare din registru de lucru în locația variabilei.

O soluție corectă a problemei trebuie să lanseze procesele în execuție concurentă și să asigure atomicitatea operației de incrementare la nivelul fiecărui proces activ, astfel încât valoarea finală a variabilei să fie egală cu numărul proceselor rulate. Cea mai simplă manieră de rezolvare este tratarea incrementării ca secvență critică, deci instrucțiune supusă accesului sub excludere mutuală, exclusiv de un proces la un moment dat.

Nedeterminismul execuției concurente reiese din faptul că la execuții diferite ordinea în care procesele incrementează valoarea curentă a variabilei este aleatoare.

In [Scheiber, 1999] este tratată în detaliu rezolvarea problemei adunării concurente folosind diferite mecanisme de asigurare a excluderii mutuale: algoritmul Dekker, semafoare, monitoare, RPC.

Problema PRODUCĂTOR-CONSUMATOR

Problema producător-consumator se referă la organizarea bufferului de date când acesta este accesat de procese de tip producător și consumator.

Problema trebuie tratată diferit în funcție de proprietățile particulare pe care le are bufferul în ceea ce privește dimensiunea lui, politica de ocupare cu date, protocolul de acces la date ș.a.m.d. De exemplu, se poate presupune că bufferul este de dimensiune fixată, adică mărginit sau, mai mult, că este ciclic. De obicei se consideră cazul în care sloturile sunt logic numerotate și un proces are acces la o anumită locație bine precizată în funcție de operația pe care procesul respectiv o solicită și, eventual, în funcție de operația anterioară care s-a executat asupra bufferului.

De asemenea, putem pune în evidență cazuri particulare de probleme în funcție de numărul proceselor care au acces la bufferul de date. Astfel, putem avea situația mai simplă cu un producător și un consumator sau, o situație mai generală, cu mai mulți producători și mai mulți consumatori.

O altă direcție de generalizare rezultă dacă se consideră că un producător poate depune pe bandă la un acces mai multe produse și un consumator, de asemenea, poate lua de pe bandă la un acces mai multe produse.

Rezolvarea cu semafoare

In acest paragraf ne propunem să exemplificăm rezolvarea problemei producător-consumator în câteva situații particulare, folosind semafoare.

Un producător, un consumator, buffer ciclic. Pentru rezolvarea acestei situații sunt necesare și suficiente două semafoare cu următoarele semnificații: unul numit DATE care să reprezinte datele din buffer la un moment dat (numărul articolelor produse și încă neconsumate) și celălalt numit SPATII care să reprezinte locațiile libere din buffer la un moment dat.

Algoritmul de rezolvare poate fi reprezentat prin următoarea schemă sugestivă:

= posibilă întârziere

Figura 15. Rezolvarea cu semafoare a problemei producător-consumator (1P, 1C)

Valorile inițiale ale semafoarelor sunt: DATE = 0 și SPATII = N, unde N este numărul de locații din buffer. In continuare algoritmul trebuie să transcrie următoarele afirmații:

Când producătorul vrea să depune date în buffer, el execută o primitivă SIGNAL(DATE); dacă operația de depunere este permisă (posibilă) atunci are loc o incrementare a valorii semaforului DATE;

Când consumatorul vrea să ia date din buffer, el execută o primitivă SIGNAL(SPATII); dacă operația este permisă (posibilă) atunci are loc o incrementare a valorii semaforului SPATII;

Când bufferul este gol (adică valoarea lui DATE este 0) și apare un potențial consumator atunci acesta va fi blocat la WAIT(DATE) în așteptare la semaforul DATE;

Când bufferul este plin (adică valoarea lui SPATII este 0) și apare un potențial producător atunci acesta va fi blocat la WAIT(SPATII) în așteptare la semaforul SPATII.

Observații.

Deoarece am considerat cazul unui singur producător și al unui singur consumator rezultă că nu apar probleme de acces concurent, deci nu trebuiesc rezolvate probleme legate de excluderea mutuală a accesului la datele din buffer.

Operațiile WAIT și SIGNAL fiind atomice, asigură că acțiunile unui producător nu se pot interfera cu cele ale unui consumator.

O implementare completă a algoritmului trebuie să stabilească politica de depunere/preluare a datelor în/din buffer. Pentru aceste aspecte, schema algoritmului a propus programatorului folosirea unor contoare și eventual a pointerilor de localizare în structura bufferului.

Mai mulți producători și/sau mai mulți consumatori, buffer ciclic. Deoarece există mai mulți producători sau mai mulți consumatori care au acces la bufferul de articole rezultă că se impune rezolvarea concurenței acestor procese. Concret, procesele de același tip trebuie să se excludă reciproc de la utilizarea simultană a bufferului.

Pentru rezolvarea acestei probleme, soluția anterioară se poate completa cu câte un semafor poartă pentru sincronizarea producătorilor și, respectiv a consumatorilor. Fie aceste semafoare POARTA_P și POARTA_C.

In figura următoare este prezentată schema algoritmului de rezolvare a problemei producător-consumator în care avem mai mulți producători și un consumator. Pentru acest caz s-a folosit numai variabila POARTA_P necesară pentru sincronizarea producătorilor.

= posibilă întârziere

Figura 16. Rezolvarea cu semafoare a problemei producător-consumator (nP, 1C)

Funcția semaforului poartă este îndeplinită dacă valoarea inițială este 1 [Georgescu, 1996]. Această modalitate de utilizare a semaforului POARTA_P este cea care asigură excluderea mutuală a proceselor producător deoarece secvența de operații executate între WAIT(POARTA_P) și SIGNAL(POARTA_P) este secțiunea critică a procesului producător apelant [Georgescu, 1996].

Rezolvarea cu monitoare

Soluția cu monitoare a problemei producător-consumator propune încapsularea într-un monitor a bufferului, a contoarelor și a pointerilor care asigură utilizarea corectă a bufferului.

Această abordare este justificată de faptul că bufferul este o resursă partajată. Soluția este elegantă deoarece însăși structura de monitor asigură accesul exclusiv al proceselor la monitorul-buffer. De aici rezultă că mai este esențială deosebirea între situațiile cu un producător/consumator sau mai mulți.

Deoarece problema excluderii mutuale a proceselor este rezolvată, rezultă că mai trebuie asigurată sincronizarea proceselor, respectiv blocarea lor în situațiile de buffer gol sau plin. Pentru aceasta propunem folosirea a două variabile de condiție numite tocmai GOL și PLIN. Cu acestea, metodele DEPUNE și PREIA asociate monitorului-buffer ar putea fi:

procedure DEPUNE(articol)

if (buffer plin) then WAIT(PLIN)

endif

depune articol în buffer

SIGNAL(GOL)

return

procedure PREIA

if (buffer gol) then WAIT(GOL)

endif

preia articol din buffer

SIGNAL(PLIN)

return articol

Rezolvarea cu obiecte active

In acest paragraf propunem o soluție pentru problema producător-consumator care folosește obiecte active. Aici sincronizarea (întâlnirea, RENDEZ-VOUS) între procesele care comunică se stabilește folosind primitivele SELECT și ACCEPT.

Ca și în soluția cu monitor, entitatea elementară, aici obiectul activ, corespunde bufferului de articole. In plus, vom introduce variabila NR care să rețină numărul de articole care se găsesc în buffer la un moment dat. Evident, valoarea inițială pentru NR va fi 0.

Algoritmul de rezolvare urmărește o structură similară cu lucrul în Ada.

Propozițiile ACCEPT sunt executate prin apeluri externe de către procesul (taskul) care a intrat în construcția SELECT. Nu este definit care task execută la un moment dat instrucțiunile dintr-un ACCEPT. Aici fiecare ACCEPT este gardat de îndeplinirea unei condiții, în sensul că apelul metodei depune, respectiv preia este executat numai dacă este îndeplinită condiția introdusă prin clauza WHEN.

O construcție SELECT permite definirea mai multor propoziții ACCEPT accesibile proceslor pentru apel.

task-body buffer is

declaratii

begin

loop

SELECT

when NR<lung_buff

ACCEPT depune(articol) do depune articol în buffer

end

NR=NR+1

actualizează pointeri la următoarea locație pentru depunere

OR

when NR>0

ACCEPT preia(articol) do preia articol din buffer

end

NR=NR–1

actualizează pointeri la următoarea locație pentru preluare

end

end loop

end buffer

Ca și în lucrul cu monitoare, se apelează din exterior o metodă internă monitorului/taskului buffer pentru a depune (prelua) un articol în (din) buffer. Pentru monitoare, programatorul este cel care trebuie să gestioneze situațiile de buffer plin (gol). Pentru obiecte active, în Ada, această acțiune este preluată de gestionarul taskului activ care acceptă spre execuție numai acele apeluri care pot fi executate cu succes.

Când sunt îndeplinite condițiile unei alternative SELECT atunci procesul producător (consumator) care a testat condițiile este acceptat de taskul activ buffer. Se spune că are loc întâlnirea (RENDEZ-VOUS) între cele două entități și urmează să se execute instrucțiunile din alternativa SELECT respectivă.

Problema CITITOR-SCRIITOR

Problema cititor-scriitor se referă la organizarea bufferului de date când acesta este accesat de procese de tip cititor și scriitor.

Așa cum am arătat și anterior, un cititor este un proces care poate accesa o resursă simultan cu alte procese cititor, dar fără a putea opera modificări asupra resursei respective. In același timp, un scriitor este un proces care trebuie să aibă acces exclusiv la resursa comună, având și drepturi de modificare asupra resursei respective.

In timp ce procesele producător și consumator aveau de executat activități comparabile asupra bufferului (unul depunea articole, celălalt le prelua), procesele cititor și scriitor au de executat activități fundamental diferite, care trebuie ordonate corect pentru execuție. Pentru aceasta, proceselor cititor și scriitor pot să li se asocieze anumite reguli de prioritate pentru execuție.

Dacă, de exemplu, resursa comună este un fișier de pe disc, atunci ordinea execuției proceselor trebuie să respecte regula: informația citită să fie cea mai actuală. Pentru aceasta putem presupune că de îndată ce un scriitor cere să acceseze fișierul (resursa comună), acesta va primi controlul de îndată ce toți cititorii curenți (procesele cititor active) își vor fi finalizat acțiunile, fără ca vreun cititor să mai primească accesul între timp.

Uneori este de preferat ca scriitorul să primească controlul chiar întrerupând procesele cititor. Prin mecanismele puse la dispoziție de limbajele de programare, programatorul poate să organizeze accesul la bufferul de date de o manieră convenabilă.

Rezolvarea cu semafoare

Fie o soluție a problemei cititor-scriitor care folosește două semafoare generale, C – pentru cititor, S – pentru scriitor și două semafoare poartă, POARTA_S și POARTA.

Semaforul C are valoarea inițială 0 și numără cererile eșuate ale cititorilor de a citi bufferul când există un scriitor care scrie; acești cititori vor fi blocați în așteptare la semaforul C. Semaforul S are valoarea inițială 0 și numără cererile eșuate ale scriitorilor de a scrie în buffer când există cititori care citesc bufferul și există scriitor care scrie deja; acești scriitori vor fi blocați în așteptare la semaforul S.

Semaforul poartă POARTA_S are valoarea inițială 1 și este folosit pentru a asigura accesul exclusiv al unui scriitor la resursa comună (excluderea reciprocă a scriitorilor). Semaforul poartă POARTA are valoarea inițială 1 și este folosit pentru a impune restricții particulare de acces exclusiv la resursa comună pentru un număr fixat de cititori și/sau scriitori. Utilitatea acestui semafor este evidentă atunci când sunt acceptate următoarele situații: atunci când un cititor cere să acceseze resursa el devine cititor activ; atunci când un cititor activ chiar citește resursa atunci este un cititor activ care citește; atunci când un scriitor cere să acceseze resursa el devine scriitor activ; atunci când un scriitor activ chiar scrie (modifică resursa) atunci este un scriitor activ care scrie. La un moment dat pot fi mai mulți scriitori activi, dar numai unul dintre ei scrie efectiv.

Pentru acest algoritm propunem următoarele notații:

ca = numărul cititorilor activi;

cc = numărul cititorilor activi care citesc;

sa = numărul scriitorilor activi;

ss = numărul scriitorilor activi care scriu efectiv

Algoritmul poate fi reprezentat astfel:

Figura 17. Rezolvarea cu semafoare a problemei cititor-scriitor

„Diagonalele” punctate din schema algoritmului reprezintă semnale de sincronizare. Astfel se arată că eliberarea resursei poate determina trimiterea unor semnale de sincronizare de tip “wake-up” înspre cozile de procese ale celor două semafoare R și W. in acest fel, ultimul cititor care și-a încheiat acțiunea de a citi poate „trezi” oricare dintre scriitorii activi care nu scriu și ultimul scriitor activ care și-a încheiat acțiunea de a scrie poate „trezi” oricare dintre cititorii activi.

Rezolvarea cu regiuni critice condiționate

O soluție pentru problema cititor-scriitor, care să folosească regiuni critice condiționate ar putea fi următoarea:

Figura 18. Rezolvarea cu regiuni critice condiționate a problemei cititor-scriitor

Se poate observa că, pentru programator, această soluția este cu mult mai simplă decât cea care folosește semafoare. Afirmația este susținută de două argumente: (1) singura grijă a programatorului este să folosească corect apelul primitivei AWAIT și (2) problema deblocării (trezirii) proceselor în așteptare este implicit gestionată de mecanismul de lucru cu regiuni critice.

Rezolvarea cu monitoare

Reluând problema producător-consumator se poate observa că soluțiile propuse au considerat bufferul de date ca fiind entitatea elementară care să se reprezinte ca monitor, respectiv task (obiect) activ.

Pentru rezolvarea cu monitoare a problemei cititor-scriitor, nu mai este corect să considerăm că monitorul încapsulează datele și proprietățile bufferului deoarece ar apărea următoarea contradicție: pe de o parte se știe că structura de monitor implică accesul exclusiv al unui singur proces la metodele monitorului la un moment dat, iar pe de altă parte, problema cititor–scriitor trebuie să permită mai multor cititori să consulte simultan bufferul de date.

Propunem o soluție care folosește un monitor citeste-scrie și două variabile de condiție: LIBER_LA_CITIRE și LIBER_LA_SCRIERE. Metodele monitorului sunt: startCiteste, endCiteste, startScrie, endScrie. In plus, monitorul mai are trei variabile locale: cc și sa — cu aceleași semnificații ca și în rezolvarea problemei cu semafoare, adică cc este numărul cititorilor care la un moment dat sunt în curs de citire a bufferului, iar sa este numărul de scriitori activi (care și-au anunțat intenția de a scrie și au fost întârziați) — și seScrie — variabilă booleană care are valoarea TRUE cât timp există un scriitor care scrie în bufferul de date.

Descrierea monitorului este următoarea:

citeste-scrie: monitor

entry-procedures startCiteste, endCiteste, startScrie, endScrie

var cc, sa: integer

seScrie: boolean

LIBER_LA_CITIRE, LIBER_LA_SCRIERE: condition

procedure startCiteste()

if sa > 0 then WAIT(LIBER_LA_CITIRE)

cc = cc + 1

SIGNAL(LIBER_LA_CITIRE)

// dacă un cititor poate citi atunci și alți cititori pot;

// fiecare cititor trezește alți cititori

return

end

procedure endCiteste()

cc = cc – 1

if cc = 0 then SIGNAL(LIBER_LA_SCRIERE)

return

end

procedure startScrie()

sa = sa + 1

if seScrie or cc > 0 then WAIT(LIBER_LA_SCRIERE)

seScrie = TRUE

return

end

procedure endScrie()

seScrie = FALSE

sa = sa – 1

if sa > 0 then SIGNAL(LIBER_LA_SCRIERE)

else SIGNAL(LIBER_LA_CITIRE)

return

end

begin

seScrie = FALSE

end citeste-scrie

Alte probleme clasice de concurență

In acest paragraf preluăm din [Georgescu, 1996] o serie de probleme specifice calculului concurent.

Problema rezervării biletelor. Fiecare terminal al unei rețele de calculatoare este plasat într-un punct de vânzare a biletelor pentru un anumit scop (spectacol, călătorie etc.). Se cere să se găsească o modalitate de a evita vânzarea mai multor bilete pentru același loc.

Jocul vieții. Un tabel dreptunghiular, notat A, cu m linii și cu n coloane conține celule care pot fi vii sau moarte. Fiind dată o configurație curentă a tabelului, se cere să se determine configurația generației următoare, știind că celulele moarte își păstrează starea, iar o celulă vie moare dacă și nuami dacă numărul celulelor vii, vecine ei este mai mic decât 2 sau mai mare decât 4. O celulă are cel mult 8 vecini: pe orizontală, pe verticală și pe diagonale.

Problema filosofilor chinezi. La o masă rotundă stau cinci filosofi chinezi. Principala lor activitate este aceea de a gândi, dar, evident, din când în când trebuie să și mănânce, folosind pentru aceasta câte două bețișoare. Stiind că între oricare doi filosofi se află un bețișor și că un filosof poate mânca doar dacă a ridicat de pe masă atât bețișorul din stânga sa, cât și pe cel din dreapta sa, se cere să se simuleze activitățile filosofilor așezeți la masă.

Problema bărbierului somnoros. Prăvălia unui bărbier este formată din două camere: cea de la stradă, folosită ca sală de așteptare și cea din spate, în care se găsește scaunul pe care se așează clienții pentru a fi bărbieriți. Dacă nu are clienți, bărbierul somnoros se culcă. Să se simuleze activitățile care se desfășoară în prăvălia bărbierului. Problema este o reformulare a problemei producător- consumator în care locul bufferului de articole este preluat de scaunul bărbierului, iar consumatorul este bărbierul, în sensul că își bărbierește clienții.

Problema ceasului deșteptător al lui Hoare a fost enunțată de C.A.R. Hoare [1974]. Mai multe persoane, numerotate cu 1, 2, …, n au următorul tabiet: persoana k dorește să se trezească din k în k ore pentru a întreprinde o foarte scurtă activitate, după care se culcă la loc. Se cere să se simuleze aceste activități.

Problema alocării resurselor. Sunt disponibile max unități dintr-o resursă oarecare. Există nc clienți care doresc să aibă de mai multe ori acces la resursa respectivă, un acces constând în a lua (a încerca să ia) un număr de unități din resursă, de a folosi aceste unități și apoi de a le returna. Se cere să se simuleze aceste activități.

Problema grădinii ornamentale sau problema excluderii reciproce. Intrarea în grădinile ornamentale ale unui oraș oriental se face prin N porți. Se pune problema să se țină evidența numărului de persoane care au intrat în grădină. Fiecare poartă de intrare în grădină este o resursă care trebuie accesată exclusiv de un proces. Dacă la un moment dat pe una dintre porți intră o persoană atunci în acel moment pe nici o altă poartă nu mai intră vreo persoană în grădină.

Problema emițător-receptor. Un emițător emite succesiv mesaje, fiecare dintre ele trebuind să fie recepționat de toți receptorii, înainte ca emițătorul să transmită mesajul următor. Un caz particular pentru această problemă ar fi cea în care emițătorul este grăbit și emite mesajul numai acelor receptori care la momentul emisiei sunt gata să îl primească; totuși, se cere ca cel puțin un receptor să primească mesajul.

Problema autobuzului. Un autobuz, având capacitatea maximă de N locuri, parcurge o traiectorie circulară pe care se află P persoane care urcă și coboară din autobuz. Se cere să se simuleze activitatea autobuzului și a pasagerilor. Se presupune că nici un pasager nu dorește să facă mai mult de un tur complet.

LISTA FIGURILOR

Figura 1. Replicarea codului. Partiționarea datelor 17

Figura 2. Topologii de sisteme concurente 20

Figura 3. Operații cu procese 33

Figura 4. Mecanismul de lucru cu corutine 38

Figura 5. Mecanismul Fork – Join 39

Figura 6. Suportul de limbaj pentru gestionarea proceselor 40

Figura 7. Implementarea proceselor concurente fără suportul sistemului de operare 42

Figura 8. Implementarea proceselor interne bazată pe suportul sistemului de operare 43

Figura 9. Combinarea threadurilor utilizator și de nivel nucleu 43

Figura 10. Localizarea proceselor: mai multe procese în același spațiu de adresă 46

Figura 11. Localizarea proceselor: un proces – un spațiu de adresă, aceeași mașină 46

Figura 12. Localizarea proceselor: un proces – un spațiu de adresă, pe mașini diferite 47

Figura 13. Evoluția primitivelor IPC 56

Figura 14. Mecanisme IPC de nivel înalt 57

Figura 15. Rezolvarea cu semafoare a problemei producător-consumator (1P, 1C) 84

Figura 16. Rezolvarea cu semafoare a problemei producător-consumator (nP, 1C) 85

Figura 17. Rezolvarea cu semafoare a problemei cititor-scriitor 89

Figura 18. Rezolvarea cu regiuni critice condiționate a problemei cititor-scriitor 90

BIBLIOGRAFIE

Andrews G.R. (1991), Concurrent Programming – Principles and Practice, Redwood City CA: Benjamin/Cummings

Athanasiu I. s.a. (2000) Limbajul Java – o perspectivă pragmatică, Computer Libris Agora, Cluj-Napoca

Bacon J. (1998) Concurrent Systems – operating systems, database and distributed systems: an integrated approach, Addison-Wesley

Ben-Ari M. (1990) Principles of concurrent and distributed programming, Englewood Cliffs NJ: Prentice-Hall

Boian F.M. (1994) Sisteme de operare interactive, Editura Libris, Cluj-Napoca

Boian F.M. (1999) Programarea distribuită în Internet – metode și aplicații, Editura Albastră, Cluj-Napoca

Braunl T. (1993) Parallel programming – an introduction, Prentice-Hall

Brinch Hansen P. (1978) Distributed Processes: A concurrent programming concept, Comm. ACM 21(11)

Burns A., Davies G. (1993) Concurrent programming, Addison-Wesley

Campbell R.H., Haberman N.A. (1974) The Specification of Process Synchronization by Path Expressions, LNCS 16 Berlin: Springer Verlag

Campbell R.H., Kolstad R.B. (1980) An overview of Path Pascal’s design and Path Pascal user manual, ACM SIGPLAN notices 15(9)

Chiorean I. (1995) Calcul paralel – fundamente, Editura Albastră, Cluj-Napoca

Coulouris G.F. s.a. (1999) Distributed systems – concepts and design, Wokingham: Addison-Wesley

Dijkstra E.W. (1968) The structure of THE operating system, Comm. ACM 11(5)

Dijkstra E.W. (1975) Guarded commands, nondeterminacy and their formal derivation of programs, Comm. ACM 18(8)

Eleș P., Cicârlie H. (1991) Programarea concurentă în limbaje de nivel înalt, Editura Științifică, București

Flynn M.J. (1972) Some Computer Organizations and their Effectiveness, IEEE Transactions on Computers, C-21

Gelernter D. (1985) Generative Communication in Linda, ACM Trans. Prog. Lang. And Sys. 7(1)

Georgescu H. (1996) Programare concurentă – teorie și aplicații, Editura Tehnică, București

Grigoraș D. (2000) Calcul paralel – de la sisteme la programarea aplicațiilor, Computer Libris Agora, Cluj-Napoca

Hoare C.A.R. (1974) Monitors: an operating system structuring concept, Comm. ACM 17(10)

Hoare C.A.R. (1978) Communicating Sequential Processes, Comm. ACM 21(8)

Hoare C.A.R. (1985) Communicating Sequential Processes, Englewood Cliffs NJ: Prentice-Hall

Hockney R.W., Jesshope C.R. (1991) Calculatoare paralele – arhitectură, programare, algoritmi, Editura Tehnică, București

IEEE (1988) IEEE Standard Portable Operating System Interface for Computer Environments (POSIX), IEEE 1003.1

Ionescu F. (1999) Principiile calculului paralel, Editura Tehnică, București

Păunescu F., Goleșteanu D.V. (1993) Sisteme cu prelucrare distribuită și aplicațiile lor, Editura Tehnică, București

Quinn M.J.(1994) Parallel computing – theory and practice, McGraw-Hill

Reed D.P., Kanodia R.K. (1979) Synchronization with eventcounts and sequencers, Comm. ACM 23(2)

Rotariu E. (1999) Limbajul Java, Computer Press Agora, Cluj-Napoca

Scheiber E. (1999) Lecții de calcul paralel, Reprografia Universității Transilvania Brașov

Sloman M., Kramer J. (1987) Distributed Systems and Computer Networks, Englewood Cliffs NJ: Prentice-Hall

Văduva C.M. (2001) Programarea în Java, Editura Albastră, Cluj-Napoca

Welsh J., Lister A. (1981) A comparative study of task communication in ADA, Software, Practice and Experience 11

Williams S.A. (1990) Programming models for parallel systems, John Wiley & Sons

*** Programare concurentă Cover Story, PC Report 40 (ianuarie 1996)

*** Procesarea distribuită Cover Story, PC Report 50 (noiembrie 1996)

*** Modelul client/server Cover Story, PC Report 54 (martie 1997)