Carrying out disk accesses in the order they are received will not always produce optimal performance.
Seek time is the reason for differences in performance
For a single disk there will be a number of I/O requests
If requests are selected randomly, we will expect poor performance
Can use priority scheme
Can reduce average access time by sending requests to disk controller in certain order
Disk Scheduling
I/O Scheduling 1
CS@VT Computer Organization II ©2005-2013 McQuain
First-in, first-out (FIFO)
– process request sequentially
– “fair” to all processes
– approaches random scheduling in performance if there are many processes
Request order: 55 58 39 18 90 160 150 38 184
200 150 100
50
FIFO Scheduling
0
0123456789
Total distance head moves: 498
FIFO Scheduling
I/O Scheduling 2
CS@VT Computer Organization II ©2005-2013 McQuain
SSTF: shortest seek (service) time first
– select the disk I/O request that requires the least movement of the disk arm from its current position
– guarantees minimum average seek time, but can lead to starvation
Request order: 55 58 39 18 90 160 150 38 184 Actual order: 90 58 55 39 38 18 150 160 184
200 150 100
50
SSTF Scheduling
0
0123456789
Total distance head moves: 248
SSTF Scheduling
I/O Scheduling 3
CS@VT Computer Organization II ©2005-2013 McQuain
SCAN: “elevator algorithm”
– arm moves in one direction only, satisfying all outstanding requests until it reaches the last track in that direction
– then direction is reversed
Request order: 55 58 39 18 90 160 150 38 184
Actual order:
150 160 184 90 58 55 39 38 18
200 150 100
50
SCAN Scheduling
0
0123456789
Total distance head moves: 250
SCAN Scheduling
I/O Scheduling 4
CS@VT Computer Organization II ©2005-2013 McQuain
C-SCAN:
– restricts scanning to one direction only
– when the last track has been visited in one direction, the arm is returned to the opposite end of the disk and the scan begins again
– more uniform waiting times
– “fairer” than SCAN
Request order: 55 58 39 18 90 160 150 38 184 Actual order: 150 160 184 18 38 39 55 58 90
200 150 100
50
C-SCAN Scheduling
0
0123456789
Total distance head moves: 312
C-SCAN Scheduling
I/O Scheduling 5
CS@VT Computer Organization II ©2005-2013 McQuain
N-step-SCAN
– Segments the disk request queue into subqueues of length N
– Subqueues are processed one at a time, using SCAN
– New requests added to other queue when queue is processed
FSCAN
– Two queues
– One queue is empty for new requests
Other Variations
I/O Scheduling 6
CS@VT Computer Organization II ©2005-2013 McQuain
Comparison
I/O Scheduling 7
CS@VT Computer Organization II ©2005-2013 McQuain
Operating systems are the best place to manage the scheduling of disk accesses.
Problem: high-level interfaces like ATA and SCSI provide the OS with logical block addresses, not physical disk addresses.
Fallacy
I/O Scheduling 8
CS@VT Computer Organization II ©2005-2013 McQuain
FIGURE 6.19 Example showing OS versus disk schedule accesses, labeled host-ordered versus drive-ordered.
The former takes three revolutions to complete the four reads, while the latter completes them in just three-fourths of a revolution (from Anderson [2003]). Copyright © 2009 Elsevier, Inc. All rights reserved.
Host-Ordered vs Drive-Ordered
I/O Scheduling 9
CS@VT Computer Organization II ©2005-2013 McQuain