streamalism.org

1. Inleiding

Het probleem van Dining Philosophers is een van de klassieke problemen die vroeger beschrijf synchronisatieproblemen in een omgeving met meerdere threads en illustreer technieken om deze op te lossen. Dijkstra formuleerde dit probleem eerst en presenteerde het met betrekking tot computers die toegang hebben tot randapparatuur voor tapedrives.

De huidige formulering werd gegeven door Tony Hoare, die ook bekend staat om het uitvinden van het quicksort-sorteeralgoritme. In dit artikel analyseren we dit bekende probleem en coderen we een populaire oplossing.

2. Het probleem

Het bovenstaande diagram geeft het probleem weer. Er zijn vijf stille filosofen (P1 - P5) die rond een ronde tafel zitten en hun leven doorbrengen met eten en denken.

Er zijn vijf vorken die ze kunnen delen (1 - 5) en om te kunnen eten, moet een filosoof de vorken in beide handen hebben. Na het eten legt hij ze allebei neer en dan kunnen ze worden geplukt door een andere filosoof die dezelfde cyclus herhaalt.

Het doel is om een ​​schema / protocol te bedenken dat de filosofen helpt hun doel van eten en denken te bereiken zonder uitgehongerd te worden.

3. Een oplossing

Een eerste oplossing zou zijn om elk van de filosofen het volgende protocol te laten volgen:

