Cina filozofilor (The Dining philosophers problem)

Cina filozofilor (The Dining philosophers problem)

Modeleaza procese care concureaza pentru acces exclusiv la un numar limitat de resurse, cum ar fi dispozitivele I/O.

Problema poate fi formulata astfel :

Se considera cinci filozofi care stau la o masa rotunda, fiecare avand in fata o farfurie cu mancare. Intre doua farfurii vecine exista o singura furculita.Viata unui filozof consta in alternarea perioadelor cand acesta mananca si respectiv gandeste. Cand unui filozof i se face foame, el incearca sa ia furculita din dreapta si furculita din stanga. Daca reuseste, mananca o perioada apoi pune furculitele jos si continua sa gandeasca.

Solutia evidenta duce din pacate la esec :

#define N 5 /* numarul filozofilor */

Sa presupunem ca toti cei cinci filozofi iau fiecare furculita din stanga simultan. Niciunul nu va mai putea sa ia furculita din dreapta, rezultand o situatie de impas.

Programul poate fi modificat in sensul ca, dupa ce ia furculita din stanga, filozoful i verifica daca furculita din dreapta este disponobila. Daca nu, pune furculita din stanga pe masa, asteapta un timp si apoi repeta intregul proces. Cu un pic de ghinion, toti filozofii pot incepe algoritmul simultan, sa ia furculitele din stanga, sa observe ca furculitele din dreapta nu sunt disponibile, sa puna pe masa furculitele din stanga, sa astepte, sa ia din nou furculitele din stanga simultan s.a.m.d., pentru totdeauna.

O observatie care poate veni in minte este ca filozofii sa astepte un timp aleator inainte de a relua procesul de achizitionare a furculitelor. Aceasta observatie este buna, dar se prefera solutiile care merg intotdeauna si nu esueaza din cauza unei anumite serii de numere aleatoare.

O imbunatatire ar fi folosirea unui semafor. Astfel, inainte sa ia furculitele, filozoful i poate apela functia DOWN pe un semafor mutex. Dupa ce mananca si pune furculitele pe masa, apeleaza functia UP pe mutex. Din punct de vedere teoretic, solutia este buna, dar practic, duce la un rezultat putin curios : la un moment dat, doar un singur filozof poate manca desi sunt disponibile cinci furculite si deci, pot manca doi filozofi simultan.

Solutia prezentata mai jos este corecta si ofera maximum de paralelism pentru un numar oarecare de filozofi. Programul foloseste un tablou, stare, care memoreaza starea fiecarui filozof : gandeste, ii este foame (si incearca sa obtina furculitele), mananca. Un filozof poate manca numai daca vecinii lui nu mananca. Vecinii sunt reprezentati prin macro-urile STANGA si DREAPTA. Astfel, daca i este 2, STANGA este 1 iar DREAPTA este 3.

Programul mai foloseste un tablou de semafoare, unul pentru fiecare filozof , folosit pentru a bloca filozoful daca nu poate obtine furculitele necesare.

Obs .: Fiecare proces ruleaza procedura filozof ; procedurile ia_furc, test, pune_furc sunt proceduri obisnuite si nu procese separate.