pthread_mutex_unlock SuS interpretation question
David Schwartz
There's a debate on the Linux kernel mailing list right now about the
interpretation of a section in the SuS definition of 'pthread_mutex_unlock'.
SuS says:
"If there are threads blocked on the mutex object referenced by mutex when
pthread_mutex_unlock() is called, resulting in the mutex becoming available,
the scheduling policy shall determine which thread shall acquire the mutex."
This is being interpreted to prohibit the releasing thread from
reacquiring the mutex. The idea is that if there are waiting threads, the
releasing thread cannot be one of them. Since the the scheduling policy
*shall* determine which thread *shall* acquire the mutex *when*
pthread_mutex_unlock is called, then it can't choose the current thread,
because it can't know that the current thread wants the mutex back by then.
Is there any way to refute this interpretation? Unfortunately, it sounds
reasonable (though, I hope, not intended!).
My response is simply that it does not say the scheduling policy shall
determine which thread shall acquire the mutex when pthread_mutex_unlock is
called. For example, if I say, "if there are two people who want to request
use of my car on Monday, I shall decide who gets it". That does *not* mean
I'll decide on Monday. It means if the people request on Monday, I'll decide
at some unspecified future time. But that seems kind of weak.
DS
David Hopwood
> There's a debate on the Linux kernel mailing list right now about the
> interpretation of a section in the SuS definition of 'pthread_mutex_unlock'.
> SuS says:
>
> "If there are threads blocked on the mutex object referenced by mutex when
> pthread_mutex_unlock() is called, resulting in the mutex becoming available,
> the scheduling policy shall determine which thread shall acquire the mutex."
>
> This is being interpreted to prohibit the releasing thread from
> reacquiring the mutex. The idea is that if there are waiting threads, the
> releasing thread cannot be one of them. Since the the scheduling policy
> *shall* determine which thread *shall* acquire the mutex *when*
> pthread_mutex_unlock is called, then it can't choose the current thread,
> because it can't know that the current thread wants the mutex back by then.
>
> Is there any way to refute this interpretation?
Yes: the "as if rule". It could have been the case that the other threads ran
more slowly, so that they didn't reach the point of blocking on the mutex
before the pthread_mutex_unlock().
--
David Hopwood <david.nosp...@blueyonder.co.uk>
David Schwartz
"David Hopwood" <david.nosp...@blueyonder.co.uk> wrote in message
news:eUVBf.194553$D47....@fe3.news.blueyonder.co.uk...
> Yes: the "as if rule". It could have been the case that the other threads
> ran
> more slowly, so that they didn't reach the point of blocking on the mutex
> before the pthread_mutex_unlock().
We have a winner! Thanks.
DS
Joe Seigh
SCHED_OTHER is essentially non-deterministic. I don't see how anyone could
claim determinism in that case. All the scheduler interaction points have
undefined behavior for SCHED_OTHER to allow for optimizations that would not be
possible if the actual scheduler had to be called to decide.
In this case it's an important optimization. Mutexes that implement SCHED_FIFO
or SCHED_RR run a lot slower and don't scale as well as SCHED_OTHER when the
former scheduling policies are in effect.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
David Schwartz
"David Hopwood" <david.nosp...@blueyonder.co.uk> wrote in message
news:eUVBf.194553$D47....@fe3.news.blueyonder.co.uk...
> Yes: the "as if rule". It could have been the case that the other threads
> ran
> more slowly, so that they didn't reach the point of blocking on the mutex
> before the pthread_mutex_unlock().
Crap, no. Imagine if the mutex is a priority inheritance mutex and the
locking thread has a higher priority than the unlocking thread. You can tell
that the other thread is waiting for the mutex because your priority will go
up.
Anyone?
DS
Joe Seigh
What scheduling policy is this for? And what do you think "the scheduler"
means in that case?
David Hopwood
> "David Hopwood" <david.nosp...@blueyonder.co.uk> wrote:
>
>>Yes: the "as if rule". It could have been the case that the other threads
>>ran more slowly, so that they didn't reach the point of blocking on the mutex
>>before the pthread_mutex_unlock().
>
> Crap, no. Imagine if the mutex is a priority inheritance mutex and the
> locking thread has a higher priority than the unlocking thread. You can tell
> that the other thread is waiting for the mutex because your priority will go
> up.
In this specific case, isn't it desirable that the unlocking thread *should not*
reacquire the mutex? The intent of priority inheritance is to ensure that the
mutex is unlocked as soon as possible in order that *other* threads with a
higher static priority can acquire it.
--
David Hopwood <david.nosp...@blueyonder.co.uk>
Stephan Brönnimann
My first thought is that the interpretation is common sense.
If -by definition of the OP- threads are waiting for the mutex why
should it be allowed that the unlocking thread gets "in front of the
queue"?
Note: it is not possible that the unlocking thread is waiting for
another lock of the mutex in the moment it calls
pthread_mutex_unlock().
Side-kick: do we need to consider the situation where the unlocking
thread locks the mutex before any of the waiting threads gets CPU time?
I guess one can only find an argument against the interpretation
"not the releasing thread" by showing that
a) there are situations where the system should "wait a little bit to
see if the releasing thread locks again" (I hope you understand what I
mean)
AND
b) there's no other way to solve such situations or such solutions are
way too complex.
Another "simple minded question" (as software engineer I'm a user of
the POSIX thread library): If the releasing thread needs to lock the
mutex just after it has released it, why (the heck) would it unlock in
the first place?
Just a few ideas for the moment, Stephan
bro...@osb-systems.com
Open source rating and billing engine for communication networks.
David Schwartz
> In this specific case, isn't it desirable that the unlocking thread
> *should not*
> reacquire the mutex? The intent of priority inheritance is to ensure that
> the
> mutex is unlocked as soon as possible in order that *other* threads with a
> higher static priority can acquire it.
Right, but that's not the point. The point is that the previous argument
was based upon the assumption that one thread can never tell that another
thread is blocked on a mutex. PI means that one thread *can* tell that
another thread is blocked on a mutex. It can then change its priority and
perform other operations, still knowing that the other thread is blocked on
the mutex (because it knows what the other thread will do when it gets the
mutex).
DS
David Schwartz
"Stephan Brönnimann" <bro...@hotmail.com> wrote in message
news:1138306321.9...@g43g2000cwa.googlegroups.com...
> My first thought is that the interpretation is common sense.
> If -by definition of the OP- threads are waiting for the mutex why
> should it be allowed that the unlocking thread gets "in front of the
> queue"?
Because there is no queue. POSIX specifically chose not to require
mutexes to behave like queues. As for why it should be allowed, simple,
because it's already running and the other threads are not. It is owed a
timeslice by the scheduler, and the other threads may not be.
> Note: it is not possible that the unlocking thread is waiting for
> another lock of the mutex in the moment it calls
> pthread_mutex_unlock().
Right.
> Side-kick: do we need to consider the situation where the unlocking
> thread locks the mutex before any of the waiting threads gets CPU time?
That's the question.
> Another "simple minded question" (as software engineer I'm a user of
> the POSIX thread library): If the releasing thread needs to lock the
> mutex just after it has released it, why (the heck) would it unlock in
> the first place?
Because, when it unlocked it, it had no idea that it would need it
again. Also, it may not know whether or not a higher-priority thread is
waiting for the mutex.
DS
Casper H.S. Dik
> Because there is no queue. POSIX specifically chose not to require
>mutexes to behave like queues. As for why it should be allowed, simple,
>because it's already running and the other threads are not. It is owed a
>timeslice by the scheduler, and the other threads may not be.
And the other threads may hit a page fault as soon as they start running
and they may never make it to the lock after being woken up.
> Because, when it unlocked it, it had no idea that it would need it
>again. Also, it may not know whether or not a higher-priority thread is
>waiting for the mutex.
Or, because it didn't need it for a while or was about to do something
for which it didn't want to hold the lock because it didn't know how
long it would take, like allocating memory.
Casper
--
Expressed in this posting are my opinions. They are in no way related
to opinions held by my employer, Sun Microsystems.
Statements on Sun products included here are not gospel and may
be fiction rather than truth.
Stephan Brönnimann
> "Stephan Brönnimann" <bro...@hotmail.com> wrote in message
> news:1138306321.9...@g43g2000cwa.googlegroups.com...
>
> > My first thought is that the interpretation is common sense.
> > If -by definition of the OP- threads are waiting for the mutex why
> > should it be allowed that the unlocking thread gets "in front of the
> > queue"?
>
> Because there is no queue.
> POSIX specifically chose not to require
> mutexes to behave like queues. As for why it should be allowed, simple,
> because it's already running and the other threads are not. It is owed a
> timeslice by the scheduler, and the other threads may not be.
>
> > Side-kick: do we need to consider the situation where the unlocking
> > thread locks the mutex before any of the waiting threads gets CPU time?
>
> That's the question.
Agreed, yet the programmer's question remains:
If this happens in 1/100 situations, do I (the user) care?
And remember: multi-CPU system become more and more popular.
>
> > Another "simple minded question" (as software engineer I'm a user of
> > the POSIX thread library): If the releasing thread needs to lock the
> > mutex just after it has released it, why (the heck) would it unlock in
> > the first place?
>
> Because, when it unlocked it, it had no idea that it would need it
> again.
Yes, but for this I'll need a few CPU cycles; thus lowering the changes
for the question above.
> Also, it may not know whether or not a higher-priority thread is
> waiting for the mutex.
Back to the original problem and definition:
"If there are threads blocked on the mutex object referenced by mutex
when pthread_mutex_unlock() is called, resulting in the mutex becoming
available, the scheduling policy shall determine which thread shall
acquire the mutex."
Now I turn the question:
"If releasing thread has highest priority based on the scheduling
policy and it is requesting the look again before any other of the
locked threads get CPU time:
Why should it not get the lock again?"
(Note that precondition makes questions like "Can it happen?", "Why is
this needed?" obsolete.)
I can't see anything in the definition that says this shall not be
allowed.
This is because the definition only speaks about scheduling policies
and unless somewhere else there's a specification that forbids a policy
like "Always give the mutex to the thread with highest priority".
Regards, Stephan
David Hopwood
>>> David Hopwood:
>>>> David Schwartz:
>>>>> There's a debate on the Linux kernel mailing list right now about the
>>>>> interpretation of a section in the SuS definition of 'pthread_mutex_unlock'.
>>>>> SuS says:
>>>>>
>>>>> "If there are threads blocked on the mutex object referenced by mutex when
>>>>> pthread_mutex_unlock() is called, resulting in the mutex becoming available,
>>>>> the scheduling policy shall determine which thread shall acquire the mutex."
Note that this doesn't say "shall determine which of these blocked threads shall
acquire the mutex.", so that is one way out.
>>>>> This is being interpreted to prohibit the releasing thread from
>>>>> reacquiring the mutex. The idea is that if there are waiting threads, the
>>>>> releasing thread cannot be one of them. Since the the scheduling policy
>>>>> *shall* determine which thread *shall* acquire the mutex *when*
>>>>> pthread_mutex_unlock is called, then it can't choose the current thread,
>>>>> because it can't know that the current thread wants the mutex back by then.
>>>>>
>>>>> Is there any way to refute this interpretation?
>>>>
>>>> Yes: the "as if rule". It could have been the case that the other threads ran
>>>> more slowly, so that they didn't reach the point of blocking on the mutex
>>>> before the pthread_mutex_unlock().
>>>
>>> Crap, no. Imagine if the mutex is a priority inheritance mutex and the
>>> locking thread has a higher priority than the unlocking thread. You can tell
>>> that the other thread is waiting for the mutex because your priority will go
>>> up.
>>
>>In this specific case, isn't it desirable that the unlocking thread *should not*
>>reacquire the mutex? The intent of priority inheritance is to ensure that the
>>mutex is unlocked as soon as possible in order that *other* threads with a
>>higher static priority can acquire it.
>
> Right, but that's not the point. The point is that the previous argument
> was based upon the assumption that one thread can never tell that another
> thread is blocked on a mutex. PI means that one thread *can* tell that
> another thread is blocked on a mutex. It can then change its priority and
> perform other operations, still knowing that the other thread is blocked on
> the mutex (because it knows what the other thread will do when it gets the
> mutex).
Yes, on reflection I think you're right: the interpretation given on the Linux
kernel list is an overspecification for some cases. OTOH, care should be taken
not to weaken the spec in ways that might break the desired behaviour for
priority inheritance and similar situations. This might be quite difficult.
--
David Hopwood <david.nosp...@blueyonder.co.uk>
Dave Butenhof
What I'd tell them:
Unlocking a mutex MAY (but need not) UNBLOCK a thread that had been
waiting on the mutex. When a thread is unblocked, it is SCHEDULED.
Critical distinction here: the UNBLOCK is a synchronization action. The
SCHEDULING is, um, well, a scheduling operation. (Bet nobody saw that
one coming.)
If the UNLOCK results in an UNBLOCK, and if the/an unblocked thread has
a higher priority and preemptive scheduling policy (e.g., SCHED_FIFO),
then the act of unblocking MAY preempt the unlocking thread. (It WILL,
on a uniprocessor which is, technically, the only environment where
POSIX preemptive scheduling is fully defined, but we'll ignore that
technicality for a moment.)
IF the UNLOCKING thread is PREEMPTED, then the preempting thread will
obviously have it's first hack at the mutex before the unlocking thread
gets another chance.
However, if the unlocking thread is not preempted by the scheduling
action, then it becomes simply one of many scheduled threads that may be
contending for the now available mutex. It is, as the standard says, up
to the scheduling policy to determine which gets it.
Priority inheritance and other non-default mutex protocols can
complicate all of this, but what it comes down to is simply that it's
the SCHEDULER that determines which threads are active at any time on
each processor. But the act of locking or unlocking a mutex is a
synchronization action, not a scheduling action, and does not in itself
imply any scheduling constraints -- especially not preempting the
unlocking thread.
POSIX deliberately (and correctly) does not require that mutex ownership
be ASSIGNED to a waiting thread as a consequence of unlocking; rather,
all waiters contend "equally" (where, as George Orwell's pigs observed,
though all threads are equal some are more equal than others as
specified by realtime priority protocols).
Threads live in the same address space, and share all resources
including those opaque to the application code (including but not
limited to malloc synchronization mechanisms). They are by nature,
design, and intent cooperative, not competitive. The process is trying
to achieve some goal(s), and the threads are all trying to help. It's
rare that the progress of one thread is really more important than
others; and more importantly it's almost impossible to truly enforce
such a statement because of the implicitly shared resources.
The thread that just released the mutex is "hot"; it's running, it's in
cache, etc. If it can continue to make progress, that's almost always
what's in the application's best interests. In the rare cases where this
isn't true, you need to apply realtime scheduling, priority protection
protocols, and a lot of duct tape and superglue to avoid your critical
thread being bogged down by a call to malloc() at the wrong time.
And if that's not the environment for you, you should stay well away
from threads. Processes can cooperate, too, though at a coarser
granularity; but because their resources are independent, they can also
compete if that's what you want.
So, process == compete. Thread == cooperate. And if you're cooperating
then it doesn't matter "who wins" as long as the job gets done. In fact,
the concept of "win" doesn't even apply.
hyc
>waiting on the mutex. When a thread is unblocked, it is SCHEDULED.
Why is this a "MAY (but need not)" ? If there are blocked threads, and
calling pthread_mutex_unlock doesn't unblock one of the waiting
threads, then what will?
David Schwartz
"hyc" <h...@highlandsun.com> wrote in message
news:1138419888.8...@g43g2000cwa.googlegroups.com...
Consider, for example, an implementation that can only run one thread
from a given process at a time and schedules threads in user space. If
thread A is blocked on the mutex while thread B is running and unlocks it,
the implementation may still choose to keep thread A blocked until the next
time the user space thread scheduler is invoked. (Although I suppose you
could argue that making it ready-to-run in the user-space scheduler
constitutes unblocking it.)
DS
Joe Seigh
> I'm having trouble with these explanations. Perhaps we can break it
> down a bit further.
>
> Dave was careful to distinguish the synchronization action from the
> scheduling action. That makes sense, but if that was really the
> underlying motivation, it should have been expressed in the spec
> originally.
>
> Back to the definition:
> http://www.opengroup.org/onlinepubs/000095399/functions/pthread_mutex_unlock.html
>
> The pthread_mutex_unlock() function shall release the mutex object
> referenced by mutex. [XSI] [Option Start] The manner in which a mutex
> is released is dependent upon the mutex's type attribute. [Option End]
> If there are threads blocked on the mutex object referenced by mutex
> when pthread_mutex_unlock() is called, resulting in the mutex becoming
> available, the scheduling policy shall determine which thread shall
> acquire the mutex.
> <<<
>
> scheduling action. The spec does not say "the scheduling policy shall
> determine which thread shall *get the chance to acquire the mutex*." If
> you simply unblock a thread (synchronization action) and allow that
> thread to compete with all the other running threads (scheduling
> action), you have not actually *determined* which thread *shall*
> acquire the mutex. You have only determined that a particular thread
> *could* acquire it, if other unknown conditions are just right.
>
> Now, I can sort of understand breaking things up into a synchronization
> and a scheduling action. That is, a scheduler only cares that threads
> block or become runnable, it doesn't care *why* those things happen.
> Given this conceptual model, the scheduler doesn't know or care that a
> bunch of threads are contending for a mutex. It just knows that some of
> them are runnable, and once one of them is selected to run, it steps
> aside, until that thread does something that causes the scheduler to be
> invoked again.
>
[...]
There's a couple of reasons to be vague about scheduling. One is as soon
as you say *anything* about the state of other threads, that is going to
require synchronization and synchronization is going to slow things down.
So the less speed bumps you architect in, the better. The other is that
posix has few if any forward progress guarantees. That might be in part
because of the first reason but it does limit what you can say about things.
This whole issue is a how many angels can dance on the head of a pin arguement.
Furthermore it doesn't matter if the arguement can even be resolved because the
NPTL architects will pretty much do whatever they feel like even if it is
provably suboptimal.
Dave Butenhof
The point is that there needn't necessarily BE "blocked threads" (in the
scheduler) just because there's a locked synchronization object and
waiters for it. Scheduling and synchronization are orthagonal.
On an SMP implementation, synchronization is often optimized to avoid
expensive blocking operations -- synchronization areas should be small,
so usually by the time a thread has blocked the mutex has long since
been unlocked and time has been wasted. It's common to SPIN for a bit,
and then sometimes SLEEP and perhaps spin again before blocking, in hope
that the mutex will have been released before you need to block.
So it's possible that there can be waiters for a mutex, but no BLOCKED
waiters. Even if a thread is in the spin, on some architectures its a
good idea to spin in cache rather than repeating the
main-memory-interlocking load-lock/store-conditional or compare-and-swap
sequence indefinitely, and thus the mutex may actually be unlocked for
some small period of time before the spinning thread can notice.
Even if a thread is blocking, another thread might unlock before the
blocking thread is deep enough into the scheduler that it can be
rescheduled immediately, and again the lock can be reacquired before it
could notice.
All of these latencies can be really annoying if you're trying to make
threads COMPETE for resources; but the whole thread model is predicated
on COOPERATION. And if you're cooperating, it makes sense to give the
lock to whichever thread gets there first -- even if it's the one that
just released it -- because it lets the APPLICATION get more work done
more quickly, without wasting time on context switches. And that's what
it's all about.
David Schwartz
> The spec doesn't distinguish between the synchronization action and the
> scheduling action. The spec does not say "the scheduling policy shall
> determine which thread shall *get the chance to acquire the mutex*." If
> you simply unblock a thread (synchronization action) and allow that
> thread to compete with all the other running threads (scheduling
> action), you have not actually *determined* which thread *shall*
> acquire the mutex. You have only determined that a particular thread
> *could* acquire it, if other unknown conditions are just right.
I think what you keep missing is the fact that the thread says that the
"scheduling *policy* shall decide". It does not say that the scheduler shall
decide, but that policy shall be decide. Policy is a decision-making
process, not a decision. The specification demands a policy, it does not
demand a decision.
DS
hyc
>Furthermore it doesn't matter if the arguement can even be resolved because the
>NPTL architects will pretty much do whatever they feel like even if it is
provably suboptimal.
I suppose you have a point there.
I see they at least tried:
http://nptl.bullopensource.org/status.php
http://nptl.bullopensource.org/phpBB/viewtopic.php?t=5
hyc
about software here, so eventually all "policy" must boil down to
executable code that provides a definite answer, otherwise the software
is unusable.
I mean, the language of the spec *may* allow a policy of "display a
menu of all threads in the system on the system console and wait for
the sysop to choose the next thread" but nobody would implement such a
thing.
The scheduler is the embodiment in code of the scheduling policy. I
don't think there's any point in distinguishing the two.
Joe Seigh
implementation that performs significantly better than the
NPTL implementation.
David Schwartz
> The scheduler is the embodiment in code of the scheduling policy. I
> don't think there's any point in distinguishing the two.
There is a huge difference conceptually between an agent and the policy
that agent implements. For example, if a specification says an agent must
make a decision, then the agent must make the decision. If the specification
says that policy must make the decision, then the agent need not make the
decision, so long as there is a policy by which the decision is made.
I think I explained this in an analogy before. If a company's bylaw says
the board of directors must make a decision, then they have to make a
decision. If the bylaw says the board's policy shall determine the answer,
then the board does not have to make a decision itself but can postone the
decision, request more information, and even delegate or delay.
In this case, the specification says "scheduling policy" shall determine
the answer. This is far different from demanding the scheduler make the
decision.
DS