Capitolo 4

(1)

Capitolo 4

Broker System

Introduzione

In questo capitolo verranno illustrate le scelte e le motivazioni che hanno condotto all'implementazione di un prototipo di un tool che fornisce le funzionalità di information gathering e advance reservation e la rispettiva libreria di interfacciamento per utilizzare tali servizi. Inizialmente verrà discusso l'approccio adottato per la rappresentazione delle risorse sia dal punto di vista logico sia dal punto di vista della sintassi scelta per descriverle. Saranno introdotti i concetti di filtro e di vincolo che regolano i meccanismi del sistema di filtraggio e del sistema di prenotazione. In seguito sarà descritta l'architettura logica del sistema, elencando i moduli che lo compongono, per poi passare ai dettagli implementativi delle parti componenti il modulo Broker. Infine sarà presentata una breve panoramica della API fornita dalla libreria.

(2)

4.1 Ontologia fondazionale delle risorse

Le scelte fatte sono state guidate dalla necessità di supportare adeguatamente le richieste di eventuali mapper e/o scheduler di applicazioni parallele, quindi senza la pretesa di avere un'astrazione del tutto generale, ma che coprisse unicamente gli aspetti del campo di interesse. In particolar modo, il lavoro si è incentrato sulla descrizione del dominio delle risorse computazionali.

Pur non adottando un approccio semantico al problema del matching, esiste la necessità di definire un'ontologia delle risorse, che fornisca uno schema concettuale di classificazione. Il termine ontologia in questo caso va interpretato nella sua accezione più generica, cioè rappresenta una gerarchia di concetti, organizzati con la relazione di sussunzione, spesso chiamata isa, senza includere anche altre relazioni semantiche che descrivano il modo in cui i concetti sono interrelati. Si è quindi definito un'ontologia fondazionale che è in qualche misura assimilabile ad un glossario di base, nei cui termini tutto il resto deve essere descritto.

Per fare questo, siamo partiti definendo un'astrazione delle risorse che riuscisse a modellare e a classificare i sistemi esistenti. Da questa astrazione è scaturito un certo numero di vocaboli, propri del dominio, che sono andati a formare il lessico utilizzato per descrivere le caratteristiche funzionali e strutturali delle risorse.

In generale una applicazione parallela e nel caso particolare un programma assist sono costituiti da una rete di processi interconnessi. Quindi il relativo mapper e/o scheduler effettueranno richieste al fine di trovare risorse che soddisfino le caratteristiche di performance che i processi dovranno possibilmente avere durante l'esecuzione. Di fatto un processo, per essere

(3)

eseguito, ha bisogno essenzialmente di un processore e di una memoria, ma necessita anche di uno spazio disco, sia per eventuali operazioni di input/output, sia per essere memorizzato quando non è in esecuzione.

Risulta chiaro, a questo punto, che occorre un modo per descrivere le caratteristiche del processore, della memoria centrale e del supporto di memorizzazione di massa. Queste tre entità compongono l'unità minima che possa essere considerata come risorsa computazionale, cioè la macchina (machine, host o workstation).

