Semafori

Premessa

Come sappiamo due funzioni in esecuzione in parallelo con memoria condivisa possono avere problemi di interferenza di sincronizzazione (dovuti a problematiche legate al tempo) e di competizione (dovuti a problematiche legate ai dati). Questo avviene sia quando siamo in uno scenario di interleaving (esecuzione concorrente) che di overlapping (esecuzione parallela).

Dal punto di vista più formale quando si scrive una applicazione in programmazione parallela, occorre soddisfare le condizioni di Bernstein:

R(f1) ⋂ R(F2) = ∅

R(F) ⋂ D(F2) = ∅

D(F1) ⋂ R(F2) = ∅

dove f1 e f2 sono le due funzioni parallele, R il rango e D il dominio delle funzioni. Più semplicemente, una funzione che scrive delle variabili non può essere eseguita in parallelo di una funzione che legge o scrive lo stesso insieme di variabili.

Compito del programmatore è quindi scrivere delle funzioni parallele che garantiscano mutua esclusione ed impediscano starvation (applicazione sempre in attesa) e deadlock (dipendenze cicliche). 

In conclusione le applicazioni parallele devono garantire la stessa correttezza che avrebbero se fossero eseguite come delle applicazioni sequenziali. 

Sezione critica

Per risolvere i problemi di parallelismo introduciamo il concetto di sezione critica.

Una sezione critica è una particolare porzione del codice che può essere eseguita solo da un limitato numero di thread in contemporanea, o uno soltanto. Questo concetto si applica esclusivamente ad applicazioni a memoria condivisa (come i thread, ma non come i processi).

La sezione critica garantisce quindi che una sola funzione (o un numero limitato) accedano a risorse condivise, per tutto il tempo necessario ad usare la risorsa condivisa, senza rischi di interferenza. Si veda in figura uno schema di accesso con un solo processo nella sezione critica.

Sono molti gli esempi nel mondo reale che presentano una qualche analogia con il concetto di sezione critica:

– un supermercato con una cassa: i clienti che hanno riempito il carrello in modo indipendente si devono mettere in coda alla cassa, venendo serviti uno solo alla volta. Dopo aver pagato tornano indipendenti.

– un ufficio postale con sportelli dove occorre prendere un numero di prenotazione, ed attendere il proprio turno venendo chiamati dal primo sportello libero.

– il casello autostradale con uno o più valichi di accesso, dove si formano code parallele per ciascuna corsia.

Nel codice si ha una sezione critica quando più thread hanno bisogno di accedere ad una variabile condivisa, ad esempio per poter modificare quella variabile. Ipotizziamo di avere una funzione che sarà eseguita da due thread che eseguono lo stesso codice:

void somma(int *b, int a) {
   int sum = a + *b;
   *b = sum;   
}

int main() {
  int b = 3;
   thread thread0 = thread(somma, &b, 5);
   thread thread1 = thread(somma, &b, 2);
   thread0.join();
   thread1.join();
   return 0;
}

La variabile b è letta e scritta da entrambi i thread, in istruzioni differenti. Come si può vedere il rango delle due funzioni coincide quindi ci si deve aspettare una qualche interferenza. Ad esempio potrebbe essere eseguita questa sequenza di istruzioni:

Il valore finale di b sarebbe 8 mentre gli effetti dell’ultima istruzione del thread 1 completamente annullati. Un’altra esecuzione (si ricorda che lo scheduling non è deterministico) l’ordine di esecuzione delle singole istruzioni potrebbe essere:

In questo caso b varrebbe 5 e sarebbe il thread 0 ad essere penalizzato. Già con un caso molto semplice, con una funzione di appena due righe di codice, possiamo avere comportamenti del tutto inaspettati.

La sezione critica nasce per questo: impedire che l’esecuzione sia “imprevedibile” e che porti quindi a risultati diversi da quelli attesi.

Per risolvere questo problema ci si affida ad una libreria di sistema operativo, detta semaforo. Sarà il sistema operativo che tramite il semaforo regolerà il traffico in entrata ed uscita dalla sezione critica.

Vediamolo in dettaglio.

Mutex (o semaforo binario)

