Durante l’uso di un computer è capitato a tutti all’improvviso di trovarlo drammaticamente bloccato. All’inizio si pensa che sia solo ‘lento’ per una qualche ragione ignota ma il nostro ottimismo decresce velocemente fino a svanire quando dopo alcuni minuti siamo sempre lì, con una barra di progressione dannatamente ferma o con dei fastidiosi pallini che ruotano indefinitamente. A quel punto, nonostante siamo consci di non aver salvato le ultime modifiche al file sul quale stavamo lavorando, prendiamo coraggio e spegniamo la dannata macchina, sperando che al successivo avvio le cose vadano meglio. Cosa è successo ? Perché fino a poco prima tutto andava bene e poi improvvisamente ha smesso?
Molto spesso la causa di questa situazione va ricercata in ciò che si chiama “errata condivisione delle risorse”, ad esempio quando due parti del programma richiedono contemporaneamente la risorsa ‘memoria’ oppure ‘hard disk’ e nessuna delle due parti riesce ad accedervi perché bloccata in qualche modo dall’altra.
Il motivo per cui normalmente tutto funziona a dovere, ma ogni tanto appare il problema, è insito nel fatto che in linea di principio i programmi sono scritti bene, ma tuttavia esistono casi in cui non si è tenuto conto di situazioni limite che appunto generano questo tipo di blocchi del sistema.
Per descrivere la questione e per trovarne una soluzione, gli informatici hanno ideato un esempio molto simpatico, che è un interessante problema di logica chiamato La cena dei cinque filosofi: ad un tavolo apparecchiato con 5 piatti e 5 forchette sono seduti 5 filosofi che, da buoni filosofi, fanno soltanto due cose: o mangiano, o pensano.
Nei piatti ci sono degli spaghetti e per mangiarli hanno bisogno di usare due forchette, poiché non possono aiutarsi con un cucchiaio (si, lo so che a molti di noi basta e avanza una sola forchetta per divorare un piatto di pasta, ma evidentemente questi filosofi non sono italiani o comunque hanno poca dimestichezza con la pasta lunga). Se da un lato i filosofi sembrano un po’ snob e impacciati a mangiare, dall’altro però a loro non importa scambiarsi microbi quindi accettano volentieri di condividere le forchette. Il tutto è raffigurato in Figura 1:

Figura 1. La cena dei 5 filosofi ...con 5 forchette.

La speranza è che succeda questo: dopo essere riuscito a prendere due forchette un filosofo mangia per un po', poi lascia le forchette e ricomincia a pensare. Così mediamente tutti e 5 riescono serenamente sia a pensare, sia a mangiare, in un tempo ragionevole prima che la pasta si raffreddi.
Tuttavia questo è solo un desiderio, ma è evidente che ci sono restrizioni, ad esempio non tutti i filosofi possono mangiare contemporaneamente perché il numero di forchette non è sufficiente.
Inoltre si possono addirittura venire a creare alcune situazioni molto incresciose:

1. ciascun filosofo prende una forchetta, in attesa che si liberi l’altra. Ma siccome lo fanno tutti contemporaneamente, la seconda forchetta non si libererà mai;

2. mentre un filosofo sta mangiando, i suoi vicini di posto sono costretti ad attendere indefinitamente perché il golosone è un po’ stanco di pensare e non ripone le forchette, quindi la pastasciutta dei vicini si fredderà di sicuro.

In informatica la prima situazione si chiama ‘deadlock’, una sorta di stallo, di strada senza uscita. La seconda si chiama ‘starvation’, una condizione di inedia, per cui un processo sarebbe pronto ad iniziare, ma è impossibilitato perennemente a farlo per la mancanza delle risorse di cui ha bisogno: quando il nostro computer si blocca, molto probabilmente è incorso in uno di questi due casi. Userò questi due termini nel seguito, non per fare lo splendido, ma perché riassumono in una singola parola le due condizioni enunciate.

Sebbene il problema sia descritto in modo molto semplice, la sua soluzione è piuttosto articolata e richiede una buona dose di logica. Anzi, esiste più di una soluzione, ciascuna con i suoi pro e contro.
Un primo metodo consiste nell’aggiungere alla scena un cameriere che svolge la funzione di arbitro insindacabile: prima di prendere le forchette, il filosofo deve chiedere il permesso al cameriere. Questi lo concede solo se entrambe le forchette sono disponibili. Così evita che un filosofo si impadronisca di una forchetta aspettando all’infinito che si liberi la seconda, prevenendo la situazione di deadlock.
I passi logici di questa soluzione sono visibili in Figura 2:

Figura 2. Algoritmo risolutivo che prevede la presenza di un supervisore, il cameriere.

Sebbene l’algoritmo così come descritto non risolva anche il problema della starvation, l’aggiunta di una lista di priorità aggiusta le cose anche in questo senso: in caso di più richieste in coda, il cameriere accorderà il permesso di prendere le forchette al filosofo che è in attesa da più tempo.
Questo algoritmo permette l’uso concorrente delle risorse, infatti più filosofi possono mangiare contemporaneamente e il supervisore gestisce le forchette in modo efficiente.

