Semafori

Abbiamo visto come realizzare la sezione critica con soluzioni puramente software o con l’ausilio di istruzioni hardware speciali. Queste ultime permettono di ottenere mutua esclusione tramite un ciclo “a vuoto” che attende l’acquisizione di un lock globale. Si ottengono i così detti spin-lock, ovvero codice che cicla finché non ottiene il lock.

Questo tipo di sincronizzazione non è efficiente per diverse ragioni:

• Ciclare a vuoto spreca tempo di CPU inutilmente;
• Le istruzioni hardware speciali semplificano la realizzazione degli spin-lock ma la loro realizzazione è complessa. Ad esempio in architetture multi-core è necessario, durante la loro esecuzione, bloccare l’accesso da parte di tutti i core, degradando le prestazioni.

Di fatto gli spin-lock si utilizzano nel codice dei sistemi operativi ma quasi mai a livello applicazione. Il sistema operativo o la jvm, nel caso di java, forniscono meccanismi di sincronizzazione più semplici ed efficaci che possono essere utilizzati per programmare applicazioni multi-threaded.

I semafori

I semafori furono proposti da Edsger Dijkstra nel 1965. Un semaforo altro non è che un contatore intero con una coda di attesa:

struct semaphore {
   int valore;
   thread *queue;
}

Come interpretiamo il valore di un semaforo S?

• S.valore > 0: il semaforo è verde. Il valore indica il numero di accessi consentiti prima che il semaforo diventi rosso;
• S.valore <= 0: il semaforo è rosso. Il valore (tolto il segno) indica il numero di thread in attesa sulla coda del semaforo.

NOTA: in alcune implementazioni i semafori non assumono mai un valore negativo e un semaforo rosso assume sempre il valore 0, indipendentemente dal numero di thread in attesa.

I semafori non vengono mai incrementati e decrementati direttamente ma solo tramite speciali funzioni che gestiscono la sincronizzazione dei thread:

• P(S) o wait(S): decrementa il valore del semaforo S. Se il semaforo era rosso già prima del decremento il thread attende sulla coda associata al semaforo;
• V(S) o post(S): incrementa il valore del semaforo S. Se ci sono thread in attesa sul semaforo, viene sbloccato il primo della coda.

Mostriamo, in pseudocodice, le due funzioni:

P(semaphore S) {
  S.valore--;
  if (S.valore<0)
    < Metti il thread corrente in attesa su S.queue >
}

V(semaphore S) {
  S.valore++;
  if (S.valore<=0)
    < Sblocca il primo thread in attesa su S.queue >
}

Sezione critica con i semafori

I semafori permettono di realizzare la sezione critica in modo estremamente semplice ed efficace. Il valore del semaforo indica il numero di accessi consentiti prima di diventare rosso. Nel caso della sezione critica solo un thread alla volta deve accedere, quindi utilizziamo un semaforo mutex che inizializziamo al valore 1. Per controllare l’accesso è sufficiente eseguire una P(mutex). All’uscita della sezione critica si esegue una V(mutex) per ripristinare il valore del semaforo e sbloccare un thread eventualmente in attesa:

thread T {
  ...
  P(mutex);
  < Sezione critica >
  V(mutex);
  ...
}

Esempio: sezione critica con tre thread in esecuzione

Vediamo un esempio di esecuzione con tre thread in esecuzione su 3 core distinti. Consideriamo un semaforo mutex inizializzato a 1 e per semplicità scriviamo P e V invece che P(mutex) e V(mutex):

T1 -----------P====V----P==============V--------------

T2 --------------------------P         +====V---------

T3 -------------------------------P         +====V----

mutex
 valore: 1    0    1    0   -1   -2   -1    0    1  
 queue:  _    _    _    _    |    |    |    _    _  
                             T2   T2   T3  
                                  |  
                                  T3 

Spiegazione:

• abbiamo indicato:
  • con - l’esecuzione fuori sezione critica;
  • con = l’esecuzione in sezione critica;
  • in basso, lo stato del semaforo mutex: valore (inizialmente 1) e coda (inizialmente vuota);
• T1 entra ed esce dalla sezione critica. In basso indichiamo lo stato del semaforo: mutex da 1 (verde) diventa 0 (rosso) e poi torna 1 (verde);
• poi T1 torna in sezione critica ponendo nuovamente a 0 (rosso) il semaforo;
• quando T2 cerca di entrare in sezione critica eseguendo una P(mutex) il semaforo viene decrementato (-1) e T2 va in attesa sulla coda. Lo stesso accade a T3;
• T1 esce dalla sezione critica eseguendo una V(mutex) e sblocca T2, il primo thread in coda portando il semaforo a -1;
• a sua volta T2 esce dalla sezione critica e sblocca T3 che riporterà il semaforo a 1 (verde) uscendo dalla propria sezione critica.

Osserviamo alcuni fatti interessanti:

• per i valori negativi di mutex il valore assoluto corrisponde al numero di thread in coda;
• fuori sezione critica (indicato da -) i thread possono essere eseguiti senza limitazioni, ad esempio i thread sono contemporaneamente in esecuzione all’inizio;
• la sezione critica viene sequenzializzata in modo che non ci sia mai più di un thread in esecuzione. Si può notare infatti che il simbolo = non  compare mai contemporaneamente su più thread: viene realizzata la mutua esclusione;
• la sezione critica può andare in parallelo con codice non critico: il simbolo = può andare assieme al simbolo -.

