Chapter 7, Device Management, Ida A. Flynn and Ann McIver McHoes, Understanding Operating Systems, Second Edition, PWS Publishing Company (1993)

Lesson B: Optical Disk Storage, Access Time Required, Fixed Head Devices, Movable Head Devices, Components of the I/O Subsystem, Communication Among Devices, Management of I/O Requests, Device Handler Seek Strategies, Search Strategies: Rotational Ordering

Problem 4.  Given that it takes 1 ms to travel from one track to the next, and that the arm is originally positioned at track 15 moving toward the low-numbered tracks, compute how long it will take to satisfy the following requests ( 4, 40, 11, 35, 7, 14 ) using the SCAN scheduling policy.  Ignore rotational time and transfer time; just consider seek time.  How does your result compare to the one in Figure 7.15?

Under the SCAN policy, the arm moves from one extreme track to the other extreme track.   We are told that the arm is originally positioned at track number 15.  We are not told how many tracks exist on the disk under consideration.  Because track 40 is in the request list, we know either at least 41 tracks exist.  Assume there are only 41 tracks, numbered 0 through 40.

Assume that all requests in the list ( 4, 40, 11, 35, 7, 14 ) are present when the arm begins motion.  We are told that the arm is moving from track 15 to track 0.   Assume no new requests are received after the arm begins in motion.

The order in which tracks are visited are:  ((15), 14, 11, 7, 4, 0, 35, 40).

Compute the seek time to satisfy the requests.

Caution about making conclusions from this example.  It did make a difference for this example, and it is good to see that differences exist.  However, the need is to examine performance over a large number of track requests that are received over time.   Over a large number of requests received over time, I do not expect a significant difference to exist between a decision to initially search up compared to a decision to initially search down.

If you use the LOOK algorithm belonging to the request list that generated Fig. 7-15, but initially go down instead of up, the number of tracks transited is 47, yielding a smaller average number of tracks transited per requested move.  This is the proper algorithm to compare to Problem 7.4 if your goal is to choose between the two techniques.

Problem 5.  Interactive systems must respond quickly to users.  Minimizing the variance of response time is an important goal, but it does not always prevent an occasional user from suffering indefinite postponement.  What mechanism would you incorporate into a disk scheduling policy to counteract this problem and still provide reasonable response time to the user population as a whole?

1. You could include aging of a request into the priority system.  This would increase the amount of data you collect, and increase the processing time devoted to the scheduler.
2. You could schedule the arm to make a sweep periodically to satisfy extreme track requests.  The strategy could be determined by studying the effect of such a policy on average job turnaround time for the system, or other measure of effectiveness appropriate to the computer center.
3. You could implement the C-LOOK policy.

Author's Answer:  The use of C-LOOK combined with rotational optimization would provide very good service under medium to heavy loads, although its efficiency would probably be wasted under light loads.

Rotational optimization is supported in some disk controllers by providing a way for the software to inspect the current sector number under the read/write head.  For example, if two or more requests of the same cylinder are pending, the driver can issue a request for the sector that will pass under the read/write head next, thus optimizing rotational delay within that track.  In addition, when there are requests for multiple surfaces in the same cylinder, the consecutive requests for different surfaces can be satisfied without penalty because the controller can immediately activate any of the read/write heads wince this does not require arm motion or rotation.

Problem 7.  Under very light loading conditions, every disk scheduling policy discussed in this chapter tends to approximate one of the policies discussed in this chapter.  Which one is it and why?

First Come First Served.  If you have only one request at a time to schedule, the Shortest Seek Time First (SSTF), LOOK and C-LOOK algorithms become the FCFS algorithm.   The SCAN, N-Step SCAN and C-SCAN algorithms are wasteful.  The author remarks that SCAN is similar to SSTS in throughput and mean service times.  This observation requires a system to be busier than just one request at a time.

Problem 10.  Track requests are not usually equally or evenly distributed.  For example, the tracks where the disk directory resides are accessed more often than those where the user's files reside.  Suppose that you know that 50 percent of the requests are for a small fixed number of cylinders.

1. Which one of the scheduling policies presented in this chapter would be "the best" under these conditions?

The C-SCAN is a good contender when file directory tracks are near the outside edge and are updated every time a file access.  With this strategy, you batch track visits.   There is a choice and risk involved in when to actually write the updated directory information.  Without batching, and requiring directory data to be updated as part of a critical region operation for that file, you slow the system.  When the system is used in an adverse environment or by novice users, the very conservative approach is warranted.  When the system is part of a reliable system, this is not a good choice.

Author's Answer:  It depends on where in the disk these heavily requested files are stored.  For example, if they are located in the mid-range numbered cylinders (in the case of cylinders numbered 0-399, mid-range could be defined as cylinders 150 to 250), then LOOK would be the "best" scheduling policy because the arm travels twice through the mid-range cylinders: once on its way toward the center of the disk, and a second time on its way toward the rim of the disk.

2. Can you design one that would be better?

Put the directory on centrally located tracks if you require that they be updated every time a file is accessed.

If the directory is not required to be updated every time a file is accessed, then place the directory near the home position of the arm.

In a more sophisticated system, have the directory near the arm home position, and keep a working copy of the directory in memory.  Update the directory on the disk during quiescent periods.

Author's Answer:  Consider the probability factor in the design of the scheudling policy.  It may be possible to "flag" requests to those highly used cylinders, making them high priority requests thus satisfying them first.  Or, it may be possible to always position the read/write heads at those cylinders after a long list of requests has been satisfied, again giving them special treatment.