Il semaforo privato

IL SEMAFORO PRIVATO

In tutti gli esempi visti fin qui, la procedura di rilascio si affida sempre alla primitiva SIGNAL per sbloccare un processo. La politica di scheduling dei processi che si può ottenere utilizzando questa primitiva non dipende dalla particolare risorsa interessata, giacché la SIGNAL si comporta sempre nella stessa maniera.

Questo evidente inconveniente si può superare utilizzando il concetto di SEMAFORO PRIVATO. Su di un semaforo di questa specie, un solo processo può eseguire la WAIT, mentre altri che ne hanno visibilità possono solamente sbloccarlo eseguendo una SIGNAL. Il semaforo è dunque 'privato' nel senso che su di esso può rimanere in attesa al più un solo processo.

Diversamente dal solito, questo semaforo è inizializzato a zero, in modo tale che il processo che richiede la corrispondente risorsa si blocchi su di esso finché non intervenga un altro processo a dargli il 'via libera'.

Un semaforo privato consente di realizzare differenti politiche di schedulazione. Esaminiamo il seguente esempio, tratto dall'Ancilotti-Boari (pag.93). Esso riprende il problema dei lettori scrittori ed è finalizzato a risolvere la questione della possibile attesa indefinita degli uni e degli altri.

Type processi = 1.. num_proc ;

var mutex : semaphore initial (1) ;

priv : array [1.. num_proc] of semaphore initial (0) ;

procedure Acquisizione (i: processi, ) ;

begin

WAIT (mutex) ;

if < condizione di sincronizzazione > then

begin

< allocazione della risorsa > ;

SIGNAL (priv[i]) ;

end ;

else < indicazione di sospensione del processo > ;

SIGNAL (mutex) ;

WAIT (priv[i]) ;

end ;

procedure Rilascio () ;

var i: processi ;

begin

WAIT (mutex) ;

< rilascio della risorsa > ;

if < esiste almeno un processo sospeso per il quale

la condizione di sincronizzazione è soddisfatta > then

begin

< scelta del processo P_i da riattivare > ;

< allocazione della risorsa a P_i > ;

< indicazione che P_i non è più sospeso > ;

SIGNAL (priv[i]) ;

end ;

SIGNAL (mutex) ;

end ;

Nella procedura di acquisizione, andiamo a consultare una struttura dati nella quale è registrato lo stato della risorsa. Quest'ultimo infatti deve essere compatibile con la richiesta fatta dal processo, e all'interno della struttura dati vi saranno vari parametri, relativi ai tipi di utilizzo della risorsa che i processi possono voler fare (è previsto quindi che sia consentita più di una operazione).

