nexos wrote:
Don't even get me started on Linux, and especially GNU. They are perhaps more bloated then Windows in all of its bloat.
I politely disagree
nexos wrote:
Using a red black tree in the scheduler? I'm being serious, I really do want somebody to explain the benefits of that over an O(1) queue.
Well, that's because processes or, better, tasks have not only a fixed priority, but also a dynamic priority that depends on how they behaved. Also, with simple "fair" schedulers, without dynamic priority, a low-priority process may never get to run, until there is a higher-priority runnable process. That's OK for real-time processes, but definitively not for regular ones as lower-priority processes might suffer from starvation for an indefinite amount of time. What we actually want from a
completely fair scheduler instead, is that, no matter what, all processes are guaranteed to get some % of the CPU time, in proportion to their priority.
Assume there are just two processes on the system, process A with prio 9 and process B with prio 11. Assume that higher prio number means higher priority (on linux that is the opposite for regular processes). Assume also that both A and B want to run all the time because they are completely CPU-bound. With a simple scheduler, B will run forever (or, until ends) and A will never run before B dies, despite B have just slightly higher priority than A. What we want instead, is A to get 9/20 of the CPU time and B to get 11/20 of the CPU time. If, as a process runs and consumes its time-slices it's dynamic priority gets lower, at some point A will preempt the higher-priority process B and will run for some time. That's what's desirable, for most of the processes on desktop and server systems.
Because a process' total computed priority (static + dynamic) changes all the time, a red-black tree is used to select the process with the highest priority. Real-time scheduling instead is much simpler and it's done in O(1).
Of course, that was a very rough explanation. For a much better one, read the 4th chapter "Process scheduling" of the Linux Kernel Development book, 3rd edition.