Parte 2: Sincronizzazione dei Processi (completo)

7. Sincronizzazione dei Processi

• Importante: l’accesso concorrente a dati condivisi può produrre dati inconsistenti • processi cooperanti attraverso la condivisione

di dati devono agire in modo ordinato, cioè sincronizzarsi

• Esempio dimostrativo Produttore/Consumatore che usa tutti gli elementi del buffer. (n elementi al massimo nel buffer)

2

Esempio:

Produttore-Consumatore con n elementi

• Aggiungere counter inizializzato a 0 alle variabili shared che indica il numero di elementi nel buffer

shared var n: integer; counter: integer; type item = ...;

shared var buffer: array [0..n-1] of item;

shared var in, out: 0..n-1;

• Buffer circolare con due puntatori in e out inizializzati a 0 (vedi cap. 4)

3

Esempio:

Produttore-Consumatore con n elementi

Produttore

var nextp: item; repeat

<produce un nuovo item in nextp>

while counter = n do no_op; buffer[in] := nextp;

in := in+1 mod n; counter := counter+1;

Esempio:

Produttore-Consumatore con n elementi

Consumatore

var nextc: item; repeat

while counter = 0 do no_op; nextc := buffer[out]; out := out+1 mod n; counter := counter-1; <consuma l'item in nextc> until false;

5

Esempio:

Produttore-Consumatore con n elementi

• Sebbene le routine siano corrette se considerate separatamente, possono non funzionare se eseguite in concorrenza !!! • Problema: accesso alla variabile condivisa

counter

• Se counter vale 5, dopo le istruzioni di incremento e decremento può essere uno qualunque tra 4, 5 o 6 !!

6

Cosa non funziona ?

• Incremento e decremento di counter In producer: register1 = counter register1 = register1 + 1 counter = register1 In consumer: register2 = counter register2 = register2 - 1 counter = register2

Cosa non funziona

Producer: register1 = counter Producer: register1 = register1 + 1 Consumer: register2 = counter Consumer: register2 = register2 - 1 Producer: counter = register1 Consumer: counter = register2

8

7.2 Sezioni critiche

• I due programmi possono produrre risultati scorretti perché insieme manipolano la stessa variabile concorrentemente

• Se avessi l’aritmetica in memoria (una sola istruzione, un solo processore):

– nessun problema ⇒ una istruzione è eseguita in modo atomico

9

7.2 Sezioni critiche

• Se avessi l’aritmetica in memoria ma più di un processore:

– ancora problemi perché l’istruzione accede due volte in memoria (per leggere e per depositare il risultato)

• L’intrallacciamento di istruzioni o di accessi in memoria provoca corsa critica

⇒ sequenzializzare l’accesso alla variabile da manipolare concorrentemente

7.2 Sezioni critiche

• Sezione critica =:= segmento di codice che deve essere eseguito senza interfogliamento con altre sezioni critiche della stessa famiglia • Le variabili condivise determinano le

sezioni critiche.

• Problema: assicurare che quando un processo sta eseguendo la propria sezione critica, nessun altro processo abbia il permesso di eseguire la sua sezione critica.

11

7.2 Sezioni critiche

• Un processo è costituito da:

♦ entry section: per chiedere di entrare ♦ sezione critica vera e propria

♦ exit section per segnalare l’uscita dalla sezione critica

♦ remainder section che non fa accesso a dati critici

12

7.2 Proprietà richieste alle

soluzioni

• Mutua esclusione nella sezione critica • Progresso: se la sezione critica è vuota,

solo chi cerca di entrare partecipa alla decisioni di chi entrerà davvero, ed entro un tempo finito

• Attesa limitata superiormente, per chi attende fuori che la sezione si liberi

7.2 Proprietà richieste alle

soluzioni

• Velocità dei processi non nulla, ma nessuna ipotesi sulle velocità relative perché la soluzione non dipenda dallo scheduling della CPU

• Vediamo una soluzione per due processi…

– Usiamo una variabile turn inizializzata a 0 – se turn = i, allora Pipuò accedere alla sezione

critica

14

Algoritmo 1

• Il codice di P_iè repeat

while (turn ≠ i) do no_op; <critical section>

turn = j;

<remainder section> until false;

• Assicura mutua esclusione, ma non il progresso: stretta alternanza dei processi

15

Algoritmo 2

• Sostituiamo turn con

– shared var flag: array[0..1] of boolean;

– Inizializzazione flag[0] = flag[1] = false

• Il codice di P_iè repeat

