====== (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).
{{http://rudot.blog.com/files/2011/08/plot_sysbench_2cpu.gif}}

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