Che materia stai cercando?

Appunti di Sistemi Operativi

Conoscenze e abilità da conseguire
Conoscenza delle problematiche di progetto relative all'organizzazione di sistemi concorrenti. Modelli di riferimento per la sincronizzazione e comunicazione tra processi. Metodologie di analisi e sintesi di sistemi concorrenti.

Programma/Contenuti
1.Protezione e sicurezza

Richiami sulla protezione: modelli, politiche e meccanismi
Sicurezza... Vedi di più

Esame di Sistemi Operativi M docente Prof. A. Ciampolini

Anteprima

ESTRATTO DOCUMENTO

Capitolo 6

Modello a scambio di messaggi

Nel caso i processi non condividano una memoria comune, la comunicazione tra loro può avvenire

solo mediante scambio di messaggi attraverso vari canali. La ricezione, da uno o più canali,

e la sincronizzazione, all’invio e ricezione, costituisce in questo scenario il nuovo problema da

risolvere.

L’aspetto che caratterizza questo modello è l’assenza di possibilità, da parte dei processi, di condividere

risorse: ogni processo potrà solo accedere, in modo esclusivo, alle risorse allocate nella propria memoria

locale, pertanto ogni risorsa del sistema potrà essere acceduta da un solo processo. Nel caso in cui una

risorsa sia necessaria a più processi, si andrà a definire un modello client/server in cui più processi client

richiedono l’accesso alla risorsa all’unico processo server che ne ha accesso esclusivo. Il processo server sarà

quindi il gestore della risorsa.

La modalità di interazione tra i processi avviene solamente attraverso lo scambio di messaggi mediante

un canale di comunicazione. A seconda della direzione del flusso di dati è possibile avere:

• Canali monodirezionali: in cui i dati viaggiano in unica direzione, mittente-destinatrio.

• Canali bidirezionali: usati sia per inviare che ricevere messaggi.

A seconda dei processi in gioco è possibile avere:

1

• Link: canale simmetrico uno-a-uno.

• Port: canale asimmetrico molti-a-uno.

• Mailbox: canale asimmetrico molti-a-molti.

A seconda del tipo di sincronizzazione è possibile avere:

• Comunicazione asincrona: il processo mittente continua la sua esecuzione dopo aver inviato il

messaggio. Il messaggio ricevuto, però, non potrà contenere informazioni che riguardano lo stato del

processo mittente, in quanto quest’ultimo potrà cambiare dopo l’invio. Per questo motivo, si ha un

problema di trade-off tra la capacità espressiva e il grado di concorrenza. Un ulteriore problema è dato

dal fatto che, teoricamente, si avrebbe bisogno di un buffer di capacità illimitata se si volesse mantenere

immutata la semantica asincrona della send. Occorre quindi un supporto a tempo di esecuzione che

provveda a sospendere il processo mittente in caso di buffer pieno (non sempre disponibile).

• Comunicazione sincrona con rendezvous semplice: il primo dei due processi comunicanti che

esegue l’invio o la ricezione si sospende, in attesa che l’altro sia pronto ad eseguire l’operazione duale.

Non è necessario un buffer, in quanto il messaggio può essere inviato solo se il ricevente è pronto per

riceverlo. In questo caso, il messaggio scambiato può contenere informazioni sullo stato attuale del

processo mittente, semplificando la scrittura e la verifica dei programmi.

• Comunicazione sincrona con rendezvous esteso: è simile al modello procedente, con la differenza

che in questa tipologia il processo mittente si ferma fino a che il processo ricevente non conclude

l’operazione richiesta (ciò è anche molto simile ad una chiamata a procedura). La riduzione del

1 Per simmetrico s’intende che da entrambi i lati del canale c’è lo stesso numero di processi.

40

parallelismo è un fattore rilevante in questo modello, ma il punto di sincronizzazione permette un

elevato grado di semplificazione in fase di verifica dei programmi.

Mittente richiesta e Server

Ricevente

dati

... parametri

Client ...

invio_dati(); ... ... accettazione_richiesta();

ricezione_dati(); invio richiesta

attesa ...

chiamata_remota();

invio_ack(); attesa risultati

... invio_risultati();

...

ricezione_ack(); ...

... ACK risultati

(a) (b)

Semplice. Esteso con l’uso di un canale bidirezionale.

Figura 6.1: Modelli di rendezvous.

6.1 Primitive di comunicazione sincrone

6.1.1 Definizione del canale

Come già detto, un canale port è un canale asimmetrico molti-a-uno. La dichiarazione di un canale di questo

tipo avviene nella seguente modalità: Per esempio:

port <tipo> <identificatore>.

int

1 port ch1;

in questo caso l’identificatore denota un canale per il trasferimento di messaggi di tipo intero. viene

ch1 ch1

dichiarato locale al processo ricevente, ed è visibile dagli altri processi mediante la dot notation:

1 <nome processo >. ch1

6.1.2 Invio

La primitiva di invio viene utilizzata come dove:

send(<value>) to <port>,

• identifica il canale a cui inviare il messaggio;

<port>

• identifica un’espressione dello stesso tipo di e il cui valore rappresenta il contenuto

<value> <port>

del messaggio.

Per esempio: int

1 port ch1;

2 send (125) to P.ch1;

dove il processo che la esegue invia il valore 125 al processo mediante il canale da cui solo può

P ch1, P

ricevere.

6.1.3 Ricezione

La primitiva di ricezione che accetta valori analoghi alla è

receive(<variabile>) from <porta>, send,

bloccante se non ci sono messaggi sul canale, sospendendo il processo. Restituisce un tipo di valore process

che identifica il nome del processo mittente:

1 proc = receive (m) from ch1;

Se sono presenti messaggi in essa estrae il primo e ne assegna il valore a Successivamente assegna

ch1, m.

alla variabile di tipo il nome del processo che ha inviato il messaggio.

proc, process,

Il server in ricezione prevede più canali di ingresso per rispondere a diverse richieste di servizio. Se la

è bloccante si deve scegliere su quale canale eseguirla; ciò comporta una notevole inefficienza in

receive

quanto il server può bloccarsi su un canale anche se su altri esistono già delle richieste pronte. Per risolvere

41

questo problema si utilizza una non bloccante, la quale verifica lo stato del canale restituendo

receive

un messaggio, se è presente una richiesta, o un’indicazione di canale vuoto. Il server può quindi eseguire un

ciclo d’ispezione e ricezione da tutti i canali.

Con quest’ultima soluzione si ha però il problema dell’attesa attiva: in caso di assenza di messaggi su

tutti i canali, il server continua a ripetere il ciclo.

Un meccanismo di ricezione ideale dovrebbe consentire al processo server di verificare la disponibilità di

messaggi su almeno due canali, abilitando la ricezione da uno qualsiasi dei canali contenenti i messaggi. Nel

caso ogni canale ne sia privo, il processo viene bloccato in attesa di messaggi su un canale qualsiasi.

6.1.4 Comando con guardia

Una guardia è espressa dalla sintassi

1 <espressione booleana >; <primitiva receive > -> <istruzione >

dove la guardia vera e propria è la coppia formata dall’espressione booleana e dalla primitiva receive.

Quando viene valutata può fornire 3 diversi risultati:

1. Guardia fallita se l’espressione booleana ha valore in questo caso il comando fallisce non

false:

producendo alcun effetto.

2. Guardia ritardata se l’espressione booleana ha valore ma la è bloccante poiché sul

true, receive

canale su cui viene eseguita non ci sono messaggi: il processo che esegue il comando viene sospeso e,

quando arriva il primo messaggio, il processo viene riattivato, esegue la e, successivamente,

receive

esegue l’istruzione specificata nella guardia.

3. Guardia valida se l’espressione booleana ha valore e la può essere eseguita senza

true receive

ritardi: la viene eseguita ed il processo esegue l’istruzione specificata.

receive

6.1.4.1 Comando con guardia alternativo

Data la sintassi:

if

1

2 [] <guardia_1 > -> <istruzione_1 >;

3 ...

4 [] <guardia_n > -> <istruzione_n >;

5 fi

vengono valutate le guardie di tutti i rami e si distinguono 3 casi:

1. Se una o più guardie sono valide viene scelto, in maniera non deterministica, uno dei rami con guardia

valida e la relativa viene eseguita. Viene quindi eseguita l’istruzione relativa al ramo scelto

receive

e, con ciò, termina l’esecuzione dell’intero comando alternativo.

2. Se tutte le guardie non fallite sono ritardate, il processo in esecuzione si sospende in attesa che arrivi

un messaggio che abilita la transizione di una guardia da ritardata a valida. A quel punto si procede

come nel caso precedente.

3. Se tutte le guardie sono fallite il comando termina.

6.1.4.2 Comando con guardia ripetitivo

Un comando analogo all’alternativa, ma che automaticamente rivaluta l’insieme di guardie dopo che è stato

eseguito uno qualunque dei rami, è il comando con guardia ripetitivo, espresso dalla seguente sintassi:

do

1

2 [] <guardia_1 > -> <istruzione_1 >;

3 ...

4 [] <guardia_n > -> <istruzione_n >;

5 od

In maniera analoga alla guardia alternativa se tutte le guardie sono fallite il comando termina, ma se anche

una sola è ritardata o valida dopo la sua esecuzione il comando viene ripetuto.

42

Esempio 6.1 – Processo server Sfruttando una guardia ripetitiva è possibile implementare un sem-

plice server che offre due servizi:

1 process server {

int

2 port servizioA ; // Esecuzione di A() su R

3 port real servizioB ; // Esecuzione di B() su R

4 Tipo_di_R R;

int

5 x;

6 real y;

7 do

8

9 [] ( condA); receive (x) from servizioA ; -> {

10 R.A(x);

11 // Eventuale restituzione dei risultati al cliente

12 }

13 [] ( condB); receive (y) from servizioB ; -> {

14 R.B(y);

15 // Eventuale restituzione dei risultati al cliente

16 }

17 od

18 }

6.2 Primitive di comunicazione asincrone

Nel modello a scambio di messaggi i processi possono svolgere operazioni sulle risorse condivise in 3 modalità:

• una sola operazione;

• più operazioni mutuamente esclusive;

• più operazioni con condizioni di sincronizzazione.

6.2.1 Risorsa condivisa con una sola operazione

Una risorsa condivisa di questo tipo mette a disposizione di un insieme di processi clienti una sola operazione

con il solo vincolo della mutua esclusione. La soluzione, nel modello a memoria comune, sarebbe stata

quella di utilizzare un monitor con un’unica operazione entry (fun), a cui i client possono accedere in modo

mutuamente esclusivo.

Nella soluzione a scambio di messaggi, invece, si ha un unico processo server che offre un unico servizio

senza condizioni di sincronizzazione, utilizzando un solo canale risposta di tipo e un solo canale

tipo_out

input di tipo Per il processo cliente si ha:

tipo_in.

1 process cliente {

2 port tipo_out risposta ;

3 tipo_in a;

4 tipo_out b;

5 process p;

6

7 send(a) to server .input;

8 p = receive (b) from risposta ;

9 }

mentre per il processo server:

1 tipo_out fun( tipo_in x);

2

3 process server {

4 port tipo_in input;

5 tipo_var var;

6 process p;

7 tipo_in x;

8 tipo_out y;

9 43

while

10 (true) {

11 p = receive (x) from input;

12 y = fun(x);

13 send(y) to p. risposta ;

14 }

15 }

6.2.2 Risorsa condivisa con più operazioni

In questo caso la risorsa condivisa mette a disposizione di un insieme di processi clienti due operazioni con

il solo vincolo della mutua esclusione.

Nel modello a memoria comune si sarebbe usato un unico monitor con due operazioni (fun1 e fun2),

mutuamente esclusive. Nel modello a scambio di messaggi si possono invece avere due tipi di soluzione, a

seconda che si faccia uso, o meno, delle guardie.

6.2.2.1 Soluzione senza comandi con guardia

Il processo servitore offre 2 servizi senza condizioni di sincronizzazione utilizzando un solo canale per entrambi

i tipi di richiesta.

La struttura dati per la tipologia del messaggio è definibile nel seguente modo:

typedef struct

1 {

enum

2 (fun1 , fun2) servizio ;

union

3 {

4 tipo_in1 x1; // Parametri di fun1

5 tipo_in2 x2; // Parametri di fun2

6 } parametri ;

7 } in_mess ;

Il processo server sarà definito come:

1 tipo_out1 fun1( tipo_in1 x1);

2 tipo_out2 fun2( tipo_in2 x2);

3

