Hard drive simulator

Learning Objective(s)

1. Be able to code stack, queues, and priority queues
2. Create different types of testing data to different types of situations
3. Introduction to optimization of a hard drive

Overview of the Challenge

To optimize the hard drive, the main concern in the movement of the read/write head from different tracks. The most optimized solution will get all possible request in a increasing manner. This is similar to how a good elevator will work. Your job is not to developed an optimized scheduling of track requests, but to see how it performs with three different data structures (stacks, queues, and priority queues) to see which might perform better. You need to track the number of times the read/write head changes direction.
Example If the requests where handled in the following order: 2, 5, 8, 4, 3, 6. It would change directions two times (one from increasing to decreasing (8 to 4) and then one from decreasing to increasing (3 to 6).

Specifics:

• You need to create your own data files (reading in integers, one per line).
• A -2 indicates that all currently queued up requests should be processed before reading any more.
• The drive should be initially loaded with three requests (less if -1 or eof is encountered) before processing any.
• After processing one request (i.e. the next track), the next request (if not eof or not -1) should be added to the waiting list. Then 3 more should be loading (with a -1 or eof stopping the loading)
• Output each track number as it is processed.
• When done, output the number of changes in directions made.
• Run with the same input for a stack and a queue
• You must use an array to implement the queue
• You must use a linked list to implement the stack.
• Your implementations of stacks and queues need to handle faults by correctly throwing exceptions.

Complete example (with one number per line and using a queue)

Data: 2, 3, 8, 5, 3, -1, 4, 3, -1, -2, 5, 6, 10, 15, 6, -1, -2, 5, 1

1. First add 2, 3, and 8 to the queue
2. Enter the loop
3. Add 5, 3 to the queue (stopping because a -1 is encountered)
4. Remove 2 from the queue (since was at 0, it is going in an increasing direction)
5. Add 4 to queue (now at 3, 8, 5, 3, 4)
6. Start at the beginning of the loop and add "three numbers" (only 3 because -1 encountered). Queue is now 3, 8, 5, 3, 4, 3
7. Remove 3 from queue (increasing so no change in direction). (Queue is now 8, 5, 3, 4, 3)
8. Read the -2 → time to empty the queue (take no more requests until the queue is empty)
   1. Remove 8 . Still increasing
   2. Remove 5. Since going from 8 down to 5 → now decreasing → one change in direction
   3. Remove 3. Still decreasing
   4. Remove 4. Now increasing → another change in direction
   5. Remove 3. Now decreasing → third change in direction
9. Back to start of loop → add three numbers to queue (5, 6, 10)
10. Remove 5 from queue → Now increasing → fourth change in direction
11. Add 15 to queue
12. Start of loop → add "three numbers" (only 6 because of -1) to queue → now 6, 10, 15, 6
13. Process 6 from queue → still increasing
14. Read -2 → time to empty queue
    1. Remove 10 from queue → still increasing
    2. Remove 15 from queue → still increasing
    3. Remove 6 from queue → decreasing → fifth change in direction
15. Start of loop → add "three numbers" (only 5, 1 because of end of file)
16. Process 5 → still decreasing
17. No change to queue because end of file (but queue not empty)
18. Start of loop → add "three numbers" (none because at end of file)
19. Process 1 → still decreasing
20. No change to queue because end of file
21. End loop (end of file and queue is empty)
22. There were five changes in direction

Design components

Refer to the software design/development report for additional details. For the design component of this lab, pay special attention to:

• A quality set of testing data. This should include many different types of situations as possible and the results you expect
• Try to have a somewhat accurate estimate of how long you think it will take to code your design.
• An estimation of which data type is better under which situations.

Optional improvements

Any/all of these can be added to your program for extra credit. But do not attempt them until your program (including the write up) is complete and receiving at least a 90%. Extra credit will only be given to those programs that receive at least a 90% on all the required work. It is much more important to do the required work well than to do the extra credit. Typically, extra credit work is also done on your own with limited (typically no) help from the instructor. The options are listed in order of importance. While you may implement any/all in any order, the order listed will focus you on the more important items first

1. Add the use of priority queues. Have two queues. one that is "increasing" and one that is "decreasing" (hint: negative numbers). If the next track to be added is helpful in your current direction, add it to that priority queue, otherwise added to the second one. When you change directions swap around the priority queues.
2. Track when a track request went in (the sequence number) and when it came out. The difference is "how long it waited". Analyze the results based on the average and maximum wait in addition to the number of times it changes directions.
3. Have the file be specified at the command line