cerca
Riassunto del libro di Sistemi Operativi - Capitolo 7: Sincronizzazione dei processi
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Uni.SOcap7 History

Show minor edits - Show changes to output

Changed line 229 from:
%lframe%Attach:log2.jpg|The Log Lady
to:
%lframe%Attach:log2.jpg|'''The Log Lady'''
Added line 5:
Changed lines 214-215 from:
...
to:
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
%lframe%Attach:log2.jpg|The Log Lady
'''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
.
Changed lines 2-3 from:
%titolo%''':: Riassunto del libro di Sistemi Operativi - Capitolo 7: Sincronizzazione dei processi ::'''
to:
%titolo%''':: Capitolo 7: Sincronizzazione dei processi ::'''
Added lines 111-214:
!!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
...
Added lines 1-111:
(:title Riassunto del libro di Sistemi Operativi - Capitolo 7: Sincronizzazione dei processi:)
%titolo%''':: Riassunto del libro di Sistemi Operativi - Capitolo 7: Sincronizzazione dei processi ::'''

[[Torna alla pagina di Sistemi Operativi -> 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:
# Mutua esclusione
# Progresso: 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: 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''''altro'''processo. 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'''.

[[Torna alla pagina di Sistemi Operativi -> Sistemi Operativi]]