Problema filozofilor

Enuntul problemei
Mai muti filozofi stau la o masa rotunda. Un filozof face doar doua lucruri: gandeste si mananca. El gandeste pentru o vreme, dupa care i se face foame. Mananca pana se satura si apoi incepe sa gandeasca din nou. Fiecare filozof este atat de implicat in activitatea sa de a gandi sau manca incat este total neatent la ce se intampla in jurul sau. Intre 2 filozofi se afla un singur betigas pentru mancat. Un filozof are nevoie si de betigasul din dreapta si de cel din stanga pentru a putea manca. Evident, 2 filozofi vecini nu pot manca in acelasi timp. Un filozof nu-l poate deranja pe vecinul sau. Daca un filozof vrea sa manance si un vecin de-al sau are unul dintre cele doua betigase, el trebuie sa astepte pana cand betigasul respectiv devine disponibil.

Algoritmul problemei
Pentru rezolvarea acestei problemei voi implementa pentru fiecare filozof in parte cate un fir de executie.
Un algoritm simplu de aplicat pentru fiecare filozof ar fi urmatorul:
       1. gandeste;
       2. ia betigasul din dreapta;
       3. ia betigasul din stanga;
       4. mananca;
       5. lasa betigasul din stanga;
       6. lasa betigasul din dreapta;
       7. reia procedeul.
In acest algoritm apare insa o problema serioasa, si anume: daca toti filozofii ridica betigasul din dreapta in acelasi timp, cand vor incerca sa ridice betigasul din stanga, nu va fi acolo. Va fi la vecinul din stanga. Astfel toti filozofii vor muri de foame cu un betigas in mana si cu mancarea pe masa. Acest lucru se numeste deadlock (impas).

In problemele care necesita implementarea mai multor fire de executie, asa cum este cea de fata, deadlocks sunt un mare pericol. Ele pot aparea din unul din urmatoarele motive:
- fiecare fir (filozof) are nevoie exclusiva de cele doua betigase;
- unui filozof nu ii este permis sa ia betigasul de la vecinul lui;
- fiecare filozof asteapta in timp ce tine un betigas pe care un alt filozof il asteapta.
Primele doua motive nu pot fi inlaturate, deci ramane doar al treilea. Deadlocks pot fi inlaturate daca exista un betigas anume pe care nici un filozof nu-l poate tine in timp ce asteapta celalalt betigas. Asadar orice filozof poate manca cu acest betigas, dar nu-l poate tine fara sa manance. Pentru aceasta voi marca un betigas ca fiind "aur", iar celelatle ca fiind "lemn". Filozofii ridica un betigas, apoi pe celalalt. Daca betigasul "aur" este ales primul, este lasat jos imediat si este ales celalalt. Este posibil ca in timpul dintre lasarea acestuia jos si ridicarea celuilalt, acesta din urma sa fie cel de aur. In acest caz, se reia algoritmul. Dar iata care este algoritmul folosit:
       1. gandeste;
       2. ridica betigasul din dreapta;
       3. daca betigasul din dreapta este marcat "aur", atunci
              3.1. begin
              3.2. lasa jos betigasul din dreapta;
              3.3. ridica betigasul din stanga;
              3.4. daca betigasul din stanga este marcat "aur", atunci
                     3.4.1. lasa jos betigasul din stanga;
                     3.4.2. treci la pasul 2.
              3.5. (altfel) apuca betigasul din dreapta;
              3.6. end;
       4. altfel apuca betigasul din stanga;
       5. mananca;
       6. inverseaza betigasele;
       7. lasa jos betigasul din mana dreapta;
       8. lasa jos betigasul din mana stanga;
       9. treci la pasul 1.
Dupa ce mananca, fiecare filozof trebuie sa inverseze betigasele. Acest lucru acorda sanse egale tuturor. Altfel, cel din stanga ar fi dezavantajat.
Pentru ca filozofii sa nu interfereze unul cu altul, voi folosi o regiune critica pentru a ma asigura ca un filozof are posibilitatea de a ridica sau de a lasa jos un betigas. In timp ce un filozof ridica sau lasa jos un betigas, veinul lui nu are voie sa atinga betigasul. Daca un filozof vrea sa ridice un betigas, dar acesta nu este disponibil, el trebuie sa astepte pana va fi disponibil. Toate acestea se realizeaza prin sincronizarea firelor de executie.

Programul include:
1. clasa "Philosopher" care mosteneste clasa "Thread" pentru implementarea cate unui fir de executie pentru fiecare filozof in parte. Aici este suprascrisa functia run() care apeleaza functiile definite tot aici think(), PickUpSticks(), eat(), PutDownSticks(),
2. clasa "Chopstick" pentru desenarea betigaselor;
3. clasa "ScenePainter" pentru desenarea celor 5 stari ale filozofilor (gandeste, asteapta betigasul din dreapta, are betigasul din dreapta si asteapta betigasul din stanga, betigasul din dreapta a fost marcat "aur", mananca);
4. alte clase pentru afisare grafica.