Il costrutto 'monitor'

IL COSTRUTTO 'MONITOR'

Un OGGETTO è caratterizzato dal possedere:

- una struttura dati;

- dei metodi per accedere a tale struttura.

L'oggetto inoltre si trova volta per volta in un determinato STATO. Lo stato iniziale viene assegnato tramite una procedura di inizializzazione; l'oggetto poi transita di stato in stato per mezzo dei summenzionati metodi di accesso alla struttura dati.

Il Pascal Concorrente permette di definire un oggetto tramite il costrutto CLASS. Anche il Pascal standard, a partire dalla versione 6.0, permette di definire oggetti mediante il costrutto Unit, ma nel contesto di una programmazione rigidamente sequenziale (il Pascal standard non è difatti un linguaggio concorrente).

Il costrutto MONITOR rappresenta un'estensione del concetto di oggetto. I 'metodi' di accesso alla struttura dati, detti ENTRY, vengono eseguiti in mutua esclusione tra i vari processi che la richiedono. (Di un oggetto possono far parte inoltre altre procedure, di livello più basso rispetto alle entry, e che vengono da queste richiamate per svolgere determinate funzioni).

Questo costrutto dunque permette di incapsulare in un unico modulo una struttura dati comune a più processi e le procedure che agiscono su di essa. Nei fatti, MONITOR costituisce un ulteriore modo di creare un gestore di risorsa. Infatti, un gestore di risorsa è per definizione una struttura dati corredata di metodi di accesso che devono essere eseguiti in mutua esclusione tra più processi. Anche MONITOR consente di inizializzare la struttura dati al momento della sua istanziazione.

Ora presentiamo il costrutto MONITOR a livello di linguaggio di programmazione concorrente.

Type < nome del tipo > = MONITOR ;

< dichiarazione di variabili locali > ; /* rappresentano le variabili condivise

tra vari processi, il cui accesso deve essere regolamentato */

Procedure entry < nome > () ;

begin end ;

Procedure entry < nome > () ;

begin end ;

Procedure < nome > () ;

begin end ;

Procedure < nome > () ;

begin end ;

begin

< inizializzazione delle variabili locali >

end ;

Come si vede il costrutto MONITOR si presenta, da un punto di vista sintattico, identico al costrutto CLASS, e questo è naturale in quanto entrambi sono stati ideati per definire degli oggetti. Ci sono tuttavia delle differenze molto significative:

1) MONITOR permette di condividere l'oggetto tra più processi;

2) non appena un processo invoca una procedura ENTRY e riesce ad accedere al monitor, il compilatore deve garantire che questo sia l'unico processo attivo all'interno del monitor. Quindi se altri processi invocano una ENTRY del medesimo monitor vengono sospesi, e solo quando il processo che si trova nel monitor ne esce uno di essi può entrarvi. Tutto ciò comunque avviene in maniera trasparente rispetto al programmatore che usa il costrutto MONITOR;

3) se capita che un processo penetra nel monitor e, dopo aver valutato una condizione, si 'accorge' di non potere più andare avanti, il costrutto deve fare in modo che il processo ne esca e che vengano create le condizioni affinché altri possano entrare. Questa è una generalizzazione dell'istruzione AWAIT cui si è accennato nel denunciare gli inconvenienti della Regione critica condizionale (in effetti il costrutto MONITOR, essendo il più generale visto fin qui, deve necessariamente includere tutti i costrutti già studiati).

Cerchiamo ora di capire come viene ad essere implementata a livello di linguaggio quest'ultima prerogativa.

Si definisce una variabile appartenente ad un tipo 'speciale', nel senso che può essere utilizzato soltanto in quei linguaggi nei quali è previsto il costrutto MONITOR. Si tratta del tipo CONDITION:

Var x : CONDITION;

Su di una variabile di tipo condition possono essere fatte due operazioni, indicate con i nomi di x.wait e x.signal, che però non vanno confuse con le omonime primitive funzionanti sui semafori.

Effettuare una x.wait significa esprimere la volontà incondizionata di sospendersi. Ad ogni variabile di tipo condition è associata una coda, e un processo che esegue un'operazione di wait su di una variabile del genere si va a mettere deliberatamente in quella coda, liberando il monitor. A questo punto, solo l'esecuzione di una x.signal da parte di un altro processo potrà risvegliarlo. La x.signal non ha invece alcun effetto se viene eseguita quando non vi è alcun processo in attesa sulla variabile condition x.

Un processo si mette in attesa (mediante l'esecuzione di un x.signal) perché è risultata falsa una condizione di sincronizzazione dipendente sia dalle variabili locali del monitor che dalle variabili proprie del processo.

Poiché, d'altronde, la x.signal può essere eseguita solamente dall'interno di un monitor, sembrerebbe che in seguito a tale istruzione nel monitor debbano ripartire due processi contemporaneamente: P, che ha eseguito la x.signal, e Q, che ne è stato appena risvegliato. Ciò sarebbe contrario a quanto è stato detto poco fa nel punto 2). In realtà, il meccanismo garantisce che in quest'eventualità uno dei due processi viene automaticamente sospeso. Per la precisione, è il processo sbloccante ad essere arrestato. Questo perché, se fosse consentito invece a P di proseguire, quest'ultimo potrebbe modificare ancora una volta la condizione di sincronizzazione e compromettere una successiva ripartenza di Q.

