Appunti di Sistemi Operativi

P D,

genera la stessa traccia. La verifica può essere agevolmente svolta tramite il debugging.

Nei programmi concorrenti, invece, l’esito dell’esecuzione dipende da quale sia l’effettiva sequenza

cronologica di esecuzione delle istruzioni contenute, poiché non si hanno vincoli su cosa esegue prima e

15

cosa dopo. Ogni esecuzione di un programma su un particolare insieme di dati quindi, dà origine ad

P D,

una traccia dell’esecuzione diversa. La verifica è molto complessa in un programma concorrente, poiché il

semplice debug su un’esecuzione non fornisce garanzia del soddisfacimento di una proprietà data.

Volendo fornire una definizione precisa, una proprietà di un programma è un attributo che è sempre

P

vero in ogni possibile traccia generata dall’esecuzione di . In generale vengono classificate in due categorie:

P

• Safety properties: garantiscono che, durante l’esecuzione di , non si entrerà mai in uno stato

P

errato, ossia uno stato in cui le variabili assumono valori non desiderati.

• Liveness properties: garantiscono che, durante l’esecuzione di , prima o poi si entrerà in uno stato

P

corretto, ossia uno stato in cui le variabili assumono valori desiderati.

Un programma sequenziale deve avere fondamentalmente due proprietà:

• Correttezza del risultato finale: per ogni esecuzione il risultato ottenuto è giusto (safety property).

• Terminazione: prima o poi l’esecuzione termina (liveness property).

Un programma concorrente, invece, deve avere fondamentalmente le stesse proprietà di un programma

sequenziale con l’aggiunta di:

• Mutua esclusione nell’accesso a risorse condivise: per ogni esecuzione non accadrà mai che più

di un processo acceda contemporaneamente alla stessa risorsa (safety property).

• Assenza di deadlock: per ogni esecuzione non si verificheranno mai situazioni di blocco critico

(safety property). ossia assenza di un blocco critico in attesa infinita di acquisire una risorsa;

• Assenza di starvation:

prima o poi ogni processo potrà accedere alle risorse richieste (liveness property).

16

Capitolo 4

Modello a memoria comune

L’interazione tra processi basata su una memoria condivisa richiede degli strumenti per sincroniz-

zare gli accessi alle risorse in modo che solo un processo per volta possa utilizzarle. Lo strumento

più semplice e di basso livello per imporre questo vincolo è il semaforo.

L’interazione tra processi può essere descritta in due modelli: il modello a memoria comune o il modello

a scambio di messaggi.

Il modello a memoria comune può essere rappresentato graficamente come in Fi- O

2

gura 4.1. Esso rappresenta la naturale astrazione del funzionamento di un sistema P P

1 2

multiprogrammato, costituito da uno o più processori che hanno accesso ad una O

3

memoria comune: anche se ad ogni processore può essere associata una memoria O O

1 4

privata, ogni interazione avviene tramite oggetti contenuti nella memoria comune, P 3

ossia un ambiente globale accessibile a tutti.

Ogni applicazione viene strutturata come un insieme di componenti, suddiviso in Figura 4.1: Modello a

due sottoinsiemi disgiunti: i processi, detti componenti attivi, e le risorse, dette memoria comune.

componenti passivi, le quali a loro volta sono suddivise in risorse di tipo primitivo e di tipo astratto.

Per risorsa si intende qualunque oggetto fisico, o logico, di cui un processo necessita per portare a termine

il suo compito. Le risorse sono raggruppate in classi, e una classe identifica l’insieme di tutte le operazioni

che un processo può eseguire per operare su risorse di quella classe. Il termine risorsa si identifica in quello

di struttura dati allocata nella memoria comune.

In questo modello è indispensabile specificare un meccanismo di controllo degli accessi, il quale ha il

compito di controllare che gli accessi dei processi alle risorse avvengano in modo corretto. A tal proposito,

si definisce, per ogni risorsa il suo gestore, il quale definisce in ogni istante l’insieme dei processi

R, t S (t)

R

che in quell’istante hanno il diritto di operare su R.

Una risorsa può essere classificata in 4 modi, come indicato in Tabella 4.1:

≤

• Risorsa dedicata se ha una cardinalità sempre

R S (t) 1.

R

• Risorsa condivisa se non è dedicata.

R ∀t.

• Risorsa allocata staticamente se è costante In questo caso il gestore è

R S (t) S (t) = S (t ),

0

R R R

il programmatore.

• Risorsa allocata dinamicamente se è funzione del tempo. In questo caso il gestore è un

R S (t)

R

componente della stessa applicazione. Risorse dedicate Risorse condivise

Risorse allocate staticamente A: Risorse private B: Risorse comuni

Risorse allocate dinamicamente C: Risorse comuni D: Risorse comuni

Tabella 4.1: Classificazione delle risorse.

I compiti di un gestore sono: 17

• Mantenere aggiornato l’insieme ossia lo stato di allocazione della risorse di cui è gestore.

S (t),

R

• Fornire i meccanismi che un processo può utilizzare per acquisire il diritto di operare sulla risorsa,

entrando a far parte dell’insieme e per rilasciare tale diritto quando non più necessario.

