Swappa :: Sistemi Operativi - Sincronizzazione

Torna alla pagina di Sistemi Operativi

 :: Appunti 2.0 ::

Sincronizzazione

Concorrenza

La concorrenza sussiste quando ho più processi che richiedono l'accesso a risorse condivise usabili solo in mutua esclusione. Tali processi vengono definiti concorrenti. Sarà detto qui una volta per tutte, tutto ciò di cui si parlerà in questa sede si applica sia ai processi che ai thread, a meno di notifica.
Per mutua esclusione si intende banalmente che non possono essere compiute contemporaneamente sulla stessa risorsa operazioni incompatibili da parte di più processi. Ad esempio una scrittura e una lettura sullo stesso dato non sono concesse, due letture sì. Il suo scopo è dunque preservare la consistenza dell'informazione, o si avrebbero casi in cui i processi computino dati scorretti. La sincronizzazione è quindi quell'insieme di politiche e meccanismi che si occuperanno di garantire tale principio per l'uso di risorse condivise, che queste siano fisiche (come le periferiche) o informative (come file o altri dati). Notare come sia un problema peculiare dei sistemi multi-tasking, dal momento che se avessi un'esecuzione seriale dei processi non avrei mai richieste di accesso parallele.

Corse e sezioni critiche

Il problema del produttore-consumatore è un modello classico per lo studio della sincronizzazione nei sistemi operativi. Esso consiste nel sincronizzare due processi, uno (il produttore) che vuole inviare informazioni (sui suoi prodotti) e l'altro (il consumatore) che vuole leggerli. Entrambi i processi utilizzano un buffer circolare di n elementi come struttura dati di appoggio condivisa. I codici potrebbero essere i seguenti:

Produttore

while (count == BUFFER_SIZE) ; // non fa nulla
// aggiungi un elemento nel buffer
++count;
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;

Quando il produttore vorrà inviare delle informazioni, se il buffer non è pieno le inserirà nel primo spazio vuoto disponibile, incrementando di uno il valore di ''count'.

Consumatore

while (count == 0) ; // non fa nulla
// rimuovi un elemento nel buffer
--count;
item = buffer[out];
out = (out + 1) % BUFFER_SIZE;

Se il consumatore trova il buffer vuoto aspetta, altrimenti legge l'informazione e decrementa di uno il contatore degli elementi presenti nel buffer.

Il problema nasce nella condivisione della variabile count. Se ad esempio scade il time slice del processo produttore proprio quando sta per incrementare il contatore, avrei risultati inconsistenti dato che l'inserimento non sarà segnalato al consumatore che accederà a valori obsoleti. Queste situazioni in cui più processi accedono agli stessi dati in maniera concorrente e il risultato dell'esecuzione dipende dall'ordine in cui ha avuto luogo l'accesso, si chiamano corse critiche. Ricorrono molto frequentemente e non sempre conducono a effettiva inconsistenza delle informazioni. Il problema è che possono farlo, dunque vanno evitate.
Quindi, la corsa critica del problema del produttore-consumatore non è legata ad operazioni contemporanee di lettura e scrittura, dal momento che ognuna di esse avviene all'interno dello spazio di indirizzamento dei rispettivi processi; ma è dovuta ai possibili errori nell'aggiornamento del contatore del buffer. Le operazioni di incremento e decremento sono infatti realizzate con una sequenza di istruzioni assembler, e proprio in quanto sequenza per definizione interrompibili.

La sezione critica è una porzione di codice che può generare corse critiche se eseguita in modo concorrente, ad esempio modifiche di variabili comuni, scrittura su file condivisi, eccetera. Lo scopo della sua individuazione è quello di creare un protocollo che possa essere utilizzato per bypassare i problemi di inconsistenza; la soluzione deve dunque soddisfare tre condizioni:

mutua esclusione, ovvero se un processo sta eseguendo la sua sezione critica nessun altro può farlo
progresso, che stabilisce che solo chi non sta eseguendo la propria sezione critica può concorrere con gli altri per accedervi, e la scelta non può durare indefinitamente
attesa limitata, bisogna cioè fare in modo che nessun processo attenda troppo a lungo di evolversi

Riassumendo, le sezioni critiche di codice devono avere accesso esclusivo alle variabili condivise, e devono sfruttarle in modo rapido perché altri processi che usano la stessa risorsa non debbano attendere indefinitamente. Ciò si ottiene progettando processi cooperanti, che superino le criticità con un'opportuna sincronizzazione dell'evoluzione delle loro computazioni. L'idea di base è che ognuno di loro sappia a che punto della computazione si trova l'altro prima di entrare in una sezione critica, e che questi interrompa la computazione fintanto che il primo vi rimane.

