Mutex implementation with semaphores
Rob Stedman
I'm trying to implement mutex functionality using semaphores only. I
have a solution which I know to not be thread safe that uses two
sempahores. Can anyone suggest how to make the mutex fully thread
safe.
Here's example pseudo-code for the mutex obtain algorithm. This is
not threadsafe at the point where the caller has had to wait to obtain
the mutex. The task may be prempted in between lines 19 to 20.
Another task could obtain access to the mutex, then when the first
task resumes from line 20 on it forces hold count to 1.
Can anyone suggest a thread safe alternative?
Thanks,
Rob
Code example:
1 Obtain()
2 {
3 Get caller task Id
4 Lock access to mutex internals using lock semaphore
5 if (mutex is not currently taken)
6 {
7 set mutex hold count = 1
8 take mutex semaphore
9 }
10 else
11 {
12 if ( current holding task Id == caller's task Id)
13 {
14 increment muxtex hold count
15 }
16 else
17 {
18 unlock access to mutex internals
19 wait to obtain mutex sempahore
20 lock access to mutex internals << NOT THREADSAFE
21 set mutex hold count = 1
22 }
23 }
24 unlock access to mutex internals
25 }
Herman Bruyninckx
> I'm trying to implement mutex functionality using semaphores only. I
I thought a mutex was just a (binary) semaphore... So, you have
already your implementation.
Herman
Steve Watt
Rob Stedman <robste...@yahoo.co.uk> wrote:
>Hi,
>
>I'm trying to implement mutex functionality using semaphores only. I
>have a solution which I know to not be thread safe that uses two
>sempahores. Can anyone suggest how to make the mutex fully thread
>safe.
You're pretty close...
>Code example:
>
> 1 Obtain()
> 2 {
> 3 Get caller task Id
> 4 Lock access to mutex internals using lock semaphore
> 5 if (mutex is not currently taken)
> 6 {
> 7 set mutex hold count = 1
> 8 take mutex semaphore
> 9 }
>10 else
>11 {
>12 if ( current holding task Id == caller's task Id)
>13 {
>14 increment muxtex hold count
>15 }
>16 else
>17 {
>18 unlock access to mutex internals
>19 wait to obtain mutex sempahore
goto line 4
>22 }
>23 }
>24 unlock access to mutex internals
>25 }
OK, one doesn't have to *code* it with a goto, but that should
be all you need. Yes, I know that it might not be "fair", but
mutexes aren't, in general.
--
Steve Watt KD6GGD PP-ASEL-IA ICBM: 121W 56' 57.8" / 37N 20' 14.9"
Internet: steve @ Watt.COM Whois: SW32
Free time? There's no such thing. It just comes in varying prices...
Ephraim Gadsby
wrote:
In the example below each mutex has one semaphore which is held while
the mutex is held. The semaphore serves two functions. it gives tasks
something to block on, and it protects the internals.
obtain(mutex){
if( mutex->task == this_task){
mutex->count++
}
else{
wait_semaphore (mutex->semaphore)
mutex->count = 1
mutex->task = this_task
}
}
release(mutex){
mutex->count --
if (mutex->count == 0)
mutex->task = NO_TASK
drop_semaphore(mutex->semaphore)
}
}
Rob Stedman
thanks for the reply. Unfortunately the example below still doesn't
look thread safe as there's nothing to stop different threads altering
the mutex internal data simultaneously.
I also intended that the mutex may only be released by the task that
currently has the mutex, so the release function must check it is the
task holding the mutex before it can decrement the hold count.
I still can't see how it's done in a thread safe way with 2 semaphores
Rob
Ephraim Gadsby <a@b.c> wrote in message >
Rob Stedman
Steve,
thanks for the reply - this looks like a good solution!
Rob
Benjamin Kaufman
Ben
Benjamin Kaufman
<snip>
>
>Can anyone suggest a thread safe alternative?
>
>Thanks,
>Rob
> :
>
1 Initialize semaphore with count of 1.
2. To obtain "mutex", make decrement call on semaphore.
3. To release "mutex", siimply make increment call on semaphore.
Ben
NSC
The difference between a mutex (or correctly it should be called a monitor
based on Tony Hoare's work) and the binary semaphore is the concept of
ownership. With a semaphore any task can call the pend/post (p/v; there is
no check made that the task calling the post is the task that did the pend.
Also, with most OS's, the semaphore can be initailised to empty(0) or
full(1). This allows a programmer to use the semaphore as a signal (by init
to 0).
The monitor/mutex by contrast checks that the task doing the release is the
same task doing the lock. Also an extension to the original monitor is the
ability to wait within the critical region. Once signalled this blocked task
has priority over the other waiting tasks for the monitor.
Niall.
"Benjamin Kaufman" <robomechan...@pobox.com> wrote in message
news:r8k1mu8kvhj85qr6n...@4ax.com...
Chris Jones
As was pointed out elsewhere in this thread, this is incorrect. Mutexes
have the concept of ownership, so only the read which acquired the mutex
may release it. Semaphores allow any thread to release the semaphore.
Also, mutexes allow the owning thread to acquire it multiple times,
while semaphores will block any thread which attempts to lock a
semaphore which has a count of zero.
It is a misconception, albeit an all too common one, that mutexes and
binary semaphores are identical.
Ephraim Gadsby
wrote:
>thanks for the reply. Unfortunately the example below still doesn't
>look thread safe as there's nothing to stop different threads altering
>the mutex internal data simultaneously.
>
>I also intended that the mutex may only be released by the task that
>currently has the mutex, so the release function must check it is the
>task holding the mutex before it can decrement the hold count.
>
>I still can't see how it's done in a thread safe way with 2 semaphores
>
Firstly, in the implementation I gave, only a task that holds the
mutex manipulates the internals, (while the underlying semaphore is
held). Note that (mutex->task == this_task) is a reliable test that
the current task already holds the mutex - follow it through.
if( mutex->task == this_task){
// if we reach here then the current task MUST have the mutex
mutex->count++ // this line is therefore safe
}
else{
// we don't yet have the mutex so we wait for the semaphore
// other tasks may alter mutex->task
// but they wont set it to this task's task_id
wait_semaphore (mutex->semaphore)
// at this point mutex->task == NO_TASK
// (see the release function)
mutex->count = 1
mutex->task = this_task
}
[ Nit-Picking Aside. Theoretically this could fail if task id
assignment is not atomic, and changing a value from NO_TASK to TASK_A,
temporarily produced a value equal to TASK_B. That is pretty
artificial and also trivial to handle.]
On the second point, a task that does not hold the mutex should
*never* be in a position to release it. The decrement should not be
conditional, but something like an assert, or throwing an exception
would be more appropriate.
Ephraim Gadsby
>The semaphore and mutex are not the same.
>
>The difference between a mutex (or correctly it should be called a monitor
>based on Tony Hoare's work) and the binary semaphore is the concept of
>ownership. With a semaphore any task can call the pend/post (p/v; there is
>no check made that the task calling the post is the task that did the pend.
>Also, with most OS's, the semaphore can be initailised to empty(0) or
>full(1). This allows a programmer to use the semaphore as a signal (by init
>to 0).
>
>The monitor/mutex by contrast checks that the task doing the release is the
>same task doing the lock. Also an extension to the original monitor is the
>ability to wait within the critical region. Once signalled this blocked task
>has priority over the other waiting tasks for the monitor.
As I understand it a mutex is a way of implementing monitors in
languages that don't have direct monitor support.
e.g.
monitor a{
foo()
bar()
}
gets implemented in C as
as
foo(){
take_mutex(mutex_a)
...
release_mutex(mutex_a)
}
bar(){
take_mutex(mutex_a)
...
release_mutex(mutex_a)
}
In the monitor foo can call bar, so a key property of mutexes is that
once a task has the mutex it can take it again provided it releases it
the same number of times.
Benjamin Kaufman
Ben
Alexander Terekhov
Rob Stedman wrote:
[...]
You might want to take a look at "Semaphore-based recursive lock..." here:
http://groups.google.com/groups?selm=c29b5e33.0201300253.5f94f544%40posting.google.com
(Subject: Re: (Slightly OT): Communicating bwt processes using shared mem.)
regards,
alexander.
Emil Rojas
problem.
I think posix provides a mechanism to modify the state of one
semaphore while releasing for grabing another. VxWorks allows you to
take a semaphore after calling taskLock() making it thread safe, and
you should only need one semaphore (I recently had cause to use this
to make an Win32 like event under VxWorks, my implementation had a
similar problem.) Some OSs simply provide both, e.g. Win32.
emil
robste...@yahoo.co.uk (Rob Stedman) wrote in message news:<2d6415f5.02081...@posting.google.com>...
NSC
"Ephraim Gadsby" <a@b.c> wrote in message
Yes you're quite right, I was wrong to mix the mutex and the monitor.
Strictly speaking a monitor is module that combines shared variables,
procedures/functions and an initial statement.
The mutex is like a semaphore except it (a) has the concept of ownership,
and (b) is re-entrant (as you pointed out if I own the mutex I won't block
again).
Regards,
Niall.
Steve Watt
Ephraim Gadsby <a@b.c> wrote:
>On 19 Aug 2002 02:44:29 -0700, robste...@yahoo.co.uk (Rob Stedman)
>wrote:
>>thanks for the reply. Unfortunately the example below still doesn't
>>look thread safe as there's nothing to stop different threads altering
>>the mutex internal data simultaneously.
>>
>>I also intended that the mutex may only be released by the task that
>>currently has the mutex, so the release function must check it is the
>>task holding the mutex before it can decrement the hold count.
>>
>>I still can't see how it's done in a thread safe way with 2 semaphores
[ He hadn't gotten to my other post yet. ]
>Firstly, in the implementation I gave, only a task that holds the
>mutex manipulates the internals, (while the underlying semaphore is
>held). Note that (mutex->task == this_task) is a reliable test that
>the current task already holds the mutex - follow it through.
>
> if( mutex->task == this_task){
>
> // if we reach here then the current task MUST have the mutex
> mutex->count++ // this line is therefore safe
No, because it relied on unsynchronized access to shared data.
> }
> else{
> // we don't yet have the mutex so we wait for the semaphore
> // other tasks may alter mutex->task
> // but they wont set it to this task's task_id
>
> wait_semaphore (mutex->semaphore)
>
> // at this point mutex->task == NO_TASK
> // (see the release function)
>
> mutex->count = 1
> mutex->task = this_task
> }
>
>[ Nit-Picking Aside. Theoretically this could fail if task id
>assignment is not atomic, and changing a value from NO_TASK to TASK_A,
>temporarily produced a value equal to TASK_B. That is pretty
>artificial and also trivial to handle.]
No, this is just another variant of double-checked locking, and can't
be made to work reliably on all systems. Google for "DCL" and/or
"double check locking" in this newsgroup.
Ephraim Gadsby
wrote:
I'm cannot find the threads you mean, "double check[ed] locking"
produces no hits in this group and dcl produces too many in a
different context. But from what I've read of DCL I believe you have
misunderstood what is going on here.
Everything else is obviously manipulated under the semaphore so the
key thing here is:
if( mutex->task == this_task){
mutex->count++
}
The increment statement is only reached on recursive calls when the
mutex (and the underlying semaphore) is already held. This means that
ALL mutex internals are written under the semaphore. Of course this
hinges on the "if" statement being a reliable test that the semaphore
is held.
Setting mutex->task can only be done by taking the semaphore, and the
last thing that is done before the semaphore is released is to set it
back to NO_TASK. No other task can set a value of mutex->task that
makes the logical statement true for the current task.
I can see no damaging compiler reordering here, that can be done
without exchanging the order of assignment and semaphore operations,
which is obviously not going to happen..
Even if "mutex->task" is held in a register, and not reread then
it can only be out of synch when the semaphore is not held, so there
is still no problem.
Ephraim Gadsby
wrote:
>In article <2d6415f5.02081...@posting.google.com>,
At the goto statement the mutex semaphore is held and the internals
lock is about to be taken.
At line 7 the internals lock is held and the mutex semaphore is about
to be taken.
Steve Watt
Ephraim Gadsby <a@b.c> wrote:
>On Tue, 20 Aug 2002 19:05:50 GMT, st...@nospam.Watt.COM (Steve Watt)
>wrote:
>
>>In article <65m1mug2kdf1ur8kr...@4ax.com>,
>>Ephraim Gadsby <a@b.c> wrote:
>>> if( mutex->task == this_task){
>>>
>>> // if we reach here then the current task MUST have the mutex
>>> mutex->count++ // this line is therefore safe
>>
>>be made to work reliably on all systems. Google for "DCL" and/or
>>"double check locking" in this newsgroup.
>
>I'm cannot find the threads you mean, "double check[ed] locking"
>produces no hits in this group and dcl produces too many in a
>different context. But from what I've read of DCL I believe you have
>misunderstood what is going on here.
[ This one's for you, Alexander. ]
http://groups.google.com/groups?as_q=double+check+locking&as_ugroup=comp.programming.threads
>The increment statement is only reached on recursive calls when the
>mutex (and the underlying semaphore) is already held. This means that
>ALL mutex internals are written under the semaphore. Of course this
>hinges on the "if" statement being a reliable test that the semaphore
>is held.
It isn't enough that they are written under protection -- *reading* must
be synchronized with writing. It is possible for unordered memory accesses
by the processor to break an astonishing number of assumptions.
>I can see no damaging compiler reordering here, that can be done
>without exchanging the order of assignment and semaphore operations,
>which is obviously not going to happen..
Ah, but reads and writes can be done in different orders by the CPU
unless you take action to prevent it. That action is a memory barrier.
For portable code, that action is a synchronization point (i.e. mutex,
condvar, semaphore, a few other things).
Alexander Terekhov
Steve Watt wrote:
[...]
> [ This one's for you, Alexander. ]
>
> http://groups.google.com/groups?as_q=double+check+locking&as_ugroup=comp.programming.threads
;-)
< Ephraim Gadsby <a@b.c> wrote: >
> >The increment statement is only reached on recursive calls when the
> >mutex (and the underlying semaphore) is already held. This means that
> >ALL mutex internals are written under the semaphore. Of course this
> >hinges on the "if" statement
But this "if" statement VIOLATES portable memory sync. rules:
http://www.opengroup.org/onlinepubs/007904975/basedefs/xbd_chap04.html#tag_04_10
Well, there are non-portable "exceptions" when it's harmless
(see algorithms for implementing condvars and read-write locks
using semas I've referenced here earlier), but THIS ONE ISN'T
"HARMLESS" AT ALL.
> > being a reliable test that the semaphore is held.
Thread specific data (TSD) is the only portable "reliable test
that the semaphore is held" -- see TSD-based solution for impl.
recursive lock on top of one single {bin.}sema I've referenced
here earlier.
regards,
alexander.
Ephraim Gadsby
wrote:
I understand, but this problem is subtlely different to those DCL
examples, because task ids are unique to each task and a task only
ever writes NO_TASK or its own task ID into mutex->task.
I'll go through the cases to make it a little clearer,
1. The Current Task Already has the Semaphore
in this case there is no problem
so "mutex->task == this_task" IS TRUE
2. The Current Task Doesn't Have the Semaphore
two subcases:
2.1 it gets a correct value of mutex->task
so "mutex->task == this_task" IS FALSE
2,2 It gets an out of date value for mutex->task
The only values it can have are NO_TASK,
or the task ID for a different task,
so "mutex->task == this_task" IS FALSE
On other words even though access to mutex->task is not synchronized
and mutex->task may be wrong. the boolean value of
"mutex->task==this_task" is always correct.
Ephraim Gadsby
Quoting pthread rules is of limited relevence, since this is a
realtime group, not a pthead group.
Asserting that it doesn't work because it violates synchronization
rules is not an answer, because as I've said elsewhere, it doesn't
rely on synchronization.
What it boils down to is this:
#define MAGIC 42
int x = 0;
TASK_B()
{
// loop aound writing any value EXCEPT MAGIC into x
while(1){
semtake()
temp = random_int
if(temp != MAGIC){
x=temp
}
semGive()
}
}
Task_A(){
// loop around while we see if the lack of synchronization matters
while (1){
If (x == MAGIC){
printf("test fail")
}
semtake()
x = MAGIC
If (x != MAGIC){
printf("test failed")
}
x = 0
semGive()
}
}
Could you please quote a realistic scenario where either printf
statemant would be reached.
(other than the rather artificial case involving non-atomic
read-write of x which I already gave, and which can be trivially
fixed by wrapping each read/write to x in its own semaphore).
Alexander Terekhov
Ephraim Gadsby wrote:
[...]
> Quoting pthread rules is of limited relevence, since this is a
> realtime group, not a pthead group.
Okay, then please quote some COUNTER "realtime" rules, if you can.
Unless, of course, you simply presume a) atomicity w.r.t. "task-id"
access and b) that your programs can only run on >>uniprocessors<<
[scheduling allocation domains of size one -- with well/portably-
defined real-time sched. behavior; that's according to IEEE Std
1003.1/POSIX.1 standard, BTW].
> Asserting that it doesn't work because it violates synchronization
> rules is not an answer, because as I've said elsewhere, it doesn't
> rely on synchronization.
No, it does. Atomicity aside, to begin with, there is the guarantee
that your "if" in task A wouldn't see/read the "task-id" written by
some "old" (already terminated and reclaimed task) in the past that
had the same "task-id"? (and, due to lack of memory synchronization,
whether it had released a lock prior to termination or not, doesn't
really matter, BTW)
regards,
alexander.
Steve Watt
Ephraim Gadsby <a@b.c> wrote:
[ ... ]
This is not quite equivalent to what you showed before.
Previously, you had (code vertically compressed):
obtain(mutex *m) {
if (m->task == this_task) m->count++;
else { semTake(m->sem); m->count = 1; m->task = this_task; }
}
release(mutex *m) {
if (--m->count == 0) { m->task = NO_TASK; semGive(m->sem); }
}
First bug is that release assumes you're the owner. Yeah, that's a user
error, but still an unprotected access.
One scenario where this fails is on a multiprocessor machine:
if the m->task write gets stuck in a write buffer on one processor, then
the semaphore is posted. There's nothing in the next obtain *on the other
processor* to ensure that the write buffer has cleared. The next
processor comes along, has picked up the exact same thread (which was
preempted, or whatever, on the first processor). You now have a case
where m->task == this_task, but m->sem has not been taken by this
task.
Another scenario where this fails is if you have dynamic tasks, and
one dies while holding the mutex. If another task can be assigned
the same task ID, all bets are off.