At 06:12 PM 5/28/2003 -0400, Bill Davidsen wrote:
>On Wed, 21 May 2003, Olivier Galibert wrote:
>
> > On Wed, May 21, 2003 at 03:12:12PM +0200, Arjan van de Ven wrote:
> > > if you had spent the time you spent on this colorful graphic on reading
> > > SUS or Posix about what sched_yield() means, you would actually have
> > > learned something. sched_yield() means "I'm the least important thing in
> > > the system".
> >
> > Susv2:
> >
> > DESCRIPTION
> >
> > The sched_yield() function forces the running thread to relinquish
> > the processor until it again becomes the head of its thread list. It
> > takes no arguments.
> >
> >
> > Aka "I skip the rest of my turn, try the others again once", not "I'm
> > unimportant" nor "please rerun me immediatly".
> >
> > What is it with you people wanting to make sched_yield() unusable for
> > anything that makes sense?
>
>Have to agree, I have a context switching benchmark which uses a spinlock
>in shared memory for do-it-yourself gating, and it wants sched_yeild() to
>be useful on uni. The SuS is pretty clear about this, the useful behaviour
>is also the required behaviour, why are people resisting doing it that
>way?
It can be argued that the current implementation does exactly what SuS
describes. The thread's list can be considered to be the sum of the active
queue and the expired queue. Merely rotating the active queue and
scheduling away excludes the yielding thread's equally important expired
peers from participation in the game. Furthermore, if you are the only
thread left in the active array, (you are at the head obviously), and all
of your peers are currently expired, yielding would become meaningless...
the thing you're trying to yield (the remainder of your slice) sticks to you.
Having said that, it can also be argued that we are violating the SuS
description in that yielding the remainder of your slice yields to all
threads in all lists, not only it's list. What makes more sense to me than
the current implementation is to rotate the entire peer queue when a thread
expires... ie pull in the head of the expired queue into the tail of the
active queue at the same time so you always have a player if one
exists. (you'd have to select queues based on used cpu time to make that
work right though)
That would still suck rocks for mutex usage... as it must with any
implementation of sched_yield() in the presence of peer threads who are not
playing with the mutex. Actually, using sched_yield() makes no sense what
so ever to me, other than what Arjan said. It refers to yielding your
turn, but from userland "your turn" has no determinate meaning. There is
exactly one case where it has a useable value, and that is when you're the
_only_ runnable thread... at which time it means precisely zero. (blech)
-Mike
On Thu, 29 May 2003, Mike Galbraith wrote:
> [...] What makes more sense to me than the current implementation is to
> rotate the entire peer queue when a thread expires... ie pull in the
> head of the expired queue into the tail of the active queue at the same
> time so you always have a player if one exists. (you'd have to select
> queues based on used cpu time to make that work right though)
we have tried all sorts of more complex yield() schemes before - they
sucked for one or another workload. So in 2.5 i took the following path:
make yield() _simple_ and effective, ie. expire the yielding task (push it
down the runqueue roughly halfway, statistically) and dont try to be too
smart doing it. All the real yield() users (mostly in the kernel) want it
to be an efficient way to avoid livelocks. The old 2.4 yield
implementation had the problem of enabling a ping-pong between two
higher-prio yielding processes, until they use up their full timeslice.
(we could do one more thing that still keeps the thing simple: we could
re-set the yielding task's timeslice instead of the current 'keep the
previous timeslice' logic.)
OpenOffice used to use yield() as a legacy of 'green thread'
implementation - where userspace threads needed to do periodic yield()s to
get any sort of multitasking behavior.
Ingo
On Thu, 29 May 2003, Mike Galbraith wrote:
> That would still suck rocks for mutex usage... as it must with any
> implementation of sched_yield() in the presence of peer threads who are not
> playing with the mutex. Actually, using sched_yield() makes no sense what
> so ever to me, other than what Arjan said. It refers to yielding your
> turn, but from userland "your turn" has no determinate meaning. There is
> exactly one case where it has a useable value, and that is when you're the
> _only_ runnable thread... at which time it means precisely zero. (blech)
No, it works usefully without threads at all, with processes sharing a
spinlock in shared memory. If the lock is closed process does a
sched_yeild() to allow whoever has the lock to run. Yes to all comments
WRT order of running, if you care you don't do this, clearly. But in the
case where a process forks to a feeder and consumer it's faster than
semaphores, signal, etc.
All that's needed is to put the yeild process on the end of the
appropriate run queue and reschedule. Doing anything else results in bad
performance and no gain to anything else.
--
bill davidsen <[email protected]>
CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.
On Mon, 2 Jun 2003, Ingo Molnar wrote:
>
> On Thu, 29 May 2003, Mike Galbraith wrote:
>
> > [...] What makes more sense to me than the current implementation is to
> > rotate the entire peer queue when a thread expires... ie pull in the
> > head of the expired queue into the tail of the active queue at the same
> > time so you always have a player if one exists. (you'd have to select
> > queues based on used cpu time to make that work right though)
>
> we have tried all sorts of more complex yield() schemes before - they
> sucked for one or another workload. So in 2.5 i took the following path:
> make yield() _simple_ and effective, ie. expire the yielding task (push it
> down the runqueue roughly halfway, statistically) and dont try to be too
> smart doing it. All the real yield() users (mostly in the kernel) want it
> to be an efficient way to avoid livelocks. The old 2.4 yield
> implementation had the problem of enabling a ping-pong between two
> higher-prio yielding processes, until they use up their full timeslice.
>
> (we could do one more thing that still keeps the thing simple: we could
> re-set the yielding task's timeslice instead of the current 'keep the
> previous timeslice' logic.)
>
> OpenOffice used to use yield() as a legacy of 'green thread'
> implementation - where userspace threads needed to do periodic yield()s to
> get any sort of multitasking behavior.
The way I use it is in cases when I fork processes which communicate
through a state machine (I'm simplifying) gated by a spinlock, both in
shared memory. On SMP machines the lock time is trivial and the processes
run really well. On uniprocessor you can get hangs for a full timeslice
unless a shed_yeild() is used if the lock is not available.
Since the processes have no shared data other than the small bit of shared
memory, it seems that threads give no benefit over fork, and for some o/s
much worse. Use of a mutex seems slightly slower in Linux, and quite
slower elsewhere.
The method you describe seems far more useful than some other discussion
which seems to advocate making the yeild process the lowest priority thing
in the system. That really doesn't seem to fit SuS, although I think they
had a single queue in mind. Perhaps not, in any case you seem to provide a
workable solution.
I'm not sure if there would any any significant difference by pushing down
halfway, all the way in the same queue, or just down one. The further down
it goes the better chance there is that the blocking process will run, but
the slower the access to the shared resource and the more chance that
another process will grab the resource. Perhaps down one the first time
and then to the end of the queue if there has not been a timeslice end or
i/o block before another yeild. That would prevent looping between any
number of competitors delaying dispatch to the holder of the lock.
Feel free to disagree, that just came to me as I typed.
--
bill davidsen <[email protected]>
CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.
> No, it works usefully without threads at all, with processes sharing a
> spinlock in shared memory. If the lock is closed process does a
> sched_yeild() to allow whoever has the lock to run. Yes to all comments
> WRT order of running, if you care you don't do this, clearly. But in the
> case where a process forks to a feeder and consumer it's faster than
> semaphores, signal, etc.
>
> All that's needed is to put the yeild process on the end of the
> appropriate run queue and reschedule. Doing anything else results in bad
> performance and no gain to anything else.
>
> --
> bill davidsen <[email protected]>
> CTO, TMR Associates, Inc
> Doing interesting things with little computers since 1979.
I've found sched_yield to be most useful in a case where you can't afford
to wait for a lock, but your processing will be much more efficient if you
have that lock. So you do this:
bool TryYieldLock(lock *f)
{
if(TryLock(f)) return true;
sched_yield();
return TryLock(f);
}
And you use it like this:
if(TryYieldLock(f))
{ /* great, we got the lock, just do it */
DoItNow(x);
Unlock(f);
}
else
{ /* oh well, we didn't get the lock */
schedule_thread(DoItLater, f);
}
In other words, you try a bit harder than the usual 'trylock' function but
not as hard as waiting for the lock. If you don't get the lock, you have to
process it a more expensive way (perhaps scheduling another thread to come
around later and wait for the lock).
Consider a 'free' function for a custom allocator. If there's contention,
you might be willing to do a sched_yield to free it immediately. But you
really don't want to block while some other thread tries to do some
expensive coalescing, in that case you'd rather schedule another thread to
come around later and free it.
This is much less useful on an MP machine though. It's unlikely that
'sched_yield()' will give the other thread enough time to release the lock
since odds are it's running on the other CPU.
DS