Attendere un altro thread

Esistono altri utilizzi dei semafori, oltre alla realizzazione della sezione critica.

Supponiamo che T2, prima di eseguire la porzione di codice < D > debba attendere che T1 abbia eseguito il codice < A >. Possiamo realizzare questa semplice sincronizzazione con un semaforo S inizializzato a 0 come segue:

semaphore S=0;

  T1 {                    T2 {
    < A >                    < C >
    V(S) ------------------> P(S)
    < B >                    < D >
  }                       }

Spiegazione: poiché S è inizializzato a 0 (rosso) la P(S) di T2 sarà bloccante e di conseguenza il codice < D > sarà eseguito necessariamente dopo < A >. Quindi, < A > e < C > possono andare in parallelo. Lo stesso vale per < B > e < D >. Anche < B > e < C > possono andare in parallelo in quanto la V(S) non è mai bloccante. Notare che se la V(S) è eseguita prima della P(S) il semaforo diventerà 1 (verde) e la successiva P(S) non sarà bloccante.

Questo semplice esempio ricorda la sincronizzazione che si ottiene nello scambio di messaggi: la V(S) è come una send asincrona mentre la P(S) come una receive sincrona. Abbiamo evidenziato questa analogia con una freccia dalla V(S) alla P(S).

Regolare l’accesso a risorse

Abbiamo visto che un semaforo inizializzato a 1 può essere utilizzato per regolare l’accesso alla sezione critica. In generale, un semaforo iniziato a MAX permette MAX accessi prima di diventare bloccante. Possiamo quindi dare la seguente interpretazione alle operazioni P e V:

• P(S): richiesta di risorsa: se ce ne è almeno una disponibile viene assegnata, altrimenti si attende;
• V(S): rilascio di risorsa: se ci sono thread in attesa il primo viene sbloccato.

Ad esempio se abbiamo 3 stampanti possiamo usare S inizializzato a 3 e quando i primi 3 thread eseguiranno P(S) per allocarsi una stampante, il semaforo diventerà rosso bloccando eventuali altri thread che desiderino stampare. Finita la stampa, l’esecuzione di V(S) sbloccherà il primo thread in attesa.

Produttore e consumatore con semafori

Proviamo ora a risolvere il problema del produttore-consumatore usando i semafori. Abbiamo due sincronizzazioni da realizzare: quando il buffer è pieno il produttore deve attendere, per evitare di sovrascrivere; quando il buffer è vuoto il consumatore deve attendere, per evitare di leggere celle non ancora scritte.

La soluzione è di usare due semafori distinti che regolano l’accesso a risorse: vuote inizializzato al numero MAX di celle inizialmente vuote e piene inizializzato a 0 in quanto inizialmente non abbiamo celle piene.

Ecco la soluzione per un produttore e un consumatore:

semaphore piene=0, vuote=MAX;

Produttore {
  while(1) {
    < produce d >
    P(vuote); // richiede una cella vuota
    buffer[inserisci] = d;
    inserisci = (inserisci+1) % MAX;
    V(piene); // rilascia una cella piena
  }
}
 
Consumatore {
  while(1) {
    P(piene); // richiede una cella piena
    d = buffer[preleva];
    preleva = (preleva+1) % MAX:
    V(vuote); // rilascia una cella vuota
    < consuma d >
  }
}

Tanti produttori e consumatori

Cosa accade se abbiamo tanti produttori e tanti consumatori?

Potrebbero esserci interferenze in scrittura e lettura sul buffer. Ad esempio due produttori potrebbero scrivere sulla stessa cella buffer[inserisci], sovrascrivendosi l’uno con l’altro, e poi entrambi incrementare inserisci. Oppure potrebbero interferire sull’incremento di inserisci, come abbiamo discusso nelle lezioni precedenti.

La soluzione è di proteggere il codice che aggiorna variabili condivise con una sezione critica. Ecco la soluzione con tanti produttori e tanti consumatori utilizzando un semaforo mutex inizializzato a 1:

semaphore piene=0, vuote=MAX, mutex=1;

Produttore {
  while(1) {
    < produce d >
    P(vuote); // richiede una cella vuota
    P(mutex); // entra in sezione critica
    buffer[inserisci] = d;
    inserisci = (inserisci+1) % MAX;
    V(mutex); // esce dalla sezione critica
    V(piene); // rilascia una cella piena
  }
}
 
Consumatore() {
  while( {
    P(piene); // richiede una cella piena
    P(mutex); // entra in sezione critica
    d = buffer[preleva];
    preleva = (preleva+1) % MAX:
    V(mutex); // esce dalla sezione critica
    V(vuote); // rilascia una cella vuota
    < consuma d >
  }
}

Notare che se scambiamo P(piene) o P(vuote) con P(mutex) il primo thread che entra acquisisce il mutex e se si blocca in sezione critica potrebbe creare uno stallo. Ad esempio, se venisse schedulato per primo un consumatore, esso si bloccherebbe su P(piene) bloccando, a sua volta, tutti gli altri thread sul mutex indefinitamente. Quando si inseriscono sezioni critiche bisogna quindi fare attenzione che non ci siano semafori bloccanti al loro interno.