Brain Fuck Scheduler

from Wikipedia, the free encyclopedia
Brain Fuck Scheduler (BFS)
Basic data

Maintainer Con Kolivas
developer Con Kolivas
Publishing year September 2009
Current  version 0.512 for
Linux kernel 4.8
(October 3, 2016)
operating system Linux
programming language C.
License GPL
kernel.kolivas.org
Multiple Queue Skiplist Scheduler (MuQSS)
Basic data

Maintainer Con Kolivas
developer Con Kolivas
Publishing year October 2016
Current  version 0.193 for
Linux kernel 5.2
(July 22, 2019)
operating system Linux
programming language C.
License GPL
kernel.kolivas.org

The Brain Fuck Scheduler ( BFS ) or Multiple Queue Skiplist Scheduler ( MuQSS ) is a desktop-oriented process scheduler for the Linux kernel . It was developed in August 2009 as an alternative to the Completely Fair Scheduler (CFS for short) and the O (1) scheduler . The aim of the FSO is outstanding desktop interactivity and system responsiveness .

history

The BFS has been developed by long-time kernel developer Con Kolivas since 2009 and improves the responsiveness of Linux-based mobile devices with light NUMA architecture (Non-Uniform Memory Architecture) and desktop computers with fewer than 16 cores .

Shortly after its introduction, the new scheduler made headlines in the Linux community with reports on the front page of Slashdot , in Linux Magazine and Linux Pro Magazine.

The Brain Fuck Scheduler has no direct relationship with the Brainfuck programming language .

On October 3, 2016, Con Kolivas announced that the scheduler was renamed Multiple Queue Skiplist Scheduler (MuQSS). As reasons for the renaming, Kolivas cited the big and drastic code changes and the name Brain Fuck Scheduler, which is too offensive to some people . MuQSS supports a run queue per logical CPU and a skiplist for task lookups . With the two new properties, Kolivas wants to bypass two major BFS restrictions (only one run queue and expensive lookups with the time complexity ).

functionality

The BFS is based on the CFS when it comes to distributing computing times. However, with CFS, the rest periods measured in the process in the past also influence the decision of how long a time slice for the process will last in the future.

This can be a hindrance to user input, especially with inferior hardware, such as cell phones. If there were too many idle times in the input process in the past, less time will be allocated in the future until the statistics change again - precisely when user interaction takes place again. The BFS removes this complex calculation of the time slices on the basis of sleep calls and tries to strive for a completely fair distribution.

The algorithm owes its name to this “wrong” approach.

use

A first test of version 0.208 by Ingo Molnar did not reveal any performance advantages. The kernel developer, however, agreed to the basic goal of Con Kolivas for more support for desktop systems. Although there have been various reports of improved performance and responsiveness, it is unlikely that BFS will be adopted into the main branch of the Linux kernel.

Version 4.1.6 of the BFS was integrated into the CyanogenMod , a distribution of the Android mobile operating system , and has resulted in reported speed improvements. Steve Kondik announced at the end of October 2009 that he would remove the BFS from the main development branch. The FSO was also included in an experimental branch of the Android development repository on September 23, 2009. However, it was not included in the Froyo release (Android 2.2.x) after blind tests with the Motorola Milestone and the Nexus One showed no improvement in the user experience.

The BFS is the default scheduler of the GNU / Linux distributions Zenwalk Linux 6.4 and PCLinuxOS 2010.

In December 2012 it became known that the Linux developer Matthias Kohler was working on a new scheduler based on BFS and Linux 3.6.2. The specialty is the support of different run queue configurations. BFS only uses one run queue for all CPUs . In addition to this function, a run queue per CPU or a run queue per two CPUs can be configured using the scheduler, which was not named at the time .

See also

Web links

swell

  1. ↑ BFS version 0.512, linux-4.8-ck1, MuQSS for linux-4.8
  2. ↑ linux-5.2-ck1, MuQSS version 0.193 for linux-5.2
  3. ^ A b Marcel Hilzinger: Con Kolivas Introduces New BFS Scheduler. In: Linux Pro Magazine Online. September 2, 2009, accessed December 18, 2012 .
  4. ↑ a b graysky: CPU SCHEDULERS 3COMPARED. (PDF; 631 kB) October 20, 2012, accessed on December 18, 2012 .
  5. ↑ a b Con Kolivas: FAQS about BFS. v0.330. In: http://ck.kolivas.org . September 5, 2010, accessed December 18, 2012 .
  6. ↑ timothy: Con Kolivas Returns, With a Desktop-Oriented Linux Scheduler. In: http://linux.slashdot.org . September 6, 2009, accessed December 18, 2012 .
  7. ↑ Britta Wuelfing: Ingo Molnar Tests New BF Scheduler. In: Linux Magazine Online. September 8, 2009, accessed December 18, 2012 .
  8. ↑ Con Kolivas: BFS version 0.512, linux-4.8-ck1, MuQSS for linux-4.8. October 3, 2016, accessed January 11, 2017 .
  9. ↑ Con Kolivas: MuQSS - The Multiple Queue Skiplist Scheduler v0.105. October 1, 2016, accessed January 11, 2017 .
  10. ↑ Ingo Molnar: FSO vs. mainline scheduler benchmarks and measurements. In: Linux kernel mailing list. September 6, 2009, accessed December 18, 2012 .
  11. ↑ cyanogen: CyanogenMod-4.1.6 with BFS is here! In: Twitter. September 8, 2009, accessed December 18, 2012 .
  12. ↑ cyanogen: [ROM] CyanogenMod - This is Bat Country! (EXPERIMENTAL) [9/18 - v4.1.11.1]. changelog and user comments. In: xda-developers.com. September 18, 2009, accessed December 18, 2012 .
  13. ↑ cyanogen: Going to drop BFS for the stable release. In: Twitter. October 21, 2009. Retrieved December 19, 2012 .
  14. ↑ cyanogen: CyanogenMod 5 changelog. (No longer available online.) In: http://wiki.cyanogenmod.org . 2010, archived from the original on December 3, 2012 ; Retrieved December 18, 2012 . Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2Template: Webachiv / IABot / wiki.cyanogenmod.org
  15. ↑ BFS is added to the Android repository ( Memento from May 30, 2010 in the Internet Archive )
  16. ↑ hyperion: Zenwalk 6.4 is ready! (No longer available online.) In: zenwalk.org. May 27, 2010, archived from the original on October 23, 2013 ; Retrieved December 18, 2012 . Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2Template: Webachiv / IABot / www.zenwalk.org
  17. ↑ admin: PCLinuxOS 2010 Edition is now available for download. In: PCLinuxOS.com. April 20, 2010, accessed December 18, 2012 .
  18. ^ Matthias Kohler: Multiple run queues for BFS. In: LKML.org. December 15, 2012, accessed December 18, 2012 .