Sistema
Sistema di
di supporto
supporto
per
per l'allocazione
l'allocazione di
di processi
processi
in
in ambito
ambito distribuito
distribuito
Simone Colombo
Matricola: 0000231933
Verso la parallelizzazione
Attualmente per incrementare le prestazioni e ridurre i tempi di esecuzione
si va sempre più verso una parallelizzazione dell'esecuzione, come
mostrano i recenti sviluppi nell'ambito dei processori, con l'introduzione dei
dual core e dei quad core.
Da qui nasce l'idea di utilizzare la parallelizzazione anche sfruttando più
macchine assieme e di progettare quindi una applicazioni di supporto che
la fornisca in automatico, in modo tale che il programmatore possa
occuparsi solo della realizzazione del suo applicativo, come se dovesse
girare in locale.
Sarà poi sufficiente eseguire l'applicazione di supporto su tutte le macchine
che si desidera partecipino alla rete e successivamente eseguire la propia.
Requisiti
I requisiti che una applicazione del genere deve rispettare sono:


gestire l'ingresso e l'uscita di una macchina dalla rete, anche
dinamicamente durante l'esecuzione
gestire la distribuzione dei processi tra le varie macchine,
bilanciando opportunamente il carico

gestire eventuali oggetti condivisi utilizzati dai vari processi

comunicare il risultato all'applicazione madre

essere tollerante ai guasti, almeno nell'ipotesi di guasto singolo
Architettura generale
Il sistema è stato diviso in due parti:


una che si occupa della gestione della rete
una che si occupa della parte di deployment e argomenti correlati
La prima parte, implementata dalla classe NetManager, ha nello
specifico i seguenti compiti:



Ingresso dei nodi nella rete e loro uscita, mantenendo sempre la
stessa in uno stato integro
gestione della riconnessione di un nodo nel caso in cui questo sia
caduto
gestione della comunicazione tramite messaggi tra i vari nodi (via TCP)
La seconda parte, implementata dalla classe Server, si occupa invece di:

gestione degli oggetti condivisi e delle code di prenotazione

gestione dei processi: allocazione, riallocazione, rimozione
La rete 1/2
L'ingresso di un nodo nella rete (realizzata ad anello) avviene nel seguente
modo:
1 - Invio di messaggio su UDP a tutti i nodi della rete, su porta predefinita
2 - Ogni nodo che riceve il messaggio risponde (sempre su quella porta
UDP) comunicando il suo IP e quello dei suoi vicini
3 - Il nodo entrante sceglie come primo vicino il primo nodo a rispondergli,
come secondo il primo a rispondere fra i due vicini di quest'ultimo; se
non riceve risposte si considera l'unico nodo della rete
4 - Vengono create le connessioni TCP tra il nodo entrante e i due vicini,
e chiuse quella precedente tra i due vicini
La rete 2/2
5 - Il nodo entrante manda un messaggio nella rete nel quale comunica
quali processi avviati da altri su di lui ha in sospeso (in modo da
sapere se riavviarli o meno) e quali lui si aspetta siano in esecuzione
su altri nodi (per procedere eventualmente a una riallocazione)
6 - Gli altri nodi che ricevono questo messaggio aggiornano man mano le
informazioni, in modo che quello entrante possa comportarsi di
conseguenza
Quando un nodo deve uscire dalla rete prima manda un messaggio
indicando quali processi assegnati a lui da altri nodi ha in esecuzione su di
se, e quali lui ha assegnato ad altri nodi; in questo modo i membri della
rete sanno quali processi sospendere.
Provvede poi a informare il nodo precedente e successivo che hanno un
nuovo vicino, richiudendo così l'anello.
La comunicazione nella rete
La comunicazione avviene tramite messaggi fatti circolare nell'anello; ogni
messaggio (implementato dalla classe Message) ha i seguenti campi:

un identificatore del tipo di messaggio (EnterNetwork, ReurceAsking,
ecc)

IP del sender, ovvero del nodo che ha mandato in giro il messaggio

una GUID usata come identificativo univoco

