COOPERAZIONE TRA PROCESSI CONCORRENTI

Ad ogni segnale inviato da P₀ deve corrispondere un'attivazione. Questo vuol dire che, anche se il segnale di attivazione arriva mentre il processo sta ancora eseguendo l'azione del ciclo precedente (cosa possibile), il segnale non deve 'andare perduto'. Non appena terminata l'azione precedente, il processo, che nel frattempo ha ricevuto un ulteriore segnale di attivazione, deve riprendere immediatamente l'esecuzione.

Nel risolvere questo problema di competizione, bisogna tener conto dei due vincoli che abbiamo sottolineato.

È sufficiente introdur 252e44c re per ogni processo P_i un semaforo s_i con valore iniziale zero, che serve a indicare la presenza o assenza del segnale di attivazione. Ogni P_i esegue la primitiva WAIT (s_i) per effettuare una richiesta di attivazione, mentre P₀ si occupa di eseguire la primitiva SIGNAL (s_i) per inviare a P_i un segnale di attivazione.

Program scambio_di_segnali_temporali ;

var s: array [1..n] of semaphore initial (0)

/* inizializzazione di tutti i semafori associati ai processi al valore zero */

Process P₀ ;

...

begin

loop

...

SIGNAL (s_i)

...

end ;

end ;

Process P_i ;

...

begin

loop

WAIT (s_i)

...

end ;

end ;

2) Scambio di messaggi: il problema produttore / consumatore. L'esempio menzionato nel paragrafo precedente rappresenta un caso di comunicazione asimmetrica tra processi. Infatti, l'esecuzione del processo P_i è regolata da quella di P₀, ma non vale il contrario. Invece il classico problema del produttore e consumatore rappresenta un caso di due processi che regolano ciascuno l'esecuzione dell'altro.

Un primo processo produttore genera ad ogni ciclo un messaggio e lo deposita in un'area di memoria. Un secondo processo consumatore preleva dall'area di memoria tale messaggio e lo usa. Sono previsti i seguenti vincoli:

- il produttore non può depositare un nuovo messaggio se il consumatore non ha ancora raccolto il precedente;

- il consumatore non può raccogliere dall'area di memoria un messaggio prima che il produttore l'abbia depositato.

La soluzione a questo problema prevede che produttori e consumatori si scambino segnali per indicare l'avvenuto deposito e prelievo messaggio dall'area di memoria. Quindi ciascun processo deve attendere, per compiere la sua azione, l'arrivo del segnale dall'altro processo.

In un caso più generale, produttore e consumatore usano un buffer contenente più messaggi. Ad esempio, un processo produce linee da stampare e le pone in un buffer; il corrispondente consumatore provvede alla stampa di tali linee. In tal caso, le due condizioni menzionate diventano:

- il produttore non può inserire un messaggio nel buffer se questo è pieno;

- il consumatore non può prelevare un messaggio dal buffer se questo è vuoto.

Il buffer viene allora programmato come una risorsa condivisa fra i processi produttore e consumatore. In particolare, poiché chiaramente i messaggi devono essere ricevuti nello stesso ordine in cui sono stati inviati, il buffer è una coda di messaggi, e viene corredata da due semafori, che chiameremo spazio_disponibile e messaggio_disponibile, usati dai processi per scambiarsi segnali di avvenuto prelievo e deposito di un messaggio [1].

Il produttore e il consumatore usano rispettivamente le procedure Invio e Ricezione per l'accesso alla risorsa buffer.

Type messaggio = ...

var coda _di_messaggi: ... ;   /* struttura dati del buffer */

messaggio_disponibile: semaphore initial (0) ;

spazio_disponibile: semaphore initial (N) ;

procedure Invio (x : messaggio) ; /* procedure di accesso al buffer */

begin

WAIT (spazio_disponibile) ;

< deposito del messaggio x nella coda dei messaggi >

SIGNAL (messaggio_disponibile) ;

end ;

procedure Ricezione (var x : messaggio) ;

begin

WAIT (messaggio_disponibile) ;

< prelievo di un messaggio dalla coda e sua assegnazione al parametro x >

SIGNAL (spazio_disponibile) ;

end ;

