content |

Students investigate the behavior of disk scheduling algorithms
by using a simulation program.

The following information can be found below:

**Title: An Investigation of Disk Scheduling Algorithms
Summary:**

1) Students study a program that simulates disk scheduling algorithms and answer a set of questions about it. This part of the laboratory project could be skipped.

2) The students use the program to generate data that reflects the performance of the First Come First Serve and the Shortest Seek Time First algorithms under a variety of conditions (request arrival rates of 10, 20, 30, and 40 per second, distributed exponentially; 4 or 50 sectors per track). For each algorithm under each situation the program simulates how the algorithm would handle the situation and calculates the expected service time between requests, the expected waiting time for a request, and the standard deviation of these waiting times. The students graph the 48 data points and then use their graphs and their knowledge of disk scheduling algorithms to answer another set of questions. This is the heart of the laboratory project.

Additional Exercise A: The students could implement the simulation of the Look Algorithm, collect the data about it from the simulation, and answer a question about the differences between Look and SSTF. The current simulation program is designed so that it is easy to add the Look simulation; the students just have to code the Look algorithm.

Additional Exercise B: An optional wrap up exercise is to have the students read the article that this lab is based on,

If the students are not familiar with random number generation techniques or with the use of simulation to analyze processes, then a short lecture on these topics should be given. The program used in this laboratory project generates random numbers for uniform and exponential distributions.

- Instruction before meeting for the laboratory session: 15 minutes
- Study program specifications and code before arriving for
the session: 30 minutes

During the lab session: - Answering preliminary questions in the laboratory session: 20 minutes
- Run the program and create the graphs: 30 minutes
- Answer analysis questions: 20 minutes

Option A: Including the Look algorithm: - Design, code, and test enhancement: 100 minutes
- Answer questions: 30 minutes

Option B: Research article - Study of article and answering questions: 45 minutes

Before the lab session:

**Validation:** This laboratory project has been used successfully
several times by the author in an open lab format.

**Feedback location:**

**Resources and materials required:**

1. Pascal compiler and run time environment.

2. Graphing software strongly suggested.

Also, the following files are required for this lab:

**Hints:** Be careful of machine imposed restrictions on the
random number generation code contained in the disksim program
that is used in this lab. *Random Number Generators: Good Ones
are Hard to Find* by Stephen K. Park and Keith W. Miller, CACM,
October 1988, Volume 31, Number 8, page 1192, is a clearly written
discussion of the requirements for a random number generator and
includes several algorithms for generating random numbers, one
of which should work on your system. The disksim.pas program uses
the "Integer Version 2" version of their minimal standard
random number generator, which should work for systems for which
maxint is 2^31-1 or higher. If you want to use the program in
a Turbo Pascal system you should change the appropriate integer
variables to longints.

You might consider devoting an entire laboratory session to the
investigation of random number generation before attempting this
laboratory project. Students could test various random number
generators and determine which version of Park and Miller's minimally
perfect RNG works on their system. You could also study how to
take random numbers that are based on a uniform distribution and
transform them into random numbers based on other distributions.

When covering disk scheduling, in addition to considering the
goal of minimization of average seek time you should also cover
the idea of minimizing average wait time, plus the concept of
seek or wait time standard deviation and why we might want to
minimize them (to provide reliable service time). Rotational delay,
also known as latency, is also figured into the simulation, as
is transfer time, so they should be covered.

**Title: An Investigation of Disk Scheduling Algorithms
Course:** Operating Systems, Computer Performance Modeling

The following text files are also required or are useful for this lab:

**Goals:** In addition to learning about disk scheduling algorithms
you will see the usefulness of simulation, especially as a tool
for investigating systems and be exposed to operating systems
research (even though it is from 1972) and to a non-trivial program.

Disk Scheduling Algorithms

Laboratory Project

**Name:**

Notes: Do **NOT** work together. Use these sheets for your
final answers (do rough work somewhere else.)

**Prelude:** The underlying purpose of this assignment is
not to teach about disk scheduling, although you will certainly
learn something about that topic. The purpose is threefold. First,
to introduce you to the usefulness of simulation, especially as
a tool for investigating systems. Second, to expose you to some
accessible yet challenging operating systems research, albeit
research that is many years old. Third, to expose you to a non-trivial
program.

**First Movement:** "Libretto'', i.e. "Read'',
i.e. you do not need to run any program to obtain the answers
in this section. You only need to read and study the disksim program.
Of course, if you like, you may also run the programs, perhaps
to verify your answers.

- Which line of disksim transforms a random real between 0
and 1 to a random number based on an exponential distribution
with mean equal to 1 over the arrival rate in milleseconds?

- For SSTF, suppose two requests are tied for shortest. Which
one will be chosen, the one with the earlier arrival time or
the one with the later arrival time? Which specific line(s) of
the program provides the answer?
Circle one: EARLIER LATER

Line(s):

- The value of SLOPE is set on line 398. What will the value
be set to?

- Why is the THEN statement necessary on line 280? Quote the
Disk Scheduling Simulation Specification
in your answer.

- Describe in general what the difference in the program's
output would be if the INCARRT constant was set to 5 instead
of 10 on line 29.

- Explain the purpose of the boolean expression (equality)
on line 228.

- Explain the purpose of the if-then statement on lines 235-236.

**Second Movement:** "Chorus''

Run DISKSIM. Use 27349 as the random number seed. Graph the
output as shown in the graph sample. You
should have a pair of graphs for each of the three performance
measures. Use the same scale for M = 4 and M = 50. Staple your
graphs to the back of these sheets. Use the program output and
your graphs to answer the questions in this section.

- What is the effect of M (number of sectors) on the Expected
Service Time for FCFS? Why?

- What is the effect of M on the Expected Service Time for
SSTF? Why?

- Describe and explain the difference between Expected Service
Time for FCFS and SSTF.

- Describe (do not explain, just describe) the difference between
Expected Waiting Time for FCFS and SSTF.

- Expected Service Time for FCFS appears to be constant, i.e.
it does not vary much with lambda. Give an argument as to why
it would be constant. Explain how you would change some of the
CONSTANT values in the program in order to verify this conclusion.

**Third Movement:** "Variations on a Theme''

Additional Exercise A: "Improvisation" - Add the
code for the Look disk scheduling algorithm to the simulation
program. Add a new line of information to each of your graphs
that represents the data collected from the simulation of the
Look algorithm.

Write an essay that addresses the question "Which algorithm
is better, SSTF or Look?"

Additional Exercise B: "Studying the Classics" -
Read "A Comparative Analysis of Disk Scheduling Policies''
by Teorey and Pinkerton, Communications of the ACM, March 1972.
Do not worry about understanding everything in the article. Just
understand enough to get an idea of their research, what it was
about and what it entailed, and to answer the following questions.

- According to the authors, SSTF acts like what other algorithm
under heavy loading conditions?

- Describe the difference between the SCAN algorithm and the
N-STEP SCAN algorithm.

- What extra factor does the Eschenbach scheme optimize?

- In Table I they give an expression for the Expected Seek
Time for FCFS. Plug the numbers from DISKSIM into their equation
and calculate their predicted Expected Seek Time. Show your work.

- Based on Figure 2 in the paper: Which policy gives the lowest
Expected Service Time when there are 50 requests/second?

- Which N-STEP policy, N=10 or N=infinity, gives the lower
Expected Waiting Time when there are 30 requests/second.

They suggest a two-part algorithm for disk scheduling. Describe the purpose of L1 in their implementation of this algorithm.