Reti e problematiche di Rete - unibg.it · 6 Reti e problematiche di rete - Enrico Cavalli -...

1

Reti e problematiche di Rete

I Processi Concorrenti

Enrico Cavalli

Anno Accademico 2008-2009

I problemi con i processi concorrenti

2

Reti e problematiche di rete - Enrico Cavalli - Università di Bergamo 3

I processi concorrenti

• La concorrenza tra processi avviene secondo diverse modalità. Si parla infatti di competizione nell’accesso alle risorse come nel caso di due amici che litigano per la restituzione di un prestito e di cooperazione nell’evoluzione dei processi come nel caso della produzione dei cedolini paga degli stipendi eseguiti da due processi, uno dei quali effettua il calcolo della paga e l’altro la stampa

• La cooperazione tra processi può avvenire con la condivisione di risorse , per esempio mediante la condivisione di un’area della memoria centrale per processi concorrenti su un singolo calcolatore, oppure tramite comunicazione, con lo scambio di messaggi, come avviene ai processi che interagiscono in un sistema distribuito.

• La competizione nell’accesso alle risorse può portare allo stallo dei processi mentre la cooperazione tra processi concorrenti può causare l’inconsistenza dei dati elaborati.

• I problemi di concorrenza tra processi si presentano sia con i processi di sistema che con i processi degli utenti. La concorrenza è importante sia per la comprensione dei sistemi operativi sia nello sviluppo di applicazioni con linguaggi che supportano il multi threading.



do ProduceDatiCliente; eseguito da P0ScriveDatiNelBuffer; eseguito da P0

LeggeDatiDaBuffer; eseguito da P1StampaEstrattoConto; eseguito da P1

while (EsistonoClienti);

Buffer

Dato

P0 P1

DatiClienti

EstrattoConto

/* ------------------------------------------------ -------------------* P 0 esegue P1 esegue* ------------------------------------------------- ------------------ */

do doProduceDatiCliente; LeggeDatiDaBuffer;ScriveDatiNelBuffer; StampaEstrattoConto;

while (EsistonoClienti); while (EsistonoClienti);

Il comportamento

desiderato

La produzione degli estratti conto con due processi cooperanti

3



typedef struct { int NumeroConto;double Saldo; } contoCorrente;

contoCorrente Dati0, Dati1, Buffer;/*------------------------------------------------- ----------------

* Per effetto dell’accesso concorrente può succeder e che *-------------------------------------------------- --------------- */

Buffer.NumeroConto = Dati0.NumeroConto; eseguito da P0Dati1.NumeroConto = Buffer.NumeroConto; eseguito da P1Dati1.Saldo = Buffer.Saldo; eseguito da P1Buffer.Saldo = Dati0.Saldo; eseguito da P0

L’elaborazione concorrente può portare a malfunzionamenti per: accesso concorrente alle informazioni e differente velocità di esecuzione dei processi

5784 5783

3225.15

5783

3225.15

NumeroConto

Saldo 215.32

Dati 0 Cliente B

BufferCliente A

Dati1Cliente A

5784 5784

215.32

5784

3225.15

NumeroConto

Saldo 215.32

Dati 0 Cliente B

BufferCliente B

Dati1Cliente ?



La differente velocità di esecuzione dei processi può portare alla perdita di informazioni o alla duplicazione delle informazioni.

• Se P0 è più veloce di P1 può succedere che P0 pone nel buffer i dati di C prima cheP1 ha letto quelli di B, che non saranno mai stampati.

• Se P1 è più veloce di P0, può accadere che P1, dopo avere stampato i dati di A,acceda al buffer prima che P0 lo abbia aggiornato con i dati di B. In tale caso P1stamperebbe i dati di A due volte.

I due problemi principali della programmazione concorrente sono:

- Accesso concorrente alle informazioni

- Sincronizzazione dei processi

4



Per risolvere il problema dell’accesso concorrente alle informazioni bisogna impedire che mentre P0 modifica il buffer, P1 lo acceda per leggerlo. In pratica questo significa che le due procedure ScriveDatiNelBuffer, LeggeDatiDaBuffer devono essere eseguite in mutua esclusione:

Le attività dei due processi devono anche essere sincronizzate per evitare che un estratto conto non sia stampato o che sia stampato più volte:

• P0 può scrivere nel buffer solo se il buffer è vuoto. In pratica: P0 può scrivere nelbuffer solo dopo che P1 lo ha letto svuotandolo.

• P1 può leggere il buffer solo se il buffer è pieno. In pratica: P1 può leggere il buffersolamente dopo che P0 ha scritto nel buffer riempiendolo.

Le porzioni di codice P0, P1, .. , Pn, sono eseguite in mutua esclusione se l’esecuzione di Pi può iniziare solo se nessuna Pj, i ≠≠≠≠ j, è in esecuzione.



/* ------------------------------------------------ ----------------------* Processo P 0 Processo P 1

* ------------------------------------------------- --------------------- */do do

ProduceDatiCliente; AttendiBufferPieno;AttendiBufferVuoto; LeggeDatiDaBuffer;ScriveDatiNelBuffer; BufferVuoto;BufferPieno; StampaEstrattoConto;

while(EsistonoClienti); while(EsistonoClienti);

/* ------------------------------------------------ -------------* Programma EstrattoConto* ------------------------------------------------- ------------ */

void main()begin

typedef enum {vuoto,pieno} stato;stato StatoBuffer;contoCorrente Buffer; void P0(); void P1();StatoBuffer = vuoto;parbegin P0(); P1(); parend;

end;

parbegin P0(); P1(); parend ;

P0 e P1 sono eseguite in parallelo

5



/* ------------------------------------------------ ------------------------* Processo P0* ------------------------------------------------- ----------------------- */

void P0()begin

do ProduceDatiCliente; while (StatoBuffer == pieno) endwhile; attende: buffer == vuoto

ScriveDatiNelBuffer;StatoBuffer = pieno; buffer vale pieno

while (EsistonoClienti);end;

/* ------------------------------------------------ -----------------------* Processo P1* ------------------------------------------------- ---------------------- */

void P1()begin

dowhile (StatoBuffer == vuoto) endwhile; attende: buffer == pieno

LeggeDatiDaBuffer;StatoBuffer = vuoto; buffer vale vuotoStampaEstrattoConto;

while (EsistonoClienti);end;

Soluzione ottenuta con: - Attesa attiva- Processi forzati alla stessa velocità


Accesso alle regioni critiche

/* ------------------------------------------------ ----------------------* Conteggio dei posti liberi * ------------------------------------------------- --------------------- */

LOAD R1,Posti Posti = Posti - 1; SUB R1,UNO

STORE R1,Posti

Istruzioni Processo R1 Posti

. . . 50LOAD R1,posti P 0 50 50. . . -- schedulato P 1, salvato R1(50)LOAD R1,posti P 1 50 50SUB R1,uno P 1 49 50STORE R1,posti P 1 49 49. . . –- riprende P 0, ripristinato R1(50)SUB R1,uno P 0 49 49STORE R1,Posti P 0 49 49. . .

Esecuzione concorrente di due processi che eseguono: Posti = Posti - 1;

50

P0: Posti--

P1: Posti--

6


Corse critiche

Per risolvere il problema delle corse critiche servono due istruzioni speciali:

