Concurență (IT)

În informatică , concurența este o caracteristică a sistemelor de calcul în care se poate întâmpla ca un set de procese sau subprocese de calcul ( fire ) să ruleze în același timp. Acest sistem se numește sistem concurent sau sistem concurent . Executarea simultană poate duce la interacțiunea dintre procese atunci când este implicată o resursă partajată. O clasă importantă de sisteme informatice în care aspectele concurenței sunt fundamentale este cea a sistemelor de operare .

Problema filozofilor la cină , o problemă clasică a concurenței și a partajării resurselor

Introducere

Conceptul de concurență este opus celui de secvențialitate. Într-un sistem secvențial, procesele rulează unul câte unul și nu există nicio formă de interacțiune între ele pe măsură ce rulează.

Având în vedere că într-un sistem concurent varietatea interacțiunilor care pot apărea între procesele în curs de desfășurare este considerabilă, s-au dezvoltat teorii cu privire la gestionarea problemelor legate de concurență. Pe baza acestor teorii, au fost dezvoltate atât tehnici de programare (programare concurentă), cât și limbaje care integrează nativ primitive pentru gestionarea corectă a concurenței.

Probleme

Concurența poate duce la o serie de probleme legate de utilizarea aceleiași resurse partajate de mai multe procese. O anumită succesiune de evenimente poate provoca condiții critice. Programarea simultană exploatează câteva principii pentru a face față și a rezolva acest tip de problemă.

Curse critice ( Condiții de cursă )
În unele sisteme se poate întâmpla ca procesele care rulează să partajeze o resursă comună de orice fel (fie că este o zonă de memorie partajată sau un periferic). În special, dacă se întâmplă că mai multe procese depind de ordinea în care se execută rezultatul final, aceasta este o condiție critică a cursei (condiția cursei). Rezultatul execuției în cazul rulărilor critice este absolut imprevizibil.

Problema „rulărilor critice” poate fi evitată împiedicând mai multe procese să acceseze resurse partajate la un moment dat. Excluderea reciprocă împiedică mai multe procese care concurează pentru o resursă să o poată accesa în același timp.

Impas
Atunci când unui proces i se acordă acces exclusiv (de exemplu prin excludere reciprocă) la o resursă, pot apărea situații de blocaj. În mod formal, un set de procese este blocat atunci când fiecare proces din set așteaptă un eveniment care poate avea loc numai printr-un alt proces din set. Deoarece toate procesele sunt în așteptare, nimeni nu va putea crea vreodată evenimentul de deblocare prin prelungirea așteptării la nesfârșit. Tehnicile de identificare a situațiilor de impas implică analiza graficelor resurselor alocate sau prin crearea așa-numitelor „matrici de alocare”. Rezoluția standului poate fi abordată în mai multe moduri. Conceptual ele pot fi împărțite în:
- Rezoluție prin pre-lansare : se alege un proces care deține o resursă din setul de procese blocate și se elimină accesul exclusiv (pre-lansare sau preempțiune) la o resursă partajată (cauza blocării). Operația este uneori dificilă, uneori imposibilă și depinde de tipul de resursă pe care procesul a blocat-o.
- Rezoluție după punct de control : Se creează jurnale (puncte de control) care descriu starea de utilizare a resurselor partajate. Când este detectată o staționare, se face o „ revenire la punctul de control ” la condițiile anterioare. Chiar și această tehnică este dificilă sau chiar imposibilă de implementat, deoarece returnarea ar putea cauza pierderea datelor sau inconsecvență.
- Rezoluție prin ștergere : se alege și se încheie un proces. Această tehnică este, de asemenea, foarte complexă și necesită estimări și presupuneri cu privire la tipul de proces care trebuie eliminat. Mai mult, ieșirea din starea de stand nu este garantată, deci poate fi necesară încheierea altor procese, situație care complică și mai mult problema.

De asemenea, este posibil să se facă estimări asupra resurselor care vor fi angajate printr-un proces. Datorită acestor estimări, există sisteme în care în loc să rezolve situații de blocaj este mai ușor să le eviți a priori.

Toate tehnicile implică construirea matricelor care urmăresc utilizarea resurselor (matricele traiectoriei resurselor) sau se bazează pe algoritmi cunoscuți ca algoritmul bancherului .

Foame
Literal, de foame, este o problemă strâns legată de blocare. Când politicile de alocare a resurselor partajate favorizează un proces față de altul, procesul în care sunt atribuite într-o măsură mai mică suferă de foame . De fapt, este blocat și nu poate continua, deși nu este într-o stare de stand. În sistemele în care sunt accesate resursele partajate, este întotdeauna necesar să se stabilească o politică prioritară și ordinea în care acestea sunt partajate. Deși aceste politici pot fi cât se poate de corecte, ele pot duce la condiții de foame.

Comunicarea intraprocesuala

În contextul programării concurente, comunicarea interprocese (IPC sau Interprocess Communication) este de o importanță fundamentală pentru gestionarea corectă a posibilelor situații de acces la resurse partajate. Sistemele concurente oferă primitive de comunicare care vă permit să alternați (excludându-vă reciproc) în accesarea unei resurse partajate, precum și primitive de sincronizare care vă permit să interveniți asupra secvenței în funcție de care vor avea loc anumite evenimente. Fiecare sistem concurent implementează și pune la dispoziție propriile sale primitive, dar totuși sistemele se referă la o bază teoretică comună. Pentru aceasta puteți crea o imagine de ansamblu.

Cele mai frecvente modalități de comunicare prin proces sunt:

