Problema dei filosofi a cena

Il problema dei filosofi a cena, altrimenti noto come problema dei cinque filosofi, è un esempio che illustra un comune problema di controllo della concorrenza in informatica. Si tratta di un classico problema di sincronizzazione fra processi paralleli.

Descrizione

L'esempio fu descritto nel 1965 da Edsger Dijkstra, che se ne servì per esporre un problema di sincronizzazione.^[1] Cinque filosofi siedono ad una tavola rotonda con un piatto di spaghetti davanti e una forchetta a sinistra (o a destra; secondo un'altra versione vi è invece un bastoncino cinese^[2]^[3]). Ci sono dunque cinque filosofi, cinque piatti di spaghetti e cinque forchette.

Illustrazione del problema dei filosofi a cena

Si immagini che la vita di un filosofo consista di periodi alterni di mangiare e pensare, e che ciascun filosofo abbia bisogno di due forchette per mangiare, ma che le forchette vengano prese una per volta. Dopo essere riuscito a prendere due forchette il filosofo mangia per un po', poi lascia le forchette e ricomincia a pensare. Il problema consiste nello sviluppo di un algoritmo che impedisca lo stallo (deadlock) o la morte d'inedia (starvation). Il deadlock può verificarsi se ciascuno dei filosofi tiene in mano una forchetta senza mai riuscire a prendere l'altra. Il filosofo F₁ aspetta di prendere la forchetta che ha in mano il filosofo F₂, che aspetta la forchetta che ha in mano il filosofo F₃, e così via in un circolo vizioso.^[1] La situazione di starvation può verificarsi indipendentemente dal deadlock se uno dei filosofi non riesce mai a prendere entrambe le forchette.

La presa di forchette è analoga al blocco di risorse limitate nella programmazione reale, situazione nota con il nome di "concorrenza". Bloccare una risorsa è una tecnica comune per garantirne l'accesso da parte di un programma solo o di una sola porzione di programma alla volta. Se la risorsa richiesta da un programma è già stata bloccata, il programma aspetta fino a quando la risorsa si sblocca. Se il blocco coinvolge più di una risorsa, è possibile che in alcune circostanze si verifichi un deadlock. Come esempio si consideri il caso di un programma che ha bisogno di due file da elaborare. Se due programmi di questo genere bloccano un file ciascuno, entrambi aspetteranno invano che l'altro programma sblocchi l'altro file.

Soluzione

Una possibile soluzione è quella di numerare le forchette ed esigere che vengano prese in ordine numerico crescente, analogamente ad un caso di allocazione gerarchica delle risorse. In questa soluzione i filosofi sono denominati F₁, F₂, F₃, F₄ e F₅, mentre le forchette alla loro sinistra sono rispettivamente f₁, f₂, f₃, f₄ e f₅. Il primo filosofo F₁ dovrà prendere la prima forchetta f₁ prima di poter prendere la seconda forchetta f₂. I filosofi F₂, F₃ e F₄ si comporteranno in modo analogo, prendendo sempre la forchetta f_i prima della forchetta f_i+1. Rispettando l'ordine numerico ma invertendo l'ordine delle mani, il filosofo F₅ prenderà prima la forchetta f₁ e poi la forchetta f₅. Si crea così un'asimmetria che serve ad evitare i deadlock.

L'efficacia nella prevenzione della starvation dipende dal metodo di mutua esclusione utilizzato. Le implementazioni che fanno uso di spinlock, ovvero cicli di attesa, possono provocare starvation a causa di problemi di sincronia inerenti a tali metodi. Altri metodi di mutua esclusione che utilizzano code di attesa possono prevenire la starvation in modo più efficiente assicurando uguale accesso alle forchette da parte di tutti e due i filosofi adiacenti.

Questa soluzione può anche essere generalizzata al caso in cui si voglia consentire ad un qualsiasi numero di agenti di ottenere accesso esclusivo ad un qualsiasi numero di risorse. È necessario che gli agenti si attengano a queste regole:

Tutti gli agenti devono richiedere accesso alle risorse in ordine crescente, prima cioè di richiedere l'accesso ad una risorsa di ordine maggiore, l'agente deve aver ottenuto l'accesso alle risorse di ordine minore di cui ha bisogno.
Prima di richiedere l'accesso a una risorsa di ordine minore, l'agente deve rilasciare le risorse di ordine maggiore alle quali sta accedendo.
Se non ha accesso a una risorsa di ordine maggiore, l'agente deve rilasciare le risorse di ordine minore alle quali sta accedendo.

Note

^ ^a ^b Dijkstra, Edsger W. EWD-1000. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.
^ (EN) Axel Jantsch, Modeling Embedded Systems and SoC's: Concurrency and Time in Models of Computation, Elsevier, 2003, p. 85, ISBN 9780080511825.
^ (EN) Kevin R. Burton, Net Common Language Runtime Unleashed, Sams Publishing, 2002, p. 312, ISBN 9780672321245.

Bibliografia

Silberschatz, Abraham; Peterson, James L., Operating Systems Concepts, Addison-Wesley, 1988, ISBN 0-201-18760-4.
Dijkstra, E. W. (1971, June). Hierarchical ordering of sequential processes. Acta Informatica 1(2): 115–138.
Lehmann, D. J., Rabin M. O, (1981). On the Advantages of Free Choice: A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem. Principles Of Programming Languages 1981 (POPL'81), pp. 133–138.