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."
Martin Rinard, rinard@lcs.mit.edu, www.cag.lcs.mit.edu/~rinard
8/22/1998