EntraSezioneCritica; EsciSezioneCritica;

da inserire immediatamente prima e dopo la sezione critica che ne garantiscono l’esecuzione in mutua esclusione.

/* ------------------------------------------------ --------------------* Processo P0 Processo P1* ------------------------------------------------- ------------------- */

do doArrivaSpettatore; ArrivaSpettatore; EntraSezioneCritica; EntraSezioneCritica;

Posti = Posti - 1; Posti = Posti - 1;EsciSezioneCritica; EsciSezioneCritica;

forever ; forever ;


Corse critiche

/* ------------------------------------------------ -------------------------* Programma ContaPostiLiberi* ------------------------------------------------- ------------------------ */

void main()begin

int Posti;typedef enum {P0, P1} turno ;turno Processo;void P0(); void P1();Posti = 400; Processo = P0;parbegin P0(); P1(); parend ;

end; /* ------------------------------------------------ -------------------------

* Processo P0 Processo P1* ------------------------------------------------- ------------------------ */

void P0() void P1()begin begin

do doArrivaSpettatore; ArrivaSpettatore; while (Processo==P1) endwhile ; while (Processo==P0) endwhile ;

Posti = Posti - 1; Posti = Posti - 1; Processo = P1; Processo = P0;

forever ; forever ;end; end;

Soluzione corretta ma non accettabile

operativamente perché . . .

7

La mutua esclusione in software


La mutua esclusione in software

Una buona soluzione al problema della mutua esclusione richiede che siano rispettate certe condizioni:

- la mutua esclusione fra i processi deve essere garantita;

- un processo fuori dalla sezione critica non deve impedire né ritardare l’accesso alla sezione critica da parte degli altri processi che vi vogliono accedere;

- non si possono fare ipotesi sulla velocità relativa dei diversi processi;

- i processi rimangono nella loro sezione critica per un tempo limitato;

- non ci deve essere stallo nè ritardo indefinito.

Consideriamo diversi approcci alla soluzione del

problema della mutua esclusione

8


Mutua esclusione in software

/* ------------------------------------------------ ----------------------- ** Programma MutuaEsclusione1 ** ------------------------------------------------- ---------------------- */

void main() begin

boolean Occupata;void P0(); void P1(); Occupata = false;parbegin P0(); P1(); parend ;

end;// ------------------------------------------------ ------------------------


. . . . . . while (Occupata) endwhile ; while (Occupata) endwhile ;Occupata = true; Occupata = true;

<Sezione Critica> <Sezione Critica>Occupata = false; Occupata = false; . . . . . .

end; end;

La mutua esclusione non è

garantita



/* ------------------------------------------------ --------------------- ** Programma MutuaEsclusione2 ** ------------------------------------------------- -------------------- */

void main() begin

boolean VoglioEntrare[2];void P0(); void P1(); VoglioEntrare[0] = VoglioEntrare[1] = false;parbegin P0(); P1(); parend ;

end;//------------------------------------------------- -----------------------


. . . . . .VoglioEntrare[0] = true; VoglioEntrare[1] = true;while (VoglioEntrare[1]) while (VoglioEntrare[0]) endwhile ; endwhile ;

<Sezione Critica> <Sezione Critica>VoglioEntrare[0] = false; VoglioEntrare[1] = false ;. . . . . .

end; end;

C’è pericolo di stallo

9



/* ------------------------------------------------ --------------------- ** Programma MutuaEsclusione3 ** ------------------------------------------------- -------------------- */

void main() begin

boolean VoglioEntrare[2];void P0(); void P1(); VoglioEntrare[0] = VoglioEntrare[1] = false;parbegin P0(); P1(); parend ;

end;//------------------------------------------------- -----------------------


. . . . . .VoglioEntrare[0] = true; VoglioEntrare[1] = true;while (VoglioEntrare[1]) while (VoglioEntrare[0])

VoglioEntrare[0]=false; VoglioEntrare[1]=false; AspettaCasuale(); AspettaCas uale();VoglioEntrare[0]=true; VoglioEntrare[1]=true;

endwhile ; endwhile ;<Sezione Critica> <Sezione Critica>

VoglioEntrare[0] = false; VoglioEntrare[1] = false ;. . . . . .

end; end;

C’è pericolo di ritardo indefinito



Nel 1965 l’olandese Dekker ha proposto un algoritmo per risolvere via software il problema della mutua esclusione. L’algoritmo di Dekker è piuttosto complicato e difficile da comprendere. Solo nel 1981 Peterson ha proposto una nuova soluzione molto piùsemplice di quella proposta da Dekker. Il fatto che ci siano voluti ben 16 anni per scoprire un nuovo semplice algoritmo per risolvere via software il problema della mutua esclusione lascia comprendere come siano difficili da risolvere i problemi che si incontrano con i processi concorrenti.

L’algoritmo di Peterson , che combina le idee di ContaPostiLiberi e MutuaEsclusione2 è, per così dire, un algoritmo basato sulla gentilezza perché, in caso di accesso contemporaneo alla sezione critica, entrambi i processi cedono il passo all’altro.

Si noti che anche l’algoritmo di Peterson, semplice ed elegante, fa uso del ciclo di attesa attiva e, di conseguenza, non è molto efficiente.

10



/* ------------------------------------------------ ---------------------- ** AlgoritmoDiPeterson ** ------------------------------------------------- --------------------- */

void main() begin

boolean VoglioEntrare[2];int Turno;void P0(); void P1();VoglioEntrare[0] = VoglioEntrare[1] = false; Turno = 1;parbegin P0(); P1(); parend ;

end;//------------------------------------------------- -----------------------void P0() void P1()begin begin

. . . . . .VoglioEntrare[0] = true; VoglioEntrare[1] = true;Turno = 1; Turno = 0;while (VoglioEntrare[1] AND while (VoglioEntrare[0] ANDTurno==1) endwhile ; Turno==0) endwhile ;

<Sezione Critica> <Sezione Critica>VoglioEntrare[0] = false; VoglioEntrare[1] = false;. . . . . .

end; end;

Se P0 è nella propria sezione critica allora non può esserlo P1

Supporti Hardware per la programmazione concorrente

11


Supporti hardware

La ragione del fallimento della mutua esclusione nel programma MutuaEsclusione1 èdovuto al fatto che le coppia di istruzioni:

while (Occupata) endwhile ;Occupata = true;

non è eseguita in modo atomico. Se fosse possibile eseguire quella coppia di istruzione in modo atomico MutuaEsclusione1 funzionerebbe correttamente.

Ci sono due modi per eseguire le due istruzioni atomicamente:

- disabilitare le interruzioni prima di eseguire le istruzioni che devono essere eseguite in modo atomico e riabilitarle subito dopo. La tecnica della disabilitazionedelle interruzioni è fortemente sconsigliata per tre ragioni: è pericoloso autorizzare un processo a disabilitare le interruzioni; il calcolatore funziona in modo inefficiente perché il sistema operativo non può attuare le proprie politiche di ottimizzazione; non funziona nei sistemi multi processore (e questo taglia la testa al toro)

- usare istruzioni macchina (se ci sono) che controllano il valore di un dato e lo modificano nella medesima istruzione


L’istruzione TSL

