From: Ingo Molnar
Subject: Re: Network slowdown due to CFS
Date: Oct 1, 9:25 am 2007

* Jarek Poplawski <jarkao2@o2.pl> wrote:

> BTW, it looks like risky to criticise sched_yield too much: some 
> people can misinterpret such discussions and stop using this at all, 
> even where it's right.

Really, i have never seen a _single_ mainstream app where the use of 
sched_yield() was the right choice.

Fortunately, the sched_yield() API is already one of the most rarely 
used scheduler functionalities, so it does not really matter. [ In my 
experience a Linux scheduler is stabilizing pretty well when the 
discussion shifts to yield behavior, because that shows that everything 
else is pretty much fine ;-) ]

But, because you assert it that it's risky to "criticise sched_yield() 
too much", you sure must know at least one real example where it's right 
to use it (and cite the line and code where it's used, with 
specificity)?

	Ingo
-


From: David Schwartz
Subject: RE: Network slowdown due to CFS
Date: Oct 1, 9:49 am 2007

> * Jarek Poplawski <jarkao2@o2.pl> wrote:
>
> > BTW, it looks like risky to criticise sched_yield too much: some
> > people can misinterpret such discussions and stop using this at all,
> > even where it's right.

> Really, i have never seen a _single_ mainstream app where the use of
> sched_yield() was the right choice.

It can occasionally be an optimization. You may have a case where you can do
something very efficiently if a lock is not held, but you cannot afford to
wait for the lock to be released. So you check the lock, if it's held, you
yield and then check again. If that fails, you do it the less optimal way
(for example, dispatching it to a thread that *can* afford to wait).

It is also sometimes used in the implementation of spinlock-type primitives.
After spinning fails, yielding is tried.

I think it's also sometimes appropriate when a thread may monopolize a
mutex. For example, consider a rarely-run task that cleans up some expensive
structures. It may need to hold locks that are only held during this complex
clean up.

One example I know of is a defragmenter for a multi-threaded memory
allocator, and it has to lock whole pools. When it releases these locks, it
calls yield before re-acquiring them to go back to work. The idea is to "go
to the back of the line" if any threads are blocking on those mutexes.

There are certainly other ways to do these things, but I have seen cases
where, IMO, yielding was the best solution. Doing nothing would have been
okay too.

> Fortunately, the sched_yield() API is already one of the most rarely
> used scheduler functionalities, so it does not really matter. [ In my
> experience a Linux scheduler is stabilizing pretty well when the
> discussion shifts to yield behavior, because that shows that everything
> else is pretty much fine ;-) ]

Can you explain what the current sched_yield behavior *is* for CFS and what
the tunable does to change it?

The desired behavior is for the current thread to not be rescheduled until
every thread at the same static priority as this thread has had a chance to
be scheduled.

Of course, it's not clear exactly what a "chance" is.

The semantics with respect to threads at other static priority levels is not
clear. Ditto for SMP issues. It's also not clear whether threads that yield
should be rewarded or punished for doing so.

DS


-


From: Ingo Molnar
Subject: Re: Network slowdown due to CFS
Date: Oct 1, 10:31 am 2007

* David Schwartz <davids@webmaster.com> wrote:

> > > BTW, it looks like risky to criticise sched_yield too much: some 
> > > people can misinterpret such discussions and stop using this at 
> > > all, even where it's right.
> 
> > Really, i have never seen a _single_ mainstream app where the use of 
> > sched_yield() was the right choice.
> 
> It can occasionally be an optimization. You may have a case where you 
> can do something very efficiently if a lock is not held, but you 
> cannot afford to wait for the lock to be released. So you check the 
> lock, if it's held, you yield and then check again. If that fails, you 
> do it the less optimal way (for example, dispatching it to a thread 
> that *can* afford to wait).

These are generic statements, but i'm _really_ interested in the 
specifics. Real, specific code that i can look at. The typical Linux 
distro consists of in execess of 500 millions of lines of code, in tens 
of thousands of apps, so there really must be some good, valid and 
"right" use of sched_yield() somewhere in there, in some mainstream app, 
right? (because, as you might have guessed it, in the past decade of 
sched_yield() existence i _have_ seen my share of sched_yield() 
utilizing user-space code, and at the moment i'm not really impressed by 
those examples.)
 
Preferably that example should show that the best quality user-space 
lock implementation in a given scenario is best done via sched_yield(). 
Actual code and numbers. (And this isnt _that_ hard. I'm not asking for 
a full RDBMS implementation that must run through SQL99 spec suite. This 
is about a simple locking primitive, or a simple pointer to an existing 
codebase.)

> It is also sometimes used in the implementation of spinlock-type 
> primitives. After spinning fails, yielding is tried.

(user-space spinlocks are broken beyond words for anything but perhaps 
SCHED_FIFO tasks.)

> One example I know of is a defragmenter for a multi-threaded memory 
> allocator, and it has to lock whole pools. When it releases these 
> locks, it calls yield before re-acquiring them to go back to work. The 
> idea is to "go to the back of the line" if any threads are blocking on 
> those mutexes.