Dunque, in seguito alla x.signal P viene sospeso e Q riparte. Tuttavia, il meccanismo fornisce anche una 'assicurazione' a Q, nel senso che non appena P uscirà del monitor (per averne completato l'uso, o perché di nuovo costretto a sospendersi) sarà Q a rientrarvi, e non altri processi che nel frattempo potrebbero essersi messi in attesa. Tutte queste operazioni vengono garantite in modo automatico dal costrutto MONITOR.

Il monitor resterà libero quando P e Q avranno entrambi terminato, o se si troveranno entrambi in uno stato di wait, o se uno dei due avrà terminato e l'altro si troverà in uno stato wait. È compito del programmatore garantire che quando il monitor viene liberato esso abbia una struttura dati consistente.

Facciamo ora un esempio pratico: la realizzazione di una regione critica mediante il costrutto MONITOR. Specificamente, mediante le procedure Richiesta e Rilascio i processi rispettivamente richiedono l'uso esclusivo di una risorsa e la rilasciano. Si ha:

type allocatore : MONITOR ;

var occupato: boolean ;

libero: condition

procedure Richiesta ;

begin

if occupato then libero.wait ;

occupato : = true ;

end ;

procedure Rilascio ;

begin

occupato : = false ;

libero.signal ;

end ;

begin

occupato : = false ;

end ;

Indicando ora con alloc una variabile di tipo allocatore (le variabili monitor vengono chiamate anche istanze):

Var alloc : allocatore ;

un generico processo effettuerà la richiesta e il successivo rilascio della risorsa secondo il semplice schema:

Process P_i ;

begin

alloc.Richiesta ;

< uso della risorsa > ;

alloc.Rilascio ;

end ;

Si comprende facilmente che questo esempio rappresenta la realizzazione di un semaforo binario. La procedura richiesta ne rappresenta la primitiva WAIT, e rilascio rappresenta la SIGNAL. La coda del semaforo coincide con la coda della variabile libero di tipo condition, mentre la variabile semaforo è rappresentata dalla booleana occupato.

La condizione di sincronizzazione che, se non verificata, provoca l'autosospensione di un processo richiedente è occupato = false.

Questo esempio illustra le reali differenze fra le primitive wait & signal operanti sui semafori e le omonime utilizzate all'interno dei monitor. In questo secondo caso, wait e signal hanno unicamente lo scopo di sospendere e riattivare i processi, e infatti il test sullo stato della risorsa controllata viene realizzato al di fuori di tali primitive

REALIZZAZIONE DEL COSTRUTTO MONITOR

La condizione di mutua esclusione tra le procedure può essere ottenuta associando ad ogni istanza del monitor un semaforo mutex inizializzato ad 1. Dunque la richiesta da parte di un processo di usare una procedura del monitor equivale all'esecuzione di una WAIT (mutex).

Quando un processo sospeso viene riattivato, deve essere sempre sospeso il processo che ha eseguito la signal sulla variabile condizione. Per ottenere questo risultato, si associa ad ogni monitor un secondo semaforo urgent, inizializzato a 0, sul quale il processo 'sbloccante' si arresta tramite una WAIT (urgent). Prima di abbandonare il monitor è necessario verificare che nessun processo sia in coda a tale semaforo.

Indicando con urgentcount un contatore, inizializzato a 0, del numero di processi sospesi sul semaforo urgent, l'uscita da una procedura del monitor viene codificata così:

if urgentcount > 0 then SIGNAL (urgent) else SIGNAL (mutex) ;

Veniamo adesso alla variabile di tipo condition (la chiamiamo cond). Ad essa associamo un semaforo condsem, inizializzato a 0, sul quale un processo può sospendersi tramite una WAIT (condsem), e un contatore condcount, inizializzato a 0, per tener conto dei processi sospesi sul semaforo condsem.

L'operazione COND.WAIT può essere realizzata così:

condcount : = condcount + 1

if urgentcount > 0 then SIGNAL (urgent) else SIGNAL (mutex) ;

WAIT (condsem) ;

condcount : = condcount - 1 ;

Mentre per l'operazione COND.SIGNAL è:

urgentcount : = urgentcount + 1 ;

if condcount > 0 then

begin

SIGNAL (condsem) ;

WAIT (urgent) ;

end ;

urgentcount : = urgentcount - 1 ;

Imponiamo ora una condizione: cioè che l'operazione COND.SIGNAL sia eseguita sempre come ultima operazione di ogni procedura. Questa non è una condizione eccessivamente restrittiva, e ha il vantaggio di semplificare le cose; infatti non è necessario introdurre il semaforo urgent e il contatore urgentcount. La COND.WAIT diviene:

condcount : = condcount + 1 ;

SIGNAL (mutex) ;

WAIT (condsem) ;

condcount : = condcount - 1 ;

E la COND.SIGNAL:

if condcount > 0 then SIGNAL (condsem) else SIGNAL (mutex) ;

In conclusione, possiamo dire che il costrutto MONITOR è un'astrazione che permette al programmatore di concentrarsi sulle politiche di gestione delle risorse senza andare ad impantanarsi nelle code e nei meccanismi semaforici di basso livello. Anche se si usa un linguaggio che non mette a disposizione il costrutto MONITOR, conviene ragionare in termini di tale costrutto e successivamente effettuare una traduzione. Del resto è consigliabile creare una volta per tutte le necessarie procedure (COND.WAIT etc.), in modo che quando queste si renderanno necessarie sarà sufficiente richiamarle.

La volta scorsa abbiamo introdotto il costrutto MONITOR e ne abbiamo visto la traduzione in termini di semafori e una semplice applicazione.

I processi che si bloccano su di una variabile di tipi condition vengono gestiti secondo l'usuale disciplina FIFO. Quindi l'esecuzione di una istruzione del tipo x.signal sortisce il risveglio del processo che è in attesa da più tempo. In alcuni casi tale politica, che impedisce il problema dell'attesa infinita, risulta però inadeguata, poiché sarebbe preferibile usufruire di una differente gestione prioritaria dei processi. Questo può essere ottenuto in due modi:

- mediante una signal che invece di risvegliare il processo in testa alla coda, risveglia il processo che, secondo i criteri che sono stati fissati, risulta avere la maggiore priorità.

- mediante una wait condizionale, che riceve in ingresso un parametro intero p, di cui essa si serve per inserire il processo bloccato al posto p-esimo della coda. In questo modo la signal classica sbloccherebbe automaticamente il processo più prioritario.

Nel seguito supporremo di usare questo tipo di wait, accettando il rischio (comunque molto improbabile) di provocare un fenomeno di attesa infinita.

Esaminiamo un ulteriore, interessante problema che può essere risolto agevolmente mediante i monitor.

GESTIONE DI UN DISCO A TESTE MOBILI

Ricordiamo che su di un disco viene letto o scritto un blocco fisico per volta, di solito un settore. L'indirizzo di un blocco fisico di un disco, sia esso rigido o floppy, è composto di tre elementi: indirizzo del cilindro, traccia e settore. Ci poniamo l'obbiettivo di minimizzare i tempi di attesa.

In linea di massima, si potrebbe provare ad ottimizzare il tempo di ricerca di tutti e tre questi componenti Tuttavia, il tempo di selezione della traccia è trascurabile rispetto agli altri due, poiché esso è di natura elettronica, mentre i tempi di selezione di cilindro e settore sono di natura meccanica. In particolare, la selezione del cilindro viene effettuata tramite uno spostamento radiale del pettine (= l'insieme delle testine) e il tempo necessario a tale selezione si chiama TEMPO DI SEEK. Ovviamente, se il disco è dotato di testine fisse invece che mobili non ha senso parlare di tempo di seek. Per selezionare il settore occorre aspettare che la giusta zona del disco, ruotando, passi sotto alla testina e il relativo tempo di attesa prende il nome di TEMPO DI LATENZA.

Data l'irrilevanza del tempo di selezione di una traccia, possiamo considerare valida la relazione:

TEMPO ACCESSO DISCO = TEMPO DI SEEK + TEMPO DI LATENZA

Supponiamo di voler ottimizzare soltanto rispetto al tempo di seek. Ciò significa minimizzare lo spostamento radiale del pettine durante i successivi accessi al disco.

I due algoritmi fondamentali di scheduling possono essere spiegati in questo modo:

- ogni volta che deve servire la richiesta da parte di un processo relativa a informazioni contenute sul disco, il SO tiene conto della posizione attuale del pettine e tra tutte le richieste pendenti accontenta quella che si riferisce alla traccia più vicina, a prescindere dall'attuale direzione del pettine (verso l'interno o verso l'esterno delle superfici), e cioè a prescindere dalla direzione di quelli che sono stati gli spostamenti precedenti.

DISCO MAGNETICO VISTO DALL'ALTO (schema)

Spostamento radiale del pettine

Tracce

- il SO serve la richiesta più vicina rispetto alla posizione attuale, ma solo nella direzione attuale del pettine. Ad esempio, nel caso seguente (il grafico è di facile comprensione):

richiesta 1                      richiesta 2

posizione attuale del pettine

viene servita prima la richiesta 2, poiché la richiesta 1, più vicina, si trova nella direzione opposta rispetto a quella attualmente seguita dal pettine.

Noi faremo riferimento a questo seconda strategia. Per convinzione il movimento del pettine dal cilindro più esterno verso quello più interno prende il nome di salita e l'altro spostamento è detto discesa. L'algoritmo che ora consideriamo è detto ALGORITMO ASCENSORE. Si pensi infatti ad un ascensore 'a prenotazione', tipo quelli installati negli edifici della Federico II. Quando l'ascensore è in salita, esso serve tutti gli utenti che desiderano salire, raccogliendoli man mano che sale per i vari piani. Nella successiva fase di discesa l'ascensore servirà in modo analogo tutti coloro che desiderano scendere. L'unica cosa che differenzia il nostro algoritmo dal comportamento di un ascensore del genere è che, se viene fatta una richiesta relativa ad una traccia appena servita, questa non sarà presa in considerazione subito, ma soltanto dopo il successivo cambiamento di direzione del pettine. Questo per evitare che si verifichi uno starvation dovuto a continue richieste relative ad una stessa traccia.

Per realizzare questa strategia di gestione del disco utilizzeremo il costrutto MONITOR. Il nostro monitor conterrà una procedura di richiesta ed una di rilascio. Così, un processo che voglia scrivere qualcosa sul disco dovrà richiamare la procedura di richiesta, specificando la posizione in cui intende scrivere, e quando il monitor lo riterrà opportuno gli consentirà di eseguire il driver del disco (il programma che rende possibile il passaggio delle informazioni). Fatto ciò, il processo effettuerà la procedura di rilascio.

Le variabili locali del monitor comprendono:

- posizione : la posizione corrente del pettine, ottenuta come numero della traccia su cui il pettine si trova;

- direzione : la direzione del movimento;

- occupato : lo stato attuale del disco.

Inoltre, definiamo due variabili condition per la sospensione dei processi, direzione_su e direzione_giù, ed una funzione, cond.queue, che dice se ci sono processi sospesi nella coda associata alla variabile cond.

Type traccia = 0..N ;

type movimento_braccio = MONITOR ;

var posizione: traccia ;

direzione: (giù, su) ;

occupato: boolean ;

direzione_giù, direzione_su: condition;

Procedure entry Richiesta (dest: traccia) ;

begin

if occupato then

if posizione < dest or (posizione = dest and direzione = giù) then

direzione_su.wait (dest) /* il processo si mette in attesa sulla salita;

esso va a occupare la posizione dest

nella coda dei processi sospesi sulla salita */

else

direzione_giù.wait (N - dest) ; /* il processo si pone in attesa sulla discesa */

occupato : = true ;

posizione : = dest ;

end ;

Procedure entry Rilascio ;

begin

occupato : = false ;

if direzione = su then

if direzione_su.queue then /* la coda dei processi sospesi in salita

non è vuota */

direzione_su.signal ; /* liberato un processo in attesa sulla salita */

else

begin

direzione : = giù ; /* non ci sono processi in attesa sulla salita;

inversione del senso di marcia */

direzione_giù.signal ; /* liberato un processo in attesa sulla discesa */

end ;

else /* direzione = giù */

if direzione_giù.queue then

direzione_giù.signal ;

else

begin

direzione : = su ; /* inversione del senso di marcia */

direzione_su.signal

end ;

end ;

begin

posizione : = 0 ; /* si parte dalla traccia più esterna */

direzione : = su ;

occupato : = false

end ;

Osservazioni:

- se la variabile occupato risulta vera, significa che qualche processo sta eseguendo il driver. Il driver rappresenta in questo caso la procedura d'uso della risorsa disco, e ci si potrebbe domandare perché mai non è stato inserito anch'esso come parte del monitor. La risposta è che se fosse stato incluso anche il driver, avremmo serializzato la richiesta da parte di un processo con l'uso da parte di un altro, e questo sarebbe stato un appesantimento non necessario.

- il parametro dest indica la priorità del processo sospeso. Si ricordi che abbiamo adottato una diversa versione della wait su variabili condition, quella che è in grado di gestire la priorità dei processi, servendosi in questo caso dell'indice dest.

- la variabile posizione costituisce per il processo che ha effettuato la richiesta la posizione in cui sta leggendo o scrivendo il processo che prima di lui ha ottenuto l'utilizzo del driver, nel caso in cui la risorsa risulti occupata.

COSTRUTTO MONITOR: PROBLEMA LETTORI-SCRITTORI

Riconsideriamo il problema dei lettori scrittori. Ricordiamo che la politica di assegnazione ottimale della risorsa (pag. 80) stabilisce che un nuovo lettore non possa acquisire la risorsa se c'è uno scrittore in attesa, e che tutti i lettori sospesi al termina di una scrittura abbiano la priorità sul successivo scrittore.

Indichiamo allora con:

- num_lettori : numero dei processi lettori attivi sulla risorsa;

- occupato : variabile booleana che vale true se la risorsa è occupata da uno scrittore;

- ok_lettura, ok_scrittura : variabili condition su cui si sospendono rispettivamente lettori e scrittori.

Il codice è:

Type lettori_scrittori = MONITOR ;

var num_lettori : integer ;

occupato : boolean ;

ok_lettura, ok_scrittura : condition ;

Procedure entry Inizio_lettura ;

begin

if occupato or ok_scrittura.queue then

ok_lettura.wait ;

num_lettori : = num_lettori + 1 ;

ok_lettura.signal ;

end ;

Quando un lettore viene sbloccato (a causa dell'uscita di uno scrittore), grazie all'istruzione ok_lettura.signal esso sblocca a sua volta un altro lettore. Lo stesso farà quest'ultimo con un altro lettore in attesa, e così via. In questo modo si realizza la 'liberazione a cascata' di tutti gli eventuali lettori in attesa. Ricordiamo che detta istruzione non ha effetto se non ci sono processi da sbloccare. Vediamo ora la procedure di fine lettura.

Procedure entry Fine_lettura ;

begin

num_lettori : = num_lettori - 1 ;

if num_lettori = 0 then ok_scrittura.signal ;

end ;

Quando tutti i processi lettori sono usciti, è necessario e sufficiente offrirsi di liberare un eventuale scrittore bloccato. Se non esiste alcuno scrittore in attesa, sicuramente non esisteranno neanche lettori in attesa.

Procedure entry Inizio_scrittura ;

begin

if num_lettori <> 0 or occupato then

ok_scrittura.wait ;

occupato : = true ;

end ;

Procedure entry Fine_scrittura ;

begin

occupato : = false ;

if ok_lettura.queue then

ok.lettura.signal 

else ok_scrittura.signal ;

end ;

begin

num_lettori : = 0 ;

occupato : = false ;

end ;

CONSIDERAZIONI CONCLUSIVE

Nulla impedisce, in linea di principio, di innestare i monitor. È possibile quindi che all'interno di una procedura entry di un monitor venga interpellata una procedura entry facente parte di un secondo monitor.

Questo comunque va evitato, poiché genera dei grossi problemi di programmazione; in particolare perché mette in pericolo la consistenza della struttura dati. Se un processo effettua l'operazione appena menzionata, esso potrebbe rimanere bloccato sul secondo monitor, e così facendo rimarrebbe automaticamente bloccato anche il monitor più esterno, impedendo ad altri processi di accedervi.

Con questa puntualizzazione, abbiamo terminato l'analisi della competizione e della cooperazione tramite semafori nel modello a MEMORIA COMUNE. Ora passeremo ad analizzare le procedure che consentono la cooperazione nel modello a SCAMBIO DI MESSAGGI (ricordiamo che il problema della competizione non si presenta in questo modello).

INTERAZIONE TRA I PROCESSI

NEL MODELLO A SCAMBIO DI MESSAGGI

Ricordiamo che in questo modello ciascun processo dispone della propria memoria locale, evolve in un ambiente proprio che non è comune ad altri processi. Ne segue che non è possibile che i processi entrino in competizioni su strutture dati condivise. Ne segue anche però che se due processi devono interagire, non possono più farlo tramite la memoria comune (per il semplice motivo che non esiste una memoria comune), ma possono farlo solo scambiandosi dei messaggi tramite il kernel del SO. Ogni volta che un processo desidera inviare un messaggio ad un altro processo, e ogni volta che un processo desidera ricevere un processo, essi devono fare una richiesta al kernel.

Un linguaggio di programmazione concorrente progettato per una macchina a memoria locale deve mettere a disposizione delle primitive per lo scambio di messaggi. Ancora una volta, generalmente le primitive in questione sono soltanto due:

- una primitiva di invio send;

- una primitiva di ricezione receive.

Esisteranno una send a livello di linguaggio concorrente ed una send a livello di kernel; la prima send sarà più potente e più sofisticata, in quanto realizzata tramite opportuno uso di più send del livello kernel. Ugualmente dicasi per la receive.

Questo modello risulta particolarmente indicato per i sistemi distribuiti, più comunemente detti reti di calcolatori, ma è spesso usato anche con riferimento a macchine singole.

Le risorse sono sempre private rispetto a i singoli processi, e quindi se la natura del contesto impone che siano previste delle risorse comuni, esse potranno essere tali solo a livello logico, e non fisico. Nei fatti una risorsa appartiene ad un solo processo che nella fattispecie rappresenta il suo gestore. Il processo gestore di risorsa riceve, a mezzo del kernel, dei messaggi di richiesta, opera sulla risorsa di cui è proprietario e fornisce eventuali risposte. Quindi, mentre nel modello a memoria globale il gestore era una risorsa allocata staticamente e condivisa tra più processi, nel modello a memoria locale il gestore è un processo (ha quindi un carattere 'attivo', anziché 'passivo'), e poiché la sua ragione di essere è unicamente quella di servire le richieste di utilizzo da parte di altri processi esso viene detto processo servitore.

Cominciamo ora a prendere in considerazione alcuni tipi di primitive send & receive a livello di linguaggio. Al momento opportuno vedremo quali di esse corrispondono alla omonime primitive a livello kernel.

Le varie primitive send, receive si distinguono fra di loro per due motivi fondamentali:

- il modo in cui i meccanismi di trasmissione e ricezione si sincronizzano tra di loro utilizzando queste due primitive;

- il modo in cui vengono designati il processo destinatario della send ed il processo mittente della receive.

Queste differenziazioni d'altra parte possono riguardare solo i linguaggi, perché a livello kernel mittente & destinatario non possono che essere individuati mediante indirizzi di memoria (e si noti che possono essere indirizzi appartenenti all'area di memoria privata del mittente, all'area di memoria privata del destinatario o all'area di memoria propria del kernel); quanto alla sincronizzazione, per il kernel esisteranno solo i due tipi di sincronizzazioni più elementari possibili.

SINCRONIZZAZIONE TRA PROCESSI COMUNICANTI

Una comunicazione completa tra due processi può avvenire solo se vengono effettuate un send da parte del un mittente ed una receive da parte del destinatario.

La sincronizzazione delle operazioni in gioco in un simile fenomeno di comunicazione è legata alla semantica delle primitive. Si può distinguere come segue:

a) send asincrona;

b) send sincrona;