In molti processori è presente l’istruzione macchina TSL, acronimo di Test and Set Lock:TSL Registro, Blocco

che trasferisce in un registro il contenuto della parola di memoria Blocco e, nella medesima istruzione, memorizza in Blocco un valore intero diverso da zero: il comportamento di TSL può essere descritto come quello della funzione TestSet che: restituisce il valore del proprio argomento X (1) e assegna a X il valore true (2)

/* ------------------------------------------------ ---------------- ** TestSet ** ------------------------------------------------- --------------- */

boolean TestSet( boolean &X) begin

Boolean SalvaX;SalvaX = X;X = true; return SalvaX;

end;

true

X

X12

TestSet(X):

12


Mutua esclusione con TSL

/* ------------------------------------------------ ----------------------- ** MutuaEsclusioneTestSet ** ------------------------------------------------- ---------------------- */

void main() begin

boolean Blocco;Blocco = false;parbegin P0(); P1(); parend;

end;//------------------------------------------------- -----------------------


. . . . . .while (TestSet(Blocco)) endwhile; while (TestSet(Blo cco)) endwhile;<Sezione Critica> <Sezione Critica>Blocco = false; Blocco = false;. . . . . .

end; end;

La soluzione è generalizzabile a N processi concorrenti e opera corretta-mente sia in ambiente mono che multi processore. Purtroppo usa un ciclo di attesa attiva: sarebbe meglio sospendere un processo e poi svegliarlo

Attesa / risveglio: I Semafori

13


I semafori

I semafori sono variabili pensate per gestire i meccanismi di collaborazione tra processi concorrenti. Un processo può fermarsi in attesa di ricevere un segnale inviato da un altro processo. Per inviare e ricevere segnali un processo dispone delle due primitive Wait e Signal :

Signal : invia un segnale a un semaforo che lo riceve e lo memorizza Wait : ricevere i segnali inviati a un semaforo: se il segnale non è stato inviato il processo è sospeso in attesa della trasmissione; se invece il segnale è già stato trasmesso il processo lo riceve e prosegue nella esecuzione.

I semafori possono essere pensati come oggetti composti da una variabile intera e una coda di processi. Sono creati assegnando un valore opportuno alla variabile intera e possono essere manipolati con le sole primitive Wait e Signal che non sono interrompibili.

typedef struct { int Count;CodaDiProcessi Coda;} semaforo;

semaforo S (=1);

La variabile intera S.Count conta i segnali inviati al semaforo S; la coda S.Coda èinizialmente vuota

S.Count= 1 S.Coda è vuota


I semafori

Una Wait eseguita da un processo P sul semaforo S decrementa S.Count e, se il valore decrementato è minore di 0, blocca P e lo inserisce nella coda associata al semaforo S.

L’esecuzione di Signal su un semaforo S incrementa S.Count e, se S.Coda non èvuota, sveglia uno dei processi in attesa nella coda associata a S.

Si dice che Wait consuma i segnali inviati a un semaforo, mentre Signal invia segnali a un semaforo. Count tiene conto del numero di segnali inviati a un semaforo e del loro utilizzo

P2

-3

P1 P0

S

S.Count = -3Tre processi in S.Coda

14


I semafori

/* ------------------------------------------------ ---------------------- ** Wait ** ------------------------------------------------- --------------------- */

void Wait(semaforo &S)begin

S.Count = S.Count - 1; if (S.Count < 0 )

InserisciProcesso(S.Coda);BloccaProcesso;

endif; end;

/* ------------------------------------------------ ---------------------- ** Signal ** ------------------------------------------------- --------------------- */

void Signal(semaforo &S)begin

processo P;if (S.Count < 0)

P = EstraiProcesso(S.Coda);AttivaProcesso(P);

endif; S.Count = S.Count + 1;

end;

Usa un segnale inviato al semaforo

Se non ci sono segnali da usare, il processo P che ha attivato la Wait è

fermato e inserito in S.Coda

Se la coda non è vuota, attiva un processo

Conta i segnali inviati al semaforo


I semafori

La figura mostra che la variabile Count di un semaforo S:

Per Count ≥≥≥≥ 0 indica il numero di segnali di sveglia che sono stati inviati a S con Signal(S) e non sono stati ancora ricevuti con Wait(S) ;

Quando Count < 0 indica quanti sono i processi nella coda di S, in attesa di ricevere un segnale di sveglia.

Con i semafori si risolvono i problemi di mutua esclusione e sincronizzazione

P

-11 0

P: Wait(S) P: Wait(S)

Q: Signal(S)Q: Signal(S)

15


L’accesso in mutua esclusione a una porzione di codice si ottiene usando un semaforo S inizializato a 1 e facendo precedere la regione critica con Wait(S) e segnalando l’uscita dalla regione critica con Signal(S)

Mutua esclusione con i semafori

/* ------------------------------------------------ ----------------- ** MutuaEsclusione con i semafori ** ------------------------------------------------- ---------------- */

void main()begin

semaforo Mutex(Count=1);void P0(); void P1();parbegin P0(); P1(); parend;

end;/* ------------------------------------------------ ----------------- */


do do. . . . . .Wait(Mutex); Wait(Mutex);SezioneCritica; SezioneCritica;Signal(Mutex); Signal(Mutex);. . . . . .

forever; forever;end; end;

Mutua Esclusione : il semaforo è inizializzato a 1

EntraCritica �� Wait (Mutex)

EsciCritica � Signal (Mutex)


Se P0 è il primo processoche riesce a eseguire

Wait(Mutex) . . .

Mutua esclusione con i semafori

1 0P0

Wait(Mutex)

P1

-10 P1

Wait(Mutex)Se anche P1 cerca di accedere alla sezione

critica . . .

P1

0-1P0

Signal(Mutex)Quando P0 lascia lasezione critica P1 è

svegliato e prosegue . . .

16


Sincronizzazione con i semafori

Per sincronizzare due processi su un evento si usa un semaforo S inizializzatoa 0. Il processo che rileva l’evento esegue Signal(S) e l’altro processo si sincronizza sull’evento con Wait(S).

/* ------------------------------------------------ ----------------- ** Sincronizzazione con i semafori ** ------------------------------------------------- ---------------- */

void main()begin

semaforo S(Count=0);void P0(); void P1();S.Count= 0; parbegin P0(); P1(); parend;

end;/* ------------------------------------------------ ----------------- */


AzioniPreEvento; RilevaEvento;Wait(S); Signal(S); AzioniDopoEvento; AltreOperazioni;

end; end;

Sincronizzazione : il semaforo èinizializzato a 0

Wait : per sincronizzarsi sull’evento

Signal : per rilevare l’evento


Implementazione dei semafori

/* ------------------------------------------------ ----------------- ** Implementazione di Wait(S) ** ------------------------------------------------- ---------------- */

void Wait(semaforo &S)begin

while (TestSet(Occupata)) endwhile;S.Count = S.Count – 1;if (S.Count < 0)

BloccaProcesso; InserisciProcesso(S.Coda);

endif;Occupata = false;

end;/* ------------------------------------------------ ----------------- *

* Implementazione di Signal(S) ** ------------------------------------------------- ---------------- */

void Signal(semaforo &S)begin

while (TestSet(Occupata)) endwhile;if (S.Count < 0)


