Parte 2: Sincronizzazione dei Processi (slides 1-44)

6. 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; until false;

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

6.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

6.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

8

6.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.

9

6.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

6.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

11

6.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 Pi può accedere alla sezione

critica

12

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

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> until false; 14

Algoritmo 2

• Soddisfa mutua esclusione, ma non il requisito di progresso

• Consideriamo la seguente sequenza di esecuzione

– P0 pone flag[0] = true

– P₁ pone flag[1] = true

• P₀ e P₁ entrano nel while e non ne escono più !

15

Algoritmo 3

• Usiamo sia turn che flag

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

• Il codice di Pi è repeat

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

while (flag[j] and turn = j) do no_op;

<critical section>

flag[i] := false;

<remainder section>

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

17

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)

18

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 Pi and Pj ricevonolo stesso

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

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 (a₀,…, a_n-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

20

Algoritmo del fornaio(Cont.)

repeat

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; 21

6.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

6.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

23

6.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;

24

6.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

6.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

26

6.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;

27

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;

6.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; wait(sync); • P2 esegue: signal(sync); S2; 29

6.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;

30

6.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

6.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;

• wakeup(P): mette P in ready queue (schedulando o meno a seconda se lo scheduling è pre-emptive)

32

6.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

33

6.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)

6.4.3 Deadlock & Starvation

6.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

36

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;

Produttore-Consumatore

• Produttore

repeat

…

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

Produttore-Consumatore

remove an item from buffer to nextc …

signal(mutex); signal(empty);

…

consume the item in nextc …

until false;

39

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

Lettori-Scrittori

• Strutture dati condivise

var mutex, wrt: semaphore (=1);

readcount : integer (=0); • Processo scrittore wait(wrt); … writing is performed … signal(wrt); 41

Lettori-Scrittori

if readcount = 1 then wait(wrt);

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

if readcount = 0 then signal(wrt);

signal(mutex):

42

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

Problema dei filosofi

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