c) send di tipo chiamata di procedura remota;

d) receive bloccante;

e) receive non bloccante.

Passiamo ad esaminare nel dettaglio le cinque alternative.

A) SEND ASINCRONA Questo è il solo tipo di send messo a disposizione dai kernel dei SO, e di conseguenza tutte le altre si ottengono a partire da questa, con lo scopo di ottenere una più sofisticata tempificazione.

La sua caratteristica saliente è questa: il mittente continua nella propria esecuzione dopo avere inviato un messaggio.

La send effettuata dal mittente consiste in una chiamata al supervisore. Con la send vengono specificati due parametri: l'indirizzo del buffer della propria area memoria il cui contenuto deve essere inviato al destinatario, e l'identificatore del destinatario. A questo punto, il kernel accede all'area di memoria del mittente, copia il buffer indicato in un buffer della propria area dati, e restituisce il controllo al mittente. Il mittente riscontra che il proprio buffer è stato liberato, e dal suo punto di vista questo è il segno che l'operazione send è conclusa. Di conseguenza esso ridiventa running sul proprio processore virtuale [1].

Questa versione della send si dice asincrona perché in essa non è presente alcuna relazione tra stato del mittente e stato del destinatario; il mittente invia il suo messaggio senza preoccuparsi dello stato del destinatario; a tempo debito, il destinatario riceverà il messaggio senza interessarsi dello stato attuale del mittente.

