Re: [HACKERS] New locking code - Mailing list pgsql-hackers

> 2) The system implements a FIFO queue.  I.E. A reader can't "cut in
> line" in front of a waiting writer just because the current access
> mode is shared.  The operations that have been waiting the longest get
> serviced first.

I thinking about this FIFO comment, here is a better fix.  It implements
a FIFO for the lock wait queue, except it groups readers togther in the
queue.  The major change is that I now loop past as many writers that
may be at the head of the queue, then put the readers in the queue.  If
there are already readers in the queue after the writers, I add them to
the end of the existing readers.  The source code comments are changed,
and provide a more detailed explaination.

I am planning to put this into 6.3, to fix a possible reader starvation
problem with the new code.

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

*** ./backend/storage/lmgr/proc.c.orig    Tue Jan 27 21:29:29 1998
--- ./backend/storage/lmgr/proc.c    Wed Feb 18 20:10:04 1998
***************
*** 451,469 ****
            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;
!     }

      MyProc->prio = prio;
      MyProc->token = token;
--- 451,492 ----
            int prio,
            LOCK *lock)
  {
!     int            i = 0;
      PROC       *proc;
      struct itimerval timeval,
                  dummy;

+     /*
+      *    If the first entries in the waitQueue have a greater priority than
+      *    we have, we must be a reader, and they must be a writers, 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 writers.  This way, we have a FIFO, but
+      *    keep the readers together to give them decent priority, and no one
+      *    starves.  Because we group all readers together, a non-empty queue
+      *    only has a few possible configurations:
+      *
+      *    [readers]
+      *    [writers]
+      *    [readers][writers]
+      *    [writers][readers]
+      *    [writers][readers][writers]
+      *
+      *    In a full queue, we would have a reader holding a lock, then a
+      *    writer gets the lock, then a bunch of readers, made up of readers
+      *    who could not share the first readlock because a writer was waiting,
+      *    and new readers arriving while the writer had the lock.
+      *
+      */
      proc = (PROC *) MAKE_PTR(waitQueue->links.prev);
!
!     /* If we are a reader, and they are writers, skip past them */
!     while (i++ < waitQueue->size && proc->prio > prio)
!         proc = (PROC *) MAKE_PTR(proc->links.prev);
!
!     /* The rest of the queue is FIFO, with readers first, writers last */
!     while (i++ < waitQueue->size && proc->prio <= prio)
!         proc = (PROC *) MAKE_PTR(proc->links.prev);

      MyProc->prio = prio;
      MyProc->token = token;
***************
*** 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);

--- 619,625 ----

          /*
           * 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