死锁
假设有一组事务{T1,T2,T3,...,Tn},其中每个事务都在等待该集合中的另一个事务,这时该事务中的每个事务都无法进行下一步动作,这种现象定义为死锁.
处理死锁大致有两种方法.如果系统进入死锁的概率相对较高,则通常使用死锁预防机制;否则,使用检测与恢复机制更有效.
-
死锁预防: 保证系统永远不会进入死锁状态. -
死锁检测: 事务定时对获得锁的事务和等待中的事务做检测,如果检测到死锁,则终止其中一个事务.
死锁检测
检测系统算法周期性地激活,判断有无死锁发生,如果发生死锁,则系统必须尝试从死锁中恢复.死锁可以用称为等待图的有向图精确描述,顶点表示系统中的事务,边(T1-->T2)表示事务 T1 在等待事务 T2 释放所需数据项.当前仅当等待图包含环时,系统中存在死锁.
-
直接等待
假设事务T1等待事务T2,使用有向图边来表示(T1-->T2),事务T2等待事务T3(T2-->T3),事务T3等待事务T1(T3-->T1);
死锁检测就是在事务等待有向图中找“环”的过程.如上有向图(T1-->T2-->T3-->T1)产生了环,系统中存在死锁.
以上示例中事务T1等待事务T2(T1-->T2),事务 T2 已持有锁,我们将这种等待构成的边定义为实边.针对这种硬边构成的环通过中断某个运行事务的方式打破环.
-
间接等待
假设在申请 A 资源中,事务 T1 已经持有 A 资源对应的锁.事务 T2 进入等待 A 资源的等待队列中,此后,事务 T3 也需要申请 A 资源,进入等待队列中,形成链式间接等待(T3-->T2-->T1).这种 T3,T2 都没有持有锁的等待称为软边(softedge),也就是目前暂时还没有形成，但是后续将会形成的等待关系的边。
针对这种类型的环,可以尝试通过调整等待顺序实现打破环形等待,从而不用终止任何事务就能避免死锁.
死锁检测触发机制
PG 中,在会话(backend)启动时,每个会话都会注册一个死锁检测定时器,该定时器基于SIGALRM 信号处理机制实现.会定时唤醒,会话(backend),从而进行死锁检测.
/** 注册后端进程的超时处理函数** 功能:* 为不同类型的超时事件注册对应的处理函数** 注册的超时类型包括:* - DEADLOCK_TIMEOUT: 死锁检测超时* - LOCK_TIMEOUT: 锁等待超时** 注意事项:* - 仅在非bootstrap模式下注册* - 每个超时类型都有独立的处理函数* - 这些处理函数将在对应超时发生时被调用*/if (!bootstrap){RegisterTimeout(DEADLOCK_TIMEOUT, CheckDeadLockAlert);RegisterTimeout(LOCK_TIMEOUT, LockTimeoutHandler);}
CheckDeadLockAlert 为注册后端进程的死锁检测超时处理函数.在后端会话进入锁等待后(ProcSleep),CheckDeadLockAlert会调用 SetLatch 唤醒等待锁进程进行死锁检测.
/** CheckDeadLockAlert - 处理死锁超时到期的信号处理函数** 功能:* 1. 设置死锁超时标志(got_deadlock_timeout)* 2. 设置进程latch以唤醒等待进程* 3. 保存和恢复errno以避免信号处理影响主程序** 注意事项:* - 运行在信号处理上下文中，必须非常小心* - 即使handle_sig_alarm已经设置了latch，这里仍需再次设置* - 当在procsignal_sigusr1_handler()中调用时，handler会在之后再次设置latch*/voidCheckDeadLockAlert(void){int save_errno = errno;got_deadlock_timeout = true;// 设置死锁超时标志/** Have to set the latch again, even if handle_sig_alarm already did. Back* then got_deadlock_timeout wasn't yet set... It's unlikely that this* ever would be a problem, but setting a set latch again is cheap.** Note that, when this function runs inside procsignal_sigusr1_handler(),* the handler function sets the latch again after the latch is set here.*//* 设置进程latch以唤醒等待进程 */SetLatch(MyLatch);errno = save_errno;}
死锁检测流程
死锁检测入口函数为CheckDeadLock,CheckDeadLockAlert 一旦被触发,ProcSleep 就会被唤醒进行死锁检测,详细如下所示,如果没有死锁 ProcSleep 再次进入睡眠状态.
do{if (InHotStandby) //热备模式下的锁冲突处理逻辑{}else // 非热备模式下的锁等待处理逻辑{// 1. 使用WaitLatch等待锁被授予或超时// - WL_LATCH_SET: 等待latch被设置// - WL_EXIT_ON_PM_DEATH: 如果postmaster进程终止则退出// - 0: 无超时时间(由外部超时机制控制)// - PG_WAIT_LOCK: 等待类型为锁等待(void) WaitLatch(MyLatch, WL_LATCH_SET | WL_EXIT_ON_PM_DEATH, 0,PG_WAIT_LOCK | locallock->tag.lock.locktag_type);// 2. 重置latch状态，准备下一次等待ResetLatch(MyLatch);// 3. 检查是否触发了死锁检测超时if (got_deadlock_timeout){// 执行死锁检测CheckDeadLock();// 重置死锁超时标志got_deadlock_timeout = false;}}} while (myWaitStatus == PROC_WAIT_STATUS_WAITING);
死锁检测实现CheckDeadLock
每个会话(backend)都会执行死锁检测,因此CheckDeadLock 只关心当前会话是否会构成环.
等待图中节点由PGPROC(会话 backend)表示,边由 EDGE 结构体表示.EDGE 由等待者PGPROC和被等待者PGPROC构成.
//EDGE - 死锁检测中的等待边结构体//用于表示等待图中的一条边，描述进程间的等待关系typedef struct{//(等待者)等待锁的进程组领导者指针PGPROC *waiter; /* the leader of the waiting lock group *///(被等待者)阻塞waiter的进程组领导者指针PGPROC *blocker; /* the leader of the group it is waiting for *///被等待的锁对象指针LOCK *lock; /* the lock being waited for *///拓扑排序工作区，记录前驱节点索引int pred; /* workspace for TopoSort *///拓扑排序工作区，用于链接后继节点int link; /* workspace for TopoSort */} EDGE;
CheckDeadLock 执行流程如下所示:
-
获取所有锁分区的排他锁(按分区号顺序避免死锁) -
检查是否已被其他进程唤醒(通过检查等待队列链接) -
调用DeadLockCheck检测给定进程是否涉及死锁 -
如果检测到死锁:
-
从等待队列移除当前进程 -
设置等待状态为PROC_WAIT_STATUS_ERROR
-
释放所有锁分区锁(按逆序释放)
static voidCheckDeadLock(void){// 1.循环获取NUM_LOCK_PARTITIONS个锁分区的排他锁// 必须按分区号顺序获取，避免LWLock死锁;形成临界区，防止被cancel/die中断for (i = 0; i < NUM_LOCK_PARTITIONS; i++)LWLockAcquire(LockHashPartitionLockByIndex(i), LW_EXCLUSIVE);/* 2.检查进程链接状态判断是否已被唤醒 */// 如果links.prev或links.next为NULL，表示已从等待队列移除// 直接跳转到check_done标签释放锁if (MyProc->links.prev == NULL ||MyProc->links.next == NULL)goto check_done;// 3.检测给定进程是否涉及死锁，尝试通过重新排列等待队列来解决死锁// 如果无法解决则返回DS_HARD_DEADLOCK，调用者应中止该进程的事务deadlock_state = DeadLockCheck(MyProc);/* 检测到无法解决的死锁，只能通过ERROR退出(硬死锁) */if (deadlock_state == DS_HARD_DEADLOCK){// 4.从等待队列中移除当前进程// RemoveFromWaitQueue会将MyProc->waitStatus设置为PROC_WAIT_STATUS_ERROR，// ProcSleep引发的错误会导致事务中止，从而释放我们持有的其他锁，允许其他进程被唤醒RemoveFromWaitQueue(MyProc, LockTagHashCode(&(MyProc->waitLock->tag)));}// 5.确保在死锁检测完成后正确清理锁资源check_done:for (i = NUM_LOCK_PARTITIONS; --i >= 0;)LWLockRelease(LockHashPartitionLockByIndex(i));}
每一个进程进入死锁检测函数时,都会从当前进程出发,向自己依赖的等待关系进行深度优先搜索,同时构造等待图,有三种可能的结果:
-
没有环路,不存在死锁 - 有环路，但环路没有回到起点
对于这种情况，取消当前进程不会对解除死锁有任何帮助，应当等 P2 进程发生死锁超时触发死锁检测时，从 P2 进程出发检测到一个回到 P2 的环路，P2 进程才会尝试回滚自己的事务，破坏这个环路。
- 有环路，且环路回到了起点 (当前进程).
对于这种情况,死锁检测算法会报告出现死锁。在后续处理中，通过取消当前进程的事务来破坏环路，解决死锁。
具体探测是否有环的方法为在深度优先搜索过程中记录已经访问过的节点数组,当要检查新的节点时,将其与已访问数据进行比较,如果已经包含在已访问数组中,则说明存在环,具体代码如下:
static boolFindLockCycleRecurse(PGPROC *checkProc,int depth,EDGE *softEdges, /* output argument */int *nSoftEdges) /* output argument */{int i;dlist_iter iter;/** 如果当前进程属于锁组，则检查其领导者进程*/if (checkProc->lockGroupLeader != NULL)checkProc = checkProc->lockGroupLeader;/** 检查当前进程是否已被访问过* 遍历已访问进程数组visitedProcs，查找是否包含当前检查的进程checkProc*/for (i = 0; i < nVisitedProcs; i++){// 包含当前检查进程checkProcif (visitedProcs[i] == checkProc){/** 如果回到了起始点(i==0)，说明检测到死锁环(因为checkProc是首先被加入visitedProcs)*/if (i == 0){Assert(depth <= MaxBackends);nDeadlockDetails = depth;return true; // 返回true表示检测到死锁}/** 如果检测到环但不是起始点，说明是局部环(没有回到起点)* 这种情况不构成死锁，返回false*/return false;}}/** 标记当前进程为已访问状态* 1. 将当前检查的进程checkProc加入已访问进程数组visitedProcs* 2. 递增已访问进程计数器nVisitedProcs*/Assert(nVisitedProcs < MaxBackends);visitedProcs[nVisitedProcs++] = checkProc;}
死锁检测算法深度优先搜索
相比于普通的深度优先搜索有所不同,PG 中存在软边和硬边两种不同的概念,前面已经介绍.所以相关算法也会有所不同.
下面通过一个示例说明软边和硬边, P1 正持有Lock A;P2 请求持有 Lock A进入等待队列;P3 请求持有 Lock A进入等待队列Lock A: P3-->P2-->P1(持有).根据软边和硬件的定义,从 P2 到 P1，从 P3 到 P1，各有一条 hard edge.P3 到 P2 之间形成了一条 soft edge.
下面介绍 PG 构建有向图以及软边、硬边示例,图中实线为硬边、虚线为软边.PG 采用分阶段的深度优先搜索方法查找是否包含环,第一阶段只遍历硬边,当存在环直接返回;如果不存在环,第二阶段遍历软边,查看是否存在环.
如下图所示,如果环中包含软边,重新安排锁等待队列中进程的顺序。如果新的锁等待次序能够消除图中的环路，那么自身事务就无需回滚。如下示例,P1-->P8 为死锁环中的软边;当调整其顺序为(P7<--P1<--P8),那么就消除了P1-->P8 这条软边,从而破除了软死锁.该逻辑主要在ExpandConstraints/TopoSort 函数中实现.
下面为深度遍历代码简述,重点对分阶段深度搜索进行介绍.
static boolFindLockCycleRecurseMember(PGPROC *checkProc,PGPROC *checkProcLeader,int depth,EDGE *softEdges, /* output argument */int *nSoftEdges) /* output argument */{PGPROC *proc;//当前检查进程正在等待的锁对象//从checkProc->waitLock获取，表示该进程被阻塞等待的锁LOCK *lock = checkProc->waitLock;//遍历持有该锁的所有进程锁(PROCLOCK)结构procLocks = &(lock->procLocks);//从procLocks队列头开始遍历proclock = (PROCLOCK *) SHMQueueNext(procLocks, procLocks,offsetof(PROCLOCK, lockLink));while (proclock){/* 当前进程硬阻塞检测进程 */if (FindLockCycleRecurse(proc, depth + 1,softEdges, nSoftEdges)){return true;}proclock = (PROCLOCK *) SHMQueueNext(procLocks, &proclock->lockLink,offsetof(PROCLOCK, lockLink));}//没有找到实边构成的环//开始找包含虚边的环,先尝试找到一个等待队列PGPROC *lastGroupMember = NULL; //查找等待队列中当前锁组的最后一个成员/* 使用实际的锁等待队列顺序 */waitQueue = &(lock->waitProcs);/* 重新扫描等待队列以识别软冲突 */queue_size = waitQueue->size;proc = (PGPROC *) waitQueue->links.next;while (queue_size-- > 0){/* 获取当前进程的锁组领导者 */PGPROC *leader;/* 当到达目标进程时结束扫描 */if (proc == lastGroupMember)break;/* 当前进程软阻塞检测进程 */if (FindLockCycleRecurse(proc, depth + 1,softEdges, nSoftEdges)){/* 将这条边添加到死锁环的软边列表中 */Assert(*nSoftEdges < MaxBackends);softEdges[*nSoftEdges].waiter = checkProcLeader;softEdges[*nSoftEdges].blocker = leader;softEdges[*nSoftEdges].lock = lock;(*nSoftEdges)++;return true;}proc = (PGPROC *) proc->links.next;}return false;}