Disk Scheduling
One of the responsibilities of the operating system is to use the hardware efficiently. For disks this means having fast access time and large disk bandwidth. For magnetic disks, the access time has two major components.
The seek time is the time for the disk arm to move the heads to the cylinder
containing the desired sector.
The rotational latency is the additional time for the disk to rotate the
desired sector to the disk head. The disk bandwidth is the total number
of bytes transferred, divided by the total time between the first request
for service and the completion of the last transfer.
We can improve the access time and bandwidth by managing the order in which disk I/O requests are serviced.
Whenever a process needs I/O to or from the disk, it issues a system call to the OS. The request specifies several pieces of information:
- Whether this operation is input or output
- What the disk address for the transfer is
- What the memory address for the transfer is
- What the number of sectors to be transferred is
If the desired disk drive and controller are available, the request can be serviced immediately. If the drive or controller is busy, any new requests for service will be placed in the queue of pending requests for that drive.
For a multiprogramming system with many processes, the disk queue may often have several pending requests. Thus, when one request is completed, the OS chooses which pending request to service next. How does the OS make this choice? Any one of several disk scheduling algorithm can be used.
First Come, First Served (FCFS) Scheduling
The simplest form of disk scheduling is the first-come, first-served (FCFS) algorithm. The algorithm is intrinsically fair, but it generally does not provide the fastest service.
Example:
Queue for I/O to blocks on cylinders:
cylinders_queue = [98, 183, 37, 122, 14, 124, 65, 67]
HEAD
|
V
0 14 37 53 65 67 98 122 124 183 199
|-----|--------|------|--|--|------------|---|---|-----------------------|-------|
01| x
02| x
03| x
04| x
05| x
06| x
07| x
08| x
09| x
This produces a total of head movements of 640 cylinders.
The swing from 122 to 14 back to 124 shows the waste.
Shortest Seek Time First (SSTF) Scheduling
It seems reasonable to service all the requests close to the current head
position before moving the head far away to service other requests.
This assumption is the basis for the shortest-seek-time-first algorithm
The SSTF algorithm selects the request with the least seek time from the current head position. i.e. it chooses the next pending request closest to the current HEAD position.
Queue for I/O to blocks on cylinders:
cylinders_queue = [98, 183, 37, 122, 14, 124, 65, 67]
HEAD
|
V
0 14 37 53 65 67 98 122 124 183 199
|-----|--------|------|--|--|------------|---|---|-----------------------|-------|
01| x
02| x
03| x
04| x
05| x
06| x
07| x
08| x
09| x
This results in a total head movements of 236.
SSTF scheduling is a form of shortest-job-first (SJF) scheduling. This may cause starvation of some requests. Although, this algorithm is better than FCFS it is still not optimal.
SCAN/LOOK Scheduling
In the SCAN algorithm, the disk arm starts at one end of the disk and moves toward the other end, servicing requests as it reaches each cylinder, until it gets to the other end of the disk. At the other end the direction of head movement is reversed and servicing continues. The head continuously scans back and forth across the disk.
This is sometimes called the elevator algorithm, since the arm behaves
just like an elevator in a building. First servicing all the requests
going up and then reversing to service requests going down.
Queue for I/O to blocks on cylinders:
cylinders_queue = [98, 183, 37, 122, 14, 124, 65, 67]
HEAD
|
V
0 14 37 53 65 67 98 122 124 183 199
|-----|--------|------|--|--|------------|---|---|-----------------------|-------|
01| x
02| x
03| x
04| x
05| x
06| x
07| x
08| x
09| x
SCAN will actually go to 0 and the end. LOOK will check to see if it can switch to the other direction instead of going to the end if it doesn’t need to.
C-SCAN/C-LOOK Scheduling
Circular Scan (C-Scan) scheduling is a variant of SCAN designed to provide a more uniform wait time. Like SCAN, C-SCAN moves the head from one end to another servicing requests along the way. When the head reaches the other end it immediately returns to the beginning of the disk without servicing any requests on the return trip. This essentially treats the disk as a cylinder list that wraps around from the final cylinder to the first one.
Queue for I/O to blocks on cylinders:
cylinders_queue = [98, 183, 37, 122, 14, 124, 65, 67]
HEAD
|
V
0 14 37 53 65 67 98 122 124 183 199
|-----|--------|------|--|--|------------|---|---|-----------------------|-------|
01| x
02| x
03| x
04| x
05| x
06| x
07| x
08| x
09| x
C-SCAN will actually go back to 0 once it reaches the end. C-LOOK will check to see what the next smallest cylinder is when it reaches the max cylinder in the queue.
Selecting a Disk-Scheduling Algorithm
How the fuck do we choose the best one?
SSTF is common and has natural appeal because it increases performance over FCFS. SCAN and C-SCAN perform better for systems that place a heavy load on the disk, because they are less likely to cause a starvation problem.
For any particular list of requests, we can define an optimal order of retrieval, but the computation needed to find an optimal schedule may not justify the savings over SSTF or SCAN.
With any scheduling algorithm performance depends heavily on the number and types of requests.
E.g.
If the queue usually has just one outstanding request. Then all scheduling algorithms behave the same, because they have only one choice of where to move the disk head; they all behave like FCFS scheduling.
Requests for device service can be greatly influenced by the file-allocation method. A program reading a contiguously allocated file will generate several requests that are close together on disk, resulting in limited head movement.
A linked or indexed file may include blocks that are widely scattered on the disk, resulting in greater head movement.
The location of directories and index blocks is also important. Since every file must be opened to be used, and opening a file requires searching the directory structure, the directories will be accessed frequently.
Suppose that a directory entry is on the first cylinder and a file’s data are on the final cylinder. In this case, the disk head has to move the entire width of the disk.
If the directory entry were on the middle cylinder, the head would have to move only one-half the width. Caching the directories and index blocks in main memory can also help to reduce disk-arm movement, particularly for read requests.
Because of these complexities, the disk-scheduling algorithm should be written as a separate module of the operating system, so that it can be replaced with a different algorithm if necessary. Either SSTF or LOOK is a reasonable choice for the default algorithms.
The scheduling algorithms described here consider only the seek distances.
For modern disks, the rotational latency can be nearly as large as the average seek time. It is difficult for the operating system to schedule for improved rotational latency because modern disks do not disclose the physical location of logical blocks. Disk manufacturers have been alleviating this problem by implementing disk-scheduling algorithms in the controller hardware built into the disk drive.
If the operating system sends a batch of requests to the controller, the controller can queue them and then schedule them to improve both the seek time and the rotational latency.
If I/O performance were the only consideration, the operating system would gladly turn over the responsibility of disk scheduling to the disk hardware.
In practice the OS may have other constraints on the service order for requests.
Demand paging may take priority over application I/O and writes are more urgent than reads if the cache is running out of free pages. It may be desirable to guarantee the order of a set of disk writes to make the file system robust int he face of a system crash. What could happen if the operating system allocated a disk page to a file and the application wrote data into that page before the operating system had a chance to flush the file system metadata block to disk. To accommodate such requirements an operating system may choose to do its own disk scheduling and to spoon-feed the requests to the disk controller, one by one, for some type of I/O.