7. Sincronizzazione tra processi

Con l'avvento della multiprogrammazione e dei sistemi multicore è nata la necessità di gestire l'accesso concorrente dei processi (in particolare i thread) alle risorse condivise. Solitamente infatti, quando i thread accedono ad un'area di memoria comune, si possono verificare errori nella consistenza (consistency) dei dati. Si parla in particolare di race condition laddove il contenuto di un'area di memoria condivisa o il valore letto da questa dipende dall'ordine di esecuzione dei processi. Ciò è chiaramente un problema in quanto fa sì che il codice non sia più univoco nelle operazioni svolte e nei risultati generati a parità di input (matematicamente non sarebbe più una funzione).
Esempio
Prendiamo in considerazione un modello in cui 2 processi vengono divisi in produttore e consumatore.

• Produttore: produce un messaggio
• Consumatore: consuma un messaggio

Si ha inoltre un'esecuzione concorrente tramite un buffer:

• Produttore: aggiunge al buffer (non posso aggiungere se il buffer è pieno)
• Consumatore: toglie dal buffer (non posso consumare se il buffer è vuoto)

Il tutto viene regolato da una variabile condivisa counter che indica il numero di elementi nel buffer.

• Produttore: aumenta counter di $1$ alla volta
• Consumatore: diminuisce counter di $1$ alla volta

Questo tuttavia introduce un problema: i due processi possono modificare counter contemporaneamente (es. macchina multiprocessore che esegue i thread allo stesso momento) e potrebbe capitare che i due processi aumentano e diminuiscono counter allo stesso tempo.

È importante quindi proteggere l'accesso alla cosiddetta sezione critica.

Sezione critica

La sezione critica è una porzione di codice in cui si accede ad una risorsa condivisa (per esempio la modifica di una variabile). Una qualsiasi soluzione al problema della sezione critica deve avere i seguenti requisiti:

• Mutua esclusione: Solo un processo alla volta può accedere alla sezione critica.
• Progresso: Solo i processi che vogliono entrare nella sezione critica possono partecipare per decidere chi di loro può entrare. Tale decisione deve avvenire in tempo definito. Per esempio, solo le persone che stanno aspettando per andare in bagno possono decidere chi entra, non persone esterne.
• Attesa limitata (bounded waiting): Esiste un numero massimo di volte consecutive per il quale un processo può aspettare prima di entrare in sezione critica (ovvero il processo deve poter entrare prima o poi).

Il problema di sincronizzazione può essere risolto tramite software o hardware. Entrambe le soluzioni richiedono codice aggiuntivo, ma la soluzione con HW è considerata generalmente più efficiente, in quanto, nonostante necessiti di apposito HW, usa meno risorse. Inoltre, le architetture moderne non supportano più la sincronizzazione software, in quanto la naturale evoluzione dell'HW ha reso tale soluzione molto più conveniente.
Vediamo ora nel dettaglio alcuni algoritmi per la sincronizzazione a livello software.

Soluzioni Software

Algoritmo 1

In questa soluzione sono presenti due soli processi. Uso la variabile turn come una sorta di chiave. Il processo che "possiede" il turn può entrare nella SC, mentre gli altri processi devono aspettare. Si garantisce così la mutua esclusione.
Questo tuttavia introduce ad un problema. Infatti se uno dei due processi non ha più necessità di entrare nella sezione critica, anche l'altro processo non può più entrare in essa, visto che il turn continua a tenerselo il processo che è andato via, ma non lo restituirà più agli altri processi, perchè sta eseguendo il codice dopo a turn = j. Questo porta ad una violazione del criterio del progresso.

PROCESS i;
int turn; // se turn == i allora è il turno di i
while (true)
{
    while (turn != i);      // aspetto che arrivi il mio turno
    #sezione critica
    turn = j;
    #sezione non critica
}

Algoritmo 2

In questa soluzione sono presenti due soli processi. Uso il vettore flag come una sorta di chiave. Il processo $i$ che setta la posizione $i$ del vettore a true può entrare nella SC, mentre gli altri processi devono aspettare che il processo $i$ reimposti a false la posizione $i$ di flag. In questo modo si risolve il problema del precedente algoritmo, ma se ne introducono altri.
Infatti se uno dei due processi va in errore e quindi si interrompe, lascia flag[i] a true, impedendo all'altro processo di accedere alla SC (andrà in loop nel while). Oppure, se un processo imposta flag[i] a true, e parte improvvisamente l'altro processo che imposta a sua volta flag[i] a true, avremo una situazione di stallo (i due processi vanno in loop nel while). Vedremo in seguito che queste situazioni vengono dette deadlock.

PROCESS i;
boolean flag[2];  //inizializzato a false
while (true)
{
    flag[i] = true;  //vuole entrare nella SC
    while (flag[j] == true);    // aspetta che flag[j] == false
    #sezione critica
    flag[i] = false;  //sono uscito dalla SC
    #sezione non critica
}

Algoritmo 2 - variante

