Sezione critica

Come abbiamo evidenziato la scorsa lezione per poter coordinare thread che condividono memoria sono necessari dei meccanismi di sincronizzazione che assicurino un’esecuzione “ordinata” dei thread in modo da preservare la coerenza dei dati.

La Sezione Critica è la parte di codice in cui i processi accedono a dati condivisi.

Consideriamo un generico thread T in cui sia presente una sezione critica:

thread T {
  ....
  < ingresso >
  < sezione critica >
  < uscita >
  ....
}

vogliamo progettare il codice di ingresso e uscita dalla sezione critica in modo da garantire mutua esclusione ovvero che un solo un thread alla volta possa accedere alla sezione critica

Questa proprietà deve valere senza fare assunzioni sulla velocità relativa dei processi (temporizzazione), a prescindere quindi da come vengono schedulati.

Soluzioni software

Proviamo a realizzare la sezione critica con soluzioni puramente in software: senza l’ausilio di meccanismi hardware e chiamate a sistema.

Tentativo 1: lock

Utilizziamo una variabile booleana globale lock inizializzata a false:

thread T {
  ....
  while(lock) {}
  lock = true;
  < sezione critica >
  lock = false;
  ....
}

Descrizione: il codice di ingresso attende ciclando “a vuoto” finché il lock è true. Quando il lock viene rilasciato esce dal while e acquisisce il lock, ponendolo a true. Alla fine della sezione critica il lock viene settato a false e quindi rilasciato.

Problema: se due thread entrano contemporaneamente in sezione critica potrebbe accadere che superino il while entrambi, in quanto leggono il valore false prima che l’altro thread abbia settato lock a true. In tale caso è come se entrambi acquisissero il lock e la mutua esclusione non è garantita: ci sono 2 thread in sezione critica.

Thread T0                                       Thread T1

while(lock) {}                                  while(lock) {}

            # Entrambi i thread superano il ciclo while!

lock = true;                                    lock = true;  
< sezione critica >                             < sezione critica > 
lock = false;                                   lock = false;

Tentativo 2: turno

Utilizziamo una variabile booleana globale turno  inizializzata a 1. I thread eseguono codice che dipende dal proprio ID. Vediamo questa soluzione con 2 thread:

thread T0 {                        thread T1 { 
  ....                                ....  
  while(turno != 0) {}                while(turno != 1) {}    
  < sezione critica >                 < sezione critica >   
  turno = 1;                          turno = 0; 
  ....                                ....  
}                                   }

Descrizione: il codice di ingresso attende ciclando “a vuoto” finché non è il proprio turno. Alla fine della sezione critica il turno viene dato all’altro thread.

Mutua esclusione: la mutua esclusione è garantita dal fatto che turno non può valere contemporaneamente 0 e 1, di conseguenza uno dei due thread rimarrà in attesa sul ciclo while.

Problema: Anche se la soluzione garantisce mutua esclusione esistono esecuzioni problematiche: supponiamo che T0 voglia entrare 2 volte di seguito nella sezione critica mentre T1 sta eseguendo altro codice. T0 esce dalla prima sezione critica e assegna il turno a T1, a questo punto si bloccherà sul while in attesa che T1 vada in sezione critica e ceda a sua volta il turno. Il problema è che non sappiamo se e quando T1 entrerà in sezione critica (potrebbe anche non andarci mai!).

Manca quindi una seconda proprietà fondamentale che denominiamo progresso: se nessun thread è in sezione critica, un thread che chiede di accedere deve poterlo fare immediatamente.

Tentativo 3: pronto

Vediamo questa soluzione con 2 thread utilizzando un array di booleani globale pronto[2] inizializzati a false. Anche in questo caso i thread eseguono codice che dipende dal proprio ID.

thread T0 {                        thread T1 { 
  ....                                ....  
  pronto[0] = true;                   pronto[1] = true;
  while(pronto[1]) {}                 while(pronto[0]) {}    
  < sezione critica >                 < sezione critica >   
  pronto[0] = false;                  pronto[1] = false;
  ....                                ....  
}                                   }

Descrizione: quando il thread i-esimo vuole entrare pone a true la variabile pronto[i] per segnalare all’altro thread la sua volontà di accedere. Successivamente cicla a vuoto se anche l’altro thread è pronto. Quando esce dalla sezione critica, il thread pone a false pronto[i] per indicare che non ha più bisogno della sezione critica.

Mutua esclusione: la mutua esclusione è garantita dal fatto che se un thread è in sezione critica la sua variabile pronto è settata a true e l’altro thread si bloccherà sul ciclo while.

Problema: Anche se la soluzione garantisce mutua esclusione esistono esecuzioni problematiche: supponiamo che T0 e T1 vogliano entrare entrambi in sezione critica. Potrebbe accadere che settino simultaneamente pronto[i]=true e poi si blocchino entrambi sul proprio ciclo while. Notare che questa situazione di attesa è irrisolvibile e quindi inaccettabile.

Lo stallo di T0 e T1:

Thread T0                           Thread T1

  pronto[0] = true;                   pronto[1] = true;

        # entrabe le variabili sono settate a true

  while(pronto[1]) {}                 while(pronto[0]) {} 

        # i thread sono in stallo!

NOTA: Se invertiamo il while e l’assegnamento pronto[i]=true potrebbe accadere che entrambi i thread superino il ciclo while rompendo la mutua esclusione.

Soluzione: L’algoritmo di Peterson

Nel 1981, Gary L. Peterson propose una soluzione al problema della soluzione critica per 2 thread che di fatto combina 2 dei tentativi che abbiamo descritto sopra: pronto e turno.