Il suo vantaggio evidente è che essa permette il massimo del parallelismo, in quanto il mittente, una volta ricevuto indietro il controllo del proprio processore da parte del SO, è libero di proseguire nelle sue operazioni e non deve stare ad aspettare che il destinatario prelevi il messaggio. Tuttavia, questa send presenta anche molti svantaggi. Uno è che, trattandosi di un meccanismo di basso livello, cercare di realizzare schemi più complessi a partire da esso risulterebbe molto laborioso. Inoltre, almeno in linea teorica, il kernel dovrebbe avere un buffer illimitato, dato che, potenzialmente, il mittente potrebbe fare infinite send senza attendere alcuna receive.

B) SEND SINCRONA I parametri che devono essere specificati sono gli stessi del caso precedente.

Inoltre anche in questo caso quando il mittente esegue una send viene effettuata una system call e interviene il kernel del SO. A questo punto, si presentano due alternative:

1) il destinatario ha già eseguito una receive;

2) il destinatario non ha ancora eseguito la receive.

Nel secondo caso, il mittente viene sospeso finché il destinatario non effettua la receive. Dato che il mittente è sospeso, esso si trova 'con le mani legate' rispetto alla possibilità di inviare ulteriori messaggi e quindi non c'è necessità di svuotare il contenuto del buffer. Quando finalmente il destinatario fa la receive, il kernel copia il messaggio dall'area di memoria indicata nella send a quella indicata nella receive [2], e entrambi i processi ridiventano running ciascuno sul proprio processore virtuale.

