Date: Fri, 16 Aug 2002 04:17:28 -0700 From: Terry Lambert <tlambert2@mindspring.com> To: Jonathon McKitrick <jcm@FreeBSD-uk.eu.org> Cc: freebsd-hackers@freebsd.org Subject: Re: When to consider the new scehduler? Message-ID: <3D5CDF48.9C9B30ED@mindspring.com> References: <20020816104037.GA58453@dogma.freebsd-uk.eu.org>
next in thread | previous in thread | raw e-mail | index | archive | help
Jonathon McKitrick wrote:
> A couple of months ago, I saw a note on daemonnews that there was a
> patch for a proportional share scheduler. When would this work better
> than the existing priority feedback scheduler?
>
> NOTE: Please CC me, as I am not currently subscribed. Thanks.
Basically, you use it if you expect the system to be overloaded,
and don't want to spend the engineering effort to prevent/handle
the overload, and astill want the system to degrade gracefully.
The "fixed" scheduling class used to support the X server in the
UnixWare/SVR4.0.2/SVR4.2 case is, in the limit, a proportional
share scheduler. Rather than addressing the lack of working set
quotas that caused some programs (e.g. the linker) to thrash a
large number of pages out, the fixed scheduling class was added
to permit the X server sufficient CPU to trash the pages back in;
it didn't fix the problem, and there was a lot of useless page
thrashing, but the result was that the X server had sufficiently
good interactive response to fullfill the "move mouse -> wiggle
cursor" requirement amd avoid cognitive dissonance on the part
of the user attached to the mouse. 8-).
Here is an introduction from a moderately good paper on the subject.
Note that not all proportional share schedulers implement all the
attributes described here, and most are not O(1). I can't comment
on Luigi's work in detail, because I haven't studied it in detail
(soft real time systems are not very interesting to me unless they
support deadlining).
Abstracted from:
http://www.cs.utah.edu/flux/papers/ps-rtss01/RegehrRTSS01wip.pdf
| There are compelling reasons to use proportional share
| scheduling techniques to support multimedia and other
| soft real-time applications on general-purpose operating
| systems. First, proportional share (PS) schedulers are
| a good match for existing infrastructure such as a peri-odic
| timer interrupt and mechanisms for assigning priori-ties
| to applications—priorities can be mapped to shares in
| a proportional-share environment. Second, PS schedulers
| provide stronger guarantees to applications than do tradi-tional
| time-sharing schedulers: they allocate a specific frac-tion
| of the CPU to each thread, and some schedulers provide
| error bounds on the allocation rate. Third, PS schedulers
| have clear semantics during underload: excess CPU time
| is allocated fairly, in contrast with some reservation-based
| schedulers that must idle or back off to a secondary scheduling
| policy once all application budgets are exhausted.
FWIW, here's a paper on an O(1) proportional share scheduler.
It's not incredibly interesting, except in that it tries to
implement fair queueing:
http://citeseer.nj.nec.com/nieh01virtualtime.html
For my money, the algorithm to use in networking equipment, in
which you want to optimize packet throughput, is Weighted Fair
Share Queueing (as in the IBM/UMass work on QLinux, which also
implements Lazy REceiver Processing; see the QLinux site at
http://lass.cs.umass.edu/software/qlinux/ ).
-- Terry
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-hackers" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3D5CDF48.9C9B30ED>