Disk Arm Scheduling Algorithms (see Fig. 5.18)

Figure 5.18: From left to right: First-in, First-out (FIFO); Shortest Seek Time First; Elevator Algorithm (SCAN); Modified Elevator (Circular SCAN, C-SCAN)

• Time required to read or write a disk block determined by 3 factors; Seek time, Rotational delay, Actual transfer time
• Seek time dominates
• For a single disk, there will be a number of I/O requests
• Processing them in random order leads to worst possible performance
• First-in, First-out (FIFO)
  • Process requests as they come
  • Fair (no starvation)
  • Good for a few processes with clustered requests
  • Deteriorates to random if there are many processes
• Shortest Seek Time First
  • Select request that minimises the seek time
  • Generally performs much better than FIFO
  • May lead to starvation
• Elevator Algorithm (SCAN)
  • Move head in one direction; Services requests in track order until it reaches the last track, then reverses direction
  • Better than FIFO, usually worse than SSTF
  • Avoids starvation
  • Makes poor use of sequential reads (on down-scan)
• Modified Elevator (Circular SCAN, C-SCAN)
  • Like elevator, but reads sectors in only one direction; When reaching last track, go back to first track non-stop
  • Better locality on sequential reads
  • Better use of read ahead cache on controller
  • Reduces max delay to read a particular sector
• Selecting a Disk-Scheduling Algorithm
  • SSTF common, natural appeal
  • SCAN and C-SCAN perform better if heavy load on disk
  • Performance depends on number and types of requests
  • Requests for disk service influenced by file-allocation method
  • Disk-scheduling should be separate module of OS, allowing replacement with different algorithm if necessary