endif;S.Count = S.Count + 1;Occupata = false;

end;

AttivaProcessoRealizzata richiedendo i servizi del

sistema operativo per operare il cambiamento di stato del processo

boolean Occupata

BloccaProcessoRealizzata richiedendo i servizi del

sistema operativo per operare il cambiamento di stato del processo

Realizzate nel nucleo. In

alternativa . . .

17

Problemi caratteristici con i semafori


Il problema del produttore consumatore

DatiProduttore

Buffer

Consumatore

il produttore deve essere sicuro di riempire un buffer vuoto;

il consumatore deve essere sicuro di svuotare un buffer pieno.

/* ------------------------------------------------ ----------------- ** Programma ProduttoreConsumatore ** ------------------------------------------------- ---------------- */

void main()begin

semaforo Prelevato(Count=1);semaforo Depositato(Count=0);

string Buffer;void Produttore(); void Consumatore();parbegin Produttore; Consumatore; parend;

end;

Count = 1 : Via libera al produttore

Count = 0 : Blocca il consumatore

18


Il problema del produttore consumatore

/* ------------------------------------------------ -----------------* Produttore: si sincronizza sull’evento Prelevato e rileva * l’evento Depositato* Consumatore: si sincronizza sull’evento Depositat o e rileva * l’evento Prelevato* ------------------------------------------------- ---------------- */

void Produttore() void Consumatore()begin begin

string Dato; string Dato;do do

Produce(Dato); Wait( Depositato );Wait( Prelevato ); Dato = Buffer; Buffer = Dato; Signal( Prelevato );Signal( Depositato ); Consuma(Dato);

while (CiSonoDati); while (CiSonoDati);end; end;

Prelevato.Count = 1 : Via libera al produttore

Depositato.Count = 0 : Blocca il consumatore


Produttore consumatore con un buffer circolare

Produttore Consumatore

Buffer

xxxxxxxxxxxxxxxxxx

xxxxxx

0

1

2

3

4

5

6

7

8

9

NextOut

NextIn

string Buffer[10];

NextOut=(NextOut+1)% N;

NextIn=(NextIn+1)% N;

/* ------------------------------------------------ ----------------- ** Programma BufferCircolare ** ------------------------------------------------- ---------------- */

void main()begin

const N = ...; string Buffer[N];int NextIn(=0), NextOut(=0);semaforo Pieno(Count=N)semaforo Vuoto(Count=0);void Produttore(); void Consumatore();parbegin Produttore(); Consumatore(); parend;

end;

Pieno permette di inserire N dati nel buffer prima di fermare il produttore

Vuoto blocca subito il consumatore

19



/*------------------------------------------------- ---------------------------*/



Produce(Dato); Wait(Vuoto);Wait(Pieno); Dato = Buffer[NextOut];

Buffer[NextIn] = Dato; NextOut = (NextOut+1) % N;NextIn = (NextIn+1) % N; Signal(Pieno);

Signal(Vuoto); Consuma(Dato);


Le corse critiche si possono avere solo se NextIn = NextOut cioè in caso di buffer vuoto oppure di buffer pieno. Supponiamo che il buffer sia pieno, per esempio perché il consumatore è fermo: allora Pieno.Count = 0 e il produttore non può accedere alla sezione critica. Se invece il buffer è vuoto si ha: Vuoto.Count = 0 e il consumatore si ferma prima di accedere alla sezione critica per effetto di Wait(Vuoto) .

Pieno.Count = N via libera N volte al produttore

Vuoto.Count = 0 blocca subito il consumatore

NextIn = NextOut = 0



/* ------------------------------------------------ ------------------------ ** Programma ProduttoriConsumatori ** ------------------------------------------------- ----------------------- */

void main()begin

const N = ...; string Buffer[N]; int NextIn, NextOut ;semaforo Pieno(Count=N), Vuoto(Count=0), Mutex(Coun t=1);void Produttore(1); void Produttore(2); ... void Con sumatore(1); ... parbegin

Produttore(1); Produttore(2); .. ; Consumatore(1); Consumatore(2); .. ; parend;

end;/* ------------------------------------------------ ------------------------- */

void Produttore(i) void Consumatore(i)begin begin


Produce(Dato); Wait(Vuoto);Wait(Pieno); Wait(Mutex);Wait(Mutex); Dato = Buffer[NextOut];

Buffer[NextIn] = Dato; NextOut = (NextOut+1)%N;NextIn = (NextIn+1)%N; Signal(Mutex);

Signal(Mutex); Signal(Pieno);Signal(Vuoto); Consuma(Dato);


Attenzione: se ci sono più consumatori e/o più produttori l’accesso al buffer e l’aggiornamento dei puntatori devono avvenire in mutua esclusione. Si introduce il semafori Mutexinizializzato con Mutex.Count = 1

20


Il problema dei lettori e degli scrittori

AreaDati

Scrittore

Lettore

Lettore

Scrittore

Scrittore

Un insieme di processi accedono a dati condivisi, un file o il record di un file, per esempio. I processi scrittori , inseriscono nuovi dati e/o modificano quelli esistenti, mentre i processi lettori si limitano a leggere i dati, senza modificarli.

- La scrittura dei dati può essere fatta da un solo processo per volta

- La lettura dei dati può essere effettuata da più lettori a condizione che non ci siano processi scrittori che stanno modificando i dati

- Quando uno scrittore accede ai dati nessun lettore o scrittore può accedervi

Sono regole abbastanza naturali e sono lo standard nell’accesso ai dati di un database


Il problema dei lettori e degli scrittori

/* ------------------------------------------------ ----------------- ** Programma LettoriScrittori ** ------------------------------------------------- ---------------- */

void main()begin

int Lettori;semaforo Scrivi(Count=1);semaforo Mutex(Count=1);Lettori = 0; parbegin Lettore(); Lettore(); Scrittore(); parend;

end;/* ------------------------------------------------ ---------------- */

void Lettore()begin

do void Scrittore() Wait(Mutex); begin

Lettori++; do if(Lettori==1)Wait(Scrivi);endif; Wait(Scrivi);

Signal(Mutex); ScriveDati;LeggeDati; Signal(Scrivi);Wait(Mutex); forever;

Lettori--; end;if(Lettori==0)Signal(Scrivi);endif;

Signal(Mutex);forever;

end;

Lettori==1: il primo lettore

Lettori==0: non ci sono più lettori

Priorità ai lettori

Lettori: contatore dei lettori

Scrivi: le operazioni di scrittura devono avvenire in mutua esclusione

Mutex: mutua esclusione nei conteggi

21


Il problema del barbiere che dorme

Il negozio, gestito da un solo barbiere, è dotato di una poltrona da barbiere, ma ci sono un certo numero di sedie per i clienti in attesa. In assenza di clienti il barbiere si accomoda sulla sedia di lavoro e dorme, diversamente il barbiere li serve in ordine di arrivo. I clienti entrano nel negozio e, se ci sono posti a sedere liberi si accomodano, diversamente lasciano immediatamente il negozio

/* ------------------------------------------------ ---------------- ** Programma NegozioDelBarbiere * * ------------------------------------------------- --------------- */

void main()begin

const MaxClienti = ...;int NumClienti;semaforo Mutex(Count=1);semaforo Barbiere(Count=1);semaforo Cliente(Count=0);NumClienti = 0; parbegin