Ovviamente, tale struttura deve essere manipolata nel contesto di una sezione critica, per cui occorre premettere una WAIT (mutex). Una volta che ci si è impossessati della struttura dati, si controlla se è soddisfatta la condizione di sincronizzazione, ovvero se la richiesta fatta dal processo è compatibile con lo stato attuale della risorsa. Supposto che la condizione di sincronizzazione sia verificata, si alloca la risorsa, e questo comporta che nella struttura dati sia memorizzato il fatto che un processo sta utilizzando quella risorsa. Dopodiché, come si vede, il processo fa una SIGNAL sul suo semaforo privato, che parte da 0 e quindi a questo punto assume il valore 1 (l'inserimento di questa SIGNAL può sembrare strano, ma il seguito ne vedremo il motivo).

Naturalmente, se non è prevista la possibilità di effettuare operazioni diverse sulla risorsa, la condizione di sincronizzazione è proprio lo stato della medesima.

Se tale condizione non è verificata l'acquisizione non viene concessa e il processo viene bloccato. L'"indicazione della sospensione del processo" sta a significare che nella struttura dati bisogna registrare il fatto che su quella risorsa è in attesa un processo, dimodoché, quando la risorsa si renderà successivamente disponibile, il processo pendente potrà essere servito. Ovviamente ciò può avvenire solo in conseguenza della esecuzione della procedura di rilascio dai parte di qualche altro processo.

Fatto ciò, si libera la regione critica (SIGNAL (mutex)). Supponiamo che la condizione di sincronizzazione entro la regione critica non sia stata verificata. In tal caso l'unica operazione effettuata sul semaforo privato risulta essere la WAIT (priv[i]), con la quale il processo in questione si mette in attesa della risorsa sul proprio semaforo privato. Tale attesa va realizzata fuori della sezione critica, per non causare il blocco del sistema. Se invece la condizione era stata verificata, si eseguono in sequenza una SIGNAL e una WAIT sul semaforo privato, e questo fa sì che il processo non si trovi ad attendere sulla WAIT, e che il semaforo sia riportato a zero.

Vediamo ora come è fatta la procedura di rilascio. Dopo essere penetrati nella regione critica, bisogna registrare nella struttura dati associata alla risorsa il fatto che la stessa è libera. La successiva operazione consiste nel controllare se il rilascio consente di sbloccare un altro processo, cioè se esiste almeno un processo tra quelli sospesi per il quale, in seguito al rilascio appena effettuato, risulta soddisfatta la condizione di sincronizzazione. Anche questa informazione è reperibile all'interno della struttura dati (dato che ogni processo che viene sospeso scrive delle informazioni in tale struttura).

Se un tale processo viene trovato, si entra nel ramo then e questo permette di eseguire l'istruzione che rappresenta il vero e proprio nocciolo della questione: la scelta del processo P_i da riattivare.

La riattivazione non viene cioè realizzata a mezzo di una semplice SIGNAL, ma piuttosto viene richiamato un algoritmo che, in base a criteri legati alla natura della risorsa in questione, sceglie il processo più adatto, ovviamente sempre che ve ne sia più di uno. Questo vuol dire adattare la politica di scheduling alla particolare risorsa che si sta usando.

Una volta allocata la risorsa, si deve indicare (sempre nella struttura dati) la cessata sospensione del processo P_i, e infine sbloccare quest'ultimo sul suo semaforo privato: P_i viene così sbloccato dall'attesa a cui era stato costretto a causa dell'istruzione WAIT (priv[i]) ed entra nella procedura d'uso; ciò equivale a fargli compiere le transizioni di stato wait - ready - running.

Notiamo che sarebbe possibile mettere in ciclo l'istruzione if < esiste almeno un processo > in modo da consentire, in seguito alla liberazione di una risorsa da parte di un processo, lo sblocco di più processi. Questa eventualità non deve sembrare strana: supponendo ad esempio che la risorsa in gioco sia uno spazio di memoria, può capitare che un processo ne rilasci un'area di considerevole ampiezza, la quale quindi possa essere poi distribuita tra due o più processi in attesa di aree di memoria più piccole.

Le procedure di cui si è discusso fin qui rivelano degli inconvenienti.

Il più evidente è che il codice relativo alla allocazione della risorsa si trova in entrambe. Infatti tale codice è necessario nella procedura di acquisizione per allocare la risorsa nel caso essa risulti libera; è necessario nella procedura di rilascio, per allocarla nel caso di sblocco di un processo. Questa circostanza è da considerarsi negativa, perché è auspicabile che le procedure facenti parte del Kernel soddisfino dei buoni requisiti di economia di spazio e tempo, e la duplicazione di una stessa parte di codice non può che ostacolare tale proposito.

Per ragioni similari sarebbe meglio evitare l'"arzigogolo" di dover effettuare, nella procedura di acquisizione, una SIGNAL subito seguita da una WAIT (sul semaforo privato).

Prenderemo ora in esame un secondo schema per le procedure di acquisizione & rilascio il quale non presenta questi difetti. Per contro, esso non prevede la possibilità di sbloccare più processi all'atto del rilascio della risorsa, e quindi risulta adatto solo per quelle periferiche per le quali non ha senso considerare tale possibilità, tipo le stampanti.

Var mutex : semaphore initial (1) ;

priv : array [1.. num_proc] of semaphore initial (0) ;

procedure Acquisizione (i : processi) ;

begin

WAIT (mutex) ;

if not < condizione di sincronizzazione > then

begin

< indicazione di sospensione del processo > ;

SIGNAL (mutex) ;

WAIT (priv[i]) ;

< indicazione processo non più sospeso > ;

end ;

< allocazione della risorsa > ;

SIGNAL (mutex) ;

and ;

Procedure Rilascio () ;

var i : processi ;

begin

WAIT (mutex) ;

< rilascio della risorsa > ;

if < esiste almeno un processo sospeso

per il quale la condizione di sincronizzazione è soddisfatta >

then

begin

< scelta del processo P_i da riattivare >

SIGNAL (priv[i]) ;

end ;

else SIGNAL (mutex) ;

end ;

Le procedure di acquisizione dei due schemi sono grossomodo uguali, tranne per il fatto che la seconda è progettata in modo da impedire la sequenza signal - wait sul semaforo privato. Dal punto di vista del codice, le differenze sono tre: la verifica della condizione di sincronizzazione viene fatta al negativo (if not < condizione di >); l'eventuale sospensione del processo (WAIT (priv[i])) viene effettuata all'interno della procedura, e non alla fine, come nel caso precedente; infine, si è reso necessario replicare l'istruzione SIGNAL (mutex).

La vera differenza tra i due schemi è però rappresentata dalle procedure di rilascio. Osserviamo che esse coincidono fino al ramo then dell'istruzione if, dopodiché si differenziano sostanzialmente. Se esiste un processo sospeso per il quale sia soddisfatta la condizione di sincronizzazione, si sceglie ancora il processo da riattivare, ma non ne conseguono né l'allocazione della risorsa, né l'indicazione del fatto che il processo non è più sospeso.

Questo perché nel caso precedente il processo sbloccato partiva dall'istruzione WAIT (priv[i]) che si trovava al termine della procedura di acquisizione ed entrava direttamente nella procedura d'uso. Invece, in questo secondo caso, il processo sbloccato parte dall'interno della procedura di acquisizione, ed è quindi in questa procedura che troviamo l'indicazione della cessata sospensione del processo e l'allocazione della risorsa.

Dovrebbero ora essere più chiare le modifiche apportate alla procedura di acquisizione.

In tale procedura, si entra nella regione critica facendo, come di consueto, la WAIT (mutex).

- In caso di sospensione del processo, si esce una prima volta dalla regione critica mediante la SIGNAL (mutex) che si trova all'interno della condizione if not. Un processo P* che libera la risorsa effettuerà la WAIT (mutex) che si trova in testa alla procedura di rilascio. Se esiste almeno un processo sospeso, a quest'ultimo è delegato il compito di liberare nuovamente la regione critica, eseguendo la SIGNAL (mutex) che si trova in chiusura della procedura di Acquisizione. Se non ne esiste nessuno, se ne occuperà lo stesso P* (ramo else della procedura di rilascio).

- Se invece la condizione di sincronizzazione è soddisfatta, la regione critica viene liberata direttamente dalla SIGNAL che si trova in chiusura della procedura di acquisizione. Subito dopo verrà eseguita la procedura d'uso della risorsa.

Perché non è consentito mettere in ciclo la ricerca di un processo per cui la condizione di sincronizzazione è soddisfatta e la sua attivazione? Perché se si provasse a farlo partirebbero più processi all'interno della regione critica, e questo, per definizione stessa di regione critica, è inammissibile.

ESEMPI D'USO DEI SEMAFORI PRIVATI

PRIMO ESEMPIO. È basato sul secondo modello di semaforo privato, quello presentato a pag. 72.

Ogni processo può usare una risorsa di un comune insieme dopo averne fatto richiesta, quindi la deve rilasciare. Le procedure richiesta e rilascio devono essere programmate in modo da consentire una gestione delle risorse comuni secondo la priorità dei processi.

Indichiamo con:

- PS [i] : variabile booleana che assume il valore vero se il processo P_i è sospeso, falso altrimenti;

- risorse [j] : variabile booleana che è falsa se la risorsa j-esima è occupata, vera altrimenti;

- disponibile : numero delle risorse non occupate;

- sospesi : numero dei processi sospesi;

- mutex : semaforo di mutua esclusione;

- priv [i] : semaforo privato del processo P_i;

- x : indice della risorsa allocata al processo richiedente o rilasciata;

- i : nome del processo.

Il codice è il seguente:

Var risorse : array [1.. num_ris] of boolean initial (true) ;

PS : array [1.. num_proc] of boolean initial (false) ;

disponibile : 0.. num_ris initial (num_ris) ;

sospesi : 0.. num_proc initial (0) ;

mutex : semaphore initial (1) ;

priv : array [1..num_proc] of semaphore initial (0) ;

procedure Richiesta (var x : 1.. num_ris; i : 1.. num_proc);

var k : 0..num_ris;

begin

WAIT (mutex) ;

if disponibile = 0 then /* il processo deve essere sospeso */

begin

PS[i] : = true ;

sospesi : = sospesi + 1 ;

SIGNAL (mutex) ;

WAIT (priv[i]) ; /* effettiva sospensione;

superata questa wait, il processo non è più sospeso */

PS[i] : = false ;

sospesi : = sospesi - 1 ;

end ; /* si procede all'assegnazione di una risorsa */

k : = 0 ;

repeat

k : = k + 1

until risorse [k] ;

x : = k ; /* assegnazione */

risorse [k] : = false ;

disponibile : = disponibile - 1 ;

SIGNAL (mutex) ;

end ;

Procedure Rilascio (x : 1.. num_ris) ;

var j : 1.. num_proc ;

begin

WAIT (mutex) ;

risorse [x] : = true ;

disponibile : = disponibile + 1 ;

if sospesi > 0 then

begin

< seleziona il processo P_j a massima priorità fra quelli sospesi

utilizzando il vettore PS dei processi sospesi > ;

SIGNAL (priv[j]) ;

end ;

else SIGNAL (mutex) ; /* non ci sono processi in attesa */

end ;

Nella procedura di richiesta si esamina anzitutto la variabile disponibile. Se è uguale a zero, il processo in questione deve andare a ingrossare il numero dei processi sospesi, e quindi è necessario incrementare la variabile sospesi e modificare il vettore PS Dopodiché si libera la regione critica e si attende la commutazione del semaforo privato.

Quando il processo è sbloccato aggiorniamo il vettore e la variabile sospesi. Di conseguenza viene presa la prima risorsa libera mediante un ciclo sul vettore risorse. Quindi si aggiornano il vettore risorse e la variabile disponibili e si esce dalla regione critica.

Nella procedura di rilascio incrementiamo la variabile disponibile e segnaliamo nel vettore risorse il fatto che una risorsa è stata rilasciata. Se c'è almeno un processo sospeso occorre selezionare quello da sbloccare in base ai criteri di priorità che sono stati scelti. (La priorità di un processo è di solito memorizzata in uno dei campi del suo descrittore, e potrebbe essere assegnata staticamente o anche aggiornata di volta in volta durante l'esecuzione). Se invece non ci sono processi sospesi la procedura termina.

