[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    [W:0.031 / U:3.416 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site