Il problema dei filosofi a tavola in Java

1. Introduzione

Il problema Dining Philosophers è uno dei classici problemi utilizzati per descrivere i problemi di sincronizzazione in un ambiente multi-thread e illustrare le tecniche per risolverli . Dijkstra per primo ha formulato questo problema e lo ha presentato per quanto riguarda i computer che accedono alle periferiche delle unità a nastro.

La presente formulazione è stata fornita da Tony Hoare, noto anche per aver inventato l'algoritmo di ordinamento quicksort. In questo articolo, analizziamo questo noto problema e codifichiamo una soluzione popolare.

2. Il problema

Il diagramma sopra rappresenta il problema. Ci sono cinque filosofi silenziosi (P1 - P5) seduti attorno a un tavolo circolare, che passano la vita mangiando e pensando.

Ci sono cinque forchette da condividere (1 - 5) e per poter mangiare, un filosofo deve avere le forchette in entrambe le mani. Dopo aver mangiato, li mette giù entrambi e poi possono essere raccolti da un altro filosofo che ripete lo stesso ciclo.

L'obiettivo è di elaborare uno schema / protocollo che aiuti i filosofi a raggiungere il loro obiettivo di mangiare e pensare senza morire di fame.

3. Una soluzione

Una prima soluzione potrebbe essere quella di far seguire a ciascuno dei filosofi il seguente protocollo:

