George Mason University

CS491 Great Principles Fall 2002

Design Problem D4 (10 points)

Due 11/18/02

Read the Queueing Networks Tutorial linked to the resources section of the CS491 web page, third item from bottom of the list. For an historical perspective on how performance models came into their own, see the essay Performance Evaluation and Experimental Computer Science (1981), second last item in the resources list. Optional: You will find a complete, in-depth tutorial about these models and their applications to queueing systems in Operational Analysis of Queueing Network Models (1978), last item in the resource list. Also look at the CS471/571 slides about Queueing systems. For what follows you will need to refer to the computational algorithm called "mean value algorithm" and to the bottleneck analysis.

Queueing systems are important because they have been a remarkably effective model for determining capacity of communication system for over 100 years and of computer systems for over 50 years. They enable system designers to configure systems to meet throughput and response time targets in the face of randomness (uncertainty) in the arrivals, service times, and choices of servers. Extraordinarily efficient computational algorithms have been developed for making these calculations.

Let's examine how to use a queueing network model to understand the problem of thrashing in multiprogrammed systems. Recall from our study of virtual memory that thrashing was one of the early performance problems that virtual memory designers encountered. You should consult the previous materials again to refresh your understanding of thrashing.

For a model, let's consider a time sharing system with N users, think time Z, a CPU (with service time S1 and visit ratio V1), and a paging disk (S2, V2). A job exits the CPU after a CPU burst for one of two reasons: either the job requested a page swap operation (it goes next to the disk) or the job completed (it leaves the system and returns to the user). The mean value equations for this system are

   T1  =  D1*(1+Q1*(N-1)/N)
   T2  =  D2*(1+Q2*(N-1)/N)
   R   =  T1+T2
   X   =  N/(R+Z)
   Q1  =  X*T1
   Q2  =  X*T2

Where Ti is the mean total residence time per visit to server i (1,2), Ti = Vi*Ri where Ri is the mean response time per visit, Qi is the mean queue length at server i, Di is the mean demand for server i (Di = Si*Vi), R is the system response time, X is the system throughput, and Z is the think time. To evaluate these equations, make an initial guess for Qi of N/2; then cycle through the equations creating new guesses for Qi until the difference between successive guesses is less than 0.001. By evaluating for various N, you can construct graphs of system throughput X(N) and and response time R(N).

To add multiprogramming to this model, we suppose that the main memory has M pages and is equally divided among the jobs; thus each job gets M/N pages. Assume that the jobs have identical fault functions, F(m) = number of page faults when m pages are allocated. Note that V2=F(M/N).

Here are some parameters to get started with a study using this model:

   think time Z = 30 sec
   total CPU demand (over all visits) D1 = 5 sec.
   DISK service time S2 = 50 msec per visit
   DISK visit ratio V2 = F(M/N)
   total DISK demand D2 = S2*V2
   F(m) = 1000, m<10 pages
        = (1000-20*(m-10), m=10,11,12,13,14
        = 10, m=15,16,....
   total memory M = 150 pages

(1) Using the mean value equations, find the system throughput X(N) for N=1,2,...,25. Plot it on a graph along with the throughput asymptotes imposed by the CPU and DISK. The CPU's asymptote is 1/D1 and the DISK's is 1/D2(N). Note that the CPU's asymptote is a constant while the DISK's changes with N. From this you should see an optimal level of multiprogramming (N) that is strongly related to the clamping effect on throughput from saturation of the disk under heaving paging loads.

(2) Make an interpretation for what is going on here. What is depressing the throughput? Why does this happen? What can a system designer do to prevent the problem?

(3) Suppose the system is augmented with a controller that maintains a queue of jobs wanting to be loaded into main memory but are blocked by the controller to prevent thrashing. Suppose the controller decides to let N into memory and keep the surplus in its holding queue. Then if K jobs are submitted, all K are in memory when K is less than or equal to N, and exactly N are in memory when K>N (in which case K-N are in the holding queue). Sketch the throughput curve as a function of K (not N). Make interpretations. (You should be able to conclude that a controller that can figure out the optimal N will enable the system to run at maximum throughput for all K>N.)

(4) Working-set memory management is based on the idea that the working set window will observe a program's current locality and preserve it in memory. A working set controller will admit a new job from the holding queue only when there is sufficient space in memory for its working set. In the example, the program localities are about 15 pages in size. Suppose that the working set window were chosen so that the working set windows observed these 15 favored pages most of the time. Draw conclusions about the stability of the system when using a working set controller. How would the performance of this controller compare with that of a controller that simply picked a fixed value of N?