|
Problema dei filosofi a cenaIl 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. DescrizioneL'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 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:
Note
Bibliografia
Voci correlateAltri progetti
Collegamenti esterni
|
