streamalism.org

1. Introduksjon

Dining Philosophers-problemet er et av de klassiske problemene som brukes til beskrive synkroniseringsproblemer i et miljø med flere tråder og illustrere teknikker for å løse dem. Dijkstra formulerte først dette problemet og presenterte det angående datamaskiner som fikk tilgang til periferiutstyr for båndstasjoner.

Den nåværende formuleringen ble gitt av Tony Hoare, som også er kjent for å oppfinne quicksort-sorteringsalgoritmen. I denne artikkelen analyserer vi dette velkjente problemet og koder en populær løsning.

2. Problemet

Diagrammet ovenfor representerer problemet. Det er fem stille filosofer (P1 - P5) som sitter rundt et sirkulært bord og tilbringer livet sitt med å spise og tenke.

Det er fem gafler som de kan dele (1 - 5) og for å kunne spise, trenger en filosof å ha gafler i begge hendene. Etter å ha spist legger han dem begge ned, og så kan de bli plukket av en annen filosof som gjentar den samme syklusen.

Målet er å komme opp med en ordning / protokoll som hjelper filosofene å nå sitt mål om å spise og tenke uten å bli sultet i hjel.

3. En løsning

En første løsning ville være å få hver av filosofene til å følge følgende protokoll:

mens (sant) {// I utgangspunktet tenker på liv, univers og alt tenker (); // Ta en pause fra å tenke, sulten nå pick_up_left_fork (); pick_up_right_fork (); spise(); put_down_right_fork (); put_down_left_fork (); // Ikke sulten lenger. Tilbake til å tenke! } 

Som den ovennevnte pseudokoden beskriver, tenker hver filosof i utgangspunktet. Etter en viss tid blir filosofen sulten og ønsker å spise.

På dette punktet, han strekker seg etter gaflene på begge sider, og når han har begge to, fortsetter han å spise. Når spiseringen er ferdig, legger filosofen gaflene ned, slik at de er tilgjengelige for naboen.

4. Gjennomføring

Vi modellerer hver av våre filosofer som klasser som implementerer Kjørbar grensesnitt slik at vi kan kjøre dem som separate tråder. Hver Filosof har tilgang til to gafler på venstre og høyre side:

offentlig klasse filosof implementerer Runnable {// Gaflene på hver side av denne private filosofen Object leftFork; privat Object rightFork; public Philosopher (Object leftFork, Object rightFork) {this.leftFork = leftFork; this.rightFork = rightFork; } @ Override public void run () {// Likevel for å fylle ut denne metoden}}

Vi har også en metode som instruerer a Filosof å utføre en handling - spis, tenk eller skaff deg gafler som forberedelse til å spise:

offentlig klasse filosof implementerer Runnable {// medlemsvariabler, standard konstruktør privat ugyldig doAction (strenghandling) kaster InterruptedException {System.out.println (Thread.currentThread (). getName () + "" + action); Thread.sleep (((int) (Math.random () * 100))); } // Resten av metodene som er skrevet tidligere}

Som vist i koden ovenfor, er hver handling simulert ved å suspendere påkallingstråden i en tilfeldig periode, slik at utførelsesordren ikke håndheves av tiden alene.

La oss nå implementere kjernelogikken til a Filosof.

For å simulere anskaffelse av en gaffel, må vi låse den slik at ingen Filosof tråder anskaffer det samtidig.

For å oppnå dette bruker vi synkronisert nøkkelord for å skaffe den interne skjermen til gaffelobjektet og forhindre at andre tråder gjør det samme. En guide til synkronisert nøkkelord i Java finner du her. Vi fortsetter med å implementere løpe() metoden i Filosof klasse nå:

public class Philosopher implementerer Runnable {// medlemsvariabler, metoder definert tidligere @ Override public void run () {try {while (true) {// thinking doAction (System.nanoTime () + ": Thinking"); synkronisert (leftFork) {doAction (System.nanoTime () + ": Plukket opp venstre gaffel"); synkronisert (rightFork) {// spise doAction (System.nanoTime () + ": Plukket opp høyre gaffel - å spise"); doAction (System.nanoTime () + ": Sett ned høyre gaffel"); } // Tilbake til å tenke doAction (System.nanoTime () + ": Sett ned venstre gaffel. Tilbake til å tenke"); }}} fange (InterruptedException e) {Thread.currentThread (). interrupt (); komme tilbake; }}} 

Denne ordningen implementerer nøyaktig den som er beskrevet tidligere: a Filosof tenker en stund og bestemmer seg da for å spise.

Etter dette anskaffer han gaflene til venstre og høyre og begynner å spise. Når du er ferdig, legger han gaflene ned. Vi legger også til tidsstempler for hver handling, som vil hjelpe oss med å forstå rekkefølgen hendelser inntreffer.

For å starte hele prosessen, skriver vi en klient som lager 5 Filosofer som tråder og starter dem alle:

offentlig klasse DiningPhilosophers {public static void main (String [] args) kaster Unntak {Philosopher [] filosofer = ny Philosopher [5]; Objekt [] gafler = nytt objekt [filosofer.lengde]; for (int i = 0; i <gafler.lengde; i ++) {gafler [i] = nytt objekt (); } for (int i = 0; i <philosophers.length; i ++) {Object leftFork = gafler [i]; Objekt rightFork = gafler [(i + 1)% gafler.lengde]; filosofer [i] = ny filosof (leftFork, rightFork); Tråd t = ny tråd (filosofer [i], "Filosof" + (i + 1)); t.start (); }}}

Vi modellerer hvert av gaflene som generiske Java-objekter og lager så mange av dem som det er filosofer. Vi passerer hver Filosof venstre og høyre gafler som han prøver å låse ved hjelp av synkronisert nøkkelord.

Å kjøre denne koden resulterer i en utdata som ligner på følgende. Produksjonen din vil mest sannsynlig avvike fra den som er gitt nedenfor, hovedsakelig fordi søvn() metoden påkalles for et annet intervall:

Philosopher 1 8038014601251: Thinking Philosopher 2 8038014828862: Thinking Philosopher 3 8038015066722: Thinking Philosopher 4 8038015284511: Thinking Philosopher 5 8038015468564: Thinking Philosopher 1 8038016857288: Plukket opp venstre gaffel Philosopher 1 80380: Picked høyre 80380: Picked høyre gaffel gaffel Philosopher 4 8038063952219: Plukket opp venstre gaffel Philosopher 1 8038067505168: Sett ned høyre gaffel Philosopher 2 8038089505264: Plukket opp venstre gaffel Philosopher 1 8038089505264: Sett ned venstre gaffel. Tilbake til å tenke Philosopher 5 8038111040317: Plukket opp venstre gaffel

Alle de Filosofbegynner først å tenke, og det ser vi Filosof 1 fortsetter å ta opp venstre og høyre gaffel, deretter spiser og fortsetter å plassere dem begge ned, hvorpå `Philosopher 5` plukker den opp.

5. Problemet med løsningen: Dødlås

Selv om det ser ut til at løsningen ovenfor er riktig, er det et problem med en fastlåst situasjon.

En fastlåst tilstand er en situasjon der fremdriften til et system stoppes ettersom hver prosess venter på å skaffe seg en ressurs som en annen prosess har.

Vi kan bekrefte det samme ved å kjøre ovennevnte kode et par ganger og sjekke at koden bare henger noen ganger. Her er et eksempel på en utgang som demonstrerer problemet ovenfor:

Philosopher 1 8487540546530: Thinking Philosopher 2 8487542012975: Thinking Philosopher 3 8487543057508: Thinking Philosopher 4 8487543318428: Thinking Philosopher 5 8487544590144: Thinking Philosopher 3 8487543318428: Thinking Philosopher 5 8487544590144: Thinking Philosopher 3 8487589069046: Picked up left fork Philosopher 1 848: Philosopher 1 848 4 8487617680958: Plukket opp venstre gaffel Philosopher 2 8487631148853: Plukket opp venstre gaffel

I denne situasjonen, hver av Filosofs har skaffet seg venstre gaffel, men kan ikke skaffe seg sin høyre gaffel, fordi naboen allerede har skaffet seg den. Denne situasjonen er ofte kjent som sirkulær ventetid og er en av forholdene som resulterer i en fastlåst tilstand og forhindrer fremdriften i systemet.

6. Løsning av fastlåsen

Som vi så ovenfor, er den primære årsaken til en fastlåst sirkulær ventetilstand der hver prosess venter på en ressurs som blir holdt av en annen prosess. Derfor må vi sørge for at den sirkulære ventetilstanden er ødelagt for å unngå en fastlåst situasjon. Det er flere måter å oppnå dette på, den enkleste er følgende:

Alle filosofer strekker seg etter venstre gaffel først, bortsett fra en som først strekker seg etter sin høyre gaffel.

Vi implementerer dette i vår eksisterende kode ved å gjøre en relativt liten endring i koden:

offentlig klasse DiningPhilosophers {public static void main (String [] args) kaster Unntak {final Philosopher [] filosofer = new Philosopher [5]; Objekt [] gafler = nytt objekt [filosofer.lengde]; for (int i = 0; i <gafler.lengde; i ++) {gafler [i] = nytt objekt (); } for (int i = 0; i <philosophers.length; i ++) {Object leftFork = gafler [i]; Objekt rightFork = gafler [(i + 1)% gafler.lengde]; hvis (i == filosofer.lengde - 1) {// Den siste filosofen plukker opp høyre gaffel første filosofer [i] = ny filosof (høyreFork, venstreFork); } annet {filosofer [i] = ny filosof (leftFork, rightFork); } Tråd t = ny tråd (filosofer [i], "Filosof" + (i + 1)); t.start (); }}} 

Endringen kommer i linje 17-19 i ovennevnte kode, hvor vi introduserer tilstanden som får den siste filosofen til å nå sin høyre gaffel først, i stedet for til venstre. Dette bryter den sirkulære ventetilstanden, og vi kan avverge fastlåsen.

Følgende produksjon viser en av tilfellene der alle Filosoffår sjansen til å tenke og spise uten å forårsake en fastlåst situasjon:

Philosopher 1 88519839556188: Thinking Philosopher 2 88519840186495: Thinking Philosopher 3 88519840647695: Thinking Philosopher 4 88519840870182: Thinking Philosopher 5 88519840956443: Thinking Philosopher 3 88519864404195: Picked 5 forgaffel58 5 88519876989405: Plukket opp høyre gaffel - spiser Philosopher 2 88519935045524: Plukket opp venstre gaffel Philosopher 5 88519951109805: Sett ned høyre gaffel Philosopher 4 88519997119634: Plukket opp høyre gaffel - spising Philosopher 5 88519997113229: Legg ned venstre gaffel. Tilbake til å tenke Philosopher 5 88520011135846: Thinking Philosopher 1 88520011129013: Plukket opp venstre gaffel Philosopher 4 88520028194269: Sett ned høyre gaffel Philosopher 4 88520057160194: Sett ned venstre gaffel. Tilbake til å tenke Philosopher 3 88520067162257: Plukket opp høyre gaffel - spise Philosopher 4 88520067158414: Thinking Philosopher 3 88520160247801: Sett ned høyre gaffel Philosopher 4 88520249049308: Picked up left fork Philosopher 3 88520249119769: Legg ned venstre gaffel. Tilbake til å tenke 

Det kan verifiseres ved å kjøre koden flere ganger, at systemet er fritt for den fastlåste situasjonen som skjedde før.

7. Konklusjon

I denne artikkelen utforsket vi det berømte Dining Philosophers problemet og begrepene sirkulær venting og fastlåst. Vi kodet en enkel løsning som forårsaket en fastlåst situasjon og gjorde en enkel endring for å bryte den sirkulære ventetiden og unngå en fastlåst situasjon. Dette er bare en start, og mer sofistikerte løsninger finnes.

Koden for denne artikkelen finner du på GitHub.