I processori e/o i compilatori possono riordinare le istruzioni o ritardare l’aggiornamento della memoria principale per ottimizzare la velocità dei programmi.
Per risolvere questo problema, bisogna agire a livello hardware: per questo sono state introdotte le barriere di memoria.
Definizione: barriera di memoria
Una barriera di memoria (o recinzione di memoria, in inglese memory barrier o memory fence) è un’istruzione che impedisce al processore di riordinare le letture e scritture di memoria al di là della barriera, garantendo che tutte le operazioni di memoria prima della barriera siano completate e visibili alle altre unità di elaborazione prima di eseguire le operazioni di memoria dopo la barriera.
Istruzioni hardware atomiche
Molte delle moderne architetture offrono particolari istruzioni che permettono di effettuare operazioni di lettura e scrittura contemporaneamente in modo atomico, cioè come un’unità non interrompibile, permettendo così la risoluzione del problema della sezione critica in modo relativamente semplice.
Si implementa attraverso una variabile booleana condivisa, detta lock, che indica se la risorsa contesa è libera o occupata, e una funzionetest_and_set che prende come argomento il lock, lo imposta a true (per indicare che la risorsa è occupata) e restituisce il suo valore precedente:
Prima di entrare nella sezione critica, il programma esegue un ciclo che esegue la test_and_set sul lock e, se quest’ultimo indica che la risorsa era precedentemente libera (lock == true), allora può entrare nella sezione critica, altrimenti aspetta finché non si libera attraverso il meccanismo del busy waiting:
while (test_and_set(&lock)); // Busy waiting// Esecuzione della sezione criticalock = false;// Esecuzione della sezione non critica
Si implementa attraverso tre variabili, value di tipo puntatore a intero ed expected e new_value di tipo intero, e una funzionecompare_and_swap che le prende come argomenti. La funzione si salva il valore di value in una variabile temporaneatemp di tipo intero e, se questo corrisponde a quello di expected, viene sostituito con new_value; infine restituisce il valore originale:
int compare_and_swap(int *value, int expected, int new_value) { int temp = *value; if (*value == expected) *value = new_value; return temp;}
Prima di entrare nella sezione critica, il programma esegue un ciclo che esegue la compare_and_swap sul lock e, se quest’ultimo indica che la risorsa era precedentemente libera (lock == 0), allora può entrare nella sezione critica, altrimenti aspetta finché non si libera attraverso il meccanismo del busy waiting:
while (compare_and_swap(&lock, 0, 1) != 0);// Esecuzione della sezione criticalock = 0;// Esecuzione della sezione non critica
Una variabile atomica è una variabile su cui sono possibili operazioni di lettura e scrittura solo in modo atomico, cioè senza la possibilità di poter essere interrotte.
Esempio di uso delle variabili atomiche
L’incremento o il decremento di un valore intero può produrre una Race condition: le variabili atomiche possono essere utilizzate per garantire la mutua esclusione in situazioni in cui potrebbe esserci una Race condition su una singola variabile durante il suo aggiornamento, come quando un contatore viene incrementato.
L’algoritmo di Peterson richiede che le unità condividano i seguenti dati:
una variabile di tipo intero dal nome turn che segnala di chi è il turno per poter accedere alla propria sezione critica (avrà come unici valori possibili 0 e 1):
int turn;
e
un array di booleani di lunghezza 2 dal nome flag che indica se l’unità di elaborazionei-esima è pronta a entrare nella sezione critica (cioè flag[i] == true se è pronta a entrare, flag[i] == false altrimenti):
assegna a flag[0] il valore true per segnalare che è pronta per accedere alla sua sezione critica e
attribuisce a turn il valore 1, conferendo così a P1 la facoltà di entrare nella sua sezione critica.
Se P1 proverà a fare la stessa cosa contemporaneamente, una delle due unità sovrascriverà il valore di turn dell’altra: quello che ne risulterà vincitore stabilirà chi sarà autorizzato a entrare per prima nella propria sezione critica, mentre l’altra continuerà a verificare di continuo se è arrivato il suo turno attraverso il meccanismo del busy waiting.
Si desume da queste due osservazioni che P0 e P1 sono impossibilitate a eseguire con successo le rispettive istruzioni while approssimativamente nello stesso momento: turn, infatti, può valere 0 o 1, ma non entrambi. Ne consegue che non è possibile che entrambe entrino contemporaneamente: una delle due unità di elaborazione deve attendere finché l’altra non esce.
Lo spinlock (da spin, girare in inglese, e lock, lucchetto in inglese) è una soluzione software al problema della sezione critica che previene le Race condition attraverso l’implementazione di una variabile booleana condivisa, il lock, che indica se la risorsa condivisa è occupata (lock == true) o meno (lock == false) ed è gestita attraverso due funzioni atomiche:
La funzioneacquire che effettua un busy waiting su lock finché questa non si libera (cioè finché non risulta vero che lock == false):
acquire() { while (lock); // Busy waiting lock = true;}
Nonostante il problema del busy waiting, gli spinlock hanno il vantaggio di non rendere necessario alcun cambio di contesto (operazione che può richiedere molto tempo) quando un’unità di elaborazione deve attendere un lock e tornano quindi utili quando si prevede che i lock verranno trattenuti per tempi brevi.
typedef struct { int value; struct process *list;} semaphore;
Quando un’unità di elaborazione invoca la funzionewait e trova che il value non è positivo, deve attendere, ma anziché effettuare un busy waiting si mette in coda nella list e blocca se stessa con una sleep:
wait(semaphore *s) { s->value--; if (s->value < 0) { // Aggiungi quest'unità di elaborazione a s->list; sleep(); }}
Quando un’altra unità di elaborazione invoca la funzionesignal, incrementa il value e se ci sono unità bloccate le preleva dalla list e le riattiva con una wakeup:
signal(semaphore *s) { s->value++; if (s->value <= 0) { // Togli un'unità di elaborazione P da s->list; wakeup(P); }}
I semafori trovano applicazione nel controllo dell’accesso a una data risorsa presente in un numero finito di esemplari. Dopo aver inizialmente impostato il value al numero di risorse disponibili:
I processi che desiderino utilizzare una risorsa invocanowait, decrementandone così il valore, e dopo l’esecuzione di questa eseguono la propria sezione critica:
wait(s);// Esecuzione della sezione critica
I processi che restituiscono una risorsa dopo aver eseguito la propria sezione critica, invece, invocanosignal, incrementandone il valore:
// Esecuzione della sezione criticasignal(s);
Quando il semaforo vale 0, tutte le risorse sono occupate e i processi che ne richiedano l’uso dovranno bloccarsi fino a che il semaforo non ritorni positivo.
Osservazione: implementazione della lista dei processi bloccati
La lista dei processi che attendono a un semaforo si può facilmente realizzare con un puntatore al relativo PCB di quei processi gestiti attraverso una coda FIFO. In generale, tuttavia, si può usare qualsiasi criterio d’accodamento; il corretto uso dei semafori non dipende dal particolare criterio adottato.
Osservazione: semafori nei sistemi mono-elaborazione e multi-elaborazione
Come già abbiamo detto, le operazioni sui semafori devono essere eseguite in modo atomico: si deve garantire che nessuna coppia di processi possa eseguire operazioni wait e signal contemporaneamente sullo stesso semaforo. Si tratta di un problema della sezione critica e in un sistema mono-elaborazione lo si può risolvere semplicemente inibendo le interruzioni durante l’esecuzione di wait e signal, dal momento che rappresentano i soli elementi di disturbo: non vi sono istruzioni eseguite da altre unità di esecuzione. Finché non si riattivino le interruzioni, dando la possibilità allo scheduler di riprendere il controllo della CPU, il processo corrente continua indisturbato la sua esecuzione.
Nei sistemi multi-elaborazione sarebbe necessario disabilitare le interruzioni di tutte le unità di elaborazione, perché altrimenti le istruzioni dei diversi processi in esecuzione su unità di elaborazione distinte potrebbero interferire fra loro. Tuttavia, disabilitare le interruzioni in questo caso può essere complesso e causare un notevole calo delle prestazioni. È per questo che, per garantire l’esecuzione atomica di wait e signal, i sistemi smp devono mettere a disposizione altre tecniche di realizzazione dei lock (per esempio, CAS o spinlock).
Monitor
Benché i semafori costituiscano un meccanismo pratico ed efficace per la sincronizzazione dei processi, il loro uso scorretto può generare errori difficili da individuare, in quanto si manifestano solo in presenza di particolari sequenze di esecuzione che non si verificano sempre, ossia a causa di race condition.
Altri errori nell’uso dei semafori possono nascere invece da un involontario errore di programmazione o essere causato dalla mancata collaborazione del programmatore. Per esempio, supponiamo che un processo capovolga l’ordine in cui sono eseguite le istruzioni wait e signal, in questo modo:
signal(s);
// Esecuzione della sezione critica
wait(s);
Questi esempi chiariscono come sia facile incorrere in errori quando i programmatori utilizzano i semafori in maniera scorretta nel risolvere il problema delle sezioni critiche. Una strategia per gestire tali errori consiste nell’incorporare questi strumenti di sincronizzazione in costrutti ad alto livello che li astragga, come il monitor.
typedef monitor { var v1; var v2; // Dichiarazione di altre variabili var vn; function f1(); function f2(); // Dichiarazione di altre funzioni function fn();}
monitor conto_corrente { double saldo := 0.0 procedure preleva(double importo) { if importo < 0.0 then error "L'importo del prelievo deve essere un numero positivo" else if saldo < importo then error "Fondi insufficienti per il prelievo" else saldo:= saldo - importo } procedure versa(double importo) { if importo < 0.0 then error "L'importo del versamento deve essere un numero positivo" else saldo:= saldo + importo } double function saldo() { return saldo }}
Variabili di condizione
In questa definizione di monitor appena vista non basta per assicurare il suo corretto uso: per esempio, riprendiamo il problema del produttore-consumatore. Se dovessimo usare un monitor nella sua implementazione, avremmo che il consumatore può entrare nel monitor anche quando il buffer è vuoto, ma non potendo consumare rimane in attesa finché non trova qualcosa da consumare. Tuttavia, dato che il monitor è già occupato dal consumatore, il produttore non può accedervi e di conseguenza non può produrre nuovi elementi: ciò causa uno stallo tra i due.
Questo problema può essere arginato dall’uso di particolari variabili, dette variabili di condizione, che permettono al consumatore di bloccarsi, rilasciando il monitor e permettendo al produttore di accedervi.
Definizione: variabile di condizione
Una variabile di condizione (in inglese condition variable) è una variabile presente in un monitor che consente a un’unità di esecuzione, mentre si trova all’interno del monitor, di sospendere la propria esecuzione fino a quando una certa condizione logica sui dati del monitor non risulta vera, permettendo temporaneamente ad altre unità di esecuzione l’accesso al monitor.
Le uniche funzioni eseguibili su una variabile di condizionex sono:
la x.wait() con cui l’unità di esecuzione che la invoca rimane sospesa finché un’altra non invoca
la x.signal() che risveglia una delle unità di esecuzione rimaste sospese dopo l’esecuzione della x.wait().
Osservazione: differenza tra la signal dei semafori e dei monitor
Se non esistono unità di esecuzione sospese dopo l’esecuzione di una x.wait(), l’esecuzione di una x.signal() in un monitor non ha alcun effetto, vale a dire che lo stato di x resta immutato, come se la funzione non fosse stata eseguita.
Ciò non equivale alla signal di un semaforo, poiché questa influisce sempre sullo stato del semaforo incrementando il suo value.
Facciamo finta che un processoP0 abbia invocato l’istruzionex.signal() e che esista un processoP1 sospeso associato alla variabile di condizionex (e cioè che ha eseguito x.wait()). Chiaramente, se al processo sospeso P1 si permette di riprendere l’esecuzione, il processo segnalante P0 è costretto ad attendere, altrimenti P0 e P1 sarebbero contemporaneamente attivi all’interno del monitor. Sussistono allora due possibilità la signal-and-wait e la signal-and-continue.
Signal-and-continue è una politica di gestione dei monitor nel caso dell’uso di variabili di condizione in cui l’unità di esecuzione che esegue la signal continua la propria esecuzione, lasciando che l’altra unità risvegliata aspetti il suo turno. È contrapposta alla politica signal-and-wait.
Osservazione: realizzazione di un monitor per mezzo di semafori
A ogni monitor si associa un semaforos, il cui value è inizializzato a 1, per garantire la mutua esclusione; un processo deve eseguire wait(s) prima di entrare nel monitor e signal(s) dopo aver lasciato il monitor.
Useremo nella nostra implementazione la politica signal-and-wait. Poiché un processo che esegue una signal deve attendere finché il processo risvegliato si metta in attesa o lasci il monitor, introduciamo un altro semaforo next inizializzato a 0, su cui i processi che eseguono una signal possono autosospendersi. Per contare i processi sospesi al semaforonext, usiamo una variabile interacounter:
semaphore s = 1;semaphore next = 0;int next_count = 0;
Quindi, ogni funzionef() esterna al monitor si sostituisce col seguente codice:
wait(s);// Corpo di f()if (counter > 0) signal(next);else signal(s);
In questo modo si assicura la mutua esclusione all’interno del monitor.
L’operazione x.signal() si può realizzare come segue:
if (x_counter > 0) { counter++; signal(x_semaphore); wait(next); counter--;}
Ordine di ripresa
Se più unità di esecuzione in un monitor sono sospese alla variabile di condizionex e se qualcun’altra esegue l’operazione x.signal(), è necessario stabilire quale tra le unità sospese debba essere riattivata per prima.
Una semplice soluzione consiste nell’usare una politica FIFO, secondo cui l’unità di esecuzione che attende da più tempo viene ripreso per primo. Tuttavia, in molti casi ciò non risulta adeguato, ragion per cui in questi casi si può implementare una priorità attraverso un numero di priorità.
Il valore di p viene valutato al momento dell’esecuzione della wait e viene poi associato alla relativa unità di esecuzione sospesa che l’ha eseguita. Quando si esegue x.signal(), si riattiva l’unità cui è associato il numero di priorità più basso.
Valutazione delle soluzioni
Abbiamo descritto diversi strumenti di sincronizzazione utilizzabili per risolvere il problema della sezione critica. Con una corretta implementazione e un utilizzo appropriato, questi strumenti possono essere efficacemente impiegati per garantire la mutua esclusione e affrontare problemi di liveness. Con la diffusione di programmi concorrenti in grado di sfruttare la potenza dei moderni sistemi multicore viene prestata sempre maggior attenzione alle prestazioni degli strumenti di sincronizzazione. Cercare di identificare quale strumento utilizzare e quando, tuttavia, può essere una sfida improba. In questo paragrafo presentiamo alcune semplici strategie per determinare quando utilizzare specifici strumenti di sincronizzazione.
Le soluzioni hardware descritte nel Paragrafo 6.4 sono considerate di livello molto basso e vengono tipicamente utilizzate come base per la costruzione di altri strumenti di sincronizzazione, come i lock mutex. Tuttavia, ci si è concentrati di recente sull’uso dell’istruzione cas per costruire algoritmi privi di lock che forniscono protezione dalle race condition senza l’overhead dei lock. Sebbene queste soluzioni lock-free stiano guadagnando popolarità grazie al basso overhead e alla loro scalabilità, gli algoritmi sono spesso difficili da sviluppare e testare.
Gli approcci basati su cas sono considerati ottimistici: prima si aggiorna fiduciosamente una variabile e poi si utilizza il rilevamento delle collisioni per verificare se un altro thread stia aggiornando la stessa variabile contemporaneamente. In tal caso, si riprova ripetutamente l’operazione fino a quando la variabile non viene aggiornata correttamente e senza conflitti. Il lock mutex, al contrario, è considerato una strategia pessimistica: si presuppone che un altro thread stia aggiornando contemporaneamente la variabile e in modo pessimistico si acquisisce il lock prima di apportare qualsiasi aggiornamento.
Le seguenti linee guida identificano delle regole generali per distinguere le prestazioni della sincronizzazione basata su cas e della sincronizzazione tradizionale (come i lock mutex e i semafori) al variare del livello di contesa:
Nessuna contesa. Sebbene entrambe le opzioni siano generalmente veloci, la protezione cas sarà leggermente più veloce della sincronizzazione tradizionale.
Contesa moderata. La protezione cas sarà più veloce e in alcuni casi molto più veloce rispetto alla sincronizzazione tradizionale.
Alta contesa. Con carichi molto elevati, la sincronizzazione tradizionale sarà in definitiva più veloce della sincronizzazione basata su cas.
La contesa moderata è particolarmente interessante da esaminare. In questo scenario, l’operazione cas ha esito positivo per la maggior parte del tempo e, in caso di errore, itererà nel ciclo mostrato nella Figura 6.8 solo poche volte prima di avere successo. Per contro, con i lock mutex qualsiasi tentativo di acquisire un lock conteso comporterà l’esecuzione di un codice più complicato e oneroso che sospende un thread e lo colloca in una coda di wait, richiedendo un cambio di contesto verso un altro thread.
La scelta di un meccanismo per affrontare le race condition può anche influire notevolmente sulle prestazioni del sistema. Per esempio, gli interi atomici sono molto più leggeri dei lock tradizionali e sono generalmente più appropriati dei lock mutex o dei semafori per singoli aggiornamenti di variabili condivise come i contatori. Ciò è visibile anche nella progettazione dei sistemi operativi, in cui gli spinlock vengono utilizzati su sistemi multiprocessore quando i lock vengono mantenuti per brevi periodi. In generale, i lock mutex sono più semplici e comportano meno overhead rispetto ai semafori; sono preferibili ai semafori binari per proteggere l’accesso a una sezione critica. Tuttavia, in alcuni casi, come nel controllo dell’accesso a un numero limitato di risorse, un semaforo contatore è generalmente più appropriato di un lock mutex. Analogamente, in alcuni casi, un lock lettore-scrittore può essere preferito a un lock mutex, in quanto consente un maggior grado di concorrenza (cioè più lettori).
L’attrattiva di strumenti di livello superiore come monitor e variabili condizionali si basa sulla loro semplicità e facilità d’uso. Tuttavia, tali strumenti potrebbero avere un overhead significativo e, a seconda della loro implementazione, potrebbero essere meno scalabili a situazioni con elevate contese.
Fortunatamente sono in corso molte ricerche per sviluppare strumenti scalabili ed efficienti che rispondano alle esigenze della programmazione concorrente. Alcuni esempi comprendono:
progettazione di compilatori che generano codice più efficiente;
sviluppo di linguaggi che forniscono supporto per la programmazione concorrente;
miglioramento delle prestazioni delle librerie e delle api esistenti.
Nel prossimo capitolo esamineremo in che modo i vari sistemi operativi e le api disponibili agli sviluppatori implementano gli strumenti di sincronizzazione presentati in questo capitolo.