5.7. Disk Scheduling

  • File systems must be accessed in an efficient manner, especially with hard drives, which are the slowest part of a computer.
  • As a computer deals with multiple processes over a period of time, a list of requests to access the disk builds up. For efficiency purposes, all requests (from all processes) are aggregated together.
  • The technique that the operating system uses to determine which requests to satisfy first is called disk scheduling

5.7.1. First-Come, First-Served Disk Scheduling

In FCFS, we process the requests in the order they arrive, without regard to the current position of the heads.

Horrible performance

5.7.2. Shortest Seek Time first (SSTF) Disk-Scheduling

The shortest-seek-time-first (SSTF) disk-scheduling algorithm moves the heads the minimum amount it can to satisfy any pending request.

Suffers from starvation

5.7.3. SCAN Disk Scheduling

  • An elevator is designed to visit floors that have people waiting. In general, an elevator moves from one extreme to the other (say, the top of the building to the bottom), servicing requests as appropriate.
  • The SCAN disk-scheduling algorithm works in a similar way, except instead of moving up and down, the read/write heads move in toward the spindle, then out toward the platter edge, then back toward the spindle, and so forth.

5.7.4. In Class Example

A disk system has 100 cylinders, numbered 0 to 99. Assume that the read / write head is at cylinder 50 and determine the order of head movement for each algorithm to satisfy the following stream of requests. For comparison purposes, calculate the total head travel distance. They are listed in the order received.

40, 12, 22, 66, 67, 33, 80, 75, 85, 65, 8