while (true) {// Aanvankelijk denkend aan het leven, het universum en alles think (); // Neem een ​​pauze van het denken, honger nu pick_up_left_fork (); pick_up_right_fork (); eten(); put_down_right_fork (); put_down_left_fork (); // Geen honger meer. Terug aan het denken! } 

Zoals de bovenstaande pseudocode beschrijft, denkt elke filosoof in eerste instantie. Na een bepaalde tijd krijgt de filosoof honger en wil hij eten.

Op dit punt, hij reikt naar de vorken aan zijn weerszijden en zodra hij ze allebei heeft, gaat hij verder met eten. Als het eten klaar is, legt de filosoof de vorken neer, zodat ze beschikbaar zijn voor zijn buurman.

4. Implementatie

We modelleren al onze filosofen als klassen die de Runnable interface zodat we ze als afzonderlijke threads kunnen uitvoeren. Elk Filosoof heeft toegang tot twee vorken aan zijn linker- en rechterkant:

public class Philosopher implementeert Runnable {// De vorken aan weerszijden van dit Philosopher private Object leftFork; privaat object rightFork; openbare Filosoof (Object leftFork, Object rightFork) {this.leftFork = leftFork; this.rightFork = rightFork; } @Override public void run () {// Deze methode moet nog worden ingevuld}}

We hebben ook een methode die een Filosoof om een ​​actie uit te voeren - eet, denk of koop vorken ter voorbereiding op het eten:

public class Philosopher implementeert Runnable {// Member variabelen, standaard constructor private void doAction (String action) gooit InterruptedException {System.out.println (Thread.currentThread (). getName () + "" + action); Thread.sleep (((int) (Math.random () * 100))); } // Rest van de eerder geschreven methoden}

Zoals in de bovenstaande code wordt getoond, wordt elke actie gesimuleerd door de aanroepende thread voor een willekeurige tijd op te schorten, zodat de uitvoeringsopdracht niet alleen door de tijd wordt afgedwongen.

Laten we nu de kernlogica van een Filosoof.

Om het verkrijgen van een vork te simuleren, moeten we deze vergrendelen zodat er geen twee Filosoof threads verkrijgen het tegelijkertijd.

Om dit te bereiken gebruiken we de gesynchroniseerd trefwoord om de interne monitor van het vorkobject te verkrijgen en te voorkomen dat andere threads hetzelfde doen. Een gids voor de gesynchroniseerd trefwoord in Java is hier te vinden. We gaan verder met het implementeren van het rennen() methode in de Filosoof les nu:

public class Philosopher implementeert Runnable {// Member variabelen, eerder gedefinieerde methoden @Override public void run () {try {while (true) {// thinking doAction (System.nanoTime () + ": Thinking"); gesynchroniseerd (leftFork) {doAction (System.nanoTime () + ": Picked up left fork"); synchronized (rightFork) {// eating doAction (System.nanoTime () + ": Picked right fork - eating"); doAction (System.nanoTime () + ": rechter vork neerzetten"); } // Terug naar denken doAction (System.nanoTime () + ": linker vork neerzetten. Terug naar denken"); }}} catch (InterruptedException e) {Thread.currentThread (). interrupt (); terugkeren; }}} 

Dit schema implementeert exact het eerder beschreven schema: a Filosoof denkt even na en besluit dan te eten.

Hierna pakt hij de vorken links en rechts en begint te eten. Als hij klaar is, legt hij de vorken neer. We voegen ook tijdstempels toe aan elke actie, die ons zouden helpen de volgorde te begrijpen waarin gebeurtenissen plaatsvinden.

Om het hele proces een vliegende start te geven, schrijven we een klant die er 5 maakt Filosofen als threads en start ze allemaal:

openbare klasse DiningPhilosophers {openbare statische leegte hoofd (String [] args) gooit Uitzondering {Filosoof [] filosofen = nieuwe Filosoof [5]; Object [] forks = nieuw object [filosofen.lengte]; for (int i = 0; i <forks.length; i ++) {forks [i] = new Object (); } for (int i = 0; i <filosofers.length; i ++) {Object leftFork = forks [i]; Object rightFork = forks [(i + 1)% forks.length]; filosofen [i] = nieuwe filosoof (leftFork, rightFork); Thread t = nieuwe Thread (filosofen [i], "Philosopher" + (i + 1)); t.start (); }}}

We modelleren elk van de vorken als generieke Java-objecten en maken er zoveel als er filosofen zijn. We passeren elk Filosoof zijn linker- en rechtervorken die hij probeert te vergrendelen met de gesynchroniseerd trefwoord.

Het uitvoeren van deze code resulteert in een uitvoer die lijkt op de volgende. Uw uitvoer zal hoogstwaarschijnlijk verschillen van de onderstaande, voornamelijk omdat de slaap() methode wordt aangeroepen voor een ander interval:

Filosoof 1 8038014601251: Denkende Filosoof 2 8038014828862: Denkende Filosoof 3 8038015066722: Denkende Filosoof 4 8038015284511: Denkende Filosoof 5 8038015468564: Denkende Filosoof 1 8038016857288: Filosoof opvork links 8038016857288: Filosoof 32vork oppakken vork Philosopher 4 8038063952219: Opgenomen linkervork Philosopher 1 8038067505168: Rechtervork neerzetten Philosopher 2 8038089505264: Opgenomen linkervork Philosopher 1 8038089505264: Linkervork neerzetten. Terug naar denken Filosoof 5 8038111040317: Opgenomen linkervork

Al de Filosoofs beginnen in eerste instantie na te denken, en dat zien we Filosoof 1 gaat verder met het oppakken van de linker- en rechtervork, eet en gaat verder met het neerleggen van beide, waarna `Filosoof 5 'het oppakt.

5. Het probleem met de oplossing: impasse

Hoewel het lijkt alsof de bovenstaande oplossing correct is, is er een probleem met een impasse.

Een impasse is een situatie waarin de voortgang van een systeem wordt stopgezet terwijl elk proces wacht op het verkrijgen van een bron die door een ander proces wordt vastgehouden.

We kunnen hetzelfde bevestigen door de bovenstaande code een paar keer uit te voeren en soms te controleren of de code gewoon vastloopt. Hier is een voorbeelduitvoer die het bovenstaande probleem laat zien:

Philosopher 1 8487540546530: Thinking Philosopher 2 8487542012975: Thinking Philosopher 3 8487543057508: Thinking Philosopher 4 8487543318428: Thinking Philosopher 5 8487544590144: Thinking Philosopher 3 8487589069046: Pick-up vork links 8487589069046: Pick-up vork links 8487589069046: Pick-up vork 848 4 8487617680958: Opgenomen linkervork Philosopher 2 8487631148853: Opgenomen linkervork

In deze situatie kan elk van de Filosoofs heeft zijn linkervork verworven, maar kan zijn rechtervork niet krijgen, omdat zijn buurman die al heeft verworven. Deze situatie is algemeen bekend als de cirkelvormig wachten en is een van de voorwaarden die resulteert in een impasse en de voortgang van het systeem verhindert.

6. De impasse oplossen

Zoals we hierboven hebben gezien, is de belangrijkste reden voor een impasse de circulaire wachttoestand waarbij elk proces wacht op een bron die wordt vastgehouden door een ander proces. Om een ​​impasse te voorkomen, moeten we er daarom voor zorgen dat de cirkelvormige wachttoestand wordt verbroken. Er zijn verschillende manieren om dit te bereiken, de eenvoudigste is de volgende:

Alle filosofen reiken als eerste naar hun linkervork, behalve één die als eerste naar zijn rechtervork reikt.

We implementeren dit in onze bestaande code door een relatief kleine wijziging in de code aan te brengen:

openbare klasse DiningPhilosophers {openbare statische leegte hoofd (String [] args) gooit Uitzondering {laatste Filosoof [] filosofen = nieuwe Filosoof [5]; Object [] forks = nieuw Object [filosofen.lengte]; for (int i = 0; i <forks.length; i ++) {forks [i] = new Object (); } for (int i = 0; i <filosofers.length; i ++) {Object leftFork = forks [i]; Object rightFork = forks [(i + 1)% forks.length]; if (i == Philosophers.length - 1) {// De laatste filosoof pakt de rechtervork eerste filosofen [i] = nieuwe filosoof (rightFork, leftFork); } anders {filosofen [i] = nieuwe filosoof (leftFork, rightFork); } Thread t = nieuwe Thread (filosofen [i], "Philosopher" + (i + 1)); t.start (); }}} 

De verandering komt in regels 17-19 van de bovenstaande code, waar we de voorwaarde introduceren die ervoor zorgt dat de laatste filosoof als eerste naar zijn rechtervork reikt, in plaats van naar links. Dit doorbreekt de cirkelvormige wachtconditie en we kunnen de impasse vermijden.

De volgende uitvoer toont een van de gevallen waarin alle Filosoofs krijgen de kans om na te denken en te eten, zonder een impasse te veroorzaken:

Filosoof 1 88519839556188: Denkende filosoof 2 88519840186495: Denkende Filosoof 3 88519840647695: Denkende filosoof 4 88519840870182: Denkende filosoof 5 88519840956443: Denkende Filosoof 8851986440870182: Denkende filosoof 5 88519840956443: Denkende Filosoof 885198644040870182: Denkende Filosoof 5 88519840956443: Denkende Filosoof 419854 Filosoof 885198644041985 5 88519876989405: Opgenomen rechtervork - etende Filosoof 2 88519935045524: Opgenomen linkervork Filosoof 5 88519951109805: Rechtervork neerzetten Filosoof 4 88519997119634: Opgenomen rechtervork - eten Filosoof 5 88519997113229: Linkervork neergezet. Terug naar denken Filosoof 5 88520011135846: Denken Filosoof 1 88520011129013: Opgenomen linkervork Filosoof 4 88520028194269: Rechtervork neerzetten Filosoof 4 88520057160194: Linkervork neerzetten. Terug naar denken Filosoof 3 88520067162257: Opgenomen rechtervork - eten Filosoof 4 88520067158414: Denkende filosoof 3 88520160247801: Rechtervork neerzetten Filosoof 4 88520249049308: Opgenomen linkervork Filosoof 3 88520249119769: Linkervork neerzetten. Terug aan het denken 

Door de code meerdere keren uit te voeren, kan worden geverifieerd dat het systeem vrij is van de eerder opgetreden impasse-situatie.

7. Conclusie

In dit artikel hebben we het beroemde probleem van Dining Philosophers en de concepten van circulair wachten en impasse. We hebben een eenvoudige oplossing gecodeerd die een impasse veroorzaakte en een eenvoudige wijziging aangebracht om het cirkelvormige wachten te doorbreken en een impasse te vermijden. Dit is slechts een begin, en er bestaan ​​meer geavanceerde oplossingen.

De code voor dit artikel is te vinden op GitHub.