O(1) scheduler & interactivity improvements

O(1) scheduler & interactivity improvements

[Felipe Alfaro Solana]

Hi all,

I must say I'm a little bit disappointed with the interactive feeling of
latest kernels. From what I have read, it seems the scheduler decides on
the "interactive" behavior of a process based on its CPU usage and
sleeping times. I am no kernel expert, so I will assume this is how it
works, more or less, behind the scenes.

I think that marking a process as "interactive" based on the previous
premise is quite unreal. Let's take, for example, a real application
like a word processor which performs background spell checking. The word
processor should be considered interactive, even when it may be hogging
the CPU a lot to perform the background spell check and the rest of its
threads are sleeping waiting for user input.

As someone said before in the list, a process should be marked
"interactive" based on the fact that it's receiving user input, for
example, key strokes, mouse movements or any events received from any
input device, not based on its CPU usage. I think applications like XMMS
or mplayer shouldn't be considered interactive (at least, not until they
start interacting with user), and they have a constant usage of CPU.
However, interactive applications have peaks, requiring shots of CPU for
very short times. However, that's not necessarily true, as I said before
with the example of the word processor: it could well be wasting 100% of
CPU to perform spellchecking but it should still be considered an
interactive application: a single user keystroke should take preference
over the background spellchecking.

For terminal based, interactive applications (like pine, vi, and
company), which are connected to tty devices, a user input event could
make the scheduler boost the process priority for a brief time (and
then, reduce the priority in a nearly quadratic fashion until reaching
it's original, or a lower, priority) to give it a better response time
and increase the interactive feeling.

However, for X11 based applications it seems a lot more difficult since
all user-based input events are received by the X server itself (and not
the process for which the event is intended). Based on the previous
thoughts, the X11 server would be marked interactive, but not the
application (like the word processor). This is not the desired effect.

So the question is, how can we detect the ultimate process for which the
user input event is intended? Should the X11 server help the scheduler
by increasing the target process priority (it normally runs as root)?
Should the window manager increase the priority of the process which
owns the current foreground, active window? Solaris seems to work this
way: when the user changes the focus to a new window, the window owner
is brought into the interactive scheduling class. When the user chooses
a new window, the window which loses the focus forces its owner to
return to the time-shared scheduling class.

What do you think about all of this? Should we use behavior-based
against CPU-usage behavior to decide process interactivity?

Thanks for listening.

Re: O(1) scheduler & interactivity improvements

[Davide Libenzi]

On Sun, 22 Jun 2003, Felipe Alfaro Solana wrote:

> Hi all,
>
> I must say I'm a little bit disappointed with the interactive feeling of
> latest kernels. From what I have read, it seems the scheduler decides on
> the "interactive" behavior of a process based on its CPU usage and
> sleeping times. I am no kernel expert, so I will assume this is how it
> works, more or less, behind the scenes.
>
> I think that marking a process as "interactive" based on the previous
> premise is quite unreal. Let's take, for example, a real application
> like a word processor which performs background spell checking. The word
> processor should be considered interactive, even when it may be hogging
> the CPU a lot to perform the background spell check and the rest of its
> threads are sleeping waiting for user input.

I'm sorry to disagree. A word processor that waited 24 hours to receive an
input should be *gradually* migrated to lower priorities (CPU hogs) when
it starts eating all its timeslice. You can tune how *gradually* (negative
feedback) you move the process, but you can't bolt in explicit rules into
the scheduler. If your word processor that was waiting by 24 hours will
start eating all its timeslice, it must be migrated down in priority. When
the spell check will be over, it'll re-gain its status of interactive task.
One suggestion for Ingo would be to use the previous task history to
compute how gradually to migrate the task, with a factor for each direction.
Processes with a long history of interactive tasks should have a brake
when migrating towards lower priorities, like the ones that showed CPU
hogs properties repeatedly should have a brake when moving to higher
priorities. The value of this "brake" should be made function of the
previous history.



- Davide

Re: O(1) scheduler & interactivity improvements

[Jesse Pollard]

On Sunday 22 June 2003 15:00, Davide Libenzi wrote:
> On Sun, 22 Jun 2003, Felipe Alfaro Solana wrote:
> > Hi all,
> >
> > I must say I'm a little bit disappointed with the interactive feeling of
> > latest kernels. From what I have read, it seems the scheduler decides on
> > the "interactive" behavior of a process based on its CPU usage and
> > sleeping times. I am no kernel expert, so I will assume this is how it
> > works, more or less, behind the scenes.
> >
> > I think that marking a process as "interactive" based on the previous
> > premise is quite unreal. Let's take, for example, a real application
> > like a word processor which performs background spell checking. The word
> > processor should be considered interactive, even when it may be hogging
> > the CPU a lot to perform the background spell check and the rest of its
> > threads are sleeping waiting for user input.
>
> I'm sorry to disagree. A word processor that waited 24 hours to receive an
> input should be *gradually* migrated to lower priorities (CPU hogs) when
> it starts eating all its timeslice. You can tune how *gradually* (negative
> feedback) you move the process, but you can't bolt in explicit rules into
> the scheduler. If your word processor that was waiting by 24 hours will
> start eating all its timeslice, it must be migrated down in priority. When
> the spell check will be over, it'll re-gain its status of interactive task.
> One suggestion for Ingo would be to use the previous task history to
> compute how gradually to migrate the task, with a factor for each
> direction. Processes with a long history of interactive tasks should have a
> brake when migrating towards lower priorities, like the ones that showed
> CPU hogs properties repeatedly should have a brake when moving to higher
> priorities. The value of this "brake" should be made function of the
> previous history.

Wait a minute... A word processor that waits 24 hours to recieve an input is
IDLE for everything except file save/checkpoint.

No CPU utilization at all.

What SHOULD happen gradually is that it's memory (RSS) should be trimmed due
to lack of activity.

The processor priority should/could stay the same (or even go higher). That
way the applications gets a chance to page in necessary data AS SOON as the
input IS available.

The described word processor is a MEMORY scheduling issue, not an interactive
scheduling issue.

Interactive jobs can be identified by having short term sleep events occuring
before (more often than) timeslice consumption. These processes could use a
priority boost (special conditions do occurr with polling without a timeout).

Those processes that exhaust a timeslice frequently are CPU bound, with 
little I/O involved. These could do with a reduced priority (again, some
special conditions do occur with poll).

Re: O(1) scheduler & interactivity improvements

[Helge Hafting]

Felipe Alfaro Solana wrote:
> Hi all,
> 
> I must say I'm a little bit disappointed with the interactive feeling of
> latest kernels. From what I have read, it seems the scheduler decides on
> the "interactive" behavior of a process based on its CPU usage and
> sleeping times. I am no kernel expert, so I will assume this is how it
> works, more or less, behind the scenes.
> 
> I think that marking a process as "interactive" based on the previous
> premise is quite unreal. Let's take, for example, a real application
> like a word processor which performs background spell checking. The word
> processor should be considered interactive, even when it may be hogging
> the CPU a lot to perform the background spell check and the rest of its
> threads are sleeping waiting for user input.
> 
I thought this worked perfectly, like this:

The background spellchecking thread hogs the cpu and is
quite correct marked non-interactive.

The other thread that mostly sleeps waiting for keystrokes
is marked interactive because of all that sleeping.

So the spellchecker might stall now ant then, and the interactive
thread gets priority when it occationally have work to do.

Don't get confused by the fact that this word processor of
yours is two (or more) threads, with separate priorities.
The kernel don't prioritize tasks like "word processor" or
"mail daemon", it deals with separate threads.

> As someone said before in the list, a process should be marked
> "interactive" based on the fact that it's receiving user input, 

This is almost impossible to get right, except for a few very special
cases like a single user working at the console.  Unix is supposed to
do much better than that - the user logging in via a serial port,
(or more commonly these days, via the network) should get exactly
the same responsiveness as that console user.

Further, we may (sometimes) know that some devices is connected
to a human.  But how about that script reading one disk file
and writing to another?  Is it some cron job, did it start
from some GUI menu with a user eagerly waiting for it to finish?
Or did the user switch to the workd processor because he
knows the script will take "forever"?


> for example, key strokes, mouse movements or any events received from any
> input device, not based on its CPU usage. I think applications like XMMS
> or mplayer shouldn't be considered interactive (at least, not until they
> start interacting with user), 
The're interactive if the user is staring at / listening to the output.