4 process server {

5 port in_mes input;

6

7 process p;

8 in_mes richiesta ;

9 tipo_out1 y1;

10 tipo_out2 y2;

11 while

12 (true) {

13 p = receive ( richiesta ) from input;

switch

14 ( richiesta . servizio ) {

case

15 fun1:

16 y1 = fun1( richiesta . parametri .x1);

17 send(y1) to p. risposta1 ;

break;

18 case

19 fun2:

20 y2 = fun2( richiesta . parametri .x2);

21 send(y2) to p. risposta2 ;

break;

22

23 }

24 }

25 }

Il client sarà infine realizzato come:

1 process client {

2 port tipo_out1 risposta1 ;

3 port tipo_out2 risposta2 ;

4 tipo_in1 a1; 44

5 tipo_in2 a2;

6 tipo_out1 b1;

7 tipo_out2 b2;

8 process p;

9 if

10 (/* Servizio 1 */) {

11 send(a1) to server .input;

12 p = receive (b1) from risposta1 ;

else

13 } {

14 send(a2) to server .input;

15 p = receive (b2) from risposta2 ;

16 }

17 }

6.2.2.2 Soluzione con comandi con guardia

In questa soluzione si utilizzano due canali, uno per ogni tipo di richiesta. Ciò permette di abbandonare la

struttura dati per la richiesta dell’operazione e il server viene modificato come:

1 tipo_out1 fun1( tipo_in1 x1);

2 tipo_out2 fun2( tipo_in2 x2);

3

4 process server {

5 port tipo_in1 input1 ;

6 port tipo_in2 input2 ;

7 process p;

8 tipo_in1 x1;

9 tipo_in2 x2;

10 tipo_out1 y1;

11 tipo_ou2 y2;

12 do

13

14 [] p = receive (x1) from input1 ; -> {

15 y1 = fun1(x1);

16 send(y1) to p. risposta1 ;

17 }

18 [] p = receive (x2) from input2 ; -> {

19 y2 = fun2(x2);

20 send(y2) to p. risposta2 ;

21 }

22 od

23 }

6.2.3 Risorsa condivisa con più operazioni e condizioni di

sincronizzazione

Una risorsa di questo tipo mette a disposizione dei processi client due o più operazioni con le relative

condizioni di sincronizzazione.

Nel modello a memoria comune si utilizza un monitor con due entry (op1 e e due variabili condizione

op2)

(c1 e utilizzate con politica signal and wait:

c2),

1 entry tipo_out1 op1( tipo_in1 x1) {

2 ...

if

3 (! cond1)

4 wait(c1);

5 ...

6 signal (c2);

7 ...

8 }

9

10 entry tipo_out2 op2( tipo_in2 x2) { 45

11 ...

if

12 (! cond2)

13 wait(c2);

14 ...

15 signal (c1);

16 ...

17 }

Nel modello a scambio di messaggi, invece, si ha un processo servitore con più servizi e con la specifica di

condizioni di sincronizzazione all’interno delle guardie:

1 tipo_out1 fun1( tipo_in1 x1);

2 tipo_out2 fun2( tipo_in2 x2);

3

4 process server {

5 port tipo_in1 input1 ;

6 port tipo_in2 input2 ;

7 process p;

8

9 tipo_in1 x1;

10 tipo_in2 x2;

11 tipo_out1 y1;

12 tipo_ou2t y2;

13 do

14

15 [] ( cond1); p = receive (x1) from input1 ; -> {

16 y1 = fun1(x1);

17 send(y1) to p. risposta1 ;

18 }

19 [] ( cond2); p = receive (x2) from input2 ; -> {

20 y2 = fun2(x2);

21 send(y2) to p. risposta2 ;

22 }

23 od

24 }

Modello a memoria comune Modello a scambio di messaggi

Risorsa condivisa: istanza di un monitor Risorsa condivisa: struttura dati locale a un

processo server

Identificatore di funzione di accesso al monitor Porta del processo server

Funzione del monitor Ramo (comando con guardia) dell’istruzione

ripetitiva che costituisce il corpo del server

Tipo dei parametri della funzione Tipo della porta

Tipo del valore restituito dalla funzione Tipo della porta da cui il processo cliente riceve

il risultato

Condizione di sincronizzazione di una funzione Guardia logica componente del ramo corrispon-

entry dente alla funzione

Chiamata di funzione entry Invio della richiesta sulla corrispondente porta

del server e attesa dei risultati sulla propria porta.

Mutua esclusione fra le entry del monitor Scelta di uno dei rami con guardia valida del

comando ripetitivo del server

Corpo della funzione Istruzione del ramo corrispondente alla funzione

Tabella 6.1: Corrispondenze riassuntive tra il modello a memoria comune con monitor e il modello a scambio di

messaggi con processi servitori. 46

6.3 Modelli di processi servitori

Per esempi d’uso delle primitive di comunicazione per modellare diversi modelli di comunicazioni tra processi

si rimanda a § B.

6.4 Realizzazione primitive asincrone

Di seguito si presenta la realizzazione delle primitive di comunicazione e del costrutto al fine di

port,

definire i canali utilizzati dalle primitive. Saranno utilizzati gli strumenti di comunicazione offerti dal kernel

del sistema operativo in architetture monoprocessore, multiprocessore e distribuite.

6.4.1 Architettura mono e multiprocessore

Si assumono le seguenti ipotesi semplificative:

• tutti i messaggi scambiati tra i processi sono di un unico tipo predefinito a livello di kernel;

T

• tutti i canali sono da molti ad uno (port) e, quindi, associati al solo processo ricevente;

• essendo le primitive asincrone, ogni porta deve contenere un buffer di lunghezza indefinita.

La coda ed i messaggi ad essa associati saranno rappresentati da opportune strutture dati:

typedef struct

1 {

2 T informazione ;

3 PID mittente ;

4 messaggio * successivo ;

5 } messaggio ;

6 typedef struct

7 {

8 messaggio * primo;

9 messaggio * ultimo ;

10 } coda_messaggi ;

Si avranno quindi due operazioni per inserire un messaggio nella coda e per estrarre il primo:

void

1 inserisci ( messaggio *m, coda_messaggi c) {

if(c.primo

2 == null)

3 c.primo = m;

else

4

5 c.ultimo -> successivo = m;

6 c. ultimo = m;

7 m-> successivo = null;

8 }

9

10 messaggio * estrai ( coda_messaggi c) {

11 messaggio *res = c.primo;

12 c. primo = c.primo -> successivo ;

if(c.primo

13 == null)

14 c. ultimo = null;

return

15 res;

16 }

Il descrittore del processo sarà aggiornato con un puntatore a strutture dati che descrivono le code associate

al processo, mentre un campo registra se il processo è attivo oppure bloccato. In questo caso, esso

stato

tiene traccia delle porte sulle quali è in attesa:

1 boolean coda_vuota ( coda_messaggi c) {

return

2 c.primo == null;

3 }

4 typedef struct

5 porta {

6 coda_di_messaggi coda; 47

struct

7 porta * puntatore ;

8 } des_porta ;

9 typedef

10 des_porta * p_porta ;

11 typedef struct

12 process {

13 p_porta porte_processo [M];

14 PID nome;

15 modalita_di_servizio servizio ;

16 tipo_contesto contesto ;

17 tipo_stato stato ;

18 PID padre ;

int

19 N_figli ;

20 des_figlio prole [ max_figli ];

struct

21 process * successivo ;

22 } des_processo ;

23 typedef

24 des_processo *p_des;

Il campo verrà quindi testato e modificato dalle seguenti due funzioni:

stato int

1 boolean bloccato_su ( p_des p, ip) {

2 // Testa il campo "stato" nel descrittore del processo di cui p è il

3 // puntatore e restituisce il valore true se il processo risulta bloccato

4 // in attesa di ricevere messaggi dalla porta il cui indice nel campo

5 // porte_processo è ip

6 }

7 void

8 blocca_su (int ip) {

9 // Modifica il campo "stato" del descrittore del processo_in_esecuzione

10 // per indicare che lo stesso si blocca in attesa di messaggi dalla porta

11 // il cui indice nel campo porte_processo è ip

12 }

Come ultimi componenti, si avranno delle funzioni per manipolare le porte:

void

1 testa_porta (int ip) {

2 p_des esec = processo_in_esecuzione ;

3 p_porta pr = esec -> porte_processo [ip ];

if(

4 coda_vuota (pr ->coda)) { // Sospensione

5 blocca_su (ip);

6 assegnazione_CPU (); // Context switch

7 }

8 }

9

10 messaggio * estrai_da_porta (int ip) {

11 messaggio *m;

12 p_des esec = processo_in_esecuzione ;

13 p_porta pr = esec -> porte_processo [ip ];

14 m = estrai (pr ->coda);

return

15 m;

16 }

17 void int

18 inserisci_porta ( messaggio *m, PID proc , ip) {

19 p_des destinatario = descrittore (proc);

20 p_porta pr = destinatario -> porte_processo [ip];

21 inserisci (m, pr ->coda);

if(

22 bloccato_su ( destinatario , ip))

23 attiva ( destinatario ); // Porta destinatario nello stato di ready

24 }

E infine e

send receive:

void int

1 send(T inf , PID proc , ip) {

2 messaggio *m = new messaggio ;

3 m-> informazione = inf;

4 m-> mittente = processo_in_esecuzione ->nome;

5 inserisci_porta (m, proc , ip); 48

6 }

7 void int

8 receive (T *inf , PID *proc , ip) {

9 messaggio *m;

10 testa_porta (ip);

11 m = estrai_da_porta (ip);

12 *proc = m-> mittente ;

13 *inf = m-> informazione ;

14 }

6.4.1.1 Ricezione su più canali

Se si fosse invece interessati a porsi in ascolto su molteplici porte contemporaneamente, si dovranno definire

una e una nuova che permettano di ricevere messaggi su più porte:

testa_porte receive

int int

1 testa_porte (int ip[], n) {

2 p_porta pr;

int

3 ris = -1;

int

4 indice_porta ;

5 p_des esec = processo_in_esecuzione ;

for

6 (int i = 0; i < n; i++) {

7 indice_porta = ip[i];

8 pr = esec -> porte_processo [ indice_porta ];

if(

9 coda_vuota (pr ->coda))

10 blocca_su ( indice_porta );

else

11 {

12 ris = indice_porta ;

13 esec -> stato = // Processo attivo

break;

14

15 }

16 }

if(ris

17 == -1)

18 assegnazione_CPU (); // Tutte le porte sono vuote: sospensione

return

19 ris;

20 }

21 int int int

22 receive_any (T *inf , PID *proc , ip[], n) {

23 messaggio *mes;

int

24 indice_porta ;

do

25

26 indice_porta = testa_porte (ip ,n);

while

27 ( indice_porta == -1);

28

29 mes = estrai_da_porta ( indice_porta );

30 *proc = mes -> mittente ;

31 *inf = mes -> informazione ;

return

32 indice_porta ;

33 }

6.4.2 Architetture distribuite

Esistono due tipologie di architetture distribuite:

• Sistemi operativi distribuiti: detti anche Distributed Operating System DOS, costituiscono

un insieme di nodi tra loro omogenei, dotati dello stesso sistema operativo. Essi gestiscono tutte

le risorse nascondendo all’utente la loro distribuzione sulla rete. L’interfaccia di rete è un normale

dispositivo, la cui gestione è quindi basata su interruzioni.

• Sistemi operativi di rete: detti anche Network Operating Systems NOS, costituiscono un

insieme di nodi eterogenei, con sistemi operativi diversi e autonomi. Ogni nodo della rete è in grado

di offrire servizi a clienti remoti presenti su altri nodi della rete tramite l’uso di socket. La trasparenza

49

della distribuzione delle risorse viene ottenuta mediante un’entità middleware, interposta su ogni

nodo tra sistema operativo e applicazioni. Nodo j

Nodo i

Nodo i Applicazione distribuita

Kernel del OS Middleware Middleware

Altre

Interfaccia di rete OS locale OS locale

interfacce con servizi con servizi

di I/O

Ricezione

Trasmissione di rete di rete

rete rete

(a) (b)

Architettura DOS. Architettura NOS.

Figura 6.2: Architetture distribuite.

6.4.2.1 Pacchetti, interfacce e canali

Il pacchetto è l’unità di trasmissione fondamentale tra i nodi. Oltre alla componente del messaggio vero

e proprio, esso contiene altre informazioni utili, in fase di ricostruzione, al destinatario. Per permettere la

comunicazione, i nodi necessitano di un’interfaccia di rete, la quale è costituita da due canali:

• Un canale di trasmissione acceduto per permettere l’invio di pacchetti. Ad esso sono associati:

tx,

– una coda di pacchetti, nella quale ogni mittente deposita il proprio pacchetto nel caso il canale

sia occupato da un altro processo;

– un registro buffer (della dimensione di un pacchetto).

• Un canale di ricezione acceduto per permettere la ricezione di pacchetti. Ad esso è associato un

rx,

