[lkml]   [2004]   [Feb]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [RFC][PATCH] O(1) Entitlement Based Scheduler
Andy Lutomirski wrote:
> Peter Williams wrote:
>> Andy Lutomirski wrote:
>>> How hard would it be to make shares hierarchial? For example (quoted
>>> names are just descriptive):
>> As Peter Chubb has stated such control is possible and is available on
>> Tru64, Solaris and Windows with Aurema's (<>)
>> ARMTech product. The CKRM project also addresses this issue.
> Cool. I hadn't realized ARMTech did that, and I haven't fully read up
> on CKRM.
>>> Also, could interactivity problems be solved something like this:
>>> prio = ( (old EBS usage ratio) - 0.5 ) * i + 0.5
>>> "i" would be a per-process interactivity factor (normally 1, but
>>> higher for interactive processes) which would only boost them when
>>> their CPU usage is low. This makes interactive processes get their
>>> timeslices early (very high priority at low CPU consumption) but
>>> prevents abuse by preventing excessive CPU consumption. This could
>>> even by set by the (untrusted) process itself.
>> Interactive processes do very well under EBS without any special
>> treatment.
>> Programs such as xmms aren't really interactive processes although
>> they usually have a very low CPU usage rate like interactive
>> processes. What distinguishes them is their need for REGULAR access
>> to the CPU. It's unlikely that such a modification would help with
>> the need for regularity.
> I'm guessing the reason make -j16 broke it is because it (i.e. make)
> spawns lots of processes frequenly. Since make probably uses almost no
> CPU under this load, its usage per share stays near zero. As long as it
> is below that of xmms, then all of its children are too, at least until
> part-way into their first timeslices. The problem is that there are a
> bunch of these children, and, if enough start at once, they all run
> before xmms, and the audio buffer underruns. My approach would give
> xmms a better chance of running sooner (in fact, it would potentially
> have better priority than any non-interactive task until it started
> hogging CPU).

That's close to the reason. The real culprit is the dreaded "ramp up"
which is our tag for the fact that it takes a short while (dependent on
half life) for the scheduler to estimate the usage rate of a new process
(or a sudden change in the usage rate of an existing process) so they
get treated as low usage tasks for the first part of their life. In
most cases this is a good thing as it causes commands run from the
command line to get a boost and since a lot of these are very short
lived (e.g. ls) they run very quickly and have very good response times.
In the case of a kernel build there are lots of C compiler tasks being
launched and these run for several seconds but for the first few moments
of their lives (during ramp up) they look like low CPU usage tasks and
get high priority. This effect is short lived and doesn't effect normal
interactive programs because regularity of access isn't important to
them and the estimated usages of the C compiler tasks quickly exceeds
the estimated usages of the interactive tasks. It only has an effect on
xmms because regularity of access is important to it (i.e. xmms IS
getting sufficient CPU but isn't always getting it as regularly as it

The X server is a different case. Although it isn't an interactive
program it does have an influence on interactive responsiveness when X
windows is being used. Unfortunately, because it is generally serving a
number of clients, its CPU usage can be quite high and it takes a little
longer for the estimated usage rate of the C compiler tasks to exceed
its estimated usage. For this reason, we recommend that sysadmins
arrange for the X server to be run at somewhere between nice -9 and nice

It should be obvious from the above that another way that interactive
response can be improved is by shortening the half life. But there is a
trade off with lowered overall system throughput resulting if the half
life is too short. In the current version of EBS, root can change the
half life on a running system and this functionality is there so that
experiments into the effect of changing the half life on system
performance can be conducted without the need to recompile the kernel
and reboot the system. The default value of 5 seconds is one that we've
found is good for overall performance and interactive response provided
that the X server is run with an appropriate level of niceness.

>> Once again I'll stress that in order to cause xmms to skip we had to
>> (on a single CPU machine) run a kernel build with -j 16 which causes a
>> system load well in excess of 10 and is NOT a normal load. Under
>> normal loads xmms performs OK.
>>> I imagine that these two together would nicely solve most
>>> interactivity and fairness issues -- the former prevents starvation
>>> by other users and the latter prevents latency caused by large
>>> numbers of CPU-light tasks.
>>> Is this sane?
>> Yes. Fairness between users rather than between tasks is a sane
>> desire but beyond the current scope of EBS.
> I have this strange masochistic desire to implement this. Don't expect
> patches any time soon -- it would be my first time playing with the
> scheduler ;)

Good luck
Dr Peter Williams, Chief Scientist
Aurema Pty Limited Tel:+61 2 9698 2322
PO Box 305, Strawberry Hills NSW 2012, Australia Fax:+61 2 9699 9174
79 Myrtle Street, Chippendale NSW 2008, Australia

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

 \ /
  Last update: 2005-03-22 14:01    [from the cache]
©2003-2011 Jasper Spaans