Sincronizzazione dei processi
Operating System Concepts – 8th Edition
Silberschatz, Galvin and Gagne ©2009
Outline






Il problema della sincronizzazione
Sincronizzazione hardware
Semafori
Monitor
Problemi tipici di sincronizzazione
 Produttori/Consumatori
 Lettori/Scrittori
 5 filosofi
Stallo
Operating System Concepts – 8th Edition
6.2
Silberschatz, Galvin and Gagne ©2009
Outline






Il problema della sincronizzazione
Sincronizzazione hardware
Semafori
Monitor
Problemi tipici di sincronizzazione
 Produttori/Consumatori
 Lettori/Scrittori
 5 filosofi
Stallo
Operating System Concepts – 8th Edition
6.3
Silberschatz, Galvin and Gagne ©2009
Il problema della sincronizzazione

Nei Sistemi Operativi multi-programmati diversi processi o thread sono in esecuzione asincrona e
possono condividere dati

I processi cooperanti possono…

...condividere uno spazio logico di indirizzi, cioè codice e dati (thread)

…oppure solo dati

L’accesso concorrente a dati condivisi può condurre all’incoerenza dei dati nel momento in cui non si
adottano politiche di sincronizzazione

Per garantire la coerenza dei dati occorrono meccanismi che assicurano l’esecuzione ordinata dei
processi cooperanti

… Vediamo un esempio per capire meglio il problema
Operating System Concepts – 8th Edition
6.4
Silberschatz, Galvin and Gagne ©2009
Il problema produttore/consumatore - 1


Consideriamo il problema del produttore e del consumatore dove:

Un produttore genera degli oggetti

Un consumatore preleva gli oggetti
Gli oggetti vengono inseriti/prelevati in un buffer condiviso

Il buffer permette di inserire al più DIM_BUFFER elementi

Una variabile contatore condivisa viene incrementa ogni volta che si aggiunge un elemento nel buffer e si
decrementa ogni volta si preleva un elemento dal buffer

Dati condivisi:
#define DIM_BUFFER 10
typedef struct {
. . .
} Elemento;
Elemento buffer[DIM_BUFFER];
int contatore  0;
Operating System Concepts – 8th Edition
6.5
Silberschatz, Galvin and Gagne ©2009
Produttore e cinsumatore

Produttore

inserisci: indice della successiva posizione libera nel buffer
while (true) {
/* produce un elemento in appena_Prodotto */
while (contatore == DIM_BUFFER) ; /* non fa niente */
buffer[inserisci] = appena_Prodotto;
inserisci = (inserisci + 1) % DIM_BUFFER;
contatore++;
}

Consumatore

preleva : indice della prima posizione piena nel buffer
while (true) {
while (contatore == 0) ; /* non fa niente */
da_Consumare = buffer[preleva];
preleva = (preleva - 1) % DIM_BUFFER;
contatore--;
}
Operating System Concepts – 8th Edition
6.6
Silberschatz, Galvin and Gagne ©2009
Inconsistenza dei dati - 1

La variabile contatore è usata in modo concorrente dal produttore e dal consumatore e quindi il suo valore
potrebbe essere inconsistente ad un certo punto

Se le istruzioni contatore++ e contatore– sono tipicamente implementate in linguaggio macchina nel
seguente modo
registro1 := contatore
registro1 := registro1 + 1
contatore : = registro1

L’esecuzione concorrente di queste istruzioni può portare alla seguente sequenza di istruzioni interleaved:
T0:
T1:
T2:
T3:
T4:
T5:

registro2 := contatore
registro2 := registro2 - 1
contatore : = registro2
produttore esegue
produttore esegue
consumatore esegue
consumatore esegue
produttore esegue
consumatore esegue
registro1
registro1
registro2
registro2
contatore
contatore
=
=
=
=
=
=
contatore
registro1 + 1
contatore
register2 – 1
registro1
registro2
{registro1 = 5}
{registro1 = 6}
{registro2 = 5}
{registro2 = 4}
{contatore = 6}
{contatore = 4}
… Che portano ad avere contatore pari a 4 (per il consumatore) e 6 (per il produttore)!
Operating System Concepts – 8th Edition
6.7
Silberschatz, Galvin and Gagne ©2009
Il problema della sezione critica

Supponiamo di avere n processi {P0, P1,…,Pn} ognuno con una porzione di codice, definita sezione critica (o
regione critica), in cui può modificare dati condivisi


L’esecuzione della sezione critica da parte dei processi deve essere mutuamente esclusiva nel tempo



Ad esempio una variabile, un file, etc.
Un solo processo alla volta può trovarsi nella propria sezione critica
Processi devono quindi cooperare:

Ogni processo deve chiedere il permesso di accesso alla sezione critica, tramite una sezione d’ingresso
(entry section)

La sezione critica è seguita da una sezione d’uscita (exit section)

Il rimanente codice è non critico
Un processo avrà la seguente struttura
while (true) {
sezione di ingresso
sezione critica
sezione di uscita
sezione non critica
}
Operating System Concepts – 8th Edition
6.8
Silberschatz, Galvin and Gagne ©2009
Soluzione al problema della sezione critica

Il problema della sezione critica si affronta progettando un protocollo che i processi possono usare per cooperare
e che deve deve soddisfare i 3 requisiti:

Mutua esclusione

Se il processo Pi è in esecuzione nella sua sezione critica nessun altro processo può trovarsi nella propria
sezione critica


Progresso

Se nessun processo è in esecuzione nella propria sezione critica ed esiste qualche processo che desidera
accedervi, allora la selezione del processo che entrerà prossimamente nella propria sezione critica non può
essere rimandata indefinitamente


Ad esempio nessun processo può impossessarsi della stampante se è già utilizzata da un processo
In altre parole, si deve permettere l’accesso
Attesa limitata

Deve esistere un limite al numero di volte che si consente ai processi di entrare nella propria sezione critica
dal momento in cui un processo precedentemente ha richiesto di farlo

In altre parole, un processo entrerà prima o poi in tempo finito nella propria sezione critica (politica fair
per evitare la starvation)
Operating System Concepts – 8th Edition
6.9
Silberschatz, Galvin and Gagne ©2009
Uso del lock

Per una corretta gestione della sezione critica bisogna garantire
 mutua esclusione



L’accesso alla sezione critica può essere risolto utilizzando uno strumento detto lock (lucchetto)


progresso
attesa illimitata
Tutte le strutture dati condivise sono protette da uno o più lock
Per accedere alle strutture dati è necessario acquisire il possesso del lock che verrà restituito all’uscita
della sezione critica
while (true) {
acquisisce il lock
sezione critica
restituisce il lock
sezione non critica
}
Operating System Concepts – 8th Edition
6.10
Silberschatz, Galvin and Gagne ©2009
Outline






Il problema della sincronizzazione
Sincronizzazione hardware
Semafori
Monitor
Problemi tipici di sincronizzazione
 Produttori/Consumatori
 Lettori/Scrittori
 5 filosofi
Stallo
Operating System Concepts – 8th Edition
6.11
Silberschatz, Galvin and Gagne ©2009
Sincronizzazione hardware

Per poter implementare il concetto della lock esistono istruzioni implementate in hardware nelle moderne
CPU, ad esempio:
 testAndSet(var) - testa e modifica il valore di una cella di memoria
 swap(var1, var2) - scambia il valore di due celle di memoria

L’aspetto fondamentale di queste istruzioni macchina è che sono atomiche ovvero non possono essere
interrotte da un cambio di contesto
 Due istruzione atomiche eseguite contemporaneamente saranno sempre eseguite completamente
in modo sequenziale in un ordine arbitrario
Operating System Concepts – 8th Edition
6.12
Silberschatz, Galvin and Gagne ©2009
TestAndSet

Avendo definito la variabile globale che mantiene lo stato del lock come segue:
boolean lock = false;

L’istruzione testAndSet può essere definita nel seguente modo:
boolean testAndSet(boolean *lockVar) {
boolean valorePrecedente = *lockVar;
*lockVar = true;
return valorePrecedente;
}

Il significato è quello di impostare la variabile lock a true e restituire il suo precedente valore contenuto
in valorePrecedente
Operating System Concepts – 8th Edition
6.13
Silberschatz, Galvin and Gagne ©2009
Mutua esclusione con testAndSet

La mutua esclusione mediate testAndSet può essere realizzata attraverso una variabile booleana
globale lock inizializzata a false nel seguente modo
while (true) {
while(testAndLock(&lock)) ;
sezione critica
lock = false;
sezione non critica
}


La testAndSet per poter risolvere il problema della sezione critica deve poter soddisfare i requisiti di:
 Mutua esclusione
 Progresso
 Attesa limitata
Sono soddisfatti tutti e tre i requisiti?
Operating System Concepts – 8th Edition
6.14
Silberschatz, Galvin and Gagne ©2009
TestAndSet – Mutua Esclusione
while (true) {
while(testAndLock(&lock)) ;
sezione critica /*lock = true*/
lock = false;
sezione non critica
}

Dati due processi P1 e P2 il primo dei due che esegue la testAndSet imposta lock a true ed entra nella
sezione critica

L’altro processo troverà lock a true e si metterà in attesa nel ciclo while
Operating System Concepts – 8th Edition
6.15
Silberschatz, Galvin and Gagne ©2009
TestAndSet – Progresso
while (true) {
while(testAndLock(&lock)) ;
sezione critica /*lock = true*/
lock = false;
sezione non critica
}

Un processo P dopo aver lasciato la sezione critica imposta lock a false permettendo ad un altro processo di
entrare nella sezione critica
Operating System Concepts – 8th Edition
6.16
Silberschatz, Galvin and Gagne ©2009
TestAndSet con attesa limitata
while (true) {
attesa[i] = true;
chiave = true;
Strutture dati condivise: lock e attesa[n]
while (attesa[i] && chiave)
chiave = testAndSet(&lock);
attesa[i] = false;
Mutua esclusione:
Entra nella sezione critica quando chiave è false o attesa[i] è false
sezione critica
j = (i + 1) % n;
while ((j != i) && !attesa[i])
j = (j + 1) % n;
Progresso:
In uscita imposta lock=false a
if (j==i)
lock = false;
else
attesa[j] = false;
Attesa limitata:
Scorre la lista e trova il primo interessato ad entrare
sezione non critica
}

Il processo che esce dalla propria sezione critica designa attraverso una coda circolare il prossimo processo che
può entrare

Qualsiasi processo che intende entrare nella sezione critica attenderà al più n-1 turni
Operating System Concepts – 8th Edition
6.17
Silberschatz, Galvin and Gagne ©2009
Outline






Il problema della sincronizzazione
Sincronizzazione hardware
Semafori
Monitor
Problemi tipici di sincronizzazione
 Produttori/Consumatori
 Lettori/Scrittori
 5 filosofi
Stallo
Operating System Concepts – 8th Edition
6.18
Silberschatz, Galvin and Gagne ©2009
Semafori

Un semaforo S è una variabile intera utilizzata come strumento di sincronizzazione

Le due operazioni atomiche possibili su S sono:

wait(S)

signal(S)
wait(S) {
while(S <= 0)
; //no-op
S--;
}
Operating System Concepts – 8th Edition
signal(S) {
S++;
}
6.19
Silberschatz, Galvin and Gagne ©2009
Esempi di uso del semaforo

Accesso a sezioni critiche

Un semaforo può essere utilizzato per risolvere il problema dell’accesso alla sezione critica tra n processi
mediante un semaforo comune mutex (mutual exclusion) inizializzato ad 1
while (true) {
wait(mutex);
sezione critica
signal(mutex);
sezione non critica
}

Sincronizzazione di operazioni

Supponiamo che il processo P1 debba compiere una operazione op1 prima dell’operazione op2 del
processo P2. Quindi op2 sarà eseguita solo dopo che op1 termina

Utilizziamo un semaforo mutex inizializzato a 0
op1;
signal(mutex);
Operating System Concepts – 8th Edition
wait(mutex);
op2;
6.20
Silberschatz, Galvin and Gagne ©2009
Evitare il busy waiting dei semafori - 1

I processi che girano inutilmente mentre attendono un semaforo per il rilascio di una risorsa sono chiamati spin
lock (girano sul lucchetto)

Il busy waiting o attesa attiva costituisce un problema per i sistemi multiprogrammati, perché la condizione di
attesa spreca cicli di CPU che altri processi potrebbero sfruttare produttivamente

L’attesa attiva è vantaggiosa solo quando è molto breve perché, in questo caso, può evitare un context switch

Per evitare il busy waiting possiamo modificare la definizione di wait in modo che:

Il processo invoca una wait per ottenere una risorsa

Se la risorsa è in uso, blocca se stesso inserendosi in una coda di attesa del semaforo e passando nello
stato di attesa

Lo scheduler della CPU può quindi selezionare un altro processo pronto per l’esecuzione

Il processo sarà sbloccato da una signal da parte di qualche altro processo
Operating System Concepts – 8th Edition
6.21
Silberschatz, Galvin and Gagne ©2009
Evitare il busy waiting dei semafori - 2

Per realizzare l’operazione di bloccaggio abbiamo bisogno di una struttura dati semaforo implementata nel
seguente modo
typedef struct {
int valore;
struct Processo *lista;
} semaforo;


Il sistema operativo deve inoltre fornire due operazioni:

block() – sospende il processo che la invoca

wakeup(P) – pone in stato di pronto il processo P bloccato
Le operazioni wait() e signal() saranno realizzate nel seguente modo:
wait(semaforo *S) {
S->valore--;
if(S->valore < 0) {
aggiungi questo processo a S->lista
block();
}
}
Operating System Concepts – 8th Edition
signal(semaforo *S) {
S->valore++;
if(S->valore <= 0) {
togli un processo P da S->lista
wakeup(P);
}
}
6.22
Silberschatz, Galvin and Gagne ©2009
Outline






Il problema della sincronizzazione
Sincronizzazione hardware
Semafori
Monitor
Problemi tipici di sincronizzazione
 Produttori/Consumatori
 Lettori/Scrittori
 5 filosofi
Stallo
Operating System Concepts – 8th Edition
6.23
Silberschatz, Galvin and Gagne ©2009
Monitors
Incapsula dati osservabili e modificabili
solamente dall’ “interno” del monitor
Costrutto
linguistico
Realizza l’accesso in
mutua esclusione ai dati
che incapsula
una sola procedura d’accesso
alla volta può essere attiva
(1 processo alla volta)
Operating System Concepts – 8th Edition
6.24
Silberschatz, Galvin and Gagne ©2009
Monitor

Il monitor è un costrutto di sincronizzazione di alto livello che permette la condivisione sicura di un tipo astratto di
dati fra processi concorrenti

Incapsula i dati privati mettendo a disposizione metodi pubblici per operare su tali dati

La rappresentazione di un tipo monitor è formata da:


dichiarazioni di variabili i cui valori definiscono lo stato di un’istanza del tipo

procedure o funzioni che realizzano le operazioni sul tipo stesso
Supportati da Concurrent Pascal, C#, Java
Operating System Concepts – 8th Edition
6.25
Silberschatz, Galvin and Gagne ©2009
Esempio di monitor in Java?
Variabili condivise il cui accesso
deve avvenire in mutua esclusione
class MyMonitor {
private int dato1;
private Vector dato 2;
public void cambiaDato2() {
synchronized(this) {
…
}
}
public int getDato1() {
synchronized(this) {
…
}
}
}
Operating System Concepts – 8th Edition
6.26
Silberschatz, Galvin and Gagne ©2009
Outline






Il problema della sincronizzazione
Sincronizzazione hardware
Semafori
Monitor
Problemi tipici di sincronizzazione
 Produttori/Consumatori
 Lettori/Scrittori
 5 filosofi
Stallo
Operating System Concepts – 8th Edition
6.27
Silberschatz, Galvin and Gagne ©2009
Problemi tipici di sincronizzazione

Alcuni problemi tipici di sincronizzazione dove poter verificare schemi di sincronizzazione sono:

Problema dei produttori e consumatori

Problema dei lettori e degli scrittori

Problema dei cinque filosofi
Operating System Concepts – 8th Edition
6.28
Silberschatz, Galvin and Gagne ©2009
Problema dei produttori e consumatori

Il problema del produttore e del consumatore con memoria limitata può essere risolto utilizzando i
semafori e le seguenti strutture dati

buffer[DIM_BUFFER]


buffer circolare di dimensione limitata
Semafori piene, vuote, mutex

piene inizializzato a 0, mantiene il numero degli elementi inseriti

vuote inizializzato a n, mantiene il numero delle posizioni libere

mutex inizializzato ad 1, sincronizza gli accessi al buffer
Va in attesa se buffer è utilizzato (mutex = 0)
Va in attesa se piene è <= 0
Va in attesa se buffer è utilizzato (mutex = 0)
Va in attesa se vuote è <= 0
while(true) {
produce un elemento in prod
wait(vuote);
wait(mutex);
…
inserisce in buffer l’elemento prod
…
signal(mutex);
signal(piene);
}
while(true) {
wait(piene);
wait(mutex);
…
rimuove un elemento da buffer e lo mette in prod
…
signal(mutex);
signal(piene);
…
consuma l’elemento in prod
}
Consumatore
Produttore
Operating System Concepts – 8th Edition
6.29
Silberschatz, Galvin and Gagne ©2009
Problema dei lettori e degli scrittori

Un insieme di dati (ad es., un file) deve essere condiviso da più
processi concorrenti che possono:

Lettori: richiedere la sola lettura del contenuto…

Scrittori: richiedere l’accesso ai dati sia in lettura che in scrittura

I processi lettori possono accedere contemporaneamente al file

Un processo scrittore deve accedere in mutua esclusione con tutti gli
altri processi (sia lettori che scrittori)

Strutture dati condivise:


numLettori: Inizializzato a 0, mantiene il numero di processi
che leggono i dati
while(true) {
wait(mutex);
numLettori++;
if(numLettori == 1)
wait(scrittura);
signal(mutex);
…
esegue l’operazione di lettura
…
wait(mutex);
numLettori--;
if(numLettori == 0)
signal(scrittura);
signal(mutex);
}
Lettore
Semafori mutex ,scrittura

mutex inizializzato a 1, gestisce l’accesso a numLettori

scrittura inizializzato a 1, gestisce la mutua esclusione
nella scrittura
while(true) {
wait(scrittura);
…
esegue l’operazione di scrittura
…
signal(scrittura);
}
Scrittore
Operating System Concepts – 8th Edition
6.30
Silberschatz, Galvin and Gagne ©2009
Problema dei cinque filosofi

Il problema dei 5 filosofi è un classico problema di sincronizzazione
sviluppato da Dijkstra

Cinque filosofi passano la loro vita pensando e mangiando

I filosofi siedono attorno ad un tavolo rotondo con 5 posti

Un filosofo può essere nei seguenti stati:

Pensa: non interagisce con niente e nessuno

Mangia: tenta di prendere le bacchette alla sua destra ed
alla sua sinistra

Il filosofo può appropriarsi di una sola bacchetta alla volta

Quando un filosofo affamato possiede due bacchette
contemporaneamente, mangia; terminato il pasto, appoggia
le bacchette e ricomincia a pensare


Variabili condivise:

La zuppiera di riso (l’insieme dei dati)

Cinque semafori, bacchetta[5], inizializzati ad 1
La soluzione con i semafori non esclude la possibilità di deadlock

I filosofi hanno fame contemporaneamente ed ognuno
si impossessa della bacchetta alla propria sinistra
Operating System Concepts – 8th Edition
6.31
while(true) {
wait(bacchetta[i]);
wait(bacchetta[(i+1) % 5]);
…
mangia
…
signal(bacchetta[i]);
signal(bacchetta[(i+1) % 5]);
…
pensa
…
}
Silberschatz, Galvin and Gagne ©2009
Outline






Il problema della sincronizzazione
Sincronizzazione hardware
Semafori
Monitor
Problemi tipici di sincronizzazione
 Produttori/Consumatori
 Lettori/Scrittori
 5 filosofi
Stallo
Operating System Concepts – 8th Edition
6.33
Silberschatz, Galvin and Gagne ©2009
Come risolvere
il deadlock?
Operating System Concepts – 8th Edition
6.34
Silberschatz, Galvin and Gagne ©2009
Condizioni Necessarie e Sufficienti per Generare
uno Stato di Deadlock
divieto di rapina
(no preemption)
accesso in mutua
esclusione alle risorse
acquisizione incrementale
delle risorse
attese circolari
Operating System Concepts – 8th Edition
6.35
Silberschatz, Galvin and Gagne ©2009
Accesso in mutua esclusione

Alcune risorse sono per natura non condivisibili quindi è difficile prevenire lo
stallo negando la condizione di mutua esclusione …
Operating System Concepts – 8th Edition
6.36
Silberschatz, Galvin and Gagne ©2009
Acquisizione incrementale

Acquisire tutte le risorse atomicamente


acquisire le 2 forchette con una unica azione
Rilascio risorse con timeout

rilasciare una forchetta acquisita se trascorso un certo tempo non si riesce
a progredire (starvation, livelock)
Operating System Concepts – 8th Edition
6.37
Silberschatz, Galvin and Gagne ©2009
No Preemption

È possibile “rubare” le risorse a processi che le hanno già acquisite


prendere una forchetta già acquisita da un filosofo
Rollback

rilasciare tutte le forchette e ricominciare
Operating System Concepts – 8th Edition
6.38
Silberschatz, Galvin and Gagne ©2009
Attese circolari

Protocolli ad-hoc

Introdurre un ordine specifico di acquisizione delle risorse


alcuni filosofi acquisiscono le forchette in ordine inverso
Escludere alcuni processi dall’attività

solamente 4 dei 5 filosofi possono sedersi al tavolo
Operating System Concepts – 8th Edition
6.39
Silberschatz, Galvin and Gagne ©2009
Alcune soluzioni al problema dei filosofi

Se dopo un certo perido di tempo la bacchetta mancante non si libera, si
rilascia qualla acquisita


Un filosofo può prendere le bacchette solo se sono entrambe disponibili


Viola acquisizione incrementale
Alcuni filosofi prendono le bacchette con ordine inverso


Viola acquisizione incrementale
Viola attese circolari
Solo quattro filosofi possono stare a tavola contemporaneamente

Viola attese circolari
Operating System Concepts – 8th Edition
6.40
Silberschatz, Galvin and Gagne ©2009