flag[i] := true; while flag[j] do no_op; <critical section> flag[i] := false; <remainder section>

Algoritmo 2

• Soddisfa mutua esclusione, ma non il requisito di progresso

• Consideriamo la seguente sequenza di esecuzione

– Pipone flag[i] = true

– Pjpone flag[j] = true

• P_ie P_jentrano nel while e non ne escono più !

17

Algoritmo 3

• Usiamo sia turn che flag

– Inizializzazione flag[0] = flag[1] = false, turn = 0 {0 o 1 è lo stesso}.

• Il codice di P_iè repeat

flag[i] := true; turn := j; while (flag[j] and turn = j) do

no_op; <critical section> flag[i] := false; <remainder section> until false; •Il codice di Pjè repeat

flag[j] := true; turn := i;

while (flag[i] and turn = i) do no_op; <critical section> flag[j] := false; <remainder section> until false; 18

Algoritmo 3

• Mutua esclusione: se tentano di entrare assieme (ognuno ha già assegnato il suo flag) uno dei due assegnamenti a turn sarà l’ultimo (atomicità delle

istruzioni!) e non cambia fino a che non si rientra

nella entry section

• Progresso: chi esce si dichiara fuori (falso al proprio flag) e quindi il while dell’altro termina e lascia entrare

Algoritmo 3

• Attesa limitata: il loop non può essere eseguito per più tempo della sezione critica e quindi è limitata dalla durata della sezione critica dell’altro

• Non si ipotizza che i processi viaggino a velocità opportuna

• Per n processi c’è l’algoritmo "del fornaio" (sul libro)

20

Algoritmo del Fornaio

• Soluzione al problema della sezione critica per n processi

• Prima di entrare nella propria sezione critica, un processo riceve un numero.

• Il possessore del numero minore entra nella sezione critica.

• Se due processi Piand Pjricevono lo stesso

numero, se i < j, allora P_ientra; altrimenti entra P_j. • I numeri vengono generati sempre in ordine

crescente, ad es., 1,2,3,3,3,3,4,5...

21

Algoritmo del fornaio(Cont.)

