6.1 Sistemi operativi Sincronizzazione di processi Background Il problema delle sezioni critiche...

Sistemi operativi6.1

Sincronizzazione di processi

• Background

• Il problema delle sezioni critiche

• Hardware di sincronizzazione

• Semafori

• Problemi classici di sincronizzazione

• Regioni critiche

• Monitor


Background

• L’accesso concorrente a dati condivisi può causare incoerenza nei dati.

• Il mantenimento della coerenza dei dati richiede meccanismi che assicurino l’esecuzione ordinata dei processi cooperanti.

• La soluzione con memoria condivisa del problema del buffer limitato permette al più n–1 elementi residenti contemporaneamente nel buffer. Una soluzione in cui tutti gli n elementi del buffer siano impiegati non è semplice.

– Si può pensare di modificare il codice del produttore-consumatore aggiungendo una variabile counter, inizializzata a 0 e incrementata ogni volta che un nuovo elemento viene inserito nel buffer.


Buffer limitato• Dati condivisi

type item = … ;

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

in, out: 0..n-1;

counter: 0..n;

in, out, counter := 0;

• Processo produttore

repeat

…

produce un elemento in nextp

…

while counter = n do no-op;

buffer [in] := nextp;

in := in + 1 mod n;

counter := counter +1;

until false;


Buffer limitato• Processo consumatore

repeat

while counter = 0 do no-op;

nextc := buffer [out];

out := out + 1 mod n;

counter := counter – 1;

…

consuma l’elemento in nextc

…

until false;

• Le istruzioni counter := counter + 1; e counter := counter - 1; devono essere operazioni atomiche. In realtà counter := counter +1 corrisponde a

register := counter;

register := register + 1;

counter := register;


Problema della sezione critica

• Si hanno n processi che competono per usare alcuni dati condivisi.

• Ciascun processo ha una parte di codice, chiamata sezione critica, in cui accede a dati condivisi.

• Problema – assicurare che quando un processo esegue la sezione critica, nessun altro processo possa eseguire la propria sezione critica.

• Struttura del processo Pi

repeat

entry section

sezione critica

exit section

sezione non critica

until false;


Condizioni per la soluzione del problema della sezione critica

1. Mutua esclusione. Se il processo Pi sta eseguendo la propria sezione critica, allora nessun altro processo può eseguire le proprie sezioni critiche.

2. Progresso. Se nessun processo è in esecuzione nella propria sezione critica ed esiste qualche processo che desidera entrare nella propria sezione critica, allora la selezione del processo che può entrare nella propria sezione critica non può essere rimandata indefinitamente.

3. Attesa limitata. E’ necessario porre un limite al numero di volte che si consente ad altri processi di entrare nelle proprie sezioni critiche, prima che la richiesta del primo processo sia stata accordata.

Si assume che ciascun processo sia eseguito ad una velocità diversa da zero. Non si fanno assunzioni relative alla velocità relativa degli n processi.


Primi tentativi di soluzione del problema

• Solo 2 processi, P0 e P1

• Struttura generale del processo Pi (altro processo Pj)

repeat

entry section

sezione critica

exit section

sezione non critica

until false;

• I processi possono condividere alcune variabili comuni per sincronizzare le proprie azioni.


Algoritmo 1

• Variabili condivise: – var turn: 0..1;

(inizialmente turn = 0)

– Se turn = i Pi può entrare nella propria sezione critica

• Processo Pi

repeat

while turn i do no-op;

sezione critica

turn := j;

sezione non critica

until false;

• Soddisfa la mutua esculsione, ma non il progresso. Se turn=0, P1 non può entrare nella propria sezione critica, anche se P0 si trova nella propria sezione non critica.


Algoritmo 2

• Variabili condivise

– var flag: array [0..1] of boolean;(inizialmente flag [0] = flag [1] = false).

– Se flag [i] = true Pi è pronto ad entrare nella propria sez. critica

• Processo Pi

repeat

flag[i] := true;while flag[j] do no-op;

sezione critica

flag [i] := false;

sezione non critica

until false;

• Soddisfa la mutua esculsione, ma non il progresso. I due processi possono settare entrambi flag[i] = true, bloccandosi indefinitamente.


Algoritmo 3

• Combina le variabili condivise degli algoritmi 1 e 2.

• Processo Pi

repeat

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

sezione critica

flag [i] := false;

sezione non critica

until false;

