Filosofenprobleem: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
+cat paradox – voel je vrij om mij te vertelllen dat dit geen (schijn)paradox is |
details |
||
Regel 1:
[[Afbeelding:Dining philosophers.png|thumb|200px|Illustratie bij het filosofenprobleem]]
In de [[informatica]] is het '''filosofenprobleem''' een aansprekend voorbeeld van de problematiek van [[gedistribueerd programmeren|synchronisatie]].
In [[1965]]
==Het probleem==
▲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_(situatie)|deadlock]]': er is helemaal geen voortgang in het systeem meer mogelijk. Elke filosoof zal verhongeren.
Er zijn technieken om tot
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.
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.
| |||