課程名稱︰系統效能評估
課程性質︰選修
課程教師︰周承復
開課學院：電資學院
開課系所︰資工所、網媒所
考試日期（年月日）︰2007.11.07
考試時限（分鐘）：100
試題 :
Mid-term Exam 2007 2007/11/7
(100 min)
1. Let 12 f_n - 11 f_(n-1) + 2 f_(n-2) = (1/2)^n, n=2,3,4,…. And f_0 = 0,
f_1 = 4. Please find out fn, n=0,1,2,….
2. 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.
3. Proof the following properties of Poisson process.
(a) The superposition of two independent Poisson process with rate λ_1 and
λ_2 is a Poisson process with rate λ_1 + λ_2.
(b) If we perform Bernoulli trials to make independent random erasures from
a Poisson process, the remaining arrivals also form a Poisson process.
4. Please prove that for an exponential distribution, it has Markov property or
it is memoryless.
5. Consider a single-server queue with Poisson arrivals exponential service
time having the following variation: Whenever a service is completed, a
departure occurs only with probability α. With the probability 1-α, the
customer, instead of leaving, joins the end of the queue. Note that a
customer may be serviced more than once.
(a) Set up the balance equations and solve for the steady-state
probabilities, stating conditions for it to exist.
(b) Find the expected waiting time of a customer from the time he arrives
until he enters service for the first time.
(c) What is the probability that a customer enters service exactly n times,
for n = 1,2,…?
6. 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 repair time of the failed processor is exponentially
distributed with parameter δ.
(a) Draw the state transition diagram.
(b) Find the probability that there are i customers in the system.
7. Derive the stationary distribution of an M/M/2 system where the two servers
have different service rates μ_l and μ_h respectively. The arrival process
is Poisson arrival with rate λ. A customer that arrives when the system
empty is routed to the faster server, i.e., the server with service
rate μ_h.
8. Consider the failures of a link in a communication network. Failures occur
according to a Poisson process with rate 7.2 per day. Find
(i) P[time between failures ≦ 15 days]
(ii) P[10 failures in 20 days]
(iii) Expected time between two consecutive failures.
(iv) P[0 failures in next day]
(v) Suppose 12 hours have elapsed since the last failure. Then, find the
expected time to next failure.