Deadline scheduler

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

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 and also for certain database workloads.

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 anyways.

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.

...
Wikipedia