Conditionals...

[David Reid <dr...@jetnet.co.uk>]

Folks,

The httpd guys have started adding the code that uses pthread conditionals,
but we did talk about possibly adding it to APR.  So, what do we think?

I guess what we're talking about is

apr_cond_t

apr_cond_create

apr_cond_signal
apr_cond_broadcast
apr_cond_wait

apr_cond_destroy

I know it'll be a PITA to write the implementation on beos, but it *should*
be possible.  Given that the code in httpd currently is unix specific
anyway, should we add a cond directory and simply return APR_ENOTIMPL for
the other platforms while work is started for them?  ISTR that no clear
answer was given as to the possibility of having conditionals on OS/2,
Windows and Netware...

david

Re: Conditionals...

[Jeff Trawick <tr...@attglobal.net>]

"Roy T. Fielding" <fi...@ebuilt.com> writes:

> > > All variables are an approximation -- cosmic rays can change the value as
> > > well, with only a slightly smaller probability than mid-increment time
> > > slices in a non-test system.
> > 
> > hmmm... I've seen many fixes needed for several instruction sequences
> > which did not handle being interrupted (i.e. broken serialization);
> > unclear how many of the unrepeatable bugs are due to cosmic rays...
> > as a programmer I wouldn't want to assume that any of them
> > are... certainly the customers I'm familiar with would not accept that
> > as an answer :)
> 
> Due to mid-increment time slices?  All of the race conditions I have seen
> in practice have been due to I/O operations (not register loads).

mid-increment?  I don't recall any (in the implementation language
used on the product, a special keyword on a variable declaration
caused compare-and-swap logic to be generated; very hard to screw up)

other several instruction sequences?  yep (one cause was that even
when the proper instruction sequence was known by the programmer the
compiler would sometimes play with the specified asm :( )

-- 
Jeff Trawick | trawick@attglobal.net | PGP public key at web site:
       http://www.geocities.com/SiliconValley/Park/9289/
             Born in Roswell... married an alien...

Re: Conditionals...

["Roy T. Fielding" <fi...@ebuilt.com>]

> > All variables are an approximation -- cosmic rays can change the value as
> > well, with only a slightly smaller probability than mid-increment time
> > slices in a non-test system.
> 
> hmmm... I've seen many fixes needed for several instruction sequences
> which did not handle being interrupted (i.e. broken serialization);
> unclear how many of the unrepeatable bugs are due to cosmic rays...
> as a programmer I wouldn't want to assume that any of them
> are... certainly the customers I'm familiar with would not accept that
> as an answer :)

Due to mid-increment time slices?  All of the race conditions I have seen
in practice have been due to I/O operations (not register loads).

In any case, I have no doubt that such a condition can occur.   I am simply
saying that I don't care, and neither will the customer if I have written
the code correctly.  If I did care, *then* I would use locks.

....Roy

Re: Conditionals...

[Jeff Trawick <tr...@attglobal.net>]

"Roy T. Fielding" <fi...@ebuilt.com> writes:

> > >                                         Likewise, even a mid-update context
> > > switch doesn't matter for a variable that is only incremented/decremented.
> > 
> > only if the variable is used for an approximation :)
> 
> I said only one writer.

Well, you certainly know how to interpret what you write and I
certainly didn't :)

> All variables are an approximation -- cosmic rays can change the value as
> well, with only a slightly smaller probability than mid-increment time
> slices in a non-test system.

hmmm... I've seen many fixes needed for several instruction sequences
which did not handle being interrupted (i.e. broken serialization);
unclear how many of the unrepeatable bugs are due to cosmic rays...
as a programmer I wouldn't want to assume that any of them
are... certainly the customers I'm familiar with would not accept that
as an answer :)

-- 
Jeff Trawick | trawick@attglobal.net | PGP public key at web site:
       http://www.geocities.com/SiliconValley/Park/9289/
             Born in Roswell... married an alien...

Re: Conditionals...

["Roy T. Fielding" <fi...@ebuilt.com>]

> >                                         Likewise, even a mid-update context
> > switch doesn't matter for a variable that is only incremented/decremented.
> 
> only if the variable is used for an approximation :)