while(true) { // Initially, thinking about life, universe, and everything think(); // Take a break from thinking, hungry now pick_up_left_fork(); pick_up_right_fork(); eat(); put_down_right_fork(); put_down_left_fork(); // Not hungry anymore. Back to thinking! } 

Come descrive lo pseudo codice sopra, ogni filosofo sta inizialmente pensando. Dopo un certo periodo di tempo, il filosofo ha fame e desidera mangiare.

A questo punto, prende le forchette su entrambi i lati e una volta che le ha entrambe, inizia a mangiare . Una volta finito di mangiare, il filosofo posa le forchette, in modo che siano disponibili per il suo vicino.

4. Implementazione

Modelliamo ciascuno dei nostri filosofi come classi che implementano l' interfaccia Runnable in modo da poterli eseguire come thread separati. Ogni filosofo ha accesso a due forchette sui lati sinistro e destro:

public class Philosopher implements Runnable { // The forks on either side of this Philosopher private Object leftFork; private Object rightFork; public Philosopher(Object leftFork, Object rightFork) { this.leftFork = leftFork; this.rightFork = rightFork; } @Override public void run() { // Yet to populate this method } }

Abbiamo anche un metodo che istruisce un filosofo a eseguire un'azione: mangiare, pensare o acquistare forchette in preparazione per mangiare:

public class Philosopher implements Runnable { // Member variables, standard constructor private void doAction(String action) throws InterruptedException { System.out.println( Thread.currentThread().getName() + " " + action); Thread.sleep(((int) (Math.random() * 100))); } // Rest of the methods written earlier }

Come mostrato nel codice sopra, ogni azione viene simulata sospendendo il thread di richiamo per un periodo di tempo casuale, in modo che l'ordine di esecuzione non venga applicato solo dal tempo.

Ora, implementiamo la logica di base di un filosofo .

Per simulare l'acquisizione di un fork, è necessario bloccarlo in modo che non vengano acquisiti contemporaneamente da due thread Philosopher .

Per ottenere ciò, utilizziamo la parola chiave synchronized per acquisire il monitor interno dell'oggetto fork e impedire ad altri thread di fare lo stesso. Una guida alla parola chiave sincronizzata in Java può essere trovata qui. Procediamo ora con l'implementazione del metodo run () nella classe Philosopher :

public class Philosopher implements Runnable { // Member variables, methods defined earlier @Override public void run() { try { while (true) { // thinking doAction(System.nanoTime() + ": Thinking"); synchronized (leftFork) { doAction( System.nanoTime() + ": Picked up left fork"); synchronized (rightFork) { // eating doAction( System.nanoTime() + ": Picked up right fork - eating"); doAction( System.nanoTime() + ": Put down right fork"); } // Back to thinking doAction( System.nanoTime() + ": Put down left fork. Back to thinking"); } } } catch (InterruptedException e) { Thread.currentThread().interrupt(); return; } } } 

Questo schema implementa esattamente quello descritto in precedenza: un filosofo pensa per un po 'e poi decide di mangiare.

Dopo questo, acquisisce le forchette alla sua sinistra e destra e inizia a mangiare. Quando ha finito, posa le forche. Aggiungiamo anche timestamp a ciascuna azione, che ci aiuterebbero a capire l'ordine in cui si verificano gli eventi.

Per avviare l'intero processo, scriviamo un client che crea 5 Filosofi come thread e li avvia tutti:

public class DiningPhilosophers { public static void main(String[] args) throws Exception { Philosopher[] philosophers = new Philosopher[5]; Object[] forks = new Object[philosophers.length]; for (int i = 0; i < forks.length; i++) { forks[i] = new Object(); } for (int i = 0; i < philosophers.length; i++) { Object leftFork = forks[i]; Object rightFork = forks[(i + 1) % forks.length]; philosophers[i] = new Philosopher(leftFork, rightFork); Thread t = new Thread(philosophers[i], "Philosopher " + (i + 1)); t.start(); } } }

Modelliamo ciascuno dei fork come oggetti Java generici e ne creiamo tanti quanti sono i filosofi. Passiamo a ogni Filosofo i suoi fork sinistro e destro che tenta di bloccare usando la parola chiave sincronizzata .

L'esecuzione di questo codice produce un output simile al seguente. Il tuo output sarà molto probabilmente diverso da quello indicato di seguito, principalmente perché il metodo sleep () viene invocato per un intervallo diverso:

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 8038022332758: Picked up right fork - eating Philosopher 3 8038028886069: Picked up left fork Philosopher 4 8038063952219: Picked up left fork Philosopher 1 8038067505168: Put down right fork Philosopher 2 8038089505264: Picked up left fork Philosopher 1 8038089505264: Put down left fork. Back to thinking Philosopher 5 8038111040317: Picked up left fork

Tutti i Filosofi inizialmente iniziano a pensare, e vediamo che Filosofo 1 procede a prendere la forchetta sinistra e destra, poi mangia e procede a metterle entrambe giù, dopo di che "Filosofo 5" la raccoglie.

5. Il problema con la soluzione: deadlock

Sebbene sembri che la soluzione di cui sopra sia corretta, si verifica un problema di deadlock.

Un deadlock è una situazione in cui l'avanzamento di un sistema viene interrotto poiché ogni processo è in attesa di acquisire una risorsa detenuta da un altro processo.

Possiamo confermare lo stesso eseguendo il codice sopra alcune volte e verificando che alcune volte il codice si blocchi. Ecco un output di esempio che dimostra il problema precedente:

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 8487596641267: Picked up left fork Philosopher 5 8487597646086: Picked up left fork Philosopher 4 8487617680958: Picked up left fork Philosopher 2 8487631148853: Picked up left fork

In questa situazione, ciascuno dei Filosofi ha acquisito la forchetta sinistra, ma non può acquisire la forchetta destra, perché il suo vicino l'ha già acquistata. Questa situazione è comunemente nota come attesa circolare ed è una delle condizioni che determina un deadlock e impedisce l'avanzamento del sistema.

6. Risolvere il deadlock

Come abbiamo visto sopra, il motivo principale per un deadlock è la condizione di attesa circolare in cui ogni processo attende una risorsa che è trattenuta da un altro processo. Quindi, per evitare una situazione di deadlock, dobbiamo assicurarci che la condizione di attesa circolare sia interrotta. Esistono diversi modi per ottenere ciò, il più semplice è il seguente:

Tutti i filosofi raggiungono per primi il bivio a sinistra, tranne uno che per primo raggiunge il bivio a destra.

Lo implementiamo nel nostro codice esistente apportando una modifica relativamente minore al codice:

public class DiningPhilosophers { public static void main(String[] args) throws Exception { final Philosopher[] philosophers = new Philosopher[5]; Object[] forks = new Object[philosophers.length]; for (int i = 0; i < forks.length; i++) { forks[i] = new Object(); } for (int i = 0; i < philosophers.length; i++) { Object leftFork = forks[i]; Object rightFork = forks[(i + 1) % forks.length]; if (i == philosophers.length - 1) { // The last philosopher picks up the right fork first philosophers[i] = new Philosopher(rightFork, leftFork); } else { philosophers[i] = new Philosopher(leftFork, rightFork); } Thread t = new Thread(philosophers[i], "Philosopher " + (i + 1)); t.start(); } } } 

La modifica avviene nelle righe 17-19 del codice precedente, dove introduciamo la condizione che fa sì che l'ultimo filosofo raggiunga per primo la sua biforcazione destra, invece della sinistra. Questo interrompe la condizione di attesa circolare e possiamo evitare il deadlock.

L'output seguente mostra uno dei casi in cui tutti i filosofi hanno la possibilità di pensare e mangiare, senza causare una situazione di stallo:

Philosopher 1 88519839556188: Thinking Philosopher 2 88519840186495: Thinking Philosopher 3 88519840647695: Thinking Philosopher 4 88519840870182: Thinking Philosopher 5 88519840956443: Thinking Philosopher 3 88519864404195: Picked up left fork Philosopher 5 88519871990082: Picked up left fork Philosopher 4 88519874059504: Picked up left fork Philosopher 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: Put down left fork. Back to thinking Philosopher 5 88520011135846: Thinking Philosopher 1 88520011129013: Picked up left fork Philosopher 4 88520028194269: Put down right fork Philosopher 4 88520057160194: Put down left fork. Back to thinking 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: Put down left fork. Back to thinking 

È possibile verificare eseguendo più volte il codice che il sistema sia libero dalla situazione di deadlock verificatasi in precedenza.

7. Conclusione

In questo articolo, abbiamo esplorato il famoso problema dei filosofi a tavola ei concetti di attesa circolare e deadlock . Abbiamo codificato una soluzione semplice che causava un deadlock e apportato una semplice modifica per interrompere l'attesa circolare ed evitare un deadlock. Questo è solo l'inizio e esistono soluzioni più sofisticate.

Il codice per questo articolo può essere trovato su GitHub.