[Techtalk] Theory vs. practice

[Val Henson]

On Tue, Jan 15, 2002 at 06:35:22PM -0500, Raven, corporate courtesan wrote:
> 
> 	Okay, I can see that that's bad.  Is there a way to quickly
> check which processes are freeing up resources rather than requesting
> them, and then assign a higher priority to those?  Something to the
> effect of "need $100, who's releasing $100?  You?  Up front!".  You
> could even do some sort of secondary categorization, such that if you
> had a Platinum account needing $100, and you had a Gold account waiting
> to deposit $100 and a Silver account waiting to deposit $100, that the
> Gold account would get priority over the silver even under the new
> "who's got $100" system.

:) I'm getting a major kick out of watching everyone discover these
protocols on their own.

You've just invented a broadcast protocol for figuring out who has a
resource.  This means you don't have to keep lists of who has a
resource, but it does mean that you have to stop every process on a
system and ask it what its resources are.  You've also figured that
priority inheritance should be transitive - good. :)

> > Linux gets around this by introducing the concept of "fairness" (I'm
> > ignoring the "realtime" priorities).  Each process does eventually get
> > to run for a while, even if a higher priority process still wants the
> > CPU.  It's very egalitarian. :)
> 
> 	Like Cisco's weighted fair queueing (for the network geeks out
> there).  How is the weighting determined?

I'm going to simplify a bit here, since the Linux scheduler has been
rewritten and fiddled with many times since this quote was written in
kernel/sched.c:

/*
 *  'schedule()' is the scheduler function. It's a very simple and nice
 * scheduler: it's not perfect, but certainly works for most things.
 */
 
Basically, the longer you wait, the higher your priority gets.
Eventually, you have the highest priority, even if you started out
with the lowest, and you are now guaranteed to run.

-VAL