linux-kernel - [ANNOUNCE] BFS CPU scheduler v0.502 for linux-4.7 with skip list.

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Date:   Fri, 23 Sep 2016 09:43:24 +1000
From:   Con Kolivas <kernel@...ivas.org>
To:     linux-kernel@...r.kernel.org
Subject: [ANNOUNCE] BFS CPU scheduler v0.502 for linux-4.7 with skip list.

This is to announce an updated stable version of the Brain Fuck Scheduler, 
version 0.502 for the current stable linux kernel. 

http://ck.kolivas.org/patches/bfs/4.0/4.7/4.7-sched-bfs-502.patch

All patches available here:
http://ck.kolivas.org/patches

Code blog:
http://ck-hack.blogspot.com

I was reluctant to announce previous versions as the cpu frequency load 
signalling changes mandated by mainline were initially poorly handled and then 
buggy in BFS until recently.

In 2011 I played with skip lists to replace the simple linked list that is 
used in BFS and after a brief period of testing did not find it advantageous 
though very little effort was putting into optimising the skip list 
implementation. Additionally I was unable to maintain the scheduling decisions 
entirely with the existing BFS implementation.

Recently I found renewed interest in improving the most obvious flaws in the 
design and trying again and found I could maintain the behaviour and 
performance at low load with improved performance at (very) high loads so I've 
incorporated them into the current version. No doubt there are other 
improvements that can be made to the skip list implementation but the low 
hanging fruit has been attended to and there seems to be little need given the 
target audience for BFS.

Patch introduction follows:

---

The Brain Fuck Scheduler v0.502 by Con Kolivas.

A single shared runqueue strict fairness earliest deadline first design.
Runqueue insertion is O(log(n)), lookup is O(1), removal is O(k) where k <= 16

Excellent throughput and latency for 1 to many CPUs on desktop and server
commodity hardware.
Not recommended for 4096 cpus.

Scalability is optimal when your workload is equal to the number of CPUs on
bfs. ie you should ONLY do make -j4 on quad core, -j2 on dual core and so on.

Interactive mode is enabled by default but can be disabled for improved
throughput

echo 0 > /proc/sys/kernel/interactive

Features SCHED_IDLEPRIO and SCHED_ISO scheduling policies as well.
You do NOT need to use these policies for good performance, they are purely
optional for even better performance in extreme conditions.

To run something idleprio, use schedtool like so:

schedtool -D -e make -j4

To run something isoprio, use schedtool like so:

schedtool -I -e amarok

Includes configurable SMT-nice support for better nice level and scheduling
policy support across SMT (aka hyperthread) sibling CPUs.

Includes accurate sub-tick accounting of tasks so userspace reported
cpu usage may be very different if you have very short lived tasks.

-- 
-ck