vault

BFQ Budget Fair Queueing Scheduler

15 min read

BFQ Budget Fair Queueing Scheduler

BFQ (Budget Fair Queueing) is a Linux block-layer I/O scheduler that divides a storage device’s bandwidth — not merely its time — among the processes (and cgroups) competing for it, in proportion to per-process weights. Unlike a time-slice scheduler, BFQ grants the disk to the in-service process until that process has consumed a budget measured in sectors, then re-schedules. The dispatch order is decided by an internal fair-queueing engine called B-WF2Q+ (Budget Worst-case-Fair Weighted Fair Queueing Plus). Layered on top of that proportional-share core are aggressive low-latency heuristics — device idling to protect sequential throughput, and weight-raising that detects interactive and soft-real-time applications and temporarily multiplies their weight so they get serviced first. The result is excellent application responsiveness and fairness on rotational disks and modest flash, at a per-request CPU cost (~1.9 µs versus ~0.7 µs for mq-deadline) that makes BFQ the wrong choice for million-IOPS NVMe. BFQ has been in mainline as a blk-mq scheduler since kernel 4.12 (2017), authored and maintained by Paolo Valente (per the BFQ source header; LWN 2019). This note pins to Linux 6.12 LTS (released 2024-11-17; behaviour unchanged through 6.18 LTS as of writing).

This note assumes familiarity with where schedulers sit in the block stack; see Linux IO Schedulers Overview for the framework and The Multi-Queue Block Layer blk-mq for the two-level software/hardware queue model BFQ plugs into. It is a sibling of mq-deadline Scheduler and Kyber IO Scheduler; Choosing an IO Scheduler gives the decision framework.

Mental Model: Budgets and Virtual Time

The cleanest way to think about BFQ is by analogy to a network packet scheduler retargeted at a disk. In packet fair queueing (the WF2Q+ family BFQ descends from), each flow gets a weight, and the scheduler emits packets so that, over any interval, each flow’s transmitted bytes track its share of link bandwidth. BFQ transplants this to storage: each process becomes a flow, each I/O request is a packet, and the “bytes transmitted” are sectors served. The device is the shared link.

The mechanism that makes this precise is virtual time. Every schedulable entity (a process’s queue, or a whole cgroup) carries two timestamps in a virtual time axis measured in sectors/weight: a start time S_i and a finish time F_i. When an entity is granted a budget, its finish timestamp is pushed forward by F_i = S_i + budget / weight (the BFQ header comment, field budget, line 176). Walk that formula symbol by symbol: budget is the number of sectors the entity is allowed to serve this turn; weight is its proportional share (a higher weight is a larger share); dividing budget by weight means a heavier entity advances its finish time more slowly per sector, so it stays eligible for service longer and thus receives a larger fraction of the device. The scheduler always serves the eligible entity with the smallest finish timestamp — the one that has, in virtual time, “fallen behind” the most. This is what guarantees proportional bandwidth.

flowchart TB
  subgraph BIC["Per-process I/O context (bfq_io_cq)"]
    P1["Process A<br/>weight 200"]
    P2["Process B<br/>weight 100"]
    P3["Process C<br/>weight 100"]
  end
  P1 --> Q1["bfq_queue A<br/>budget = N sectors<br/>F_A = S_A + N/200"]
  P2 --> Q2["bfq_queue B<br/>budget = N sectors<br/>F_B = S_B + N/100"]
  P3 --> Q3["bfq_queue C<br/>budget = N sectors<br/>F_C = S_C + N/100"]
  Q1 --> ST["B-WF2Q+ service tree<br/>(rbtree keyed on finish time)"]
  Q2 --> ST
  Q3 --> ST
  ST -->|"pick min finish time<br/>(eligible)"| INSERV["In-service queue<br/>serve until budget<br/>exhausted or timeout"]
  INSERV -->|"dispatch sectors"| DEV["Device dispatch queue<br/>(blk-mq hardware queue)"]

BFQ’s proportional-share core. What it shows: each process maps to a bfq_queue with a sector budget; B-WF2Q+ keeps the queues in a red-black service tree ordered by virtual finish time F_i = S_i + budget/weight, and repeatedly serves the eligible queue with the smallest finish time until its budget is consumed. The insight: because the divisor is weight, a process with weight 200 advances half as fast in virtual time as one with weight 100, so it is picked roughly twice as often — that is exactly how BFQ turns weights into bandwidth shares.

Mechanical Walk-through

From process to bfq_queue

When a process first issues synchronous I/O, BFQ associates it with a bfq_queue — a leaf scheduling entity holding that process’s pending requests, sorted by sector position in a red-black tree (sort_list) and also kept in a FIFO list for deadline fallback (struct bfq_queue, lines 246–412). The per-(request_queue, io_context) binding lives in a bfq_io_cq structure, which holds a matrix of queues: one row for async, one for sync, with a column per actuator (multi-actuator drives, discussed below). Asynchronous writes from all processes in a cgroup share per-priority async queues rather than getting one each, because writeback is not latency-critical and pooling it simplifies accounting.