Il difetto di pronto è che esiste un caso in cui i thread vanno in stallo. Per evitare questa situazione irrisolvibile utilizziamo una turnazione, ma solo nel caso problematico: quando entrambi i thread sono pronti. Se uno solo è pronto, tale thread può tranquillamente accedere alla sezione critica.

thread T0 {                              thread T1 { 
  ....                                      ....  
  pronto[0] = true;                         pronto[1] = true;
  turno=1;                                  turno=0;
  while(pronto[1] && turno != 0) {}         while(pronto[0] && turno != 1) {}    
  < sezione critica >                       < sezione critica >   
  pronto[0] = false;                        pronto[1] = false;
  ....                                      ....  
}                                         }

Descrizione: quando il thread i-esimo vuole entrare pone a true la variabile pronto[i] per segnalare all’altro thread la sua volontà di accedere. Successivamente cede il turno all’altro thread e cicla a vuoto se l’altro thread è pronto e se non è il proprio turno. Quando esce dalla sezione critica, il thread pone a false pronto[i] per indicare che non ha più bisogno della sezione critica.

Mutua esclusione: Per convincerci che viene garantita mutua esclusione dobbiamo considerare due casi

1. T0 supera il proprio while quando T1 è prima di turno=0. In questo caso quando T1 eseguirà turno=0 si bloccherà nel ciclo while in quanto avremo che pronto[0] è true e turno è 0 cioè diverso da 1;
2. T0 supera il proprio while quando T1 è dopo turno=0. Poiché T0 sta superando il while deve essere turno==0. Quindi avremo che T1 ancora una volta si blocca nel ciclo while ed attende.

Progresso: Se nessuno è in sezione critica pronto[i] vale false. Chiunque voglia entrare ci riuscirà in quanto la prima condizione nel while sarà falsa.

Assenza di stallo: Supponiamo che entrambi i thread siano bloccati nel while. In questo caso avremmo che turno!=0 e turno!=1 ma questo non è possibile in quanto turno viene assegnata unicamente ai valori 0 e 1 quindi uno dei due thread uscirà necessariamente dal ciclo while.

NOTA: L’algoritmo di Peterson funziona per 2 thread ma esistono anche soluzioni corrette che funzionano con un numero arbitrario di thread.

Conclusioni (soluzioni software)

È possibile risolvere il problema della sezione critica puramente in software ma tali soluzioni presentano alcune problematiche importanti:

1. I cicli while “a vuoto” (busy waiting) consumano inutilmente tempo di CPU. Su macchine con un solo core questo problema è particolarmente rilevante. Su più core diventa più accettabile in quanto i vari core dovrebbero comunque attendere che il thread in sezione critica esca;
2. Le soluzioni richiedono l’uso di diverse variabili globali e un sequenza precisa di esecuzione delle istruzioni. I compilatori e i processori attuali rimaneggiano e riordinano le istruzioni in modo da migliorare la performance. L’utilizzo di soluzioni software di sincronizzazione richiede che tali ottimizzazioni siano disabilitate per evitare di compromettere la correttezza del codice di ingresso e uscita dalla sezione critica.

Soluzioni hardware

Vediamo quali meccanismi hardware possono essere d’aiuto per realizzare la sezione critica.

Disabilitazione interruzioni

Questa tecnica veniva utilizzata nei sistemi operativi ed è tuttora usata nei sistemi embedded. Si tratta di disabilitare le interruzioni in modo da “monopolizzare” la CPU per il tempo necessario ad eseguire il codice critico. Su sistemi a singolo core questo permette di bloccare temporaneamente l’esecuzione parallela di thread e processi garantendo in modo ovvio la mutua esclusione.

Tuttavia, questa tecnica non scala su sistemi multi-core in cui disabilitare le interruzioni non elimina il parallelismo vero tra core. Inoltre non è utilizzabile per programmi utente in quanto troppo rischiosa: un errore di programmazione bloccherebbe l’intero sistema.

Istruzioni speciali

Esistono istruzioni macchina particolari che possono essere usate per semplificare le soluzioni software al problema della sezione critica e non presentano i difetti della disabilitazione delle interruzioni discussa poco fa. Un esempio classico è test_and_set. Questa istruzione permette di testare un valore ed assegnarlo in modo indivisibile. Per capirne il funzionamento la definiamo in pseudo-C come segue:

boolean test_and_set(boolean *x) {
    boolean ret = *x;
    *x = true;
    return ret;
}

test_and_set pone a true il valore della variabile x ritornando il valore booleano prima dell’assegnamento. Ci permette quindi di testare il valore di x e assegnare x a true in modo indivisibile. Possiamo usarla per risolvere il problema del primo tentativo di soluzione software con lock, in cui due thread potevano acquisire il lock simultaneamente:

thread T {
  ....
  while(test_and_set(&lock)) {}
  < sezione critica >
  lock = false;
  ....
}

Se lock è false, test_and_set ritorna false ma contemporaneamente acquisisce il lock ponendolo a true, in modo indivisibile. Il thread quindi entra in sezione critica. Se invece lock è a true, test_and_set ritorna true e lascia inalterato il valore. Di conseguenza il thread rimane dentro il while.
Questa soluzione scala su un numero arbitrario di thread e necessita di un’unica variabile booleana. L’unica accortezza è che l’assegnamento di lock non venga riordinato rispetto alle istruzioni in sezione critica dal compilatore o dal processore stesso. Questa soluzione prende il nome di spin-lock e viene usata nei sistemi operativi per realizzare la sezione critica sulle proprie strutture dati.

Nei processori Intel esiste un’istruzione atomica che permette di scambiare il valore di due variabili in modo atomico (XCHG). In pseudo C:

XCHG(boolean *x, *y) {
    boolean tmp = *x;
    *x = *y;
    *y = tmp;
}

Esercizio

Provare a realizzare la sezione critica usando XCHG.