I said only one writer.

All variables are an approximation -- cosmic rays can change the value as
well, with only a slightly smaller probability than mid-increment time
slices in a non-test system.  Unless there is a bug in the code, reading
a counter in the scoreboard never needs a lock.

....Roy

Re: Conditionals...

[Jeff Trawick <tr...@attglobal.net>]

"Roy T. Fielding" <fi...@ebuilt.com> writes:

>                                         Likewise, even a mid-update context
> switch doesn't matter for a variable that is only incremented/decremented.

only if the variable is used for an approximation :)

      x = 0

                 thread1                            thread2

                 load x into reg A                  load x into reg A
                 TIMESLICE                          increment reg A
                 (sleeping)                         store reg A at x
                 DISPATCH
                 increment reg A
                 store reg A at x

      x has been incremented twice and now has value 1

compare-and-swap can be used for this.
-- 
Jeff Trawick | trawick@attglobal.net | PGP public key at web site:
       http://www.geocities.com/SiliconValley/Park/9289/
             Born in Roswell... married an alien...

Re: Conditionals...

["Roy T. Fielding" <fi...@ebuilt.com>]

> 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).

Not all shared memory is created equal.  Simple variables that only have
one writer at a time by nature do not require additional locking.
That is how the old scoreboard worked.  Likewise, even a mid-update context
switch doesn't matter for a variable that is only incremented/decremented.

....Roy

Re: Conditionals...

["Victor J. Orlikowski" <v....@gte.net>]

Urgh...
Variable reuse, Victor, variable reuse.
<Victor hits head on desk, noting that he was obviously on vacation.>

> int Acquire_Condition_Lock(struct Condition *c) {
>       int thrid = thread_id_of(current_thread);
>       if (c->thread_id == thrid) exit(1);  /* Deadlock */
>       acquire(*(c->lock));
>       acquire(c->condlock);
>       c->thread_id = thread_id_of(current_thread);
>       release(c->condlock);
>       return 0;
> }
> 

Make that:

int Acquire_Condition_Lock(struct Condition *c) {
      int thrid = thread_id_of(current_thread);
      if (c->thread_id == thrid) exit(1);  /* Deadlock */
      acquire(*(c->lock));
      acquire(c->condlock);
      c->thread_id = thrid;
      release(c->condlock);
      return 0;
}

Victor
-- 
Victor J. Orlikowski   | The Wall is Down, But the Threat Remains!
==================================================================
v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com

Re: Conditionals...

["Victor J. Orlikowski" <v....@gte.net>]

On Friday, 3 Aug 2001, at 15:23:22,
Victor J. Orlikowski wrote:
> How about:
> 
> int Acquire_Condition_Lock(struct Condition *c) {
>       acquire(c->condlock);
>       acquire(*(c->lock));
>       c->thread_id = thread_id_of(current_thread);
>       release(c->condlock);
>       return 0;
> }
> 
> Hence, we simply block trying to acquire the condlock.
> Once we have the condlock, all is well, no?
> 

Hum, answer my own question. No.
While driving down for vacation, I thought of all the possible
deadlocks.
However, Acquire_Condition_Lock is the only one casuing them.

The following implmentation should cure it all.

int Acquire_Condition_Lock(struct Condition *c) {
      int thrid = thread_id_of(current_thread);
      if (c->thread_id == thrid) exit(1);  /* Deadlock */
      acquire(*(c->lock));
      acquire(c->condlock);
      c->thread_id = thread_id_of(current_thread);
      release(c->condlock);
      return 0;
}

As long as we always only maintain the state of c->thread_id while
holding c->lock, all will be fine. Furthermore, reads from
c->thread_id should be safe, as all write thereto should be serialized
in the implementation that includes the above Acquire_Condition_Lock.

Victor
-- 
Victor J. Orlikowski   | The Wall is Down, But the Threat Remains!
==================================================================
v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com

Re: Conditionals...

["Victor J. Orlikowski" <v....@gte.net>]

 > 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).
 > 
