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[modifica | modifica wikitesto]
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.
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 F1 aspetta di prendere la forchetta che ha in mano il filosofo F2, che aspetta la forchetta che ha in mano il filosofo F3, 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[modifica | modifica wikitesto]
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 F1, F2, F3, F4 e F5, mentre le forchette alla loro sinistra sono rispettivamente f1, f2, f3, f4 e f5. Il primo filosofo F1 dovrà prendere la prima forchetta f1 prima di poter prendere la seconda forchetta f2. I filosofi F2, F3 e F4 si comporteranno in modo analogo, prendendo sempre la forchetta fi prima della forchetta fi+1. Rispettando l'ordine numerico ma invertendo l'ordine delle mani, il filosofo F5 prenderà prima la forchetta f1 e poi la forchetta f5. 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[modifica | modifica wikitesto]
- ^ 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[modifica | modifica wikitesto]
- 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.
Voci correlate[modifica | modifica wikitesto]
Altri progetti[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file sul problema dei filosofi a cena
Collegamenti esterni[modifica | modifica wikitesto]
- (EN) Dining Philosophers Problem, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL
