Operating Systems Lecture Notes
Lecture 16
Disk Scheduling

Martin C. Rinard

• The processes running on a machine may have multiple outstanding requests for data from the disk. In what order should requests be served?
• First-Come-First-Served. This is how nachos works right now. As processes arrive, they queue up for the disk and get their requests served in order. In current version of nachos, queueing happens at the mutex lock.
• What is wrong with FCFS? May have long swings from one part of disk to another. It makes sense to service outstanding requests from adjacent parts of disk sequentially.
• Shortest-Seek-Time-First. Disk scheduler looks at all outstanding disk requests, and services the one closest to where the disk head currently is. Sort of like Shortest-Job-First task scheduling.
• What is the problem with SSTF? Starvation. A request for a remote part of the disk may never get serviced.
• SCAN algorithm. Head goes from one end of disk to another. Reverses direction when hits end of disk and goes back the other way. Eliminates starvation problem. Minor variant: C-SCAN, which goes all the way back to front of disk when it hits the end, sort of like a raster scan in a display.
• LOOK algorithm. Like scan, but reverse direction when hit the last request in the current direction. C-LOOK is the circular variant of LOOK. What most systems use in practice.

Permission is granted to copy and distribute this material for educational purposes only, provided that the following credit line is included: "Operating Systems Lecture Notes, Copyright 1997 Martin C. Rinard." Permission is granted to alter and distribute this material provided that the following credit line is included: "Adapted from Operating Systems Lecture Notes, Copyright 1997 Martin C. Rinard."