The Dining Philosophers Problem er et klassisk eksempel, der bruges i datalogi til at illustrere synkroniseringsproblemer i udviklingen af parallelle algoritmer og teknikker til løsning af disse problemer.
Problemstillingen blev formuleret i 1965 af Edsger Dijkstra som en eksamensøvelse for studerende. Et eksempel blev taget på konkurrerende adgang til et båndstation . Snart blev problemet formuleret af Anthony Hoare i den form, som det er kendt i dag [1] [2] [3] .
Fem tavse filosoffer sidder omkring et rundt bord, med en tallerken spaghetti foran hver filosof. Gafler ligger på bordet mellem hvert par af nærmeste filosoffer.
Enhver filosof kan enten spise eller tænke. At spise er ikke begrænset af mængden af tilbageværende spaghetti - en uendelig forsyning er underforstået. Filosoffen kan dog kun spise, når han holder to gafler taget fra højre og venstre (en alternativ formulering af problemet indebærer skåle med ris og spisepinde i stedet for skåle med spaghetti og gafler).
Hver filosof kan tage den nærmeste gaffel (hvis en er tilgængelig) eller lægge den fra sig, hvis han allerede holder en. At tage hver gaffel op og returnere den til bordet er separate handlinger, der skal udføres efter hinanden.
Spørgsmålet om opgaven er at udvikle en adfærdsmodel ( parallelalgoritme ) , hvor ingen af filosofferne vil sulte, det vil sige, at han for altid vil veksle mellem at spise og tænke.
Problemstillingen er formuleret på en sådan måde, at den illustrerer problemet med at undgå dødvande - en tilstand af systemet, hvor fremskridt er umuligt.
For eksempel kunne man råde enhver filosof til at udføre følgende algoritme:
Denne løsning på problemet er forkert: den tillader systemet at nå en dødvandetilstand, hvor hver filosof har taget gaffelen til venstre og venter på, at gaflen til højre bliver fri [4] .
Ressourcesultproblemet kan opstå uanset dødvandet , hvis en af filosofferne ikke kan få fat i venstre og højre gafler på grund af synkroniseringsproblemer. For eksempel kunne der foreslås en regel om, at filosoffer skal lægge en gaffel tilbage på bordet efter at have ventet fem minutter på, at en anden gaffel er tilgængelig, og vente yderligere fem minutter, før de igen forsøger at tage gaflerne i besiddelse. Denne ordning eliminerer muligheden for blokering (da systemet altid kan gå til en anden tilstand), men der er stadig mulighed for en "loop" af systemet ( eng. livelock ), hvor systemets tilstand ændres, men det udfører ikke noget nyttigt arbejde. For eksempel, hvis alle fem filosoffer dukker op i spisestuen på samme tid, og hver enkelt tager den venstre gaffel op på samme tid, vil filosofferne vente fem minutter i håb om at få den rigtige gaffel, derefter lægge den venstre gaffel og vente yderligere fem minutter, før du prøver at få gaflerne igen.
Gensidig udelukkelse er hovedideen i Dining Philosophers Problem . Dette problem er et generelt, abstrakt scenarie til at forklare denne type problemer. Filosoffers fejl illustrerer de vanskeligheder, der opstår i ægte programmering, når flere programmer kræver eksklusiv adgang til delte ressourcer. Disse spørgsmål studeres inden for parallel computing .
Dijkstras oprindelige mål med at formulere Dining Philosophers Problem var at demonstrere mulige problemer med eksterne computerenheder såsom båndstationer [1] . Omfanget af denne opgave strækker sig dog meget længere, og de kompleksiteter, der tages i betragtning i opgaven, opstår oftere, når flere processer forsøger at få adgang til et datasæt, der bliver opdateret.
Systemer, der skal håndtere et stort antal samtidige processer (såsom operativsystemkerner ) bruger tusindvis af låse og synkroniseringspunkter. Dette kræver streng overholdelse af metoder og protokoller, hvis dødvande, sult og datakorruption skal undgås.
En forholdsvis enkel løsning på problemet opnås ved at tilføje en tjener nær bordet. Filosoffer skal vente på tjenerens tilladelse, før de tager gaflen. Fordi tjeneren ved, hvor mange gafler der er i brug i øjeblikket, kan han træffe beslutninger om fordelingen af gaflerne og dermed forhindre filosoffer i at gå i lås. Hvis fire ud af fem gafler allerede er i brug, så skal den næste filosof, der anmoder om en gaffel, vente på tjenerens tilladelse - som først modtages, når gaflen slippes. Det antages, at filosoffen altid forsøger at tage den venstre gaffel først, og derefter den højre (eller omvendt), hvilket forenkler logikken. Tjeneren fungerer som en semafor , et koncept introduceret af Dijkstra i 1965 [5] .
For at vise, hvordan denne løsning virker, lad os antage, at filosofferne er mærket A til D i urets retning. Hvis filosoff A og B spiser, så er fire gafler optaget. Filosof B sidder mellem A og C, så ingen af gaflerne er tilgængelige for ham. Samtidig har filosofferne D og D adgang til én ubrugt gaffel imellem sig. Lad os antage, at filosof G er sulten. Hvis han straks tager en fri gaffel, bliver gensidig blokering af filosoffer mulig. Hvis han i stedet spørger om lov hos tjeneren, beder han ham vente - og du kan være sikker på, at så snart et par gafler er fri, så vil mindst én filosof kunne tage to gafler. Dermed bliver dødvande umuligt.
En anden simpel løsning opnås ved at tildele en delordre til ressourcerne (gafler i dette tilfælde) og gøre konventionen om, at ressourcerne anmodes i den rækkefølge og returneres i omvendt rækkefølge. Der bør heller ikke være to ressourcer ude af drift, der bruges af den samme arbejdsenhed.
Lad ressourcerne (gaflerne) være nummereret fra 1 til 5, og hver arbejdsenhed (filosof) tager altid den lavest nummererede gaffel først, og derefter den højest nummererede gaffel af de to tilgængelige. Dernæst lægger filosoffen først gaflen med det højere tal, derefter den med det mindste. I dette tilfælde, hvis fire ud af fem filosoffer tager den lavest nummererede gaffel på samme tid, vil den højest mulige nummererede gaffel forblive på bordet. Således vil den femte filosof ikke være i stand til at tage en eneste gaffel. Desuden vil kun én filosof have adgang til den højeste nummererede gaffel, så han kan spise med to gafler. Når han er færdig med at bruge gaflerne, vil han lægge den højest nummererede gaffel på bordet først, derefter den mindste, og dermed tillade den anden filosof at samle den manglende gaffel op og begynde at spise.
Denne løsning blev foreslået af Dijkstra.
Selvom ressourcehierarkiet undgår dødvande, er denne løsning ikke altid praktisk, især når listen over nødvendige ressourcer ikke er kendt på forhånd. For eksempel, hvis en arbejdsenhed har ressource 3 og 5 og beslutter, at den har brug for ressource 2, så skal den frigive ressource 5, derefter 3, derefter tage ressource 2 i besiddelse og tage ressource 3 og 5 igen. poster i en database ville ikke fungere effektivt, hvis de skulle udgive alle opskrevne plader, før de fik den nye plade i besiddelse. Dette gør denne metode upraktisk.
Eksemplet nedenfor viser en løsning, hvor gafler ikke er eksplicit repræsenteret. Filosoffer kan spise, hvis ingen af deres naboer spiser. Svarende til systemet, hvor filosoffer, der ikke kan tage den anden gaffel, skal lægge den første gaffel, før de prøver igen.
I mangel af gaffelrelaterede blokeringer skal filosoffer sikre, at starten på et måltid ikke er baseret på gamle oplysninger om naboernes tilstand. For eksempel: Hvis filosof B ser, at A ikke spiser på et givet tidspunkt og derefter vender sig om og ser på C, kunne A begynde at spise, mens filosof B kigger på C. Ved at bruge en enkelt mutex kan dette problem undgås. Denne blokering er ikke relateret til gafler, men den er relateret til beslutningen om procedurer, der kan ændre filosoffernes tilstand. Dette leveres af monitoren.
Overvågningsalgoritmen implementerer et check, take og put-skema og deler gensidigt udelukkende låsning. Bemærk, at filosoffer, der ønsker at spise, ikke vil have gafler.
Hvis monitoren tillader filosoffen, der vil spise, at handle, så tager filosoffen igen den første gaffel i besiddelse, inden han tager den allerede frie anden.
Ved afslutningen af det aktuelle måltid meddeler filosoffen monitoren, at begge gafler er frie.
Det er værd at bemærke, at denne monitoralgoritme ikke løser problemet med sult. For eksempel kan filosof B vente på sin tur på ubestemt tid, hvis filosoff A og B har overlappende spiseperioder. For også at sikre, at ingen filosof sulter, kan du holde styr på, hvor mange gange en sulten filosof ikke har spist, når hans naboer lægger gaflerne på bordet. Hvis antallet af gange overstiger en vis grænse, vil en sådan filosof gå ind i sultetilstanden, og monitoralgoritmen vil tvinge gaffelanskaffelsesproceduren og opfylde betingelsen om at forhindre sult hos nogen af naboerne.
Filosoffen, der ikke er i stand til at tage gaflerne, fordi hans nabo sulter, er i en nyttig måde at vente på, at hans nabos nabo er færdig med at spise. Denne yderligere afhængighed reducerer samtidighed. Forøgelse af sulttærskelværdien reducerer denne effekt.