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
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:
(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?
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
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