I principali vantaggi di questa tecnica sono, oltre alla soluzione dei problemi deadlock e starvation, anche:

1. la possibilità di implementare logiche flessibili di priorità, garantendo un utilizzo equo delle risorse e

2. la minore complessità logica per i filosofi, che non devono far altro che inviare una richiesta al cameriere senza controllare in prima persona se e quali forchette sono disponibili o chi sta mangiando e per quanto tempo.

Quest’ultimo aspetto, tradotto nel mondo reale, significa che le parti di circuito elettronico o di software degli utilizzatori sono mantenute semplici e snelle, con riduzione dei costi e della probabilità di guasto, in una logica di KIS (Keep It Simple) ovvero “fa le cose più semplici possibili”.
Il metodo ha anche qualche controindicazione: fin tanto che i filosofi sono 5 in un unico tavolo, il cameriere deve fare poco sforzo. Ma se deve gestire molti tavoli con un maggior numero di filosofi per tavolo, può entrare in difficoltà e causare extra-ritardi, con questo intendendo che sebbene a un tavolo ci siano le condizioni perché un filosofo riceva l’OK a prendere le forchette, deve rimanere in attesa che il cameriere termini di occuparsi di altri tavoli. Nel mondo reale, avete mai provato ad aprire molte finestre e molti file lamentandovi poi che il computer diventa lento?
Inoltre se il cameriere inciampa e va al pronto soccorso, tutti i filosofi a tutti i tavoli non possono prendere le forchette e mangiare: il fatto che ci sia un unico supervisore va bene finché questo funziona a dovere, ma in caso di un suo guasto si blocca l’intero sistema, nonostante gli utilizzatori siano perfettamente funzionanti e operativi (se fossero autonomi e liberi di decidere, i filosofi mangerebbero).

Un secondo metodo elimina il supervisore prevedendo di creare una gerarchia delle risorse e di istituire una regola per accedervi. Si numerano sia i commensali che le forchette, come in Figura 3:

Figura 3. I filosofi sono ora numerati da P₁ a P₅ e le forchette da f₁ a f₅.

Si istituisce la seguente regola: ogni filosofo deve prendere per prima la forchetta con il numero più basso e solo in un secondo momento quella con il numero più alto. Se ha entrambe le forchette può iniziare a mangiare.
Quindi il filosofo P₁, che sta fra le forchette f₁ ed f₂, prenderà sempre per prima f₁. E così via per tutti.
Ma attenzione: grazie a questa regola, il filosofo P₅, che sta fra le forchette f₅ ed f₁, prenderà per prima f₁, rompendo così la circolarità secondo cui tutti gli altri hanno preso per prima la forchetta alla propria sinistra. Il deadlock si verifica infatti quando si instaura una catena di attesa circolare, quindi rompere la circolarità garantisce di evitarlo: forzare i filosofi a prendere sempre la forchetta col numero più basso elimina la possibilità che due di essi rimangano bloccati aspettando reciprocamente che l’altro liberi una forchetta.
Un grande vantaggio di questo approccio è l’estrema semplicità. Tutto sommato, basta numerare commensali e forchette. Ma un vantaggio ancor più grande è la così detta “scalabilità”: il metodo funziona senza modifiche anche se il numero di filosofi o di forchette è diverso e anche per problemi diversi dalla cena dei filosofi che coinvolgono numerose risorse condivise, non solo le forchette.
Uno svantaggio del metodo è una possibile inefficienza: ci si può trovare in una condizione in cui un solo filosofo mangi, seppure le risorse per qualche altro siano disponibili. C’è anche lo spettro di una qualche starvation, nel malaugurato caso in cui un commensale prenda entrambe le forchette troppo frequentemente, causando attese troppo lunghe per gli altri.

Il metodo appena discusso si può però rendere più efficiente modificando la regola e mantenendo la numerazione dei filosofi: quelli con numero dispari devono prendere per prima la forchetta alla propria destra e solo dopo quella alla propria sinistra, quelli con numero pari devono fare l’opposto: prendere prima la forchetta alla propria sinistra e solo dopo quella alla propria destra.
Questo metodo, chiamato “prelievo asimmetrico delle risorse”, rompe nuovamente la catena di attesa circolare ed evita ogni possibile deadlock.

In dettaglio:

- il filosofo P₁ (dispari) prende prima f₂ (che è alla sua destra) e poi f₁ (che è alla sua sinistra)

- il filosofo P₂ (pari) prende prima f₂ (che è alla sua sinistra) e poi f₃ (che è alla sua destra)

- e così via, ma già dai primi due si capisce che la circolarità di attesa è rotta.

Questo metodo ha l’indubbio vantaggio della semplicità, unitamente al fatto che è equo: benché asimmetrico, in ogni istante qualche filosofo può sempre mangiare.
Un certo grado di starvation è possibile, nel senso che il metodo non esclude che qualche filosofo mangi troppo a lungo. Ma semplici modifiche al metodo sono possibili introducendo ad esempio dei timer per evitare un sovra utilizzo delle risorse, dando luogo a versioni più sofisticate di questo algoritmo che non hanno alcuna starvation.