Since this is a problem, we can simply protect the test with the
condlock. Not a big change.

 > > 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.

All right. This is a valid problem.

How about:

int Acquire_Condition_Lock(struct Condition *c) {
      acquire(c->condlock);
      acquire(*(c->lock));
      c->thread_id = thread_id_of(current_thread);
      release(c->condlock);
      return 0;
}

Hence, we simply block trying to acquire the condlock.
Once we have the condlock, all is well, no?

 > 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.)
 > 

I'll be sure to look at these.


Victor
-- 
Victor J. Orlikowski   | The Wall is Down, But the Threat Remains!
==================================================================
v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com

Re: Conditionals...

[Aaron Bannert <aa...@ebuilt.com>]

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

Re: Conditionals...

["Victor J. Orlikowski" <v....@gte.net>]

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.

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;
}

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

Re: Conditionals...

[Aaron Bannert <aa...@ebuilt.com>]

On Thu, Aug 02, 2001 at 12:09:05PM -0400, Victor J. Orlikowski wrote:
> Aaron Bannert writes:
>  > On Tue, Jul 31, 2001 at 06:31:23PM -0400, Victor J. Orlikowski wrote:
>  > > Rather, let's be more clear.
>  > > 
> <snip>
>  > 
> My fault. That code is more than slightly wrong, now that I look
> at it better. Let's examine the following pseudocode, which closely
> follows some of my undergraduate OS work at the university.
> I will not be doing any checking for null values, etc.
> 
> struct Condition {
>     mutex *lock; /* mutex associated with condition */
>     int thread_id; /* Current holder of the lock */
>     mutex condlock; 
> };
> 
> void Wait(struct Condition *c) {
>      acquire(c->condlock);
>      if (c->thread_id != thread_id_of(current_thread)) {
>          release(c->condlock);
>          exit(-1); /* Only the holder of the lock may call wait */ 
>      }
>      l->thread_id = -1; /* or whatever invalid thread value */
>      release(c->condlock);
>      release(*(c->lock));
>      wait_on_signal_or_broadcast(); /* hint, use a semaphore */
>      acquire(*(c->lock));
>      acquire(c->condlock);
>      c->thread_id = thread_id_of(current_thread);
>      release(c->condlock);
> }
> 
> void Signal(struct Condition *c) {
>      if (c->thread_id != thread_id_of(current_thread))
>          exit(-1); /* Only the holder of the lock may call signal */
>      wake_one_sleeper();
> }
> 
> void Broadcast(struct Condition *c) {
>      if (c->thread_id != thread_id_of(current_thread))
>          exit(-1); /* Only the holder of the lock may call broadcast */
>      wake_all_sleepers();
> }
> 
>  > Not really, but maybe I'm just being dense. Assuming "mutex1" is the
>  > mutex associated with the condition (and therefore has the same scope),
>  > what is the scope of "mutex2" and "held"?
>  > 
> The scope of mutex2 is not associated with the condition; it is
> intended to provided the needed mutual exclusion for mutex1 and the
> state variable held. However, you can ignore this, since that code was
> slightly wrong. 
> 
>  > And more importantly, if you're using sleep(), then aren't you just doing
>  > a primitive poll/wait loop, and therefore defeating the whole purpose
>  > of event-based scheduling using CVs?
> Sleep() was not intended to be sleep; I was writing pseudocode. 
> Sleep() was a place holder for whatever function you are calling
> that is used to block the current thread until is is awakened via a
> signal() or broadcast() operation. Hopefully I'm more clear in the
> above example.

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()?

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.

-aaron

Re: Conditionals...

["Victor J. Orlikowski" <v....@gte.net>]

 > void Wait(struct Condition *c) {
        if (c->thread_id != thread_id_of(current_thread))
            exit(-1); /* Only the holder of the lock may call wait */
 >      acquire(c->condlock);
 >      l->thread_id = -1; /* or whatever invalid thread value */
 >      release(c->condlock);
 >      release(*(c->lock));
 >      wait_on_signal_or_broadcast(); /* hint, use a semaphore */
 >      acquire(*(c->lock));
 >      acquire(c->condlock);
 >      c->thread_id = thread_id_of(current_thread);
 >      release(c->condlock);
 > }