registro buffer, nel quale viene depositato ogni pacchetto inviato al nodo.

L’arrivo e la partenza di pacchetti provenienti da e diretti verso canali di ricezione e trasmissione vengono

notificati tramite interruzioni. Di seguito viene mostrata la pseudo-codifica degli interrupt in trasmissione

e ricezione.

void

1 tx_interrupt_handler () {

2 packet p;

3 salvataggio_stato ();

if

4 (! packet_queue . vuota ()) {

5 p = packet_queue . estrai ();

6 // Inserimento di p nel registro buffer del canale

7 // Attivazione trasmissione

8 }

9 ripristino_stato ();

10 }

11 void

12 rx_interrupt_handler () {

13 packet p;

14 PID mit;

15 T inf;

16 PID proc;

int

17 ip;

18

19 salvataggio_stato ();

20 p = // Pacchetto ricevuto presente nel buffer del canale

21 // Attivazione ricezione

22 mit = // Mittente contenuto nel pacchetto p

23 inf = // Corpo del messaggio contenuto nel pacchetto p

24 ip = // Porta contenuta nel pacchetto p

25 proc = // Destinatario contenuto nel pacchetto p

26 50

27 messaggio *m = new messaggio ;

28 m-> informazione = inf;

29 m-> mittente = mit;

30 inserisci_porta (m, proc , ip);

31 ripristino_stato ();

32 }

6.5 Realizzazione primitive sincrone

Nello schema a singolo produttore e singolo consumatore il protocollo è piuttosto semplice: si blocca il

processo mittente durante l’esecuzione della in attesa che il ricevente abbia dato conferma.

send, consumatore

Esempio 6.2 – Mailbox di lunghezza finita produttore 1

1

In questo schema, diversamente dal caso con send pronto_cons

asincrona, il canale non è in grado di bufferizzare i consumatore

produttore mailbox

messaggi inviati, quindi si ha la necessità di realiz- i

i dati

zare una struttura interna al processo mailbox: la dati

coda di messaggi. consumatore

produttore n

n

1 process mailbox {

2 port T dati; Figura 6.3: Protocollo di uno schema molti a molti nel

3 port signal pronto_cons ; modello a scambio di messaggi (buffer di lunghezza finita).

4 T messaggio ;

5 process p;

6 signal s;

7 coda_messaggi coda;

8 do

9

10 [] !coda.piena (); p = receive ( messaggio ) from dati; ->

11 coda. inserimento ( messaggio );

12 [] !coda.vuota (); p= receive (s) from pronto_cons ; -> {

13 messaggio = coda. estrazione ;

14 send( messaggio ) to p.dati;

15 }

do

16

17 }

18

19 process produttore {

20 T messaggio ;

21 process p;

22 signal s;

23

24 // Produci il messaggio

25 send( messaggio ) to mailbox .dati;

26 }

27

28 process consumatore {

29 port T dati;

30 T messaggio ;

31 process p;

32 signal s;

33

34 send(s) to mailbox . pronto_cons ;

35 p = receive ( messaggio ) from dati;

36 // Consuma il messaggio

37 }

È possibile anche realizzare uno schema di mailbox concorrente, in cui non si ha più un solo processo

ma un numero pari alla dimensione del buffer.

mailbox, 51

6.5.1 Uso di semafori

Questa versione delle primitive sincrone prevede l’utilizzo di due semafori, uno per bloccare il mittente e

uno per bloccare il destinatario; la logica è la stessa: l’uno sblocca l’altro nel momento in cui si finisce la

propria esecuzione:

1 semaphore M = 0; // Sospensione mittente

2 semaphore R = 0; // Sospensione ricevente

3 messaggio buffer ;

4 void

5 public invio (T dato) {

6 messaggio mes;

7 mes. informazione = dato;

8 mes. mittente = processo_in_esecuzione ->nome;

9 buffer = mes;

10 V(R);

11 P(M);

12 }

13 void

14 public ricezione (T *dato , PID *mit) {

15 messaggio mes;

16 P(R);

17 mes = buffer ;

18 V(M);

19 *dato = mes. informazione ;

20 *mit = mes. mittente ;

21 }

6.5.2 Uso di primitive asincrone

È possibile fare uso delle primitive asincrone introducendo un secondo canale che verrà utilizzato per

scambiare un messaggio di conferma al fine di procedere una volta che la ricezione è stata completata:

void int

1 send(T inf , PID proc , ip) {

2 signal s;

3 a_send (inf , proc , ip);

4 a_receive (s, proc , ak);

5 }

6 void int

7 receive (T &inf , PID &proc , ip) {

8 signal s;

9 a_receive (inf , proc , ip);

10 a_send (s, proc , ak);

11 }

6.5.3 Uso di primitive del kernel

Le funzioni di appoggio e le strutture dati sono le stesse del caso asincrono; la e la però

send receive

dovranno sfruttare due funzioni per ottenere sincronizzazione tra processo mittente e destinatario:

void

1 attendi_ricezione () {

2 p_des esec = processo_in_esecuzione ;

3 esec -> stato = // Bloccato sulla send

4 assegnazione_CPU ();

5 }

6

7 messaggio estrai_da_porta (int ip) {

8 messaggio mes;

9 p_des mit;

10 p_des esec = processo_in_esecuzione ;

11 p_porta pr = esec -> porte_processo [ip ];

52

12 mes = estrai (pr ->coda);

13 mit = descrittore (mes. mittente );

14 attiva (mit); // Attiva il mittente del messaggio ricevuto

return

15 mes;

16 } 53

Capitolo 7

Comunicazione con sincronizzazione

estesa

La forma più stringente di sincronizzazione basata su scambio di messaggi, detta “sincronizzazione

estesa”, può avvenire secondo due modalità: RPC e rendezvous.

La sincronizzazione estesa è un meccanismo di comunicazione tra processi nel quale un processo che richiede

un servizio ad un altro rimane sospeso fino al completamento del servizio richiesto. Il meccanismo è sincrono

in quanto i due processi rimangono sincronizzati durante tutta l’esecuzione del servizio.

Semanticamente, il meccanismo è analogo ad una chiamata a funzione, nella quale il processo chiamante

prosegue solo dopo che l’esecuzione della funzione è terminata.

L’implementazione può avvenire in due modalità diverse:

• chiamata di procedura remota RPC;

• rendezvous.

7.1 RPC

Per ogni operazione che un processo client può richiedere viene dichiarata, lato server, una procedura e,

per ogni richiesta, il server genera un thread per l’esecuzione della richiesta corrente. È quindi necessaria la

sincronizzazione tra i vari processi creati (a carico del programmatore), ma non tra clienti e servitori.

L’insieme delle procedure remote è definito all’interno di un componente software detto modulo. Esso

contiene le variabili locali al server ed eventuali procedure e processi locali.

È importante notare che i singoli moduli operano in spazi di indirizzamento diversi e, quindi, possono

essere allocati su nodi distinti di una rete (ciò è reso trasparente all’utente).

7.2 Rendezvous

In questo modello implementativo, l’operazione richiesta viene specificata come un insieme di istruzioni che

può comparire in un punto qualunque del processo servitore. Un esempio è dato dal linguaggio Ada (§ D).

Per realizzare ciò, il processo servitore utilizza un’istruzione in ingresso, la che lo sospende in

accept,

attesa di una richiesta dell’operazione. All’arrivo della richiesta, il server esegue il relativo insieme di

istruzioni, quindi i risultati ottenuti sono inviati al chiamante.

Poiché si ha un unico servitore, il modello deve combinare meccanismi di comunicazione e sincronizzazione

con i clienti. La sincronizzazione col cliente avviene al momento della accept:

1 accept <servizio > (in <par -ingresso >, out <par -uscita >); -> {S1 , ..., Sn};

dove:

• sono i parametri di ingresso;

in 54

• sono i parametri di uscita, nei quali verrà salvato il risultato;

out

• è la sequenza di istruzioni del servizio da eseguire.

{S1, ..., Sn} n

Il cliente richiederà il servizio specificando il server, il nome del servizio ed i parametri di input:

1 call <server >.< servizio >(< parametri >);

La è sospensiva se non sono presenti richieste sul servizio. Se il servizio è richiesto da più clienti

accept

contemporaneamente, le richieste vengono inserite in una coda gestita con politica FIFO.

Ad uno stesso servizio, inoltre, possono essere associate più Ad una richiesta possono infatti cor-

accept.

rispondere azioni diverse, a seconda dello stato interno del server, il quale può essere gestito come condizione

di una guardia:

if

1

2 [] <stato1 >; accept <servizio1 > (in <par -ingresso >, out <par -uscita >);

3 -> {S11 , ..., S1n };

4 [] <stato2 >; accept <servizio2 > (in <par -ingresso >, out <par -uscita >);

5 -> {S21 , ..., S2n };

6 ...

7 fi

7.2.1 Selezione delle richieste in base ai parametri di ingresso

La decisione di servire o meno una richiesta può dipendere, oltre che dallo stato interno del server, anche

dai parametri della richiesta stessa (per esempio, politiche di accettazione delle richieste basate su priorità).

In questo caso, la guardia logica che condiziona l’esecuzione dell’azione richiesta deve essere espressa anche

in termini dei parametri di ingresso. Si necessita quindi di una doppia interazione tra processo cliente e

processo servitore: la prima per trasmettere i parametri della richiesta e la seconda per richiedere il servizio.

Nell’ipotesi semplificativa di un numero limitato di richieste differenti è possibile ottenere una semplice

soluzione a tale problema associando, ad ogni richiesta, una differente operazione di servizio tramite un

vettore di operazioni di servizio (§ D.2.2). 55

Capitolo 8

Algoritmi di sincronizzazione distribuiti

In uno scenario distribuito, per garantire la sincronizzazione nell’accesso a risorse condivise tra

nodi distinti di una rete, si rende necessario introdurre un coordinatore unico dei processi o

l’utilizzo di opportuni algoritmi. In questo contesto è inoltre richiesta una sincronizzazione degli

orologi dei diversi nodi.

In un sistema distribuito, processi distinti eseguono su nodi fisicamente separati, collegati tra loro attraverso

una rete.

In un’applicazione distribuita sussistono due requisiti fondamentali che è necessario garantire:

• Scalabilità: ogni applicazione distribuita dovrebbe aumentare le proprie prestazioni al crescere del

numero di nodi utilizzati. Un parametro di valutazione per questo requisito è lo speedup, ovvero il

rapporto tra il tempo di esecuzione dell’applicazione ottenuto con un solo nodo e il tempo di esecuzione

ottenuto con un certo numero di nodi.

• Tolleranza ai guasti: l’applicazione è in grado di funzionare anche in presenza di guasti, come ad

esempio il crash di un nodo.

L’obiettivo è di garantire che due o più processi non possano eseguire contemporaneamente certe attività.

La soluzione può essere: centralizzata, se la risorsa è gestita da un processo dedicato, detto coordinatore,

al quale tutti i processi si rivolgono per accedervi, o distribuita, in cui i processi in competizione si

sincronizzano tra loro tramite opportuni algoritmi.

In generale, le soluzioni distribuite sono più scalabili di quelle centralizzate, nelle quali il processo gestore

della risorsa costituisce un collo di bottiglia.

Esiste tuttavia un’altra distinzione tra le soluzioni:

• Permission-based: ogni processo che vuole eseguire la sua sezione critica richiede un permesso ad

uno o più altri processi. Queste soluzioni possono essere sia centralizzate che distribuite.

• Token-based: un messaggio, detto token, viene passato tra i vari processi in competizione ed il

processo che possiede il token può o eseguire la propria sezione critica, oppure passare il token ad

un altro processo (perché non intenzionato ad entrare nella propria sezione critica). Queste soluzioni

possono essere solo distribuite.

8.1 Soluzione centralizzata

L’algoritmo è basato su permessi e la risorsa viene gestita da un processo coordinatore al quale, ogni processo

che vuole eseguire la propria sezione critica, si rivolge per ottenere il permesso. Una volta eseguita la sezione

critica, ne comunica il rilascio. I processi che fanno richiesta mentre la risorsa è utilizzata verranno messi in

coda.

Il vantaggio principale di tale algoritmo è l’equità: non vi è infatti possibilità di starvation. Esso prevede

inoltre solo 3 messaggi per ogni sezione critica. La soluzione risulta però poco scalabile, in quanto il

coordinatore può rappresentare un collo di bottiglia. Se quest’ultimo è soggetto ad un guasto inoltre, ne

56

risente tutto il sistema, ed ha luogo un single point of failure. Un ulteriore difetto di questa soluzione

deriva dal fatto che, se un processo fa richiesta e non ottiene risposta, non si riesce a distinguere se si tratti

di un caso di autorizzazione non concessa oppure di un guasto al coordinatore.