L'Ancilotti-Boari (pag.84) presenta una possibile implementazione del buffer come di un vettore circolare di lunghezza N gestito tramite due puntatori, coda e testa, che individuano rispettivamente la prima porzione vuota e piena del buffer. Inizialmente si ha coda = testa. L'inserimento di un messaggio nel buffer comporta le seguenti operazioni:

vettore (coda) : = < messaggio prodotto > ;

coda : = (coda + 1) mod N ;

mentre il prelievo di un messaggio da parte del consumatore prevede le operazioni:

< messaggio prelevato > : = vettore (testa) ;

testa : = (testa+1) mod N ;

Indi, la struttura dati del buffer e le due procedure di gestione possono essere dettagliate così:

var vettore : array [0... N-1] of messaggio ; /* struttura dati del buffer */

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

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

messaggio_disponibile: semaphore initial (0) ;

spazio_disponibile: semaphore initial (N) ;

procedure Invio (x : messaggio) ;    /* procedure di accesso al buffer */

begin

WAIT (spazio_disponibile) ;

vettore [coda] : = x ;

coda : = (coda + 1) mod N ;

SIGNAL (messaggio_disponibile) ;

end ;

procedure Ricezione (var x : messaggio) ;

begin

WAIT (messaggio_disponibile) ;

x : = vettore [testa] ;

testa : = (testa + 1) mod N ;

SIGNAL (spazio_disponibile) ;

end ;

La scorsa lezione abbiamo usato le primitive WAIT e SIGNAL con lo scopo di scrivere, in casi semplici, dei gestori di risorse. Fondamentalmente, come illustrato dagli esempi fatti, un gestore è costituito dall'insieme di una struttura dati e di alcune procedure operative, tipicamente una per l'acquisizione, una o più per l'uso, una per il rilascio della risorsa.. Eseguendo la procedura di ACQUISIZIONE, un processo chiede di poter accedere ad una risorsa condivisa; poi si servirà delle procedure d'USO e infine di quella di RILASCIO per liberare la risorsa condivisa.

Le procedure di acquisizione, uso e rilascio sono eseguite nel contesto del processo che le chiama e non nel contesto del gestore. Il gestore è dunque una risorsa esso stesso, e non un processo: eseguire le procedure che per convenzione si associano ad esso non equivale a cambiare contesto. Quando si verifica un cambio di contesto (il processo in corso di esecuzione viene sospeso), è sempre un nuovo processo a continuare e non il gestore.

Le primitive WAIT e SIGNAL non sono altro che le procedure di acquisizione e rilascio per una risorsa allocata staticamente e condivisa fra più processi. Come abbiamo visto nell'esempio di pag.50, in questo caso si dovranno gestire tramite i semafori delle regioni (o sezioni) critiche, ovvero eseguire in mutua esclusione una sequenza di istruzioni che rappresenta la procedura di uso della risorsa. Nell'esempio specifico, erano possibili anzi m diverse procedure di utilizzo per la risorsa, ed è risultato conveniente inglobare in ciascuna di esse anche le operazioni di acquisizione e rilascio (ma non era indispensabile farlo).

L'uso delle primitive WAIT, SIGNAL nel modo illustrato ha consentito di evitare che due processi contemporaneamente si trovassero in una sezione critica. Ovviamente si possono avere classi (= gruppi) di sezioni critiche gestite da semafori differenti. Per cui è possibile che un processo si trovi in una sezione critica di una determinata classe e nello stesso tempo un secondo processo si trovi in una sezione critica di una diversa classe. Ciò avviene quando le due classi di sezioni critiche sono riferite a differenti risorse, e si dice che tali classi sono per ipotesi disgiunte o 'non incompatibili'.

Il passo successivo è stato quello di studiare il modo di gestire risorse equivalenti allocate dinamicamente (esempio di pag.51). Anche in questo caso abbiamo preso in considerazione delle procedure di acquisizione e rilascio; la differenza è che gestire una risorsa allocata dinamicamente comporta la necessità di possedere una struttura dati che tenga conto dello stato della risorsa. Nel caso precedente, nei fatti la struttura dati non era altro che un semaforo, giacché tutto ciò che occorreva sapere era se la sola risorsa presente fosse libera oppure occupata. Ora invece, avendo a disposizione più risorse, dobbiamo anche sapere in un dato istante quale di esse è libera e quale no. In tal caso le procedure di rilascio e acquisizione non sono più in corrispondenza uno ad uno con le primitive WAIT e SIGNAL, poiché esse sono chiamate a gestire una struttura dati molto più articolata di un semplice semaforo. Stavolta si tratta dunque di vere e proprie procedure.