And the above would be slightly better.

Victor
-- 
Victor J. Orlikowski   | The Wall is Down, But the Threat Remains!
==================================================================
v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com

Re: Conditionals...

["Victor J. Orlikowski" <v....@gte.net>]

Aaron Bannert writes:
 > On Tue, Jul 31, 2001 at 06:31:23PM -0400, Victor J. Orlikowski wrote:
 > > Rather, let's be more clear.
 > > 
<snip>
 > 
My fault. That code is more than slightly wrong, now that I look
at it better. Let's examine the following pseudocode, which closely
follows some of my undergraduate OS work at the university.
I will not be doing any checking for null values, etc.

struct Condition {
    mutex *lock; /* mutex associated with condition */
    int thread_id; /* Current holder of the lock */
    mutex condlock; 
};

void Wait(struct Condition *c) {
     acquire(c->condlock);
     if (c->thread_id != thread_id_of(current_thread)) {
         release(c->condlock);
         exit(-1); /* Only the holder of the lock may call wait */ 
     }
     l->thread_id = -1; /* or whatever invalid thread value */
     release(c->condlock);
     release(*(c->lock));
     wait_on_signal_or_broadcast(); /* hint, use a semaphore */
     acquire(*(c->lock));
     acquire(c->condlock);
     c->thread_id = thread_id_of(current_thread);
     release(c->condlock);
}

void Signal(struct Condition *c) {
     if (c->thread_id != thread_id_of(current_thread))
         exit(-1); /* Only the holder of the lock may call signal */
     wake_one_sleeper();
}

void Broadcast(struct Condition *c) {
     if (c->thread_id != thread_id_of(current_thread))
         exit(-1); /* Only the holder of the lock may call broadcast */
     wake_all_sleepers();
}

 > Not really, but maybe I'm just being dense. Assuming "mutex1" is the
 > mutex associated with the condition (and therefore has the same scope),
 > what is the scope of "mutex2" and "held"?
 > 
The scope of mutex2 is not associated with the condition; it is
intended to provided the needed mutual exclusion for mutex1 and the
state variable held. However, you can ignore this, since that code was
slightly wrong. 

 > And more importantly, if you're using sleep(), then aren't you just doing
 > a primitive poll/wait loop, and therefore defeating the whole purpose
 > of event-based scheduling using CVs?
Sleep() was not intended to be sleep; I was writing pseudocode. 
Sleep() was a place holder for whatever function you are calling
that is used to block the current thread until is is awakened via a
signal() or broadcast() operation. Hopefully I'm more clear in the
above example.

Does the new code fit better with what you expect?

Victor
-- 
Victor J. Orlikowski   | The Wall is Down, But the Threat Remains!
==================================================================
v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com

Re: Conditionals...

[Aaron Bannert <aa...@ebuilt.com>]

On Tue, Jul 31, 2001 at 06:31:23PM -0400, Victor J. Orlikowski wrote:
> Rather, let's be more clear.
> 
> bool held=false;
> 
>      acquire(mutex2);
>      release(mutex1);
>      held=false;
>      release(mutex2);
> nap: sleep();
>      acquire(mutex2);
>      if(held) goto nap;
>      acquire(mutex1);
>      held=true;
>      release(mutex2);
> 
> That explain it somewhat better? ;)

Not really, but maybe I'm just being dense. Assuming "mutex1" is the
mutex associated with the condition (and therefore has the same scope),
what is the scope of "mutex2" and "held"?

And more importantly, if you're using sleep(), then aren't you just doing
a primitive poll/wait loop, and therefore defeating the whole purpose
of event-based scheduling using CVs?

-aaron

Re: Conditionals...

["Victor J. Orlikowski" <v....@gte.net>]

Rather, let's be more clear.

bool held=false;

     acquire(mutex2);
     release(mutex1);
     held=false;
     release(mutex2);
nap: sleep();
     acquire(mutex2);
     if(held) goto nap;
     acquire(mutex1);
     held=true;
     release(mutex2);

