Techetechetè -- Dijkstra e il problema dei Filosofi a Cena
rubrica:
Autore:
… i cinque filosofi siedono davanti a un piatto di spaghetti …
Personalmente non mi sono mai trovato a cenare con Socrate, Platone, Parmenide, Empedocle e Anassimene ma se mi dovesse capitare di fare una spaghettata in loro compagnia, potrei anche cavarmela con disinvoltura, argomentando con loro il problema dei Filosofi a Cena.
Stiamo parlando di un problema di Informatica <una scienza che ancora doveva venire nella Grecia della scuola di Elea> ma che a quella scuola deve il riferimento.
Tempo fa avevamo analizzato il cosiddetto Problema del Commesso Viaggiatore (in gergo: TSP, acronimo di Travelling Salesman Problem) a cui vi rimandoper rinfrescare la memoria sull’applicazione dei Grafi in diverse questioni matematiche.
Mentre in quel caso al commesso viaggiatore veniva chiesto di trovare il percorso minimo delle sue trasferte, ai Filosofi a Cena a casa mia, viene proposto un altro quesito importante per l’Informatica noto come il Problema di controllo della concorrenza.
Ma dobbiamo andare per ordine: come potete vedere nell’immagine di copertina, i cinque filosofi siedono davanti a un piatto di spaghetti con una sola forchetta a destra e una sola a sinistra.
Nel problema si deve immaginare che ciascun filosofo possa mangiare SOLO CON DUE FORCHETTE anziché una soltanto.
Cinque sono i filosofi, cinque sono i piatti di spaghetti e cinque sono le forchette.
Si deve pensare che:
· la vita di un filosofo consista di periodi alterni di cibo e pensiero
· ciascun filosofo abbia bisogno di due forchette per mangiare
· 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.
Ecco il problema: trovare una regola che impedisca lo stallo o la morte d'inedia.
In inglese i termini rendono ancora meglio: deadlock (lo stallo) e starvation (la morte d'inedia).
Tanto per capirci meglio:
- il deadlock corrisponde a un filosofo che tiene in mano una forchetta senza mai riuscire a prendere l'altra, cioè: il filosofo F1 aspetta di prendere la forchetta che ha in mano il filosofo F2, che a sua volta aspetta la forchetta che ha in mano il filosofo F3, e così via all’infinito.
- la starvation può verificarsi indipendentemente dal deadlock se uno dei filosofi non riesce mai a prendere tutte e due le forchette.
Finché i cinque filosofi non si metteranno d’accordo sulla sequenza della presa e del rilascio delle forchette, prima o poi il Sistema complessivo entrerà in stallo e si bloccherà inevitabilmente.
Spostando il problema in tema di Risorse Informatiche all’interno del nostro comunissimo PC di casa, i cosiddetti ‘blocchi del Sistema’ che ci fanno innervosire e ci costringono a chiudere le sessioni di lavoro con l’odiato comando Ctrl Alt Canc, corrispondono proprio ai cinque filosofi che non sanno più destreggiarsi con lo scambio delle forchette nella cena a casa mia.
Già! E’ vero che il PC è sempre più potente ma le sue risorse sono quelle che sono e il Software è sempre più ingombrante, ragion per cui un deadlock o una starvation ci può anche stare!
Volendo fare i raggi X al nostro PC, va detto che il blocco di una risorsa è una tecnica comune per garantirne l'accesso da parte di un programma o di una sua partizione ma se quella risorsa è già stata bloccata, il programma aspetta fino a quando verrà sbloccata.
Quando però il blocco coinvolge più di una risorsa, è possibile arrivare all’estremo, cioè al deadlock.
Per esempio, se due programmi P1 e P2 girano contemporaneamente tenendo bloccato uno stesso file F1, si verificherà certamente che entrambi aspetteranno lo sblocco del file da parte dell’altro programma, ovviamente invano e all’infinito.
Abbiamo detto che questo problema si inquadra nell’ambito del controllo della concorrenza ma è anche un problema di sincronizzazione, tipo quello utilizzato nei nodi dei semafori ferroviari.L’esempio di cui stiamo parlando fu descritto nel 1965 dall’informatico olandese Edsger Dijkstra che se ne servì, appunto, per descrivere un problema classico di sincronizzazione.
Dijkstraera nato a Rotterdam nel ’30 ed è morto nel 2002 a Nuenen, la città in cui visse Van Gogh alla fine dell’800.
E’ rimasto celebre per il suo più importante contributo all'informatica noto come l’algoritmo di Dijkstra nel concetto Semaforico.
Tornando a noi e alla cena coi filosofi: qual è una possibile soluzione semplice alla sincronizzazione?
Eccola qua, la vedete nell’immagine:- Numerare le forchette ed esigere che vengano prese in ordine numerico crescente. 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 il blocco.
Un’ottima soluzione di un metodo di mutua esclusione.
Già … alle volte non si pensa al fatto che i problemi di logica pura che tanto ci creano imbarazzo e ci fanno irritare tutte le volte che ci vengono proposti, in realtà sono la chiave di più di una soluzione di problemi molto più complessi di pubblica utilità.
Di come dovessero scambiarsi le forchette Socrate e Platone a casa mia, sarete d’accordo con me che ben poco ci importava, ma che da quello stupido problema si sviluppasse poi il controllo dei processi informatici, la cosa non fa che stupirci sempre più.
Appuntamento alle prossime curiosità.
Francesco Caranti