SECONDO ESEMPIO. È basato questa volta sul primo schema (pag. 69).

Si vuole gestire l'allocazione di un'area di memoria secondo una politica che privilegia il processo che ha fatto la richiesta di memoria più ingente. Qualora tale richiesta non possa essere soddisfatta, l'area di memoria liberatasi non viene concessa ad altri processi, ma si aspetta che si accumuli abbastanza memoria da soddisfare sempre la richiesta maggiore. Questo modo di procedere è più ragionevole di quanto non sembri, perché in caso contrario il processo in questione rimarrebbe in eterna attesa.

Si indica con:

- sospesi : numero dei processi sospesi;

- vuote : numero di celle vuote del buffer;

- richiesta [i] : numero di celle richieste dal processo sospeso P_i;

- mutex : semaforo di mutua esclusione;

- priv [i] : semaforo privato del generico P_i;

- m : dimensione (in celle) dell'area di memoria richiesta dal messaggio, o numero di celle rilasciate;

- i : nome del processo chiamante.

Il codice è il seguente.

Var richiesta : array [1.. num_proc] of integer initial (0) ;

sospesi : integer initial (0) ;

vuote : integer initial (N) ;

mutex : semaphore initial (N) ;

priv : array [1.. num_proc] of semaphore initial (0) ;

