[ros-kernel] Process scheduler / timer resolution

[KJK::Hyperion]

At 22.51 10/03/2004, you wrote:
>Now that you talk about it. Why don't you pick up the Linux scheduler? Is 
>inside a file named sched.c written by Ingo Molnar. If there is a list 
>with the great features of Linux sorted by relevance, I would put the 
>scheduler somewhere in the first 2.

This will be my absolutely last comment on Linux: seeing it *finally*, 
after more than ten years of development and well into the new millenium, 
implement a constant-time scheduler, threads, PnP and a HAL (features that 
Windows NT has had since day one - except PnP), I officially welcome it in 
the world of real, modern operating systems (it's something that really 
makes one ponder. Really, a successful operating system is *not* defined by 
its kernel. Stallman has a sound point in calling it GNU/Linux). You 
finally made it, little penguin. Those stubby legs and wings of yours must 
be a real annoyance. Anyway, comparison with the VMS/NT scheduler, *the* 
scheduler we should implement:

>Ultra scalable (as they say and as it is, put all the CPUs you want, The 
>machine will be faster)
>all operations are O(1) (they use a small bitmap somewhere)

check. The bitmap is called "ready summary" in the VMS/NT scheduler, but 
it's not for constant execution time, it's for optimization. Doing an 
IsListEmpty() on each ready queue is O(<priority levels>) = O(32) = O(1), 
but it's just slower: first, it requires <priority levels> memory accesses 
vs <priority levels>/<bits in a word> = 1, and second, it's not uncommon 
for CPUs to have fast bit scan opcodes (the x86 does)

>threads do not constantly switch from CPU to CPU (they keep affine as much 
>as possible)

check (no, not really sure. But it would be so stupid otherwise that I just 
assume it)

>no CPU is idle when there is job to do

check

>interactive process are temporarily boosted and the quantum reduced (so 
>interactive processes answer right away even with high CPU load)

check

Now for the *real* features: how many priority levels? how does it prevent 
starvation? does it have real-time priority levels, i.e. not affected by 
boosting? does it support threads waiting for multiple events? does it 
support boosting the threads awakened by the firing of an event? will it 
keep our I/O completion ports at least as efficient as those of Windows NT? 
etc.