Nel primo caso, invece, il mittente viene temporaneamente sospeso, ma poiché non si presenta nessun ostacolo l'operazione viene portata rapidamente a compimento con la liberazione dei due processi.

Succede comunque che quando il mittente ridiventa ready lo ridiventa sicuramente anche il destinatario, e questa doppia, simultanea transizione di stato è contrassegnata dall'avvenuto passaggio dell'informazione dall'area mittente all'area destinatario. La sincronizzazione è associata al fatto che i dati vengano fisicamente trasferiti fra le due aree, e quindi la proposizione 'messaggio ricevuto' esprime di fatto lo stato del processo mittente.

Ciò comporta anche che, diversamente dal caso precedente, il destinatario ha conoscenza dello stato del mittente, e inoltre non si pone il problema della lunghezza del buffer del kernel. Lo svantaggio più evidente è costituito dalla perdita di parallelismo, poiché il mittente deve stare ad aspettare che il destinatario abbia ricevuto il messaggio prima di riprendere il proprio lavoro.

La send sincrona può essere realizzata soltanto a partire da send asincrone e come tale è propria di linguaggi ad alto livello, e non dei kernel dei SO.

Riserviamoci di esaminare la prossima volta la send tipo chiamata di procedura.

D) RECEIVE BLOCCANTE. Anche la receive è una system call ed è caratterizzata dai seguenti parametri:

Receive (indirizzo del buffer del destinatario in cui il messaggio deve essere memorizzato; nome del mittente oppure della mail box).

Poiché più mittenti possono voler inviare messaggi ad uno stesso destinatario, può essere provveduto uno spazio apposito nell'area di memoria del kernel, che è la mail box del destinatario in questione, nella quale i messaggi in arrivo vengono sistemati in una coda.

Il destinatario che esegue una receive bloccante rimane bloccato fino a che non gli viene inviato un messaggio

Vediamo cosa succede se si accoppiano una receive bloccante con una send asincrona. Se viene eseguita prima la send asincrona, il messaggio viene depositato nel buffer del kernel; quando successivamente il destinatario eseguirà la receive non rimarrà bloccato, poiché risulterà effettivamente disponibile un messaggio. Se invece è la receive bloccante ad essere eseguita per prima, il destinatario rimarrà bloccato fino a che il mittente non effettuerà una send. A questo punto entrambi i processi verranno sbloccati. Avviene in effetti (ma solo in tale eventualità) la stessa cosa che accade per una send sincrona: il messaggio viene copiato direttamente dal buffer del mittente a quello del destinatario.

Se invece accoppiamo una receive bloccante con una send sincrona, la send causerà il blocco del mittente se eseguita prima della receive, mentre non lo causerà se eseguita dopo. Si noti tuttavia che in entrambi i casi i processi ripartono contemporaneamente, divenendo running si rispettivi processori virtuali.

