The I/O scheduler optimizes disk
access. Issuing each request directly to the disk results in a bad
throughput, because this strategy would cause a high amount of
small requests, where in the worst case each request demands a
completely different disk area. Today data transfer rates
from physical disks are very high, so transfer times are very
short. The dominating part of the access time is the disk latency,
mainly caused by disk head movements of about 8 ms in average. The
strategy for optimization aims at minimizing the number of I/O
operations and disk head movements.
I/O schedulers mostly implement two functions:
Request merging
merges two adjacent requests to one request
Elevator
orders the requests to minimize seek times considering the physical data location
(seek time is the duration of a head movement to reach an addressed sector).
A "Prevent starvation" functionality is required, which ensures
that requests which are not in the 'seek reducing' order are served in an
adequate time frame. Here the various I/O schedulers have different strategies.
The noop scheduler implements only the request merging
function.
Deadline scheduler
The deadline scheduler implements request merging,
the elevator and in addition tries to prevent request
starvation (which can be caused by the elevator algorithm)
by introducing a deadline for each request. In addition,
it prefers readers. Linux does not delay write processes
until their data are really written to the disk, because
it caches the data, while readers have to wait until
their data are available.
Anticipatory scheduler ("as scheduler")
The anticipatory scheduler implements request merging,
the elevator and in addition optimizes for physical
disks by avoiding too many head movements. It tries
to solve situations where many write requests are interrupted
by a few read requests. After a read operation it waits
for a certain time frame for another read and doesn't
switch back immediately to write requests. This scheduler
is not intended to use for storage servers!
Complete fair queuing scheduler ("cfq scheduler")
The complete fair queuing scheduler implements request merging, the elevator and in
addition embarks on the strategy to allow all
users of a particular drive about the same number of
I/O requests over a given time.