La soluzione è simile a quella precedente ma abbiamo invertito le istruzioni della sezione di entrata. Qui però si introduce un nuovo problema, violando così la mutua esclusione. Infatti entrambi i processi possono trovarsi nella SC se eseguono in sequenza il while prima di impostare la flag[i] a true (cioè entrano nel while ma si interrompono prima di settare flag[i] a true.

PROCESS i;
boolean flag[2];
while (true)
{
    while (flag[j] == true);    // aspetta che flag[j] == false
    flag[i] = true;  //vuole entrare nella SC
    #sezione critica
    flag[i] = false;  //sono uscito dalla SC
    #sezione non critica
}

Algoritmo 3

In questa soluzione sono presenti due soli processi. Uso sia la variabile turn che il vettore flag. Il processo deve avere sia turn che flag[i] a true per entrare nella SC. Entrambi i processi potrebbero avere flag impostata a true ma solo uno dei due avrà il turn. Questa soluzione rispetta i $3$ criteri della sezione critica ed è chiamato algoritmo di Peterson (Peterson's algorithm).

PROCESS i;
int turn;  //per decidere a chi tocca
boolean flag[2];  //per capire chi è interessato alla SC, è inizializzato a false
while (true)
{
    flag[i] = true;  //vuole entrare nella SC
    turn = j;  //ma se l'altro processo vuole entrare, che faccia pure
    //se l'altro processo vuole entrare ed è il suo turno, aspetto
    while (flag[j] == true && turn == j);
    #sezione critica
    flag[i] = false;
    #sezione non critica
}

Dimostrazione

• Mutua esclusione:
  • $P_i$ entra nella SC $⟺$ flag[j] == false || turn == i
  • Se $P_i$ e $P_j$ sono entrambi nella SC, allora flag[j] = flag[i] = true
  • Ma $P_i$ e $P_j$ non possono aver superato entrambi il while perché turn = j oppure turn = i
  • Quindi solo uno dei due processi può essere nella SC
• Progresso e attesa limitata:
  • Se $P_j$ non è pronto per entrare nella SC allora flag[j] = false e $P_i$ può entrare
  • Se $P_j$ ha impostato flag[j] = true e si trova nel while allora turn = i oppure turn = j
  • Se turn = i allora $P_i$ può entrare nella SC
  • Se turn = j allora $P_j$ può entrare nella SC
  • In ogni caso $P_j$ esce dalla SC imposta flag[j] = false e quindi $P_i$ può entrare nella SC
  • Quindi $P_i$ può entrare nella SC al massimo dopo un'entrata di $P_j$

Abbiamo vinto!

Algoritmo del fornaio

Questo algoritmo risolve il problema con $N$ processi. Sostanzialmente il processo prende un numero, e quello con numero minore viene servito. Nella soluzione finale si gestiscono anche situazioni di numero identico (può accadere), usando un confronto a due livelli (numero, i).

Algoritmo del fornaio 0.1

In questa prima versione dell'algoritmo non viene rispettata la mutua esclusione, visto che l'assegnamento del numero non è atomica. Infatti può accadere che i processi eseguano la funzione max() ma si interrompono prima di fare l'assegnamento a number[i]. Di conseguenza più processi avranno lo stesso numero. Questo problema viene risolto nella versione 0.2.

PROCESS i; //i va da 0 a n-1
int number[N]; //vettore con "numeri presi", è inizializzato a 0
while (true)
{
	//scelgo il numero dopo all'ultimo numero preso, come al supermercato
    number[i] = max(number[0], ..., number[N-1]) + 1;
    for (j = 0; j < N; j++)
    {
	    //se number[j] == 0 vuol dire che ha finito (ha buttato il biglietto) dunque controllo il prossimo processo
	    //se ho un numero minore al processo che sto controllando passo a vedere il prossimo processo
        // altrimenti aspetto
        while (number[j] != 0 && number[j] < number[i]);
    }
    #sezione critica
    number[i] = 0;
    #sezione non critica
}

Algoritmo del fornaio 0.2

Questo algoritmo risolve il problema della versione precedente, utilizzando un ulteriore array (di bool) per far capire agli altri processi che sto scegliendo il numero. Però 2 o più processi potrebbero avere lo stesso numero, visto che max() non è atomica. Dunque si viola anche qui il criterio della mutua esclusione. Questo problema viene risolto nella versione 1.0.

PROCESS i;
bool choosing[N];
int number[N];
while (true)
{
    choosing[i] = true;
    number[i] = max(number[0], ..., number[N-1]) + 1;
    choosing[i] = false;
    for (j = 0; j < N; j++)
    {
        while (choosing[j] == true);
        while (number[j] != 0 && number[j] < number[i]);
    }
    #sezione critica
    number[i] = 0;
    #sezione non critica
}

Algoritmo del fornaio 1.0

Questo algoritmo risolve il problema della versione precedente. Infatti, per situazioni di numero identico (può accadere), si usa un confronto a due livelli (numero, i). Questa soluzione rispetta le 3 proprietà della sezione critica, anche se poco pratica. Tuttavia, questa soluzione spreca tanto tempo di utilizzo di CPU, visto che i processi ciclano nel while finchè la sezione critica non diventa nuovamente accessibile. Questa è chiamata busy waiting.

PROCESS i;
bool choosing[N];
int number[N];
while (true)
{
    choosing[i] = true;
    number[i] = max(number[0], ..., number[N-1]) + 1;
    choosing[i] = false;
    for (j = 0; j < N; j++)
    {
        while (choosing[j] == true);
        while (number[j] != 0 && number[j] < number[i] 
                || (number[j] == number[i] && j < i) );
    }
    #sezione critica
    number[i] = 0;
    #sezione non critica
}

Soluzioni Hardware

Visto che il problema è l'accesso alla sezione critica, si potrebbe risolvere il problema disattivando gli interrupt quando entro nella SC, ma questo vorrebbe dire che il processo prende il controllo di tutto e se il test per l’accesso è “lungo”, gli interrupt devono essere disabilitati per troppo tempo.
Dunque la soluzione HW definitiva è realizzata definendo particolari istruzioni che sono atomiche, ovvero sono eseguite in un unico ciclo di istruzioni e non possono essere interrotte. Le uniche due istruzioni atomiche sono la test-and-set e la swap, che utilizzate correttamente garantiscono una soluzione al problema della sezione critica.
Quali sono dunque i vantaggi e gli svantaggi di una soluzione hardware?

• Vantaggi
  • Scalabilità: Una soluzione hardware è indipendente dal numero di processi coinvolti
  • Posso estendere questa soluzione a $N$ sezioni critiche
• Svantaggi
  • Abbiamo una maggiore complessità rispetto alle soluzioni software visto che l'utilizzo di tali funzioni non è banale per un programmatore
  • Le soluzioni che implementano direttamente le funzioni sopra citate sono tutte basate su attesa attiva (busy waiting), cioè la tecnica per cui un processo aspetta in un ciclo infinito il verificarsi di una condizione per poi passare alle istruzioni successive (considerato dannoso), con conseguente spreco di CPU.

Per risolvere questi problemi sono stati introdotti i semafori, ovvero variabili intere (o binarie nel caso dei mutex o semafori binari) che i processi condividono e che sono modificabili solo attraverso le sopracitate operazioni atomiche.

Test-and-set

La test-and-set prende un valore come argomento e lo imposta a true, restituendo poi il vecchio valore

bool TestAndSet(bool &var)
{
    bool temp;
    temp = var;
    var = true;
    return temp;
}

Vediamo ora un esempio di utilizzo di questa funzione.

Utilizzo

// lock è una variabile globale inizializzata a false
bool lock;

while (true)
{
    // passa solo il primo processo che arriva e trova lock = false
    //gli altri settano il lock a true ma tanto lo è già, dunque TestAndSet() ritorna true
    while (TestAndSet(lock) == true);
    #sezione critica
    lock = false;
    #sezione non critica
}

La funzione fa il suo dovere, tuttavia potrebbe accadere che il primo processo esce dalla SC e ci ritorna subito dopo, ripetendo la situazione all'infinito. Viene dunque violato il criterio di attesa limitata. Come soluzione a questo problema è stata introdotta la test-and-set con attesa limitata. Di seguito ne è riportato un esempio.

Test-and-set con attesa limitata

boolean waiting[N];  //inizializzato a false
boolean lock;  //inizializzato a false
while (1) {
	waiting[i] = TRUE; 
	key = TRUE; 
	while (waiting[i] && key) { 
		//soltanto un processo riuscirà ad entrare, mutua esclusione garantita
		key = TestAndSet(lock);
	} 
	waiting[i] = FALSE;
	#sezione critica 
	j = (i+1) % N;
	while (j != i && !waiting[j]) {
		//se processo diverso da me e non sta aspettando, chiedo a quello successivo
		j = (j+1) % N;
	}
	if (j == i)
		lock = FALSE;
	else 
		waiting[j] = FALSE;
	#sezione non critica
}

Swap

La swap effettua semplicemente uno scambio di valori tra due variabili.

void Swap(bool &a, bool &b)
{
    bool temp;
    temp = a;
    a = b;
    b = temp;
}

Vediamo ora un esempio di utilizzo di questa funzione.

Utilizzo

Il processo che arriva e scambia dummy da true a false può entrare.

// lock è una variabile globale inizializzata a false
bool lock;

while (true)
{
    dummy = true;   // variabile locale al processo
    do
    {
        // Gli altri processi continuano a scambiare true con true e non
        // accedono alla SC finché P_i non pone lock = false
        Swap(lock, dummy);
    } while (dummy == true);    // quando dummy = false Pi accede alla SC
    #sezione critica
    lock = false;
    #sezione non critica
}

Anche qui abbiamo lo stesso problema del test-and-set, visto che viene violato il criterio di attesa limitata (manca l’equivalente della variabile turn). Inoltre non viene risolto il problema di busy waiting, visto che i processi potrebbero dover aspettare molto tempo prima di accedere alla sezione critica. Bisogna quindi utilizzare il #Test-and-set con attesa limitata.

Semafori

Per risolvere i problemi hardware precedentemente citati sono stati introdotti i semafori, ovvero variabili intere (o binarie nel caso dei mutex o semafori binari) che i processi condividono e che sono modificabili solo attraverso le sopracitate operazioni atomiche. Si fa normalmente uso di due funzioni (denominiamo $S$ la variabile intera a cui accediamo):

• Signal: V(s)
  • incrementa il valore di $S$ di $1$
• Wait: P(s)
  • tenta di decrementare il valore di $S$ di $1$
  • se $S=0$ si blocca ed aspetta che diventi maggiore di $0$, per poi decrementarlo.

Come detto prima, esistono i semafori binari e i semafori interi (o generici). Vediamoli ora più nel dettaglio.

Semafori binari

Vediamo ora l'implementazione “concettuale” di un semaforo binario. Nella realtà non è proprio implementato così.

P(s):
	while (s == false); // attesa
	s = false;
V(s):
	s = true;

Semplicemente se $s==false$, $P(s)$ continua a ciclare nel while finchè $s$ non viene settato a true da $V(s)$.

Nota: I semafori binari hanno lo stesso potere espressivo di quelli a valori interi.

Ovviamente qui manca l'atomicità delle operazioni. Dobbiamo quindi utilizzare la swap o ancora meglio la test-and-set (ricordiamo che la Swap ha il problema della busy waiting).

Implementazione con busy waiting

Implementazione della Wait:

/* s inizializzato a TRUE */
P(bool &s) {
	key = false;
	do {
		Swap(s, key);
	} while(key == false);
}

Implementazione della Signal:

/* s inizializzato a TRUE */
V(bool &s) {
	s = true;
}

Qui solo un processo riuscirà ad entrare nella sezione critica, visto che sarà il primo a fare la Swap tra s che sarà true e key che sarà false. I successivi processi troveranno s impostata a false e continueranno a scambiare false con false finchè s non verrà impostato nuovamente a true.

Semafori interi

Vediamo ora l'implementazione “concettuale” di un semaforo intero. Nella realtà non è proprio implementato così.

P(s):
	while (s == 0); // attesa
	s--;
V(s):
	s++;

Semplicemente se $s==0$, $P(s)$ continua a ciclare nel while finchè $s$ non diventa almeno $\ge 1$.

Ovviamente qui manca l'atomicità delle operazioni. Dobbiamo quindi utilizzare la swap o ancora meglio la test-and-set (ricordiamo che la Swap ha il problema della busy waiting).

Implementazione con busy waiting

Di seguito è riportata una possibile implementazione che soffre di busy waiting. Questo perchè $P$ e $V$ sono implementati usando la swap.

Implementazione della Wait:

bool mutex; /* Sem. binario iniz. TRUE */
bool delay; /* Sem. binario iniz. FALSE */

P(int &s) {
	P(mutex); //per proteggere s da un'altra modifica, garantisco la mutua esclusione
	s = s - 1;
	if (s<0) {
		//orco!! Ho decrementato s quando non potevo O_O
		V(mutex); //aspetta che libero la risorsa
		P(delay); //e mi rimetto in attesa attiva, non garantisco l'attesa limitata
	}
	else
		V(mutex); //garantisco il progresso
}

Implementazione della Signal:

bool mutex; /* Sem. binario iniz. TRUE */
bool delay; /* Sem. binario iniz. FALSE */

V(int &s) {
	P(mutex);
	s = s + 1;
	if (s<=0) {
		//vado a vedere se incrementando il valore del semaforo e s<=0
		//se questo è vero vuol dire che qualcuno è in attesa, perchè è scemo e ha fatto s-- quando era a 0
		//dunque faccio V(delay) per liberarlo
		V(delay);
	}
	V(mutex);
}

Cerchiamo ora di capire cosa succede nel codice sopra. Quando un processo vuole cambiare il valore di s deve eseguire prima una $P(s)$ per impedire agli altri processi di accedere^[1], poi cambiare il valore di s e successivamente impostare mutex a true per far accedere anche gli altri processi. Tuttavia questa implementazione non segue l'implementazione "concettuale" menzionata precedentemente, e decrementa s senza verificare se sia $>0$. Il controllo invece lo fa dopo aver fatto il decremento. Se si accorge di aver decrementato s e non poteva farlo allora libera subito l'accesso al semaforo e si mette in attesa che venga fatta una $V(delay)$ all'interno di $V(s)$. Infatti quando viene effettuata una signal essa controlla se ci sono stati processi che avevano fatto il decremento anche se non potevano (fa l'$if(s<=0)$), e li libera, impostando delay a true.

$P$ e $V$ garantiscono l'atomicità, visto che solo un processo alla volta entra nella sezione critica. Tuttavia, come detto sopra, visto che ci stiamo affidando alla swap abbiamo il solito problema di busy waiting ed un processo potrebbe continuare ad occupare la risorsa senza lasciarla neanche per un po' agli altri 😠.

Implementazione senza busy waiting

Qual è il problema nell'implementazione precedente?
Mettiamo caso che $10$ processi abbiano decrementato s fino a farlo arrivare a $-10$. Appena verrà fatto un $V(delay)$ dalla signal, solo uno tra questi $10$ processi verrà liberato, ma non si sa quale. Quindi potrebbe accadere che un processo venga liberato, riprenda subito la risorsa e che si metta nuovamente in attesa. Magari viene fatto un ulteriore $V(delay)$ e di nuovo quello stesso processo si libera e riprende subito la risorsa.
Dobbiamo allora implementare una coda così quel processo dovrà aspettare e permettere anche gli altri di utilizzare la risorsa.

In questo esempio definiamo una struct Sem, che è fatta nel seguente modo:

typedef struct {
	int value; //il valore del semaforo
	PCB* list; //una lista che contiene gli identificativi dei processi
} Sem;

Implementazione della Wait, simile a quella precedente:

bool mutex; /* Sem. binario iniz. TRUE */

P(Sem &s){
	P(mutex); //garantisco la mutua esclusione
	s.value = s.value - 1;
	if (s.value < 0) {
		//orco!! Ho decrementato s quando non potevo O_O
		V(mutex); //aspetta che libero la risorsa
		append (process i, s.List); //non faccio V(delay) ma mi aggiungo alla lista di attesa, garantendo l'attesa limitata
		sleep(); //mette il processo nello stato di waiting, rilasciando volontariamente la CPU
	}
	else
		V(mutex); //garantisco il progresso
}

Implementazione della Signal, simile a quella precedente:

bool mutex; /* Sem. binario iniz. TRUE */

V(Sem &s){
	P(mutex);
	s.value = s.value + 1;
	if (s.value <= 0) {
		V(mutex); 
		//rimuovo il processo che sta aspettando da più tempo dalla coda e me lo salvo in p
		PCB *p = remove(s.List);
		wakeup(p); //metto il processo p nello stato ready, se richiede subito la risorsa deve fare la fila
	}
	else
		V(mutex);
}

Dunque invece di aspettare in attesa attiva con la $V(delay)$ come nell'implementazione precedente, con la sleep() mi tiro fuori dai processi pronti (la sleep() mi permette di lasciare volontariamente la CPU e non rientrare nella coda dei processi pronti, rischiando di ottenere di continuo l'accesso alla risorsa).
Questa soluzione, oltre alla mutua esclusione, implementa quindi la bounded waiting. Utilizzando una FIFO infatti posso tirare fuori il primo processo che è entrato così non deve aspettare all'infinito. Ovviamente se utilizzassimo una LIFO avremmo potenzialmente un attesa infinita, visto che il povero processo che è entrato subito, se trovasse $s<0$, non prenderebbe praticamente mai la CPU.