8.2 Soluzione distribuita

8.2.1 Algoritmo Ricart-Agrawala

È un algoritmo basato su permessi. Il sistema è costituito da un insieme di processi in competizione nel

quale non è presente nessun coordinatore. Ad ogni processo sono associati 2 thread concorrenti: il main,

che esegue la sezione critica, ed il receiver, dedicato alla ricezione delle autorizzazioni. Per la definizione

dell’algoritmo si assume la presenza di un temporizzatore globale per tutti i nodi, il quale permette di poter

utilizzare un timestamp da allegare al messaggio scambiato per indicarne l’istante di invio.

Quando un processo vuole accedere alla sezione critica, il main invia richieste di autorizzazione ai

n 1

− −

receiver degli altri nodi, inviando il proprio PID e il relativo timestamp. Esso attende quindi le

n 1 n 1

autorizzazioni, per poi eseguire la sezione critica. Una volta terminata, invia alle richieste in attesa.

ok

Relativamente al receiver, quando viene ricevuta una richiesta, esso può trovarsi in 3 stati:

• il processo non è interessato ad entrare nella sezione critica e risponde

released: ok.

• il processo è in procinto di entrare nella sezione critica, quindi sta attendendo l’autorizzazione.

wanted:

Esso confronta il timestamp della richiesta ricevuta con quello della richiesta inviata e, se

T S T S

r s

, risponde In caso contrario non risponde e mette la richiesta ricevuta in coda.

ok.

T S < T S

r s

• il processo sta eseguendo la sezione critica e la richiesta viene messa in coda.

held:

Esempio 8.1 Si considerino i 3 processi: , e . e vogliono eseguire una sezione critica,

P P P P P

0 1 2 0 2

quindi inviano entrambi una richiesta agli altri due, con timestamp 5 e con timestamp 8:

P P

0 2

• è in stato Esso non risponde quindi a , in quanto e mette in coda la richiesta

wanted.

P P 8 > 5,

0 2

ricevuta;

• è in stato Risponde ad entrambi

released. ok;

P 1

• è in stato Poiché risponde a ;

wanted. ok

P 5 < 8, P

2 0

Una volta terminata la sezione critica, invia a , il quale può eseguire la propria sezione critica.

ok

P P

0 2

P P

0 0

TS=8

TS=5 ok ok

TS=5

P P P P

1 2 1 2

ok

TS=8

(a) (b)

Richieste. Risposte.

Figura 8.1: Messaggi scambiati tra i processi dell’Esempio 8.1.

Il vantaggio di questo algoritmo, rispetto al precedente, è dato dalla sua scalabilità. Lo svantaggio è invece

dato dal maggior costo: i messaggi inviati infatti, per ogni sezione critica, sono e si hanno pertanto

2(n 1),

points of failure. Se infatti uno dei nodi va in crash, esso non risponderà alle richieste degli altri. Inoltre,

n

per la struttura stessa del protocollo, non è possibile sapere se l’attesa sia dovuta ad un guasto oppure a

sezioni critiche in esecuzione.

Quest’ultimo problema può essere risolto modificando il protocollo in modo che venga sempre fornita una

risposta, per esempio in caso di autorizzazione negata. Settando un timeout sulla ricezione di questa

wait

risposta si può avere la certezza di un guasto. 57

8.2.2 Algoritmo Token Ring

L’algoritmo è basato sullo scambio di un token. Il sistema è costituito da un insieme di processi in compe-

tizione, collegati tra di loro secondo una topologia logica ad anello, in cui ogni processo conosce solo i suoi

due vicini.

Il token viene fatto circolare secondo un certo verso di percorrenza ed il processo che, in un certo istante,

detiene il token, ha il permesso di eseguire una sezione critica. Se all’arrivo del token il processo è in

stato esso trattiene il token ed esegue la sezione critica, al termine, passa quindi il token al processo

wanted,

successivo. Se invece alla ricezione del token è in stato lo passa direttamente al processo successivo.

released,

Anche in questo caso, il vantaggio dell’algoritmo è dato dalla sua scalabilità. Gli svantaggi sono invece:

• Numero di messaggi non limitato per ogni sezione critica.

• points of failure in quanto, se uno dei nodi va in crash, interrompe tutta la catena. Il problema

n

è risolvibile modificando il protocollo in modo tale che, ad ogni invio del token da a , venga

P P

i i+1

sempre restituita una risposta. Se la risposta non arriva allo scadere di un timeout, viene escluso

P i+1

dall’anello ed il token viene inviato a .

P i+2

• Possibilità di perdere il token se il processo che lo detiene va in crash.

8.2.3 Algoritmi di elezione

Sono algoritmi caratterizzati dalla presenza di un coordinatore, designato a runtime dai processi del sistema

con un algoritmo di elezione. Ciò permette di attribuire, a runtime, il ruolo di nuovo coordinatore ad un

altro processo del gruppo. In questa categoria di algoritmi si assume che ogni processo conosca i PID di

tutti gli altri processi del sistema.

8.2.3.1 Bully

Si consideri un sistema composto da processi , in cui Quando un processo rileva che

n P P ID = i. P

i i k

il coordinatore non è più attivo, organizza un’elezione inviando il messaggio a tutti i processi

election

con PID più alto. Se nessun processo risponde, vince l’elezione, diventando così il nuovo coordinatore e

P k

comunicando a tutti gli altri processi il proprio nuovo ruolo tramite il messaggio Se invece

coordinator.

un processo risponde, tale processo prende il controllo e rinuncia, uscendo dall’elezione.

P k

8.2.3.2 Elezione ad anello

Come per l’algoritmo a token ring, i processi del gruppo sono collegati tramite una topologia logica ad

anello. La posizione che ogni processo occupa all’interno dell’anello, descritta da un PID, rappresenta la sua

priorità. In questo contesto, il processo attivo con la massima priorità viene eletto coordinatore.

Quando un processo rileva che il coordinatore non risponde ha inizio la fase di elezione:

P

i

1. invia un messaggio contenente il proprio PID al suo successore . Se il successore

election

P P P

i i+1 i+1

non risponde, il messaggio viene spedito al successore di , e così via.

P i+1

2. Quando un processo riceve un messaggio election:

P j

• se il messaggio non contiene il proprio PID, lo aggiunge a tale messaggio e lo spedisce al

P j

successivo;

• se il messaggio contiene il proprio PID, allora è stato compiuto un giro completo dell’anello.

designa quindi, come coordinatore, il processo corrispondente al PID più alto nel messaggio

P j

ricevuto, quindi invia al processo successivo un messaggio contenente il PID del

coordinator

processo designato come nuovo coordinatore.

3. Quando un processo riceve un messaggio esso ne prende atto ed inoltra lo stesso

coordinator,

messaggio al successivo. 58

8.3 Algoritmi per la gestione del tempo

In un sistema distribuito ogni nodo è dotato di un proprio orologio. Diventa pertanto fondamentale

mantenere sempre sincronizzati gli orologi locali di più processi che comunicano.

Nel caso in cui si necessiti dell’ora esatta è possibile utilizzare un orologio fisico universale sul quale

è possibile applicare algoritmi di sincronizzazione. In alternativa, è possibile utilizzare un orologio logico

che associa, ad ogni evento, un istante logico, detto timestamp.

8.3.1 Orologi logici →

Dati due eventi e si indica con il fatto che venga prima di Questa relazione di precedenza

a b, a b a b.

Happened Before HB.

prende il nome di Essa può essere dovuta al fatto che tali eventi avvengano sullo

stesso processo, oppure perché è l’evento ricezione di un messaggio inviato da In aggiunta, se valgono

b a.

→ → →

contemporaneamente e allora vale (proprietà transitiva).

a b b c, a c

Dati due eventi, sono possibili 3 casi:

• precede

a b: a b;

• precede

b a: b a;

• e non sono in relazione HB fra di loro, pertanto sono concorrenti.

a b

Indicando con il timestamp dell’evento deve risultare valida

C(e) e,

→ ⇒

a b C(a) < C(b).

Per garantirne il rispetto, ogni processo gestisce localmente un contatore del tempo logico , il quale viene

C i

gestito dall’algoritmo di Lamport:

1. ogni nuovo evento all’interno di provoca un incremento di ;

P C

i i

2. ogni volta che invia un messaggio il contatore viene incrementato e, successivamente, al

P m, C

i i

messaggio viene associato il nuovo timestamp ;

C i

3. quando un processo riceve un messaggio esso imposta il proprio contatore come:

P m, C

j j

C = max(C , T S ) + 1.

j j m

59

Capitolo 9

Azioni atomiche

Per scongiurare conflitti su letture e scritture tra più processi e per garantire robustezza verso i

malfunzionamenti, le azioni sui dati devono essere atomiche. Per realizzare questo meccanismo

sono necessari particolari accorgimenti hardware e software, oltre che opportuni protocolli per la

gestione delle interazioni tra i diversi nodi di una rete.

Un’azione atomica è uno strumento di alto livello per la strutturazione di programmi concorrenti e/o distri-

buiti tolleranti ai malfunzionamenti. Più semplicemente si può dire che essa è un operazione che porta un

insieme di oggetti da uno stato consistente ad uno stato consistente .

S S

1 2

Considerando un oggetto astratto di tipo si definisce relazione invariante una relazione che caratte-

T,

rizza tale oggetto dal punto di vista semantico. Tale relazione riguarda i valori delle variabili componenti

l’oggetto.

Ogni oggetto può trovarsi in stati consistenti o inconsistenti a seconda che sia verificata, o meno, la

relazione invariante del tipo. Ogni operazione primitiva su dati di tipo deve essere programmata in modo

T

da lasciare l’oggetto su cui opera in uno stato consistente, ossia in uno stato in cui l’invariante sia soddisfatta.

Dato un insieme di oggetti, oltre alla consistenza del singolo oggetto, va anche mantenuta la consistenza

dell’insieme stesso. Si dovrà quindi definire anche una relazione invariante su tale insieme.

Affinché sia garantita la consistenza dei dati, l’azione atomica deve esibire due proprietà fondamentali:

• Serializzabilità: atomicità nei confronti della concorrenza.

• Tutto o niente: atomicità nei confronti di eventi anomali.

9.1 Serializzabilità

Durante l’esecuzione di un’operazione, l’insieme può passare attraverso stati inconsistenti, i quali non

O

devono essere visibili ad altre azioni concorrenti.

Esempio 9.1 Si consideri il dominio di un’applicazione bancaria. Un’operazione di trasferimento di x,

tra due oggetti e , deve rispettare la relazione:

O O

1 2 value + value = cost.

O O

1 2

Tale operazione prevede un primo step in cui viene prelevato da il valore per aggiungerlo ad .

O x, O

1 2

Dopo questo primo step, la relazione invariante non è soddisfatta, pertanto si ha uno stato inconsistente;

la proprietà di serializzabilità assicura però che ogni azione atomica operi sempre su un insieme di oggetti

i cui stati iniziale e finale sono consistenti ed i cui stati parziali, durante l’esecuzione, non sono visibili ad

altre azioni concorrenti. 60

9.2 Tutto o niente

È possibile che l’esecuzione di un’operazione venga interrotta a causa di una condizione anomala come un

guasto, un’eccezione o un crash. Affinché gli oggetti non rimangano in uno stato inconsistente, è necessario

un meccanismo di recupero che, in seguito ad una condizione anomala, riporti gli oggetti in uno stato

consistente. ′

A tal proposito si applica la proprietà del tutto o niente. Essa prevede che lo stato risultante dell’esecu-

S

zione di un’azione atomica possa essere, in ogni istante, o uguale a , oppure a , che sono, rispettivamente,

S S

1 2

lo stato iniziale e quello finale.

Un’azione atomica che gode della proprietà del tutto o niente è in grado di tollerare il verificarsi di

condizioni anomale durante la sua esecuzione, senza lasciare gli oggetti in stati inconsistenti.

Se non è possibile raggiungere lo stato finale di un’operazione, il meccanismo di ripristino riporterà lo

stato al valore iniziale. Tale operazione di distruzione degli effetti di un’azione atomica e ripristino del valore

iniziale degli oggetti è denominata abort.

9.3 Two phase lock protocol

Il two phase lock protocol è un protocollo volto a garantire serializzazione. Esso si basa su tre principi

fondamentali:

1. Ogni oggetto deve essere acquisito da un’azione atomica in modo esclusivo prima di qualunque

A

azione su di esso. La richiesta sull’oggetto è bloccante se l’oggetto non è libero.

2. Nessun oggetto deve essere rilasciato prima che siano eseguite tutte le operazioni su di esso.

3. Nessun oggetto, all’interno della stessa azione, può essere richiesto dopo che sia stato effettuato un

rilascio di un altro oggetto.

Esempio 9.2 Si considerino le due seguenti azioni atomiche:

1 A1 : {

2 X = X + 20;

3 Y = Y + 20;

4 }

5

6 A2 : {

7 X = X * 20;

8 Y = Y * 20;

9 }

La relazione di consistenza è quindi . Si possono avere inconsistenze in caso di esecuzione parallela

X = Y

se non vengono rispettati tutti e tre i principi. Rispettando solo i primi due è possibile avere:

1 A1 : {

2 Richiesta (X);

3 X = X + 20;

4 Rilascio (X);

5 Richiesta (Y);

6 Y = Y + 20;

7 Rilascio (Y);

8 }

9

10 A2 : {

11 Richiesta (X);

12 X = X * 20;

13 Rilascio (X);

14 Richiesta (Y);

15 Y = Y * 20;

16 Rilascio (Y);

17 } 61

Se viene eseguita tra e di non viene più rispettata la relazione di

A2 Rilascio(X) Richiesta(Y) A1,

consistenza al termine dell’esecuzione di entrambe le azioni. Rispettando anche il terzo principio si ha:

1 A1 : {

2 Richiesta (X);

3 X = X + 20;

4 Richiesta (Y);

5 Rilascio (X);

6 Y = Y + 20;

7 Rilascio (Y);

8 }

9

10 A2 : {

11 Richiesta (X);

12 X = X * 20;

13 Richiesta (Y);

14 Rilascio (X);

15 Y = Y * 20;

16 Rilascio (Y);

17 }

Quest’ultimo assicura infatti che, quando un’azione rilascia un oggetto contenente il valore finale, nessuno

degli altri oggetti su cui l’azione opera sia libero e contenga il valore iniziale.

La ragione del protocollo deriva dal fatto che l’esecuzione di ogni azione atomica definisce 2 fasi successive:

1. Fase crescente: l’azione atomica acquisisce, in modo esclusivo, tutti gli oggetti ed opera su di essi.

2. Fase calante: inizia non appena viene eseguito il primo rilascio. Durante essa non possono essere

acquisiti ulteriori oggetti.

9.3.1 Commit

Si consideri ora il verificarsi di un guasto su una macchina nella quale viene eseguita un’azione atomica:

1. acquisisce ed esegue

A X X = X + 20;

1

2. acquisisce ;

A Y

1

3. rilascia contenente il valore finale;

A X,

1 ·

4. acquisisce ed esegue

A X X = X 20;

2

5. a causa di un malfunzionamento della macchina su cui esegue , l’oggetto viene riportato al valore

A X

1

precedente all’inizio di , la quale quindi viene abortita;

A 1

6. diventa ora necessario propagare l’aborto anche ad : gli effetti dell’ultima operazione di su e

A A X

2 2

su tutti gli altri oggetti acceduti da devono essere distrutti.

A 2

Ha quindi luogo, in questo scenario, un effetto domino in cui l’aborto di un’azione atomica genera, come

effetto collaterale, l’aborto di una diversa azione atomica, e così via. Ciò avviene perché l’azione atomica

rilascia un oggetto prima di aver completato la sequenza di operazioni su tutti gli oggetti interessati, e prima

di aver raggiunto uno stadio di avanzamento tale da garantire che, da quel punto in poi, l’azione atomica

non sarà più abortita in seguito al verificarsi di qualsiasi evento anomalo.

Per soddisfare la proprietà del tutto o niente occorre definire un ulteriore requisito:

4. Nessun oggetto può essere rilasciato prima che l’azione atomica abbia completato la sua esecuzione.

Il meccanismo di recupero deve quindi comportarsi in maniera diversa a seconda dell’istante in cui si

verifica l’evento anomalo. Tale meccanismo dovrà abortire l’azione se il malfunzionamento avviene quando

gli oggetti sono in stato inconsistente, altrimenti garantirne il completamento quando gli oggetti sono nel

nuovo stato consistente . A questo scopo, viene introdotta l’operazione primitiva commit, la quale

S 2

discrimina i due tipi di comportamento. Essa viene eseguita quando tutti gli oggetti sono giunti al valore

finale, e produce come effetto l’impossibilità di aborto dell’azione atomica.

62

Il quarto requisito si può quindi riformulare nel seguente modo: ogni azione atomica deve rilasciare i

propri oggetti solo dopo l’operazione di commit.

L’azione atomica terminerà, di conseguenza, in due modi possibili:

• Terminazione normale: se l’azione atomica porta a termine l’intera sequenza delle operazioni sugli

oggetti, terminando su uno stato finale (ossia esegue la commit).

• Terminazione anomala: se l’azione atomica non porta a termine l’intera sequenza di operazioni

sugli oggetti, i quali devono essere ripristinati al valore iniziale.

Le cause di una terminazione anomala sono principalmente 2:

• Si verifica un’eccezione sollevata durante una delle operazioni sugli oggetti. Il processo in questione

esegue la primitiva abort.

• Si verifica un malfunzionamento del sistema prima che le operazioni siano terminate. Il sistema di

recupero da malfunzionamento forza l’aborto dell’azione atomica tornando allo stato iniziale.

In entrambi i casi è necessario un meccanismo di supporto alle azioni atomiche in grado di ripristinare,

per ogni oggetto, il suo stato iniziale.

9.3.1.1 Meccanismo di ripristino

Per funzionare, il meccanismo necessita di informazioni relative allo stato corrente delle operazioni ed allo

stato iniziale degli oggetti.

Nel caso il malfunzionamento sia dovuto al verificarsi di eccezioni, queste informazioni risultano facilmente

disponibili. Nel caso invece di malfunzionamento hardware, si ha la perdita di tutte le informazioni residenti

in RAM. Nel caso in cui le informazioni su memoria di massa rimangano inalterate, è possibile che il crash

dell’elaboratore sia avvenuto durante il trasferimento di informazioni nella memoria di massa; questo scenario

permette di risolvere il problema facilmente, ma purtroppo non risulta sempre verificato. A tal proposito,

esiste l’astrazione della memoria stabile, la quale è caratterizzata da un uso ridondante delle informazioni.

Le operazioni per leggere e scrivere su questa memoria sono a loro volta atomiche, e rispettano il principio

del tutto o niente.

9.4 Realizzazione di azioni atomiche

9.4.1 Caso monoprocesso

Per specificare il tipo di operazione che deve eseguire il meccanismo di recupero (aborto o completamento

dell’operazione) dopo il crash della macchina, è necessario caratterizzare lo stato del processo in base allo

stato di avanzamento nell’esecuzione dell’azione atomica. Tale stato può essere:

• Working, ossia durante l’esecuzione del corpo dell’azione atomica. Quando il processo si trova in

questo stato, gli oggetti sono inconsistenti, pertanto se si verifica un crash, il meccanismo di recupero

deve abortire l’azione atomica.

• Committing, ossia durante la terminazione corretta dell’azione, pertanto gli oggetti si trovano già

nel loro stato finale a seguito di una commit. Se il crash avviene durante questo stato, il meccanismo

di recupero deve completare l’azione.

• Aborting. Se il crash avviene durante questa fase, il meccanismo di recupero deve garantire il

completamento del ripristino dei valori iniziali degli oggetti.

Le informazioni sullo stato in cui si trova un processo che esegue un’azione atomica vengono mantenute

aggiornate nel descrittore di azione, ossia una struttura dati allocata in memoria stabile.

La realizzazione dell’azione atomica si basa su 3 primitive:

• Begin action: crea, in memoria stabile, un descrittore di azione, inizializzando lo stato del processo

a working. 63

• Abort e commit, invece, commutano atomicamente lo stato del processo, rispettivamente, ad abor-

ting e committing.

Gli oggetti risiedono in memoria stabile e, all’inizio dell’azione atomica, ne viene creata, in memoria

volatile, una copia detta copia di lavoro sulla quale eseguire le operazioni. L’aborto dell’azione atomica

coincide con la distruzione delle copie di lavoro in memoria volatile, in quanto i valori iniziali da recuperare

si trovano in memoria stabile. In caso di terminazione, invece, i valori finali delle copie di lavoro sono salvati

nella copia valida in memoria stabile.

La procedura di terminazione prevede una sequenza di operazioni stable write durante le quali, se

l’elaboratore subisce un crash, si ha uno stato inconsistente. A questo proposito, viene creata una copia

dei valori finali in memoria stabile, detta copia delle intenzioni, prima della commit, senza che venga

modificata la copia stabile originale. Solo se la copia delle intenzioni è stata correttamente memorizzata,

viene successivamente trasferito il suo valore nella copia originale:

void

1 terminazione ( descrittore_azione x) {

2 // Creazione della copia delle intenzioni in memoria stabile

3 commit (x); // Passaggio di stato da working a committing

4 // Trasferimento dei valori dalla copia delle intenzioni alla copia degli

oggetti in memoria stabile

5 // Distruzione della copia delle intenzioni

6 }

Se l’elaboratore subisce un crash durante la fase di creazione della copia delle intenzioni, la copia originale

degli oggetti in memoria stabile rimane inalterata al valore iniziale. L’azione viene quindi abortita e viene

distrutta la copia delle intenzioni. Se il crash avviene invece durante la fase di trasferimento, la copia finale

può corrompersi, ma rimane valida in memoria stabile la copia delle intenzioni. In fase di riattivazione, la

seconda fase della procedura viene eseguita dall’inizio.

9.4.2 Caso multiprocesso

In questo modello, le azioni sugli oggetti sono eseguite da più processi. Si consideri lo scenario in cui i singoli

processi operino, ciascuno, su sottoinsiemi di oggetti disgiunti, in modo che sia scongiurata competizione

tra i diversi processi sugli oggetti condivisi.

Se ogni processo esegue il two phase lock protocol, rilasciando gli oggetti su cui opera dopo la terminazione

dell’azione, è assicurata la proprietà di serializzabilità dell’azione atomica. Per la proprietà del tutto o niente,

invece, è necessario che tutti i processi completino le loro operazioni con lo stesso risultato: o con successo,

o con abort. Diventa quindi necessario introdurre un nuovo stato, ready, che indica se un processo ha

completato la propria sequenza di azioni ed è pronto a terminare con successo, ma deve attendere che gli

altri processi completino le loro operazioni. crash

9.4.2.1 Two phase commit protocol ready

La transizione da working a ready si ha quando il processo

esegue la primitiva prepare, mediante la quale il processo prepare commit

perde il diritto di abortire in modo unilaterale. begin end

Il protocollo che ciascun processo esegue, per negoziare committing

working

il tipo di completamento, prende il nome di two phase

commit protocol. Esso si svolge in due fasi: crash

abort abort end

aborting

1. ciascun processo specifica la propria scelta tra successo

o aborto; crash

2. viene verificata l’opzione degli altri: se tutti i proces-

si hanno optato per la terminazione con successo, essi Figura 9.1: Diagramma degli stati nel modello

transitano in stato committing, mentre se almeno un multiprocesso: il passaggio da ready ad aborting

avviene solo se richiesto da un altro processo.

processo ha abortito, tutti transitano in stato aborting.

64

Se si verifica un crash quando un processo è in stato ready, il meccanismo di recupero deve ripristinare,

per tale processo, lo stato ready. Il processo non può infatti essere riattivato in stato aborting poiché, con

prepare, ha perso il diritto di abortire unilateralmente. Ciò non può avvenire neanche in stato committing,

poiché ciò presuppone che tutti siano pronti a terminare correttamente.

Il descrittore di azione atomica, in memoria stabile, dovrà quindi mantenere aggiornato lo stato di tutti i

processi partecipanti.

9.4.2.2 Modello a memoria comune

Nel modello a memoria comune il descrittore di azione è un monitor. Lo schema di funzionamento del

processo si articola come segue:

i-esimo

1. richiesta esclusiva degli oggetti;

2. creazione delle copie volatili degli oggetti;

3. sequenza di operazioni sulle copie volatili;

4. terminazione.

In caso di terminazione con fallimento si entra nello stato aborting, si riporta l’informazione sul descrittore

di azione e vengono risvegliati i processi nello stato di ready.

In caso di successo:

1. si crea la copia delle intenzioni in memoria stabile;

2. si transita nello stato di ready attraverso l’esecuzione della prepare, quindi viene modificato lo stato

da working a ready nel descrittore di azione atomica;

3. si verifica se almeno un processo è in stato aborting:

• in caso affermativo si distrugge la copia delle intenzioni si esegue l’abort;

• in caso negativo si possono verificare due casi:

– qualche altro processo è ancora in stato di working: il processo resta nello stato ready e si

blocca;

– tutti i processi sono nello stato di ready: il processo entra nello stato committing, trasferisce

gli oggetti dalla copia delle intenzioni a quella originale e distrugge la copia delle intenzioni,

risvegliando un altro processo che si era precedentemente bloccato. Il processo risvegliato