Each bfq_queue is wrapped in a generic bfq_entity carrying the virtual-time timestamps, the weight, and the budget. This indirection is what lets BFQ schedule processes and cgroups with the same code: a leaf entity is a queue, an internal entity is a bfq_group (one per cgroup per device), and entities nest hierarchically. The hierarchical variant is called H-WF2Q+ — each cgroup level runs its own B-WF2Q+ instance over its children, and service flows down the tree.

B-WF2Q+ and the service trees

Within a bfq_sched_data (a scheduler queue), there are three independent service trees, one per I/O-priority class — IOPRIO_CLASS_RT (real-time), IOPRIO_CLASS_BE (best-effort, the default), and IOPRIO_CLASS_IDLE (struct bfq_sched_data, lines 99–109). Higher-priority classes are served strictly before lower ones; within a class, B-WF2Q+ orders by finish time. Each bfq_service_tree keeps an active red-black tree (backlogged entities) and an idle tree (entities not currently backlogged but whose finish time has not yet been overtaken by the scheduler’s virtual time vtime), plus a running wsum (the sum of weights of all entities) used to advance virtual time. The augmented-tree trick — caching each subtree’s minimum start time in min_start — gives B-WF2Q+ O(log N) lookups of the next entity to serve, a refinement borrowed from the EEVDF algorithm (BFQ header comment, lines 94–114).

The budget and its feedback loop

When a queue is selected for service it receives a budget in sectors (entity.budget). It keeps the disk until one of several expiration conditions fires (enum bfqq_expiration): BFQQE_BUDGET_EXHAUSTED (it served its whole budget), BFQQE_BUDGET_TIMEOUT (it held the disk too long — see bfq_timeout, default HZ/8 ≈ 125 ms), BFQQE_TOO_IDLE (the idle timer fired with no new request), BFQQE_NO_MORE_REQUESTS (it ran dry), or BFQQE_PREEMPTED.

The genius — and the fragility — of BFQ is that the next budget is not fixed; it is recomputed by a feedback heuristic in __bfq_bfqq_recalc_budget() based on why the queue expired (bfq-iosched.c, lines 3962–4101). The logic, traced from the source:

  • If the queue exhausted its budget while still backlogged (BFQQE_BUDGET_EXHAUSTED), it is a well-behaved sequential reader, so BFQ quadruples its budget (budget = min(budget * 4, bfq_max_budget)) to let it run longer and boost throughput.
  • If it timed out (BFQQE_BUDGET_TIMEOUT), BFQ doubles the budget, betting the queue is sequential but was throttled by something like zone-bit-rate variation rather than seekiness.
  • If it went idle with no outstanding requests (BFQQE_TOO_IDLE and dispatched == 0), BFQ shrinks the budget (budget -= 4 * min_budget, floored at min_budget), guessing the process only needed a small burst — a smaller next budget gives it lower latency. This is the only case where the budget is cut.

The ceiling on all of this, bfq_max_budget, is auto-tuned from the measured device peak rate so that a full budget fits in one bfq_timeout interval at peak rate: bfq_calc_max_budget = peak_rate * timeout (bfq-iosched.c, lines 3414–3418). A user can override it via the max_budget sysfs knob; setting it to 0 (the default) re-enables auto-tuning.

Device idling — the throughput-preserving wait

A naive fair scheduler would, the instant a synchronous queue runs dry, immediately switch to another queue. On a rotational disk that is catastrophic: a process doing sequential reads pauses for microseconds between requests (think time), and switching away forces the disk head to seek elsewhere and then seek back, destroying sequential throughput. BFQ instead idles — after serving a sync queue’s last pending request, it arms idle_slice_timer and waits a short interval (bfq_slice_idle, default NSEC_PER_SEC/125 = 8 ms) for that same process to issue its next contiguous request (bfq-iosched.c, line 174). If the request arrives, sequential throughput is preserved; if the timer fires first, the queue expires BFQQE_TOO_IDLE. Idling is the single biggest reason BFQ both performs well on HDDs and costs throughput on fast flash where seeking is free — hence the advice to set slice_idle = 0 on solid-state devices.

Weight-raising: detecting interactive and soft-real-time work

On top of plain proportional sharing, BFQ’s low_latency mode (default on) runs heuristics that classify queues as interactive or soft real-time and temporarily multiply their weight (wr_coeff). An interactive queue is one that is “constantly non-empty for only a limited time interval, after which it becomes empty” (BFQ header comment, lines 60–66) — the signature of an application starting up or responding to a user. A soft-real-time queue is one that issues I/O at a bounded rate with bounded think time, like an audio or video player; the default bfq_wr_max_softrt_rate of 7000 sectors/sec approximates the rate needed to play or record HD compressed video (bfq-iosched.c, lines 7335–7340).