Applicazioni

Possiamo quindi distinguere gli usi principali dei semafori in base al loro valore iniziale. Vediamo ora alcuni esempi per capire meglio.

Semaforo binario con valore iniziale $1$ (mutex)

Quando utilizziamo un semaforo binario con valore iniziale $=1$, vogliamo essenzialmente proteggere una sezione critica per $n$ processi, come abbiamo visto in tutti gli esempi sopra.

Esempio

// Valore iniziale di s = 1 (mutex)

while(true)
{
    P(s);
    # sezione critica
    V(s);
    # sezione non critica
}

Semaforo binario con valore iniziale $0$

Quando utilizziamo un semaforo binario con valore iniziale $=0$, siamo nella situazione di voler sincronizzare una o più operazione tra i processi.

Esempio 1

In questo esempio abbiamo due processi $P_1$ e $P_2$ che devono sincronizzarsi rispetto all’esecuzione di due operazioni $A$ e $B$. Vogliamo fare in modo che $P_2$ possa eseguire $B$ soltanto dopo che $P_1$ ha eseguito $A$. Come possiamo fare?

Di sicuro dobbiamo inizializzare $s$ a $0$ come detto sopra, così impediamo a $P_2$ di eseguire subito $B$. Proviamo allora nel seguente modo.

// Valore iniziale di s = 0

