Two motivating examples are presented. One is an analogy utilizing a situation outside the normal world of computing. The other is an extension of an earlier example in Chapter 3. The first uses finite probabilities as state transitions (i.e., the discrete state, discrete transition case), while the second uses flow rates as state transitions (i.e., the discrete state, continuous transition case).
Motivating Example #1: Random Walk Through England
As a graduation present by his mother, consider a lad who is given a year to spend in England. The only condition is that every day at 3:00 p.m., the lad must use his mobile phone to call his mother and simply let her know where he is and what he is doing. After only a couple of months, the mother deduces a definite pattern to her son's behavior. (See Fig. 10.2.)
Figure 10.2. England example.
The lad is always doing something in one of four locations: drinking in a Leeds pub, sightseeing in London, kayaking in the Lake District, or hiking in the Yorkshire moors.
If the lad is in a Leeds pub, he is either likely to go sightseeing in London the following day (60%), or he will still be found in a Leeds pub (40%).
If the lad is in London, he is likely to be found in a Leeds pub the following day (20%) or will decide to go hiking in the Yorkshire moors (80%).
Once found in the Lake District, there is very good chance that the lad will still be found kayaking the following day (70%), but there is a possibility that he will next be found hiking the moors (20%) or back in a Leeds pub (10%).
When found hiking in the moors, there is a good chance that he will still be hiking the following day (50%). However, he sometimes goes to a Leeds pub (30%) and sometimes decides to go kayaking in the Lake District (20%) the following day.
Simply knowing these patterns, the mother finds herself having to answer certain questions of others.
Father's question: What percentage of days is the son actually not drinking in Leeds?
Lake District relatives' question: Once the son finishes a day of kayaking in the Lake District, how long will it typically be before he returns?
Policeman's question: How many days each month can the bobbies expect to see the son driving to London after drinking in Leeds?
Kayak renters' question: How many visits each month does the son typically visit their shop and typically how long does the son keep their kayak out each visit?
Situations such as this are directly analogous to ones encountered when analyzing the performance of computer systems. For example, the workload characterization of a typical web user is very much like that of the lad. After visiting one web site (e.g., an online airline reservation site), the user is likely, with known probabilities, to visit certain other related web sites (e.g., a rental car site, a hotel reservation site). Knowing usage patterns can help answer a broad range of performance-related questions (e.g., throughput expectations, anticipated response time behavior, projections for capacity planning activities).
Motivating Example #2: Database Server Support
Consider a computer system with one CPU and two disks used to support a database server. (Note: This example is a slight modification of Example 3.2 given in Chapter 3.) Users remotely access the server and typically login, perform some database transactions, and logout. The following specifics are known about the system. (See Fig. 10.3.)
Figure 10.3. Database server example.
To guarantee acceptable QoS levels, at most two users are allowed to be logged onto the database system at any one time. However, the demand for the system is sufficiently high so that it may be assumed that exactly two users are logged onto the system at all times. That is, as soon as one user completes the requested transaction and exits the system, another eager user is waiting to log on.
Each transaction alternates between using the CPU and using a disk. The particular disk required by a user depends on the transaction, since different transactions access different files, and different files reside on different disks.
The two disks are of different speeds, with the faster disk being twice as fast as the slower disk.
A typical transaction requires a total of 10 sec of CPU time.
Transactions are equally likely to find the files they require on either disk.
If a transaction's files are found on the fast disk, it takes an average of 15 seconds to access all the requested files.
If a transaction's files are found on the slow disk, it takes an average of 30 seconds to access all the requested files.
From the above known observations, the system analyst is faced with answering various questions.
User's question: What response time can the typical user expect?
System administrator's question: How near capacity (i.e., what is the utilization) of each of the system resources?
Company president's question: If I can capture Company X's clientele, which will likely double the number of users on my system, I will need to also double the number of active users on my system. What new performance levels should I spin in my speech to the newly acquired customers?
Company pessimist's question: Since I know that the fast disk is about to fail and all the files will need to be moved to the slow disk, what will the new response time be?
Though both examples might appear at first glance to be somewhat dissimilar, they can be modeled and solved using the same Markov modeling approach.