25 Jan
2006
25 Jan
'06
7:33 p.m.
One Harold Chu on LKML is insisting that POSIX requires
pthread_mutex_unlock to reschedule if other threads are waiting on the
mutex, and that even if the calling thread immediately tries to lock the
mutex again another thread must get it. I contend that both of these
assertions are wrong - first, I just don't read the standard that way,
and second, it would lead to obviously incorrect behavior - unlocking a
mutex would no longer be an RT safe operation. What would be the point
of trylock() in RT code if unlocking is going to cause a reschedule
anyway?
Can anyone back me up on this?
Lee
25 Jan
25 Jan
10:27 p.m.
On 1/25/06, Lee Revell <rlrevell(a)joe-job.com> wrote:
One Harold Chu on LKML is insisting that POSIX
requires
pthread_mutex_unlock to reschedule if other threads are waiting on the
mutex, and that even if the calling thread immediately tries to lock the
mutex again another thread must get it. I contend that both of these
assertions are wrong - first, I just don't read the standard that way,
and second, it would lead to obviously incorrect behavior - unlocking a
mutex would no longer be an RT safe operation. What would be the point
of trylock() in RT code if unlocking is going to cause a reschedule
anyway?
Can anyone back me up on this?
Lee
In "Programming with POSIX Threads" by David R. Butenhof,
pthread_mutex_unlock is said to do this:
"Unlock a mutex. The mutex becomes unowned. If any threads are
waiting for the mutex, one is awakened..."
Seems to suggest a reschedule. Butenhof worked on the POSIX
standards, so I would consider him an authority.
10:32 p.m.
On Wed, 2006-01-25 at 22:27 -0500, Paul Coccoli wrote:
On 1/25/06, Lee Revell <rlrevell(a)joe-job.com>
wrote:
On a multiprocessor yes, another thread will be immediately awakened. I
don't think it implies that on a UP the unlocking thread must
immediately schedule away, even if it remains the highest priority
runnable thread (SCHED_FIFO) or still has timeslice left (SCHED_OTHER).
Is pthread_mutex_unlock really not an RT safe operation?
Lee
One Harold Chu on LKML is insisting that POSIX
requires
pthread_mutex_unlock to reschedule if other threads are waiting on the
mutex, and that even if the calling thread immediately tries to lock the
mutex again another thread must get it. I contend that both of these
assertions are wrong - first, I just don't read the standard that way,
and second, it would lead to obviously incorrect behavior - unlocking a
mutex would no longer be an RT safe operation. What would be the point
of trylock() in RT code if unlocking is going to cause a reschedule
anyway?
Can anyone back me up on this?
Lee
In "Programming with POSIX Threads" by David R. Butenhof,
pthread_mutex_unlock is said to do this:
"Unlock a mutex. The mutex becomes unowned. If any threads are
waiting for the mutex, one is awakened..."
Seems to suggest a reschedule. Butenhof worked on the POSIX
standards, so I would consider him an authority.
26 Jan
26 Jan
3:18 a.m.
On Wed, 2006-01-25 at 22:32 -0500, Lee Revell wrote:
On Wed, 2006-01-25 at 22:27 -0500, Paul Coccoli wrote:
Only if you lock/unlock the mutex in an RT aware manner ie; not when you
leave the critical section, but rather when you are done processing and
have met your RT goal. Your high priority thread will then be hanging on
the mutex and can grab the processor again the instant the low priority
thread leaves its critical section, unlocking the mutex.
--
On 1/25/06, Lee Revell
<rlrevell(a)joe-job.com> wrote:
On a multiprocessor yes, another thread will be immediately awakened. I
don't think it implies that on a UP the unlocking thread must
immediately schedule away, even if it remains the highest priority
runnable thread (SCHED_FIFO) or still has timeslice left (SCHED_OTHER).
Is pthread_mutex_unlock really not an RT safe operation?
One Harold Chu on LKML is insisting that POSIX
requires
pthread_mutex_unlock to reschedule if other threads are waiting on the
mutex, and that even if the calling thread immediately tries to lock the
mutex again another thread must get it. I contend that both of these
assertions are wrong - first, I just don't read the standard that way,
and second, it would lead to obviously incorrect behavior - unlocking a
mutex would no longer be an RT safe operation. What would be the point
of trylock() in RT code if unlocking is going to cause a reschedule
anyway?
Can anyone back me up on this?
Lee
In "Programming with POSIX Threads" by David R. Butenhof,
pthread_mutex_unlock is said to do this:
"Unlock a mutex. The mutex becomes unowned. If any threads are
waiting for the mutex, one is awakened..."
Seems to suggest a reschedule. Butenhof worked on the POSIX
standards, so I would consider him an authority.
4:17 a.m.
On Wed, Jan 25, 2006 at 10:32:17PM -0500, Lee Revell wrote:
On Wed, 2006-01-25 at 22:27 -0500, Paul Coccoli wrote:
If it remains the highest priority one that can be run, clearly it should
just continue. If there is a higher priority one that was waiting for
the mutex, that one should take over - that's the normal priority game.
The only corner case I can imagine is when the contention was between
equal priority threads. But even in that case I'd say that a SCHED_FIFO
thread should run until either it blocks itself, or it is pre-empted
by an higher priority one. So the unlock should have no effect at all.
In "Programming with POSIX Threads" by
David R. Butenhof,
pthread_mutex_unlock is said to do this:
"Unlock a mutex. The mutex becomes unowned. If any threads are
waiting for the mutex, one is awakened..."
Seems to suggest a reschedule. Butenhof worked on the POSIX
standards, so I would consider him an authority.
On a multiprocessor yes, another thread will be immediately awakened. I
don't think it implies that on a UP the unlocking thread must
immediately schedule away, even if it remains the highest priority
runnable thread (SCHED_FIFO) or still has timeslice left (SCHED_OTHER). Is pthread_mutex_unlock really not an RT safe
operation?
Depends on your definition of RT-safe. If it amounts to 'the running
thread can't be pre-empted' then clearly the unlock is not safe.
But with that definition _nothing_ is safe - you can be pre-empted at
any time by a higher priority thread that is woken up by an interrupt.
The normal meaning of RT-safe is more like 'doing this will not block
the caller', and in that sense the unlock is RT-safe: when a higher
priority thread takes over, you have not blocked yourself - you are
being pre-empted. That you triggered this yourself doesn't make it
'blocking'.
--
FA
5:52 a.m.
Lee! Forget my other post ...
On Wed, 2006-01-25 at 22:27 -0500, Paul Coccoli wrote:
In "Programming with POSIX Threads" by David
R. Butenhof,
pthread_mutex_unlock is said to do this:
"Unlock a mutex. The mutex becomes unowned. If any threads are
waiting for the mutex, one is awakened..."
Yes, but what is the completion of that sentence? Could it be:
... and placed in the ready state.
Or perhaps:
... in priority order to aquire the lock.
Seems to suggest a reschedule. Butenhof worked on the
POSIX
standards, so I would consider him an authority.
There seems to be consensus among Solaris/HPUX/DEC/Linux implementations
that the thread is only awake long enough to aquire the lock. And then a
rescheduling *may* take place.
The posix documentation is a bit vague though.
--
6:54 a.m.
Lee Revell wrote:
One Harold Chu on LKML is insisting that POSIX
requires
pthread_mutex_unlock to reschedule if other threads are waiting on the
mutex, and that even if the calling thread immediately tries to lock the
mutex again another thread must get it. I contend that both of these
assertions are wrong - first, I just don't read the standard that way,
and second, it would lead to obviously incorrect behavior - unlocking a
mutex would no longer be an RT safe operation. What would be the point
of trylock() in RT code if unlocking is going to cause a reschedule
anyway?
Can anyone back me up on this?
Lee
On a uniprocessor machine with two threads.
Thread A waiting for the lock.
Thread B has the lock.
If thread B unlocks the lock, and then locks it again, Thread A is
unlikely to get a chance to get the lock.
Thread A will only get the lock if the kernel happens to do a task
switch between Thread B to Thread A.
If one wants B to release the lock, and give Thread A a chance to grab
it, Thread B will have to co-operatively trigger the kernel to task
switch to Thread A. Methods for Thread B to trigger the kernel to task
switch to Thread A is not well defined, as it is just as likely that
some other process will get the task switch, and not Thread A at all.
The reliable way to fix this problem is to keep in mind that
pthread_mutex_lock/unlock is NOT FAIR. This results in one just
designing one's software differently. The Linux kernel developers all
know this fact, and have manged to always provide a solution that works.
This was discussed during the KS, and the performance hit from making
things "fair" is too high to bother trying to implement it.
James
10:02 a.m.
On Thu, 2006-01-26 at 11:54 +0000, James Courtier-Dutton wrote:
On a uniprocessor machine with two threads.
Thread A waiting for the lock.
Thread B has the lock.
If thread B unlocks the lock, and then locks it again, Thread A is
unlikely to get a chance to get the lock.
If B unlocks the mutex and A is the only thread waiting for it, then
pthread_mutex_unlock() gives the lock to A.
B can't get it back before A have had a chance to run (whenever that'll
be.)
Thread A will only get the lock if the kernel happens
to do a task
switch between Thread B to Thread A.
Not according to posix. Perhaps all this talk about "aquiring the lock"
is what confuses us, suggesting that A has to be competitively active to
get anything. Instead it is the running thread that giveth the lock
away ...
Again, according to posix.
--
11:01 a.m.
On Thu, Jan 26, 2006 at 04:02:45PM +0100, Jens M Andreasen wrote:
On Thu, 2006-01-26 at 11:54 +0000, James
Courtier-Dutton wrote:
That is probably an accurate description. In one possible implementation,
the lock has a priority-ordered list of threads waiting for it. Inside
the unlock call, the thread at the head of the list (if any) is removed
from the list, gets the lock, and is added to another priority ordered
list of runnable threads. If its priority is higher than the current
one, its also gets the CPU. In other words, the new thread gets the lock
even before it runs again, and the original owner can't take it back.
But there is a completely different (but not very efficient) way to
do this sort of thing. In this model, waiting for something (e.g. a
lock) involves trying to get it inside a loop, and going to sleep
when that fails. When for example a lock is released, all threads that
could be waiting for it (or even in the limit all threads that are
waiting for anything) are woken up, and when rescheduled and running
again, try one more iteration of the loop. One of them will succeed
and all the others will fail and go to sleep again. In such a system,
the lock is not effectively taken until the new owner is actually
running, and the original owner could take it back if it continues
after the unlock. This method can involve a *lot* of rescheduling
that is just a waste of time. But early UNIX kernels worked like
this AFAIK (using hash lists to limit the number of wasted wakeups).
--
FA
Thread A will only get the lock if the kernel
happens to do a task
switch between Thread B to Thread A.
Not according to posix. Perhaps all this talk about "aquiring the lock"
is what confuses us, suggesting that A has to be competitively active to
get anything. Instead it is the running thread that giveth the lock
away ...
Again, according to posix.
27 Jan
27 Jan
6:09 a.m.
On Thu, 2006-01-26 at 17:01 +0100, Alfons Adriaensen wrote:
-<snip>
But there is a completely different (but not very
efficient) way to
do this sort of thing. In this model, waiting for something (e.g. a
lock) involves trying to get it inside a loop, and going to sleep
when that fails. When for example a lock is released, all threads that
could be waiting for it (or even in the limit all threads that are
waiting for anything) are woken up, and when rescheduled and running
again, try one more iteration of the loop. One of them will succeed
and all the others will fail and go to sleep again. In such a system,
the lock is not effectively taken until the new owner is actually
running, and the original owner could take it back if it continues
after the unlock. This method can involve a *lot* of rescheduling
that is just a waste of time. But early UNIX kernels worked like
this AFAIK (using hash lists to limit the number of wasted wakeups).
It gets better. I dusted off one oldish book, the Pthreads Primer. It
has been a free download from Sun since 1996, so I expect quite a few
people to have read it (else, go do it now.)
On page 104 I find the following code snippet which attempts at
explaining how to create a basic mutual exclusion lock:
try_again: ldstub address -> register
compare register, 0
branch_equal got_it
call go_to_sleep
jump try_again
got_it: return
The go_to_sleep/try_again sequence suggests a busy wait. Furthermore the
surrounding text says "Notice that there is nothing that guarantee the
thread that goes to sleep will ever get the lock when it wakes up."
Now, this is not exactly how pthread_mutex_lock should work.
In all fairness though, the section at hand is about atomic operations
rather than the implementation of pthreads. (Here, ldstub is an
instruction guaranteed to load and store atomically systemwide, no
matter how many processors you have installed. It loads a memory
location and immediately sets that location to 0xFF.)
Let us flip a few pages forward and have a look at the actual
implementation. Here we have pretty pictures with sleeper queues just
like we expected. But we also have a description of a rare corner case,
where one running thread, not in the queue yet, can grab the lock before
any of those in the queue have had a chance to run. This again suggest
that the thread has to be, not only runable, but even running to get the
lock. It also suggests that pthread_mutex_unlock will do something like:
mx[mutex] = 0
if (mxq[mutex]) wakeup_one(mxq[mutex])
... which is weired when we look at the pre and post conditions of the
mutex when there are threads waiting. It is bloody locked! So why would
we ever want to unlock it?
The described behaviour may or may not have have been true for Solaris
in 1996, but a more reasonable implementation would have been:
if (mxq[mutex]) wakeup_one(mxq[mutex])
else mx[mutex] = 0
Race condition, thou be gone!
--
mvh // Jens M Andreasen
7032
days inactive
7034
days old
linux-audio-dev@lists.linuxaudio.org
9 comments
5 participants
participants (5)
-
Alfons Adriaensen -
James Courtier-Dutton -
Jens M Andreasen -
Lee Revell -
Paul Coccoli