Riassunto del libro di Sistemi Operativi - Capitolo 7: Sincronizzazione dei processi

 :: Capitolo 7: Sincronizzazione dei processi ::

Torna alla pagina di Sistemi Operativi

Processo che coopera = influenza e/o è influenzato da altri processi.
Accesso concorrente a dati condivisi = possibile inconsistenza

7.1 Il problema della sincronizzazione

Race condition = corsa critica: più thread leggono e manipolano gli stessi dati in modo concorrente => il risultato dipende dall'ordine dell'esecuzione dei thread => per evitare le corse critiche, i thread vanno sincronizzati.

7.2 Il problema della sezione critica

Sezione critica = sezione di codice in cui un thread modifica variabili comuni => se un thread esegue quel codice, nessun altro può eseguirlo.

L'esecuzione delle sezioni critiche è mutuamente esclusiva.

Per risolvere il problema delle sezioni critiche, vanno soddisfatte 3 condizioni:

1. Mutua esclusione
2. Progresso: solo chi NON sta eseguendo la propria sezione critica, può concorrere con gli altri per accedervi, e la scelta non può durare indefinitamente
3. Attesa limitata: un thread ha un limite di attesa massimo prima di entrare nella sezione critica

7.3 Soluzioni per 2 processi

Negli algoritmi qui sotto proposto, un thread deve prima usare il metodo entraSezioneCritica dal quale non uscirà finché non saranno soddisfatte le condizioni.

 entraSezioneCritica(mioPid);
 // Codice critico
 esciSezioneCritica(mioPid);

Gli algoritmi hanno indice 0 e 1, perché sono solo 2.

7.3.1 Algoritmo 1

La variabile turno è condivisa. Il thread T_i esegue la sua sezione critica solo se è il suo turno.

 inizializza() {
    turno = 0;
 }

 entraSezioneCritica(int pid) {
    while (turno != pid) {
       Thread.yield(); // faccio riposare il mio thread
    }
 }

 esciSezioneCritica(int pid) {
    turno = 1 - pid,
 }

Questo algo assicura che solo un thread alla volta entri nella sezione critica => niente progresso, perché impone stretta alternanza: il turno cambia dopo ogni utilizzo, quindi anche se un thread non usa la sezione critica, l'altro non può rientrare subito dopo la sua.

7.3.2 Algoritmo 2

Per ovviare a questo problema si introducono le variabili flag0 e flag1 che indicano se il thread è pronto ad entrare nella sezione critica.

 boolean flag0, flag1;

 inizializza() {
   flag0 = false;
   flag1 = false;
 }

 entraSezioneCritica(int pid) {
   if (pid == 0) {
     flag0 = true;
     while (flag1 == true) {
       Thread.yield();
     }
   }
   else {
     flag1 = true;
     while (flag0 = true) {
       Thread.yield();
     }
   }
 }

 esciSezioneCritica(int pid) {
   if (pid == 0) flag0 = false; 
   else flag1 = false;
 }

Problema: se prima del while in entraSezioneCritica avviene un cambio di contesto, il secondo thread potrebbe eseguire la stessa chiamata. I thread si bloccherebbero indefinitamente => condizione di progresso non rispettata.

7.3.3 Algoritmo 3

Un thread mette a true il proprio flag, e mette come turno il turno dell'altroprocesso. Se anche i due processi concorrono, la variabile turn sarà impostata o a 1, o a 0 => uno dei due sicuramente partirà.

 entraSezioneCritica(int pid) {
   int altro = 1 - t;
   turno = altro;
   if (pid == 0) {
     flag0 = true;
     while ((flag1) && (turno = altro)) {
       Thread.yield();
     }
   }
   else {
     flag1 = true;
     while((flag0) && (turno = altro)) {
       Thread.yield();
     }
   }
 }

7.4 Hardware per la sincronizzazione

Ambiente monoprocessore: se blocco gli interrupt quando una variabile condivisa viene acceduta, impedisco le corse critiche.

Ambiente multiprocessore: bloccare gli interrupt richiede più tempo (ogni processore deve farlo) => ritardo.

I calcolatori moderni offrono in HW la possibilità di controllare e modificare in modo atomico una certa parola di memoria.
Atomico = non interrompibile. Le istruzioni singole sono per definizioni atomiche, ma il controllo e la modifica in generale richiedono più istruzioni => una sequenza => interrompibili.
L'istruzione si chiama test_and_set.

7.5 Semafori

Usare istruzione HW test_and_set = pericoloso e difficile per un programmatore. Inoltre potrebbe non avere i privilegi, in modalità utente, per usarla.

Semaforo = variabile intera cui si può accedere solo con 2 operazioni: acquire e release, dopo che è stata inizializzata.
Le modifiche al valore della variabile devono essere atomiche.

7.5.1 Impiego

Semaforo generalizzato = variabile in un dominio senza restrizioni.
Semaforo binario = variabile a 2 valori.
Mutex lock = sinonimo di semaforo binario.

Utilizzo generale, in cui S è il semaforo, condiviso da tutti i thread:

 acquire(S);
 sezioneCritica();
 release(S);

