這篇文章主要講解了“怎么理解PostgreSQL Locks中的The Deadlock Detection Algorithm”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“怎么理解PostgreSQL Locks中的The Deadlock Detection Algorithm”吧！

我們提供的服務(wù)有：成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、萍鄉(xiāng)ssl等。為成百上千家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的萍鄉(xiāng)網(wǎng)站制作公司

一、The Deadlock Detection Algorithm

The Deadlock Detection Algorithm
--------------------------------
死鎖檢測算法
Since we allow user transactions to request locks in any order, deadlock
is possible.  We use a deadlock detection/breaking algorithm that is
fairly standard in essence, but there are many special considerations
needed to deal with Postgres' generalized locking model.
PG允許事務(wù)以亂序的方式申請鎖,因此會出現(xiàn)死鎖的可能.PG使用的檢測算法相當(dāng)標(biāo)準(zhǔn),
但為了適配PG的鎖模型因此有不少特別的考慮.
A key design consideration is that we want to make routine operations
(lock grant and release) run quickly when there is no deadlock, and
avoid the overhead of deadlock handling as much as possible.  We do this
using an "optimistic waiting" approach: if a process cannot acquire the
lock it wants immediately, it goes to sleep without any deadlock check.
But it also sets a delay timer, with a delay of DeadlockTimeout
milliseconds (typically set to one second).  If the delay expires before
the process is granted the lock it wants, it runs the deadlock
detection/breaking code. Normally this code will determine that there is
no deadlock condition, and then the process will go back to sleep and
wait quietly until it is granted the lock.  But if a deadlock condition
does exist, it will be resolved, usually by aborting the detecting
process' transaction.  In this way, we avoid deadlock handling overhead
whenever the wait time for a lock is less than DeadlockTimeout, while
not imposing an unreasonable delay of detection when there is an error.
一個設(shè)計(jì)上考慮的關(guān)鍵點(diǎn)是在沒有死鎖的情況下可以讓鎖授予和釋放可以執(zhí)行得更快.
通過使用一種"樂觀等待"機(jī)制來實(shí)現(xiàn):如果進(jìn)程不能馬上獲取請求的鎖,則馬上休眠而不執(zhí)行任何死鎖檢測.
但同時設(shè)置了延遲時鐘,延遲時長為DeadlockTimeout毫秒(典型值是1s).
如果在進(jìn)程被授予鎖前延遲過期,則執(zhí)行死鎖檢測和中斷代碼.通常來說,這些代碼會確定
是否存在死鎖條件,然后進(jìn)程會重新休眠并等待直至可以獲取鎖.
但如果死鎖條件確實(shí)存在,那需解決此問題,通過來說會回滾執(zhí)行檢測的事務(wù).
通過這種方法,避免鎖等待時間小于DeadlockTimeout時的死鎖處理開銷,
而在出現(xiàn)錯誤時則不執(zhí)行不合理的延遲檢測.
Lock acquisition (routines LockAcquire and ProcSleep) follows these rules:
鎖獲取(LockAcquire和ProcSleep子過程)遵循以下原則:
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.
1.對于如無沖突或者進(jìn)程已持有相同類型的鎖的鎖請求(如獲取兩次讀鎖),則馬上授予鎖.
注意進(jìn)程永遠(yuǎn)不會與自己沖突,比如已獲取獨(dú)占鎖的情況下可以獲取讀鎖.
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.
2.否則,進(jìn)程會加入到鎖等待隊(duì)列.通常來說,會加入到隊(duì)列的末尾,但存在例外情況:
如果進(jìn)程已在對象上持有鎖但與其他等待者的請求存在沖突,進(jìn)程會插入到隊(duì)列中這些waiter的前面.
(如果不執(zhí)行該檢查,死鎖檢測代碼會調(diào)整隊(duì)列順序以解決沖突,
但在ProcSleep中執(zhí)行該檢查成本相對會低一點(diǎn),同時在這種情況下可以避免一次死鎖檢測超時延遲)
注意插入時在隊(duì)列末尾的特殊情況:如果進(jìn)程在插入點(diǎn)前的請求與現(xiàn)存鎖或其他請求不存在沖突,
則放在隊(duì)列的最前面同時無需等待馬上授予鎖.
When a lock is released, the lock release routine (ProcLockWakeup) scans
the lock object's wait queue.  Each waiter is awoken if (a) its request
does not conflict with already-granted locks, and (b) its request does
not conflict with the requests of prior un-wakable waiters.  Rule (b)
ensures that conflicting requests are granted in order of arrival. There
are cases where a later waiter must be allowed to go in front of
conflicting earlier waiters to avoid deadlock, but it is not
ProcLockWakeup's responsibility to recognize these cases; instead, the
deadlock detection code will re-order the wait queue when necessary.
鎖釋放時,ProcLockWakeup會掃描鎖定對象的等待隊(duì)列.喚醒滿足(a)鎖請求與現(xiàn)存鎖不存在沖突
(b)請求與先前未喚醒的waiter不存在沖突 這兩個條件的waiter.
規(guī)則(b)確保存在沖突的請求必須按到達(dá)的先后順序授予.
避免在允許后來者可在出現(xiàn)沖突的waiter前可能出現(xiàn)的死鎖,但這不是ProcLockWakeup的職責(zé),
相反,死鎖檢測代碼會在需要時重組等待隊(duì)列.
To perform deadlock checking, we use the standard method of viewing the
various processes as nodes in a directed graph (the waits-for graph or
WFG).  There is a graph edge leading from process A to process B if A
waits for B, ie, A is waiting for some lock and B holds a conflicting
lock.  There is a deadlock condition if and only if the WFG contains a
cycle.  We detect cycles by searching outward along waits-for edges to
see if we return to our starting point.  There are three possible
outcomes:
為了執(zhí)行死鎖檢測,使用標(biāo)準(zhǔn)方法將各個進(jìn)程視為有向圖(WFG)中的節(jié)點(diǎn).
圖中,如果A進(jìn)程等待B,那么會有存在一條從A指向B的邊.當(dāng)且僅當(dāng)如出現(xiàn)循環(huán)時,則會出現(xiàn)死鎖.
沿著等待的邊進(jìn)行檢索看看是否會回到出發(fā)點(diǎn)來判斷是否出現(xiàn)循環(huán),這里有3種可能的情況:
1. All outgoing paths terminate at a running process (which has no
outgoing edge).
1. 所有出發(fā)的路徑都終止于一個正在運(yùn)行的進(jìn)程(而沒有從該進(jìn)程出發(fā)的邊).
2. A deadlock is detected by looping back to the start point.  We
resolve such a deadlock by canceling the start point's lock request and
reporting an error in that transaction, which normally leads to
transaction abort and release of that transaction's held locks.  Note
that it's sufficient to cancel one request to remove the cycle; we don't
need to kill all the transactions involved.
2. 通過判斷是否回到開始點(diǎn)來進(jìn)行死鎖檢測.
通過取消開始點(diǎn)的鎖請求并在該事務(wù)反饋一個錯誤來解決死鎖,該事務(wù)會取消并釋放持有的鎖.
注意:取消一個鎖就可以消除循環(huán)了,而不需要?dú)⒌羲邢嚓P(guān)的事務(wù).
3. Some path(s) loop back to a node other than the start point.  This
indicates a deadlock, but one that does not involve our starting
process. We ignore this condition on the grounds that resolving such a
deadlock is the responsibility of the processes involved --- killing our
start-point process would not resolve the deadlock.  So, cases 1 and 3
both report "no deadlock".
3. 某些路徑回到某些節(jié)點(diǎn)而不是開始點(diǎn).這意味著死鎖,但不涉及到開始進(jìn)程.
基于由相關(guān)進(jìn)程來解決死鎖這一原則,PG會忽略此條件(殺掉開始點(diǎn)進(jìn)程無助于解決死鎖).
因此,第1種和第3種情況會反饋"no deadlock".
Postgres' situation is a little more complex than the standard discussion
of deadlock detection, for two reasons:
PG的情況比起標(biāo)準(zhǔn)的死鎖檢查有一點(diǎn)點(diǎn)的復(fù)雜,有2點(diǎn)原因:
1. A process can be waiting for more than one other process, since there
might be multiple PROCLOCKs of (non-conflicting) lock types that all
conflict with the waiter's request.  This creates no real difficulty
however; we simply need to be prepared to trace more than one outgoing
edge.
1. 進(jìn)程可等待超過1個其他進(jìn)程,因?yàn)榇嬖诙鄠€與等待請求相沖突的鎖類型相應(yīng)的PROCLOCKs.
這不會造成實(shí)際的困難,僅需要跟蹤多個出發(fā)的邊即可.
2. If a process A is behind a process B in some lock's wait queue, and
their requested locks conflict, then we must say that A waits for B, since
ProcLockWakeup will never awaken A before B.  This creates additional
edges in the WFG.  We call these "soft" edges, as opposed to the "hard"
edges induced by locks already held.  Note that if B already holds any
locks conflicting with A's request, then their relationship is a hard edge
not a soft edge.
2. 如果進(jìn)程A在等待隊(duì)列中在B進(jìn)程之后,而它們的請求鎖沖突,這時候我們會認(rèn)為A等待B,
因?yàn)镻rocLockWakeup在B之前不會喚醒A.這會在WFG中產(chǎn)生額外的我們稱之為soft(相對于實(shí)際已持有的鎖而言)的邊.
注意如果B已持有所有與A請求沖突的鎖,那么它們的關(guān)系是硬邊而不是軟邊.
A "soft" block, or wait-priority block, has the same potential for
inducing deadlock as a hard block.  However, we may be able to resolve
a soft block without aborting the transactions involved: we can instead
rearrange the order of the wait queue.  This rearrangement reverses the
direction of the soft edge between two processes with conflicting requests
whose queue order is reversed.  If we can find a rearrangement that
eliminates a cycle without creating new ones, then we can avoid an abort.
Checking for such possible rearrangements is the trickiest part of the
algorithm.
"soft"阻塞或者等待優(yōu)先級阻塞,與硬阻塞的處理一樣.
但是,我們可以不需要取消事務(wù)而解決軟阻塞:重新排列等待隊(duì)列的順序即可.
重排會調(diào)轉(zhuǎn)相關(guān)進(jìn)程的優(yōu)先順序.如果能夠重排而解決循環(huán),那么可以避免取消事務(wù).
檢查是否存在這樣的重排是算法中最棘手的部分.
The workhorse of the deadlock detector is a routine FindLockCycle() which
is given a starting point process (which must be a waiting process).
It recursively scans outward across waits-for edges as discussed above.
If it finds no cycle involving the start point, it returns "false".
(As discussed above, we can ignore cycles not involving the start point.)
When such a cycle is found, FindLockCycle() returns "true", and as it
unwinds it also builds a list of any "soft" edges involved in the cycle.
If the resulting list is empty then there is a hard deadlock and the
configuration cannot succeed.  However, if the list is not empty, then
reversing any one of the listed edges through wait-queue rearrangement
will eliminate that cycle.  Since such a reversal might create cycles
elsewhere, we may need to try every possibility.  Therefore, we need to
be able to invoke FindLockCycle() on hypothetical configurations (wait
orders) as well as the current real order.
死鎖檢測器主要有例程FindLockCycle實(shí)現(xiàn),該例程輸入為起始點(diǎn)過程(正在等待的進(jìn)程).
如上所述,遞歸掃描指向到其他進(jìn)程的邊.如果從開始點(diǎn)沒有發(fā)現(xiàn)循環(huán),返回"false".
(正如上述所討論的,忽略與開始點(diǎn)無關(guān)的循環(huán)).
如果發(fā)現(xiàn)了存在循環(huán),FindLockCycle例程會返回"true",在展開(unwinds)時,
它還構(gòu)建了一個包含涉及所有軟邊的鏈表.如果結(jié)果鏈表為空,那么只存在硬死鎖,重排不會成功.
但是,如果鏈表非空,遞歸重排鏈表中的邊檢查是否可以消除循環(huán).
由于這樣的重排可能會在其他地方產(chǎn)生新的循環(huán),因此需要嘗試各種可能.
因此,我們需要具備在假設(shè)配置和實(shí)際順序調(diào)用FindLockCycle的能力.
The easiest way to handle this seems to be to have a lookaside table that
shows the proposed new queue order for each wait queue that we are
considering rearranging.  This table is checked by FindLockCycle, and it
believes the proposed queue order rather than the real order for each lock
that has an entry in the lookaside table.
看起來最簡單的方法是使用一個后備表,該表顯示了我們正在考慮隊(duì)列重排的每個建議的新順序.
該表通過FindLockCycle檢測,并且該例程相信建議的隊(duì)列順序而不是實(shí)際順序.
We build a proposed new queue order by doing a "topological sort" of the
existing entries.  Each soft edge that we are currently considering
reversing creates a property of the partial order that the topological sort
has to enforce.  We must use a sort method that preserves the input
ordering as much as possible, so as not to gratuitously break arrival
order for processes not involved in a deadlock.  (This is not true of the
tsort method shown in Knuth, for example, but it's easily done by a simple
doubly-nested-loop method that emits the first legal candidate at each
step.  Fortunately, we don't need a highly efficient sort algorithm, since
the number of partial order constraints is not likely to be large.)  Note
that failure of the topological sort tells us we have conflicting ordering
constraints, and therefore that the last-added soft edge reversal
conflicts with a prior edge reversal.  We need to detect this case to
avoid an infinite loop in the case where no possible rearrangement will
work: otherwise, we might try a reversal, find that it still leads to
a cycle, then try to un-reverse the reversal while trying to get rid of
that cycle, etc etc.  Topological sort failure tells us the un-reversal
is not a legitimate move in this context.
對每一存在的條目使用"topological sort"創(chuàng)建可能的新隊(duì)列順序.
我們目前考慮反轉(zhuǎn)的每個軟邊都創(chuàng)建了拓?fù)渑判虮仨殢?qiáng)制執(zhí)行的偏序?qū)傩?
我們必須使用一種盡可能保留輸入順序的排序方法,這樣就不會無緣無故破壞不涉及死鎖進(jìn)程的到達(dá)順序.
注意拓?fù)渑判蛉绻t意味著存在沖突排序約束,因此最好添加的軟邊反轉(zhuǎn)與先前的反轉(zhuǎn)存在沖突.
需要檢測這種情況以避免出現(xiàn)死循環(huán).可以試著反轉(zhuǎn),如果發(fā)現(xiàn)它仍然會導(dǎo)致循環(huán),
那么再反轉(zhuǎn),試圖擺脫那個循環(huán),等等.拓?fù)渑判蚴∫馕吨谶@種情況下反向操作是不合法的.
So, the basic step in our rearrangement method is to take a list of
soft edges in a cycle (as returned by FindLockCycle()) and successively
try the reversal of each one as a topological-sort constraint added to
whatever constraints we are already considering.  We recursively search
through all such sets of constraints to see if any one eliminates all
the deadlock cycles at once.  Although this might seem impossibly
inefficient, it shouldn't be a big problem in practice, because there
will normally be very few, and not very large, deadlock cycles --- if
any at all.  So the combinatorial inefficiency isn't going to hurt us.
Besides, it's better to spend some time to guarantee that we've checked
all possible escape routes than to abort a transaction when we didn't
really have to.
因此,重排方法的基礎(chǔ)步驟是獲取循環(huán)中的軟邊鏈表(FindLockCycle返回),依次嘗試
將每個約束的反轉(zhuǎn)作為拓?fù)渑判蚣s束添加到已經(jīng)考慮的其他約束中.
遞歸檢索所有這樣的約束集合來看看是否存在可以消除循環(huán)的可能.
雖然這看來不太可能很有效,但在實(shí)踐中也沒有什么問題,因?yàn)樗梨i循環(huán)的數(shù)量通常很小.
因此這樣的組合并不會有什么問題.話又說回來,最好花點(diǎn)時間來保證已檢測所有可能的路徑
而不是什么都不做就取消事務(wù).
Each edge reversal constraint can be viewed as requesting that the waiting
process A be moved to before the blocking process B in the wait queue they
are both in.  This action will reverse the desired soft edge, as well as
any other soft edges between A and other processes it is advanced over.
No other edges will be affected (note this is actually a constraint on our
topological sort method to not re-order the queue more than necessary.)
Therefore, we can be sure we have not created any new deadlock cycles if
neither FindLockCycle(A) nor FindLockCycle(B) discovers any cycle.  Given
the above-defined behavior of FindLockCycle, each of these searches is
necessary as well as sufficient, since FindLockCycle starting at the
original start point will not complain about cycles that include A or B
but not the original start point.
每個邊的反轉(zhuǎn)約束都可以看做是請求等待進(jìn)程A移到等待隊(duì)列的阻塞進(jìn)程B的前面.
這樣的做法會反轉(zhuǎn)有向軟邊,現(xiàn)對于在A和其他進(jìn)程之間的其他軟邊,它是advanced over的.
沒有其他邊受影響,因此可以確保不會出現(xiàn)新的死鎖循環(huán).根據(jù)以上定義的FindLockCycle行為,
這些搜索都是必要的,也是充分的,因?yàn)閺钠鹗键c(diǎn)開始的FindLockCycle不會認(rèn)為包含A或B但不包含
初始起始點(diǎn)的循環(huán)有問題.
In short then, a proposed rearrangement of the wait queue(s) is determined
by one or more broken soft edges A->B, fully specified by the output of
topological sorts of each wait queue involved, and then tested by invoking
FindLockCycle() starting at the original start point as well as each of
the mentioned processes (A's and B's).  If none of the tests detect a
cycle, then we have a valid configuration and can implement it by
reordering the wait queues per the sort outputs (and then applying
ProcLockWakeup on each reordered queue, in case a waiter has become wakable).
If any test detects a soft cycle, we can try to resolve it by adding each
soft link in that cycle, in turn, to the proposed rearrangement list.
This is repeated recursively until we either find a workable rearrangement
or determine that none exists.  In the latter case, the outer level
resolves the deadlock by aborting the original start-point transaction.
簡短的來說,等待隊(duì)列的重排通過打破一個或多個A->B這樣的軟邊來確定,
由所涉及的每個等待隊(duì)列的拓?fù)渑判虻妮敵鐾耆付?然后通過調(diào)用FindLockCycle進(jìn)行測試,
該函數(shù)從原始的起始點(diǎn)以及上面提到的每個進(jìn)程(A&B)開始.
如果沒有一個測試檢測到循環(huán),那么我們有了一個有效的配置,通過重排每個重新排序的隊(duì)列來實(shí)現(xiàn)這一點(diǎn).
如果測試發(fā)現(xiàn)了軟循環(huán),可以嘗試通過將該循環(huán)中的每個軟鏈接依次添加到建議的重排鏈表中來解決.
遞歸處理直至找到了可用的重排或者確定重排不存在.在后續(xù)的情況中,外層通過取消開始點(diǎn)事務(wù)來解決死鎖.
The particular order in which rearrangements are tried depends on the
order FindLockCycle() happens to scan in, so if there are multiple
workable rearrangements of the wait queues, then it is unspecified which
one will be chosen.  What's more important is that we guarantee to try
every queue rearrangement that could lead to success.  (For example,
if we have A before B before C and the needed order constraints are
C before A and B before C, we would first discover that A before C
doesn't work and try the rearrangement C before A before B.  This would
eventually lead to the discovery of the additional constraint B before C.)
嘗試重排的特定順序取決于FindLockCycle碰巧掃描進(jìn)來的順序,因此如果存在多個等待隊(duì)列上的重排,
那么選擇哪一個就不確定.更重要的是我們確保嘗試每個隊(duì)列重排可能會成功.
(比如,如果A在B和C的前面,B在C的前面,排序約束是C在A之前和B在C之前,首先會發(fā)現(xiàn)A在C之前是不行的,
這時候會重排C在A和B之前.這會導(dǎo)致額外的約束B在C之前)

感謝各位的閱讀，以上就是“怎么理解PostgreSQL Locks中的The Deadlock Detection Algorithm”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對怎么理解PostgreSQL Locks中的The Deadlock Detection Algorithm這一問題有了更深刻的體會，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識點(diǎn)的文章，歡迎關(guān)注！

名稱欄目：怎么理解PostgreSQLLocks中的TheDeadlockDetectionAlgorithm
URL分享：http://chinadenli.net/article6/jsisig.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)公司、面包屑導(dǎo)航、網(wǎng)站內(nèi)鏈、響應(yīng)式網(wǎng)站、企業(yè)建站、動態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)