6.1 Problema della variabile condivisa

Un classico problema di competizione molto semplice da definire è quello della variabile condivisa. Supponiamo di avere due processi, ma il discorso si può estendere al caso di più processi, e che entrambi possano accedere in lettura/scrittura ad una variabile condivisa x. Supponiamo che inizialmente questa variabile valga 0 e che i due processi concorrenti siano uguali, ossia eseguano lo stesso programma e che ad un certo punto entrambi eseguano un incremento della variabile condivisa x, con una istruzione C del tipo x=x+1, x++ o ++x.

Supponiamo inoltre che il linguaggio macchina nel quale viene tradotta questa istruzione sia piuttosto ridotto, sicché occorra passare attraverso un registro per effettuare l'incremento di una variabile in memoria. Detto questo registro R, x=x+1 diventa una sequenza di 3 operazioni di macchina eseguite in modo strettamente sequenziale:

Ciascuno dei due processi esegue, tra le altre cose, queste 3 istruzioni. Ogni processo ha un suo valore del registro R. Se vi è una sola CPU e quindi un solo registro fisico R, viene usata la tecnica di interleaving e il valore di R viene salvato nel descrittore del processo appena dopo averlo sospeso e viene copiato dal descrittore nel registro fisico R appena prima di riprendere l'esecuzione.

Ora supponiamo di essere così sfortunati che si verifichi la seguente sequenza di esecuzione. Le probabilità che vada proprio così possono anche essere poche, ma comunque è possibile e non è questa l'unica sequenza di esecuzione che fa manifestare il problema di competizione.

Come vedete entrambi i processi hanno terminato la computazione x=x+1, eppure il valore di x, che inizialmente era 0, non è 2 bensì è rimasto ad 1. Abbiamo perso un conteggio. Se invece la sequenza di esecuzione fosse stata questa, allora x varrebbe 2 alla fine, che è il risultato che ci aspettiamo:

Poichè la sequenza di esecuzione è casuale e non possiamo fare affidamento che se ne verifichi una particolare, il risultato è non deterministico (non sappiamo se alla fine x varrà 1 oppure 2), che sicuramente è una situazione non desiderata.

Come risolvereste questo problema di interazione competitiva? La prima soluzione che viene in mente è la seguente: nessuno dei due processi deve essere interrotto mentre esegue l'incremento di x.

Ma è proprio necessario che il processo non debba essere interrotto? No, può essere interrotto, l'importante è che non venga interrotto nel mezzo dell'istruzione x=x+1 per eseguire l'istruzione x=x+1 dell'altro processo. Questa è la condizione necessaria e sufficiente e meno restrittiva che deve verificarsi per evitare del tutto il problema della competizione.

Come si può ottenere questo, in maniera del tutto indipendente dallo schedulatore? L'idea è la seguente: supponiamo di avere una variabile intera s che è il valore del semaforo. Il valore di questa variabile indica se la risorsa (nel nostro caso la variabile x) è libera (in tal caso s=1, ossia semaforo verde in un paragone automobilistico) oppure è occupata da un processo (caso s=0, vale a dire semaforo rosso). Questi sono gli unici due valori che s potrà assumere in questo esempio.

Il semaforo è una struttura dati che consiste di due campi: il suo valore s e un puntatore q al descrittore del processo che è in attesa sul semaforo (q sta per queue, coda), che inizialmente vale NULL ad indicare che nessun processo è in attesa sul semaforo. Questo non è il tipo di semaforo più generale possibile, ma è sufficiente per risolvere un problema di sola competizione tra due soli processi. Estenderemo in seguito la definizione di semaforo, per ora ne adottiamo una semplificata. Usando la notazione C per le strutture possiamo definire la struttura dati semaforo e una variabile sem di tipo semaforo correttamente inizializzata in questo modo:

#define RED   0
#define GREEN 1

struct semaphore
{ unsigned int s;
  struct descriptor *q;
};

struct semaphore sem={GREEN, NULL};

Su un semaforo sono disponibili solo due operazioni, dette primitive e così definite in linguaggio C:

void wait(struct semaphore* sem)
{ if (sem->s==0)
  { sem->q=puntatore al descrittore del processo corrente;
    sospendi il processo corrente (ponilo nello stato wait);
  }
  else
    (sem->s)--;
}

void signal(struct semaphore* sem)
{ if (sem->q!=NULL)
  { poni nello stato ready il processo il cui descrittore è sem->q;
    sem->q=NULL;
  }
  else
    (sem->s)++;
}

Queste non sono da confondere con le omonime funzioni di UNIX, è solo un caso che abbiano gli stessi nomi ma sono cose completamente diverse. Affinché il semaforo possa essere di utilità per risolvere i problemi di sincronizzazione, la wait() e la signal() devono essere azioni non interrompibili, o come si dice atomiche o indivisibili.

Entrambi i processi devono utilizzare lo stesso semaforo sem, che deve quindi risiedere in una zona di memoria condivisa. Si definiscono sezioni critiche le operazioni con cui i processi accedono a risorse comuni. La singola istruzione x=x+1 è una sezione critica.

