Si tratta di un problema del tutto fittizio, di nessuna rilevanza pratica, ma è un esempio rappresentativo dei tipici problemi di sincronizzazione tra processi (in questo caso i filosofi) che tentano si usare in modo asincrono alcune risorse condivise e limitate (in tal caso le forchette). Questo esempio mette in evidenza i problemi del deadlock (in italiano blocco critico) e della starvation e fu ideato da E. W. Dijkstra.
Ci sono cinque filosofi seduti stabilmente ad un tavolo rotondo e ciascuno ha davanti un piatto di riso (che supponiamo inesauribile), oppure esiste un unico grande piatto al centro della tavola da cui ogni filosofo mangia (questo non cambia il problema). Tra un piatto ed un altro (o tra un filosofo ed un altro) però non vi sono due bastoncini come sarebbe opportuno, ma solo uno, per un totale di sole 5 bacchette, contro le 10 che sarebbero richieste per permettere a tutti di mangiare contemporaneamente. Ciascun filosofo per tutta la sua vita non fa altro che tre cose: pensare quando e' sazio, mangiare e mettersi in attesa di mangiare quando ha fame. Un filosofo decide di mettersi a pensare a qualche problema filosofico per un certo intervallo di tempo (che possiamo ritenere casuale e finito), poi si siede a tavola (supponiamo ciascuno abbia assegnato un posto fisso, ma questo non è necessario) e decide di mangiare il riso. Impiega un certo tempo a mangiare (anche questo lo faremo variare casualmente, ma sarà sempre finito), poi decide di mettersi di nuovo a pensare, poi mangia di nuovo, ecc. Quando decide di mangiare, prima di poterlo fare, ha bisogno di prendere in mano due bacchette. Un filosofo può prendere solo le due bacchette che stanno alla sua destra e alla sua sinistra, una per volta, e solo se sono libere, ovvero non può sottrarre la risorsa bacchetta ad un altro filosofo che l'ha già acquisita, cioè che sta mangiando (no preemption). Finché non riesce a prendere le bacchette, il filosofo deve aspettare affamato. Quando invece, appena dopo aver mangiato, è sazio, posa le bacchette al loro posto e si mette a pensare per un certo tempo.
La situazione è tale che due filosofi vicini non possono mai mangiare contemporaneamente. Si chiede di trovare una soluzione, ossia una strategia tramite la quale i filosofi sono costretti ad acquisire le risorse (le bacchette) che soddisfi i seguenti due obiettivi:
Ad esempio supponete che la strategia scelta (l'algoritmo eseguito dai filosofi, posto uguale per tutti) consista nell'acquisire prima la bacchetta che sta a destra e poi quella che sta a sinistra (sarebbe analoga la strategia che stabilisce di fare viceversa, essendo la tavola rotonda). Poiché abbiamo detto che le bacchette vengono prese una alla volta, è possibile che si crei la situazione di stallo di cui al punto 1 se capita che tutti i filosofi abbiano fame contemporaneamente e quindi prendono la bacchetta di destra nello stesso istante. Ognuno ritiene la sua bacchetta e tenta subito dopo di afferrare quella di sinistra, ma questa non c'è e quindi si mette in attesa che il vicino di sinistra la rilasci. Ma questo a sua volta è in attesa che il suo vicino di sinistra rilasci la sua bacchetta di sinistra e così via per tutti i 5 filosofi. Tutti i 5 filosofi rimangono immobilizzati con una sola bacchetta in mano, in attesa per l'eternità l'uno dell'altro, o più realisticamente moriranno tutti di fame (il deadlock è una specie di starvation collettiva).
Potreste obiettare che questa eterna attesa circolare normalmente capita raramente, il che è vero, ma il problema è comunque possibile che si verifichi e non può essere ignorato. Il deadlock è sempre in agguato se non vengono prese misure per prevenirlo.
Questo programma C usa i thread POSIX di UNIX per simulare il problema via software. Ogni flusso di controllo del processo, o thread, rappresenta un filosofo, nel senso che ne simula il comportamento. Poiché la strategia adottata da ogni filosofo è quella semplice descritta sopra, questo programma non è immune al problema del deadlock.
/* Simulation of the 5 philosophers problem (with deadlock!) */
/*
using gcc(1) compile with:
$ gcc -pthread -Wall -o 5philosopher 5philosopher.c
*/
#include <pthread.h>
#include <stdio.h>
#define PHILOSOPHERS 5
#define ITERATION 100
char *progname;
/* the chopsticks */
pthread_mutex_t chopstick[PHILOSOPHERS];
/* print error message and die */
void error(char *f)
{ extern char *progname;
if (progname)
fprintf(stderr, "%s: ", progname);
perror(f);
exit(1);
}
void *philosopherRoutine(void *idp)
{ int id=*(int *)idp, i;
for (i=0; i<ITERATION; i++)
{ printf("#%d is hungry\n", id);
if (pthread_mutex_lock(&chopstick[id]))
error("pthread_mutex_lock");
printf("#%d got right chopstick\n", id);
if (pthread_mutex_lock(&chopstick[(id+1) % PHILOSOPHERS]))
error("pthread_mutex_lock");
printf("#%d got left chopstick\n", id);
printf("#%d is eating\n", id);
if (pthread_mutex_unlock(&chopstick[id]))
error("pthread_mutex_unlock");
printf("#%d left right chopstick\n", id);
if (pthread_mutex_unlock(&chopstick[(id+1) % PHILOSOPHERS]))
error("pthread_mutex_unlock");
printf("#%d left left chopstick\n", id);
printf("#%d is thinking\n", id);
}
return NULL;
}
int main(int argc, char *argv[])
{ int i;
struct
{ int id;
pthread_t thread_id;
} philosopher[PHILOSOPHERS];
progname=argv[0];
/* create mutex semaphores */
for (i=0; i<PHILOSOPHERS; i++)
if (pthread_mutex_init(&chopstick[i], NULL))
error("pthread_mutex_init");
/* create and run the threads */
for (i=0; i<PHILOSOPHERS; i++)
{ philosopher[i].id=i;
if (pthread_create(&philosopher[i].thread_id, NULL,
philosopherRoutine, &philosopher[i].id))
error("pthread_create");
}
/* wait for the threads to terminate */
for (i=0; i<PHILOSOPHERS; i++)
if (pthread_join(philosopher[i].thread_id, NULL))
error("pthread_join");
return 0;
}
Eseguendo con un valore nemmeno tanto elevato di iterazioni (100), dopo poche prove mi è capitato sperimentalmente di incorrere nel deadlock. Ad un certo punto sullo schermo mi è apparsa la seguente sequenza, dopodiché il processo sembra essere bloccato indefinitamente, infatti ps(1) riporta sempre lo stato del processo come S (sleeping):
$ ./5philosophers ... #0 is thinking #0 is hungry #1 is hungry #2 is hungry #3 is hungry #4 is hungry #0 got right chopstick #1 got right chopstick #2 got right chopstick #3 got right chopstick #4 got right chopstick ^C(da un'altra consolle virtuale, prima di interrompere)
$ ps | grep 5philosopher 213 v0 S+ 0:00.03 ./5philosopher
A questo punto in UNIX, che non prende alcuna precauzione per evitare il deadlock, né statica né dinamica (questa scelta è motivata dal fatto di evitare l'overhead associato a tali misure), non resta che fare il kill manuale del processo, ad esempio premendo CTRL-C dal terminale di controllo.
Il problema 2, ossia la starvation, nel nostro programma non può verificarsi, perchè abbiamo un numero finito di iterazioni dopo il quale il filosofo esce (lascia le bacchette e si alza dalla tavola), quindi tutti i filosofi mangeranno e penseranno lo stesso numero di volte alla fine. Tuttavia se sostituite il ciclo for con un ciclo infinito, ossia se ogni filosofo effettua un numero infinito di iterazioni, il problema della starvation può verificarsi.
Un caso semplice di starvation: supponiamo di avere tempi di attesa fissi e che due filosofi non adiacenti abbiano un tempo di attesa per pensare e per mangiare molto minore degli altri. Allora accade che questi due filosofi veloci pensano, poi acquisiscono le bacchette e mangiano e poi le rilasciano e pensano ancora. Quando hanno finito di pensare per la seconda volta, gli altri 3 filosofi (quelli lenti) non hanno ancora finito di pensare per la prima volta perciò non acquisiscono le bacchette rilasciate, ma le acquisiscono ancora i filosofi veloci. La temporizzazione può essere tale che i filosofi lenti non riescono mai ad acquisire le bacchette pur avendone la chance. Questa è la starvation, che è ben diversa dal deadlock, perché non c'è un'attesa circolare e tutti hanno la change di mangiare.
Supponendo di essere su una macchina monoprocessore, se lo scheduler dei thread è di tipo not-preemptive, si verificherà banalmente la starvation per come è scritto il codice (senza le sleep), in quanto il primo thread schedulato continuerà ad essere eseguito, impedendo a tutti gli altri di eseguire. Nel mio caso, la variante di UNIX usata (FreeBSD) implementa i thread secondo lo standard POSIX e li schedula in modo preemptive vale a dire time-slicing o time-sharing e quindi la starvation è molto più raro che si verifichi. La starvation potrebbe essere evitata completamente, usando all'inizio o alla fine del ciclo, quando il filosofo non ha alcuna bacchetta, ad ogni iterazione oppure ogni volta che passa un certo numero di iterazioni, la funzione pthread_yield(), che indica allo schedulatore di sospendere forzatamente il thread corrente ed avviarne un'altro. Per lo meno questa è la soluzione più semplice.
Invece per risolvere il problema 1, cioè impedire che si verifici il deadlock, una tecnica consiste nell'adottare una soluzione asimmetrica, ossia una strategia che varia a seconda del filosofo considerato. È sufficiente numerare i filosofi e prevedere due sole strategie differenti, una per i filosofi di numero dispari e l'altra per i filosofi di numero pari. Possiamo stabilire che i filosofi dispari debbano acquisire prima la bacchetta destra e poi quella sinistra e che i filosofi pari debbano fare viceversa, oppure viceversa per entrambi. In altri termini, facciamo sì che due filosofi adiacenti competano sempre per acquisire per prima la bacchetta che li separa, evitando così che tutti acquisiscano la bacchetta alla loro destra o tutti acquisiscano quella alla loro sinistra, che sone le due uniche situazioni di deadlock. In questo modo evitiamo che si crei una attesa circolare e di conseguenza il deadlock non potrà mai verificarsi.
Ecco la nuova versione del programma, che non va incontro al problema del blocco critico. Stavolta abbiamo introdotto anche dei ritardi casuali (regolabili tra un minimo e un massimo) per rendere la simulazione più lenta e realistica. È stato introdotto anche un breve ritardo tra l'acquisizione di un bastoncino e l'altro. Il generatore di numeri casuali viene inizializzato tramite srand(3), usando come seme il valore restituito da time(3), che è il tempo in secondo trascorso dal 1 Gennaio 1970, UTC, in modo da ottenere sequenze di numeri casuali diverse tra una esecuzione e l'altra. Inoltre in questa nuova versione ho scelto di invertire l'ordine delle due azioni pensare e mangiare nel ciclo, mettendo prima l'azione di pensare. Notate la convenzione per quanto riguarda la numerazione delle bacchette: per un filosofo numero id, la bacchetta numero id è quella alla sua destra, mentre quella alla sua sinistra ha numero (id+1) % 5. Questo corrisponde ad una numerazione in senso antiorario crescente, fatta a partire da 0 dei filosofi e delle bacchette. Si noti che è irrilevante l'ordine in cui le bacchette vengono posate, che quindi può anche non coincidere con quello in cui sono state acquisite.
/* Simulation of the 5 philosophers problem.
This solution avoid deadlocks, but not starvation. */
/*
using gcc(1) compile with:
$ gcc -pthread -Wall -o 5philosopher 5philosopher.c
*/
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#define PHILOSOPHERS 5
#define ITERATION 3
char *progname;
/* the chopsticks */
pthread_mutex_t chopstick[PHILOSOPHERS];
/* print error message and die */
void error(char *f)
{ extern char *progname;
if (progname)
fprintf(stderr, "%s: ", progname);
perror(f);
exit(1);
}
/* suspend execution of the calling thread */
void waiting(int min, int max)
{ sleep(rand()%(max-min+1) + min);
}
void rightChopstick(int id)
{ if (pthread_mutex_lock(&chopstick[id]))
error("pthread_mutex_lock");
printf("#%d got right chopstick\n", id);
}
void leftChopstick(int id)
{ if (pthread_mutex_lock(&chopstick[(id+1) % PHILOSOPHERS]))
error("pthread_mutex_lock");
printf("#%d got left chopstick\n", id);
}
void *philosopherRoutine(void *idp)
{ int id=*(int *)idp, i;
for (i=0; i<ITERATION; i++)
{ printf("#%d is thinking\n", id);
waiting(1, 10);
printf("#%d is hungry\n", id);
if (id % 2)
{ rightChopstick(id);
waiting(1,2);
leftChopstick(id);
}
else
{ leftChopstick(id);
waiting(1,2);
rightChopstick(id);
}
printf("#%d is eating\n", id);
waiting(1, 10);
if (pthread_mutex_unlock(&chopstick[id]))
error("pthread_mutex_unlock");
printf("#%d left right chopstick\n", id);
if (pthread_mutex_unlock(&chopstick[(id+1) % PHILOSOPHERS]))
error("pthread_mutex_unlock");
printf("#%d left left chopstick\n", id);
}
return NULL;
}
int main(int argc, char *argv[])
{ int i;
struct
{ int id;
pthread_t thread_id;
} philosopher[PHILOSOPHERS];
progname=argv[0];
srand(time(NULL));
/* create mutex semaphores */
for (i=0; i<PHILOSOPHERS; i++)
if (pthread_mutex_init(&chopstick[i], NULL))
error("pthread_mutex_init");
/* create and run the threads */
for (i=0; i<PHILOSOPHERS; i++)
{ philosopher[i].id=i;
if (pthread_create(&philosopher[i].thread_id, NULL,
philosopherRoutine, &philosopher[i].id))
error("pthread_create");
}
/* wait for the threads to terminate */
for (i=0; i<PHILOSOPHERS; i++)
if (pthread_join(philosopher[i].thread_id, NULL))
error("pthread_join");
return 0;
}
Eliminare il deadlock, che è il problema più grave, è addirittura più semplice che eliminare la starvation. Per eliminare il deadlock è addirittura sufficiente che ci sia un solo filosofo che acquisisca le risorse in ordine inverso rispetto a tutti gli altri. Ciò consente di eliminare l'attesa circolare, facendo sì che ogni filosofo abbia una change di prendere le bacchette e mangiare e quindi elimina il deadlock, ma non assicura dal problema della starvation. Questo potrebbe essere dimostrato analizzando i casi possibili.
Antonio