completa la sua esecuzione, risvegliando a sua volta un altro processo, e così via.

9.4.2.3 Modello a scambio di messaggi

Il descrittore è un oggetto privato di un processo detto coordinatore dell’azione atomica.

Il processo coordinatore, qualora si mostri disponibile a terminare con successo l’azione atomica, crea la

copia delle intenzioni in memoria stabile, esegue la prepare per entrare nello stato ready, quindi invia ad

ogni partecipante un messaggio di richiesta dell’esito e si pone in attesa delle risposte:

• In caso il processo coordinatore ottenga almeno un esito negativo, viene eseguita la primitiva abort

e viene inviato un messaggio in cui si richiede il completamento con aborto a tutti i partecipanti. Il

coordinatore termina abortendo a sua volta.

• Se tutti i partecipanti rispondono con esito positivo, l’azione deve terminare con successo:

1. Viene eseguita la primitiva commit e viene inviato, a ciascun partecipante, un messaggio con

l’indicazione di terminare con successo. Il coordinatore rimane in attesa del messaggio di avvenuto

completamento da parte di tutti i partecipanti.

2. All’arrivo di tutti i messaggi di avvenuto completamento, il coordinatore termina eliminando il

descrittore dell’azione atomica. 65

Ogni processo, invece, terminate le operazioni sugli oggetti, può o aver abortito, o aver creato la copia delle

intenzioni e quindi trovarsi in stato ready. In entrambi i casi, il processo attende il messaggio di richiesta

sull’esito da parte del coordinatore, al quale risponde con un esito positivo o negativo a seconda dello stato

in cui si trova:

• Se è in stato aborting, termina abortendo.

• Se è in stato ready, resta in attesa del messaggio di completamento da parte del coordinatore:

– Se viene ricevuto il messaggio di completare con aborto, viene eliminata dalla memoria stabile la

copia delle intenzioni ed il processo termina abortendo.

– Se viene ricevuto il messaggio di completare con successo, il processo termina correttamente,

trasferendo i valori della copia delle intenzioni nella copia originale degli oggetti, quindi eliminando

la copia delle intenzioni ed inviando al coordinatore il messaggio di avvenuto completamento.

9.4.2.4 Malfunzionamenti

Nei sistemi distribuiti possono verificarsi due tipi particolari di malfunzionamenti:

• Crash o malfunzionamento dei singoli nodi della rete.

• Perdita o invalidazione dei messaggi in rete.

Con l’utilizzo di un temporizzatore è possibile limitare il tempo di attesa di un messaggio. Al termine del

tempo previsto, il processo viene riattivato, quindi viene eseguita una procedura per richiedere nuovamente

l’informazione oppure per abortire.

Per far fronte al crash dei singoli nodi, invece, ogni processo partecipante deve mantenere, in memoria

stabile, delle variabili di stato da utilizzare in fase di riattivazione.

9.4.3 Azioni atomiche nidificate

Si considerino due azioni atomiche e , in cui è nidificata all’interno di , ossia costituisce una

A A A A

1 2 2 1

delle operazioni eseguite da . Quando termina, il processo che la esegue rilascia tutti gli oggetti su

A A

1 2

cui ha operato. Essi sono disponibili per essere acquisiti da altri processi e, quindi, è possibile operarvi

A

2

all’interno di altre azioni atomiche.

In questo modello si ha una violazione della proprietà di serializzabilità nell’azione atomica in quanto,

A 1

se termina correttamente, essa modifica la copia stabile degli oggetti su cui ha operato e li rilascia.

A 2

Tuttavia, si ha anche la violazione della proprietà del tutto o niente per l’azione atomica in quanto, se

A

1

non termina correttamente dopo la conclusione di , abortisce, annullando tutte le modifiche effettuate

A A

1 2

sugli oggetti. Devono essere quindi ripristinati al valore iniziale anche gli oggetti di , ma, per la corretta

A 2

terminazione di , questi valori sono andati perduti.

A 2

Il problema può essere risolto modificando i protocolli di two phase lock protocol e two phase commit

protocol, in modo che siano rispettati i seguenti vincoli:

1. Una sotto-azione che termina con successo rende disponibili, in modo esclusivo, gli oggetti all’azione

atomica al cui interno la sotto-azione è nidificata. Si evita la visibilità degli stati intermedi di un’azione

atomica a causa della corretta terminazione di una sua sotto-azione.

2. Quando una sotto-azione termina con successo, la sua fase di commit viene ritardata ed eseguita solo

se l’azione più esterna termina con successo. In caso di aborto dell’azione esterna, tutte le sotto-azioni

devono essere abortite, e la modifica degli oggetti in memoria stabile è effettuata dall’azione atomica

più esterna.

Per garantire questo tipo di comportamento viene mantenuta aggiornata, per ogni oggetto, una pila di

copie di lavoro e, all’inizio di una sotto-azione, viene generata una nuova copia in testa alla pila. Se la

sotto-azione termina con successo, la copia in testa alla pila diventa la nuova copia di lavoro per l’azione

più esterna. Diversamente, viene scartata la copia in testa alla pila.

66

9.5 Realizzione della memoria stabile

Come già visto, la memoria stabile è un tipo di memoria astratta dotata delle seguenti proprietà:

1. non è soggetta a malfunzionamenti;

2. le informazioni in essa residenti non vengono perdute o alterate al verificarsi di un crash.

La prima proprietà si ottiene con la messa in atto di tecniche di memorizzazione dei dati che fanno uso di

ridondanza come i meccanismi RAID. La seconda proprietà richiede che le operazioni di lettura e scrittura

siano atomiche (stable read e stable write).

I tipi di malfunzionamento da gestire sono:

1. Errori in lettura: possono essere eliminati rileggendo le informazioni desiderate con l’utilizzo dei

Codici di Ridondanza Ciclica CRC.

2. Errori in scrittura: possono essere rilevati rileggendo le informazioni scritte e confrontandole con

quelle originali. L’errore può essere eliminato riscrivendo le informazioni.

3. Alterazioni delle informazioni: sono causate da disturbi o guasti hardware che perdurano per un

certo numero di letture consecutive.

Per trattare l’ultimo tipo di malfunzionamenti si fa ricorso alla tecnica delle copie multiple con ridon-

danza di livello due, ossia alla duplicazione di tutte le informazioni su due unità disco distinte.

I primi due tipi di malfunzionamento, invece, sono dovuti a disturbi temporanei. Un disco permanente

è un’astrazione ottenuta eliminando ogni tipo di guasto temporaneo. Un blocco stabile è invece una coppia

di blocchi, uno per ogni disco permanente, per cui si ipotizza che le due copie non vengano alterate entrambe

dallo stesso malfunzionamento. In questo modo, in fase di lettura, almeno una delle copie deve contenere il

valore corretto. Utilizzando una coppia di dischi permanenti è quindi possibile realizzare l’astrazione della

memoria stabile: il valore contenuto in un blocco stabile coincide con il valore del primo blocco se questo

contiene dati corretti, altrimenti coincide con il valore del secondo blocco.

La memoria stabile è realizzata come un monitor. Ciò garantisce l’indivisibilità delle sue operazioni.

La stable read gode della proprietà del tutto o niente poiché non esegue alcuna modifica. Relativamente

alla stable write, invece, se si verifica un guasto durante l’operazione di scrittura:

• sul primo blocco, questo viene alterato, ma rimane valido il secondo (effetto niente dell’operazione);

• sul secondo blocco, rimane valido il primo (effetto tutto dell’operazione);

• tra le due scritture, entrambi i blocchi rimangono validi, ma con valori diversi. Si termina quindi

l’operazione copiando il primo blocco nel secondo.

Le azioni atomiche vengono spesso utilizzate come strumento per strutturare applicazioni transazionali.

Una transazione è una sequenza di operazioni effettuate, per esempio, su un database, le quali fanno

transitare il sistema da uno stato all’altro. Tali stati devono essere consistenti, e la transazione deve rispettare

le proprietà ACID:

• Atomicità: la transazione deve essere un’entità indivisibile.

• Consistenza: il database deve transitare da uno stato corretto ad un altro stato corretto.

• Isolamento: le informazioni devono essere protette durante l’esecuzione della transazione.

• Durata: al completamento della transazione, i suoi effetti sul database devono rimanere persistenti.

Essi possono essere alterati soltanto da altre transazioni, ma non da malfunzionamenti del sistema.

67

Appendice A

Esercitazione I

A.1 Standard POSIX

Portable Operating System Interface for Unix POSIX è uno standard definito dall’IEEE negli anni

’80. pthreads è una libreria per lo sviluppo di applicazioni concorrenti multi-threaded ed è compatibile con

lo standard POSIX. Essa permette la gestione e la sincronizzazione di thread in ambiente Unix: creazione,

terminazione, join, mutua esclusione e semafori.

In Linux è possibile fare uso di thread anche tramite system call native come la Essi hanno tuttavia

clone.

il problema di essere poco portabili, al contrario della libreria pthreads che, essendo conforme allo standard

POSIX, è estremamente portabile.

LinuxThreads è l’implementazione di phtreads in ambiente GNU/Linux.

A.2 pthreads

A.2.1 Identificativo

L’identificatore di un thread è definito dal tipo di dato Esso è, di fatto, un

pthread_t. long unsigned,

dichiarato nell’header file pthread.h.

Per restituire l’identificatore all’interno del codice di un thread, è possibile utilizzare la funzione

1 pthread_t pthread_self (void);

A.2.2 Creazione

Per creare un thread si usa la funzione

int

1 pthread_create ( pthread_t *thread ,

2 pthread_attr_t *attr ,

void

3 *(* start_routine )(void *),

void

4 *arg);

dove:

• è il puntatore della variabile che raccoglierà l’identificatore del thread TID;

thread

• è il puntatore alla funzione che contiene il codice del nuovo thread;

start_routine

• è il puntatore all’eventuale vettore contenente i parametri della funzione da eseguire;

arg

• può essere usato per specificare eventuali attributi da associare al thread, come parametri di

attr

scheduling e legami con gli altri thread (solitamente è NULL).

Restituisce in caso di successo, un valore diverso altrimenti. L’utilizzo del puntatore a utilizzato

0 void,

anche successivamente, permette di ottenere il massimo della genericità.

68

A.2.3 Terminazione

Nei processi pesanti era possibile, tramite la trasferire al padre il risultato. Utilizzando la libreria

exit,

pthreads, tramite la funzione:

void

1 pthread_exit (void * retval );

è possibile ottenere il comportamento analogo, dove è il puntatore all’area di memoria che contiene

retval

il valore di ritorno e può essere raccolto da altri thread attraverso la join.

Alternativamente, è possibile usare un nel codice del thread.

return

A.2.4 Join

Permette ad un thread di sospendersi in attesa della terminazione di un altro thread:

int void

1 pthread_join ( pthread_t th , ** thread_return );

dove:

• è il TID del particolare thread da attendere;

th

• quando è diverso da memorizza il valore di ritorno del thread.

thread_return, NULL,

In generale è necessario che il padre chiami sempre la altrimenti rimangono allocate le aree di

join,

memoria ad esso assegnate; in alternativa è possibile staccare il thread figlio dal padre, in modo che la join

sia chiamata automaticamente dal sistema per deallocare i dati usando:

int

1 pthread_detach ( pthread_t th);

A.2.5 Compilazione

Per compilare si usa:

1 gcc -D_REENTRANT -o program program .c –lpthread

Il flag permette un’esecuzione thread safe, garantendo che l’accesso alle variabili di sistema

-D_REENTRANT

avvenga in modo corretto, il buffer di I/O condiviso sia gestito in mutua esclusione ed ogni thread gestisca

gli errori in maniera separata.

A.2.6 Semafori

La libreria pthreads definisce solo i semafori di mutua esclusione, mentre LinuxThreads definisce e imple-

menta anche i semafori generici, sempre conformi allo standard POSIX.

A.2.6.1 Mutua esclusione

I semafori binari di mutua esclusione assumono sempre come valore 0 o 1 e sono di tipo pthread_mutex_t.

Le operazioni possibili su questi semafori sono:

• inizializzazione con pthread_mutex_init;

• locking, cioè la , con pthread_mutex_lock;

P

• unlocking, cioè la , con pthread_mutex_unlock.

V 69

A.2.6.1.1 Inizializzazione Un semaforo è inizializzato con:

int

1 pthread_mutex_init ( pthread_mutex_t *mutex , pthread_mutexattr_t *attr);

dove:

• individua il semaforo da inizializzare;

mutex

• punta ad una struttura che contiene gli attributi da applicare come il valore iniziale, se

attr NULL

viene inizializzato a libero (cioè 1).

In alternativa, è possibile usare la macro per inizializzare il semaforo al valore

