Concurență (informatică)

În informatică, concurența este o proprietate a sistemelor în care mai multe operații sunt executate simultan, eventual interacționând unele cu altele. Operațiile pot fi executate pe mai multe nuclee ale aceluiași chip (multi-core), de către fire de execuție planificate in avans (preemptively time-shared threads) ale aceluiași procesor sau chiar pe procesoare separate fizic. Mai multe modele matematice au fost dezvoltate pentru calculul concurent, cum ar fi rețelele Petri, Process calculus, modelul mașinii paralele cu acces aleator (Parallel Random Access Machine), modelul Actor și limbajul de coordonare Reo.

Probleme de concurență

Deoarece calculele dintr-un sistem concurent pot interacționa unele cu altele în timp ce sunt executate, numărul de căi de execuție în sistem poate fi extrem de mare, iar rezultatul obținut nu poate fi determinat aprioric. Folosirea concurentă de resurse partajate poate fi o sursă de nedeterminare ce duce la probleme precum ajungerea într-un punct mort (deadlock), în care două sau mai multe acțiuni se așteaptă reciproc blocând execuția, sau blocarea unei acțiuni din lipsa accesului la resurse (resource starvation).^[1]

Proiectarea sistemelor concurente implică de cele mai multe ori găsirea unor tehnici solide de coordonare a execuției, schimburilor de date, alocării memoriei și planificării execuției în vederea minimizării timpului de răspuns și maximizării volumului de date procesate în unitatea de timp.^[2]

Teorie

Teoria concurenței a fost un domeniu activ de cercetare în informatica teoretică. Una dintre primele lucrări a fost cea a lui Carl Adam Petri despre rețelele Petri, scrisă în anii 1960. În perioada următoare, numeroase alte varietăți de formalisme au fost dezvoltate pentru a modela și studia concurența.

Modele de concurență

Mai multe formalisme pentru modelarea și înțelegerea sistemelor concurente au fost dezvoltate, incluzând:^[3]

Mașina paralelă cu acces aleator^[4]
Modelul Actor
Modele de corelare computațională, cum ar fi modelul Bulk Synchronous Parallel (BSP)
Rețele Petri
Process calculus
Spații Tuple (o implementare a paradigmei memoriei asociative pentru calcul paralel/distribuit), e.g. limbajul de coordonare Linda
SCOOP (Simple Concurrent Object-Oriented Programming)
Limbajul de coordonare Reo

Unele dintre aceste modele de concurență sunt destinate în primul rând modelării și stabilirii specificațiilor, în timp ce altele pot fi utilizate pe parcursul întregului ciclu de dezvoltare, inclusiv pentru proiectarea, implementarea, verificarea, testarea și simularea sistemelor concurente.

Proliferarea diferitelor modele de concurență a motivat unii cercetători să dezvolte moduri de a unifica aceste modele teoretice. De exemplu, Lee și Sangiovanni-Vincentelli au demonstrat că modelul tagged-semnal poate fi folosit pentru a oferi un cadru comun pentru definirea semanticii denotaționale a unei varietăți de modele diferite de concurență,^[5], în timp ce Nielsen, Sassone și Winskel au demonstrat că teoria categoriilor poate fi folosită pentru a oferi o înțelegere unificată diferitor modele.^[6]

Teorema de reprezentare computațională din modelul Actor oferă o modalitate destul de generală de a reprezenta sisteme concurente, care sunt închise în sensul că nu primesc comunicații din afară. (Alte sisteme concurente, e.g. process calculus pot fi modelate în modelul Actor folosind un protocol de actualizare în două etape ^[7]). Denotarea matematică a unui sistem închis S este construită prin aproximări succesive plecând de la un comportament inițial ⊥_S utilizând o funcție comportamentală de aproximare progession_S pentru a construi o denotare a lui S:^[8]

Denote_S ≡ ⊔_i∈ω progression_Sⁱ(⊥_S)

În acest fel, S poate fi caracterizat matematic în funcție de toate comportamentele sale posibile.

Tipuri de logică

Diferite tipuri de logică temporală ^[9] pot fi folosite pentru a trata problema sistemelor concurente. Unele dintre aceste logici, cum ar fi logica temporală liniară și logica bazată pe arbori computaționali de timp (o logică în care modelul timpului este o structură de tip arbore în care viitorul nu este determinat), permit specificarea secvențelor de stări prin care un sistem concurent poate trece. Altele, cum ar fi logica bazată pe arbori computaționali de acțiuni, logica Hennessy-Milner și logica temporală de acțiuni a lui Lamport (care combină logica temporală cu logica acțiunilor) primesc informația prin secvențe de acțiuni (schimbări de stare). Principala utilizare a acestor logici este definirea specificațiilor pentru sisteme concurente ^[1].

Practică