Barbiere(); Cliente(); Cliente(); ... Cliente(); parend;

end;

NumClienti : conta i clienti in attesa

Cliente : riconosce la presenza di clienti

Barbiere : rileva la disponibilità del barbiere

Mutex : mutua esclusione conteggio clienti


Il problema del barbiere che dorme

void Cliente() void Barbiere()begin begin

EntraNelNegozio; AperturaNegozio;Wait(Mutex); do if (NumClienti < MaxClienti) Wait(Cliente);

NumClienti++; Wait(Mutex);Signal(Mutex); NumClienti--;Signal(Cliente); Signal(Mutex); Wait(Barbiere); TaglioCapelli;AccedeAlTaglio; Signal(Barbiere);

else forever;Signal(Mutex); end;

endif;EsceDalNegozio;

end; Anche in questo problema c’è una doppia sincronizzazione tra cliente e barbiere. Il cliente deve segnalare il proprio arrivo e attendere che il barbiere

sia libero. Il barbiere deve segnalare la propria disponibilità e attendere che ci sia un cliente

Se

NumClienti ≥ MaxClientiil cliente lascia il negozio

22

Costrutti linguistici per la concorrenza


Esigenza di costrutti del linguaggio

semaforo Mutex(Count=1);int Posti(=0);

/* ------------------------------------------------ -------------- */void P(int J)begin

. . .Wait(Mutex);

Posti = Posti + 1;Signal(Mutex);. . .

end;

Mutua Esclusione: Semaforo inizializzato a 1

Wait : in ingresso alla sezione critica

Signal : in uscita dalla sezione critica

Cosa succede se erroneamente:

1. Si inizializza Mutex a 0

2. Si omette Signal in uscita dalla sezione critica

3. Si omette Wait in ingresso alla sezione critica

4. Si scambiano Wait con Signal

23


I monitor

monitor NomeMonitorbegin

VariabiliDelMonitor;condition VariabiliCondizione;

/* ------------------------------------------------ ---------------------- */void ProceduraMonitor1( .. )begin . . . end;void ProceduraMonitor2( .. ) begin . . . end;. . .void ProceduraMonitorN( .. )begin . . . end;

/* ------------------------------------------------ ---------------------- */begin

InizializzazioneVariabiliModulo;end;

end;

Il monitor è un costrutto del linguaggio di programmazione con il quale si definisce un modulo software che contiene al proprio interno dati e procedure per manipolarli e codice per inizializzarli, oltre a speciali variabili dette variabili condizione .

Procedure di monitor

Inizializzazioni

Variabili e Variabili Condizione del monitor


I monitor

Variabili e procedure di monitor sono caratterizzate da:

- Le variabili del monitor sono accessibili solo attraverso le procedure di monitor

- Le procedure di monitor sono eseguite in mutua esclusione

- Una sola procedura può essere attiva in un dato momento

- Un processo P è entrato nel monitor quando riesce a eseguire una procedura di monitor.

- Se più processi cercano di entrare contemporaneamente nel monitor uno solo riesce ad accedere al monitor, l’altro è inserito in una coda di attesa abbinata al monitor

- Le variabili di condizione sono manipolabili solo con Wait(Variabile) per sospendere i processi su code abbinate alle variabili e Signal(Variabile) per riattivare i processi in attesa nella coda abbinata alla variabile

- Per richiamare una procedura di monitor si usa la notazione:

NomeMonitor.NomeProcedura(Parametri);I monitor sono stati implementati in alcuni linguaggi tra cui: Java, Concurrent C, Concorrent Pascal e Modula 2.

24


I monitor

A, B sono in attesa su C1

X, Y, Z sono in attesa su C2

Q, R, S sono in attesa di entrare nel monitor

P è nel monitor

Dati del monitor

C1

M

C2

Inizializzazioni

Procedura 1

Procedura 2

Procedura 3

A B

Y ZX

R SQ

P Il monitor è un tipo di dato astratto con due particolari caratteristiche: la presenza delle variabili condizione e il fatto che le procedure di monitor sono eseguite in mutua esclusione.


Mutua esclusione con i monitor

/* ----------------------------------** definizione del monitor Posti ** ----------------------------------*/

monitor Postibegin

int PostiLiberi;/*-----------------------------*/void AssegnaPosto(boolean &Ok)begin

if (PostiLiberi > 0) PostiLiberi--;Ok = true;

elseOk = false;

endif; end;/*-----------------------------*/begin

PostiLiberi = 350;end;

end;

PostiLiberi:

variabile privata di Posti

AssegnaPosto:

procedura del monitor Posti

Inizializzazioni del monitor

/* -------------------------------- ** Il programma Prenotazioni ** -------------------------------- */

void main()begin

monitor Posti;void Cassa();parbegin

Cassa(); ... ; Cassa(); parend;

end; /* -------------------------------- */void Cassa()begin

boolean Eseguito; do

ArrivaSpettatore;Posti.AssegnaPosto(Eseguito);if (Eseguito) ... else ...

endif;forever;

end;

La mutua esclusione si ottiene trasformando tutte le sezioni critiche in procedure di monitor

25


Sincronizzazione con i monitor

Per risolvere problemi di sincronizzazione si usano le variabili condizione e le speciali operazioni Wait e Signal nel seguente modo:

• si introduce E, variabile condizione abbinata all’evento

• la procedura che rileva l’evento lo segnala con l’operazione Signal(E)

• la procedura che si deve sincronizzare sull’evento usa Wait(E) per sospendersi in attesa dell’evento.

Le operazioni Wait e Signal dei monitor differiscono dalle omonime operazioni sui semafori per l’assenza del meccanismo di conteggio dei segnali inviati con Signal :

• Wait ferma sempre il processo che la esegue • Signal(E) cerca sempre di riattivare un processo nella coda associata alla variabile

condizione E. Se la coda associata a E è vuota, il segnale viene perso.



/* ------------------------------------------------ ----------------------- ** Il programma ProduttoreConsumatore ** ------------------------------------------------- ---------------------- */

void main()begin

monitor Buffer; void Produttore(); void Consumatore();parbegin Produttore(); Produttore(); Consumatore(); parend;

end;/* ------------------------------------------------ ------------------- */void Produttore() void Consumatore()begin begin

string Dato; string Dato; do do

Produce(Dato); Buffer.Preleva(Dato);Buffer.Inserisci(Dato); Usa(Dato);


Dato

Produttore

Buffer

Consumatore

Produttore

26



monitor Bufferbegin

string Serbatoio; boolean Pieno;condition Inserimenti, Prelievi; /* ------------------------------------------------ -------------- */void Inserisci(string Dato)begin

if (NOT Pieno) Serbatoio = Dato; Pieno = true; Signal(Prelievi);

elseWait(Inserimenti);

endif; end;/* ------------------------------------------------ -------------- */void Preleva(String &Dato)begin

if (Pieno)Dato = Serbatoio; Pieno = false; Signal(Inserimenti );

elseWait(Prelievi);

endif; end;/* ------------------------------------------------ -------------- */begin Pieno = false; end;

end; // monitor Buffer

Preleva: Se il buffer è pieno preleva un dato, diversamente fermati nella coda della condizione Prelievi

