> 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. 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. It'd probably take three or more processes
contending for several locks, but it seems possible to construct a
failure scenario.
I think that the only safe way to do something like this is to teach
the lock manager itself about multiple simultaneous requests.
regards, tom lane
