apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Aaron Bannert <aa...@ebuilt.com>
Subject Re: Conditionals...
Date Fri, 03 Aug 2001 19:11:52 GMT
On Thu, Aug 02, 2001 at 02:46:59PM -0400, Victor J. Orlikowski wrote:
> Aaron Bannert writes:
>  > On Thu, Aug 02, 2001 at 12:09:05PM -0400, Victor J. Orlikowski wrote:
>  > > Aaron Bannert writes:
> <snip>
>  > Fair enough. The above is much more clear, but there is now another
>  > problem...
>  > 
>  > > 
>  > > Does the new code fit better with what you expect?
>  > 
>  > In your above example, how can more than one thread be wait()ing on
>  > a condition, if only the thread that has the "c->lock" may call
>  > wait()?
>  > 
> 
> Because, in a Condition, the thread that calls Wait releases the lock.
> Hence, another thread may acquire the lock, and call Wait thereafter.
> This will require another two functions, but that is simple enough.
> 
>  > Also, Signal() and Broadcast() may not be MT-safe, as they perform
>  > operations on c->thread_id that are non-exclusive and may be non-atomic
>  > on some platforms.
>  > 
> 
> How?
> Only one thread may obtain c->condlock.
> Hence, only one thread may be listed in thread_id.
> We must simply protect all manipulation of c->thread_id with the condlock.
> Reading the thread_id under this implementation is perfectly safe.

Simply reading from a shared variable is not atomic. All accesses to a
shared variable must be synchronized (or "serialized", if you prefer)
with some form of mutual exclusion. (An example of this is on
Solaris/Sparc, where a context switch can occur half-way through an update to
a longword (or is it a word, I'm not sure).


> Sigh. Let me give you the rest of the puzzle.
> Let Condition have a linked list of the following structure.
> 
> struct Waiter {
>     Semaphore *sem;
>     Waiter *next;
>     Waiter *prev;
> };
> 
> In Wait, allocate a new Waiter structure, with its Semaphore
> initialized to zero. Making sure to protect appends to the list with
> condlock, append this Waiter structure to the list, and then do a wait
> on the Semaphore within it.
> 
> In Signal, again protect the manipulation of the list with the
> condlock. Now, remove the Waiter at the head of the list, and post on
> its semaphore.
> 
> In Broadcast, once again protect accesses of the list via condlock.
> Now, remove Waiters, one at a time, from the list, posting on the
> semaphore of each as you remove it.
> 
> Here is the pseudocode for the finished version (please forgive the
> C++ -isms). NOTE: this is missing many needed checks for NULL values.
> 
> struct Waiter {
>     Semaphore *sem;
>     Waiter *next;
>     Waiter *prev;
> };
> 
> struct Condition {
>      mutex *lock; /* mutex associated with condition */
>      int thread_id; /* Current holder of the lock */
>      struct Waiter *list; /* list of waiters */
>      struct Waiter *tail; /* end of list */
>      mutex condlock;
> };
> 
> void Wait(struct Condition *c) {
>       Waiter *wait;
>       if (c->thread_id != thread_id_of(current_thread))
>           exit(-1); /* Only the holder of the lock may call wait */
>       wait = new Waiter;
>       wait->sem = new Semaphore(0); /* Initialized to 0 */
>       wait->next = NULL;
>       wait->prev = NULL;
>       acquire(c->condlock);
>       l->thread_id = -1; /* or whatever invalid thread value */
>       if (!(c->list))
>           c->tail = wait;
>       wait->next = c->list;
>       c->list = wait;
>       release(c->condlock);
>       release(*(c->lock));
>       wait(wait->sem);
>       acquire(*(c->lock));
>       acquire(c->condlock);
>       c->thread_id = thread_id_of(current_thread);
>       release(c->condlock);
>       delete wait->sem;
>       delete wait;
> }
> 
> void Signal(struct Condition *c) {
>       Waiter *wake;
>       if (c->thread_id != thread_id_of(current_thread))
>           exit(-1); /* Only the holder of the lock may call signal */
>       acquire(c->condlock);
>       if (c->tail) {
>           wake = c->tail;
>           c->tail = wake->prev;
>           post(wake->sem);
>       }
>       release(c->condlock);
> }
> 
> void Broadcast(struct Condition *c) {
>       Waiter *wake;
>       if (c->thread_id != thread_id_of(current_thread))
>           exit(-1); /* Only the holder of the lock may call broadcast */
>       acquire(c->condlock);
>       while (c->tail) {
>           wake = c->tail;
>           c->tail = wake->prev;
>           post(wake->sem);
>       }
>       release(c->condlock);
> }
> 
> /* 0 for success, -1 on error */
> int Acquire_Condition_Lock(struct Condition *c) {
>      if (c->thread_id != -1)
>          return -1; /* Somebody's got the lock */
>      acquire(c->condlock);
>      acquire(*(c->lock));
>      c->thread_id = thread_id_of(current_thread);
>      release(c->condlock);
>      return 0;
> }

Unfortunately this won't work. If two threads are trying to signal
they will both have to run Acquire_Condition_Lock(). The second one
will fail. What then, spin? No.

> 
> int Release_Condition_Lock(struct Condition *c) {
>      if (c->thread_id != thread_id_of(current_thread))
>          return -1; /* We don't hold the lock */
>      acquire(c->condlock);
>      release(*(c->lock));
>      c->thread_id = -1;
>      release(c->condlock);
>      return 0;
> }
> 
> void Condition_Init(struct Condition *c, Lock *l) {
>      c->condlock = new mutex;
>      acquire(c->condlock);
>      c->lock = l;
>      c->thread_id = -1;
>      c->list = c->tail = NULL;
>      release(c->condlock);
> }
> 
> void Condition_Destroy(struct Condition *c) {
>      acquire(c->condlock);
>      if (c->list || (c->thread_id != -1))
>          exit(-1); /* The list should be clear before destroying, and */
>                    /* the lock unlocked */
>      c->lock = NULL;
>      release(c->condlock);
>      delete c->condlock;
>      delete c;
> }
> 
> As you can see, thread_id manipulation only occurs in Condition_Init,
> Acquire_Condition_Lock, Release_Condition_Lock, and Wait, which
> are the only functions to manipulate c->lock beyond Condition_Destroy.
> Reading the thread_id simply serves as a sanity check in all of these functions.
> 
> Victor
> -- 
> Victor J. Orlikowski   | The Wall is Down, But the Threat Remains!
> ==================================================================
> v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com


Moving ahead, IIRC we are confident we can safely implement condition
variables on Win32 and Unix. What do we have for beos and os2? Are there
other platforms that will be a problem?


(For the curious, there is an excellent paper by Douglas C. Schmidt and Irfan
Pyarali at http://www.cs.wustl.edu/~schmidt/win32-cv-1.html called
_Strategies for Implementing POSIX Condition Variables on Win32_. The
paper includes multiple strategies for implementing POSIX CVs.)

-aaron


Mime
View raw message