Filosofenprobleem
In de informatica is het filosofenprobleem een aansprekend voorbeeld van de problematiek van synchronisatie. In 1965 werd door Edsger Dijkstra een examenvraag bedacht over vijf computers die toegang wilden hebben tot vijf tape-drives. Snel daarna vertaalde Tony Hoare het probleem in termen van vijf dinerende filosofen.
Het probleem [bewerken]
De vijf filosofen zitten aan een tafel en kunnen twee dingen doen: spaghetti eten of filosoferen. Als ze eten kunnen ze niet denken en als ze denken kunnen ze niet eten. De spaghetti staat midden op de ronde tafel en om te eten heeft elke filosoof twee vorken nodig. Er zijn echter slechts vijf vorken. Zo heeft elke filosoof één vork aan zijn linker en één aan zijn rechterhand; de filosoof kan die oppakken, maar alleen een voor een.
Het probleem is nu om de filosofen zodanige instructies te geven dat ze niet zullen verhongeren.
Dit soort problemen zijn in het algemeen niet zo eenvoudig op te lossen.
Stel bijvoorbeeld dat elke denker als filosofie heeft: ik pak een vork zo gauw ik kan, als beide beschikbaar zijn eerst de linkervork; zo gauw ik beide vorken heb eet ik wat; dan leg ik de vorken weer neer. Op het eerste gezicht een redelijk plan, maar nu kan de situatie ontstaan dat elke filosoof de linkervork in de linkerhand heeft, eeuwig wachtend tot de rechtervork vrijkomt. Dit is een voorbeeld van 'deadlock': er is helemaal geen voortgang in het systeem meer mogelijk. Elke filosoof zal verhongeren.
Er zijn technieken om tot oplossingen te komen die deadlock bewijsbaar voorkomen; Dijkstra heeft het probleem verzonnen om zulke technieken te demonstreren.
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.
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.
Relevantie [bewerken]
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 gebruik maken 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).
