Algoritmi Paraleli

Prezentarea proiectului

Problema filozofilor la masă a fost expusă prima dată de Dijkstra, în anul 1965 şi reprezintă o problemă clasică de sincronizare.

Figura 1: Masa cinei filozofilor

5 filozofi stau aşezati la o masă circulară

Fiecare filozof are in faţă o farfurie cu mâncare

Pentru a putea apuca mâncarea, la stanga si la dreapta fiecărei farfurii, se găseşte câte un beţişor

În felul acesta, între două farfurii cu mâncare se găseşte un beţişor, iar între două beţişoare, câte o farfurie

Ciclul de viaţă al fiecărui filozof este format din perioade de meditaţie şi perioade de hrănire.

Când un filozof este înfometat, încearcă să ridice beţele aflate în stânga şi în dreapta farfuriei proprii.

Dacă are la îndemână ambele beţe, va putea mânca şi, într-un final va pune beţele înapoi pe masă, în stânga şi în dreapta farfuriei. Apoi va continua, desigur, cu o perioadă de meditaţie.

Gândeşte

Ridică băţul drept

Ridică băţul stâng

Mânâncă

Aşează băţul stâng

Aşează băţul drept

Repetă

Dacă toţi filozofii apucă simultan băţul din stânga, toţi vor aştepta ca băţul din dreapta să devină disponibil.

Din moment ce nici unul dintre ei nu va reuşi să mânânce, nu va elibera băţul pe care l-a ridicat, ceea ce va crea o situaţie de impas(deadlock ).

Chiar dacă filozofii s-ar pune de acord să lase din mână băţul pe care l-au ridicat, situaţia s-ar sfârşi tragic dacă toţi ar face această operaţie simultan.

De data aceasta, filozofii s-ar bloca într-un ciclu infinit de ridicări şi aşezări de beţe, fără a fi capabili să ajungă la mâncare. O situaţie în care programele sunt executate nedefinit fără a realiza nici un fel de progres va fi numită înfometare(starvation ).

Există mai multe soluţii ale problemei filozofilor.

Pentru a nu apărea interblocarea se folosesc, în general, soluţii de prevenire a acesteia adică se impun unele restricţii în ceea ce priveşte acţiunile filozofilor, cum ar fi:

- unui filozof i se permite să ia un beţişor numai atunci când ambele beţişoare, din dreapta şi din stânga sa sunt disponibile;

- se creează o corespondenţă biunivocă între mulţimea numerelor naturale şi filozofi, fiecare filozof având un număr natural; o soluţie asimetrică impune filozofilor cu număr impar să

apuce mai întâi beţişorul din stânga şi apoi pe cel din dreapta, iar filozofilor cu număr par să ia mai întâi beţişorul din dreapta şi apoi pe cel din stânga.