Re: Revised Patch to allow multiple table locks in "Unison" - Mailing list pgsql-patches

Tom Lane wrote:
>
> > Stallings writes about preventing condition 3: "This condition can be
> > prevented in several ways. [. . .] [One way is to require that,] if a
> > process holding certain resources is denied a further request, that
> > process must release its original resources and, if necessary, request
> > them again together with the additional resources."
> >
> > This is exactly what the patch does.
>
> No, that is not what it does.  Note that Stallings specifies that the
> failed requestor must release ALL previously held resources.  That is
> not feasible in Postgres; some of the locks may be held due to previous
> commands in the same transaction.  Consider this scenario:
>
>         Process 1                       Process 2
>
>         LOCK a;                         LOCK b;
>         ...                             ...
>         LOCK b,c;                       LOCK a,c;
>
> 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?



>  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.


--
Fernando Nasser
Red Hat Canada Ltd.                     E-Mail:  fnasser@redhat.com
2323 Yonge Street, Suite #300
Toronto, Ontario   M4P 2C9