收录快的门户网站,网站建设 博采网络,建设企业网站企业网上银行登录官网下载,网站是数据概念
每个事务都在等待集合中的另一事务#xff0c;由于这个集合是一个有限集合#xff0c;因此一旦在这个等待的链条上产生了环#xff0c;就会产生死锁。自旋锁和轻量锁属于系统锁#xff0c;他们目前没有死锁检测机制#xff0c;只能靠内核开发人员在开发过程中谨慎的…概念
每个事务都在等待集合中的另一事务由于这个集合是一个有限集合因此一旦在这个等待的链条上产生了环就会产生死锁。自旋锁和轻量锁属于系统锁他们目前没有死锁检测机制只能靠内核开发人员在开发过程中谨慎的使用锁避免死锁发生。 数据库中的常规锁对申请锁的顺序没有严格的限制在申请锁时也没有严格的查验因此不可避免的就会产生死锁。pg数据库采用一种全局死锁检测的方法就是每个进程启动后会启动一个定时器定时调用死锁检测函数检测是否有死锁产生如果有死锁则进行相应的处理来解除死锁。
实边
在常规锁的申请过程中假设A事务持有表的共享锁或排它锁当时事务B申请表的排他锁时就需要进入等待状态即有等待状态B-A,我们称这种等待边为实边。它主要出现在等待者和持锁者之间。
虚边
假设事务A持有共享锁事务B要申请排他锁因为与事务A冲突那么事务B就需要进入等待队列如果此时又有事务C要申请共享锁虽然事务C与事务A并不冲突但是事务C与等待队列中的事务B要持有的排他锁冲突所以事务C也要进入等待队列中此时的冲突关系C-B ,我们称他们之间等待的边为虚边。它主要出现在等待队列的等待者之间的关系。
环
在数据库中假设事务A需要等待事务B释放锁后才能执行这样的等待关系我们称之为边边是有向的。实边和虚边是边的两种特殊情况。假设一个锁的等待队列中的所有的事务他们之间的等待关系都用边来表示这样构成关系图实际上就是一种有向图。如果有向图中出现了环我们就可以判断出现了死锁。如果环的每个边都是实边那么就是出现了实边死锁实边死锁只能通过杀掉其中一个进程来断开环从而解锁。 如果环中存在虚边那么出现的就是虚边死锁就可以通过调整等待队列的顺序来尝试断开环从而解锁。
假设有A、B、C三个事务有Lock1、Lock2两把锁其中事务A等待Lock1的排它锁事务B持有Lock1的共享锁等待Lock2的共享锁事务C持有Lock 2的排它锁等待Lock1的共享锁。对于Lock1来说事务B持有其共享锁事务A等待Lock1的排它锁与事务B形成实边事务C等待Lock1的共享锁与事务B并不冲突但是与事务A冲突所以与事务A形成虚边。对于Lock2来说事务C持有Lock2的排它锁事务B在等待Lock2的共享锁与事务C冲突形成实边。最终得到的等待关系图如上图形成了一个包含虚边的环即虚边死锁即事务A在等待事务B释放Lock1事务B在等待事务C释放Lock2而事务C在等待事务A释放Lock1从而形成了死锁要解除上面的虚边死锁可以对虚边进行拓扑排序调整虚边的等待关系即将Lock1等待队列上的C–A,改成A–C,这样得到的等待关系图就不存在环了死锁就不存在了。事务A在等待事务C释放Lock1事务B在等待事务C释放Lock2事务C可以直接获取Lock1的共享锁执行完之后就可以释放Lock2的排他锁释放后事务A获取Lock1锁事务B获取Lock2锁都不再阻塞。
拓扑排序
当存在虚边构成的环时会通过重排等待队列的方式尝试断开环从而解锁。重排的方式就是通过拓扑排序实现。 拓扑排序就是在一个有向无环图DAG将所有的点 排成一个线性的序列使得每条有向边的起点都排在终点的前面。 拓扑排序遵循的原理 1 在图中选择一个没有前驱的定点V 2 从图中删除顶点V和所有以该顶点为尾的弧。 如下图
找到没有前驱的定点V1删除V1及以V1作为起点的边继续查找没有前驱的顶点此时V2和V3都符合要求随机选择一个这里选择V2删除V2和以V2作为起点的边继续查找没有前驱的顶点V3符合选择V3删除V3以及以V3作为起点的边剩余V4排序结束。 最终得到的拓扑排序结果就有两种 V1-V2-V3-V4 V1-V3-V2-V4 死锁检测函数中调用TopoSort函数实现对包含虚边的环的拓扑排序。
死锁检测相关的结构体和全局变量
结构体
EDGE
等待关系图中的一条边。 等待者waiter和阻塞者blocker可能是锁组的成员也可能不是但如果它们中任何一个属于锁组那它将是锁组的领导者而非锁组中的其他成员。即便这些特定进程根本无需等待锁组的领导者也充当整个组的代表。等待者的锁组中至少有一个成员在给定锁的等待队列上甚至可能更多。
typedef struct
{PGPROC *waiter; /* 等待者*/PGPROC *blocker; /* 被等待者or */LOCK *lock; /* 等待的锁*/int pred; /* 拓扑排序使用的额外变量 */int link; /* 拓扑排序使用的额外变量*/
} EDGE;WAIT_ORDER
等待队列如果死锁检测处有虚边死锁则会尝试通过调整等待队列来尝试消除死锁调整时新的等待队列就保存到waitOrders数组中数组中每个元素就是一个等待队列由WAIT_ORDER结构体保存其相关信息。
typedef struct
{LOCK *lock; /* 等待的锁 */PGPROC **procs; /* 在lock上的新的等待队列 */int nProcs; /* 等待队列的长度 */
} WAIT_ORDER;DEADLOCK_INFO
死锁相关的信息
typedef struct
{LOCKTAG locktag; /* 死锁的锁tag信息*/LOCKMODE lockmode; /* 等待的锁的模式*/int pid; /* 阻塞的进程号*/
} DEADLOCK_INFO;全局变量
got_deadlock_timeout 全局死锁检测标志位为true时触发死锁死锁检测。nCurConstraints: 当前检测到的边的数量curConstraints 当前已被检测的虚边的信息数组中保存拓扑排序时就对这个数组进行排序。maxCurConstraints 允许的最大的边数量nPossibleConstraints 可能的边的数量possibleConstraints 可以被调整的虚边的信息数组中保存nWaitOrders 新的等待队列的数量waitOrders 新的等待队列的信息在查找环的过程中会将对应的等待边放到该队列中方便进行重新排列。大小是进程数的1/2因为一个边就有2个等待进程。blocking_autovacuum_proc 被vacuum阻塞的进程nVisitedProcs 访问到的进程的数量visitedProcs 访问到的进程信息数组中保存通过该数组判断是否存在环比如如果一个进程在数组中重复出现则就构成了环。nDeadlockDetails 死锁详细信息的数量deadlockDetails 死锁详细信息数组中保存beforeConstraints记录每个进程需要在多少其他进程之前afterConstraints则间接通过链表头记录每个进程需要在哪些进程之后。
死锁检查流程及相关函数 注册死锁检测定时器
在每个进程启动时会注册一个死锁检测定时器,回调函数为CheckDeadLockAlert当DEADLOCK_TIMEOUT时间超时默认是1秒时就会调用CheckDeadLockAlert函数该函数内会将全局变量got_deadlock_timeout设为true. if (!bootstrap){RegisterTimeout(DEADLOCK_TIMEOUT, CheckDeadLockAlert);RegisterTimeout(STATEMENT_TIMEOUT, StatementTimeoutHandler);RegisterTimeout(LOCK_TIMEOUT, LockTimeoutHandler);RegisterTimeout(IDLE_IN_TRANSACTION_SESSION_TIMEOUT,IdleInTransactionSessionTimeoutHandler);RegisterTimeout(IDLE_SESSION_TIMEOUT, IdleSessionTimeoutHandler);RegisterTimeout(CLIENT_CONNECTION_CHECK_TIMEOUT, ClientCheckTimeoutHandler);}进程在等待锁时会调用WaitOnLock函数等待该函数又回调用procsleep函数它里面就会根据该变量判断是否需要进行死锁检测。 if (got_deadlock_timeout){CheckDeadLock();got_deadlock_timeout false;}InitDeadLockChecking
每个backend进程启动后调用初始化死锁检测相关的全局变量, maxBackend为进程的最大数量max_connections),其中死锁检测相关的全局变量初始化的大小为 MaxBackends MaxConnections autovacuum_max_workers 1 max_worker_processes max_wal_senders 100 3 1 8 10 122默认值
全部变量名长度visitedProcsMaxBackendsdeadlockDetailsMaxBackendstopoProcsMaxBackendsbeforeConstraintsMaxBackendsafterConstraintsMaxBackendswaitOrdersMaxBackends / 2waitOrderProcsMaxBackendsmaxCurConstraintsMaxBackendscurConstraintsMaxBackendsmaxPossibleConstraintsMaxBackends * 4possibleConstraintsMaxBackends * 4 visitedProcs (PGPROC **) palloc(MaxBackends * sizeof(PGPROC *));//访问过的进程数组最大为maxbankenddeadlockDetails (DEADLOCK_INFO *) palloc(MaxBackends * sizeof(DEADLOCK_INFO));//死锁详细信息最大为maxBackends/*拓扑排序用*/topoProcs visitedProcs; /* re-use this space */beforeConstraints (int *) palloc(MaxBackends * sizeof(int));afterConstraints (int *) palloc(MaxBackends * sizeof(int));waitOrders (WAIT_ORDER *)palloc((MaxBackends / 2) * sizeof(WAIT_ORDER));//等待队列数组长度为MaxBackends/2waitOrderProcs (PGPROC **) palloc(MaxBackends * sizeof(PGPROC *));//等待队列进程最大为MaxbackendsmaxCurConstraints MaxBackends;curConstraints (EDGE *) palloc(maxCurConstraints * sizeof(EDGE));//探索的边的信息最大为MaxBackends设置过大会导致嵌套深度过大导致堆栈溢出/** 允许最多保存3*MaxBackends个约束而无需重新运行TestConfiguration。这可能已经绰绰有余但即使空间不足我们也可以通过每次需要时重新运行TestConfiguration来重新计算约束列表以应对。possibleConstraints[]中的最后MaxBackends个条目被预留作为FindLockCycle的输出工作区。*/maxPossibleConstraints MaxBackends * 4;possibleConstraints (EDGE *) palloc(maxPossibleConstraints * sizeof(EDGE));CheckDeadLock
这是死锁检测的入口函数死锁检测操作就是由该函数实现。由于死锁检测是互斥的所以死锁检测期间锁表不允许被修改。但是如果一个事务只是通过本地锁表或通过FastPath就能获得锁则它不受死锁检测的影响。
以排他模式锁住主锁表 for (i 0; i NUM_LOCK_PARTITIONS; i)LWLockAcquire(LockHashPartitionLockByIndex(i), LW_EXCLUSIVE);//以排他模式锁住主锁表调用DeadLockCheck函数检测死锁
deadlock_state DeadLockCheck(MyProc);//检测死锁如果产生了实边死锁将当前进程从等待队列中删除
if (deadlock_state DS_HARD_DEADLOCK)//产生实边死锁{RemoveFromWaitQueue(MyProc, LockTagHashCode((MyProc-waitLock-tag)));//将当前进程从等待队列中删除}释放主锁表 for (i NUM_LOCK_PARTITIONS; --i 0;)LWLockRelease(LockHashPartitionLockByIndex(i));//释放所有的锁DeadLockCheck
检查给定的进程上是否产生了死锁如果是虚边死锁会通过调整等待队列顺序来尝试解决死锁如果无法解决就会返回DS_HARD_DEADLOCK死锁的详细信息会保存到deadlockDetails[]中。
死锁检测的起点先初始化全局变量 //死锁检测开始位置初始化边相关的全局变量如nCurConstraintsnPossibleConstraints ,nWaitOrders,blocking_autovacuum_proc //死锁检测开始位置初始化边相关的全局变量nCurConstraints 0;nPossibleConstraints 0;nWaitOrders 0;/* Initialize to not blocked by an autovacuum worker */blocking_autovacuum_proc NULL;调用DeadLockCheckRecurse函数查找环如果找到实边死锁直接诶返回死锁 //查找死锁环if (DeadLockCheckRecurse(proc)){int nSoftEdges;TRACE_POSTGRESQL_DEADLOCK_FOUND();nWaitOrders 0;if (!FindLockCycle(proc, possibleConstraints, nSoftEdges))//再次检查一下死锁是否消失若消失表名有错elog(FATAL, deadlock seems to have disappeared);return DS_HARD_DEADLOCK; /* 发现实边死锁*/}遍历每个等待队列将对应锁的等待进程重新添加到锁的等待队列中并尝试唤醒一些可唤醒的进程 for (i 0; i nWaitOrders; i)//遍历每个等待队列{LOCK *lock waitOrders[i].lock;PGPROC **procs waitOrders[i].procs;int nProcs waitOrders[i].nProcs;PROC_QUEUE *waitQueue (lock-waitProcs);ProcQueueInit(waitQueue);//初始化等待队列for (j 0; j nProcs; j){SHMQueueInsertBefore((waitQueue-links), (procs[j]-links));//头插法插入到队列中waitQueue-size;}ProcLockWakeup(GetLocksMethodTable(lock), lock);//查看是否可以唤醒一些进程}如果nWaitOrders不等于0表明还有虚边死锁返回DS_SOFT_DEADLOCK如果是被vacuum进程阻塞住返回DS_BLOCKED_BY_AUTOVACUUM其他情况表明无死锁返回DS_NO_DEADLOCK if (nWaitOrders 0)//有虚边死锁return DS_SOFT_DEADLOCK;else if (blocking_autovacuum_proc ! NULL)//被vacuum阻塞return DS_BLOCKED_BY_AUTOVACUUM;elsereturn DS_NO_DEADLOCK;//无死锁DeadLockCheckRecurse
DeadLockCheckRecurse函数是一个递归过程旨在深入探索并找出有效的执行顺序以避免死锁情况。该函数的主要目的是通过递归的方式检测系统中的死锁状况并尝试找出一个无死锁的执行顺序。它在多进程或多线程环境中特别有用尤其是在涉及到资源共享和锁机制的情况下。 参数说明 curConstraints[]这是一个数组用于保存当前递归层级正在探索的边。随着递归的深入每发现一个新的循环即潜在的死锁条件就会将相应的边添加到这个数组中。waitOrders[]这个数组用于记录需要调整的锁等待队列以达到一个无死锁的状态。如果存在需要调整的队列则通过这个数组指示出来。 返回值 如果函数返回true这意味着经过当前递归层次的探索发现无法找到任何解决方案来避免死锁即系统处于或即将进入死锁状态。如果返回false则意味着已经找到了一种无死锁的执行顺序或调整策略使得所有进程或线程可以在不发生死锁的情况下继续执行。此时waitOrders[]中会包含如何重新排列锁等待队列的具体指导以实现这一目标。 工作原理 该函数通过递归地检查当前的资源分配和锁等待关系识别出所有可能形成环即死锁的前提条件的情况。对于每一个识别到的环函数尝试添加或调整虚边即改变某些进程的等待顺序或优先级以打破潜在的死锁链。这个过程持续进行直到所有可能的死锁情况都被探索完毕或者找到了一个有效的无死锁执行方案。 执行流程如下 调用TestConfiguration检测当前的边的有效性会将探测到的虚边保存到curConstraints数组并返回探测到的虚边数量。
nEdges TestConfiguration(proc);//测试边的有效性返回探测到的虚边数量如果返回的虚边数量小于0表明有实边死锁如果返回的虚边数量等于0表明无死锁如果当前探测到的nCurConstraints大于maxCurConstraints表明超出存储限制了 if (nEdges 0)//有实边死锁return true; /* hard deadlock --- no solution */if (nEdges 0)//无死锁return false; /* good configuration found */if (nCurConstraints maxCurConstraints)//边数量超出限制return true; /* out of room for active constraints? */判断PossibleConstraints中是否有空间若无空间的话就没必要保存探测到的虚边了 if (nPossibleConstraints nEdges MaxBackends maxPossibleConstraints)//有 空间保存可能的边{nPossibleConstraints nEdges;//其实边已经存在possibleConstraints地址后了只不过nPossibleConstraints没更新就会忽略而已savedList true;}else//无空间保存{savedList false;}将探测到的虚边保存到curConstraints然后递归调用该函数判断是否有死锁
curConstraints[nCurConstraints] possibleConstraints[oldPossibleConstraints i];//将探测到的边保存到curConstraintsnCurConstraints;
if (!DeadLockCheckRecurse(proc))//重新检测是否有死锁return false; /* found a valid solution! */TestConfiguration
测试当前配置的有效性。该函数首先会调用ExpandConstraints函数尝试对等待队列进行重排来尝试解除虚边死锁然后继续查找是否存在环如果存在就将虚边保存到possibleConstraints数组中。
定义查保存虚边的地址,即possibleConstraints数组 EDGE *softEdges possibleConstraints nPossibleConstraints;//探测到的虚边都在此地址存放判断possibleConstraints数组是否还有空间 if (nPossibleConstraints MaxBackends maxPossibleConstraints)return -1;尝试调整等待队列 if (!ExpandConstraints(curConstraints, nCurConstraints))//尝试调整等待队列来解除虚边死锁return -1;遍历每个探测到的边尝试根据每个边的waiter和blocker进程查找环并将找到的环中的虚边保存到softEdges中 for (i 0; i nCurConstraints; i){if (FindLockCycle(curConstraints[i].waiter, softEdges, nSoftEdges))//查询等待者进程是否存在环{if (nSoftEdges 0)return -1; /* hard deadlock detected */softFound nSoftEdges;}if (FindLockCycle(curConstraints[i].blocker, softEdges, nSoftEdges))//查询被等待者进程是否存在环{if (nSoftEdges 0)return -1; /* hard deadlock detected */softFound nSoftEdges;}}检测当前进程是否存在环。 if (FindLockCycle(startProc, softEdges, nSoftEdges))//检测当前进程是否存在环 {if (nSoftEdges 0)return -1; softFound nSoftEdges;}FindLockCycleRecurse
递归查找是否存在环查找的原理就是在查找环时先检查待测进程是否在visitedProcs数组中出现过如果没出现过就将待测进程存入到visitedProcs数组中如果出现过而且是在等待队列的起始处则表明出现了死锁的环返回死锁信息。 例如 待测进程在visitedProcs数组中未出现过没有环无死锁 待测进程在visitedProcs数组中出现过存在环但是不在起始处对当前进程而言不算死锁 待测进程在visitedProcs数组中出现过存在环且在起始处存在死锁
判断是否出现环 /*判断是否有环遍历visitedProcs数组如果检查的proc在数组中出现过且是当前的进程表明出现了环*/for (i 0; i nVisitedProcs; i){if (visitedProcs[i] checkProc)//进程重复出现{if (i 0)//是待检测的进程出现了环{nDeadlockDetails depth;return true;}return false;}}如果不存在环将待测进程保存到visitedProcs数组中
visitedProcs[nVisitedProcs] checkProc;//没有检测到环将检测进程存入visitedProcs数组如果要检查的进程处于等待状态那么就递归检测他的等待队列 if (checkProc-links.next ! NULL checkProc-waitLock ! NULL FindLockCycleRecurseMember(checkProc, checkProc, depth, softEdges,nSoftEdges))return true;如果待测进程是锁组中的一部分遍历锁组的每个成员进程检查是否存在环 如果进程没有等待但是是锁组的一部分还是有可能出现等待依赖边尽管这个进程本身没有等待。*/dlist_foreach(iter, checkProc-lockGroupMembers)//遍历每个group成员{PGPROC *memberProc;memberProc dlist_container(PGPROC, lockGroupLink, iter.cur);if (memberProc-links.next ! NULL memberProc-waitLock ! NULL memberProc ! checkProc FindLockCycleRecurseMember(memberProc, checkProc, depth, softEdges,nSoftEdges))//递归检测是否有环return true;}FindLockCycleRecurseMember
递归检查是否存在环。
获取锁的进程锁表即锁模式冲突掩码 lockMethodTable GetLocksMethodTable(lock);//获取锁方法numLockModes lockMethodTable-numLockModes;//获取锁模式数量conflictMask lockMethodTable-conflictTab[checkProc-waitLockMode];//获取与等待的锁模式冲突的掩码遍历检查锁的等待队列的每个进程如果待测进程等待的锁与当前持有的锁模式冲突递归调用FindLockCycleRecurse函数检查是否存在环如果存在返回实边死锁信息。
procLocks (lock-procLocks);//获取进程锁表proclock (PROCLOCK *) SHMQueueNext(procLocks, procLocks,offsetof(PROCLOCK, lockLink));while (proclock)//遍历检查进程的等待队列的每个进程是否有死锁{PGPROC *leader;proc proclock-tag.myProc;leader proc-lockGroupLeader NULL ? proc : proc-lockGroupLeader;if (leader ! checkProcLeader)//同组的不检查{for (lm 1; lm numLockModes; lm)//遍历每一个锁模式{if ((proclock-holdMask LOCKBIT_ON(lm)) (conflictMask LOCKBIT_ON(lm)))//如果出现锁冲突持有的锁与当前进程要等的锁模式冲突实边{if (FindLockCycleRecurse(proc, depth 1,softEdges, nSoftEdges))//递归检查{DEADLOCK_INFO *info deadlockDetails[depth];//有死锁填充死锁相关信息info-locktag lock-tag;info-lockmode checkProc-waitLockMode;info-pid checkProc-pid;return true;}if (checkProc MyProc proc-statusFlags PROC_IS_AUTOVACUUM)//没有死锁但是判断是否有autovacuum进程阻塞我们blocking_autovacuum_proc proc;break;}}}proclock (PROCLOCK *) SHMQueueNext(procLocks, proclock-lockLink,offsetof(PROCLOCK, lockLink));}找到当前锁的等待队列waitOrders[i]然后遍历等待队列的每个进程如果遍历的进程等待的锁模式与待测进程锁模式冲突递归调用FindLockCycleRecurse函数检查是否存在环如果存在则为虚边死锁将虚边保存到possibleConstraints数组中
for (i 0; i nWaitOrders; i)//从等待队列中找到当前锁所在的等待队列{if (waitOrders[i].lock lock)break;}if (i nWaitOrders)//判断是否找到对应的等待队列{PGPROC **procs waitOrders[i].procs;queue_size waitOrders[i].nProcs;for (i 0; i queue_size; i)//遍历等待队列中的每个进程{PGPROC *leader;proc procs[i];leader proc-lockGroupLeader NULL ? proc :proc-lockGroupLeader;if (leader checkProcLeader) break;if ((LOCKBIT_ON(proc-waitLockMode) conflictMask) ! 0)//等待的锁模式与待测进程的锁模式判断是否存在冲突{/* This proc soft-blocks checkProc */if (FindLockCycleRecurse(proc, depth 1,softEdges, nSoftEdges))//递归检查是否存在虚边环{/* fill deadlockDetails[] */DEADLOCK_INFO *info deadlockDetails[depth];//记录虚边死锁信息info-locktag lock-tag;info-lockmode checkProc-waitLockMode;info-pid checkProc-pid;/*即添加到possibleConstraints数组*/Assert(*nSoftEdges MaxBackends);softEdges[*nSoftEdges].waiter checkProcLeader;//保存虚边信息到即添加到possibleConstraints数组数组softEdges[*nSoftEdges].blocker leader;softEdges[*nSoftEdges].lock lock;(*nSoftEdges);return true;}}}}如果waitOrders[i]中不存在当前锁的等待队列找到该锁组的最后一个进程检查他的等待队列的每个进程如果遍历的进程等待的锁模式与待测进程锁模式冲突调用FindLockCycleRecurse函数检查是否存在环如果存在则为虚边死锁将虚边保存到possibleConstraints数组中
else//等待队列中没找到当前进程{PGPROC *lastGroupMember NULL;waitQueue (lock-waitProcs);//查找锁组的最后一个成员if (checkProc-lockGroupLeader NULL)lastGroupMember checkProc;else{proc (PGPROC *) waitQueue-links.next;queue_size waitQueue-size;while (queue_size-- 0){if (proc-lockGroupLeader checkProcLeader)lastGroupMember proc;proc (PGPROC *) proc-links.next;}}queue_size waitQueue-size;proc (PGPROC *) waitQueue-links.next;while (queue_size-- 0)//遍历等待队列查找虚边冲突{PGPROC *leader;leader proc-lockGroupLeader NULL ? proc :proc-lockGroupLeader;/* Done when we reach the target proc */if (proc lastGroupMember)break;if ((LOCKBIT_ON(proc-waitLockMode) conflictMask) ! 0 leader ! checkProcLeader)//锁冲突{if (FindLockCycleRecurse(proc, depth 1,softEdges, nSoftEdges))//检查是否有虚边锁{DEADLOCK_INFO *info deadlockDetails[depth];//报错虚边死锁信息info-locktag lock-tag;info-lockmode checkProc-waitLockMode;info-pid checkProc-pid;softEdges[*nSoftEdges].waiter checkProcLeader;//保存虚边信息到即添加到possibleConstraints数组数组softEdges[*nSoftEdges].blocker leader;softEdges[*nSoftEdges].lock lock;(*nSoftEdges);return true;}}proc (PGPROC *) proc-links.next;}}
无死锁
ExpandConstraints
将边CurConstraints扩展为对受影响等待队列的新排序 即将CurConstraints中的每个边加入到等待队列中然后对等待队列进行拓扑排序 for (i nConstraints; --i 0;)//遍历每个虚边死锁的边{LOCK *lock constraints[i].lock;for (j nWaitOrders; --j 0;)//确认等待队列中是否已经有了它{if (waitOrders[j].lock lock)break;}if (j 0)//没遍历完继续continue;//存入等待队列中waitOrders[nWaitOrders].lock lock;waitOrders[nWaitOrders].procs waitOrderProcs nWaitOrderProcs;waitOrders[nWaitOrders].nProcs lock-waitProcs.size;nWaitOrderProcs lock-waitProcs.size;if (!TopoSort(lock, constraints, i 1,waitOrders[nWaitOrders].procs))//进行拓扑排序return false;nWaitOrders;}TopoSort
当存在虚边环时会对每个虚边调用该函数对等待队列进行重新排序从而尝试解开虚边环。
将要处理的Lock的等待队列存入topoProcs数组中 proc (PGPROC *) waitQueue-links.next;for (i 0; i queue_size; i)//将锁的等待队列中的每个进程都保存到topoProcs数组中{topoProcs[i] proc;proc (PGPROC *) proc-links.next;}初始化beforeConstraints和afterConstraints这两个数组与topoProcs长度相等下面要用 MemSet(beforeConstraints, 0, queue_size * sizeof(int));//初始化这俩变量下面要用MemSet(afterConstraints, 0, queue_size * sizeof(int));遍历每一个虚边 判断虚边的waiter或他的groupleader是否在等待队列中如果在里面根据其在等待队列中的位置将beforeConstraints对应位置值1如果是锁组的成员对应值置为-1如果不在里面跳过当前虚边继续下一循环如果虚边的blocker或他的groupleader是否在等待队列中如果在里面根据其在等待队列中的位置将afterConstraints对应位置值置为其下标值1将该虚边的pred的值置为waiter在等待队列中的位置下标link置为afterConstraints对应位置的值。
for (i 0; i nConstraints; i)//遍历每一个边{proc constraints[i].waiter;Assert(proc ! NULL);jj -1;for (j queue_size; --j 0;)//遍历等待队列中的每个进程与虚边的waiter对比{PGPROC *waiter topoProcs[j];if (waiter proc || waiter-lockGroupLeader proc){//如果waiter等于等待队列中的某个进程或他的组长表示是一个该等待队列相关的边Assert(waiter-waitLock lock);if (jj -1)//是第一个将jj标记为该进程在等待队列中的位置jj j;else//其他的锁组成员标记为-1{Assert(beforeConstraints[j] 0);beforeConstraints[j] -1;}}}if (jj 0)//没有相关的等待者表名与当前锁无关continue;/*同理判断被等待者进程*/proc constraints[i].blocker;Assert(proc ! NULL);kk -1;for (k queue_size; --k 0;)//遍历等待队列中的每个进程与虚边的blocker对比{PGPROC *blocker topoProcs[k];if (blocker proc || blocker-lockGroupLeader proc){//如果blocker等于等待队列中的某个进程或他的组长表示是一个该等待队列相关的边Assert(blocker-waitLock lock);if (kk -1)//是第一个将kk标记为该进程在等待队列中的位置kk k;else//其他的锁组成员标记为-1{Assert(beforeConstraints[k] 0);beforeConstraints[k] -1;}}}if (kk 0)//没有匹配的边说明与当前锁无关continue;Assert(beforeConstraints[jj] 0);beforeConstraints[jj]; /* 如果waiter进程在topoProcs中这里就1*/constraints[i].pred jj;//保存虚边的water在等待队列中的位置constraints[i].link afterConstraints[kk];//指向afterConstraintsafterConstraints[kk] i 1;}开始进行拓扑排序遍历每个等待队列中的进程 从等待队列的尾部开始遍历找到第一个非空的进程如果进程非空且其在beforeConstraints对应位置的值为0时满足排序要求将进程存入到waiterOrder队列中然后将topoProcs中的对应位置置为空。更新beforeConstraints中的值。
last queue_size - 1;for (i queue_size - 1; i 0;)//遍历topoProcs数组反向遍历{int c;int nmatches 0;while (topoProcs[last] NULL)//找到第一个非空的进程last--;for (j last; j 0; j--){if (topoProcs[j] ! NULL beforeConstraints[j] 0)//第一个不在虚边的break;}if (j 0)//遍历完也没有不在虚边的return false;proc topoProcs[j];if (proc-lockGroupLeader ! NULL)//如果是锁组获取其组长proc proc-lockGroupLeader;Assert(proc ! NULL);for (c 0; c last; c){if (topoProcs[c] proc || (topoProcs[c] ! NULL topoProcs[c]-lockGroupLeader proc))//当前进程或当前组长进程{ordering[i - nmatches] topoProcs[c];//存入ordering数组即waitOrders[xx].procstopoProcs[c] NULL;nmatches;}}Assert(nmatches 0);i - nmatches;for (k afterConstraints[j]; k 0; k constraints[k - 1].link)beforeConstraints[constraints[k - 1].pred]--;} 查找环时找到一个虚边环虚边为D-A, 虚边保存在CurContraints 针对该虚边遍历waiterOrders数组中的每个等待队列并进行拓扑排序这里假设有等待队列如下图 遍历等待队列中的每个进程并与边进行比较将符合要求的信息存入beforeConstraints和afterConstraints并更新curContraints的pred和link字段 然后对等待队列进行排序排序后的队列为 这样警告拓扑排序后的等待关系就变成了下图环被消除了从而解决了死锁。
死锁检测示例
下面是根据上面的例子得到的函数运行流程
进程AB C锁Lock1,Lock2Lock1锁等待关系 C-A-BLock2锁等待关系: B -C假设当前进程是A触发的死锁检测。 死锁检测流程如下
* DeadLockCheck
** DeadLockCheckRecurse
*** TestConfiguration(A)
**** FindLockCycleANULL0
***** nVisitedProcs 0;
***** nDeadlockDetails 0;
****** possibleConstraints 0;
***** FindLockCycleRecurseA0NULL0
****** visitedProcs[0] A
****** FindLockCycleRecurseMember(A ,A ,0,NULL,0) //事务A等待的Lock1锁的等待队列
****** Lock1的等待队列是C-A
******* 无实边冲突
******* nWaitOrders0
******* 获取Lock1的等待队列A-C
******* FindLockCycleRecurseC1NULL0
******* visitedProcs[0] A
******* visitedProcs[0] C
******* FindLockCycleRecurseMember(C ,C ,1,NULL,0) //事务C等待的Lock1锁的等待队列
******* Lock1的等待队列是C-A
******** 无实边冲突
******** nWaitOrders0
******** 获取Lock1的等待队列A-C
******** FindLockCycleRecurseA2NULL0
********* visitedProcs[0] A
********* visitedProcs[0] C
********* 在visitedProcs出现过且为起始位置返回死锁ndeadlockDetails2, return true
******** deadlockDetails[0]记录虚边死锁信息
******** possibleConstraints[0]waiterC , blockerA, locklock1 ;nPossibleConstraints1
******** return true
******** return true
******* return true
****** return true
***** return true
**** return 1
*** nPossibleConstraints 1
*** curConstraints[0]possibleConstraints[0]waiterC , blockerA, locklock1
*** nCurConstraints
*** DeadLockCheckRecurse(A)
**** TestConfiguration(A)
***** ExpandConstraints(curConstraints,1)
****** nWaitOrders
****** waitOrders[0]locklock1, procswaitOrderProcs nWaitOrderProcs ,nprocs2
****** nWaitOrderProcs 2 2
****** TopoSort(lock1,curConstraints,2,waitOrderProcs)
******* topoProcs[0] A
******* topoProcs[1] C
******* beforeConstraints[0] 0
******* beforeConstraints[1] 1
******* afterConstraints[0] 1
******* afterConstraints[1] 0
******* curConstraints[0].pred 1
******* curConstraints[0].link 0
******* 开始拓扑排序
******* 第一次找到进程A
******* waitOrderProcs[1] A
******* 第二次找到进程C
******* waitOrderProcs[0] C
******* 最终虚边顺序调整
******* return true
****** nWaitOrders
****** return true
***** FindLockCycle(curConstraints[i].waiterC, softEdges, nSoftEdges1)
****** nVisitedProcs 0;
****** nDeadlockDetails 0;
****** possibleConstraints 0;
****** FindLockCycleRecurseC0NULL0
******* visitedProcs[0] C
******* FindLockCycleRecurseMember(C ,C ,0,NULL,0) //事务A等待的Lock1锁的等待队列
******** Lock1的等待队列是C-A
******** 无实边冲突
******** nWaitOrders1
******** FindLockCycleRecurseA1NULL0
********* visitedProcs[0] C
********* visitedProcs[1] A
********* FindLockCycleRecurseMember(A ,A ,0,NULL,0) //事务A等待的Lock1锁的等待队列
********** Lock1的等待队列是C-A
********** 无实边冲突
********** nWaitOrders1
********** break;
********** return false
********* return false
******** return false
******* return false
****** return false
***** FindLockCycle(curConstraints[i].blockerA, softEdges, nSoftEdges1)
***** FindLockCycle(A, softEdges, nSoftEdges1))
****** FindLockCycleRecurseA1NULL0
******* visitedProcs[0] A
******* FindLockCycleRecurseMember(A ,A ,0,NULL,0) //事务A等待的Lock1锁的等待队列
******** Lock1的等待队列是C-A
******** 无实边冲突
******** nWaitOrders1
******** break;
******** return false
******* return false
****** return false
***** return 0
**** return false 无死锁
*** return false
** nWaitOrders1
** 根据排序后的waitOrders重排Lock1的等待队列为A-C
** 唤醒可以被唤醒的进程。
** return DS_SOFT_DEADLOCK 有虚边死锁
* done【参考】
《PostgreSQL数据库内核分析》《Postgresql技术内幕-事务处理深度探索》《PostgreSQL指南内幕探索》pg14源码 文章转载自： http://www.morning.flqkp.cn.gov.cn.flqkp.cn http://www.morning.ylqpp.cn.gov.cn.ylqpp.cn http://www.morning.nmhpq.cn.gov.cn.nmhpq.cn http://www.morning.mrbzq.cn.gov.cn.mrbzq.cn http://www.morning.tfkqc.cn.gov.cn.tfkqc.cn http://www.morning.znsyn.cn.gov.cn.znsyn.cn http://www.morning.hjwzpt.com.gov.cn.hjwzpt.com http://www.morning.xtkw.cn.gov.cn.xtkw.cn http://www.morning.zyytn.cn.gov.cn.zyytn.cn http://www.morning.qflcb.cn.gov.cn.qflcb.cn http://www.morning.wjndl.cn.gov.cn.wjndl.cn http://www.morning.dxgt.cn.gov.cn.dxgt.cn http://www.morning.rszbj.cn.gov.cn.rszbj.cn http://www.morning.lcbnb.cn.gov.cn.lcbnb.cn http://www.morning.ztrht.cn.gov.cn.ztrht.cn http://www.morning.dqpnd.cn.gov.cn.dqpnd.cn http://www.morning.rxnl.cn.gov.cn.rxnl.cn http://www.morning.qljxm.cn.gov.cn.qljxm.cn http://www.morning.hmpxn.cn.gov.cn.hmpxn.cn http://www.morning.jgncd.cn.gov.cn.jgncd.cn http://www.morning.kxbdm.cn.gov.cn.kxbdm.cn http://www.morning.ychrn.cn.gov.cn.ychrn.cn http://www.morning.krwzy.cn.gov.cn.krwzy.cn http://www.morning.jzkqg.cn.gov.cn.jzkqg.cn http://www.morning.shsh1688.com.gov.cn.shsh1688.com http://www.morning.rscrj.cn.gov.cn.rscrj.cn http://www.morning.qmbgb.cn.gov.cn.qmbgb.cn http://www.morning.nqfxq.cn.gov.cn.nqfxq.cn http://www.morning.rrgm.cn.gov.cn.rrgm.cn http://www.morning.rpkl.cn.gov.cn.rpkl.cn http://www.morning.sgmis.com.gov.cn.sgmis.com http://www.morning.nkjpl.cn.gov.cn.nkjpl.cn http://www.morning.qhtlq.cn.gov.cn.qhtlq.cn http://www.morning.cprbp.cn.gov.cn.cprbp.cn http://www.morning.bxyzr.cn.gov.cn.bxyzr.cn http://www.morning.gmztd.cn.gov.cn.gmztd.cn http://www.morning.bpwfr.cn.gov.cn.bpwfr.cn http://www.morning.yhdqq.cn.gov.cn.yhdqq.cn http://www.morning.dppfh.cn.gov.cn.dppfh.cn http://www.morning.mcmpq.cn.gov.cn.mcmpq.cn http://www.morning.qflwp.cn.gov.cn.qflwp.cn http://www.morning.alwpc.cn.gov.cn.alwpc.cn http://www.morning.sh-wj.com.cn.gov.cn.sh-wj.com.cn http://www.morning.tkyxl.cn.gov.cn.tkyxl.cn http://www.morning.rzrbw.cn.gov.cn.rzrbw.cn http://www.morning.xrlwr.cn.gov.cn.xrlwr.cn http://www.morning.wjhdn.cn.gov.cn.wjhdn.cn http://www.morning.bnpcq.cn.gov.cn.bnpcq.cn http://www.morning.ybgyz.cn.gov.cn.ybgyz.cn http://www.morning.dpqqg.cn.gov.cn.dpqqg.cn http://www.morning.htsrm.cn.gov.cn.htsrm.cn http://www.morning.stwxr.cn.gov.cn.stwxr.cn http://www.morning.rrqgf.cn.gov.cn.rrqgf.cn http://www.morning.ysgnb.cn.gov.cn.ysgnb.cn http://www.morning.rahllp.com.gov.cn.rahllp.com http://www.morning.wwnb.cn.gov.cn.wwnb.cn http://www.morning.rrcxs.cn.gov.cn.rrcxs.cn http://www.morning.srjbs.cn.gov.cn.srjbs.cn http://www.morning.qrpx.cn.gov.cn.qrpx.cn http://www.morning.hwbf.cn.gov.cn.hwbf.cn http://www.morning.fbdkb.cn.gov.cn.fbdkb.cn http://www.morning.zqcgt.cn.gov.cn.zqcgt.cn http://www.morning.rljr.cn.gov.cn.rljr.cn http://www.morning.ryxdr.cn.gov.cn.ryxdr.cn http://www.morning.xctdn.cn.gov.cn.xctdn.cn http://www.morning.ydnxm.cn.gov.cn.ydnxm.cn http://www.morning.fjkkx.cn.gov.cn.fjkkx.cn http://www.morning.mm27.cn.gov.cn.mm27.cn http://www.morning.fhykt.cn.gov.cn.fhykt.cn http://www.morning.qichetc.com.gov.cn.qichetc.com http://www.morning.xphls.cn.gov.cn.xphls.cn http://www.morning.rgzc.cn.gov.cn.rgzc.cn http://www.morning.hpspr.com.gov.cn.hpspr.com http://www.morning.qswws.cn.gov.cn.qswws.cn http://www.morning.lkkkf.cn.gov.cn.lkkkf.cn http://www.morning.nmfml.cn.gov.cn.nmfml.cn http://www.morning.qzpsk.cn.gov.cn.qzpsk.cn http://www.morning.zzbwjy.cn.gov.cn.zzbwjy.cn http://www.morning.qxkjy.cn.gov.cn.qxkjy.cn http://www.morning.bkqdg.cn.gov.cn.bkqdg.cn
