Domenico Cotroneo » 11.Sincronizzazione nel modello ad ambiente globale

Sincronizzazione nel modello ad ambiente globale

Sommario

• Problema della mutua esclusione (competizione)
• Soluzioni hardware al problema della mutua esclusione
• Problema della comunicazione (cooperazione)
• Semafori

Competizione Processi

Più processi “competono” nell’uso di una risorsa.

Un gestore di una risorsa ha il compito di fornire un accesso sicuro e garantito alla risorsa che gestisce.

Tre problemi chiave nel controllo di accesso ad una risorsa:

• Mutua Esclusione;
• Deadlock;
• Starvation.

Problema della Mutua esclusione

Problema di competizione.

Due o più processi che vogliono utilizzare una risorsa ad uso esclusivo (come ad esempio una stampante), che chiameremo Risorsa Critica.

La porzione del codice che utilizza la risorsa è denominata Sezione Critica (la sezione critica può anche essere composta da più sezioni di codice appartenenti a più processi).

Deadlock

Indica la presenza di una condizione di attesa indefinita.

Esempio

• P1 possiede la risorsa R1 e per completare la sua esecuzione richiede la risorsa R2;
• P2 possiede la risorsa R2 e per completare la sua esecuzione richiede la risorsa R1.

Si dice che i due processi P1 e P2 sono in una situazione di stallo (deadlocked).

Starvation

Indica quelle condizioni in cui ad un processo a bassa priorità non viene mai assegnata una risorsa.

• P1 P2 P3 a priorità decrescente;
• P1 acquisisce R;
• P1 libera R, che viene assegnata a P2;
• P1 richiede nuovamente R;
• P2 libera R a favore di P1;
• ……
• il processo P3 attende indefinitamente (condizione di starvation).

Requisiti per la mutua esclusione

1. Un solo processo alla volta può accedere alla sezione critica.
2. Un processo che si arresta nella sua sezione non critica (critica) non deve interferire con altri processi.
3. Evitare deadlock e starvation (senza attesa indefinita).
4. L’accesso ad una sezione critica di un processo non deve essere ritardata se non ci sono altri processi nella sezione stessa.
5. Nessuna assunzione deve essere fatta sulla velocità di esecuzione dei processi o sul numero dei processi (no “Race Condition”).
6. Un processo può rimanere in una sezione critica solo per un tempo finito.

Supporto Hardwarealla mutua esclusione

• Disabilitazione degli Interrupt
• Istruzione Test and Set Lock

Disabilitazione degli Interrupt

In un sistema monoprocessore, al fine di garantire la mutua esclusione è sufficiente evitare che un processo, in una sezione critica, venga interrotto.

In un sistema multiprocessore, invece, la disabilitazione delle interruzioni in uno dei processori non garantisce la mutua esclusione.

L’approccio viola i principi di protezione: i processi utente dovrebbero poter disabilitare gli interrupt!!

Tuttavia è conveniente per il kernel quando deve aggiornare delle variabili condivise interne.

Variabili Lock

Soluzione basata su una variabile condivisa (lock) inizializzata a 0.
Quando un processo vuole entrare nella sezione critica, verifica il valore del lock:

• se lock=0, posiziona lock a 1 ed entra nella sezione critica;
• se lock=1, aspetta che diventi 0.

Problema: più processi potrebbero accedere contemporaneamente alla sezione critica!

Un processo legge il lock, e riscontra il valore 0. Prima che possa posizionarlo ad 1, un altro processo è schedulato, legge il lock (ancora uguale a 0), lo posiziona ad 1 ed entra nella sezione critica. Quando il primo processo torna in esecuzione, posiziona anch’esso il lock a 1, ed entra nella sezione critica insieme al secondo processo!

Ciò è dovuto al fatto che la lettura e scrittura del lock possono essere eseguite in tempi diversi: sono divisibili.

L’istruzione Test and Set Lock

Per risolvere via hardware il problema delle variabili lock, molti processori forniscono l’istruzione macchina:

TSL RX,LOCK

• Legge il contenuto della parola di memoria LOCK e lo scrive nel registro RX.
• Scrive un valore non negativo nella parola LOCK.

E’ eseguita in un solo ciclo: le operazioni di lettura e scrittura di LOCK sono quindi indivisibili.

La TSL inibisce l’accesso al bus di memoria durante la sua esecuzione: la soluzione è quindi utilizzabile anche nei sistemi multiprocessore.

Problema della mutua esclusione con istruzione TSL

La soluzione è caratterizzata da condizioni di attesa attiva (busy wait)

Problema della mutua esclusione con istruzione TSL

La soluzione al problema della mutua esclusione è ora banale:

• prima di entrare nella sezione critica, un processo chiama la procedura (ovvero, system call) “enter_region”, dove aspetta in un ciclo che la variabile LOCK diventi 0;
• la procedura “enter_region” ritorna il controllo al chiamante non appena il lock è acquisito. Il processo quindi entra nella sezione critica;
• all’uscita dalla sezione critica, il processo invoca “leave_region”, che memorizza uno 0 nella variabile LOCK, sbloccando quindi altri processi eventualmente in attesa.

La soluzione è caratterizzata da condizioni di attesa attiva (busy wait), con relativo spreco di CPU.

Priority inversion