Inserisci: Se il buffer è vuoto deposita il dato diversamente fermati nella coda della condizione Inserimenti

Costrutti linguistici per sistemi distribuiti

27


Scambio di messaggi

I problemi di concorrenza in ambienti distribuiti si possono risolvere mediante lo scambio di messaggi . Le primitive tipiche per realizzare lo scambio di messaggi sono Send e Receive :

Send(Destinazione, Messaggio) Receive(Sorgente, Messaggio)

Send invia un messaggio a un destinatario, mentre Receive serve a ricevere un messaggio da una determinata sorgente: P0 invia un messaggio a un processo P1, mentre P1 riceve un messaggio da P0.

P0 P1

Send(P1,msg) Receive(P0,msg)

Lo scambio di messaggi si può usare nei sistemi distribuiti e negli ambienti mono e multi processore a memoria condivisa. Il canale di comunicazione è una connessione fisica per i sistemi distribuiti, mentre è un’area di memo-ria gestita dal sistema operativo per i sistemi a memoria condivisa.


Messaggi e Mailbox

Si è fatto riferimento all’indirizzamento diretto nel quale mittente e destinatario sono specificati esplicitamente nelle primitive di comunicazione. Un approccio alternativo è quello dell’indirizzamento indiretto secondo il quale i messaggi sono inviati a una struttura dati condivisa da mittente e destinatario detta mailbox (casella postale) o porta. Questo approccio èparticolarmente utile nelle situazioni dove il ricevente deve accettare tutti i messaggi che gli sono stati inviati anche se non conosce i processi mittenti. Questo avviene, per esempio, nel caso di un database server che deve rispondere alle richieste di tutti i processi client.

Lunghezza Messaggio

Dati di Controllo

Priorità

Messaggio

Destinatario

Mittente

Tipo Messaggio

28


Messaggi e Mailbox

I processi spediscono messaggi alle mailbox e li ricevono prelevandoli dalla mailbox . La mailbox memorizza i messaggi in apposite code che sono gestite con diverse modalità, tenendo conto, per esempio, della priorità dei messaggi inviati alla mailbox .

Per esempio: quattro processi client richiedono i servizi a un processo server Sinviando messaggi a una mailbox . Il processo server riceve i messaggi dalla mailbox , esamina le richieste e risponde in modo opportuno. Una mailbox contiene una quantitàfinita di messaggi: conveniamo che se un processo invia un messaggio a una mailboxpiena si ferma in attesa che un processo rimuova un messaggio dalla mailbox .

Mailbox

S

C1

C4

C2

C3

Receive( Mailbox, Msg )

Send( Mailbox, Msg )


Send e Receive

Deve essere prevista una qualche forma di sincronizzazione nella spedizione e ricezione dei messaggi. Per farlo bisogna definire il comportamento di Send e Receiveal momento dell’esecuzione.

• La Send è bloccante se il processo che la esegue si blocca fino a quando il messaggio è stato ricevuto (e ne ha avuto conferma tramite una sorta di “ricevuta di ritorno”). La primitiva Send è invece non bloccante se il processo, dopo avere spedito un messaggio, prosegue nella normale esecuzione.

• Anche la Receive può essere bloccante oppure non bloccante. Si pensi a un processo P che esegue Receive(Q, msg). Nel caso di Receive bloccante , il processo P si ferma in attesa di ricevere il messaggio inviato da Q. Nel caso di Receive non bloccante , si hanno due possibilità: se il messaggio è già stato inviato P lo riceve e prosegue mentre, se Q non ha inviato il messaggio, P prosegue senza ricevere il messaggio. In questo caso, in genere, P emette un messaggio di errore.

• Il caso Send bloccante con Receive bloccante stabilisce una forma di sincronizza-zione stretta tra mittente e ricevente e si parla di rendez-vous (incontro in francese) tra i due processi che rimangono bloccati fino a trasmissione del messaggio avvenuta.

• Il caso Send non bloccante con Receive bloccante è molto diffuso, per esempio, nei processi server dove bisogna rispondere rapidamente alle richieste dei processi client.

29


Sincronizzazione con rendez-vous

/* ------------------------------------------------ -------------* Sincronizzazione con Rendez-vous* ------------------------------------------------- ------------ */



Produce(Dato); Receive(Produttore,Dato);Send(Consumatore,Dato); Consuma(Dato);


Nel caso di Send bloccante con Receive bloccante (rendez-vous ) si stabilisce una forma di sincronizzazione stretta tra mittente e ricevente. In caso di rendez-vous due processi, per esempio un processo produttore e un processo consumatore, si possono sincronizzare nel seguente modo:


Mutua Esclusione con lo scambio di messaggi

/* ------------------------------------------------ ---------------------- ** MutuaEsclusione con lo scambio di messaggi ** ------------------------------------------------- --------------------- */

void main()begin

mailbox Casella;void P0(); void P1();CreazioneMailbox(Casella); Send(Casella, ‘’);parbegin P0(); P1(); parend;

end; /* ------------------------------------------------ ------------------ */void P0() void P1()begin begin

string Msg; string Msg;do do

Receive(Casella,Msg); Receive(Casella,Msg);// SezioneCritica; // SezioneCritica;

Send(Casella,Msg); Send(Casella,Msg);AltroCodice; AltroCodice;


Mostriamo come risolvere i problemi base della programmazione concorrente nel caso di Send non bloccante , Receive bloccante e uso di mailbox .


Mutua Esclusione : Invio di un messaggio nella mailbox

per iniziare

EntraCritica �� Receive

EsciCritica � Send

30


Programmazione concorrentecon lo scambio di messaggi

Soluzione dei problemi base della programmazione concorrente con lo scambio di messaggi: Send non bloccante , Receive bloccante e uso di mailbox .


Per implementare la mutua esclusione con i messaggi si usa una mailbox che contiene un solo messaggio. La porzione di codice che deve essere eseguita in mutua esclusione deve essere delimitata in entrata con una Receive bloccante e in uscita da una Sendnon bloccante inviate a quella casella.

Sincronizzazione con lo scambio di messaggi

Per sincronizzare processi con lo scambio di messaggi si procede nel seguente modo: il processo che rivela l’evento invia un messaggio con Send non bloccante a una mailbox vuota, mentre il processo che si deve sincronizzare sull’evento esegue una Receive bloccante su quella mailbox



/* ------------------------------------------------ ---------------------- ** Sincronizzazione con lo scambio di messaggi ** ------------------------------------------------- --------------------- */

void main()begin

mailbox Casella;void P0(); void P1();CreazioneMailbox(Casella); parbegin P0(); P1(); parend;

end;

/* ------------------------------------------------ ------------------ */


string Msg(=‘ ‘); string Msg(=‘ ’);AzioniPreEvento; RilevaEvento;Receive(Casella,Msg); Send(Casella,Msg);AzioniDopoEvento; AltreOperazioni;

end; end;


P0 rimane bloccato da Receive sino a quando P1

invia un messaggio

31


Esempio: produttore - consumatore

/* ------------------------------------------------ ---------------------- ** Produttore-Consumatore con lo scambio di messa ggi ** ------------------------------------------------- --------------------- */

void main() begin

