Deadline scheduler

The deadline scheduler is an I/O scheduler for the Linux kernel which was written in 2002 by Jens Axboe.

Overview

The main goal of the Deadline scheduler is to guarantee a start service time for a request. It does so by imposing a deadline on all I/O operations to prevent starvation of requests. It also maintains two deadline queues, in addition to the sorted queues (both read and write). Deadline queues are basically sorted by their deadline (the expiration time), while the sorted queues are sorted by the sector number.

Before serving the next request, the deadline scheduler decides which queue to use. Read queues are given a higher priority, because processes usually block on read operations. Next, the deadline scheduler checks if the first request in the deadline queue has expired. Otherwise, the scheduler serves a batch of requests from the sorted queue. In both cases, the scheduler also serves a batch of requests following the chosen request in the sorted queue.

By default, read requests have an expiration time of 500 ms, write requests expire in 5 seconds.

An early version of the scheduler was published by Jens Axboe in January 2002.

Measurements have shown that the deadline I/O scheduler outperforms the CFQ I/O scheduler for certain multithreaded workloads.

sysfs tunables

fifo_batch (integer)

Deadline executes I/O Operations (IOPs) through the concept of "batches" which are sets of operations ordered in terms of increasing sector number. This tunable determines how big a batch will have to be before the requests are queued to the disk (barring expiration of a currently-being-built batch). Smaller batches can reduce latency by ensuring new requests are executed sooner (rather than possibly waiting for more requests to come in), but may degrade overall throughput by increasing the overall movement of drive heads (since sequencing happens within a batch and not between them). Additionally, if the number of IOPs is high enough the batches will be executed in a timely fashion anyway.

read_expire (integer)

The ‘read_expire’ time is the maximum time in milliseconds after which the read is considered ‘expired’. Think of this more like the expiration date on a milk carton. The milk is best used before the expiration date. The same with the deadline scheduler. It will NOT attempt to make sure all IO is issued before its expiration date. However, if the IO is past expiration, then it gets a bump in priority…. with caveats.

The read expiration queue is ONLY checked when the deadline scheduler re-evaluates read queue. For reads this means every time a sorted read is dispatched EXCEPT for the case of streaming io. While the scheduler is streaming io from the read queue, the read expired is not evaluated. When re-evaluating the read queue, the logic is

check for expired reads (look at head of FIFO ime orderedqueue)
check to see if cached read pointer valid (so even if not streaming, the cached pointer still takes precedence so the sorted queue is traversed tip to tail in a sweep)
pick up the first read from the sorted queue (start at the tip again for another sweep)
If there are expired reads, then the first one is pulled from the FIFO. Note that this expired read then is the new nexus for read sort ordering. The cached next pointer will be set to point to the next io from the sort queue after this expired one…. The thing to note is that the algorithm doesn’t just execute ALL expired io once they are past their expiration date. This allows some reasonable performance to be maintained by batching up ‘write_starved’ sorted reads together before checking the expired read queue again.

So, the maximum number of io that can be performed between read expired io is 2 * 'fifo_batch' * 'writes_starved'. One set of ‘fifo_batch’ streaming reads after the first expired read io and if this stream happened to cause the write starved condition, then possibly another ‘fifo_batch’ streaming writes. This is worse case, after which the read expired queue would be re-evaluated. At best, the expired read queue will be evaluated ‘write_starved’ times in a row before being skipped because the write queue would be used.

write_expire (integer)

Identical to read_expire but for write operations (grouped into separate batches from reads).

writes_starved (integer)

As stated previously, deadline prefers reads to writes. As a consequence, this can lead to situations where the operations are executed are almost entirely reads. This becomes more of an important tunable as write_expire is elongated or overall bandwidth approaches saturation. Decreasing this gives more bandwidth to writes (relatively speaking) at the expense of read operations. If application workload, however, is read-heavy (for example most HTTP or directory servers) with only an occasional write, decreased latency of average IOPs may be achieved by increasing this (so that more reads must be performed before a write batch is queued to disk).

front_merges (bool integer)

A "front merge" is an operation where the I/O Scheduler, seeking to condense (or "merge") smaller requests into fewer (larger) operations, will take a new operation then examine the active batch and attempt to locate operations where the beginning sector is the same or immediately after another operation's beginning sector. A "back merge" is the opposite, where ending sectors in the active batch are searched for sectors that are either the same or immediately after the current operation's beginning sectors. Merging diverts operations from the current batch to the active one, decreasing "fairness" in order to increase throughput.

Due to the way files are typically laid out, back merges are much more common than front merges. For some workloads, you may even know that it is a waste of time to spend any time attempting to front merge requests. Setting front_merges to 0 disables this functionality. Front merges may still occur due to the cached last_merge hint, but since that comes at basically zero cost, it is still performed. This boolean simply disables front sector lookup when the I/O scheduler merging function is called. Disk merge totals are recorded per-block device in /proc/diskstats.

Other I/O schedulers

* CFQ scheduler
* Anticipatory scheduler
* Noop scheduler

References

{{Reflist

Disk scheduling algorithms