Verifichiamo che se la sezione critica viene racchiusa tra le chiamate wait() e signal() non si può verificare il problema della competizione:

wait(&sem);
x=x+1;
signal(&sem);

Vediamo in questa tabella quello che succede quando si tende a verificare la stessa sequenza sfortunata che produce il problema che abbiamo illustrato prima. Studiate attentamente questa tabella:

Ci sono almeno tre cose fondamentali da notare: che il risultato della computazione ora è corretto (x vale 2), che il semaforo e tornato nello stato iniziale (verde e senza alcun processo bloccato in coda), pronto a sincronizzare eventuali altri processi che tramite il semaforo accedano alla risorsa condivisa e che il semaforo ha agito proprio al momento giusto: quando la wait() e la signal() vengono messe a guardia di una sezione critica, non è che la sezione critica non è interrompibile; può essere interrotta (ad es. perchè scade il quanto di tempo), ma non può subentrare un'altra sezione critica in competizione con la precedente, a causa della wait(). Compito del semaforo è semplicemente quello di assicurare che le operazioni di incremento di x da parte dei due processi, le sezioni critiche, non vengano eseguite in modo concorrente. Il semaforo non pone altre restrizioni non necessarie, in particolare sarebbe sovrabbondante imporre l'atomicità dell'intera sezione critica. In questo caso la sezione critica è molto semplice, ma in generale le sezioni critiche possono consistere di molte istruzioni e potrebbe risultare inefficiente non poter interrompere l'esecuzione operando la multiprogrammazione anche all'interno della sezione critica. Si devono solo evitare le competizioni e i semafori, se correttamente usati, fanno giusto questo, cioè evitano che sezioni critiche che accedono alla stessa risorsa che deve essere usata in modo mutuamente esclusivo girino concorrentemente, producendo quindi problemi di competizione. Se ricordate i diagrammi temporali visti prima, e immaginate che si riferiscano a due sezioni critiche invece che a due interi processi, distinte tramite i colori rosso e verde, il semaforo assicura solo che l'esecuzione avvenga in maniera non concorrente (ultimi due diagrammi). Come potete vedere nell'ultimo diagramma, ci possono essere anche più segmenti dello stesso colore che rappresentano la stessa sezione critica, senza che vi sia concorrenza tra le due sezioni critiche.

Ad essere sincero, devo ammettere che ho imbrogliato un po' nel proporre l'esempio semplice dell'incremento della variabile condivisa, ma il lettore mi perdonerà l'imbroglio perchè è stato fatto solo per semplificare l'analisi. In realtà infatti nel linguaggio macchina dell'architettura i386, x=x+1 verrà tradotta in una singola istruzione (incl x) e persino x=x+2 corrisponde ad un'unica istruzione di macchina (addl $2,x). Siccome l'esecuzione di una singola istruzione avviene in maniera atomica, perchè è l'hardware che assicura questo, il problema di competizione non può mai verificarsi in pratica con un semplice incremento, per lo meno su questa architettura e su molte altre che hanno una istruzione di incremento veloce. Tuttavia si potrà verificare anche sull'architettura i386 se invece di x=x+1 si ha qualcosa del tipo x=(x+1)*2 o più complicata. Comunque sia fatta la sezione critica, la soluzione al problema di sincronizzazione non cambia perchè si tratta sempre di un problema di competizione, quindi tutta la nostra discussione rimane in generale valida e necessaria. Difatti dobbiamo usare degli strumenti di sincronizzazione anche se la sezione critica consiste solo dell'istruzione x=x+1 perchè non possiamo fare affidamento su una caratteristica hardware particolare che eviti il verificarsi delle condizioni di gara: il nostro codice deve evitarle qualsiasi sia l'hardware che c'è sotto, deve essere portabile e mantenersi corretto quando viene utilizzato su altri tipi di macchine.

Potete immaginare moltissime altre situazioni in cui i processi interagenti entrano in competizione. Ad esempio supponiamo di avere un buffer condiviso da due processi: un buffer molto semplice è un array con associato un indice di fine, che individua la prima posizione libera. L'operazione di inserimento nel buffer consiste di due passi, da eseguirsi nel seguente ordine: inserire un certo elemento dati (ad es. un numero intero) nella posizione libera puntata dall'indice di fine e poi incrementare il puntatore alla fine per indicare la nuova posizione di inserimento. È facile rendersi conto che questa operazione di inserimento è una sezione critica: supponiamo per es. che il primo processo inserisce e poi viene sospeso, senza avere il tempo di incrementare l'indice di fine array, e che poi vada in esecuzione un secondo processo che pure inserisce nel buffer; quest'ultimo allora sovrascrive quello che il primo processo ha inserito, e abbiamo già provato che si è verificata una condizione di gara (race condition in inglese) tra i due processi, un altro modo con cui viene chiamato il problema della mutua esclusione.