SLEEP E WAKEUP

Per risolvere i problemi di mutua esclusione tra processi, l’algoritmo di Peterson blocca i processi in attesa attiva (busy waiting).

Per evitare di sprecare tempo di CPU, si è pensato di definire delle funzioni di libreria capaci di “bloccare” o “addormentare” un processo che non può procedere nella sezione critica, e di “svegliarlo” quando può entrare. Un esempio è quello di definire una coppia di chiamate di sistema, sleep (senza parametri, blocca il processo che la chiama) e wakeup (risveglia un processo che era bloccato, passato come parametro).

Vediamo allora come usare queste primitive in un problema “classico” dei processi concorrenti:

PRODUTTORE E CONSUMATORE con buffer limitato

Un processo produttore genera dati, che sono destinati a un processo consumatore. Per consentire ai due processi di lavorare in parallelo, il produttore inserisce i dati in un buffer (limitato) da cui il consumatore li preleva. I processi operano su un dato alla volta.

• Il produttore ed il consumatore devono accedere al buffer in mutua esclusione;
• Ogni elemento viene prelevato una sola volta;
• Gli elementi sono prelevati nello stesso ordine in cui sono stati inseriti;
• Il produttore non può inserire elementi in un buffer pieno;
• Il consumatore non può prelevare elementi dal buffer vuoto;
• Non si verifica deadlock.

La figura illustra in grigio la zona di buffer "piena" di oggetti prodotti, il produttore inserisce alla posizione in, il consumatore preleva dalla posizione out.

Precisazioni:

si può definire un problema generalizzato con m produttori ed n consumatori; la soluzione non sarebbe molto diversa;

il buffer va pensato "circolare", con i due puntatori in e out che lo percorrono in senso orario, e con l’ultima posizione "adiacente" alla prima

Possibile soluzione data con sleep e wakeup:

#define N 100        /* num. posizioni nel buffer */
int count =0;        /* num. elementi nel buffer  */

void producer (void)
{ int item;

while (TRUE) {       /* ripetere per sempre */
item= produce();     /* produci item */
if (count == N) sleep();/* buffer pieno, sospenditi */
insert(item);        /* inserisci nel buffer circol. */
count ++;            /* aumenta n. elementi */
if (count ==1) wakeup (consumer); /* se il buffer era vuoto */
}

}

void consumer (void)
{ int item;

while (TRUE) {       /* ripetere per sempre */
if (count == 0) sleep();/* buffer vuoto, sospenditi */
item= remove();      /* prendi dal buffer item */
count --;            /* diminuisce n. elementi */
if (count == N-1) wakeup (producer); /* se il buffer era pieno */
consume (item);      /* consuma item */
}

}

Purtroppo, questa NON è una soluzione, perché c’è ancora un problema di corsa critica su count.

Supponiamo che il buffer sia vuoto e che il consumatore abbia visto che count è 0. Per l’interleaving, prima che sia chiamata la sleep(), il consumatore viene sospeso e viene eseguito il produttore, che inserisce item, aumenta count e chiama wakeup. In realtà, il consumatore non ha ancora chiamato sleep, cosa che però fa immediatamente appena riattivato. Ma il produttore non chiamerà mai più wakeup: il suo risveglio è in un certo senso andato perduto.

Si potrebbe pensare di risolvere il problema memorizzando in un bit se una wakeup è arrivata prima che il processo da svegliare abbia chiamato sleep, in modo da risvegliarlo istantaneamente, ma in situazioni che coinvolgono più processi un bit non basterebbe. Ci vuole quindi un meccanismo diverso per risolvere questo problema.

SEMAFORI

Definizione dovuta a Dijkstra (1965): sostanzialmente si tratta di usare un contatore di tipo intero (non un solo bit) associato al meccanismo sleep-wakeup, in modo da memorizzare un numero arbitrario positivo di risvegli, uno 0 se nessun risveglio è stato dato finora, e un numero negativo se ci sono uno o più processi in attesa di risveglio.

Definizione: Un semaforo è una variabile intera s che, dopo l’inizializzazione, può essere modificata solo attraverso due operazioni primitive, P(s) e V(s). Il semaforo è quindi definito come un tipo di dato (astratto).

Talvolta le operazioni sono chiamate (più comprensibilmente!) down(s) e up(s). Possiamo pensarle “come se” fossero implementate come segue (ma il loop di attesa non sarà un busy waiting, il processo verrà sospeso)