That explain it somewhat better? ;)

Victor
-- 
Victor J. Orlikowski   | The Wall is Down, But the Threat Remains!
==================================================================
v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com

Re: Conditionals...

["Victor J. Orlikowski" <v....@gte.net>]

 > I've been looking into this over the last few days and although I'm
 > totally in favor of adding condition variables to APR, I'm not yet
 > convinced that we can properly implement them on non-POSIX platforms
 > without some level of kernel support. There is one specific place where
 > I'm seeing a problem:
 > 
 > - cond_wait() takes a locked mutex that is associated with the cond.
 > - it will unlock that mutex and go to sleep
 > - when it awakens it must immediately reacquire that mutex (awaken() and
 >   acquire() must be a single atomic operation)
 > - finally, cond_wait() returns.
 > 
 > Does anyone know of a way around this without some sort of kernel support
 > to make those two operations atomic? This seems like a serious potential
 > for race/deadlocks.

*Sigh.*

As I told David (off-list),
If you have mutexes or semaphores, you can implement condition
variables.
Period.

Hint: Use another mutex, right after you go to sleep.

i.e.

release(mutex1);
sleep();
acquire(mutex2);
acquire(mutex1);
release(mutex2);

Victor
-- 
Victor J. Orlikowski   | The Wall is Down, But the Threat Remains!
==================================================================
v.j.orlikowski@gte.net | orlikowski@apache.org | vjo@us.ibm.com

Re: Conditionals...

["William A. Rowe, Jr." <wr...@rowe-clan.net>]

----- Original Message ----- 
From: "William A. Rowe, Jr." <wr...@rowe-clan.net>
To: "Aaron Bannert" <aa...@ebuilt.com>; <de...@apr.apache.org>
Sent: Tuesday, July 31, 2001 3:50 PM
Subject: Re: Conditionals...


