Hacker News new | past | comments | ask | show | jobs | submit login
The Battle of the Schedulers: FreeBSD ULE vs. Linux CFS [pdf] (usenix.org)
90 points by kev009 on July 12, 2018 | hide | past | favorite | 14 comments

"Conclusion: Scheduling threads on a multicore machine is hard."

Kudos to the kernel developers who have tried nearly everything under the sun to make performance of multi-core, multi-task, general-purpose machines satisfy everyone at the same time. Your efforts are not lost on those of us who understand just how difficult that is.

Heck, even scheduling on single core machines can be hard. I don't want to even try to imagine what hell multicore adds to the mix.

In the late '80s I worked at Interactive System Corporation, the company that AT&T contracted with to do the official System V Release 3 port from the 3B2 to Intel processors. I was initially working on the port to the 286.

The 3B2 was a paging system, which did not really fit well with the 286, so it has kind of hacky. We never were able to get the scheduling to behave reasonably. Running 10 CPU bound tasks, for example, would result in one getting about 85% of the CPU, another getting about 10%, and the other 8 splitting pretty evenly the rest. It would do this for a while and then would start massively thrashing swap for a couple minutes, and then would settle back down to the 85/10/* but with different tasks getting the 85 and 10.

We were still stuck on figuring that out when AT&T came to their senses and realized that no one actually wanted System V Release 3 on a 286 and we dropped it. At most what they wanted was to run their 286 Xenix and 286 System III binaries on their 386 System V Release 3 systems, and I got moved over to working on the emulators for those, which was much more pleasant.

(Besides multicore, another thing that I would guess makes it all much harder for today's kernel people is caching. Caching on the 286, and even 386, was a lot simpler than it is today. We were still in the days when systems were primarily getting faster because clock speeds were going up, not because they were being smarter. Now I think they get a lot of performance from very good use of resources, such as cache, and it is a lot easier in kernel software therefore to blow performance).

I'm actually amazed you were able to get SysVRIII working on a 286 at all.

I'm actually kinda curious about the details on Porting System V, the 3B2 is a machine I find super interesting.

> At most what they wanted was [...]

And there goes a large slice of all wasted engineering effort ...

It's amusing that they fixed several bugs in the schedulers while writing this paper.

The FreeBSD bug report and patch for reference:


"The Linux kernel offers an API to add new schedulers to the kernel. ... [In Linux] multiple schedul- ing classes can co-exist"

Very cool! Are there any real-world applications that use non-default/custom schedulers?

Con Kolivas' schedulers have had a loyal following among some desktop users http://www.users.on.net/~ckolivas/kernel/

Most people don't know this, but #ck exists on OFTC.

Real time systems can have different scheduling metric based on utilization and/or deadlines.

Real-time branch of Linux by Ingo Molnar as well, that version of CFS works somewhat differently.

Then you have some other RT Linux versions and VM schedulers in Xen.

Custom Android distributions like Cyanogenmod IIRC

It would be interesting to compare this with DragonflyBSD seeing as Matt Dillon expressly forked FreeBSD over disagreements about how best to handle multiple cores.

i read this as battle of the shredders. like, a proper shred is hard isnt it. you need to disperse the shreds. youd think by now wed have fully entropic shredders that slowly burn the paper as it goes through

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact