1

Modellazione delle Performance

a Livello di Componenti

- Cenni di reti di code

- MVA per reti di code aperte, chiuse

2

Tipi di risorse in una rete di code

Load independent

Load dependent

Delay

S(n)R(n)

S(n)R(n)

S(n)R(n)

n

n

n

3

Reti di code aperte

DISK

TAPE

uscite

arrivi

CPU

DISK

TAPE

CPUM clienti

Reti di code chiuse

4

Nomenclatura

K: numero di code

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

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)

Si: 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.

Ri = Si + Wi

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

Di: 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)

Di = Vi Si

5

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

6

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 (na

i) è pari al numero medio di richieste nella coda i (ni) .

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

Applicando la legge di Little (ni = Xi Ri) e Ui = XiSi si ha:

. Ri = Si _

(1-Ui)

Quindi:

. R’i = Vi Ri = Di _

(1-Ui)Inoltre:

. ni = Ui _

(1-Ui)

Ri = Si (1 + ni) = Si + Si Xi Ri

Ri (1- Ui) = Si

Dato che Ui = Xi Si

7

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 _

maxki=1 Di

8

Esempio DB Server(Example 9.1)

10800 request per hour = X0

DCPU = 0,2 sec Service demand at CPU

VDISK1 = 5VDISK2 = 3SDISK1 = 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

UD2 = = 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

9

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

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

10

Trattazione Reti Aperte (Multiple Class)

r classi di utenti, k code

Input parametersDi,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

11

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

Disk 2 0,016 0,22

Response times (sec) 1,06 1,97

12

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

. X0: throughput medio della rete di code.

. Vi: 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

. Di: 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 LawData la nomenclatura vista sopra, abbiamo:

. Xi = X0 Vi

13

Mean Value Analysis (Single class)

Equazioni:

Ri(n) = Si + Wi(n) = Si + nia(n) Si = Si (1+ ni

a(n) )

Arrival Theorem: il numero medio di richieste (nia) 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 (ni

(n-1) cioè n meno quella che vuole il servizio sulla coda i-esima)

In altri termini: nia(n) = ni

(n-1)

Quindi: Ri = Si(1+ni(n-1))

e moltiplicando entrambi i membri per Vi

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

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

=> X0 = n / R0(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)

14

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

ni(n) = X0(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 ni(n) R’i(n) e X0(n)

dove n è il numero di richieste che circolano all’interno della rete in considerazione.

15

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 CPUDDISK = SDISK * VDISK = 9 * 5 = 45 msec Service demand at the disk

Using MVA Equations

n = 0; Number of cuncurrent requestsR’CPU = 0; Residence time for CPUR’DISK = 0; Residence time for diskR0 = 0; Average response timeX0 = 0; ThroughputnCPU = 0; Queue lenght at CPUnDISK = 0 Queue lenght at disk

n = 1; R’CPU = DCPU = 15 msec;

R’DISK = DDISK = 45 msec; R0 = DCPU + DDISK = 60 msec;

X0 = n/ R0 = 0,0167 tx/msecnCPU = X0 * R’CPU = 0,250nDISK = 0,750

16

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

17

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 maxk

i=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

.

X0

n

18

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 maxki=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.

19

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 , maxk

i=1 Di

20

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 DCPU

Service

demand DDISK

Di 1/

maxDi

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

21

Mean Value Analysis (Multiple Class)

Denotati con:

. N: il vettore contenente il numero di richieste per ogni classe all’interno del sistema; Nr numero di richieste di classe r. lr : 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 rR’

i,r(N)= Di,r[1+ni(N – 1r)]

-> Throughput equation for class rX0,r = Nr / K

r=1 R’i,r(N)

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

i,r

-> Queue equation ni(N)= R

r=1 ni,r(N)

22

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 ni,r(N), e ripetere il procedimento finché la differenza fra i due valori non scende al di sotto di una soglia di errore precedentemente stabilita.

Mean Value Analysis (Multiple Class)