Analisi approssimata di un modello a reti di code processor-sharing e multi-classe

Sommario
Nell’ambito della progettazione di architetture informatiche ` e necessa-
ria la valutazione delle prestazioni di un sistema utilizzando tecniche
di modellizzazione quantitativa. In particolare si considerano modelli
popolari comeleretidicodepervalutarediversiparametricheinfluen-
zano la qualit` a dei servizi.
Lo scopo della tesi ` e analizzare il tempo di risposta di un singolo
modello, valutando la qualit` a della risoluzione approssimativa che eli-
mina la complessit` a computazionale legata al calcolo esatto di questo
parametro.
Questa analisi viene estesa a modelli che presentano diversi livelli di
utenza e quindi diverse classi di richieste per un determinato servizio.
Inoltre viene proposta, attraverso diverse validazioni sperimentali,
l’ipotesichelasoluzioneapprossimatadicalcolodelResponseTimesia
un Upper-Buond della soluzione esatta.
I
Capitolo 1
Introduzione
1.1 Motivazioni e Obiettivi del lavoro
Oggiisistemidicomputer,inconseguenzaallororapidosviluppo,sono
sempre pi` u complessi e sempre pi` u essenziali sia per la comunicazione
circoscritta alle singole imprese che per quella estesa alla globalit` a de-
gli utenti. Il risultato di questa evidente crescita conduce al bisogno di
strumenti e tecniche che aiutano la comprensione del comportamento
e la progettazione di diversi sistemi.
Unodiquestistrumenti` el’astrazionedelsistemainquestioneattra-
verso un modello. Un generico modello considera esattamente alcuni
aspetti legati alla qualit` a del servizio e alle performance rispetto al-
l’insieme di dettagli presenti nel sistema. L’utilizzo di un modello per
l’analisi prestazionale di un sistema ` e meno laborioso e pi` u flessibile
rispetto la sperimentazione: ci` o ` e dettato dal fatto che evita specifiche
non necessarie alla valutazione e conduce a degli approcci puramente
metodici e analitici.
In particolare, si utilizzano dei modelli quantitativi chiamati reti di
code: essi permettono l’analisi di sistemi rappresentati da un insieme
di nodi che processano dei dati generici in arrivo (utenti o transazioni)
consentendo l’attesa nella coda di sistema nel caso in cui il centro di
servizio sia occupato per l’elaborazione di altri dati.
Questicasipossonorappresentarediversesituazionirealistichenell’am-
bito informatico (vedi [4]): basti pensare ai sistemi di attesa per l’e-
leborazione dei processi presenti su un singolo calcolatore oppure ai
sistemi di comunicazione e di trasmissione dei dati specifici basati sul
1.1. Motivazioni e Obiettivi del lavoro 2
protocollo e sulla politica di gestione store-and-forward (come esempio
si pu` o citare il paradigma richieste/risposte su un server HTTP oppure
l’inoltro di posta elettronica attraverso server SMTP).
Essendo generalmente attribuita a questi processi una distribuzione
esponenziale per l’arrivo-inoltro dei dati, si considera, per un singo-
lo modello, la tipologia denominata M/M/m con disciplina di servizio
Processor Sharing, assumendo la coda di capacit` a infinita. Tra i di-
versi parametri prestazionali ricavabili dal sistema, si vuole valutare il
tempocheunarichiestaimpiegaadessereprocessata,considerandoche
essa pu` o attendere l’esecuzione nella coda del sistema. Questo valore ` e
definito Tempo di Risposta o Response Time del modello M/M/m.
Dopo aver introdotto alcuni vincoli necessari alla corretta evoluzio-
ne del sistema, si procede con la risoluzione per il calcolo del Response
Time: gli strumenti matematici (generazione catena di Markov -vedi
[5]- e risoluzione del sistema lineare associato -vedi [8]-) permettono
una buona accuratezza nel calcolo, ma, a causa della loro complessit` a
computazionale, richiedono lunghi tempi di eleborazione e diverso spa-
zio di memorizzazione dei dati per assicurare un’alta precisione.
Proprio per la necessit` a avere una stima del Response Time da ap-
plicareallostudioprogettualediunsistemarealistico, spessononviene
applicato un calcolo molto complesso e dispendioso in termini di tem-
po e memoria, ma una formula relativamente semplice e generica per
questa tipologia di modelli.
Lo scopo diventa dunque il confronto tra queste diverse procedure
di calcolo, considerando la variazione dei parametri che caratterizzano
ungenericomodelloaretidicode: l’analisicomprende, inprimoluogo,
la comparazione per modelli a Classe Singola e successivamente, i mo-
delli M/M/m Multi-Class e la dipendenza dei risultati dal carico delle
classi presenti.
In particolare, vengono osservati i modelli a 2-Classi e a 3-Classi di
utenza che risultano facilmente estendibili in futuro per quanto riguar-
da la previsione del comportamento di un generico modello a k-Classi
di utenza, ma difficilmente osservabili a livello di valutazione esatta
del Response Time: la complessit` a cresce notevolmente all’aumentare
del numero di classi considerate, implicando dunque una capacit` a di
elaborazione e memorizzazione elevata.
Il carico delle classi presenti in un modello, incide anche sull’ap-
prossimazione del Response Time proposta, confermando alcune teorie
1.2. Struttura della tesi 3
attuali sul Load-Balancing (vedi [9],[18]) e lasciando dei possibili svi-
luppi sul miglioramento della formulazione per particolari parametri
del sistema.
Lo studio dei modelli a reti di code, in generale, tiene conto di me-
triche prestazionali che risultano difficili da ricavare sperimentalmente:
le risoluzioni analitiche solitamente si esprimono in funzione della ve-
locit` a di arrivo e di servizio delle richieste presso il sistema. Il valore
che pu` o essere ricavato per questi, attraverso sistemi di conteggio delle
frequenze transazionali, ` e sempre sensibile ad un errore molto pi` u alto
rispetto all’osservazione dell’utilizzo del centro di servizio o dell’inten-
sit` a di traffico totale per il sistema: si tiene conto, dunque, principal-
mente della variazione di questi parametri.
E’ importante stabilire, se esiste, una relazione tra i due approc-
ci: la stima pu` o essere presa in considerazione solamente per alcuni
intervalli di esistenza dei parametri oppure avere un comportamento
particolarerispettoalcalcoloesatto. Attraversolediverserappresenta-
zioni ricavate sperimentalmente si verifica la relazione di Upper-Bound
per i modelli a classe singola, estendendo l’ipotesi anche per i modelli
M/M/m a classe multipla sulla base dei dati ottenuti.
Nella progettazione di diversi impianti informatici, sia estesi che
limitati a pochi calcolatori, si ritiene utile avere una approssimazione
immediatadeltempoincuiilsistema` eingradodiprocessareunaqual-
siasirichiestachearrivadall’esternoedinmodoparticolare,stabilirese
questorisultaunvaloreottimistico. Infatti,questopresuppostopotreb-
be semplificare la risoluzione della creazione di un sistema, considerato
nella sua globalit` a, dato che tutti i componenti necessari avranno sicu-
ramente un comportamento migliore, in termini di prestazioni, di ci` o
che ` e stato stimato in precedenza.
1.2 Struttura della tesi
La tesi ` e strutturata nel modo seguente.
Nel capitolo due di questo elaborato si mostra lo stato dell’arte at-
tuale dei modelli utilizzati per l’analisi del Response Time: vengono
illustrati diversi approcci utilizzati di analisi per i modelli M/M/m, la
disciplina di servizio Processor Sharing e la dipendenza del bilancia-
mento di carico da parte delle classi di richieste presenti.
1.2. Struttura della tesi 4
Nel capitolo tre viene esposta l’analisi teorica per valutare le so-
luzioni del Response Time: dopo una breve introduzione dei concetti
necessari a chiarire le assunzioni e i vincoli dei modelli utilizzati, viene
esposto il procedimento che porta al calcolo esatto del Response Time.
In seguito viene illustrato un approccio esistente che stima il valore del
Response Time, eliminando totalmente la complessit` a che richiede il
calcolo esatto.
In particolare, viene mostrata la semplificazione di calcolo del Respon-
se Time per il modello M/M/m a Classe Singola.
Nel capitolo quattro si descrive la validazione sperimentale svolta
per il confronto dei due differenti approcci. Si mostrano, in primo luo-
go, i limiti che sono necessariamente introdotti dal calcolo di questo
parametro.
Dopo queste premesse, viene valutato l’errore commesso nell’utilizzo
della stima proposta: i casi analizzati considerano il modello M/M/m
con un unica classe di richieste, 2-Classi di richieste e 3-Classi di richie-
ste, differenziando in base al bilanciamento-sbilanciamento del carico
da parte delle classi stesse.
Nel capitolo cinque, dopo l’iniziale verifica sperimentale della rela-
zione di Upper-Bound tra i due metodi di calcolo del Response Time
per il modello M/M/m a Classe Singola, viene illustrata l’ipotesi di
Upper-Bound, basata comunque sui dati empirici ricavati, per i model-
li con diverse classi di richieste (si prendono come riferimenti sempre i
modelli a 2-Classi e a 3-Classi di richieste).
Infine, il capitolo sei riassume le conclusioni sul lavoro svolto, valu-
tando i risultati ottenuti e proponendo diverse prospettive future.