Il concetto è che nel momento in cui siamo costretti a realizzare delle procedure di acquisizione e rilascio più complesse, le WAIT e SIGNAL rappresentano semplicemente dei 'mattoni da costruzione'.

Nell'esempio a cui abbiamo accennato, quando un processo desidera l'acquisizione di una risorsa, esso controlla dei semafori, che in definitiva gli dicono se lo stato attuale delle risorse è compatibile con le sue richieste. Tale compatibilità è verificata nell'ipotesi che fra le n risorse equivalenti ve ne sia almeno una libera. In un caso più complicato, potremmo avere una sola risorsa, la quale però può gestire n servizi. Stavolta quindi dovremmo conoscere non solo lo stato della risorsa (se è libera o meno), ma anche quali servizi sta effettuando in un dato momento, per sapere se è possibile soddisfare la specifica richiesta.

In generale, la procedura di richiesta dovrà verificare al suo interno se è soddisfatta quella che è conosciuta col nome di condizione di sincronizzazione. Ciò potrebbe dipendere non semplicemente dallo stato della risorsa, ma piuttosto da una combinazione di tale stato e della particolare richiesta fatta dal processo.

PROBLEMI DI COOPERAZIONE

Come nel caso della competizione, anche nella cooperazione è necessario usufruire di un gestore. Infatti la sequenza di operazioni necessarie procede in modo analogo al caso precedente: si avrà la richiesta di una risorsa fatta da un processo, per poter cooperare con un altro, e il rilascio della medesima una volta che sia avvenuta tale cooperazione.

La volta scorsa abbiamo esaminato un semplice caso di cooperazione tra processi: il problema singolo produttore - singolo consumatore, in cui la cooperazione consiste nel fatto che un processo produce qualcosa e un altro lo usa. È stato necessario sincronizzare opportunamente tali operazioni. Alla richiesta di poter produrre doveva seguire necessariamente un consenso alla produzione, consenso dettato da vincoli abbastanza ovvi. Similmente, alla richiesta d'uso doveva seguire un consenso all'uso.

Nel caso specifico, produttore & consumatore si scambiavano messaggi servendosi di una sequenza di buffer organizzati come una coda circolare. Ciò dava la possibilità al produttore di generare n messaggi di seguito prima di vedersi negato il permesso di produrre. (Questo naturalmente si verifica nel caso limite in cui nel frattempo non avviene alcun consumo). Se invece avessimo avuto un unico buffer saremmo stati costretti ad alternare la produzione con il consumo.

Naturalmente anche in questo esempio è possibile individuare per il produttore (come del resto per il consumatore) una sequenza acquisizione (wait (spazio_disponibile) nel caso del produttore) - uso - rilascio della risorsa buffer, sennonché data la semplicità del caso questa sequenza è inglobata in una procedura unica di alto livello ('Invio' per il produttore, 'Ricezione' per il consumatore) [2].

Ora modifichiamo tale esempio con l'obbiettivo di generalizzarlo al caso di n produttori ed m consumatori. È abbastanza chiaro che i conflitti che possono nascere stavolta sono di due diverse specie: non solo tra i produttori e i consumatori così come succedeva nel caso semplificato (es.: uno qualunque dei produttori vuole produrre, ma non c'è neanche un buffer libero; esso deve quindi attendere che uno qualunque dei consumatori consumi, liberando così lo spazio di un buffer) ma anche per gli n produttori fra di loro, e per gli m consumatori fra di loro, per quanto concerne rispettivamente l'aggiornamento delle variabili coda e testa.

È evidente che, nella procedura di Invio, l'operazione 'coda : = (coda + 1)mod N', che non genera conflitti nel caso di un unico produttore, può crearne nel caso di più produttori, in quanto più di uno potrebbe chiamare nello stesso momento la procedura Invio. Ipotizzando che due processi oltrepassino contemporaneamente la WAIT su di uno stesso buffer (perché è l'unico previsto, o perché al momento è l'unico disponibile), essi finirebbero con il riempirlo entrambi e con l'incrementare la stessa variabile [3]. Questo è perciò un conflitto da risolvere, e analogamente si deve procedere nel caso dei consumatori.

