OTTIMIZZAZIONE CRITERI DI SCHEDULING PER …...2009/04/22 · OTTIMIZZAZIONE CRITERI DI SCHEDULING...
81
UNIVERSITÀ DEGLI STUDI DI PARMA FACOLTÀ DI SCIENZE MATEMATICHE FISICHE E NATURALI CORSO DI LAUREA INFORMATICA OTTIMIZZAZIONE CRITERI DI SCHEDULING PER JOB MULTIPROCESSO IN AMBIENTE GRID RELATORE: Chiar.mo Prof. ROBERTO ALFIERI CANDIDATO: LEONARDO MUTTI Anno Accademico 2007-2008
Transcript of OTTIMIZZAZIONE CRITERI DI SCHEDULING PER …...2009/04/22 · OTTIMIZZAZIONE CRITERI DI SCHEDULING...
UNIVERSITÀ DEGLI STUDI DI PARMA
FACOLTÀ DI SCIENZE MATEMATICHE FISICHE E NATURALICORSO DI LAUREA INFORMATICA
OTTIMIZZAZIONE CRITERI DI SCHEDULINGPER JOB MULTIPROCESSO IN AMBIENTE GRID
RELATORE:Chiar.mo Prof. ROBERTO ALFIERI
CANDIDATO:LEONARDO MUTTI
Anno Accademico 2007-2008
A coloro che nel mio percorso
hanno sempre creduto.
Grazie.
Indice
1 Premessa........................................................................................................................8
2 Teoria delle code..........................................................................................................10
2.1 Schema di un processo a coda.............................................................................10
2.1.1 Processo degli arrivi.....................................................................................11
2.1.2 Capacità della coda.......................................................................................11
2.1.3 Processo di servizi........................................................................................11
2.1.4 Canali di servitori.........................................................................................12
2.1.5 Descrivere una coda – Notazione Kendall...................................................12
2.1.6 Indici di efficienza........................................................................................13
2.1.7 Valutazione indici di efficienza – Legge di Little........................................15
2.2 Fair Queuing........................................................................................................16
2.2.1 Proprietà.......................................................................................................17
2.2.2 Weighted fair queuing..................................................................................18
2.3 Preemption...........................................................................................................19
2.4 Starvation.............................................................................................................20
2.5 Checkpointing......................................................................................................21
3 Scenari.........................................................................................................................22
3.1 Reti.......................................................................................................................22
3.2 Sistemi Operativi.................................................................................................24
3.2.1 Scheduler della CPU....................................................................................25
3.2.2 Scheduling con diritto di prelazione............................................................25
3.2.3 Criteri di scheduling.....................................................................................27
3.2.4 Algoritmi di scheduling................................................................................28
3.3 Job Manager.........................................................................................................28
3.3.1 Algoritmi di assegnazione dei nodi..............................................................30
4 Grid..............................................................................................................................32
4.1 Evoluzione del Grid Computing..........................................................................33
4.2 Il Cluster Grid di Parma.......................................................................................35
5 Job Sheduler................................................................................................................37
5
5.1 Controllo del traffico............................................................................................38
5.2 Obbiettivo primario..............................................................................................38
5.3 Ottimizzazione.....................................................................................................38
5.4 MAUI...................................................................................................................38
5.4.1 Filosofia e obbiettivi dello scheduler Maui..................................................39
5.4.2 Scheduling Object........................................................................................39
5.4.3 Risorse..........................................................................................................40
5.4.4 Class (or Queue)...........................................................................................41
5.4.5 Partitions......................................................................................................41
5.4.6 Account........................................................................................................42
5.4.7 Priorità..........................................................................................................42
5.4.8 Preemption...................................................................................................42
5.4.9 Fairness........................................................................................................47
5.4.10 Fairshare.....................................................................................................47
5.4.10.1 Obbiettivi del fairshare......................................................................51
5.4.11 Reservation.................................................................................................52
5.4.12 Backfill.......................................................................................................56
5.4.13 Checkpointing............................................................................................58
5.5 MOAB..................................................................................................................59
5.6 LSF.......................................................................................................................59
5.7 Job Multiprocesso................................................................................................60
6 Sviluppo del progetto...................................................................................................61
6.1 TORQUE.............................................................................................................61
6.1.1 Installazione di TORQUE............................................................................61
6.1.2 Creazione dei pacchetti RPM.......................................................................63
6.1.3 Il file “server_name”....................................................................................63
6.1.4 Il file "nodes"...............................................................................................64
6.1.5 Installare Torque in un nodo.........................................................................64
6.1.6 Il file "config"...............................................................................................64
6.1.7 Creazione delle code....................................................................................65
6.1.8 Il comando qsub...........................................................................................66
6
6.2 MAUI...................................................................................................................67
6.2.1 Installazione di Maui....................................................................................67
6.2.2 Configurazione iniziale................................................................................68
6.2.3 Maui testing..................................................................................................69
6.2.4 File layout.....................................................................................................69
6.3 MOAB..................................................................................................................71
6.3.1 Installazione di Moab...................................................................................71
6.3.2 Variabili d'ambiente......................................................................................71
6.3.3 Avviamo Moab Workload Manager.............................................................72
6.3.4 Installazione Moab Cluster Manager...........................................................72
6.4 Gestione del job CERT........................................................................................73
6.5 Esecuzione di un job multiprocesso.....................................................................74
7 Conclusioni..................................................................................................................75
8 Bibliografia..................................................................................................................77
9 Sitografia.....................................................................................................................78
10 Appendice A : maui.cfg.............................................................................................80
7
1 Premessa
La necessità di utilizzare strumenti informatici che consentano operazioni molto
complesse in tempi molto ristretti, ha portato l'idea di raccogliere risorse di calcolo per
ottenere strumenti sempre più performanti, al fine di soddisfare le richieste di molti.
Da questa idea nasce Grid: una struttura complessa di strumenti informatici distribuiti
su rete geografica che permetta, a chi né ha la possibilità, di svolgere operazioni
all'interno di siti di calcolo.
Da questa vasta disponibilità di risorse e da un numero sempre più ampio di possibili
fruitori nasce il problema affrontato in questo elaborato di tesi: come è possibile
ottimizzare la gestione di tali risorse in modo da soddisfare tutte le richieste, e renderla
“giusta”, così da ripartirle in modo equo e bilanciato ?
Da queste due domande e stato estrapolato un contesto di studio dal quale non
potevamo esulare, la gestione delle code e dei criteri di scheduling.
Partendo da un analisi teorica di come le code possano essere rappresentate per essere
gestite e studiate e stato analizzato come esse vengano risolte in due contesti informatici
fondamentali: i sistemi operativi e le reti di calcolatori.
Una volta compresi i concetti chiave di tali gestioni si è studiato più nel dettaglio i
diretti gestori di code nei siti di calcolo in ambiente Grid, ovvero i job scheduler.
Analizzando le loro principali caratteristiche e metodi di funzionamento ci siamo
imbattuti nelle problematiche della gestione di code di job come: la gestione degli
utenti, l'assegnazione delle risorse a tali utenti, la preemption, il problema della
starvation, l'introduzione della tecnica del fairshare e altre ancora.
Lavorando sul sito di calcolo dell'Università di Parma si è proceduto a configurare il job
scheduler, in modo da risolvere tali problematiche e ad introdurre con successo alcune
tecniche avanzate di gestione code come la backfill e il fairshare.
In tale contesto si è manifestata la ormai sempre più attuale necessità di gestione di job
multiprocesso, che richiedono una configurazione più complessa e accorta del sito di
8
calcolo dovuta alla loro particolare necessità di risorse in modo simultaneo.
9
2 Teoria delle code
La teoria delle code è lo studio matematico delle linee di attesa (o code) e di vari
processi correlati, quali il processo di arrivo in coda, l'attesa (essenzialmente un
processo di immagazzinamento) e il processo di servizio. Può essere applicata ad
un'ampia varietà di problemi reali, soprattutto nel campo dei trasporti, delle
telecomunicazioni, della fornitura di servizi pubblici (ad es. in sanità) e delle operazioni
aziendali.
Usualmente, la teoria delle code è considerata una branca della ricerca operativa. Le sue
origini vengono fatte risalire al 1909 quando l'ingegnere danese Agner Krarup Erlang
pubblicò un articolo intitolato “The theory of probability and telephone conversations”
relativo alle attese nelle chiamate telefoniche.
2.1 Schema di un processo a coda
Schematicamente un processo in coda possiamo rappresentarlo nel seguente modo:
Gli elementi fondamentali che caratterizzano un sistema di servizio sono:
• Processo degli arrivi
• Caratteristiche proprie della coda
• Capacità della coda
• Processo di servizio
• Canali di servitori
10
Sorgente di arrivi Coda Stazione di servizio
Clienti servitiClienti
2.1.1 Processo degli arrivi
La dimensione della sorgente degli arrivi per ipotesi è infinita. Il processo degli arrivi
viene definito in base ai tempi di interarrivo, cioè il tempo che intercorre tra due entrate
di due clienti successivi. In genere si ipotizza che il processo degli arrivi sia stazionario
cioè non dipende dal tempo e che le variabili aleatorie siano indipendenti ed
identicamente distribuite.
Le caratteristiche della coda, sono di due tipi:
• Disciplina del servizio: cioè l'ordine con cui il cliente viene scelto dalla coda per
poter usufruire del servizio:
◦ FCFS (FIFO) First In First Out
◦ LCFS (LIFO) Last In Firs Out
◦ SIRO (Servizio in ordine casuale)
◦ Basata sulla classe di priorità
• Comportamento del cliente: che può essere diverso, ad esempio:
◦ Rinuncia, il cliente aspetta poi si scoraggia
◦ Indecisione, cioè cambia coda
◦ Corruzione, paga un prezzo per avanzare di posto nella coda
◦ Inganno, avanza senza pagare il prezzo
2.1.2 Capacità della coda
Può essere o finita o infinita e questo va a influenzare la capacità del sistema, infatti se
la coda è finita e viene saturata il cliente non può accedere al servizio e deve cambiare
coda.
2.1.3 Processo di servizi
Descrive il modi in cui viene erogato il servizio, viene definito per mezzo dei tempi di
11
servizio nel caso in cui essi siano dipendenti, indipendenti ed identicamente distribuiti.
Il più comune è quello con i tempi di servizio esponenziale di Poisson. Può capitare che
il tempo di servizio dipenda dalla dimensione della coda, oppure avere dei servitori a
sequenza cioè una catena di servitori per poter ottenere il servizio completo.
2.1.4 Canali di servitori
Possiamo avere:
• Più canali ed un unico servitore, cioè una fila davanti a un posto di servizio.
• Un unico canale e più servitori, dove i clienti sono in un unica coda e appena un
servitore si libera si accede al servizio.
2.1.5 Descrivere una coda – Notazione Kendall
Nel 1953, David George Kendall introdusse la notazione A/B/C, successivamente estesa
come A/B/s/c/z/p nella quale i numeri sono sostituiti con quanto segue.
• A è la distribuzione dei tempi di interarrivo (processo degli arrivi)
• B è la distribuzione dei tempi di servizio
• s è il numero dei servitori (capacità di servizio)
• c è la capacità del sistema o capacità della sorgente di arrivi (il sistema può
accettare al massimo c clienti, per default è infinita)
• z è la disciplina del servizio (per default è FCFS)
• p è la capacità dell'intero sistema o dimensione della sorgente degli arrivi (per
default è infinita)
A è B possono assumere i seguenti valori:
• M per "di Markov", implicante una distribuzione esponenziale negativa unilatera
per i tempi di servizio o tra gli arrivi: ciò implica l'assenza di memoria di questi
ultimi;
• D per distribuzione "degenere" o "deterministica" dei tempi di servizio, tutti i
12
clienti hanno lo stesso valore;
• Ek per una distribuzione di Erlang con k come parametro di forma;
• G per una distribuzione "Generale".
z invece può assumere i valori:
• First Come First Served (FCFS) (o First In First Out - FIFO) (il primo che arriva
viene servito per primo);
• Last Come First Served (LCFS) (o Last In First Out - LIFO) (l'ultimo che arriva
viene servito per primo);
• Service In Random Order (SIRO) (servizio in ordine casuale).
Esempi di code definiti con tali convenzioni sono:
M/M/1: Questa è una coda molto semplice. Qui il tempo di arrivo e il tempo di servizio
rispettano una distribuzione esponenziale negativa (Poisson). Il sistema prevede solo un
server. Questo tipo di coda può essere applicato a una grande varietà di problemi come
un qualsiasi sistema costituito da un numero ampio e indipendente di clienti
approssimabili con un processo di Poisson.
Purtroppo l'uso del processo di Poisson per stimare il tempo di servizio spesso non è
applicabile in modo fedele ma rimarrà solo una cruda approssimazione.
M/D/n: Qui il processo di arrivo è un processo di Poisson mentre il processo di servizio
rispetta una distribuzione deterministica. Il sistema ha n server. Qui il tempo di sevizio
di può essere stimato uguale per tutti i clienti. Per esempio una biglietteria con n
cassieri.
G/G/n: Questa è il sistema più generale dove l'arrivo del cliente e il tempo di servizio
sono entrambi casuali. Il sistema ha n server. Nessuna soluzione analitica è tuttora
conosciuta per questo tipo di code.
2.1.6 Indici di efficienza
Per analizzare le prestazioni del sistema è possibile utilizzare degli indici di efficienza:
13
• L numero medio di clienti nel sistema
• Lq numero medio di clienti in coda
• W tempo medio per cliente nel sistema
• Wq tempo medio per cliente in coda
quando è passato poco tempo dalla fornitura del servizio si dice che siamo in uno stato
transitorio che è uno stato difficile da gestire e valutare. Se passa un tempo sufficiente il
sistema passa a condizioni di regime ovvero il sistema diventa stazionario, questa è la
condizione più semplice da considerare. Questi indici valgono solo per condizioni a
regime.
Un altro indice che consideriamo è:
• ρ fattore di utilizzazione del posto di servizio
Altre notazioni in input al nostro sistema sono:
• λ frequenza media dei tempi di interarrivo (ovvero il numero medio di arrivi
nell'unità di tempo)
• µ velocità media del servizio o tasso di servizio (ovvero il numero medio di
clienti per i quali è espletato il servizio nell'unita di tempo)
Partendo da λ e µ possiamo ottenere il tempo medio di interarrivo e il tempo medio di
servizio:
• 1/ λ tempo medio di interarrivo
• 1/ µ tempo medio di servizio
C'è una relazione che lega tutte e tre queste variabili ed è:
ρ = λ/ µ
Esempio
Consideriamo i seguenti intervalli di interarrivo:
3' 7' 10' 4' 6' in 30 minuti
14
e di voler calcolare il numero medio di arrivi nell'unità di tempo e il tempo medio di
interarrivo.
Il numero medio di arrivi nell'unità di tempo sarà dato da:
5/30 = 1/6 = λ
per cui il tempo medio di interarrivo sarà:
1/ λ = 6'
2.1.7 Valutazione indici di efficienza – Legge di Little
Schematicamente abbiamo una situazione del genere:
Il progettista avrà delle variabili per minimizzare il costo del servizio. Se L e W sono
grandi il modello non funziona bene, e per farlo funzionare bene posso variare il
numero di servitori, la disciplina, le regole del sistema, ecc...
Esiste una legge che ci viene in aiuto:
Legge di Little L=λW
Lq=λWq
15
ModelloL
WRange di servizio
Range di arrivo
Variabili
Se µ è costante → W = Wq + 1/µ
Applichiamo ora queste nozioni ad un caso base:
caso D/D/1, è il più facile da analizzare ma anche il più difficile che esista nella realtà:
Informazione a(i) = istante di arrivo del cliente i
s(i) = durata del servizio del cliente i
Variabili X(i) = istante di uscita del cliente i dal sistema
W(i) = tempo di attesa del cliente i
Se supponiamo che X(0) = 0 allora:
X(i) = s(i) + max {a(i), X(i-1)}
W(i) = X(i) – a(i) - s(i)
Il numero medio di clienti nel sistema è dato dalla somma dei clienti che soddisfano la
relazione:
a(i) ≤ t ≤ X(i)
Ora andremo ad analizzare alcuni delle nozioni più importanti, utili per una corretta
gestione delle code.
2.2 Fair Queuing
Il Fair Queuing è una algoritmo di scheduling usato in informatica sia nei computer per
la gestione di processi che nelle telecomunicazioni per permettere a flussi di pacchetti di
condividere equamente la capacità di trasmissione o ricezione del collegamento.
La nascita del Fair Queuing avviene nel 1985 grazie a John Nagle durante i suoi studi
nel campo delle telecomunicazioni.
16
Il vantaggio rispetto agli algoritmi di gestione delle code convenzionali è la migliore
gestione di flussi ad alto carico di lavoro, con la possibilità di sfruttare a pieno le
potenzialità del sistema. Fair Queuing può essere vista come una approssimazione del
processo di sharing della CPU in un calcolatore.
2.2.1 Proprietà
Il fair queuing è usato principalmente nei router, switch e multiplexer che inoltrano i
pacchetti da un buffer, con l'evolversi della tecnologia il fair queuing è stato utilizzato
anche per risolvere altri tipi di problemi, come nel nostro caso, la gestione di job
multiprocesso in un ambiente Grid.
Il fair queuing lavora con un buffer che può essere visto come un insieme di code dove i
pacchetti o i job vengono temporaneamente depositati prima di essere trasmessi o
eseguiti. Il buffer è suddiviso appunto in code dove vengono memorizzati i pacchetti o i
job in base alle loro caratteristiche. Ad esempio per quanto riguarda i pacchetti di rete
vengono suddivisi in base all'IP di destinazione oppure per quanto riguarda i job sono
assegnati ad una coda specifica in base a chi sottomette il job, quale è la sua priorità
oppure in base alle risorse richieste per la sua computazione.
La proprietà principale del fair queuing è quella di fissare degli obbiettivi di
massimizzazione o minimizzazione di alcuni valori, e in base a questi obbiettivi
l'algoritmo modula la gestione delle code.
Ecco il motivo del suo nome fair queuing, “code giuste”, infatti tramite l'assegnazione
di obbiettivi efficienti e corretti l'algoritmo si sviluppa nel tempo e si modula per gestire
al meglio il flusso di lavoro.
Ad esempio possiamo impostare come obbiettivo la minimizzazione del tempo di attesa
medio per ogni utente che sottomette un job, oppure nell'ambito delle reti il tempo di
attesa di ogni pacchetto in base all'IP di destinazione. L'algoritmo lavorerà per ottenere
questa minimizzazione così da soddisfare tutti i “clienti” delle code da esso gestite in
modo equo. Per ottenere tale obbiettivo l'algoritmo di scheduler farà in modo di
memorizzare tutti i dati relativi a quanto ogni utente che sottometto job oppure che deve
17
ricevere dei pacchetti di rete è stato già soddisfatto e in base a questi dati deciderà quale
utente ha ora la priorità di gestione.
2.2.2 Weighted fair queuing
WFQ è un algoritmo della famiglia degli algoritmi fair, è stato sviluppato nel 1989,
quattro anni dopo l'introduzione di Nagle del Fair Queuing, da Lixia Zhang. Questo
algoritmo è stato introdotto sempre nell'ambito della gestione delle reti in modo da
garantire un accesso equo alle risorse di rete, così da evitare che una flusso potesse
occupare tutte le risorse del canale di comunicazione.
Infatti a differenza del Fair Queuing classico dove i pacchetti vengono distribuiti su
varie code e le code vengono processate tutte simultaneamente suddividendo il canale
per le code presenti, il Weighted Fair Queuing classifica al momento dell'arrivo il
pacchetto, assegnando ad esso un peso (weight) in base ai dati contenuti nell'header del
pacchetto stesso e in base a questo peso andrà a posizionare il pacchetto in una coda
opportuna così da poter classificare le code presenti in base al peso dei pacchetti e in
base a tale peso lo scheduler andrà a ripartire la capacità di banda.
18
2.3 Preemption
La preemption (o prelazione) è, in informatica, l'operazione in cui un processo viene
temporaneamente interrotto e portato al di fuori della CPU, senza alcuna richiesta di
cooperazione e con l'intenzione di ripristinarlo in un secondo momento, per dare spazio
ad un altro processo a priorità più alta. Tale scambio è noto come context switch (o
cambiamento di contesto). La preemption può avvenire tramite uno scheduler, che ha il
compito di interrompere e/o ripristinare i processi presenti nel sistema operativo a
seconda del loro stato; in tal caso si parla di preemptive scheduling (o scheduling con
diritto di prelazione).
Tramite il metodo di preemption vengono gestiti i sistemi operativi più performanti e
vengono gestiti i Batch System che necessitano di riservare maggiore attenzione e
priorità di esecuzione a certi job rispetto altri già in esecuzione.
19
Illustrazione 1: Weighted Fair Queuing
La preemption è un metodo che interviene su due processi distinti, un primo processo
subisce la preemption e viene sospeso durante l'esecuzione per rilasciare risorse ad un
altro processo detto “processo preemptor”. Con risorse non intendiamo solo la CPU
come citato precedentemente ma vengono intese tutte le risorse necessarie al processo
“preemptor” presenti nel sito di calcolo.
2.4 Starvation
In informatica, per starvation (termine inglese che tradotto letteralmente significa
inedia) si intende l'impossibilità, da parte di un processo pronto all'esecuzione, di
ottenere le risorse di cui necessita.
Un esempio tipico è il non riuscire ad ottenere il controllo della CPU da parte di
processi con priorità molto bassa, qualora vengano usati algoritmi di scheduling a
priorità. Può capitare, infatti, che venga continuamente sottomesso al sistema un
processo con priorità più alta. Un aneddoto riguardo questo problema è la storia del
processo con bassa priorità, scoperto quando fu necessario fermare il sistema sull'IBM
7094 al MIT nel 1973: era stato sottomesso nel 1967 e fino ad allora non era ancora
stato eseguito.
Per evitare questi problemi si possono utilizzare, oltre ad algoritmi di scheduling
diversi, come Round Robin, le cosiddette tecniche di invecchiamento (aging). Ovvero si
provvede ad aumentare progressivamente, ad intervalli regolari, la priorità dei processi
qualora questi non siano riusciti ad ottenere le risorse richieste. Questo fa sì che anche
un processo con la priorità più bassa possa potenzialmente assumere quella più alta,
riuscendo così ad ottenere, in un tempo massimo predefinito, quanto di cui necessita.
Altri usi del termine starvation sono in relazione alle risorse di accesso alla memoria o
CPU: si dice che un programma è bandwidth-starved quando la sua esecuzione è
rallentata da un'insufficiente velocità di accesso alla memoria, o CPU-starved quando il
processore è troppo lento per eseguire efficacemente il codice.
20
2.5 Checkpointing
Il checkpointing è una tecnica utilizzata per fornire fault tolerance nei sistemi
informatici. Fondamentalmente si basa sulla memorizzazione dello stato corrente di una
applicazione così da poter utilizzare tali informazioni salvate per ripristinare
l'applicazione in caso di blocco o chiusura inaspettata dell'applicazione stessa.
Abbiamo 3 diverse tipologie di checkpointing: la prima cosiddetta kernel-checkpoint
dove è il kernel linux stesso che si occupa di fornire il servizio di checkpointing , la
seconda, user-checkpointing dove sono software definita dall'utente ad occuparsi di
effettuare checkpointing della applicazione in esecuzione e la terza, application-
checkpointing dove è l'applicazione stessa che è stata progettata e programmata per
effettuare checkpointing.
Come vedremo il checkpointing è ampiamente utilizzato anche nei Batch System per
una corretta gestione dei processi.
21
3 Scenari
In questo capitolo vogliamo porre l'attenzione su come la gestione delle code sia
fondamentale nelle componenti più importanti di un sistema informatico.
Sia la progettazione di reti di calcolatori che la progettazione dei sistemi operativi base
dei nostri calcolatori ha dovuto scontrarsi con la gestione di code. Senza una gestione
corretta di tali code non si sarebbe mai arrivati ad avere reti cosi preformanti e sistemi
operativi così complessi come siamo abituati ad usare.
3.1 Reti
Il primo scenario dove incontriamo la necessita di gestire le code è nella gestione dei
protocolli di comunicazione di reti di calcolatori. Infatti proprio sugli algoritmi utili alle
comunicazioni telefoniche è nata la teoria delle code che si è andata via via
approfondendosi con l'avvento delle reti di calcolatori.
Con la trasmissione di dati in formato di pacchetto la prima necessità è stata quella di
suddividere in modo equo un unico canale di comunicazione evitando il più possibile la
perdita di dati e la congestione del canale.
Con congestione del canale si intende quando il traffico offerto dalla rete è vicino o
superiore alla capacità della rete stessa.
Proprio nella gestione della congestioni si individuano gli algoritmi più complessi e il
primo approccio per una gestione “Fair” della problematica.
La congestione può essere causata da più fattori. Se improvvisamente diversi flussi di
pacchetti cominciano ad arrivare attraverso tre o quattro linee di input e tutti i pacchetti
necessitano della stessa linea di output, inizia a formarsi una coda. Se la memoria non è
sufficiente, non sarà possibile conservare tutti i dati, perciò alcuni pacchetti andranno
persi. Aggiungere memoria può aiutare fino ad un certo punto, ma Nagle (1987) ha
scoperto che se i router hanno memoria infinita la congestione peggiora anziché
migliorare, poiché quando raggiungeranno il fronte della coda, i pacchetti saranno già
22
scaduti (ripetutamente) e quindi saranno già stati trasmessi dei duplicati.
Si conoscono molti algoritmi di controllo della congestione, e per organizzarli in modo
sensato, Yang and Reddy (1995) hanno sviluppato una tassonomia. I due studiosi hanno
diviso prima di tutto gli algoritmi in soluzioni a ciclo aperto e soluzioni a ciclo chiuso;
poi hanno diviso gli algoritmi a ciclo aperto in soluzioni che agiscono sulla sorgente e
soluzioni che lavorano sulla destinazione. Anche gli algoritmi a ciclo chiuso sono stati
divisi in due categorie: soluzioni a retroazione esplicita e soluzione a retroazione
implicita.
Con algoritmi a ciclo aperto si intende quegli algoritmi che cercano di prevenire il
verificarsi della congestione ricorrendo ad una buona progettazione della rete. Mentre
gli algoritmi a ciclo chiuso si basano sul concetto di controreazione; la rete viene
costantemente monitorata, al verificarsi di una congestione i router si scambiano
informazioni al fine di migliorare la situazione.
Le tecniche più utilizzate per il controllo della congestione sono:
• Bit di allarme
Tramite un bit all'interno del pacchetto viene segnalato uno stato di congestione così da
poter diminuire il flusso di dati sino al ristabilirsi della condizione normale.
• Chole packet
In questo caso la comunicazione di congestione viene data tramite l'invio di un
pacchetto “chole packet” che comunica alla sorgente lo stato di congestione ed eventuali
altri canali da sfruttare per effettuare l'invio di pacchetti.
• Chole packet hop-by-hop
• Load shedding
Con load shedding indichiamo l'azione di eliminazione intrapresa dai router inondati da
troppi pacchetti.
• RED (Random Early Detection)
Si tratta di un algoritmo che permette ai router di scartare i pacchetti prima che tutto lo
23
spazio del buffer sia completamente esaurito, in pratica, facendo in modo che i router
scartino i pacchetti prima che la situazione diventi senza speranza è possibile bloccare il
problema sul nascere
• Jitter
Con jitter viene indicata la variazione nel tempo di arrivo del pacchetto, tramite il
controllo di questo valore è possibile effettuare controllo della congestione è diminuire
il flusso appena si osserva che i tempi di consegna stanno aumentando.
3.2 Sistemi Operativi
Il secondo scenario informatico in cui possiamo trovare la problematica della gestione
delle code è quello dei sistemi operativi. Infatti il sistema operativo ha come compito
principale quello di gestire in modo ottimale i processi in esecuzione sul calcolatore.
Tali processi vengono spesso eseguiti in modo concorrenziale richiedendo risorse come
CPU, memoria e dispositivi di input e output per essere portati a termine, proprio il
sistema operativo si occupa di tale gestione così da evitare lunghe attese dell'utente per
24
Illustrazione 2: Random Early Detection
l'esecuzione del proprio processo e situazioni di stallo del sistema operativo e quindi del
calcolatore stesso.
In questo contesto andremo ad dare una breve analisi di come il sistema operativo
gestisce l'allocazione della risorsa più importante la CPU, chi in particolare si occupa di
tale gestione, che algoritmi usa e quali problematiche possono sorgere se tale risorsa
non fosse gestita correttamente.
3.2.1 Scheduler della CPU
Lo scheduling della CPU è alla base dei sistemi operativi multi programmati: attraverso
la commutazione del controllo della CPU tra i vari processi, il sistema operativo può
rendere più produttivo il calcolatore.
L’obbiettivo della multi programmazione è avere sempre processi in esecuzione al fine
di massimizzare l’utilizzo della CPU. In un sistema con una sola unità di elaborazione si
può eseguire al più un processo alla volta; gli altri processi, se presenti, devono
attendere che la CPU si liberi e possa essere nuovamente sottoposta a scheduling.
Ogni qualvolta la CPU passa nello stato d’inattività il sistema operativo sceglie per
l’esecuzione uno dei processi presenti nella coda dei processi pronti. In particolare è lo
scheduler a breve termine, o scheduler della CPU che, tra i processi nella memoria
pronti per l’esecuzione, sceglie quale assegnare alla CPU.
La coda dei processi pronti non è necessariamente una coda in ordine di arrivo (FIFO).
Come si nota analizzando i diversi algoritmi di scheduling, una coda dei processi pronti
si può realizzare come una coda FIFO, una coda con priorità, un albero o semplicemente
una lista concatenata non ordinata.
3.2.2 Scheduling con diritto di prelazione
Le decisioni riguardanti lo scheduling della CPU si possono prendere nelle seguenti
circostanze:
1. Un processo passa dallo stato di esecuzione allo stato di attesa
2. Un processo passa dallo stato di esecuzione allo stato pronto
25
3. Un processo passa dallo stato di attesa allo stato pronto
4. Un processo termina
Il primo e l’ultimo caso non prevedono alcuna scelta di scheduling; a essi segue la scelta
di un nuovo processo da eseguire, sempre che ce ne sia uno nella coda dei processi
pronti per l’esecuzione; in questo caso si dice che lo schema di scheduling è senza
diritto di prelazione (non preemptive). Una scelta si deve invece fare nei due casi
centrali; in tal caso parliamo di scheduling con diritto di prelazione (preemptive).
Nel caso dello scheduling senza diritto di prelazione, quando si assegna la CPU ad un
processo, questo rimane in possesso della CPU fino al momento del suo rilascio, dovuto
la termine dell’esecuzione o al passaggio nello stato di attesa. Questo metodo di
scheduling è impiegato nell’ambiente Microsoft Windows ed è l’unico che si può
utilizzare in certe architetture che non prevedono la presenza di un temporizzatore,
necessario per lo scheduling con diritto di prelazione.
La capacità di prelazione si ripercuote anche sulla progettazione del nucleo del sistema
operativo. Durante l'elaborazione di una chiamata del sistema, il nucleo può essere
impegnato in attività a favore di un processo; tali attività possono comportare la
necessità di modifiche a importanti dati del nucleo, come le code I/O. Se si ha la
prelazione del processo durante tali modifiche e il nucleo deve leggere e o modificare
gli stessi dati, si può avere il caos.
Alcuni sistemi operativi, tra cui la maggior parte delle versioni dello UNIX, affrontano
questo problema attendendo il completamento della chiamata del sistema o che si abbia
il blocco dell'I/O prima di eseguire un cambio di contesto (context switching).
Purtroppo questo modello d'esecuzione del nucleo non è adeguato alle computazioni in
tempo reale e alle multielaborazioni.
Per quel che riguarda lo UNIX, sono ancora presenti sezioni di codice a rischio. Poiché
le interruzioni si possono, per definizione, verificare in ogni istante e il nucleo non può
sempre ignorarle, le sezioni di codice eseguite per effetto delle interruzioni devono
essere protette da un uso simultaneo. Il sistema operativo deve ignorare raramente le
interruzioni, altrimenti si potrebbero perdere dati in ingresso, o si potrebbero
26
sovrascrivere dati in uscita.
Per gestire in modo efficiente sistemi con sempre più numerose unità di elaborazione, si
devono ridurre al minimo le modifiche allo stato del sistema delle interruzioni, e si deve
aumentare al massimo la selettività dei meccanismi di bloccaggio.
3.2.3 Criteri di scheduling
Diversi algoritmi di scheduling della CPU hanno proprietà differenti e possono favorire
una particolare classe di processi. Prima di scegliere l'algoritmo da usare in una
specifica situazione occorre considerare le caratteristiche dei diversi algoritmi.
Per il confronto tra gli algoritmi di scheduling della CPU son stati suggeriti molti criteri.
Le caratteristiche usate per il confronto possono incidere in modo rilevante sulla scelta
dell'algoritmo migliore. Di seguito riportiamo alcuni criteri:
• Utilizzo della CPU. La CPU deve essere più attiva possibile. Teoricamente,
l'utilizzo della CPU può variare dallo 0 al 100 per cento. In un sistema reale può
variare dal 40 per cento, per un sistema con poco carico, al 90 per cento per un
sistema con utilizzo intenso.
• Produttività. La CPU è attiva quando si svolge un lavoro. Una misura del lavoro
svolto è data dal numero dei processi completati nell'unità di tempo: tale misura
è detta produttività (throughput). Per processi di lunga durata questo rapporto
può essere di un processo all'ora, mentre per brevi transazioni è possibile avere
una produttività di 10 processi al secondo.
• Tempo di completamento. Considerando un processo particolare, un criterio
importante può essere relativo al tempo necessario per eseguire il processo
stesso. L'intervallo che intercorre tra la sottomissione del processo e il
completamento dell'esecuzione è chiamato tempo di completamento (turnaround
time), ed è la somma dei tempi passati nell'attesa dell'ingresso in memoria, nella
coda dei processi pronti, durante l'esecuzione nella CPU e nel compiere
operazioni di I/O.
• Tempo di attesa. L'algoritmo di scheduling della CPU non influisce sul tempo
27
impiegato per l'esecuzione di un processo o di un operazione di I/O; influisce
solo sul tempo di attesa nella coda dei processi pronti. Il tempo d'attesa è la
somma degli intervalli d'attesa passati nella coda dei processi pronti.
• Tempo di risposta. In un sistema interattivo il tempo di completamento può non
essere il miglior criterio di valutazione: spesso accade che un processo emetta
dati abbastanza presto, e continui a calcolare i nuovi risultati mentre quelli
precedenti sono in fase d'emissione. Quindi, un'altra misura di confronto è data
dal tempo che intercorre tra la sottomissione di una richiesta e la prima risposta
prodotta. Questa misura è chiamata tempo di risposta, ed è data dal tempo
necessario per iniziare la risposta, ma non dal suo tempo di emissione.
Generalmente il tempo di completamento è limitato dalla velocità del dispositivo
d'emissione dati.
Utilizzo e produttività della CPU si devono aumentare al massimo, mentre il tempo di
completamento, il tempo d'attesa e il tempo di risposta si devono ridurre al minimo.
Nella maggior parte dei casi si ottimizzano i valori medi; in alcune circostanze è più
opportuno ottimizzare i valori minimi o massimi, anziché i valori medi; ad esempio, per
garantire che tutti gli utenti ottengano un buon servizio, può essere utile ridurre al
massimo tempo di risposta.
3.2.4 Algoritmi di scheduling
• Scheduling in ordine d'arrivo
• Scheduling per brevità
• Scheduling per priorità
• Scheduling circolare
• Scheduling a code multiple
3.3 Job Manager
In questo paragrafo viene descritto lo scenario in cui andrà a definirsi l'attività di
28
tirocinio.
Con Job Manager o anche detti Batch System si intende tutti quegli applicativi che si
occupano della gestione dei processi sottoposti ad un calcolatore o ad un insieme di
calcolatori collegati tra loro, i così detti cluster.
In maniera molto semplificata un Job Manager può essere visto come il sistema di
gestione della CPU di un sistema operativo con la capacità di gestire molteplici risorse
sia del calcolatore su cui risiede il Job manager che di altri calcolatori che tramite rete
mettono a disposizione le loro risorse computazionali.
Le risorse gestite da un Job Manager posso essere di tipo hardware e software, infatti il
Job Manager di un sito di calcolo ha in gestione le CPU, la memoria RAM e i dischi
fissi presenti sui calcolatori; inoltre il Job Manager si occupa di gestire anche le risorse
software necessarie di volta in volta ai job a lui sottomessi, infatti possono essere
richieste librerie o sistemi operativi specifici per l'esecuzione di un determinato job.
I Job Manager per svolgere il loro compito di “organizzatori del sito” sfruttano
principalmente le code, in tali code vengono inseriti i vari job sottomessi al sito di
calcolo per poi essere eseguiti.
Le code possono essere organizzate e servite in moltissimi modi diversi, infatti tramite
diversi algoritmi, diverse policy e tramite l'uso di preemption e di QoS i job vengono
serviti con criteri ben precisi e definiti dall'amministratore del sito.
I Job Manager per prima cosa devono essere configurati in modo da poter conoscere le
risorse a disposizione del sito così da poterle distribuire hai vari processi in modo
ottimale.
I Job Manager per la gestione delle code si avvalgono di un altro applicativo in diretta
collaborazione con il Job Manager stesso i così detti Job Scheduler, è proprio sull'analisi
e configurazione ottimale di tali applicativi che si snoderà il percorso pratico dell'attività
di tirocinio. In particolare andremo ad analizzare principalmente due Job Scheduler:
Maui e Moab, secondariamente andremo ad analizzare le principali caratteristiche di un
terzo Job Scheduler: LSF.
29
3.3.1 Algoritmi di assegnazione dei nodi
Mentre la priorità dei job permette al sito di calcolo di determinare quale job eseguire, le
policy di allocazione dei nodi permettono al sito di specificare quale è lo stato delle
risorse disponibili e come può essere allocato a ciascun job.
L'algoritmo usato per l'assegnazione delle risorse è specificato nel file di
configurazione, più precisamente per quanto riguarda Maui e Moab nel parametro:
NODEALLOCATIONPOLICY
Da Maui e Moab vengono messi a disposizione più algoritmi che permettono di
eseguire la selezione delle risorse su canoni di valutazione diversi.
FIRSTAVAIABLE, LASTAVAIABLE, MACHINEPRIO, CPULOAD,MINRESOURCE, CONTIGUOUS, MAXBALANCE, FASTEST and LOCAL
Altri tipi di algoritmi possono essere aggiunti attraverso estensioni di librerie.
Ora analizziamo come questa servizio offerto da Maui e Moab può essere al meglio
sfruttato, abbiamo osservato che una gestione dell'allocazione delle risorse diviene
fondamentale soprattutto in alcune situazioni:
• nei sistemi eterogenei
• nei sistemi a nodi condivisi
• nei sistemi basati sulla prenotazione del nodo
• nei sistemi senza una connessione “illimitata”
Descriviamo ora le caratteristiche principali dei vari algoritmi.
• CPULOAD
I nodi vengono scelti sulla base del carico della CPU, o meglio, viene selezionato il
nodo maggiormente scarico. Tale algoritmo può essere applicato ai job che entrano in
esecuzione immediatamente, infatti, la valutazione del carico della CPU è una
30
valutazione istantanea, se volessimo gestire job con partenza ritardata l'algoritmo
consigliato e il MINRESOURCE.
• FIRSTAVAIABLE
Questo algoritmo molto semplicemente assegna il primo nodo libero che è stato
elencato nel Resource Manager. Algoritmo molto veloce.
• LASTAVAIABLE
Questo algoritmo è un algoritmo “best fit in time” infatti minimizza l'impatto della
prenotazione dei nodi.
• MACHINEPRIO
Questo algoritmo permette di specificare la priorità di assegnazione dei nodi, è una
versione personalizzabile del MINRESOURCE.
• MINRESOURCE
Questo algoritmo seleziona il nodo con le caratteristiche e le risorse il più possibile
simili a quelle richieste da job.
• CONTIGUOUS
Questo algoritmo assegna i nodi in modo lineare uno dopo l'altro, era un algoritmo
richiesto dal Compaq RMS system.
• MAXBALANCE
Questo algoritmo tenta di allocare il più “bilanciato” set di nodi al job, la maggior parte
dei casi la misura per effettuare la scelta è data dalla velocità. Ad esempio se sono
richieste due CPU l'algoritmo tenta di assegnare CPU con la stessa velocità.
• FASTEST
Questo algoritmo seleziona il nodo che presenta la CPU più veloce.
• LOCAL
Questo è l'algoritmo di default, non ha nessun criterio particolare.
31
4 Grid
Il termine Grid Computing (calcolo a griglia) sta ad indicare un paradigma del calcolo
distribuito, di recente introduzione, costituito da un'infrastruttura altamente
decentralizzata e di natura variegata in grado di consentire ad un vasto numero di utenti
l'utilizzo di risorse (prevalentemente CPU e storage) provenienti da un numero
indistinto di calcolatori (di potenza spesso non particolarmente elevata) interconnessi da
una rete (Internet). Il termine “griglia” deriva dalla similitudine fatta dai primi ideatori
del Grid Computing secondo i quali in un prossimo futuro si sarebbe arrivati a poter
reperire risorse di calcolo con la stessa facilità con la quale oggi si può usufruire
dell'energia elettrica, ovvero semplicemente attaccandosi ad una delle tante prese
presenti nel nostro appartamento Power Grid.
Le prime definizioni di Grid Computing, di cui si sente spesso parlare come della
prossima rivoluzione dell'informatica, (come a suo tempo fu per il Word Wide Web),
risalgono di fatto a circa metà degli anni novanta.
Le griglie di calcolo vengono prevalentemente utilizzate per risolvere problemi
computazionali di larga scala in abito scientifico e ingegneristico (la cosiddetta e-
Science). Sviluppatesi originariamente in seno alla fisica delle alte energie, il loro
impiego è già da oggi esteso alla biologia, all'astronomia e in maniera minore anche ad
altri settori.
I maggiori player dell'ITC in ambito commerciale hanno già da tempo cominciato ad
interessarsi al fenomeno, collaborando ai principali progetti grid word-wide con
sponsorizzazioni o sviluppando propri progetti grid in vista di un utilizzo finalizzato al
mondo del commercio e dell'impresa.
32
L'idea del Grid Computing è scaturita dalla constatazione che in media l'utilizzo delle
risorse informatiche di un organizzazione è pari al 5% delle sue reali potenzialità. Le
risorse necessarie sarebbero messe a disposizione da varie entità in modo da creare
un'organizzazione virtuale (VO) con a disposizione un 'infrastruttura migliore di quella
che la singola entità potrebbe sostenere.
LHC@home è un progetto di calcolo distribuito partito il 1º settembre 2004 con lo
scopo di raccogliere dati per simulare l'attività del Large Hadron Collider, un progetto
del CERN di Ginevra in Svizzera per la costruzione di un acceleratore di particelle,
divenuto operativo nel settembre 2008.
4.1 Evoluzione del Grid Computing
Il progetto SETI@home, lanciato nel 1999 da Dan Werthimer, è un esempio molto noto
di un progetto, seppur semplice, di Grid Computing. SETI@home è stato seguito poi da
33
Illustrazione 3: LHC Grid Project
tanti altri progetti simili nel campo della matematica e della microbiologia.
A differenza di quella utilizzata da SETI@home, attualmente una grid viene concepita
prevedendo un livello middleware fra le risorse di calcolo, dette computing element
(CE) e memoria, dette storage element (SE) e gli utenti della griglia stessa.
Lo scopo principale del middleware è quello di effettuare il cosiddetto match-making,
ossia l'accoppiamento tra le risorse richieste e quelle disponibili in modo da garantire il
dispatching dei job nelle condizioni migliori avendo sempre visibilità dello stato
dell'intera grid.
Attualmente, la più importante grid europea è quella del CERN di Ginevra che ora si
chiama EGEE (gLite è il nome del middleware che viene utilizzato; precedentemente
LCG e prima ancora DataGrid), sviluppato da un team italo-ceco e prevalentemente
presso l'IFN, Istituto Nazionale di Fisica Nucleare.
L'organismo di riferimento per lo sviluppo di omogeneità e standard dei protocolli usati
dalle grid è GGF (Global Grid Forum), che ha creato gli standard OGSA (Open Grid
Services Architecture). Nel 2004 è stato emanato WSRF (Web Services Resource
34
Illustrazione 4: The Directory Information Tree (DIT)
Framework), che è un insieme di specifiche per aiutare i programmatori a scrivere
applicazioni capaci di accedere alle risorse di Grid.
4.2 Il Cluster Grid di Parma
Presso INFN di Parma sono attivi diversi gruppi di ricerca che si occupano di
simulazione numerica, particolarmente nei campi della Relatività Generale e della
Teoria di Gauge su Reticolo.
Riguardo la simulazione numerica della Relatività Generale, Parma fa parte di una
collaborazione nazionale che ha installato a Parma 2 cluster MPI:
• Albert100, installato nel 2002, è composto da 44 Dual PIII a 1.13 GHz, con
interconnessioni in Fast Ethernet.
• Albert2, installato nel 2004, è dotato di 16 Dual Opteron e Infiniband.
35
Illustrazione 5: GridLab
Le simulazioni su reticolo della QCD vengono svolte prevalentemente con strumenti di
calcolo dei progetti APE, con cui Parma collabora attivamente, anche con cluster di PC.
Attualmente vi sono 2 installazioni:
• HAM, composto da 10 Dual Athlon a 2GHz con rete Myrinet.
• Exalibur, dotato di un blade con 7 DualXeon.
Esiste inoltre una farm di Calcolo Dipartimentale, senza supporto MPI, con 4 nodi di
calcolo a 64 bit e 3 nodi a 32 bit, a disposizione di tutti gli utenti locali del sito.
Infine, dal 2004, è attivo un sito INFN-Grid con 4 dual Xeon 2.4GHz dedicato
prevalentemente per il calcolo Mpi e per lo storage di dati delle Virtual Organization di
Theophys e ILDG (International Lattice Data Grid).
Il Resource Manager utilizzato da tutti i cluster (che ne fanno uso) è OpenPBS o
Torque/Maui.
36
Illustrazione 6: Il cluster Grid di Parma
5 Job Sheduler
L'obbiettivo di uno scheduler nel senso più ampio è quello di rendere gli utenti e gli
amministratori felici. Gli utenti desiderano la possibilità di specificare le risorse,
svolgere rapidamente il loro job e ricevere affidabile allocazione delle risorse. Gli
amministratori desiderano utenti soddisfatti e gestione semplice e completa. Così da
comprendere al meglio sia il carico di lavoro alla quale il loro sistema è sottoposto che
le risorse a loro disposizione. Questo include stato del sistema, statistiche dettagliate e
informazione su cosa sta avvenendo all'interno del sistema.
Gli amministratori dei siti necessitano di un completo set di comandi e funzioni che
permettano la gestione del sistema, la gestione degli utenti e la regolazione delle
statistiche.
I job scheduler sono componenti fondamentali di sistemi più ampi, i Sistemi Batch
(Batch system), tali sistemi si occupano dei meccanismi per sottomettere, lanciare e
tracciare un job all'interno di un pool di risorse condivise. Il servizio di scheduling
provvede a fornire un accesso gestito e centralizzato di tali risorse.
I job-scheduler spesso sono integrati in un batch-system, il batch system è colui che si
occupa di eseguire il match-making tra le richieste e le risorse, i batch-system
maggiormente utilizzati sono principalmente 4:
• LSF: (Load Sharing Facility), sviluppato da Platform, fa sia da batch-system che
da job-scheduler. E' il sistema attualmente in uso dal CNAF, è a pagamento.
• SGE: (Sun Grid Engine), sistema sviluppato da Sun a pagamento.
• TORQUE-MOAB: sviluppati dalla Cluster Resource inc., Moab è un scheduler a
pagamento.
• TORQUE-MAUI: in questo caso il batch-system è Torque mentre il job-
scheduler è Maui, sono entrambi open source. Vengono sviluppati dagli stessi
produttori di Moab.
La soluzione Torque-Maui è quella attualmente utilizzata dall'Università di Parma e sarà
37
il sistema di riferimento durante lo svolgimento di questa tesi.
Avendo la possibilità di usufruire di alcune licenze di LSF a basso costo tramite
particolari accordi con l'INFN durante il nostro lavoro ci preoccuperemo di paragonare
l'uso e le potenzialità di Maui con LSF.
5.1 Controllo del traffico
Lo scheduler deve prevenire che i vari job interferiscano tra di loro. Se più job
dovessero contendersi delle risorse l'un l'altro può verificarsi un calo delle performance
del cluster, allungare i tempi di esecuzione dei job o perfino portare al fallimento di
alcuni job. Quindi lo scheduler dovrà tenere traccia delle risorse utilizzate dai vari job
cosi da prevenirne l'uso concorrente.
5.2 Obbiettivo primario
Quando un cluster per il calcolo Grid viene creato, viene creato sempre per uno scopo
primario. Tale scopo porta a definire diverse regole su come il sistema potrà essere
utilizzato, chi o cosa potrà essere eseguito, per fare ciò lo scheduler dovrà implementare
una serie di policies che vincoleranno lo scheduler stesso durante l'assegnazione delle
risorse.
5.3 Ottimizzazione
Spesso le richieste sottomesse ad un sistema sono superiori alle sue possibilità. Uno
scheduler intelligente dovrà prevedere tale situazione e prendere decisioni corrette così
da permettere un completo svolgimento di tutti i job sottomessi e una rapida
assegnazione delle risorse che al termine di ogni singolo job andranno a liberarsi.
5.4 MAUI
Ora analizzeremo le principali funzionalità dei job-scheduler come queste funzionano e
come esse intervengono nella gestione delle code.
Tali funzionalità verranno analizzate nell'ambito del job-scheduler Maui, essendo quello
38
utilizzato durante il lavoro di tirocinio.
Tale scelta non è particolarmente limitante, infatti, abbiamo osservato che le tecniche di
gestione delle code sono comuni a tutti i job-scheduler, in alcuni casi sono molto simili
anche le tecniche di configurazione.
5.4.1 Filosofia e obbiettivi dello scheduler Maui
I gestori di un sistema rivolto al calcolo Grid desiderano il massimo ritorno degli
investimenti, spesso ciò significa un alto utilizzo del sistema e la possibilità di offrire
diversi servizi a vari utenti o gruppi di utenti. Hanno bisogno di capire come vengono
assegnate le risorse agli utenti che ne fanno richiesta e hanno bisogno di amministratori
capaci di soddisfare gli obbiettivi del sito.
Cosa avviene in uno scheduler può essere determinato solo tramite l'uso di misuratori
che devono essere stabiliti e condivisi. Successivamente tramite l'analisi delle statistiche
del sito tali misuratori potranno essere utilizzati al fine di stimare il buon o il cattivo
funzionamento del sito, la soddisfazione degli utenti e il carico complessivo o
temporaneo del sito.
Lo Scheduler Maui è stato sviluppato con un intensa collaborazione degli utenti,
amministratori e dei gestori. E' un tool studiato per gestire le risorse e fornire tutte le
informazioni dello stato attuale del sistema. Creato per soddisfare le necessità dei
sistemi batch e degli amministratori di tali sistemi impegnati costantemente nella ricerca
della configurazione ottimale per soddisfare le richieste degli utenti di gruppi e dei
gestori.
5.4.2 Scheduling Object
Maui funziona mediante l'uso di 5 oggetti primari: job, nodo, reservation, QoS structure
e policies.
• Job, il job da Maui è visto semplicemente come un set di richieste di risorse,
indipendentemente da cosa il job dovrà fare, per Maui il job possiede alcuni
parametri dove vengono specificati il tipo e la quantità di risorse necessarie, tali
39
informazione vengono passate da Resource Manager.
• Nodo, il nodo è un insieme di risorse con caratteristiche simili. Spesso il nodo è
semplicemente un PC ma sempre più frequentemente con l'avvento dei cluster
multiprocessore il nodo non è più visto come singolo PC ma come insieme di
tanti PC che forniscono risorse in modo condiviso. Le informazioni su nodi
vengono fornite dal Resource Manager.
• Reservation, è un oggetto che serve per riservare un blocco di risorse specifiche
per un uso particolare o per un utente particolare in un determinato periodo di
tempo.
• QoS Policies (Quality of Service Policies), vengono specificate nei file di
configurazione, e prevedono: job priority, fairness policies, fairshare
configuration e policy di scheduling.
• QoS Structure (Quality of Service Structure), è un set di policies che permettono
a Maui di gestire varie classi, utenti e gruppi.
5.4.3 Risorse
In Maui le risorse sono classificate in base a 4 parametri principali e 2 parametri
secondari.
I parametri principali sono: processore, memoria, swap e disco, mentre i parametri
secondari sono: task e processor equivalent (PE).
I task sono una collection di risorse che devono essere utilizzate insieme, come un
singolo nodo.
Il concetto di processor equivalent (PE) è necessario per tradurre in modo efficace le
capacità di calcolo di un nodo multi risorsa. Attraverso una semplice formula Maui
utilizzando le richieste di un job inviato dal Resource Manager calcola le effettive
necessita del job e le risorse che possono essere destinate a tale job.
PE = MAX(ProcsRequestedByJob / TotalConfiguredProcs, MemoryRequestedByJob / TotalConfiguredMemory, DiskRequestedByJob / TotalConfiguredDisk,
40
SwapRequestedByJob / TotalConfiguredSwap) * TotalConfiguredProcs
5.4.4 Class (or Queue)
In Maui le code vengono chiamate Class, sono dei contenitori logici che vengono
utilizzati per assegnare le policies ai vari job sottomessi al sistema. Spesso dei vincoli di
coda possono essere imposti dal Resource Manager così da indirizzare Maui nella
gestione del job. Vedremo successivamente come definire una coda in Maui, quali sono
i suoi utilizzi e possibilità.
Le classi vengono impostate nel file maui.cfg tramite il comando:
CLASSCFG[nomeclasse] ...parametri...
5.4.5 Partitions
Partizioni sono un costrutto logico utilizzato per suddividere le risorse a disposizione.
Un job può utilizzare per la sua esecuzione una o più partizioni (il default è una).
Tramite le partizioni lo scheduler può assegnare in modo efficiente le risorse rispettando
sia i vincoli di tempo di esecuzione che di priorità in base all'utente o al gruppo di utenti
che hanno lanciato il job.
La definizione delle partizioni viene data nel file di configurazione di Maui (maui.cfg)
tramite il comando:
NODECFG[nomenodo] PARTITION=nomepartizione
Con il comando NODECFG viene definito un nodo, come descritto sopra un nodo è un
insieme di caratteristiche simili, nell'ambiente GRID i nodi vengono detti WN (Worker
Node) e spesso sono vere e proprie macchine fisiche messe a disposizione del sito di
calcolo.
I nodi vengono definiti nel dettaglio nel Resource Manager, li sono definiti con il loro
nome e le loro caratteristiche (processore, memoria, disco …) nello scheduler vengono
semplicemente richiamati per poter essere assegnati a partizioni diverse.
41
5.4.6 Account
La credenziale account è spesso riferita ad un progetto o ad un gruppo di utenti che
devono lavorare su un progetto condiviso. Possiamo definire uno o più account
all'interno del file di configurazione tramite il parametro
ACCOUNTCFG[nomeaccount] ...
5.4.7 Priorità
Il concetto fondamentale che governa l'intero meccanismo di gestione delle code negli
scheduler per sistemi batch è il concetto di priorità.
Infatti il primo parametro con cui andremo a gestire le nostre code sarà il parametro
PRIORITY.
Maggiore sarà la priorità di un job e maggiore sarà la sua priorità nell'assegnamento
delle risorse da parte dei job scheduler.
Sulla priorità si basano anche tutti gli altri meccanismi di gestione di job degli
scheduler, sia di Moab che di Maui, tramite modifiche sulla priorità di un job viene
gestito il Fairshare anche la preemption come primo parametro di controllo usa il
parametro PRIORITY.
Il parametri PRIORITY può essere impostato in qualunque oggetto dello scheduler,
infatti la priorità di un job può essere data tramite la coda di assegnamento, l'account
con il quale viene eseguito oppure tramite la policy QoS che gli viene assegnata.
Ad esempio per assegnare ad una coda la priorità 1000:
CLASSCFG[nomecoda] PRIORITY=1000
5.4.8 Preemption
Molti siti possiedono cicli di job di diversa importanza. Mentre per alcuni job è
importante che le risorse siano assegnate immediatamente per altri job è possibile
attendere maggiormente la disponibilità delle risorse e quindi la loro terminazione.
Questi job a bassa priorità una volta cominciata la loro esecuzione possono anche essere
sospesi, per liberare risorse necessarie all'esecuzione di job a maggiore priorità, per poi
42
essere ripresi successivamente.
La gestione di questo meccanismo in Maui viene svolta tramite l'uso di due flag che
definiscono due tipologie di QoS. Certe QoS possono essere marcate con il flag
PREEMPTOR mentre altri vengono marcate con PREEMPTEE.
Con questa configurazione i job a bassa priorità o preemptee job vengono lanciati solo
quando ci sono risorse libere, e tali job possono essere eseguiti fino a che non arriva un
job classificato preemptor, in quel momento il job preemptee viene sospeso allo stato di
esecuzione a cui era arrivato e le risorse da lui occupate vengono liberate per il job a
maggiore priorità.
Solo dopo il termine del preemptor job il job appena sospeso verrà ricaricato e rimesso
in esecuzione.
Con questo approccio di gestione delle risorse possiamo mantenere il nostro cluster
vicino al 100% di utilizzo delle risorse.
Il comando per definire un QoS preemptee or preemptor è:
QOS[nomeQoS] QFLAGS=PREEMPTEEQOS[nomeQoS] QFLAGS=PREEMPTOR
Abbiamo quattro tipologie di gestione per un job che deve essere sospeso: suspend,
checkpoint, requeue, e cancel. La prima soluzione cerca di sospendere il job allo stato in
cui è arrivato per poi riprenderlo appena la risorsa richiesta viene a liberarsi, questa
soluzione è anche la soluzione che Maui adotta se non né vengono specificate altre. La
soluzione checkpoint utilizza la tecnologia di checkpointing per interrompere un job in
esecuzione, per sfruttare tale tecnologia sono necessarie alcune modifiche a livello di
kernel inoltre il codice del processo che verrà sospeso deve essere implementato
mediante la tecnologia di checkpointing.
La terza soluzione, quella probabilmente più utilizzata, interrompe il job in esecuzione e
lo rimette in coda, ovviamente cosi facendo viene perso lo stato in cui il job era giunto,
il job verrà rilanciato facendo ripartire la sua esecuzione dall'inizio. La quarta soluzione
adottata solo in casi estremi prevede l'eliminazione del job senza possibilità che esso
venga successivamente rieseguito.
43
Per impostare che tipologia di gestione lo scheduler deve utilizzare durante la
preemption dobbiamo impostare il parametro:
PREEMPTPOLICY SUSPEND
ResourceManager
Torque PBSPro LoadLeveler LSF
Cancel Yes Yes Yes YesRequeue Yes Yes Yes YesSuspend Yes Yes Yes YesCheckpoint Yes on IRIX Yes on IRIX Yes Dipende da OS
Tabella 1: Resource Manager Preemption Constraints
In base alla policy scelta bisogna specificare alcuni flag, che andranno a caratterizzare i
job che verranno eseguiti, infatti in ogni classe andrà inserito il parametro
JOBFLAGS=RESTARTABLE
oppure se si è scelto di sospendere i job:
JOBFLAGS=SUSPENDABLE
se è stata impostata la policy “suspend” bisogna impostare anche il parametro
SUSPENDSIG=19
nel parametro RMCFG.
Per prima cosa vanno impostati alcuni parametri generali sulla gestione delle
preemption policies:
PREEMPTPOLICY può assumere due valori: REQUEUE o SUSPEND, tali valori
indicano come viene gestito il job che viene sospeso per lasciare spazio al preemptor
job, nel primo caso il job viene rimesso in coda insieme ad eventuali altri job e si dovrà
aspettare nuovamente il suo turno per l'esecuzione, nel secondo caso invece il job viene
solamente sospeso senza perdere la sua posizione nello scheduler cosi che al termine del
44
preemptor job il job sospeso venga immediatamente ripreso.
PREEMPTPOLICY REQUEUEPREEMPTPOLICY SUSPEND
Ora impostati questi parametri generali possiamo procedere a definire le nostre QoS
Policies.
I comandi di preemption in Maui non sono flessibili come in altri sistemi, infatti
possiamo definire una coda o preemptor o preemptee e non entrambi e possiamo
definire una coda come preemptor e le altre come preemptee oppure una coda come
preemptee e le altre come preemptor.
Ora per impostare una coda come preemptee o preemptor andremo a generare duo o più
QoS Policies cosi da poterle poi assegnare ad ogni coda in modo generale.
Per creare una QoS Policy preemptee usiamo:
QOSCFG[nomeQoS] QFLAGS=PREEMPTEE
altrimenti per generare una QoS Policy preemptor usiamo:
QOSCFG[nomeQoS] QFLAGS=PREEMPTOR
Prima però di andare a gestire le QoS Policies dobbiamo attivare il parametro
QOSWEIGHT.
QOSWEIGHT 1
Ora una volta create le nostre policy possiamo assegnarla alle code (CLASS) usando
l'opzione QDEF nel parametro CLASSCFG
CLASSCFG[nomecoda] QDEF=nomeQoS
Il parametro QDEF assegna una o più QoS ad una coda, per assegnare ad una coda solo
ed esclusivamente una QoS dobbiamo usare il simbolo “&” al termine del nome della
QoS, nel nostro caso:
CLASSCFG[fast] PRIORITY=1000 QLIST=hi& QDEF=hi&
Assegnamo la QoS “hi” come unica QoS.
45
Un altro flag che bisogna impostare nella nostra coda “preemptee” è il flag che specifica
che i job sottomessi a tali code possono essere o sospesi o riaccodati.
CLASSCFG[slow] FLAGS=RESTARTABLE
Nel nostro caso abbiamo scelto di usarle la tecnica del riaccodamento quindi la coda
denominata “slow” ha il flag RESTARTABLE che indica che i job presenti in tale coda
potranno essere riaccodati in presenza di job “preemptor”.
La priorità della coda “preemptor” dovrà essere comunque posta molto maggiore delle
code “preemptee”, se i job con flag “preemptor” non avranno priorità maggiore dei job
“preemptee” non godranno della meccanismo di preemption.
Affinché la funzionalità di preemption funzioni correttamente dobbiamo impostare un
parametro anche in Torque; infatti alle code di Torque va comunicato che risorsa
utilizzare per mettere in esecuzione il job preemptor.
set queue <NOMECODA> resources_default.nodes=1:ppn=1
Cosi facendo comunichiamo alla coda che la risorsa di default da utilizzare è la 1 e la
CPU di default è la 1.
Ora possiamo testare la funzionalità della preemption infatti lanciando prima una job
sulla coda “preemptee” e poi un job sulla coda “preemptor” osserviamo che dapprima il
job preemptor viene messo in stato “idle” successivamente viene bloccato il job in
esecuzione che abbiamo lanciato per primo e il job “preemptor” viene messo in
esecuzione, il primo job che avevamo lanciato passa dallo stato “blocked” allo stato
“idle” pronto per essere eseguito appena vi saranno risorse disponibili.
Questa tecnologie la utilizzeremo durante lo sviluppo del progetto per risolvere la
problematica del job certificatore lanciato dalla comunità GRID per il test dei siti di
calcolo.
46
5.4.9 Fairness
Maui implementa la gestione del Fairness in diversi modi con diverse possibilità di
gestione e livelli di dettaglio.
In particolare in Maui il Fairness viene gestito tramite la combinazione dei parametri
indicati nella tabella sottostante:
Facility Description ExampleThrottlingPolicies
Imposta i limiti diutilizzo di ogni risorsadisponibile.
USERCFG[john] MAXJOB=3GROUPCFG[DEFAULT] MAXPROC=64GROUPCFG[STAFF] MAXPROC=128(permette a John di eseguire solo 3 job allavolta, permette al gruppo staff di utilizzarenon più di 128 CPU e a tutti gli altri gruppidi utilizzare non più di 64 CPU)
JobPrioritization
Specifica che parametroè il più importante allivello di policy per loscheduler.
SERVWEIGHT 1QUEUETIMEWEIGHT 10(provoca l'incremento di priorità dei job di10 punti ogni minuto che passano in coda)
Fairshare Specifica l'obbiettivo diuso per limitare l'accessoalle risorse, basato sullostorico dell'uso di risorse.
USERCFG[steve] FSTARGET=25.0+FSWEIGHT 1FSUSERWEIGHT 10(abilita il fairshare basato sulla priorità especifica un obbiettivo di fairshare perl'utente steve, i job di steve verrannofavoriti all'esecuzione in modo damantenere al 25% il totale di usodell'utente steve)
AllocationManagement
Specifica credenziali alungo termine, e limiti diuso a lungo termine.
BANKTYPE QBANKBANKSERVER server.sys.net(abilita il sistema di allocazione Qbank,permette di assegnare una maggioreattenzione alla priorità dei job lanciati dalsito server.sys.net)
5.4.10 Fairshare
E' il Fairshare lo strumento più innovativo e potente di Maui, infatti tramite il Fairshare
47
possiamo ottenere un perfetto bilanciamento del carico di lavoro del nostro sito,
mantenendo, come dice la parola stessa, una gestione giusta del sito.
Tramite il Fairshare possiamo applicare policy di gestione a tutte le nostre entità
presenti nella configurazione del sito di calcolo. Possiamo applicare Fairshare in modo
indipendente ad utenti, gruppi, code, account e a livello di QoS.
Il Fairshare in Maui è configurato in due livelli. Il primo, livello di sistema, riguarda
tutte quelle configurazioni che indicano come lo scheduler deve raccogliere e processare
tutte le informazioni di uso del nodo di calcolo. Il secondo livello si occupa di
configurare come le informazioni raccolte in base alle configurazioni del sito andranno
ad influenzare direttamente i job sottomessi.
I parametri a livello di sistema sono i seguenti:
• FSINTERVAL, indica la durata delle finestre di Fairshare.
• FSDEPTH, indica quante finestre dovranno essere conteggiate durante l'utilizzo
di Fairshare.
• FSDECAY, specifica il fattore di decadimento per ogni finestra.
• FSPOLICY, indica la metrica utilizzata durante l'utilizzo di Fairshare.
48
Abbiamo diverse metodologie con la quale possiamo tenere traccia dell'utilizzo delle
risorse, tale metodologia viene impostata dall'amministratore del sito tramite il
parametro FSPOLICY
Metrica Descrizione
DEDICATEDPESViene memorizzato il tempo di utilizzo delvalore “processore equivalente” per ognijob.
DEDICATEDPS Viene memorizzato il tempo di utilizzo delprocessore per ogni job.
PDEDICATEDPSViene memorizzato il tempo di utilizzo delprocessore in funzione della velocità dellaCPU del nodo per ogni job.
SDEDICATEDPES
Viene memorizzato il tempo di utilizzo delvalore “processore equivalente” infunzione della velocità del nodo per ognijob.
UTILIZEDPS Viene semplicemente memorizzati esecondi di uso del processore per ogni job.
Con il sistema di Fairshare il tempo viene suddiviso in un numero distinto di finestre
dette “fairshare windows”, la durata di tali finestre temporali viene specificata tramite il
parametro FSINTERVAL mentre tramite il parametro FSDEPTH viene stabilito quante
finestre nel tempo l'algoritmo di fairshare deve considerare, quindi il tempo di
valutazione del fairshare è dato dal valore FSINTERVAL*FSDEPTH.
Molti siti vogliono limitare l'impatto del fairshare in base al tempo di utilizzo. Il
parametro FSDECAY permette di assegnare maggiore importanza ai dati più recenti e
minore rilevanza ai fini de fairshare ai dati più obsoleti.
Il parametro è specificato con un valore compreso tra 0 e 1, di default è 1, cioè non c'è
decadimento nel tempo.
Riportiamo una tabella che permette di comprendere meglio il significato del parametro.
49
DecayFactor
Window0
Window1
Window2
Window3
Window4
Window5
Window6
Window7
1,00 100% 100% 100% 100% 100% 100% 100% 100%0,80 100% 80% 64% 51% 41% 33% 26% 21%0,75 100% 75% 56% 42% 31% 23% 17% 12%0,50 100% 50% 25% 13% 6% 3% 2% 1%
Quando Maui deve determinare l'uso fairshare di una particolare credenziale calcola il
peso del decadimento medio delle informazioni di uso del sito di calcolo per tale
credenziale utilizzando l'intervallo fairshare più recente, utilizzando il parametro
FSDEPTH per controllare il numero di finestre da valutare.
Per esempio, vogliamo conoscere la posizione dell'utente John avendo settato i
parametri di fairshare in modo seguente:
FSINTERVAL 12:00:00 FSDEPTH 4 FSDECAY 0.5
e assumendo che gli intervalli di fairshare hanno il seguente valori di utilizzo per
l'utente:
Fairshare Interval Total User John Usage Total Cluster Usage0 60 1101 0 1252 10 1003 50 150
Basandosi su queste informazioni, il valore corrente di uso fairshare per l'utente John
viene calcolato nel modo seguente:
USAGE = (60 + 0.5^1 * 0 + 0.5^2 * 10 + 0.5^3 *50) / (110 +0.5^1 * 125 + 0.5^2 * 100
+ 0.5^3 * 150)
50
5.4.10.1 Obbiettivi del fairshareUna volta configurate tutti i parametri delle policy di fairshare, bisogna impostare come
le le informazioni di fairshare andranno a modificare il comportamento dello scheduler.
Questo viene fatto tramite le specifiche degli obbiettivi di fairshare.
Gli obbiettivi di fairshare possono essere applicati a utenti, gruppi, account, QoS o code
utilizzando il parametro FSTARGET. Questo parametro permette alle informazioni di
fairshare di avere effetto sulle priorità dei job, il parametro può avere tre tipi di
impostazione che differiscono per il comportamento dello scheduler durante
l'applicazione delle policy di fairshare.
Tipo diobbiettivo
Valoreparametro
Impattosul job
Formato Descrizione
Meno - Priorità Uso percentuale Aggiusta la priorità del jobabbassandola quando l'usosupera l'obbiettivo di fairshare
Più + Priorità Uso percentuale Aggiusta la priorità del jobalzandola quando l'obbiettivo diuso scende
Obbiettivo Priorità Uso percentuale Aggiusta la priorità del jobquando l'uso non ha l'obbiettivodi fairshare
Ad esempio vogliamo che lo scheduler incrementi le priorità dei job di John sino a che
non viene raggiunto il 16.5 % dell'uso totale del cluster. Mentre le priorità di tutti gli
altri job vengono alzate o abbassate per portare il valore di uso del cluster al 10 % per
ogni job.
FSWEIGHT 1 FSUSERWEIGHT 100 USERCFG[john] FSTARGET=16.5+ USERCFG[DEFAULT] FSTARGET=10
Esiste anche un parametro che va a imporsi sulle richieste di aumento della priorità dei
job dovute al fairshare. Il parametro FSCAP può essere applicato a utenti, gruppi,
account, code e QoS e viene impostato con un valore relativo o assoluto e permette allo
51
scheduler di bloccare un job se tale job a raggiunto la percentuale di uso del cluster
impostata con tale parametro. Una volta che tale percentuale tornerà a scendere il job
verrà reinserito in coda per essere eseguito.
Tipo di limite Parametro Impattosul job
Formato Descrizione
Limite assoluti ^ Esecuzione Usoassoluto
Costringe il job ad attendereper la sua esecuzione
Limite relativo % Esecuzione Usopercentuale
Costringe il job nella suaesecuzione
Il seguente esempio costringe l'account “Marketing” ad un uso non superiore di 16.500
secondi di processore durante un periodo di una settimana, allo stesso tempo tutti gli
altri account sono costretti ad un uso non superiore al 10 %.
FSPOLICY DEDICATEDPS FSINTERVAL 12:00:00 FSDEPTH 14 ACCOUNTCFG[marketing] FSCAP=16500ACCOUNTCFG[DEFAULT] FSCAP=10%
Osserviamo come la finestra di valutazione di una settimana è data dal parametro
FSINTERVAL = 12 ore e il parametro FSDEPTH impostato a 14.
Per far si che le politiche di fairshare vengano utilizzate dobbiamo impostare il “peso”
che il fairshare assumerà durante i calcoli di priorità dei job, per fare questo dobbiamo
impostare il parametro FSWEIGHT.
Esistono politiche di gestione del fairshare anche più complesse, ma tali politiche
possono essere sfruttate solo utilizzando il job scheduler a pagamento Moab.
5.4.11 Reservation
La reservation è un meccanismo con il quale Maui garantisce la disponibilità di risorse
o set di risorse in un particolare momento.
Ogni reservation è formata da tre componenti principali: la lista delle risorse da
52
riservare, lo spazio temporale e la access control list (ACL). Esiste anche una Advanced
Reservation che abilità la gestione della reservation tramite la tecnologia di backfill,
dealine, QoS e meta scheduling.
La lista delle risorse per una reservation in Maui è specificata utilizzando un unico
oggetto “task” che descrive le risorse necessarie per la reservation. Ogni reservation può
contenere uno o più task che specificano le risorse necessarie.
Riportiamo un esempio per chiarire:
La reservation A necessita di 4 task. Ogni task è definito da 1 processore e 1GB di
memoria.
Abbiamo 3 nodi:
Node X ha 2 processori e 3 GB di memoria
Nodo Y ha 2 processori e 1 GB di memoria
Nodo Z ha 2 processori e 2 GB di memoria
Nel tentativo di raccogliere le risorse necessarie per la reservation Maui esamina ogni
nodo a turno. Maui trova che il Nodo X supporta 2 dei 4 task necessari riservando 2
processori e 2 GB di memoria, lasciando 1 GB di memoria non riservata.
Analizzando il Nodo Y osserva che può supportare solamente 1 task dei 4 necessari
riservando 1 processore e 1 GB di memoria, lasciando 1 processore inutilizzato.
Purtroppo non possiamo combinare la memoria rimasta libera del Nodo X con il
processore libero del Nodo Y, infatti per soddisfare le richieste di un “task” Maui
necessità che le risorse siano situate in un nodo solo.
Alla fine Maui analizza il Nodo Z che può supportare 2 task terminando la reservation
di tutte le risorse necessarie.
Attualmente le risorse che possono essere assegnate ad una reservation sono: processori,
memoria, swap, disco locale, periferiche, licenze software e tape drives.
Associata ad ogni reservation c'è il timeframe. Il timeframe specifica quando le risorse
dovranno essere riservate o dedicate al job che utilizzano la reservation. Il timeframe
53
consiste semplicemente in una data e ora di inizio e una data e ora di fine, oppure una
durata.
Le access control list sono utilizzate dalla reservation per specificare quali jobs hanno
diritto ad utilizzare la reservation. Solamente i job che vengono abilitati dai criteri della
ACL possono utilizzare le risorse riservate.
Attualmente le reservation access control list possono includer: utenti, gruppi, account,
classes, QoS, e anche la durata del job.
Ovvero possiamo creare reservation che possono essere assegnate hai job in base alla
loro durata prevista.
Mentre una reservation ACL permette ad un particolare job di utilizzare delle risorse
riservate, la reservation non impone ad un job di utilizzare tali risorse. Per ogni job
Maui tenta di assegnare la migliore combinazione di risorse possibile scegliendo tra
risorse riservate e non riservate.
Ad esempio
54
Illustrazione 7: Reservation
Nella figura 7 osserviamo che il job X rispetta i criteri di ACL di entrambe le
reservation A e B, Maui assegna le risorse per il job scegliendo sia dalle risorse riservate
che dalle risorse non riservate (in grigio).
Maui può comunque essere configurato in modo da obbligare i jobs a utilizzare solo le
risorse riservate, ovviamente se il job ne ha la possibilità.
Ci sono due tipologie di reservation con la quale i siti di calcolo possono lavorare.
Il primo, la reservation amministrativa, e tipicamente usata per creare reservation una
volta sola per soddisfare necessità di progetti o richieste speciali. Questo tipo di
reservation viene creata tramite il comando SETRES, questo tipo di reservation può
essere molto comoda se si presenta la necessita di riservare risorse in tempi brevi e per
situazioni temporanee.
Da notare che questo comando può sfruttare la tecnica delle espressioni regolari.
setres -g staff -d 8:00:00 'node[1-4]'
Il secondo tipo di reservation è la reservation permanente, viene utilizzata quando si
presenta la necessita di prenotare risorse in modo ricorrente e continuativo. Tale
reservation viene configurata all'interno del file di configurazione di Maui (maui.cfg).
Per esempio, la seguente configurazione crea una reservation permanente di 6
processori e 3 GB di memoria che possono essere utilizzati dalla coda “interactive”
durante le ore di lavoro.
SRNAME[0] interactiveSRTASKCOUNT[0] 6SRRESOURCES[0] PROCS=1;MEM=512SRPERIOD[0] DAYSRDAYS[0] MON TUE WED THU FRISRSTARTTIME[0] 9:00:00SRENDTIME[0] 17:00:00SRCLASSLIST[0] interactive
Dalla versione 3.2 di Maui possiamo configurare le reservation utilizzando il parametro
SRCFG ad esempio:
SRCFG[interactive] STARTTIME=9:00:00
55
ENDTIME=17:00:00SRCFG[interactive] PERIOD=DAYDAYS=MON,TUE,WED,THU,FRISRCFG[interactive] TASKCOUNT=6RESOURCES=PROCS:1;MEM:512SRCFG[interactive] CLASSLIST=interactive
RESERVATIONPOLICY indica se un job che aveva conquistato una certa priorità in
una coda e quindi aveva riservato per se delle risorse può o non può essere scavalcato da
un job giunto successivamente ma con priorità maggiore.
Infatti pensiamo ad un job in esecuzione che deve essere sospeso a causa dell'arrivo di
un preemptor job, il job sospeso tiene riservate per se delle risorse che tra l'altro stava
già utilizzando, mentre il job è sospeso viene sottomesso un job a maggiore priorità che
potrebbe scavalcare il job sospeso facendo perdere al job la prenotazione delle risorse.
Tale parametro specifica il comportamento dello scheduler in queste occasioni, le
opzioni possibili sono tre: CURRENTHIGHEST, HIGHEST, NEVER.
La prima opzione se impostata indica che solamente il job con un apposito parametro di
prenotazione (RESERVATIONDEPTH) più alto del job sospeso può passare avanti, la
seconda opzione indica che il job che a preso la prenotazione la potrà mantenere anche
se altri job con priorità maggiore sono stati sottomessi al sistema, l'ultima opzione
indica che non viene utilizzata la gestione delle prenotazioni.
RESERVATIONPOLICY CURRENTHIGHESTRESERVATIONPOLICY HIGHESTRESERVATIONPOLICY NEVER
5.4.12 Backfill
La backfill è una ottimizzazione dello scheduling che permette allo scheduler di ottenere
un impiego delle risorse migliore eseguendo i job a lui sottomessi non in ordine di
sottomissione. Infatti quando Maui ha assegnato la priorità ai job nella loro coda di
destinazione, in base ai fattori che influenzano la priorità di un job, Maui ordina i job in
funzione della priorità a loro assegnata. Dopo di che Maui cerca di eseguire il primo job
della lista, quello con la priorità maggiore. Siccome tutti i job e tutte le reservation
56
possiedono un tempo di partenza e un limite per essere eseguito, Maui può determinare i
tempi di completamento di tutti i job in coda. Di conseguenza Maui può determinare
quali risorse saranno disponibili prima per il job a maggiore priorità.
La backfill sfrutta proprio questa informazione, siccome Maui conosce le risorse
necessarie al job con maggiore priorità e conosce il tempo necessario perché le risorse
per tale job vengano liberate, Maui può determinare quali job possono essere eseguiti
senza influenzare i tempi di esecuzione del job in testa alla coda.
Abilitando la backfill lo scheduler può eseguire job a minore priorità senza che tali
esecuzioni influenzino la priorità del job in testa. Maui utilizzando la reservation
prenota le risorse necessarie per il job a maggiore priorità di volta in volta che esse
vengono liberate, così facendo tali risorse non potranno essere occupate al momento
dell'esecuzione del job.
E' stato osservato che l'utilizzo della backfill incrementa del 20 % le prestazioni di un
sito di calcolo di grandi dimensioni. Infatti molto spesso il 90 % dei job di breve durata
godono della tecnica del backfill.
Ci sono pero alcuni “lati negativi” nell'uso della backfill, il primo si osserva quando
l'uso della backfill comporta una diminuzione dell'influenza della priorità dei job
impostata dagli amministratori del sito di calcolo.
Maui utilizza tre algoritmi per la gestione della backfill:
• FIRSFIT
• BESTFIT
• GREEDY
57
La backfill viene abilitata specificando in Maui il parametro BACKFILLPOLICY, di
default la backfill è abilitata utilizzando l'algoritmo FIRSFIT. Comunque il parametro
può essere settato nel maui.cfg scegliendo tra uno degli algoritmi oppure impostandolo
a NONE cosi da disabilitarla.
Il numero di reservation che il meccanismo di backfill può utilizzare può essere
comunque impostato utilizzando il parametro RESERVATIONDEPTH.
5.4.13 Checkpointing
In Maui possiamo utilizzare la tecnologia di checkpointing durante la preemption,
infatti Maui appoggiandosi ad una libreria esterna gratuita, può utilizzare il
checkpointing per sospendere un processo in esecuzione con flag preemptee per
eseguirne un altro con flag preemptor, per poi riprenderlo dal punto esatto in cui l'aveva
interrotto.
Questa modalità di preemtion evita che un job debba ricominciare dall'inizio la sua
computazione nel momento in cui viene sospeso a favore di un job “preemptor”.
58
Illustrazione 8: Backfill
La libreria utilizzata è la Berkeley Lab Checkpoint/Restart (BLCR) , questa libreria che
deve essere installata prima dell'installazione del batch system implementa la tecnologia
di checkpointing kernel-mode.
Quindi la tecnologia di checkpointing nei sistemi batch può essere utilizzata non
soltanto per implementare fault tolerance ma anche come tecnica, molto efficiente, di
preemption.
Per impostare il checkpointing andiamo ad editare il parametro PREEMPTIONPOLICY
PREEMPTPOLICY CHECKPOINT
5.5 MOAB
Sempre sviluppato dalla Cluster Resource inc. lo scheduler Moab è un software a
pagamento che si appoggia al Batch System Torque per il suo funzionamento.
A differenza di Maui, Moab presenta maggiori possibilità di configurazione e gestione,
infatti presenta sia una gestione grafica attraverso un tool specifico che una gestione
remota tramite web server.
Ovviamente le principali caratteristiche di installazione e configurazione sono uguali a
quelle di Maui.
Moab permette di gestire il Fairshare su nodi multi-cluster, per fare ciò, è necessario
l'utilizzo di un identity manager, che si occupi di sincronizzare tutte le credenziali
presenti nel cluster.
Dopo alcuni test abbiamo osservato come Moab non si differenzi molto da Maui se non
in senso di possibilità e semplicità di gestione, gestione che potrebbe divenire piuttosto
complessa in siti di calcolo distribuito di grosse dimensione, dove gli utenti, le risorse e
le code di job da gestire potrebbero crescere notevolmente.
5.6 LSF
In diretta concorrenza con Moab si trova LSF (Load Sharing Facility), sempre a
pagamento presenta sia un Job Manager che un Job Scheduler.
59
Abbiamo testato anche LSF perché è attualmente il sistema utilizzato dal CNAF,
abbiamo riscontrato che una gestione meno complessa di Moab in quanto LSF offre una
gestione del sito di calcolo meno ampia e diversificata ma non per questo meno
funzionale.
Purtroppo è stato abbastanza complessa la gestione della licenza, essendo una licenza
condivisa posta su un server remoto, ed essendo un licenza basata sul numero di core
del sito di calcolo e non più sul numero di processori si è osservato come la scelta di
LSF come batch system potrebbe essere una scelta troppo onerosa.
5.7 Job Multiprocesso
Dopo aver analizzato tutte le tecniche di gestione delle code che vari job scheduler
possono offrire vorremmo fare un breve excursus su come l'introduzione dei job
multiprocesso sono andati ad inserirsi e ad influenzare la gestione di code di job.
Infatti se con i job sequenziali tutte le tecniche analizzate possono sembrare semplici e
facilmente realizzabili con i job multiprocesso le cose si complicano; basti pensare a
come può essere gestita la preemption se il job “preemptor” che deve essere eseguito è
un job multiprocesso che quindi ha bisogno di risorse multiple, oppure come la gestione
della starvation diventa molto più complessa quando ad esempio un job in coda richiede
10 CPU per essere eseguito, mentre le CPU continuano ad essere riassegnate a job che
richiedono una CPU per la loro esecuzione.
Di fondamentale importanza diventa la tecnica di backfill con reservation infatti tramite
la tecnica di reservation lo scheduler può programmare l'esecuzione di un job
multiprocesso senza paralizzare il sito di calcolo perché non vi sono risorse disponibili,
utilizzando la backfill per procedere con esecuzioni di job più “leggeri” in attesa che
tutte le risorse per il job multiprocesso vengano al liberarsi.
Oppure la gestione del checkpointing, che in presenza di job multiprocesso diventa
molto più pericolosa, proprio per questo la libreria BLCR collabora indipendentemente
dallo scheduler con la libreria MPI.
60
6 Sviluppo del progetto
In questo capitolo andremo a descrivere tutto il lavoro svolto durante l'attività di
tirocinio. Verranno descritti gli scenari di lavoro in dettaglio e tutte le operazioni,
scendendo nei dettagli del codice eseguito, necessario per rendere il sito INFN di Parma
funzionante, performante e per risolvere le problematiche del sito riscontrate durante i
precedenti utilizzi da parte degli utenti. Particolare attenzione è stata posta alle tecniche
di scheduling e gestione delle policy, ma dopo poco tempo si è resa necessaria una più
attenta analisi dei sistemi batch che erano già preinstallati sui calcolatori, così da poter
comprendere al meglio le loro capacità di utilizzo.
Inizialmente il lavoro è stato svolto sul cluster, già funzionante da tempo, dell'INFN di
Parma, su tale cluster vi è installato Torque come Job Manager e Maui come Job
Scheduler, su tale cluster si è svolta una prima analisi del lavoro da compiere
osservando il funzionamento del sito di calcolo e raccogliendo dati su tutte le
problematiche presenti e sulle eventuali migliorie da poter apportare.
Dopo di che si è passati ad una fase di test vera e propria che, non potendosi svolgere
sulle macchine del cluster INFN causa il suo utilizzo da parte dei gruppi di sviluppo e
ricerca delle varie facoltà e dagli utenti di Grid, si è svolta su un piccolo cluster creato
ad-hoc, così da poter gestire il cluster in modo del tutto autonomo e svincolato.
Tale cluster è composto da 4 calcolatori sui quali è stata installata una Scientific Linux
4.6. Il cluster prende il nome di SDLAB.
6.1 TORQUE
6.1.1 Installazione di TORQUE
Andiamo ad installare Torque su una macchina virtuale con Scientific Linux
(Utente: root)
Scarichiamo Torque
61
cd optmkdir torquecd torquewgethttp://www.clusterresources.com/download/torque/torque-2.3.5.tar.gz
Installiamo Torque
Deve essere preinstallato gcc
tar -xzvf torque.tar.gzcd torque./configuremakemake install
Configuriamo pbs_server (Torque)
Viene configurato Torque con una coda chiamata “batch”
./torque_setup root
Proviamo Torque
# shutdown server> qterm
# start server> pbs_server
# verify all queues are properly configured> qstat -q
# view additional server configuration> qmgr -c 'p s'
# verify all nodes are correctly reporting> pbsnodes -a
# submit a basic job> echo "sleep 30" | qsub
# verify jobs display
62
> qstat
Con il comando pbs_server avviamo il Resouce Manager. Prima di fare ciò è opportuno
configurare i nodi, in questo caso andremo a configurare la macchina stessa sia come
Resource Manager che come nodo di calcolo.
6.1.2 Creazione dei pacchetti RPM
Per aver una gestione dell'installazione di Torque migliore abbiamo la possibilità di
creare i pacchetti RPM, tramite il comando:
make rpm
Torque andrà a creare tutti i pacchetti necessari per l'installazione server e client di
Torque, i pacchetti verranno depositati in /usr/scr/redhat/RPMS/i386, ovviamente questa
cartella varierà a seconda della distribuzione linux in uso.
Tramite il comando rpm andremo ad effettuare l'installazione:
rpm -ivh torque-2.3.6-1cri.rpmrpm -ivh torque-server-2.3.6-1crirpm -ivh torque-devel-2.3.6-1crirpm -ivh torque-client-2.3.6-1cri
Questi 4 pacchetti sono necessari per l'installazione del server Torque, mentre:
rpm -ivh torque-2.3.6-1crirpm -ivh torque-mom-2.3.6-1cri
Sono i pacchetti necessari ai nodi di calcolo.
Installando Torque tramite i pacchetti RPM abbiamo la comodità di avere già
configurato i servizi di Torque in modalità esecuzione automatica all'avvio del sistema.
6.1.3 Il file “server_name”
Il principale file di configurazione di Torque viene creato durante l'installazione ed è
situato in /var/spool/torque ed è “server_name”, dentro tale file viene scritto il nome del
63
server sulla quale è in esecuzione Torque, su questo file si baseranno anche le
configurazione dei nodi di calcolo.
6.1.4 Il file "nodes"
File da creare solo nel Resource Manager in /var/spool/torque/server_priv/
localhost np=2
Con localhost indichiamo che la macchina è anche nodo di calcolo, con np indichiamo il
numero di processori della macchina.
6.1.5 Installare Torque in un nodo
Possiamo creare i pacchetti per la distribuzione di Torque
cd /opt/torque/torque/2.3.5make packages
Ogni nodo necessità dei pacchetti: torque-package-clients-linux-i686.tar.gz torque-
package-mom-linux-i686.tar.gz
6.1.6 Il file "config"
Tale file va creato e configurato su tutti i nodi di calcolo che andremo ad utilizzare nel
nostro cluster. Il file va creato in /var/spool/torque/mom_priv
$pbsserver localhost$logevent 255
Ora siamo pronti per rilanciare pbs_server e su ogni nodo lanciamo pbs_mom.
Attenzione, terminata tale procedura i job non verranno eseguiti per mancanza dello
scheduler.
Torque installa uno scheduler di default che si può avviare tramite il comando
64
pbs_sched, previa la sua configurazione tramite il file:
/var/spool/torque/sched_priv/sched_config. Tale scheduler è molto semplice sia nel suo
utilizzo che nelle sue capacità di gestione.
6.1.7 Creazione delle code
Con il comando “qmgr” andiamo a settare i parametri di Torque, infatti in Torque
dobbiamo per prima cosa andare a creare e impostare le code che ci serviranno nel
nostro sito di calcolo.
Dentro la cartella di installazione di Torque è presente un file “torque_setup” che
permette di creare una coda di default chiamata “batch” per cominciare ad usare Torque.
Altrimenti possiamo creare le code a nostro piacimento utilizzando il comando qmgr.
Nel nostro caso abbiamo creato una coda “cert” e altre due code per utilizzo comune
dette “slow” e “fast”.
qmgr -c "create queue cert"qmgr -c "set queue local queue_type = Execution"qmgr -c "set queue local enabled = True"qmgr -c "set queue local started = True"qmgr -c "set queue local resources_max.cput = 00:40:00"qmgr -c "set queue local resources_max.walltime =01:10:00"qmgr -c "set queue local max_queuable = 10"
qmgr -c "create queue slow"qmgr -c "set queue local queue_type = Execution"qmgr -c "set queue local max_running = 10"qmgr -c "set queue local enabled = True"qmgr -c "set queue local started = True"qmgr -c "set queue local resources_max.cput = 00:40:00"qmgr -c "set queue local resources_max.walltime =01:10:00"qmgr -c "set queue local max_queuable = 10"
qmgr -c "create queue fast"qmgr -c "set queue local queue_type = Execution"qmgr -c "set queue local max_running = 10"qmgr -c "set queue local enabled = True"qmgr -c "set queue local started = True"
65
qmgr -c "set queue local resources_max.cput = 00:40:00"qmgr -c "set queue local resources_max.walltime =01:10:00"qmgr -c "set queue local max_queuable = 10"
Con il parametro max_running andiamo ad impostare il limite massimo di job che
possono esser eseguiti sulla coda, con il parametro resources_max.cput andiamo ad
impostare il tempo massimo di utilizzo della cpu di un job inserito nella coda, con il
parametro resources_max.walltime impostiamo il tempo massimo di accodamento di un
job e con il parametro max_queuable settiamo quanto lunga può essere la coda, nel
nostro caso superato i 10 job la coda non accetta più sottomissioni di job.
Con un comando di qmgr possiamo controllare le code create in Torque:
qmgr -c "list queue @localhost"
Ovviamente tutte le code inserite in Torque andranno poi configurate all'interno dello
scheduler, così che lo scheduler stesso si occuperà di assegnarvi dei job a seconda delle
richieste pervenute al sito di calcolo.
6.1.8 Il comando qsub
Il comando principale di Torque è qsub, tramite questo comando sottomettiamo un job
al sistema batch, indipendentemente dallo scheduler presente, il job sottomesso viene
accodato, se non è stata definita una coda di default o se non è stata specificata tramite
parametro, Torque stesso sceglierà una coda di assegnazione, ovviamente senza una
scheduler in esecuzione il job verrà accodato ma mai eseguito.
Con il comando qmgr impostiamo una coda di default, dove Torque inserirà i job a cui
nn è stata specificata la coda di destinazione.
qmgr -c "set server default_queue=slow"
Il comando qsub ha alcuni parametri con la quale è possibile gestire al meglio la
sottomissione del proprio job al sito di calcolo:
[-a date_time] [-A account_string]
66
[-c interval] [-C directive_prefix] [-d path] [-D path] [-e path] [-h] [-I ] [-j join ] [-k keep ] [-l resource_list ] [-m mail_options] [-M user_list] [-N name] 'Nome da assegnare al job[-o path] [-p priority] [-q destination] 'Coda di destinazione[-r c] [-S path_list] [-t array_request] [-T prologue/epilogue script_name] [-u user_list] [-v variable_list] [-V ] [-W additional_attributes] [-X] [-z] [script]
Torque offre altri comandi per la gestione dei job, comandi abilitati solo per gli
amministratori del sito di calcolo, come qdel che permette di cancellare un job o qrun
che permette di forzare l'esecuzione di un job in coda.
6.2 MAUI
6.2.1 Installazione di Maui
L'installazione dello schedule Maui è molto semplice infatti una volta scaricato il
pacchetto dal sito web andremo prima a scompattare il pacchetto e successivamente a
eseguire l'installazione.
Maui verrà installato sul server denominato Computeing Element (CE) come suggerito
dalle direttive della EGEE1.
1 Enabling Grids for E-sciencE (EGEE) is the largest multi-disciplinary grid infrastructure in the world.
67
> gtar -xzvf maui-3.0.7.tar.gz > cd maui-3.0.7 > ./configure > make > make install
6.2.2 Configurazione iniziale
Con l'installazione uno script preconfigurato si occuperà di settare i principali parametri
per una corretta esecuzione di Maui.
I parametri d'esecuzione di Maui vengono registrati in un file (maui.cfg), all'interno di
tale file troveremo tutte le impostazioni di Maui, dalle più generali alle più specifiche
che tratteremo direttamente come la gestione delle code di job.
Analizziamo i parametri principali che forniscono a Maui le informazioni sul sistema di
calcolo della quale andrà a far parte.
• SERVERHOST specifica dove Maui è in esecuzione, deve essere specificato il
nome del host per intero compreso il dominio di appartenenza.
• SERVERPORT specifica su quale porta il server Maui resta in ascolto per
ricevere le connessioni dei client. Default: 40559
• ADMIN1 Maui presenta tre livelli di sicurezza per quanto riguarda
l'amministratore del sistema, con ADMIN1 viene identificato l'amministratore
principale, ha possibilità di controllare completamente il sistema, sono presenti
anche ADMIN2 e ADMIN3 che hanno rispettivamente solo la possibilità di
modificare i permessi il primo e di avere informazioni sullo stato di Maui il
secondo.
• RMCFG[base] con questo parametro sono impostate tutte le informazioni
riguardanti il Resource Manager con la quale Maui dovrà collaborare.
◦ TYPE imposta il tipo di Resource Manager. Ex: PBS
◦ AUTHTYPE specifica il tipo di protocollo di sicurezza per il dialogo tra
Maui e il RM. Ex: CHECKSUM or PKI
◦ NAME specifica il nome del Resource Manager
68
◦ PORT specifica la porta sulla quale interrogare il Resource Manager
◦ POOLINTERVAL indica ogni quanto interrogare il Resource Manager, in
secondi. Ex: 60
• ADMINHOST specifica da quale host potranno pervenire i comandi di
amministrazione di Maui. Ex: grid-ce.pr.infn.it
6.2.3 Maui testing
Maui è stato studiato con la possibilità di effettuare dei test senza mettere a rischio
l'intero sistema, infatti possiamo eseguire Maui in “test-mode” cosi da mantenere in
esecuzione un eventuale precedente versione che è già in funzione all'interno del
sistema.
Nella modalità test Maui andrà a raccogliere le informazioni dal Resource Manager in
tempo reale e agirà come se fosse lo scheduling in esecuzione ma senza la possibilità di
lanciare, modificare o cancellare job, infatti tali comandi saranno disabilitati.
• SERVERMODE è il parametro con la quale andiamo ad impostare il tipo di
esecuzione di Maui.
◦ NORMAL
◦ TEST
◦ SIMULATION
6.2.4 File layout
$(MAUIHOMEDIR)
• maui.cfg file di configurazione di Maui
• maui-private.cfg file contenete le informazioni di configurazione private
necessarie al server
• fs.cfg file di configurazione del Fair Sharing, da Maui 3.0.6 e precedenti
versioni
69
• maui.ck Maui checkpoint file
• maui.pid Maui lock file per prevenire esecuzioni multiple
• log cartella contenente i file di log
◦ maui.log
◦ maui.log.1
• stats cartella contenente i file di statistica
◦ stats.<yyyy>_<mm>_<dd>
• tools cartella contenente i tool di Maui
• trace cartella con i trace file delle simulazioni di Maui
• bin cartella contenente i file eseguibili
◦ maui eseguibili
◦ maui_client eseguibili user-interface
◦ profiler tool per l'analisi delle statistiche
• src cartella con i sorgenti di Maui
• spool cartella con i file temporanei
• contrib cartella contenente i file di contributo di Maui, come algoritmi e GUI
Abbiamo osservato immediatamente che la posizione dei file non viene sempre
rispettata, infatti nell'installazione sulla quale stiamo lavorando, Maui è stato installato
nella cartella /usr/local/maui.
Anche il nome dei file di statistica non è uguale a quello dichiarato dai produttori di
Maui, probabilmente sono parametri che possono essere modificati durante la fase di
compilazione.
70
6.3 MOAB
Abbiamo installato anche lo scheduler Moab, sfruttando una licenza demo della durata
di 45 giorni, scaricabile dal sito di Cluster Resource previa registrazione
6.3.1 Installazione di Moab
Scarichiamo i pacchetti MOAB necessari:
• Moab Workload Manager
wget --http-user=leonardo.mutti --http-passwd=targetclusterhttp://www.clusterresources.com/download/eval/moab-5.3.0-linux-i686-torque.tar.gz
• Moab Cluster Manager
wget --http-user=leonardo.mutti --http-passwd=targetclusterhttp://www.clusterresources.com/download/eval/mcm-5.2.0-01.linux.tar.gz
• Moab Access Portal
wget --http-user=leonardo.mutti --http-passwd=targetclusterhttp://www.clusterresources.com/download/eval/map-5.2.0.tar.gz
cd /opt/moabtar -xzf moab-5.3.0-linux-i686-torque.tar.gzcd moab-5.3.0./configuremake install
6.3.2 Variabili d'ambiente
export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH
71
Questo comando possiamo anche renderlo permanente creando un file (es:moab-var.sh)
in /etc/profile.d con dentro il comando export sopra citato.
6.3.3 Avviamo Moab Workload Manager
moab
Con il comando “showq” possiamo testare il corretto funzionamento di Moab.
File di configurazione di Moab: /opt/moab/moab.cfg
6.3.4 Installazione Moab Cluster Manager
Il Cluster Manager è un tool grafico utile per controllare Moab e con esso l'intero
sistema batch, per impostare o modificare i parametri delle code e anche per analizzare
lo stato di utilizzo del sito.
Prima di installare il Cluster Manager proviamo la corretta esecuzione di Moab:
showq
tar -zxf mcm-5.2.0-01.linux.tar.gzcd mcm-5.2.0-01./mcm
72
6.4 Gestione del job CERT
Nel sito di Parma come negli altri siti che partecipano al progetto GRID a periodi
regolari viene sottomesso un job che ha il compito di verificare lo stato del sito e la sua
effettiva operatività.
Ovviamente a tale job viene assegnato un tempo di attesa scaduto il quale il sito viene
dichiarato inattivo, purtroppo questa eventualità può si verificarsi se il sito è
effettivamente inattivo, ma può verificarsi anche se il sito è completamente utilizzato e
non è stata configurata correttamente una logica di preemption per il job “certificatore”.
Per risolvere tale problematica abbiamo usato le preemption policies presenti in Maui,
abbiamo creato una coda, detta coda “cert”, che gode della possibilità di effettuare
preemption su tutte le altre code presenti nel sito, così da essere certi che anche se il sito
di calcolo dovesse essere al 100 % occupato al momento dell'arrivo del job cert, tramite
preemption verrà subito liberata una risorsa per la sua esecuzione.
73
Illustrazione 9: Moab Cluster Manager
6.5 Esecuzione di un job multiprocesso
Basandosi sulle ricerche svolte all'interno del gruppo INFN di Parma abbiamo provato
ad eseguire alcuni job multiprocesso all'interno del nostro nodo di calcolo di test così da
poter analizzare il comportamento dello scheduler Maui.
Prima di poter eseguire i job multiprocesso è stato necessario installare, basandosi sulle
linee guida di un documento già prodotto (“INTEGRARE IL CALCOLO LOCALE
MPI NELLA FARM INFN-GRID”), la libreria MPI-Start.
Dopo di che abbiamo osservato come l'esecuzione di job multiprocesso non comporta
particolari problematiche allo scheduler una volta che esso è stato configurato
correttamente, infatti l'esecuzione di job multiprocesso comporta principalmente il
problema di richieste di risorse più numerose per uno stesso job, richiesta che poteva
avvenire già in precedenza con job sequenziali.
Tramite l'utilizzo della reservation Maui gestisce tale problematica al meglio e
sfruttando la tecnica di backfill permette al sito di non giungere in situazioni di
starvation dovute a richieste di risorse troppo esose da job multiprocesso che
comporterebbero attese molto lunghe.
Per abilitare Maui alla gestione di job multiprocesso dobbiamo settare a true due
parametri:
ENABLEMULTINODEJOBS TRUE ENABLEMULTIREQJOBS TRUE
Per i dettagli di esecuzione di job multiprocesso rimandiamo al sito:
http://www.fis.unipr.it/dokuwiki/doku.php?id=grid:start
74
7 Conclusioni
Al fine di ottimizzare i criteri di scheduling per job multiprocesso in ambiente Grid,
sono stati testati i batch system Torque, con i relativi job scheduler Moab e Maui, e il
batch system LSF, integrato di job scheduler.
E' stato osservato come, rilasciato in licenza open source, Maui, insieme a Torque,
risponda perfettamente alle necessità di un sito di calcolo delle dimensioni simili a
quello dell'Università di Parma.
E' stato possibile, con successo, configurare Maui per la gestione di diverse code di job,
che tramite priority, policy, QoS e preemption possono soddisfare diverse necessità di
utilizzo da parte di svariati utenti.
L'impiego della preemption ha permesso di risolvere una problematica più volte
riscontrata all'interno di un sito di calcolo che vuole far parte di una rete estesa come
Grid, infatti il job di controllo, inviato da Grid per verificare lo stato del sito di calcolo,
deve avere priorità assoluta rispetto all'esecuzione di altri job, tale priorità di esecuzione
è possibile solamente mediante l'utilizzo della preemption.
E' stata analizzata la tecnica del fairshare e tramite opportune configurazioni è stato
introdotto il suo utilizzo all'interno del sito di calcolo, così facendo le risorse del sito
verranno assegnate dallo scheduler non più soltanto sulla base di policy e priority
predefinite ma anche mediante valutazioni statistiche di uso delle risorse nel tempo, che
permetterà una assegnazione “giusta” agli utenti.
Introducendo richieste di risorse del sito di calcolo da parte di job multiprocesso è stato
necessario installare la libreria MPI a supporto del resource manager Torque e sono state
testate due ulteriori caratteristiche dei job scheduler: backfill e reservation.
Tramite l'utilizzo della backfill è stata portata la percentuale di utilizzo delle risorse del
sito di calcolo al 90 %, mentre tramite l'impiego della reservation è stato garantita
l'esecuzione di job molto complessi e onerosi a livello di risorse richieste in tempi
ragionevoli.
75
Possibili sviluppi futuri potrebbero certamente interessare una migliore integrazione tra
batch system e sistema operativo.
Al termine di quest’esperienza ringrazio sentitamente il Prof. Roberto Alfieri per aver
creduto in me ed avermi assistito durante la stesura della tesi.
76
8 Bibliografia
• Andrew S. Tanenbaum,
Reti di calcolatori 4a Edizione, Pearson 2003.
• Abraham Silberschatz,
Sistemi Operativi 6a Edizione, Addisson-Wesley 2002.
• D. Gross e C.M. Harris,
Foundamentals of Queueing Theory, Wiley Series in Probability and statistics.
• L. Kleinrock,
Queueing System, Wiley and Sons
• E. Cinlar,
Introduction to Stochastic Processes, Prentice Hall 1975
77
9 Sitografia
• Cluster Resources Inc. - Homepage
http://www.clusterresources.com/
• Paltform - Homepage
http://www.platform.com/
• Future Technology Group – Berkeley Lab Checkpoint/Restart (BLCR)
https://ftg.lbl.gov/CheckpointRestart/CheckpointRestart.shtml
• Centro Nazionale per la Ricerca e Sviluppo nelle Tecnologie Informatiche e
Telematiche (CNAF) - Homepage
http://www.cnaf.infn.it/
• European Organization for Nuclear Research (CERN) - Homepage
http://www.cern.ch/
• Wikipedia – Italian Homepage
http://it.wikipedia.org/
• National Institute of Nuclear Physics - Homepage
http://www.infn.it/
• Università di Parma (Fisica) – Docuwiki Grid
http://www.fis.unipr.it/dokuwiki/doku.php?id=grid:start
• gLITE - Homepage
http://glite.web.cern.ch/glite/packages/R3.1/updates.asp
• TCG Working Group on MPI - Homepage
http://www.grid.ie/mpi/wiki/FrontPage
• Universität Stuttgart – MPI Project
78
http://www.hlrs.de/organization/amt/projects/mpi-start/
• IFCA Grid Website – Dokuwiki - MPI
http://wiki.ifca.es/e-ciencia/index.php/MPI_Support
79
10 Appendice A : maui.cfg
# maui.cfg 3.2.6p20
SERVERHOST localhost
# primary admin must be first in list
ADMIN1 root
# Resource Manager Definition
RMCFG[localhost] TYPE=PBS SUSPENDSIG=23
# Allocation Manager Definition
AMCFG[bank] TYPE=NONE
RMPOLLINTERVAL 00:00:02
SERVERPORT 42559SERVERMODE NORMAL
# Admin:
LOGFILE maui.logLOGFILEMAXSIZE 10000000LOGLEVEL 3
# Job Priority:
QUEUETIMEWEIGHT 1 CLASSWEIGHT 100QOSWEIGHT 1
# FairShare:
FSPOLICY PSDEDICATEDFSDEPTH 7FSINTERVAL 86400FSDECAY 0.80
# Throttling Policies:
80
# NONE SPECIFIED
# Backfill:
BACKFILLPOLICY FIRSTFITRESERVATIONPOLICY NEVERPREEMPTPOLICY REQUEUE
# Node Allocation:
NODEALLOCATIONPOLICY MINRESOURCE
#MULTIPROCESS
ENABLEMULTINODEJOBS TRUEENABLEMULTIREQJOBS TRUE
# QOS:
QOSCFG[hi] PRIORITY=1000 QFLAGS=PREEMPTOR:RESTARTPREEMPTQOSCFG[low] PRIORITY=10 QFLAGS=PREEMPTEE
# Standing Reservations:
SRSTARTTIME[test] 8:00:00SRENDTIME[test] 17:00:00SRDAYS[test] MON TUE WED THU FRISRTASKCOUNT[test] 20SRMAXTIME[test] 0:30:00
# Creds:
USERCFG[DEFAULT] FSTARGET=25.0USERCFG[john] PRIORITY=100 FSTARGET=10.0-GROUPCFG[staff] PRIORITY=1000 QLIST=hi:low QDEF=hiCLASSCFG[slow] PRIORITY=10 FLAGS=RESTARTABLE
QLIST=low& QDEF=low&CLASSCFG[fast] PRIORITY=1000 QLIST=hi& QDEF=hi&
81
![Compendium [G.Marciani] - Sistemi Operativi, Scheduling Della CPU](https://static.fdocumenti.com/doc/165x107/577cd23d1a28ab9e78954342/compendium-gmarciani-sistemi-operativi-scheduling-della-cpu.jpg)
