BFQ I / O scheduler better

In addition to the atomic KMS operations, another useful innovation was recently introduced to users of the Linux workstation - the BFQ (Budget Fair Queue) input and output subsystem scheduler. It is an improvement of the default CFQ (Completely Fair Queue), debuted as much as 9 years ago, but only in version 4.12 it hit the mainline.

Before talking about how the scheduler works, check out the Paolo Valente developer demo , this will give you the motivation to continue. The screen shot shows the start of the player with 10 background tasks to read the file from the disk for two schedulers: CFQ and BFQ . Guess which one of them did not start with such a load?

Now briefly about the algorithm. Just as in CFQ, synchronous requests are grouped in queues by task, and asynchronous - by device. Then BFQ for new tasks is transformed by a simple Round Robin scheduler, based on timestamps, so that the algorithm takes as its basis the budgets, in which the disk sectors serve as a measure. Depending on the nature and behavior of the task, the budget may vary, and the BFQ ensures that the flow of disk data will be adequately distributed between tasks.

BFQ at any given time only works with one task. When the device driver is ready to serve the next task, the algorithm requests from the queue the first C-LOOK in the order specified and sends it to the driver for execution.

Budget Policy Planner

Let's take a closer look at specific aspects of the algorithm in pseudocode. The add_request function add_request new request R to the queue, and if no other requests are received, then that's it.

 active_appl = none ; //     remaining_budget = 0 ; //    //:  ,    add_request(int i, request R) { appl = applications[i] ; //   i //     R; enqueue(R, appl.queue) ; if (appl.queue.size == 1) { //   if (appl != active_appl) b-wf2q+_insert(appl) ; else //   if(waiting_for_next_req()) //  unset_timer() ; //   } } 

Logic Scheduler .

In the diagram, arrows indicate the path from the request to the disk device, and ellipses indicate the algorithms and operations.

The dispatch function returns the value no request if all applications are idle, or the active application waits for the next request. On the other hand, the application is deduced from the list if it does not have time to fulfill the request in the budget allocated to it. Calling the function b−wf2q+update_vfintime updates the application timestamps so that only the useful time during which requests are processed is taken into account. The fact that the application failed to reset the request queue means that the batch of requests exceeded the allocated budget. Therefore, the budget should be increased by a given amount, which does not exceed a certain threshold level B _{i, max} .

 request dispatch() { // if (all_applic_are_idle() OR waiting_for_next_req()) return no_request ; if(active_appl ! = none AND remaining budget < C−LOOK next req (active_appl.queue).size ) { b−wf2q+update_vfintime(active_appl, active_appl.budget − remaining_budget); if(active_appl.budget + BUDG_INC_STEP <= active_appl. max_budget) active_appl.budget += BUDG INC STEP ; else active_appl.budget = active_appl.max budget ; b−wf2q+ insert(active_appl) ; active_appl = none ; } if (active_appl == none ) { //       b-wf2q+ active_appl = b−wf2q+ get_next_application() ; remaining budget = active_appl.budget ; } //          next_request = dequeue_next_req(active_appl.queue) ; remaining budget −= next_request.size; if(is empty (active_appl.queue)) set_timer(T_wait) ; //    //   b-wf2q+ b-wf2q+_inc_tot_service(next_request.size) ; return next_request ; 

Next, the application with the new budget falls into the B-WF ² Q + scheduler. If now there are no active applications left from the B-WF ² Q + scheduler queue, the following is taken and everything is new - for the active application, the next request R is taken from a string of similar ones and a budget is assigned to it.

Finally, the active application has been exhausted. The new timer is set equal to the current time + T _wait , in the case of the absence of new requests, the timer_expiration function timer_expiration . The application is declared idle and the new one gets the same budget as the previous one.

 timer_expiration() active_appl.budget = active_appl.budget − remaining_budget ; b-wf2q+_update_vfintime(active_appl, active_appl.budget); active_appl = none ; //   , //dispatch()   . 

It is worth mentioning the internal algorithms: C-LOOK B-WF ² Q +.

• C-LOOK (Circular LOOK) is a disk scheduler in which the disk head moves from one end to the other, serving incoming requests. Then, after the last request, reverses the direction, not reaching the finish , unlike the C-SCAN algorithm.
• B-WF ² Q + adapted for block devices variant of the packet scheduler WF ² Q +. The Weighted Fair Queue algorithm allows you to assign each thread its own priority, or weight, in proportion to which a part of the channel is allocated.

So what's the deal?

Here you should place a picture of Boromir, who with irritation tries to say that you can’t just take and add the scheduler to the main branch of the Linux kernel. In addition to code licked to mirror shine, patience and advanced social communication skills are needed here. There are no tangible reasons because of which it was necessary to marinate BFQ for so long and it remains only to applaud the unrelenting perseverance of its author. The official reason for the refusal to accept the new best scheduler was the lack of support for the new multiqueue API , since BFQ was able only to the previous block device API. Fortunately, Jens Axboe, the main maintainer of the multiqueue API , came to the rescue, and together they managed to achieve the desired result.

Starting the gnome-terminal application on Hitachi HDD (less is better) .

At the moment, users of these distributions can safely watch movies while copying a file from a USB flash drive, unpacking a large archive and other I / O-demanding operations. In them, the BFQ scheduler is used by default .

• Manjaro
• Mageia
• OpenMandriva
• Sabayon
• Arch Linux ARM
• Rosa

Performance on Hitachi HDD (more is better) .

Optionally, the BFQ scheduler is available at:

• Arch
• openSUSE
• PCLinuxOS
• Gentoo

It takes a few simple steps . First, change the GRUB bootloader line so that it looks like this:

 GRUB_CMDLINE_LINUX="scsi_mod.use_blk_mq=1" 

Then after the reboot, check the availability of the required scheduler.

 (5:500)$ sudo cat /sys/block/sda/queue/scheduler noop bfq deadline [cfq] 

Change the default scheduler.

 (5:501)$ sudo echo bfq > /sys/block/sda/queue/scheduler 

You can do this more thoroughly by applying the udev rule by writing the file /path/to/rules.d/60-scheduler.rules .

 ACTION=="add|change", KERNEL=="sd[az]", ATTR{queue/scheduler}="bfq" 

Materials on the topic

• A way forward for BFQ
• Budget Fair Queueing (BFQ) Storage-I / O Scheduler
• High Throughput Disk Scheduling with Fair Bandwidth Distribution
• Linux 4.12 Kernel