Modellazione delle Performance a Livello di Componenti

Modellazione

delle Performance a

Livello di Componenti

- Cenni di reti di code

- MVA per reti di code aperte, chiuse

Tipi di risorse in una rete di code

Load independent

Load dependent

S(n) R(n)

S(n) R(n)

S(n) R(n)

n

n

n

Reti di code aperte

DISK

TAPE

uscite

arrivi

CPU

DISK

M clienti CPU

Reti di code chiuse

Nomenclatura

K: numero di code

X0: throughput medio della rete. Nel caso di rete aperta in regime stazionario X₀ = 

Vi: numero medio di visite al servente i da parte di una

richiesta generica da quando viene generata all’istante in cui viene soddisfatta (esce dal sistema nel caso di rete aperta)

S_i: tempo medio di servizio di una richiesta del servente i

Wi: tempo medio di attesa in coda di una richiesta nella coda i Ri: tempo medio di risposta di una richiesta nella coda i.

R_i = S_i + W_i

Xi: throughput della coda i-esima Xi =X0 Vi

R’i: tempo medio di residenza di una richiesta generica nella coda i dall’istante in cui viene generata all’istante in cui viene soddisfatta (esce dal sistema nel caso di rete aperta)

R_’i =Vi Ri

D_i: la domanda di servizio che una richiesta effettua ad un servente di una coda i dall’istante in cui viene generata all’istante in cui viene soddisfatta (esce dal sistema nel caso di rete aperta)

Qi: tempo totale speso da una richiesta in attesa nella coda i dall’istante in cui viene generata all’istante in cui viene soddisfatta (esce dal sistema nel caso di rete aperta)

Qi =Vi Wi

---

R^’i =Vi Ri =Vi (Wi +Si) =Wi Vi + Si Vi = Qi +Di

---

R0: tempo medio di risposta ad una richiesta dell’intero sistema

R0 = ^k i=1 R’i

ni: numero medio di richieste alla coda i in attesa o che stanno ricevendo un servizio

N: numero medio di richieste nel sistema N = ^k i=1 ni

Trattazione Reti Aperte (Single Class)

Equazioni:

Arrival theorem (for open networks): il numero medio di richieste residenti in una coda i trovate da una richiesta entrante nella stessa coda (nai) è pari al numero medio di richieste nella coda i (ni) .

. Ri(n) = Si + Wi(n) = Si + ni  Si

Applicando la legge di Little (n_i = X_i R_i) e U_i = X_iS_i si ha:

. Ri = Si _

(1-Ui) Quindi:

. R’i = Vi Ri = Di _ (1-Ui) Inoltre:

. ni = Ui _ (1-Ui)

R_i = S_i (1 + n_i) = S_i + S_i X_i R_i R_i (1- U_i) = S_i

Dato che U_i = X_i S_i

Trattazione Reti Aperte (Single Class)

Calcolo del massimo  :

Ricordiamo che in una rete aperta la frequenza media di utenti che entrano nella rete viene fissata a priori; dato che per  troppo alto la rete diventerà instabile, siamo interessati al massimo valore di  che possiamo applicare alla rete.

Dato che:

. Ui = Xi Si =  Vi Si

vale la

.  = Ui / Di dato che Di = Vi Si

Sapendo che in condizioni di massimo utilizzo della coda i Ui sarà pari a 1, possiamo calcolare il massimo  che non destabilizza il sistema:

.   1 _

max_ki=1 D_i

Esempio DB Server

(Example 9.1)

10800 request per hour = X0

DCPU = 0,2 sec Service demand at CPU V_DISK1 = 5

VDISK2 = 3

SDISK1 = SDISK2 = 15 msec

DDISK1 = VDISK1 * SDISK1 = 5 * 15 msec = 75 msec Service demand at disk 1 DDISK2 = VDISK2 * SDISK2 = 3 * 15 msec = 45 msec Service demand at disk 2 .

Service Demand Law

UCPU = DCPU * X0 = 0,2 sec/req * 3 req/sec = 0,6 Utilization of the CPU UD1 = DDISK1 * X0 = = 0,225 Utilization of the disk 1

U_D2 = = 0,135 Utilization of the disk 1

R’CPU = DCPU / (1- UCPU ) = 0,5 sec Residence times R’D1 = DDISK1 / (1- UDISK1 ) = 0,097 sec

R’D2 = DDISK2 / (1- UDISK2 ) = 0,052 sec

CPU DISK1 DISK2

Total response time

R0 = R’CPU + R’D1 + R’D2 = 0,649 sec

Average number of requests at each queue nCPU = UCPU / (1- UCPU ) = 0,6 / (1-0,6) = 1,5

nDISK1 = = 0,29

nDISK2 = = 0,16