down(s): while (s<=0); /* loop di attesa */
s--;

up(s): s++;

Le assegnazioni a s sono eseguite in modo atomico e se s>0 tutta down(s) e`eseguita in modo atomico.

Il nome "semaforo" suggerisce l’idea di bloccare un processo "sul rosso", ovvero quando eseguendo down si trova s <= 0.

MUTUA ESCLUSIONE CON SEMAFORI

Vediamo innanzi tutto che basta un semaforo s per garantire che un certo numero N di processi entrino a turno nella rispettiva regione critica:

#define N 5 /* numero processi */
semaphore s=1;

Process Pi /* da ripetere con i=1..5*/
{
while () /* per sempre */
{ down (s);
crit(i);
up(s);
non_critical(i);
}
}

Tutti questi processi partono contemporaneamente e sono eseguiti “per sempre”. Questo programma gode delle seguenti proprietà:

• vi è al più un processo alla volta nella regione critica;
• nessun processo è ritardato all'infinito;
• non vi è deadlock.

Questo ovviamente purché crit(i) termini sempre!

Verifichiamo cosa accade con un

Esempio:

Supponiamo di avere 5 processi P1...P5 che condividono una regione critica controllata dal semaforo s. Osserviamo cosa accade per una sequenza di richieste al semaforo.

Condizione iniziale:

tutti i processi attivi;
semaforo inizializzato a 1;
nessun processo in coda

• P1 esegue down(s); è s=0; coda vuota;
• P1 esegue la propria regione critica;
• P3 esegue down(s) è s=-1; P3 sospeso; coda = (P3)
• P5 esegue down(s) è s=-2; P5 sospeso; coda = (P3, P5)
• P2 esegue down(s) è s=-3;  P2 sospeso; coda = (P3, P5, P2)
• P1 esegue up(s)è s=-2; P3 attivo; coda = (P5, P2)
• P4 esegue down(s) è s=-3; P4 sospeso; coda = (P5, P2, P4)
• P3 esegue la propria regione critica;
• P3 esegue up(s)è s=-2; P5 attivo; coda = (P2, P4)

.... eccetera

Possiamo allora dare finalmente la soluzione al problema del produttore e consumatore con buffer limitato.

Produttore e consumatore con i semafori:

Il programma gestisce il buffer in modo circolare, esplicitando le operazioni per inserimento e rimozione, ed usa tre semafori:

mutex: per la mutua esclusione;
empty: conta il n. di posizioni piene (blocca il produttore se non c’è posto)
full: conta il n. posizioni vuote (blocca il consumatore se non ci sono elementi)

int buffer [N];
int in,out,count;
semaphore full=0;
semaphore empty=n; /* ci sono n pos.da riempire*/
semaphore mutex=1; /* mutua esclusione */

void producer (void)
{int nextp;

while (TRUE)
{nextp= produce ();/*codice per produrre nextp*/
down(empty); /*coda per producer*/
down(mutex); /*coda per entrambi*/
buffer[in]=nextp;
in=(in++)%N; /* pos. seguente modulo N */
up(mutex);
up(full);
}

}

void consumer (void)
{ int nextc;

while(TRUE)
{down(full); /*coda per consumer*/
down(mutex); /*coda per entrambi*/
nextc=buffer[out];
out=(out++)%N; /* pos. seguente modulo N */
up(mutex);
up(empty);
consume (nextc); /*codice per consumare nextc*/
}

}

Osserviamo che il semaforo mutex serve per garantire la mutua esclusione tra produttore e consumatore, mentre i due semafori empty e full servono per sincronizzare i due processi (cioè per garantire che non si verifichino situazioni non gestibili)

Esercizio proposto:

Cosa cambia se considero N produttori e M consumatori?

Implementazione di semafori

Un semaforo oltre a mantenere un valore intero deve anche poter gestire una "coda" di processi sospesi:

struct semaforo {
int cnt;
process_queue sl;
}

In generale in un sistema saranno definiti un certo numero di semafori, per cui si avrà una array di semafori. Per il semaforo s, avremo allora cnt[s] e sl[s].

Inizializzazione:

cnt [s] >=0; sl[s] = empty;

Naturalmente si deve evitare un busy wait nell’implementazione di down e up:

down (s);
{ lock(s);
cnt[s]--;
if (cnt[s]<0) disable (s);
unlock(s);
}

up(s);
{ lock(s);
cnt[s]++;
if (cnt(s)<=0) enable (s);
unlock(s);
}

Le due funzioni enable e disable operano sulla coda dei processi sl[s] ed eseguono al loro interno la unlock. Le operazioni lock e unlock si possono implementare con una istruzione TSL.

Osserviamo che per come viene gestita la coda del semaforo, essa contiene k processi quando il valore di cnt[s] e` -k.

