streamalism.org

1. Bemutatkozás

Az étkező filozófusok problémája az egyik klasszikus probléma írja le a szinkronizálási kérdéseket egy több szálat tartalmazó környezetben, és szemléltesse a megoldási technikákat. Dijkstra először megfogalmazta ezt a problémát, és bemutatta a szalagos meghajtó perifériáihoz hozzáférő számítógépekkel kapcsolatban.

A jelen megfogalmazást Tony Hoare adta, aki szintén ismert a quicksort rendezési algoritmus feltalálásáról. Ebben a cikkben elemezzük ezt a jól ismert problémát, és egy népszerű megoldást kódolunk.

2. A probléma

A fenti ábra a problémát ábrázolja. Öt csendes filozófus (P1 - P5) ül egy kör alakú asztal körül, életüket evéssel és gondolkodással töltik.

Öt villa van, hogy megosszák őket (1 - 5), és hogy enni tudjanak, a filozófusnak mindkét kezében villával kell rendelkeznie. Evés után leteszi mindkettőjüket, majd egy másik filozófus választhatja őket, aki megismétli ugyanazt a ciklust.

A cél egy olyan rendszer / protokoll kidolgozása, amely segíti a filozófusokat az evés és gondolkodás céljának elérésében anélkül, hogy éhen halnának.

3. Megoldás

Kezdeti megoldás az lenne, ha a filozófusok mindegyikét követnék a következő protokoll szerint:

