Concurență (informatica)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 24 iulie 2022; verificările necesită 2 modificări .

În informatică , paralelismul este o proprietate a sistemelor în care mai multe calcule sunt efectuate simultan și, făcând acest lucru, posibil interacționează între ele. Calculele pot rula pe mai multe nuclee pe același cip cu fire preventive de partajare a timpului pe același procesor sau pot rula pe procesoare separate fizic . Au fost dezvoltate o serie de modele matematice pentru a efectua calcule paralele, inclusiv rețele Petri , calcul de proces , modele de calcul cu acces aleator paralel și modele actor .

Notă  - În literatura în limba rusă, termenii „paralelism” și „competitivitate” sunt adesea confundați. . Ambii termenii înseamnă simultaneitatea proceselor, dar primul este la nivel fizic (execuția paralelă a mai multor procese, care vizează doar creșterea vitezei de execuție prin utilizarea unui suport hardware adecvat), iar al doilea unul este la nivel logic ( paradigma de proiectare a sistemului care identifică procesele ca independente, ceea ce , printre altele, le permite să fie executate fizic în paralel, dar are ca scop în primul rând simplificarea scrierii programelor multi-threaded și creșterea stabilității acestora).

Probleme

Deoarece calculele în sisteme paralele interacționează între ele, numărul de căi de execuție posibile poate fi extrem de mare, iar rezultatul rezultat poate deveni nedeterminist (nedeterminat). Utilizarea concomitentă a resurselor partajate poate fi o sursă de non-determinism, ceea ce duce la probleme precum blocarea sau lipsa de resurse. [unu]

Construirea sistemelor paralele necesită găsirea de metode fiabile pentru coordonarea proceselor de rulare, comunicare, alocare a memoriei și programare pentru a minimiza timpul de răspuns și a crește debitul.

Teorie

Teoria calculului paralel este un domeniu activ de cercetare în informatica teoretică . Una dintre primele propuneri în această direcție a fost lucrarea fundamentală a lui Carl Adam Petri asupra rețelelor Petri la începutul anilor 1960. În anii următori, au fost dezvoltate o gamă largă de formalisme pentru modelarea și descrierea sistemelor paralele.

Modele

Un număr mare de metode formale au fost deja dezvoltate pentru modelarea și înțelegerea funcționării sistemelor paralele, inclusiv: [2]

Unele dintre aceste modele de concurență sunt în principal pentru descrieri de inferență și specificații, în timp ce altele pot fi utilizate pe tot parcursul ciclului de dezvoltare, inclusiv proiectarea, implementarea, dovezile rezultatelor, testarea și simularea sistemelor paralele.

Proliferarea diferitelor modele de concurență a determinat unii cercetători să dezvolte modalități de a combina aceste modele teoretice. De exemplu, Lee și Sangiovanni-Vincentelli au arătat că așa-numitul model „semnale etichetate” poate fi folosit pentru a oferi un cadru comun pentru descrierea semanticii denotaționale a diferitelor modele de concurență [4] și Nielsen, Sassoon și Winskle au arătat acea teorie a categoriilor poate fi folosită pentru a oferi o înțelegere comună a diferitelor modele. [5]

Teorema reprezentării simultane din modelul actorului oferă o modalitate destul de generală de a descrie sistemele concurente care sunt închise în sensul că nu primesc mesaje din exterior. Alte metode de descriere a concurenței, cum ar fi calculul procesului , pot fi descrise în termeni de model de actor folosind protocolul de comitere în două faze. [6] Notația matematică folosită pentru a descrie un sistem închis S oferă o aproximare mai bună dacă acesta este construit dintr-un comportament inițial, notat cu ⊥ S , folosind o progresie a funcției de comportament de aproximare S . [7] Atunci notația pentru S este construită după cum urmează:

Notăm S ≡ ⊔ i∈ω progresia S i (⊥ S )

Astfel, S poate fi exprimat matematic în termenii tuturor comportamentelor sale posibile.

Logica

Pentru a oferi raționament logic despre sistemele paralele, pot fi utilizate diverse tipuri de logici temporale [8] . Unele dintre ele, cum ar fi logica temporală liniară sau logica arborescentă de calcul, permit să se facă declarații despre succesiunea stărilor prin care poate trece un sistem paralel. Altele, cum ar fi logica de acțiune a arborelui de calcul, logica Hennessy-Milner sau logica de acțiune temporală a lui Lamport, își construiesc declarațiile dintr-o secvență de acțiuni (modificări de stare). Principala utilizare a acestor logici este de a scrie specificații pentru sisteme paralele. [unu]

