Disk Scheduling

Disk Scheduling

Disk requests include the disk address, memory address, number of sectors to transfer, and whether the request is for reading or writing. When one request is completed, the operating system chooses which pending request to service next. Any one of the several disk scheduling algorithms can be used to make this choice.

1. FCFS Scheduling

This algorithm is fair, but it generally does not provide the fastest service. Consider, a disk queue with requests for I/O to blocks on cylinders.

A total of head movement of 640 cylinders. There are wild swings of the head movement.

2. SSTF Scheduling

Shortest Seek Time First scheduling is more efficient, but may lead to starvation if a constant stream of requests arrives for the same general area of the disk. The SSTF algorithm selects the requests with the least seek time from the current head position.

SSTF reduces the total head movement to 236 cylinders, down from 640 required for the same set of requests under FCFS. However that the distance could be reduced still further to 208 by starting with 37 and then 14 first before processing the rest of the requests.

3. SCAN Scheduling

This algorithm is sometimes called the elevator algorithm. In this algorithm, the disk arm starts at one end of the disk and moves towards the other end. The direction of head movement has to be known in addition to the head’s current position.

Under the SCAN algorithm, If a request arrives just ahead of the moving head then it will be processed right away, but if it arrives just after the head has passed, then it will have to wait for the head to pass going the other way on the return trip. This leads to a fairly wide variation in access times which can be improved upon.

4. C-SCAN Scheduling

The Circular-SCAN algorithm improves upon SCAN by treating all requests in a circular queue fashion - Once the head reaches the end of the disk, it returns to the other end without processing any requests, and then starts again from the beginning of the disk.

5.  LOOK Scheduling

LOOK scheduling improves upon SCAN by looking ahead at the queue of pending requests, and not moving the heads any farther towards the end of the disk than is necessary. 

6. Selection of a Disk-Scheduling Algorithm

With very low loads all algorithms are equal, since there will normally only be one request to process at a time.

For slightly larger loads, SSTF offers better performance than FCFS, but may lead to starvation when loads become heavy enough.

For busier systems, SCAN and LOOK algorithms eliminate starvation problems.

Requests for disk service can be greatly influenced by the file-allocation method. The location of directories and index blocks are also important.