When a queue is weight-raised, wr_coeff jumps to bfq_wr_coeff (default 30, line 7331) — a 30× weight multiplier — for a bounded duration (bfq_wr_rt_max_time, default 300 ms for the soft-real-time form). This is what makes a terminal or browser feel instant even while a backup hammers the disk: BFQ recognises the burst as interactive and shoves it to the front. While weight-raised, the queue is also given a small constant budget (2 * min_budget) to keep its latency low (bfq-iosched.c, lines 3971–3979). LWN measured that, with weight-raising and dispatch-plug tuning, “applications start about 80% more quickly under load” (LWN 2019).

Configuration: Weights, cgroups, and sysfs tunables

Selecting BFQ

# Select BFQ for a specific device (requires CONFIG_IOSCHED_BFQ)
echo bfq > /sys/block/sda/queue/scheduler
cat /sys/block/sda/queue/scheduler        # -> mq-deadline kyber [bfq] none

Line by line: the scheduler sysfs file lists the available elevators with the active one in brackets; writing a name switches it live. BFQ must be compiled in (CONFIG_IOSCHED_BFQ=y or as a module). Most distributions ship a udev rule that defaults rotational disks to BFQ or mq-deadline and NVMe to none — see Choosing an IO Scheduler.

Per-process priority

Without cgroups, a process’s BFQ weight is derived from its I/O priority via weight = (IOPRIO_BE_NR - ioprio) * 10 (docs.kernel.org/block/bfq-iosched), where ioprio is set with ionice:

ionice -c 2 -n 0 -p 1234   # best-effort class, highest priority (ioprio 0) for PID 1234
ionice -c 1 dd if=/dev/sda of=/dev/null   # real-time class: strictly served before best-effort

cgroup weights — the blkio/io controller integration

BFQ is the only upstream scheduler that implements full hierarchical cgroup proportional control. It registers a cgroup policy exposing a weight knob (bfq-cgroup.c, lines 1254–1386):

# cgroup v2 (unified hierarchy): per-cgroup weight, range 1..1000, default 100
echo 500 > /sys/fs/cgroup/mygroup/io.bfq.weight
 
# cgroup v1: same knob, different path
echo 500 > /sys/fs/cgroup/blkio/mygroup/blkio.bfq.weight
 
# Per-device override (major:minor weight)
echo "8:0 300" > /sys/fs/cgroup/mygroup/io.bfq.weight_device

The kernel registers the file as the bare name bfq.weight; the cgroup core prefixes io. (v2) or blkio. (v1). The setter bfq_io_set_weight_legacy() validates the value against BFQ_MIN_WEIGHT (1) and BFQ_MAX_WEIGHT (1000), with CGROUP_WEIGHT_DFL = 100 as the default (bfq-cgroup.c line 1024; cgroup.h lines 37–38). The per-group I/O accounting BFQ keeps (bfq.io_service_bytes, bfq.io_serviced, bfq.io_service_time, etc.) is the scheduler-side counterpart of the device-level accounting described in Block Layer Statistics and iostat — BFQ attributes service to cgroups, while /proc/diskstats aggregates per device.

Cross-link, not duplication

BFQ’s bfq.* cgroup statistics (service bytes, service time, wait time) are scheduler-internal per-cgroup counters. They are distinct from, and complementary to, the device-level counters in Block Layer Statistics and iostat (/proc/diskstats, /sys/block/<dev>/stat). The shared thread is the blkio/io cgroup controller; the two notes cover the two ends of it.

The sysfs tunables

Every BFQ tunable lives under /sys/block/<dev>/queue/iosched/ (the bfq_attrs table, lines 7604–7616):

TunableDefaultMeaning
slice_idle (_us)8 msHow long to idle waiting for the next contiguous sync request. Set 0 on flash.
low_latency1Enable interactive/soft-real-time weight-raising. Set 0 to chase pure throughput.
max_budget0 (auto)Cap on sectors served per queue per turn; 0 auto-tunes from peak rate.
timeout_sync125 msMax device time a sync queue may hold before forced expiry.
strict_guarantees0Force one outstanding request and continuous idling for exact fairness, at throughput cost.
fifo_expire_sync125 msDeadline after which a starved sync request is force-dispatched in FIFO order.
fifo_expire_async250 msSame for async.
back_seek_max16 MiBLargest backward seek BFQ will treat as “close” when merging/anticipating.
back_seek_penalty2Cost factor making backward seeks less attractive than forward.

(Defaults read from bfq_init_queue() and the file-scope constants, bfq-iosched.c lines 164–204, 7314–7335.)

Failure Modes and Common Misunderstandings