E) RECEIVE NON BLOCCANTE. Quando viene eseguita, il ricevente non viene bloccato anche se non c'è nessun messaggio disponibile.

Questa receive serve per realizzare il cosiddetto POLLING. Supponiamo che un processo abbia la possibilità di attingere da più mailbox. In tal caso è evidente che deve essere usata una receive non bloccante, poiché non avrebbe senso che il destinatario rimanesse bloccato in attesa su di una mailbox quando in qualche altra potrebbe arrivare (o essere già arrivato) un messaggio.

Per esigenze di programmazione, però, potrebbe essere necessario fare in modo che un processo ricevente si blocchi in seguito ad una Receive e fino a quando non giunge un messaggio; per rendere possibile questa situazione nei SO che implementano la receive non bloccante, si fa così: il processo effettua la receive e se il risultato è negativo si mette in attesa su di un SEMAFORO TEMPORALE (un semaforo che automaticamente 'diventa verde' dopo un certo intervallo di tempo). Quando viene risvegliato, esso riesegue la receive non bloccante. La receive restituirà ogni volta un parametro di ritorno che dice se l'area buffer interpellata è piena o vuota.

Una receive non bloccante può essere accoppiata, come del resto accadeva per la bloccante, sia con una send asincrona che con una send sincrona. In questo secondo caso, se si esegue una receive quando non c'è nessun processo in attesa sulla send, il ricevente prosegue la sua esecuzione. Quando in seguito il mittente chiama la send, esso si blocca; non si tiene conto cioè della receive precedente, come se quest'ultima non fosse stata proprio eseguita, in quanto l'unica cosa che conta è se in questo momento il buffer del destinatario è disponibile a ricevere messaggi.

Ancora sulla SEND SINCRONA. Esclusivamente con riferimento a sistemi distribuiti su reti locali, quella che abbiamo chiamato send sincrona è ribattezzata send bloccante e viene soggetta alla seguente distinzione:

- send bloccante semplice;

- send bloccante sincrona.

Supponiamo di avere a che fare con una rete di elaboratori elettronici. Se avviene uno scambio tra un mittente ed un destinatario all'interno di una stessa macchina, e quindi nell'ambito di uno stesso SO, tutto procede come per la send sincrona descritta prima.

Se i processi mittente e destinatario si trovano invece su macchine differenti, la send provoca comunque un blocco del mittente, ma per un diverso motivo. Il mittente viene bloccato non fino a quando il messaggio viene copiato nel buffer del destinatario, ma fino a quando il messaggio viene consegnato ad una particolare routine del kernel, detta TRASMETTITORE, incaricata di provvedere alla trasmissione delle informazioni sulla rete.

In questo caso, dunque, bisogna aspettare semplicemente che sia libero il processo trasmettitore. Il messaggio viene allora prelevato dall'area di memoria del mittente e affidato al trasmettitore; il mittente viene immediatamente sbloccato.

Questa send è bloccante, ma semplice e non sincrona, poiché non è richiesto che il mittente attenda l'avvenuta ricezione del messaggio. D'altra parte ciò sarebbe non poco complicato; premesso che sulle due macchine risiederanno due diversi SO ciascuno con il proprio kernel, il mittente dovrebbe effettuare la sua send e mettersi in attesa; il kernel dovrebbe aspettare che il trasmettitore sia libero e trasmettere mediante esso il messaggio al kernel della macchina su cui c'è il processo destinatario. Questo secondo kernel dovrebbe a sua volta aspettare la receive da parte del destinatario; a questo punto avverrebbe la consegna del messaggio, e in più dovrebbe essere inviato un messaggio al kernel del processo mittente, che potrà essere così sbloccato.

LA SEND TIPO 'CHIAMATA A PROCEDURA REMOTA'