at a quick glance this seems broken too - but if you show the specific 
code i might be able to point out the breakage in detail. (One 
underlying problem here appears to be fairness: a quick unlock/lock 
sequence may starve out other threads. yield wont solve that fundamental 
problem either, and it will introduce random latencies into apps using 
this memory allocator.)

> > Fortunately, the sched_yield() API is already one of the most rarely
> > used scheduler functionalities, so it does not really matter. [ In my
> > experience a Linux scheduler is stabilizing pretty well when the
> > discussion shifts to yield behavior, because that shows that everything
> > else is pretty much fine ;-) ]
> 
> Can you explain what the current sched_yield behavior *is* for CFS and 
> what the tunable does to change it?

sure. (and i described that flag on lkml before) The sched_yield flag 
does two things:

 - if 0 ("opportunistic mode"), then the task will reschedule to any
   other task that is in "bigger need for CPU time" than the currently 
   running task, as indicated by CFS's ->wait_runtime metric. (or as 
   indicated by the similar ->vruntime metric in sched-devel.git)

 - if 1 ("agressive mode"), then the task will be one-time requeued to 
   the right end of the CFS rbtree. This means that for one instance, 
   all other tasks will run before this task will run again - after that 
   this task's natural ordering within the rbtree is restored.

> The desired behavior is for the current thread to not be rescheduled 
> until every thread at the same static priority as this thread has had 
> a chance to be scheduled.

do you realize that this "desired behavior" you just described is not 
achieved by the old scheduler, and that this random behavior _is_ the 
main problem here? If yield was well-specified then we could implement 
it in a well-specified way - even if the API was poor.

But fact is that it is _not_ well-specified, and apps grew upon a random 
scheduler implementation details in random ways. (in the lkml discussion 
about this topic, Linus offered a pretty sane theoretical definition for 
yield but it's not simple to implement [and no scheduler implements it 
at the moment] - nor will it map to the old scheduler's yield behavior 
so we'll end up breaking more apps.)

	Ingo
-


From: David Schwartz
Subject: RE: Network slowdown due to CFS
Date: Oct 1, 11:23 am 2007

> These are generic statements, but i'm _really_ interested in the
> specifics. Real, specific code that i can look at. The typical Linux
> distro consists of in execess of 500 millions of lines of code, in tens
> of thousands of apps, so there really must be some good, valid and
> "right" use of sched_yield() somewhere in there, in some mainstream app,
> right? (because, as you might have guessed it, in the past decade of
> sched_yield() existence i _have_ seen my share of sched_yield()
> utilizing user-space code, and at the moment i'm not really impressed by
> those examples.)

Maybe, maybe not. Even if so, it would be very difficult to find. Simply
grepping for sched_yield is not going to help because determining whether a
given use of sched_yield is smart is not going to be easy.

> (user-space spinlocks are broken beyond words for anything but perhaps
> SCHED_FIFO tasks.)

User-space spinlocks are broken so spinlocks can only be implemented in
kernel-space? Even if you use the kernel to schedule/unschedule the tasks,
you still have to spin in user-space.

> > One example I know of is a defragmenter for a multi-threaded memory
> > allocator, and it has to lock whole pools. When it releases these
> > locks, it calls yield before re-acquiring them to go back to work. The
> > idea is to "go to the back of the line" if any threads are blocking on
> > those mutexes.

> at a quick glance this seems broken too - but if you show the specific
> code i might be able to point out the breakage in detail. (One
> underlying problem here appears to be fairness: a quick unlock/lock
> sequence may starve out other threads. yield wont solve that fundamental
> problem either, and it will introduce random latencies into apps using
> this memory allocator.)

You are assuming that random latencies are necessarily bad. Random latencies
may be significantly better than predictable high latency.


> > Can you explain what the current sched_yield behavior *is* for CFS and
> > what the tunable does to change it?

> sure. (and i described that flag on lkml before) The sched_yield flag
> does two things:

>  - if 0 ("opportunistic mode"), then the task will reschedule to any
>    other task that is in "bigger need for CPU time" than the currently
>    running task, as indicated by CFS's ->wait_runtime metric. (or as
>    indicated by the similar ->vruntime metric in sched-devel.git)
>
>  - if 1 ("agressive mode"), then the task will be one-time requeued to
>    the right end of the CFS rbtree. This means that for one instance,
>    all other tasks will run before this task will run again - after that
>    this task's natural ordering within the rbtree is restored.

Thank you. Unfortunately, neither of these does what sched_yiled is really
supposed to do. Opportunistic mode does too little and agressive mode does
too much.

> > The desired behavior is for the current thread to not be rescheduled
> > until every thread at the same static priority as this thread has had
> > a chance to be scheduled.

> do you realize that this "desired behavior" you just described is not
> achieved by the old scheduler, and that this random behavior _is_ the
> main problem here? If yield was well-specified then we could implement
> it in a well-specified way - even if the API was poor.

