scheduler

It's been quite a long time since my last report so I think it is a good time to describe what I have been doing in the last two months. The main scheduler logic has been completed and now I am concentrating mainly on bug fixes, adjusting tunables and some minor improvements. I also removed gSchedulerLock, a spinlock I mentioned in my last post, and replaced it with more fine grained locking. An new interfaces for cpufreq and cpuidle modules has been created together with a cpufreq module for Intel Sandy Bridge or newer cores and cpuidle module for all processors that support C-states and invariant TSC. Furthermore, IRQs (including MSI) can be now directed to an arbitrary logical processor. Implementation of inter-processor interrupts has been improved so that it avoids acquiring any lock if it is not necessary and supports multicast interrupts. And, last but not least, 8 processor limit has been removed.

Soon I am going to work as a full-time Haiku developer on enhancing the scheduler. The goal is to improve performance of the whole system and finally deal with some long standing problems. To achieve this CPU affinity will be introduced what would make cache utilization better and I will implement scheduler strategies based on dynamic priorities what, hopefully, would once and for all deal with priority inversion. In addition to that, I want to make scheduler more power-aware. Haiku currently lacks low-level support for some of the more advanced power related features of CPUs but having scheduler ready for would save us from redesigning it later. Also, there are still ways to conserve energy without using the most recent technologies.

(Or: knitting a delicate fabric, part II: sewing it all together)
(Or: Right, Joker, the underwear might be on the outside, but I get to drive the Batmobile!)
(Or: I just had to say something about Batman and the Batmobile. Couldn't help it.)

Cool, now we have a space- and time-efficient data structure (which is nothing more than a nice structure to handle non-overlapping numeric ranges) we can use to implement the simplified stride scheduling thing I've been discussing ou the previous posts, which will remain small most of the time, and won't change its shape like mad, so it's also very gentle on the CPU cache. Not only that, but the same effects hold for any trees, shall we decide that red-black trees aren't adequate and set ourselves to use splay trees, AA trees, AVL trees, Huffman trees, unbalanced binary trees (please: no.), whatever. So far we took care of the (not any more) skewed proportions due to randomness (by using strides), the mapping of "tickets" to tasks (by using trees to store the queues, "indexes" as the tickets, offsets to simulate "special" tickets, and lazy evaluation to efficiently implement offset propagation to upper queues), and the order of complexity (by using the queues as the node elements of the tree, where the key is base priority times number of threads in that queue).