Completely fair queueing

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Completely Fair Queuing (CFQ) is a Linux I/O scheduler created in 2003 by Jens Axboe. It organizes disk requests into per‑process queues for synchronous I/O and gives each queue a time slice to access the disk. The time slice and how many requests a queue can send depend on the process’s I/O priority. Asynchronous requests from all processes are grouped into a few queues, one per priority. CFQ doesn’t use explicit anticipatory scheduling, but it can boost overall throughput by letting a queue idle after finishing synchronous I/O, effectively “anticipating” more I/O from that process.

History in brief: Andrea Arcangeli proposed a stochastic fair queueing idea in 2003, which Axboe implemented and patched for the kernel. CFQ was added to the mainline kernel as an optional scheduler and could be chosen at boot with the elevator parameter. Red Hat Enterprise Linux 4 used CFQ by default on a 2.6.9-based kernel. CFQ version 2 (CFQv2) appeared in 2.6.10 with better responsiveness and fewer starvation issues. It could be switched at runtime via /sys/block//queue/scheduler. A later CFQ design, CFQv3, introduced true time-slicing and per‑process priorities (ioprio_get(2) and ioprio_set(2), typically set with ionice). CFQ became the default scheduler, replacing the anticipatory scheduler, and it eventually evolved into Budget Fair Queueing (BFQ).