CSCE 317 Spring 2014 Solutions to Second Midterm Exam 1. (Accept-reject method; 10 points) Using the accept-reject method, show how to sample the r.v. X whose pdf is 12t2 (1 − t) if 0 ≤ t ≤ 1, fX (t) = 0 otherwise, given that you can sample Y ∼ Uniform(0, 1). What is the expected number c of repetitions needed to get a good sample? Show your work. Answer: We first find c: fX (t) fX (t) = sup = sup fX (t) = 12 sup t2 (1 − t) . 1 t t t 0≤t≤1 fY (t) c = sup Since fX (t) is differentiable in the interval (0, 1), and its values at t = 0 and t = 1 are both 0, the supremum is achieved when (d/dt)(fX (t)) = 0. We have d 2 d t (1 − t) = (t2 − t3 ) = 2t − 3t2 = 0 dt dt when t = 0 or t = 2/3. The larger value is then fX (2/3) = 16 =c. 9 The algorithm is thus: (a) Generate u ∼ Uniform(0, 1). (b) Accept and output u with probability fX (u)/c: i. Generate x ∼ Uniform(0, 1). ii. If x ≤ (27/4)u2 (1 − u), then accept and output u. iii. Otherwise, repeat the whole algorithm. 2. (An ergodic system; 5 points) Over the course of a day, customers walk into a bank at an average rate of one customer every 20 seconds. There are on average 15 customers in the bank at any given time. How much time does an average customer spend in the bank (in minutes)? Answer: By Little’s law for an open system, we have E[N ] = λ E[T ], where N is the number of customers in the bank, λ is the average arrival rate, and T is the time a customer spends in the bank. We are given that E[N ] = 15 and that λ = 1/20 customers per second, or equivalently, λ60/20 = 3 customers per minute. We then find E[T ] = 15/3 = 5 (minutes). 1 3. (An interactive system; 15 points) Consider the following interactive system: .. . Database 4 5 CPU 1 5 Suppose we are given the following information: • mean user think time = 4 seconds • expected time spent at the database = 2.5 seconds/visit • expected number of jobs at the database = 7.5 • expected response time of the system = 2 seconds/job (this does not include think time) • average CPU usage (service demand) is 0.02 seconds/job cpu ] of jobs queued at the CPU? What is the expected number E[NQ Answer: By “job” we mean a system completion. We are given: E[Z] = 4 sec E[R] = 2 sec/job E[TDB ] = 2.5 sec/visit E[DCPU ] = 0.02 sec/job E[NDB ] = 7.5 • We also know based on the diagram that each job visits the CPU exactly once, and so DCPU = VCPU SCPU = SCPU , i.e., E[SCPU ] = 0.02 sec /visit. • Also based on the diagram, we know that the expected throughput at the database XDB = XCPU /5 = X/5. • By Little’s law, XDB E[TDB ] = E[NDB ] = 7.5, and so XDB = 7.5/2.5 = 3 visits/sec. • Plugging this into the previous equation, we get X = XCPU = 5XDB = 15 visits/sec = 15 jobs/sec. • We can now use the response time law to find N : We have 2 = E[R] = N/X − E[Z] = N/15 − 4, and so N = (6)(15) = 90 jobs in the whole system. • We will need to find the expected number E[NCPU ] of jobs at the CPU. Each of the 90 jobs in the whole system is either at the CPU, at the database, or being thought about by a user, and so we have 90 = E[NCPU ] + E[NDB ] + E[Nthink ]. This gives E[NCPU ] = 90 − E[NDB ] − E[Nthink ] = 82.5 − E[Nthink ], but we still need E[Nthink ]. • We get E[Nthink ] by Little’s law applied to the open system of the thinking users: E[Nthink ] = X · E[Tthink ] = X · E[Z] = (15)(4) = 60 jobs. • Plugging this into the previous equation, we get E[NCPU ] = 82.5 − 60 = 22.5 jobs. 2 • The jobs at the CPU are split between those waiting in the queue and those currently cpu running: 22.5 = E[NQ ] + E[Nrunning ]. • If we apply Little’s law to the actual processor (not including the queue), we get E[Nrunning ] = XCPU · E[SCPU ] = (15)(0.02) = 0.3 jobs. (In this specific case, we are really invoking the utilization law: ρCPU = λCPU /µCPU = XCPU · E[SCPU ] = 0.3.) cpu • Finally, plugging this into the previous equation, we have E[NQ ] = 22.5 − 0.3 = 22.2 jobs in the queue (on average). 4. (Modification analysis; 10 points) The following measurements were obtained over a long stretch of time for an interactive system consisting of a CPU and a slow disk: • Bcpu = 250 seconds • Bslowdisk = 750 seconds • C = Ccpu = 500 jobs • Cslowdisk = 1000 jobs • E[Z] = 10 seconds • N = 30 users (a) What is N ∗ ? Would you say that N is high or low compared with N ∗ ? (b) Which of the following two options would improve the response time more: (i) replacing the CPU with one twice as fast; or (ii) replacing the disk with one twice as fast? Explain. (c) Suppose you install another disk twice as fast as the one you currently have, and balance the load between the two disks. Is the CPU now the bottleneck? Explain. Answer: We observe the following system parameters: Bcpu 250 = = 0.5 sec/job C 500 Bslowdisk 750 Dslowdisk = = = 1.5 sec/job = Dmax C 500 D = Dcpu + Dslowdisk = 2 sec/job Bslowdisk 750 = Sslowdisk = = 0.75 sec/visit Cslowdisk 1000 Dcpu = (a) N∗ = D + E[Z] 2 + 10 = =8. Dmax 1.5 So N is high compared with N ∗ (30 8). (b) Replacing the disk would improve the response time more. The disk is the bottleneck device. Replacing the CPU will make hardly any difference, because doing so does not change Dmax , which controls the response time when N is high. (c) Actually, all three devices have the same load in this case, so all three are bottleneck devices, including the CPU. We see this as follows: 3 • The current average number of disk accesses per job is Vslowdisk = Cslowdisk 1000 = = 2 visits/job . C 500 • After buying the fast disk, we balance the load by finding the new average number of visits V˜slowdisk and V˜fastdisk to the slow and fast disk, respectively. These quantities should satisfy V˜slowdisk + V˜fastdisk = 2 Sfastdisk · V˜fastdisk = Sslowdisk · V˜slowdisk (this is the current Vslowdisk ) ˜ fastdisk = D ˜ slowdisk ) (i.e., D • Since the fast disk is twice as fast as the slow one, we have Sslowdisk = 2Sfastdisk , and so the second equation above becomes V˜fastdisk = 2V˜slowdisk . • Solving the two equations then gives 4 V˜fastdisk = , 3 2 V˜slowdisk = . 3 ˜ fastdisk = D ˜ slowdisk = Sslowdisk ·V˜slowdisk = (3/4)(2/3) = 0.5 = Dcpu . • So we finally get D So all devices have the same load. ˜ ∗ = 23, and so N is still (somewhat) high.) (By the way, the new threshold is N 5. (Inverse transform method; 10 points extra credit) Using the inverse transform method, show how to sample the r.v. X whose pdf is 2t if 0 ≤ t ≤ 1, fX (t) = 0 otherwise, given that you can sample Y ∼ Uniform(0, 1). Show your work. Answer: For 0 ≤ x ≤ 1, we have Z x FX (x) = Z fX (t) dt = −∞ So if FX (x) = u, then x = √ x 2t dt = x2 . 0 u. So here is the algorithm: (a) Generate u ∼ Uniform(0, 1). √ (b) Output u. 4

© Copyright 2019 ExploreDoc