Prendiamo in esame il terzo ed ultimo tipo di send: la CHIAMATA A PROCEDURA REMOTA, una send a livello di linguaggio, detta anche rendez vous esteso.

In questo caso il mittente non soltanto rimane in attesa che il destinatario riceva il messaggio, ma aspetta anche un messaggio di risposta dal destinatario. In altre parole, il mittente (che viene detto anche cliente) chiede un servizio al destinatario(servitore): gli passa dei parametri con i quali specifica il tipo di servizio desiderato, e dei parametri di ritorno destinati a contenere i risultati. I risultati del servizio richiesto possono consistere in una semplice risposta, la quale dice in sostanza se il servizio è stato realizzato o meno, oppure possono essere delle informazioni più articolate.

In generale, dunque, i tempi di attesa saranno più lunghi rispetto a quelli della send sincrona, se è vero che il mittente deve rimanere bloccato per tutto il tempo che il ricevente impiega ad eseguire il servizio richiesto e a restituire i risultati.

A basso livello, una simile send può essere realizzata mediante una send asincrona e una receive bloccante, entrambe eseguite all'interno del cliente. In questo modo il cliente spedisce il messaggio senza bloccarsi in fase di invio, e poi si mette in attesa sulla ricezione del risultato. La 'chiamata a procedura remota', un costrutto proprio dei linguaggi di programmazione concorrente ad alto livello, ha la stessa struttura di una normale chiamata a sottoprogramma, cioè:

Call Pippo (parametri) Send Pippo (parametri)

La similitudine con le chiamate a sottoprogramma arriva al punto che il cliente che utilizza questo costrutto desidera avere completa visibilità del servizio richiesto, usufruendone come se il servitore fosse un suo sottoprogramma, mentre ovviamente esso 'gira' in un differente contesto se non addirittura su di un'altra macchina. Per realizzare questa trasparenza si pone un problema di passaggio dei parametri.

Se ad esempio il cliente passa dei parametri di ingresso per indirizzo, questi devono essere dapprima trasformati in dati veri e propri dal kernel, e poi spediti. Si inizia con una fase di 'impacchettamento' del messaggio da parte del cliente, che memorizza i parametri di scambio inopportune locazione della propria area di memoria privata. Il cliente esegue quindi la sequenza send asincrona - receive bloccante. Ricevuto il segnale di 'ok' da parte del servitore, il compilatore concorrente ricostruisce a partire dai parametri di scambio il messaggio da inviare a quest'ultimo mediante un'operazione di 'spacchettamento' a suo favore.

Corrispondentemente, il servitore prevederà nell'ordine le seguenti operazioni:

- una receive bloccante (questa è sempre la prima istruzione del servitore, e quindi è implicito che in questo caso il destinatario resta immobile fino a che qualcuno non richiede un suo servizio);

- uno 'spacchettamento' del messaggio in arrivo da parte del kernel;

- l'esecuzione del servizio;

- un 'rimpacchettamento' del risultato, nelle locazione di memoria dell'area privata del servitore;

- una send asincrona.

PRODUTTORI CONSUMATORI

NEL MODELLO A SCAMBIO DEI MESSAGGI

Risolveremo questo problema mediante i costrutti send asincrona e receive bloccante.

In questo caso, abbiamo bisogno di un PROCESSO BUFFER, dedicato ad assolvere quelle funzioni che nel modello a memoria comune venivano svolte dal buffer di memoria condiviso tra produttori e consumatori. Ciò è necessario, perché nel modello a memoria locale non è più possibile parlare di risorse condivise (per lo meno non nell'accezione a noi nota) e quindi non si può fare ricorso ad un buffer di memoria condiviso. Si deve allora prendere un buffer di memoria e renderlo 'privato' ad un processo, che rappresenterà il gestore di tale risorsa; produttori & consumatori allora 'dialogheranno' con tale gestore per poter effettuare lo scambio dei messaggi. Lo schema di riferimento è quello riportato nella pagina seguente.

Le primitive usate sono:

SEND (mes, proc)

dove mes = variabile 'messaggio inviato', appartenente ad un certo tipo che indichiamo con T, e proc = nome del processo destinatario, appartenete al tipo che conosciamo col nome di process;

Proc : = RECEIVE (mes)

Mes sarà naturalmente una variabile dello stesso tipo. Si noti inoltre che la primitiva RECEIVE restituisce come parametro il nome del processo mittente e questo nome viene assegnato alla variabile proc (informazione a beneficio del destinatario).

Si suppone che ogni processo in grado di ricevere dei messaggi possegga una coda di messaggi a lui inviati che viene gestita dal kernel (queste code non vanno confuse con le code locali del processo buffer, di cui poi si dirà). La SEND, ogni volta che viene chiamata, inserisce il messaggio mes nella coda di ingresso del processo proc e termina. RECEIVE analizza la coda di ingresso del processo che la esegue: se è vuota, il processo viene bloccato, altrimenti viene estratto il primo messaggio e il suo valore viene assegnato alla variabile mes.

produttore 1                                                                                                                     consumatore 1

PRONTO