buffer : /* il buffer sarà dichiarato come un insieme di celle */ ;

Procedure Acquisizione (m: integer; i: 1.. num_proc);

begin

WAIT (mutex) ;

if sospesi = 0 and vuote >= m then /* la richiesta può essere soddisfatta */

begin

vuote : = vuote - m ;

< assegnazione al processo di m celle del buffer > ;

SIGNAL (priv[i]) ;

end ;

else /* permesso negato */

begin

richiesta [i] : = m ;

sospesi : = sospesi + 1;

end ;

SIGNAL (mutex) ;

WAIT (priv[i]) ;

end ;

Procedure Rilascio (m: integer) ;

var i, max : = 1.. num_proc ;

begin

WAIT (mutex) ;

vuote : = vuote + m ;

while sospesi <> 0 do

begin

max : = 1 ;

for i : = 1 to num_proc do

if richiesta [max] < richiesta [i] then max : = i ;

if richiesta [max] <= vuote then

begin

vuote : = vuote - richiesta [max] ;

< assegnazione al processo P_k delle celle richieste > ;

richiesta [max] : = 0 ;

sospesi : = sospesi - 1 ;

SIGNAL  (priv[max]) ;

end ;

else exit ; /* esce dal ciclo while */

end ;

SIGNAL (mutex) ;

end ;

Si noti che nell'acquisizione la condizione di sincronizzazione è:         

sospesi = 0 and vuote >= m

Se 'non c'è alcun processo sospeso' e contemporaneamente 'il numero di celle vuote è maggiore del richiesto' si può concedere l'assegnazione.

Se ci sono processi sospesi, la richiesta non può essere soddisfatta in nessun caso. Infatti, se la richiesta del processo che ha chiamato la procedura di acquisizione è minore di quella di un processo sospeso, l'assegnazione è impedita dalla particolare politica di gestione che abbiamo adottato. Se è maggiore, l'assegnazione è logicamente impossibile.

Nel caso in cui non ci sia alcun processo sospeso, occorre controllare anche se la richiesta è compatibile con la memoria a disposizione.

Si osservi poi il ruolo del vettore Richiesta. Esso dice esplicitamente quante celle di memoria richiede ogni processo, e implicitamente quali processi sono sospesi e quali no: infatti per un processo sospeso si ha richiesta[i] <> 0.