PTHREAD_MUTEX_INIZIALIZER

di default.

A.2.6.1.2 Lock e unlock Le operazioni di e sono eseguite rispettivamente con:

P V

int

1 pthread_mutex_lock ( pthread_mutex_t * mutex);

e int

1 pthread_mutex_unlock ( pthread_mutex_t *mutex);

Nel caso della se il semaforo è a 0, il thread chiamante si sospende, altrimenti occupa il semaforo.

lock,

La unlock invece, se vi sono processi in attesa, ne risveglia uno, altrimenti libera il semaforo.

A.2.6.2 Semafori di LinuxThreads

Questi semafori sono definiti nella libreria come tipo In particolare si ha:

semaphore.h sem_t.

• per inizializzare un semaforo;

sem_init

• che implementa la ;

sem_wait P

• che implementa la .

sem_post V

Queste ultime due operazioni accettano come unico parametro un puntatore al semaforo su cui operare.

A.2.6.2.1 Inizializzazione Il semaforo è creato con:

1 int sem_init ( sem_t *sem , int pshared , unsigned int value);

dove:

• individua il semaforo da inizializzare;

sem

• è impostato a 0 se il semaforo non è condiviso tra task, 1 altrimenti;

pshared

• è il valore iniziale da assegnare al semaforo.

value 70

Appendice B

Modelli di processi servitori

B.1 Pool di risorse equivalenti 1. Richiesta

client server

Per ognuna delle risorse equivalenti si ha un processo che la 2. #i

gestisce. È inoltre presente un’entità centrale server che si

occupa, per ognuna delle richieste, di verificare lo stato del 4. Rilascio

3. Operazione

pool. Se sono presenti processi liberi da “allocare” al client,

allora, essa restituirà a quest’ultimo l’indice del processo libero

in modo da comunicare direttamente, altrimenti viene messo P P P

1 i n

in attesa. Una volta effettuata la richiesta, il client contatta Figura B.1: Protocollo gestione di un pool di

nuovamente il server per rilasciare la risorsa. risorse nel modello a scambio di messaggi.

Per quanto riguarda il client si ha:

1 process cliente {

int

2 port risorsa ;

3 signal s;

int

4 r;

5 process p, server ;

6

7 send(s) to server . richiesta ; // Richiesta della risorsa

8 p = receive (r) from risorsa ; // Attesa della riposta

9 // Uso delle risorsa r-esima

10 send (r) to server . rilascio ; // Rilascio della risorsa

11 }

Passando al server invece si ha:

1 process server {

2 port signal richiesta ;

int

3 port rilascio ;

int

4 disponibili = N;

5 boolean libera [N];

6 process p ;

7 signal s;

int

8 r;

9 for

10 (int i = 0; i < N; i++)

11 libera [i] = true; // Inizializzazione

12 do

13

14 [] disponibili > 0; p = receive (s) from richiesta ; -> {

int

15 i = 0;

while

16 (! libera [i])

17 i++;

18 libera [i] = false;

19 disponibili --;

20 send (i) to p. risorsa ;

21 }

22 [] p = receive (r) from rilascio ; -> {

71

23 disponibili ++;

24 libera [r] = true;

25 }

26 od

27 }

Il rilascio non prevede una sincronizzazione, pertanto non è presente una condizione logica nel ramo da

soddisfare. Non è possibile che entrambe le guardie falliscano, pertanto risulta impossibile uscire dal ciclo.

È tuttavia possibile che entrambe le guardie siano valide e, in questo caso, non è possibile prevedere quale

dei due rami si attiverà perché l’evento è non deterministico.

B.2 Simulazione di un semaforo

È possibile simulare il comportamento di un semaforo tramite l’utilizzo di un processo server in ascolto su

due porte e

P V:

1 process semaphore {

2 port signal P;

3 port signal V;

int

4 valore = I;

5 process proc ;

6 signal s;

7 do

8

9 [] valore > 0; p = receive (s) from P; -> {

10 valore --;

11 send (s) to proc. risposta ;

12 }

13 [] p = receive (s) from V; ->

14 valore ++;

15 od

16 }

Un eventuale processo client chiamerà quindi le due funzioni con i meccanismi già visti:

1 process client {

2 signal s;

3 port signal risposta ;

4

5 ...

6 // Chiamata di P

7 send(s) to semaphore .P;

8 receive (s) from risposta ;

9 ...

10 // Chiamata di V

11 send(s) to semaphore .V;

12 ...

13 }

B.3 Pool di risorse equivalenti con priorità

Il criterio di priorità deve privilegiare i processi con un indice più basso. I processi clienti avranno sempre

B.1). Per il processo server invece si ha:

la stessa struttura (presentata in §

1 process server {

2 port signal richiesta ;

int

3 port rilascio ;

int

4 disponibili = N;

5 boolean libera [N];

6 process p;

7 signal s; 72

int

8 r;

int

9 sospesi = 0;

10 boolean bloccato [M];

11 process client [M];

12

13 // Inizializzazione

for(int

14 i = 0; i < N; i++)

15 libera [i] = true;

for(int

16 j = 0; j < M; j++)

17 bloccato [j] = false;

18 client [0] = P0; // Salvo i riferimenti ai processi in un opportuno array

19 ...

20 client [M -1] = PM_1;

21 do

22

23 [] p = receive (s) from richiesta ; -> {

if(

24 disponibili > 0) {

int

25 i = 0;

while

26 (! libera [i])

27 i++;

28 libera [i] = false;

29 disponibili --;

30 send (i) to p. risorsa ;

else

31 } {

int

32 j = 0;

33 sospesi ++;

while(

34 client [j] != p)

35 j++;

36 bloccato [j] = true;

37 }

38 }

39 [] p = receive (r) from rilascio ; -> {

if(

40 sospesi == 0) {

41 disponibili ++;

42 libera [r] = true;

else

43 } {

int

44 i = 0;

while

45 (! bloccato [i])

46 i++;

47 sospesi --;

48 bloccato [i] = false ;

49 send (r) to client [i]. risorsa ;

50 }

51 }

52 od

53 }

B.4 Produttori-consumatori consumatore

produttore 1

Si prenda in considerazione un modello in cui sono presenti pronto

più produttori e un unico consumatore: in questo caso il smistatore

dati

processo server non è necessario, in quanto la soluzione è consumatore

i

offerta direttamente dalla porta a cui un produttore invia i dati

messaggi ed il produttore li preleva.

Nel caso invece di più consumatori, è necessario interporre consumatore

n

tra produttori e consumatori un processo server che funga

da smistatore. Esso ha il compito di scegliere il consumatore Figura B.2: Protocollo di uno schema

produttori-consumatori molti-a-molti nel modello

a cui inviare il messaggio in base alla disponibilità a ricevere a scambio di messaggi.

messaggi che i singoli consumatori comunicano al server.

73

Utilizzando la asincrona, inoltre, si elimina la necessità di introdurre esplicitamente un buffer,

send

in quanto i canali di comunicazione contengono già al loro interno un buffer di dimensione teoricamente

illimitata.

Il processo smistatore ha due porte: la porta per ricevere dati dai produttori, e la porta per

dati, pronto,

ricevere il messaggio di controllo inviato dai consumatori pronti a ricevere il messaggio. Ogni consumatore,

quando desidera ricevere un messaggio da un produttore, invia un messaggio di tipo sulla porta

signal

del server, quindi si mette in attesa di ricevere il messaggio sulla propria porta Il modello è

pronto dati.

pertanto di tipo pull.

Il codice dello smistatore, senza utilizzo di guardie, sarà:

1 process smistatore {

2 port T dati;

3 port signal pronto ;

4 T messaggio ;

5 process prod , cons;

6 signal s;

7 while

8 (true) {

9 cons = receive (s) from pronto ;

10 prod = receive ( messaggio ) from dati;

11 send( messaggio ) to cons.dati;

12 }

13 }

Si noti che la dimensione del buffer risulta implicitamente determinata dalla capacità del canale dati.

B.5 Mailbox

Diversamente dal modello precedente, qui è consumatore

produttore 1

1

presente un limite superiore esplicito alla di- pronto_prod pronto_cons

mensione del buffer dei messaggi: i messaggi ok_to_send

inviati, ma non ancora ricevuti, non possono consumatore

produttore mailbox i

i

essere più di . Questa limitazione introdu-

N dati

ce pertanto il vincolo che un nuovo messaggio dati

non possa essere inviato se il buffer è pieno. I consumatore

produttore n

n

consumatori, inoltre, non possono estrarre un

messaggio se il buffer è vuoto. In entrambi i ca- Figura B.3: Protocollo schema molti a molti nel modello a

scambio di messaggi.

si, la rispettiva operazione risulterà sospensiva

con l’uso di un’opportuna porta per segnalare che l’operazione è disponibile.

1 process mailbox {

2 port T dati;

3 port signal pronto_prod , pronto_cons ;

4 T messaggio ;

5 process prod , cons;

6 signal s;

int

7 contatore = 0;

8 do

9

10 [] contatore < N; prod = receive (s) from pronto_prod ; -> {

11 contatore ++;

12 send(s) to prod. ok_to_send ;

13 }

14 [] contatore > 0; cons = receive (s) from pronto_cons ; -> {

15 prod = receive ( messaggio ) from dati;

16 contatore --;

17 send( messaggio ) to cons.dati;

18 }

19 od

20 } 74

21

22 process produttore {

23 port signal ok_to_send ;

24 T messaggio ;

25 process p;

26 signal s;

27

28 // Produci il messaggio

29 send(s) to mailbox . pronto_prod ;

30 p = receive (s) from ok_to_send ;

31 send ( messaggio ) to mailbox .dati;

32 }

33

34 process consumatore {

35 port T dati;

36 T messaggio ;

37 process p;

38 signal s;

39

40 send(s) to mailbox . pronto_cons ;

41 p = receive ( messaggio ) from dati;

42 // Consuma il messaggio

43 } 75

Appendice C

Esercitazione III

Go è un linguaggio concorrente sviluppato da Google nel 2009, con primitive per lo scambio di messaggi.

Esso offre pertanto supporto per la creazione di canali, sincrone e asincrone e comandi con guardia.

send

Esempio C.1 – Hello World Per ogni nuovo linguaggio non può mancare il programma più famoso:

package

1 main

import

2 "fmt"

3 func

4 main () {

5 fmt.Print ("Hello World !\n")

6 }

Da linea di comando è possibile utilizzare:

1 go run hello.go # Compilazione ed esecuzione

2 go build hello .go # Solo compilazione

I due tool di sviluppo più utilizzati sono:

• LiteIDE: ambiente di sviluppo open source.

• GoClipse: plugin per Eclipse.

C.1 Costrutti linguistici

C.1.1 Dichirazioni e definizioni

var int

1 i // Variabile i di tipo intero

var

2 k = 0.99 // k variabile reale con valore iniziale 0.99

const

3 PI = 22. / 7. // Approssimazione della costante PI = 3.14

type struct int

4 Point { x, y } // Tipo Point

func int) int

5 sum(a, b { // Funzione che restituisce un intero

return

6 a + b

7 }

C.1.1.1 Short declaration

Soltanto all’interno del corpo di funzioni, le dichiarazioni possono essere espresse in modo più sintetico nella

forma: 1 v := value

dove il tipo della variabile è lasciato dedurre al compilatore (in questo caso quello della variabile value).

C.1.2 Assegnamento

L’assegnamento viene eseguito con la sintassi ma è anche possibile eseguire un assegnamento multiplo:

a = b, 76

1 x, y, z = f1 () , f2 (), f3()

2 a, b = b, a // Swap

Le funzioni possono restituire più di un risultato, pertanto è possibile scrivere:

1 nbytes , err := Write(buf)

per dichiarare due nuove variabili ed assegnare loro i valori di ritorno.

C.1.3 If

La sintassi è analoga a quella classica, ma non è necessario inserire fra parentesi tonde le condizioni, mentre

è obbligatorio l’utilizzo delle parentesi graffe anche per un’istruzione singola:

if

1 x < 5 {

2 less ()

3 }

4 if

5 x < 5 {

6 less ()

else if

7 } x == 5 {

8 equal ()

else

9 } {

10 more ()

11 }

Esiste inoltre la possibilità di inizializzare la condizione utilizzando il punto e virgola come separatore:

if

1 v := f(); v < 10 {

2 fmt. Printf ("%d less than 10\n", v)

else

3 } {

4 fmt. Printf ("%d not less than 10\n", v)

5 }

C.1.4 For

La sintassi è:

for

1 i := 0; i < 10; i++ { ... }

Come in C, esiste la possibilità di omettere gli argomenti e, quindi, di eseguire un ciclo infinito. Due

diversi modi per scriverlo sono:

for

1 ;; { fmt. Printf ("Ciclo infinito ") }

for

2 { fmt. Printf ("Ciclo infinito ") }

Sono possibili anche assegnamenti multipli, ma non una sequenza di istruzioni separate da richiedendo

,

pertanto un assegnamento multiplo invece dell’uso degli operatori di incremento e decremento:

for

1 i, j := 0, N; i < j; i, j = i + 1, j - 1 { ... }

C.1.5 Switch

Espresso in maniera simile al C, uno switch è:

switch

1 a {

case

2 0: fmt. Printf ("0")

default

3 : fmt. Printf ("non -zero")

4 }

Come è possibile notare, tuttavia, non vi è necessità di utilizzare il per impedire che vengano eseguiti

break

anche i casi successivi a quello che ha fatto match.

È inoltre possibile ottenere più espressività utilizzando più variabili:

77

switch

1 a, b := x[i], y[j] {

case return

2 a < b: -1

case return

3 a == b: 0

case return

4 a > b: 1

5 }

C.1.6 Funzioni

Le dichiarazioni vengono eseguite tramite la keyword func:

func float64 float64

1 square (f ) {

return

2 f * f

3 }

Come già accennato, una funzione può restituire più di un valore come:

func float64 bool)

