Assignment 1 (20 marks)
Due: February 9, 2010 (3:30pm)
The purpose of this assignment is to gain experience with analytical methods that are used in computer systems performance evaluation.
Please do any 3 of the following 5 questions, and then attempt as many others as you wish. Note that the marks allocated are the same for each question, but not all questions are of the same difficulty.
Q1. M/G/1 Queues (5 marks)
The average number of customers in an M/G/1 system is given by the well-known Pollaczek-Khinchin (P-K) mean value formula. One of the important parameters in this formula is C-squared, the squared coefficient of variation for the general (G) service time distribution.
- (1 mark) Use the P-K mean value formula to calculate the average number of customers in an M/M/1 queueing system.
- (1 mark) Use the P-K mean value formula to calculate the average number of customers in an M/D/1 queueing system.
- (3 marks) Use Little's Law to express the mean time T in the system for an M/G/1 queue in terms of rho, C-squared, and the mean service time x.
Q2. Other Markovian Queues (5 marks)
Consider a Markovian queueing system in which the service rate mu is the same for all states k > 0, while the transition rate lambda_k out of each state k (k >= 0) is given by lambda_k = alpha_to_the_k times lambda, for some alpha between 0 and 1.
- (3 marks) Find the equilibrium probability p_k of having k customers in the system. Express your answer in terms of p_0.
- (2 marks) Give a closed form expression for p_0.
Q3. Weasley Barber Shop (5 marks)
The Weasley twins, Fred and George, have opened a new barber shop at Hogwarts. Their shop has two barber chairs for customers to sit in while getting their hair cut, either by Fred (chair 1) or George (chair 2). There are also 3 regular chairs in the waiting room for customers who are waiting for service, in a First-Come-First-Serve fashion.
Customers arrive to the barber shop according to an open-loop continuous-time Poisson process with average rate lambda. If both barber chairs are empty upon arrival, arriving customers choose their barber uniformly at random (since they can't tell the twins apart). If only one barber chair is empty, the customer moves to that chair. If both barber chairs are occupied, then the arriving customer moves to the waiting room, if space is available. If the waiting room is full, the customer leaves and never returns. If there are waiting customers, they receive service by the next available barber as soon as the barber chair is vacated. The service time for a haircut is exponentially distributed. However, Fred is slightly faster than George at cutting hair. Their respective service rates are mu1 and mu2, with mu1 > mu2.
- (1 mark) Draw a Markov chain representing the states and transition rates of this system.
- (1 mark) Write the flow balance equations for this system.
- (2 marks) Derive the (steady-state) equilibrium state probabilities p_i for this system. (Tip: Ignore the waiting room initially. Add it back in later.)
- (1 mark) Assuming reasonable numerical values for lambda, mu1, and mu2, calculate the average utilization of each barber chair, as well as the expected number of customers in the system, and the proportion of customers lost due to waiting room overflow.
Q4. Stupid Card Tricks (5 marks)
A special deck contains N cards that are numbered from 1 to N. The deck is randomly and thoroughly shuffled, and the cards are spread out face down on a table. You then select k cards, one at a time, and place them face down in front of you as your "hand" for this game, where 1 <= k <= N.
- (1 mark) What is the probability that your hand contains card 1?
- (1 mark) What is the probability that your hand contains both card 1 and card 2?
- (3 marks) What is the probability that your hand contains all the cards from 1 to j (inclusive), for some 1 <= j <= k <= N.
Q5. Charitable Donations (5 marks)
Each January, Professor Williamson cleans his garage and identifies usable stuff that should be given away to charity. This year, just like last year, he found N = 100 items to give away. Also like last year, there are m = 4 equally deserving charitable organizations. In 2009, Professor Williamson resolved this dilemma by generating a uniformly distributed random value between 0 and 1, and dividing the pile of N items into 2 piles according to this single random variate. He then recursively divided each of the 2 piles using an iid U(0,1) variate for each, producing 4 piles of random sizes, with one pile for each charitable organization. In 2010, Professor Williamson was pressed for time, so he did the whole process in one step, without the intermediate splitting. That is, he generated four values from a U(0,1) distribution, and then normalized the sum of these to determine the number of items for each organization.
- (1 mark) Calculate the expected number of items received by each charitable organization, both in 2009 and 2010. Compare and comment.
- (2 marks) Calculate the variance in the number of items received by each charitable organization, both in 2009 and 2010. Compare and comment.
- (2 marks) Extend your results for general N and m. (Restricting m to be a power of 2 is suggested, to facilitate recursive splitting into 2 piles for as many levels as needed.)
Bonus (up to 5 marks)
Do any remaining questions that you initially chose to skip.
Submitting Your Assignment
When you are finished, hand in a hardcopy version of your solution to your instructor, either in person, or under his office door. Provide proper citation for any literature or Internet sources used. Submissions must be received on or before the stated submission deadline, otherwise a late penalty of 10% (2 marks) per day will apply.