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

Re: [PATCH] New condition variable design: OpenOffice works



On Mon, Nov 04, 2002 at 01:55:48PM +0100, Alexander Terekhov wrote:
> phil-list redhat com schrieb am 03.11.02 07:34:05:
> > On Sat, 2 Nov 2002, Alexander Terekhov wrote:
> > 
> > > P.S. Oh, BTW, I'm just curious: who's the author of NPTL's
> > > DESIGN-rwlock.txt?
> > 
> > i wrote the DESIGN-*.txt pseudocode, with fixes & suggestions from Ulrich.  
> > The actual implementation in NPTL is Ulrich's.
> > 
> > 	Ingo
> 
> It seems to me that the way how you handle futex value transitions
> [0<->1] and waiting in the current rwlock is well, ``Not Good.''
> 
>     futex_wait(&rwlock->readers_wakeup, 0)
> 
> Unless I'm just missing and/or misunderstanding something, this 
> might easily degrade to busy-waiting/spinning -- the futex values 
> aren't guaranteed to be zero, as far as I can see.

I think that you are right: if the rwlock gets write-locked after
readers are woken up, and there is more than one reader, a busy wait
happens.


Here is an alternative design that should solve the problem.

The basic idea here is that we keep counts of threads blocking reads
and writes and of ones queued on futexes on that variable: this has
the side effect of making the design intuitive.

This design also adds a "first come first served" algorithm where an
unlock awakes everyone and waiting threads never block opposite-mode
waiters (this isn't very useful, it's included mostly for
completeness).

IMHO this fixes all possible problems.

The Linux/x86 assembly implementation is left as an exercise for the
reader.


Reader Writer Locks pseudocode
==============================

	pthread_rwlock_rdlock(pthread_rwlock_t *rwlock);
	pthread_rwlock_unlock(pthread_rwlock_t *rwlock);
	pthread_rwlock_wrlock(pthread_rwlock_t *rwlock);

struct pthread_rwlock_t {

   unsigned int lock:
         - internal mutex

   unsigned int algorithm;
         - locking mode: READERS_RULE recursive, readers preferred
                         WRITERS_RULE nonrecursive, writers preferred
                         FIRST_COME_FIRST_SERVED obvious


   unsigned int readers;
         - number of read-only references various threads have

   pthread_t writer;
         - descriptor of the writer or 0

   unsigned int read_blockers;
         - number of threads blocking readers

   unsigned int write_blockers;
         - number of threads blocking writers

   unsigned int nr_readers_queued;
         - number of readers queued up.

   unsigned int nr_writers_queued;
         - number of writers queued up.
}

pthread_rwlock_rdlock(pthread_rwlock_t *rwlock)
{
  lll_lock(rwlock->lock);
  if(rwlock->algorithm == READERS_RULE)
    ++rwlock->write_blockers;

  for (;;) {
    read_blockers = rwlock->read_blockers;
    if (!read_blockers)
        break;

    ++rwlock->nr_readers_queued;
    lll_unlock(rwlock->lock);
    futex_wait(&rwlock->read_blockers, read_blockers)
    lll_lock(rwlock->lock);
    --rwlock->nr_readers_queued;
  }

  if(rwlock->algorithm != READERS_RULE)
    ++rwlock->write_blockers;
  lll_unlock(rwlock->lock);
}

pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock)
{
  int result = EBUSY;
  lll_lock(rwlock->lock);
  if (!rwlock->read_blockers)
  {
    ++rwlock->write_blockers;
    result = 0;
  }
  lll_unlock(rwlock->lock);
  return result;
}

rwlock_query(pthread_rwlock_t *rwlock)
{
  lll_lock(rwlock->lock);
  writers = rwlock->writer ? 1 : 0;
  readers = writers ? 0 : rwlock->write_blockers;
  lll_unlock(rwlock->lock);
}

pthread_rwlock_wrlock(pthread_rwlock_t *rwlock)
{
  lll_lock(rwlock->lock);
  if(rwlock->algorithm == WRITERS_RULE)
    ++rwlock->read_blockers;

  for (;;) {
    write_blockers = rwlock->write_blockers;
    if (!write_blockers)
        break;

    ++rwlock->nr_writers_queued;
    lll_unlock(rwlock->lock);
    futex_wait(&rwlock->write_blockers, write_blockers)
    lll_lock(rwlock->lock);
    --rwlock->nr_writers_queued;
  }

  if(rwlock->algorithm != WRITERS_RULE)
    ++rwlock->read_blockers;

  rwlock->writer = pthread_self();
  ++rwlock->write_blockers;
  lll_unlock(rwlock->lock);
}

pthread_rwlock_unlock(pthread_rwlock_t *rwlock)
{
  lll_lock(rwlock->lock);

  if (rwlock->writer)
  {
    rwlock->writer = 0;
    --rwlock->read_blockers;
  }

  --rwlock->write_blockers;

  wake_writers = !rwlock->write_blockers && rwlock->nr_writers_queued;
  wake_readers = !rwlock->read_blockers && rwlock->nr_readers_queued;

  /* if rwlock->algorithm == FIRST_COME_FIRST_SERVED we awake everyone */
  if(wake_writers && (!wake_readers || (rwlock->algorithm == WRITERS_RULE))
    futex_wake(&rwlock->write_blockers, 1);
  if(wake_readers && (!wake_writers || (rwlock->algorithm == READERS_RULE))
    futex_wake(&rwlock->read_blockers, MAX_INT);

  lll_unlock(rwlock->lock);
}

Attachment: pgp00040.pgp
Description: PGP signature


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