Riguardo alla cena dei 5 filosofi è sensato introdurre un timer mentre sarebbe davvero fuori luogo e maleducato assegnare loro delle priorità, ovvero privilegiare qualche filosofo a dispetto degli altri. Proprio ciò che avviene, ahi me, nei parchi giochi dove col semplice vile denaro si può saltare la fila, sistema a mio avviso davvero odioso ed esecrabile, perché offre un modello di comportamento sbagliato e ingiusto proprio ai più piccoli.
Ma ci sono casi in cui istituire delle priorità è invece desiderabile e positivo. Ad esempio una variazione sul tema dell’esempio della cena vede al posto del tavolo una rotonda stradale e al posto dei filosofi dei mezzi di trasporto. La situazione rimane identica fin tanto che i mezzi sono normali auto o moto. Ma cosa succede se alla rotonda arrivano contemporaneamente i mezzi di Figura 4, cioè due auto, un’autoambulanza, un’altra autoambulanza a sirene spiegate e una camionetta dei Vigili del Fuoco anch’essa a sirene spiegate?
È questo un caso in cui lo stesso Codice della Strada prevede delle priorità di transito. La motivazione profonda è il bene stesso della società: se passa per prima la camionetta dei Vigili del Fuoco, probabilmente più di una vita umana sarà messa in salvo, se segue l’ambulanza allarmata un’altra singola vita umana sarà salvata. Le altre auto devono aspettare questi due transiti importanti prima di occupare la rotonda, ivi compresa l’autoambulanza priva di sirena che è considerata alla stessa stregua di un’auto civile. Tuttavia sarebbe sensato, ancorché non obbligatorio, che gli automobilisti dessero comunque precedenza a quest’ultima, perché pur senza un soccorso in atto è comunque un mezzo che si sta muovendo per la tutela di tutti.

Figura 4. Rotonda autostradale con ingresso di utenti a diversa priorità.

In merito anche a quest’ultima considerazione, possiamo stabilire la seguente lista di priorità:

(i valori intermedi saranno assegnati ad altri mezzi, ad esempio auto dei Carabinieri, etc.)

In condizioni normali, ovvero con ingressi di utilizzatori con identica priorità, come è lecito pensare succeda nella stragrande maggioranza dei casi, la regola sarà una di quelle viste per la cena dei filosofi.
Invece in casi particolari come quello di Figura 4 l’allocazione della risorsa ‘rotonda autostradale’ deve essere modificata e risulta più complicata.
Al sopraggiungere di un mezzo con priorità più alta, il normale ‘scheduling’ verrà bloccato per asservire chi è sopraggiunto e ciò avverrà a catena per i casi più complessi come quello mostrato, basandosi rigorosamente sul valore di priorità.
La gestione riprenderà normalmente come per i filosofi a cena non appena gli utilizzatori con priorità maggiore avranno liberato la risorsa.
Nel caso dei computer, le auto possono essere pensate, ad esempio, come le porte USB: non ha senso considerarne una più prioritaria dell’altra e il processore ha da fare cose ben più importanti con regolarità che non asservire la comunicazione con periferiche esterne che a tali porte vengono collegate.
L’ambulanza allarmata è un po’ come la memoria del computer, se non la gestiamo con ragionevole priorità, i dati si perdono.
La camionetta dei vigili del fuoco è come il clock del sistema, ovvero il cuore pulsante del computer. Se le schede elettroniche non gestiscono per primo questo, tutto si ferma.

In definitiva può apparire sorprendente che un problema apparentemente semplice come questo porti ad algoritmi risolutivi piuttosto articolati e figli della logica matematica. Sta di fatto che la gestione delle risorse condivise all’interno di un computer è stato da sempre un annoso problema, inizialmente affrontato per via hardware tramite schede piuttosto complesse che implementavano “arbitri elettronici” per dare un ordine sensato alle richieste di utilizzo. In seguito l’aumentata capacità di calcolo dei computer parallelamente alla maggior velocità di esecuzione hanno permesso di spostare molta dell’elaborazione dell’arbitro dall’hardware al software (quello del Sistema Operativo).
Oggi nell’era del consumismo più sfrenato si è anche assistito alla messa in atto di una soluzione categorica: dotare ogni filosofo di una coppia di forchette, che oltre ad evitare tout-court il problema della condivisione delle risorse, limita il passaggio di microbi da un commensale all’altro.
Gli ingegneri chiamano questo modo (molto americano) di risolvere le cose “brute-force strategy” e, a parte il fatto che è applicabile solo in ristretti segmenti per motivi economici e di spazio, annichilisce tutto l’ingegno di chi ha elaborato algoritmi e strategie per risolvere i problemi in modo intelligente e arguto.
Molto meglio, insomma, tenere sempre sveglio il cervello e ottimizzare sistemi e programmi, sfruttando senza sprechi ciò che si ha a disposizione.

Marco Sartore

Nell'immagine di copertina il dipinto di Jean Huber intitolato "Le Dîner des philosophes"