Can semaphore operations replace mutex+cond var?
climb...@gmail.com
I have seen an program using pthread, that attempts to use only
semaphores(provided in semaphore.h) instead of mutex and condition
variables.
The code snippet is attached below. I am not sure these two
implementations would behave the same. The first version follows the
conventional way, and the second version is the replacement attempt.
but what would the 2nd version do?
// assme that a mutex and a condition var is available in type rw_x
void start_read(rw_x *a) {
pthread_mutex_lock(&a->mutex);
while (a->rw == 0)
pthread_cond_wait(&a->cv, &a->mutex);
a->rw++;
pthread_mutex_unlock(&a->mutex);
}
// assme that two semaphores are defined in type rw_y, that are meant
to replace mutex and cv respectively.
void start_read(rw_y *a) {
sem_wait(&a->rd_mutex);
if (a->nr == 0) sem_wait(&a->wr_sem);
a->nr++;
sem_post(&a->rd_mutex);
}
thanks
tony
Hallvard B Furuseth
> The code snippet is attached below. I am not sure these two
> implementations would behave the same.
> void start_read(rw_x *a) {
> pthread_mutex_lock(&a->mutex);
> while (a->rw == 0)
> pthread_cond_wait(&a->cv, &a->mutex);
> a->rw++;
> pthread_mutex_unlock(&a->mutex);
> }
This looks like a semaphore where rw <= 0 instead of the more common
case where rw >= 0. So maybe the equivalent code with semaphores
is simply to invert the sign and use
while ((rc = sem_wait(a)) < 0 && rc == EINTR);
where you take care to use positive instead of negative values.
However you don't show the code which signals/broadcasts to the rw_x, so
there's no way to tell if there is a simple semaphore equivalent to your
code.
--
Hallvard
climb...@gmail.com
> However you don't show the code which signals/broadcasts to the rw_x, so
> there's no way to tell if there is a simple semaphore equivalent to your
> code.
>
More details about the program is posted here. The semaphore version
uses two semphore variables to replace mutex and cv.
-----------------------------------------------------------------------
typedef struct {
int rw; /* -1: one writer; 0: idle; > 0: #readers */
pthread_mutex_t mutex;
pthread_cond_t cv;
} rw_arbiter;
void start_read(rw_arbiter *a) {
pthread_mutex_lock(&a->mutex);
while (a->rw < 0)
pthread_cond_wait(&a->cv, &a->mutex);
a->rw++;
pthread_mutex_unlock(&a->mutex);
}
void end_read(rw_arbiter *a) {
pthread_mutex_lock(&a->mutex);
a->rw--;
pthread_cond_broadcast(&a->cv);
pthread_mutex_unlock(&a->mutex);
}
void start_write(rw_arbiter *a) {
pthread_mutex_lock(&a->mutex);
while (a->rw != 0)
pthread_cond_wait(&a->cv, &a->mutex);
a->rw = -1;
pthread_mutex_unlock(&a->mutex);
}
void end_write(rw_arbiter *a) {
pthread_mutex_lock(&a->mutex);
a->rw = 0;
pthread_cond_broadcast(&a->cv);
pthread_mutex_unlock(&a->mutex);
}
Szabolcs Ferenczi
> Hi all,
> I have seen an program using pthread, that attempts to use only
> semaphores(provided in semaphore.h) instead of mutex and condition
> variables.
Yes, it is possible. You can use semaphores for any synchronisation
problems as well as you can use mutex+condvar+sharedvar combination.
> The code snippet is attached below. I am not sure these two
> implementations would behave the same.
Unfortunately not. The semaphore version will deadlock provided a->nr
is handled under the protection of a->rd_mutex in the rest of the
program too. Namely, when any thread of computation starts waiting on
a->wr_sem, the mutex remains closed so not change of a->nr is possible
provided it is protected by rd_mutex.
> The first version follows the
> conventional way, and the second version is the replacement attempt.
> but what would the 2nd version do?
>
> // assme that a mutex and a condition var is available in type rw_x
> void start_read(rw_x *a) {
> pthread_mutex_lock(&a->mutex);
> while (a->rw == 0)
> pthread_cond_wait(&a->cv, &a->mutex);
> a->rw++;
> pthread_mutex_unlock(&a->mutex);
>
> }
>
> // assme that two semaphores are defined in type rw_y, that are meant
> to replace mutex and cv respectively.
> void start_read(rw_y *a) {
> sem_wait(&a->rd_mutex);
> if (a->nr == 0) sem_wait(&a->wr_sem);
> a->nr++;
> sem_post(&a->rd_mutex);
>
> }
You might look up the readers and writers problem solved with
semaphores from any standard course-book on concurrent programming.
Best Regards,
Szabolcs
Szabolcs Ferenczi
> [...] The semaphore version
> uses two semphore variables to replace mutex and cv.
You have to be careful with the mapping since the cv wait operation
atomically unlocks the mutex before the thread is suspended and the
mutex is locked before the wait operation is completed.
If you try to mimic it with two semaphores, you have to take care of
unlocking and locking the semaphore used for the mutex role otherwise
you create a deadlock.
You must also consider that if you unlock the semaphore playing the
mutex role before suspending the thread on the semaphore playing the
cv role, the two operations are not atomic consequently anything may
happen in between.
Usually, it is better to think differently when you work with
semaphores. E.g. check out the canonical example of the bounded buffer
solved with counting semaphores and with mutex+condvar from any
standard textbook on concurrent programming.
Best Regards,
Szabolcs
Chris M. Thomasson
news:4c943c06-0cb2-4639...@75g2000hso.googlegroups.com...
If you want to use semaphores like condvars, well, then I suggest you have a
look at Alex Terekhovs work in pthread-win32. Joe Seigh created a rw-lock
using SysV semaphores:
http://groups.google.com/group/comp.unix.programmer/msg/eeb6ef534e0fc189
You can't do that with POSIX semaphores. He takes advantage of the SysV
`semop()' function which can atomically operate on several semaphores at
once.
One example use of semaphores would be something like:
_______________________________________________________________
class blocking_collection {
collection m_col;
mutex m_mtx;
semaphore m_sem;
public:
void push(void* const obj) {
{
mutex::guard lock(m_mtx);
m_col.push(obj);
}
m_sem.post();
}
void* pop() {
m_sem.wait();
mutex::guard lock(m_mtx);
return m_col.try_pop();
}
};
_______________________________________________________________
However, this use of semaphore is inefficient because its internal counter
is keeping redundant state around and the collection itself already knows
how many items it holds. Therefore, one can use a condvar and use the
collections internal state as a predicate:
_______________________________________________________________
class blocking_collection {
collection m_col;
mutex m_mtx;
condvar m_cond;
public:
void push(void* const obj) {
{
mutex::guard lock(m_mtx);
m_col.push(obj);
}
m_cond.signal();
}
void* pop() {
void* obj;
mutex::guard lock(m_mtx);
while (! (obj = m_col.try_pop())) {
m_cond.wait(lock);
}
return obj;
}
};
_______________________________________________________________
Semaphores really make sense when you need to artificially create shared
state just to make use of a condvar; I explain some of that here:
http://groups.google.com/group/comp.programming.threads/msg/4f51d03346a8b3f1
Also, condvar signaling and broadcasting can be more efficient than a
semaphore post; they can be NOP's when you signal/broadcast to a condvar
with no current waiters. On the other hand, when you post a semaphore it
always issues an atomic RMW _and_ a membar...
David Schwartz
> void start_write(rw_arbiter *a) {
> pthread_mutex_lock(&a->mutex);
> while (a->rw != 0)
> pthread_cond_wait(&a->cv, &a->mutex);
> a->rw = -1;
> pthread_mutex_unlock(&a->mutex);
>
> }
If the intent was that this let in only a single writer, it's broken.
Nothing stops two waiting writers from both waking from
'pthread_cond_wait' at the same time, both finding a->rw==0 and both
setting a->rw to -1. Not only will both writers run concurrently, but
when either of them releases the lock, the other one will be running
concurrently with readers.
This is not a proper way to make reader/writer lock out of a mutex and
a cv.
In pseudo-code, the proper way is:
Acquire Read Lock:
1) Lock sync mutex.
2) Increment waiting reader count.
3) Block on reader condvar while writercount>0, releasing sync mutex.
4) Increment reader count.
5) Decrement waiting reader count.
6) Release sync mutex.
Release Read Lock:
1) Lock sync mutex.
2) Decrement reader count.
3) If reader count is equivalent to zero and writer count is greater
than zero,
signal writer condvar.
4) Release sync mutex.
Acquire Write Lock:
1) Acquire synx mutex.
2) Increment writer count
3) Block on writer condvar while reader count is not zero.
4) Set reader count to -1.
5) Release sync mutex.
(One and only one thread can set reader count from zero to negative
one, and can only do so when there are no active readers.)
Release Write Lock:
1) Acquire synx mutex.
2) Set reader count to zero.
3) Decrement writer count.
4) If writer count is non-zero, signal writer condvar. Else if waiting
reader count is non-zero, broadcast reader condvar.
5) Release synx mutex.
You can merge the condvars. Platform-specific optimizations may be
possible.
Note that if you implement 'try lock' functions, you may need to
change all condvar signals to broadcasts.
DS
Hallvard B Furuseth
> On Oct 30, 10:33 am, climber....@gmail.com wrote:
>> void start_write(rw_arbiter *a) {
>> pthread_mutex_lock(&a->mutex);
>> while (a->rw != 0)
>> pthread_cond_wait(&a->cv, &a->mutex);
>> a->rw = -1;
>> pthread_mutex_unlock(&a->mutex);
>>
>> }
>
> If the intent was that this let in only a single writer, it's broken.
> Nothing stops two waiting writers from both waking from
> 'pthread_cond_wait' at the same time, both finding a->rw==0 and both
> setting a->rw to -1.
What? The mutex stops them. And the while, with the mutex locked.
--
Hallvard
David Schwartz
wrote:
The 'pthread_cond_wait' function unlocks the mutex. Imagine two
threads running this code concurrently, both returning from
'pthread_cond_wait' to find a->rw==0.
DS
David Schwartz
Ack! Ignore my other reply. You are right.
They can't both return from pthread_cond_wait, since the thread won't
return until it re-acquires the mutex. Only one thread can change the
value from 0 to -1.
DS
Szabolcs Ferenczi
> On Oct 31, 4:22 am, Hallvard B Furuseth <h.b.furus...@usit.uio.no>
> wrote:
>
>
>
> > David Schwartz writes:
> > > On Oct 30, 10:33 am, climber....@gmail.com wrote:
> > >> void start_write(rw_arbiter *a) {
> > >> pthread_mutex_lock(&a->mutex);
> > >> while (a->rw != 0)
> > >> pthread_cond_wait(&a->cv, &a->mutex);
> > >> a->rw = -1;
> > >> pthread_mutex_unlock(&a->mutex);
>
> > >> }
>
> > > If the intent was that this let in only a single writer, it's broken.
> > > Nothing stops two waiting writers from both waking from
> > > 'pthread_cond_wait' at the same time, both finding a->rw==0 and both
> > > setting a->rw to -1.
>
> > What? The mutex stops them. And the while, with the mutex locked.
>
> The 'pthread_cond_wait' function unlocks the mutex.
... and it locks the mutex on return.
> Imagine two
> threads running this code concurrently, both returning from
> 'pthread_cond_wait' to find a->rw==0.
... so they can do it one at a time since mutual exclusion is provided
by the mutex.
Best Regards,
Szabolcs
Eric Sosman
Okay: I'm now imagining a broken pthread_cond_wait() implementation
that somehow fails to re-lock the mutex before returning, as it is
specified to do ...
If there's something wrong with the loop shown above, I'm not
seeing it. There may be problems elsewhere, in the code not shown,
but I can't spot any problem in what's visible.
David Schwartz
wrote:
> ... so they can do it one at a time since mutual exclusion is provided
> by the mutex.
>
> Best Regards,
> Szabolcs
My brain took a brief vacation on that one. It's back now. The code I
was "correcting" does substantially the same thing as my corrected
code does.
DS