Reconsider the first motivating example (i.e., the random walk through England). Instead of a single son, suppose there are twin sons. Both lads behave independently but statistically the same. That is, they do not necessarily travel together. One can be hiking the Yorkshire moors while the other is sightseeing in London, though the probabilities of where to go the following day are the same. If, by chance, both sons happen to be kayaking the same day, they share a kayak. Solve this new system and answer the following four questions.
Father's question: What percentage of days is neither son drinking in Leeds?
Lake District relatives' question: Once a son finishes a day of kayaking in the Lake District, how long will it typically be before one of the sons is next there?
Policeman's question: How many days each month can the bobbies expect to see one or both of the sons driving to London after drinking in Leeds?
Kayak renters' question: How many days each month do they need to have a kayak available?
In Section 10.6, in the model interpretation of the database server support example, provide all the details to verify the answer to the company president's question.
Is the mean recurrence time for a periodic state always equal to its period? Justify your answer.
Reconsider Fig. 10.7. Suppose the probability of going from D to E is 1/3, from D to A is 2/3, from E to D is 3/4, from E to F is 1/4, from H to I is 1/2, and from H back to itself is 1/2. All other probabilities are 1. Give the mean recurrence time for each of the recurrent states.
Give a two state Markov model, where the mean recurrence time for state 1 is 1.75. What is the range of recurrence times that can be observed for state 2?
Consider a small store with a single worker. The store is only large enough to have at most two customers in the store. (If another customer walks up when two other customers occupy the store, the third customer does not enter the store and simply goes away.) Once a customer is in the store and the worker is available, the worker spends an average of 5 minutes serving the customer. The worker can only service one customer at a time. Suppose the acceptable service level is 7.5 minutes that an average customer spends in the store. What is the maximum allowable arrival rate of customers to the store to guarantee this level of service?
Give a two state Markov diagram, where the sum of the mean recurrence times of the two states is as small as possible.
Suppose that the actual workload on the system consists of two jobs, one completely CPU-bound and the other completely disk-bound. However, suppose that the system analyst decided to aggregate the two jobs into a single class. Thus, the assumed workload consists of two identical jobs, both of which spend half their time at the CPU and the other half at the disk. How much error is made in making this assumption? Justify your answer. You may choose to consider system throughput, device utilization, response time, or some other important performance metric.
Consider the following "system." Students arrive at the weight room at the Rec Center with an inter-arrival time of 10 minutes, exponentially distributed. When a student enters the weight room he/she immediately proceeds to the treadmill. Assume that there is only one treadmill and only one student can use it at a time. Once a student finishes with the treadmill, she/he proceeds to one of the two stationary bikes. When finished with the bike, the student leaves and goes home. No loitering is allowed in the exercise room. That is, if someone arrives at a piece of equipment and they can't begin using the equipment immediately, they must leave the room and go home frustrated. Once someone starts exercising on a piece of equipment, he/she uses it for an average of 15 minutes (exponentially distributed).
Draw the appropriate Markov model. Label all arcs.
In steady state, what are the probabilities of being in each state?
Give the mean number of students using the stationary bikes.
What percentage of arriving students who come to the exercise room, wanting to use the treadmill, must leave frustrated because it's busy?
What is the "good" throughput of the exercise room (i.e., the rate at which students happily leave the Rec Center, having exercised on both pieces of equipment)?
Consider the following twist to the previous problem. In the weight room at the Rec Center the following equipment is present: one treadmill; two stationary bikes; and one rowing machine. After visiting the treadmill, students go to a bike with probability 0.3 and to the rowing machine with probability 0.7. After using a bike, students always go to the rowing machine. After using the rowing machine, students always go to the treadmill. Once someone starts exercising on a piece of equipment, he/she uses it for an average of 3 minutes (exponentially distributed). There are exactly two students in the weight room at all times (i.e., when one student leaves the weight room, another student enters at the same time). Upon entering the weight room, a typical student will use the rowing machine 3 separate times (i.e., visits). If a student goes to a piece of equipment and he/she can't begin using it immediately because of the other athlete, he/she patiently wait their turn.
Draw the Markov model of this system. Clearly label all the arcs.
How many times does the typical student use the treadmill?
How many times does the typical student use the rowing machine?
What are the steady state probabilities of each state?
What is the utilization of each piece of equipment?
How many students leave the weight room per hour?
How much time does the typical student stay in the weight room (i.e., what's the response time per student)?
An Internet Service Provider (ISP) has m dial-up ports. Connection requests arrive at a rate of l requests/sec. An average session duration is equal to 1/m seconds (i.e., each session completes at a rate of m req/sec).
Draw a state transition diagram for the ISP showing the arrival and departure rates [Hint: the state k represents the number of active connections].
Give an expression for the probability pk (k = 0, ..., m) that k connections are active as a function of l, m, and m.
Find an expression for the probability pbusy that a customer finds all dial-up ports busy as a function of the state probabilities pk.
A Web server is subject to 10 load tests. The number, n, of requests processed by the server is kept constant during each test. There is only one request in execution at the server in test number 1. This number is incremented by one at each subsequent test. The server's average response time, R, is measured for each load test. The results are shown in Table 10.1.
Table 10.1. Data for Exercise 10.12
R (in sec)
Find the throughput of the Web server for each of the 10 tests.
Assume the throughput characteristics of the Web server obtained in the previous item and assume also that the Web server is subject to a load of 2 request/sec. Suppose that requests are rejected when the number of requests at the server is equal to W. Find the fraction, f, of lost requests for W = 1, ..., 10. Plot a graph of f versus W.