streamalism.org

1. Introduktion

Dining Philosophers-problemet er et af de klassiske problemer, der bruges til beskrive synkroniseringsproblemer i et multitrådet miljø og illustrere teknikker til løsning af dem. Dijkstra formulerede først dette problem og præsenterede det angående computere, der fik adgang til periferiudstyr til bånddrev.

Den nuværende formulering blev givet af Tony Hoare, som også er kendt for at opfinde quicksort-sorteringsalgoritmen. I denne artikel analyserer vi dette velkendte problem og koder en populær løsning.

2. Problemet

Diagrammet ovenfor repræsenterer problemet. Der sidder fem tavse filosoffer (P1 - P5) omkring et cirkulært bord og bruger deres liv på at spise og tænke.

Der er fem gafler, som de kan dele (1 - 5), og for at være i stand til at spise, skal en filosof have gafler i begge hænder. Efter at have spist sætter han dem begge ned, og så kan de vælges af en anden filosof, der gentager den samme cyklus.

Målet er at komme med en ordning / protokol, der hjælper filosoferne med at nå deres mål om at spise og tænke uden at blive sultet ihjel.

3. En løsning

En indledende løsning ville være at få hver af filosofferne til at følge følgende protokol:

mens (sandt) {// Oprindeligt tænker på liv, univers og alt tænker (); // Tag en pause fra at tænke, sulten nu pick_up_left_fork (); pick_up_right_fork (); spise(); put_down_right_fork (); put_down_left_fork (); // Ikke længere sulten. Tilbage til at tænke! } 

Som den ovennævnte pseudokode beskriver, tænker hver filosof oprindeligt. Efter en vis tid bliver filosofen sulten og ønsker at spise.

På dette tidspunkt, han rækker ud efter gaflerne på begge sider, og når han først har begge, fortsætter han med at spise. Når spisningen er færdig, lægger filosofen gaflerne ned, så de er tilgængelige for sin nabo.

4. Implementering

Vi modellerer hver af vores filosoffer som klasser, der implementerer Kan køres interface, så vi kan køre dem som separate tråde. Hver Filosof har adgang til to gafler på venstre og højre side:

offentlig klasse filosof implementerer Runnable {// gaflerne på hver side af denne filosof private objekt leftFork; privat Objekt rightFork; public Philosopher (Object leftFork, Object rightFork) {this.leftFork = leftFork; this.rightFork = rightFork; } @Override public void run () {// Alligevel at udfylde denne metode}}

Vi har også en metode, der instruerer en Filosof at udføre en handling - spis, tænk eller erhverv gafler som forberedelse til at spise:

public class Philosopher implementerer Runnable {// medlemsvariabler, standard konstruktør privat ugyldig doAction (strenghandling) kaster InterruptedException {System.out.println (Thread.currentThread (). getName () + "" + handling); Thread.sleep (((int) (Math.random () * 100))); } // Resten af ​​de metoder, der er skrevet tidligere}

Som vist i koden ovenfor simuleres hver handling ved at suspendere den påkaldende tråd i en tilfældig periode, så eksekveringsordren ikke håndhæves af tiden alene.

Lad os nu implementere kernelogikken i en Filosof.

For at simulere erhvervelse af en gaffel er vi nødt til at låse den, så ingen to Filosof tråde erhverver det på samme tid.

For at opnå dette bruger vi synkroniseret nøgleord for at hente den interne skærm af gaffelobjektet og forhindre andre tråde i at gøre det samme. En guide til synkroniseret nøgleord i Java kan findes her. Vi fortsætter med at implementere løb() metode i Filosof klasse nu:

public class Philosopher implementerer Runnable {// medlemsvariabler, metoder defineret tidligere @ Override public void run () {try {while (true) {// thinking doAction (System.nanoTime () + ": Thinking"); synkroniseret (leftFork) {doAction (System.nanoTime () + ": Picked left fork"); synkroniseret (rightFork) {// spise doAction (System.nanoTime () + ": Picked right fork - eating"); doAction (System.nanoTime () + ": Sæt højre gaffel ned"); } // Tilbage til tænkning doAction (System.nanoTime () + ": Sæt venstre fork. Tilbage til tænkning"); }}} fange (InterruptedException e) {Thread.currentThread (). interrupt (); Vend tilbage; }}} 

Denne ordning implementerer nøjagtigt den, der er beskrevet tidligere: a Filosof tænker et stykke tid og beslutter sig derefter for at spise.

Efter dette erhverver han gaflerne til venstre og højre og begynder at spise. Når du er færdig, lægger han gaflerne ned. Vi tilføjer også tidsstempler til hver handling, som vil hjælpe os med at forstå rækkefølgen, i hvilken begivenheder opstår.

For at starte hele processen, skriver vi en klient, der opretter 5 Filosoffer som tråde og starter dem alle:

offentlig klasse DiningPhilosophers {public static void main (String [] args) throw Exception {Philosopher [] philosophers = new Philosopher [5]; Objekt [] gafler = nyt objekt [filosofer.længde]; for (int i = 0; i <gafler.længde; i ++) {gafler [i] = nyt objekt (); } for (int i = 0; i <filosofer.længde; i ++) {Objekt leftFork = gafler [i]; Objekt rightFork = gafler [(i + 1)% gafler.længde]; filosoffer [i] = ny filosof (leftFork, rightFork); Tråd t = ny tråd (filosoffer [i], "Filosof" + (i + 1)); t.start (); }}}

Vi modellerer hvert af gaflerne som generiske Java-objekter og fremstiller så mange af dem, som der er filosoffer. Vi passerer hver Filosof hans venstre og højre gafler, som han forsøger at låse ved hjælp af synkroniseret nøgleord.

Kørsel af denne kode resulterer i en output svarende til følgende. Din produktion vil sandsynligvis afvige fra den nedenstående, hovedsagelig fordi søvn() metode påkaldes for et andet interval:

Philosopher 1 8038014601251: Thinking Philosopher 2 8038014828862: Thinking Philosopher 3 8038015066722: Thinking Philosopher 4 8038015284511: Thinking Philosopher 5 8038015468564: Thinking Philosopher 1 8038016857288: Picked up left fork Philosopher 1 80380: Picked left 80 gaffel gaffel Philosopher 4 8038063952219: Picked up left fork Philosopher 1 8038067505168: Læg ned højre gaffel Philosopher 2 8038089505264: Picked up left fork Philosopher 1 8038089505264: Sæt venstre gaffel. Tilbage til tænkning Philosopher 5 8038111040317: Picked left fork

Alle Filosofs begynder med at tænke, og det ser vi Filosof 1 fortsætter med at samle venstre og højre gaffel op, spiser derefter og fortsætter med at placere dem begge ned, hvorefter `Philosopher 5` samler den op.

5. Problemet med løsningen: Deadlock

Selvom det ser ud til, at ovenstående løsning er korrekt, er der et problem med en dødvande, der opstår.

En blokering er en situation, hvor et systems fremskridt standses, da hver proces venter på at erhverve en ressource, som en anden proces har.

Vi kan bekræfte det samme ved at køre ovenstående kode et par gange og kontrollere, at koden nogle gange bare hænger. Her er et eksempel på output, der demonstrerer ovenstående problem:

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

I denne situation, hver af de Filosofs har erhvervet sin venstre gaffel, men kan ikke erhverve sin højre gaffel, fordi hans nabo allerede har erhvervet den. Denne situation er almindeligt kendt som cirkulær ventetid og er en af ​​de betingelser, der resulterer i en blokering og forhindrer systemets fremskridt.

6. Løsning af deadlock

Som vi så ovenfor, er den primære årsag til en blokering den cirkulære ventetilstand, hvor hver proces venter på en ressource, der er indeholdt i en anden proces. Derfor er vi nødt til at sikre, at den cirkulære ventetilstand er brudt for at undgå en dødvande-situation. Der er flere måder at opnå dette på, hvor den enkleste er følgende:

Alle filosoffer strækker sig først efter deres venstre gaffel, undtagen en der først strækker sig efter sin højre gaffel.

Vi implementerer dette i vores eksisterende kode ved at foretage en relativt mindre ændring i kode:

offentlig klasse DiningPhilosophers {public static void main (String [] args) throw Exception {final Philosopher [] filosofer = new Philosopher [5]; Objekt [] gafler = nyt objekt [filosofer.længde]; for (int i = 0; i <gafler.længde; i ++) {gafler [i] = nyt objekt (); } for (int i = 0; i <filosofer.længde; i ++) {Objekt leftFork = gafler [i]; Objekt rightFork = gafler [(i + 1)% gafler.længde]; hvis (i == filosofer.længde - 1) {// Den sidste filosof opfanger den rigtige fork første filosoffer [i] = ny filosof (højreFork, venstreFork); } andet {filosoffer [i] = ny filosof (leftFork, rightFork); } Tråd t = ny tråd (filosoffer [i], "Filosof" + (i + 1)); t.start (); }}} 

Ændringen kommer i linje 17-19 i ovenstående kode, hvor vi introducerer den betingelse, der får den sidste filosof til at række ud efter sin højre gaffel først i stedet for til venstre. Dette bryder den cirkulære ventetilstand, og vi kan afværge dødvandet.

Efterfølgende output viser et af de tilfælde, hvor alle Filosofs får deres chance for at tænke og spise uden at skabe dødvande:

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 gaffel58 5 88519876989405: Picked up right fork - eating Philosopher 2 88519935045524: Picked up left fork Philosopher 5 88519951109805: Put down right fork Philosopher 4 88519997119634: Picked up right fork - eating Philosopher 5 88519997113229: Sæt venstre gaffel. Tilbage til tænkning Philosopher 5 88520011135846: Thinking Philosopher 1 88520011129013: Picked up left fork Philosopher 4 88520028194269: Sæt højre fork ned Philosopher 4 88520057160194: Sæt venstre fork. Tilbage til tænkning Philosopher 3 88520067162257: Picked up right fork - eating Philosopher 4 88520067158414: Thinking Philosopher 3 88520160247801: Put down right fork Philosopher 4 88520249049308: Picked up left fork Philosopher 3 88520249119769: Sæt venstre gaffel. Tilbage til tænkning 

Det kan verificeres ved at køre koden flere gange, at systemet er fri for den blokeringssituation, der opstod før.

7. Konklusion

I denne artikel undersøgte vi det berømte Dining Philosophers problem og begreberne cirkulær ventetid og blokering. Vi kodede en simpel løsning, der forårsagede en blokering og foretog en simpel ændring for at bryde den cirkulære ventetid og undgå en blokering. Dette er bare en start, og der findes mere sofistikerede løsninger.

Koden til denne artikel kan findes på GitHub.