Linux Kernel I/O Schedulers Explained: NOOP, CFQ, Deadline & Anticipatory

Introduction

The Linux kernel includes four I/O schedulers: NOOP , Anticipatory , Deadline , and CFQ (Completely Fair Queuing). Disk read/write latency is primarily caused by mechanical head movement; the kernel mitigates this through caching and I/O scheduling algorithms.

I/O Scheduler Concepts

When data blocks are written to or read from a device, requests are placed in a queue awaiting completion.

Each block device has its own request queue.

The I/O scheduler maintains queue order to utilize the media more efficiently, turning unordered I/O operations into ordered ones.

The kernel must first determine the number of requests in the queue before scheduling begins.

I/O Scheduler Purpose and Position

The I/O scheduler decides the submission order of block device I/O operations with two goals: increase I/O throughput and reduce I/O response time. These goals often conflict, so multiple algorithms adapt to different workloads. For database random read/write workloads, Deadline is considered most beneficial.

Each block device or partition has a request_queue, and each queue can select an I/O scheduler to coordinate submitted requests. The scheduler sorts requests by sector number to minimize head movement. Internally, each scheduler maintains its own queues; the request at the front is moved to the device's request queue for service.

Two primary techniques are used:

Merging : adjacent requests to neighboring sectors are combined into a single request.

Sorting : requests are ordered by the disk's rotation direction.

The scheduler balances merging and sorting while avoiding excessive delay for individual requests.

1. NOOP Scheduler

NOOP (No Operation) uses a simple FIFO queue: requests are processed in arrival order. It performs merging when possible; otherwise it attempts to insert the new request at a suitable sorted position. If the queue contains only old requests, the new request is appended to the end. NOOP does not optimize for seek time, making it unsuitable for traditional rotating disks but ideal for SSDs, NAS devices with intelligent controllers, workloads where the application already optimizes I/O order, and scenarios where request order must not be altered.

2. CFQ (Completely Fair Queuing)

CFQ assigns each process its own request queue and a time slice. During its time slice, a process can submit read/write requests to the underlying block device. When the time slice expires, the process's queue is suspended. Time slice length and queue length depend on the process's I/O priority, which has three classes:

RT (real time)

BE (best effort)

IDLE (idle)

RT and BE each have 8 sub-priorities, configurable via ionice. Higher priority processes get earlier service, larger time slices, and more requests processed per slice.

Only synchronous requests (read or sync write) are associated with a process and placed in its private queue. Asynchronous requests of the same priority share a common queue, resulting in 8 (RT) + 8 (BE) + 1 (IDLE) = 17 async queues.

Since Linux 2.6.18, CFQ has been the default I/O scheduler. It is a good general-purpose choice for typical servers, but the article stresses that benchmarking under the specific workload is essential.

3. Deadline Scheduler

Deadline addresses the starvation problem inherent in CFQ by adding dedicated FIFO queues for read and write I/O alongside CFQ's sorted queue.

Read FIFO maximum wait time: 500 ms (configurable).

Write FIFO maximum wait time: 5 s (configurable).

Priority order: FIFO(Read) > FIFO(Write) > CFQ sorted queue .

Deadline guarantees minimal latency for a given request, making it suitable for decision support systems (DSS). It improves on the Elevator algorithm by:

Preventing requests from waiting indefinitely.

Differentiating read and write operations.

Deadline maintains three queues:

A sector-sorted queue (like Elevator).

A read FIFO queue ordered by submission time.

A write FIFO queue ordered by submission time.

Reads receive higher priority because applications typically block waiting for read results, whereas writes often return after copying to memory (async writeback). Each new request enters the sorted queue and the tail of the appropriate FIFO queue. The scheduler processes the sorted queue while checking the FIFO heads; if a request exceeds its timeout (read 5 ms threshold mentioned in the detailed walkthrough, write 5 s ), it is serviced immediately.

Author's note: For partitions hosting database change logs (e.g., Oracle online logs, MySQL binlog) where fsync is frequently called, Deadline may not be ideal because incomplete writes can significantly impact application performance.

4. Anticipatory Scheduler

CFQ and Deadline optimize for random I/O but do not specifically optimize sequential reads. Anticipatory builds on Deadline by adding a 6 ms anticipation window for each read I/O. If a read request for an adjacent sector arrives within this window, it is served immediately, benefiting mixed random/sequential workloads.

Summary and Recommendations

I/O scheduler selection depends on both hardware characteristics and application workload:

Traditional SAS disks : CFQ, Deadline, and Anticipatory are all viable choices.

Dedicated database servers : Deadline offers strong throughput and latency.

SSDs / Fusion-io : The simplest scheduler, NOOP , often performs best because the other three optimize for seek time reduction, which is irrelevant on solid-state media with negligible access latency.