Disk Scheduling

Disk Scheduling Algorithms

In a multiprogramming system, processes may continually request disk reads and writes. Since requests sometimes arrive faster than a disk can respond, each disk needs a waiting queue. Disk scheduling algorithms aim to improve disk access performance, generally by optimizing the order of requests.

Assume the request sequence is 98, 183, 37, 122, 14, 124, 65, 67, with each number identifying a track. The head initially sits at track 53.

First Come First Served (FCFS)

FCFS is simple and straightforward. However, when many processes compete for a disk, requested tracks may be widely scattered, and long seek times can make its performance poor.

Shortest Seek Time First (SSTF)

SSTF chooses the request requiring the shortest seek from the current head position.

SSTF can starve some requests, giving users unequal opportunities for service. The head may move back and forth within a small region, causing large variations in response time and making some requests' response times unpredictable.

SCAN

To prevent SSTF starvation, the head can be required to move in one direction, serving outstanding requests until it reaches the last track in that direction before reversing. This is also called elevator scheduling: an elevator moves in one direction before reversing; SCAN reverses at the disk boundary.

SCAN performs well and can prevent prolonged starvation when requests can continue to be processed. However, tracks near the middle have an advantage: they are visited more frequently than other tracks, so service frequency varies by position.

Circular Scan (CSCAN)

CSCAN serves requests only while the head moves in a particular direction. On the return trip it moves directly to the opposite edge, resetting the head. This still takes head movement time, and no requests are served along the return trip.

CSCAN serves requests in only one direction and gives tracks at different positions relatively more uniform service frequency than SCAN.