IBM 10 SP1 EAL4 manual Deadline I/O scheduler, Anticipatory I/O scheduler

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.

5.1.7.1Deadline 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.

5.1.7.2Anticipatory 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.

5.1.7.3Completely 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

52