Lab 6: Disk Scheduling

Due by 10:00 PM, Tuesday, April 24th, 2012

Description

For this lab you will simulate the following disk scheduling algorithms:

Instructions

  1. The first command-line argument to the program will be the filename whose contents are to be treated as those of a magnetic disk.
  2. The second command-line argument to the program will be the filename whose contents are to be treated disk read requests.
  3. Requests are listed one per line as: 
    cylinder track sector
  4. There will be less than 100 requests.
  5. Using fseek() and fread(), the program should traverse the file data and print what it finds at the given location.
  6. fseek() should simulate moving the read head from one cylinder to another.
    7. Consequently, use only SEEK_CUR for the last parameter of fseek().
  7. There are 4 tracks with 8 sectors each per cylinder. There are 64 cylinders (numbered 0 - 63).
  8. Unlike the real algorithms, read (buffer) an entire cylinder. (The program should NOT copy the entire contents of the secondary file, but use fread() to access the contents.) Then the program will output what is stored in the appropriate track and sector (i.e., a single character).
  9. Print to stdout, on it's own line, the algorithm's four letter acronym followed by ": " and then all of the characters read.
  10. Initially, the read head begins at the innermost cylinder (i.e., 63) at the last track and sector for FCFS and LOOK. For SSTF, the read head starts at cylinder 32, track 0, sector 0.
  11. When selecting the ordering of locations to visit, measure distances between disk locations as if the disk was a one-dimensional array (i.e., take into account the cylinder, track and sector).
  12. Additionally, calculate the average seek distance (i.e., the average number of cylinders (and just cylinders) traveled by the read head) for each algorithm. Print to stdout, on it's own line, the algorithm's four letter acronym followed by ": Average seek distance: " and then the average seek distance with two decimals places of precision. Then print two newlines.


Testing

For testing purposes, use at least the following files:
Use can use the labTester.sh (right-click on link to download) script to test the output of your program. The parameters to the script are:
  1. Filename of expected stdout output
  2. Filename of executable
  3. Command-line argument(s) to the executable file
For example: 
  chmod 755 labTester.sh
  ./labTester.sh  lab6-set1-stdout.txt  lab6  lab6-set1-secondary.txt  lab6-set1-requests.txt
If the stdout of the executable matches that of the key, then all you should see is the following: 
The output and the answer key match perfectly!!!
Instead of right-clicking on the link above, after logging into ranger, you can copy labTester.sh with the following command: 
  cp /nfshome/hcarroll/public_html/3250/labTester.sh .

Example Output

Example output is for set 1 of the testing files.
$ ./lab6 lab6-set1-secondary.txt lab6-set1-requests.txt
FCFS: characters should appear here
FCFS: Average seek distance: XX.XX

LOOK: characters should appear here
LOOK: Average seek distance: XX.XX

SSTF: characters should appear here
SSTF: Average seek distance: XX.XX

Submission

Submit the source code file using the handin program. For example, to submit the code for this lab, type the following in a terminal exactly as it appears: 
  handin  lab6  lab6.cpp

Alternatively, you can submit the assignment from any computer via PeerSpace. After successfully logging into PeerSpace, go to Tools, then Assignments. Click on the Submit link.

Rubric:

Points          Item
----------      --------------------------------------------------------------
_____ / 40      Correctly outputs individual chars to stdout for FCFS
_____ / 10      Correctly outputs the average seek distance to stdout for FCFS
_____ / 20      Correctly outputs individual chars to stdout for LOOK
_____ /  5      Correctly outputs the average seek distance to stdout for LOOK
_____ / 20      Correctly outputs individual chars to stdout for SSTF
_____ /  5      Correctly outputs the average seek distance to stdout for SSTF

_____ / 100


Hints

  1. Start by writing the major steps as pseudocode and saving them as comments. Then, fill out the next level of steps as pseudocode (same them as comments in the code as well).
  2. Q: I overheard that we had to copy the files in a specific manner. Will copy and paste work?
    A: As with all of the labs, it's better to download the file or copy the entire file on the command-line. Copying and pasting may not get the last character correctly. To download the file, use a browser and either choose something like "save link as..." or pull-up the page and choose "save". To copy it on the command-line, execute something similar to "cp /nfshome/hcarroll/public_html/3250/lab6-set1-secondary.txt .".
  3. Use ftell() to debug where the read position in the secondary memory file is. For example, print it out before and after a call to fread().

Source: Recycled (with modifications) from Dr. Pettey.