mailbox Consumato, Prodotto;string Msg;void Produttore(); void Consumatore();CreaMailbox(Prodotto); CreaMailbox(Usato); Send(Usato,‘’);parbegin Produttore(); Consumatore(); parend;

end; /* ------------------------------------------------ ------------------- */



Produce(Dato); Receive(Prodotto, Msg);Receive(Usato,Msg); Dato = Msg;Msg = Dato; Send(Usato,Msg);Send(Prodotto,Msg); Consuma(Dato);


Doppia sincronizzazione

Via libera al produttore

Bloccato il consumatore

Send: Rileva evento

Receive: Si sincronizzasull’evento


Domande(1)

1. I processi P0 e P1 sono eseguiti in parallelo e cooperano come indicato di seguito:

/*------------------------------------------------- -------* P0 esegue P1 esegue*-------------------------------------------------- ------ */

do doProduceDati; EntraCritica;EntraCritica; LeggeBuffer;ScriveBuffer; EsceCritica;EsceCritica; StampaDati;

forever; forever;

L’accesso in mutua esclusione al buffer è garantito? La sincronizzazione è garantita? Cosa può accadere se il processo P0 è più veloce del processo P1?Cosa può accadere se il processo P0 è più lento del processo P1?

2. Quali delle seguenti affermazioni sono vere (V) e quali sono false (F)

- I semafori sono speciali variabili pensate per implementare il meccanismo attesa risveglio fra processi concorrenti

- I semafori sono rappresentabili come un intero e una coda di processi - I semafori sono una struttura normalmente programmabile- La primitiva Wait decrementa la variabile intera del semaforo - Se il contatore di un semaforo vale -5 allora ci sono 4 processi in coda sul semaforo- Se il contatore di un semaforo è >= 0 non ci sono processi in coda su quel semaforo

32


Domande(2)

3. Il valore di Count del semaforo S è 4. Un processo P esegue per tre volte Wait(S) e subito dopo il processo Q esegue due Wait(S). Quali sono lo stato di P e di Q?

4. Il valore di Count del semaforo S è 0. Un processo P esegue Wait(S) e poco dopo il processo Q esegue Signal(S). Quali sono lo stato di P e di Q?

5. Il valore di Count del semaforo S è -2 e il processo P è in attesa nella coda associata ad S. Un processo Q esegue Signal(S). Quali sono lo stato di P e di Q?

6. I processi P e Q competono per accedere a una sezione critica secondo il seguente codice che usa il semaforo Mutex inizializzato a 1.

/* ------------------------------------------------ -------------------------* P Q * ------------------------------------------------- ------------------------ */

. . . . . .Wait(Mutex); Wait(Mutex);

// SezioneCritica; // SezioneCritica;Signal(Mutex); Wait(Mutex);. . . . . .

Commentate la soluzione.Commentate la soluzione nel caso di Mutex inizializzato a 0 ed a 2.


Domande(3)

7. Il processo P si deve sincronizzare con Q attraverso un evento rilevato da Q. Per farlo si usa un semaforo S e il seguente codice: /* ------------------------------------------------ --------------- *

* P Q ** ------------------------------------------------- -------------- */

. . . . . .AzioniPreEvento; RilevaEvento;Wait(S); Signal(S); AzioniDopoEvento; AltreOperazioni; . . . . . .

Commentate la soluzione nel caso si S inizializzato a 0 ed a 1.

8. Nel programma ProduttoreConsumatore si usano: Depositato (Count =0) e Prelevato (Count =1): void Produttore() void Consumatore()begin begin


Produce(Dato); Wait( Depositato );Wait( Prelevato ); Dato = Buffer; Buffer = Dato; Signal( Prelevato );Signal( Depositato ); Consuma(Dato);


Commentate la soluzione. Commentate la soluzione nel caso che i due semafori siano inizializzaticome Depositato (Count =1) e Prelevato (Count =0). Nel programma ProduttoreConsumatore a cosa serve Signal(Prelevato) ?

33


Domande(4)

9. Nel monitor M ci sono due procedure P e Q. Due processi eseguono contemporaneamente M.P e M.Q. Cosa succede?

10. Due processi P e Q si vogliono sincronizzare su un evento E rilevato da P usando la primitiva Sendnon bloccante, Receive bloccante e una mailbox di nome Casella. Per farlo: a. - P esegue Send(Casella , msg) Q esegue Send(Casella, msg)b. - P esegue Send(Casella, msg) Q esegue Receive(Casella, msg) c. - P esegue Receive(Casella, msg) Q esegue Receive(Casella, msg) d. - P esegue Receive(Casella, msg) Q esegue Send(Casella, msg)

11. Due processi P e Q devono accedere in mutua esclusione a una regione critica usando la primitiva Send non bloccante e Receive bloccante e una mailbox di nome Casella che contiene un solo messaggio. Per farlo entrambi i processi circondano la sezione critica:

a. - Con Receive(Casella, msg) prima della regione critica Send(Casella, msg) dopob. - Con Receive(Casella, msg) prima della regione critica Receive(Casella, msg) dopoc. - Con Send(Casella, msg) prima della regione critica Receive(Casella, msg) dopod. - Con Send(Casella, msg) prima della regione critica Send(Casella, msg) dopo


Esercizi(1)

1. I processi P0 e P1, eseguiti in parallelo, sono composti da istruzioni che consideriamo indivisibili.

/*------------------------------------------------- -------* P0 esegue P1 esegue*-------------------------------------------------- ------ */

begin beginA = A + 1; A = A * 3;

end; A = A - 1;end;

Se il valore iniziale di A è 3 quali sono i possibili valori di A dopo l’esecuzione concorrente dei dueprocessi P0 e P1

2. Modificare il programma ContaPostiLiberi (diapositiva 12) in modo che possa funzionare con piùcasse. Naturalmente la soluzione sarà soggetta alle medesime limitazioni del programma originale.

3. Nel programma ContaPostiLiberi si vogliono contare il numero di posti ancora liberi e quello dei posti occupati. Per farlo si usano due variabili Liberi e Occupati che devono essere aggiornate dai processi P0 e P1. Si progettino due possibili soluzioni al problema usando le speciali istruzioni EntraCritica ed EsciCritica. Una delle due soluzioni deve garantire che in ogni momento sia rispettato il vincolo di integrità: Liberi+Occupati = 500 e l’altra che non garantisca questa condizione.

4. Mostrate come sincronizzare due processi con l’istruzione TSL

34


Esercizi(2)

5. Si mostri come risolvere, con i semafori, il problema dell’accesso a due regioni critiche RCX ed RCY da parte dei due processi concorrenti P e Q che interagiscono nel seguente modo: /*------------------------------------------------- ----------------

* P Q *-------------------------------------------------- --------------- */

do doAzioni1_P; Azioni1_Q;RCX_P; RCY_Q;Azioni2_P; Azioni2_Q;RCY_P; RCX_Q;Azioni3_P; Azioni3_Q;

forever; forever;

La regione RCX indica una sezione critica nella quale si accede alla variabile condivisaX mentre RCY indica una sezione critica nella quale si accede alla variabile condivisa Y

6. In alcuni processori è disponibile un’istruzione macchina che scambia il valore di un dato in memoria con quello di un registro. L’istruzione di scambio può essere definita formalmente come:

