În programarea simultană , Comunicarea proceselor secvențiale ( CSP ) este o algebră de proces pentru modelarea interacțiunii sistemelor.
CSP încorporează un mecanism de sincronizare bazat pe principiul întâlnirii (detaliat mai târziu prin comanda de intrare / ieșire). Combinând acest mecanism cu o sintaxă simplă și concisă, CSP permite implementarea rapidă a paradigmelor clasice ale concurenței, cum ar fi producătorii / consumatorii sau cititorii / scriitorii. Nu este un limbaj de programare complet.
CSP a fost descris pentru prima dată de CAR Hoare într-un articol din 1978, dar de atunci a evoluat substanțial. CSP a fost pus în practică industrial ca un instrument pentru specificarea formală a execuției concurente a diferitelor sisteme - cum ar fi Transputerul T9000 sau un sistem computerizat de tranzacții comerciale sigure. Este un domeniu de cercetare mereu activ.
Un program CSP ia forma unei serii de comenzi și declarații variabile separate prin punct și virgulă:
x : integer; y : integer; x := 4; ...Hoare face distincție între două tipuri de comenzi:
Comenzile de intrare / ieșire, paralele, repetitive și alternative vor fi detaliate mai târziu. Comanda nulă, prin definiție, nu face nimic. Vă permite doar să completați blocuri de instrucțiuni goale. Comanda de atribuire are o sintaxă clasică variabilă: = valoare :
x := 5Eșecul unei comenzi (de exemplu, în cazul unei comenzi de intrare / ieșire, dacă procesul vizat nu există) provoacă eșecul procesului sau al comenzii structurate care îl conține (eșecul unei comenzi poate conduce, prin urmare, până la sfârșitul programului). Să observăm cazul particular al unei repetitive în care eșecul unei comenzi interne duce la încetare și nu la faliment (a se vedea secțiunea Comanda repetitivă).
Prin urmare, eșecul nu este o greșeală în sine.
O noțiune de semnal a fost, de asemenea, introdusă în CSP. Un semnal este într-un fel o variabilă complexă (sau structurată) alcătuită dintr-un constructor (un identificator liber), precum și un set de valori. Valorile pot fi fie de tip elementar (număr întreg, șir de caractere etc.), fie de alte semnale.
Exemple:
Rețineți, de asemenea, că un semnal poate fi atribuit unei variabile (exemplu: x: = p (4)) și poate fi, de asemenea, ținta unei alocări. Aceasta permite alocări de tipul (x, y): = (y, x).
Permite concurența proceselor prin următoarea sintaxă:
[ proc1 :: liste de commandes || proc2 :: liste de commandes || ... ]O astfel de comandă se termină numai atunci când toate procesele pe care le definește sunt terminate, eșecul uneia provocând eșecul comenzii paralele. Rețineți că o variabilă definită înainte de o comandă paralelă este vizibilă proceselor pe care le conține. Acest lucru implică în mod necesar că toate procesele definite trebuie să aibă acces la variabilele declarate înainte de comanda paralelă. Aici asistăm, așadar, la o partajare a resurselor, ale căror constrângeri (acces exclusiv etc.) sunt responsabilitatea programatorului.
De asemenea, observăm posibilitatea de a declara mai multe procese pentru aceeași listă de comenzi, așa cum se arată în următorul exemplu:
proc1 [i:1..10] :: liste de commandesAici vor fi concurate zece procese cu aceeași listă de comenzi.
Comunicarea între procese se bazează pe această comandă. Pentru a explica modul în care funcționează, să începem de la cazul simplu al celor două procese de producător și consumator, primul dorind să transmită o variabilă x la a doua. O astfel de comunicare va avea loc prin următoarele comenzi:
consommateur!xpermite procesului producătorului să trimită x procesului consumatorului
producteur?xva permite procesului consumatorului să primească x din procesul producătorului
Din punct de vedere al sintaxei, observăm că! indică o comandă de ieșire, în timp ce indică o comandă de intrare. Mai formal, o comandă de intrare va lua forma:
processus_source?variable_cibleși o comandă de ieșire sub forma:
processus_cible!expression_source.În plus, pentru ca comunicarea să fie posibilă între două comenzi I / O, CSP necesită:
În aceste condiții, transmisia poate avea loc, iar conținutul expresiei sursă este copiat în variabila țintă. Dacă oricare dintre aceste condiții nu este îndeplinită, procesele sunt suspendate, rezultând un impas. Dacă oricare dintre procese este mort, atunci orice comandă I / O care implică acel proces ar trebui să eșueze. În cele din urmă, primul proces care solicită comunicarea trebuie pus în așteptare până când al doilea se alătură acestuia. Aici găsim principiul întâlnirii. De remarcat și cazul particular al unei sincronizări simple, adică fără transmiterea valorii, posibil datorită utilizării unui semnal pur. Exemplu:
[ producteur :: ... consommateur?p(); ... || consommateur :: ... producteur!p(); ... ]O ordine alternativă vine sub forma unui set de selective, fiecare constând dintr-un paznic, precum și o listă de ordine. O gardă este alcătuită dintr-o parte de expresie booleană și o parte de control de intrare, care poate fi omisă. Sintaxic, o comandă alternativă arată astfel:
[ garde1 → liste de commandes [] garde2 → liste de commandes [] ... ]În cazul în care Custodia1 și garde2 sunt de forma:
expression_booleenne ; commande_entréeCeea ce dă de exemplu:
[ i < 5 ; processus?p(x) → ... [] console!write(msg) → ... [] i > 5 → ... ]Când se execută o comandă alternativă, fiecare dintre gărzile sale este testat, pentru a-și determina valoarea în conformitate cu logica banalizată (adică o gărză poate fi adevărată, falsă sau neutră):
Astfel, dacă una sau mai multe comenzi păstrate sunt adevărate, trebuie făcută o alegere nedeterministă (adică aleatorie) pentru a selecta doar una. Dacă niciuna nu este adevărată, dar unele sunt neutre, procesul așteaptă comenzile de intrare corespunzătoare. Și dacă toate comenzile păstrate sunt greșite, comanda alternativă eșuează.
Dacă este selectată o pază, atunci trebuie executată lista de comenzi corespunzătoare.
De asemenea, este important să rețineți că constrângerea sintactică care limitează comenzile I / O din gărzi la comenzile simple de intrare, provine dintr-o alegere făcută de HOARE pentru a evita inconsecvențele.
Pentru a ilustra acest lucru, să începem cu următorul exemplu (care presupune utilizarea unei comenzi de ieșire în gărzi):
[ proc1 :: [ proc2?p() → ... [] proc2?q() → ... ] || proc2 :: [ proc1!p() → ... [] proc1!q() → ... ] ]Să presupunem că cele două procese au aterizat fiecare pe ordinea lor alternativă. Prin urmare, cele două comenzi vor fi evaluate în paralel:
Dacă ambele opțiuni selectează aceeași comunicare, nu apare nicio problemă. Pe de altă parte, dacă fiecare selectează o comunicare diferită, participăm la un caz de inconsecvență care are ca rezultat un impas.
Astfel, comunicarea între comenzile de intrare / ieșire păzite cauzând probleme, HOARE a decis să o prevină permițând doar comenzile de intrare către gardieni.
Rețineți, totuși, că compilatorul propus la sfârșitul acestui articol autorizează comenzile de ieșire în gărzi, dar adaugă următoarea condiție în schimb:
Astfel, problema descrisă este bine evitată.
Comanda repetitivă este compusă dintr-o singură comandă alternativă, a cărei eșec duce la sfârșitul repetării. Prin urmare, putem considera că un repetitiv se poate termina doar cu succes. Sintaxic, ia forma unei stele urmată de o alternativă:
*commande alternativeDe exemplu :
i := 0; *[ i < 10 → i := i + 1 ]Aici, comanda repetată se va termina când i-am atins valoarea 10.
Adesea găsim sintaxa PROCES == listă de instrucțiuni pentru a defini un proces în afara unei comenzi paralele, cu singurul scop de a clarifica codul. Exemplu:
PREMIER == x : integer := 5; ... SECOND == msg : string; ... MAIN == [ premier :: PREMIER || second :: SECOND ]Lista de instrucțiuni MAIN este executată la pornirea programului.
Pentru a afișa un mesaj pe ecran, de obicei folosim comanda:
print (message)Vă permite să luați un număr aleatoriu în intervalul [început, sfârșit]
Oprește procesul care rulează pentru tps milisecunde. Vă permite să simulați timpii de așteptare etc.
Folosim în mod obișnuit sintaxa:
define CONSTANTE valeurExemplu:
define PI 3.1415Un producător trimite un șir de numere unui proces delegator care le transmite către doi consumatori. Utilizarea unei comenzi alternative în delegator permite: