7. Sincronizzazione tra processi
Con l'avvento della multiprogrammazione e dei sistemi multicore รจ nata la necessitร di gestire l'accesso concorrente dei processi (in particolare i thread) alle risorse condivise. Solitamente infatti, quando i thread accedono ad un'area di memoria comune, si possono verificare errori nella consistenza (consistency) dei dati. Si parla in particolare di race condition laddove il contenuto di un'area di memoria condivisa o il valore letto da questa dipende dall'ordine di esecuzione dei processi. Ciรฒ รจ chiaramente un problema in quanto fa sรฌ che il codice non sia piรน univoco nelle operazioni svolte e nei risultati generati a paritร di input (matematicamente non sarebbe piรน una funzione).
Esempio
Prendiamo in considerazione un modello in cui 2 processi vengono divisi in produttore e consumatore.
- Produttore: produce un messaggio
- Consumatore: consuma un messaggio
Si ha inoltre un'esecuzione concorrente tramite un buffer:
- Produttore: aggiunge al buffer (non posso aggiungere se il buffer รจ pieno)
- Consumatore: toglie dal buffer (non posso consumare se il buffer รจ vuoto)
Il tutto viene regolato da una variabile condivisa counter che indica il numero di elementi nel buffer.
- Produttore: aumenta counter di
alla volta - Consumatore: diminuisce counter di
alla volta
Questo tuttavia introduce un problema: i due processi possono modificare counter contemporaneamente (es. macchina multiprocessore che esegue i thread allo stesso momento) e potrebbe capitare che i due processi aumentano e diminuiscono counter allo stesso tempo.
/%F0%9F%92%BE%20Sistemi%20Operativi/Teoria/_images/Inconsistenza.png)
ร importante quindi proteggere l'accesso alla cosiddetta sezione critica.
Sezione critica
La sezione critica รจ una porzione di codice in cui si accede ad una risorsa condivisa (per esempio la modifica di una variabile). Una qualsiasi soluzione al problema della sezione critica deve avere i seguenti requisiti:
- Mutua esclusione: Solo un processo alla volta puรฒ accedere alla sezione critica.
- Progresso: Solo i processi che vogliono entrare nella sezione critica possono partecipare per decidere chi di loro puรฒ entrare. Tale decisione deve avvenire in tempo definito. Per esempio, solo le persone che stanno aspettando per andare in bagno possono decidere chi entra, non persone esterne.
- Attesa limitata (bounded waiting): Esiste un numero massimo di volte consecutive per il quale un processo puรฒ aspettare prima di entrare in sezione critica (ovvero il processo deve poter entrare prima o poi).
Il problema di sincronizzazione puรฒ essere risolto tramite software o hardware. Entrambe le soluzioni richiedono codice aggiuntivo, ma la soluzione con HW รจ considerata generalmente piรน efficiente, in quanto, nonostante necessiti di apposito HW, usa meno risorse. Inoltre, le architetture moderne non supportano piรน la sincronizzazione software, in quanto la naturale evoluzione dell'HW ha reso tale soluzione molto piรน conveniente.
Vediamo ora nel dettaglio alcuni algoritmi per la sincronizzazione a livello software.
Soluzioni Software
Algoritmo 1
In questa soluzione sono presenti due soli processi. Uso la variabile turn come una sorta di chiave. Il processo che "possiede" il turn puรฒ entrare nella SC, mentre gli altri processi devono aspettare. Si garantisce cosรฌ la mutua esclusione.
Questo tuttavia introduce ad un problema. Infatti se uno dei due processi non ha piรน necessitร di entrare nella sezione critica, anche l'altro processo non puรฒ piรน entrare in essa, visto che il turn continua a tenerselo il processo che รจ andato via, ma non lo restituirร piรน agli altri processi, perchรจ sta eseguendo il codice dopo a turn = j. Questo porta ad una violazione del criterio del progresso.
PROCESS i;
int turn; // se turn == i allora รจ il turno di i
while (true)
{
while (turn != i); // aspetto che arrivi il mio turno
#sezione critica
turn = j;
#sezione non critica
}
Algoritmo 2
In questa soluzione sono presenti due soli processi. Uso il vettore flag come una sorta di chiave. Il processo
Infatti se uno dei due processi va in errore e quindi si interrompe, lascia flag[i] a true, impedendo all'altro processo di accedere alla SC (andrร in loop nel while). Oppure, se un processo imposta flag[i] a true, e parte improvvisamente l'altro processo che imposta a sua volta flag[i] a true, avremo una situazione di stallo (i due processi vanno in loop nel while). Vedremo in seguito che queste situazioni vengono dette deadlock.
PROCESS i;
boolean flag[2]; //inizializzato a false
while (true)
{
flag[i] = true; //vuole entrare nella SC
while (flag[j] == true); // aspetta che flag[j] == false
#sezione critica
flag[i] = false; //sono uscito dalla SC
#sezione non critica
}
Algoritmo 2 - variante
La soluzione รจ simile a quella precedente ma abbiamo invertito le istruzioni della sezione di entrata. Qui perรฒ si introduce un nuovo problema, violando cosรฌ la mutua esclusione. Infatti entrambi i processi possono trovarsi nella SC se eseguono in sequenza il while prima di impostare la flag[i] a true (cioรจ entrano nel while ma si interrompono prima di settare flag[i] a true.
PROCESS i;
boolean flag[2];
while (true)
{
while (flag[j] == true); // aspetta che flag[j] == false
flag[i] = true; //vuole entrare nella SC
#sezione critica
flag[i] = false; //sono uscito dalla SC
#sezione non critica
}
Algoritmo 3
In questa soluzione sono presenti due soli processi. Uso sia la variabile turn che il vettore flag. Il processo deve avere sia turn che flag[i] a true per entrare nella SC. Entrambi i processi potrebbero avere flag impostata a true ma solo uno dei due avrร il turn. Questa soluzione rispetta i
PROCESS i;
int turn; //per decidere a chi tocca
boolean flag[2]; //per capire chi รจ interessato alla SC, รจ inizializzato a false
while (true)
{
flag[i] = true; //vuole entrare nella SC
turn = j; //ma se l'altro processo vuole entrare, che faccia pure
//se l'altro processo vuole entrare ed รจ il suo turno, aspetto
while (flag[j] == true && turn == j);
#sezione critica
flag[i] = false;
#sezione non critica
}
Dimostrazione
- Mutua esclusione:
entra nella SC flag[j] == false || turn == i- Se
e sono entrambi nella SC, allora flag[j] = flag[i] = true - Ma
e non possono aver superato entrambi il whileperchรฉturn = joppureturn = i - Quindi solo uno dei due processi puรฒ essere nella SC
- Progresso e attesa limitata:
- Se
non รจ pronto per entrare nella SC allora flag[j] = falseepuรฒ entrare - Se
ha impostato flag[j] = truee si trova nelwhilealloraturn = ioppureturn = j - Se
turn = iallorapuรฒ entrare nella SC - Se
turn = jallorapuรฒ entrare nella SC - In ogni caso
esce dalla SC imposta flag[j] = falsee quindipuรฒ entrare nella SC - Quindi
puรฒ entrare nella SC al massimo dopo un'entrata di
- Se
Abbiamo vinto!
Algoritmo del fornaio
Questo algoritmo risolve il problema con
Algoritmo del fornaio 0.1
In questa prima versione dell'algoritmo non viene rispettata la mutua esclusione, visto che l'assegnamento del numero non รจ atomica. Infatti puรฒ accadere che i processi eseguano la funzione max() ma si interrompono prima di fare l'assegnamento a number[i]. Di conseguenza piรน processi avranno lo stesso numero. Questo problema viene risolto nella versione 0.2.
PROCESS i; //i va da 0 a n-1
int number[N]; //vettore con "numeri presi", รจ inizializzato a 0
while (true)
{
//scelgo il numero dopo all'ultimo numero preso, come al supermercato
number[i] = max(number[0], ..., number[N-1]) + 1;
for (j = 0; j < N; j++)
{
//se number[j] == 0 vuol dire che ha finito (ha buttato il biglietto) dunque controllo il prossimo processo
//se ho un numero minore al processo che sto controllando passo a vedere il prossimo processo
// altrimenti aspetto
while (number[j] != 0 && number[j] < number[i]);
}
#sezione critica
number[i] = 0;
#sezione non critica
}
Algoritmo del fornaio 0.2
Questo algoritmo risolve il problema della versione precedente, utilizzando un ulteriore array (di bool) per far capire agli altri processi che sto scegliendo il numero. Perรฒ 2 o piรน processi potrebbero avere lo stesso numero, visto che max() non รจ atomica. Dunque si viola anche qui il criterio dellaย mutua esclusione. Questo problema viene risolto nella versione 1.0.
PROCESS i;
bool choosing[N];
int number[N];
while (true)
{
choosing[i] = true;
number[i] = max(number[0], ..., number[N-1]) + 1;
choosing[i] = false;
for (j = 0; j < N; j++)
{
while (choosing[j] == true);
while (number[j] != 0 && number[j] < number[i]);
}
#sezione critica
number[i] = 0;
#sezione non critica
}
Algoritmo del fornaio 1.0
Questo algoritmo risolve il problema della versione precedente. Infatti, per situazioni di numero identico (puรฒ accadere), si usa un confronto a due livelli (numero, i). Questa soluzione rispetta le 3 proprietร della sezione critica, anche se poco pratica. Tuttavia, questa soluzione spreca tanto tempo di utilizzo di CPU, visto che i processi ciclano nel while finchรจ la sezione critica non diventa nuovamente accessibile. Questa รจ chiamata busy waiting.
PROCESS i;
bool choosing[N];
int number[N];
while (true)
{
choosing[i] = true;
number[i] = max(number[0], ..., number[N-1]) + 1;
choosing[i] = false;
for (j = 0; j < N; j++)
{
while (choosing[j] == true);
while (number[j] != 0 && number[j] < number[i]
|| (number[j] == number[i] && j < i) );
}
#sezione critica
number[i] = 0;
#sezione non critica
}
Soluzioni Hardware
Visto che il problema รจ l'accesso alla sezione critica, si potrebbe risolvere il problema disattivando gli interrupt quando entro nella SC, ma questo vorrebbe dire che il processo prende il controllo di tutto e se il test per lโaccesso รจ โlungoโ, gli interrupt devono essere disabilitati per troppo tempo.
Dunque la soluzione HW definitiva รจ realizzata definendo particolari istruzioni che sono atomiche, ovvero sono eseguite in un unico ciclo di istruzioni e non possono essere interrotte. Le uniche due istruzioni atomiche sono la test-and-set e la swap, che utilizzate correttamente garantiscono una soluzione al problema della sezione critica.
Quali sono dunque i vantaggi e gli svantaggi di una soluzione hardware?
- Vantaggi
- Scalabilitร : Una soluzione hardware รจ indipendente dal numero di processi coinvolti
- Posso estendere questa soluzione a
sezioni critiche
- Svantaggi
- Abbiamo una maggiore complessitร rispetto alle soluzioni software visto che l'utilizzo di tali funzioni non รจ banale per un programmatore
- Le soluzioni che implementano direttamente le funzioni sopra citate sono tutte basate su attesa attiva (busy waiting), cioรจ la tecnica per cui un processo aspetta in un ciclo infinito il verificarsi di una condizione per poi passare alle istruzioni successive (considerato dannoso), con conseguente spreco di CPU.
Per risolvere questi problemi sono stati introdotti i semafori, ovvero variabili intere (o binarie nel caso dei mutex o semafori binari) che i processi condividono e che sono modificabili solo attraverso le sopracitate operazioni atomiche.
Test-and-set
La test-and-set prende un valore come argomento e lo imposta a true, restituendo poi il vecchio valore
bool TestAndSet(bool &var)
{
bool temp;
temp = var;
var = true;
return temp;
}
Vediamo ora un esempio di utilizzo di questa funzione.
Utilizzo
// lock รจ una variabile globale inizializzata a false
bool lock;
while (true)
{
// passa solo il primo processo che arriva e trova lock = false
//gli altri settano il lock a true ma tanto lo รจ giร , dunque TestAndSet() ritorna true
while (TestAndSet(lock) == true);
#sezione critica
lock = false;
#sezione non critica
}
La funzione fa il suo dovere, tuttavia potrebbe accadere che il primo processo esce dalla SC e ci ritorna subito dopo, ripetendo la situazione all'infinito. Viene dunque violato il criterio di attesa limitata. Come soluzione a questo problema รจ stata introdotta la test-and-set con attesa limitata. Di seguito ne รจ riportato un esempio.
Test-and-set con attesa limitata
boolean waiting[N]; //inizializzato a false
boolean lock; //inizializzato a false
while (1) {
waiting[i] = TRUE;
key = TRUE;
while (waiting[i] && key) {
//soltanto un processo riuscirร ad entrare, mutua esclusione garantita
key = TestAndSet(lock);
}
waiting[i] = FALSE;
#sezione critica
j = (i+1) % N;
while (j != i && !waiting[j]) {
//se processo diverso da me e non sta aspettando, chiedo a quello successivo
j = (j+1) % N;
}
if (j == i)
lock = FALSE;
else
waiting[j] = FALSE;
#sezione non critica
}
Swap
La swap effettua semplicemente uno scambio di valori tra due variabili.
void Swap(bool &a, bool &b)
{
bool temp;
temp = a;
a = b;
b = temp;
}
Vediamo ora un esempio di utilizzo di questa funzione.
Utilizzo
Il processo che arriva e scambia dummy da true a false puรฒ entrare.
// lock รจ una variabile globale inizializzata a false
bool lock;
while (true)
{
dummy = true; // variabile locale al processo
do
{
// Gli altri processi continuano a scambiare true con true e non
// accedono alla SC finchรฉ P_i non pone lock = false
Swap(lock, dummy);
} while (dummy == true); // quando dummy = false Pi accede alla SC
#sezione critica
lock = false;
#sezione non critica
}
Anche qui abbiamo lo stesso problema del test-and-set, visto che viene violato il criterio di attesa limitata (manca lโequivalente della variabileย turn). Inoltre non viene risolto il problema di busy waiting, visto che i processi potrebbero dover aspettare molto tempo prima di accedere alla sezione critica. Bisogna quindi utilizzare il #Test-and-set con attesa limitata.
Semafori
Per risolvere i problemi hardware precedentemente citati sono stati introdotti i semafori, ovvero variabili intere (o binarie nel caso dei mutex o semafori binari) che i processi condividono e che sono modificabili solo attraverso le sopracitate operazioni atomiche. Si fa normalmente uso di due funzioni (denominiamo
- Signal: V(s)
- incrementa il valore di
di
- incrementa il valore di
- Wait: P(s)
- tenta di decrementare il valore di
di - se
si blocca ed aspetta che diventi maggiore di , per poi decrementarlo.
- tenta di decrementare il valore di
Come detto prima, esistono i semafori binari e i semafori interi (o generici). Vediamoli ora piรน nel dettaglio.
Semafori binari
Vediamo ora l'implementazione โconcettualeโ di un semaforo binario. Nella realtร non รจ proprio implementato cosรฌ.
P(s):
while (s == false); // attesa
s = false;
V(s):
s = true;
Semplicemente se
Nota: I semafori binari hanno lo stesso potere espressivo di quelli a valori interi.
Ovviamente qui manca l'atomicitร delle operazioni. Dobbiamo quindi utilizzare la swap o ancora meglio la test-and-set (ricordiamo che la Swap ha il problema della busy waiting).
Implementazione con busy waiting
Implementazione della Wait:
/* s inizializzato a TRUE */
P(bool &s) {
key = false;
do {
Swap(s, key);
} while(key == false);
}
Implementazione della Signal:
/* s inizializzato a TRUE */
V(bool &s) {
s = true;
}
Qui solo un processo riuscirร ad entrare nella sezione critica, visto che sarร il primo a fare la Swap tra s che sarร true e key che sarร false. I successivi processi troveranno s impostata a false e continueranno a scambiare false con false finchรจ s non verrร impostato nuovamente a true.
Semafori interi
Vediamo ora l'implementazione โconcettualeโ di un semaforo intero. Nella realtร non รจ proprio implementato cosรฌ.
P(s):
while (s == 0); // attesa
s--;
V(s):
s++;
Semplicemente se
Ovviamente qui manca l'atomicitร delle operazioni. Dobbiamo quindi utilizzare la swap o ancora meglio la test-and-set (ricordiamo che la Swap ha il problema della busy waiting).
Implementazione con busy waiting
Di seguito รจ riportata una possibile implementazione che soffre di busy waiting. Questo perchรจ
Implementazione della Wait:
bool mutex; /* Sem. binario iniz. TRUE */
bool delay; /* Sem. binario iniz. FALSE */
P(int &s) {
P(mutex); //per proteggere s da un'altra modifica, garantisco la mutua esclusione
s = s - 1;
if (s<0) {
//orco!! Ho decrementato s quando non potevo O_O
V(mutex); //aspetta che libero la risorsa
P(delay); //e mi rimetto in attesa attiva, non garantisco l'attesa limitata
}
else
V(mutex); //garantisco il progresso
}
Implementazione della Signal:
bool mutex; /* Sem. binario iniz. TRUE */
bool delay; /* Sem. binario iniz. FALSE */
V(int &s) {
P(mutex);
s = s + 1;
if (s<=0) {
//vado a vedere se incrementando il valore del semaforo e s<=0
//se questo รจ vero vuol dire che qualcuno รจ in attesa, perchรจ รจ scemo e ha fatto s-- quando era a 0
//dunque faccio V(delay) per liberarlo
V(delay);
}
V(mutex);
}
Cerchiamo ora di capire cosa succede nel codice sopra. Quando un processo vuole cambiare il valore di s deve eseguire prima una
Implementazione senza busy waiting
Qual รจ il problema nell'implementazione precedente?
Mettiamo caso che
Dobbiamo allora implementare una coda cosรฌ quel processo dovrร aspettare e permettere anche gli altri di utilizzare la risorsa.
In questo esempio definiamo una struct Sem, che รจ fatta nel seguente modo:
typedef struct {
int value; //il valore del semaforo
PCB* list; //una lista che contiene gli identificativi dei processi
} Sem;
Implementazione della Wait, simile a quella precedente:
bool mutex; /* Sem. binario iniz. TRUE */
P(Sem &s){
P(mutex); //garantisco la mutua esclusione
s.value = s.value - 1;
if (s.value < 0) {
//orco!! Ho decrementato s quando non potevo O_O
V(mutex); //aspetta che libero la risorsa
append (process i, s.List); //non faccio V(delay) ma mi aggiungo alla lista di attesa, garantendo l'attesa limitata
sleep(); //mette il processo nello stato di waiting, rilasciando volontariamente la CPU
}
else
V(mutex); //garantisco il progresso
}
Implementazione della Signal, simile a quella precedente:
bool mutex; /* Sem. binario iniz. TRUE */
V(Sem &s){
P(mutex);
s.value = s.value + 1;
if (s.value <= 0) {
V(mutex);
//rimuovo il processo che sta aspettando da piรน tempo dalla coda e me lo salvo in p
PCB *p = remove(s.List);
wakeup(p); //metto il processo p nello stato ready, se richiede subito la risorsa deve fare la fila
}
else
V(mutex);
}
Dunque invece di aspettare in attesa attiva con la
Questa soluzione, oltre alla mutua esclusione, implementa quindi la bounded waiting. Utilizzando una FIFO infatti posso tirare fuori il primo processo che รจ entrato cosรฌ non deve aspettare all'infinito. Ovviamente se utilizzassimo una LIFO avremmo potenzialmente un attesa infinita, visto che il povero processo che รจ entrato subito, se trovasse
I semafori hanno delle applicazioni generiche, che non valgono solo per l'accesso alla sezione critica. Quindi se il semaforo deve aspettare una condizione che รจ breve, per esempio la sezione critica per l'accesso in memoria, potrebbe valere la pena tenersi il busy waiting (detto anche spinlock). Questo perchรจ, nonostante la CPU controlli attivamente il verificarsi della condizione di accesso alla sezione critica, รจ un controllo veloce e non complesso, non bisogna implementare niente. Se invece dobbiamo sincronizzare operazione piรน lunghe come ad esempio operazioni di I/O, allora ne vale la pena implementarlo con la coda di attesa, ricordando che si deve tenere conto del tempo di gestione, la gestione della coda ecc.
Applicazioni
Possiamo quindi distinguere gli usi principali dei semafori in base al loro valore iniziale. Vediamo ora alcuni esempi per capire meglio.
Semaforo binario con valore iniziale (mutex)
Quando utilizziamo un semaforo binario con valore iniziale
Esempio
// Valore iniziale di s = 1 (mutex)
while(true)
{
P(s);
# sezione critica
V(s);
# sezione non critica
}
Semaforo binario con valore iniziale
Quando utilizziamo un semaforo binario con valore iniziale
Esempio 1
In questo esempio abbiamo due processi
Di sicuro dobbiamo inizializzare
// Valore iniziale di s = 0
P1 {
...
A
V(s);
...
}
P2 {
...
P(s);
B
V(s);
...
}
Sembra funzionare no? ๐. In realtร si ma c'รจ un problema.
// Valore iniziale di s = 0
P1 {
...
A
V(s);
...
}
P2 {
...
P(s);
B
...
}
Soluzione corretta! ๐ค
Esempio 2
In questo esempio abbiamo due processi
Dunque la soluzione precedente non va piรน bene, visto che
// Valore iniziale di s1 = 1
// Valore iniziale di s2 = 0
P1 {
...
P(s1);
A
V(s2);
...
}
P2 {
...
P(s2);
A
V(s1)
...
}
Esempio 3
In questo esempio abbiamo due processi
bool s1 = 1;
bool s2 = 0;
int c1 = 0;
int c2 = 0;
P1 {
while(1) {
P(s1);
A
c1++;
if(c1 % 4 == 0)
V(s2);
else
V(s1);
}
...
}
P2 {
while(1) {
P(s2);
B
c2++;
if(c2 % 2 == 0)
V(s1)
else
V(s2)
}
}
Abbiamo i due semafori binari
Limitazioni
Vediamo ora alcuni problemi e limitazioni dei semafori.
Il problema principale รจ il deadlock (blocco critico), che avviene quando un processo รจ bloccato in attesa di un evento che solo lui puรฒ generare. Eccone un esempio:
// Valore iniziale di s = 1
// Valore iniziale di q = 1
P1 {
P(s);
P(q);
//operazioni
V(s);
V(q);
}
P2 {
P(q);
P(s);
//operazioni
V(q);
V(s);
}
In questo esempio se parte
Un'altra situazione di deadlock avviene quando un processo fa la
Un altro problema รจ lo starvation, ovvero l'attesa indefinita all'interno di un semaforo. Questo avviene quando non si garantisce l'attesa limitata e di conseguenza alcuni processi non riescono mai eseguire le loro operazioni.
Infine, lโutilizzo dei semafori presenta alcune complicazioni come la difficoltร nella scrittura dei programmi e la scarsa "visibilitร " della correttezza delle soluzioni.
In alternativa, vengono utilizzati specifici costrutti forniti da linguaggi di programmazione ad alto livello, come:
- Monitor (Hoare, 1974), che vedremo in seguito
- Classi synchronized di Java
- CCR (Conditional Critical Region)
Esempio di utilizzo dei semafori - problemi classici
Problema del produttore โ consumatore
Il problema descrive due processi, uno produttore ed uno consumatore che condividono un buffer di dimensione fissata. Il produttore genera dati e li deposita nel buffer di continuo. Contemporaneamente, il consumatore consuma i dati prodotti, prelevandoli di volta in volta dal buffer. Il problema รจ assicurare che il produttore non elabori nuovi dati se il buffer รจ pieno, e che il consumatore non cerchi dati se il buffer รจ vuoto. Quanti semafori dobbiamo usare?
Dobbiamo usare esattamente 3 semafori:
- mutex, binario inizializzato a TRUE (mutua esclusione per buffer)
- empty, intero inizializzato a
(dice al produttore quanti item ancora puรฒ produrre, e lo blocca se empty รจ zero) - full, intero inizializzato a
(dice al consumatore quanti item ancora puรฒ consumare, e lo blocca se full รจ zero)
bool mutex = true;
int empty = n;
int full = 0;
PRODUCER {
while (1) {
produce item
P(empty);
P(mutex);
deposit item
V(mutex);
V(full);
}
}
CONSUMER {
while (1) {
P(full);
P(mutex);
remove item
V(mutex);
V(empty);
consume item;
}
}
Problema dei dining philosophers
Il problema descrive
- Abbiamo un tavolo con
bacchette e una ciotola di riso - Se un filosofo pensa non interagisce con gli altri
- Se un filosofo ha fame prende 2 bacchette e inizia a mangiare, ma puรฒ prendere solo le bacchette che sono alla sua destra e alla sua sinistra
- Il filosofo puรฒ prendere una bacchetta alla volta
- Se non ci sono 2 bacchette libere il filosofo non puรฒ mangiare
- Quando un filosofo termina di mangiare rilascia le bacchette
Vediamo ora una soluzione intuitiva a questo problema.
Dati condivisi da ogni filosofo:
- semafori
inizializzati a (ogni elemento rappresenta una bacchetta) cerco di prendere la bacchetta rilascio la bacchetta
int semafori[N]; //ogni elemento inizializzato a 1
FILOSOFO[i] {
while(1) {
P(s[i]);
P(s[(i+1) % N]);
โฆ
// mangia
โฆ
V(s[i]);
V(s[(i+1) % N]);
โฆ
// pensa
โฆ
}
}
In questa soluzione perรฒ รจ possibile che si verifichi un deadlock, visto che se ogni filosofo prendesse la bacchetta di destra (cioรจ ogni filosofo fa
Elenchiamo ora un paio di semplici soluzioni che risolvono il deadlock, ma che non risolvono esattamente il problema originale.
- Permettere solo a
filosofi di mangiare contemporaneamente - Soluzione asimmetrica:
- I filosofi in posizioni pari prendono la bacchetta sinistra seguita dalla destra
- I filosofi in posizioni dispari fanno viceversa
- Si passano un token
- Permettere ai filosofi di prendere la forchetta solo se entrambi disponibili
Soluzione corretta
Vediamo ora la soluzione corretta al problema originale.
Ogni filosofo puรฒ trovarsi in
- Pensante (THINKING)
- Affamato (HUNGRY)
- Mangiante (EATING)
Dati condivisi da ogni filosofo:
bool semaphore mutex = 1;
int semaphore f[N]; //binario, inizializzato a 0
int stato[N] = THINKING;
Void Philosopher (int i) {
while (1) {
Think(); //fa uno sleep(random())
Take_fork(i);
Eat(); //fa uno sleep(random())
Drop_fork(i);
}
}
Void Take_fork (int i) {
P(mutex);
stato[i] = HUNGRY;
test(i);
V(mutex);
P(f[i]);
}
Void test (int i) {
if (stato[i] == HUNGRY &&
stato[i-1] != EATING &&
stato[i+1] != EATING)
{
stato[i] = EATING;
V(f[i]);
}
}
Void Drop_fork (int i)
{
P(mutex);
stato[i] = THINKING;
test((i-1)%N);
test((i+1)%N);
V(mutex);
};
Questa soluzione perรฒ ha un problema. Infatti con un numero pari di filosofi abbiamo il problema di starvation, ossia puรฒ presentarsi il caso in cui a coppie i filosofi non mangiano, provocando un attesa indefinita. Se invece abbiamo un numero dispari di filosofi questo non succede. Un modo per risolvere questo problema รจ utilizzare le prioritร .
Problema dello sleepy barber
Il problema descrive un negozio che ha una sala dโattesa con
- In assenza di clienti, il barbiere si addormenta
- Quando entra un cliente
- Se le sedie sono occupate, il cliente se ne va
- Se il barbiere eโ occupato il cliente si siede
- Se il barbiere eโ addormentato, il cliente lo sveglia
Dati condivisi dal barbiere e dai clienti:
int semaphore customers = 0; // sveglia il barbiere
bool semaphore barbers = 0; // stato del barbiere
bool semaphore mutex = 1; // protegge la sezione critica
int waiting = 0; // conta i clienti in attesa
int N; // il numero di clienti
BARBER{
while(1) {
P(customers); // aspetta che entri un cliente
P(mutex); //aspetta che il cliente modifichi waiting
waiting--; //faccio entrare il cliente nella stanza
V(barbers); //sono pronto per tagliargli i capelli
V(mutex);
cut hair;
}
}
COSTUMER{
while(1) {
P(mutex); //per modificare waiting
if (waiting < N) {
waiting++;
V(customers); //sveglia!!
V(mutex);
P(barbers); //pronto per il taglio
get haircut;
}
else
V(mutex); //non c'รจ posto
}
}
Monitor
Nonostante i semafori siano uno strumento molto potente, in grado di risolvere qualsiasi problema di sincronizzazione, non sempre per il programmatore รจ semplice capire come utilizzarli per risolvere il problema e risulta comunque difficile dimostrare la correttezza della soluzione implementata. Possono infatti esserci degli errori che si verificano solo in particolari condizioni di esecuzione e per questo difficili da individuare. Per questi motivi i linguaggi di programmazione di alto livello spesso forniscono altri strumenti come i monitor, le classi syncronized di Java e le CCR (Conditional Critical Region). In questa sezione vedremo i monitor nel dettaglio.
I monitor sono un tipo di dato astratto, una sorta di "classe" che incapsula variabili e procedure che saranno protette in automatico con la mutua esclusione. In questo modo il programmatore non si deve preoccupare di utilizzare lock o semafori mutex per potervi accedere. Le variabili dichiarate in un monitor formano lo stato del monitor e sono visibili solo allโinterno del monitor stesso. Le funzioni definite nel monitor possono accedere solamente alle variabili dello stato, oltre che a quelle dichiarate localmente alla funzione ovviamente. Inoltre il monitor garantisce che un solo processo alla volta possa essere attivo allโinterno del monitor, dunque il programmatore non deve codificare esplicitamente la mutua esclusione.
Per permettere ad un processo di attendere allโinterno del monitor e quindi di sincronizzarsi con gli altri processi, il monitor รจ provvisto di un ulteriore meccanismo di sincronizzazione dato dal costrutto condition. Sono essenzialmente delle variabili (dette appunto condizioni) interne al monitor sulle quali si possono invocare la
Per esempio, mettiamo caso che sia dichiarata la variabile condition x. Similmente ai semafori, il processo che invoca la
Riassumendo:
- Blocca sempre il processo che la chiama, tuttavia si puรฒ decidere con altro codice se chiamarla o no (i.e., if..then..else)
- Sveglia esattamente un processo
- Se piรน processi in attesa, lo scheduler decide quale processo puรฒ entrare
- Se nessun processo in attesa, nessun effetto
C'รจ da fare perรฒ una precisazione sulla
- Signal and wait: Il processo che ha chiamato signal attende e lโesecuzione passa al processo che si รจ sbloccato.
- Signal and continue: Il processo che ha chiamato signal continua la sua esecuzione ed esce dal monitor (in questo caso signal deve essere lโultima istruzione della procedura).
Problema del produttore/consumatore con i monitor
Producer() {
while (TRUE) {
make_item(); // crea nuovo item
ProducerConsumer.enter(); // chiamata alla funzione enter
}
}
Consumer() {
while (TRUE) {
ProducerConsumer.remove(); // chiamata alla funzione remove
consume_item() ; // consuma item
}
}
monitor ProducerConsumer {
condition full, empty;
int count = 0;
entry enter() {
if (count == N)
full.wait(); //se buffer รจ pieno, blocca
put_item(); // mette item nel buffer
count = count + 1; // incrementa count
if (count == 1) //solo una signal verrร intercettata
empty.signal(); // se il buffer era vuoto, sveglia il consumatore
}
entry remove(){
if (count == 0)
empty.wait(); // se buffer รจ vuoto, blocca
remove_item(); // rimuove item dal buffer
count = count - 1; // decrementa count
if (count == N-1) //solo una signal verrร intercettata
full.signal(); // se il buffer era pieno, sveglia il produttore
}
}
Limitazioni
Per concludere la trattazione sui monitor bisogna evidenziare che, sebbene essi siano piรน semplici da utilizzare per il programmatore, pochi linguaggi li implementano e per funzionare necessitano di memoria condivisa.
Classi syncronized in Java
Java come linguaggio ad alto livello fornisce un suo meccanismo per la sincronizzazione dei processi ovvero la keyword syncronized. Un metodo syncronized รจ un metodo che puรฒ essere eseguito da una sola thread alla volta. Ciรฒ viene realizzato mantendendo un singolo lock (detto monitor, ma da non confondere con i monitor trattati in precedenza) per oggetto. Se il metodo syncronized รจ statico allora il lock viene messo sulla classe. Eโ possibile inoltre definire una sezione critica su qualsiasi blocco utilizzando sempre la keyword syncronized. Sono disponibili inoltre altri metodi di sincronizzazione disponibili nella classe Object e quindi ereditati da tutti gli oggetti, ovvero wait(), notify(), notifyAll().
Problema del produttore/consumatore con le classi syncronized
public class BoundedBuffer {
Object[] buffer;
int nextin;
int nextout;
int size;
int count;
//costruttore
public BoundedBuffer(int n) {
size = n;
buffer = new Object[size];
nextin = 0;
nextout = 0;
count = 0;
}
public synchronized deposit(Object x) {
while (count == size) wait();
buffer [nextin] = x;
nextin = (nextin+1) mod N;
count = count + 1;
notifyAll();
}
public synchronized Object remove() {
Object x;
while (count = 0) wait();
x = buffer[nextout];
nextout = (nextout+1) mod N;
count = count - 1;
notifyAll();
return x;
}
}
Il primo processo che vuole accedere troverร mutex a true ed entrerร (settando cosรฌ mutex a false), mentre gli altri processi si bloccheranno ad aspettare che ridiventi true. โฉ๏ธ