Ätande filosofer

Ätande filosofer är inom datavetenskap ett tankeexperiment menat att illustrera vissa problem som uppkommer vid parallella aktiviteter eller multikörning, till exempel baklås och resurssvält.

Problemet har sitt ursprung i ett problem som användes som tentamensproblem av Edsger Dijkstra 1965, där fem datorer skulle ha åtkomst till fem gemensamma bandspelare. Snart därefter återberättade Tony Hoare problemet som de ätande filosoferna. Problemet beskrevs även av Dijkstra i en artikel från 1971.

Problem

Illustration av problemet.

Fem filosofer sitter runt ett runt bord och ägnar sig åt två saker, att äta och tänka, men de pratar aldrig med varandra. De tänker inte när de äter och de äter inte när de tänker. Filosoferna har en tallrik med spaghetti var, det är från den de äter. Till höger om varje filosof ligger en gaffel, men för att äta spaghettin behöver de två gafflar.

Så när en filosof vill äta, måste han plocka upp två gafflar, den till vänster och den till höger. Men då kan filosoferna som sitter bredvid honom inte äta. Om alla filosofer samtidigt plockar upp gaffeln till höger om sig först kommer ingen av filosoferna att kunna äta vilket leder till baklås. Filosof $F_{1}$ kommer vänta på gaffeln som hålls av filosof $F_{2}$ som väntar på gaffeln som hålls av filosof $F_{3}$ och så vidare, vilket bildar en cirkulär kedja.

Lösningar

Tidsbegränsning

Man kan förebygga vanligt baklås genom att sätta in ett tidskrav: en filosof får använda en gaffel i högst fem minuter. Detta är dock en ganska dålig lösning då det fortfarande kan vara så att filosoferna börjar äta exakt samtidigt; alla börjar med att ta upp vänster gaffel och sitter sedan och väntar på höger gaffel i fem minuter, då de lägger ner vänster gaffel för att direkt ta upp den igen och sitta och vänta igen, och så vidare.

Kypare

Genom att introducera en kypare vid bordet som filosoferna måste fråga om lov innan de plockar upp gafflarna löses många problem. Om fyra gafflar används måste nästa filosof som frågar efter en gaffel vänta på kyparens tillåtelse. Säg att filosoferna kallas A, B, C, D och E och filosoferna A och C äter. Då är båda gafflarna bredvid B upptagna, men D och E har en ledig gaffel mellan sig. Om D skulle ta upp gaffeln skulle risken för baklås vara stor, men nu måste han fråga kyparen om lov innan han tar upp gaffeln och på så vis förhindras baklås.

Resurshierarki

Genom att introducera en partialordning över gafflarna och införa regeln att en filosof måste alltid börja med att ta upp den lägst ordnade gaffeln och när han ätit klart att lägga ner den högst ordnade gaffeln först undviks dödläge.

Exempelvis, låt gafflarna vara numrerade 1 till 5. En filosof måste alltid börja med att ta upp den med lägst nummer och sedan den med högst nummer. När han ätit klart lägger han först ner den med högst nummer och sedan den med lägst nummer. Säg att fyra filosofer tar upp sina lägst numrerade gafflar först, då endast den gaffeln numrerad som 5 ligger kvar på bordet. Den siste filosofen kan då inte ta upp denna gaffel eftersom han inte har sin lågt numrerade gaffel i sin hand. Endast en filosof kommer att kunna ta upp gaffel nummer 5 så han kommer att kunna äta.

Metoden med resurshierarki är inte alltid praktiskt användbar då man inte alltid känner till listan på resurser i förväg. Exempelvis, om en enhet använder resurserna 3 och 5 och sedan bestämmer sig för att den behöver resurs 2, måste den först släppa enhet 3 och 5, sedan ta resurs 2 och återta resurserna 3 och 5.

Referenser

• Dahl, Ola (2004). Realtidsprogrammering. Studentlitteratur. sid. 73-74. ISBN 91-44-03130-0 

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, tidigare version.

Externa länkar

• Java-applet som illustrerar problemet