A Dining Philosophers Problem egy klasszikus példa, amelyet a számítástechnikában használnak a szinkronizálási problémák szemléltetésére az ilyen problémák megoldására szolgáló párhuzamos algoritmusok és technikák fejlesztése során .
A problémát Edsger Dijkstra fogalmazta meg 1965-ben tanulói vizsgagyakorlatként. Példát vettünk a szalagos meghajtó versengő hozzáférésére . A problémát hamarosan Anthony Hoare fogalmazta meg a mai formában [1] [2] [3] .
Öt hallgatag filozófus ül egy kerek asztal körül, mindegyik filozófus előtt egy tányér spagettivel. Villák hevernek az asztalon a legközelebbi filozófusok között.
Minden filozófus tud enni vagy gondolkodni. Az étkezést nem korlátozza a megmaradt spagetti mennyisége – ez végtelen készletről van szó. A filozófus azonban csak akkor tud enni, ha két jobbról és balról vett villát tart (a probléma másik megfogalmazása szerint a spagetti- és villatálak helyett rizstálak és pálcikák vannak).
Minden filozófus előveheti a legközelebbi villát (ha van ilyen), vagy leteheti, ha már a kezében van. Az egyes villák felemelése és az asztalra való visszahelyezése különálló műveletek, amelyeket egymás után kell végrehajtani.
A feladat kérdése egy olyan viselkedési modell ( párhuzamos algoritmus ) kidolgozása, amelyben egyik filozófus sem éhezik, vagyis örökké váltogatja az evést és a gondolkodást.
A probléma úgy van megfogalmazva, hogy illusztrálja a holtpont elkerülésének problémáját – a rendszer olyan állapotát , amelyben a haladás lehetetlen.
Például minden filozófusnak azt tanácsolhatjuk, hogy hajtsa végre a következő algoritmust:
Ez a probléma megoldása hibás: lehetővé teszi a rendszer számára, hogy elérje a holtpontot, ahol minden filozófus megragadta a bal oldali villát, és arra vár, hogy a jobb oldali villa felszabaduljon [4] .
Az erőforrás-éhezés probléma a holtponttól függetlenül előfordulhat, ha az egyik filozófus szinkronizálási problémák miatt nem tudja megfogni a bal és a jobb villát. Például egy olyan szabályt lehetne javasolni, amely szerint a filozófusoknak vissza kell tenniük egy villát az asztalra, miután öt percet vártak, amíg egy másik villa rendelkezésre áll, és várjon még öt percet, mielőtt újra megpróbálná birtokba venni a villát. Ez a séma kiküszöböli a blokkolás lehetőségét (hiszen a rendszer mindig átmehet egy másik állapotba), de továbbra is fennáll a rendszer „hurok” lehetősége ( eng. livelock ), amelyben a rendszer állapota megváltozik, de hasznos munkát nem végez. Például, ha mind az öt filozófus egyszerre jelenik meg az ebédlőben, és mindegyik egyszerre veszi fel a bal villát, a filozófusok öt percet várnak abban a reményben, hogy megkapják a jobb villát, majd leteszik a bal villát és várnak. még öt perccel, mielőtt megpróbálná megszerezni a villákat.
A Dining Philosophers Problem fő gondolata a kölcsönös kizárás . Ez a probléma egy általános, elvont forgatókönyv az ilyen típusú problémák magyarázatára. A filozófusok hibái illusztrálják azokat a nehézségeket, amelyek a valós programozás során felmerülnek, amikor több program kizárólagos hozzáférést igényel a megosztott erőforrásokhoz. Ezeket a kérdéseket a párhuzamos számítástechnika területén vizsgáljuk .
Dijkstra eredeti célja az étkezési filozófus problémájának megfogalmazásakor az volt, hogy bemutassa a külső számítógépes eszközök, például a szalagos meghajtók lehetséges problémáit [1] . Ennek a feladatnak a hatóköre azonban sokkal tovább bővül, és a feladatban figyelembe vett bonyolultságok gyakrabban merülnek fel, amikor több folyamat próbál hozzáférni egy frissítés alatt álló adatkészlethez.
Azok a rendszerek, amelyeknek nagyszámú párhuzamos folyamattal kell foglalkozniuk (például operációs rendszermagok ), több ezer zárolást és szinkronizálási pontot használnak. Ez megköveteli a módszerek és protokollok szigorú betartását, ha el akarjuk kerülni a holtpontokat, az éhezést és az adatsérülést.
A probléma viszonylag egyszerű megoldása egy pincér hozzáadásával érhető el az asztal közelében. A filozófusoknak meg kell várniuk a pincér engedélyét, mielőtt elvennék a villát. Mivel a pincér tudja, hány villa van jelenleg használatban, döntéseket hozhat a villák elosztásáról, és így megakadályozhatja a filozófusok holtpontját. Ha öt villából négy már használatban van, akkor a következő filozófusnak, aki villát kér, meg kell várnia a pincér engedélyét – amit addig nem kapnak meg, amíg a villát el nem engedik. Feltételezzük, hogy a filozófus először mindig a bal villát próbálja megfogni, majd a jobbat (vagy fordítva), ami leegyszerűsíti a logikát. A pincér úgy működik, mint egy szemafor , ezt a fogalmat Dijkstra vezette be 1965-ben [5] .
A megoldás működésének bemutatásához tegyük fel, hogy a filozófusok A-tól D-ig vannak jelölve az óramutató járásával megegyező irányban. Ha A és B filozófusok esznek, akkor négy villa van elfoglalva. B filozófus A és C között ül, így egyik villa sem áll rendelkezésére. Ugyanakkor D és D filozófusok hozzáférnek egy-egy használaton kívüli villához. Tegyük fel, hogy G filozófus éhes. Ha azonnal szabad villát vesz, akkor lehetségessé válik a filozófusok kölcsönös blokkolása. Ha ehelyett engedélyt kér a pincértől, megkéri, hogy várjon – és biztos lehet benne, hogy amint szabad lesz egy pár villa, legalább egy filozófus két villát is el tud venni. Így a holtpont lehetetlenné válik.
Egy másik egyszerű megoldás úgy érhető el, hogy részleges sorrendet rendelünk az erőforrásokhoz (jelen esetben villákhoz), és azt a megállapodást kötjük, hogy az erőforrásokat ebben a sorrendben kérik, és fordított sorrendben adják vissza. Ezenkívül nem szabad két rendellenes erőforrást használni, amelyet ugyanaz a munkaegység használ.
Legyen az erőforrások (villák) számozva 1-től 5-ig, és minden munkaegység (filozófus) először mindig a legalacsonyabb számú villát veszi fel, majd a rendelkezésre álló kettő közül a legmagasabb számú villát. Ezután a filozófus először a nagyobb számmal rendelkező villát teszi le, majd a kisebbet. Ebben az esetben, ha öt filozófusból négy egyszerre veszi a legalacsonyabb számozású villát, akkor a lehető legmagasabb számú villa marad az asztalon. Így az ötödik filozófus egyetlen villát sem fog tudni elvenni. Ráadásul csak egy filozófus férhet hozzá a legmagasabb számú villához, tehát két villával is ehet. Amikor befejezte a villák használatát, először a legmagasabb sorszámú villát teszi le az asztalra, majd a kisebbet, így a másik filozófus felveszi a hiányzó villát és elkezd enni.
Ezt a megoldást Dijkstra javasolta.
Míg az erőforrás-hierarchia elkerüli a holtpontokat, ez a megoldás nem mindig praktikus, különösen akkor, ha a szükséges erőforrások listája nem ismert előre. Például, ha egy munkaegység rendelkezik a 3-as és az 5-ös erőforrással, és úgy dönt, hogy szüksége van a 2-es erőforrásra, akkor fel kell szabadítania az 5-ös, majd a 3-as erőforrást, majd birtokba kell vennie a 2-es erőforrást, és újra át kell vennie a 3-as és 5-ös erőforrást. Az adatbázis rekordjai nem működnének hatékonyan, ha az új rekord birtokbavétele előtt ki kellett adniuk az összes felülírt rekordot. Emiatt ez a módszer nem praktikus.
Az alábbi példa egy olyan megoldást mutat be, ahol a villák nincsenek kifejezetten ábrázolva. A filozófusok ehetnek, ha egyik szomszédjuk sem eszik. Hasonló a rendszerhez, ahol a filozófusoknak, akik nem tudják felvenni a második villát, le kell tenniük az első villát, mielőtt újra próbálkoznának.
A villával kapcsolatos dugulások hiányában a filozófusoknak gondoskodniuk kell arról, hogy az étkezés megkezdése ne a szomszédok állapotáról szóló régi információkon alapuljon. Például: Ha B filozófus látja, hogy A nem eszik egy adott időpontban, majd megfordul, és C-re néz, akkor A elkezdhet enni, miközben B filozófus C-t nézi. Egyetlen mutex használatával ez a probléma elkerülhető. Ez a blokkolás nem a forkokhoz kapcsolódik, hanem a filozófusok állapotát megváltoztató eljárások döntéséhez. Ezt a monitor biztosítja.
A monitor algoritmusa ellenőrzi, vegyen és helyezze el a sémát, és megosztja a kölcsönösen kizáró zárolást. Megjegyzendő, hogy azoknak a filozófusoknak, akik enni akarnak, nem lesz villájuk.
Ha a monitor megengedi az enni vágyó filozófusnak, hogy cselekedjen, akkor a filozófus ismét birtokba veszi az első villát, mielőtt elveszi a már szabad másodikat.
Az aktuális étkezés végén a filozófus értesíti a monitort, hogy mindkét villa szabad.
Érdemes megjegyezni, hogy ez a monitoralgoritmus nem oldja meg az éhezés problémáját. Például B filozófus korlátlan ideig várhat a sorára, ha A és B filozófusok étkezési periódusai átfedik egymást. Annak érdekében, hogy egy filozófus se éhezzen, nyomon követheti, hogy egy éhes filozófus hányszor nem evett, amikor a szomszédai letették a villát az asztalra. Ha az alkalmak száma meghalad egy bizonyos határt, az ilyen filozófus éhezés állapotba kerül, és a monitor algoritmusa kikényszeríti a villanyerési eljárást, teljesítve azt a feltételt, hogy megakadályozza bármelyik szomszéd éhezését.
A filozófus, aki nem tudja elvenni a villákat, mert szomszédja éhezik, hasznos módban várja, hogy a szomszédja befejezze az evést. Ez a további függőség csökkenti az egyidejűséget. Az éhezési küszöbérték növelése csökkenti ezt a hatást.