Variabili di turno

Un tipo di approccio a livello di istruzioni per la sincronizzazione di due processi concorrenti, sono le variabili di turno. Esse sono variabili condivise tra i processi che interagiscono per accedere in modo concorrente a una risorsa, stabilendone il turno d'uso. In altre parole dicono quale processo ha il diritto di usarla in un certo istante. Vediamo tre possibili implementazioni che garantiscono la mutua esclusione tra due processi 0 e 1.

Algoritmo 1

Riportiamo parte del codice, e in seguito i commenti.

...
  private volatile int turn;  // la variabile di turno 
  public Algorithm 1() // (1)
  {
    turn = TURN 0;
  }
  public void enteringCriticalSection (int t) // (2)
  {
    while (turn != t)
      Thread.yield();
  }
  public void leavingCriticalSection (int t) // (3)
  {
    turn = 1 - t;
  }
...

(1) Inizializza a 0 la variabile di turno, dando così la possibilità al processo 0 di accedere alla propria sezione critica.
(2) Il processo 0 può accedere all'uso della risorsa condivisa, mentre a un qualsiasi altro processo (con valore t diverso da 0) viene invece impedito l'accesso, lasciandolo bloccato nella funzione di attesa yield(). Ovviamente, se fosse il processo 1 quello che sta utilizzando in quel momento la risorsa, sarebbe 0 quello mantenuto in attesa.
(3) Quando il processo 0 (o 1) avrà terminato le sue operazioni nella sezione critica, concederà l'uso delle risorse condivise all'altro processo. Ciò avviene cambiando il valore alla variabile turn, in questo caso con l'assegnamento "1 - t" (perché ho solo due processi).

Questo algoritmo garantisce la mutua esclusione imponendo una stretta alternanza dei processi, con tutti gli svantaggi che questo comporta. Se ad esempio ho un produttore che vuole deporre più informazioni durante il suo turno, non potrà farlo perché dovrà prima aspettare che il consumatore esaurisca il suo (e viceversa). In più, non viene garantito il progresso, dato che non lo lascio evolvere fino ai suoi limiti naturali; nel caso del consumatore essi sono l'aver letto tutte le informazioni, mentre per il produttore è ritrovarsi col buffer pieno.

Algoritmo 2

Associa un flag per ogni processo in modo che sia impostato a true quando sono nella sezione critica, false altrimenti. Come prima, riportiamo parte del codice e in seguito i commenti.

...
  private volatile boolean flag0, flag1;
  public Algorithm 2() // (1)
  {
    flag0 = false; flag1 = false;
  }
  public void enteringCriticalSection (int t) // (2)
  {
    if (t == 0) 
    {
      flag0 = true;
      while (flag1 == true)
        Thread.yield();
    }
    else 
    {
      flag1 = true;
      while (flag0 == true)
        Thread.yield();
    }
  }
  public void leavingCriticalSection (int t) // (3)
  {
    if(t == 0) flag0 = false; else flag1 = false;
  }
...

(1) Inizializza entrambi i flag a false per l'ovvio motivo che i processi devono ancora fare richiesta di entrare nelle rispettive sezioni critiche.
(2) Se il processo che vuole accedere alla risorsa è lo 0, flag0 passa a true. Nel caso in cui flag1 sia già a true (e quindi stia già usando la risorsa condivisa), attende prima che finisca.
(3) Quando un processo termina le sue operazioni sulla sezione critica, pone il proprio flag a false.

Questo algoritmo garantisce la mutua esclusione ma senza imporre una stretta alternanza dei processi, dato che chi fa richiesta di accesso a una risorsa controlla dai valori dei flag se gli è consentito o meno. Continua però a non garantire il progresso, e per di più potrebbe portare un processo a un'attesa infinita.

Algoritmo 3

Utilizza sia i flag che la variabile di turno, i primi per la prenotazione della risorsa, la seconda per stabilire chi ha accesso. Riportiamo parte del codice e in seguito i commenti.

...
  private volatile boolean flag0, flag1;
  private volatile int turn;
  public Algorithm 3()
  {
    flag0 = false; flag1 = false;
    turn = TURN 0;
  }
  public void enteringCriticalSection (int t) // (1)
  {
    int other = 1 - t;
    turn = other;
    if (t == 0) 
    {
      flag0 = true;
      while (flag1 == true && turn == other)
        Thread.yield();
    }
    else 
    {
      flag1 = true;
      while (flag0 == true && turn == other)
        Thread.yield();
    }
  }
  public void leavingCriticalSection (int t)
  {
    if(t == 0) flag0 = false; else flag1 = false;
  }