10 campi in cui inserire le informazioni
Ogni nodo ha un buffer in cui tiene i messaggi inviati dall'ultimo ping
effettuato sul vicino a quel momento, in modo da poterli rimandare, in
caso di caduta del nodo successivo, una volta ripristinata la rete.
Tiene inoltre in memoria i messaggi arrivati negli ultimi due intervalli di
rilevamento, in modo da identificare eventuali ricezioni doppie.
La distribuzione del carico
I processi che si vogliono far eseguire dovranno ereditare da una specifica
classe, che implementa i metodi base, oppure implementare l'interfaccia
apposita.
Il protocollo adottato per la distribuzione e l'allocazione è il seguente:
1 - L'applicazione client ottiene un riferimento al server, che prima
aveva registrato il suo servizio.
2 - L'applicazione invoca apposita procedura sul server, passando il
processo, e i coefficienti di uso di CPU e RAM.
3 - Viene mandato un messaggio nell'anello con i coefficienti, ogni nodo
calcola il proprio punteggio e se superiore al migliore attuale, lo
aggiorna, indicando anche il proprio IP.
4 - Quando il messaggio torna al nodo sender, questo provvede a passare
il processo al nodo prescelto (segnandosi a chi lo ha consegnato).
5 - Il nodo prescelto si segna da chi lo ha ricevuto e lo avvia.
La consegna dei risultati
Quando un processo termina, provvede lui stesso, dopo aver richiesto un
riferimento all'oggetto remoto server, a informarlo della sua terminazione.
Quest'ultimo provvederà a informare il nodo che aveva assegnato a lui il
processo, in caso di caduta di quest'ultimo terrà memorizzato il thread
terminato per un certo tempo, per poi cancellarlo.
Sarà l'applicazione che a polling dovrà chiedere al nodo su cui è in
esecuzione se ci sono suoi thread terminati, indicando il relativo
identificativo.
Gli oggetti condivisi
Per permettere interazione tra i thread, è stata data la possibilità
all'applicazione di fornire oggetti condivisi fra i vari processi, che potranno
utilizzarli in mutua esclusione.
Una volta che il client ha fornito tali oggetti, la procedura per utilizzarli è la
seguente:
1 - Il processo fa richiesta di utilizzo al nodo su cui sta eseguendo.
2 - La richiesta viene propagata al nodo che aveva richiesto l'esecuzione.
3 - Se l'oggetto è libero, viene consegnato al nodo richiedente, altrimenti
la richiesta viene messa in coda.
4 - L'oggetto viene usato.
5 - Il thread chiede al nodo di restituire l'oggetto, la consegna viene
propagata al nodo “main”.
6 - Se vi sono richieste in coda, l'oggetto viene consegnato, altrimenti
viene segnato come disponibile.
Rilevazione dei guasti
Il sistema per offrire una minima resistenza ai guasti, dovrà essere in grado
di identificare e rispondere in modo opportuno alla caduta di un nodo della
rete.
Per identificare tali cadute, ogni 20 secondi un nodo controlla che i due
vicini siano ancora presenti, se non lo sono allora capisce di essere caduto
lui, altrimenti, se è caduto il suo successore, avvia la procedura di ripristino.
In caso di caduta, il nodo provvede a sospendere tutti i processi assegnati
da altri a lui e a segnare l'istante di interruzione, sia per questi, sia per
quelli assegnati da lui ad altri.
Prova poi a riconnettersi 3 volte in modo automatico alla rete, a distanza di
tempo, fallite le quali si potrà nuovamente accedere alla rete manualmente.
Reazione ai guasti
Se ci si accorge che il successore è caduto, si manda un messaggio nell'anello
in senso contrario, indicando l'indirizzo del nodo caduto e il propio.
Gli altri nodi propagheranno il messaggio, sospendendo i processi relativi al
nodo caduto (e settandone il FallIstant), fino a che questo non giungerà al
nodo successivo a quello guasto.
Questo provvederà a richiudere l'anello e a mandare un messaggio per
informare del termine della procedura di recovery.
Comunicazione con nodi caduti
Può capitare che un nodo cerchi di comunicare con uno caduto, il cui
guasto non è ancora stato rilevato.
Se la comunicazione avviene tramite messaggio tutto sembrerà andare
correttamente, anche se ovviamente il messaggio non sarà ricevuto.
Per ovviare a questo è stata implementata una politica Exactly Once,
come discusso in precedenza.
Se invece si comunica tramite invocazione di procedura remota, ci si
accorgerà subito del problema; in tale caso si memorizzerà l'azione che
si voleva effettuare per poi farla una volta che il nodo torna in rete.
Se l'azione era l'assegnazione di un processo a quel nodo, viene
ripetuto il protocollo di scelta.
Gestione dei processi
Come già discusso in precedenza, se il nodo che ha allocato un processo
o quello su cui è stato allocato cadono, entrambi segneranno quel
momento come FallIstant relativo a quel nodo.
E' presente un demone attivo che periodicamente controlla quanto
tempo è passato dal FallIstant, se è superiore al timeout rimuove il
thread e, nel caso sa il demone in esecuzione sul nodo che ha allocato il
processo, avvia la procedura di riallocazione.
Quando un thread viene rimosso anche gli oggetti condivisi usati da lui
vengono liberati, vengono cancellate sue eventuali richieste in coda, e se
vi sono comunicazioni pendenti tra i due nodi inerenti quel processo,
vengono rimosse anche loro.
Test 1/2
I test sono stati effettuati su un numero di pc variabile da 1 a 4, con
caratteristiche generalmente non troppo differenti.
I tempi riportati sono quelli medi, ottenuto con l'istanza “fl417”, effettuando
8 esecuzioni contemporanee.
Si noti come il comportamento, sia per quando riguarda lo speed up, sia per
l'efficienza sia quello che è lecito aspettarsi.
Test 2/2
Il grafico mostra come il rapporto tra numero di processori e tempo sia
approssimabile con una iperbole e quindi con una proporzionalità inversa.
Il grafico è differente da quello ideale a causa della non perfetta allocazione
del carico, dei tempi di comunicazione (anche se trascurabili) e della
presenza di parti che non possono essere parallelizzate (accesso a risorse
comuni).
Conclusioni e sviluppi futuri
L'applicativo, come evidenziato dai test, risponde a tutti i requisiti
richiesti, permette di collegare un numero arbitrario di macchine in rete
e non risulta essere particolarmente pesante.
I tempi vengono ridotti significativamente, anche se vanno dati in modo
corretto i due coefficienti che vengono usati per decidere l'allocazione, e
questo spesso non è facile.
Nel caso si volesse procedere nello sviluppo, i punti principali su cui
potrebbe vertere il miglioramento sono:



Revisione della funzione che calcola il punteggio di ciascun nodo,
considerando anche altri parametri oltre a CPU e RAM.
Cambiamento del protocollo di join dei nodi, per permettere l'ingresso
di più macchine assieme
Estensione del funzionamento oltre la rete locale.