> From: "Aaron Bannert" <aa...@ebuilt.com>
> Sent: Tuesday, July 31, 2001 2:21 PM
> 
> 
> > I've been looking into this over the last few days and although I'm
> > totally in favor of adding condition variables to APR, I'm not yet
> > convinced that we can properly implement them on non-POSIX platforms
> > without some level of kernel support. There is one specific place where
> > I'm seeing a problem:
> > 
> > - cond_wait() takes a locked mutex that is associated with the cond.
> > - it will unlock that mutex and go to sleep
> > - when it awakens it must immediately reacquire that mutex (awaken() and
> >   acquire() must be a single atomic operation)
> > - finally, cond_wait() returns.
> > 
> > Does anyone know of a way around this without some sort of kernel support
> > to make those two operations atomic? This seems like a serious potential
> > for race/deadlocks.
> 
> Oh duh, this is a breeze on win32 [except that cond's themselves must be implemented.]
> 
> http:....

wrong href...

http://msdn.microsoft.com/library/en-us/dllproc/hh/winbase/synchro_5h2s.asp?frame=true

Only solves NT, but if we use some cheap trick on 9x to emulate, I don't much care.

Bill

Re: Conditionals...

["William A. Rowe, Jr." <wr...@rowe-clan.net>]

From: "Aaron Bannert" <aa...@ebuilt.com>
Sent: Tuesday, July 31, 2001 2:21 PM


> I've been looking into this over the last few days and although I'm
> totally in favor of adding condition variables to APR, I'm not yet
> convinced that we can properly implement them on non-POSIX platforms
> without some level of kernel support. There is one specific place where
> I'm seeing a problem:
> 
> - cond_wait() takes a locked mutex that is associated with the cond.
> - it will unlock that mutex and go to sleep
> - when it awakens it must immediately reacquire that mutex (awaken() and
>   acquire() must be a single atomic operation)
> - finally, cond_wait() returns.
> 
> Does anyone know of a way around this without some sort of kernel support
> to make those two operations atomic? This seems like a serious potential
> for race/deadlocks.

Oh duh, this is a breeze on win32 [except that cond's themselves must be implemented.]

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/hh/winbase/synchro_5h2s.asp

Re: Conditionals...

["William A. Rowe, Jr." <wr...@rowe-clan.net>]

My response below... Brad, what does Netware look like on this?

From: "Aaron Bannert" <aa...@ebuilt.com>
Sent: Tuesday, July 31, 2001 2:21 PM


> I've been looking into this over the last few days and although I'm
> totally in favor of adding condition variables to APR, I'm not yet
> convinced that we can properly implement them on non-POSIX platforms
> without some level of kernel support. There is one specific place where
> I'm seeing a problem:
> 
> - cond_wait() takes a locked mutex that is associated with the cond.
> - it will unlock that mutex and go to sleep
> - when it awakens it must immediately reacquire that mutex (awaken() and
>   acquire() must be a single atomic operation)
> - finally, cond_wait() returns.
> 
> Does anyone know of a way around this without some sort of kernel support
> to make those two operations atomic? This seems like a serious potential
> for race/deadlocks.

First, for Win32 syncronization objects, see this chapter

http://msdn.microsoft.com/library/en-us/dllproc/hh/winbase/synchro_4q3y.asp?frame=true

Second, it _has_ been done on Win32, as redhat's win32 pthreads (lgpl) library shows.

What exactly are we trying to accomplish?  For this to be truly useful, it has to
be abstracted to our non-pthread unix models as well :(

If we are just concerned with atomic updates, then we could implement something quite
a bit simpler...

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/hh/winbase/synchro_925v.asp

...but if we are convinced we want to sleep on the variable, then perhaps we can use
the APC Queue to schedule the wakeable async test.

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/hh/winbase/synchro_925v.asp

I guess I need a pointer to what it is we care to accomplish.  It can be done, but
to what end?

Bill




> On Tue, Jul 31, 2001 at 06:39:57PM +0100, David Reid wrote:
> > Folks,
> > 
> > The httpd guys have started adding the code that uses pthread conditionals,
> > but we did talk about possibly adding it to APR.  So, what do we think?
> > 
> > I guess what we're talking about is
> > 
> > apr_cond_t
> > 
> > apr_cond_create
> > 
> > apr_cond_signal
> > apr_cond_broadcast
> > apr_cond_wait
> > 
> > apr_cond_destroy
> > 
> > I know it'll be a PITA to write the implementation on beos, but it *should*
> > be possible.  Given that the code in httpd currently is unix specific
> > anyway, should we add a cond directory and simply return APR_ENOTIMPL for
> > the other platforms while work is started for them?  ISTR that no clear
> > answer was given as to the possibility of having conditionals on OS/2,
> > Windows and Netware...
> > 
> > david
> 
> 

Re: Conditionals...

[Aaron Bannert <aa...@ebuilt.com>]

I've been looking into this over the last few days and although I'm
totally in favor of adding condition variables to APR, I'm not yet
convinced that we can properly implement them on non-POSIX platforms
without some level of kernel support. There is one specific place where
I'm seeing a problem:

- cond_wait() takes a locked mutex that is associated with the cond.
- it will unlock that mutex and go to sleep
- when it awakens it must immediately reacquire that mutex (awaken() and
  acquire() must be a single atomic operation)
- finally, cond_wait() returns.

Does anyone know of a way around this without some sort of kernel support
to make those two operations atomic? This seems like a serious potential
for race/deadlocks.

-aaron


On Tue, Jul 31, 2001 at 06:39:57PM +0100, David Reid wrote:
> Folks,
> 
> The httpd guys have started adding the code that uses pthread conditionals,
> but we did talk about possibly adding it to APR.  So, what do we think?
> 
> I guess what we're talking about is
> 
> apr_cond_t
> 
> apr_cond_create
> 
> apr_cond_signal
> apr_cond_broadcast
> apr_cond_wait
> 
> apr_cond_destroy
> 
> I know it'll be a PITA to write the implementation on beos, but it *should*
> be possible.  Given that the code in httpd currently is unix specific
> anyway, should we add a cond directory and simply return APR_ENOTIMPL for
> the other platforms while work is started for them?  ISTR that no clear
> answer was given as to the possibility of having conditionals on OS/2,
> Windows and Netware...
> 
> david