S (t)

R

• Implementare la strategia di allocazione della risorsa e definire quando, a chi e per quanto tempo

allocare la risorsa.

Nel modello a memoria comune il gestore è una risorsa condivisa. Come un monitor in ambiente Java,

quindi, è un entità passiva, mentre nel modello a scambio di messaggi è un processo, ossia un entità attiva.

Se è allocata staticamente a , il processo possiede il diritto di operare in qualunque istante sulla risorsa

R P

Se invece è allocata dinamicamente a , è necessario prevedere un gestore che implementi le funzioni di

R. P

richiesta e rilascio. Il processo deve quindi eseguire il protocollo di:

P

1. richiesta;

2. esecuzione;

3. rilascio.

Se è una risorsa condivisa è necessario assicurare che gli accessi avvengano in modo non divisibile,

R

quindi l’accesso alla risorsa deve essere programmato come sezione critica utilizzando i meccanismi di

sincronizzazione offerti dal linguaggio di programmazione e supportati dalla macchina corrente. Se è una

R

risorsa dedicata, essendo l’unico processo che può accedervi, non è necessario prevedere nessun meccanismo

P

di sincronizzazione.

L’interazione tra processi per la gestione delle risorse condivise può avvenire in due modi:

• Competizione:

– Con la modalità B la competizione tra processi avviene al momento dell’accesso alla risorsa, e l’ac-

cesso esclusivo è garantito dal meccanismo di mutua esclusione utilizzato nella programmazione

delle funzioni di accesso.

– Con la modalità C la competizione avviene al momento dell’accesso alle operazioni del gestore.

• Cooperazione:

– Con la modalità B si ha cooperazione se uno dei processi memorizza in informazioni che possono

R

essere lette da un altro processo.

– Con la modalità C si ha cooperazione se un processo acquisisce dal gestore il diritto di operare

su vi memorizza informazioni e se successivamente il diritto di accesso viene acquisito da un

R,

altro processo che legge quelle informazioni.

4.1 Regione critica condizionale

La regione critica condizionale è un formalismo che consente di esprimere la specifica di qualunque vincolo

di sincronizzazione. Data una risorsa condivisa:

R

1 region R << Sa; when(C) Sb; >>

il corpo della regione rappresenta un’operazione da eseguire sulla risorsa condivisa essa costituisce per-

R;

tanto una sezione critica che deve essere eseguita in mutua esclusione con le altre operazioni definite su R.

Nell’esempio presentato è costituita da due istruzioni da eseguire in sequenza: l’istruzione quindi, dopo

S a

aver atteso che la condizione diventi vera, l’istruzione .

C S

b

Alcuni casi particolari di regioni critiche sono:

• specifica della sola mutua esclusione senza che sia prevista alcuna forma di

region R << S; >>:

sincronizzazione diretta.

• specifica di un semplice vincolo di sincronizzazione, quindi il processo

region R << when(C) >>:

attende che sia verificata prima di proseguire.

C

• specifica il caso in cui la condizione di sincronizzazione caratterizza

region R << when(C) S; >>: C

lo stato in cui la risorsa deve trovarsi al fine di poter eseguire l’operazione

R S.

18 M

Mittente Destinatario

Esempio 4.1 In questo esempio si mostra l’utilizzo di re- T mes; T mes;

gioni critiche condizionali applicate ad un’ipotetica situazione ... ...

M.inserisci(mes); M.estrai();

di scambio di messaggi tra due processi, mittente e destina- Buffer

... ...

tario. Essi condividono una variabile per leggere e scrivere

il messaggio, quindi con un doppio vincolo di sincronizzazio- Figura 4.2: Buffer di scambio di messaggi.

ne da soddisfare. Supponendo che sia una risorsa con i

M

seguenti campi:

1 T buffer ;

2 boolean pieno ;

si ha: 1 void inserisci (T dato):

2 region M << when( pieno == false)

3 buffer = dato;

4 pieno = true; >>

5

6 T estrai ():

7 region M << when( pieno == true)

8 pieno = false;

9 return buffer ; >>

4.2 Richiami al problema della mutua esclusione

Il problema della mutua esclusione nasce quando più di un processo alla volta può aver accesso a variabili

comuni. La regola di mutua esclusione impone che le operazioni con le quali i processi accedono alle variabili

comuni non si sovrappongano nel tempo. Tali operazioni vengono dette atomiche in quanto eseguono delle

trasformazioni di stato indivisibili, ossia per le quali può esistere uno stato intermedio nella realizzazione

delle azioni che non è però rilevabile all’esterno. La parte di istruzioni con le quali un processo accede e

modifica un insieme di variabili comuni prende il nome di sezione critica.

La regola di mutua esclusione stabilisce che:

Sezioni critiche appartenenti alla stessa classe devono escludersi mutuamente nel tempo.

oppure

Ad ogni istante può essere in esecuzione al più una sezione critica di ogni classe.

La realizzazione di tale regola può avere tre tipi di soluzioni:

• soluzioni algoritmiche (come gli algoritmi di Dekker o di Patterson e altre);

• soluzioni hardware (come la disabilitazione delle interruzioni e il lock-unlock);

• utilizzo di strumen