Quoting Martin Husemann (martin@duskware.de):
> Are there any details beyound marketing?
> 
> "There is a fixed number of priority levels, so selecting a runnable process
> has constant costs" does not realy justify the name.

It does. The question when doing Big Oh notation is what the n is
bound to. I think the n in O(1)-scheduler case is bound to the number
of processes served by the kernel. This makes the number of priorities
to c, which correctly is constant. Keeping an array of run-queues,
we at max need c steps to traverse the whole queue. Ergo, we can
select the next proces in O(c) = O(1) time. Now, where it gets
interesting is in the part where we exhaust the priority array. I think
the scheduler switches to another datastructure it has made ready for 
the cause if I do not remember wrongly. So there is 2 arrays running
in parallel, called the working and the restructuring copy. When the
working copy is exhausted we switch. 

What is then needed is the change of priority. And this is the non-
trivial part. 

I cannot remember what the 44BSD scheduler does, but I remember it
moves long-term sleeping processes out of the calculation altogether.

The FreeBSD people has started to look at the ULE-scheduler which is
an alternative to 44BSD. AFAIR this work is lead by Jeff Roberson,
but I might be wrong. It incorporates a number of things from the
O(1)-scheduler of Linux-fame. They are planning to make it the default
scheduler after 5.2 has been released in order to stress it and see
where it lacks power.

-- 
j.