課程名稱︰系統效能評估
課程性質︰選修
課程教師︰周承復
開課學院：電資學院
開課系所︰資工所、網媒所
考試日期（年月日）︰2008.11.19
考試時限（分鐘）：150
試題 :
Mid-term Exam 2008 2008/11/19
(150 min)
1. (15%) Consider the following program segment consisting of the while loop:
while (B) S;
Let X_i denote the execution time for the ith iteration of statement
group S. Assume that the sequence of tests of the Boolean expression B
defines a sequence of Bernoulli trials with parameter p. Clearly, the
number N of iterations of the loop is a geometric random variable with
parameter p so that E[N] = 1/p. Letting T denote the total execution time
of the loop, and assuming that the X_i's are exponentially distributed
with parameter λ. Find the variance of execution time T.
2. (15%) Poisson process:
Def. A: the counting process {N(t), t ≧ 0} is said to be Poisson process
having rate λ, λ > 0 if
(a) N(0) = 0.
(b) The process has independent-increments.
(c) Number of events in any interval of length t is Poisson dist.
with mean λt, that is for all s, t ≧ 0.
-λt (λt)^n
P[N(t+s) - N(s) = n] = e ─────
n!
n = 0, 1, 2, ...
Def. B: The counting process {N(t), t ≧ 0} is said to be a Poisson process
with rate λ, λ > 0, if
(a) N(0) = 0.
(b) The process has stationary and independent increments.
(c) P[N(h) = 1] = λh + o(h)
(d) P[N(h) ≧ 2] = o(h)
f(h)
The func. f is said to be o(h) if lim ─── = 0
h→0 h
Prove Def A => Def B (c) and (d)
3. (15%) Consider a single processor with an infinite waiting room. Customer
arrivals are assumed to be Poisson with rate λ and service times are
exponentially distributed with expectation 1/μ. Suppose that the processor
fails at rate γ and, when failed, all of the customers in the system are
assumed to be lost. The failed processor is fixed at an exponential rate
of α. Please
(a) draw the state transition diagram and
(b) find the probability that there are i customers in the system.
4. (15%) Assume that a Poisson process with mean arrival rate λ branches out
into n output paths as shown in Figure 1. We assume that the successive
selections of an output stream from a sequence of generalized Bernoulli
trials with p_k (1 ≦ k ≦ n) denoting the probability of the selection of
output stream k. Let {N(t) | t ≧ 0} be the input Poisson process, and let
{N_k(t) | t ≧ 0} for 1 ≦ k ≦ n denote the output processes. Given that
N(t) = m, compute P[N_1(t) = m_1, N_2(t) = m_2, ... , N_n(t) = m_n].
p_1
Poisson stream ┌────┐┌────→ λp_1 ╮
with rate λ │ ├┘ │
────────→│ ├─────→ λp_2 ├ n Poisson streams
│ │ ︰ p_2 │
│ ├┐ ︰ │
└────┘└────→ λp_n ╯
p_n
5. (10%) We wish to determine the maximum call rate that can be supported
by one telephone booth. Assume that the mean duration of a telephone
conversation is 3 min, and that no more than a 3-min (average) wait for
the phone may be tolerated; what is the largest amount of incoming traffic
that can be supported?
6. (15%) Let τ_1 and τ_2 be two exponentially distributed, independent
random variables with means 1/λ_1 and 1/λ_2.
(a) Show that the random variable min{τ_1 , τ_2} is exponentially
distributed with mean 1/(λ_1 + λ_2) and that
P{τ_1 < τ_2} = λ_1 / (λ_1 + λ_2).
(b) Use these facts to show that the M/M/1 queue can be described by a
continuous-time Markov chain with transition rates q_(n(n+1)) = λ,
q_((n+1)n) = μ, n = 0,1,…
7. (15%) Consider the M/M/1/m system which is the same as M/M/1 except that
there can be no more than m customers in the system and customers arriving
when the system is full are lost. Show that the steady-state occupancy
probabilities are given by
n
ρ (1-ρ)
P_n = ─────── , 0 ≦ n ≦ m
1 - ρ^(m+1)
8. (20%) In the M/G/1 system, show that
_
(a) P{the system is empty} = 1 - λX
(b) Average length of time between busy periods = 1/λ
_ _
(c) Average length of busy period = X / (1 - λX)
_
(d) Average number of customers served in a busy period = 1 / (1 - λX)