Oltre al problema dell’attesa attiva, la soluzione con TSL presenta il problema della “priority inversion”.
Due processi accedono alla stessa sezione critica:

• Processo H con priorità alta;
• Processo L con priorità bassa.

Lo scheduling è tale da assegnare la CPU ad H non appena è nello stato “pronto”.

Ad un certo istante, mentre L è nella sezione critica, H entra nello stato “pronto” (ad esempio, una op. di I/O completa).

H inizia il busy wait tramite TSL, ma siccome L non è mai schedulato mentre H è in esecuzione, L non lascerà mai la sezione critica: H rimane bloccato nel suo ciclo di attesa attiva per sempre.

La soluzione…

I problemi di attesa attiva e di priority inversion vengono risolti “forzando” il processo che trova la variabile LOCK al valore 1 a sospendersi (transita nello stato bloccato) in attesa di un evento.

Utilizzo di due system call:

• suspend(P1), sospende il processo P1 in attesa di un segnale di risveglio;
• Wake-up(P2), segnale di risveglio inviato ad un processo P2 che è stato sospeso mediante la suspend.

Semafori

Variabili Speciali utilizzate per la cooperazione e la competizione tra processi.

Due o più processi possono competere o cooperare attraverso l’uso dei segnali, in modo tale che un processo può essere forzato a sospendersi in un determinato punto finché non riceve un segnale.

• Usando una variabile semaforo, un processo può inviare un segnale sul semaforo s tramite una procedura signal(s).
• Per ricevere un segnale sul semaforo s si esegue la primitiva wait(s): se il segnale non è stato ancora ricevuto, il processo si sospende.

Sulle procedure di wait e signal sono disabilitate le interruzioni.

Semafori

Un tipo di dato astratto s che incapsula:

• una variabile di tipo intero (s.value);
• una coda (s.queue), per tenere traccia dei processi che si sono sospesi nell’attesa di una signal.

Sono definite le seguenti operazioni:

• inizializzazione della variabile ad un valore non negativo;
• operazione di wait, che ha l’effetto di decrementare il valore del semaforo. Se il valore del semaforo diventa negativo, il processo viene bloccato;
• l’operazione di signal che ha l’effetto di incrementare il valore del semaforo. Se il valore del semaforo diventa minore o uguale a zero viene “sbloccato” un processo che si era sospeso durante l’esecuzione della Wait.

Semafori: modello concettuale

Semafori Binari

Il suo valore intero può essere soltanto 0 o 1; può essere più semplice da realizzare

Il problema della mutua esclusione con l’utilizzo dei semafori

Si utilizza un semaforo s (chiamato mutex), inizializzato a 1.

const int n = /* numero di processi */
semaphore mutex;
...
void P(int i) { /* il codice del processo i-mo*/


...
wait(mutex);
/* sezione critica */
signal(mutex);


...
}
...
int main() {


mutex.value = 1;
/* esecuzione concorrente di P(1), ..., P(n) */


}


Esempio

Si hanno 4 processi concorrenti, denominati A, B, C e D.

Si supponga che l’esecuzione di A, B e C dipenda dall’esecuzione del processo D.

Esempio

1) Inizialmente A è in esecuzione, B, C e D sono ready, il valore del semaforo è 1. A esegue una wait

Esempio

2) A esegue una wait, il valore di S viene decrementato. A non viene sospeso

Esempio

3) B esegue una wait, il valore del semaforo è decrementato e B viene sospeso

Esempio

4) D esegue una signal, che permette a B di essere inserito nella coda dei proc pronti. Si noti che in questo caso D non viene sospeso

Esempio

5) D raggiunge la coda dei proc. pronti. C raggiunge il processore ed esegue una wait. C verrà sospeso. Anche A e B eseguono una wait, e per lo stesso motivo verranno sopesi

Esempio

6) D esegue un signal, che sbloccherà il processo C

Problema della comunicazione

Problema di cooperazione.

Un processo “produttore” genera ciclicamente un messaggio e lo deposita in un buffer.

Un processo “consumatore” preleva dal buffer il messaggio e lo utilizza.

Vincoli:

• il produttore non può inserire un nuovo messaggio prima che il consumatore abbia prelevato il precedente;
• il consumatore non può prelevare dal buffer un nuovo messaggio prima che il produttore l’abbia depositato.

Differenze con il problema della mutua esclusione

Pur esistendo un problema di mutua esclusione nell’utilizzo del buffer comune.

La soluzione impone un ordinamento nelle operazioni dei due processi.

E’ necessario che produttori e consumatori si scambino segnali per indicare rispettivamente l’avvenuto deposito e prelievo.

Ciascuno dei due processi deve attendere, per completare la sua azione, l’arrivo del segnale dell’altro processo.

Soluzione al Problema della comunicazione con i semafori

Due semafori

spazio_disponibile (v.i. 1)
messaggio_disponibile (v.i.0)
Processo Produttore

produttore{
do {


<produzione del nuovo messaggio>;
wait (spazio_ disponibile);
<deposito del messaggio nel buffer>;
signal (messaggio_ disponibile)


} while (!fine);


}


Soluzione al Problema della comunicazione con i semafori

Processo Consumatore

consumatore{
do {


wait (messaggio_ disponibile);
<prelievo del messagio dal buffer>;
signal (spazio_ disponibile);
<consumo messaggio>;
} while (!fine);


}