Per i produttori useremo quindi una procedura come quella che segue.

Procedure deposito (x : messaggio) ;

begin

wait (spazio_disponibile) ;

wait (mutex1) ;

i = coda ;

coda = (coda+1) mod N ;

signal (mutex1) ;

vettore (i) : = x ;

signal (messaggio_disponibile) 

end ; [4]

Si noti che l'operazione di deposito messaggio nel buffer non è stata serializzata (se avessimo voluto farlo, avremmo dovuto metterla prima dell'istruzione signal(mutex1)). Ciò sarebbe inutile, giacché è perfettamente legittimo (anzi, è addirittura auspicabile) che un altro produttore si serva della coda prima ancora che il primo abbia effettuato il suo deposito. L'unica cosa da assicurare è il salvataggio della posizione in cui il primo processo deve depositare il proprio messaggio, prima di aggiornare il puntatore coda a beneficio di altri produttori, cosa che è stata fatta.

Dunque, bisogna stare attenti a non precludere il parallelismo del riempimento buffer da parte dei produttori. Questo sarebbe specialmente importante nel caso in cui l'operazione di scrittura nel buffer fosse piuttosto lenta. In tal caso tutti gli altri produttori rimarrebbero immobili per lungo tempo pur essendoci dei buffer liberi, e di conseguenza rimarrebbero immobili anche i consumatori che non avrebbero alcun buffer da consumare. A questo scopo, abbiamo portato il deposito al di fuori della regione critica e abbiamo fatto uso di una variabile temporanea, i.

La procedura per i consumatori è la duale di quella scritta per i produttori.

Procedure prelievo (var x : messaggio) ;

begin

wait (messaggio_disponibile) ;

wait (mutex2) ;

i = testa ;

testa = (testa+1) mod N ;

signal (mutex2) ;

x : =  vettore (i);

signal (spazio_disponibile)

end ; [5]

Le procedure proposte rappresentano la versione ottimizzata di quelle che si possono trovare alle pag. 86,87 dell'Ancilotti-Boari.

IL PROBLEMA DEL LETTORI SCRITTORI

Ad un certo buffer (o, più in generale, ad una certa struttura dati) possono accedere più processi, di cui alcuni solo lettori (possono prelevare il contenuto del buffer, ma non modificarlo) e altri scrittori (sono in grado di aggiornare il contenuto del buffer). In questo caso, la sincronizzazione stabilisce che un lettore non può accedere ad una struttura dati che uno scrittore sta modificando, e che quindi è in uno stato inconsistente. Similmente, uno scrittore non può accedere ad una struttura dati che un lettore sta leggendo, in quanto così facendo la renderebbe inconsistente per quest'ultimo. Quindi, esiste un vincolo di mutua esclusione fra lettori e scrittori nell'uso della risorsa.

Oltre a ciò, anche gli scrittori tra di loro si contendono la risorsa in mutua esclusione. Si deve cioè evitare che uno scrittore possa accedere alla struttura dati se questa è attualmente in possesso di un altro scrittore.

Non è invece necessario imporre la mutua esclusione tra i lettori, in quanto questi non modificano la struttura dati e quindi non possono renderla in alcun modo inconsistente. È cioè consentita la contemporaneità di accesso alla struttura dati da parte di due lettori.

Questo problema prevede varie soluzioni. Cominciamo ad esaminarne una, per la quale ipotizziamo che:

i lettori possono accedere alla risorsa anche se ci sono scrittori in attesa;

- uno scrittore può accedere alla risorsa solo se questa è libera.

Questa impostazione, che appare ottimale, presenta l'inconveniente di rendere possibile, in teoria, un'attesa infinita degli scrittori (STARVATION). Uno scrittore in attesa potrebbe essere perennemente sopravanzato da lettori, e quindi non trovare mai la risorsa libera. Tuttavia questa eventualità non si verifica quasi mai nella pratica, a causa di tutta una serie di fattori quali le velocità relative dei lettori rispetto agli scrittori, la frequenza delle operazioni e il tempo necessario ad eseguirle.

