Understanding Linux I/O Schedulers: NOOP, CFQ, Deadline, and Anticipatory

Linux kernel includes four I/O schedulers: Noop, Anticipatory, Deadline, and CFQ.

anticipatory: expected; occurring early; looking forward

Disk read/write latency is mainly caused by head movement; the kernel mitigates this with caching and I/O scheduling algorithms.

Scheduling Algorithm 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 queue.

The I/O scheduler maintains the order of these queues to use the medium more efficiently, turning unordered I/O into ordered I/O.

The kernel first determines the total number of requests in the queue before scheduling.

IO Scheduler

IO scheduler is the OS method for deciding the submission order of I/O operations on block devices, aiming to increase throughput and reduce response time.

Because throughput and response time often conflict, multiple algorithms are provided to suit different request patterns; for random read/write workloads such as databases, the Deadline algorithm is most beneficial.

Location of the I/O scheduler in the kernel stack is shown below:

Each block device’s request queue can select an I/O scheduler to coordinate submitted requests.

The basic goal is to arrange requests by sector number to minimize head movement and improve efficiency; requests are served in order.

Schedulers also maintain additional internal queues to process incoming requests, moving the front request to the request queue for response.

The scheduler reduces disk rotation needs via two mechanisms:

Merge

Sort

When a new request arrives, if it is adjacent to an existing one, they can be merged; otherwise, requests are sorted according to disk rotation direction.

1. NOOP

NOOP (No Operation) is a simple FIFO scheduler that processes requests in order, suitable for SSDs where seek time is negligible.

It is also known as the elevator algorithm.

Operation steps:

If requests can be merged, merge them.

If not, attempt to insert in sorted position; if not possible, place at the end.

If neither merge nor suitable position, append to the end of the queue.

Applicable scenarios:

When preserving request order is not required.

Devices with more intelligent scheduling (e.g., NAS storage).

Applications that have already optimized I/O ordering.

Non‑rotational devices such as SSDs.

2. CFQ (Completely Fair Queuing)

CFQ aims to allocate a request queue and time slice to each process competing for a block device, providing fairness.

Time slices and queue lengths depend on the process’s I/O priority (RT, BE, IDLE, with sub‑priorities). Higher priority processes receive more time and earlier service.

Synchronous requests are placed in per‑process queues, while asynchronous requests share a common queue with 17 sub‑queues (8 RT, 8 BE, 1 IDLE).

Since Linux 2.6.18, CFQ is the default scheduler; it is a good choice for general servers, but the optimal algorithm should be selected based on benchmarked workload characteristics.

3. DEADLINE

DEADLINE builds on CFQ to prevent request starvation, providing separate FIFO queues for read and write I/O.

Read FIFO has a maximum wait time of 500 ms, write FIFO 5 s (configurable). Read FIFO has higher priority than write FIFO, which in turn outranks CFQ.

The algorithm maintains three queues: one sorted by physical location (like Elevator) and two time‑sorted queues for reads and writes, ensuring timely processing of both types.

4. ANTICIPATORY

ANTICIPATORY adds a 6 ms wait window after each read request; if a subsequent read to an adjacent sector arrives within this window, it is served immediately, improving performance for mixed random and sequential workloads.

Summary

The choice of I/O scheduler depends on hardware characteristics and workload scenarios. Traditional SAS disks benefit from CFQ, DEADLINE, or ANTICIPATORY, while SSDs often perform best with the simple NOOP scheduler because they lack seek latency.