Per sospendere un processo nella coda di s, si usa

disable(s);
{ rimuovi il processo dalla coda READY;
inserisci il processo nella coda sl[s];
passa al prossimo processo;
}

Per riattivare uno dei processi che erano sospesi, si usa

enable(s);
{ estrai un processo dalla coda sl[s];
inserisci il processo nella coda READY;
passa al prossimo processo;
}

SINCRONIZZAZIONE CON SEMAFORI

Abbiamo due processi, P1 e P2: voglio che l'istruzione s2 di P2 sia eseguita solo dopo il termine dell'istruzione s1 di P1.

Abbiamo bisogno di un semaforo:

semaphore synch=0;

Possibili errori con i semafori:

non usando i semafori correttamente si può violare la mutua esclusione.

Esempio 1: Inizializzazione non corretta:

Semaforo di mutua esclusione inizializzato a 0 (= nessun processo entrerà mai nella regione critica) oppure inizializzato a 2 (= possono entrare due processi contemporaneamente nella regione critica).

Esempio 2: "dimenticare" una up:

cosa succede se...?

Esempio 3:"scambiare" down e up:

cosa succede se...?

I semafori sono sufficienti a risolvere i problemi di mutua esclusione e sincronizzazione tra processi concorrenti, ma non è semplice programmare con essi: sono quindi stati proposti due meccanismi più agevoli al programmatore, i monitor e lo scambio di messaggi. Il secondo è adatto ai sistemi distribuiti, dove non si possono quindi usare zone di memoria condivise, ma è comunque utilizzabile anche su un processore in multiprogrammazione.

MONITOR

Sono stati ideati da C.A.R.Hoare e P.Brinch Hansen (1974-75), e richiedono un linguaggio di programmazione che li preveda (per i semafori, basta avere a disposizione una libreria di funzioni, chiamabile ad esempio dal C ed integrata con il sistema operativo, che realizzi up e down).

Idea: garantire l’integrità di una struttura dati condivisa permettendo l’accesso soltanto attraverso le procedure del monitor (tipi di dato astratto).

Definizione: un monitor è un tipo di dato costituito da:

• una struttura dati condivisa: contiene le informazioni utilizzate dai processi concorrenti e le variabili di stato per garantire la sincronizzazione dei processi che usano il monitor;

• una operazione di inizializzazione della struttura;

• un insieme di procedure di monitor dette entry che sono l’unico modo per accedere dall’esterno alla struttura condivisa; esse utilizzano le variabili di stato ed eventuali altre variabili e procedure locali. Le entry sono eseguite in modo mutuamente esclusivo;

• variabili di condizione, condition variables, per garantire la sincronizzazione.

Dichiarazione: (Concurrent Pascal)

type monitor_name = monitor
var "strutture dati del monitor";

procedure entry proc_name1("parametri");
body_1;

...

procedure entry proc_nameN("parametri");
body_N;

begin
"inizializzazione";
end;

Istanziazione:

var M: monitor_name; "viene eseguita l’inizializzazione"

Utilizzo (chiamata) delle procedure entry:

M.proc_namei("valori dei parametri");

Sincronizzazione:

I processi possono sincronizzarsi (quindi venire messi in coda in attesa di un evento) attraverso una condition variable dichiarata:

var x: condition;

all’interno delle procedure di monitor posso usare:

• wait(x); sospende il processo che aveva eseguito la procedura entry e rilascia la mutua esclusione;

• signal(x); riattiva un processo sospeso su x.

ATTENZIONE:

wait e signal sono diverse dalle operazioni up e down su semafori:

• signal(x) non viene memorizzata se nessun processo e’ in coda sulla condition variable x (quindi "va persa");
• up(s) su semaforo incrementa il "contatore" cnt[s] di 1 (quindi il semaforo puo’ diventare "verde" per eventuali processi che arriveranno in futuro);

Quando un processo esegue wait(x), esso viene messo in una coda associata ad x e rilascia la mutua esclusione.