Practică

În această secțiune, vom folosi două noțiuni de paralelism care sunt comune în literatura engleză, deoarece vom vorbi despre compararea lor între ele. Termenul Concurență va fi tradus „simultaneitate”, iar termenul Paralelism va fi tradus „paralelism”.

Programarea simultană include limbaje de programare și algoritmi utilizați pentru implementarea sistemelor simultane. Programarea simultană este în general considerată a fi mai generală decât programarea paralelă, deoarece poate implica modele dinamice arbitrare de comunicare și interacțiune, în timp ce sistemele paralele implementează cel mai adesea modele de comunicare predefinite și bine structurate. Principalele obiective ale programării concurente sunt corectitudinea , eficiența , stabilitatea . Sistemele concurente, cum ar fi sistemele de operare și sistemele de gestionare a bazelor de date, sunt concepute în primul rând pentru a funcționa în condiții incerte, inclusiv recuperare automată după o defecțiune, nu ar trebui să înceteze să funcționeze în mod neașteptat. Unele sisteme concurente operează într-o formă de simultaneitate transparentă, în care entitățile de calcul concurente pot concura pentru utilizarea aceleiași resurse, dar esența acestei competiții este ascunsă programatorului.

Deoarece sistemele concurente partajează resurse, ele necesită de obicei un fel de arbitru încorporat în implementarea lor (adesea hardware-ul de bază) pentru a controla accesul la acele resurse. Utilizarea arbitrilor creează posibilitatea de incertitudine în calculele simultane, ceea ce este de mare importanță pentru practică, inclusiv pentru asigurarea corectitudinii și eficienței. De exemplu, arbitrajul nu exclude indeterminismul nemărginit, care este asociat cu problema de verificare a modelului , care este cauza naturii explozive a spațiului de stări și poate duce chiar la formarea unui model cu un număr infinit de stări.

Unele modele de programare concurente includ crearea de coprocese și simultaneitatea deterministă . În aceste modele, firele de execuție de control al procesului își oferă în mod explicit secțiunile de timp fie sistemului, fie altui proces.

Vezi și

Note

  1. ↑ 1 2 Cleaveland, Rance; Scott Smolka. Direcții strategice în cercetarea concurenței  //  ACM Computing Surveys : jurnal. - 1996. - Decembrie ( vol. 28 , nr. 4 ). — P. 607 . - doi : 10.1145/242223.242252 .
  2. ↑ Filman, Robert; Daniel Friedman. Calcul coordonat - Instrumente și tehnici pentru  software distribuit . - McGraw-Hill Education , 1984. - ISBN 0-07-022439-0 . Copie arhivată (link indisponibil) . Consultat la 5 octombrie 2011. Arhivat din original pe 16 mai 2007. 
  3. ↑ Keller, George; Christoph Kessler, Jesper Träff. Programare practică PRAM  (neopr.) . - John Wiley and Sons , 2001.
  4. ↑ Lee, Edward; Alberto Sangiovanni-Vincentelli. Un cadru pentru compararea modelelor de calcul  // IEEE Tranzacții pe  CAD : jurnal. - 1998. - Decembrie ( vol. 17 , nr. 12 ). - P. 1217-1229 . - doi : 10.1109/43.736561 .
  5. ↑ Mogens Nielsen; Vladimiro Sassone și Glynn Winskel (1993). „Relații între modelele de concurență” . Școala/Simpozion REX . Arhivat din original pe 26.02.2009 . Accesat 2011-10-05 . Parametrul depreciat folosit |deadlink=( ajutor )
  6. ↑ Frederick Knabe. Un protocol distribuit pentru comunicarea pe canal cu Choice PARLE 1992.
  7. ↑ William Clinger. Fundamentele semanticii actorilor  (neopr.) . - MIT, 1981. - Iunie ( vol. Teză de doctorat în matematică ).
  8. ↑ Roscoe, Colin. Proprietățile modale și temporale ale  proceselor . - Springer, 2001. - ISBN 0-387-98717-7 .

Link -uri

  Accesați articolul Wikidata  Dicționare și enciclopedii