:: 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
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.
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:
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.
La variabile turno è condivisa. Il thread Ti 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.
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.
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();
}
}
}
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.
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.
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:
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 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).
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.
Usati per verificare i vari algoritmi.
Produttore = mette nel buffer con insert
Consumatori = rimuovono con remove
Occorre un semaforo per garantire mutua esclusione nell'accesso al buffer
Dati condivisi:
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.
Ci sono 5 filosofi attorno ad un tavolo
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.
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.
...
...
Sezioni critiche eseguite in mutua esclusione => in certi casi (basi di dati) è preferibile che le operazioi siano compiute del tutto, o non compiute affatto.
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:
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:
Esistono poi diversi tipi di record:
Write-ahead logging = prima di eseguire una scrittura, modifico il log.
Con il log si possono ripristinare tutti i dati:
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:
Quando c'è un guasto, non parto dall'inizio del log, ma dall'ultimo punto di verifica = checkpoint.
Checkpoint = eseguito periodicamente. Salva nel log:
Quando accade un guasto:
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à.
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
Una schedulazione non seriale è equivalente ad una schedulazione seriale se presenta gli stessi conflitti => è valida = conflict serializable.
Si associa a ciascun dato un lock e ogni transazione deve rispettare il protocollo di lock.
Su di un dato, una transazione può ottenere:
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:
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.
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:
Le operazioni di read e write devono rispettare le marche di tempo:
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.