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 necessariamente 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.

Semafori

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

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 valori negativi ma nella nostra trattazione consideriamo il caso più generale in cui si ammettono valori negativi.

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

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

Mostriamo, in pseudocodice, le due funzioni:

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:

Vediamo un esempio di esecuzione con tre thread in esecuzione su 3 core distinti. Consideriamo un semaforo mutex inizializzato a 1:

Per semplicità scriviamo P e V invece che P(mutex) e V(mutex).
Indichiamo con – l’esecuzione fuori sezione critica e con = l’esecuzione in sezione critica. Si può osservare che fuori sezione critica i thread possono essere eseguiti senza limitazioni. La sezione critica invece viene sequenzializzata in modo che non ci sia mai più di un thread in esecuzione. Notare anche che la sezione critica può andare in parallelo con codice non critico.

Inizialmente T1 entra ed esce dalla sezione critica. In basso indichiamo lo stato del semaforo. S 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 avviene a T3. T1 esce dalla sezione critica eseguendo una V 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. Notare che per i valori negativi il valore assoluto corrisponde al numero di thread in coda.

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:

Se S è inizializzato a 0 (rosso) la P(S) di T2 sarà bloccante e di conseguenza il codice B 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 quindi 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:

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:

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. In questo caso specifico se viene schedulato per primo un consumatore, esso si bloccherà su P(piene) bloccando tutto gli altri thread sul mutex indefinitamente. Quando si inseriscono sezioni critiche bisogna quindi fare attenzione che non ci siano semafori bloccanti al loro interno.

Leave a Reply

Your email address will not be published. Required fields are marked *