Semaforo generalizzato = si usa per un numero finito di istanze della risorsa:

• viene inizializzato al numero di istanze disponibili
• acquire = decremento
• release = incremento
• acquire possibile finché non è 0

7.5.2 Implementazione

Problema dell'algoritmo 3: busy wait = un ciclo che continuamente controlla le variabili = spreco di cicli CPU.

Un semaforo che fa questo effetto è detto spinlock.

Per evitare lo spinlock:

• il processo che non riesce ad acquirare si blocca
• il processo che releasa sveglia (wakeup) i dormienti in attesa del semaforo

Il semaforo mantiene una lista di processi in coda per esso, gestita in un qualunque modo.

Problema: le op. di acquire sono comunque corse critiche => non dovrebbe essere permesso a 2 processi di eseguire una acquire contemporaneamente.

=> Come prima, posso fermare gli interrupt in un sistema monoprocessore, o usare l'algoritmo 3 in un sistema multiprocessore => riemerge ancora l'attesa attiva per l'acquire, ma in questo caso è molto breve (max 10 istruzioni prima di mettere il processo che ha chiesto l'acquire in lista di attesa).

7.5.3 Stall e starvation

Stallo = deadlock

Un insieme di processi è in stallo quando tutti attendono una risorsa che può essere liberata solo da uno dei processi dell'insieme.

Starvation = blocco indefinito: avviene quando un processo attende indefinitamente nella coda del semaforo, se questa è gestita male.

7.6 Problemi classici di sincronizzazione

Usati per verificare i vari algoritmi.

7.6.1 Il problema del buffer limitato

Produttore = mette nel buffer con insert
Consumatori = rimuovono con remove

Occorre un semaforo per garantire mutua esclusione nell'accesso al buffer

7.6.2 Il problema dei lettori-scrittori

Dati condivisi:

• alcuni vogliono scrivere
• alcuni vogliono solo leggere

2 lettori in contemporanea non fanno danni. Basta però uno scrittore a generare pericoli di incoerenza => gli scrittori devono avere accesso esclusivo ai dati.

Primo problema dei lettori-scrittori: nessun lettore dovrebbe attendere la fine di un altro lettore solo perché c'è uno scrittore in attesa.

Secondo problema dei lettori-scrittori: se uno scrittore è in attesa del lock, nessun lettore può passargli davanti

Una soluzione ad entrambi i problemi porta alla starvation: nel primo caso la starvation la subiscono gli scrittori; nel secondo i lettori.

7.6.3 Il problema del pranzo dei filosofi

Ci sono 5 filosofi attorno ad un tavolo

• al centro del tavolo c'è il riso
• un filosofo o mangia o pensa
• per mangiare occorrono 2 bacchette
• ci sono 5 bacchette per tavolo
• viene presa una bacchetta alla volta
• vengono lasciate le bacchette solo dopo aver mangiato
• le bacchette non possono essere rubate a chi ce l'ha già in mano

Se un filosofo ha fame prende una bacchetta alla volta. Quando ne ha 2, mangia. Quando ha finito di mangiare, posa le bacchette e torna a pensare.

Occorre risolvere il problema senza che nessuno muoia di fame.

Eg: se tutti hanno fame nello stesso istante, ed ognuno prende una bacchetta, non ce ne saranno più per gli altri => nessuno si sblocca.

7.7 Monitor

Semafori = c'è il problema che vanno chiamate le funzioni acquire e release nell'ordine giusto, pena deadlock.

Il monitor affronta questo problema.
È un tipo di dati astratto => l'accesso alle risorse condivise viene "filtrato" dai metodi esposti pubblicamente => protetti da accesso concorrente.

Ci sono delle condizioni che ogni thread che vuole accedere ai dati condivisi deve vedere soddisfatte, prima di poter operare.
Un thread è associato ad una o più di queste condizioni. Se sono verificabili, prosegue, altrimenti chiama wait e si mette in attesa.
Un thread che controlla le stesse condizioni e finisce le sue operazioni deve segnalare con signal il fatto che ha finito => risveglia i thread in attesa.

Il thread che chiama signal lascia il monitor, e quello in attesa viene risvegliato subito.

Il problema sta nel segnale, che dovrebbe essere inviato a tutti quelli che sono in attesa, così da poter concorrere tra loro per avere il monitor.

7.8 La sincronizzazione in Java

...

7.9 Esempi di sincronizzazione

...

7.10 Transazioni atomiche

Sezioni critiche eseguite in mutua esclusione => in certi casi (basi di dati) è preferibile che le operazioi siano compiute del tutto, o non compiute affatto.

7.10.1 Modello del sistema

Transazione = insieme di operazioni che eseguono un'unica funzione logica => il problema è preservare l'atomicità nonostante i guasti.

Transazione: composta da read e write, e seguita da commit o abort.

Una transazione abortita può aver modificato dei dati => rollback ad uno stato consistente precedente.

Le periferiche di archiviazione sono classificate, rispetto a questa visione, in:

• archivio volatile
• archivio non volatile
• archivio stabile = astrazione, ovviamente nella realtà non si può dare niente per scontato

