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
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, A Comparative Analysis of Disk Scheduling Policies by Teorey and Pinkerton, CACM, 3/72, and answer some questions about the article.
Content Area: Operating Systems
Topics: Disk scheduling algorithms
Type of Interaction: Designed for individual work; however, since the construction of the graphs is tedious, it might be possible to distribute this work among students and allow them to share the completed graphs. Optimally, students should use some type of graphing software to automatically generate graphs from an output data file generated by the program.
Pre-requisites: Before students try this lab they should already understand something about disk scheduling. A "standard" lecture on disk scheduling algorithms should suffice: describe the problem and define the classic algorithms (FCFS, SSTF, SCAN, LOOK). See Silberschatz and Galvin's Operating Systems Concepts, 4th edition, Addison Wesley, Section 12.2 for a review of disk scheduling algorithms.
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.
Goals/Objectives: Teach about disk scheduling algorithms; demonstrate the usefulness of simulation, especially as a tool for investigating systems; exposure to operating systems research (even though it is from 1972); exposure to a non-trivial program. Learn the FCFS, SSTF, and LOOK disk scheduling algorithms; use simulation; use graphing tools.
Before the lab session:
Validation: This laboratory project has been used successfully
several times by the author in an open lab format.
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
Topic: Disk Scheduling
Resources and materials required: Pascal compiler and run time environment. Graphing software strongly suggested.
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.
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.
Circle one: EARLIER LATER
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.
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
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.