Presentiamo dunque le procedure risolutive, che saranno quattro, una di richiesta lettura, una di fine lettura (e fra queste due si interporrà l'operazione di lettura vera e propria), una di richiesta scrittura, una di fine scrittura (fra le quali si interporrà l'operazione di scrittura).

Var mutex : semaphore initial (1) ;

synch : semaphore initial (1) ;

num_lettori : integer initial (0) ;

Procedure Inizio_lettura ;

begin

WAIT (mutex) ;

num_lettori : = num_lettori + 1 ;  

if num_lettori = 1 then WAIT (synch) ;

SIGNAL (mutex) ;

end ;

Procedure Fine_lettura ;

begin

WAIT (mutex) ;

num_lettori : = num_lettori -1 ;

if num_lettori = 0 then SIGNAL (synch) ; 

SIGNAL (mutex) ;

end ;

Procedure Inizio_scrittura ;

begin

WAIT (synch) ;

end ;

Procedure Fine_scrittura ;

begin

SIGNAL (synch) ;

end ;

Cerchiamo di capire il funzionamento dei due semafori, mutex e synch. Ricordiamo che i lettori devono essere bloccati solo se è in corso un'operazione di scrittura. Synch ha appunto lo scopo di sincronizzare lettori e scrittori, esso serve cioè a bloccare uno scrittore nel caso che almeno un processo (lettore) stia leggendo, e a bloccare un lettore nel caso che un processo (scrittore) stia scrivendo.

Dovrebbe essere chiaro il significato dell'istruzione

if num_lettori = 1 then WAIT (synch)

Se num_lettori = 1, allora il processo corrente è l'unico lettore e si rende necessario azzerare il semaforo synch ('rosso') per bloccare gli scrittori. Se il numero dei lettori è superiore a 1, vuol dire che altri lettori stanno già leggendo la struttura dati e questo indica che gli scrittori sono stati già bloccati in precedenza.

Analogamente, nella procedura Fine_lettura il semaforo synch diventa 'verde' solo se il lettore in questione era l'unico che stava leggendo la struttura dati. Quindi synch non viene sbloccato ogni volta che un lettore esaurisce il suo lavoro, ma solo quando tutti i lettori hanno terminato. A questo punto, gli scrittori possono usare la risorsa.

Il meccanismo presentato genera una competizione fra i lettori nella gestione della variabile num_lettori, la quale per un corretto funzionamento deve essere manipolata (incrementata e decrementata) in mutua esclusione. Il semaforo mutex è stato inserito a questo fine.

Un lettore, in definitiva, si troverebbe ad attendere per due motivi: o perché c'è un processo scrittore che sta scrivendo, o perché un altro lettore ha chiamato inizio_lettura e quindi ha chiamato in causa la regione critica relativa alla variabile num_lettori (ma questo genere di attesa è senz'altro molto breve).

Con lo stesso semaforo synch riusciamo a gestire anche la competizione fra gli scrittori. Ricordiamo che uno scrittore può iniziare la scrittura solo se nessun processo (né lettore, né scrittore) sta usando la struttura dati. Le procedure di inizio e fine per gli scrittori consistono semplicemente in una WAIT e una SIGNAL sul semaforo synch. Si tratta infatti del caso banale cui si accennava all'inizio di questa lezione: gestione in mutua esclusione di una struttura dati condivisa e allocata staticamente.

La soluzione fin qui presentata è asimmetrica, in quanto palesemente sbilanciata verso i lettori. Mentre uno scrittore sta effettuando la propria operazione di scrittura, si può venire a creare una coda di processi in attesa. Può trattarsi di altri scrittori, i quali inequivocabilmente attenderanno il semaforo synch, o di lettori: il primo di essi in attesa sul semaforo synch, tutti gli altri sul semaforo mutex (che il primo lettore aveva reso 'rosso'). Se il primo processo a passare è un lettore, il suo passaggio provoca a valanga quello di tutti gli altri lettori. A questo punto, prima che uno scrittore sia in grado di impossessarsi della struttura dati, occorre attendere che tutti i lettori fino all'ultimo abbiano terminato le proprie operazioni di lettura.

Una soluzione più 'equa' è quella che presentiamo qui di seguito. Essa è progettata in modo che, se uno scrittore sta scrivendo e finisce il proprio compito, a subentrare sarà un altro scrittore e non un lettore.

