Performance Evaluation of Computer Systems and Networks, 02/07/2015
Exercise 1
A university exam consists in four distinct subjects, called a, b, c, d for simplicity. Students get to
pass the exam if they prove to be knowledgeable in at least one between (a and b) and (c and d).
Every other combination of subjects (e.g., a and c) leads to failing the exam. Call px the probability
that a student is knowledgeable in subject x, and let px , p y be independent when x ≠ y .
1) Model the above situation using switches, and compute the probability Psuccess that a student
passes the exam.
2) Assume that a student tries her luck by repeating the exam over and over until she passes it.
Express the probability that it takes n attempts to pass the exam. Assume that each attempt is
independent of the previous ones.
The university decides that students that fail an exam accumulate a penalty of k points to that
exam’s grade (per failure).
3) Assume that the exam grade depends only on the number of failures, and it is equal to 100 at
the first attempt. Compute the average grade as a function of k and Psuccess .
4) Assume that the university requires that the average grade be equal to a given value G.
Compute the required value of the penalty k as a function of Psuccess to achieve that objective
and draw a qualitative diagram of k as a function of Psuccess and G.
Esercizio 1
Un esame universitario consiste di quattro argomenti, chiamati a, b, c, d per semplicità. Gli studenti
passano l’esame se riescono a dimostrare preparazione in almeno uno tra (a and b) e (c and d), ed in
nessun altro caso (e.g., a and c). Si chiami px la probabilità che uno studente sia preparato
sull’argomento x, e siano px , p y indipendenti se x ≠ y .
1) Modellare il problema sopra indicato usando interruttori, e calcolare la probabilità Psuccess che
uno studente passi l’esame.
2) Si assuma che uno studente tenta la fortuna ripetendo l’esame finché non lo passa.
Esprimere la probabilità che ci vogliano n tentativi per passare l’esame. Si assuma che ogni
tentativo sia indipendente dai precedenti.
L’università decide che gli studenti che falliscono un esame accumulano una penalità al voto di
quell’esame pari a k punti per fallimento.
3) Si assuma che il voto d’esame dipenda solo dal numero di tentativi, e che sia uguale a 100 al
primo tentativo. Calcolare il voto medio in funzione di k e Psuccess .
4) Si assuma che l’università richiede che il voto medio sia pari ad un dato valore G. Calcolare
il valore richiesto della penalità k in funzione di Psuccess in modo da raggiungere questo
obiettivo. Disegnare un diagramma qualitativo di k in funzione di Psuccess e G.
Performance Evaluation of Computer Systems and Networks, 02/07/2015
Exercise 2
A car repair service company has n repair bays, and expects customers’ cars to come in for repair
with exponentially distributed interarrivals, at a rate λ . The repair of a car takes an exponentially
distributed time with a mean of 1 µ . The company wants to man the smallest possible number of
repair bays (so as to save money), but knows that its customers find it unacceptable to have to wait.
1) Model the above system as a birth-death process and draw the transition diagram
2) Compute the steady-state probabilities. Express the stability condition
3) Compute the probability Pwait that a car that breaks has to wait before entering a repair bay
4) Assume λ = µ . Compute Pwait as a function of n and study its behavior with n.
5) Under the above hypothesis, state whether 6 manned repair bays are enough to have Pwait
smaller than 5 ⋅10−4 .
n
It may be useful to observe that nlim
∑
→∞
j =0
 n xj 
1
= lim  ∑  =  e x  = e , and that
x =1
j ! n →∞  j = 0 j !  x =1
n
1
∑ j ! ≈ e when
n≥5.
j =0
Esercizio 2
Un’officina di riparazione auto ha n banchi di riparazione, e si aspetta che le auto dei client vengano
portate a riparare con interarrivi esponenziali ad un tasso λ . La riparazione di un’auto richiede un
tempo distribuito esponenzialmente con media 1 µ . L’officina vuole tenere aperto il minimo
numero possibile di banchi di riparazione (per risparmiare denaro), ma sa che i suoi clienti trovano
inaccettabile dover aspettare.
1) Modellare il sistema come un processo di nascita-morte e disegnare il diagramma delle
transizioni.
2) Calcolare le probabilità stazionarie di stato. Esprimere la condizione di stabilità.
3) Calcolare la probabilità Pwait che una macchina che si rompe debba attendere prima di entrare
in riparazione
4) Si assuma λ = µ . Calcolare Pwait in funzione di n e studiare il suo andamento.
5) Nell’ipotesi precedente, stabilire se 6 banchi di riparazione aperti sono abbastanza da
rendere Pwait inferiore a 5 ⋅10−4 .
n
Può essere utile osservare che nlim
∑
→∞
j =0
 n xj 
