I took a little while to learn more about SD and CFS to see what the linux guys were up to. I have a couple of interesting comments. Including some discussion of increased algorithm complexity in the CFS scheduler; it's no longer O(1). Please keep in mind that these comments are entirely from reading code and documentation. I make no claim of knowing which scheduler actually makes the best scheduling decisions.


There were two things about the earlier linux scheduler that I didn't like, both of which I had tried in earlier versions of ULE. The first was the double-queue mechanism, which I only replaced in the "ULE 2.0" commits. This made fair scheduling incredibly difficult. It also made nice very difficult. The second thing was using variable slice sizes to adjust cpu time allocation. It just seemed hacky and pessimized throughput in tasks with small slices.

The SD scheduler kept both of these things. It then used an very complex priority bitmap to determine how many slices a thread would be assigned on the current run-queue. It did remove many of the interactivity related heuristics in an attempt to simplify the scheduler. I understand it had favorable behavior on the desktop, but I imagine there were many pathological behaviors with it. In general I found it overcomplicated, as most of the attempts I made with the double-queue system were.

CFS got rid of the variable slice sizes and the double-queue. However, it also increased the algorithmic complexity on insert/removal to O(log n) through the use of a rb tree rather than a run-queue The mainline scheduler was much touted for it's O(1) complexity. The historic scheduler, prior to O(1), was only O(n) in a loop that ran once per-second to recalculate task priorities. This is similar to the 4BSD scheduler algorithm. They were otherwise O(1) for insert/removal.

I'm curious to see if they find the increased algorithm complexity will show up on many profiles. You can imagine that when dealing with hundreds or thousands of running threads the cache misses when walking log n could be quite expensive. Especially because you'd have many, many, more scheduling events with this number of threads.

The other interesting thing in CFS is nanosecond resolution precise accounting of time. We've actually been discussing this for a while in bsd as we already keep some of these stats for getrusage(). Hooking it up in the scheduler would make several issues nicer and would remove the possibility of timing heuristic based scheduler attacks.

I have not looked at what heuristics were employed to determine which processes are interactive in the mainline scheduler. However, ULE's interactivity heuristic adapts with CPU load and I can't imagine abandoning it as they have with CFS. ULE and CFS both attempt fair cpu distribution over some period modulo nice values. In this regard ULE with the interactivity disabled (sysctl kern.sched.interact=0) should be as 'completely fair' as CFS. As was the older 4BSD scheduler. However, FreeBSD users report a marked improvement in responsiveness with the interactivity hint in ULE.

repeat_schedule:
        /*
         * Default process to select..
         */
        next = idle_task(this_cpu);
        c = -1000;
        list_for_each(tmp, &runqueue_head) {
                p = list_entry(tmp, struct task_struct, run_list);
                if (can_schedule(p, this_cpu)) {
                        int weight = goodness(p, this_cpu, prev->active_mm);
                        if (weight > c)
                                c = weight, next = p;
                }
        }