Var mutex : semaphore initial (1) ;

mutex1 : semaphore initial (1) ;

mutex2 : semaphore initial (1) ;

synch : semaphore initial (1) ;

num_lettori : integer initial (0)

num_scrittori : integer initial (0) ;

procedure Inizio_scrittura ;

begin

WAIT (mutex2) ;

num_scrittori : = num_scrittori + 1 ;

if num_scrittori = 1 then WAIT (synch) ;

SIGNAL (mutex2) ;

WAIT (mutex1) ;

end ;

procedure Fine_scrittura ;

begin

SIGNAL (mutex1) ;

WAIT (mutex2) ;

num_scrittori : = num_scrittori - 1 ;

if num_scrittori = 0 then SIGNAL (synch) ;

SIGNAL (mutex2) ;

end ;

Le procedure relative alla lettura rimangono immutate.

Il semaforo synch realizza la mutua esclusione fra la 'categoria' lettori e la 'categoria' scrittori. Infatti, il primo di processo che esegue la WAIT (synch) impedisce ai processi dell'altra classe di accedere alla risorsa. Se questo processo è un lettore, altri lettori possono accedere, e solo quando tutti i lettori hanno terminato si può risvegliare un eventuale scrittore in attesa mediante la SIGNAL (synch). Se questo processo è uno scrittore, si ha un comportamento perfettamente simmetrico degli scrittori nei confronti dei lettori, con un'unica differenza: gli scrittori non possono operare contemporaneamente. La loro mutua esclusione è allora assicurata dal semaforo mutex1. Infine, il semaforo mutex2 serve per garantire la mutua esclusione sulla variabile num_scrittori.

L'inconveniente è che questa volta si può verificare un'attesa indefinita anche per i lettori, oltre che per gli scrittori. La prossima volta considereremo dunque il modo di scongiurare lo STARVATION (ma almeno qualcosa in questo senso si può già intuire: il segreto sta nel 'far passare' alternativamente un lettore ed uno scrittore).

Introduciamo un nuovo argomento. Con il meccanismo visto fino a questo momento, relativo alle procedure di acquisizione e rilascio, in effetti non è prevista nessuna vera politica di gestione della risorsa tramite scheduling, perché la signal per sua stessa natura si limita a fare passare il primo processo in attesa sul semaforo.

Naturalmente potremmo pensare di prelevare dalla coda dei processi ready un processo diverso dal primo, ma questo non servirebbe a risolvere il problema in senso generale. Il nocciolo della questione sta nel fatto che l'operazione di sblocco rimane legata alla primitiva signal e non alla particolare risorsa che stiamo gestendo. Sarebbe conveniente avere a disposizione per diverse risorse diverse politiche di sblocco.

Occorrerebbe perciò architettare un meccanismo con il quale, oltre alle procedure di acquisizione e rilascio, si implementa una politica di sblocco diversa da quella standard offerta della signal.

La soluzione al problema sta nell'introdurre un ulteriore, particolare meccanismo semaforico, detto del semaforo privato. Un semaforo si dice privato quando è visibile da più processi, ma uno solo di questi può eseguirvi la primitiva WAIT (mentre anche altri possono eseguirvi la SIGNAL). Quindi il semaforo è privato del processo A se solo A può eseguirvi una WAIT. Un'altra caratteristica peculiare è che il semaforo privato è sempre inizializzato a zero.

Un esempio di semaforo privato è il processo temporizzatore, nel quale ogni processo temporizzato esegue una WAIT sul suo proprio semaforo, mentre il temporizzatore è l'unico che può effettuare una SIGNAL su tutti i semafori.

Un altro esempio classico riguarda la gestione delle periferiche [6]. La routine pilota di una periferica lancia la propria periferica e poi ne impedisce l'accesso, eseguendo una WAIT su un semaforo privato. Successivamente la periferica stessa, per comunicare il fatto che l'operazione desiderata è stata eseguita, lancia un segnale di interruzione, il quale viene servito da un ramo della ISR. In tale ramo sarà presente semplicemente una SIGNAL: essa, pur non modificando il valore del semaforo (che deve rimanere sempre inizializzato a 0) ha l'effetto di sbloccare la periferica per successivi utilizzi.

---