Nella procedure di rilascio viene realizzato un ciclo che dura fintantoché ci sono processi sospesi, finalizzato a scegliere il processo con la massima richiesta di memoria. A questo punto, abbiamo due alternative: se la quantità richiesta è non maggiore del numero di celle vuote si può procedere con l'assegnazione, eseguendo delle operazioni facilmente comprensibili. Si noti che l' "assegnazione al processo delle celle richieste" consiste ad esempio, in una gestione a partizione, memorizzare nel descrittore del processo la partizione che è stata concessa. Fatto questo il ciclo while può essere ripetuto, in quanto è possibile che la quantità di memoria che è stata rilasciata sia sufficiente per liberare più di un processo in attesa.

Si esce dal while non appena il processo caratterizzato dalla maggiore richiesta di memoria verifica la condizione richiesta [k] > vuote.

TERZO ESEMPIO. Riguarda l'eliminazione del problema della possibili attese infinite nel caso del lettori scrittori (pag. 63 sgg). Dobbiamo usare necessariamente il primo schema di semaforo privato, dato che in seguito alla scrittura di un messaggio deve essere consentito a più processi lettori in attesa (se ce ne sono) di riprendere l'esecuzione.

Come accennato la scorsa volta, il fenomeno dello starvation viene scongiurato alternando, quando è possibile, l'esecuzione dei lettori a quella degli scrittori. Se 'arriva' un lettore in un momento in cui altri lettori stanno leggendo, si controlla se c'è uno scrittore in attesa e in caso affermativo il lettore in questione viene bloccato. Al termine della lettura sarà quindi uno scrittore a passare al semaforo. Si comprende dunque che un lettore che esegue la procedura di acquisizione del buffer viene sospeso non solo se c'è uno scrittore in esecuzione, ma anche se ci sono dei lettori e almeno uno scrittore in attesa. In modo analogo, se uno scrittore sta scrivendo e ci sono in attesa sia lettori che scrittori, alla fine dell'operazione di scrittura vengono fatti passare tutti i lettori presenti in modo da evitare un possibile starvation dei lettori.

Ad esempio, se uno scrittore esce e risulta che ci sono in attesa due scrittori e dieci lettori, vengono fatti passare tutti e dieci i lettori. Se nel frattempo giungesse un undicesimo lettore esso sarebbe sospeso, perché troverebbe degli scrittori in attesa. Quindi viene data la parola al primo dei due scrittori. L'undicesimo lettore passerà solo dopo che tale scrittore avrà terminato.

Indichiamo con:

- lettori_attivi : numero di lettori che stanno operando contemporaneamente sul record comune;

- scrittori_attivi : variabile booleana che vale true se uno scrittore sta operando sul record comune, false in caso contrario (si noti che è sufficiente una variabile logica, dal momento che al massimo ci può essere uno scrittore attivo);

- lettori_bloccati : numero di lettori sospesi;

- scrittori_bloccati : analoga variabile per gli scrittori;

- mutex : semaforo necessario per operare sulle precedenti variabili in modo mutuamente esclusivo;

- sem_priv_lett : semaforo privato dei lettori; il concetto di semaforo viene qui esteso (e subito utilizzato) ad un gruppo di processi equivalenti. Infatti, la strategia prevede di controllare la priorità fra i due gruppi di processi e non fra i processi singoli;

- sem_priv_scritt : analogo semaforo per i processi scrittori.

Segue il codice.

Var mutex : semaphore initial (1) ;

lettori_attivi : integer initial (0) ;

scrittori_attivi : boolean initial (false) ;

lettori_bloccati : integer initial (0) ;

scrittori_bloccati : integer initial (0) ;

sem_priv_lett : semaphore initial (0) ;

sem_priv_scritt : semaphore initial (0) ;

Procedure Inizio_lettura ;

begin

WAIT (mutex) ;

if not scrittori _attivi and scrittori_bloccati = 0 then

begin

SIGNAL (sem_priv_lett) ;

lettori_attivi : = lettori_attivi + 1 ;

end ;

else lettori_bloccati : = lettori_bloccati + 1 ;

SIGNAL (mutex) ;

WAIT (sem_priv_lett) ;

end ;

Procedure Fine_lettura ;

begin

WAIT (mutex) ;

lettori_attivi : = lettori_attivi - 1 ;

if lettori_attivi = 0 and scrittori_bloccati > 0 then

begin

scrittori_attivi : = true ;

scrittori_bloccati : = scrittori_bloccati - 1 ;

SIGNAL (sem_priv_scritt) ;

end ;

SIGNAL (mutex) ;

end ;

Procedure Inizio_scrittura ;

begin

WAIT (mutex) ;

if lettori_attivi = 0 and not scrittori_attivi then

begin

SIGNAL (sem_priv_scritt) ;

scrittori_attivi : = true ;

end

else scrittori_bloccati : = scrittori_bloccati + 1 ;

SIGNAL (mutex)M

