IBM 10 SP1 EAL4 User Manual
application, the I/O scheduler is considered an important kernel component in the I/O path. SLES includes
four I/O scheduler options to optimize system performance.
four I/O scheduler options to optimize system performance.
5.1.7.1 Deadline I/O scheduler
The deadline I/O scheduler available in the Linux 2.6 kernel incorporates a per-request expiration-based
approach, and operates on five I/O queues. The basic idea behind the implementation is to aggressively
reorder requests to improve I/O performance, while simultaneously ensuring that no I/O request is being
starved. More specifically, the scheduler introduces the notion of a per-request deadline, which is used to
assign a higher preference to read than write requests.
As stated earlier, the deadline I/O scheduler maintains five I/O queues. During the enqueue phase, each I/O
request gets associated with a deadline, and is inserted into I/O queues that are either organized by starting
block (a sorted list) or by the deadline factor (a first-in-first-out [FIFO]) list. The scheduler incorporates
separate sort and FIFO lists for read and write requests, respectively. The fifth I/O queue contains the requests
that are to be handed off to the device driver. During a dequeue operation, in the case that the dispatch queue
is empty, requests are moved from one of the four I/O lists (sort or FIFO) in batches. The next step consists
of passing the head request on the dispatch queue to the device driver.
The logic behind moving the I/O requests from either the sort or the FIFO lists is based on the scheduler’s
goal to ensure that each read request is processed by its effective deadline without actually starving the
queued-up write requests. In this design, the goal of economizing on the disk seek time is accomplished by
moving a larger batch of requests from the sort list, which is sector sorted, and balancing it with a controlled
number of requests from the FIFO list.
approach, and operates on five I/O queues. The basic idea behind the implementation is to aggressively
reorder requests to improve I/O performance, while simultaneously ensuring that no I/O request is being
starved. More specifically, the scheduler introduces the notion of a per-request deadline, which is used to
assign a higher preference to read than write requests.
As stated earlier, the deadline I/O scheduler maintains five I/O queues. During the enqueue phase, each I/O
request gets associated with a deadline, and is inserted into I/O queues that are either organized by starting
block (a sorted list) or by the deadline factor (a first-in-first-out [FIFO]) list. The scheduler incorporates
separate sort and FIFO lists for read and write requests, respectively. The fifth I/O queue contains the requests
that are to be handed off to the device driver. During a dequeue operation, in the case that the dispatch queue
is empty, requests are moved from one of the four I/O lists (sort or FIFO) in batches. The next step consists
of passing the head request on the dispatch queue to the device driver.
The logic behind moving the I/O requests from either the sort or the FIFO lists is based on the scheduler’s
goal to ensure that each read request is processed by its effective deadline without actually starving the
queued-up write requests. In this design, the goal of economizing on the disk seek time is accomplished by
moving a larger batch of requests from the sort list, which is sector sorted, and balancing it with a controlled
number of requests from the FIFO list.
5.1.7.2 Anticipatory I/O scheduler
The design of the anticipatory I/O scheduler attempts to reduce the per-thread read response time. It
introduces a controlled delay component into the dispatching equation. The delay is invoked on any new
request to the device driver, thereby allowing a thread that just finished its I/O request to submit a new
request.
Implementation of the anticipatory I/O scheduler is similar to, and may be considered as, an extension to the
deadline scheduler. In general, the scheduler follows the basic idea that if the disk drive just operated on a
read request, the assumption can be made that there is another read request in the pipeline, and hence it is
worthwhile to wait. The I/O scheduler starts a timer, and at this point, there are no more I/O requests passed
down to the device driver. If a close read request arrives during the wait time, it is serviced immediately, and
in the process, the actual distance that the kernel considers as close grows as time passes, which is the
adaptive part of the heuristic. Eventually the close requests dry out, causing the scheduler to submit some of
the write requests, converging back to what is considered a normal I/O request dispatching scenario.
introduces a controlled delay component into the dispatching equation. The delay is invoked on any new
request to the device driver, thereby allowing a thread that just finished its I/O request to submit a new
request.
Implementation of the anticipatory I/O scheduler is similar to, and may be considered as, an extension to the
deadline scheduler. In general, the scheduler follows the basic idea that if the disk drive just operated on a
read request, the assumption can be made that there is another read request in the pipeline, and hence it is
worthwhile to wait. The I/O scheduler starts a timer, and at this point, there are no more I/O requests passed
down to the device driver. If a close read request arrives during the wait time, it is serviced immediately, and
in the process, the actual distance that the kernel considers as close grows as time passes, which is the
adaptive part of the heuristic. Eventually the close requests dry out, causing the scheduler to submit some of
the write requests, converging back to what is considered a normal I/O request dispatching scenario.
5.1.7.3 Completely Fair Queuing scheduler
The Completely Fair Queuing (CFQ) I/O scheduler can be considered an extension to the Stochastic Fair
Queuing (SFQ) scheduler implementation. The focus of both implementations is on the concept of fair
allocation of I/O bandwidth among all the initiators of I/O requests. The actual implementation utilizes n
(normally 64) internal I/O queues, as well as a single I/O dispatch queue.
During an enqueue operation, the PID of the currently running process (the actual I/O request producer) is
utilized to select one of the internal queues, which is normally hash-based, and, hence, the request is inserted
into one of the queues in FIFO order. During dequeue, it calls for a round-robin based scan through the non-
empty I/O queues, and selects requests from the head of the queues. To avoid encountering too many seek
operations, an entire round of requests is first collected, sorted, and ultimately merged into the dispatch queue.
Next, the head request in the dispatch queue is passed to the actual device driver. The CFQ I/O scheduler
implements time sharing, in which the processes possess time slices during which they can dispatch I/O
Queuing (SFQ) scheduler implementation. The focus of both implementations is on the concept of fair
allocation of I/O bandwidth among all the initiators of I/O requests. The actual implementation utilizes n
(normally 64) internal I/O queues, as well as a single I/O dispatch queue.
During an enqueue operation, the PID of the currently running process (the actual I/O request producer) is
utilized to select one of the internal queues, which is normally hash-based, and, hence, the request is inserted
into one of the queues in FIFO order. During dequeue, it calls for a round-robin based scan through the non-
empty I/O queues, and selects requests from the head of the queues. To avoid encountering too many seek
operations, an entire round of requests is first collected, sorted, and ultimately merged into the dispatch queue.
Next, the head request in the dispatch queue is passed to the actual device driver. The CFQ I/O scheduler
implements time sharing, in which the processes possess time slices during which they can dispatch I/O
52