7.10.2 Recupero basato sui log

Log = registro in cui sono registrate tutte le modifiche effettuate; salvato in memoria stabile.

Ogni record nel log descrive un'operazione di scrittura e ha i seguenti campi:

• nome della transazione
• nome dell'oggetto modificato
• vecchio valore
• nuovo valore

Esistono poi diversi tipi di record:

• inizio transazione
• commit della transazione

Write-ahead logging = prima di eseguire una scrittura, modifico il log.

Con il log si possono ripristinare tutti i dati:

• undo(Ti) = ripristina tutte le cose modificate dalla transazione Ti
• redo(Ti) = ripete tutte le cose fatte dalla transazione Ti

Undo e redo sono idempotenti = più esecuzioni della stessa operazione devono dare luogo allo stesso risultato.

Se una transazione fa abort, si esegue undo(Ti).

Se c'è un guasto, le transazioni vengono messe in 2 gruppi:

• se la transazione i ha un begin nel log, ma non un commit, faccio l'undo
• se la transazione i ha un begin ed un commit, faccio il redo

7.10.3 Punti di verifica

Quando c'è un guasto, non parto dall'inizio del log, ma dall'ultimo punto di verifica = checkpoint.

Checkpoint = eseguito periodicamente. Salva nel log:

• scrive i record del log ancora in memoria volatile, in memoria stabile
• scrive tutti i dati modificati in memoria volatile
• scrive un record <checkpoint> nel log

Quando accade un guasto:

• si torna all'ultimo checkpoint
• trovo:
  • l'ultima transazione che è iniziata ma non committata prima del checkpoint
  • tutte le operazioni iniziate dopo il checkpoint
• faccio il redo di tutte le transazioni che hanno un commit nel log dopo il checkpoint
• faccio l'undo di tutte le transazioni che non hanno un commit nel log dopo il checkpoint

7.10.4 Transazioni atomiche concorrenti

Serializzabilità = l'esecuzione concorrente di un gruppo di transazioni deve essere equivalente all'esecuzione delle stesse transazioni in un qualsiasi ordine seriale.

Gli algoritmi di controllo della concorrenza si occupano di questa proprietà.

7.10.4.1 Serializzabilità

Schedulazione = sequenza di esecuzione di transazioni.
Schedulazione seriale = sequenza di istruzioni di varie transazioni, in cui le istruzioni di una transazione appaiono insieme.

=> n transazioni => n! schedulazioni seriali valide.

Una schedulazione non seriale non è necessariamente non corretta, ma deve essere equivalente ad una schedulazione seriale per essere corretta.

Per verificare ciò, uso il concetto di conflitto tra operazioni = due operazioni sono in conflitto se

• appartengono a transazioni diverse
• accedono allo stesso dato
• almeno una delle due è una scrittura

Una schedulazione non seriale è equivalente ad una schedulazione seriale se presenta gli stessi conflitti => è valida = conflict serializable.

7.10.4.2 Protocollo di lock

Si associa a ciascun dato un lock e ogni transazione deve rispettare il protocollo di lock.

Su di un dato, una transazione può ottenere:

• lock condiviso (S = shared) = può leggere ma non scrivere
• lock esclusivo (X = exclusive) = può leggere e scrivere

Se il lock chiesto è disponibile, viene concesso, altrimenti la transazione aspetta.

Il protocollo di lock a 2 fasi prevede che le richieste di lock e gli unlock siano eseguiti in 2 fasi distinte:

• fase di crescita = una transazione ottiene lock ma non può rilasciarli
• fase di contrazione = una transazione può rilasciare i lock ma non può ottenerne di nuovi.

Quando una transazione rilascia il primo lock, entra nella fase di contrazione e non può richiederne altri, anche su altri dati.

Il protocollo di lock a 2 fasi assicura serializzabilità ma non l'assenza di stalli.

7.10.4.3 Protocolli basati su marche di tempo

Si assegna una marca di tempo = timestamp unica e fissa ad ogni transazione, in ordine crescente (le si possono ricavare dal clock del computer o da un contatore).

Ciascun dato possiede due marche di tempo:

• WTM = la marca di tempo più elevata tra quelle delle transazioni che hanno eseguito scritture sul dato
• RTM = la marca di tempo più elevata tra quelle delle transazioni che hanno eseguito letture sul dato

Le operazioni di read e write devono rispettare le marche di tempo:

• read
  • se il ts della transazione che vuole leggere è inferiore al WTM, viene rifiutata perché troppo vecchia
  • se no viene accettata, e l'RTM viene aggiornato al maggiore tra il ts di questa transazione ed il valore precedente
• write
  • se il ts della transazione che vuole scrivere è inferiore al WTM o al RTM, viene rifiutata perché troppo vecchia
  • viene aggiornato il WTM

Garantisce serializzabilità, anche se in modo più restrittivo rispetto al lock a 2 fasi (alcune schedulazioni accettat dal lock a 2 fasi sono rifiutate dal protocollo basato sui timestamp).

Inoltre, assicura anche l'assenza di stalli.

Torna alla pagina di Sistemi Operativi