...

(1) Grazie all'assegnamento turn = other;, la prossima volta che viene lanciata la funzione verrà passato other (l'altro processo) come parametro. Se quest'ultimo non deve fare nulla ripassa immediatamente il turno all'altro, altrimenti esegue le operazioni sulla risorsa di cui ha ottenuto l'accesso.

Questo algoritmo garantisce sia la mutua esclusione che il progresso, perché non rimane bloccato a causa di prenotazioni grazie alla doppia condizione del while.

Variabili di lock

La variabile di lock è una variabile condivisa che definisce lo stato di uso di una risorsa, cioè quando è in uso da parte di un processo (che è evidentemente nella sua sezione critica). Cambia così il punto di vista rispetto alla variabile di turno: non sono più i processi ad alternarsi ma è la risorsa stessa a dire se è disponibile o no. Inoltre, le variabili di turno devono essere inizializzate e gestite a seconda del numero di processi che accedono alla stessa risorsa, e nella grande maggioranza dei casi questo numero non è predicibile a priori; i lock invece scalano benissimo, perché non importa quanti sono i processi che vogliono una risorsa, lui sarà sempre o libero o occupato.
Può assumere due valori: 0 se la risorsa è libera, 1 se è in uso.

L'acquisizione di una risorsa avviene a interruzioni disabilitate, come si evince dai seguenti passaggi operativi:

disabilito le interruzioni
leggo la variabile di lock
se la risorsa è libera (lock = 0), la marco in uso ponendo lock = 1 e riabilito le interruzioni
se la risorsa è in uso (lock = 1), riabilito le interruzioni e pongo il processo in attesa che la risorsa si liberi
per rilasciare la risorsa pongo lock = 0

Il motivo per cui vanno bloccate le interruzioni è che le operazioni di lettura ed eventuale scrittura di un lock sono realizzate con una sequenza di istruzioni macchina, quindi interrompibili (solo la singola istruzione macchina è atomica). Se quindi non mi tutelo sospendendo gli interrupt finirei per avere una corsa critica nello stesso sistema che uso per prevenirle.

Una soluzione alternativa è introdurre direttamente nell'hardware del processore dei meccanismi per ottenere la sincronizzazione. Ad esempio è possibile inserire l'istruzione atomica TEST-AND-SET che traduce la sequenza di istruzioni precedenti in una sola, non rendendo più necessaria alcuna sospensione delle interruzioni. Essa implementa infatti in un'unica istruzione le seguente operazioni: legge la variabile di lock e la pone in un flag del processore, quindi la pone uguale a uno, infine se il flag (vecchio valore di lock) era 0 allora significa che la risorsa era libera, altrimenti il processo dovrà attendere. Il limite di questa soluzione è che non spetta al programmatore la sua implementazione, bensì al progettista del processore.

Semafori

La gestione delle variabili di lock è un'operazione delicata, quindi è preferibile evitare di fare affidamento sul solo buonsenso dei programmatori, lasciando che sia il sistema operativo ad occuparsene. Ciò implica un innalzamento del livello di astrazione della sincronizzazione e una garanzia di consistenza, visto che l'esecuzione supervisor è a interruzioni disabilitate.
A tal fine sono stati introdotti i semafori binari S, una struttura dati (in particolare, una variabile binaria) gestita dal sistema operativo che rappresenta lo stato di uso della risorsa condivisa: ha valore 1 se la risorsa è libera, 0 se è in uso.
Nonostante il significato dei valori sia opposto a quelli di lock, non c'è rischio di confondersi dato che il programmatore userà direttamente le funzioni di sistema, delegando a quest'ultimo il problema di assegnare il valore corretto.
Le funzioni succitate per la manipolazione del semaforo S sono atomiche proprio in quanto chiamate di sistema, e vanno utilizzate all'entrata e all'uscita della sezione critica di un processo. Esse sono:

acquire(S), che richiede l'uso della risorsa (se il valore del semaforo è 1, lo porta a 0)
release(S), che rilascia la risorsa (riporta il valore a 1)

Se ho delle code di attesa posso regolarle con una qualsiasi politica di ordinamento, in tutto simili a quelle viste per la schedulazione, passando ulteriori parametri alla acquire() che diano informazioni sulla gestione della coda stessa.