Programarea concurentă cuprinde limbaje de programare și algoritmi utilizați în implementarea sistemelor concurente. Programarea concurentă este de obicei considerată a fi mai generală decât programarea paralelă, deoarece aceasta poate implica modele arbitrare și dinamice de comunicare și interacțiune, în timp ce sistemele paralele au în general un model de comunicații predefinit și bine structurat. Obiectivele de bază ale programării concurente includ corectitudinea, performanța și robustețea. Sistemele concurente, cum ar fi sistemele de operare și sistemele de management ale bazelor de baze sunt în general concepute pentru a funcționa pe termen nelimitat, includ funcții de redresare la defect, și nu se opresc în mod neașteptat. Unele sisteme concurente pun în aplicare o formă de concurență transparentă, în care entitățile computaționale pot concura și partaja o resursă unică, însă complexitatea mecanismului este ascunsă programatorului.

Deoarece folosesc resurse partajate, sistemele concurente necesită în general includerea unui arbitru în implementare (de multe ori în hardware-ul sistemului), pentru a controla accesul la aceste resurse. Utilizarea de arbitri introduce posibilitatea nedeterminării în calculul concurent, care are implicații majore în practică, afectând corectitudinea și performanța. De exemplu, arbitrarea introduce nondeterminism nelimitat, care ridică probleme cu verificarea modelului, provocând o explozie în spațiul stărilor și poate duce chiar la modele cu un număr infinit de stări.

Unele modele concurente de programare includ co-procese și concurență deterministă. În aceste modele, fire de execuție de control oferă în mod explicit timpul lor de execuție fie sistemului de operare, fie altui proces.

Vezi și

Note

^ ^a ^b en Cleaveland, Rance (December, 1996). „Strategic Directions in Concurrency Research”. ACM Computing Surveys. 28 (4): 607. doi:10.1145/242223.242252. Verificați datele pentru: |date= (ajutor)
^ en Campbell, Colin; Johnson, Ralph; Miller, Ade; Toub, Stephen (2010). Parallel Programming with Microsoft .NET. Microsoft Press. ISBN 978-0-7356-5159-3.
^ en Filman, Robert (1984). Coordinated Computing - Tools and Techniques for Distributed Software. McGraw-Hill. ISBN 0-07-022439-0. Arhivat din original la 16 mai 2007. Accesat în 27 mai 2012.
^ en Keller, Jörg (2001). Practical PRAM Programming. John Wiley and Sons.
^ en Lee, Edward (December, 1998). „A Framework for Comparing Models of Computation”. IEEE Transactions on CAD. 17 (12): 1217–1229. doi:10.1109/43.736561. Parametru necunoscut |unused_data= ignorat (ajutor); Verificați datele pentru: |date= (ajutor)
^ en Nielsen, Mogens (1993). Relationships Between Models of Concurrency.
^ en Frederick Knabe. A Distributed Protocol for Channel-Based Communication with Choice PARLE 1992.
^ en William Clinger (iunie 1981). „Foundations of Actor Semantics”. Mathematics Doctoral Dissertation. MIT.
^ en Roscoe, Colin (2001). Modal and Temporal Properties of Processes. Springer. ISBN 0-387-98717-7.

Lectură suplimentară

en Lynch, Nancy A. (1996). Distributed Algorithms. Morgan Kauffman. ISBN 1-55860-348-4.
en Tanenbaum, Andrew S. (2002). Distributed Systems: Principles and Paradigms. Prentice Hall. ISBN 0-13-088893-1.
en Kurki-Suonio, Reino (2005). A Practical Theory of Reactive Systems. Springer. ISBN 3-540-23342-3.
en Garg, Vijay K. (2002). Elements of Distributed Computing. Wiley-IEEE Press. ISBN 0-471-03600-5.
en Magee, Jeff;, Kramer, Jeff (2006). Concurrency: State Models and Java Programming. Wiley. ISBN 0-470-09355-2.

Legături externe

en Concurrent Systems Arhivat în 28 ianuarie 2006, la Wayback Machine. at The WWW Virtual Library

[cleaveland1996-1] Cleaveland, Rance (December, 1996). „Strategic Directions in Concurrency Research”. ACM Computing Surveys. 28 (4): 607. doi:10.1145/242223.242252. Verificați datele pentru: |date= (ajutor)

[2] Campbell, Colin; Johnson, Ralph; Miller, Ade; Toub, Stephen (2010). Parallel Programming with Microsoft .NET. Microsoft Press. ISBN 978-0-7356-5159-3.

[3] Filman, Robert (1984). Coordinated Computing - Tools and Techniques for Distributed Software. McGraw-Hill. ISBN 0-07-022439-0. Arhivat din original la 16 mai 2007. Accesat în 27 mai 2012.

[4] Keller, Jörg (2001). Practical PRAM Programming. John Wiley and Sons.

[5] Lee, Edward (December, 1998). „A Framework for Comparing Models of Computation”. IEEE Transactions on CAD. 17 (12): 1217–1229. doi:10.1109/43.736561. Parametru necunoscut |unused_data= ignorat (ajutor); Verificați datele pentru: |date= (ajutor)

[6] Nielsen, Mogens (1993). Relationships Between Models of Concurrency.

[7] Frederick Knabe. A Distributed Protocol for Channel-Based Communication with Choice PARLE 1992.

[clinger1981-8] William Clinger (iunie 1981). „Foundations of Actor Semantics”. Mathematics Doctoral Dissertation. MIT.

[stirling-9] Roscoe, Colin (2001). Modal and Temporal Properties of Processes. Springer. ISBN 0-387-98717-7.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]