[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
[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