Total number of requests at the server N = nCPU + nDISK2 +nDISK2 = 1,95 requests

RMaximum arrival rate

 = 1 _ = 1 _ = 5 rich /sec

max^ki=1 Di max (0,2; 0,075; 0,045)

Trattazione Reti Aperte (Multiple Class)

r classi di utenti, k code Input parameters

Di,r , r

Equations

. Ui,r () = r Vi,r Si,r = r Di,r

. Ui () = ^Rr=1 Ui,r ()

. R^’i,r () = Di,r delaying resource Di,r / (1-Ui ()) queuing resource

. R0,r () = ^Ki=1 R^’i,r ()

. ni,r () = Ui,r () / (1-Ui ())

. ni, () = ^Rr=1 ni,r ()

Average residence time of class r request at resource i

Utilization

Average class r requests at resource i

Average class r request response time

Average number of requests at resource i

Esempio DB server

(example 9.2)

query – 5 tx per second (tps) 2 classi di richieste

update – 2 tx per second (tps)

Service demand x

Query Updates

• CPU 0,1 0,15

• DISK1 0,08 0,20

• DISK2 0,07 0,10

Utilizations (%)

CPU 50 30

Disk1 40 40

Disk 2 35 20

Residence times (sec)

CPU 0,50 0.75

Disk1 0,40 1,00

Trattazione Reti Chiuse

( Mean Value Analysis)

• Permette di calcolare gli indici prestazionali (tempo medio di risposta, throughput, lunghezza media della coda, ecc…) di una rete chiusa

• Metodo iterativo basato sulla considerazione che i risultati di una rete di code possano essere calcolati a partire dai risultati della stessa rete con una popolazione ridotta di un’unità.

• Utilizzabile anche per reti di code ibride Nomenclatura

. X₀: throughput medio della rete di code.

. V_i: numero medio di visite di una richiesta ad una coda i.

. Si: tempo medio di servizio di una richiesta del servente i.

. Ri: tempo medio di permanenza di una richiesta alla coda i.

. R_’i: tempo totale medio di permanenza di una richiesta alla coda i considerando tutte le sue visite alla coda. Pari a Vi Ri

. D_i: tempo totale medio di servizio di una richiesta alla coda i considerando tutte le sue visite alla coda . Pari a Vi Si

. R0: tempo medio di risposta della rete di code. Pari alla somma degli R’i

nia: numero medio di richieste che una richiesta trova al suo ingresso in coda.

Forced Flow Law

Data la nomenclatura vista sopra, abbiamo:

Mean Value Analysis (Single class)

Equazioni:

R_i(n) = S_i + W_i(n) = S_i + n_i^a(n) S_i = S_i (1+ n_i^a(n) )

Arrival Theorem: il numero medio di richieste (n_ia) residenti in una coda i che vengono trovate da una richiesta entrante nella coda stessa è pari al numero medio di richieste in tutta la coda i nel caso in cui nella rete di code vi siano n-1 richieste (n_i (n-1) cioè n meno quella che vuole il servizio sulla coda i-esima) In altri termini: n_i^a(n) = n_i(n-1)

Quindi: R_i = S_i(1+n_i(n-1)) e moltiplicando entrambi i membri per V_i

=> R’i = Di(1+ni(n-1))

Applicando la legge di Little a tutto il sistema “rete di code” (n=X0R0), abbiamo che:

=> X₀ = n / R₀(n) = n / ^Kr=1 R^’_i(n)

Applicando la legge di Little e la Forced Flaw Law:

=> ni(n) = Xi(n) Ri(n) = X0(n) Vi Ri(n) = X0(n) R’i(n)

Mean Value Analysis (Single class)

Riassumendo, le tre equazioni sono:

-> Residence Time equation R’i = Di[1+ni(n-1)]

-> Throughput equation X0 = n / Kr=1 R’i(n) -> Queue lenght equation

n_i(n) = X₀(n) R^’_i(n)

Procedimento iterativo:

1. Sappiamo che ni(n) = 0 per n=0; infatti se non ci sono messaggi nelle rete di code certamente non ci sono in ognuna delle singole code che la costituiscono.

2. Sapendo ni(0) si possono calcolare i vari R’i(1)

3. Sapendo gli R’i(1) si possono calcolare i vari ni(1) e X0(1) 4. Sapendo gli ni(1) si possono calcolare gli R’i(2)

5. Si continua finchè non si sono trovati gli n_i(n) R^’_i(n) e X₀(n) dove n è il numero di richieste che circolano all’interno della rete in considerazione.

Esempio DB Server

(example 9.3)

• Richieste da 50 clients

• Ogni richiesta necessita 5 letture di record da un disco

• Average read time di un record = 9 msec

• Ogni richiesta al DB necessita di 15 msec di CPU

DCPU = SCPU = 15 msec Service demand at CPU DDISK = SDISK * VDISK = 9 * 5 = 45 msec Service demand at the disk

Using MVA Equations

n = 0; Number of cuncurrent requests

R’CPU = 0; Residence time for CPU R’DISK = 0; Residence time for disk

R0 = 0; Average response time

X0 = 0; Throughput

nCPU = 0; Queue lenght at CPU

nDISK = 0 Queue lenght at disk

n = 1;

R’CPU = DCPU = 15 msec;

R’DISK = DDISK = 45 msec;

Reti Chiuse (Single Class) Bounds

Identificazione del collo di bottiglia (1/2)

Normalmente il throughput generato da una rete di code tenderà a saturare al crescere delle richieste all’interno del sistema; siamo

quindi interessati a individuare quale sia il componente all’interno del sistema (supposto che sia uno solo) che provoca la saturazione.

 Ricordando che nel caso di reti aperte:   1 _

maxki=1 Di

e sostituendo  con X0 (n): X0 (n)  1 _

maxki=1 Di

 Ricordando la Throughput Equation di MVA e tenendo presente che R’i  Di per tutte le code i, abbiamo:

X0 (n) = n  n _

Kr=1 R’i Kr=1 Di

Reti Chiuse (Single Class) Bounds

Identificazione del collo di bottiglia (2/2)

Combinando le due equazioni ottenute abbiamo:

-> X0 (n)  min n _ , 1 _

_Kr=1 Di maxki=1 Di

Quindi per n piccoli il throughput crescerà al più linearmente con n, dopo di che si appiattisce su un valore pari a 1/ maxki=1 Di

. X₀

n

Reti Chiuse (Single Class) Bounds

Tempi medi di risposta (1/2)

Quando il throughput raggiunge il suo massimo valore (cioè per n grande) il tempo medio di risposta corrisponde a:

R0 (n)  n _ max throughput

Quindi per grandi valori di n il tempo di risposta cresce linearmente con n:

-> R0 (n)  n max_ki=1 Di

Al contrario, per piccoli valori di n (n prossimo ad 1) il tempo medio di risposta sarà pari a .

-> R0 (n) = ^Kr=1 Di

dato che i tempi di attesa sono nulli.

Reti Chiuse (Single Class) Bounds

Tempi medi di risposta (2/2)

Potremo quindi stabilire un lower bound sul tempo medio di risposta pari a:

-> R0 (n) ^ max Kr=1 Di , maxki=1 Di

Esempio DB Server

(Example 9.4)

Nuovi scenari rispetto es.precedente:

• Aumento degli indici nel DB

• Disco 60% più veloce (average service time = 5,63 msec)

• CPU più veloce (service demand = 7,5 msec)

Scenario Service

demand D_CPU Service

demand D_DISK

 D_i 1/

maxD_i

Bootleneck

a 15 2,5 * 9 = 22,5 37,5 0,044 disk

b 15 5*5,63 = 28,15 43,15 0,036 disk

c 15/2 = 7,5 45 52,5 0,022 disk

a+b 15 2,55*5,63 = 14,08 29,08 0,067 CPU

a+c 15/2 = 7,5 2,5 * 9 = 22,5 30,0 0,044 disk

Mean Value Analysis (Multiple Class)

Denotati con:

. N: il vettore contenente il numero di richieste per ogni classe all’interno del sistema; N_r numero di richieste di classe r

. l_r : un vettore contenente 0 in ogni posizione diversa da r e 1 nella posizione r;

Le equazioni caratterizzanti il sistema sono:

-> Residence Time Equation for class r R’i,r(N)= Di,r[1+ni(N – 1r)]

-> Throughput equation for class r X0,r = Nr / Kr=1 R’i,r(N)

-> Queue lenght equation for class r ni,r(n) = X0,r(n) R^’i,r

Quando si usano molte classi, il calcolo della ni per un certo N richiede di calcolare tutte le ni,r; queste dipendenze

rendono spesso molto oneroso il calcolo della MVA;

Per questo si usa un metodo approssimato basato

sull’osservazione che il numero di richieste di una classe r presenti un una coda è proporzionale al numero di richieste di classe r nella rete di code. Da questo segue che:

ni,r ( N – lr) = Nr – 1

ni,r ( N ) Nr

E quindi la seguente equazione:

-> Approssimazione

ni,r ( N – lr) = Nr – 1 ni,r ( N )

Nr

Tuttavia questa approssimazione si basa sulla conoscenza di:

ni,r(N). Normalmente per risolvere questo problema si usa un metodo iterativo basato sull’utilizzare un valore ni,r(N)

approssimato, ricavare iterativamente n (N), e ripetere il

Mean Value Analysis

(Multiple Class)