1 MySqrt (f ) (float64 , {

if

2 f >= 0 {

return true

3 math.Sqrt(f),

else

4 } {

return false

5 0,

6 }

7 }

C.1.7 Array

Sono espressi come

var int

1 ar [10]

ed è possibile anche ottenerne la dimensione usando la funzione len():

len(ar)

1 X :=

Esiste la possibilità di definire slice come sotto-vettori:

1 A := ar [2:8] // A riferimento agli elementi del vettore ar

C.1.8 Struct

Sono molto simili a C, con la differenza che qui non esiste l’operatore per i puntatori a struct in quanto

->

la dereferenziazione è automatica.

type struct

1 Point {

float64

2 x, y

3 }

4 var

5 p Point

6 p.x = 7

7 p.y = 23.4

8 var new(Point)

9 pp * Point = // Allocazione dinamica

10 *pp = p

11 pp.x = 3.14 // Equivalente a (* pp).x

C.2 Struttura

Un programma è composto da un insieme di moduli detti package, ognuno definito da uno o più file sorgenti,

e contiene almeno il package dal quale ha inizio l’esecuzione. Il codice di ogni package è costituito

main 78

da un insieme di funzioni, che a loro volta possono riferire nomi (ossia funzioni), tipi, variabili e costanti

esportate da altri package mediante la sintassi: packagename.ItemName.

L’importazione di nomi definiti in un package avviene con la seguente sintassi:

import

1 "pippo "

2 ...

3 pippo.Util ()

Per l’esportazione, invece, si deve tenere conto del fatto che solo i nomi che iniziano per maiuscola possono

essere esportati:

package

1 pippo

const

2 GLO = 100 // Esportata

var float64

3 priv = 0.99 // Privata

func

4 Util () { ... } // Esportata

Esempio C.2 Per prima cosa si definisce il package sfruttando la funzione chiamata automa-

init(),

ticamente da Go prima dell’importazione (se presente) per inizializzare le variabili:

package

1 pigreco

2 import

3 "math"

4 var float64

5 Pi

func

6 init () { // init inizializza la variabile globale Pi

7 Pi = 4 * math.Atan (1)

8 }

È ora possibile utilizzare il package come:

package

1 main

2 import

3 (

4 "fmt"

5 " pigreco "

6 )

var

7 twoPi = 2 * pigreco .Pi

func

8 main () {

9 fmt. Printf ("2*Pi = %g\n", twoPi )

10 }

C.3 Concorrenza

L’unità di esecuzione concorrente è la goroutine, una funzione che esegue in maniera concorrente ad altre

goroutine nello stesso spazio di indirizzamento.

C.3.1 Crezione

Per avviare una gorutine è sufficiente una normale chiamata a funzione, preceduta dalla keyword go:

func string int64)

1 IsReady (what , minutes {

2 time. Sleep ( minutes *60*1 e9) // Unità: nanosecondi

3 fmt. Println (what , " is ready")

4 }

5 func

6 main () {

go

7 IsReady ("tea", 6)

go

8 IsReady (" coffee ", 2)

9 fmt. Println ("I'm waiting ...")

10 ...

11 }

In questo modo sono stati creati 3 thread: il main e due isReady.

79

C.4 Canali

I processi comunicano attraverso l’utilizzo di canali che permettono sia la comunicazione che la sincro-

nizzazione tra goroutines. Go permette la creazione di ogni combinazione possibile di canale (simme-

trico/asimmetrico, sincrono/asincrono e bidirezionale/monodirezionale) e l’implementazione è un oggetto

tipato: var chan

1 ch <tipo > // <tipo > dei messaggi

C.4.1 Inizializzazione

var chan bool

1 C1 , C2

make(chan bool)

2 C1 = // Canale non bufferizzato : send sincrone

make(chan bool

3 C2 = , 100) // Canale bufferizzato : send asincrone

C.4.2 Utilizzo

Tramite l’operatore è possibile esprimere sia che

<- send receive.

C.4.2.1 Invio

Ponendo il canale a sinistra dell’operatore e il valore da inviare a destra, è possibile esprimere la come:

send

make(chan int)

1 c :=

2 c <- 1 // Invio il valore 1 in c (send sincrona )

C.4.2.2 Ricezione

In maniera analoga, ponendo il canale a destra e un’istruzione di assegnamento (o dichiarazione) a sinistra,

è possibile esprimere la receive:

1 v = <- c // Riceve un valore da c e lo assegna v

2 <- c // Riceve un messaggio da c che viene scartato

3 i := <- c // Riceve un messaggio , il cui valore inizializza i

Eseguire una da un canale non inizializzato (ossia con valore è bloccante.

receive nil)

Esempio C.3 Unendo le due primitive è possibile avere un esempio completo:

func chan int)

1 partenza (ch <- {

for

2 i := 0; ; i++ { ch <- i } // Invia

3 }

func chan int)

4 arrivo (ch <- {

for

5 { fmt. Println (<-ch) } // Ricevi e stampa

6 }

7 make(chan int)

8 ch1 :=

go

9 partenza (ch1)

go

10 arrivo (ch1)

Si noti l’uso di nella definizione delle funzioni, al fine di vincolare l’uso del canale, rispettivamente, al

<-

solo invio e ricezione.

C.4.2.3 Sincronizzazione padre-figlio

Per imporre al padre l’attesa della terminazione di un figlio, si fa uso di un canale dedicato alla sincroniz-

zazione: 80

var make(chan bool)

1 done =

2 func

3 figlio () {

4 ... true

5 done <-

6 }

7 func

8 main () {

go

9 figlio ()

10 <- done // Attesa del figlio

11 }

Non risulta di interesse valutare il messaggio trasferito attraverso pertanto esso viene scartato ed il

done,

processo main rimane in attesa fino alla terminazione del figlio.

C.4.2.4 Funzioni-canali

È possibile che una funzione restituisca un canale:

func chan int

1 partenza () {

make(chan int)

2 ch :=

go func

3 () {

for

4 i := 0; ; i++ { ch <- i }

5 }()

return

6 ch

7 }

8

9 stream := partenza () // Stream è un canale int

10 fmt. Println (<- stream ) // Stampa il primo messaggio : 0

Si noti inoltre che non è necessario definire preventivamente una funzione per invocarla come gorutine, ma

è possibile farne una dichiarazione anonima inline ed invocarla al momento.

C.4.2.5 Chiusura canale

Un canale può essere chiuso dal mittente tramite la close:

close(ch)

1

Il destinatario può quindi verificare se il canale è chiuso nel modo seguente:

1 msg , ok := <-ch

se il canale è ancora aperto, vale altrimenti perché il mittente lo ha chiuso.

ok true, false

C.4.2.6 Range

È una clausola che, all’interno di un for, permette di ripetere la da un canale fino a che questo non

receive

viene chiuso:

for range

1 v := ch { fmt. Println (v) }

ed equivale a:

for

1 {

2 v, ok := <-ch

if else break

3 ok { fmt. Println (v) } { }

4 }

C.4.3 Send asincrone

Come già accennato, la creazione di un canale bufferizzato permette un meccanismo asincrono di invio e

ricezione: 81

make(chan int

1 c := , 50)

go func

2 () {

3 time. Sleep (60 * 1e9)

4 x := <- c

5 fmt. Println (" Ricevuto ...", x)

6 }()

7 fmt. Println (" Sending ...", 10)

8 c <- 10 // Non sospensiva

9 fmt. Println (" Inviato ", 10)

C.5 Select

è un’istruzione di controllo, analoga al comando con guardia alternativo:

select select

1 {

case

2 /* Guardia 1 */:

3 // Istruzioni 1

case

4 /* Guardia N */:

5 // Istruzioni 2

6 ...

case

7 /* Guardia N */:

8 // Istruzioni N

9 }

Analogamente al comando con guardia alternativo, la selezione di un ramo è non deterministica. Nella

le guardie sono solo o Go, infatti, non prevede la guardia logica, pertanto si avranno

select, receive send.

solo guardie valide o ritardate.

make(chan int), make(chan string

1 ci , cs := )

select

2 {

case

3 v := <- ci:

4 fmt. Printf (" ricevuto %d da ci\n", v)

case

5 v := <- cs:

6 fmt. Printf (" ricevuto %s da cs\n", v)

7 }

C.5.1 Guardia logica

Basandosi sul fatto che una eseguita su un canale è sospensiva, è possibile costruire la guardia

receive nil

logica usando una funzione:

func bool chan int) chan int

1 when( condition , ch {

if

2 ! condition {

return nil

3

4 }

5 return

6 ch

7 }

Essa restituisce il canale passato se la condizione è vera, altrimenti. È perciò possibile effettuare la

ch nil

su quanto restituito dalla funzione:

receive select

1 {

case

2 msg := <- when( contatore < N, dati):

3 contatore ++

4 // Inserimento del messaggio nel buffer

case

5 x := <- when( contatore > 0, pronto_cons ):

6 contatore --

7 // Invio primo messaggio al consumatore che l'ha richiesto

8 } 82


PAGINE

96

PESO

433.71 KB

PUBBLICATO

6 mesi fa


DESCRIZIONE APPUNTO

Conoscenze e abilità da conseguire
Conoscenza delle problematiche di progetto relative all'organizzazione di sistemi concorrenti. Modelli di riferimento per la sincronizzazione e comunicazione tra processi. Metodologie di analisi e sintesi di sistemi concorrenti.

Programma/Contenuti
1.Protezione e sicurezza

Richiami sulla protezione: modelli, politiche e meccanismi
Sicurezza multilivello
Reference Monitor e sistemi fidati
2. Virtualizzazione

Virtualizzazione dell'hardware: finalità e soluzioni
Realizzazione di virtual machine monitor: virtualizzazione e paravirtualizzazione
Analisi e sperimentazione di tecnologie: il caso di xen
Virtualizzazione come supporto al cloud computing
3. Programmazione concorrente

Introduzione e definizioni
Processi non sequenziali.
Tipi di interazione
Architetture e linguaggi per la programmazione concorrente
4. Modello a memoria comune

Richiami su:

Mutua esclusione
Semafori
Monitor
Variabili condizione
Uso di linguaggi concorrenti nel modello a memoria comune: Java, c/pthread, Ada.

5. Modello a scambio di messaggi

Aspetti caratterizzanti
Richiami su canali e primitive
Primitive send e receive
Comandi con guardia
Rendez-vous e chiamata di procedura remota
Uso di Linguaggi concorrenti nel modello a scambio di messaggi: go, ada.

6. Nucleo di un sistema a processi basato sul modello a memoria comune:

Realizzazione dei meccanismi di gestione dei thread e di sincronizzazione all’interno del kernel di un sistema monoprocessore
Estensione al caso multiprocessore: Modello a nucleo condiviso SMP, Modello loosely-coupled.
7.Sistemi operativi distribuiti

caratteristiche dei sistemi operativi distribuiti
algoritmi per il controllo distribuito: mutua esclusione distribuita, algoritmi di elezione, gestione deadlock.
8.Azioni atomiche

Proprietà
Azioni atomiche multiprocesso
Azioni atomiche innestate
Uso di azioni atomiche nei sistemi distribuiti
Realizzazione dell'azione atomica nel modello a scambio di messaggi e nel modello a memoria comune


DETTAGLI
Corso di laurea: Corso di laurea magistrale in ingegneria informatica
SSD:
Università: Bologna - Unibo
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher piscoTech di informazioni apprese con la frequenza delle lezioni di Sistemi Operativi M e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Bologna - Unibo o del prof Ciampolini Anna.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Sistemi operativi m

Domande di Teoria di Sistemi Operativi
Appunto