P1 {
	...
	A
	V(s);
	...
}

P2 {
	...
	P(s);
	B
	V(s);
	...
}

Sembra funzionare no? 😄. In realtà si ma c'è un problema. $P_1$ di sicuro esegue $A$ per primo, visto che se $P_2$ eseguisse per primo rimarrebbe bloccato ($s$ è $0$ e la $P(s)$ di $P_2$ decrementa $s$, ma non può quindi aspetta). Il problema è la $V(s)$ dopo $B$, perchè riporta $s$ a $1$ e $B$ potrebbe ripartire subito dopo. Noi vogliamo che venga eseguito sempre prima $A$ di $B$ (quindi esecuzioni del tipo $AAA$ o $ABAA$ ma non $ABB$), ma questa soluzione non garantisce questo. Rimuoviamo allora $V(s)$ da $P_2$.

// Valore iniziale di s = 0

P1 {
	...
	A
	V(s);
	...
}

P2 {
	...
	P(s);
	B
	...
}

Soluzione corretta! 🤓

Esempio 2

In questo esempio abbiamo due processi $P_1$ e $P_2$ che devono sincronizzarsi rispetto all’esecuzione di una sola operazione $A$. Vogliamo fare in modo che $P_1$ esegui per primo $A$, poi $P_2$, poi $P_1$ e così via.

