Re: Revised Patch to allow multiple table locks in "Unison"

> > The second LOCK statements cannot release the locks already held,
> > therefore this is a deadlock.
>
> But that is a programmer's error.  He/she is acquiring the locks in
> reversed order.  The fact that the second lock request is in a multiple
> lock is not much different from doing it with a single lock like in:
>
>         Process 1                       Process 2
>
>         LOCK a;                         LOCK b;
>         ...                             ...
>         LOCK b;                         LOCK a;
>
> I guess you've mentioned this scenario because of the undetected
> deadlock
> concerns, right?
>

I guess so.  The above would issue a deadlock error message, while the
LOCK a,b would just spin around.

> >  While that's no worse than we had
> > before, I believe that your patch introduces a possibility of
> > undetected deadlock.  Consider this:
> >
> >         Process 1                       Process 2
> >
> >         LOCK a,b;                       LOCK b,a;
> >
> > A possible interleaving of execution is: 1 acquires lock a, 2 acquires
> > b, 1 tries to acquire b and fails, 2 tries to acquire a and fails,
> > 1 releases a, 2 releases b, 1 acquires b, 2 acquires a, 1 tries to
> > acquire a and fails, etc etc.  It's implausible that this condition
> > would persist in perfect lockstep for very long on a uniprocessor
> > machine ... but not so implausible if you have dual CPUs, each running
> > one of the two processes at exactly the same speed.
> >
> > I haven't quite managed to work out a full scenario, but I think it is
> > possible that the combination of these two effects could result in an
> > indefinite, never-detected deadlock --- without implausible assumptions
> > about process speed.
>
>
> I believe the undetected deadlock is not possible.  To get the multiple
> lock statement involved in the deadlock scenario, at least one of the
> locks
> desired must have been acquired (in a separate statement) by the other
> process.
>
> The key property of the algorithm that prevents the undetected deadlocks
> is
> that it waits on the last failed-to-acquire lock.
>
> As the algorithm waits on the last non-obtained lock and restarts
> from there (in a circular fashion), it will eventually reach the lock
> that
> the other process has and then stop for good (thus allowing the deadlock
> detection to see it).
>
> Even if the algorithm started always from the first specified lock and
> then
> got in the lockstep mode you've described, the (potential) deadlock
> would
> not be detected because it had not happened yet.  It will only happen
> when
> the 2nd situation you've described ceases to exist and the crossed locks
> are
> attempted.  But them the processes are really stopped and the deadlock
> can be detected.

The unusual case here is that deadlock is not checked on request, but
only after waiting on the lock for a while.  This is because deadlock
detection is an expensive operation.   In fact, you don't want deadlock
detection in this case because LOCK a,b could be evaluated as a,b or b,a
and you don't want it to fail randomly with deadlock messages.

I certainly would like to find a solution to this that makes everyone
comfortable.

--
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026