POSIX and mutex locking?
Bill Gribble
I've noticed that under LinuxThreads (a kernel-level POSIX threads
package for Linux) it's possible for thread B to be starved in a bit
of code like the fragment at the end of this message. I interpreted
this as a bug in the mutex code, fixed it, and sent a patch to the
author. He replied by saying that the behavior I observed was
correct, it is perfectly OK for a thread to be starved by another
thread of equal priority, and that POSIX makes no guarantees about
mutex lock ordering.
I don't have the $$ to get a copy of the standard, so I have to defer
to the interpretation of those of you who do have a copy. I wonder
(1) if the behavior I observed is within the standard and (2) if it
is, what the f%^& were the POSIX people thinking? I can't think of
any explanation that justifies not requiring FIFO locking of a mutex.
Sorry, I'm just a bit aggravated by this.
Any info appreciated,
Bill Gribble
- example code fragment -------------------
pthread_mutex_t mutex;
(thread A)
while (1) {
pthread_mutex_lock(&mutex);
pthread_mutex_unlock(&mutex);
}
(thread B)
pthread_mutex_lock(&mutex);
-------------------
Steven G. Townsend
Bill Gribble wrote:
>
> I've noticed that under LinuxThreads (a kernel-level POSIX threads
> package for Linux) it's possible for thread B to be starved in a bit
> of code like the fragment at the end of this message. I interpreted
> this as a bug in the mutex code, fixed it, and sent a patch to the
> author. He replied by saying that the behavior I observed was
> correct, it is perfectly OK for a thread to be starved by another
> thread of equal priority,
> and that POSIX makes no guarantees about
> mutex lock ordering.
True.
>
[snip]
> I wonder
> (1) if the behavior I observed is within the standard
Yes.
> and (2) if it
> is, what the f%^& were the POSIX people thinking? I can't think of
> any explanation that justifies not requiring FIFO locking of a mutex.
The problem comes with the overhead of ordering mutex lock requests.
consider... To maintain FIFO ordering the lock request would have to be
kept in some type of a queue structure. This structure would need to
be protected by a mutex itself. Now consider many threads all making
lock requests... After a large number of lock requests (which have now
been sequentially ordered waiting to access the ordering structure
[BTW... what maintains the ordering while waiting for access to the
ordering structure?]) Anyway after a large N lock requests are queued
a unlock occurs, however, the unlock can not complete until it can get
access to the ordering structure to determine who is next on the list.
All of this adds *alot* of overhead to the mutex lock/unlock path.
The lock/unlock path *must* be as fast as possible if significant
bottlenecks are to be avoided.
Mutexes were intended to control access to critical (non-shareable)
resources and/or sections of code (i.e. MUTual EXclusion).
They were not intended to control the order of thread execution only
the number of threads executing (i.e. 1)
>
> Sorry, I'm just a bit aggravated by this.
>
> Any info appreciated,
> Bill Gribble
>
[snip]
Bill Gribble
I've noticed that under LinuxThreads (a kernel-level POSIX threads
package for Linux) it's possible for thread B to be starved in a bit
of code like the fragment at the end of this message. I interpreted
this as a bug in the mutex code, fixed it, and sent a patch to the
author. He replied by saying that the behavior I observed was
correct, it is perfectly OK for a thread to be starved by another
thread of equal priority, and that POSIX makes no guarantees about
mutex lock ordering.
I don't have the $$ to get a copy of the standard, so I have to defer
to the interpretation of those of you who do have a copy. I wonder
(1) if the behavior I observed is within the standard and (2) if it
is, what the f%^& were the POSIX people thinking? I can't think of
any explanation that justifies not requiring FIFO locking of a mutex.
Sorry, I'm just a bit aggravated by this.
Any info appreciated,
Bill Gribble
- example code fragment -------------------
Bil Lewis
Bill Gribble wrote:
>
> I've noticed that under LinuxThreads (a kernel-level POSIX threads
> package for Linux) it's possible for thread B to be starved in a bit
> of code like the fragment at the end of this message. I interpreted
> this as a bug in the mutex code, fixed it, and sent a patch to the
> author. He replied by saying that the behavior I observed was
> correct, it is perfectly OK for a thread to be starved by another
> thread of equal priority, and that POSIX makes no guarantees about
> mutex lock ordering.
>
> I don't have the $$ to get a copy of the standard, so I have to defer
> to the interpretation of those of you who do have a copy. I wonder
> (1) if the behavior I observed is within the standard and (2) if it
> is, what the f%^& were the POSIX people thinking? I can't think of
> any explanation that justifies not requiring FIFO locking of a mutex.
Without going into great detail, the issue comes down to a couple of
things.
1) It is possible to implement a near-FIFO lock using the POSIX
primitives. Unfortunately said lock is something like 3x slower.
2) It is not possible to implement a 100% correct, true FIFO lock using
the POSIX primitives because it requires hardware support. I do not
know of ANY hardware that ever gave that kind of support. (Basically
the hardware would have to implement the entire lock.)
3) Threads run asynchronously anyway, so you can't know which thread is
going to get the lock and which will sleep on it. Thus a 100% correct
FIFO lock is sort of silly.
I wasn't on the committee, but I assume this was their reasoning too.
So... If you want near-FIFO & don't care about speed, do it!
-Bil
--
================
B...@LambdaCS.com
http://www.LambdaCS.com
Lambda Computer Science
555 Bryant St. #194
Palo Alto, CA,
94301
Phone/FAX: (415) 328-8952
James Pitcairn-Hill
------------------------------------------------------------------------
Bill Gribble <gr...@cs.utexas.edu> wrote:
>... it is perfectly OK for a thread to be starved by another
>thread of equal priority, and that POSIX makes no guarantees about
>mutex lock ordering.
Hmmm. Contrary to the two followup contributers I read POSIX as requiring
wakeup order according to the scheduling policy. Perhaps someone can explain
the following wording from Chapter 11 p257:
11.3.3 Locking and Unlocking a Mutex
...
576 If there are threads blocked on the mutex object referenced by
mutex when pthread_mutex_unlock() is called, th mutex becomes
available, and the scheduling policy is used to determine which
thread shall acquire the mutex. See 13.6 for full details.
This seems doubly harsh since taken to extremes it prevents a busy spin
if there is more than one waiter - assuming you consider a busy spin to
be a blocked state.
Of course if the policy is SCHED_OTHER the implementation can do whatever
it likes.
..jph...
William King
James,
I believe this is true if _POSIX_THREAD_PRIORITY_SCHEDULING is defined.
Priority scheduling is an option in POSIX.1-1996. Section 13.4 of the
standard discusses thread scheduling.
Regards,
W
William King
Bill,
I do have a copy of ISO/IEC 9945-1:1996. It addresses this issue.
Basically, if _POSIX_THREADS_PRIORITY_SCHEDULING is defined, both
threads have the PTHREAD_SCOPE_PROCESS contention scope attribute
and both have the SCHED_FIFO scheduling policy attribute, then
the rules in section 13.2.1 apply.
The scheduling model is one of priority lists, with each thread given
an application defined (mostly, e.g. PTHREAD_PRIO_PROTECT) priority.
The thread to be run under this policy is the one at the head of the
highest priority list. The following rules apply (quoted from 13.2.1):
1) When a running thread becomes a preempted thread, it becomes the
head of the thread list for its priority.
2) When a blocked thread becomes a runnable thread, it becomes the
tail of the thread list for its priority
[ other rules excised ]
7) When a running thread issues the sched_yield() function, the
thread becomes the tail of the thread list for its priority
8) At no other time shall the position of a thread with this
scheduling policy winth the thread lists be affected.
The SCHED_RR policy modifies this behavior slightly to ensure that
one thread cannot monopolize the processor by allocating a time slice
of sched_rr_get_interval() or longer to each thread, and pre-empting
a thread and placing it at the end of its priority list after this
interval has expired.
Sounds like you might want to play with the SCHED_RR policy ...
Regards,
W
Bill Gribble wrote:
>
> I've noticed that under LinuxThreads (a kernel-level POSIX threads
> package for Linux) it's possible for thread B to be starved in a bit
> of code like the fragment at the end of this message. I interpreted
> this as a bug in the mutex code, fixed it, and sent a patch to the
> author. He replied by saying that the behavior I observed was
> correct, it is perfectly OK for a thread to be starved by another
> thread of equal priority, and that POSIX makes no guarantees about
> mutex lock ordering.
>
> I don't have the $$ to get a copy of the standard, so I have to defer
> to the interpretation of those of you who do have a copy. I wonder
> (1) if the behavior I observed is within the standard and (2) if it
> is, what the f%^& were the POSIX people thinking? I can't think of
> any explanation that justifies not requiring FIFO locking of a mutex.
>
Dave Butenhof
James Pitcairn-Hill wrote:
>
> ------------------------------------------------------------------------
> Bill Gribble <gr...@cs.utexas.edu> wrote:
> >thread of equal priority, and that POSIX makes no guarantees about
> >mutex lock ordering.
>
> Hmmm. Contrary to the two followup contributers I read POSIX as requiring
> wakeup order according to the scheduling policy. Perhaps someone can explain
> the following wording from Chapter 11 p257:
There's a big difference between "wakeup order" and "locking order".
> 11.3.3 Locking and Unlocking a Mutex
> ...
> 576 If there are threads blocked on the mutex object referenced by
> mutex when pthread_mutex_unlock() is called, th mutex becomes
> available, and the scheduling policy is used to determine which
> thread shall acquire the mutex. See 13.6 for full details.
POSIX says that "next locker" (acquire) is based entirely on scheduling
policy/priority. What this means in practice is that, when a thread
unlocks a mutex, it unblocks (awakens) the highest priority waiter.
That says nothing about which thread might next lock the mutex... that
decision is up to the scheduler. On an SMP, the unblocked thread may be
able to run immediately and acquire the lock. But then, on an SMP,
another thread may be running simultaneously and may still get there
first. On a uniprocessor, the thread that unlocked the mutex will not
yield the processor to the awakened thread unless it has higher
priority -- so if it's in a loop locking and unlocking, and doesn't
block (or get timesliced) before reaching the next lock, it will beat
the thread it unblocked (which hasn't yet been able to run).
> This seems doubly harsh since taken to extremes it prevents a busy spin
> if there is more than one waiter - assuming you consider a busy spin to
> be a blocked state.
Since POSIX (even 1003.1j, which introduces "spinlocks") really says
nothing substantial about what "blocked" means, there's a lot of leeway
for implementors. In particular, keep in mind that busy-wait spinning
is absurd on a uniprocessor, and POSIX specifically says that the
interpretation of realtime scheduling rules is "implementation defined"
when the "allocation domain" is greater than 1 (i.e., the application
threads are potentially executing upon multiple processors).
> Of course if the policy is SCHED_OTHER the implementation can do whatever
> it likes.
>
> ..jph...
/---[ Dave Butenhof ]-----------------------[ bute...@zko.dec.com ]---\
| Digital Equipment Corporation 110 Spit Brook Rd ZKO2-3/Q18 |
| 603.881.2218, FAX 603.881.0120 Nashua NH 03062-2698 |
\-----------------[ Better Living Through Concurrency ]----------------/
Dave Butenhof
William King wrote:
>
> Bill,
>
> I do have a copy of ISO/IEC 9945-1:1996. It addresses this issue.
> Basically, if _POSIX_THREADS_PRIORITY_SCHEDULING is defined, both
> threads have the PTHREAD_SCOPE_PROCESS contention scope attribute
> and both have the SCHED_FIFO scheduling policy attribute, then
> the rules in section 13.2.1 apply.
>
> The scheduling model is one of priority lists, with each thread given
> an application defined (mostly, e.g. PTHREAD_PRIO_PROTECT) priority.
> The thread to be run under this policy is the one at the head of the
> highest priority list. The following rules apply (quoted from 13.2.1):
Actually, "PRIO_PROTECT" is an option specifying that the "priority
ceiling" attribute is supported. Using this attribute (on a mutex)
allows the priority of a thread locking the mutex to be raised while
holding the mutex, to solve "priority inversion" problems. But, aside
from that, you're correct.
> Sounds like you might want to play with the SCHED_RR policy ...
This has nothing to do with the original problem, however. POSIX mutexes
do not (and should not) prevent starvation. Threads are assumed to be
co-workers, not competitors, and the architecture is streamlined to
allow the most efficient implementation of basic synchronization and
scheduling. If threads are partners, it makes far more sense for the
currently running thread to get the mutex again (if it wants it) rather
than forcing a context switch (which is expensive) to allow another
thread to lock the mutex.
POSIX priority scheduling attributes affect the order in which threads
waiting on a mutex are UNBLOCKED when the mutex is unlocked... the
highest priority thread is unblocked first. But it has nothing to do
with the order in which threads may then LOCK the mutex. Another thread
might get there first... and letting it lock the mutex is faster than
making it wait (a context switch) while a currently ready (idle) thread
is scheduled to take the mutex. It just doesn't make sense.
There are VERY few cases where "lock ordering" is truly necessary. In
general, when it may seem to be necessary, using a work queue to
distribute the work across a pool of threads will be easier and more
efficient. If you're convinced that you need lock ordering, rather than
POSIX wakeup ordering, you have to code it yourself -- using,
essentially, a work queue model where threads wishing to lock your
"queued mutex" queue themselves in order. Use a condition variable and
"next waiter" predicate to ensure proper locking order. It's not that
hard.
If you have control of a POSIX thread implementation, and you want to
add an optional (non-portable) attribute to allow specifying lock
ordering on mutexes, be my guest. If it works out well, maybe you can
even convince POSIX or The Open Group to add it to a future standard.
> Regards,
> W
>
> Bill Gribble wrote:
> >
> > I've noticed that under LinuxThreads (a kernel-level POSIX threads
> > package for Linux) it's possible for thread B to be starved in a bit
> > of code like the fragment at the end of this message. I interpreted
> > this as a bug in the mutex code, fixed it, and sent a patch to the
> > author. He replied by saying that the behavior I observed was
> > correct, it is perfectly OK for a thread to be starved by another
> > thread of equal priority, and that POSIX makes no guarantees about
> > mutex lock ordering.
Maybe they shouldn't be the same priority, huh? If they are, then
they're supposed to be equally important to the application. In which
case the thread that can lock the mutex fastest should get it. You want
"fairness" -- that's an entirely different ball of wax.
> > I don't have the $$ to get a copy of the standard, so I have to defer
> > to the interpretation of those of you who do have a copy. I wonder
> > (1) if the behavior I observed is within the standard and (2) if it
> > is, what the f%^& were the POSIX people thinking? I can't think of
> > any explanation that justifies not requiring FIFO locking of a mutex.
We wanted to build an architecture that would allow FAST programs.
Optional attributes allow implementations to add complex options that
aren't often useful and radically slow down the works.
Douglas C. Schmidt
In article <32DC51...@zko.dec.com>,
Dave Butenhof <bute...@zko.dec.com> wrote:
++ There are VERY few cases where "lock ordering" is truly necessary. In
++ general, when it may seem to be necessary, using a work queue to
++ distribute the work across a pool of threads will be easier and more
++ efficient. If you're convinced that you need lock ordering, rather than
++ POSIX wakeup ordering, you have to code it yourself -- using,
++ essentially, a work queue model where threads wishing to lock your
++ "queued mutex" queue themselves in order. Use a condition variable and
++ "next waiter" predicate to ensure proper locking order. It's not that
++ hard.
Right, and you can find a freely available implementation of
essentially a "FIFO Mutex" in ACE. Take a look at
http://www.cs.wustl.edu/~schmidt/ACE_wrappers/ace/Token.h
http://www.cs.wustl.edu/~schmidt/ACE_wrappers/ace/Token.i
http://www.cs.wustl.edu/~schmidt/ACE_wrappers/ace/Token.cpp
Doug
--
Dr. Douglas C. Schmidt (sch...@cs.wustl.edu)
Department of Computer Science, Washington University
St. Louis, MO 63130. Work #: (314) 935-4215; FAX #: (314) 935-7302
http://www.cs.wustl.edu/~schmidt/
James Pitcairn-Hill
>>
>> I do have a copy of ISO/IEC 9945-1:1996. It addresses this issue.
>> Basically, if _POSIX_THREADS_PRIORITY_SCHEDULING is defined, both
>>
>waiting on a mutex are UNBLOCKED when the mutex is unlocked... the
>highest priority thread is unblocked first.
Hi,
While not in any way attempting to promote this behaviour as
a good thing I will note, at the risk of pedantry, that my copy of the
spec says that the mutex becomes available _and_ that the scheduling
policy determines who _acquires_ it, namely the new owner. Nowhere
that I could see does it use the term unblock.
I acknowledge this is not in general a useful semantic - I'm merely
questioning the assertion about what the spec says. Enough disclaimers.
Perhaps there should a formal interpretation request ?
sincerely,
..jph...
William King
Dave,
Thanks for the clarification. My reference to
PTHREAD_PRIO_PROTECT was meant to qualify my statement
that the priorities were (completely) application defined.
When PTHREAD_PRIO_PROTECT is defined, the +implementation+
can temporarily raise the priority of a thread as you correctly
note.
On the issue of scheduling and mutexes, I think 11.3.3.2, L576
applies:
"If there are threads blocked on the mutex object referenced
by mutex when pthread_mutex_unlock() is called, the
mutex becomes available, and the scheduling policy is used
to determine which thread shall acquire the mutex".
In the example given (which I unfortunately didn't keep), I
recall that there were just two threads competing for a mutex
and doing nothing else, in which case it seems like you +would+
end up with thread starvation if both threads have the
SCHED_FIFO scheduling policy but could avoid starvation if
the threads had the SCHED_RR policy. Yes ?
Regards,
W
Dave Butenhof
William King wrote:
> In the example given (which I unfortunately didn't keep), I
> recall that there were just two threads competing for a mutex
> and doing nothing else, in which case it seems like you +would+
> end up with thread starvation if both threads have the
> SCHED_FIFO scheduling policy but could avoid starvation if
> the threads had the SCHED_RR policy. Yes ?
No, not really. The only difference between SCHED_FIFO and SCHED_RR is
that the latter preempts compute-bound threads that run longer than some
fixed interval (timeslicing).
The timeslicing interval isn't synchronized with the lock and unlock
cycle. Thus, the SCHED_RR thread may be preempted while the mutex is
locked. Code that is subject to this sort of starvation, almost by
definition, spends most of its time with the mutex locked -- and thus
will *probably* be preempted with the mutex locked. So you get the same
starvation, with a lot of pointless context switches thrown in.
Dave Butenhof
James Pitcairn-Hill wrote:
>
> In article <32DC51...@zko.dec.com>,
> Dave Butenhof <bute...@zko.dec.com> wrote:
>>POSIX priority scheduling attributes affect the order in which threads
>>waiting on a mutex are UNBLOCKED when the mutex is unlocked... the
>>highest priority thread is unblocked first.
>
> While not in any way attempting to promote this behaviour as
> a good thing I will note, at the risk of pedantry, that my copy of the
> spec says that the mutex becomes available _and_ that the scheduling
> policy determines who _acquires_ it, namely the new owner. Nowhere
> that I could see does it use the term unblock.
It doesn't use the term "unblock", but nevertheless, it means exactly
what I said. Note, several paragraphs before, that a thread calling
pthread_mutex_lock for a mutex that's already locked "blocks until the
mutex becomes available". Thus, "the mutex becomes available" directly
requires that "a waiting thread shall no longer be blocked" (in other
words, "a waiting thread is unblocked"). This says nothing about the
next owner.
"The scheduling policy is used to determine which thread shall acquire
the mutex" means exactly that. The unblocked thread is allowed to run
immediately IF and only if it has higher priority than the thread that
is unlocking the mutex. Scheduling policies specify preemption rules
(who preempts whom, when, and where they go when preempted), and nothing
else.
If the unblocked thread does not preempt the running thread, it is free
to continue running until it blocks or is otherwise preempted. And it is
perfectly free to lock the same mutex again before the unblocked thread
can run.
> I acknowledge this is not in general a useful semantic - I'm merely
> questioning the assertion about what the spec says. Enough
> disclaimers.
While I agree that the wording could be more clear, what it says is
correct and intentional. Nobody ever said "standardese" was easy to
read!
> Perhaps there should a formal interpretation request ?
Feel free to request an interpretation, if you wish. Describe your
problem as clearly and completely as you can, and mail it to
stds-pasc-in...@ieee.org.
Check out http://www.pasc.org/interps/ for information on the POSIX
interpretations process.
> sincerely,
> ..jph...