CSTC Banner

 CSTC home --> browse resources --> cover page --> content
An Investigation of Disk Scheduling Algorithms Laboratory

Daniel T. Joyce


Students investigate the behavior of disk scheduling algorithms by using a simulation program.
The following information can be found below:

  • Instructor Cover Sheet
  • Student Cover Sheet
  • An Investigation of Disk Scheduling Algorithms Lab


  • Instructor Cover Sheet

    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, 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

    Level: Intermediate

    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.

    Time:

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

    Feedback location:

    Send comments to Daniel Joyce, Villanova University: joyce@monet.vill.edu


    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:

  • dsimspec.html Disk scheduling program specification.
  • disksim.pas A Pascal program that fulfills the specification.
  • disksim.lis The listing of disksim.pas. This includes line numbers.
  • graph.gif A sample of how the data should be graphed.


  • 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.






    Student Cover Sheet

    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:

  • dsimspec.html Disk scheduling program specification.
  • disksim.pas A Pascal program that fulfills the specification.
  • disksim.lis The listing of disksim.pas. This includes line numbers.
  • graph.gif A sample of how the data should be graphed.


  • 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.




    An Investigation of
    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.

    1. 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?


    2. 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):

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


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


    5. 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.

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

    7. 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.

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


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


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


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

    5. 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.

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

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

    3. What extra factor does the Eschenbach scheme optimize?

    4. 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.

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

    6. 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.