1

Esercitazione

• Sistemi distribuiti: sistemi che risisedono su più calcolatori interconnessi da una rete di comunicazione

• Algoritmi distribuiti: programmi costituiti da più processi in esecuzione ciascuno su una macchina diversa.

• I processi non condividono memoria primaria nè secondaria

• Gli algoritmi distribuiti utilizzano un processo coordinatore per svolgere funzioni quali la mutua esclusione o la ricerca di deadlock

2

Esercitazione

• Quando il processo coordinatore termina in modo anomalo l’algoritmo distribuito può continuare a funzionare correttamente solo se uno dei processi rimasti diviene il nuovo processo coordinatore

• La scelta del nuovo processo coordinatore viene fatta tramite un algoritmo distribuito di elezione messo in atto dai processi che partecipano all’algoritmo distribuito.

3

Esercitazione:

• Scopo dell’esercitazione è l’implementazione di una simulazione di un algoritmo distribuito di elezione noto come ring algorithm

• Il nome deriva dal fatto che i processi che implementano l’algoritmo sono organizzati in uno schema ad anello, in cui ogni processo comunica solo con il processo adiacente (a destra o a sinistra)

4

Osservazioni generali:

• Ad ogni processo nel sistema distribuito è assegnata una priorità unica e nota solo a quel processo

• Il processo coordinatore è sempre quello con valore di priorità più grande

• Ogni processo conosce solo la propria priorità e non quella degli altri processi attivi, eccetto che durante l’esecuzione della procedura di elezione

5

Considerazioni generali:

• Per il corretto funzionamento dell’algoritmo distribuito, tutti i processi devono conoscere l’identità del processo coordinatore

• I processi sono organizzati in un anello circolare unidirezionale: ogni processo può inviare messaggi solo al suo vicino di destra o di sinistra (ma non ad entrambi)

6

Esempio di configurazione:

P1, 5

P2, 7 P3, 2

7

Considerazioni generali:

• La struttura dati principale usata dall’algoritmo di elezione è l’active list che è formata da un elenco di coppie <Processo,Priorità>, una coppia per ogni processo coinvolto nell’algoritmo

• Ogni processo possiede una copia della active list, identica per tutti i processi.

8

Considerazioni generali:

• Non può esistere una copia della active list in memoria condivisa o in un file (si ricordi che si sta simulando una situazione con processi che girano su macchine diverse, che quindi non condividono nessun tipo di memoria)

• Al termine dell’algoritmo di elezione la active list contiene informazioni aggiornate su tutti i processi attivi e ogni processo può individuare il nuovo coordinatore

9

L’algoritmo da implementare:

• Passo 1.– Quando un processo Pi con priorità p

scopre che il processo coordinatore non è più attivo, fa partire l’algoritmo di elezione, creando un propria active list inizialmente vuota.

– Poi invia un messaggio elect(Pi,p) al suo vicino, in modo da proporsi come nuovo processo coordinatore, e aggiunge la propria priorità e identificatore alla active list

10

L’algoritmo da implementare:

• Passo 2.– Se un processo Pi riceve un

messaggio elect(Pj,q) dal suo vicino, capisce che è in corso una procedura di elezione, e deve rispondere in uno dei seguenti tre modi:

a) Se questo è il primo messaggio elect che ha visto o mandato, Pi crea una propria active list con i valori (Pi,p) e (Pj,q). Poi manda il messaggio elect(Pi,p) seguito dal messaggio elect(Pj,q). (attenzione, l’ordine è importante. Perchè?)

11

L’algoritmo da implementare:

• (Passo 2 cont.: caso in cui questo non è il primo messaggio elect che Pi riceve/invia)

b) Se Pi != Pj allora Pi aggiunge (Pj,q) alla lista e inoltra il messaggio al suo vicino (manda elect(Pj,q))

c) Se Pi=Pj, allora la active list di Pi contiene tutte le informazioni sui processi attivi nel sistema.

• Passo 3:– Il processo Pi può determinare il coordinatore

cercando il processo con priorità massima nella active list.

12

I processi Pi• Il generico processo Pi esegue un

ciclo infinito in cui dorme per un breve periodo di tempo e quando si sveglia controlla se l’algoritmo di elezione è stato iniziato (cioè se è arrivato un messaggio elect)– Se sì vi partecipa,– se no torna a dormire.

• Esempio di codice:while (1) { sleep(5); if (check_election()) partecipate(); }

13

Avvio dell’algoritmo di elezione

• Il fallimento del processo coordinatore è segnalato ad un processo qualunque tra quelli attivi tramite l'invio del segnale SIGUSR1 da parte dell'utente.

• Il processo che riceve il segnale inizia l’algoritmo di elezione.

• La procedura di gestione del segnale SIGUSR1 può quindi ospitare il codice dell’algoritmo di elezione.

14

Terminazione dell’algoritmo di elezione

• Al termine dell’algoritmo, i processi scrivono su un file di log comune l’identificatore del nuovo processo coordinatore

• Il corretto funzionamento dell’algoritmo di elezione è segnalato dal fatto che tutti i processi hanno eletto lo stesso coordinatore

15

Cose da fare

• Per l’implementazione dell’algoritmo di elezione si deve progettare un meccanismo per lo scambio di messaggi tra i processi (si consiglia l’uso di una o più code di messaggi, o in alternativa, di file di tipo pipe).

• Si deve prevedere uno script shell per l'attivazione dei processi che compongono il sistema distribuito che permetta di avere:– un numero di processi parametrico– l’assegnamento di una priorità diversa a

ciascuno dei processi creati

16

Cose da fare

• Si deve prevedere la possibilità che nuovi processi si aggiungano a quelli attivi

• Si deve prevedere la possibilità che se anche un processo termina anzi tempo il meccanismo di elezione continua a funzionare.

17

Costruzione dell’anello di processi:

• Mediante un processo supervisor che stabilisce chi comunica con chi, e gestisce anche l’ingresso di nuovi processi e il caso in cui uno dei processi esistenti scompaia.

• Il supervisor inizializza le code di messaggi e le mette a disposizione dei processi che devono comunicare fra loro.

18

Sviluppo di Applicativi in Unix

• Come si compila un programma C– gcc nomefile.c : compila, link e genera

file eseguibile a.out– gcc -o exefile nomefile.c : come

prima, ma genera file eseguibile exefile

– gcc -c nomefile.c : compila soltanto e genera file oggetto nomefile.o

– gcc -o exefile nomefile.c -lm : compila, link con libreria matematica (-lm) e genera eseguibile exefile

– gcc -o exefile nomefile.o -lm : link con libreria matematica (-lm) e genera eseguibile exefile

19

Il comando make• Permette di ricompilare solo i moduli

che hanno subito delle modifiche.

• Si basa sul concetto di regole di dipendenza tra file

• Le regole specificano delle dipendenze e i comandi da eseguire per aggiornarle

• Le regole che esso utilizza devono essere inserite in un file denominato "Makefile".– make : esegue le regole descritte nel file

Makefile (default)

– make -f nomefile : esegue le regole nel file nomefile

20

Un esempio di Makefile

# Makefile

#commands

COMP = gcc -c

LINK = gcc -o

#directories

DIREXE = ../bin

# pippo dipende da stringa.h , pippo.c e routines.o

${DIREXE}/pippo : stringa.h pippo.c routines.o

rm -f ${DIREXE}/pippo

${LINK} ${DIREXE}/pippo pippo.c routines.o

# routines.o dipende da stringa.h e routines.c

routines.o : stringa.h routines.c

${COMP} routines.c