Il problema dell'acquire() è che crea attese attive sul semaforo S, ovvero processi che pur essendo in stato di attesa continuano a effettuare computazioni per verificare se la risorsa si è liberata. Ciò comporta spreco di CPU che altri processi potrebbero usare in modo più produttivo. Questo fenomeno si chiama spinlock e se avviene per brevi periodi può tornare anche utile, dal momento che evita onerosi cambi di contesto (i processi rimangono sempre nello stato di wait). Quando però i tempi di attesa attiva diventano troppo lunghi si può adottare una tecnica diversa, ovvero spostare i processi in attesa in una coda di attesa così concepita:

quando un processo esegue un' acquire(S), se la risorsa non è disponibile passa in stato di wait e viene accodato nella coda di attesa del semaforo
quando un processo esegue una release(S), la risorsa viene rilasciata e viene attivato il primo processo della coda di attesa di S, a cui viene concesso l'accesso
nel frattempo lo schedulatore dei processi in attesa della risorsa definisce l’ordine di ottenimento della risorsa stessa in base alla politica adottata

Bisogna comunque prestare attenzione alla progettazione della coda di attesa, o potrei avere fenomeni di stallo (deadlock) in cui due o più processi aspettano un evento che può essere generato solo da uno dei processi in attesa. In altre parole bisogna prestare attenzione all'ordine con cui avvengono le chiamate di sistema di prenotazione e rilascio delle risorse, o potrei avere attesa circolari senza rilascio. Un altro pericolo è quello di incorrere in una starvation, il blocco indefinito meglio affrontato nel capitolo sulla schedulazione.

I semafori generalizzati S sono invece variabili intere che rappresentano lo stato di uso di un insieme di risorse omogenee condivise; in altre parole, indicano il numero n di risorse libere del tipo richiesto. La sintassi delle funzioni di manipolazioni del semaforo rimangono le stesse, con la differenza che in questo caso l' acquire(S) (acquisizione d'uso di una risorsa) e la release(S) (rilascio della risorsa) rispettivamente incrementano e decrementano di uno il valore del semaforo. In particolare, quando l'acquire() arriva a 0 si blocca.

Monitor

Nonostante la loro semplicità ed efficacia, il problema principale della sincronizzazione con uso di semafori è che la responsabilità della loro correttezza è lasciata al programmatore. Per quanto questi possa essere preparato e attento, potrebbero comunque avvenire errori nella progettazione e/o implementazioni del codice; un esempio piuttosto grossolano potrebbe essere dimenticarsi di rilasciare una risorsa, o gestire male le code d'attesa così da avere starvation. E' per questo motivo che è preferibile sollevare il programmatore da questo onere, innalzando ulteriormente il livello di astrazione per la gestione della sincronizzazione lasciando che sia il sistema operativo ad occuparsene. Un costrutto fondamentale di questo tipo è il tipo di dati astratto monitor, che incapsula un'insieme di operazioni definite dall'utente su cui garantisce la mutua esclusione. Viene formulato a livello di linguaggio di programmazione, e al suo interno vengono definite una serie di procedure, ognuna delle quali se invocata causa l'accesso del processo a una sezione critica. La sincronizzazione è implicita, dal momento che il compilatore del linguaggio non consentirebbe l'esecuzione di più flussi concorrenti nello stesso tipo di dati.

Un esempio di pseudocodice in java è il seguente:

monitor nome-del-monitor
{
  // dichiarazione delle variabili

  public entry p1(..) { ... }
  public entry p2(..) { ... }
  ...
}

Perché un processo possa accedere alle risorse deve soddisfare alcune condizioni, rappresentate da variabili di tipo condition definite dal programmatore. Se il processo associato a una di esse la verifica, prosegue; altrimenti chiama una funzione speciale di wait e si mette in attesa, fino a quando un altro processo associato alle stesse condizioni lo risveglia con una signal. Notare come quest'ultima funzione non si riferisca a un processo specifico, ma a tutti quelli nella coda dei processi associati alla condizione, così che possano concorrere tra loro per avere il monitor.
Supponiamo ora di avere due processi P e Q associati a una condizione x, con Q in attesa. Se P invoca una x.signal e viene concesso al processo Q di riprendere, posso comportarmi in due modi:

segnala e aspetta, in cui P attende finché Q lascia il monitor, o aspetta un'altra condizione
segnala e continua, il contrario

Un compromesso tra le due è la soluzione adottata dal linguaggio Concurrent Pascal: quando il processo P esegue l'operazione signal, lascia immediatamente il monitor e Q viene subito risvegliato.

Transazioni atomiche

Lettura festosa dal libro.

Torna alla pagina di Sistemi Operativi