Mutex : variabile binare care vă permit să gestionați accesul la o resursă partajată prin accesul exclusiv al unuia dintre concurenți. Operațiunile de blocare (în termeni simplisti care solicită acces la resursa partajată) și deblocare (eliberarea resursei) sunt atomice.

Semafoare n-ary: variabile n-ary care pot fi incrementate și decrementate. Procesul care diminuează semaforul se va opri imediat ce se atinge zeroul variabilei. Un proces care crește semaforul, pe de altă parte, trezește toate procesele care au fost blocate în faza de decrement. Aceasta este una dintre primitivele de bază care permit sincronizarea. Operațiile de creștere, descreștere și control al semaforului sunt atomice.

Tastați variabilele de condiție: cunoscute și sub numele de variabile de condiție sunt variabile asociate cu două primitive: așteptați (în așteptare) și semnal (semnale, treziți). O procedură care numește așteptarea primitivă se pune în așteptare nedeterminată, o procedură care numește semnalul primitiv trezește o așteptare în așteptare. De asemenea, în acest caz operațiile sunt atomice.

Schimb de mesaje : Două proceduri, trimiterea și primirea, permit două procese să schimbe mesaje. Schimbul de mesaje este de obicei utilizat în sistemele paralele.

Bariere : Aplicațiile sunt uneori împărțite în faze, cu regula că niciun proces nu poate continua dacă toți colegii săi nu sunt pregătiți să facă acest lucru mai întâi. Barierele pun în aplicare acest concept: un proces care și-a încheiat etapa denumește o barieră primitivă și se prăbușește. Când toate procesele implicate și-au terminat etapa de execuție invocând și bariera primitivă, sistemul le deblochează pe toate, permițându-le să treacă la o etapă ulterioară.

Conceptul de atomicitate în sistemele concurente are două caracteristici fundamentale:

Executarea acestuia nu poate fi anticipată: blocarea și deblocarea unui mutex nu pot fi întrerupte în timpul executării acestora.
Executarea sa este unică: nu se poate întâmpla ca două procese să reușească simultan să blocheze același mutex. În sistemele uniprocesor, această afirmație este o consecință a celei anterioare, deoarece conceptul de „contemporaneitate” este doar virtual.

Este evident că toate primitivele de comunicare și sincronizare din cadrul procesului trebuie să respecte această condiție de atomicitate.

Probleme clasice

Există o serie de probleme clasice în programarea concurentă. Acestea sunt utilizate pentru a demonstra eficiența anumitor teorii sau algoritmi și oferă o bază comună pentru a face comparații. Printre cele mai faimoase sunt enumerate:

Producător și consumator: cunoscut și ca problema bufferului la capacitate limitată (problema bufferului delimitat). Un set de procese numite producători produc date pentru a le pune într-un buffer de dimensiune finită, în timp ce un alt set, consumatorii, extrage date din acest buffer reprezentând resursa partajată. Programarea simultană ideală oferă acces exclusiv la buffer și arbitrează corect comportamentul producătorilor atunci când bufferul este plin și al consumatorilor atunci când bufferul este gol.

Cititori și scriitori : modele de acces la baze de date . Scriitorii, care îi modifică conținutul, și cititorii care îl recuperează, acționează asupra unei baze de date. Programarea simultană corectă necesită accesul unui singur scriitor în timpul fazei de modificare (și fără cititor pentru a evita inconsecvența) în timp ce accesul multor cititori este posibil atâta timp cât nu există scriitori activi în același timp. Vezi și secțiunea „ Secțiunea critică ”.

Filosofii la cină : formulat de Edsger Dijkstra ca o problemă a filosofilor culinare . Unii filosofi (5 în textul original) sunt așezați la masă în fața farfuriei și a două furci (împărțite cu vecinii lor). Filosofii alternează momente în care să meditezi și momente în care să mănânci. Pentru a mânca trebuie să ia cele două furculițe lângă farfurie și să mănânce în timp ce în timpul meditației trebuie să țină furculitele pe masă. Este clar că numărul de furci împiedică toți filosofii să mănânce în același timp, prin urmare o programare concurentă corectă trebuie să fie capabilă să hrănească alternativ toți filosofii, evitând că cineva suferă în special de foame și evită tarabele în faza de achiziție. ".

Frizer adormit : un frizer deține un magazin cu un singur scaun de lucru și un număr limitat de locuri de așteptat. Dacă nu există clienți, frizerul doarme. Când ajunge primul client, frizerul se trezește și începe să-l slujească. Dacă clienții ajung în perioada de afaceri a frizerului, aceștia așteaptă locurile disponibile. La sfârșitul locurilor de așteptare, un alt client este aruncat. Această problemă este foarte apropiată de sistemul de operare computerizat de asistență în care operatorul servește, unul câte unul, toți clienții din coadă sau așteaptă, fără a efectua nicio operațiune specială, pentru sosirea de noi apeluri. Programarea simultană corectă trebuie să-l facă pe frizer să „doarmă” în absența clienților, să îl activeze pe primul client la sosire și să pună la coadă toți clienții ulteriori, menținându-i inactivi.

Modele matematice

Plasele Petri sunt un instrument excelent pentru descrierea sistemelor concurente.

Bibliografie

Texte aprofundate

Paolo Ancilotti, Maurelio Boari, Programare simultană și distribuită , McGraw-Hill, ianuarie 2007, ISBN 88-386-6358-0 . Soluțiile exercițiilor rezumative pot fi descărcate gratuit online .

Elemente conexe

Alte proiecte

Wikționarul conține dicționarul lema « competiție »
Wikimedia Commons conține imagini sau alte fișiere despre concurență

linkuri externe

( EN ) Simulator

Portal IT : accesați intrările Wikipedia care se ocupă cu IT