Vi è anche la mutua esclusione sulle procedure entry, quindi una ulteriore coda di ingresso al monitor. In generale le code di accesso al monitor saranno "FIFO", ma potrebbe non essere sempre vero.

In certe implementazioni del monitor è presente anche una funzione queue(x); restituisce TRUE se ci sono processi in coda sulla condition variable x, altrimenti FALSE.

Differenza con sleep e wakeup:

Tanto signal quanto wakeup NON memorizzano nulla se nessun processo è in attesa, quindi si potrebbe pensare che … neppure i monitor possano funzionare!

In realtà il fatto che vi sia comunque la mutua esclusione sulle entry garantisce che se il consumatore sta per eseguire wait, nessun produttore potrà inviare signal prima del completamento di tale wait (e quindi non si perderà tale signal).

PRODUTTORE E CONSUMATORE con buffer limitato

type bounded_buffer = monitor
var buffer: array[0..n-1] of item;
in,out: 0..n-1; size: 0..n; nonempty,nonfull: condition;

procedure entry put (x: item);
begin
if size=n then wait(nonfull);
buffer[in]:=x;
in:=(in+1) mod n;
size:=size+1;
signal(nonempty);
end;

procedure entry get (var x:item);
begin
if size=0 then wait(nonempty);
x:= buffer[out];
out:=(out+1) mod n;
size:=size-1;
signal(nonfull);
end;

begin "inizializzazione"
size:=0; in:=0; out:=0;
end "della dich. Monitor"

Nota: in questo esempio dopo la signal non ci sono altre istruzioni. Questo pero’ potrebbe non essere sempre vero, per altri monitor!

program producer_consumer;
type bounded_buffer= monitor " vedi sopra"

var buf: bounded_buffer;
num:integer;

process producer;
begin
while true do
"produce x"
buf.put(x);
endwhile
end;

process consumer;
begin
while true do
buf.get(x);
"consuma x"
endwhile
end;

begin
”partono produttore e consumatore”
end.

IMPLEMENTAZIONE DI UN MONITOR (Hoare)

L'accesso al monitor e la sincronizzazione al suo interno sono regolate da semafori.

E' necessario un primo semaforo per regolare l'accesso al monitor in mutua esclusione, sia esso mutex, inizializzato a 1.

La coda associata a mutex è di tipo FIFO e si accede effettivamente al monitor eseguendo

down(mutex);

Per ogni condition variable occorre implementare una coppia di wait/signal. Esse richiedono:

• un semaforo condsem, inizializzato a 0, che corrisponde alla condizione su cui il processo intende sospendersi;
• una variabile intera condcount, inizializzata a 0, che conta quanti processi sono in attesa sulla coda della condizione.

Implementazione di wait e signal su una condizione:

wait ("condition")
begin
condcount:=condcount+1;
up(mutex); /* per far entrare altri processi */
down(condsem); /* per sospendersi */
condcount:=condcount-1; /* quando si risveglia */
end;

signal("condition")
begin
if condcount>0 then
up(condsem) /* processo da svegliare */
else
up(mutex); /* per far entrare altri processi */
end;

Nota:

Questa signal presuppone che il processo che la esegue intenda anche uscire dal monitor. Infatti ne risveglia un altro, sospeso sulla condition variable o all'ingresso, su mutex.

Questa implementazione è detta monitor di tipo monitor.

In molti casi (forse tutti quelli che servono!) le signal sono effettivamente le ultime operazioni delle procedure di monitor.

Potrebbero però esistere problemi in cui dopo una signal il processo deve eseguire altre operazioni, quindi l'implementazione sopra vista non può essere sempre valida. In tal caso si usano altre implementazioni del monitor, che sono però più complesse del monitor di tipo monitor.

Ad es. il monitor di tipo mediatore realizza una coda ulteriore per i processi sospesi dopo una signal ma che devono ancora eseguire operazioni prima di uscire dal monitor. I monitor di tipo mediatore avranno quindi bisogno di un altro semaforo ed un contatore ad esso associato per regolare la fase di "uscita".

SCAMBIO DI MESSAGGI

I processi concorrenti devono poter comunicare e sincronizzarsi ANCHE senza poter disporre di una memoria condivisa (es. sistemi distribuiti, oppure scelta deliberata dei progettisti del SO: Minix ad esempio).

