Tredicesima puntata del nostro viaggio
Come descritto nel post introduttivo alla computazione distribuita, un secondo problema rilevante è quello della sincronizzazione, in cui i vari esecutori non devono coordinare il loro lavoro, che ognuno svolge in maniera autonoma, ma devono evitare di intralciarsi nell’uso di risorse che servono a tutti.
Lo discutiamo attraverso l’esempio di un ufficio in cui due impiegati, Rossi e Bianchi, devono ognuno controllare le proprie pratiche senza doversi coordinare nella loro gestione. Assumiamo per semplicità che il loro lavoro consista solo nel controllo, seguito dal rifiuto o dall’approvazione della pratica in esame. L’approvazione della pratica avviene suggellando la decisione attraverso un timbro particolare, fatto da due parti che si trovano in due posti diversi. Se i due impiegati non attuano una qualche forma di sincronizzazione, si possono trovare nella situazione in cui uno ha preso una parte del timbro, l’altro ha preso l’altra parte e nessuno dei due può approvare la pratica. Escludiamo strategie particolari che le persone potrebbero attuare in casi come questi, per esempio andando a trovare l’altro responsabile e concordando che uno dei due ceda la sua parte all’altro per fargli timbrare la sua pratica per poi ricevere indietro il timbro completo per approvare la propria.
Questo è il più semplice esempio possibile di sincronizzazione. Può essere risolto facendo eseguire a entrambi gli agenti uno stesso algoritmo, detto di Peterson, che non riporto interamente qua per la sua complessità formale, rimandando al mio libro La rivoluzione informatica per la sua spiegazione di dettaglio e fornendo nel seguito una descrizione intuitiva.
L’algoritmo assume che vi siano tre “variabili globali” che, nel contesto di un ufficio quale quello che stiamo considerando, possiamo considerare come tre bacheche che tutti gli impiegati possono leggere. Ogni bacheca è identificata da un nome: Rossi_vuole_timbrare, Bianchi_vuole_ timbrare, Adesso_è_il_turno_di. All’inizio dell’algoritmo in ognuna delle prime due bacheche è scritto FALSO, mentre ciò che è scritto sulla terza è irrilevante.
L’algoritmo ripete in continuazione la sequenza di azioni descritta nel seguito.
L’impiegato che deve approvare la sua pratica dichiara che vuole timbrare, cioè scrive VERO sulla bacheca che inizia col suo nome, e scrive il nome dell’altro impiegato sulla bacheca che esprime di chi è il turno.
Dopo di questo, controlla se è contemporaneamente vero che l’altro impiegato vuole timbrare e che è il suo turno, e in caso positivo (chiamiamo “semaforo rosso” questa eventualità) si mette ad aspettare che questa situazione diventi falsa.
Quando ciò accade (cioè non vi è più il semaforo rosso) allora (1) va a prendere entrambi le parti del timbro, (2) approva la pratica, (3) rilascia entrambe le parti del timbro. Queste tre azioni vengono tecnicamente definite “sezione critica”, perché sono quelle che devono essere eseguite solo da un automa per volta, per non causare la situazione di blocco descritta all’inizio.
Successivamente all’esecuzione della sezione critica l’impiegato scrive FALSO sulla bacheca che inizia col suo nome e continua a controllare le sue pratiche.
Terminata la descrizione dell’algoritmo facciamo vedere che effettivamente la sezione critica può essere eseguita solo da un automa alla volta e che solo un automa alla volta può essere nello stato di attesa.
Assumiamo che Bianchi stia eseguendo la sua sezione critica e che Rossi sia in attesa. Allora Rossi potrà entrare nella sua sezione critica solo quando Bianchi uscirà dalla sua e scriverà FALSO sulla bacheca Bianchi_vuole_timbrare (rendendo così falsa la condizione che teneva Rossi in attesa, ovvero rimuovendo il semaforo rosso). Quando questo accade, Bianchi si trova a controllare pratiche e Rossi entra nella sezione critica: dopo un po’ anche Rossi uscirà dalla sua sezione critica e passerà a controllare pratiche.
Immaginiamo adesso che, mentre Bianchi continua a controllare pratiche, Rossi dichiari che vuole timbrare. Se Bianchi continua sempre a controllare pratiche allora Rossi non deve attendere (perché su Bianchi_vuole_timbrare c’è scritto FALSO) ed entra nella sua sezione critica. Se, in questa fase in cui Rossi è nella sua sezione critica, anche Bianchi dichiara di voler timbrare, allora troverà il semaforo rosso (perché su Rossi_vuole_timbrare c’è scritto VERO e inoltre sulla bacheca del turno c’è scritto che è il turno di Rossi) e rimarrà in attesa. Siamo quindi nella situazione precedentemente descritta, a parti invertite tra Rossi e Bianchi.
Vediamo invece che succede se, proprio subito dopo che Rossi ha dichiarato che vuol timbrare, anche Bianchi scrive VERO sulla bacheca Bianchi_vuole_timbrare. Allora non può accadere che entrambi vadano nello stato di attesa perché, anche se tentano di scrivere contemporaneamente sulla bacheca che esprime di chi è il turno potranno scrivere solo uno dopo l’altro e alla fine sulla bacheca ci sarà scritto o Bianchi o Rossi. Nel primo caso è Rossi che va in attesa e Bianchi entra nella sezione critica, nel secondo caso, avviene il contrario. Se invece il tentativo di scrittura sulla bacheca del turno, dopo aver dichiarato entrambi la volontà di timbrare, non è contemporaneo ma avviene prima (ad esempio) quello di Rossi, allora sarà Rossi a entrare in attesa, ma solo momentaneamente, perché quando poi Bianchi arriva a scrivere sulla bacheca del turno renderà falsa la condizione che bloccava Rossi nello stato di attesa, consentendo a quest’ultimo di entrare nella sua sezione critica mentre lui (Bianchi) va in attesa.
Nel prossimo post esamineremo il terzo importante problema della computazione distribuita, quello del consenso.
( I post di questa serie sono basati sul libro dell’Autore La rivoluzione informatica: conoscenza, consapevolezza e potere nella società digitale, al quale si rimanda per approfondimenti. I lettori interessati al tema possono anche dialogare con l’Autore, su questo blog interdisciplinare. )