Dunque la soluzione precedente non va più bene, visto che $P_1$ potrebbe eseguire $A$ più volte consecutivamente. Dobbiamo allora utilizzare $2$ semafori! In questo modo alterniamo l'incremento e il decremento di essi in modo che $A$ venga eseguito esattamente prima da $P_1$ e poi da $P_2$.

// Valore iniziale di s1 = 1
// Valore iniziale di s2 = 0

P1 {
	...
	P(s1);
	A
	V(s2);
	...
}

P2 {
	...
	P(s2);
	A
	V(s1)
	...
}

Esempio 3

In questo esempio abbiamo due processi $P_1$ e $P_2$ che devono sincronizzarsi rispetto all’esecuzione di due operazioni $A$ e $B$. Vogliamo fare in modo che $P_1$ esegui per primo $AAAA$, poi che $P_2$ esegui $BB$, poi $P_1$ esegui $AAAA$ e così via.

bool s1 = 1;
bool s2 = 0;
int c1 = 0;
int c2 = 0;

P1 {
	while(1) {
		P(s1);
		A
		c1++;
		if(c1 % 4 == 0)
			V(s2);
		else
			V(s1);
	}
	...
}

P2 {
	while(1) {
		P(s2);
		B
		c2++;
		if(c2 % 2 == 0)
			V(s1)
		else
			V(s2)
	}
}