WAIT (sem_priv_scritt) ;

end ;

Procedure Fine_scrittura ;

begin

WAIT (mutex) ;

scrittori_attivi : = false ;

if lettori_bloccati > 0 then

repeat

lettori_attivi : = lettori_attivi + 1 ;

lettori_bloccati : = lettori_bloccati - 1 ;

SIGNAL (sem_priv_lett) ;

until lettori_bloccati = 0 ;

else if scrittori_bloccati > 0 then

begin

scrittori_attivi : = true ;

scrittori_bloccati := scrittori_bloccati - 1 ;

SIGNAL (sem_priv_scritt) ;

end ;

SIGNAL (mutex) ;

end ;

Esaminiamo brevemente le quattro procedure.

In Inizio_lettura, la condizione che si trova all'interno della regione critica è che non ci siano scrittori bloccati né attivi. Si esegue dunque la SIGNAL sul semaforo privato della classe dei lettori. Se la condizione di sincronizzazione non è soddisfatta, il numero dei lettori bloccati viene accresciuto e ci si mette in attesa sul semaforo privato.

Nella procedura Fine_lettura, dopo aver decrementato il numero dei lettori attivi si passa a verificare la condizione di sblocco di un altro processo. Essa è verificata solo se non ci sono più lettori attivi e c'è almeno uno scrittore bloccato (su Inizio_scrittura). Si noti che in caso di assenza di scrittori bloccati non è possibile che ci siano dei lettori in attesa, dato che se un lettore sopraggiunge in questo frangente la risorsa gli viene concessa senz'altro. Se la condizione di sblocco scrittori è soddisfatta, vengono compiute tre operazioni di ovvio significato. Naturalmente il rilascio del lettore provoca al massimo lo sblocco in un solo scrittore.

In Inizio_scrittura, risulta, coerentemente con quello che sappiamo, che per potere scrivere non ci devono essere né lettori, né scrittori attivi. In caso contrario lo scrittore ultimo arrivato viene bloccato.

La procedura Fine_scrittura è probabilmente la più interessante delle quattro, per il modo in cui viene implementata la partenza "a cascata" di più lettori. Se ci sono lettori bloccati, viene fatto un ciclo che, fino ad esaurimento degli stessi, esegue le tre operazioni: decremento della variabile dei lettori bloccati, incremento di quella dei lettori attivi, sblocco di un lettore. Se non ci sono lettori bloccati si passa a verificare la presenza di scrittori in attesa e in caso affermativo se ne sblocca uno.

Considerazioni conclusive sui semafori privati. Abbiamo visto che un processo sospeso registra la sua condizione di sospensione all'interno di una struttura dati condivisa fra tutti i processi. La struttura dati tiene il conto da un lato dei processi in attesa, ma dall'altro anche dello stato della risorsa (nei tre esempi fatti, questo stato è memorizzato rispettivamente nelle variabili vuote, risorse e lettori_attivi / scrittori attivi). Per non rendere inconsistente la struttura dati, la registrazione di tale informazione va fatta all'interno di una regione critica.

In secondo luogo, gli schemi presentati tendono a separare nettamente la fase di assegnazione della risorsa da quella di uso della medesima. L'assegnazione avviene nelle procedure di acquisizione & rilascio, mentre l'uso avviene poco prima della chiamata della procedura di rilascio.

IL COSTRUTTO 'REGIONE CRITICA'

Fino a questo momento, abbiamo visto vari modi di realizzare un gestore di risorsa avendo a disposizione le primitive WAIT e SIGNAL, le quali tipicamente sono messe a disposizione dal SO.

Le cose cambiano notevolmente quando si ha a che fare con un LINGUAGGIO DI PROGRAMMAZIONE CONCORRENTE, il quale generalmente consente di utilizzare dei costrutti linguistici più potenti. Sarà poi compito del compilatore eliminare il gap semantico, traducendo questi costrutti sofisticati in termini di WAIT e SIGNAL.

Al solo scopo di capire questo concetto, vedremo alcuni costrutti di linguaggio ad alto livello, e la loro corrispondente realizzazione in termini di WAIT e SIGNAL. Qualora il particolare linguaggio in uso non prevedesse i costrutti che presenteremo, potrebbe essere conveniente usarli ugualmente in fase di progetto e poi effettuare una 'compilazione a mano' mediante i costrutti WAIT e SIGNAL.

Il costruttore più banale è quello della REGIONE CRITICA, che serve a risolvere il problema della mutua esclusione. Volendo scrivere del codice che deve essere eseguito in mutua esclusione, ad esempio relativo all'uso di una risorsa, dovremmo premettere ad esso le primitive WAIT e SIGNAL:

WAIT (sem)

REGIONE CRITICA

SIGNAL (sem)