“BFQ is slow.” BFQ does not make the device slow; it makes the CPU work harder per request. Its proportional-share bookkeeping costs roughly 1.9 µs per request on an Intel i7-2760QM versus 0.7 µs for mq-deadline (docs.kernel.org/block/bfq-iosched). That overhead is irrelevant on a 200-IOPS hard disk and crippling on a device that wants to do hundreds of thousands of IOPS. The documented ceilings: with hierarchical scheduling on and CONFIG_BFQ_CGROUP_DEBUG off, BFQ saturates a single core at roughly 400 KIOPS on an Intel i7-4850HQ, 250 KIOPS on an AMD A8-3850, and 80 KIOPS on an ARM Cortex-A53. Above those rates BFQ becomes the bottleneck and you must use none or mq-deadline.

Idling kills throughput on SSDs. Because slice_idle defaults to 8 ms, BFQ on a fast flash device may sit idle waiting for a request the device could have started servicing immediately from another queue. On solid-state storage set slice_idle = 0 (or just don’t use BFQ). The source explicitly notes: “if the main or only goal, with a given device, is to achieve the maximum-possible throughput at all times, then do switch off all low-latency heuristics” (bfq-iosched.c, lines 80–83).

Weight-raising can be surprising. Because low_latency can multiply a queue’s weight by 30×, a workload that BFQ misclassifies as interactive can momentarily starve a genuinely throughput-bound job. This is by design for desktops but undesirable for servers; disable it with low_latency = 0.

cgroup weights need the controller enabled. io.bfq.weight exists only when BFQ is the active scheduler for the device and the io controller is enabled in the cgroup subtree. On a device using none, there is no BFQ policy and the knob is absent.

Uncertain

Verify: the exact per-request overhead numbers (1.9 µs, 0.7 µs) and the KIOPS ceilings (400/250/80). Reason: these come from the docs.kernel.org BFQ page, which is a concepts page not pinned to 6.12, and the figures date from older hardware/measurements. To resolve: they are order-of-magnitude guidance, not 6.12-specific benchmarks; re-measure on target hardware before relying on a precise threshold. uncertain

Multi-Actuator Drives — a modern wrinkle

A subtle 6.x-era addition: BFQ understands multi-actuator hard drives (drives with more than one independent read/write head assembly, which can serve I/O to disjoint LBA ranges in parallel). BFQ_MAX_ACTUATORS is 8, and a bfq_io_cq keeps a separate sync/async queue per actuator so that I/O destined for different actuators is scheduled independently and can be injected concurrently (bfq-iosched.h, lines 41, 477–505). This lets BFQ exploit hardware parallelism that single-queue assumptions would waste — but it is niche; the overwhelming majority of drives are single-actuator and the array is size 1 in practice.

Alternatives and When to Choose Them

  • mq-deadline Scheduler — far cheaper per request; bounds latency with read/write deadlines but offers no per-process or per-cgroup fairness and no interactive detection. The right default for general SATA/SAS and the standard fallback when BFQ’s CPU cost is too high.
  • Kyber IO Scheduler — minimal, latency-target-driven, built for fast multi-queue flash. It throttles to hit target read/write latencies rather than guaranteeing shares; much lower overhead than BFQ.
  • none — pure FIFO pass-through with no reordering. Correct for high-end NVMe where the device’s own queues reorder better than software can, and where any scheduler is pure overhead.

Choose BFQ specifically when you need per-process or per-cgroup bandwidth fairness or desktop-grade interactive responsiveness on a device slow enough (rotational, eMMC, low-end SATA SSD, single-LUN arrays) that its ~1.9 µs/request overhead is negligible against the device’s service time. See Choosing an IO Scheduler for the full matrix.

Production Notes

BFQ is the default scheduler for rotational devices in several desktop-oriented distributions (it became the desktop default in some setups precisely because of the responsiveness wins LWN documents). On Android, BFQ’s interactive heuristics map well to UI-latency goals on eMMC/UFS storage, and it has seen deployment there. The strict caution from both the source header and the LWN write-up is consistent: BFQ is not for high-IOPS NVMe servers, where the scheduler itself becomes the throughput wall — those should run none. Paolo Valente, the maintainer, has continued to optimise the per-request cost (LWN’s 2019 article reports a ~10% reduction to ≈0.6 µs/event on some configurations after dispatch-plug rework), but the fundamental order-of-magnitude gap to mq-deadline/none remains (LWN 2019).

Uncertain

Verify: the specific claim that BFQ is the default rotational scheduler in named distributions, and its use as an Android default. Reason: distribution and Android-vendor defaults change across releases and were not confirmed against a primary distro/AOSP source during this note. To resolve: check the current udev/init scheduler rules of the target distro and the AOSP kernel config at the relevant version. uncertain

See Also

Graph View

Backlinks