Return-Path: 
 <dev-return-3776-apmail-apr-dev-archive=apr.apache.org@apr.apache.org>
Delivered-To: apmail-apr-dev-archive@apr.apache.org
Received: (qmail 11772 invoked by uid 500); 2 Aug 2001 18:47:01 -0000
Mailing-List: contact dev-help@apr.apache.org; run by ezmlm
Precedence: bulk
List-Post: <mailto:dev@apr.apache.org>
List-Help: <mailto:dev-help@apr.apache.org>
List-Unsubscribe: <mailto:dev-unsubscribe@apr.apache.org>
List-Subscribe: <mailto:dev-subscribe@apr.apache.org>
Delivered-To: mailing list dev@apr.apache.org
Received: (qmail 11733 invoked from network); 2 Aug 2001 18:47:00 -0000
From: "Victor J. Orlikowski" <v.j.orlikowski@gte.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-ID: <15209.40995.720313.919910@critterling.garfield.home>
Date: Thu, 2 Aug 2001 14:46:59 -0400
To: Aaron Bannert <aaron@ebuilt.com>
Cc: dev@apr.apache.org
Subject: Re: Conditionals...
In-Reply-To: <20010802100837.G643@ebuilt.com>
References: <008901c119e7$f1071ec0$8100a8c0@godzilla>
	<20010731122140.A21458@ebuilt.com>
	<15207.5106.746348.166281@critterling.garfield.home>
	<15207.12731.943499.735032@critterling.garfield.home>
	<20010802000343.D643@ebuilt.com>
	<15209.31521.952343.898121@critterling.garfield.home>
	<20010802100837.G643@ebuilt.com>
X-Mailer: VM 6.95 under Emacs 20.7.1
Reply-To: v.j.orlikowski@gte.net
X-Spam-Rating: h31.sny.collab.net 1.6.2 0/1000/N

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