míg (igaz) {// Kezdetben az életről, az univerzumról és mindenről gondolkodva gondolkodik (); // Tartson egy kis szünetet a gondolkodásban, éhes most pick_up_left_fork (); pick_up_right_fork (); eszik(); put_down_right_fork (); put_down_left_fork (); // Már nem éhes. Vissza a gondolkodáshoz! } 

Amint a fenti álkód leírja, minden filozófus kezdetben gondolkodik. Bizonyos idő elteltével a filozófus megéhezik és enni akar.

Ezen a ponton, mindkét oldalán a villák után nyúl, és miután megkapta mindkettőjüket, enni kezd. Miután az evés megtörtént, a filozófus leteszi a villákat, hogy azok elérhetőek legyenek a szomszédja számára.

4. Végrehajtás

Minden filozófusunkat mint osztályt modellezzük, amely megvalósítja a Futható interfészt, hogy külön szálakként futtathassuk őket. Minden egyes Filozófus két villához van hozzáférése a bal és a jobb oldalán:

nyilvános osztály A filozófus Runnable-t valósít meg // // A filozófus magánobjektum mindkét oldalán található villák leftFork; private Object rightFork; public Filozófus (Object leftFork, Object rightFork) {this.leftFork = leftFork; this.rightFork = rightFork; } @Orride public void run () {// Ennek ellenére feltölti ezt a módszert}}

Van olyan módszerünk is, amely utasítja a Filozófus cselekedet végrehajtása - enni, gondolkodni vagy villát szerezni az étkezés előkészítéséhez:

public class A filozófus Runnable {// tagváltozókat valósít meg, a standard konstruktor private void doAction (String action) dobja az InterruptedException {System.out.println (Thread.currentThread (). getName () + "" + action); Szál.alszik (((int) (Math.random () * 100))); } // A korábban leírt módszerek többi része}

Amint az a fenti kódban látható, minden műveletet a hívó szál véletlenszerű ideig tartó felfüggesztésével szimulálnak, így a végrehajtási parancsot csak idő nem hajtja végre.

Most valósítsuk meg a Filozófus.

A villa megszerzésének szimulációjához le kell zárnunk, hogy ne legyen kettő Filozófus szálak egyszerre megszerzik.

Ennek eléréséhez a szinkronizált kulcsszó a villa objektum belső monitorjának megszerzéséhez és más szálak megakadályozásához. Útmutató a szinkronizált kulcsszó a Java-ban itt található. Folytatjuk a fuss() módszer a Filozófus osztály most:

public class A filozófus futtatható {// tagváltozókat, korábban definiált módszereket valósít meg @Override public void run () {try {while (true) {// thinking doAction (System.nanoTime () + ": Thinking"); szinkronizált (leftFork) {doAction (System.nanoTime () + ": Felvette a bal villát"); szinkronizált (rightFork) {// étkezési doAction (System.nanoTime () + ": Felvett jobb villa - evés"); doAction (System.nanoTime () + ": Tegye le a jobb villát"); } // Vissza a gondolkodáshoz doAction (System.nanoTime () + ": Tegye le a bal villát. Vissza a gondolkodáshoz"); }}} catch (InterruptedException e) {Szál.currentThread (). megszakítás (); Visszatérés; }}} 

Ez a séma pontosan végrehajtja a korábban leírtakat: a Filozófus gondolkodik egy darabig, majd úgy dönt, hogy enni fog.

Ezek után megszerzi a bal és jobb oldali villákat, és enni kezd. Ha kész, leteszi a villákat. Az egyes műveletekhez időbélyegeket is adunk, amelyek segítenek megérteni az események sorrendjét.

A teljes folyamat elindításához írunk egy klienst, amely létrehozza az 5-öt Filozófusok szálakként, és mindegyiket elindítja:

public class DiningPhilosophers {public static void main (String [] args) dob Kivételt {Filozófus [] filozófusok = új filozófus [5]; Object [] villák = new Object [filozófusok.hossz]; for (int i = 0; i <villák.hossz; i ++) {villák [i] = új objektum (); } for (int i = 0; i <filozófusok.hossz; i ++) {Object leftFork = villák [i]; Object rightFork = villák [(i + 1)% villa.hossz]; filozófusok [i] = új filozófus (leftFork, rightFork); Szál t = új Szál (filozófusok [i], "Filozófus" + (i + 1)); t.start (); }}}

Az egyes villákat általános Java objektumokként modellezzük, és annyit készítünk belőlük, ahány filozófus van. Mindegyiket elhaladjuk Filozófus bal és jobb villáját, amelyeket megpróbál lezárni a szinkronizált kulcsszó.

A kód futtatása az alábbihoz hasonló kimenetet eredményez. A kimenet nagy valószínűséggel eltér az alábbiakban megadottaktól, főleg azért, mert a alvás() metódust más időközönként hívják meg:

Filozófus 1 8038014601251: Gondolkodó filozófus 2 8038014828862: Gondolkodó filozófus 3 8038015066722: Gondolkodó filozófus 4 8038015284511: Gondolkodó filozófus 5 8038015468564: Gondolkodó filozófus 1 8038016857288: Felvette bal villát evő filozófus: Felkapott filozófus balra: Felveszett balra filozófus 3: Balra: Elkapta: Filozófus 3: Balra: Elkapta villa filozófus 4 8038063952219: felvette bal villát filozófus 1 8038067505168: tegye le a jobb villát filozófus 2 8038089505264: felvette bal villát filozófus 1 8038089505264: tegye le a bal villát. Vissza a gondolkodóhoz Filozófus 5 8038111040317: Felvette a bal villát

Mind a Filozófuss kezdetben gondolkodni kezd, és ezt látjuk Filozófus 1 átveszi a bal és a jobb villát, majd eszik, és leteszi mindkettőjüket, majd a `Philosopher 5` felveszi.

5. A megoldás problémája: holtpont

Bár úgy tűnik, hogy a fenti megoldás helytálló, a holtpont problémája merül fel.

A holtpont egy olyan helyzet, amikor a rendszer előrehaladása leáll, mivel minden folyamat arra vár, hogy valamilyen más folyamatban lévő erőforrást megszerezzen.

Megerősíthetjük ugyanezt azzal, hogy néhányszor futtatjuk a fenti kódot, és ellenőrizzük, hogy a kód néha csak lefagy-e. Íme egy példa kimenet, amely bemutatja a fenti problémát:

Filozófus 1 8487540546530: Gondolkodó filozófus 2 8487542012975: Gondolkodó filozófus 3 8487543057508: Gondolkodó filozófus 4 8487543318428: Gondolkodó filozófus 5 8487544590144: Gondolkodó filozófus 3 848758456016: Felvett filozófus 8: 8 4 8487617680958: Bal villát felvette Filozófus 2 8487631148853: Bal villát felvett

Ebben a helyzetben mindegyik Filozófuss megszerezte a bal villáját, de nem tudja megszerezni a jobb villáját, mert a szomszédja már megszerezte. Ez a helyzet közismert nevén körkörös várakozás és egyike azoknak a feltételeknek, amelyek holtpontot eredményeznek és megakadályozzák a rendszer előrehaladását.

6. A holtpont megoldása

Amint fentebb láttuk, a holtpont elsődleges oka a körkörös várakozási feltétel, amikor minden folyamat egy más folyamat által tartott erőforrásra vár. Ezért a holtpont elkerülése érdekében meg kell győződnünk arról, hogy a körkörös várakozási feltétel meghibásodott. Ennek többféle módja van, a legegyszerűbb a következő:

Minden filozófus először a bal villájához nyúl, kivéve azt, aki először a jobb villájához nyúl.

Ezt a meglévő kódunkban viszonylag kicsi változtatással valósítjuk meg:

public class DiningPhilosophers {public static void main (String [] args) dob Kivételt {final Philosopher [] filozófusok = new Philosopher [5]; Object [] villák = new Object [filozófusok.hossz]; for (int i = 0; i <villák.hossz; i ++) {villák [i] = új objektum (); } for (int i = 0; i <filozófusok.hossz; i ++) {Object leftFork = villák [i]; Object rightFork = villa [(i + 1)% villa.hossz]; if (i == filozófusok.hossz - 1) {// Az utolsó filozófus felveszi a jobb villás első filozófusokat [i] = új filozófus (rightFork, leftFork); } else {filozófusok [i] = új filozófus (leftFork, rightFork); } Téma t = új Téma (filozófusok [i], "Filozófus" + (i + 1)); t.start (); }}} 

A változás a fenti kód 17–19. Sorában következik be, ahol bemutatjuk azt a feltételt, amely az utolsó filozófust a bal villája helyett a jobb villájához nyúlja. Ez megszakítja a körkörös várakozási feltételt, és elháríthatjuk a holtpontot.

A következő kimenet az egyik olyan esetet mutatja, amikor az összes Filozófuslehetőséget kapnak gondolkodni és enni, anélkül, hogy holtpontot okoznának:

Filozófus 1 88519839556188: Gondolkodó filozófus 2 88519840186495: Gondolkodó filozófus 3 88519840647695: Gondolkodó filozófus 4 88519840870182: Gondolkodó filozófus 5 88519840956443: Gondolkodó filozófus 3 885198644054 5 88519876989405: Felvette a jobb villát - evő filozófus 2 88519935045524: Felvette a bal villát filozófus 5 88519951109805: Tegye le a jobb villát filozófus 4 88519997119634: Felvette a jobb villát - a filozófus elfogyasztása 5 88519997119632: Vissza a gondolkodó filozófushoz 5 88520011135846: Gondolkodó filozófus 1 88520011129013: Bal villát felvette Filozófus 4 88520028194269: Tegye le a jobb villát Filozófus 4 88520057160194: Tegye le a bal villát. Vissza a gondolkodó filozófushoz 3 88520067162257: Felvette a jobb villát - eszik filozófust 4 88520067158414: Gondolkodó filozófus 3 88520160247801: Tegye le a jobb villát filozófus 4 88520249049308: Felvette a bal villát Filozófus 3 88520249119769: Balra tette le a villát. Vissza a gondolkodáshoz 

A kód többszöri futtatásával ellenőrizhető, hogy a rendszer mentes-e a korábban bekövetkezett holtpontról.

7. Következtetés

Ebben a cikkben feltártuk a híres Dining Philosophers problémát és a körkörös várakozás és a holtpont fogalma. Kódoltunk egy egyszerű megoldást, amely holtpontot okozott, és egyszerű változtatást hajtottunk végre a körkörös várakozás megtörése és a holtpont elkerülése érdekében. Ez csak egy kezdet, és léteznek kifinomultabb megoldások is.

A cikk kódja a GitHub oldalon található.