(Re)implement the BFS scheduler into the FreeBSD - Final report
Abstract
- The goal of this project is to implement the BFS scheduler into the FreeBSD operating system. I will then run some benchmarks to find out how this BFS implementation compares to the existing 4BSD and ULE schedulers. I hope I could achieve some interesting results. BFS (Brain Fuck Scheduler) is a scheduler designed for the Linux kernel in August 2009 as an alternative to the CFS and the O(1) scheduler. It was created by Con Kolivas.
Ovewview of accomplished milestone goals
Simple scheduler with 64 round robin queues. I will also publish simple benchmarking results. - Acccomplished, benchmarks published on project blog page.
The 64 queues act according to the BFS specification (With necessary modifications to match the FreeBSD design) Static priorities and SCHED_ISO are taken round robin, SCHED_NORMAL and SCHED_IDLEPRIO are taken according to their deadline. (The lookup is O(n)). I will also publish the results of the same benchmark tests as in the previous release point. - Accomplished, the necessary modifications have been described on my blog page.
Implementing the scalability features to the BFS as specified in the BFS specification. I might also consider adding improvements which are not part of the BFS spec. I will also publish the results of the same benchmark tests as in the previous release points.-Partially accomplished. I implemented cache locality and CPU affinity. I considered researching the scenarios where the scheduler caused bad user experience and fixing it as my priority.
Running (implementing) additional benchmarks, analysing results. Finding the cause of possible bad results, bug fixing.-Accomplished, benchmarks have been published on my project blog page.
Scheduler characteristics
The scheduler shows the best performance when running on top of small number of CPU cores. Here I present the sysbench benchmark on amd64 machine with 2 cores. When the number of cores increases, the scheduler performance goes down when compared to the other schedulers (4BSD and ULE). 
# of threads |
4BSD |
FBFS |
ULE |
1 |
567.67 |
552.79 |
551.22 |
2 |
1016.09 |
947.07 |
929.73 |
3 |
996.46 |
949.89 |
935.66 |
4 |
975.27 |
950.46 |
924.17 |
5 |
954.44 |
950.58 |
919.60 |
6 |
940.93 |
948.40 |
913.45 |
7 |
921.10 |
948.32 |
897.68 |
8 |
921.26 |
946.30 |
898.29 |
9 |
911.30 |
946.30 |
889.82 |
10 |
906.52 |
946.18 |
885.45 |
11 |
897.82 |
945.69 |
878.32 |
12 |
893.87 |
945.65 |
874.08 |
13 |
886.44 |
944.82 |
866.88 |
14 |
883.50 |
942.59 |
863.34 |
15 |
876.91 |
940.93 |
858.07 |
16 |
869.90 |
940.91 |
857.42 |
More information
To find out more information about the scheduler, latest patches, or what other people say about this scheduler, please visit the project blog page http://rudot.blog.com