Per questo si usa il meccanismo di scambio messaggi (message passing), tramite

• send (destination, message)
• receive (source, message)

col significato rispettivamente di inviare e ricevere un messaggio al/dal primo parametro (caso particolare, ricevere da ANY, cioè chiunque).

Problemi:

• Queste funzioni bloccano il chiamante fino al completamento dell’invio/ ricezione? Potrebbe essere un tempo molto lungo, che dipende da cosa sta facendo l’altro processo coinvolto.
• Queste funzioni come fanno a conoscere i “nomi” dei processi, e come garantiscono l’autenticità del mittente/ destinatario?
• Queste funzioni mandano un acknowledgement (conferma)? Potrebbe essere importante se ad es. la rete è poco affidabile.
• Quante volte viene copiato il messaggio? Dall’utente al kernel, al buffer del periferico,…

PRODUTTORE E CONSUMATORE

Nel sistema “circolano” N messaggi (dove N è l’analogo della dimensione del buffer per le altre implementazioni).

Il consumatore inizialmente invia N messaggi vuoti al produttore, il quale ogni volta che “produce qualcosa” preleva un messaggio vuoto e invia un messaggio “pieno” cioè contenente l’informazione prodotta.

Se il produttore è più veloce, si blocca in attesa di un messaggio vuoto dopo averne spediti N pieni; il consumatore man mano che consuma rinvia messaggi vuoti. Se il consumatore è più veloce, sta inattivo in attesa di un altro messaggio pieno.

Il buffer in pratica è interno al SO ed ha dimensione massima N messaggi (da entrambi i lati dei due processi, quindi eventualmente su macchine diverse).

#define N 100 /* n.slot nel buffer */

void producer (void)
{ int item;
message m; /* buffer messaggi */
while (TRUE) {

item = produce(); /* genera un item */
receive (consumer, m); /* riceve msg vuoto, attende se non c'e' */
build_msg (m,item); /* mette item nel messaggio m */
send (consumer, m); /* invia msg */

}
}

void consumer (void)
{ int item, i;
message m;
for (i=0; i<N; i++) send (producer, m); /* manda N msg vuoti */
while (TRUE) {

receive(producer, m); /* prende il msg conten.item */
item= extract(m); /* estrae item dal msg */
send (producer,m); /* invia msg vuoto */
consume (item); /* gestisce l'item */

}
}

Vediamo infine altri due problemi tipici della programmazione concorrente. Possono essere implementati con semafori, monitor, messaggi.

PROBLEMA DEI LETTORI E SCRITTORI

Si ha un data base condiviso tra lettori e scrittori.

• I processi lettori si limitano a consultare i dati senza modificarli (possono quindi accedere concorrentemente tra loro);
• I processi scrittori modificano i dati (quindi devono accedere in modo mutuamente esclusivo tra loro e con i lettori).

La mutua esclusione non consente la concorrenza ai lettori, facendo così perdere il parallelismo possibile. Quindi la lettura deve avvenire al di fuori dalla sezione critica, ma deve avere un opportuno prologo (ed epilogo) per garantire le condizioni di mutua esclusione con gli scrittori. La scrittura invece deve avvenire in una sezione critica.

typedef int semaphore;
semaphore mutex = 1; /* mutua esclusione su rc */
semaphore db = 1; /* accesso al database */
int rc =0; /* numero processi lettori */

void reader (void)
{
while (TRUE) { /*per sempre */

down(mutex); /* accedi a rc */
rc = rc +1;
if (rc == 1) down (db); /* il primo lettore... */
up (mutex); /* rilascia rc */
read_database(); /* lettura NON in mutua escl. */
down(mutex); /* accedi a rc */
rc = rc-1;
if (rc == 0) up (db); /* l'ultimo lettore ... */
up(mutex); /* rilascia rc */
use_data(); /* regione non critica */

}
}

void writer (void)
{
while (TRUE) /* per sempre */

think_data (); /* regione non critica */
down (db); /* accesso esclusivo */
write_database(); /* aggiornamento */
up(db); /* rilascia accesso esclusivo */

}
}

Osservazioni:

• posso avere starvation degli scrittori (cioè sempre rc>1);
• se uno scrittore è nella propria regione critica e ho n lettori in attesa, allora il primo è sospeso su db, i rimanenti n-1 sono sospesi su mutex;
• la up(db) nel processo scrittore riattiva uno dei processi in coda:
  • se è un lettore allora, sbloccando mutex, riattiva tutti i lettori;
    se è uno scrittore è l’unico che può procedere;
