LinuxThreads question
David Schwartz
The comments in the spinlock code say:
The waiting list is not sorted by priority order.
Actually, we always insert at top of list (sole insertion mode
that can be performed without locking).
For __pthread_unlock, we perform a linear search in the list
to find the highest-priority, oldest waiting thread.
This is safe because there are no concurrent __pthread_unlock
operations -- only the thread that locked the mutex can unlock it. */
Why the maximally pessimistic behavior? The thread that's been waiting
the longest is the least likely to have any code or data it needs in
cache. The default mutexes are supposed to be fast, not fair. (Why be
fair to threads? They have no feelings that can be hurt.)
DS
David Schwartz
> Why the maximally pessimistic behavior? The thread that's been waiting
> the longest is the least likely to have any code or data it needs in
> cache. The default mutexes are supposed to be fast, not fair. (Why be
> fair to threads? They have no feelings that can be hurt.)
In fact, this behavior is *so* bad I'm going to have to downgrade. It
breaks so many things it's not even funny.
Consider, for example, a job queue. The code looks like this:
while(1)
{
Lock();
while((job=GetJob())==NULL) pthread_cond_wait(lock, job_ready_cond);
Unlock();
DoJob();
}
Assume for the sake or argument that:
1) Each job starts as a pretty small amount of work, and
2) Each job has a 75% chance of queueing another job to this queue.
3) One in a thousand jobs blocks for some I/O, so two threads services
this queue to not stall other jobs (and to get SMP advantages).
In previous LinuxThreads versions, on single CPU, one thread would run
until its timeslice was exhausted, the Lock/Unlock operations being
virtually free. With this pessimization, one context switch is required
for every job to be done! This is insanity!
DS
David Schwartz
Actually, I take back my shrieking, it's not as bad as I thought. But
it's still maximally pessimized.
DS
Kaz Kylheku
>
> The comments in the spinlock code say:
>
> The waiting list is not sorted by priority order.
> Actually, we always insert at top of list (sole insertion mode
> that can be performed without locking).
> For __pthread_unlock, we perform a linear search in the list
> to find the highest-priority, oldest waiting thread.
> This is safe because there are no concurrent __pthread_unlock
> operations -- only the thread that locked the mutex can unlock it. */
>
> Why the maximally pessimistic behavior?
Firstly, you should be looking at the lastest glibc 2.2 stream.
The internal locks have been replaced with alternate locks
(marked by the word ``alt'' in their function names). The alternate
locks do not have the behavior of atomically handing off a lock
to one of the waiting threads; instead they allow competition.
Previously, __pthread_lock and __pthread_unlock were used extensively
within LinuxThreads for locks that are not visible to the user, like
the lock protecting the wait queue in a condition variable, and such.
>The thread that's been waiting
>the longest is the least likely to have any code or data it needs in
>cache. The default mutexes are supposed to be fast, not fair. (Why be
>fair to threads? They have no feelings that can be hurt.)
It's been discussed before. The problem is that people complain when
their code demonstrates unfair behavior. And then there is POSIX
which asks that when a lock is released, it be given to one of the
waiting threads according to the scheduling policy. So the default mutex
still does this behavior of handing off the lock to a waiting threads.
There is a non-default lock that is faster; in glibc 2.2 you have
PTHREAD_MUTEX_ADAPTIVE_NP which does not have the behavior of atomically
handing off the lock to a waiting thread, but rather allows competition
for the lock. It's implemented using the ``alt'' fastlock operations.
David Schwartz
Here's another strange thing, to avoid a supposed "thundering herd"
problem, only one thread blocked on a mutex is awakened when it's
released. However, this results in massive scheduling delays.
For people who use mutexes properly (only holding them for a split
second), you want to wake at least as many threads as you have
processors (arguably more) and then let them spin for the mutex if
needed. In all probability, as the schedulers get around to scheduling
each thread, the mutex will be used by the threads without any
contention at all.
Suppose you have five threads that use a mutex and two processors.
Normally, the mutex is only held for, say 250 machine cycles, but
somehow a thread manages to get descheduled while holding the mutex. Now
the other four threads block on the mutex. You want to wake them all,
because even with two CPUs, the odds that two threads will wind up
asking for the mutex within 250 machine cycles are near-zero. Instead,
the losing thread doesn't even become ready-to-run until the winning
thread actually runs. This causes alternation instead of concurrency.
Why, again, do we have maximally pessimized code?
DS
Charles Bryant
David Schwartz <dav...@webmaster.com> wrote:
> Suppose you have five threads that use a mutex and two processors.
>Normally, the mutex is only held for, say 250 machine cycles, but
>somehow a thread manages to get descheduled while holding the mutex. Now
>the other four threads block on the mutex. You want to wake them all,
>because even with two CPUs, the odds that two threads will wind up
>asking for the mutex within 250 machine cycles are near-zero. Instead,
>the losing thread doesn't even become ready-to-run until the winning
>thread actually runs. This causes alternation instead of concurrency.
>
> Why, again, do we have maximally pessimized code?
I'll have a guess that it's because the chances of several threads
getting blocked on the mutex are so low that it's more important to
optimise the case where there are no threads waiting, and after that
the case where there is exactly one. Does the code appear to be
optimised for these cases instead?
--
Eppur si muove