Modellazione
delle Performance
a
Livello di Componenti
- Cenni di reti di code
- MVA per reti di code aperte, chiuse
1
Tipi di risorse in una rete di code
S(n)
R(n)
n
Load independent
S(n)
R(n)
n
Load dependent
S(n)
R(n)
n
Delay
2
Reti di code aperte
uscite
arrivi
DISK
CPU
TAPE
Reti di code chiuse
DISK
M clienti
CPU
TAPE
3
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
4
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
5
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 (ni = Xi Ri) e Ui = XiSi si
ha:
. Ri =
Ri = Si (1 + ni) = Si + Si Xi Ri
Si _
(1-Ui)
Ri (1- Ui) = Si
Quindi:
. R’i = Vi Ri =
Di _
(1-Ui)
Inoltre:
. ni =
Ui _
(1-Ui)
Dato che Ui = Xi Si
6
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
7
Esempio DB Server
(Example 9.1)
CPU
DISK1
DISK2
10800 request per hour = X0
DCPU = 0,2 sec Service demand at CPU
VDISK1 = 5
VDISK2 = 3
SDISK1 = SDISK2 = 15 msec
DDISK1 = VDISK1 * SDISK1 = 5 * 15 msec = 75 msec
DDISK2 = VDISK2 * SDISK2 = 3 * 15 msec = 45 msec
.
Service Demand Law
UCPU = DCPU * X0 = 0,2 sec/req * 3 req/sec = 0,6
UD1 = DDISK1 * X0 =
= 0,225
UD2 =
= 0,135
Service demand at disk 1
Service demand at disk 2
R’CPU = DCPU / (1- UCPU ) = 0,5 sec
R’D1 = DDISK1 / (1- UDISK1 ) = 0,097 sec
R’D2 = DDISK2 / (1- UDISK2 ) = 0,052 sec
Residence times
Utilization of the CPU
Utilization of the disk 1
Utilization of the disk 1
8
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)
nDISK1 =
nDISK2 =
= 1,5
= 0,29
= 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)
9
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 ()
Utilization
Average residence
time of class r request
at resource i
Average class r request
response time
Average class r requests at
resource i
Average number of requests
at resource i
10
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
CPU
0,50
0.75
Disk1
0,40
1,00
Disk 2
0,016
0,22
Response times (sec)
1,06
1,97
Residence times (sec)
11
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 Law
Data la nomenclatura vista sopra, abbiamo:
. Xi = X0 Vi
12
Mean Value Analysis
(Single class)
Equazioni:
Ri(n) = Si + Wi(n) = Si + nia(n) Si = Si (1+ nia(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)
13
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.
14
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
DDISK = SDISK * VDISK = 9 * 5 = 45 msec
Service demand at CPU
Service demand at the disk
Using MVA Equations
n = 0;
R’CPU = 0;
R’DISK = 0;
R0 = 0;
X0 = 0;
nCPU = 0;
nDISK = 0
Number of cuncurrent requests
Residence time for CPU
Residence time for disk
Average response time
Throughput
Queue lenght at CPU
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/msec
nCPU = X0 * R’CPU = 0,250
nDISK = 0,750
15
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
Kr=1 R’i

n
_
Kr=1 Di
16
Reti Chiuse (Single Class)
Bounds
Identificazione del collo di bottiglia (2/2)
Combinando le due equazioni ottenute abbiamo:
-> X0 (n)  min
n
_,
Kr=1 Di
1
_
k
max 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
17
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.
18
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
19
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/
Bootleneck
maxDi
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
20
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 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
-> Queue equation
ni(N)= Rr=1 ni,r(N)
21
Mean Value Analysis
(Multiple Class)
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.
22