Condition vs. Mutex.
Nicholas Twerdochlib
other threads trigger a mutex. Thus the threads in question will sleep on a
pthread_mutex_lock().
I have recently read some info that suggests I should use a condition
variable in this area. It suggests that the way that I am doing will/could
cause race conditions on the system. I am currently running this code on a
HP server with 4 processors, along with an instance of Informix and I have
not had any cases of excessive CPU utilization. Other than when we do a
load/unload on the database.
Can anyone offer their two cents and validate this claim. Maybe I am just
not seeing something.
Thanks in advance,
Nicholas
Ian Collins
A mutex should be used to protect a cricical object and conditionals are
used
to sync threads. You can also get problems with priority inversion if
you use
a mutex in this way.
You can also perform timed waits on conditionals.
--
Ian Collins
Tom Payne
: I have a multithreaded app. Some of the threads in my app do not run until
: other threads trigger a mutex. Thus the threads in question will sleep on a
: pthread_mutex_lock().
: I have recently read some info that suggests I should use a condition
: variable in this area. It suggests that the way that I am doing will/could
: cause race conditions on the system. I am currently running this code on a
: HP server with 4 processors, along with an instance of Informix and I have
: not had any cases of excessive CPU utilization. Other than when we do a
: load/unload on the database.
: Can anyone offer their two cents and validate this claim. Maybe I am just
: not seeing something.
A mutex should never be used for long-term waiting. It is simply a
lock that is used to briefly protect a condition or two and the data
used in deciding whether or not to wait and when to allow a thread to
resume. The mutex it used to make atomic these coordination actions
and the decisions to peform them.
Tom Payne
Sean Burke
You seem to be under the impression that phtread_mutex_lock is a
"spin lock", where the thread busy-waits for the lock. This is not
the case.
It appears that Nicholas is using the mutex in effect as
a semaphore with count initialized to one. As long as
correct semaphore discipline is used, where the thread that
locked the mutex is the one that releases it, there should
be no problems.
Added comp.programming.threads to followups.
-SEan
Patrick TJ McPhee
Sean Burke <sean_...@earthlink.net> wrote:
% Tom Payne wrote:
% >
% > In comp.unix.internals Nicholas Twerdochlib
% <nich...@thecygnusgroup.com> wrote:
% > : I have a multithreaded app. Some of the threads in my app do not run until
% > : other threads trigger a mutex. Thus the threads in question will sleep on a
% > : pthread_mutex_lock().
[...]
% > A mutex should never be used for long-term waiting. It is simply a
I dunno, I think a mutex should be used to wait until the resource it's
protecting is available.
% It appears that Nicholas is using the mutex in effect as
% a semaphore with count initialized to one. As long as
% correct semaphore discipline is used, where the thread that
% locked the mutex is the one that releases it, there should
% be no problems.
It sounds to me like he wants some threads to wait for a condition to be
true before they start. The cleanest way to do this in pthreads is with
a condition variable. The problem with using just a mutex is that you have
to be careful the trigger thread gets the mutex first. The nice thing
about condition variables is that threads block without holding any
locks.
Blocking threads:
pthread_mutex_lock(&mux);
/* test the condition */
while (!go)
/* release the lock until you're told to retest, then grab it again
atomically. You never hold the lock while you're waiting, and you
never get here if you were supposed to go. */
pthread_cond_wait(&cond, &mux);
pthread_mutex_unlock(&mux);
Trigger thread:
pthread_mutex_lock(&mux);
go = 1;
/* tell everybody who's blocking that it's time to go, which they'll
do as soon as they can get the mutex */
pthread_cond_broadcast(&cond);
/* let the games begin */
pthread_mutex_unlock(&mux);
% Added comp.programming.threads to followups.
What the hell, I directed all follow-ups there.
--
Patrick TJ McPhee
East York Canada
pt...@interlog.com
Kaz Kylheku
>Tom Payne wrote:
>> A mutex should never be used for long-term waiting. It is simply a
>> used in deciding whether or not to wait and when to allow a thread to
>> resume. The mutex it used to make atomic these coordination actions
>> and the decisions to peform them.
>
>You seem to be under the impression that phtread_mutex_lock is a
>"spin lock", where the thread busy-waits for the lock. This is not
>the case.
However, note that pthread_mutex_lock() is not a cancellation point. This
means that it's clearly inappropriate for *indefinite* waiting, since then
rude, crude techniques are required to unblock the thread to precipitate a
shutdown.
pthread_cond_wait() on the other hand can be broken by cancelling the thread
with pthread_cancel().
The POSIX threads paradigm is such that mutexes are for brief locks, and
conditions are for longer, possibly indefinite, waits.
Conditions can be broadcast, thus allowing many threads to be unblocked in one
fell swoop, which is useful if many threads are interested in a common
predicate becoming true, such as the availability of a global resource.
There is also a way to do timed-out waits using pthread_cond_timedwait(),
which can be occasionally useful (like in the implementation of a
timer call-out service, for instance).
Tom Payne
:> In comp.unix.internals Nicholas Twerdochlib <nich...@thecygnusgroup.com> wrote:
:> : I have a multithreaded app. Some of the threads in my app do not run until
:> : other threads trigger a mutex. Thus the threads in question will sleep on a
:> : pthread_mutex_lock().
:>
:> : I have recently read some info that suggests I should use a condition
:> : variable in this area. It suggests that the way that I am doing will/could
:> : cause race conditions on the system. I am currently running this code on a
:> : HP server with 4 processors, along with an instance of Informix and I have
:> : not had any cases of excessive CPU utilization. Other than when we do a
:> : load/unload on the database.
:>
:> : Can anyone offer their two cents and validate this claim. Maybe I am just
:> : not seeing something.
:> A mutex should never be used for long-term waiting. It is simply a
:> lock that is used to briefly protect a condition or two and the data
:> used in deciding whether or not to wait and when to allow a thread to
:> resume. The mutex it used to make atomic these coordination actions
:> and the decisions to peform them.
: You seem to be under the impression that phtread_mutex_lock is a
: "spin lock", where the thread busy-waits for the lock. This is not
: the case.
My somewhat dogmatic statement is based on my understanding of the
intent of the folks like Brinch-Hansen, Hoare, Lampson etc., who
introduced and developed these concepts, i.e., mutex and condition.
* Efficiency: Some threads implementations use low-level waiting
for mutex and high-level for condition.
* Facilities: Some threads implementations make provision for
timeouts, alarms, broadcasts for conditions and not for mutexes.
* Style: As an aid to program understanding, it is helpful to
separate concerns and use mutexes only to provide atomicity
and use conditions to implement scheduling protocols.
: It appears that Nicholas is using the mutex in effect as
: a semaphore with count initialized to one. As long as
: correct semaphore discipline is used, where the thread that
: locked the mutex is the one that releases it, there should
: be no problems.
Right.
Perhaps the warning about possible race conditions with mutexes had to
do with the fact that a semaphore will remember an unawaited release,
while AFIK a mutex makes no such guarantee.
Tom Payne
Casper H.S. Dik - Network Security Engineer
Tom Payne <t...@hill.cs.ucr.edu> writes:
>My somewhat dogmatic statement is based on my understanding of the
>intent of the folks like Brinch-Hansen, Hoare, Lampson etc., who
>introduced and developed these concepts, i.e., mutex and condition.
> * Efficiency: Some threads implementations use low-level waiting
> for mutex and high-level for condition.
Solaris threads will block; kernel mutexs work differently: they will
spin if the owner is currently executing on a CPU else they'll block.
Waking up and rescheduling takes place.
Solaris condition variables are typically used for a
release-lock
wait
get-lock
(you have the lock when you call cond_wait and you have it again when
you release it; you need to release the lock in such situations because while
holding the lock the situation you're waiting for might never arise)
> * Facilities: Some threads implementations make provision for
> timeouts, alarms, broadcasts for conditions and not for mutexes.
> * Style: As an aid to program understanding, it is helpful to
> separate concerns and use mutexes only to provide atomicity
> and use conditions to implement scheduling protocols.
If you need scheduling, you shouldn't be using locking primitives.
mutex_lock serves one purpose: "I need this and I need it exclusively".
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.
Tom Payne
: Tom Payne <t...@hill.cs.ucr.edu> writes:
:>My somewhat dogmatic statement is based on my understanding of the
:>intent of the folks like Brinch-Hansen, Hoare, Lampson etc., who
:>introduced and developed these concepts, i.e., mutex and condition.
[...]
:> * Style: As an aid to program understanding, it is helpful to
:> separate concerns and use mutexes only to provide atomicity
:> and use conditions to implement scheduling protocols.
: If you need scheduling, you shouldn't be using locking primitives.
: mutex_lock serves one purpose: "I need this and I need it exclusively".
The point is that to make scheduling decisions you need exclusive
access to both the conditions on which you might wait and the data on
which you'll base the decision of whether or not to wait, i.e., you
need to make the decision/wait operation atomic. You use a mutex to
create such atomicity and, I recommend, that should be the only use of
mutexes. Sure you can use mutexes to allocate single-unit resources,
e.g., the printer on a server, but as a matter of style, I prefer to
do such long-term waiting on a condition. (Also, I'd prefer to do
something more clever than FIFO scheduling, say shortest-job-first, in
such cases.)
Tom Payne
Frank Cusack
> mutexes. Sure you can use mutexes to allocate single-unit resources,
> e.g., the printer on a server, but as a matter of style, I prefer to
> do such long-term waiting on a condition. (Also, I'd prefer to do
> something more clever than FIFO scheduling, say shortest-job-first, in
> such cases.)
In which case I'd submit 1000 1-page jobs instead of one large job. :)
~frank
--
* I am Pentium of Borg. Division is futile. You will be approximated. *
* PGP ID: C001AA75 -|- fcu...@iconnet.net *
Kaz Kylheku
>Tom Payne <t...@hill.cs.ucr.edu> writes:
>
>> mutexes. Sure you can use mutexes to allocate single-unit resources,
>> e.g., the printer on a server, but as a matter of style, I prefer to
>> do such long-term waiting on a condition. (Also, I'd prefer to do
>> something more clever than FIFO scheduling, say shortest-job-first, in
>> such cases.)
>
>In which case I'd submit 1000 1-page jobs instead of one large job. :)
But then you would have to remove other people's 1 page jobs interspersed among
your pages. :)
Sean Burke
>
> In comp.unix.internals Sean Burke <sean_...@earthlink.net> wrote:
> : Tom Payne wrote:
> [...]
> :> In comp.unix.internals Nicholas Twerdochlib <nich...@thecygnusgroup.com> wrote:
> :> : I have a multithreaded app. Some of the threads in my app do not run until
> :> : other threads trigger a mutex. Thus the threads in question will sleep on a
> :> : pthread_mutex_lock().
> :>
> :> : I have recently read some info that suggests I should use a condition
> :> : variable in this area. It suggests that the way that I am doing will/could
> :> : cause race conditions on the system. I am currently running this code on a
> :> : HP server with 4 processors, along with an instance of Informix and I have
> :> : not had any cases of excessive CPU utilization. Other than when we do a
> :> : load/unload on the database.
> :>
> :> : Can anyone offer their two cents and validate this claim. Maybe I am just
> :> : not seeing something.
> :>
> :> A mutex should never be used for long-term waiting. It is simply a
> :> lock that is used to briefly protect a condition or two and the data
> :> used in deciding whether or not to wait and when to allow a thread to
> :> resume. The mutex it used to make atomic these coordination actions
> :> and the decisions to peform them.
>
> : You seem to be under the impression that phtread_mutex_lock is a
> : "spin lock", where the thread busy-waits for the lock. This is not
> : the case.
>
> intent of the folks like Brinch-Hansen, Hoare, Lampson etc., who
> introduced and developed these concepts, i.e., mutex and condition.
>
> for mutex and high-level for condition.
>
> timeouts, alarms, broadcasts for conditions and not for mutexes.
>
> separate concerns and use mutexes only to provide atomicity
> and use conditions to implement scheduling protocols.
>
> : a semaphore with count initialized to one. As long as
> : correct semaphore discipline is used, where the thread that
> : locked the mutex is the one that releases it, there should
> : be no problems.
>
> Right.
>
> Perhaps the warning about possible race conditions with mutexes had to
> do with the fact that a semaphore will remember an unawaited release,
> while AFIK a mutex makes no such guarantee.
>
> Tom Payne
A mutex does retain state - if one thread releases it before
a second thread tries to lock it, the second thread will find
it available. I think that the warning about race conditions
was incorrect.
My take on the original post was as follows: Nicholas was doing
something that was probably technically correct, but showed poor
style. He received criticism to the effect that there was some
mysterious feature of mutexes that he didn't understand.
It is proper to criticize his solution as a matter of style, but
I wanted to dispel the notion that he was missing some subtlety
of mutexes. Good style is built on the basis of understanding.
-SEan
original poster seemed to possess, then style will follow it time.
Tom Payne
:> do with the fact that a semaphore will remember an unawaited release,
:> while AFIK a mutex makes no such guarantee.
:>
:> Tom Payne
: A mutex does retain state - if one thread releases it before
: a second thread tries to lock it, the second thread will find
: it available. I think that the warning about race conditions
: was incorrect.
Agreed.
A semaphore's state (i.e., its count and/or the number of waiting
threads) is simply its initial count plus the number or releases minus
the number of acquires on it. So, its state is independent of the
order in which release and acquire are invoked on it, i.e., there's no
possibility of a race condition. On the other hand, an unowned mutex
is not guaranteed to remember an invocation of unlock, a situation
that could be called a "race condition." But unlocking an unowned
mutex is an illegal operation and a mutex must remember up to one
release unacquired release, so there is no possibility of a race
condition on a properly used mutex.
Tom Payne
Kaz Kylheku
>A semaphore's state (i.e., its count and/or the number of waiting
>threads) is simply its initial count plus the number or releases minus
>the number of acquires on it. So, its state is independent of the
>order in which release and acquire are invoked on it, i.e., there's no
>possibility of a race condition. On the other hand, an unowned mutex
>is not guaranteed to remember an invocation of unlock, a situation
>that could be called a "race condition."
I would call this situation ``undefined behavior''. Unlocking a mutex that is
not currently locked is simply not a well-defined operation. A useful response
from mutex implementation, at least during debugging, would be to halt the
program with an error message such as ``assertion failure: mutex unlocked with
no lock held''. It's like dividing by zero, dereferencing an invalid
pointer, or subtracting one from an int whose value is INT_MIN. :)
Tom Payne
: On 14 May 1999 17:19:03 GMT, Tom Payne <t...@hill.cs.ucr.edu> wrote:
[...]
:> On the other hand, an unowned mutex
:>is not guaranteed to remember an invocation of unlock, a situation
:>that could be called a "race condition."
: I would call this situation ``undefined behavior''.
AFIK, a race condition is any situation that is sensitive to the order
in which otherwise uncoordinated threads operate on a shared variable.
Of course, the ensuing behavior may be undefined for certain possible
outcomes of the race.
In the case of a mutex, however, all sequences of operations that
produce defined behavior, produce equivalent states. So, like you, I
hesitate to think of it as "a race condition," but I can't quarrel
with those who want to call it that.
Tom Payne
Dave Butenhof
> In comp.programming.threads Kaz Kylheku <k...@ashi.footprints.net> wrote:
> : On 14 May 1999 17:19:03 GMT, Tom Payne <t...@hill.cs.ucr.edu> wrote:
> [...]
> :> On the other hand, an unowned mutex
> :>is not guaranteed to remember an invocation of unlock, a situation
> :>that could be called a "race condition."
>
> : I would call this situation ``undefined behavior''.
>
> AFIK, a race condition is any situation that is sensitive to the order
> in which otherwise uncoordinated threads operate on a shared variable.
> Of course, the ensuing behavior may be undefined for certain possible
> outcomes of the race.
Yes, that's a good basic definition of a race.
> In the case of a mutex, however, all sequences of operations that
> produce defined behavior, produce equivalent states. So, like you, I
> hesitate to think of it as "a race condition," but I can't quarrel
> with those who want to call it that.
Maybe you can't, but I can! My general comment on this topic has to be:
"How easy it is to sink into pedantic and pointless arguments." (And this
is a ridiculous number of newsgroups in which to be crossposting such
philosophical nonsense!)
Functionally, a mutex is much like a binary semaphore. The difference is
that a mutex includes the concept of OWNERSHIP, while a semaphore is just a
signalling mechanism. Yes, you can "release", (in POSIX terms, sem_post), a
counted semaphore that's unowned. However, that bumps the count from 1
(unlocked) to 2. That's neither "locked" nor "unlocked", and calling it
something like "pending unlock" is a stretch. (The semaphore isn't a lock
anymore, it's a signalling mechanism more comparable to a condition
variable, and you've issued a "pending wake".) In any case, you can't do
that with a true binary semaphore. (Though the only example of which I'm
aware, msem_unlock, doesn't specify what happens if you try.)
A mutex that's locked is OWNED by the thread that locked it. Only that
thread can legally unlock the mutex. Once its unlocked, it's no longer
owned by that thread, and an additional unlock is illegal. POSIX does not
require that an implementation DETECT ownership violations, because
detection may be expensive on some implementations, and it's a programming
error that even relatively minimal care in design can avoid.
Implementations MAY detect the programming error, though, so you can never
write a legal program that depends on failure to detect these errors.
If you write a program that unlocks a locked mutex, even on an
implementation that doesn't detect the error, that's not a "race". It's
just a broken program. Sorry, folks, there's nothing to see here; please
move on.
Dave Butenhof
> On Mon, 10 May 1999 16:43:18 -0700, Sean Burke <sean_...@earthlink.net> wrote:
> >Tom Payne wrote:
> >> A mutex should never be used for long-term waiting. It is simply a
> >> lock that is used to briefly protect a condition or two and the data
> >> used in deciding whether or not to wait and when to allow a thread to
> >> resume. The mutex it used to make atomic these coordination actions
> >> and the decisions to peform them.
> >
> >You seem to be under the impression that phtread_mutex_lock is a
> >"spin lock", where the thread busy-waits for the lock. This is not
> >the case.
But pthread_mutex_lock MAY, legally, and reasonably, be a spinlock. POSIX does not
require that the calling thread be de-scheduled, either immediately or at all, to
wait for the mutex to become available. An implementation that simply spins is
perfectly reasonable, though really only practical for a multiprocessor realtime
embedded system. More realistically, "mainstream" implementations often do spin for
a short time before de-scheduling the waiter. This follows directly from the design
and intended use of a mutex. A mutex should be held over a small portion of code,
for a short time. Any other use risks severe performance and concurrency reduction
due to inherent conflicts with the design of the synchronization function.
Is is LEGAL to use a mutex for a long wait? Sure. It's not a good design, though,
and may perform poorly, (ironically), on implementations optimized for high
performance multiprocessor mutex synchronization.
> However, note that pthread_mutex_lock() is not a cancellation point. This
> means that it's clearly inappropriate for *indefinite* waiting, since then
> rude, crude techniques are required to unblock the thread to precipitate a
> shutdown.
This is a really big point to remember. For any unbounded wait, your thread should
be cancellable. Of course, if you know that only you can create a thread that might
run the routine doing the wait, and you know that you'll never cancel it, that's
irrelevant. But if you're writing a library routine that might be called in
"someone else's" thread, you should write it to be cancellable, and cancel-safe.
> pthread_cond_wait() on the other hand can be broken by cancelling the thread
> with pthread_cancel().
>
> The POSIX threads paradigm is such that mutexes are for brief locks, and
> conditions are for longer, possibly indefinite, waits.
>
> Conditions can be broadcast, thus allowing many threads to be unblocked in one
> fell swoop, which is useful if many threads are interested in a common
> predicate becoming true, such as the availability of a global resource.
In practice, the benefit of broadcast is overstated here. Remember that each thread
awakening from a condition wait must reaquire the associated mutex. So the
"concurrently" awakened threads are always serialized anyway, by mutex wakeup
ordering.
People seem to like to think of condition signal as the "normal" operation, and
broadcast as a special case. It's really the other way around. Broadcast is the
normal operation, completely general and functionally correct for any combination
of waiters. (Each will be able to reevaluate its wait predicate, so it works even
if they're waiting for different things.) Signal is an OPTIMIZATION for the case
where you know that all threads are waiting for the same predicate, and that only
one of those waiters is needed to satisfy the program invariants. Signal allows you
to avoid all of the scheduling overhead of some number of threads being started,
reevaluating their predicates, and going back to sleep.
Broadcast is always functionally correct, but often performs suboptimally. Signal
performs better as long as your waiters meet the restrictions necessary to use it
safely.
> There is also a way to do timed-out waits using pthread_cond_timedwait(),
> which can be occasionally useful (like in the implementation of a
> timer call-out service, for instance).
Absolutely.
Zeke
> >threads) is simply its initial count plus the number or releases minus
> >the number of acquires on it. So, its state is independent of the
> >order in which release and acquire are invoked on it, i.e., there's no
> >is not guaranteed to remember an invocation of unlock, a situation
> >that could be called a "race condition."
>
> not currently locked is simply not a well-defined operation. A useful response
> from mutex implementation, at least during debugging, would be to halt the
> program with an error message such as ``assertion failure: mutex unlocked with
> no lock held''. It's like dividing by zero, dereferencing an invalid
> pointer, or subtracting one from an int whose value is INT_MIN. :)
I get confused in my old age, so please help me out here.
I'm seeing things like "semaphore" , "mutex", "lock", and
"unlock", so I'm thinking that we're not performing P and V
on a semaphore to achieve mutual exclusion.
Furthermore, we're not changing the initialized value of the
semaphore to achieve synchronization (event-wait).
So is this part of that new Pthreads thing? If so, then
the choice of locking versus waiting is a matter of what
is appropriate, right? If all you have to worry about is,
say some critical section that requires mutual exclusion
and nothing more, then Pthread_mutex_* should solve
the problem (watch out for unwanted termination 'cuz I'm
not talking about UNIX IPC semaphores). If something more
than just mutual exclusion is required, say synchronization
as an example, then some of that fancy new Pthread_cond_*
could be used.
So the original poster should understand what it is he
wants to do in order to provide the best implementation.
And he should also keep in mind the wisdom of not
fixing something that works. ;^)
BTW, let me tell you this was some programming
task to just enter this message in on the toggle
switches of the front panel. But you know, I can
still remember the days when we didn't even
have those toggles. It was just one's and zero's
back in those days...
...before that we just had zero's. :^)
It's amazing to see the progress achieved.
Kaz Kylheku
>I get confused in my old age, so please help me out here.
>I'm seeing things like "semaphore" , "mutex", "lock", and
>"unlock", so I'm thinking that we're not performing P and V
>on a semaphore to achieve mutual exclusion.
You can certainly use a semaphore's P and V operations to implement mutual
exclusion. But in the case of a semaphore, you can do V even without doing a
prior P. Or you can have one thread which always does P and another one which
always does only V.
These sorts of things are not possible with mutexes/monitors.
>not talking about UNIX IPC semaphores). If something more
>than just mutual exclusion is required, say synchronization
>as an example, then some of that fancy new Pthread_cond_*
>could be used.
Or fancy old. :) Monitors and conditions date back to the 60's. They were
invented by Hoare (the Quicksort guy). Though Hoare's semantics differ markedly
from POSIX.
>switches of the front panel. But you know, I can
>still remember the days when we didn't even
>have those toggles. It was just one's and zero's
>back in those days...
>
>...before that we just had zero's. :^)
We still have those, but now they have moved up to management.
(My old retort to an old joke. :)
>It's amazing to see the progress achieved.
You'll be eating your words the next time you use a PC. :)
Tom Payne
: This is a multi-part message in MIME format.
: --------------064208188C0C12CE0B96D168
: Content-Type: text/plain; charset=us-ascii
: Content-Transfer-Encoding: 7bit
: Tom Payne wrote:
[...]
:> AFIK, a race condition is any situation that is sensitive to the order
:> in which otherwise uncoordinated threads operate on a shared variable.
:> Of course, the ensuing behavior may be undefined for certain possible
:> outcomes of the race.
: Yes, that's a good basic definition of a race.
[...]
: If you write a program that unlocks a locked mutex, even on an
unlocked !?!
: implementation that doesn't detect the error, that's not a "race".
Threads A and B race to, respectively, lock and unlock a given
unlocked mutex. Suppose B wins and unlocks the unlocked mutex. A
race is a race regardless of outcome. (See the "good basic
definition" above.)
: It's just a broken program.
All programs that contain error-producing races are broken.
Tom Payne
BTW, what's with the petulance on this matter?
David Schwartz
> Threads A and B race to, respectively, lock and unlock a given
> unlocked mutex. Suppose B wins and unlocks the unlocked mutex. A
> race is a race regardless of outcome. (See the "good basic
> definition" above.)
Two threads cannot race to unlock a given mutex as only the thread that
holds a mutex may unlock it and only one thread may hold a mutex at a
time.
DS
Tom Payne
:> Threads A and B race to, respectively, lock and unlock a given
It has been legislated that B "may not" unlock the mutex, but that
doesn't stop him from doing so. (Legislation alone never stops
crime.) The race goes on, and the behavior of the program becomes
undefined whenever B wins the race, which is different from the
outcome when A wins the race. By defnition, we have a "race
condition," and a program whose behavior is sometimes undefined. I
agree that such a program is "broken," but so is any other program
with a race condition. Why the reluctance to call this a "race
condition"?
Tom Payne
Doug Reiland
Tom Payne wrote in message <7na9ct$638$1...@pravda.ucr.edu>...
I'm not sure what race has got to do with this response. If the question is:
Can bad code be written to attempt to unlock a mutex that another thread has
locked? The answer is YES. Of course, an implementation can keep accounting
to keep catch of the owning thread and abort the bad thread.
The guy really probably wanted to know what David answered. Usually mutex
can design as follows:
lock:
get control of mutex (atomic operation) - spins until it gets control
look at state of mutex:
- if mutex already locked, goto sleep, return failed, etc..
depending on arguments
- if not locked, lock it (set a flag)
release control of mutex (atomic operation)
unlock:
get control of mutex (atomic operation) - spins util it gets control
clear lock (clear flag)
release control of mutex (atomic operation)
This assumes the mutex is an exclusive mutex.
Doug
Patrick TJ McPhee
Tom Payne <t...@hill.cs.ucr.edu> wrote:
% with a race condition. Why the reluctance to call this a "race
% condition"?
I normally think of a race condition as something that comes up if each
of the components, on its own, works correctly, but taken together
they fail. In this case, you don't need the `healthy' code to be running
for the problem to come up, so the problem isn't a race.
Tom Payne
: In article <7na9ct$638$1...@pravda.ucr.edu>,
: Tom Payne <t...@hill.cs.ucr.edu> wrote:
: % with a race condition. Why the reluctance to call this a "race
: % condition"?
: I normally think of a race condition as something that comes up if each
: of the components, on its own, works correctly, but taken together
: they fail. In this case, you don't need the `healthy' code to be running
: for the problem to come up, so the problem isn't a race.
Huh? Most folks don't debug race conditions where both outcomes are
equally correct. So, in all the race conditions I hear about, one
outcome is intended (and correct), while the other is unintended (and
incorrect). Also, in the usual case, the incorrect outcome is far
less frequent, yielding an intermittent bug that's quite tedious to
track down.
Tom Payne
David Schwartz
When you go outside the rules, behavior _always_ becomes undefined.
This tells us nothing about mutexes or race conditions.
DS
Tom Payne wrote:
>
> In comp.programming.threads David Schwartz <dav...@webmaster.com> wrote:
>
> :> Threads A and B race to, respectively, lock and unlock a given
> :> unlocked mutex. Suppose B wins and unlocks the unlocked mutex. A
> :> race is a race regardless of outcome. (See the "good basic
> :> definition" above.)
>
> : Two threads cannot race to unlock a given mutex as only the thread that
> : holds a mutex may unlock it and only one thread may hold a mutex at a
> : time.
>
> It has been legislated that B "may not" unlock the mutex, but that
> doesn't stop him from doing so. (Legislation alone never stops
> crime.) The race goes on, and the behavior of the program becomes
> undefined whenever B wins the race, which is different from the
> outcome when A wins the race. By defnition, we have a "race
> condition," and a program whose behavior is sometimes undefined. I
> agree that such a program is "broken," but so is any other program
> with a race condition. Why the reluctance to call this a "race
> condition"?
>
> Tom Payne
Ken Pizzini
>It has been legislated that B "may not" unlock the mutex, but that
>doesn't stop him from doing so.
You also "may not" free() memory that was not allocated with
malloc()/calloc()/realloc(), but that doesn't stop one from
doing so.
> (Legislation alone never stops
>crime.) The race goes on, and the behavior of the program becomes
>undefined whenever B wins the race, which is different from the
>outcome when A wins the race. By defnition, we have a "race
>condition," and a program whose behavior is sometimes undefined. I
>agree that such a program is "broken," but so is any other program
>with a race condition. Why the reluctance to call this a "race
>condition"?
Because it is a flat-out bug to release a lock that you don't own.
A "race" refers to the class of bugs where at least one ordering
of the execution of multiple threads is correct and at least
one other ordering is incorrect. But, since you have a bug whether
you release a lock that isn't allocated or you release a lock which
belongs to another thread, there is no race.
--Ken Pizzini
David Schwartz
Ken Pizzini wrote:
>
> On 23 Jul 1999 17:39:41 GMT, Tom Payne <t...@hill.cs.ucr.edu> wrote:
> >It has been legislated that B "may not" unlock the mutex, but that
> >doesn't stop him from doing so.
>
> You also "may not" free() memory that was not allocated with
> malloc()/calloc()/realloc(), but that doesn't stop one from
> doing so.
Yes, but it means that we can't analyze (portably) what happens when
you do it. We simply say "that's not defined" and we move on to consider
other things.
No matter how a mutex behaves when it is unlocked by a thread that
hasn't locked it, it says nothing bad about mutexes. A mutex can behave
any way it wants if you manipulate it in undefined ways.
DS
Kaz Kylheku
>
>
>Ken Pizzini wrote:
>>
>> On 23 Jul 1999 17:39:41 GMT, Tom Payne <t...@hill.cs.ucr.edu> wrote:
>> >It has been legislated that B "may not" unlock the mutex, but that
>> >doesn't stop him from doing so.
>>
>> You also "may not" free() memory that was not allocated with
>> malloc()/calloc()/realloc(), but that doesn't stop one from
>> doing so.
>
> Yes, but it means that we can't analyze (portably) what happens when
>you do it. We simply say "that's not defined" and we move on to consider
>other things.
We had this debate about two months ago. My view is that unlocking
a mutex that you do not own is a simple case of violating an interface
contract.
It's wrong even if there is only a single thread in the system, in which case
there is nothing to race against, so it's not a race condition (at least not in
that case).
In a multithreaded program, there are all kinds of things that may happen in an
unpredictable order, yet the outcome is correct. A race condition happens when
among the multiple possible execution orders, some lead to incorrect results,
the misuse of data objects, or other kinds of failures.
Unlocking a mutex by other than the owner leads to a misuse of an object in
*all* possible execution orders. *Whether or not* the mutex is locked by thread
A, it is illegal for thread B to try to unlock it. So it's irrelevant whether
B wins the race and tries to unlock before A locks, or whether it loses the
race and tries to unlock afterward or whether some concurrency interleaving
happens between the two.
In my view, if all possible execution orders lead to the failure, then
the problem should be considered something other than race
condition---particularly if all executions lead to the *same* problem, or to
one of a set of problems that are closely related.
Only if some of the execution orders are incorrect, the problem should be
properly called a race condition.
> No matter how a mutex behaves when it is unlocked by a thread that
>hasn't locked it, it says nothing bad about mutexes. A mutex can behave
>any way it wants if you manipulate it in undefined ways.
Agreed. The program could, for instance, bring up a game of Tetris each
time it is run, regardless of the scheduling order of its threads. :)
Tom Payne
: On 23 Jul 1999 17:39:41 GMT, Tom Payne <t...@hill.cs.ucr.edu> wrote:
:>It has been legislated that B "may not" unlock the mutex, but that
:>doesn't stop him from doing so.
: You also "may not" free() memory that was not allocated with
: malloc()/calloc()/realloc(), but that doesn't stop one from
: doing so.
Exactly.
:> (Legislation alone never stops
:>crime.) The race goes on, and the behavior of the program becomes
:>undefined whenever B wins the race, which is different from the
:>outcome when A wins the race. By defnition, we have a "race
:>condition," and a program whose behavior is sometimes undefined. I
:>agree that such a program is "broken," but so is any other program
:>with a race condition. Why the reluctance to call this a "race
:>condition"?
: Because it is a flat-out bug to release a lock that you don't own.
Agreed.
: A "race" refers to the class of bugs where at least one ordering
: of the execution of multiple threads is correct and at least
: one other ordering is incorrect.
Right. And, the hypothesized situation is:
> Threads A and B race to, respectively, lock and unlock a given
> unlocked mutex. ...
If B wins, we have a constraint violation, which is a bug. If A wins,
we have conforming behavior, not a bug. That seems to fill your
requirements for a race condition.
: But, since you have a bug whether you release a lock that isn't
: allocated or you release a lock which belongs to another thread,
: there is no race.
What's wrong with calling this situation is "a race condition leading
to a possible constraint violation"? Keep in mind that there is no
constraint violation until and unless B wins the race, and by then the
race has occurred.
Tom Payne
Kaz Kylheku
>What's wrong with calling this situation is "a race condition leading
>to a possible constraint violation"? Keep in mind that there is no
>constraint violation until and unless B wins the race, and by then the
>race has occurred.
I believe that it's wrong for B to unlock if it does not hold the lock, whether
or not A holds the lock. The constraint is violated regardless of the execution
order. B simply has no business executing the unlock operation.
We might as well replace B's unlock operation with a division by zero.
Ken Pizzini
>> unlocked mutex. ...
>
>If B wins, we have a constraint violation, which is a bug. If A wins,
>we have conforming behavior, not a bug. That seems to fill your
>requirements for a race condition.
How is it conforming that B releases a lock that A required?
Unless A explicitly gives B permission to release the lock,
which it shouldn't be doing before it owns the lock, B has
no business in releasing A's lock, even if the API permits it.
>: But, since you have a bug whether you release a lock that isn't
>: allocated or you release a lock which belongs to another thread,
>: there is no race.
>
>What's wrong with calling this situation is "a race condition leading
>to a possible constraint violation"? Keep in mind that there is no
>constraint violation until and unless B wins the race, and by then the
>race has occurred.
I'm still failing to see how this is a race, because I'm still
failing to see how B can validly think that it's okay to be releasing
that lock.
--Ken Pizzini
Tom Payne
:>> Threads A and B race to, respectively, lock and unlock a given
:>> unlocked mutex. ...
:>
:>If B wins, we have a constraint violation, which is a bug. If A wins,
:>we have conforming behavior, not a bug. That seems to fill your
:>requirements for a race condition.
: How is it conforming that B releases a lock that A required?
: Unless A explicitly gives B permission to release the lock,
: which it shouldn't be doing before it owns the lock, B has
: no business in releasing A's lock, even if the API permits it.
Right. (I missed your point.) Unless we presume that A implicitly
passes ownership of the lock, we have a race between two different
constraint violations --- not a significant difference in outcomes and
therefore not a race.
Tom Payne
Dave Butenhof
Ownership of a mutex cannot be passed. There's no such mechanism, or
concept.
(You can, of course, "pass ownership" with a semaphore, where ownership is
a matter of application convention rather than interface semantics.)
If the code is written so that thread B can even TRY to unlock a mutex it
has not locked, that's a static coding error. As everyone's been saying, it
cannot be considered a race. As someone commented, it's no different than
coding thread B to execute the statement "1/0". That's not a "race", even
if there's some chance that thread B won't actually execute the statement.
(Unless perhaps some other thread intends to concurrently change the value
of 0. ;-) )
/---------------------------[ Dave Butenhof ]--------------------------\
| Compaq Computer Corporation David.B...@compaq.com |
| 110 Spit Brook Rd ZKO2-3/Q18 http://members.aol.com/drbutenhof |
| Nashua NH 03062-2698 http://www.awl.com/cseng/titles/0-201-63392-2/ |
\-----------------[ Better Living Through Concurrency ]----------------/
David Schwartz
> If the code is written so that thread B can even TRY to unlock a mutex it
> has not locked, that's a static coding error. As everyone's been saying, it
> cannot be considered a race. As someone commented, it's no different than
> coding thread B to execute the statement "1/0". That's not a "race", even
> if there's some chance that thread B won't actually execute the statement.
> (Unless perhaps some other thread intends to concurrently change the value
> of 0. ;-) )
You could do that on VAX Fortran, it wasn't too careful about
protecting its constants. You could do the equivalent of:
void set(int *j)
{
*j=1;
}
void test(void)
{
const int c=2;
int a,b;
set((int *)&c);
a=2;
b=1;
if(a==b) printf("Yes, you would actually see this\n");
}
It would happily pass pointers into the table where it stored program
constants. If you modified them, subsequent loads of the constants would
load the modified values.
DS