• Sono soddisfatte tutte e tre le condizioni. Risolve il problema della sezione critica per due processi. Pi entra nella sezione critica (progresso) al massimo dopo un’entrata da parte di Pj (attesa limitata).


Algoritmo del fornaio

• Prima di entrare in una sezione critica, i processi ricevono un numero (biglietto del negozio). Il possessore del numero più basso entra nella sezione critica.

• Se i processi Pi e Pj ricevono lo stesso numero, se i < j, allora Pi viene servito prima, altrimenti Pj è servito prima.

• Lo schema di numerazioni genera sempre numeri non decrescenti; esempio, 1,2,3,3,3,3,4,5...

Soluzione del problema delle sezioni critiche per n processi

• Notazione per indicare il numero e il processo (numero #, 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 per i = 0, …, n – 1

• Dati condivisi

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

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

Le strutture dati sono inizializzate a false e 0 rispettivamente


Algoritmo del fornaio

repeatchoosing[i] := true;number[i] := max(number[0], number[1], …, number [n – 1])+1;choosing[i] := false;for j := 0 to n – 1

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

and (number[j],j) < (number[i], i) do no-op; end;sezione critica

number[i] := 0; sezione non critica

until false;

number[i] = 0 indica che Pi non vuole entrare in sezione critica.


Hardware di sincronizzazione

• E’ necessario per testare e modificare il contenuto di una parola in modo atomico.

function Test-and-Set (var target: boolean): boolean;

begin

Test-and-Set := target;target := true;

end;


Mutua Esclusione con Test-and-Set

• Dati condivisi: var lock: boolean; (inizialmente false)

• Processo Pi

repeat

while Test-and-Set (lock) do no-op;

sezione critica

lock := false;

sezione non critica

until false;

Non soddisfa attesa limitata (qualunque processo può passare avanti).


Semafori

• I semafori sono strumenti di sincronizzazione.

• Il semaforo S è una variabile intera.

• Si può accedere al semaforo solo attraverso due operazioni indivisibili (atomiche).

wait (S): while S 0 do no-op;S := S – 1;

signal (S): S := S + 1;


Esempio: sezione critica con n processi

• Variabili condivise

– var mutex : semaforo; (inizialmente mutex = 1)

• Processo Pi

repeat

wait(mutex);

sezione critica

signal(mutex);

sezione non critica

until false;


Implementazione dei semafori

• Per evitare di lasciare un processo in attesa nel ciclo while si può implementare il semaforo nel seguente modo

• Si definisce un semaforo come un record

type semaphore = record

value: integer

L: list of process;

end;

• Si assume che siano disponibili due semplici operazioni:

– block sospende il processo che lo chiama.

– wakeup(P) riprende l’esecuzione di un processo bloccato P.


Implementazione dei semafori

• Le operazioni dei semafori possono essere definite come

wait(S): S.value := S.value – 1;

if S.value < 0

then begin

aggiungere questo processo a S.L;block;

end;

signal(S): S.value := S.value = 1;

if S.value 0

then begin

rimuovere il processo P da S.L;wakeup(P);

end;

In un ambiente con un unico processore è possibile disabilitare le

interruzioni all’inizio e alla fine delle operazioni wait e signal.


Uso dei semafori

• Eseguire B in Pj solo dopo che A è stato eseguito in Pi

• Si impiega un semaforo flag inizializzato a 0

• Codice:

Pi Pj

. . . . . . . .

A wait(flag)

signal(flag) B. .. .. .


Deadlock e Starvation

• Deadlock – due o più processi sono in attesa indefinita per un evento che può essere generato solo da uno dei due processi in attesa.

• Siano S e Q due semafori inizializzati a 1

P0 P1

wait(S); wait(Q);

wait(Q); wait(S);

. .

. .

. .

. .

signal(S); signal(Q);

signal(Q); signal(S);

Se dopo wait(S) di P0 viene eseguita wait(Q) di P1 si ha un deadlock.

• Starvation – blocco indefinito. Un processo attende indefinitamente ad un semaforo, e non può essere mai rimosso dalla coda del semaforo in cui è sospeso.


Due tipi di semafori

• Semaforo contatore – intero che può assumere valori in un dominio non limitato.

• Semaforo binario – intero che può essere settato solo a 0 o 1; può essere implementato più semplicemente.

• Si può ovviamente implementare un semaforo binario per mezzo di un semaforo contatore. Ma anche il viceversa è possibile.


Problemi classici di sincronizzazione

• Problema del buffer limitato

• Problema di scrittore e lettore (produttore-consumatore)

• Problema dei cinque filosofi


Problema del buffer limitato• Dati condivisi

type item = …var buffer: …

full, empty, mutex: semaphore;nextp, nextc: item;full :=0; empty := n; mutex :=1;

• Processo produttorerepeat

…produce un elemento in nextp

…wait(empty);wait(mutex);

… inserisce nel buffer l’elemento in nextp

…signal(mutex);signal(full);

until false;


Problema del buffer limitato

• Processo consumatorerepeat

wait(full)wait(mutex);

…rimuove un elemento da buffer e lo pone in nextc

…signal(mutex);signal(empty);

…consuma l’elemento in nextc

…until false;


Problema scrittori–lettori

• Alcuni processi devono accedere in lettura e/o scrittura ad una risorsa condivisa (es. file).

• Se due lettori accedono contemporaneamente all’insieme di dati non ci sono problemi.

• Gli scrittori devono avere accesso esclusivo all’insieme di dati condivisi.

• Due formulazioni del problema sono le seguenti:

– Nessun lettore rimanga in attesa, a meno che uno scrittore abbia già ottenuto il permesso di utilizzare l’insieme di dati condiviso.

– Uno scrittore, una volta pronto, esegua il proprio compito di scrittura al più presto (nessun nuovo lettore deve iniziare la lettura da questo momento).


Problema scrittori–lettori

• Dati condivisi var mutex, wrt: semaphore (=1);readcount: integer (=0);

• Processo scrittorewait(wrt);

…si effettua la scrittura

…signal(wrt);

• Processo lettorewait(mutex);

readcount := readcount +1;if readcount = 1 then wait(wrt);

signal(mutex); …

si effettua la lettura …

wait(mutex);readcount := readcount – 1;if readcount = 0 then signal(wrt);

signal(mutex);


Problema dei 5 filosofi

• I filosofi mangiano e pensano.

• Quando un filosofo ha fame, tenta di prendere le due bacchette che ha accanto.

• Prende prima una bacchetta poi l’altra.

• Non rilascia le bacchette finché non ha finito.



• Filosofo i:repeat

wait(chopstick[i])wait(chopstick[i+1 mod 5])

…mangia …

signal(chopstick[i]);signal(chopstick[i+1 mod 5]);

…pensa …

until false;

• Dati condivisi

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



• Non esclude il deadlock, ad esempio se tutti i filosofi hanno fame contemporaneamente e prendono prima la bacchetta alla loro destra.

• Alcune soluzioni:– Solo quattro filosofi possono essere seduti contemporaneamente a tavola.– Un filosofo può prendere le sue bacchette solo se sono entrambe disponibili (attenzione alle sezioni critiche).– Adottare una soluzione asimmetrica. Un filosofo dispari prende prima la bacchetta di sinistra, un filosofo pari prende prima

la bacchetta di destra.


Regioni critiche

• Un errato utilizzo dei semafori può condurre a degli errori è necessario un costrutto di sincronizzazione di alto livello.

• Una variabile condivisa v di tipo T, viene dichiarata come:

var v: shared T;

• Si può accedere alla variable v solo con l’istruzione

region v when B do S;

dove B è un’espressione booleana. Mentre l’istruzione S è in esecuzione, nessun altro processo può accedere alla variabile v.

• Le regioni che si riferiscono alla stessa variabile condivisa escludono qualunque altra.

• Quando un processo tenta di eseguire l’istruzione region, viene valutata l’espressione booleana B. Se questa è falsa, il processo è ritardato fino a che B diventa vera e nessun altro processo si trova nella regione associata con v.


Esempio: buffer limitato

• Variabili condivise:

var buffer: shared record

pool: array [0..n–1] of item;count,in,out: integer

end;

• Il processo produttore inserisce nextp nel buffer condiviso

region buffer when count < ndo begin

pool[in] := nextp;in:= in+1 mod n;count := count + 1;

end;

• Il processo consumatore rimuove un elemento dal buffer condiviso e lo pone in nextcregion buffer when count > 0

do begin nextc := pool[out];out := out+1 mod n;count := count – 1;

end;


Implementazione di region x when B do S

• Si associano con la variabile condivisa x le seguenti variabili:

var mutex, first-delay, second-delay: semaphore;first-count, second-count: integer,

• L’accesso mutuamente esculsivo alla sezione critica è fornito da mutex.

• Se un processo non può entrare nella sezione critica perché l’espressione booleana B è falsa, attende inizialmente nel semaforo first-delay; viene poi mosso nel semaforo second-delay prima che gli sia consentito di valutare ancora B.

• Si tiene traccia del numero di processi che attendono in first-delay e second-delay, per mezzo di first-count e second-count.

• L’algoritmo assume un ordinamento FIFO nell’accodamanto dei processi per un semaforo.

• Per avere una disciplina di accodamento arbitraria, è richiesta una implementazione più complicata.


wait(mutex);while not B

do begin first-count := first-count + 1;if second-count > 0

then signal(second-delay);else signal(mutex);

wait(first-delay):first-count := first-count – 1;if first-count > 0 then signal(first-delay);

else signal(second-delay);wait(second-delay);second-count := second-count – 1;

end;S;if first-count >0

then signal(first-delay);else if second-count >0

then signal(second-delay);else signal(mutex);


• E’ un costrutto di sincronizzazione di alto livello che permette la condivisione sicura di un tipo astratto di dati fra processi concorrenti.

type monitor-name = monitordichiarazione variabiliprocedure entry P1 :(…);

begin … end;procedure entry P2(…);

begin … end;………….

procedure entry Pn (…);begin…end;

begincodice di inizializzazione

end

MonitorMonitor


• Per permettere ad un processo di attendere dentro al monitor, variabili condition devono essere dichiarate come segue:

var x, y: condition

• La variabile condizione può essere usata solo con le operazioni wait e signal.

– L’operazione

x.wait;vuol dire che il processo che chiama questa operazione viene sospeso finché un altro processo chiama

x.signal;

– L’operazione x.signal riprende esattamente un processo sospeso. Se nessun processo è sospeso, allora l’operazione di signal non ha effetto.

MonitorMonitor


Monitor e monitor con variabili conditionMonitor e monitor con variabili condition


type dining-philosophers = monitorvar state : array [0..4] of :(thinking, hungry, eating);var self : array [0..4] of condition;procedure entry pickup (i: 0..4);

beginstate[i] := hungry;test (i);if state[i] eating then self[i], wait;

end;

procedure entry putdown (i: 0..4);begin

state[i] := thinking;test (i+4 mod 5);test (i+1 mod 5);

end;

Esempio dei filosofiEsempio dei filosofi


procedure test(k: 0..4);begin

if state[k+4 mod 5] eatingand state[k] = hungryand state[k+1 mod 5] ] eatingthen begin

state[k] := eating;self[k].signal;

end;

end;

beginfor i := 0 to 4

do state[i] := thinking;

end.

Esempio dei filosofiEsempio dei filosofi


• Variabili var mutex: semaphore (init = 1)

next: semaphore (init = 0)next-count: integer (init = 0)

• Ciascuna procedura esterna F viene rimpiazzata conwait(mutex); … corpo di F; …if next-count > 0

then signal(next);else signal(mutex);

• La mutua esclusione viene assicurata con un monitor.

Implementazione del monitor con semaforiImplementazione del monitor con semafori


• Per ogni variabile condizione x si ha:var x-sem: semaphore (init = 0)

x-count: integer (init = 0)

• L’operazione x.wait può essere implementata con:x-count := x-count + 1;if next-count >0

then signal(next)else signal(mutex);

wait(x-sem);x-count := x-count – 1;

Implementazione del monitorImplementazione del monitor

• L’operazione x.signal può essere implementata con:if x-count > 0

then beginnext-count := next-count + 1;signal(x-sem);wait(next);next-count := next-count – 1;

end;


• Costrutto Conditional-wait: x.wait(c);

– c: espressione intera valutata quando viene eseguita l’operazione wait.

– Il valore di c (numero di priorità) viene memorizzato con il nome del processo che viene sospeso.

– Quando si esegue x.signal, si riprende il processo che ha associato il numero di priorità più basso.

• Si controllano due condizioni per stabilire la correttezza del sistema:

– I processi utente devono sempre fare le loro chiamate al monitor con una sequenza corretta.

– E’ necessario assicurare che un processo non cooperativo non ignori la porta di mutua esclusione fornita dal monitor, e provi ad accedere direttamente alle variabili condivise, senza impiegare i protocolli di accesso.

Implementazione del monitorImplementazione del monitor

6.1 Sistemi operativi Sincronizzazione di processi Background Il problema delle sezioni critiche...

Documents

Transcript of 6.1 Sistemi operativi Sincronizzazione di processi Background Il problema delle sezioni critiche...