• Notazione: ordine lessicografico (# biglietto, process id)

– (a,b) < (c,d) se a < c o se a = c e b < d – max (a0,…, an-1) è un numero k, tale che k ≥ ai

∀ i = 0, … , n – 1

• Variabili condivise inizializzate a false e 0 rispettivamente

var choosing: array [0..n – 1] of boolean; number: array [0..n – 1] of integer

Algoritmo del fornaio(Cont.)

choosing[i] := true;

number[i] := max(number[0], number[1], …, number [n – 1])+1; choosing[i] := false;

for j := 0 to n – 1 do begin

while choosing[j] do no-op; while number[j] ≠ 0

and (number[j],j) < (number[i], i) do no-op; end; critical section number[i] := 0; remainder section until false; 23

7.3 Sincronizzazione via Hardware

• Problemi con l’algoritmo del fornaio

– troppo complesso in codice e dati

– i processi fanno busy-waiting =:= attendere usando la CPU

• Altra soluzione: Disabilitare gli interrupt per evitare context switch, ma

– la sezione critica può essere molto lunga – non si può girare a lungo con interrupt

disabilitati

24

7.3 Sincronizzazione via Hardware

– non va bene sui multiprocessori (o richiede troppo tempo, mentre Algoritmo#3 oppure la panetteria vanno bene)

– produce errori nella misurazione del tempo (fatta con le interruzioni)

• ⇒ introdurre istruzioni speciali che scambiano atomicamente il valore di un registro e di una cella di memoria

– TestAndSet – Swap

7.3 Sincronizzazione via Hardware

shared var lock: boolean;

Inizializzazione lock = false

repeat

while TestAndSet(lock) do no_op; <critical section>

lock := false; <remainder section> until false;

26

7.3 Sincronizzazione via Hardware

• Va bene anche per i multiprocessori con sharing di memoria

• TestAndSet o Swap è una caratteristica del bus e della memoria, difficile da realizzare

27

7.4 Semafori

• Per avere attesa limitata (TestAndSet da sola non lo da) occorre un algoritmo con strutture dati complesse (vedi libro) • Anche con istruzioni speciali si fa

busy-waiting

• Semafori inventati da Dijkstra (1965) per minimizzare busy-waiting

7.4 Semafori

• Definiti tramite due operazioni

– P (Proberen) e V (Verhogen) oppure – W (Wait) e S (Signal)

• Le operazioni devono essere atomiche. • Semaforo in genere inizializzato a 1

– wait(sem) : while sem ≤ 0 do no_op;

sem := sem-1; – signal(sem) : sem := sem+1;

29

Sezione critica con n processi

• Variabili condivise

– var mutex : semaphore – initially mutex = 1 • Generico processo Pi repeat wait(mutex); critical section signal(mutex); remainder section until false; 30

7.4 Semafori

• Si possono usare anche per problemi di sincronizzazione diversi; ad es., eseguire S1 prima di S2; usiamo un semaforo sync:=0; • P1 esegue: S1; signal(sync); • P2 esegue: wait(sync); S2;

7.4.2 Implementazione dei Semafori

• Se li implementiamo come le sezioni critiche → busy waiting → sono detti spinlock

⇒ invece, bloccare il processo in attesa in opportuna coda

type semaphore = record value: integer;

L: list of process;

end;

32

7.4.2 Implementazione dei Semafori

• wait(S) :

S.value := S.value -1; if S.value<0 then begin

<add this proc to S.L>

block; end;

• block: invoca scheduler e dispatcher→ commutazione della CPU

33

7.4.2 Implementazione dei Semafori

• signal(S) :

S.value := S.value+1;

if S.value ≤ 0 then begin

<remove proc P from S.L>

wakeup(P); end;

7.4.2 Implementazione dei Semafori

• Wait e Signal sono sezioni critiche

– molto brevi

– su monoprocessore si può disabilitare le interruzioni – TestAndSet o soluzioni complesse sui

multiprocessori

⇒ busy-wait o interrupt disabilitati ridotti al minimo, ma non eliminati

• Busy-waiting NON DEVE essere adottato per sezioni critiche applicative e quindi di lunga durata

35

7.4.3 Deadlock & Starvation

• I semafori sono molto meno strutturati ⇒ due o più processi possono attendere su un

semaforo sul quale solo uno di loro può fare (ha un programma tale che fa) una signal =:= deadlock

• È CATTIVA PROGRAMMAZIONE!!! (dei processi)

36

7.4.3 Deadlock & Starvation

• P 0 P 1 wait(S); wait(Q); wait(Q); wait(S); … ... signal(S); signal(Q); signal(Q); signal(S);

7.4.3 Deadlock & Starvation

• Starvation =:= non uscire mai dalla coda di attesa.

• CATTIVA PROGRAMMAZIONE DELLA SIGNAL

– (cioè della exit section dalle sezioni critiche) e quindi dello scheduling

• Applicazioni dei semafori per esercizio

38

Produttore-Consumatore

• Buffer di n posizioni a cui i processi accedono

• Dati condivisi

type item = …

var buffer = array [0..n-1] of item; full, empty, mutex: semaphore; nextp, nextc: item;

full :=0; empty := n; mutex :=1;

39

Produttore-Consumatore

• Produttore

repeat

…

produce an item in nextp … wait(empty); wait(mutex); … signal(mutex); signal(full); until false;

Produttore-Consumatore

remove an item from buffer to nextc …

signal(mutex); signal(empty);

…

consume the item in nextc …

until false;

41

Lettori-Scrittori

• Condividere risorse (ad es. un file) tra molti processi

• Alcuni processi richiedono solo la lettura (processi lettori), altri possono modificare la risorsa (processi scrittori)

• Due o più lettori possono accedere contemporaneamente

• Un processo scrittore deve accedere in mutua esclusione con TUTTI gli altri processi

42

Lettori-Scrittori

• Strutture dati condivise

var mutex, wrt: semaphore (=1); readcount : integer (=0); • Processo scrittore wait(wrt); … writing is performed … signal(wrt);

Lettori-Scrittori

• Processo lettore wait(mutex);

readcount := readcount +1;

if readcount = 1 then wait(wrt);

signal(mutex); … reading is performed … wait(mutex); readcount := readcount – 1;

if readcount = 0 then signal(wrt);

signal(mutex):

44

Problema dei filosofi

• 5 filosofi passano la vita pensando e mangiando • I filosofi condividono un

tavolo rotondo con 5 posti.

• Un filosofo per mangiare deve usare due bacchette Dati condivisi

var chopstick: array [0..4] of semaphore; (=1 initially)

45

Problema dei filosofi

• Philosopher i: repeat wait(chopstick[i+1 mod 5]) wait(chopstick[i]) … eat … signal(chopstick[i]); signal(chopstick[i+1 mod 5]); … think … until false;

Problema dei filosofi

• La soluzione presentata non esclude il deadlock (diverse soluzioni)

– solo 4 filosofi a tavola contemporaneamente – prendere le due bacchette insieme (sezione

critica!)

– prelievo asimmetrico in un filosofo

• Inoltre, si deve escludere starvation di un filosofo

47

7.6 Regioni Critiche Condizionali

• 7.7 Monitor

• Costrutti linguistici inventati per evitare i problemi di programmazione che facilmente si fanno con i semafori

• Attenzione con i thread: in tale ambiente ci sono in genere solo semafori o poco più • Li vedrete nel prossimo corso

48

7.9 Transazioni Atomiche

• Mutua esclusione ⇒ esecuzione indivisibile di sezioni critiche

• Transazione Atomica =:= transazione indivisibile che avviene completamente oppure non avviene affatto

⇒ non sono osservabili stati intermedi ⇒ se non può essere completata con successo,

lascia il mondo inalterato

• È un concetto del mondo dei data base, ma

– utile nei SO

7.9.1 Modello del Sistema

Transazionale

• Transazione =:= funzione logica costituita da molteplici operazioni, fra le quali interessano

– read/write – commit/abort

– abort causato dal SO o dall’hardware (crash!)

• Quando la transazione abortisce bisogna ripristinare lo stato come prima dell’inizio della transazione ⇒ roll-back.

– È compito del sistema transazionale

(SO+ambiente specifico) realizzare il roll-back.

50

Proprietà delle Memorie

• Volatile: si perde per crash (ad es RAM) • Non volatile: sopravvive ai crash

(EEPROM, dischi, nastri, etc) ma ha comunque una significativa probabilità di perdita

• Stabile: non si perde mai (quasi, mai apprezzabilmente)

51

Problematiche

⇒ replicare l'informazione, scriverla e modificarla in modo appropriato ⇒ realizzare transazioni atomiche in un

ambiente in cui ci può essere perdita di informazione su memoria volatile (cioè la memoria volatile non è considerata sufficiente)

7.9.2 Ripristino Basato su Log

• Log =:= registrazione (non logaritmo!) ⇒ registrare su memoria stabile tutte le

modifiche fatte dalla transazione ai dati (che in genere vengono tenuti su memoria non volatile)

• Write-ahead logging: ogni record contiene

– nome della transazione – nome del dato – vecchio valore – nuovo valore

53

7.9.2 Ripristino Basato su Log

• Record per registrare inizio, commit, abort di transazione

• Il log record di write viene scritto prima di fare la write

– due write al posto di una!

∃ due procedure undo(T_i) e redo(T_i) che si basano sul log.

• Sono ambedue idempotenti

54

7.9.2 Ripristino Basato su Log

• Se il log contiene < T_istart> e < T_icommit> e la memoria non volatile si è perduta ⇒ redo(T_i)

• Se il sistema ha un crash allora

– se esiste < Tistart> ma non esiste < Ticommit>

⇒ undo(T_i)

– se esistono ambedue < Tistart> e < Ticommit>

7.9.3 Checkpoint

• Possibile che ad ogni crash dobbiamo rifare tutte le transazioni eseguite dal crash precedente? No!

• Checkpoint =:= punto di verifica

– tutti i record di log da memoria volatile a memoria stabile

– tutti i dati da memoria volatile a memoria stabile

– emettere un log record <checkpoint> sul log in memoria stabile

56

7.9.3 Checkpoint

• Ci si comporta poi così:

– 1. Ad ogni crash si esamina il log cercando dal fondo (all’indietro) l’ultimo record di <checkpoint> che vi si trova

– 2. A partire da tale record di checkpoint si trova all’indietro (prima di tale ultimo <checkpoint>) la più recente Tiche è partita prima del

checkpoint→ la prima < Tistart> che si trova

leggendo all’indietro il file di log

57

7.9.3 Checkpoint

• Nota bene: l’ipotesi è che nel sistema si esegua una transazione alla volta

– 3. Si legge in avanti il file di log facendo undo o redo di tutte le transazioni che si trovano, come nel caso che non si utilizzi il checkpoint

7.9.4 Transazioni Atomiche

Concorrenti

• Devono godere della proprietà di serializzabilità =:= l’effetto finale complessivo ottenuto deve essere identico all’effetto che si sarebbe ottenuto con uno degli ordini di esecuzioni seriale possibili ⇒ abbiamo un problema di mutua esclusione

e sezioni critiche

• Utilizzare un unico semaforo è troppo restrittivo → poco parallelismo

59

7.9.4 Transazioni Atomiche

Concorrenti

• Il parallelismo massimo dipende dal modo con cui i dati vengono usati nelle transazioni • Serial schedule di due transazioni =:=

ognuna delle due transazioni è eseguita in modo atomico, senza parallelismo

T0 T1 read(A) write(A) read(B) write(B) -- read(A) - write(A) - read(B) - write(B) 60

7.9.4 Transazioni Atomiche

Concorrenti

• Se dobbiamo eseguire n transazioni abbiamo n! possibili serial schedule • Ci interessano le schedule non seriali, che

però siano equivalenti ad una schedule seriale

• Schedule non seriali =:= schedule in cui le transazioni si sovrappongono in tempo almeno in parte.

7.9.4 Transazioni Atomiche

Concorrenti

• Quando sono possibili e ancora corrette? • Operazioni O_i∈ Ti, Oj∈ Tjsono dette

conflittuali sse accedono allo stesso dato e almeno una delle due è una write

• Operazioni non conflittuali possono essere eseguite in ordine scambiato senza

modificare l’effetto finale =:= scambio non conflittuale.

62

7.9.4 Transazioni Atomiche

Concorrenti

• Se con una serie di scambi non conflittuali si ottiene una schedule seriale allora

– la schedule di partenza è conflict serializable – è equivalente ad una seriale

– è una valida esecuzione – ha maggior parallelismo!

63

7.9.4 Transazioni Atomiche

Concorrenti

• Esempio di conflitto in una schedule non seriale T0 T1 read(A) -write(A) - ↑ conflitto - read(A) ↓ - write(A) ↑non read(B) - ↓ conflitto write(B) -- read(B)

Protocollo di Locking

• Per assicurare serializzabilità associamo un lock ad ogni dato e seguiamo una regola di comportamento (=:=protocollo) per acquisire i lock prima di accedere alle variabili

• Come nel caso di lettori/scrittori:

– lock condiviso per leggere – lock esclusivo per scrivere

• Stranamente, rilasciare il lock subito dopo l’ultimo accesso ad un dato può produrre non serializzabilità

65

Protocollo di locking a due fasi

• fase di crescita: si acquisiscono lock ma non se ne rilascia nessuno

• fase di assottigliamento: si rilasciano lock ma non se ne acquisisce nessuno

– la transazione è costituita da una sola crescita seguita da un solo assottigliamento

– appena si fa un rilascio non si può che continuare a rilasciare

66

Protocollo di locking a due fasi

• Può dare deadlock

• Non produce tutte le possibili schedule serializzabili (quindi alcune schedule con parallelismo maggiore non vengono generate/permesse)

Protocolli basati su Timestamp

• Determinare in anticipo (prima che a run-time) l’ordinamento fra le operazioni delle transazioni

⇒ associare a T_iun timestamp TS(T_i) • Timestamp totalmente ordinati, assegnati

dal sistema alla partenza di ogni T_i • TS: clock di sistema o contatore logico

68

Protocolli basati su Timestamp

• Se TS(Ti) < TS(Tj) allora la schedule non

seriale deve essere equivalente alla seriale (T_i; T_j)

• Ad ogni dato Q associare

– W_TS(Q) =:= il max TS di ogni Tiche ha

eseguito con successo write(Q), e

– R_TS(Q) =:= il max TS di ogni Tiche ha

eseguito con successo read(Q).

– NB: valori da tenere aggiornati a run-time

69

Protocolli basati su Timestamp

• Logica: far fallire quelle operazioni che farebbero acquisire alla transazione dati sbagliati (attraverso la read) o

invaliderebbero dati già acquisiti per la write.

• Se quando tento di leggere ho che TS < W_TS(Q), i dati che leggo sono sbagliati

Protocolli basati su Timestamp

• Se quando tento di scrivere ho che TS < R_TS(Q), i dati che sovrascrivo sono stati letti e presi per buoni da un’altra transazione • Quando posso eseguire l’operazione il R_TS

o W_TS di Q viene aggiornato

• Quando l’operazione fallisce, la transazione è abortita, rolled-back e deve essere ritentata, ma questa volta avrà un TS maggiore!

71 T0(TS=10) T1(TS=15) read(A) R_TS(A) = 10 -write(A) W_TS(A) = 10 -- read(A) R_TS(A) = 15 - write(A) W_TS(A) = 15 •T0 prima di T1: OK ! •T1 prima di T0 : abort di T0