The Dining Philosophers Problem är ett klassiskt exempel som används inom datavetenskap för att illustrera synkroniseringsproblem i utvecklingen av parallella algoritmer och tekniker för att lösa dessa problem.
Problemet formulerades 1965 av Edsger Dijkstra som en examinationsövning för studenter. Ett exempel togs på konkurrerande tillgång till en bandenhet . Snart formulerades problemet av Anthony Hoare i den form som det är känt idag [1] [2] [3] .
Fem tysta filosofer sitter runt ett runt bord, med en tallrik spagetti framför varje filosof. Gafflar ligger på bordet mellan varje par av närmaste filosofer.
Varje filosof kan antingen äta eller tänka. Att äta begränsas inte av mängden spagetti som finns kvar - ett oändligt utbud antyds. Filosofen kan dock bara äta när han håller två gafflar, tagna från höger och vänster (en alternativ formulering av problemet innebär skålar med ris och ätpinnar istället för skålar med spagetti och gafflar).
Varje filosof kan ta närmaste gaffel (om en finns tillgänglig) eller lägga ner den om han redan håller i en. Att plocka upp varje gaffel och återföra den till bordet är separata åtgärder som måste utföras efter varandra.
Frågan om uppgiften är att utveckla en beteendemodell ( parallell algoritm ) där ingen av filosoferna kommer att svälta, det vill säga att han för alltid kommer att växla mellan att äta och tänka.
Problemet är formulerat på ett sådant sätt att det illustrerar problemet med att undvika dödläge - ett tillstånd i systemet där framsteg är omöjliga.
Till exempel kan man råda varje filosof att utföra följande algoritm:
Denna lösning på problemet är felaktig: den tillåter systemet att nå ett dödläge, där varje filosof har tagit gaffeln till vänster och väntar på att gaffeln till höger ska bli fri [4] .
Resurssvältproblemet kan uppstå oavsett dödläge om någon av filosoferna inte kan få tag i vänster och höger gafflar på grund av synkroniseringsproblem. Till exempel skulle en regel kunna föreslås att filosofer ska lägga tillbaka en gaffel på bordet efter att ha väntat fem minuter på att en annan gaffel ska vara tillgänglig, och vänta ytterligare fem minuter innan de försöker ta gafflarna i besittning igen. Detta schema eliminerar möjligheten till blockering (eftersom systemet alltid kan gå till ett annat tillstånd), men det finns fortfarande möjlighet till en "loop" av systemet ( eng. livelock ), där systemets tillstånd ändras, men det utför inget användbart arbete. Till exempel, om alla fem filosoferna dyker upp i matsalen samtidigt och var och en tar upp den vänstra gaffeln samtidigt, kommer filosoferna att vänta fem minuter i hopp om att få rätt gaffel, sedan lägga ner den vänstra gaffeln och vänta ytterligare fem minuter innan du försöker få tag i gafflarna igen.
Ömsesidig uteslutning är huvudidén i Dining Philosophers Problem . Detta problem är ett allmänt, abstrakt scenario för att förklara denna typ av problem. Filosofernas misstag illustrerar de svårigheter som uppstår i verklig programmering när flera program kräver exklusiv tillgång till delade resurser. Dessa frågor studeras inom området parallell beräkning .
Dijkstras ursprungliga mål med att formulera Dining Philosophers Problem var att demonstrera möjliga problem med externa datorenheter som bandenheter [1] . Omfattningen av denna uppgift sträcker sig dock mycket längre, och komplexiteten som beaktas i uppgiften uppstår oftare när flera processer försöker komma åt en datauppsättning som uppdateras.
System som måste hantera ett stort antal samtidiga processer (som operativsystemkärnor ) använder tusentals lås och synkroniseringspunkter. Detta kräver strikt efterlevnad av metoder och protokoll om dödlägen, svält och datakorruption ska undvikas.
En relativt enkel lösning på problemet uppnås genom att lägga till en servitör nära bordet. Filosofer måste vänta på servitörens tillstånd innan de tar gaffeln. Eftersom servitören vet hur många gafflar som används för tillfället kan han fatta beslut om fördelningen av gafflarna och på så sätt förhindra att filosofer låser sig. Om fyra av fem gafflar redan används, måste nästa filosof som begär en gaffel vänta på servitörens tillstånd - vilket inte kommer att tas emot förrän gaffeln släpps. Det antas att filosofen alltid försöker ta den vänstra gaffeln först, och sedan den högra (eller vice versa), vilket förenklar logiken. Servitören fungerar som en semafor , ett koncept som introducerades av Dijkstra 1965 [5] .
För att visa hur denna lösning fungerar, låt oss anta att filosoferna är märkta A till D i medurs riktning. Om filosoferna A och B äter, är fyra gafflar upptagna. Filosof B sitter mellan A och C, så att ingen av gafflarna är tillgänglig för honom. Samtidigt har filosoferna D och D tillgång till en oanvänd gaffel mellan sig. Låt oss anta att filosof G är hungrig. Om han omedelbart tar en gratis gaffel, blir ömsesidig blockering av filosofer möjlig. Om han istället ber servitören om lov, ber han honom att vänta – och du kan vara säker på att så fort ett par gafflar är lediga, så kommer åtminstone en filosof att kunna ta två gafflar. Därmed blir dödläget omöjligt.
En annan enkel lösning uppnås genom att tilldela en delordning till resurserna (gafflar i detta fall) och göra konventionen att resurserna begärs i den ordningen och returneras i omvänd ordning. Det bör inte heller finnas två resurser ur funktion som används av samma arbetsenhet.
Låt resurserna (gafflarna) numreras från 1 till 5, och varje arbetsenhet (filosof) tar alltid den lägsta numrerade gaffeln först, och sedan den högsta numrerade gaffeln av de två tillgängliga. Därefter lägger filosofen ner gaffeln med den högre siffran först, sedan den med den mindre. I det här fallet, om fyra av fem filosofer tar den lägsta numrerade gaffeln samtidigt, kommer den högsta möjliga numrerade gaffeln att finnas kvar på bordet. Således kommer den femte filosofen inte att kunna ta en enda gaffel. Dessutom kommer bara en filosof att ha tillgång till den högsta numrerade gaffeln, så han kan äta med två gafflar. När han har slutat använda gafflarna kommer han att lägga den högsta numrerade gaffeln på bordet först, sedan den mindre, vilket gör att den andra filosofen kan plocka upp den saknade gaffeln och börja äta.
Denna lösning föreslogs av Dijkstra.
Även om resurshierarkin undviker dödlägen, är denna lösning inte alltid praktisk, särskilt när listan över nödvändiga resurser inte är känd i förväg. Till exempel, om en arbetsenhet har resurs 3 och 5 och beslutar att den behöver resurs 2, måste den släppa resurs 5, sedan 3, sedan ta resurs 2 i besittning och ta resurs 3 och 5 igen. poster i en databas skulle inte fungera effektivt om de behövde släppa alla upphöjda skivor innan de tog den nya skivan i besittning. Detta gör denna metod opraktisk.
Exemplet nedan visar en lösning där gafflar inte är explicit representerade. Filosofer kan äta om ingen av deras grannar äter. Liknar systemet där filosofer som inte kan ta upp den andra gaffeln måste lägga ner den första gaffeln innan de försöker igen.
I avsaknad av gaffelrelaterade blockeringar måste filosofer se till att starten på en måltid inte baseras på gammal information om grannarnas tillstånd. Till exempel: Om filosof B ser att A inte äter vid en given tidpunkt och sedan vänder sig om och tittar på C, kan A börja äta medan filosof B tittar på C. Genom att använda en enda mutex kan detta problem undvikas. Denna blockering är inte relaterad till gafflar, men den är relaterad till beslutet om procedurer som kan förändra filosofernas tillstånd. Detta tillhandahålls av monitorn.
Övervakningsalgoritmen implementerar ett check, take och put-schema och delar ömsesidigt uteslutande låsning. Observera att filosofer som vill äta inte kommer att ha gafflar.
Om monitorn låter filosofen som vill äta att agera, tar filosofen återigen den första gaffeln i besittning innan han tar den redan lediga andra.
I slutet av den aktuella måltiden meddelar filosofen monitorn att båda gafflarna är lediga.
Det är värt att notera att denna monitoralgoritm inte löser problemet med svält. Filosof B kan till exempel vänta på sin tur på obestämd tid om filosoferna A och B har överlappande ätperioder. För att även säkerställa att ingen filosof blir hungrig kan du hålla reda på hur många gånger en hungrig filosof inte ätit när hans grannar lägger gafflarna på bordet. Om antalet gånger överskrider en viss gräns kommer en sådan filosof att gå in i svälttillståndet, och monitoralgoritmen kommer att tvinga fram gaffelförvärvsproceduren och uppfylla villkoret för att förhindra svält hos någon av grannarna.
Filosofen, som inte kan ta gafflarna eftersom hans granne svälter, är i ett användbart läge att vänta på att hans grannes granne ska sluta äta. Detta ytterligare beroende minskar samtidighet. Att öka svälttröskelvärdet minskar denna effekt.