Thread: some question about deadlock
Hi,
Below is the notes from postgresql-8.1.3/src/backend/storage/lmgr/README:
Lock acquisition (routines LockAcquire and ProcSleep) follows these rules:
1. A lock request is granted immediately if it does not conflict with
any existing or waiting lock request, or if the process already holds an
instance of the same lock type (eg, there's no penalty to acquire a read
lock twice). Note that a process never conflicts with itself, eg one
can obtain read lock when one already holds exclusive lock.
any existing or waiting lock request, or if the process already holds an
instance of the same lock type (eg, there's no penalty to acquire a read
lock twice). Note that a process never conflicts with itself, eg one
can obtain read lock when one already holds exclusive lock.
2. Otherwise the process joins the lock's wait queue. Normally it will
be added to the end of the queue, but there is an exception: if the
process already holds locks on this same lockable object that conflict
with the request of any pending waiter, then the process will be
inserted in the wait queue just ahead of the first such waiter. (If we
did not make this check, the deadlock detection code would adjust the
queue order to resolve the conflict, but it's relatively cheap to make
the check in ProcSleep and avoid a deadlock timeout delay in this case.)
Note special case when inserting before the end of the queue: if the
process's request does not conflict with any existing lock nor any
waiting request before its insertion point, then go ahead and grant the
lock without waiting.
be added to the end of the queue, but there is an exception: if the
process already holds locks on this same lockable object that conflict
with the request of any pending waiter, then the process will be
inserted in the wait queue just ahead of the first such waiter. (If we
did not make this check, the deadlock detection code would adjust the
queue order to resolve the conflict, but it's relatively cheap to make
the check in ProcSleep and avoid a deadlock timeout delay in this case.)
Note special case when inserting before the end of the queue: if the
process's request does not conflict with any existing lock nor any
waiting request before its insertion point, then go ahead and grant the
lock without waiting.
I am confused with that exception(in bold), could some one give me an example?
Best regards.
ipig wrote: > Hi, > > Below is the notes from postgresql-8.1.3/src/backend/storage/lmgr/README: > > > Lock acquisition (routines LockAcquire and ProcSleep) follows these rules: > > 1. A lock request is granted immediately if it does not conflict with > any existing or waiting lock request, or if the process already holds an > instance of the same lock type (eg, there's no penalty to acquire a read > lock twice). Note that a process never conflicts with itself, eg one > can obtain read lock when one already holds exclusive lock. > > 2. Otherwise the process joins the lock's wait queue. Normally it will > be added to the end of the queue, but there is an exception: if the > process already holds locks on this same lockable object that conflict > with the request of any pending waiter, then the process will be > inserted in the wait queue just ahead of the first such waiter. (If we > did not make this check, the deadlock detection code would adjust the > queue order to resolve the conflict, but it's relatively cheap to make > the check in ProcSleep and avoid a deadlock timeout delay in this case.) > Note special case when inserting before the end of the queue: if the > process's request does not conflict with any existing lock nor any > waiting request before its insertion point, then go ahead and grant the > lock without waiting. > > > I am confused with that exception(in bold), could some one give me an example? Well, first you are requiring people to be reading HTML email to see the bold text you added, which is not good: an exception: if the process already holds locks on this same lockableobject that conflict with the request of any pendingwaiter, then theprocess will be inserted in the wait queue just ahead of the first suchwaiter. An example would be you have a read lock and want an exclusive lock, and someone else in the queue is waiting for a read lock too. In this case, the exclusive lock goes before the queued read lock. -- Bruce Momjian http://candle.pha.pa.us EnterpriseDB http://www.enterprisedb.com + If your life is a hard drive, Christ can be your backup. +
Hi, Thanks for your reply. I changed the format to plain text. For the question, suppose that process p0 held the lock of object A, and the wait queue for A is p1,p2,p3,...., that processp1 is the first waiter in the queue. Since p1 is in the wait queue, the lock p1 requests must be conflict with thelock p0 held. That is to say, if p0 wants to lock A again, then p0 will be put before p1, and p0 will be at the headof the queue. Why do we need to find the first waiter which conflicts p0? I think that p0 must be added at the head ofthe wait queue. For your example, p0 has a read lock and wants an exclusive lock. Since p0 has a read lock, then inthe queue, p1 must wait an exclusive lock. Then p0 will be put before p1, and p0 will be at the head of the queue. Is there anything I misunderstood? Best wishes. ----- Original Message ----- From: "Bruce Momjian" <pgman@candle.pha.pa.us> To: "ipig" <ipig@ercist.iscas.ac.cn> Cc: <pgsql-hackers@postgresql.org> Sent: Monday, May 29, 2006 9:49 PM Subject: Re: [HACKERS] some question about deadlock > ipig wrote: >> Hi, >> >> Below is the notes from postgresql-8.1.3/src/backend/storage/lmgr/README: >> >> >> Lock acquisition (routines LockAcquire and ProcSleep) follows these rules: >> >> 1. A lock request is granted immediately if it does not conflict with >> any existing or waiting lock request, or if the process already holds an >> instance of the same lock type (eg, there's no penalty to acquire a read >> lock twice). Note that a process never conflicts with itself, eg one >> can obtain read lock when one already holds exclusive lock. >> >> 2. Otherwise the process joins the lock's wait queue. Normally it will >> be added to the end of the queue, but there is an exception: if the >> process already holds locks on this same lockable object that conflict >> with the request of any pending waiter, then the process will be >> inserted in the wait queue just ahead of the first such waiter. (If we >> did not make this check, the deadlock detection code would adjust the >> queue order to resolve the conflict, but it's relatively cheap to make >> the check in ProcSleep and avoid a deadlock timeout delay in this case.) >> Note special case when inserting before the end of the queue: if the >> process's request does not conflict with any existing lock nor any >> waiting request before its insertion point, then go ahead and grant the >> lock without waiting. >> >> >> I am confused with that exception(in bold), could some one give me an example? > > Well, first you are requiring people to be reading HTML email to see the > bold text you added, which is not good: > > an exception: if the process already holds locks on this same lockable > object that conflict with the request of any pending waiter, then the > process will be inserted in the wait queue just ahead of the first such > waiter. > > An example would be you have a read lock and want an exclusive lock, and > someone else in the queue is waiting for a read lock too. In this case, > the exclusive lock goes before the queued read lock. > > -- > Bruce Momjian http://candle.pha.pa.us > EnterpriseDB http://www.enterprisedb.com > > + If your life is a hard drive, Christ can be your backup. + > > ---------------------------(end of broadcast)--------------------------- > TIP 5: don't forget to increase your free space map settings
ipig wrote: > Hi, > Thanks for your reply. > I changed the format to plain text. > > For the question, suppose that process p0 held the lock of object A, and the wait queue for A is p1,p2,p3,...., thatprocess p1 is the first waiter in the queue. > Since p1 is in the wait queue, the lock p1 requests must be conflict with the lock p0 held. > That is to say, if p0 wants to lock A again, then p0 will be put before p1, and p0 will be at the head of the queue.Why do we need to find the first waiter which conflicts p0? I think that p0 must be added at the head of the wait queue. > > For your example, p0 has a read lock and wants an exclusive lock. > Since p0 has a read lock, then in the queue, p1 must wait an exclusive lock. > Then p0 will be put before p1, and p0 will be at the head of the queue. > > Is there anything I misunderstood? I am guessing that p0 is put at the head _only_ if there are conflicting locks so that p0 does not starve other waiting processes. -- Bruce Momjian http://candle.pha.pa.us EnterpriseDB http://www.enterprisedb.com + If your life is a hard drive, Christ can be your backup. +
Alvaro Herrera wrote: > ipig wrote: > > Hi, > > Thanks for your reply. > > I changed the format to plain text. > > > > For the question, suppose that process p0 held the lock of object A, and the wait queue for A is p1,p2,p3,...., thatprocess p1 is the first waiter in the queue. > > Since p1 is in the wait queue, the lock p1 requests must be conflict with the lock p0 held. > > That is to say, if p0 wants to lock A again, then p0 will be put before p1, and p0 will be at the head of the queue.Why do we need to find the first waiter which conflicts p0? I think that p0 must be added at the head of the wait queue. > > > > For your example, p0 has a read lock and wants an exclusive lock. > > Since p0 has a read lock, then in the queue, p1 must wait an exclusive lock. > > Then p0 will be put before p1, and p0 will be at the head of the queue. > > > > Is there anything I misunderstood? > > You missed this: > > "Note that a process never conflicts with itself, eg one can obtain read > lock when one already holds exclusive lock." > > If p0 is holding a read lock and wants an exclusive lock, it will be > granted right away. It will not be put in the waiting queue. Uh, unless other processes also hold a read lock on the object. In that case, p0 has to wait, and I think the description is saying p0 will be put ahead of other readers waiting for the object. -- Bruce Momjian http://candle.pha.pa.us EnterpriseDB http://www.enterprisedb.com + If your life is a hard drive, Christ can be your backup. +
Hi, an exception: if the process already holds locks on this same lockable object that conflict with the request of any pending waiter, then the process will be inserted in the wait queue just ahead of the first such waiter. From the exception, I got that the process must be added at the head, since the first waiter in the queue must conflictwith the lock-held process. Best wishes. ----- Original Message ----- From: "Bruce Momjian" <pgman@candle.pha.pa.us> To: "ipig" <ipig@ercist.iscas.ac.cn> Cc: <pgsql-hackers@postgresql.org> Sent: Monday, May 29, 2006 11:26 PM Subject: Re: [HACKERS] some question about deadlock > ipig wrote: >> Hi, >> Thanks for your reply. >> I changed the format to plain text. >> >> For the question, suppose that process p0 held the lock of object A, and the wait queue for A is p1,p2,p3,...., thatprocess p1 is the first waiter in the queue. >> Since p1 is in the wait queue, the lock p1 requests must be conflict with the lock p0 held. >> That is to say, if p0 wants to lock A again, then p0 will be put before p1, and p0 will be at the head of the queue.Why do we need to find the first waiter which conflicts p0? I think that p0 must be added at the head of the wait queue. >> >> For your example, p0 has a read lock and wants an exclusive lock. >> Since p0 has a read lock, then in the queue, p1 must wait an exclusive lock. >> Then p0 will be put before p1, and p0 will be at the head of the queue. >> >> Is there anything I misunderstood? > > I am guessing that p0 is put at the head _only_ if there are conflicting > locks so that p0 does not starve other waiting processes. > > -- > Bruce Momjian http://candle.pha.pa.us > EnterpriseDB http://www.enterprisedb.com > > + If your life is a hard drive, Christ can be your backup. +
"ipig" <ipig@ercist.iscas.ac.cn> writes:
> That is to say, if p0 wants to lock A again, then p0 will be put before p1, and p0 will be at the head of the
queue.Why do we need to find the first waiter which conflicts p0? I think that p0 must be added at the head of the wait
queue.
Your analysis is assuming that there are only two kinds of lock, which
is not so. Process A might hold a weak lock and process B a slightly
stronger lock that doesn't conflict with A's. In the wait queue there
might be process C wanting a lock that conflicts with B's but not A's,
followed by process D wanting a strong lock that conflicts with all three.
Now suppose A wants to get a lock of the same type D wants. Since this
conflicts with B's existing lock, A must wait. A must go into the queue
before D (else deadlock) but if possible it should go after C, on
fairness grounds.
A concrete example here isA has AccessShareLock (reader's lock)B has RowExclusiveLock (writer's lock)C wants ShareLock
(henceblocked by B but not A)D wants AccessExclusiveLock (must wait for all three)
If A wants to upgrade to AccessExclusiveLock, it *must* queue in front
of D, and we'd prefer that it queue behind C not in front of C.
regards, tom lane
Hi, In your example, it seems that process B is the first such waiter( the request of B conflicts AccessShareLock). Best regards. ----- Original Message ----- From: "Tom Lane" <tgl@sss.pgh.pa.us> To: "ipig" <ipig@ercist.iscas.ac.cn> Cc: "Bruce Momjian" <pgman@candle.pha.pa.us>; <pgsql-hackers@postgresql.org> Sent: Monday, May 29, 2006 11:51 PM Subject: Re: [HACKERS] some question about deadlock > "ipig" <ipig@ercist.iscas.ac.cn> writes: >> That is to say, if p0 wants to lock A again, then p0 will be put before p1, and p0 will be at the head of the queue.Why do we need to find the first waiter which conflicts p0? I think that p0 must be added at the head of the wait queue. > > Your analysis is assuming that there are only two kinds of lock, which > is not so. Process A might hold a weak lock and process B a slightly > stronger lock that doesn't conflict with A's. In the wait queue there > might be process C wanting a lock that conflicts with B's but not A's, > followed by process D wanting a strong lock that conflicts with all three. > Now suppose A wants to get a lock of the same type D wants. Since this > conflicts with B's existing lock, A must wait. A must go into the queue > before D (else deadlock) but if possible it should go after C, on > fairness grounds. > > A concrete example here is > A has AccessShareLock (reader's lock) > B has RowExclusiveLock (writer's lock) > C wants ShareLock (hence blocked by B but not A) > D wants AccessExclusiveLock (must wait for all three) > If A wants to upgrade to AccessExclusiveLock, it *must* queue in front > of D, and we'd prefer that it queue behind C not in front of C. > > regards, tom lane > > ---------------------------(end of broadcast)--------------------------- > TIP 4: Have you searched our list archives? > > http://archives.postgresql.org
"ipig" <ipig@ercist.iscas.ac.cn> writes: > In your example, it seems that process B is the first such waiter( the request of B conflicts AccessShareLock). No. Better go study http://developer.postgresql.org/docs/postgres/explicit-locking.html#LOCKING-TABLES After looking at the example again, consider the further assumption that C already has AccessShareLock (which is certainly a valid configuration). Then A *must* queue between C and D; there is no other valid order to grant the requests in. regards, tom lane