CIT 595 Spring 2011

Homework #4

Due Fri Mar 4 11:59pm


Introduction

In this assignment, you will implement three different algorithms for scheduling the arm on a hard disk. That is, you will simulate the motion of the disk arm by taking a set of requests for cylinders/tracks to read and then determining the order in which they will be read. You will then report the total "distance" the disk arm had to travel. Be sure to review Section 5.4.3 in Tanenbaum's "Modern Operating Systems" (3rd edition) before proceeding.


Part I (10 points)

Write a C program called fcfs.c that implements the First Come-First Serve disk scheduling algorithm described on page 379 in the course textbook. Assume the disk arm starts at cylinder/track 50. The set of "requests" to the disk (cylinders/tracks to be read) should be provided as command-line arguments to your program (note: it is safe for your program to assume that the inputs are all well-formed integers between 0 and 100). The output of your program should show the order in which the cylinders/tracks are read, and the total distance traveled. For instance, if your program were executed like this:

./fcfs 5 28 10 7 39 20 45 67 36 35
then the output should look like this:
Reading track 5
Reading track 28
Reading track 10
Reading track 7
Reading track 39
Reading track 20
Reading track 45
Reading track 67
Reading track 36
Reading track 35
Total distance: 219

 

Part II (20 points)

Write a C program called ssf.c that implements the Shortest Seek First disk scheduling algorithm described on page 380 in the course textbook. As in Part I, the set of "requests" to the disk (cylinders/tracks to be read) should be provided as command-line arguments to your program, and the output of your program should show the order in which the cylinders/tracks are read, and the total distance traveled. Assume the disk arm starts at cylinder/track 50.

Note: the SSF algorithm looks for the track closest to where the disk arm currently is positioned, not to where it started.

Also: in the case where two tracks are both equally as close to the current position, you can choose either one (the higher one or the lower one), as long as it's a "local" decision (i.e., you do not consider what you'll do after that).

 

Part III (20 points)

Write a C program called look.c that implements the Elevator disk scheduling algorithm (sometimes called the LOOK algorithm) described on page 381 in the course textbook. As in Parts I and II, the set of "requests" to the disk (cylinders/tracks to be read) should be provided as command-line arguments to your program, and the output of your program should show the order in which the cylinders/tracks are read, and the total distance traveled. Assume the disk arm starts at cylinder/track 50.

Note: you can choose whether the disk arm is moving up or is moving down at the start of your program.

 


Academic Honesty

You must work on this assignment individually. Collaboration is explicitly not allowed. That includes (but is not limited to) working together on the assignment, providing solutions to or receiving solutions from another student, or receiving assistance from an outside source. Whereas it is okay to discuss the intent of the assignment or address other clarification issues with other students, you must not discuss approaches, algorithms, or code.

If you need help with this assignment, please visit a member of the teaching staff during office hours, or contact one of us to set up an appointment.


Submission
For this assignment:
  1. Put your C source code files (fcfs.c, ssf.c, look.c) in a directory called "homework4_[your-SEAS-id]". For instance, mine would be homework4_cdmurphy.
  2. Additionally, include a Makefile that compiles all your programs and put that in the same directory, too.
  3. Last, from the directory ABOVE your "homework4_[your-SEAS-id]" directory (ie, its parent), tar and/or zip the directory with all your files in it. For instance, on eniac you could do "tar -cvf homework4_[your-SEAS-id].tar ./homework4_[your-SEAS-id]".
  4. Submit the tar/zip file in Blackboard.

Failure to properly follow the submission instructions could result in a delay of grading your assignment and/or a lateness penalty, so please be sure to do it correctly!

Homeworks are to be submitted via Blackboard, as described on the course overview page. Please be sure to tar and/or zip your files into a single submission file!