lkml.org 
[lkml]   [1999]   [May]   [7]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: Overscheduling DOES happen with high web server load.


On Fri, 7 May 1999 davem@redhat.com wrote:
>
> [ Linus, please correct me if I'm wrong below, this is about the
> wake-one scheme you described to us earlier today. ]

Okey-dokey..

> > [ for everyone else's benefit Linus's suggestion is for the task to
> > indicate, when placing himself on the run queue, that he is
> > "wake one" capable, then the wake up routines stop doing work
> > when they hit the first task which is marked this way and is not
> > running already ]
>
> Unfortunately you also need to consider a common case where another task
> POSIXly requires waking. The classic is select(). Such tasks should always
> be woken.
>
> I think Linus meant another thing, and I worded it incorrectly above, sorry.

Yes. My way of handling this will _always_ wake up everything that is not
marked exclusive, and that obviously very much includes select().

> I believe he intended that the wakeup scheme be:
>
> 1) Wakes up everyone not marked as "wake one" capable, this deals with
> the select issue and is the crux behind why he suggests this scheme.
>
> 2) Amongst (only) the "wake one" capable tasks, the first one which is
> not already running is woken, and then no further "wake one" capable
> tasks are poked.

Well, it's even easier than the above. What you do is:

- the wakeup-queue is a linked list (surprise, surprise, that's
how it works already)
- you add the "exclusive" entries to the end of the list (or at least
after any oher non-exclusive ones: depending on how the list is
organized one or the other may be the more efficient way to handle it).
They are also marked some way - preferably just a bit in the task
state.
- when you do a wakeup, you do exactly what you do now: walk the list,
waking up each process. The ONLY difference is that if you find an
exclusive process (easy to test for: you already look at the task state
anyway) that you woke up, you stop early and go home. You mark the one
you woke non-exclusive _or_ you make the exclusivity test also verify
that the thing is not running, so two consecutive wakeup calls will
always wake up two exclusive processes.

So:
- nonexclusive waiters are always woken up. They are at the head of the
list.
- _one_ non-exclusive process is always woken up.

> This means you do not indicate "wake one" capability for the listen
> socket polling case, for example.

Indeed. That would be extremely stupid.

The more complex case is for things like "read()", where you _can_ make
use of the exclusive code if you want to (for things that have queue-like
behaviour and thus have a notion of an exclusive head-of-queue: pipes,
sockets, and some character devices), but you have to make sure that if
you don't empty the queue you do another "wakeup()" on the wait queue,
otherwise there might be another exclusive reader that doesn't wake up
when you stop reading.

For accept(), that's not even an issue, as you can just guarantee that if
you wake up and there's a socket to be accepted, you will accept it (so
you never have to wake up anybody else for the half-baked case).

Note that the thing that makes this really safe is that you're guaranteed
that the _only_ things that change behaviour are the ones you expressly
asked to change. That was always a problem with "wake_up_one()", where it
had non-local changes to behaviour (a wake_up_one() would change how a
sleep somewhere else behaved).

Linus


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:51    [W:0.255 / U:0.084 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site