Il costrutto corrispondente a questo semplice schema è:

REGION v DO S

V rappresenta una variabile che identifica una certa risorsa, S è una delle regioni critiche che fanno riferimento ad essa. Quindi, se due processi devono operare su di una medesima struttura dati in mutua esclusione, essi saranno scritti come segue:

REGION v DO   REGION v do

begin begin

< codice A > < codice B >

end ; end ;

La variabile v può essere dichiarata, ad esempio, così:

var v : shared T

ove T è un tipo comune a più processi.

Il compilatore di un linguaggio che prevede la REGION non fa altro che inserire una WAIT ed una SIGNAL rispettivamente prima del begin e dopo l'end. Ovviamente occorreranno tanti semafori quanto sono le regioni critiche.

Un prerogativa del costrutto REGION è che esso evita di commettere errori banali, come quello di scrivere due WAIT di seguito sullo stesso semaforo anziché una WAIT e una SIGNAL, o quello di invertire l'ordine di queste due primitive. Inoltre, REGION rende più semplice il nesting delle regioni critiche. Ad esempio, immaginiamo che all'interno di una regione critica riguardante del codice da eseguire in mutua esclusione tra un processo A ed un processo B, sia presente un'altra regione critica che deve essere eseguita in mutua esclusione tra A e C, ma che a C non sia consentito l'accesso alla prima regione critica. Tutto ciò è esprimibile come segue:

WAIT (sem)

.