Abbiamo i due semafori binari $s1$ e $s2$ per decidere se far partire il processo $P_1$ o il processo $P_2$ e le variabili $c1$ e $c2$ per far stampare 4 volte $A$ e 2 volte $B$. Ovviamente questo esempio è generalizzabile con $n$ volte $A$ e $m$ volte $B$.

Limitazioni

Vediamo ora alcuni problemi e limitazioni dei semafori.

Il problema principale è il deadlock (blocco critico), che avviene quando un processo è bloccato in attesa di un evento che solo lui può generare. Eccone un esempio:

// Valore iniziale di s = 1
// Valore iniziale di q = 1

P1 {
	P(s);
	P(q);
	//operazioni
	V(s);
	V(q);
}

P2 {
	P(q);
	P(s);
	//operazioni
	V(q);
	V(s);
}

In questo esempio se parte $P_1$ ed esegue tutte le righe di codice allora non succede niente di male. Ma se parte $P_1$ e fa solo la $P(s)$, poi parte $P_2$ che fa la $P(q)$, poi di nuovo $P_1$ e poi subito $P_2$ siamo in una situazione di stallo, dato che $P_1$ aspetta che $q$ venga incrementata e $P_2$ aspetta che $s$ venga incrementata. Ma questo non accadrà mai!
Un'altra situazione di deadlock avviene quando un processo fa la $P(s)$ ma non la rispettiva $V(s)$.

Un altro problema è lo starvation, ovvero l'attesa indefinita all'interno di un semaforo. Questo avviene quando non si garantisce l'attesa limitata e di conseguenza alcuni processi non riescono mai eseguire le loro operazioni.

Infine, l’utilizzo dei semafori presenta alcune complicazioni come la difficoltà nella scrittura dei programmi e la scarsa "visibilità" della correttezza delle soluzioni.
In alternativa, vengono utilizzati specifici costrutti forniti da linguaggi di programmazione ad alto livello, come:

• Monitor (Hoare, 1974), che vedremo in seguito
• Classi synchronized di Java
• CCR (Conditional Critical Region)

Esempio di utilizzo dei semafori - problemi classici

Problema del produttore – consumatore

Il problema descrive due processi, uno produttore ed uno consumatore che condividono un buffer di dimensione fissata. Il produttore genera dati e li deposita nel buffer di continuo. Contemporaneamente, il consumatore consuma i dati prodotti, prelevandoli di volta in volta dal buffer. Il problema è assicurare che il produttore non elabori nuovi dati se il buffer è pieno, e che il consumatore non cerchi dati se il buffer è vuoto. Quanti semafori dobbiamo usare?

Dobbiamo usare esattamente 3 semafori:

• mutex, binario inizializzato a TRUE (mutua esclusione per buffer)
• empty, intero inizializzato a $N$ (dice al produttore quanti item ancora può produrre, e lo blocca se empty è zero)
• full, intero inizializzato a $0$ (dice al consumatore quanti item ancora può consumare, e lo blocca se full è zero)

bool mutex = true;
int empty = n;
int full = 0;

PRODUCER {
	while (1) {
		produce item
		P(empty);
		P(mutex);
		deposit item
		V(mutex);
		V(full);
	}
}

CONSUMER {
	while (1) {
		P(full);
		P(mutex);
		remove item
		V(mutex);
		V(empty);
		consume item;
	}
}

Problema dei dining philosophers

Il problema descrive $N$ filosofi, che passano la vita mangiando e pensando. Nello specifico:

• Abbiamo un tavolo con $N$ bacchette e una ciotola di riso
• Se un filosofo pensa non interagisce con gli altri
• Se un filosofo ha fame prende 2 bacchette e inizia a mangiare, ma può prendere solo le bacchette che sono alla sua destra e alla sua sinistra
• Il filosofo può prendere una bacchetta alla volta
• Se non ci sono 2 bacchette libere il filosofo non può mangiare
• Quando un filosofo termina di mangiare rilascia le bacchette

Vediamo ora una soluzione intuitiva a questo problema.

Dati condivisi da ogni filosofo:

• semafori $s[N]$ inizializzati a $1$ (ogni elemento rappresenta una bacchetta)
• $P(s[j])=$ cerco di prendere la bacchetta $j$
• $V(s[j])=$ rilascio la bacchetta $j$

int semafori[N]; //ogni elemento inizializzato a 1

FILOSOFO[i] {
	while(1) {
		P(s[i]);
		P(s[(i+1) % N]);
		…
		// mangia
		…
		V(s[i]);
		V(s[(i+1) % N]);
		…
		// pensa
		…
	}
}

In questa soluzione però è possibile che si verifichi un deadlock, visto che se ogni filosofo prendesse la bacchetta di destra (cioè ogni filosofo fa $P(s[i])$ e poi parte un altro filosofo), rimarrebbero tutti ad aspettare che si liberi quella di sinistra, che nessuno puo’ rilasciare.

Elenchiamo ora un paio di semplici soluzioni che risolvono il deadlock, ma che non risolvono esattamente il problema originale.

1. Permettere solo a $N-1$ filosofi di mangiare contemporaneamente
2. Soluzione asimmetrica:
   • I filosofi in posizioni pari prendono la bacchetta sinistra seguita dalla destra
   • I filosofi in posizioni dispari fanno viceversa
3. Si passano un token
4. Permettere ai filosofi di prendere la forchetta solo se entrambi disponibili

Soluzione corretta

Vediamo ora la soluzione corretta al problema originale.

Ogni filosofo può trovarsi in $3$ stati:

• Pensante (THINKING)
• Affamato (HUNGRY)
• Mangiante (EATING)

Dati condivisi da ogni filosofo:

bool semaphore mutex = 1;
int semaphore f[N]; //binario, inizializzato a 0
int stato[N] = THINKING;

Void Philosopher (int i) {
	while (1) {
		Think(); //fa uno sleep(random())
		Take_fork(i);
		Eat(); //fa uno sleep(random())
		Drop_fork(i);
	}
}

Void Take_fork (int i) {
	P(mutex);
	stato[i] = HUNGRY;
	test(i);
	V(mutex);
	P(f[i]);
}

Void test (int i) {
	if (stato[i] == HUNGRY && 
	    stato[i-1] != EATING && 
	    stato[i+1] != EATING)
	{
	    stato[i] = EATING;
		V(f[i]);
	}
}

Void Drop_fork (int i)
{
	P(mutex);
	stato[i] = THINKING;
	test((i-1)%N);
	test((i+1)%N);
	V(mutex);
};

Questa soluzione però ha un problema. Infatti con un numero pari di filosofi abbiamo il problema di starvation, ossia può presentarsi il caso in cui a coppie i filosofi non mangiano, provocando un attesa indefinita. Se invece abbiamo un numero dispari di filosofi questo non succede. Un modo per risolvere questo problema è utilizzare le priorità.

Problema dello sleepy barber

Il problema descrive un negozio che ha una sala d’attesa con $N$ sedie, ed una stanza con la sedia del barbiere. Nello specifico:

• In assenza di clienti, il barbiere si addormenta
• Quando entra un cliente
  • Se le sedie sono occupate, il cliente se ne va
  • Se il barbiere e’ occupato il cliente si siede
  • Se il barbiere e’ addormentato, il cliente lo sveglia

Dati condivisi dal barbiere e dai clienti:

int semaphore customers = 0; // sveglia il barbiere
bool semaphore barbers = 0; // stato del barbiere
bool semaphore mutex = 1; // protegge la sezione critica
int waiting = 0; // conta i clienti in attesa
int N; // il numero di clienti

BARBER{
	while(1) {
		P(customers); // aspetta che entri un cliente
		P(mutex); //aspetta che il cliente modifichi waiting
		waiting--; //faccio entrare il cliente nella stanza
		V(barbers); //sono pronto per tagliargli i capelli
		V(mutex); 
		cut hair;
	}
}

COSTUMER{
	while(1) {
		P(mutex); //per modificare waiting
		if (waiting < N) {
			waiting++;
			V(customers); //sveglia!!
			V(mutex);
			P(barbers); //pronto per il taglio
			get haircut;
		}
		else
			V(mutex); //non c'è posto
	}
}

Monitor

Nonostante i semafori siano uno strumento molto potente, in grado di risolvere qualsiasi problema di sincronizzazione, non sempre per il programmatore è semplice capire come utilizzarli per risolvere il problema e risulta comunque difficile dimostrare la correttezza della soluzione implementata. Possono infatti esserci degli errori che si verificano solo in particolari condizioni di esecuzione e per questo difficili da individuare. Per questi motivi i linguaggi di programmazione di alto livello spesso forniscono altri strumenti come i monitor, le classi syncronized di Java e le CCR (Conditional Critical Region). In questa sezione vedremo i monitor nel dettaglio.

