New locking code - Mailing list pgsql-hackers

I was reading in my "Unix Internals:  New Frontiers" book by Vahalia
yesterday, and he was talking about multi-cpu kernels, and he was
talking about read/write locks, and he said:


---------------------------------------------------------------------------

When the last active reader releases its shared lock, it must wake up a
single waiting writer.

When a writer releases a lock, it must choose whether to wake up another
writer or the other readers, assuming both readers and writers are
waiting.  If writers are given preference, the readers could starve
indefinitely under heavy contention.  The preferred solution is to wake
up all waiting readers when releasing an exclusive lock.  If there are
no waiting readers, wake up a single waiting writer.

The scheme can lead to writer starvation.  If there is a constant stream
of readers, they will keep the resource read-locked, and the writer
will never acquire the lock.  To avoid this situation, a lockShared()
request must block if there is any waiting writer, even though the
resource is currently only read-locked.  Such a solution, under heavy
contention, will alternate access between individual writer and batches
of readers.


---------------------------------------------------------------------------

The attached patch will do something similar to what he is suggesting.
My change is to keep a single waiting writer at the front of the queue,
even if the current lock holder is a writer.  Any readers arriving
during the current lock holder, or when the new writer gets the lock
will be bunched together and be given the shared lock after the writer
releases the lock.  It just doesn't seem fair for the readers to jump in
front of a single waiting writer.  If multiple writers are waiting, then
they will be behind the readers, except in cases where a late-arriving
reader can't share the readlock, and sits behind the first writer, so in
that case it would be alternating.

What do people think of this patch?  Is his way better, to always put
the readers at the front if the current lock holder is a writer?

The patch basically reverses the queue order, putting the readers before
the writers, except that now, a single writer can sit at the front of
the queue.  This structure also makes it easy for us to check to see if
we should allow a new reader to share a readlock.  We can quickly check
the front of the queue to see if there is a writer waiting.

---------------------------------------------------------------------------


*** ./backend/storage/lmgr/proc.c.orig    Wed Feb 18 13:48:11 1998
--- ./backend/storage/lmgr/proc.c    Wed Feb 18 14:15:09 1998
***************
*** 451,465 ****
            int prio,
            LOCK *lock)
  {
!     int            i;
      PROC       *proc;
      struct itimerval timeval,
                  dummy;

      proc = (PROC *) MAKE_PTR(waitQueue->links.prev);
!     for (i = 0; i < waitQueue->size; i++)
      {
!         if (proc->prio >= prio)
              proc = (PROC *) MAKE_PTR(proc->links.prev);
          else
              break;
--- 451,490 ----
            int prio,
            LOCK *lock)
  {
!     int            i = 0;
      PROC       *proc;
      struct itimerval timeval,
                  dummy;

      proc = (PROC *) MAKE_PTR(waitQueue->links.prev);
!     /*
!      *    If the first entry in the waitQueue has a greater priority than
!      *    we have, we must be a reader, and he must be a writer, and we
!      *    must be here because the current holder is a writer or a
!      *    reader but we don't share shared locks if a writer is waiting.
!      *    We put ourselves after the first writer.  What this hopefully
!      *    does it to bunch up all the waiting readers first, unless there
!      *    is a waiting writer, in which case all the waiting readers are
!      *    after the first waiting writer.  This way, we alternate between
!      *    writers and bunches of readers and don't starve anyone. So the
!      *    queue becomes:
!      *
!      *    [optional writer][reader][reader][reader][writer][writer][writer]
!      *
!      *    In a full queue, we would have a writer holding a lock, then another
!      *    writer gets the lock, then a bunch of readers, it repeats.
!      *    This may seem strange, but because new readers share the lock even
!      *    if older writers are waiting, this seems only fair. - bjm
!      */
!     if (i < waitQueue->size)
!         if (proc->prio > prio)
!         {
!             proc = (PROC *) MAKE_PTR(proc->links.prev);
!             i++;
!         }
!     for (; i < waitQueue->size; i++)
      {
!         if (proc->prio <= prio)
              proc = (PROC *) MAKE_PTR(proc->links.prev);
          else
              break;
***************
*** 596,603 ****

          /*
           * ProcWakeup removes proc from the lock waiting process queue and
!          * returns the next proc in chain.    If a writer just dropped its
!          * lock and there are several waiting readers, wake them all up.
           */
          proc = ProcWakeup(proc, NO_ERROR);

--- 621,627 ----

          /*
           * ProcWakeup removes proc from the lock waiting process queue and
!          * returns the next proc in chain.
           */
          proc = ProcWakeup(proc, NO_ERROR);


--
Bruce Momjian
maillist@candle.pha.pa.us