void Scambia( boolean &X, boolean &Y) begin

boolean Temp; Temp = X; X = Y;Y = Temp;

end;

Mostrate come risolvere il problema della mutua esclusione con l’istruzione Scambia


Esercizi(3)

7. I semafori binari sono semafori nei quali la variabile Count può assumere i soli valori 0 ed 1 e le operazioni Wait e Signal per i semafori binari sono definite da: /* ------------------------------------------------ ------------------------- *

* Wait per i semafori binari ** ------------------------------------------------- ------------------------ */

void Wait( semaforoBinario &S)begin

if ( S.Count == 1 ) S.Count = 0;

elseInserisciProcesso(S.Coda);BloccaProcesso;

endif ; end;

/* ------------------------------------------------ ------------------------- ** Signal per i semafori binari ** ------------------------------------------------- ------------------------ */

void Signal( semaforoBinario &S)begin

processo P;if ( S.Coda è vuota )

S.Count = 1; else


endif ; end;

Descrivete con le vostre parole il comportamento di un semaforo binario e mostrate comeimplementarlo usando i semafori come sono stati definiti nel corso.

35


Esercizi(4)

8. Dopo aver controllato come implementare le procedure Wait e Signal con con TestSet mostrate come realizzarle con Scambia

9. Risolvete l problema presentato nell’esercizio 3 con i semafori

10. Risolvere il problema trattato in EstrattoConto (diapositive 8 e 9) con i semafori

11. Risolvere il problema trattato in ContaPostiLiberi (diapositiva 12) con i semafori

12. Dopo aver controllato come implementare le procedure Wait e Signal con con TestSet mostrate come realizzarle sfruttando le interruzioni

13. Dite per quale ragione è ragionevole implementare i semafori con le interruzioni e in quale situazione è invece impossibile usare le interruzioni per implementare i semafori.

14. Dite se è possibile realizzare Wait e Signal in software e nel caso riteniate sia possibile mostrare come farlo.

15. Un ponte sul quale si può viaggiare in un solo senso per volta, attraversa un fiume in direzione nord-sud. Implementare con i semafori la gestione dell’accesso al ponte secondo le seguenti regole: il passaggio da nord a sud è possibile se sul ponte non ci sono veicoli che viaggiano in senso opposto; il passaggio da sud a nord è possibile solo se il ponte è libero e non ci sono veicoli in attesa nell’altro senso. (Suggerimento: controllate accuratamente il testo e confrontatelo con quello del problema LettoriScrittori)


Esercizi(5)

16. Un ponte molto breve, sul quale passa una sola automobile per volta, attraversa un fiume in direzione nord-sud. Implementare con i semafori la gestione dell’accesso al ponte secondo le seguenti regole: il passaggio da nord a sud è possibile se il ponte è libero; il passaggio da sud a nord è possibile solo se il ponte è libero e non ci sono veicoli in attesa nell’altro senso. In poche parole: senso unico alternato con precedenza ai veicoli da nord a sud.

17. Si consideri un ascensore che trasporta i visitatori a una torre. I passeggeri accedono all’ascensore, in grado di trasportare 50 passeggeri per volta, passando attraverso due tornelli. Raggiunto il numero massimo di visitatori trasportabili i tornelli si bloccano e l’ascensore parte. Risolvete il problema di controllare i tornelli e l’ascensore supponendo un flusso continuo di visitatori

18. Risolvete con i semafori il problema di un processo produttore e un processo consumatore che interagiscono, usando due buffer, secondo lo schema:

/*------------------------------------------------- ----------------* P0 esegue P1 esegue*-------------------------------------------------- --------------- */

do doProduceDati1; LeggeBuffer1;ScriveBuffer1; UsaDati1;ProduceDati2; LeggeBuffer2;ScriveBuffer1; UsaDati1;

forever ; forever ;

36


Esercizi(6)

19. Il problema dei filosofi a tavola ha la seguente formulazione: Ci sono 5 filosofi che vivono assieme e passano il loro tempo pensando o mangiando. Per cibarsi si accomodano a un tavolo circolare apparecchiato con cinque piatti ripieni di spaghetti. Di fianco a ogni piatto c’è una forchetta per magiare la pasta. Quando un filosofo vuole mangiare prende la forchetta alla destra e quella alla sinistra del piatto e mangia. Gestire la situazione con i semafori. Ci sono problemi di mutua esclusione perché la forchetta alla sinistra di un piatto è anche la forchetta alla destra di un altro e di conseguenza due filosofi che si siedono uno di fianco all’altro non possono mangiare contemporaneamente.

semaforo Forchetta[5](Count=1);void Filosofo( int J)begin

doPensa;Wait(Forchetta[J]); Wait(Forchetta([(J+1)%5]);

PrendePosate;Mangia;

DepositaPosate;Signal(Forchetta([(J+1)%5]);Signal(Forchetta[J]);

forever ;end;

La procedura in figura mostra il comportamento di uno dei filosofi in una possibile soluzione che usa un array di semafori inzializzati a 1. Studiate la soluzione è spiegate che non è accettabile perchépuò portare allo stallo.


Esercizi(7)

20. C’è una soluzione al problema dei filosofi a tavola che evita lo stallo: un filosofo prima di impugnare le forchette controlla che siano entrambe disponibili e poi le prende e mangia. Lo schema di soluzione è il seguente: semaforo Mutex(Count = 1);void Filosofo( int J)begin

doPensa; Wait(Mutex);

if (ci sono le posate) PrendePosate; Mangia; DepositaPosate;

endifSignal(Mutex);

forever ;end;

Scrivete il codice completo della soluzione. Per controllare l’esistenza delle posate servirà un arraydi flag per sapere se una posata è libera o in uso. Spiegare perché con la soluzione proposta c’è un solo filosofo alla volta che mangia e c’è il pericolo di ritardo indefinito.

21. Affinate la soluzione proposta nel precedente esercizio in modo che ci sia più di un filosofo che sta mangiando. Per farlo osservate che la mutua esclusione deve riguardare solo il momento nel quale si decide di mangiare e si impugnano le posate e non quando si mangia. Anche in questa soluzione c’è il rischio di ritardo indefinito.

22. Risolvere il problema discusso in EstrattoConto (diapositive 8-9) con i monitor.

37


Esercizi(8)

23. Risolvere il problema dei Lettori/Scrittori (diapositiva 40) con i monitor.

24. Risolvere il problema della salita in ascensore dell’esercizio 17 con i monitor.

25. Risolvere il problema del produttore/consumatore con un buffer circolare usando i monitor.

26. Risolvere il problema discusso in EstrattoConto (diapositive 8-9) con lo scambio di messaggi

27. Risolvere il problema di un processo produttore e un processo consumatore che interagiscono, usando due buffer, secondo lo schema dell’esercizio 18, con lo scambio di messaggi.

28. Risolvere, mediante lo scambio di messaggi, il problema di un processo produttore e un processo consumatore che si scambiano dati per mezzo di un buffer in grado di memorizzare sino a 20 oggetti prodotti.

Reti e problematiche di Rete - unibg.it · 6 Reti e problematiche di rete - Enrico Cavalli -...

Documents

Transcript of Reti e problematiche di Rete - unibg.it · 6 Reti e problematiche di rete - Enrico Cavalli -...