Problema filozofilor la cină

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Problema Filozofilor la cină , cunoscută și sub numele de Problema celor cinci filozofi , este un exemplu care ilustrează o problemă comună de control al concurenței în informatică . Aceasta este o problemă clasică de sincronizare între procese paralele.

Descriere

Exemplul a fost descris în 1965 de Edsger Dijkstra , care l-a folosit pentru a expune o problemă de sincronizare. [1] Cinci filozofi stau la o masă rotundă cu o farfurie de spaghete în față și o furculiță în stânga (sau în dreapta; conform unei alte versiuni există în schimb un băț chinezesc [2] [3] ). Prin urmare, există cinci filozofi, cinci farfurii de spaghete și cinci furculițe.

Ilustrare a problemei filozofilor la cină

Imaginați-vă că viața unui filosof constă în alternarea perioadelor de mâncare și gândire și că fiecare filozof are nevoie de două furculițe pentru a mânca, dar că furculițele sunt luate pe rând. După ce a reușit să ia două furci, filosoful mănâncă o vreme, apoi lasă furcile și începe să se gândească din nou. Problema rezidă în dezvoltarea unui algoritm care previne blocarea sau înfometarea . Impasul poate apărea dacă fiecare dintre filosofi ține o furcă și nu reușește niciodată să o ia pe cealaltă. Filosoful F 1 așteaptă să ia furca pe care o ține filosoful F 2 , care așteaptă furca pe care o ține filosoful F 3 și așa mai departe într-un cerc vicios. [1] Situația de foame poate apărea indiferent de impas dacă unul dintre filosofi nu reușește niciodată să ia ambele furci.

Alegerea furcilor este analogă blocului de resurse limitate din programarea reală, situație cunoscută sub numele de „concurență”. Blocarea unei resurse este o tehnică obișnuită pentru acordarea accesului la aceasta de către un singur program sau o porțiune a programului la un moment dat. Dacă resursa solicitată de un program a fost deja blocată, programul așteaptă până când resursa este deblocată. Dacă blocarea implică mai multe resurse, în anumite circumstanțe poate apărea un blocaj. De exemplu, luați în considerare cazul unui program care are nevoie de două fișiere pentru procesare. Dacă două astfel de programe blochează câte un fișier, ambii vor aștepta degeaba ca celălalt program să deblocheze celălalt fișier.

Soluţie

Poziția filosofilor și a furcilor în soluționarea problemei

O soluție posibilă este să numerotăm furculițele și să le luăm în ordinea numerică crescândă, similar cu cazul alocării ierarhice a resurselor . În această soluție filosofii sunt numiți F 1 , F 2 , F 3 , F 4 și F 5 , în timp ce furcile din stânga lor sunt respectiv f 1 , f 2 , f 3 , f 4 și f 5 . Primul filosof F 1 va trebui să ia prima furcă f 1 înainte să poată lua a doua furcă f 2 . Filozofii F 2 , F 3 și F 4 se vor comporta într-un mod similar, luând întotdeauna furculița f i înainte de furca f i + 1 . Respectând ordinea numerică, dar inversând ordinea mâinilor, filosoful F 5 va lua mai întâi furca f 1 și apoi furca f 5 . Acest lucru creează o asimetrie care servește pentru a evita blocajele .

Eficacitatea în prevenirea foametei depinde de metoda de excludere reciprocă utilizată. Implementările care utilizează blocuri rotative sau bucle de așteptare pot provoca foamete din cauza problemelor de sincronie inerente acestor metode. Alte metode de excludere reciprocă care utilizează cozi pot preveni foametea mai eficient, asigurând accesul egal la furci de către ambii filosofi adiacenți.

Această soluție poate fi, de asemenea, generalizată în cazul în care se dorește să se permită oricărui număr de agenți să obțină acces exclusiv la orice număr de resurse. Agenții trebuie să respecte aceste reguli:

  1. Toți agenții trebuie să solicite accesul la resurse în ordine crescătoare, adică înainte de a solicita accesul la o resursă de ordin superior, agentul trebuie să fi obținut acces la resursele de ordin inferior de care are nevoie.
  2. Înainte de a solicita accesul la o resursă de comandă minoră, agentul trebuie să elibereze resursele de comandă majoră la care accesează.
  3. Dacă agentul nu are acces la o resursă de ordin superior, agentul trebuie să elibereze resursele de ordin inferior la care accesează.

Notă

  1. ^ a b Dijkstra, Edsger W. EWD-1000. Arhiva EW Dijkstra. Center for American History, Universitatea Texas din Austin.
  2. ^ (EN) Axel Jantsch, Modeling Embedded Systems and SoC's: Concurrency and Time in Models of Computation, Elsevier, 2003, p. 85, ISBN 9780080511825 .
  3. ^ (EN) Kevin R. Burton, .Net Common Language Runtime Unleashed, Sams Publishing, 2002, p. 312, ISBN 9780672321245 .

Bibliografie

  • Silberschatz, Abraham; Peterson, James L., Conceptele de sisteme de operare , Addison-Wesley, 1988, ISBN 0-201-18760-4 .
  • Dijkstra, EW (1971, iunie). Ordonarea ierarhică a proceselor secvențiale . Acta Informatica 1 (2): 115–138.
  • Lehmann, DJ, Rabin M. O, (1981). Despre avantajele liberei alegeri: o soluție simetrică și complet distribuită la problema filozofilor de luat masa. Principiile limbajelor de programare 1981 ( POPL '81), pp. 133–138.

Elemente conexe

Alte proiecte

Informatică Portal IT : accesați intrările Wikipedia care se ocupă cu IT
Adus de la „ https://it.wikipedia.org/w/index.php?title=Problema_dei_filosofi_a_cena&oldid=120153160 ”