Figura 4.1 Diagramma UML29_{rappresentante l'astrazione della risorsa computazionale di}

base. Ogni rettangolo rappresenta una classe, al cui interno sono descritti gli attributi più significativi. La linea rappresenta la relazione di composizione, ai suoi estremi è presente un rombo pieno indicante il tutto (o composito) e dall'altro un range numerico indicante la molteplicità della parte (o componente). Da notare che tale relazione sta ad indicare anche che le parti non esistono indipendentemente e al di fuori del tutto.

Una macchina può essere realizzata con varie architetture che si differenziano principalmente per il numero di processori e per la modalità

(4)

degli accessi in memoria centrale. In figura 4.1 è presente l'astrazione usata per descrivere la risorsa computazionale di base, che chiameremo Machine. Quindi le parti fondamentali componenti una risorsa di calcolo sono state identificate semplicemente con Processor, Memory e Disk. Tale astrazione permette di modellare molte delle architetture che occorrerà descrivere e utilizzare nel motore di matchmaking.

Tale astrazione consente di modellare, oltre ai sistemi monoprocessore come le workstation, anche diversi sistemi di calcolo multiprocessore. Una architettura multiprocessore a processori anonimi, meglio conosciuta come SMP30 può essere modellata con una machine composta da n processori e una singola memory. Invece un multiprocessore a processori dedicati conosciuto con il termine NUMA31 può essere modellato con una machine in cui il numero di memory cresce di pari passo con il numero di processor. Una risorsa di calcolo molto diffusa, sia per il basso costo sia per la facilità di realizzazione, sono i cluster [B99]. Tale termine viene comunemente utilizzato per identificare numerose tipologie di sistemi anche con caratteristiche tra loro piuttosto differenti [DSSS05]. Per esempio, i

comodity cluster sono un insieme di nodi di calcolo indipendenti e

interconnessi da una rete locale, in particolar modo i sistemi Beowulf [BEO] sono corredati di software che ne permette una gestione trasparente, cioè permette di vedere l’intero clustercome se fosse una singola macchina. Altro esempio sono i cluster blade, sistemi nei quali in un singolo box sono assemblati numerosi nodi di calcolo stand-alone interconnessi da reti ad alte prestazioni spesso ridondanti. Un sistema cluster può essere composto da nodi di calcolo a loro volta paralleli, in tal caso il cluster ha due livelli di parallelismo, dove il grado del primo livello è dato dal numero di nodi

(5)

interconnessi dalla rete di comunicazione locale, e il grado del secondo livello è dato, nel caso in cui i nodi siano omogenei, dal numero di processori presenti in ogni nodo. Tale distinzione viene sottolineata con i termini cluster-NOW, indicante il fatto che il grado di parallelismo del primo livello è superiore a quello del secondo, e con constellation, per indicare il caso opposto.

L'astrazione che presentiamo per descrivere le risorse computazionali di tipo cluster è quella presente in figura 4.2, in cui un Cluster viene presentato come una composizione di due o più Machine, precedentemente descritte. Tale astrazione ci consente di descrivere praticamente tutta la gamma di sistemi prima elencati, compresi cluster di SMP o di NUMA, sfruttando la definizione ricorsiva del termine Machine.

Figura 4.2 Diagramma UML rappresentante l'astrazione di un cluster (detto aggregato), vista come una relazione di aggregazione di due o più machine (detta parte). Questo relazione implica che l'aggregato non può esistere indipendentemente dalle parti, ma le parti possono esistere indipendentemente dall'aggregato.

A questo punto abbiamo a disposizione una serie di vocaboli sia per descrivere la struttura delle risorse computazionali: Cluster, Machine,

(6)

Processor, Memory e Disk, sia per descriverne le caratteristiche di

maggiore interesse: clockSpeed, size, capacity, nodecount, cpucount. Quest'ultimi, ed altri che aggiungeremo in seguito, assumeranno un ruolo determinante per l'espletazione delle funzionalità del broker. Vedremo in seguito che sarà possibile arricchire le descrizioni delle caratteristiche delle risorse computazionali con un numero arbitrario di attributi.

4.2 Classi per rappresentare le risorse

Per rendere il sistema espandibile sono state usate tecniche tipiche dei linguaggi di programmazione ad oggetti: interfacce e classi astratte; di conseguenza l'implementazione di tutto il sistema è stata realizzata per utilizzare tali tecnologie. Dal punto di vista programmativo, si è cercato di fornire un insieme di classi astratte che consentano la descrizione della struttura e delle caratteristiche di molti tipi di risorsa; senza dover intaccare l'organizzazione del sistema. Le classi astratte più importanti messe a disposizione sono Resource e Reservable. Parte delle funzionalità disponibili in queste classi sono stategià implementate perché indipendenti dal tipo di risorsa, le altre sono state solamente definite per mezzo di interfacce astratte. L'implementazione delle interfacce, e quindi il tipo di comportamento di queste funzionalità, sono demandate alle specifiche risorse. Nel caso generale, per descrivere la struttura di un nuovo tipo di risorsa, è possibile creare una gerarchia di classi la cui radice erediti dalla classe Resource e le cui foglie ereditino dalla classe Reservable. Tuttavia è sufficiente che la gerarchia sia formata da un'unica classe che erediti da Resource e incapsuli almeno un oggetto che eredita da Reservable. In

(7)

pratica, con una tale strutturazione, ogni tipo di risorsa può essere suddivisa in più parti, ognuna delle quali potrà essere prenotata separatamente, in pratica le classi che ereditano da Reservable rappresentano l'unità minima di prenotazione. Dai diagrammi UML presentati nelle figure 4.1 e 4.2 si ricava facilmente la composizione delle classi per rappresentare una risorsa computazionale in memoria, il diagramma è presentato in figura 4.3.

Figura 4.3 Diagramma UML rappresentante la gerarchia e la composizione delle classi per la descrizione delle risorse di tipo computazionale. Il nome delle classi in corsivo rappresentano classi astratte, la freccia vuota indica una relazione di ereditarietà.

Ogni classe che estende la classe Resource eredita anche una classe

Vocabulary, nella quale è possibile specificare tutti i termini che saranno

usati per definire gli attributi necessari per descrivere le caratteristiche qualificanti delle risorse. Tali attributi influenzano il comportamento di molte parti del sistema, tra cui il parser, il matchmaker e il sistema di

prenotazione. Questi attributi prenderanno il nome di attributi di vocabolario. Per gli attributi di carattere generale, invece, è disponibile la

classe ResourceAttributes, in cui saranno memorizzati tutti gli attributi i cui valori non determinano modifiche del comportamento del sistema. Questi

(8)

attributi saranno denominati semplicemente attributi generici. Scindere in due gruppi distinti gli attributi ha permesso di realizzare un sistema in cui è possibile dare un certo peso semantico ad alcuni attributi, consentendo di trattare tutti gli altri in maniera generica. In pratica solo gli attributi che sono contenuti nel vocabolario sono strettamente necessari e i termini lessicali che li descrivono non possono essere modificati, mentre gli altri attributi possono essere inventati e aggiunti dagli utenti. Per esempio la descrizione di un processore non potrà prescindere dall'attributo

clockSpeed. Se invece un utente volesse aggiungere la descrizione della

cache di secondo livello potrebbe inserire un attributo del tipo L2cacheSize e utilizzarlo per ottenere un filtraggio più accuirato.

4.3 Sintassi per la descrizione delle risorse

Avendo deciso di implementare un motore di matching simmetrico basato su attributi è necessario definire un linguaggio che ci permetta di descrivere e strutturare le caratteristiche delle risorse e le relative richieste. Per realizzarlo è stata adottata la tecnologia XML [XML04]. XML è un metalinguaggio di demarcazione per la descrizione di dati strutturati, che possiede una sintassi che consente di definire facilmente relazioni del tipo attributo-valore. Inoltre fornisce una serie di strumenti che consentono una semplice implementazione di parser e tool per la validazione dei documenti per mezzo del DTD32 o con XSD33.

Il corpo di un documento XML è composto da elementi che possono essere

(9)

annidati. Ogni elemento inizia con un tag o marcatore di apertura (esempio <tagname>) e termina con un tag di chiusura (esempio </tagname>) e comprende tutto quello che vi è annidato nel mezzo. Ogni tag può essere accompagnato da uno o più attributi espressi nella forma chiave=”valore”. A livello logico, tale struttura può essere rappresentata come un albero, quindi è facilmente adattabile all'astrazione che abbiamo dato delle risorse computazionali. I termini Cluster, Machine, Processor, Memory e Disk, descritti nel paragrafo precedente, verranno fatti corrispondere a tag per definire elementi XML. I termini usati per descrivere le caratteristiche delle risorse saranno utilizzati come valore per gli attributi. Di seguito forniamo la sintassi da noi utilizzata per la descrizione di una caratteristica di una risorsa:

<a name="value">

<d metric="value" type="value" value="value" /> </a>

Quindi se volessimo descrivere la frequenza del ciclo di clock di un processore a 2000 Mhz, dovremmo scrivere:

<a name="clockSpeed">

<d metric="Mhz" type="float" value="2000" /> </a>

</processor>

Questa sintassi permette di descrive un numero illimitato di caratteristiche per ogni risorsa o per ognuna delle sue parti. Inoltre permette l'introduzione di nuove caratteristiche nelle risorse già descritte, ottenendo una buona espandibilità. Nel resto del testo il termine attributo sarà utilizzato per indicare una singola caratteristica della risorsa e potrà essere specificato con

(10)

la sintassi sopra illustrata.

Anche se nel linguaggio per la descrizione delle risorse gli attributi risultano semanticamente equipollenti, in realtà, il motore di matchmaking, il parser e in generale il broker, ne utilizzano alcuni per espletare determinate funzionalità. Tali attributi sono i già citati attributi di vocabolario che assumeranno un valore semantico ben preciso e andranno determinati una volta per tutte.

Per quanto riguarda le risorse computazionali sono stati individuati i seguenti attributi di vocabolario: clockSpeed, size, capacity, fixedload,

nodecount, cpucount, clusterfrag e machinefrag. I primi quattro vengono

utilizzati per gestire le funzionalità di advance reservation; gli altri vengono utilizzati in parte dal parser e in parte dal motore di matchmaking. La presenza di questi attributi con i relativi valori nella descrizione di una risorsa computazionale è obbligatoria. In mancanza di tali attributi il parser cerca di determinarne un valore dipendentemente dal contesto e nel caso in cui no riesca in tale compito ne assegna uno di default.

Per convenzione, ogni documento XML contenente la descrizione di una o più risorse deve iniziare con il tag <resources> e terminare con il tag corrispondente nella classica sintassi XML </resources>. Di seguito riportiamo un esempio di un documento che rappresenta la descrizione completa di una workstation:

(11)

<disk>

</machine> </resurce>

L'attributo cpucount in questo caso è stato omesso, dato che il parser è in grado di inferirlo facilmente. Se la workstation da descrivere fosse stata un SMP con quattro processori, una possibilità sarebbe stata quella di replicare per quattro volte la sezione processor oppure, più semplicemente, sarebbe bastato specificare l'attributo cpucount con un valore uguale a quattro, lasciando immutato il resto della descrizione.

Di seguito presentiamo il documento che descrive il cluster pianosa presso il Dipartimento di Informatica dell'Università di Pisa, arricchito con gli attributi necessari al deploy di applicazioni Assist:

(12)

<disk>

</machine> </cluster> </resource>

Da notare l'uso dell'attributo nodecount del tutto simile a quello di

cpucount, precedentemente descritto. Nel caso si dovesse descrivere un

cluster non omogeneo, come per esempio backus.cli.di.unipi.it, con la sintassi attuale, occorrerebbe specificare tutte le machine.

Per terminare, qui di seguito presentiamo il DTD per la validazione dei documenti XML scritti con la sintassi illustrata precedentemente:

<!DOCTYPE resources [

<!ELEMENT resources (cluster*,machine*)> <!ELEMENT cluster (a*,machine+)>

(13)

<!ELEMENT machine (a*,processor+,memory+,disk*)> <!ELEMENT processor (a+)>

<!ELEMENT memory (a+)> <!ELEMENT disk (a+)> <!ELEMENT a (d)>

<!ATTLIST a name CDATA #REQUIRED> <!ELEMENT d EMPTY>

<!ATTLIST d metric CDATA #REQUIRED value CDATA #REQUIRED

type CDATA #REQUIRED >

Lo scopo di un DTD è quello di definire gli elementi ammessi nella costruzione di un documento XML. Può essere dichiarato all'interno di uno stesso documento XML (dichiarazione inline) oppure può essere un file esterno. Di seguito elenchiamo le caratteristiche di un DTD:

• Definisce gli elementi leciti all'interno del documento. Non si

possono usare altri elementi se non quelli definiti. Quindi è come una specie di "vocabolario" per i file che lo useranno.

• Definisce la struttura di ogni elemento. La struttura indica cosa può contenere ciascun elemento, l'ordine, la quantità di elementi che possono comparire e se sono opzionali o obbligatori. Quindi è una specie di "grammatica".

• Dichiara una serie di attributi per ogni elemento e che valori possono o devono assumerne questi attributi.

• Fornisce infine alcuni meccanismi per semplificare la gestione del documento, come la possibilità di dichiarare entity e la possibilità di importare parti di altri DTD.

(14)

4.4 Filtri

Nel paragrafo precedente è stata illustrata la sintassi per la descrizione delle caratteristiche delle risorse da utilizzare per pubblicare le informazioni nel Broker. Dato che il nostro sistema di matching si ispira in buona parte al modello simmetrico, in teoria, si potrebbe utilizzare la stessa sintassi per specificare le richieste. Al fine di offrire un'interfaccia più flessibile per la codifica delle richieste, invece di utilizzare la sintassi XML, è stato introdotto il concetto di filtro. Un filtro è l'entità con cui l'utilizzatore della libreria potrà specificare le caratteristiche desiderate dalle risorse. Di fatto, un filtro rappresenterà la modalità standard offerta dalla libreria per effettuare le richieste, anche se sarà messa a disposizione una funzionalità in grado di compilare un filtro partendo da una richiesta espressa con la sintassi vista sopra. Un filtro offrirà lo stesso potere espressivo della sintassi XML con in più, come vedremo, la possibilità di specificare vincoli relativi alle prenotazioni. Per mezzo delle impostazioni dei vari parametri del filtro è possibile interagire con il sistema di information ghatering, che restituirà soltanto le informazioni relative alle risorse che rispetteranno i requisiti desiderati. Per ogni filtro è necessario specificare il tipo di risorsa a cui ci si riferisce ed è possibile impostare vincoli di vario genere. Il Filtro, infatti, rappresenta essenzialmente un contenitore di vincoli. I vincoli possono essere di due tipi distinti:

• constraint: vincoli sulle caratteristiche delle risorse.

• reservation constraint: vincoli riguardanti il sistema di advance

(15)

Ogni vincolo del primo tipo dovrà essere specificato per mezzo di un oggetto Constraint. Tale vincolo è composto da un attributo, da un valore e da un operatore relazionale. I vincoli del secondo tipo saranno contenuti da oggetti denominati ReservationConstraint e saranno costituiti da uno slot temporale finito o infinito, una priorità, una percentuale di utilizzo della risorsa e in certi casi da una serie di attributi dipendenti dal tipo di risorsa che si desidera prenotare.

Formalmente, per ogni filtro si possono specificare zero o più constraint, questi dovranno riferirsi al tipo di risorsa selezionata nel filtro e, come vedremo, almeno un reservation constraint. Gli attributi dei constraint devono trovare corrispondenza tra gli attributi presenti nella descrizione della risorsa. Il sistema di filtraggio selezionerà come valide soltanto le risorse che rispetteranno tutti i requisiti impostati dai constraint compresi i reservation constraint. Inoltre non saranno ritenute valide le risorse che non possiederanno nella loro descrizione tutti gli attributi specificati dai vincoli del filtro. L'insieme delle risorse ottenuto dal filtraggio verrà restituito dalla libreria per mezzo di un iteratore, e utilizzando alcuni parametri del filtro sarà possibile richiedere anche l'ordinamento degli elementi restituiti.

4.4.1 Constraints

Un constraint è la descrizione di un vincolo per una determinata caratteristica di una risorsa. Come già accennato ogni constraint è composto da una terna di valori (attributo,valore,relOp), dove:

(16)

caratteristica di una risorsa.

• valore rappresenta il valore che deve avere l'attributo.

• relOp rappresenta l'operatore relazionale da applicare nel

confronto tra il valore impostato nel vincolo e il valore presente nel descrittore della risorsa interessata.

Quando si dichiara un filtro è possibile specificare un numero qualsiasi di constraint. Aumentando il numero di vincoli si ottiene una maggiore precisione nella selezione delle risorse a costo un maggiore carico computazionale nell'esecuzione dell'algoritmo di filtraggio. Infatti l'algoritmo dovrà prima individuare l'attributo corrispondente nel descrittore della risorsa e poi confrontarne il valore associato con quello presente nel vincolo. Il confronto dei valori avviene valutando una relazione del seguente tipo:

valore_v relOp valore_d

dove i valori valore_v del vincolo e valore_d del descrittore della risorsa saranno associati al medesimo attributo e dovranno essere dello stesso tipo (reale, intero, booleano, stringa), e relOp è l'operatore relazionale specificato tra i parametri del constraint. La valutazione di tale relazione restituirà sempre unn valore booleano.

Per rendere il meccanismo dei vincoli generico ed espandibile, quando si dichiara un constraint non è necessario distinguere gli attributi generici dagli attributi di vocabolario; infatti il filtro si incaricherà di differenziarli e di utilizzarli nella maniera appropriata rendendone la gestione trasparente all'utente. Inoltre non è necessario, anche se possibile, indicare il tipo del

(17)

dato relativo al valore dell'attributo di un constraint; il sistema di filtraggio, infatti, si incaricherà di inferirne automaticamente il tipo desumendolo dalla descrizione della risorsa fornita al Broker.

4.4.2 Reservation constraint

I vincoli destinati alla gestione del sistema di prenotazione verranno chiamati reservation constraint. Le informazioni necessarie per impostare un vincolo di questo tipo sono le seguenti:

• slot temporale (timeslot): indica iltempo per cui si intende utilizzare

una risorsa. Lo slot temporale è rappresentato da due attributi, l'istante di inizio (Ti) e quello di fine (Tf). Tali attributi possono assumere un qualsiasi valore che rappresenti un tempo espresso in secondi, inoltre sono ammessi anche alcuni valori speciali. Per esempio, il tempo di inizio può essere indicato come immediato (NOW), realizzando così una immediate reservation [KN00], oppure il tempo di fine può essere indefinito (UNDEFINED). Quest'ultimo sarà utile nei casi in cui non sia presente, o non del tutto specificato, un contratto di performance oppure nel caso di una computazione senza fine.

• percentuale di utilizzo (rate): indica la frazione della risorsa che si

intende utilizzare. Questo è senz'altro uno degli aspetti più delicati dell'intero sistema, in quanto non tutte le risorse possono essere utilizzate in maniera condivisa, e quelle che lo permettono spesso

(18)

sono gestite da uno strato software che ne maschera il controllo. Vedremo in seguito come ottenere questa percentuale per le risorse di tipo computazionale.

• priorità (priority): priorità della richiesta di prenotazione. Tale

priorità dovrà essere assegnata o vagliata da un eventuale sistema di controllo degli accessi, che lavorerà in base ai diritti posseduti dall'account dell'utente. Il meccanismo delle priorità può comportare la deschedulazione di una prenotazione con priorità bassa in favore di una con priorità alta. Questo può far scatenare una serie di operazioni, comprese segnalazioni ai livelli sovrastanti la libreria BrokerLib, al fine di trovare nuove risorse da assegnare alla prenotazione deschedulata.

I reservation constraint hanno lo scopo di fornire le informazioni necessarie al funzionamento del sistema di prenotazione. Tali informazioni sono inizialmente utilizzate per eseguire un controllo sulla possibilità di effettuare le prenotazioni delle risorse. In letteratura questa prima fase prende il nome di Admission Control [DG01]. Successivamente, le stesse informazioni serviranno per rendere effettiva la prenotazione della risorsa selezionata. Di fatto, ogni filtro dovrà contenere almeno un reservation constraint. Questo meccanismo è necessario sia per impedire che i tool di deploy utilizzino le risorse senza prenotarle, sia nei casi in cui non ci siano informazioni sufficienti per impostare i parametri di una prenotazione. Data questa necessità, ogni filtro sarà impostato di default con un reservation constraint di base contenete le informazioni sufficienti per effettuare una prenotazione generica, valida per qualsiasi risorsa. In pratica, verrà

(19)

impostato uno slot temporale avente il l'istante d'inizio (Ti) immediato e l'istante di fine (Tf) indefinito, la priorità sarò la minima possibile e il rate sarà pari al massimo (100%).

4.5 Architettura del sistema

Il sistema di brokering comprende sia la fase scelta delle risorse, in

letteratura denominata resource discovery o gathering, sia la fase di prenotazione delle stesse, detta advance reservation. Il sistema di brokering è composto da due entità, un modulo server denominato Broker e un modulo libreria denominato BrokerLib. I server Broker sono le entità predisposte alla gestione delle risorse locali di un dominio amministrativo. Il sistema di brokering è distribuito e può essere composto da un numero qualsiasi di broker, ognuno rappresentante il punto di accesso alle informazioni sulle risorse di un certo AD. All'interno di un dominio amministrativo è possibile eseguire più di un'istanza di broker. In tal caso, tutti i broker del dominio dovranno essere interconnessi in modo tale da formare una struttura gerarchica ad albero. La radice di tale albero risulterà l'unico punto di contatto per le richieste provenienti dagli strumenti che utilizzano la libreria BrokerLib, mentre i broker annidati nei nodi interni dell'albero saranno contattati ricorsivamente e in modo trasparente. Ogni nodo dell'albero potrà avere una qualsiasi arietà34. La possibilità di instaurare una gerarchia tra i broker all'interno di un dominio consente di riflettere gli eventuali annidamenti di sotto-domini amministrativi. Tale meccanismo permette sia di riflettere la topologia della rete, sia di rispettare

(20)

le relative politiche amministrative e di sicurezza.

Figura 4.4 Architettura del sistema di brokering. Ogni BrokerLib può contattare un Broker server per DA. In ogni DA è possibile creare un albero di Broker al fine di adattarsi alla topologia della rete.

Il modello di interazione utilizzato tra il Broker e la libreria BrokerLib è basato sul classico paradigma client-server. Ogni libreria potrà interfacciarsi con un numero qualsiasi di broker. I contatti tra la libreria e i broker verranno gestiti in maniera trasparente agli strati superiori, per mezzo di una API predisposta per l'interfacciamento con il servizio di brokering. Al fine di fornire un supporto ai meccanismi che gestiscono l'adattività delle applicazioni parallele e per minimizzare i costi delle comunicazioni, l'interfacciamento tra la BrokerLib e il Broker avviene per mezzo di

(21)

sessioni. Tale meccanismo è replicato anche tra i Broker server annidati, in modo da formare un albero di sessioni riconducibile ad un unico cliente. Questo dovrebbe garantire la possibilità di applicare politiche di controllo sull'accesso alle risorse.

Ogni modulo Broker è predisposto per effettuare, se necessario, anche un monitoraggio attivo delle risorse pubblicate. Il monitoraggio viene eseguito con la tecnica classica dei sensori, i quali potranno avere un'implementazione ad hoc, oppure, per mezzo di una apposita interfaccia, si potranno utilizzare i sensori di specifici tools (per esempio NWS [WSH99] o GANGLIA [MCC04]).

4.5.1 Architettura del Broker

Il broker deve svolgere essenzialmente due compiti: soddisfare le richieste riguardanti la raccolta delle informazioni sulle risorse e mantenere lo stato delle stesse, effettuando prenotazioni su richiesta. Per svolgere tali compiti, il broker, deve possedere una rappresentazione in memoria delle risorse che si vogliono pubblicare, deve avere un sistema per filtrare tali risorse in base alle caratteristiche delle richieste e implementare un sistema per la gestione delle prenotazioni. La figura 4.5 rappresenta l'architettura logica del broker, composta dai moduli che svolgono le funzionalità sopra elencate che ora analizziamo in dettaglio. Il Parser è il modulo incaricato di trasformare le descrizioni delle risorse, fornite in formato XML, in oggetti chiamati descrittori, adeguatamente strutturati e contenenti la rappresentazione delle caratteristiche delle risorse.

(22)

le connessioni con le varie istanze di BrokerLib e l'altro, invece, delegato alla gestione delle comunicazioni con i server Broker annidati.

Figura 4.5 Architettura logica del Broker server.

I due gestori sono interconnessi al fine di inoltrare le richieste provenienti dalle librerie a tutti gli eventuali livelli dell'albero di Broker di un dominio amministrativo.

Il Matchmaker System è il modulo incaricato di effettuare le operazioni di filtraggio sulle risorse. Le richieste vengono sottomesse al broker sotto forma di filtri. Il sistema elabora i filtri provenienti dalla libreria, eventualmente cercando prima una corrispondenza nella cache; infine restituisce un insieme di risorse che rispettano i requisiti richiesti. L'insieme restituito potrà essere ordinato secondo criteri scelti dall'utente e le risorse

(23)

saranno disponibili per la prenotazione. Il motore del matchmaker corrisponde ad un algoritmo di confronto tra i valori degli attributi dei vincoli di un filtro e i valori degli attributi contenuti nei descrittori delle risorse.

La Cache ha il compito di mantenere, secondo determinate politiche, l'associazione tra i filtri e l'insieme di risorse che il Matchmaker ha selezionato per mezzo di essi. Lo scopo di questo modulo sarà quello di cercare di diminuire i tempi dovuti al costo computazionale dell'algoritmo di filtraggio. Nel modulo Cache verranno memorizzati gli insiemi di risorse selezionati dall'algoritmo di filtraggio in base ai soli vincoli di tipo constraint. Da tali filtri verranno generate le chiavi per l'indirizzamento della cache. Ogni nuova richiesta contenente un filtro sarà inoltrata dal matchmaker a questo modulo. La cache dovrà verificare la presenza del filtro e, in caso positivo, restituirà l'insieme di risorse associato alla chiave generata dal filtro. L'insieme restituito dovrà comunque subire almeno un'ulteriore selezione di admission control per mezzo dei reservation constraint, al fine di ottenere uno stato aggiornato delle risorse.

Il modulo Advance Reservation System è il sistema di prenotazione delle risorse in grado di riservare frazioni di risorse per qualsiasi slot temporale, rispettando una politica di priorità. Per fare questo deve possedere lo stato aggiornato delle risorse e deve fornire per lo meno le funzionalità di prenotazione, rilascio e controllo dello stato. Per controllare che una richiesta di prenotazione (booking) possa essere soddisfatta, operazione che in letteratura prende il nome di Admission Control [B05], occorre possedere tre informazioni: slot temporale, priorità e rate.

(24)

4.5.2 Architettura della BrokerLib

La libreria BrokerLib fornisce l'interfaccia per l'accesso alle funzionalità messe a disposizione dai Broker, in pratica implementa un API. Tale interfaccia fondamentalmente offre la possibilità di stabilire e gestire una sessione di lavoro, nella quale è possibile la creazione e l'impostazione di filtri contenenti i vincoli relativi sia alle caratteristiche desiderate delle risorse, sia concernenti i parametri delle prenotazioni. La creazione di una sessione coinvolge uno dei componenti fondamentali della libreria, cioè il

gestore della sessione che è in grado di amministrare connessioni multiple

con i broker in modo trasparente. Tale trasparenza consente di impostare un unico filtro e farlo pervenire a tutti i broker che si è deciso di contattare. La peculiarità della libreria risiede nel modo in cui vengono raccolti i risultati del filtraggio. A tale scopo L'implementazione prevede che la API restituisca un iteratore, struttura dati tipica dei linguaggi orientati agli oggetti. Gli elementi restituiti dall'iteratore sono oggetti che astraggono ulteriormente la descrizione delle risorse presente nel Broker, i quanto forniscono metodi per effettuare direttamente operazioni di gestione delle prenotazioni, come se si avesse il controllo diretto della risorsa. Ogni iteratore potrà essere associato ad un unico filtro. Una caratteristica importante è la possibilità di richiedere l'ordinamento degli elementi restituiti dall'iteratore. Per mezzo del filtro, con cui verrà inizializzato l'iteratore, potrà essere impostato un certo tipo di ordinamento. In tale modo l'iteratore avrà le informazioni necessarie per selezionare il prossimo miglior elemento tra quelli che gli sono comunicati da tutti i Broker.

(25)

Figura 4.6 Architettura logica della libreria BrokerLib. I componenti più importanti sono il gestore della sessione, l'iteratore remoto e lo strato di astrazione delle risorse.

(26)

4.6 Implementazione del Broker

4.6.1 Modello usato per l'implementazione

L'implementazione del broker è basata sul modello classico server multi-threaded on demand ed è realizzato in java, in associazione con la libreria di IO basata su stream. La scelta dell'utilizzo di tale modello è dovuta alla facilità di implementazione che ne deriva, utile al fine della realizzazione di un prototipo, in termini di tempo necessario allo sviluppo. In future implementazioni sarà possibile adottare modelli diversi e più sofisticati con l'obbiettivo di ottimizzare le prestazioni. Tipicamente una prima ottimizzazione si ottiene passando dal modello on demand a quello thread

pool. Quest'ultimo consiste nella creazione e nell'attivazione di un numero

prefissato di thread, ai quali vengono passate le varie connessioni catturate dal thread principale. Alla chiusura di ogni connessione, il thread relativo non viene terminato ma viene sospeso e “riciclato” per una nuova connessione. Tale tecnica dovrebbe consentire la minimizzazione del tempo speso dalla JVM35 nella gestione dei thread e delle risorse associate. Nel nostro caso, ogni connessione rimane attiva per tutto il periodo di esecuzione del modulo brokerLib richiedente, quindi i tempi di creazione e attivazione dei thread dovrebbero risultare trascurabili. Un'altra possibile implementazione può essere realizzata utilizzando le libreria Java NIO, in cui il modello diventa single thread, ma realizzato sopra ad uno strato di gestione dei socket in grado di fare un demultiplexing dei canali di comunicazione. Questo modello risulta più complesso da realizzare ma elimina l'overhead associato alla gestione di thread multipli da parte della

(27)

JVM.

4.6.2 Sessioni

Una sessione è una connessione persistente tra un cliente ed un servente o più generalmente tra due peer. Nel prototipo implementato, viene istanziato un nuovo thread (worker), per ogni nuova connessione richiesta da un cliente BrokerLib. Il worker rimarrà attivo per tutta la durata della connessione e dovrà servire unicamente le richieste della BrokerLib invocante. In pratica ogni volta che una brokerLib richiede una nuova connessione ad un broker, fra i due moduli viene instaurata una sessione. Per ogni sessione viene istanziato un descrittore di sessione, il quale ha lo scopo di mantenerne lo stato. Nello stato sono presenti diverse informazioni:

• un identificativo univoco

• informazioni sul modulo brokerLib invocante

• informazioni sulle richieste e sulle prenotazioni effettuate

Se il Broker contattato da una BrokerLib è connesso ad un Broker annidato allora il worker, che crea la sessione, cercherà di mettersi in contatto con tale Broker, tentando a sua volta di stabilire una sessione. Questo comportamento del worker sarà reiterato per ogni nodo dell'albero dei Broker, creando una catena di sessioni riconducibili comunque ad un unico cliente. Tale meccanismo è realizzato utilizzando in maniera ricorsiva la API messa a disposizione dalla BrokerLib (figura 4.7). Infatti ogni worker

(28)

contattato da un cliente per mezzo della API, userà un'istanza della BrokerLib, quindi la API stessa per aprire una sessione con il Broker annidato.

Figura 4.7 Utilizzo ricorsivo della BrokerLib per la gestione delle sessione tra i nodi dell'albero dei Broker.

4.6.3 Sistema di prenotazione (Advance Reservation System)

Il sistema di prenotazione, descritto a livello logico come un modulo centralizzato, nell'implementazione ha una realizzazione distribuita. Il meccanismo che mantiene lo stato delle prenotazioni è realizzato dalla classe Reservation; un'istanza di tale classe è presente nella classe astratta

(29)

Reservable. Quindi tutte le classi che estenderanno la classe Reservable

erediteranno il sistema di prenotazione. Questo implica che ogni risorsa mantiene il proprio stato sulle prenotazioni e fornisce anche le funzionalità per gestirlo, realizzando così un sistema distribuito. Nel caso di una risorsa computazionale le entità che estendono la classe astratta Reservable sono

Processor, Memory e Disk. Questo implica che ognuna di esse avrà uno

stato e un interfaccia per gestire le prenotazioni in maniera separata.

Figura 4.8 (i) Diagramma di Gantt per l'allocazione di slot temporali. (ii) Aggiunta di un'asse al diagramma precedente per misurare percentualmente le sovrapposizioni degli slot.

(30)

temporali di attività, cioè lo stesso di un diagramma temporale di Gantt

(mostrato in figura 4.8 i). Il sistema deve tenere conto anche della possibilità di frazionamento della risorsa in funzione di eventuali sovrapposizioni degli slot temporali. Quindi al diagramma va aggiunto un asse raffigurante la percentuale di utilizzo della risorsa (figura 4.8 ii).

La struttura dati implementata per mantenere lo stato delle prenotazioni delle risorse deriva direttamente dalla figura 4.8 ii, arricchita dalla possibilità di ordinare gli slot temporali per priorità e quindi con la possibilità di deschedulare alcune prenotazioni. Tale struttura dati verrà discussa in seguito.

Le funzionalità offerte dall'interfaccia della classe Reservation, implementate nel prototipo sono:

• isFree(...): utilizzata per controllare se è possibile allocare in un dato

slot temporale la prenotazione richiesta; in pratica fornisce la funzionalità di Admission Control.

• book(...): utilizzata per effettuare la prenotazione, comporta una

transizione dello stato della struttura dati che gestisce la reservation per la risorsa.

• unbook(...): utilizzata per cancellare una prenotazione dal sistema.

La combinazione di queste uniche tre funzioni base consente di effettuare molte operazioni a più alto livello. Ad esempio la richiesta di modifica di una prenotazione può essere effettuata concatenando l'esecuzione delle funzioni nel seguente ordine: isFree(...), unbook(...), book(...). I parametri di ingresso di tali funzioni saranno le informazioni riguardanti le prenotazioni, le quali verranno raggruppate in oggetti che chiameremo booking. Tali

(31)

informazioni sono le stesse utilizzate per generare un Reservation

Constraint; per chiarezza verranno nuovamente elencate:

• slot temporale di durata della prenotazione (TimeSlot) • priorità (priority)

• percentuale di utilizzo (rate)

Tra queste, il rate è il valore più critico, in quanto andrà calcolato in funzione sia delle prestazioni che si vogliono ottenere dall'applicazione, sia delle prestazioni offerte dalla risorsa che si intende prenotare.

4.6.3.1 Struttura dati per l'Advance Reservation

La struttura dati che serve a mantenere le informazioni sulle prenotazioni concettualmente può essere vista come una lista di TSS36. Un TSS rappresenta un intervallo di tempo che può essere limitato o illimitato: un TSS limitato possiede un orario di inizio ed uno di fine, mentre un TSS illimitato possiede solo l’orario di inizio. I TSS sono ordinati temporalmente e gli intervalli di tempo che rappresentano sono fra loro a due a due disgiunti. E’ possibile definire la granularità dell’asse temporale fino ad arrivare alla risoluzione di un millisecondo; di default questa è comunque impostata al valore di un secondo. Il TSS al suo interno contiene una lista di Booking.

(32)

Figura 4.9 Rappresentazione della struttura dati per il mantenimento delle prenotazioni. Sono visibili i TimeSlotSchedule con la percentuale di risorsa allocata (TimeSlot1, …, TimeSlot3), le prenotazioni effettuate con la percentuale di risorsa prenotata (b1,…,b3) e le priorità ad esse associate (p1,…,p3). Sono inoltre rappresentati gli istanti temporali iniziali e finali dei TSS (t1,…,t50).

Il Booking rappresenta una singola prenotazione e contiene: il suo identificativo, l’intervallo temporale in cui ha validità (specificato con modalità analoghe al TSS), la percentuale di risorsa prenotata e la priorità. La lista di Booking posseduta dal TSS è l’insieme di tutte le prenotazioni attive nello slot temporale rappresentato dal TSS. Un TSS esiste se e solo se possiede almeno un Booking, un Booking appartiene almeno ad uno o a più TSS. Il TSS contiene anche la percentuale totale di utilizzo della risorsa nell’intervallo di tempo che rappresenta. Questo valore è ottenuto sommando le percentuali di utilizzo specificate nei booking presenti nella lista del TSS. In figura 4.9 viene mostrata la lista di TSS (TimeSlot1..3) con assegnate alcuni booking (b1, b2, b3) di diversa priorità (p1, p2, p3).

Il numero riportato in alto a destra nei TSS e nelle prenotazioni rappresenta rispettivamente la percentuale di utilizzo della risorsa in quell'intervallo di tempo e la percentuale di risorsa riservata per una particolare prenotazione.

(33)

Le funzioni che operano sulla struttura dati sono tre: isFree, Book e Unbook. Più in dettaglio:

• isFree: questa funzione serve a controllare se esiste la possibilità di effettuare la prenotazione specificata. Per far questo viene effettuata una ricerca binaria all’interno della lista dei TSS, confrontando l’intervallo temporale della prenotazione da effettuare con quello del TSS corrente e verificando, in caso di sovrapposizione di prenotazioni, il rispetto delle percentuali di allocazione.

• Book: partendo dalla situazione presentata in figura 4.9 inseriamo, ad esempio una nuova prenotazione (b4) che va dall’istante t21 all’istante t50; per far ciò viene invocata la isFreeAux la quale ha un comportamento analogo alla isFree ma addizionalmente restituisce il vettore dei TSS interessati dalla prenotazione; il vettore verrà utilizzato per operare le necessarie modifiche sui TSS. In questo caso verrà creato un nuovo TSS (TimeSlot4) e la prenotazione b4 sarà aggiunta sia al nuovo TSS che agli altri due coinvolti nell’operazione, che vengono a loro volta ridimensionati (TimeSlot2, TimeSlot3); durante l’operazione di assegnamento della prenotazione ai TSS vengono aggiornate anche le percentuali di utilizzo della risorsa. La situazione dopo l’inserimento è quella riportata in figura 4.10

(34)

Figura 4.10 Rappresentazione della struttura dati dopo l’inserimento di una nuova prenotazione (b4).

Consideriamo un altro caso: Partendo dalla situazione in figura 4.10 aggiungiamo la prenotazione b5 che specifica un intervallo da t33 a t37, intervallo completamente interno a quello rappresentato dal TSS 4. In questo caso durante la prima fase dell’inserimento vengono individuati tre TSS su cui intervenire (2,3,4). Il TSS 4 viene suddiviso in tre TSS (4,5,6) e vengono effettuati i necessari aggiornamenti visti nel caso precedente. La situazione risultante è quindi quella della figura 4.11

(35)

Figura 4.11 Situazione risultante dopo l’inserimento della prenotazione b5. Da notare come il TSS 4 venga frammentato in tre TSS diversi (4,5,6).

• Unbook: l’operazione di cancellazione è effettuata scorrendo la lista dei TSS e controllando l’appartenenza della prenotazione da cancellare al TSS corrente; una volta trovato il Booking, sfruttando i suoi riferimenti agli altri TSS a cui eventualmente appartiene, viene eliminato da tutti i TSS. I TSS che dopo questa operazione rimangono vuoti vengono eliminati. Poiché l’accesso alla struttura è effettuato tramite l’identificativo della prenotazione, l’implementazione attuale della Unbook scorre la lista per la ricerca della prenotazione da cancellare. Si potrebbe avere un accesso in tempo costante utilizzando una hashtable <id_prenotazione, rif_prenotazione> pagando un costo maggiore in termini di occupazione di memoria.

Presentiamo qualche considerazione sulla complessità di tali operazioni. Le funzioni IsFree e Book eseguono al loro interno una ricerca sugli elementi della lista di TSS. Questa è indicizzata e rende quindi possibile effettuare una ricerca binaria. Le altre operazioni effettuate (frammentazione e ridimensionamento dei TSS, assegnamento delle prenotazioni etc.) hanno complessità trascurabile rispetto alla ricerca nella lista. La complessità delle due funzioni è pertanto O(log n) con n numero dei TSS presenti in lista. La funzione Unbook, come accennato, per ragioni di implementazione esegue una ricerca che ha costo O(nm) con n pari al numero dei TSS trattati e m

(36)

funzione con l’ottimizzazione proposta precedentemente si potrebbe eliminare la ricerca e quindi portare la complessità della funzione a O(1).

4.6.4 Sistema di filtraggio

Il modulo di filtraggio è il motore di quasi tutte le funzionalità messe a disposizione dal Broker. Infatti, ogni BrokerLib che apre una nuova sessione effettuerà delle richieste di filtraggio. Quindi al fine di aumentare le performance del sistema, anche questo modulo è stato implementato in maniera distribuita. Tale scelta implementativa è stata agevolata dall'architettura multi-threaded adottata, in cui viene creato un thread (worker) per ogni nuova sessione. L'algoritmo usato per il filtraggio è suddiviso in tre fasi distinte:

• Valutazione degli attributi di vocabolario. • Valutazione degli attributi generici. • Admission Control della prenotazione.

La prima fase consiste nell'estrazione degli attributi di vocabolario, impostati nel filtro, e nell'applicare le regole associate a tali attributi. Le regole sono specifiche per ogni tipo di risorsa, quindi non è possibile dare una stima del costo computazionale per applicarle, in ogni caso bisogna necessariamente scorrere tutto l'insieme delle risorse.

La seconda fase consiste nell'applicazione dell'algoritmo di matching per gli attributi generici. Il comportamento dell'algoritmo è piuttosto semplice: prende in ingresso un filtro e confronta tutti gli attributi dei vincoli con

(37)

quelli presenti nei descrittori delle risorse. La complessità computazionale dell'algoritmo è in funzione del numero di confronti che si devono eseguire, quindi si è cercato di minimizzare tale numero. Se si confrontasse tutto l'insieme di attributi del filtro, di cardinalità m, con l'insieme di attributi di ogni risorsa, di cardinalità k, si dovrebbero effettuare k per m confronti. Invece si procede selezionando un primo attributo del filtro e si confronta con l'attributo corrispondente nei descrittori di tutte le risorse, ottenendo un sottoinsieme con cui verrà confrontato il secondo attributo del filtro. Questo procedimento viene reiterato fino all'esaurimento di tutti gli attributi. In questo modo, nel caso medio, in cui ogni sottoinsieme ha dimensione dimezzata rispetto al precedente, il numero di confronti può essere calcolato con la seguente:

∑

−1 0

2

k = i i

m

Questa formula rappresenta una serie geometrica di ragione 1/2, da cui si ricava che il numero di confronti, al variare del numero di attributi k tra 0 e infinito, varia tra 0 e 2m.

La terza fase è quella di Admission Control, necessaria affinché l'insieme finale delle risorse restituite possa essere prenotabile dagli utenti della libreria. Quindi dovranno essere scartate tutte quelle risorse che:

• pur rispettando i requisiti imposti dai vincoli del filtro, hanno già

assegnate delle prenotazioni nello slot temporale di interesse.

• la percentuale di risorsa libera è inferiore a quella calcolata (rate) per

(38)

• la priorità della richiesta non consente di rilasciare un numero

sufficiente di prenotazioni tale che la nuova percentuale di risorsa libera sia maggiore uguale al rate.

Una volta ottenuto l'insieme finale di risorse è possibile che nel filtro sia impostata l'opzione di ordinamento che fa transire in una nuova fase in cui l'insieme viene ordinato. L'algoritmo utilizzato nel prototipo per eseguire l'ordinamento è il mergesort offerto dalla libreria standard di Java. Il costo computazionale di tale algoritmo è di n*log(n), con n rappresentante la cardinalità dell'insieme da ordinare.

4.6.5 Parser

Il parser delle risorse è il modulo incaricato di allocare in memoria i descrittori delle risorse a partire dal file contente la loro descrizione, espressa con la sintassi XML discussa sopra. Esistono due tipologie di parser: validanti e non validanti. I primi, oltre a controllare se un documento è ben-formato, cioè che ogni elemento sia racchiuso tra due tag (uno di apertura e uno di chiusura), controlla anche se esso è un documento XML valido, cioè se è fedele alle regole definite nella sua DTD. I parser non validanti, invece, si preoccupano solo di controllare se un documento è ben formato. Il nostro prototipo, allo stato attuale, è validante solo in parte, anche se sarebbe possibile estenderlo in tal senso. Le possibili scelte implementative date dalla tecnologia Java sono essenzialmente due: usare un'interfaccia object-based oppure usare un interfaccia event-based. Con

(39)

l'approccio object-based, il parser costruisce esplicitamente in memoria un albero che contiene tutti gli elementi del documento XML. Con l'approccio event-based, invece, il parser genera un evento ogni qual volta incontra, durante la lettura del documento XML, un elemento, un attributo, o del testo. Sono previsti eventi per i tag di apertura e di chiusura, per gli attributi, per il testo, per le entità e così via. Questo secondo approccio è quello adottato dall'API SAX che è quella che abbiamo utilizzato per implementare il prototipo del parser. Il codice che gestisce gli eventi avrà come parametri d'input il nome del tag e gli eventuali attributi XML. Grazie a questo meccanismo è possibile generare i descrittori delle risorse con la struttura più idonea e funzionale al sistema, arricchendoli anche con gli oggetti dedicati alla gestione delle prenotazioni. Inoltre, tale meccanismo unito a quello della reflection di Java, permette, con un'opportuna implementazione, di ottenere un parser generico ed espandibile, cioè in grado di effettuare il parsing di nuovi termini, aggiunti al linguaggio di descrizione per rappresentare nuovi tipi di risorse. In tal è possibile generare agevolmente nuovi tipi di descrittori. Allo stato attuale il prototipo del modulo che effettua il parsing è in grado di interpretare solamente documenti XML contenenti la descrizione di risorse computazionali.

4.6.6 Caching dei filtri

Il sistema di caching dei filtri è stato introdotto con lo scopo di diminuire i costi computazionali dovuti all'algoritmo di filtraggio. In pratica è stata realizzata una struttura in grado di memorizzare i risultati dell’esecuzione dell’algoritmo di filtraggio associandoli ai relativi filtri utilizzati in input.

(40)

L'implementazione del sistema di caching è ottenuto mediante una struttura dati composita, formata da una tabella associativa (hash) i cui valori saranno riferimenti a vettori, in pratica una struttura simile ad una cache parzialmente associativa. Le chiavi della hash, che serviranno come indirizzamento primario, sono formate dalla concatenazione ordinata degli attributi dei singoli filtri. Ad ogni chiave è associato un vettore contenente, per ogni elemento, una coppia formata dall'insieme di risorse filtrate e dal filtro utilizzato per selezionarle. Questa struttura dati deve supportare essenzialmente i seguenti tipi di operazioni: inserimento, rimpiazzo e

accesso in lettura.

L'operazione di inserimento è eseguita al termine della prima fase dell'algoritmo di filtraggio, cioè dopo aver selezionato le risorse per mezzo dei soli constraint del filtro. Il modulo genererà una chiave, per indirizzare la hash, concatenando ordinatamente gli attributi presenti nei constraint. In pratica più filtri potranno essere mappati sulla medesima chiave della hash, dato che i loro constraint potrebbero contenere gli stessi attributi. Pe r risolvere questo conflitto viene utilizzato un vettore associato alla chiave, il quale memorizza, in ogni suo elemento, un filtro e l'insieme di risorse filtrate con esso. Nel caso in cui le entrate della hash o del vettore siano sature occorre effettuare una operazione di rimpiazzo per inserire le nuove informazioni. Per decidere cosa rimuovere dalla cache, le strutture dati sono state dotate delle informazioni necessarie per adottare entrambe le politiche classiche di rimozione: LRU37 e LFU38. L'operazione di accesso in lettura viene eseguita ad ogni nuova richiesta contenente un filtro proveniente dalla brokerlib. La cache, genererà la chiave nel modo sopra descritto ed effettuerà l'accesso nella hash. Nel caso in cui l'accesso abbia successo,

(41)

occorrerà scorrere il vettore associato alla chiave, valutando per ogni filtro la compatibilità dei suoi vincoli con quelli del filtro richiesto. Se verrà trovato un filtro compatibile avremo quello che si chiama cache hit (successo), mentre se non si riesce accedere alla hash o non viene trovato un filtro compatibile avremo un cache miss (fallimento), e si dovrà procedere ad eseguire il normale algoritmo di filtraggio.

I vantaggi temporali apportati dalla cache in caso di successo non dovranno essere vanificati da un costo eccessivo in caso di fallimento. In caso di cache miss, infatti, il costo computazionale dell'esecuzione dell'algoritmo di filtraggio andrà sommato con il costo di un accesso in cache fallito.

Il costo in caso di cache hit è dato dal costo pagato per l'accesso nalla hash, che è stimato essere costante O(1), sommato al costo pagato per la ricerca nel vettore di un filtro compatibile, stimato essere lineare O(n) in funzione del numero di filtri presenti nel vettore. Quindi sarebbe ragionevole che la dimensione massima del vettore fosse un ordine di grandezza inferiore rispetto al numero totale di risorse gestite dal broker.

4.7 API della BrokerLib

Un API39 indica un insieme di procedure disponibili al programmatore, di solito raggruppate a formare un set di strumenti specifici per un determinato compito. Un API È un metodo per ottenere un'astrazione tra il software a basso e quello ad alto livello, in pratica un insieme di funzioni che possono essere richiamate da un'applicazione per svolgere un determinato compito. L'implementazione della API che presentiamo è realizzata in Java e

(42)

consente di usufruire dei servizi offerti dal Broker System, quindi i già citati servizi di information gathering e advance reservation. Qui di seguito daremo una breve panoramica delle classi e dei metodi di maggiore interesse, senza lo scopo di dettagliare un reference per il programmatore. Infatti spesso verranno omessi alcuni dettagli della API e in alcuni casi varrà usata una sintassi Java impropria.

Le principali funzionalità fornite dalla libreria possono essere utilizzate istanziando la classe ResourceBroker presente nel package

broker.brokerLib. I metodi messi a disposizione dell'oggetto ResourceBroker per stabilire una sessione con i vari Broker sono i seguenti:

• void initialize(String filename)

Utilizzato per indicare gli indirizzi e le porte dei broker da contattare per mezzo di un file in formato XML.

• void addBroker(InetSocketAddress brokerAdress)

Utilizzato per aggiungere l'indirizzo e la porta di nuovo Broker da aggiungere alla sessione.

• void startSession()

Apre una nuova sessione connettendosi a tutti i Broker specificati con il metodo precedentemente.

• void stopSession()

Chiude la sessione corrente. • void shutdown()

Rimuove tutte le strutture dati create nella fase di inizializzazione della libreria e chiude tutte le connessioni ai Broker.

(43)

sessioni sequenzialmente, ma non sarà possibile annidarle, il tentativo di annidamento solleverà una eccezione. Una volta aperta una sessione è possibile inizializzare uno o più filtri e richiederne la valutazione. Il package contenente l'oggetto Filter da istanziare è broker.filter, qui di seguito sono riportati i costruttori disponibili:

• Filter(ResourceType resourceType)

• Filter(ResourceType resourceType, Constraint constraint)

• Filter(ResourceType resourceType, ReservationConstraint

baseReservationConstraint)

• Filter(ResourceType resourceType, ReservationConstraint

baseReservationConstraint,Constraint constraint)

Quando si istanzia un oggetto di tipo Filter è necessario specificare il tipo di risorsa a cui vanno applicati i vincoli. Il tipo deve essere specificato mediante un'apposita classe che dovrà essere presente all'interno del package che contiene la descrizione della risorsa. Per esempio per le risorse computazionali esiste il package broker.resource.computational contenente la classe ComputationalResourceType. Di seguito sono elencati i metodi messi a disposizione dalla classe Filter per impostare i constraint:

• boolean set(Constraint constraint)

• boolean set(String attribute, Value value, byte boolOp)

• boolean set(String attribute, String metric, String value, String type,

byte boolOp)

(44)

Un vincolo è composto dalla terna (attributo, valore,

opertaoreRelazionale), in cui il secondo elemento è a sua volta espandibile

in una terna (metrica, valore, tipo). Queste due terne possono essere specificate per mezzo di due classi, rispettivamente Constraint e Value. Di seguito riportiamo alcuni dei loro costruttori:

• Constraint(String attribute, Value value, byte boolOp)

• Constraint(String attribute, String value, byte boolOp)

• Value(String metric, String value, String type)

Questi costruttori combinati ai vari overload del metodo set forniscono un'ampia gamma di possibilità per specificare un vincolo. Da notare, in particolare, la possibilità di specificare un vincolo senza dichiarare il tipo del valore associato all'attributo, ma usando una semplice stringa. Il seguente frammento di codice illustra tale tecnica:

filter.set( new Constraint( “clockSpeed”, “1800”, EQUAL ))

Per mezzo del metodo set quindi sarà possibile specificare un numero qualsiasi di Constraint, in una qualsiasi successione.

Una funzionalità importante messa a disposizione dal filtro è la capacità di ordinare l'insieme delle risorse che verranno selezionate per mezzo dei vincoli specificati. Tale funzionalità può essere attivata per mezzo del metodo mustOrder(). Il criterio di ordinamento sarà in funzione degli attributi specificati nei vincoli, per esempio una risorsa computazionale potrà essere ordinata in prima battuta in base alla velocità del clock e in seguito secondo la dimensione della memoria e così via. Il criterio di

(45)

ordinamento può essere deciso con un meccanismo implicito oppure con uno esplicito. Il metodo implicito si base sull'ordine in cui vengono assegnati i Constraint nel filtro. Il metodo esplicito invece consiste nell'uso di una esplicita funzione in cui verranno elencati ordinatamente gli attributi da utilizzare. Qui di seguito è presentato un frammento di codice che fa uso del meccanismo implicito:

Filter f = new Filter( new ComputationalResourceType() );

f.set( new Constrint(“clockSpeed”, “2000”, GREATER ) ); f.set( new Constrint(“size”, “128”, EQUAL, NOT_ORD ) ); f.set( new Constrint(“capacity”, “10”, GREATER ) ); f.mustOrder();

Il frammento di codice mostra come istanziare un filtro per selezionare risorse di tipo computazionale che presentino determinate caratteristiche di processore, memoria e disco. Inoltre, si specifica che l'insieme di risorse restituite mediante l'iteratore dovrà essere ordinato secondo i valori degli attributi clockSpeed e capacity rispettivamente. Praticamente un attributo è sempre considerato ordinante, a meno che non si specifichi il contrario per mezzo del flag NOT_ORD nel costruttore del Constraint.

Oltre ai vincoli sulle caratteristiche delle risorse, la classe filter permette di specificare i vincoli sulle prenotazioni, al fine di fornire le informazioni necessarie ad eseguire lo Admission Control. Il metodo predisposto a questo scopo è il seguente:

(46)

Le informazioni necessarie per creare un ReservationConstraint sono: il nome della parte prenotabile (Reservable) della risorsa identificata per mezzo di una stringa (type), lo slot temporale di durata della prenotazione (TimeSlot), una priorità (priority) ed infine una percentuale di utilizzo (rate). La classe ReservationConstraint è astratta, questo permette di avere una maggiore flessibilità e diverse alternative al fine di calcolare il corretto valore del rate. La prima alternativa consiste nell'uso della classe

GenericReservationConstraint, che estende la classe ReservationConstraint, nel cui costruttore andrà specificato il nome della

parte di risorsa Reservable a cui ci si riferisce, il timeslot, la priority ed il valore del rate ricavato in qualche modo dall'utente della libreria. Questa modalità lascia totale libertà sulla tecnica scelta per il calcolo del rate. La seconda alternativa invece propone l'uso di classi specifiche associate ad ogni parte Reservable delle risorse. Tali classi dovranno estendere

ReservationConstraint e di conseguenza dovranno implementare un metodo

per il calcolo del rate. Per ognuna di esse sarà necessario specificare il valore di un particolare attributo inerente, in maniera diretta o indiretta, alla performance della parte di risorsa da prenotare, il quale verrà utilizzato per calcolare il rate. Queste classi dovranno essere fornite all'interno dei package che descrivono le risorse e avranno una interfaccia ben definita. Nel caso di risorse computazionali è presente una classe per ognuna delle sue parti prenotabili, una per la cpu, una per la memoria e una per il disco, ognuna istanziabile impostando l'attributo specifico:

• ProcessorResrvConstr(TimeSlot timeSlot, byte priority,float

servicetime)

(47)

• DiskResrvConstr(TimeSlot timeSlot, byte priority, float size)

Sono disponibile anche dei costruttori in cui il valore dell'attributo specifico è esprimibile tramite la classe Value, in modo tale che sia possibile descrivere la metrica che si vuole usare. Il seguente frammento di codice ne illustra l'utilizzo nel caso si volessero prenotare uno spazio disco da dieci mega per sei ore :

f.setReservationConstraint( new DiskResrvConstr( new

TimeSlot(“8/1/2005 13:30:00”,“/1/2005 19:30:00”), 5, new Value(“Mbyte”,”10”,”real”) ) );

Nel caso in cui non venga specificato esplicitamente nessun vincolo di prenotazione il filtro ne userà uno preimpostato di base, il quale verrà assegnato ad ogni parte Reservable della risorsa specificata. Il vincolo preimpostato è implementato dalla classe BaseReservationConstraint, ed è settato con i seguenti valori: Timeslot(NOW,UNDIFINED) indicante uno slot temporale che ha inizio istantaneamente e una lunghezza indefinita,

Priority(MIN) indicante la priorità minore possibile e il rate massimo

(100%).

Dopo aver creato un filtro con le caratteristiche desiderate, è possibile istanziare un iteratore per acquisire le informazioni sulle risorse ed eventualmente prenotarle. I metodi da usare sono sempre contenuti nella classe ResourceBroker e sono:

• void resourcesGather(int where)