[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]

Re:DESIGN-condvar



phil-list redhat com schrieb am 11.10.02 18:56:29:
> phil-list redhat com schrieb am 11.10.02 10:23:12:
> > On Wed, 9 Oct 2002, Alexander Terekhov wrote:
> > 
> > > Q2) POSIX does require that deleting a condition variable 
> > >     after final signaling should be OK/safe(*). Are you 
> > >     sure that this would actually work under the current 
> > >     DESIGN-condvar?
> > 
> > i think you are right, cond_signal() + free() is unsafe.
> > 
> > does broadcast require the same semantics, ...
> 
> I think that both signal() and broadcast() [actually the 
> main problem is in *wait(), AFAICS] functions require the 
> same semantics with respect to ``It shall be safe to 
> destroy an initialized condition variable upon which no 
> threads are currently blocked.'' Unless I'm just missing
> something.
> 
> phil-list redhat com schrieb am 11.10.02 10:09:08:
> > On Wed, 9 Oct 2002, Alexander Terekhov wrote:
> > 
> > > Q1) Are you sure that given the current CV design, it's 
> > >     really guranteed that a player just can't consume his 
> > >     own signal as spurious wakeup... resulting in a sort 
> > >     of deadlock (until the main/initial thread would come
> > >     it and resolve it declaring game over)?
> > 
> > do you mean: "a cond_wait()-ing thread should not be woken up by a
> > cond_signal() it did previously" ?
> > 
> > ( Please describe your question(s) in simpler terms, not through some
> > complex example. Providing the simplest possible description for a problem
> > is just as important as implementing the simplest possible code for a
> > given specification. Too complex examples only cause us to 1) not be able
> > to read your description immediately or 2) even to skip it altogether.  
> > Having simple examples and even suggestions for fixes will save tons of
> > time on our side, and tons of typing on your side. Thanks! )
> 
> Well, I'm sorry, but the best that I can do at the moment ....


< I apologize in advance for something obviously erroneous/silly,
  but after 2x~3.* hours thinking about it, here's what I've got. >

What about the following futex-based-CV pseudocode?
===================================================

       pthread_cond_{timed}wait();
       pthread_cond_signal();
       pthread_cond_broadcast();
       pthread_cond_destroy();

// Upper bound value for signal/broadcast counting
#define MAX 2 // 0,1,2 (or more, but not less ;-) )

// Just to release ALL waiters
#define ALL UINT_MAX

// EndOfCycle value for signalling event counting 
#define EOC(cycle_bit) ((cycle_bit) ? 0 : MAX)

struct pthread_cond_t {

   unsigned int lock:

         internal mutex.

   unsigned int futex:

         internal futex.

   unsigned int cycle_bit:

         0/1 bit for cycling (more macros [VAL/INC/DEC] 
         will be needed to have it 'embedded' into the
         futex itself; probably):

              cycle 0: [++] 0,1,...MAX: cycle change/count=MAX-1/WAKE ALL.
              cycle 1: [--] MAX,...1,0: cycle change/count=0x001/WAKE ALL.

              'count' is futex value ('embedded' cycle_bit aside).

              cycle change/WAKE ALL is done by the *last* sleeper 
              on the *current* cycle (not counting EOC-sleepers).

              pthread_cond_destroy() *enforces* End-Of-Cycle just 
              to ensure *safe* destruction - synchronization with 
              respect to *exiting* sleepers (if any).

   unsigned int nr_wakers:

         number of threads signalled to be woken up.

   unsigned int nr_sleepers[2]:

         number of threads waiting on the cv ["when"]:

              [0] - EOC(cv->cycle_bit) != futex value/count.
              [1] - EOC(cv->cycle_bit) == futex value/count.
}

cond_wait_timeout(cv, mutex, timeout)
{
  unsigned int futex;

  lock(cv->lock);
  mutex_unlock(mutex); // here or below

  ++cv->nr_speepers[ EOC(cv->cycle_bit) == (futex = cv->futex) ];

  unlock(cv->lock); 
  // mutex_unlock(mutex);

  FUTEX WAIT (cv->futex, futex, timeout);

  lock(cv->lock);

  if ( futex != cv->futex ) {

    --cv->nr_sleepers[0];

    if ( 0 !=   cv->nr_wakers &&
         0 == --cv->nr_wakers && 
         EOC(cv->cycle_bit) == cv->futex ) {

      cv->futex = ( cv->cycle_bit ^= 1 ) ? MAX-1 : 1;
      cv->nr_sleepers[0] = cv->nr_wakers = cv->nr_sleepers[1];
      cv->nr_sleepers[1] = 0;

      FUTEX WAKE (cv->futex, ALL);

    }

  }
  else
     --cv->nr_speepers[ EOC(cv->cycle_bit) == futex ];

  unlock(cv->lock);
  mutex_lock(mutex);

}

cond_signal(cv)
{
  unsigned int do_wakeup;

  lock(cv->lock);
 
  if ( do_wakeup = (cv->nr_sleepers[0] > cv->nr_wakers) ) {

    if ( cv->cycle_bit ? 
             0 == --cv->futex :
           MAX == ++cv->futex ) {
      do_wakeup = ALL;
      cv->nr_wakers = cv->nr_sleepers[0];
    }
    else
      ++cv->nr_wakers;
  
  }

  unlock(cv->lock);

  if (do_wakeup)
    FUTEX WAKE (cv->futex, do_wakeup);
}

cond_broadcast(cv)
{
  bool do_wakeup;

  lock(cv->lock);
 
  if ( do_wakeup = (cv->nr_sleepers[0] > cv->nr_wakers) ) {

    cv->nr_wakers = cv->nr_sleepers[0];

    if ( cv->cycle_bit ) 
      --cv->futex;
    else
      ++cv->futex;

  }

  unlock(cv->lock);

  if (do_wakeup)
    FUTEX WAKE (cv->futex, ALL);
}

cond_destroy(cv)
{
  unsigned int futex;

  lock(cv->lock);

  // optional EBUSY checking
  if ( cv->nr_sleepers[0] > cv->nr_wakers ) {
    unlock(cv->lock);
    return EBUSY;
  }
    
  while ( cv->nr_sleepers[0] ) {

    if ( EOC(cv->cycle_bit) != cv->futex )
      cv->futex = EOC(cv->cycle_bit);

    futex = cv->futex;
                     
    unlock(cv->lock);

    FUTEX WAIT (cv->futex, futex);

    lock(cv->lock);

  }

  // unlock(cv->lock);
  // now it's safe to reclaim
}

it might generate spurious wakeups in >>both<< signal() 
*and* broadcast() case, but those are allowed by POSIX.

regards,
alexander.


________________________________________________________________
Keine verlorenen Lotto-Quittungen, keine vergessenen Gewinne mehr! 
Beim WEB.DE Lottoservice: http://tippen2.web.de/?x=13






[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]