I monitor sono un tipo di dato astratto, una sorta di "classe" che incapsula variabili e procedure che saranno protette in automatico con la mutua esclusione. In questo modo il programmatore non si deve preoccupare di utilizzare lock o semafori mutex per potervi accedere. Le variabili dichiarate in un monitor formano lo stato del monitor e sono visibili solo all’interno del monitor stesso. Le funzioni definite nel monitor possono accedere solamente alle variabili dello stato, oltre che a quelle dichiarate localmente alla funzione ovviamente. Inoltre il monitor garantisce che un solo processo alla volta possa essere attivo all’interno del monitor, dunque il programmatore non deve codificare esplicitamente la mutua esclusione.

Per permettere ad un processo di attendere all’interno del monitor e quindi di sincronizzarsi con gli altri processi, il monitor è provvisto di un ulteriore meccanismo di sincronizzazione dato dal costrutto condition. Sono essenzialmente delle variabili (dette appunto condizioni) interne al monitor sulle quali si possono invocare la $signal()$ e la $wait()$, simili alle operazioni $P()$ e $V()$ dei semafori.
Per esempio, mettiamo caso che sia dichiarata la variabile condition x. Similmente ai semafori, il processo che invoca la $x.wait()$ è bloccato fino all’invocazione della corrispondente $x.signal()$ da parte di un altro processo.

Riassumendo:
$\star$ Comportamento della $wait()$

• Blocca sempre il processo che la chiama, tuttavia si può decidere con altro codice se chiamarla o no (i.e., if..then..else)

$\star$ Comportamento della $signal()$

• Sveglia esattamente un processo
  • Se più processi in attesa, lo scheduler decide quale processo può entrare
  • Se nessun processo in attesa, nessun effetto

C'è da fare però una precisazione sulla $signal()$, visto che nel suo caso ci sono due comportamenti possibili:

• Signal and wait: Il processo che ha chiamato signal attende e l’esecuzione passa al processo che si è sbloccato.
• Signal and continue: Il processo che ha chiamato signal continua la sua esecuzione ed esce dal monitor (in questo caso signal deve essere l’ultima istruzione della procedura).

Problema del produttore/consumatore con i monitor

Producer() {
	while (TRUE) {
		make_item(); // crea nuovo item
		ProducerConsumer.enter(); // chiamata alla funzione enter
	}
}

Consumer() {
	while (TRUE) {
		ProducerConsumer.remove(); // chiamata alla funzione remove
		consume_item() ; // consuma item
	}
}

monitor ProducerConsumer {
	condition full, empty;
	int count = 0;
	
	entry enter() {
		if (count == N)
			full.wait(); //se buffer è pieno, blocca
		
		put_item(); // mette item nel buffer
		count = count + 1; // incrementa count
		
		if (count == 1) //solo una signal verrà intercettata
			empty.signal(); // se il buffer era vuoto, sveglia il consumatore
	}

	entry remove(){
		if (count == 0)
			empty.wait(); // se buffer è vuoto, blocca
			
		remove_item(); // rimuove item dal buffer
		count = count - 1; // decrementa count
		
		if (count == N-1) //solo una signal verrà intercettata
			full.signal(); // se il buffer era pieno, sveglia il produttore
	}
}

Limitazioni

Per concludere la trattazione sui monitor bisogna evidenziare che, sebbene essi siano più semplici da utilizzare per il programmatore, pochi linguaggi li implementano e per funzionare necessitano di memoria condivisa.

Classi syncronized in Java

Java come linguaggio ad alto livello fornisce un suo meccanismo per la sincronizzazione dei processi ovvero la keyword syncronized. Un metodo syncronized è un metodo che può essere eseguito da una sola thread alla volta. Ciò viene realizzato mantendendo un singolo lock (detto monitor, ma da non confondere con i monitor trattati in precedenza) per oggetto. Se il metodo syncronized è statico allora il lock viene messo sulla classe. E’ possibile inoltre definire una sezione critica su qualsiasi blocco utilizzando sempre la keyword syncronized. Sono disponibili inoltre altri metodi di sincronizzazione disponibili nella classe Object e quindi ereditati da tutti gli oggetti, ovvero wait(), notify(), notifyAll().

Problema del produttore/consumatore con le classi syncronized

public class BoundedBuffer {
	Object[] buffer;
	int nextin;
	int nextout;
	int size;
	int count;

	//costruttore
	public BoundedBuffer(int n) {
		size = n;
		buffer = new Object[size];
		nextin = 0;
		nextout = 0;
		count = 0;
	}

	public synchronized deposit(Object x) { 
		while (count == size) wait();
		buffer [nextin] = x;
		nextin = (nextin+1) mod N;
		count = count + 1;
		notifyAll(); 
	}
	 
	public synchronized Object remove() {
		Object x;
		while (count = 0) wait(); 
		x = buffer[nextout];
		nextout = (nextout+1) mod N;
		count = count - 1;
		notifyAll(); 
		return x;
	}
}