Il semaforo binario, detto anche mutex, è una variabile che può essere modificata da un solo thread alla volta. E’ una variabile gestita dal sistema operativo, e il thread in esecuzione non ha quindi controllo sulla scrittura del mutex. Può semplicemente cercare di acquisirlo (lock), restando in attesa se occupato, e rilasciarlo, liberandolo per il thread successivo.

In pratica si entra nella sezione critica eseguendo un lock sul semaforo (che diventa “rosso”), si esegue la sequenza di operazioni critiche, e poi si rilascia il lock (il semaforo diventa “verde”).

mutex mtx;
...

mtx.lock(); 
/*
critical istructions
*/
mtx.unlock();

Se un thread richiederà il semaforo mentre il primo è ancora dentro la sezione critica, lo troverà “rosso”, quindi si fermerà ed attenderà che diventi verde. E’ il sistema operativo che fornisce questa funzionalità: tutti i thread che richiedono il lock del mutex sono messi in attesa che il semaforo sia sbloccato. Inoltre il sistema operativo garantisce che l’operazione avvenga in perfetta sincronia per tutti i processori, quindi anche in caso di richiesta contemporanea di un semaforo da parte di più processori, tutte le parallelizzazioni sono sospese. 

Il codice precedente diventa quindi:

mutex mtx;

void somma(int *b, int a) {
   mtx.lock();
   int sum = a + *b;
   *b = sum;  
   mtx.unlock(); 
}

int main() {
  int b = 3;
   thread thread0 = thread(somma, &b, 5);
   thread thread1 = thread(somma, &b, 2);
   thread0.join();
   thread1.join();
   return 0;
}

Se si esegue questo codice si otterrà che solo uno dei thread potrà eseguire la somma.

Semaforo di Dijkstra (semaforo generalizzato)

Il semaforo generalizzato (o semaforo di Dijkstra^[1]) è una estensione del semaforo binario che permette l’accesso alla sezione critica da parte di più di un thread alla volta. Operativamente il semaforo prevede un valore numerico (condiviso tra i thread) ed una coda di attesa. In C/C++ è gestita tramite due funzioni, P e V, che consentono l’accesso alla sezione critica ai thread.

P: questa funzione, eseguita dal thread, richiede l’accesso alla sezione critica.

void p(int *semaphore) {  
  if (*semaphore == 0) {
    unique_lock<mutex> lock(m);
    cv.wait(lock);    
  }
  (*semaphore)--;  
}

Unique lock e wait sono funzioni di sistema operativo.^[2]

Quando un thread vuole accedere alla sezione critica esegue una operazione p(int *semaphore) dove semaphore è la variabile condivisa che contiene il numero di thread attualmente disponibili. Per prima cosa diminuisce di 1 il valore del semaforo. Se questo valore è sotto 0, il thread si mette in attesa.

void v(int *semaphore) {    
  if ((*semaphore) == 0) {
    cv.notify_one();    
  }
  (*semaphore)++;  
}

Quando un thread esce dalla sezione critica, esegue una operazione v(int *semaphore) che aumenta di 1 il valore del semaforo. Se il valore è uguale a 0, il sistema operativo toglie il primo thread in attesa in coda e lo fa entrare in sezione critica. 

Poniamo di avere 3 thread ed un semaforo pari a 2. 

Questo significa che solo 2 thread in esecuzione possono entrare nella sezione critica. Il terzo thread si metterà in coda attendendo l’uscita di un qualsiasi altro thread nella sezione critica.

Una analogia col mondo reale è quella dell’ufficio postale, con ad esempio 3 sportelli che servono 3 persone, e una persona in attesa (col numero di prenotazione) che attende che si liberi il primo sportello.

Qui un esempio di semaforo di valore 3.

^[1] Dijikstra è stato uno dei più grandi informatici, inventore oltre che del semaforo (1965) anche del più noto algoritmo che prende il suo nome (che governa la distribuzione dei pacchetti nella rete Internet) e della teoria sulla verifica formale di un algoritmo. E’ noto per aver inventato (insieme a Wirth) la programmazione strutturata e infine per i suoi aforismi, come la famosa critica alla programmazione ad oggetti. 

^[2] La condition variable è oggetto che con l’istruzione wait() ferma il thread mettendolo in una coda e con l’istruzione notify() lo riattiva.