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

Okay, I've developed a case where the proposed multi-LOCK implementation
will wait forever without detecting deadlock --- indeed, there is no
true deadlock, but it won't figure out how to get out of it.

The problem is that we have multiple types of locks, some of which
conflict and some of which don't. It's sufficient to think about
"shared" (reader) and "exclusive" (writer) locks for this example.
Consider this scenario:

Process 1 Process 2 Process 3

SH LOCK A

SH LOCK B

EX LOCK B 3 now waits for 2

EX LOCK A 2 now waits for 1

SH LOCK B

Since process 3 is waiting for ex lock on B, our normal behavior is to
queue up 1 behind 3 in the queue for B (if we let 1 go first, 3 could be
starved indefinitely by a succession of transactions that want to read
B). In this situation, however, that would be a deadlock. The deadlock
detection code recognizes this, and also recognizes that it can escape
from the deadlock by allowing 1 to go ahead of 3 --- so SH LOCK B is
granted to 1, and we can proceed. Note that since the deadlock can only
be recognized by looking at locks and procs that are unrelated to the
queue for table B, it's extremely expensive to detect this case, and so
we don't try to do so during LockAcquire. Only when the timeout expires
and we run the full deadlock-detection algorithm do we realize that we
have a problem and find a way out of it.

Now, let's extend this to a multi-LOCK scenario:

Process 1 Process 2 Process 3 Process 4 Process 5

SH LOCK A

SH LOCK B SH LOCK C

EX LOCK B EX LOCK C

EX LOCK A EX LOCK A

(at this point, 3 waits for 2, 5 waits for 4, 2 and 4 wait for 1)

MULTI SH LOCK B,C

Now, what will happen? The multi lock code will do an unconditional
lock on B. This will initially queue up behind 3. After a deadlock
detection interval expires, the deadlock code will grant the requested
sh lock on B to 1 to escape otherwise-certain deadlock. Now the multi-
lock code will do a conditional lock on C, which will fail (since the
lock manager will not run the deadlock detection code before failing the
conditional request). The multi lock code then releases its shlock on B
and does an unconditional shlock on C. One detection interval later,
it will have that, but its conditional lock on B will fail. And away we
go.

The bottom line here is you cannot make this work correctly unless you
teach the lock manager about it. Yes, it's not trivial.

regards, tom lane