Assignment 4

Note: You may work with one other student on this assignment if you wish. The assignment is due 2:40pm, Friday, October 26. You will submit a written report for this assignment.

Objectives

To use system simulation to analyze algorithms.
To become more familiar with disk scheduling techniques.
To practice design of systems algorithms.

Problem

In this assignment, you will implement and test a selection of disk scheduling algorithms, including SSTF (Shortest Seek Time First), Elevator scheduling, and C-LOOK (the one-way elevator).

You will also consider how to schedule disks for a disk of two arms. One might add a second arm to a disk to improve overall performance. Actually, many computers use redundant disks (called mirroring --- or RAID level 1), which essentially can behave like multiple arms to the same data when processes are simply trying to read data. In this project you'll investigate how additional arms can help and you'll design new algorithms for this problem.

Source code

A simulation code suite is available by typing getcs 350 4. This will place into your directory six files:

`Makefile`	A makefile for creating your code
`DiskSimulate.h`	declares classes for simulating processes accessing a disk
`DiskSimulate.C`	defining methods for these simulation classes
`Strategy.h`	declares classes representing disk scheduling strategies
`Strategy.C`	defines methods for these strategy classes
`main.C`	contains `main()`

DiskSimulate.h defines four classes used in the simulation package.

`DiskArm`	Represents the arm of a disk
`Disk`	Represents a disk (with possibly several arms)
`Process`	Represents a process making disk requests
`RequestQueue`	Represents a set of processes

Look within the header files for additional documentation about the classes' methods. Your modifications to DiskSimulate.h and DiskSimulate.C should be only for debugging purposes.

Strategy.h defines two classes.

`DiskStrategy`	Represents a strategy for scheduling the disk
`FIFO`	Represents the first-in, first-out strategy

All of your official code for submission in this assignment should go into Strategy.h and Strategy.C.

Your modifications to main.C will only be for debugging purposes. You will want to modify this file as you add new strategies, in order to test them. (You'll see several commented lines in main() indicating how you might add more.)

Testing

You can compile and run your program thus.

% make
% sim 2 30
    time      mean   num num
  elapsed    sq wait arm pro strategy
 259618.75   67752.70  1  30 FIFO

Here we have run a simulation of how FIFO works with a 2-arm, 1048-cylinder disk if there are 30~processes, each making a sequence of requests to 1000~random cylinders on the disk. (The number of arms and the number of processes are specified on the command line. The rest is built into the program.)

Arm movement on the disk is modeled by the following: Say the arm is at cylinder $i$ and moves to cylinder $j$, and there are a total of $C$ cylinders. It will take $4 + 14|i-j|/C$ milliseconds to accomplish this. This represents a disk where it takes $4$ milliseconds to enable the arm movement machinery, and $14$ milliseconds to move the arm across the disk once it is moving. Though this is not a perfect model of arm movement, it is realistic enough for our purposes.

This gives two statistics about how the strategy performed. The first, time elapsed, measures the total amount of time taken to serve all the requests of all 30 processes. The second, the mean square wait time, is a measurement of the average square of the wait time for each request. This is a measurement of how fair the strategy has been as far as giving each request an equal priority. (If the strategy starves some requests very long, then the square of these requests will be very large, and the mean square wait time will increase.)

A good strategy will minimize both measurements --- it will both optimize the total throughput of the disk, but it will also avoid making requests wait an undue amount of time.

What to hand in

You should implement and test the three other strategies (Shortest Seek Time First, Elevator, and C-LOOK) as subclasses of DiskStrategy. You should also design and test your own algorithm, keeping the two-arm disk in mind.

Hand in your code electronically via handincs 350 4. Also, in class, submit a typed paper report summarizing your work.

The typed paper report should be in the form of an experimental research paper: You should describe your own algorithm, your experimental procedure, your results, and your own analysis of the results. It will not contain C++ code. The paper should be addressed to others who understand operating system concepts but are not involved in this class. Think of it as a short research paper that you are submitting to a journal for publication.

An outstanding report will contain graphs displaying how algorithms' performance changes as the number of processes increases, both with a single arm and with two arms. An outstanding report will also present a new algorithm that outperforms the standard algorithms in the two-arm case, with simulation results to back it up.

Grading criteria

I reserve the right to deduct points for stylistic, grammatical, and presentational issues in both your code and your report.

10	SSTF implementation
10	Elevator algorithm implementation
10	CLOOK implementation
15	Your own algorithm's implementation and performance
10	Description in paper of your algorithm
10	Quality of results presentation
15	Quality of analysis
8	(bonus) Outstanding performance of your custom algorithm
80	TOTAL

Bonus points will be awarded competitively, based on the performance of the custom algorithm, as judged by the professor.