> But fact is that it is _not_ well-specified, and apps grew upon a random
> scheduler implementation details in random ways. (in the lkml discussion
> about this topic, Linus offered a pretty sane theoretical definition for
> yield but it's not simple to implement [and no scheduler implements it
> at the moment] - nor will it map to the old scheduler's yield behavior
> so we'll end up breaking more apps.)

I don't have a problem with failing to emulate the old scheduler's behavior
if we can show that the new behavior has saner semantics. Unfortunately, in
this case, I think CFS' semantics are pretty bad. Neither of these is what
sched_yield is supposed to do.

Note that I'm not saying this is a particularly big deal. And I'm not
calling CFS' behavior a regression, since it's not really better or worse
than the old behavior, simply different.

I'm not familiar enough with CFS' internals to help much on the
implementation, but there may be some simple compromise yield that might
work well enough. How about simply acting as if the task used up its
timeslice and scheduling the next one? (Possibly with a slight reduction in
penalty or reward for not really using all the time, if possible?)

DS


-


From: Ingo Molnar
Subject: Re: yield API
Date: Oct 1, 11:46 pm 2007

* David Schwartz <davids@webmaster.com> wrote:

> > These are generic statements, but i'm _really_ interested in the 
> > specifics. Real, specific code that i can look at. The typical Linux 
> > distro consists of in execess of 500 millions of lines of code, in 
> > tens of thousands of apps, so there really must be some good, valid 
> > and "right" use of sched_yield() somewhere in there, in some 
> > mainstream app, right? (because, as you might have guessed it, in 
> > the past decade of sched_yield() existence i _have_ seen my share of 
> > sched_yield() utilizing user-space code, and at the moment i'm not 
> > really impressed by those examples.)
> 
> Maybe, maybe not. Even if so, it would be very difficult to find. 
> Simply grepping for sched_yield is not going to help because 
> determining whether a given use of sched_yield is smart is not going 
> to be easy.

sched_yield() has been around for a decade (about three times longer 
than futexes were around), so if it's useful, it sure should have grown 
some 'crown jewel' app that uses it and shows off its advantages, 
compared to other locking approaches, right?

For example, if you asked me whether pipes are the best thing for 
certain apps, i could immediately show you tons of examples where they 
are. Same for sockets. Or RT priorities. Or nice levels. Or futexes. Or 
just about any other core kernel concept or API. Your notion that 
showing a good example of an API would be "difficult" because it's hard 
to determine "smart" use is not tenable i believe and does not 
adequately refute my pretty plain-meaning "it does not exist" assertion.

If then this is one more supporting proof for the fundamental weakness 
of the sched_yield() API. Rarely are we able to so universally condemn 
an API: real-life is usually more varied and even for theoretically 
poorly defined APIs _some_ sort of legitimate use does grow up.

APIs that are not in any real, meaningful use, despite a decade of 
presence are not really interesting to me personally. (especially in 
this case where we know exactly _why_ the API is used so rarely.) Sure 
we'll continue to support it in the best possible way, with the usual 
kernel maintainance policy: without hurting other, more commonly used 
APIs. That was the principle we followed in previous schedulers too. And 
if anyone has a patch to make sched_yield() better than it is today, i'm 
of course interested in it.

	Ingo
-

From: Chris Friesen
Subject: Re: Network slowdown due to CFS
Date: Oct 1, 9:55 am 2007

Ingo Molnar wrote:

> But, because you assert it that it's risky to "criticise sched_yield() 
> too much", you sure must know at least one real example where it's right 
> to use it (and cite the line and code where it's used, with 
> specificity)?

It's fine to criticise sched_yield().  I agree that new apps should 
generally be written to use proper completion mechanisms or to wait for 
specific events.

However, there are closed-source and/or frozen-source apps where it's 
not practical to rewrite or rebuild the app.  Does it make sense to 
break the behaviour of all of these?

Chris
-


From: Ingo Molnar
Subject: Re: Network slowdown due to CFS
Date: Oct 1, 10:09 am 2007

* Chris Friesen <cfriesen@nortel.com> wrote:

> Ingo Molnar wrote:
> 
> >But, because you assert it that it's risky to "criticise sched_yield() 
> >too much", you sure must know at least one real example where it's right 
> >to use it (and cite the line and code where it's used, with 
> >specificity)?
> 
> It's fine to criticise sched_yield().  I agree that new apps should 
> generally be written to use proper completion mechanisms or to wait 
> for specific events.

yes.

> However, there are closed-source and/or frozen-source apps where it's 
> not practical to rewrite or rebuild the app.  Does it make sense to 
> break the behaviour of all of these?

See the background and answers to that in:

   http://lkml.org/lkml/2007/9/19/357
   http://lkml.org/lkml/2007/9/19/328

there's plenty of recourse possible to all possible kinds of apps. Tune 
the sysctl flag in one direction or another, depending on which behavior 
the app is expecting.

	Ingo
-