WAIT (sem')

.

SIGNAL (sem')

.

SIGNAL (sem)            

con il rischio evidente di invertire per errore l'ordine di qualcuna delle primitive. Ma questo pericolo diventa inesistente se ci si affida al costrutto REGION:

REGION v DO

begin

.

REGION v DO

begin

end ;

.

end ;

Il costrutto REGIONE CRITICA CONDIZIONALE consente ad un processo di accedere alla variabile v solo se è verificata la condizione B.

REGION v WHEN B DO S

Supponendo di trovarla libera, il processo entra nella regione critica e verifica la condizione B. Se questa è verificata, il processo esegue S ed esce dalla regione. Contrariamente, esso si mette in attesa che la regione critica sia rilasciata. Il processo resta in attesa fino a che B diventa vera, e sempre che nessun altro processo stia operando all'interno della regione critica. Nella prossima lezione il funzionamento di questo costrutto risulterà più chiaro. Osserviamo comunque che esso è più potente di quello precedente, giacché il compilatore non solo si fa carico di verificare se il processo può entrare nella regione critica, ma anche di risvegliarlo quando qualcuno ne esce (a livello di programma non dovremo quindi preoccuparci di gestire questa situazione, che risulta apertamente espressa dalla sintassi del comando). Ogniqualvolta un processo abbandona la regione critica, siccome la condizione per cui un altro processo è bloccato può risultare modificata, il compilatore deve provvedere a riattivare i processi sospesi e fare in modo che, uno alla volta, possano riverificare la condizione B.

Vediamo infine un paio di esempi di uso di questi costrutti; ci rifaremo a due problemi già considerati, cioè quello dell'allocazione dinamica di un insieme di risorse equivalenti (pag.51) e quello dello scambio di messaggi tra processi (pag.55). Si noterà che le procedure risolutive appaiono più brevi e leggibili.

Abbiamo N risorse equivalente condivise tra k diversi processi. Utilizzando i costrutti regione critica & regione critica condizionale, si avrà:

Var gestore_risorse : shared record

libero : array [1..N] of boolean initial (true) ;

disponibile : 0..N initial (N) ;

end ;

Procedure Acquisizione (var x : 1.. N) ;

var i : 0.. N ;

begin

REGION gestore _risorse

WHEN disponibile > 0 DO

i : = 1 ;

while not libero [i] do i : = i + 1 ;

x : = i ;

libero [i] : = false ;

disponibile : = disponibile - 1 ;

end ;

end ;

Procedure Rilascio (x : 1..N) ;

begin

REGION gestore_risorse

DO

libero [x] : = true ;

disponibile : = disponibile + 1 ;

end ;

end ;

Nella procedura di acquisizione, si entra nella regione critica relativa al gestore della risorsa solo quando c'è almeno una risorsa libera, che in questo caso viene prelevata. Nel caso del rilascio, invece, si entra sempre nella regione critica e la risorsa viene liberata.

Riscriviamo ora le procedure relative al problema dello scambio di messaggi tra processi.

Var mailbox : shared record

buffer : array [0.. N-1] of messaggio ;

testa : 0.. N-1 initial (0) ;

coda : 0..N-1 initial (0) ;

cont : 0..N initial (0) ;

end ;

Procedure Invio (x : messaggio) ;

begin

REGION mailbox

WHEN cont < N do

buffer [coda] : = x ;

coda : = (coda + 1) mod N ;

cont : = cont + 1 ;

end ;

end ;

Procedure Ricezione (var x : messaggio) ;

begin

REGION mailbox

WHEN cont > 0 do

x : = buffer [testa] ;

testa : = (testa + 1) mod N :

cont : = cont - 1 ;

end ;

end ;

La regione critica si chiama ora mailbox e può essere acceduta in acquisizione quando è presente, all'interno del pool, almeno un buffer libero. In caso affermativo, poniamo il messaggio nel buffer, incrementiamo il puntatore alla coda e il conteggio dei messaggi memorizzati. In ricezione possiamo entrare nella regione critica quando c'è almeno un buffer occupato, e in questo caso il messaggio viene ovviamente prelevato.

Notiamo che questa soluzione ha un parallelismo minore rispetto a quella realizzata con Wait e Signal. Non è più possibile che vi siano contemporaneamente una produzione ed un consumo su buffer differenti, dal momento che produttori e consumatori operano sulla stessa regione critica mailbox e su questa il compilatore garantisce la mutua esclusione. Come spesso accade quando si agisce in modo tale da aumentare l'astrazione, le cose diventano più facili ma si perde qualche cosa in flessibilità.

La volta scorsa abbiamo introdotto il costrutto Regione critica condizionale.

REGION v WHEN B DO S end ;

Oggi ci occupiamo di tradurre tale costrutto in termini di primitive WAIT e SIGNAL. Innanzitutto, trattandosi di una regione critica, è necessario usare un semaforo di mutua esclusione, mutex:

Var mutex: semaphore initial (1) ;

synch: semaphore initial (0) ;

cont: integer initial (0) ;

WAIT (mutex) ;

while not B do

begin

cont : = cont + 1 ;

SIGNAL (mutex) ;

WAIT (synch) ;

WAIT (mutex) ;

end ;

S ;

while cont <> 0 do

begin

SIGNAL (synch) ;

cont : = cont - 1 ;

end ;

SIGNAL (mutex) ;

Per iniziare, viene effettuata una WAIT sul semaforo mutex in modo che, quando il processo lo supera, è sicuro di essere il solo a stare nella regione critica.

Una volta entrato nella regione critica, si controlla la condizione B[2]. Se è soddisfatta si passa ad eseguire la regione critica S.

In caso contrario viene aggiornato il contatore cont, che si occupa di contare i processi bloccati sulla condizione B. Subito dopo occorre liberare la regione critica eseguendo una SIGNAL (mutex) e mettersi in attesa sul semaforo synch, che è inizializzato a zero.

Un processo che è stato in grado di eseguire la regione critica S effettua successivamente una serie di SIGNAL (synch) finalizzata a sbloccare tutti i processi (diciamoli 'SB') che erano stati sospesi perché non rispondevano al requisito B. Quindi i processi SB vengono bloccati nuovamente, ma questo volta sul semaforo mutex, finché il processo non esegue la SIGNAL (mutex) liberando così la regione critica. Naturalmente è possibilissimo che nel frattempo altri processi si siano posti in attesa sul semaforo mutex (istruzione WAIT (mutex) che si trova in testa al codice), nel quale caso i processi SB non potranno fare altro che accodarsi. A questo punto al primo dei processi in attesa su mutex viene data facoltà di verificare la condizione B e di ricominciare il ciclo. Osserviamo dunque che, in definitiva, il processo sbloccante rimette in gioco non solo i processi SB (cioè quelli che erano in attesa su synch), ma anche quelli in attesa su mutex.

Questa soluzione presenta lo svantaggio di essere molto dispendiosa in termini di tempo. All'uscita dalla regione critica viene liberata una certa quantità di processi, e a questi viene concessa la possibilità di valutare la condizione B, finché non se ne trova uno che la verifica. Tutti gli altri processi rimangono bloccati, chi sul semaforo mutex, chi sul semaforo synch. Tutto ciò provoca svariati cambiamenti di contesto, i quali a loro volta comportano uno spreco di tempo. In conclusione, questo costrutto è efficiente solo se i processi che interagiscono sulla regione critica non sono molto numerosi.

Inoltre sarebbe auspicabile che i processi SB, una volta risvegliati, abbiano la precedenza sulla risorsa B, ma questa soluzione non lo permette. Infine, essa non prevede una possibilità che appare molto comoda, ossia che un processo entri comunque nella regione S e valuti al suo interno la condizione di sincronizzazione, uscendone eventualmente se questa non è soddisfatta; allo scopo si potrebbe usare un costrutto del tipo:

REGION v

DO

S₁ ;

AWAIT B ;

S₂ ;

end ;

Noi non approfondiremo questa differente versione della regione critica condizionale.