Modello a Memoria Globale: Interazioni tra processi

Modello a Memoria Globale: Interazioni tra processi

Nel modello a memoria globale le interazioni tra processi possono essere la cooperazione (tramite scambio di informazioni attraverso risorse comuni) e la competizione (nell'accesso a risorse ad uso esclusivo o a risorse comuni con un numero massimo di utilizzatori minore del numero di richiedenti). Il gestore di risorsa in questo modello è sempre una risorsa gestore (in realtà potrebbe in teoria essere anche un processo gestore che coopera coi processi in competizione, ma poichè tale cooperazione richiede a sua volta un processo supplementare di coordinamento, nella pratica nel modello a memoria globale il gestore è convenientemente sempre una risorsa) e su di essa solitamente agiscono solo due procedure, una per la richiesta di acquisizione - se possibile - della risorsa e l'altra per il suo rilascio affinchè altri processi possano usarla.

Semaforo

Una tipica risorsa gestore messa a disposizione dal SO nel modello a memoria globale è il Semaforo, costituito da una singola variabile booleana (come il primo modello di semaforo ideato da Dijkstra) o intera (con un range massimo, si parla di semaforo generalizzato) e corredato da due procedure di acquisizione e rilascio, Wait e Signal, così schematizzabili

var s : semaforo;

procedure wait(s : semaforo);

begin Wait attende che il semaforo diventi "verde" (ovvero positivo)

repeat dopodichè lo decrementa, eventualmente rendendolo "rosso"

until s>0; per almeno un altro processo diverso da sè

s:= s - 1;

end;

procedure signal(s : semaforo);

begin Signal incrementa il semaforo rendendolo sempre "verde"

s:= s + 1; per almeno un altro preocesso eventualmente in attesa del

end; semaforo stesso (si parla di "risveglio" di un processo)

Per come è definito, attraverso un semaforo booleano (o binario) può passare un solo processo per volta, mentre attraverso un semaforo generalizzato passano N processi per volta. Le operazioni sopra descritte sono da considerarsi atomiche (non interrompibili dal SO) ed è evidente che delle due la procedura più critica è la Wait, visto che nella sua forma generale prevede un esame continuo del semaforo con evidente spreco di tempo:  tali procedure, in particolare la Wait, vengono implementate in modo diverso secondo necessità e contesto. In un sistema multiprocessore la Wait può essere realizzata facendo uso di una opportuna procedura atomica da chiamare in loop (effettuato a livello codice macchina con un'istruzione di salto JUMP dopo una serie di NOP) detta Test_And_Set, che legge il valore del semaforo e nello stesso ciclo di bus lo decrementa (eventualmente lo pone a false se il semaforo è booleano

procedure Test_And_Set(s : semaforo);

begin Legge il valore di S e lo memorizza, dopodichè nello stesso

Test_And_Set:= s; ciclo di bus setta il semaforo a 0. L'operazione è atomica per

s:= s - 1; evitare che prima del Set da parte del processo corrente un

altro processo faccia il Test e rilevi lo stesso valore (per

end; S booleano potrebbero passare 2 processi contemporaneamente!)

procedure wait(s : semaforo);

begin In un sistema multiprocessore due o più processi sono attivi

while Test_And_Set(s) do Nop contemporaneamente: una o più Nop sono necessarie per dare il

end; tempo ad altri processi di incrementare eventualmente S

In un sistema monoprocessore non multiprocessing la Wait sarebbe irrealizzabile nella sua forma generale: a causa infatti della non interrompibilità della Wait, essa entrerebbe in un ciclo infinito in cui un semaforo "rosso", senza l'apporto di altri processi che possano incrementarlo, rimarrebbe tale a tempo indefinito. Il caso di interesse per noi è però il sistema monoprocessore multiprocessing, in cui ciascun processo ha a disposizione un processore virtuale e il loop può essere interrotto quando il processo che ha eseguito la Wait diventa Waiting, così che un altro processo possa quindi eventualmente agire sul semaforo; in realtà, meglio ancora, il SO realizza un semaforo tale da trasformare un'attesa attiva del processo sul processore virtuale (che impegna comunque ciclicamente la CPU per eseguire un loop vuoto) in una attesa passiva del processo che renda quest'ultimo di fatto Ready e poi Running solo quando il semaforo ritorna "verde": tale semaforo diventa un tipo strutturato e contiene un contatore ma anche un oggetto coda, che consente di implementare la coda dei processi in attesa sul semaforo in oggetto come coda dei loro PCB

tipo semaforo : record

contatore : integer;

tail : coda;

end;

var s : semaforo;

procedure wait(s : semaforo); La chiamata a Wait genera una Interruzione

begin

if s.contatore = 0 then begin Se il semaforo è "rosso"

<inserisci PCB del processo attualmente Running nella "s.tail">

Context_Switch; il processo corrente viene sospeso e la CPU

viene assegnata ad altro processo

end;

else s.contatore:= s.contatore - 1; Se invece il semaforo è "verde" esso viene

decrementato e il processo prosegue

end; Questa è una RTE (Return Exception)

procedure signal(s : semaforo);

begin

if <"s.tail" NON vuota> then <sposta il primo PCB da "s.tail" nella coda processi Ready>

else s.contatore:= s.contatore + 1; Incrementa il semaforo

end;

La coda del semaforo è generalmente implementata con una lista dinamica, comprendente un puntatore al primo processo in attesa, un puntatore all'ultimo processo in attesa e spesso anche (campo non necessario ma utile) il numero dei processi in attesa: la transizione di un processo Running  Waiting  Ready determina una analoga transizione del suo PCB attraverso una coda di attesa per un semaforo verso la coda dei processi ready.

L'invocazione di una procedura Wait o Signal costituisce per il processo chiamante una SVC che genera quindi una interruzione (PC e PSW vengono salvati nello stack del kernel) e rende non interrompibile l'esecuzione della procedura stessa (le interruzioni vengono disabilitate). Se la procedura eseguita è la Wait, viene analizzato il semaforo, nel caso sia "verde" viene rapidamente decrementato e si produce una RTE (che ripristina dallo stack PC e PSW), altrimenti il PCB del processo attualmente Running viene linkato alla coda di attesa relativa a quel semaforo rendendolo di fatto Waiting, il PCB viene aggiornato con lo stato corrente del processo testè sospeso presente nello stack, viene lanciato lo scheduler per determinare il prossimo processo Ready da far diventare Running e dal PCB di quest'ultimo viene prelevato il nuovo contesto da mettere nello stack (in pratica si esegue un Context_Switch) e si produce la RTE. Il nuovo processo prescelto dallo scheduler è quello in testa alla coda dei processi ready o quello considerato a massima priorità: il vantaggio di usare una coda anzichè le priorità sta nel fatto che rispettando l'ordine di sospensione si evita che un processo rimanga in attesa illimitata non riuscendo ad ottenere mai una sufficiente priorità. Condizione particolare si verifica quando la coda dei processi ready è vuota: lo scheduler abilita le interruzioni e in teoria potrebbe iniziare un proprio ciclo di attesa, tuttavia si preferisce inserire tra i processi di sistema un dummy process fittizio e a minima priorità che rimane sempre Ready ed esegue un ciclo vuoto senza fine, finchè almeno un altro processo non diventa Ready. Se la procedura eseguita è la Signal, allora il primo processo in testa alla coda di attesa del semaforo passa nella coda dei processi Ready e, se la coda di attesa è vuota, il semaforo viene incrementato, dopodichè c'è la RTE e il processo che ha eseguito la Signal prosegue la sua esecuzione (in realtà, se si adotta un meccanismo basato anche sulle priorità e non solo sull'ordine di sospensione, si può avere una Signal con prerilascio, ovvero viene confrontata la priorità del processo che ha eseguito la Signal con la priorità del processo in testa alla coda dei processi ready e se quest'ultima è superiore il processo che dovrebbe essere ripreso viene in realtà sospeso e inserito nella coda dei processi ready mentre l'altro viene mandato in esecuzione: il termine prerilascio indica proprio la perdita forzosa e anticipata della CPU da parte di un processo per un motivo differente dalla sua terminazione o dalla indisponibilità di una risorsa).

Gestione delle Risorse Condivise (uso del Semaforo)

La gestione delle risorse condivise (in particolare ad uso esclusivo) può essere ricondotta al programma utente (e quindi al programmatore) in due modi distinti: questi può allocare staticamente le risorse rendendole però private mediante l'utilizzo delle regole di visibilità del linguaggio, oppure può renderle dinamicamente private mediante una virtualizzazione delle risorse, ovvero usando procedure di Acquisizione e Rilascio delle risorse che facciano uso di una risorsa gestore come un semaforo, per risolvere il problema fondamentale della mutua esclusione (non più di un processo può utilizzare contemporaneamente una stessa risorsa). La procedura di acquisizione, in particolare, prima di concedere l'uso di una risorsa al processo che l'ha lanciata, deve verificare la cosiddetta condizione di sincronizzazione, soddisfatta in generale solo se la risorsa è libera e contemporaneamente se l'operazione richiesta alla risorsa è realmente effettuabile (il termine sincronizzazione, anche intuitivamente, suggerisce che in assenza di questa condizione il processo richiedente la risorsa deve attendere

Analizziamo 5 casi paradigmatici

Caso 1: Competizione tra processi per una singola risorsa

var R : T; Dichiarazione della singola Risorsa condivisa

mutex : semaforo initial(1); Semaforo booleano

procedure Gen_Operation; Generica procedura di accesso e manipolazione della Risorsa

begin

wait(mutex); Acquisizione della Risorsa

<sezione critica> Sequenza di istruzioni da eseguire sulla risorsa R in modo

mutuamente esclusivo rispetto ad altre sezioni critiche

signal(mutex); Rilascio della Risorsa

end;

Assegnata una singola risorsa condivisa R,  un insieme di sequenze di istruzioni da eseguire in mutua esclusione con le altre su R costituisce una classe di sezioni critiche per la risorsa R (più in generale comunque è possibilissimo che un processo esegua una sezione critica per una certa risorsa X e un altro processo esegua contemporaneamente una sezione critica per una diversa risorsa Y si dice che le due sezioni critiche appartengono a classi disgiunte o non compatibili). Il problema in esame si risolve banalmente associando a R un semaforo booleano mutex e incapsulando ogni sezione critica nella coppia Wait(mutex) e Signal(mutex): dalla definizione generale delle due primitive scaturisce che un solo processo per volta potrà eseguire una sezione critica.

Caso 2: Allocazione dinamica di un insieme limitato di risorse equivalenti a processi in competizione

var R : array[1..N] of T; Dichiarazione delle Risorse condivise

libero : array[1..N] of boolean initial(true) Status delle Risorse

risorse : semaforo initial(N); Semaforo generalizzato

mutex : semaforo initial(1); Semaforo booleano

procedure Acquisizione(var k:1..N); Procedura di acquisizione della Risorsa k-esima

var i:0..N;

begin

wait(risorse); Ci sono risorse disponibili?

wait(mutex); Sono il solo ad operare sulle risorse?

i:=0;

repeat

i:=i+1;

until libero[i]=true; In C for(k=1; libero[k]==false; k++);

libero[i]:=false;

k:=i;

signal(mutex); adesso non opero più sulle risorse

end;

procedure Rilascio(k:1..N); Procedura di rilascio della Risorsa k-esima

begin

wait(mutex); Sono il solo ad operare sulle risorse?

libero[k]:=true; La sezione critica qui è banale

signal(mutex); adesso non opero più sulle risorse

signal(risorse); c'è una risorsa disponibile in più

end;

procedure Gen_Operation; Generica procedura di accesso e manipolazione della Risorsa

var i:0..N;

begin

Acquisizione(i); "i" è parametro di Input/Output

Sequenza di istruzioni da eseguire sulla risorsa R[i]

Rilascio(i); "i" è parametro di Input

end;

Assegnate N risorse condivise R[i] equivalenti (è indifferente l'uso di una piuttosto che di un'altra), l'accaparramento di una di esse da parte di uno dei processi in competizione deve avvenire in modo indifferente. Nel caso precedente, di risorsa unica visibile a tutti i processi che ne possono fare uso, le sezioni critiche sono costituite proprio dalle M operazioni potenziali che ciascun processo può eseguire sulla risorsa: due processi che operassero contemporaneamente entrerebbero in conflitto. Nel caso in esame invece, in cui le risorse sono più di una ed equivalenti tra loro, le sezioni critiche sono solo due, ovvero le operazioni effettuate direttamente sulla risorsa gestore dell'insieme, anch'essa visibile a tutti i processi, per verificare/alterare - in fase di acquisizione e rilascio della singola risorsa dell'insieme - lo stato della risorsa gestore stessa (numero e lista di risorse libere e dunque allocabili); la mutua esclusione dei processi deve in teoria essere garantita sia nella fase di modifica della risorsa gestore e sia nella manipolazione della singola risorsa, tuttavia la prima implica in modo naturale la seconda, in quanto, una volta che la singola risorsa sia divenuta visibile ad un processo che l'abbia acquisita, essa diventa automaticamente invisibile agli altri processi: in pratica le  sequenze di istruzioni che costituiscono le generiche operazioni da effettuare sulla singola risorsa non sono più sezioni critiche, ma prima e dopo la loro esecuzione occorre eseguire sezioni critiche. A questo scopo, naturalmente, un singolo semaforo non è più sufficiente e ne occorrono almeno due: mutex per regolare l'accesso mutuamente esclusivo alla risorsa gestore, risorse per segnalare l'opportunità che vi si acceda (se infatti non vi sono risorse libere non ha senso che un processo tenti di accaparrarsene una accedendo alla risorsa gestore); cercare infine di generalizzare il caso precedente, utilizzando cioè N semafori per N risorse, non costituisce una soluzione accettabile al problema, perchè non tiene conto che le risorse sono tra loro equivalenti (se la risorsa I è occupata ma è libera la risorsa J, nulla deve ostare il singolo processo dall'accaparrarsi J piuttosto che rimanere in attesa che I si liberi

Caso 3: Cooperazione tra processi concorrenti con scambio di segnali temporali

Premettiamo che la cooperazione tra processi consiste sempre in un transito di informazioni tra processi - un vero e proprio scambio oppure un transito a senso unico (comunicazione asimmetrica) - dal momento che l'esecuzione di uno o più processi può dipendere o essere regolata dall'esecuzione di altri: esistono quindi dei vincoli sull'ordinamento temporale delle operazioni di processi cooperanti.

var s : array[1..N] of semaforo initial(0); N Semafori booleani

process P_regolatore; Processo regolatore

begin

loop

Signal(s[i]); Ciclicamente il semaforo i-esimo si incrementa

end; Il regolatore quindi funge da temporizzatore

end; ma anche da accumulatore di "token"

process P_i_esimo; Processo i-esimo regolato

begin

loop

Wait(s[i]); Il processo attende che sia disponibile almeno un

<sequenza di istruzioni regolata da s[i]> "token" sul semaforo i-esimo per eseguire la

sequenza di istruzioni prevista

end;

end;

Assegnato un processo regolatore e N processi da esso regolati, bisogna garantire che il processo i-esimo esegua ciclicamente una sequenza di istruzioni ogni volta che il regolatore trasmette un segnale di temporizzazione. Tale segnale, più che un clock, costituisce un dispensatore di token e quindi di permessi di esecuzione: il processo i-esimo non può agire prima di avere un token, ma se ne ha più d'uno deve riprendere ciclicamente l'esecuzione finchè non li esaurisce: è sufficiente avere N semafori booleani inizializzati a 0 sui quali il regolatore accatasta i token, e da ciascuno dei quali il singolo processo regolato li preleva (il semaforo funziona in pratica da stack).

Caso 4: Cooperazione tra processi concorrenti con scambio di messaggi (modello produttori-consumatori)

Il problema del produttore e consumatore descrive il caso classico di processi che regolano ciascuno l'esecuzione dell'altro: uno produce messaggi e li deposita in un buffer, l'altro consuma i messaggi e li preleva dal buffer (chiaramente il buffer è una risorsa condivisa visibile ad ambedue i processi). Il vincolo principale è scontato: il produttore non può depositare se il buffer è pieno, il consumatore non può prelevare se il buffer è vuoto.

var buffer : T; Buffer per il messaggio di tipo T

spazio_disponibile : semaforo initial(1); Semaforo booleano

messaggio_disponibile : semaforo initial(0); "

procedure Invio(x : T);

begin

wait(spazio_disponibile);

buffer:=x;

signal(messaggio_disponibile);

end;

procedure Ricezione(var x : T);

begin

wait(messaggio_disponibile);

x:=buffer;

signal(spazio_disponibile);

end;

Nel caso di un singolo produttore, singolo consumatore e di singolo buffer l'implementazione è banale, dacchè ciascuno dei due processi agisce solo quando il proprio semaforo di riferimento diventa "verde", lo rende "rosso" prima di agire e quando ha finito setta "verde" il semaforo dell'altro processo: la produzione si alterna col consumo in senso stretto e per il produttore è impossibile continuare a produrre finchè il consumatore non svuota il buffer.

var buffer : array[0..N-1] of T; Buffer a cardinalità N per i messaggi di tipo T

testa : 0..N initial(0); Puntatore alla testa della coda circolare

coda : 0..N initial(0); Puntatore alla coda della coda circolare

spazio_disponibile : semaforo initial(N); Semaforo generalizzato

messaggio_disponibile : semaforo initial(0); "

procedure Invio(x : T);

begin

wait(spazio_disponibile);

buffer[coda]:=x;

coda:= (coda + 1) mod N;

signal(messaggio_disponibile);

end;

procedure Ricezione(var x : T);

begin

wait(messaggio_disponibile);

x:=buffer[testa];

testa:= (testa + 1) mod N;

signal(spazio_disponibile);

end;

Nel caso di buffer multiplo (fermo restando un unico produttore e un unico consumatore) l'implementazione precedente va corretta esclusivamente nel meccanismo di gestione del buffer: la soluzione più semplice è implementare una coda circolare (nell'esempio tale coda è statica ma potrebbe essere anche dinamica) il che ha il vantaggio di garantire che il produttore si possa portare avanti con la produzione prima di vedersi negato l'accesso al buffer, oltre al fatto che l'ordine di prelievo continua ad essere coerente con l'ordine di deposito. Per il resto rimane tutto uguale compresi i semafori (che qui diventano generalizzati), il loro significato e la loro gestione.

var Definizione del buffer e della coda per gestirlo

spazio_disponibile : semaforo initial(N); Semaforo generalizzato

messaggio_disponibile : semaforo initial(0); "

mutex1 : semaforo initial(1); Semaforo booleano

mutex2 : semaforo initial(1); "

procedure Invio(x : T);

var

begin

wait(spazio_disponibile); Richiesta di un buffer vuoto

wait(mutex1);

<prelievo del buffer vuoto dalla coda>

signal(mutex1);

<riempimento del buffer prelevato>

wait(mutex2);

<deposito del buffer pieno nella coda>

signal(mutex2);

signal(messaggio_disponibile); Segnalazione di un buffer pieno disponibile

end;

procedure Ricezione(var x : T);

var

begin

wait(messaggio_disponibile); Richiesta di un buffer pieno

wait(mutex2);

<prelievo del buffer pieno dalla coda>

signal(mutex2);

<svuotamento del buffer prelevato>

wait(mutex1);

<deposito del buffer vuoto nella coda>

signal(mutex1);

signal(spazio_disponibile); Segnalazione di un buffer vuoto disponibile

end;

Il caso più generale è quello di molteplici produttori che concorrono e competono nel deposito dei messaggi e molteplici consumatori che concorrono e competono nel loro prelievo da un buffer, nel caso più generale buffer multiplo (il caso di buffer singolo si ottiene banalmente dal caso generale). L'implementazione presentata contiene rispetto a quella precedente due semafori supplementari - mutex1 e mutex2 - che trasformano in sezioni critiche le fasi di prelievo/rilascio di buffer vuoti e di rilascio/prelievo di buffer pieni il motivo di ciò è presto detto. Facendo riferimento all'implementazione precedente, in presenza di più di un produttore e di più di un buffer vuoto disponibile, può accadere che ad esempio 2 produttori superino la Wait(spazio_disponibile) e che ciascuno però finisca per operare sul medesimo buffer vuoto sovrascrivendo in sequenza il valore memorizzato dal processo che ha operato per primo su di esso

procedure Invio(x : T); procedure Invio(x : T);

begin begin

wait(spazio_disponibile);

wait(spazio_disponibile);

buffer[coda]:=x;

buffer[coda]:=x;

coda:= (coda + 1) mod N;

coda:= (coda + 1) mod N;

signal(messaggio_disponibile);

signal(messaggio_disponibile);

end;

end;

Se le operazioni indicate (a sinistra il primo processo, a destra il secondo) seguono l'ordine in cui sono inframmezzate, è evidente che solo il secondo processo depositerà il suo messaggio mentre il secondo dei due buffer inizialmente vuoti conterrà un valore non definito: mutex1 impedisce che più produttori prelevino per sè lo stesso buffer vuoto. Stando così le cose si potrebbe pensare che mutex2 sia superfluo e che le operazioni di prelievo, uso e rilascio del buffer possano essere inserite tutte all'interno di un'unica sezione critica del tipo

procedure Invio(x : T);

begin

wait(spazio_disponibile);

wait(mutex);

Qui c'è una operazione implicita di scelta

del buffer libero puntato da "coda"

buffer[coda]:=x;

coda:= (coda + 1) mod N;

signal(mutex);

signal(messaggio_disponibile);

end;

Ciò evita sicuramente l'interferenza descritta sopra ma di fatto serializza l'accesso dei produttori all'insieme dei buffer nel complesso, non distinguendo tra prelievo, uso e rilascio: mentre un processo si sceglie il buffer, un altro non può depositare in un altro buffer il suo messaggio e un terzo non può rilasciare il proprio buffer nel quale ha già effettuato il deposito. Nell'esempio qui sopra, supponendo che i processi siano in grado di prelevare i buffer vuoti alla stessa velocità (la procedura sarà unica per tutti) potremmo avere che un produttore più lento impedisce ad un altro più rapido di effettuare un deposito solo perchè si è prenotato per primo: la soluzione è spostare la fase d'uso del buffer fuori dalla sezione critica in cui tale buffer vuoto viene prelevato, ottenendo la seguente versione

procedure Invio(x : T);

var i:0..N-1;

begin

wait(spazio_disponibile);

wait(mutex);

i:=coda;

coda:= (coda + 1) mod N; Prelievo "de facto" del buffer da usare

signal(mutex);

buffer[i]:=x;

signal(messaggio_disponibile);

end;

che non presenta il problema considerato. Naturalmente, lo stesso tipo di conflitto si ha anche tra molteplici consumatori che superano tutti la Wait(messaggio_disponibile) e poi magari finiscono per prelevare tutti lo stesso messaggio, ignorando gli altri. Alla luce quindi di quanto detto, è banale ottenere la versione corretta anche della procedura di ricezione

procedure Ricezione(var x : T);

var i:0..N-1;

begin

wait(messaggio_disponibile);

wait(mutex);

i:=testa;

testa:= (testa + 1) mod N; Prelievo "de facto" del buffer da usare

signal(mutex);

x:=buffer[i];

signal(spazio_disponibile);

end;

Appare evidente a questo punto che il semaforo mutex non può essere unico, altrimenti vengono serializzate le operazioni di prelievo di buffer vuoto e deposito di buffer pieno, che in linea di principio sono indipendenti: occorre usare mutex1 nel primo caso e mutex2 nel secondo. Potrebbe però non essere chiaro il motivo per cui esiste una sezione critica relativa a mutex2 nella procedura di Invio (e dualmente una relativa a mutex1 in quella di Ricezione) ma ciò si spiega osservando che la fase di rilascio di un buffer in una coda circolare statica dalla quale, di fatto, non è mai stato fisicamente eliminato non ha senso ed è quindi una operazione superflua: viceversa, se usassimo una coda a puntatori, la fase di prelievo determinerebbe un delinkaggio effettivo del buffer prelevato e sarebbe quindi necessario un successivo relinkaggio alla stessa coda di un buffer pieno, operazione questa che va fatta chiaramente in mutua esclusione con un'operazione di prelievo dalla stessa coda di un buffer pieno, e ciò spiega il perchè si usi il semaforo mutex2 (per la procedura Ricezione vale lo stesso analogo discorso). L'implementazione generica che abbia descritto, facente uso dei due semafori mutex1 e mutex2, si dimostra quindi perfettamente generale.

Comunque, nel caso in cui usassimo la solita coda circolare statica (e quindi non a puntatori) degli esempi precedenti, va detto che l'implementazione fin qui sviluppata non è priva di problemi. Supponiamo infatti, a titolo di esempio, di partire da buffer tutti vuoti, supponiamo che 2 processi produttori si accaparrino i primi 2 buffer liberi, che il primo decida di depositare il proprio messaggio in buffer[1] e il secondo in buffer[2], che inoltre il secondo processo completi il deposito prima del primo processo e che quindi, a seguito della sua Signal(spazio_disponibile), il secondo buffer sia pieno mentre il primo è ancora vuoto: quando un processo consumatore va a prelevare il presunto buffer pieno in realtà preleva quello puntato da testa, che però è ancora vuoto! E' facile immaginare che questo tipo di problema produce malfunzionamenti a catena, dal momento che i consumatori finiscono nel migliore dei casi per prelevare i messaggi nell'ordine sbagliato, nel peggiore perdono i messaggi. Nel caso della coda dinamica a puntatori tutto questo non succede, perchè un buffer non ancora riempito non si trova ancora fisicamente nella coda e quindi è inaccessibile; nella coda statica al contrario il buffer viene solo apparentemente prelevato ma in realtà è sempre là e, poichè il processo di deposito dei messaggi è sì parallelizzato ma non esiste alcuna struttura dati che tenga conto dell'effettivo ordine di deposito, ciò crea grossi problemi.

Il modo più ovvio di risolvere il problema conservando una struttura statica è quello di aggiungere alla coda circolare statica (gestita dai soli indici testa e coda) un'altro vettore contenente lo stato dei singoli buffer

var buffer : array[0..N-1] of T; Buffer a cardinalità N per i messaggi di tipo T

testa : 0..N initial(0); Puntatore alla testa della coda circolare

coda : 0..N initial(0); Puntatore alla coda della coda circolare

stato : array[0..N-1] of 0..2 initial(0); Stato dei buffer (Vuoto, In uso, Pieno)

spazio_disponibile : semaforo initial(N); Semaforo generalizzato

messaggio_disponibile : semaforo initial(0); "

mutex1 : semaforo initial(1); Semaforo booleano

mutex2 : semaforo initial(1); "

procedure Invio(x : T);

var i:0..N-1;

begin

wait(spazio_disponibile);

wait(mutex1);

i:=coda;

repeat coda:=(coda + 1) mod N; Definisce la nuova "coda" saltando tutti

until stato[coda]=0; i buffer PIENI e IN USO eventualmente "doppiati"

stato[i]:=1; - Buffer IN USO -

signal(mutex1);

buffer[i]:=x;

stato[i]:=2; - Buffer PIENO -

signal(messaggio_disponibile);

end;

procedure Ricezione(var x : T);

var i:0..N-1;

begin

wait(messaggio_disponibile);

wait(mutex2);

i:=testa;

while stato[i]<2 do Cerca il prossimo buffer PIENO

i:= (i + 1) mod N;

if i=testa then Se "testa" punta ad un buffer ancora IN USO non

testa:= (testa + 1) mod N; viene incrementato: viene conservata la priorità

acquisita dal "produttore lento"

stato[i]:=1; - Buffer IN USO -

signal(mutex2);

x:=buffer[i];

stato[i]:=0; - Buffer VUOTO -

signal(spazio_disponibile);

end;

Questa implementazione risolve elegantemente il problema delle interferenze e ancora una volta non richiede che il rilascio di un buffer pieno o vuoto costituiscano sezioni critiche; la gestione della coda privilegia inoltre il minimo stravolgimento possibile (senza garanzie comunque) dell'ordine con il quale i produttori si accaparrano i buffer, di modo che il prelievo dei messaggi da parte dei consumatori sia il più possibile coerente con esso. Per conservare quest'ordine in modo assolutamente preciso, occorre necessariamente utilizzare una coda circolare a puntatori, statica o dinamica che sia.

Si noti che in tutte le implementazioni viste è sempre possibile raggruppare in procedure distinte ed indipendenti sottosequenze di istruzioni (ad esempio, è possibile concepire una procedura Invio che chiami a sua volta 3 distinte procedure per la richiesta e l'acquisizione del buffer vuoto, per la manipolazione del buffer e in fine per il suo rilascio) e che ciò chiaramente può avvenire in diversi modi possibili.

Caso 5: Problema dei lettori-scrittori

Il problema dei lettori e scrittori descrive il caso che una risorsa (tipicamente una struttura dati, un buffer) sia condivisa tra processi in grado di leggerne il contenuto senza modificarlo - lettori - e processi in grado di modificarne il contenuto - scrittori. La condizione di sincronizzazione per un processo che voglia accedere alla risorsa deve essere definita in vista di uno scopo fondamentale, evitare che la risorsa enti in uno stato di inconsistenza. In quest'ottica, un lettore non può accedere alla risorsa se uno scrittore la sta modificando perchè è in uno stato inconsistente, analogamente uno scrittore non può modificare la risorsa mentre un lettore la sta leggendo perchè la renderebbe inconsistente per quest'ultimo: esiste quindi un vincolo di mutua esclusione tra lettori e scrittori; certamente anche gli scrittori che competono per l'accesso alla risorsa devono agire in mutua esclusione, perchè altrimenti le loro scritture interferirebbero tra loro rendendo la risorsa inconsistente, mentre i lettori viceversa possono tranquillamente leggere la risorsa in contemporanea, perchè non c'è pericolo che la rendano inconsistente.

var buffer : T; Definizione del buffer

lettori : integer initial(0); Numero di lettori

synch : semaforo initial(1); Semaforo booleano

mutex : semaforo initial(1); "

procedure Lettura(var x : T);

begin

wait(mutex); Fase di Inizio Lettura

lettori:= lettori + 1;

if lettori=1 then wait(synch); Se è il primo lettore reclama il "token"

signal(mutex);

x:=buffer; <Operazione di Lettura>

wait(mutex); Fase di Fine Lettura

lettori:= lettori - 1;

if lettori=0 then signal(synch); se è l'ultimo lettore rilascia il "token"

signal(mutex);

end;

procedure Scrittura(x : T);

begin

wait(synch); Fase di Inizio Scrittura (reclama il "token")

buffer:=x; <Operazione di Scrittura>

signal(synch); Fase di Fine Scrittura (rilascia il "token")

end;

Questa implementazione risolve il problema della competizione tra lettori e scrittori e tra scrittori e scrittori in modo molto elegante. La modifica dello stato del semaforo synch (condizione di sincronizzazione) costituisce un meccanismo equivalente alla gestione di un token, ovvero di un permesso con il quale un processo può scrivere da solo o leggere in gruppo: finchè c'è almeno un lettore in attesa, il gruppo lettori conserva il token (synch resta "rosso") e lo rilascia (synch diventa "verde") solo quando tutti i lettori hanno terminato; chiaramente la modifica della variabile di stato lettori avviene in mutua esclusione, per evitare che due lettori la modifichino contemporaneamente rendendola inconsistente, e anche la richiesta e il rilascio del token, attraverso la Wait(synch) e Signal(synch), avviene nella stessa sezione critica, di modo che un solo lettore per volta richieda il token e lo rilasci.

Un problema però di questa implementazione è che è totalmente sbilanciata a favore dei lettori, i quali hanno sempre la massima priorità sugli scrittori e questi ultimi, in teoria, potrebbero entrare nella indesiderabile condizione di starvation (impossibilità da parte di un processo pronto all'esecuzione di ottenere le risorse di cui necessità): i lettori leggono sempre la risorsa ma gli scrittori non riescono mai a modificarla. Se infatti uno scrittore sta operando sulla risorsa e altri processi scrittori e lettori sono in coda (per la verità un solo processo lettore può essere contemporaneamente in coda sul semaforo synch, tutti gli altri resteranno in attesa su mutex), laddove a passare per primo sia il processo lettore, tutti gli altri lettori passano a valanga insieme ad esso, a scapito di eventuali altri scrittori in attesa. Una soluzione più equa prevede due semafori e una variabile di stato in più

var buffer : T; Definizione del buffer

lettori : integer initial(0); Numero di lettori

scrittori : integer initial(0); Numero di scrittori

synch : semaforo initial(1); Semaforo booleano

mutex : semaforo initial(1); "

mutex1 : semaforo initial(1); "

mutex2 : semaforo initial(1); "

procedure Scrittura(x : T);

begin

wait(mutex2); Fase di Inizio Scrittura

scrittori:= scrittori + 1;

if scrittori=1 then wait(synch); Se è il primo scrittore reclama il "token"

signal(mutex2);

wait(mutex1);

buffer:=x; <Operazione di Scrittura>

signal(mutex1);

wait(mutex2); Fase di Fine Scrittura

scrittori:= scrittori - 1;

if scrittori=0 then signal(synch); se è l'ultimo scrittore rilascia il "token"

signal(mutex2);

end;

Mentre la procedura di Lettura rimane inalterata, quella di Scrittura diventa ad essa speculare, con synch che realizza come prima la mutua esclusione tra lettori e scrittori, con mutex2 che realizza (al pari di mutex) la mutua esclusione nelle modifiche di un comune variabile di stato e infine con mutex1 che realizza la mutua esclusione nella scrittura dei processi scrittori. L'inconveniente stavolta è che anche i lettori, come gli scrittori, possono in teoria subire un'attesa indefinita.

Anche qui, naturalmente, con riferimento a ciascuna delle due alternative implementazioni è possibile raggruppare in procedure distinte le diverse fasi (Inizio_Lettura, Lettura, Fine_Lettura, Inizio_Scrittura, Scrittura, Fine_Scrittura).

Semaforo privato

Un tipo particolare di semaforo è il semaforo privato, normalmente settato a 0, visibile da tutti i processi che possono eseguirvi una Signal (lo incrementano) ma tale che solo uno di essi vi esegue la Wait (rimane in attesa su di esso). Un semaforo privato non è concettualmente differente da un semaforo generico, è l'uso che ne viene fatto che lo rende privato (in pratica il programmatore lo usa nel modo descritto). Resta da capire che utilità abbia.

Un semaforo nel suo uso classico, quindi non privato, viene associato ad una (semaforo booleano) o più risorse (semaforo generalizzato) e i processi in competizione tra loro per l'allocazione si mettono in attesa su di esso; quando un processo esegue una Wait il suo PCB entra in una coda associata al semaforo, ma non esiste una vera politica di scheduling dei processi in attesa su quel semaforo: la Signal eseguita da un processo che ha terminato di usare la risorsa sblocca sempre il processo in attesa da più tempo, ovvero il primo in coda viene spostato nella coda dei processi ready: non è possibile scegliere il prossimo processo che allocherà la risorsa sulla base dello stato della risorsa e del tipo di richiesta che i singoli processi in attesa vogliono effettuare (condizioni di sincronizzazione), nè è possibile assegnare a ciascuno una priorità, magari dinamica,  e sbloccare di volta in volta il processo a massima priorità. Si potrebbe pensare di prelevare dalla coda un processo diverso dal primo ma ciò non consentirebbe comunque una reale politica di scheduling, giacchè la Signal funziona sempre allo stesso modo. Un semaforo privato risolve questo problema.

Intuitivamente un semaforo classico funziona così: data una risorsa (o un insieme di risorse) condivisa, il semaforo è unico e tutti i processi si mettono in fila indiana su di esso, sicchè il primo processo che rilascia la risorsa e sblocca il semaforo favorisce il processo in attesa da più tempo su di esso. Un semaforo privato invece funziona diversamente: data una risorsa (o un insieme di risorse) condivisa, ogni processo ha un proprio semaforo privato, sul quale esso soltanto può mettersi in attesa e la procedura di rilascio della risorsa viene concepita per stabilire dinamicamente quale tra tutti i semafori privati deve essere sbloccato, producendo di fatto una reale schedulazione dei processi in attesa. Un semaforo classico deve normalmente essere inizializzato ad un valore positivo, il che indica che normalmente la risorsa cui è associato deve essere disponibile (salvo allocazioni temporanee da parte dei processi che sono interessati ad usarla), viceversa un semaforo privato deve normalmente essere inizializzato a zero, coerentemente col fatto che il processo cui è associato è in attesa su di esso e attende un segnale di sblocco (l'attesa è la condizione normale su un semaforo privato).

La gestione attraverso semafori privati di una risorsa (o un insieme di risorse) R condivisa da N processi richiede N semafori privati e un gestore di risorsa, come al solito una risorsa gestore, una struttura dati nella quale viene memorizzato lo stato della risorsa (occupata, totalmente libera, parzialmente libera da cui si deducono anche le operazioni disponibili) e lo stato dei processi in attesa su di essa (quanti sono, che operazioni desiderano eseguire, eventuale priorità statica), e sulla quale agiscono le solite procedure di Acquisizione e Rilascio. Si noti che abbiamo già definito risorse gestore di questo tipo (si pensi alle variabili/vettori di stato libero, testa e coda, stato, lettori e scrittori) ma stavolta, facendo uso di semafori privati, Acquisizione e Rilascio sono in grado di determinare dinamicamente quale semaforo va sbloccato e quale processo ha la priorità nell'allocazione: semafori privati, risorsa gestore e i suoi metodi di accesso costituiscono uno scheduler.

Un primo schema d'uso dei semafori privati consente non solo di schedulare il prossimo processo cui allocare la risorsa ma più in generale individuare più processi che soddisfino ciascuno la propria condizione di sincronizzazione con la risorsa: più di un processo può essere sbloccato sulla risorsa

var mutex : semaforo initial(1); Semaforo booleano

priv : array[1..N] of semaforo initial(0); N Semafori privati (per N processi)

procedure Acquisizione(p:1..N, ); Procedura di acquisizione per il Processo p-esimo

begin

wait(mutex); Altri processi operano sulla risorsa gestore?

if <condizione di sincronizzazione> then begin

<allocazione della risorsa al processo p-esimo>

signal( priv[p] ); Sblocco del semaforo privato

end;

else <indicazione nella risorsa gestore che il processo p-esimo è in attesa>

signal(mutex); adesso non opero più sulla risorsa gestore

wait( priv[p] ); Il processo chiamante è proprio il p-esimo per cui

se la risorsa è stata acquisita la sequenza

"signal-wait" non ha effetto sul semaforo, il

chiamante non viene sospeso (l'ultima wait incontra

semaforo "verde") e all'Acquisizione segue l'uso

Viceversa il chiamante si sospende restando in

attesa sul suo semaforo privato

end;

procedure Rilascio(); Procedura di rilascio della Risorsa k-esima

begin

wait(mutex); Altri processi operano sulla risorsa gestore?

<rilascio della risorsa>

if <esiste almeno un processo sospeso in attesa della risorsa

che possa verificare la sua condizione di sincronizzazione> then begin

<schedulazione del prossimo processo p-esimo da riattivare>

<allocazione della risorsa al processo p-esimo>

<indicazione nella risorsa gestore che il processo p-esimo non è più in attesa>

signal( priv[p] ); Sblocco del semaforo privato

end;

signal(mutex); adesso non opero più sulla risorsa gestore

end;

Il funzionamento dello schema è chiaro: se un processo rispetta la condizione di sincronizzazione per poter allocare la risorsa gli viene allocata e prosegue la sua esecuzione, altrimenti annota in un opportuno gestore di risorsa il suo stato di processo sospeso e si mette in attesa sul proprio semaforo, aspettando che qualche altro processo lo sblocchi; una volta rilasciata la risorsa (presumibilmente dopo l'uso), viene lanciato un opportuno algoritmo di schedulazione che alloca la risorsa ad un processo in attesa, sempre che ce ne siano; sostituendo inoltre nella Rilascio l'istruzione

while <esiste almeno un processo sospeso in attesa della risorsa

che possa verificare la sua condizione di sincronizzazione> do begin

è possibile eventualmente allocare la risorsa a più processi contemporaneamente (laddove operino su parti diverse della risorsa per esempio se la risorsa è un array di risorse, oppure è un'area di memoria, ). In realtà, in questo schema, il blocco di istruzioni

<allocazione della risorsa al processo p-esimo>

è presente in ambedue le procedure, così come nella procedura Acquisizione è presente una cascata Signal - Wait sul semaforo privato, aspetti questi che denotano una ridondanza del codice in contrasto coi requisiti di efficienza che  le routine del Kernel dovrebbero avere.

Un secondo schema d'uso dei semafori privati elimina le ridondanze precedenti ma non consente di sbloccare più processi all'atto del Rilascio della risorsa, ed è dunque adatto a dispositivi che non prevedono questa possibilità (per esempio le stampanti

var mutex : semaforo initial(1); Semaforo booleano

priv : array[1..N] of semaforo initial(0); N Semafori privati (per N processi)

procedure Acquisizione(p:1..N, ); Procedura di acquisizione per il Processo p-esimo

begin

wait(mutex); Altri processi operano sulla risorsa gestore?

if not <condizione di sincronizzazione> then begin

<indicazione nella risorsa gestore che il processo p-esimo è in attesa>

signal(mutex); adesso non opero più sulla risorsa gestore

wait( priv[p] );

<indicazione nella risorsa gestore che il processo p-esimo non è più in attesa>

end;

<allocazione della risorsa al processo p-esimo>

signal(mutex); adesso non opero più sulla risorsa gestore

end;

procedure Rilascio(); Procedura di rilascio della Risorsa k-esima

begin

wait(mutex); Altri processi operano sulla risorsa gestore?

<rilascio della risorsa>

if <esiste almeno un processo sospeso in attesa della risorsa

che possa verificare la sua condizione di sincronizzazione> then begin

<schedulazione del prossimo processo p-esimo da riattivare>

signal( priv[p] ); Sblocco del semaforo privato

end; else signal(mutex); adesso non opero più sulla risorsa gestore

end;

Anche qui il funzionamento dello schema è abbastanza chiaro: se un processo NON rispetta la condizione di sincronizzazione per poter allocare la risorsa, annota nel gestore di risorsa il suo stato di processo sospeso, esce dalla sezione critica di accesso al gestore e si mette in attesa sul proprio semaforo aspettando che qualche altro processo lo sblocchi; un processo che rilasci la risorsa (presumibilmente dopo l'uso), verifica se esiste almeno un processo in attesa, lancia un opportuno algoritmo di schedulazione per sceglierlo ma NON gli alloca la risorsa, semplicemente ne sblocca il corrispondente semaforo: in tale ipotesi il processo sbloccante NON esce dalla sezione critica (ci penserà il processo sbloccato) mentre il processo schedulato, superata la Wait sul proprio semaforo annota nel gestore di risorsa il suo nuovo stato, si alloca la risorsa ed esce finalmente dalla sezione critica. Chiaramente, il meccanismo indicato (il processo sbloccante entra nella sezione critica e quello sbloccato si occupa di uscirne) non consente di mettere in ciclo la ricerca di più processi da sbloccare.

Vediamo 4 possibili applicazioni dei semafori privati

Esempio 1: Processi temporizzati da un processo temporizzatore

Corrisponde al Caso 3 d'uso dei semafori già analizzato (in quell'esempio i semafori sono privati).

Esempio 2: Allocazione dinamica di un insieme limitato di risorse equivalenti a processi in competizione

var R : array[1..M] of T; Dichiarazione delle Risorse condivise

libera : array[1..M] of boolean initial(true); Status delle Risorse

libere : 0..M initial (M); "

sospeso : array[1..N] of boolean initial(false); Status dei Processi

sospesi : 0..N initial(0); "

mutex : semaforo initial(1); Semaforo booleano

priv : array[1..N] of semaforo initial(0); N Semafori privati (per N processi)

procedure Acquisizione(var r:1..M, p:1..N); Procedura di acquisizione per il Processo p-esimo

var k:0..M;

begin

wait(mutex); Altri processi operano sulla risorsa gestore?

if libere=0 then begin Condizione di sincronizzazione negata e

sospeso[p]:=true; "annotazione" dello stato di sospensione

sospesi:=sospesi + 1;

signal(mutex);

wait( priv[p] ); Attesa sul semafoto privato

sospeso[p]:=false; Condizione di sincronizzazione ripristinata e

sospesi:=sospesi - 1; eliminazione dell'"annotazione" di sospensione

end;

k:=0; Ricerca della risorsa da allocare

repeat k:=k+1; until libera[k]=true;

r:=k; Allocazione della risorsa

libera[r]:=false; con "annotazione" nel gestore risorsa

libere:=libere - 1;

signal(mutex); adesso non opero più sulla risorsa gestore

end;

procedure Rilascio(r:1..M); Procedura di rilascio della Risorsa r-esima

var k:0..N;

begin

wait(mutex); Altri processi operano sulla risorsa gestore?

libera[r]:=true; "Annotazione" del rilascio nel gestore risorsa

libere:=libere + 1;

if sospesi>0 then begin Condizione di schedulazione

<selezione del processo k-esimo a massima priorità>

signal( priv[k] ); Sblocco del suo semaforo privato

end; else signal(mutex); adesso non opero più sulla risorsa gestore

end;

Esempio 3: Allocazione dinamica di un'area di memoria

Si disponga di un'area di memoria di cardinalità M condivisa tra N processi, i quali possono allocarne una parte anche tutti contemporaneamente, purchè la loro richiesta sia non superiore allo spazio libero disponibile. La politica di schedulazione adottata privilegia sempre il processo che richiede la quantità massima di memoria, ragionevole in quanto, in caso contrario, tale processo potrebbe attendere indefinitamente prima di vedersi allocare lo spazio richiesto. Questo esempio è un caso particolare del caso precedente, ma se ne differenzia perchè durante il rilascio di una parte delle risorse (ciascuna cella del banco di memoria può essere considerata una risorsa di un insieme di risorse e le risorse vengono assegnate a blocchi) si considera ammissibile un ciclo di schedulazione che allochi eventualmente più blocchi di celle a più processi.

var R : array[1..M] of T; Dichiarazione delle Risorse condivise

libera : array[1..M] of boolean initial(true); Status delle Risorse

libere : 0..M initial (M); "

richiesta : array[1..N] of integer initial(0); Status dei Processi (sospeso[i] <=> richiesta[i]>0)

sospesi : 0..N initial(0); "

mutex : semaforo initial(1); Semaforo booleano

priv : array[1..N] of semaforo initial(0); N Semafori privati (per N processi)

procedure Acquisizione(var r:integer, p:1..N); Procedura di acquisizione per il Processo p-esimo

var k:0..M;

begin

wait(mutex); Altri processi operano sulla risorsa gestore?

if sospesi=0 and r<=libere then begin Condizione di sincronizzazione: solo se la richiesta

è accettabile e non ci sono altri processi in attesa

(se ce ne sono, la loro richiesta è minore/uguale e

quindi quella attuale non è soddisfacibile, oppure

è maggiore e in tal caso essi hanno la priorità)

<assegnazione di r celle al processo> Allocazione della risorsa

<manipolazione del vettore libera> con "annotazione" nel gestore risorsa

libere:=libere - r;

signal( priv[p] );

end; else begin "annotazione" di sospensione del processo

richiesta[p]:=r;

sospesi:=sospesi + 1;

end;

signal(mutex); adesso non opero più sulla risorsa gestore

wait( priv[p] );

end;

procedure Rilascio(r:1..M); Procedura di rilascio della Risorsa r-esima

var k,max:0..N;

begin

wait(mutex); Altri processi operano sulla risorsa gestore?

<manipolazione del vettore libera> Rilascio e "annotazione" nel gestore risorsa

libere:=libere + r;

while sospesi>0 do begin

max:=1;

for i:=2 to N do if richiesta[i]>richiesta[max] then max:=i;

if richiesta[max]<=libere then begin

<assegnazione delle celle al processo> Allocazione della risorsa

<manipolazione del vettore libera> con "annotazione" nel gestore risorsa

libere:=libere - richiesta[max];

richiesta[max]:=0; e "annotazione" che il processo non

sospesi:=sospesi - 1; è più sospeso

signal( priv[max] ); Sblocco del semaforo privato

end; else break; "break" del ciclo while

end;

signal(mutex); adesso non opero più sulla risorsa gestore

end;

Esempio 4: Problema dei lettori-scrittori

Soluzione alternativa a quelle già presentate nel precedente Caso 5 d'uso dei semafori già analizzato, relativo al problema dei lettori e scrittori. Il problema dello starvation viene risolto alternando lettori e scrittori secondo questa regola: se un lettore sopraggiunge mentre uno scrittore sta scrivendo oppure altri lettori stanno leggendo MA c'è già in attesa almeno uno scrittore, esso entrerà in attesa e subentrerà al primo scrittore (precedendo eventuali altri scrittori in attesa) insieme a tutti i lettori che si saranno messi in attesa fino a quel momento.

var buffer : T; Definizione del buffer

lettori : integer initial(0); Numero di lettori attivi

scrittori : boolean initial(false); Scrittori attivi?

sospesi_l : integer initial(0); Numero di lettori sospesi

sospesi_s : integer initial(0); Numero di scrittori sospesi

mutex : semaforo initial(1); Semaforo booleano

priv_l : semaforo initial(0); Semaforo privato dei lettori

priv_s : semaforo initial(0); Semaforo privato degli scrittori

procedure Lettura(var x : T);

begin

wait(mutex); Fase di Inizio Lettura

if sospesi_s=0 and not scrittori then begin Se nessuno scrittore all'orizzonte

lettori:=lettori + 1; sblocca i lettori

signal(priv_l);

end; else sospesi_l:=sospesi_l + 1; altrimenti metti il nuovo lettore in attesa

signal(mutex);

wait(priv_l);

x:=buffer; <Operazione di Lettura>

wait(mutex); Fase di Fine Lettura

lettori:=lettori - 1; Rimuovi il lettore corrente

if lettori=0 and sospesi_s>0 then begin e se non ci sono altri lettori attivi

scrittori:=true;

sospesi_s:=sospesi_s - 1;

signal(priv_s); sblocca il prossimo scrittore (se ce n'è uno)

end;

signal(mutex);

end;

procedure Scrittura(x : T);

begin

wait(mutex); Fase di Inizio Scrittura

if lettori=0 and not scrittori then begin Se nessun lettore o scrittore attivo

scrittori:=true; sblocca il prossimo scrittore

signal(priv_s);

end; else sospesi_s:=sospesi_s + 1; altrimenti metti il nuovo scrittore in attesa

signal(mutex);

wait(priv_s);

buffer:=x; <Operazione di Scrittura>

wait(mutex); Fase di Fine Scrittura

scrittori:=false; Rimuovi lo scrittore

while sospesi_l>0 do begin e sblocca tutti i lettori in attesa finora

lettori:=lettori + 1;

sospesi_l:=sospesi_l - 1;

signal(priv_l);

end; else if sospesi_s>0 then begin oppure sblocca il prossimo scrittore in attesa

scrittori:=true;

sospesi_s:=sospesi_s - 1;

signal(priv_s);

end;

signal(mutex);

end;

Costrutti Regione Critica e Monitor

Costruire un gestore di risorsa all'interno di un linguaggio di programmazione concorrente può essere più facile se si usano costrutti di alto livello: sarà poi il compilatore ad eliminare il gap semantico traducendoli in termini di semafori, Wait e Signal messi a disposizione dal SO.

Il costrutto regione critica risolve il problema della mutua esclusione

var v : shared T; Variabile di un tipo comune a più processi

che identifica una risorsa condivisa

Region v DO Region v DO

begin begin

wait(semaforo);

<sezione critica A> <sezione critica B> <sezione critica>

signal(semaforo);

end; end;

Il compilatore non fa altro che assegnare ad ogni regione critica un semaforo, di fatto aggiungendo una Wait in corrispondenza del begin e una Signal in corrispondenza dell'end. Nulla vieta il nesting (vedi anche problemi del nesting dei Monior, più avanti) di una regione critica dentro un'altra. Più in generale, il costrutto regione critica condizionale consente ad un processo di accedere alla risorsa V solo se una condizione B (da intendersi come una vera e propria condizione di sincronizzazione) è verificata

Region v When B DO Se la risorsa è libera (semaforo S "verde") il processo entra nella RC

begin e verifica la condizione B: se è verificata esegue la "sezione critica"

altrimenti si mette "in attesa" che la B risulti verificata ma nel

<sezione critica> frattempo lascia la RC. Ogni processo che abbandona la RC "risveglia"

tutti i processi sospesi affinchè riprovino a verificare ciascuno la

end; proprio condizione B

tradotta in generale dal compilatore in termini di questo tipo

var mutex : semaforo initial(1); Semaforo booleano

synch : semaforo initial(0); Semaforo generalizzato

count : integer initial(0); Numero dei processi sospesi

wait(mutex); entra nella RC

while not B do begin se la condizione non è verificata

count:=count + 1; aumenta il numero dei processi sospesi

signal(mutex); lascia la RC

wait(synch); e resta in attesa del prossimo processo in uscita dalla RC

wait(mutex); rientra nella RC e riverifica la condizione

end;

<sezione critica> Se la condizione è verificata esegui la "sezione critica"

while count>0 do begin Sblocca TUTTI i processi fino ad allora sospesi che non hanno

signal(synch); verificato la B, ora in attesa su "synch", detti "SB"

count:=count - 1;

end;

signal(mutex); lascia finalmente la RC

E' evidente che questa soluzione ha lo svantaggio di favorire continui ingressi/uscite dalla regione critica con conseguenti sospensioni (e quindi cambi di contesto tra processi) ogni volta che la condizione B deve essere verificata: è pertanto una soluzione onerosa, adatta solo se i processi che competono per la regione critica non sono molto numerosi. Si noti inoltre che il ciclo finale sblocca tutti i processi "SB" in attesa sul semaforo synch, ma non agisce su eventuali processi che non siano ancora entrati nel ciclo while not B e che siano in attesa sul semaforo mutex: i primi e i secondi quindi si contendono la risorsa B (risorsa perchè nella fattispecie una condizione va verificata su un dato, e un dato è una risorsa) senza che i processi "SB" abbiano una qualche prelazione, il che invece sarebbe preferibile. Infine, questa soluzione non prevede la possibilità che la condizione B sia verificata dentro la sezione critica, eventualmente uscendone se B non è soddisfatta, come illustrato qui di seguito

Region v DO

begin

<sezione critica - 1 parte>

AWAIT B; Costrutto che non abbiamo approfondito

<sezione critica - 2 parte>

end;

A titolo di esempio, con questo costrutto è possibile riscrivere il gestore di N risorse equivalenti condivise

var gestore : shared record

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

liberi : 0..N initial(N); Qui un intero sostiuisce un semaforo (risorse)!

end;

procedure Acquisizione(var k:1..N); Procedura di acquisizione della Risorsa k-esima

var i:0..N;

begin

REGION gestore WHEN liberi>0 DO

begin

i:=0;

repeat

i:=i+1;

until libero[i]=true;

libero[i]:=false;

liberi:=liberi - 1;

k:=i;

end;

end;

procedure Rilascio(k:1..N); Procedura di rilascio della Risorsa k-esima

begin

REGION gestore DO

begin

libero[k]:=true;

liberi:=liberi + 1;

end;

end;

oppure le procedure relative al problema produttori e consumatori con buffer multiplo

var mailbox : shared record

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

testa : 1..N initial(0);

coda : 1..N initial(0);

messaggi : 0..N initial(0); Qui un intero sostituisce 2 semafori

(messaggio_disponibile, spazio_disponibile)!

end;

procedure Invio(x : T);

begin

REGION mailbox WHEN messaggi<N DO

begin

buffer[coda]:=x;

coda:= (coda + 1) mod N;

messaggi:=messaggi + 1;

end;

end;

procedure Ricezione(var x : T);

begin

REGION mailbox WHEN messaggi>0 DO

begin

x:=buffer[testa]:=x;

testa:= (testa + 1) mod N;

messaggi:=messaggi - 1;

end;

end;

in cui però (una sola variabile ha sostituito due semafori!) produzione e consumo avvengono nella stessa regione critica per cui non può succedere che un processo faccia Invio su un buffer e contemporaneamente un altro processo  faccia Ricezione su un altro, ovvero la mutua esclusione tra produttori e consumatori riduce drasticamente il parallelismo: all'aumentare della facilità di composizione e l'astrazione, si riduce l'efficienza.

Altro costrutto evoluto che consente di costruire un gestore di risorsa è l'oggetto Monitor, che comprende una struttura dati (più in generale una collezione di variabili) usata per rappresentare lo stato di una risorsa, i metodi ad essa associati (procedure che implementano delle operazioni su di essa) ed una sequenza costruttore (che provvede ad inizializzare ad uno stato di partenza la struttura dati). Le regioni critiche condizionali sono come abbiamo visto dispendiose da realizzare nell'ambito dei singoli processi, inoltre le istruzioni che eseguono sulle variabili che formano le risorse condivise sono disperse fra tutti i processi che le utilizzano: per vedere tutti i modi in cui una risorsa viene utilizzata è necessario analizzare il codice dell'intero programma. Un monitor risolve questi due problemi incapsulando sia la risorsa gestore che le operazioni in un unico modulo, consentendo non solo al programmatore di disinteressarsi dell'implementazione della risorsa gestore quando semplicemente la usa (classico della programmazione a oggetti), ma anche di non preoccuparsi di come impostare l'uso esclusivo della risorsa gestore quando programma il monitor che la implementa (una evoluzione rispetto ad un "oggetto" classico). Un'istanza del costrutto monitor è quindi un oggetto, condiviso tra più processi, i cui metodi di accesso sono definiti entry,  ovvero tali che lo stesso monitor garantisca essi vengano eseguiti in mutua esclusione con le altre procedure entry e gli altri processi: non più di un processo per volta può accedere al monitor eseguendo una qualunque procedura entry; inoltre, laddove un processo penetrato nel monitor si blocchi in attesa di verificare una condizione, il costrutto deve prevedere meccanismi che facciano fuoriuscire il processo bloccato garantendo agli altri processi la possibilità di entrare nel monitor. In linea teorica nulla vieta di innestare i monitor - per cui si potrebbe avere all'interno di una procedura entry per un monitor A la chiamata ad una procedura entry per un monitor B - ma in pratica ciò può produrre grossi problemi di programmazione, per esempio rendendo inconsistente la struttura dati del monitor (un processo che generasse queste chiamate innestate potrebbe rimanere bloccato sul monitor B bloccando automaticamente anche il monitor A, impedendo anche ad altri processi di accedervi) ed è quindi sconsigliabile.

Nei linguaggi che prevedono il costrutto monitor, è possibile definire un semplice gestore di risorsa

type gestore : monitor; Definizione del tipo "gestore" di risorsa

utilizzando il costrutto Monitor

var occupato : boolean; Stato della risorsa gestita

cond : condition; Variabile di tipo "condition" (di cui parleremo)

procedure entry Acquisizione;

begin

if occupato then wait(cond); Verifica della "condizione di sincronizzazione" e, in caso di

insuccesso, il processo corrente viene sospeso

occupato:=true; altrimenti la risorsa viene settata come IN USO

end;

procedure entry Rilascio;

begin

occupato:=false; Dopo l'uso la risorsa viene settata come LIBERA

signal(cond); e un processo sospeso viene "risvegliato"

end;

begin

occupato:=false; Inizializzazione dello stato della risorsa

end;

e dichiararne una istanza con l'istruzione

var allocatore : gestore; Allocatore è un Monitor (come quello dichiarato qui sopra)

La variabile X : condition usata nel generico oggetto monitor è una variabile strutturata - solo concettualmente associata ad una "condizione", nella fattispecie di sincronizzazione, che può dipendere invece da variabili del monitor (come nel caso banale in esempio) e del singolo processo, e costituita da un semaforo e da una coda (a sua volta costituita almeno da due puntatori) associata al semaforo - su cui operano fondamentalmente due procedure, denominate wait(X) e signal(X), che operano come i nomi suggeriscono in modo molto simile alle omonime procedure già viste con i semafori: se un processo esegue all'interno del monitor la chiamata wait(X), esso esprime la volontà incondizionata (in realtà una tale chiamata è tipicamente conseguenza della verifica di una "condizione", come abbiamo visto, effettuata aldifuori della variabile condition di sospendersi e di accodarsi alla coda contenuta nella variabile condition X, in attesa che il semaforo cui la predetta coda è associata diventi verde; viceversa, se un processo esegue all'interno del monitor la chiamata signal(X), esso produce il risveglio del primo processo in coda sullo stesso semaforo oppure, in assenza di processi in coda, non ha alcun effetto. In verità, quando un processo P esegue (tipicamente dopo aver terminato di operare sul monitor) una signal(X) (e per poterlo fare deve trovarsi ancora DENTRO il monitor) e risveglia un processo Q che era in attesa, si pone un problema: sia P che Q vengono a trovarsi "dentro" il monitor, contro il vincolo che impone il limite massimo di un solo processo per volta attivo su di esso. Tale problema viene risolto dal monitor in questi termini: prima di riattivare il processo Q dentro il monitor, il processo sbloccante P viene a sua volta sospeso ed espulso temporaneamente dal monitor (la sua prosecuzione potrebbe infatti alterare ancora una volta la condizione di sincronizzazione e compromettere la ripartenza di Q), con la condizione però che, quando Q avrà terminato di operare sul monitor, P avrà una priorità di rientro (per un eventuale ulteriore utilizzo) su altri eventuali processi in attesa; il monitor tornerà libero per altri processi solo quando P e Q abbiano ciascuno o lasciato il monitor, avendo terminato le operazioni su di esso, o invocato una wait(X), finendo dunque sospeso.

L'implementazione di un monitor attraverso l'utilizzo di costrutti classici prevede la definizione di un certo numero di strutture dati e procedure, tra le quali la Entry, cui viene passata come funzione callback una generica procedura entry (da eseguire in mutua esclusione con le altre) e che contiene una sequenza di entrata nel monitor e una sequenza di uscita che salvaguarda l'esecuzione in mutua esclusione. Chiaramente ogni processo che intendesse accedere alla risorsa gestore incapsulata nel monitor, eseguirà una sequenza di operazioni preceduta da una chiamata ad una qualche procedura di Acquisizione e seguita da una analoga chiamata a qualche procedura di Rilascio: nella prima ci sarà la verifica di una qualche condizione di sincronizzazione ed in caso di insuccesso una wait(cond:condition), nella seconda - dopo il rilascio della risorsa gestore - ci sarà una signal(cond:condition).

Il modello proposto di seguito è noto come Modello di Hoare e contiene la definizione di ciascuna delle 3 procedure fondamentali citate

type condition : record;

sem : semaforo initial(0); Semaforo booleano

tail : coda; Coda (implementata in un modo qualunque)

end;

var mutex : semaforo initial(1); Semaforo booleano

cond : condition; Variabile condition

sospesi : integer initial(0); Contatore associato a "cond.tail"

urgent : semaforo initial(0); Semaforo generalizzato

urgenti : integer initial(0); Contatore associato alla coda del semaforo "urgent"

procedure Entry(proc : procedure);

begin

wait(mutex); Fase di Entrata nel Monitor

proc; Esecuzione della procedura "entry"

if urgenti>0 then signal(urgent); Fase di Uscita dal Monitor

else signal(mutex);

end;

procedure Wait(cond : condition);

begin

sospesi:=sospesi + 1; Il processo "auto-bloccante" predisponde la sua

sospensione incrementando il numero dei sospesi

if urgenti>0 then signal(urgent); se è sospeso almeno un processo "urgente"

else signal(mutex); lo risveglia, altrimenti lascia il monitor

wait(cond.sem); si sospende

sospesi:=sospesi - 1; riattivatosi si cancella dai sospesi

end;

procedure Signal(cond : condition);

begin

urgenti:=urgenti + 1; Il processo ha finito di usare il monitor e, prima di

proseguire, si organizza per risvegliare, se ce ne sono, il

primo processo in attesa di entrare nel monitor: per fare questo

però si deve sospendere, concedendosi comunque la prelazione su

altri processi in attesa per un suo eventuale nuovo rientro nel

monitor, per cui non diventerà solo un "sospeso" ma un "sospeso

con risveglio urgente" e si accoderà al semaforo "urgent". In

previsione di queste operazioni incrementa il numero dei

"sospesi con risveglio urgente"

if sospesi>0 then begin Se è sospeso almeno un processo

signal(cond.sem); risveglia il primo "sospeso"

wait(urgent); e si sospende come "urgente"

end;

urgenti:=urgenti - 1; riattivatosi si cancella dai "sospesi urgenti"

end;

da utilizzare, come già descritto, nell'ambito di uno schema che preveda procedure di Acquisizione e Rilascio

procedure entry Acquisizione;

begin

if <condizione> then wait(cond);

<annotazione di risorsa occupata>

end;

procedure entry Rilascio;

begin

<annotazione di risorsa rilasciata>

signal(cond);

end;

procedure Gen_Operation; Generica procedura di accesso e manipolazione della Risorsa

begin

Acquisizione;

<Uso della risorsa>

Rilascio;

end;

Se si impone l'ulteriore condizione semplificativa e non eccessivamente restrittiva che la signal(X) sia sempre eseguita come ultima operazione di ogni procedura (in pratica un processo la chiama prima di terminare), il modello descritto si semplifica notevolmente, non essendo più necessaria la gestione dei processi "sospesi urgenti"

procedure Entry(proc : procedure);

begin

wait(mutex);

proc;

signal(mutex);

end;

procedure Wait(cond : condition);

begin

sospesi:=sospesi + 1;

signal(mutex);

wait(cond.sem);

sospesi:=sospesi - 1;

end;

procedure Signal(cond : condition);

begin

if sospesi>0 then signal(cond.sem);

end;

E' possibile infine definire una wait(cond:condition, p:integer) cosiddetta condizionale, che consenta cioè al processo che la chiama - per sospendersi - di accodarsi alla cond.coda non in ultima posizione bensì nella p-esima, con p crescente in base alla priorità: la signal(cond:condition) risveglierà quindi sempre il processo a massima priorità comportandosi da vero e proprio scheduler (in questo caso esiste però il rischio che un processo a priorità minima attenda indefinitamente

Vediamo due possibili applicazioni del costrutto monitor

Esempio 1: Gestione di un disco a teste mobili

Un disco rigido è costituito da una serie di dischi impilati sui quali leggono e scrivono testine mobili, su ogni disco è possibile distinguere tracce circolari e concentriche ciascuna divisa in settori, un blocco di settori consecutivi su una medesima traccia è chiamato cluster e l'insieme di tutte le tracce omologhe su ogni disco costituisce un cilindro. Affinchè si possa leggere/scrivere uno specifico settore occorre che la giusta testina si posiziona su quel settore, il che avviene in un certo tempo di accesso, somma del cosiddetto tempo di seek nel quale le testine operano uno spostamento radiale, del cosiddetto tempo di latenza nel quale i dischi ruotano fino alla posizione corretta e del tempo di selezione della traccia, nettamente trascurabile (essendo non di natura meccanica bensì elettronica

Un gestore della risorsa disco potrebbe essere concepito per ottimizzare uno di questi tempi al fine di ridurre globalmente il tempo richiesto per una sequenza più o meno lunga di accessi del tutto casuali al suddetto disco. Una possiblità è quella di ottimizzare il tempo di seek, minimizzando quindi gli spostamenti radiali delle testine, e un semplice algoritmo di scheduling prevede che, in base alla traccia attuale dell'ultimo accesso, si privilegi lo spostamento delle testine sulla traccia (fra le tracce destinazioni in attesa di essere visitate) più vicina a quella corrente, a prescindere dalla direzione di percorrenza attuale (ascendente o in salita se verso il centro dei dischi, discendente o in discesa se verso la periferia dei dischi). Un'alternativa è una variante del cosiddetto algoritmo dell'ascensore, nel quale si servono prima - nell'ordine naturale di avvicinamento - tutte le destinazioni che è possibile visitare continuando lo spostamento nell'attuale direzione di percorrenza, dopodichè si inverte la direzione di marcia e si applica nuovamente lo stesso criterio; con riferimento al disco però, diversamente da quel che accade con un ascensore  - e qui è la variante - la richiesta relativa alla traccia appena visitata viene sospesa e soddisfatta solo alla prossima inversione di marcia, viceversa si potrebbe avere uno starvation dovuto alle continue richieste relative sempre alla stessa traccia (l'ascensore aprirebbe e chiuderebbe continuamente le sue porte senza muoversi

Un intuitivo gestore del disco che usi questo secondo algoritmo di scheduling può essere definito utilizzando il costrutto monitor nel modo seguente

type gestore_testine : monitor; Definizione del tipo "gestore" di risorsa

utilizzando il costrutto Monitor

var occupato : boolean; Stato della risorsa gestita

posizione : integer; "

direzione : (giu, su); "

direzione_su, direzione_giu : condition;

procedure entry Acquisizione(destinazione : integer);

begin

if occupato then begin

if (direzione=giu AND destinazione=posizione)

OR (destinazione>posizione) then wait(direzione_su, destinazione);

else wait(direzione_giu, N-destinazione);

end;

occupato:=true;

posizione:=destinazione;

end;

procedure entry Rilascio;

begin

occupato:=false;

if direzione=su then

if <direzione_su.coda NON vuota> signal(direzione_su);

else begin

direzione:=giu;

signal(direzione_giu);

end;

else

if <direzione_giu.coda NON vuota> signal(direzione_giu);

else begin

direzione:=su;

signal(direzione_su);

end;

end;

begin

occupato:=false;

posizione:=0;

direzione:=su;

end;

procedure Operation(destinazione : integer);

begin

Acquisizione;

<Lettura/Scrittura attraverso l'esecuzione del driver del disco>

Rilascio;

end;

Si noti che il secondo parametro della wait( , ) è la distanza della destinazione dalla posizione corrente e rappresenta banalmente la priorità di accesso della destinazione stessa.

Esempio 2: Problema dei lettori-scrittori

Soluzione analoga a quella già presentata nell'Esempio 4 d'uso dei semafori privati, con il problema dello starvation risolto alternando lettori e scrittori secondo la regola: se un lettore sopraggiunge mentre uno scrittore sta scrivendo oppure altri lettori stanno leggendo MA c'è già in attesa almeno uno scrittore, esso entrerà in attesa e subentrerà al primo scrittore (precedendo eventuali altri scrittori in attesa) insieme a tutti i lettori che si saranno messi in attesa fino a quel momento. Qui usiamo il costrutto monitor

var buffer : T; Definizione del buffer

type lettori_scrittori : monitor; Definizione del tipo "gestore" di risorsa

utilizzando il costrutto Monitor

var occupato : boolean; Stato della risorsa gestita

lettori : integer; "

sospesi_l, sospesi_s : condition;

procedure entry Inizio_Lettura;

begin

if occupato or <sospesi_s.coda NON vuota> then wait(sospesi_l);

lettori:=lettori + 1;

signal(sospesi_l); Questa istruzione produce la liberazione "a cascata"

dei lettori sospesi da parte di quelli attivi (se la coda

è vuota "signal" non ha effetto)

end;

procedure entry Fine_Lettura;

begin

lettori:=lettori - 1;

if lettori=0 then signal(sospesi_s);

end;

procedure entry Inizio_Scrittura;

begin

if occupato or lettori>0 then wait(sospesi_s);

occupato:=true;

end;

procedure entry Fine_Scrittura;

begin

occupato:=false;

if <sospesi_l.coda NON vuota> then signal(sospesi_l);

else signal(sospesi_s);

end;

begin

occupato:=false;

lettori:=0;

end;

procedure Lettura(var x : T);

begin

Inizio_Lettura;

x:=buffer;

Fine_Lettura;

end;

procedure Scrittura(x : T);

begin

Inizio_Scrittura;

buffer:=x;

Fine_Scrittura;

end;