> and they have a constant usage of CPU.
> However, interactive applications have peaks, requiring shots of CPU for
> very short times. However, that's not necessarily true, as I said before
> with the example of the word processor: it could well be wasting 100% of
> CPU to perform spellchecking but it should still be considered an
> interactive application: a single user keystroke should take preference
> over the background spellchecking.

Use a multithreaded word processor and you'll get exactly this behaviour,
with the current system.  See above.

> 
> For terminal based, interactive applications (like pine, vi, and
> company), which are connected to tty devices, a user input event could
> make the scheduler boost the process priority for a brief time (and
> then, reduce the priority in a nearly quadratic fashion until reaching
> it's original, or a lower, priority) to give it a better response time
> and increase the interactive feeling.
> 
This works already, because the app slept waiting for that keystroke.


> However, for X11 based applications it seems a lot more difficult since
> all user-based input events are received by the X server itself (and not
> the process for which the event is intended). Based on the previous
> thoughts, the X11 server would be marked interactive, but not the
> application (like the word processor). This is not the desired effect.
> 
This usually works fine:  The part of X handling keystrokes
sleep - and get interactivity bonus when you press keys.

The apps waiting for X io sleeps, and get interactivity bonus
when they get something to do.  The sleep-based interactivity
estimate works here.

> So the question is, how can we detect the ultimate process for which the
> user input event is intended? Should the X11 server help the scheduler

That is _hard_, perhaps so hard that it isn't worth it.  Making it work
with X means a change to the X protocol (because the user might
wery well sit at some other pc/xterminal).  Unfortunately, the
other end might run something else than linux.


> by increasing the target process priority (it normally runs as root)?
> Should the window manager increase the priority of the process which
> owns the current foreground, active window? Solaris seems to work this

It can't without that X protocol change, for the "foreground process",
the "window manager" and the "X server" may all be running on three
different machines.

I do this all the time at home:
I sit at a pc that is configured as a X terminal.  It runs the X server
only.  My window manager and ordinary shells runs at another machine
with much better cpus.  (Why?  Because my girlfriend use the big machine
for reading mail and playing games) Then I log into my office pc
and runs some X apps from there.  Will your scheme work with
this - and work right?

If you only solves for the common case of one
user running all apps on the same machine, then my x-terminal
apps will wait too much for my girfriends games.  Even if
the office pc has plenty of free cpu time, because the big
machine won't give ssh priority enough to transfer the X output
to my xterminal.

This case works well today.

> way: when the user changes the focus to a new window, the window owner
> is brought into the interactive scheduling class. When the user chooses
> a new window, the window which loses the focus forces its owner to
> return to the time-shared scheduling class.
> 
> What do you think about all of this? Should we use behavior-based
> against CPU-usage behavior to decide process interactivity?
> 
I don't think you can make it work in all the cases where
today's system works well.  If you overload the machine something
has to wait - it is that simple.  Letting those that wait more than
they have to (i.e. io waiting) get extra priority seems to work
quite well.

Helge Hafting

Re: O(1) scheduler & interactivity improvements

[Felipe Alfaro Solana]

On Mon, 2003-06-23 at 10:09, Helge Hafting wrote:
> Felipe Alfaro Solana wrote:
> > As someone said before in the list, a process should be marked
> > "interactive" based on the fact that it's receiving user input, 
> 
> This is almost impossible to get right, except for a few very special
> cases like a single user working at the console.  Unix is supposed to
> do much better than that - the user logging in via a serial port,
> (or more commonly these days, via the network) should get exactly
> the same responsiveness as that console user.
> 
> Further, we may (sometimes) know that some devices is connected
> to a human.  But how about that script reading one disk file
> and writing to another?  Is it some cron job, did it start
> from some GUI menu with a user eagerly waiting for it to finish?
> Or did the user switch to the workd processor because he
> knows the script will take "forever"?

Maybe I have different a different idea of what "interactive" should be.
For me, an interactive process should have nearly-realtime response
times to user events. For example, if I click on a link in my web
browser's window, I want almost an immediate response:I want the process
to acknowledge the event, although it could be impossible to perform it
due to network latency, etc.

Currently, 2.5 kernels don't have a good "interactive" kernel, if we
stick to the previous definition of "interactive". I can easily starve
processes (XMMS) and moving windows around the screen do feel jerky and
laggy at best when the machine is loaded. For a normal desktop usage, I
prefer all my intensive tasks to start releasing more CPU cycles so
moving a window around the desktop feels completely smooth (sorry to
say, as Windows does). The same applies to repainting, or even launching
a new process.

> 
> 
> > for example, key strokes, mouse movements or any events received from any
> > input device, not based on its CPU usage. I think applications like XMMS
> > or mplayer shouldn't be considered interactive (at least, not until they
> > start interacting with user), 

> The're interactive if the user is staring at / listening to the output.

Or the user is feeding events to it, for example, by dragging a window,
clicking the mouse or pressing keys. If a process has received user
input in the past, ir's pretty probable that the process is an
interactive one.

I don't consider compiling the kernel an interactive process as it's
done almost automatically without any user intervention. XMMS is not a
complete interactive application as it spends most of the time decoding
and playing sound.

> Use a multithreaded word processor and you'll get exactly this behaviour,
> with the current system.  See above.

I agree. The word processor example was a bad one. Most word processors
are multithreaded.

> > For terminal based, interactive applications (like pine, vi, and
> > company), which are connected to tty devices, a user input event could
> > make the scheduler boost the process priority for a brief time (and
> > then, reduce the priority in a nearly quadratic fashion until reaching
> > it's original, or a lower, priority) to give it a better response time
> > and increase the interactive feeling.
> > 
> This works already, because the app slept waiting for that keystroke.

So then, why I can easily starve the X11 server (which should be marked
interactive), Evolution or OpenOffice simply by running "while true; do
a=2; done". Why don't they get an increased priority boost to stop the
from behaving so jerky?

> > by increasing the target process priority (it normally runs as root)?
> > Should the window manager increase the priority of the process which
> > owns the current foreground, active window? Solaris seems to work this
> 
> It can't without that X protocol change, for the "foreground process",
> the "window manager" and the "X server" may all be running on three
> different machines.

That's what is said at course SA-400 Solaris 8 Tuning from the Solaris
Official Curriculum. In fact, it works when working locally on a Solaris
8 or 9 machine.

Re: O(1) scheduler & interactivity improvements

[Daniel Gryniewicz]

On Mon, 2003-06-23 at 06:18, Felipe Alfaro Solana wrote:

> If a process has received user
> input in the past, ir's pretty probable that the process is an
> interactive one.

<snip>

> So then, why I can easily starve the X11 server (which should be marked
> interactive), Evolution or OpenOffice simply by running "while true; do
> a=2; done". Why don't they get an increased priority boost to stop the
> from behaving so jerky?

You're own metric will kill you here.  You're while true; loop is
running in the shell, which is interactive (it has accepted user in put
in the past) and can therefore easily starve anything else.  You need a
an easy way to make an interactive process non-interactive, and that's
what these threads are all about, making interactive threads
non-interactive (and the other way around) in a fashion that maximises
the user experience.  A history of user input is not necessarily a good
metric, as many non-interactive CPU hogs start out life as interactive
threads (like your loop above).
-- 
Daniel Gryniewicz <dang@fprintf.net>

Re: O(1) scheduler & interactivity improvements

[Felipe Alfaro Solana]

On Mon, 2003-06-23 at 18:21, Daniel Gryniewicz wrote:
> > So then, why I can easily starve the X11 server (which should be marked
> > interactive), Evolution or OpenOffice simply by running "while true; do
> > a=2; done". Why don't they get an increased priority boost to stop the
> > from behaving so jerky?
> 
> You're own metric will kill you here.  You're while true; loop is
> running in the shell, which is interactive (it has accepted user in put
> in the past) and can therefore easily starve anything else.  You need a
> an easy way to make an interactive process non-interactive, and that's
> what these threads are all about, making interactive threads
> non-interactive (and the other way around) in a fashion that maximises
> the user experience.  A history of user input is not necessarily a good
> metric, as many non-interactive CPU hogs start out life as interactive
> threads (like your loop above).

OK, replace "while true; ..." with a parallel kernel compile, for
example, and the effect, on a 700Mhz laptop, is nearly the same: you can
easily starve XMMS, and X11 feels jerky. Changing between virtual
desktops in KDE produces the same effect, also.

Memory? Re: O(1) scheduler & interactivity improvements

[Roger Larsson]

On måndagen den 23 juni 2003 20.59, Felipe Alfaro Solana wrote:
> On Mon, 2003-06-23 at 18:21, Daniel Gryniewicz wrote:
> > > So then, why I can easily starve the X11 server (which should be marked
> > > interactive), Evolution or OpenOffice simply by running "while true; do
> > > a=2; done". Why don't they get an increased priority boost to stop the
> > > from behaving so jerky?
> >
> > You're own metric will kill you here.  You're while true; loop is
> > running in the shell, which is interactive (it has accepted user in put
> > in the past) and can therefore easily starve anything else.  You need a
> > an easy way to make an interactive process non-interactive, and that's
> > what these threads are all about, making interactive threads
> > non-interactive (and the other way around) in a fashion that maximises
> > the user experience.  A history of user input is not necessarily a good
> > metric, as many non-interactive CPU hogs start out life as interactive
> > threads (like your loop above).
>
> OK, replace "while true; ..." with a parallel kernel compile, for
> example, and the effect, on a 700Mhz laptop, is nearly the same: you can
> easily starve XMMS, and X11 feels jerky. Changing between virtual
> desktops in KDE produces the same effect, also.

And you are shure that you do not fill up your RAM?
(700MHz laptop does not sound like lots of RAM...)

* Parallel kernel compile, unlimited?
* Changing virtual desktops might be memory limited too...

Check with 'vmstat'

/RogerL

-- 
Roger Larsson
Skellefteå
Sweden

Re: O(1) scheduler & interactivity improvements

[Helge Hafting]

On Mon, Jun 23, 2003 at 12:18:29PM +0200, Felipe Alfaro Solana wrote:
> On Mon, 2003-06-23 at 10:09, Helge Hafting wrote:
> > Felipe Alfaro Solana wrote:
> > > As someone said before in the list, a process should be marked
> > > "interactive" based on the fact that it's receiving user input, 
> > 
> > This is almost impossible to get right, except for a few very special
> > cases like a single user working at the console.  Unix is supposed to
> > do much better than that - the user logging in via a serial port,
> > (or more commonly these days, via the network) should get exactly
> > the same responsiveness as that console user.
> > 
> > Further, we may (sometimes) know that some devices is connected
> > to a human.  But how about that script reading one disk file
> > and writing to another?  Is it some cron job, did it start
> > from some GUI menu with a user eagerly waiting for it to finish?
> > Or did the user switch to the workd processor because he
> > knows the script will take "forever"?
> 
> Maybe I have different a different idea of what "interactive" should be.
> For me, an interactive process should have nearly-realtime response
> times to user events. For example, if I click on a link in my web
> browser's window, I want almost an immediate response:I want the process
> to acknowledge the event, although it could be impossible to perform it
> due to network latency, etc.
> 
Quick response is only possible if the job requested is small.
A big job won't happen quicly even if you get 100% cpu.
(Some sort of feedback ought to be possible though.)

> Currently, 2.5 kernels don't have a good "interactive" kernel, if we
> stick to the previous definition of "interactive". I can easily starve
> processes (XMMS) and moving windows around the screen do feel jerky and
> laggy at best when the machine is loaded. For a normal desktop usage, I
> prefer all my intensive tasks to start releasing more CPU cycles so
> moving a window around the desktop feels completely smooth (sorry to
> say, as Windows does). The same applies to repainting, or even launching
> a new process.
> 
I don't say the current 2.5 kernel is perfect - but I do
believe the current scheme (sleep-based priority) is good.
2.5 may need some tweaking to get good, such as:
 * how much boost for how much sleep
 * how long do you keep the boost

> > > for example, key strokes, mouse movements or any events received from any
> > > input device, not based on its CPU usage. I think applications like XMMS
> > > or mplayer shouldn't be considered interactive (at least, not until they
> > > start interacting with user), 
> 
> > The're interactive if the user is staring at / listening to the output.
> 
> Or the user is feeding events to it, for example, by dragging a window,
> clicking the mouse or pressing keys. If a process has received user
> input in the past, ir's pretty probable that the process is an
> interactive one.
> 
Except for when the user starts a cpu hog, which really is
almost all cpu hogs. :-/

> I don't consider compiling the kernel an interactive process as it's
> done almost automatically without any user intervention. XMMS is not a
> complete interactive application as it spends most of the time decoding
> and playing sound.
> 
A kernel compile isn't interactive - sure.  It may get some boosts
anyway for io waiting.  This quite correctly puts it above a
pure cpu hog like a mandelbrot calculation.

> > Use a multithreaded word processor and you'll get exactly this behaviour,
> > with the current system.  See above.
> 
> I agree. The word processor example was a bad one. Most word processors
> are multithreaded.
> 
> > > For terminal based, interactive applications (like pine, vi, and
> > > company), which are connected to tty devices, a user input event could
> > > make the scheduler boost the process priority for a brief time (and
> > > then, reduce the priority in a nearly quadratic fashion until reaching
> > > it's original, or a lower, priority) to give it a better response time
> > > and increase the interactive feeling.
> > > 
> > This works already, because the app slept waiting for that keystroke.
> 
> So then, why I can easily starve the X11 server (which should be marked
> interactive), Evolution or OpenOffice simply by running "while true; do
> a=2; done". Why don't they get an increased priority boost to stop the
> from behaving so jerky?
> 
A badly implemented or ill-tuned scheduler.  The loop isn't interactive.
Openoffice is a bad example though - it has _so_ much overhead
during startup that it seems to (correctly) become noninteractive.
 
> > > by increasing the target process priority (it normally runs as root)?
> > > Should the window manager increase the priority of the process which
> > > owns the current foreground, active window? Solaris seems to work this
> > 
> > It can't without that X protocol change, for the "foreground process",
> > the "window manager" and the "X server" may all be running on three
> > different machines.
> 
> That's what is said at course SA-400 Solaris 8 Tuning from the Solaris
> Official Curriculum. In fact, it works when working locally on a Solaris
> 8 or 9 machine.

Sure, you can do this locally, but that is not enough.  Being fair is
important, particularly in multi-user situations.  And multi-user becomes
_more_ common now that corporations realize they can save costs by
having 2-4 users share a single pc.  (Duplicate screens & keyboard, but
not the rest.)  Then there's remote login for administration,
spreading a large job over many pc's and so on.

Helge Hafting 

Re: O(1) scheduler & interactivity improvements

[Bill Davidsen]

On Mon, 23 Jun 2003, Helge Hafting wrote:

> On Mon, Jun 23, 2003 at 12:18:29PM +0200, Felipe Alfaro Solana wrote:

> > I don't consider compiling the kernel an interactive process as it's
> > done almost automatically without any user intervention. XMMS is not a
> > complete interactive application as it spends most of the time decoding
> > and playing sound.
> > 
> A kernel compile isn't interactive - sure.  It may get some boosts
> anyway for io waiting.  This quite correctly puts it above a
> pure cpu hog like a mandelbrot calculation.

Why? Not why does the scheduler do that, but why *should* a compile be in
any way more deserving that a Mandelbrot? It isn't obvious to me that
either are interacting with the user, and if they are it would be the
Mandelbrot doing realtime display.

-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: O(1) scheduler & interactivity improvements

[Helge Hafting]

On Tue, Jun 24, 2003 at 02:12:20PM -0400, Bill Davidsen wrote:
> On Mon, 23 Jun 2003, Helge Hafting wrote:
> 
> > On Mon, Jun 23, 2003 at 12:18:29PM +0200, Felipe Alfaro Solana wrote:
> 
> > > I don't consider compiling the kernel an interactive process as it's
> > > done almost automatically without any user intervention. XMMS is not a
> > > complete interactive application as it spends most of the time decoding
> > > and playing sound.
> > > 
> > A kernel compile isn't interactive - sure.  It may get some boosts
> > anyway for io waiting.  This quite correctly puts it above a
> > pure cpu hog like a mandelbrot calculation.
> 
> Why? Not why does the scheduler do that, but why *should* a compile be in
> any way more deserving that a Mandelbrot? It isn't obvious to me that
> either are interacting with the user, and if they are it would be the
> Mandelbrot doing realtime display.

This has nothing to do with "interacting with the user", the sleep-based
priority system solves other problems as well.  A pure cpu hog
utilizes all the cpu it gets.  A compile will end up waiting a lot for io
because it reads input files.  This starves the compile, the cpu hog
utilizes all of its timeslices plus the time the compile waits.
This is rectified by giving the compile a boost whenever it waits
(and lets someone else have the cpu).  This avoids penalizing processes
just because they do io or lots of io.  Readers would otherwise
progress very slowly in the precense of cpu hogs.

Incidentally, this also helps interactivity a lot because interactive
programs tend to wait for user input in the form of io, and when
they get it they get a boost and process the user input quickly.


As for my mandelbrot/compile example - the kernel cannot know
wether you:
* are busy watching fractals and just do a background compile,
or:
* wait for an important compile and pass some time rendering fractals
  when the compiler stall reading.

But you can tell it using explicit "nice"

Helge Hafting

Re: O(1) scheduler & interactivity improvements

[Helge Hafting]

Mike Galbraith wrote:
> At 02:12 PM 6/24/2003 -0400, Bill Davidsen wrote:
> 
>> On Mon, 23 Jun 2003, Helge Hafting wrote:
>>
>> > On Mon, Jun 23, 2003 at 12:18:29PM +0200, Felipe Alfaro Solana wrote:
>>
>> > > I don't consider compiling the kernel an interactive process as it's
>> > > done almost automatically without any user intervention. XMMS is 
>> not a
>> > > complete interactive application as it spends most of the time 
>> decoding
>> > > and playing sound.
>> > >
>> > A kernel compile isn't interactive - sure.  It may get some boosts
>> > anyway for io waiting.  This quite correctly puts it above a
>> > pure cpu hog like a mandelbrot calculation.
>>
>> Why? Not why does the scheduler do that, but why *should* a compile be in
>> any way more deserving that a Mandelbrot? It isn't obvious to me that
>> either are interacting with the user, and if they are it would be the
>> Mandelbrot doing realtime display.
> 
> 
> If the compile didn't receive a boost for it's io waits, the mandelbrot 
> would have an unfair advantage.  While the compile is sleeping, the 
> mandelbrot has sole access to the cpu.  Seems to me that this is quite 
> fair...
> 
>         -Mike
> 
> <semi-random thoughts>
> 
> ...until total sleep credit being accrued per unit time approaches unit 
> time?
> 
> At any rate, as soon as your cpu becomes saturated, tasks which 
> participate in the sleep bonus program can take over and starve the 
> sleep deprived _literally_ forever (iff the expired array is empty, 
> otherwise it's limited by STARVATION_TIMEOUT).  I think that hole needs 
> to be closed... at least the scheduler shouldn't default to starve 
> forever.  One way to combat active starvation would be to use lengthy 
> lack of idle calls to trigger periodic array switches.  That would 
> guarantee that everybody gets _some_ cpu.
> 
> ponders obnoxious ($&#!...;) irman process_load...
> 
> Too many random sleeper tasks steadily becoming runnable can DoS lower 
> priority tasks accidentally, but the irman process_load kind of DoS 
> seems to indicate a very heavy favoritism toward cooperating threads.  
> It seems to me that any thread group who's members sleep longer than 
> they run, and always has one member runnable is absolutely guaranteed to 
> cause terminal DoS.  Even if there isn't _always_ a member runnable, 
> waking a friend and waiting for him to do something seems like a very 
> likely thing for threaded process to do, which gives the threaded 
> process a huge advantage because the cumulative sleep_avg pool will 
> become large simply because it's members spend a lot of time jabbering 
> back and forth.
> 

How about _removing_ the io-wait bonus for waiting on pipes then?
If you wait for disk io, someone else gets to use
the cpu for their work.  So you get a boost for
giving up your share of time, waiting
for that slow device.

But if you wait for a pipe, you wait for some other
cpu hog to do the first part of _your_ work.
I.e. nobody else benefitted from your waiting,
so you don't get any boost either.

This solves the problem of someone artifically
dividing up a job, using token passing
to get unfair priority.


This can be fine-tuned a bit: We may want the pipe-waiter
to get a _little_ bonus at times, but that has to be
subtracted from whatever bonus the process at the
other end of the pipe has.  I.e. no new bonus
created, just shift some the existing bonus around.
The "other end" may, after all, have gained legitimate
bonus from waiting on the disk/network/paging/os, and passing
some of that on to "clients" might make sense.

So irman and similar pipe chains wouldn't be able to build
artifical priority, but if it get some priority
in an "acceptable" way then it is passed
along until it expires.

I.e. "bzcat file.bz2 | grep something | sort | less" could
pass priority down the chain when bzcat suffers
a long nfs wait...

Helge Hafting


> Take any two cpu hungry products.  Run one monolithic version, and one 
> chopped into little cooperative pieces at the same time, and the 
> monolithic version can get down to zero cpu.  An application developer 
> can greatly improve a shoddy product's appeal by chopping it up and 
> making the other guy's nice high speed low drag monolithic product look 
> like doggy doo in comparison.  He can show the other guy's product being 
> torn to ribbons by light load while his keeps right on ticking.  (he'll 
> cleverly avoid pointing out the fact that the light load he ripped his 
> competition's head off with gets no cpu while _his_ product is running)

Re: O(1) scheduler & interactivity improvements

[Mike Galbraith]

At 11:59 AM 6/26/2003 +0200, Helge Hafting wrote:
>Mike Galbraith wrote:
>
>>ponders obnoxious ($&#!...;) irman process_load...
>>Too many random sleeper tasks steadily becoming runnable can DoS lower 
>>priority tasks accidentally, but the irman process_load kind of DoS seems 
>>to indicate a very heavy favoritism toward cooperating threads.
>>It seems to me that any thread group who's members sleep longer than they 
>>run, and always has one member runnable is absolutely guaranteed to cause 
>>terminal DoS.  Even if there isn't _always_ a member runnable, waking a 
>>friend and waiting for him to do something seems like a very likely thing 
>>for threaded process to do, which gives the threaded process a huge 
>>advantage because the cumulative sleep_avg pool will become large simply 
>>because it's members spend a lot of time jabbering back and forth.
>
>How about _removing_ the io-wait bonus for waiting on pipes then?

That's been done.

>If you wait for disk io, someone else gets to use
>the cpu for their work.  So you get a boost for
>giving up your share of time, waiting
>for that slow device.
>
>But if you wait for a pipe, you wait for some other
>cpu hog to do the first part of _your_ work.
>I.e. nobody else benefitted from your waiting,
>so you don't get any boost either.
>
>This solves the problem of someone artifically
>dividing up a job, using token passing
>to get unfair priority.

For pipes.

         -Mike 

Re: O(1) scheduler & interactivity improvements

[Bill Davidsen]

On Thu, 26 Jun 2003, Helge Hafting wrote:

> This can be fine-tuned a bit: We may want the pipe-waiter
> to get a _little_ bonus at times, but that has to be
> subtracted from whatever bonus the process at the
> other end of the pipe has.  I.e. no new bonus
> created, just shift some the existing bonus around.
> The "other end" may, after all, have gained legitimate
> bonus from waiting on the disk/network/paging/os, and passing
> some of that on to "clients" might make sense.
> 
> So irman and similar pipe chains wouldn't be able to build
> artifical priority, but if it get some priority
> in an "acceptable" way then it is passed
> along until it expires.
> 
> I.e. "bzcat file.bz2 | grep something | sort | less" could
> pass priority down the chain when bzcat suffers
> a long nfs wait...

This is the case which worries me, passing back the priority of the
process which is waiting for user input. It's desirable, but hard to do
and subject to unintended boosts.

-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: O(1) scheduler & interactivity improvements

[Timothy Miller]

Helge Hafting wrote:

> How about _removing_ the io-wait bonus for waiting on pipes then?
> If you wait for disk io, someone else gets to use
> the cpu for their work.  So you get a boost for
> giving up your share of time, waiting
> for that slow device.
> 
> But if you wait for a pipe, you wait for some other
> cpu hog to do the first part of _your_ work.
> I.e. nobody else benefitted from your waiting,
> so you don't get any boost either.
> 
> This solves the problem of someone artifically
> dividing up a job, using token passing
> to get unfair priority.
> 
> 
> This can be fine-tuned a bit: We may want the pipe-waiter
> to get a _little_ bonus at times, but that has to be
> subtracted from whatever bonus the process at the
> other end of the pipe has.  I.e. no new bonus
> created, just shift some the existing bonus around.
> The "other end" may, after all, have gained legitimate
> bonus from waiting on the disk/network/paging/os, and passing
> some of that on to "clients" might make sense.
>

In other words:

Don't give pipe-waiting any kind of boost or penalty, but do balance the 
interactivity points between entities at each end of the pipe.

So, if you're waiting on a pipe, but the other end is a CPU hog, then 
since you don't get a boost (pipe wait), you don't give a boost to the 
CPU hog, but since he's a CPU hog, he DOES share negative points with 
you, lowering your priority.

Conversely, if a process is waiting on real I/O (disk, user input, 
etc.), then it gets an interactivity boost that it can share with other 
processes it's connected to via pipe.

Since most X clients only do pipe waiting on the server, then it's the X 
server that gets the interactivity boost by waiting on user input, which 
it can share with clients.

And since there is no effect from pipe wait, you can still judge a 
process as interactive or not based on what it does when it's NOT 
waiting on a pipe -- if it becomes a CPU hog THEN, you deduct points, etc.

Here's an interesting question:  Would you often have a situation where 
a process at one end of a pipe is a CPU hog, and the process at the 
other end is interactive?  Is that a problem?

If you're always adding or subtracting points, that situation could be 
less than optimal, but you'll never get to the point where the 
interactive process is believed to be a cpu hog or vice versa.  The 
points each process would be assessed at a faster rate than the sharing 
between processes.

Do you want to always share points, or do you share only when something 
wakes up from a pipe wait?

Re: O(1) scheduler & interactivity improvements

[Mike Galbraith]

At 10:50 AM 6/26/2003 -0400, Bill Davidsen wrote:
>On Thu, 26 Jun 2003, Helge Hafting wrote:
>
> > This can be fine-tuned a bit: We may want the pipe-waiter
> > to get a _little_ bonus at times, but that has to be
> > subtracted from whatever bonus the process at the
> > other end of the pipe has.  I.e. no new bonus
> > created, just shift some the existing bonus around.
> > The "other end" may, after all, have gained legitimate
> > bonus from waiting on the disk/network/paging/os, and passing
> > some of that on to "clients" might make sense.
> >
> > So irman and similar pipe chains wouldn't be able to build
> > artifical priority, but if it get some priority
> > in an "acceptable" way then it is passed
> > along until it expires.
> >
> > I.e. "bzcat file.bz2 | grep something | sort | less" could
> > pass priority down the chain when bzcat suffers
> > a long nfs wait...
>
>This is the case which worries me, passing back the priority of the
>process which is waiting for user input. It's desirable, but hard to do
>and subject to unintended boosts.

The thought of building/passing "connection" information around in the 
scheduler gives me a bad case of the willies.  I can imagine a process 
struct containing a list of components and their cpu usage information as a 
means to defeat fairness/starvation issues, but I can't imagine how to do 
that and retain high speed low drag O(1) scheduling.

Until someone demonstrates that the DoS/abuse scenarios I might be 
imagining are real, in C, I think I'll do the smart thing: try to stop 
worrying about it and stick to very very simple stuff.

         -Mike

(heck, i don't know why i'm even _thinking_ about it.  plain white cone 
doesn't cut it, and there's a "you have to be this tall" line at the 
entrance to the wizards section of the hat store;) 

Re: O(1) scheduler & interactivity improvements

[Helge Hafting]

Mike Galbraith wrote:

> The thought of building/passing "connection" information around in the 
> scheduler gives me a bad case of the willies.  I can imagine a process 
> struct containing a list of components and their cpu usage information 
> as a means to defeat fairness/starvation issues, but I can't imagine how 
> to do that and retain high speed low drag O(1) scheduling.
> 
The idea isn't that complicated.  When a process wakes up, make
a simple check to see what it woke up from.  Ordinary
io is handled as today, with a io boost.

A pipe wakeup can be handled by taking a look at the other end.
If the other process has interactivity bonus, grab half of
it.  (And halve the bonus belonging to that process.)
No bonus is created in this case, so no risk of DOS.
It is merely redistributed.

And it is simple - there is one thing that woke the
process up - so only one thing to check.

Hard corner cases can be avoided.  Perhaps bunch of pipes,
files, devices, sockets and page-ins becomes ready
simultaneosly.  A detailed priority calculation is clearly
pointless, so just use one of the things - or none.

> Until someone demonstrates that the DoS/abuse scenarios I might be 
> imagining are real, in C, I think I'll do the smart thing: try to stop 
> worrying about it and stick to very very simple stuff.

I thought the Irman thing was what killed the previous attempt
at redistributing priorities?

Helge Hafting

Re: O(1) scheduler & interactivity improvements

[Mike Galbraith]

At 10:18 AM 6/27/2003 +0200, Helge Hafting wrote:
>Mike Galbraith wrote:
>
>>The thought of building/passing "connection" information around in the 
>>scheduler gives me a bad case of the willies.  I can imagine a process 
>>struct containing a list of components and their cpu usage information as 
>>a means to defeat fairness/starvation issues, but I can't imagine how to 
>>do that and retain high speed low drag O(1) scheduling.
>The idea isn't that complicated.  When a process wakes up, make
>a simple check to see what it woke up from.  Ordinary
>io is handled as today, with a io boost.

(simple?  decode stack, find out where he was sleeping, and then have to 
decide what to do based upon that after _every sleep_?  sprinkle scheduling 
decisions around every place that does wakeups?... i can just imagine Al's 
reaction to someone suggesting that for the VFS... someone better run fast 
and hide well:)

>A pipe wakeup can be handled by taking a look at the other end.
>If the other process has interactivity bonus, grab half of
>it.  (And halve the bonus belonging to that process.)
>No bonus is created in this case, so no risk of DOS.
>It is merely redistributed.
>
>And it is simple - there is one thing that woke the
>process up - so only one thing to check.

How?

>Hard corner cases can be avoided.  Perhaps bunch of pipes,
>files, devices, sockets and page-ins becomes ready
>simultaneosly.  A detailed priority calculation is clearly
>pointless, so just use one of the things - or none.
>
>>Until someone demonstrates that the DoS/abuse scenarios I might be 
>>imagining are real, in C, I think I'll do the smart thing: try to stop 
>>worrying about it and stick to very very simple stuff.
>
>I thought the Irman thing was what killed the previous attempt
>at redistributing priorities?

What I think kills the priority redistribution idea is _massive_ 
complexity.  I don't see anything simple.  You would have to build the 
logical connections between tasks, which currently doesn't exist.  Wakeups 
and task switches are extremely light weight operations, and no decision 
you make at wakeup time has a ghost of a chance of not hurting like 
hell.  Just using the monotonic_clock() in the wakeup/schedule paths is 
fairly painful.  There is just no way you can run around looking for and 
processing "who shot JR" information in those paths (no way _I_ can imagine 
anyway) without absolutely destroying performance.

         -Mike 

Re: O(1) scheduler & interactivity improvements

[Helge Hafting]

Mike Galbraith wrote:
> At 10:18 AM 6/27/2003 +0200, Helge Hafting wrote:
> 
[...]

 > (simple?  decode stack, find out where he was sleeping,
Complicated indeed, but why do that?
A process sleeping on a pipe will wake up in the kernel's
pipe reading code, won't it?  No need for guessing where
it was sleeping.  Code for transferring interactivity
bonus could go right there.

> 
> What I think kills the priority redistribution idea is _massive_ 
> complexity.  I don't see anything simple.  You would have to build the 
> logical connections between tasks, which currently doesn't exist.  

I must admit I don't know the details of the scheduler.  Still, Linus
tried a form of redistribution (the backboost thing).  It helped in some 
cases.
It seems to me that it got revoked because it did the wrong
thing at times, leading to starvation issus that didn't exist before.
It didn't go because it was overly complex or slow?

Helge Hafting

> Wakeups and task switches are extremely light weight operations, and no 
> decision you make at wakeup time has a ghost of a chance of not hurting 
> like hell.  Just using the monotonic_clock() in the wakeup/schedule 
> paths is fairly painful.  There is just no way you can run around 
> looking for and processing "who shot JR" information in those paths (no 
> way _I_ can imagine anyway) without absolutely destroying performance.
> 

Re: O(1) scheduler & interactivity improvements

[Mike Galbraith]

At 01:39 PM 6/27/2003 +0200, Helge Hafting wrote:
>Mike Galbraith wrote:
>>At 10:18 AM 6/27/2003 +0200, Helge Hafting wrote:
>[...]
>
> > (simple?  decode stack, find out where he was sleeping,
>Complicated indeed, but why do that?
>A process sleeping on a pipe will wake up in the kernel's
>pipe reading code, won't it?  No need for guessing where
>it was sleeping.  Code for transferring interactivity
>bonus could go right there.

<G> Suggestion:  Re-read the part you snipped before you submit the patch.

>>What I think kills the priority redistribution idea is _massive_ 
>>complexity.  I don't see anything simple.  You would have to build the 
>>logical connections between tasks, which currently doesn't exist.
>
>I must admit I don't know the details of the scheduler.  Still, Linus
>tried a form of redistribution (the backboost thing).  It helped in some 
>cases.
>It seems to me that it got revoked because it did the wrong
>thing at times, leading to starvation issus that didn't exist before.
>It didn't go because it was overly complex or slow?

It went because it drove the system nuts sometimes.  Too bad that, it was 
lovely for GUI.

         -Mike 

Re: O(1) scheduler & interactivity improvements

[Bill Davidsen]

On Fri, 27 Jun 2003, Mike Galbraith wrote:


> (simple?  decode stack, find out where he was sleeping, and then have to 
> decide what to do based upon that after _every sleep_?  sprinkle scheduling 
> decisions around every place that does wakeups?... i can just imagine Al's 
> reaction to someone suggesting that for the VFS... someone better run fast 
> and hide well:)

I'm quoting the above to show I've read you objection, but I think you
have it backward.
> 
> >A pipe wakeup can be handled by taking a look at the other end.
> >If the other process has interactivity bonus, grab half of
> >it.  (And halve the bonus belonging to that process.)
> >No bonus is created in this case, so no risk of DOS.
> >It is merely redistributed.
> >
> >And it is simple - there is one thing that woke the
> >process up - so only one thing to check.
> 
> How?


> >Hard corner cases can be avoided.  Perhaps bunch of pipes,
> >files, devices, sockets and page-ins becomes ready
> >simultaneosly.  A detailed priority calculation is clearly
> >pointless, so just use one of the things - or none.
> >
> >>Until someone demonstrates that the DoS/abuse scenarios I might be 
> >>imagining are real, in C, I think I'll do the smart thing: try to stop 
> >>worrying about it and stick to very very simple stuff.
> >
> >I thought the Irman thing was what killed the previous attempt
> >at redistributing priorities?
> What I think kills the priority redistribution idea is _massive_ 
> complexity.  I don't see anything simple.  You would have to build the 
> logical connections between tasks, which currently doesn't exist.  Wakeups 
> and task switches are extremely light weight operations, and no decision 
> you make at wakeup time has a ghost of a chance of not hurting like 
> hell.  Just using the monotonic_clock() in the wakeup/schedule paths is 
> fairly painful.  There is just no way you can run around looking for and 
> processing "who shot JR" information in those paths (no way _I_ can imagine 
> anyway) without absolutely destroying performance.

Why do it at wakeup. Is it easier to just decide at the time of the
processes blocking to decisde there if it is blocking on an interactive
transaction? Is it that easy or is it really necessary to make the process
perfect?

-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: O(1) scheduler & interactivity improvements

[Mike Galbraith]

At 11:51 PM 6/27/2003 -0400, Bill Davidsen wrote:
>On Fri, 27 Jun 2003, Mike Galbraith wrote:
>
>
> > (simple?  decode stack, find out where he was sleeping, and then have to
> > decide what to do based upon that after _every sleep_?  sprinkle 
> scheduling
> > decisions around every place that does wakeups?... i can just imagine Al's
> > reaction to someone suggesting that for the VFS... someone better run fast
> > and hide well:)
>
>I'm quoting the above to show I've read you objection, but I think you
>have it backward.
> >
> > >A pipe wakeup can be handled by taking a look at the other end.
> > >If the other process has interactivity bonus, grab half of
> > >it.  (And halve the bonus belonging to that process.)
> > >No bonus is created in this case, so no risk of DOS.
> > >It is merely redistributed.
> > >
> > >And it is simple - there is one thing that woke the
> > >process up - so only one thing to check.
> >
> > How?
>
>
> > >Hard corner cases can be avoided.  Perhaps bunch of pipes,
> > >files, devices, sockets and page-ins becomes ready
> > >simultaneosly.  A detailed priority calculation is clearly
> > >pointless, so just use one of the things - or none.
> > >
> > >>Until someone demonstrates that the DoS/abuse scenarios I might be
> > >>imagining are real, in C, I think I'll do the smart thing: try to stop
> > >>worrying about it and stick to very very simple stuff.
> > >
> > >I thought the Irman thing was what killed the previous attempt
> > >at redistributing priorities?
> > What I think kills the priority redistribution idea is _massive_
> > complexity.  I don't see anything simple.  You would have to build the
> > logical connections between tasks, which currently doesn't exist.  Wakeups
> > and task switches are extremely light weight operations, and no decision
> > you make at wakeup time has a ghost of a chance of not hurting like
> > hell.  Just using the monotonic_clock() in the wakeup/schedule paths is
> > fairly painful.  There is just no way you can run around looking for and
> > processing "who shot JR" information in those paths (no way _I_ can 
> imagine
> > anyway) without absolutely destroying performance.
>
>Why do it at wakeup. Is it easier to just decide at the time of the
>processes blocking to decisde there if it is blocking on an interactive
>transaction? Is it that easy or is it really necessary to make the process
>perfect?

I'm no clean freak, but fiddling with scheduling information all over the 
place seems like a very bad idea. (before anyone says it, yes, we fiddle 
with state all over the place;)  I can imagine doing something dirty in 
driver code for specific cases (kdb/mouse are always interactivity 
indicators), but not in generic code.

Besides, the logical bindings for foo | bar | ... | baz do not exist in the 
kernel.  The kernel knows and cares only that single entities are using 
open/read/write/close primitives.  This is why I said I could _imagine_ a 
process struct... as the container for this missing (it lives in userland) 
information.

Another besides:  it makes zero difference it you add overhead to wakeup 
time or go to sleep time.  If it's something you do a lot of, adding 
overhead to it is going to hurt a lot.

         -Mike 

Re: O(1) scheduler & interactivity improvements

[Helge Hafting]

On Sat, Jun 28, 2003 at 07:44:26AM +0200, Mike Galbraith wrote:
[...]
> 
> I'm no clean freak, but fiddling with scheduling information all over the 
> place seems like a very bad idea. (before anyone says it, yes, we fiddle 
> with state all over the place;)  I can imagine doing something dirty in 
> driver code for specific cases (kdb/mouse are always interactivity 
> indicators), but not in generic code.
> 
> Besides, the logical bindings for foo | bar | ... | baz do not exist in the 
> kernel.  The kernel knows and cares only that single entities are using 
> open/read/write/close primitives.  

Data is moved from one process to the next, so the logical binding
exists.  It may exist only for the duration of the write & read
calls, but that is enough for this purpose.

Info about the data being transferred (address, amount) must exist somewhere,
or data written to pipes would be lost.  This is updated when
someone writes into a pipe.  The kernel could, during the write call,
transfer some interactvity bonus (if any) and store it along with
the other information about the pipe.  

The pipe read call would simply grab any transferred bonus and
add it to the reader's interactivity bonus.  This should only be
a few integer operations on either end of the pipe. 
The io boost calculated for disk/device operations surely amounts to some
code too. It don't mess with every wakeup imaginable, this is specific to
pipes. 

> This is why I said I could _imagine_ a 
> process struct... as the container for this missing (it lives in userland) 
> information.
> 
> Another besides:  it makes zero difference it you add overhead to wakeup 
> time or go to sleep time.  If it's something you do a lot of, adding 
> overhead to it is going to hurt a lot.
> 
No doubt about that.  Transferring an extra int per pipe read/write
is overhead, I hope the data part of the transfer typically is much
bigger than that.

Helge Hafting

Re: O(1) scheduler & interactivity improvements

[Mike Galbraith]

At 04:34 PM 6/28/2003 +0200, Helge Hafting wrote:
>On Sat, Jun 28, 2003 at 07:44:26AM +0200, Mike Galbraith wrote:
>[...]
> >
> > I'm no clean freak, but fiddling with scheduling information all over the
> > place seems like a very bad idea. (before anyone says it, yes, we fiddle
> > with state all over the place;)  I can imagine doing something dirty in
> > driver code for specific cases (kdb/mouse are always interactivity
> > indicators), but not in generic code.
> >
> > Besides, the logical bindings for foo | bar | ... | baz do not exist in 
> the
> > kernel.  The kernel knows and cares only that single entities are using
> > open/read/write/close primitives.
>
>Data is moved from one process to the next, so the logical binding
>exists.  It may exist only for the duration of the write & read
>calls, but that is enough for this purpose.

I don't think it is enough, and regarding logical binding, we're talking 
past each other.

>Info about the data being transferred (address, amount) must exist somewhere,
>or data written to pipes would be lost.  This is updated when
>someone writes into a pipe.  The kernel could, during the write call,
>transfer some interactvity bonus (if any) and store it along with
>the other information about the pipe.

Well, yes, you can make a bucket to attach something to the data.  What are 
you going to attach to the data of irman's two completely independent pipe 
rings that is going to prevent either one or the total of the irman process 
from eating 100% cpu while I'm trying to login?  See what I mean?  When I 
say logical binding, I mean an information bucket that the system can look 
at and determine that process irman has had enough for now, and process 
mikie_logs_is needs a shot of cpu, or process threaded application A vs 
process monolithic application B.

It doesn't really matter that we're talking past each other though.  IMHO, 
the idea of spreading scheduling information around is at best horribly 
ugly, and the idea of a process context is at best horribly 
impractical.  I'd stamp a 0xdeadbeef on both ;-)

>The pipe read call would simply grab any transferred bonus and
>add it to the reader's interactivity bonus.  This should only be
>a few integer operations on either end of the pipe.
>The io boost calculated for disk/device operations surely amounts to some
>code too. It don't mess with every wakeup imaginable, this is specific to
>pipes.

However, I don't think that priority inflation is specific to pipes.

>  > This is why I said I could _imagine_ a
> > process struct... as the container for this missing (it lives in userland)
> > information.
> >
> > Another besides:  it makes zero difference it you add overhead to wakeup
> > time or go to sleep time.  If it's something you do a lot of, adding
> > overhead to it is going to hurt a lot.
> >
>No doubt about that.  Transferring an extra int per pipe read/write
>is overhead, I hope the data part of the transfer typically is much
>bigger than that.

True.

         -Mike 

Re: O(1) scheduler & interactivity improvements

[Bill Davidsen]

On Sat, 28 Jun 2003, Mike Galbraith wrote:

> At 11:51 PM 6/27/2003 -0400, Bill Davidsen wrote:
> >Why do it at wakeup. Is it easier to just decide at the time of the
> >processes blocking to decisde there if it is blocking on an interactive
> >transaction? Is it that easy or is it really necessary to make the process
> >perfect?
> 
> I'm no clean freak, but fiddling with scheduling information all over the 
> place seems like a very bad idea. (before anyone says it, yes, we fiddle 
> with state all over the place;)  I can imagine doing something dirty in 
> driver code for specific cases (kdb/mouse are always interactivity 
> indicators), but not in generic code.
> 
> Besides, the logical bindings for foo | bar | ... | baz do not exist in the 
> kernel.  The kernel knows and cares only that single entities are using 
> open/read/write/close primitives.  This is why I said I could _imagine_ a 
> process struct... as the container for this missing (it lives in userland) 
> information.
> 
> Another besides:  it makes zero difference it you add overhead to wakeup 
> time or go to sleep time.  If it's something you do a lot of, adding 
> overhead to it is going to hurt a lot.

True, but at block time you have more information. If a process blocks on
pipe read, presumably it's in the pipe read code that the process is
blocked, and that code is not common to disk read, keyboard read, socket
read, etc. Atleast not all of it is...

If you try to do something at unblock, you have to determine why the
process blocked. But if you do it at block time you have that information.
Therefore you should have a lot less overhead to add, which is why I think
it's a win over finding "what happened?" at unblock.

-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: O(1) scheduler & interactivity improvements

[jw schultz]

On Thu, Jun 26, 2003 at 11:59:36AM +0200, Helge Hafting wrote:
> How about _removing_ the io-wait bonus for waiting on pipes then?
> If you wait for disk io, someone else gets to use
> the cpu for their work.  So you get a boost for
> giving up your share of time, waiting
> for that slow device.
> 
> But if you wait for a pipe, you wait for some other
> cpu hog to do the first part of _your_ work.
> I.e. nobody else benefitted from your waiting,
> so you don't get any boost either.
> 
> This solves the problem of someone artifically
> dividing up a job, using token passing
> to get unfair priority.
> 
> This can be fine-tuned a bit: We may want the pipe-waiter
> to get a _little_ bonus at times, but that has to be
> subtracted from whatever bonus the process at the
> other end of the pipe has.  I.e. no new bonus
> created, just shift some the existing bonus around.
> The "other end" may, after all, have gained legitimate
> bonus from waiting on the disk/network/paging/os, and passing
> some of that on to "clients" might make sense.
> 
> So irman and similar pipe chains wouldn't be able to build
> artifical priority, but if it get some priority
> in an "acceptable" way then it is passed
> along until it expires.
> 
> I.e. "bzcat file.bz2 | grep something | sort | less" could
> pass priority down the chain when bzcat suffers
> a long nfs wait...

You don't want to penalise pipes either.  I can just imagine
some nutcase shifting from pipes to a less efficient
communications channel to shave 5% off his run time.

-- 
________________________________________________________________
	J.W. Schultz            Pegasystems Technologies
	email address:		jw@pegasys.ws

		Remember Cernan and Schmitt