• non è possibile forzare una delle due alternative con questo programma, su vari testi sono presentate delle varianti che “forzano” la riattivazione di uno scrittore se presente, o meno.

PROBLEMA DEI CINQUE FILOSOFI

Questo problema è stato inventato da Dijkstra nel 1965: immaginiamo cinque filosofi che vivono nella stessa casa, ciascuno alternando periodi in cui mangia a periodi in cui pensa. Il cibo è costituito da spaghetti, ed i filosofi sono capaci di nutrirsi solo se hanno a disposizione due forchette. Nella casa ce ne sono però solo cinque, e la tavola è apparecchiata come in figura:

Ogni filosofo, quando ha fame, cerca di prelevare sia la forchetta di sinistra, sia quella di destra, nell’ordine, e se una tale forchetta non c’è, si blocca in attesa che il collega finisca di mangiare.

#define N 5
void philosopher (int i)
{
while (TRUE) {

think();
take_fork(i);
take_fork((i+1)%N);
eat();
put_fork(i);
put_fork((i+1)%N);

}
}

Potrebbe però succedere che tutti e cinque contemporaneamente prelevino la prima forchetta, e nessuno possa poi mangiare: questa è una situazione di deadlock.

Può essere evitata facendo in modo che, se la seconda forchetta non è disponibile, il filosofo posi anche la prima, attenda un certo tempo e poi le riprenda entrambe. In caso estremamente sfortunato, tutti e cinque potrebbero però svolgere contemporaneamente un ciclo di prelevo-poso-attendo- prelevo nuovamente eccetera con le stesse temporizzazioni. In tal caso, i filosofi fanno “qualcosa” (posano e prendono le forchette) ma all’atto pratico non riescono a nutrirsi. Questa situazione è detta starvation, che in inglese significa appunto morte per fame.

Potremmo mettere un semaforo ed imporre che prima di acquisire le forchette i filosofi facciano down. In questo modo però mangerebbero uno alla volta, sprecando tre delle cinque forchette.

La soluzione seguente

• Funziona per un numero qualsiasi N di filosofi e forchette, consentendo di nutrirsi contemporaneamente al numero massimo possibile;
• Usa uno stato per memorizzare se il filosofo sta pensando (THINKING), mangiando (EATING) oppure è affamato (in attesa di forchette: HUNGRY)
• Individua i vicini del filosofo i con le macro LEFT e RIGHT
• Usa una array di semafori s[N]
• Ogni filosofo esegue la funzione philosopher come main del processo, mentre chiama le altre tre funzioni normalmente

#define N 5 /* n. filosofi */
#define LEFT (i+N-1)%N /* n. filosofo a sin di i */
#define RIGHT (i+1)%N /* n. filosofo a destra di i */
#define THINKING 0 /* il filosofo pensa */
#define HUNGRY 1 /* il filosofo vuole mangiare */
#define EATING 2 /* il filosofo mangia */
typedef int semaphore;
int state [N]; /* contiene lo stato di ciascun filosofo */
semaphore mutex=1; /* mutua esclusione */
semaphore s[N]; /* un semaforo per filosofo */

void philosopher (int i) /* i= numero del filosofo, 0.. N-1 */
{
while (TRUE) { /* per sempre */

think (); /* pensa */
take_forks(i); /* prende 2 forchette oppure si blocca */
eat(); /* buon appetito */
put_forks(i); /* posa le 2 forchette */

}
}

void take_forks(int i) /* i= numero del filosofo, 0.. N-1 */
{

down (mutex); /* entra nella regione critica */
state[i]= HUNGRY;
test(i); /* cerca di ricuperare le due forchette*/
up(mutex); /* esce dalla regione critica */
down (s[i]); /* si blocca se non ha preso le forchette */

}

void put_forks(int i) /* i= numero del filosofo, 0.. N-1 */
{

down(mutex); /* entra nella reg. critica) */
state[i]= THINKING;
test(LEFT); /* controlla se il vicino ha fame */
test(RIGHT); /* controlla l'altro vicino */
up(mutex); /* esce dalla regione critica */

}

void test (int i) /* i= numero del filosofo, 0.. N-1 */
{

if(state[i]==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING)
{ state[i]=EATING;
up (s[i]); }

}