Filosofenprobleem

In de informatica is het filosofenprobleem een aansprekend voorbeeld van de problematiek van synchronisatie. Het probleem is in 1965 door Edsger Dijkstra voor het eerst gesteld als tentamenvraag; die ging over vijf computers die toegang willen hebben tot vijf tape-drives. De herformulering waarin computers en tape-drives door filosofen en vorken zijn vervangen is kort daarna bedacht door Tony Hoare.

Vijf filosofen zitten aan een ronde tafel en hebben ieder een bord spaghetti voor zich. Elke filosoof moet zo nu en dan spaghetti eten. Een filosoof die niet aan het eten is, denkt na.

Er liggen vijf vorken op tafel: een tussen elke twee filosofen. Om te kunnen eten moet een filosoof beide vorken aan weerszijden in handen hebben. Een filosoof kan die vorken oppakken, maar alleen een voor een en uiteraard alleen als de buurman niet op dat moment de vork in handen heeft. Een filosoof kan een opgepakte vork weer terugleggen.

Het probleem is nu om de filosofen zodanige instructies te geven, die dus alleen betrekking hebben op het oppakken en weer terugleggen van vorken aan weerszijden, dat gegarandeerd iedere filosoof te eten krijgt. Dit is een voorbeeld van een probleem in het gedistribueerd programmeren. Zulke problemen zijn in het algemeen niet zo eenvoudig op te lossen.

Stel bijvoorbeeld dat elke denker de filosofie hanteert: ik pak een vork zo gauw ik kan, als beide beschikbaar zijn eerst de linkervork; zo gauw ik beide vorken in handen heb eet ik wat; dan leg ik de vorken weer neer. Dat lijkt op het eerste gezicht een redelijk plan. Helaas kan dan de situatie ontstaan dat elke filosoof de linkervork in de linkerhand heeft, en zal dan elke filosoof eeuwig blijven wachten tot de rechtervork vrijkomt. De situatie is een voorbeeld van deadlock: er is geen voortgang in het systeem meer mogelijk. Elke filosoof zal verhongeren.

Er zijn technieken om tot een oplossing te komen die een deadlock bewijsbaar voorkomen; Dijkstra heeft het probleem verzonnen om zulke technieken te demonstreren. Bij zulke oplossingen kunnen extra observaties en/of handelingen worden ingevoerd. Omdat we met een gedistribueerd systeem te maken hebben, zijn alle observaties en handelingen communicaties tussen de deelnemende partijen.

We kunnen bijvoorbeeld de denkers nummeren en elke denker alleen een vork laten pakken als er geen hoger genummerde denker al een vork vastheeft. Nu is deadlock onmogelijk. (Maar is deze oplossing uitvoerbaar? Het probleem is nu veranderd door te eisen dat een filosoof op de een of andere manier kan weten of een hoger genummerde buur al een vork in de andere hand heeft. Die informatie moet dus op de een of andere manier doorgegeven worden. Hoe? Stel dat een filosoof de observatie kan doen of een buur een vork in de andere hand heeft. Dat is niet toereikend: als de filosoof ziet dat dat niet zo is en op basis daarvan beslist om zelf de met die buur gedeelde vork op te pakken, kan intussen die buur de andere vork opnemen.)

Deadlock is echter niet het enige soort situatie dat in het ontwerp moet worden uitgesloten. Stel bijvoorbeeld dat we een denker zelfs geen vork laten pakken als tegelijk een hoger genummerde hetzelfde probeert. Dan zal de hoogstgenummerde altijd eten, terwijl de rest verhongert. Zo'n situatie wordt starvation genoemd.

Men kan dit nog verder aanscherpen, bijvoorbeeld door te eisen dat het systeem 'eerlijk' is, in de zin dat de filosofen niet alleen allemaal altijd nog ooit de kans krijgen te eten, maar ze die kans zelfs even vaak krijgen; of door te eisen dat de totale wachttijd zo klein mogelijk is.

Deze situatie illustreert de problemen die zich kunnen voordoen bij het synchroniseren van toegang tot resources (de vorken), bijvoorbeeld door verschillende threads (de filosofen) in een computerprogramma. Als verschillende threads gebruikmaken van dezelfde variabelen of bestanden is het niet veilig dat ze die tegelijk proberen aan te passen; daarom kan het onvermijdelijk zijn dat threads op elkaar moeten wachten. Als deze synchronisatie niet correct wordt ontworpen kan het voorkomen dat een thread helemaal nooit meer aan de beurt komt (starvation) of dat dat zelfs voor elke thread geldt (deadlock).