Why BFQ Is Replacing CFQ: Inside Linux’s New I/O Scheduler

1. What is BFQ?

BFQ (Budget Fair Queueing) is an I/O scheduler introduced in the Linux 4.12 kernel, proposed by Paolo Valente in 2010 to replace the older CFQ scheduler. It treats each disk sector as a "budget" and aims to allocate equal sector counts to all processes, ensuring fair storage access.

2. Advantages of BFQ

The scheduler balances two core metrics—high throughput and low latency—by using the Budget‑based Worst‑case Weighted Fair Queueing (b‑wf2q+) algorithm. It automatically distinguishes batch and interactive processes, guaranteeing quick response for interactive workloads while maintaining high throughput for batch jobs.

In a cold‑start test of the Gaode Map application on a Hikey device (3 read threads, 1 write thread), BFQ achieved the shortest startup time compared with noop, none, and cfq schedulers. Hikey-Tester.sh -sched noop/none/cfq/bfq -r 3 -w 1 Additional throughput experiments under various load models (random reads, sequential reads, mixed reads/writes) show BFQ’s performance equal to or better than other schedulers.

3. Why BFQ Outperforms Other Schedulers

Four main mechanisms give BFQ its edge:

Simple “budget fair” strategy: each process receives a budget of sectors; interactive processes need only a small budget, so they are scheduled frequently, ensuring fast response.

Weight management: a larger weight slows budget growth, causing the process to be scheduled more often.

Temporary weight boost for new processes: newly created processes temporarily receive higher weight to handle burst I/O such as library loading.

Deceptive idleness handling: after a synchronous I/O, BFQ waits a short Twait before expiring the process, preventing throughput loss.

Algorithm Overview (Pseudo‑code)

Key steps in the BFQ algorithm:

add_request: Insert the I/O request into the appropriate BFQ queue, allocate a remaining_budget to the active application, and handle empty queues or deceptive idleness.

dispatch_request: Send the request to the driver, decrement remaining_budget, and if the budget is exhausted, select a new active application.

b‑wf2q insertion: Insert the process queue into BFQ’s red‑black tree, update the global budget counter V, compute finish time F and start time S, and determine eligibility for scheduling.

// Pseudo‑code excerpt (simplified)
add_request(request) {
    // allocate budget, insert into appl.queue
}
dispatch_request(request) {
    // update remaining_budget, possibly expire appl
}
b_wf2q_insert(appl) {
    // insert into RB‑tree, update V, F, S
}

4. Conclusion

The core idea of BFQ is an adaptive budget mechanism: a process’s budget is increased or decreased based on its previous consumption, providing fairness and responsiveness. Additional tricks such as weight boosting, peak‑rate estimation, and deceptive idleness further enhance performance.

Major projects like Google Chrome and Fedora have already adopted BFQ, and its usage is expected to expand in the coming years.