Op 30 september 2021 07:09:40 schreef blurp:
dining philosophers probleem
Filosofen aan een ronde tafel met tussen elke 2 filosofen 1 vork, ze mogen alleen eten als ze zowel in hun linker als rechterhand een vork hebben. Als ze klaar zijn met eten leggen ze hun vorken weer neer. (Met 1 filosoof en 2 vorken is dat simpel en gaat het altijd goed. Met meer filosofen zitten ze op elkaar te wachten en moet je er iets op verzinnen dat elk kan eten)
(Zoek 'm maar ergens op. Dan is het vast beter uitgelegd dan dat ik doe. Het is een leuke en het legt uit wat "deadlock" en "starvation" is.)
In plaats van filosofen en vorken kan het ook een stuk software zijn dat wacht op 2 resources. Bijvoorbeeld schrijftoegang tot een stuk geheugen (of een file) en toegang tot een communicatiebus.
Maar met 3 filosofen en 3 vorken bijvoorbeeld, kun je methoden uitdenken hoe te voorkomen dat iedereen op elkaar zit te wachten.
Probeersel 1:
Elk pakt eerst zijn linkervork, en dan de rechter. Als er een vork niet is, wachten ze. Als ze beide vorken hebben eten ze. Als ze uitgegeten zijn leggen ze de vork neer.
Resultaat: Elk pakt een linkervork en zit te verhongeren.
Probeersel 2:
Elk pakt een linkervork, dan de rechter. Als een vork er niet is, leggen ze de vork die ze al hebben weer terug. Als ze beide vorken hebben eten ze. Als ze uitgegeten zijn leggen ze de vork neer.
Resultaat:
Een helehoop gegooi met vorken, maar er wordt met wat mazzel nog wat gegeten tussendoor.
Probeersel 3:
Elk pakt een linkervork, dan de rechter. Als een vork er niet is, wachten ze een random tijd tussen 0 en 1 seconde en als ze dan de andere vork niet hebben kunnen pakken leggen ze de vork die ze al hebben weer terug. Als ze beide vorken hebben eten ze. Als ze uitgegeten zijn leggen ze de vork neer.
Resultaat:
Een helehoop gegooi met vorken, maar er wordt nog wat gegeten tussendoor.
Er was een betere methode, maar die weet ik niet meer uit mijn hoofd.
Je kunt ook de filosofen nummeren en iets maken dat lagere nummers / hogere prioriteit vorken kan afpakken van hogere nummers / lagere prioriteit. Dan wel zorgen dat elk van je filosofen een uniek nummer heeft.
Of je maakt 1 mutex, een lepel, en wie de lepel heeft mag vorken pakken.
(Het kan ook met N/2 lepels en N vorken, maar dan moet elke filosoof toegang hebben tot elke vork, en dus niet alleen tot die die links en rechts naast 'm liggen).
1-voor-1 atomic vorken pakken (2 vorken tegelijk pakken zonder dat een ander ermee vandoor kan gaan) gaat ook goed. Moeten er wel nog 2 vorken zijn en niet nog maar eentje, maar je zit tenminste niet te wachten met elk 1 vork.
Valsspelen door ze gewoon 2x zo veel vorken te geven als er filosofen zijn, mag voor het gedachte-experiment niet (Maar kan in het echt wel werken, als je inderdaad kunt garanderen dat er altijd genoeg resources zijn / de resources gewoon vast toewijst en niet deelt - een communicatiebus waar maar 1 proces aan mag zitten of gewoon vast toegewezen geheugen.)
Valsspelen door ze 1 vork extra te geven, zodat er gagarandeerd eentje kan eten die dan zijn vorken neerlegt waarna de rest aan de beurt is mocht geloof ik wel. Maar werkt in het echt niet, als je die extra resource gewoon niet hebt. Dan heb je dus alsnog de betere methode nodig. (Bijvoorbeeld de mutex/lepel)
Er is online wel betere uitleg te vinden dan dat ik hier neerzet. Je moet er eigenlijk al een plaatje bij hebben van de ronde tafel met 3 filosofen en 3 vorken tussen hen in. (Of het bestek op een hoop in het midden: 3 vorken en 1 lepel. Of 4 vorken en 2 lepels, etc. bij meer filosofen. Wie de lepel/mutex heeft mag 2 vorken uit de hoop graaien).
't is jammer dan bd.eduweb.hhs.nl offline is, via http://www.hc11.demon.nl is het ook niet meer te bereiken. Wel zijn daar de nieuwere sheets voor de Rotterdamse studenten te vinden, maar daar kan ik het minder makkelijk terugvinden. (Desondanks is het het bekijken ongetwijfeld waard. Harry Broeders is een hele goede docent.)
EDIT: zie je wel, het ging bij mij al mis zonder plaatje te tekenen met 3 filosofen en 4 vorken. Dat is dus de "valsspelen met een extra vork" optie.