1
= lim  ∑  =  e x  = e , e che
x =1
j ! n →∞  j = 0 j !  x =1
n
1
∑ j ! ≈ e quando
j =0
n≥5.
Performance Evaluation of Computer Systems and Networks, 02/07/2015
Exercise 1 – Solution
1) The model is the following:
The probability to pass the exam is the same as the one that current flows in the above
circuit, i.e. that the upper and/or lower branches are functioning, each switch being closed
with probability px . By independence, current flows through the upper (lower) branch with
probability pa ⋅ pb ( pc ⋅ pd ), hence:
Psuccess = 1 − (1 − pa ⋅ pb ) ⋅ (1 − pc ⋅ pd ) 
= 1 − [1 − pa ⋅ pb − pc ⋅ pd + pa ⋅ pb ⋅ pc ⋅ pd ]
= pa ⋅ pb + pc ⋅ pd − pa ⋅ pb ⋅ pc ⋅ pd
2) The probability distribution is clearly a geometric one, with a success ratio equal to Psuccess .
Thus, pn = (1 − Psuccess ) ⋅ Psuccess
n −1
3) The average grade is the following:
∞
G = ∑ (100 − ( n − 1) ⋅ k ) ⋅ Pn
n =1
∞
= ∑ (100 − ( n − 1) ⋅ k ) ⋅ (1 − Psuccess )
n −1
⋅ Psuccess
n =1
= 100 − k ⋅
1 − Psuccess
Psuccess
4) From the above we have:
k = (100 − G ) ⋅
Psuccess
1 − Psuccess
k
500
450
400
350
300
250
G
200
150
100
50
0
0
0.2
0.4
0.6
0.8
Psuccess
1
Performance Evaluation of Computer Systems and Networks, 02/07/2015
Exercise 2 - Solution
1) The system is an M/M/n one, hence the diagram is the following:
2) We know from the theory that the system is stable if ρ = λ ( n ⋅ µ ) < 1 . This should also
emerge from the computation of the steady-state probabilities. The global equilibrium
equations are the following:
P0 ⋅ λ = P1 ⋅ µ
P1 ⋅ λ = P2 ⋅ 2µ
...
Pn −1 ⋅ λ = Pn ⋅ n ⋅ µ
Pn ⋅ λ = Pn +1 ⋅ n ⋅ µ
...
Pn + j ⋅ λ = Pn + j +1 ⋅ n ⋅ µ
j≥0
From which we get:
 λ  j 1
  ⋅ ⋅ P0
 µ
j!
Pj =  
 j nn
 ρ ⋅ n ! ⋅ P0

j<n
j≥n
Hence, the normalization condition is:
 n −1  λ  j 1  n n ∞

P0 ⋅ ∑   ⋅  + ⋅ ∑ ρ n  = 1
 j = 0  µ  j ! n ! j = n 
The infinite sum converges if and only if ρ < 1 , as expected. This said,
n −1
 n −1  λ  j 1  n n  ∞
 
P0 ⋅ ∑   ⋅  + ⋅  ∑ ρ n − ∑ ρ n   = 1
µ
j ! n !  j = 0
j =0
 
 j =0  
 n −1  λ  j 1  1 ( n ⋅ ρ )n 
P0 ⋅ ∑   ⋅  + ⋅
 =1
µ
j ! n ! 1 − ρ 
 j =0  

 n −1  λ  j 1  1 ( n ⋅ ρ )n 
P0 = ∑   ⋅  + ⋅

µ
j ! n ! 1 − ρ 
 j = 0  

.
−1
1
If n is large, the following approximation is reasonable: P0 =
eλ µ +
1 (n ⋅ ρ )
⋅
n! 1 − ρ
n
3) Since the system enjoys the PASTA property, the probability that a car that breaks has to
wait before entering service is the probability that j ≥ n customers are in the system, i.e.
∞
∞
∑ r = ∑ P . This can be written as:
j
j=n
j
j=n
Performance Evaluation of Computer Systems and Networks, 02/07/2015
(n ⋅ ρ )
n !(1 − ρ )
n
∞
j =n
∞
(n ⋅ ρ )
nn
⋅ P0 ⋅ ∑ ρ j =
⋅ P0 =
n!
n !(1 − ρ )
j =n
n
Pwait = ∑ Pj =
 λ  j 1  ( n ⋅ ρ ) n

∑
  ⋅ +
j ! n !(1 − ρ )
j = 0  µ 

n −1
.
Again, if n is large, the following approximation is reasonable:
Pwait ≈
1
n !(1 − ρ ) ⋅ eλ µ
(n ⋅ ρ )
n
+1
4) Note that λ = µ implies n > 1 , otherwise the system is unstable. When λ = µ , we get:
n
Pwait =
 1
n⋅ 
 n
 1
n ! 1 − 
 n
n
 1
n⋅
n −1
 1   n 
+
∑
 
 1
j = 0  j !
n ! 1 − 
 n
=
1
1
( n − 1)!( n − 1) ⋅ ∑   + 1
j = 0  j !
n −1
.
The above statement is confirmed by the fact that ( n − 1) appears in the denominator.
Pwait is obviously decreasing with n (since the denominator increases with n). Moreover,
Pwait ( n ) ≥
1
( n − 1)!( n − 1) ⋅ e + 1
, with Pwait ( n ) ≈
1
( n − 1)!( n − 1) ⋅ e + 1
when n ≥ 5 . The first few values
are reported in the table:
n
Pwait
expr.
2
3
4
5
5) When n = 6 , it is Pwait ( n ) ≈
answer is no.
1
.
600 ⋅ e + 1
13
1 11
1 49
1 261
Numerical
value
0.333333
0.090909
0.020408
0.003831
Since e < 3 , it is Pwait ( n ) >
1
1
>
= 5 ⋅10−4 ,
1800 2000
so the