判断死锁的公式(一)

死锁总概在两个或多个任务中，如果每个任务锁定了其他任务试图锁定的资源，此时会造成这些任务永久阻塞，从而出现死锁。

若无外力作用,它们都将无法推进下去.这些永远在互相等待的进程称为死锁进程.死锁的四个必要条件：互斥，占有且等待，循环等待。

进程的死锁问题可以用有向图进行准备而形象的描述,这种有向图称为系统资源分配图.一个系统资源分配图SRAG可定义为一个二元组,即SRAG=(V,E),其中V是顶点的集合,而E是有向边的集合.顶点集合可分为两种部分:P=(P1,P2,…Pn),是由系统内的所有进程组成的集合,每一个Pi代表一个进程;R=(r1,r2,…rm),是系统内所有资源组成的集合,每一个ri代表一类资源.基于上述资源分配图的定义,可给出判定死锁的法则,又称为死锁定理.(1) 如果资源分配图中没有环路,则系统没有死锁(2) 如果资源分配图中出现了环路,则系统中可能存在死锁.预防死锁的方法：资源一次性分配：（破坏请求和保持条件）可剥夺资源：即当某进程新的资源未满足时，释放已占有的资源（破坏不可剥夺条件）资源有序分配法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反（破坏环路等待条件）所以，在系统设计、进程调度等方面注意如何不让这四个必要条件成立，如何确定资源的合理分配算法，避免进程永久占据系统资源。

此外，也要防止进程在处于等待状态的情况下占用资源,在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。

因此，对资源的分配要给予合理的规划。

其中一个比较好的死锁避免算法是，银行家算法：当第i个进程需要请求系统资源时，我们就将其对各个资源的需求量送入Re数组中，然后系统依次执行。

(1)若j从1到M，所有Re(j)＜=Need(i，j)，则程序可继续，否则说明i进程的这次请求数量，超出了事先给定的它对Rj资源的最大需求，转出错处理。

⼀种简单的死锁检测算法1.死锁检测给定⼀组线程操作锁的流程，判断是否会发⽣死锁？例如:有两个线程和两个资源，线程对锁的操作如下:其中T表⽰线程id，L表⽰锁id，S表⽰操作(1表⽰获取锁，0表⽰释放锁)T L S1 1 1(线程1获取1号锁)2 2 2(线程2获取2号锁)1 2 1(线程1获取2号锁，保持等待)2 1 1(线程2获取1号锁，导致死锁)如果最后⼀次操作换为:2 2 0，就不会死锁.问题的关键是如何判断死锁的发⽣，以上⾯的例⼦为例：线程2获取1号锁时，发现1号锁被1号线程占⽤，那么就要等待线程1释放1号锁，然后再看线程1在等待2号锁，2号锁被2号线程占⽤，因此1号线程⼜要等2号线程释放2号锁，这就形成了⼀个等待环：线程2->线程1->线程2，发⽣死锁.所以检测死锁的⽅法就是判断是否存在这种等待的环路.对于给定的线程操作锁的序列：vector<vector<int>> tls，判断是否发⽣死锁要维护3个map,map<int, int> lock2thread:锁->线程，标识当前锁被哪个线程占⽤map<int, int> waitedthread2lock:标识当前线程在等待哪个锁map<int, vector<int>> thread2locks：标识线程持有的锁.伪代码如下（省去了⼀些更新和查询操作）：bool DeadLock(vector<vector<int>> &tls) {int size = tls.size();map<int, int> lock2thread;map<int, int> waitedthread2lock;map<int, vector<int>> thread2locks;for(int i = 0; i < size; i++) {int tid = tls[i][0];int lock = tls[i][1];int state = tls[i][2];if (state == 0) {//释放锁，这是⼀定不会引起死锁的，因此只需要更新3个map就可以了//1.从lock2thread中删除key==lock的元素lock2thread.erase(lock2thread.find(lock));//2.从thread2locks中移除lockthread2locks[tid].erase(find(thread2locks[tid].begin(), thread2locks[tid].end(),lock));//3.遍历waitedthread2lock，查看哪个线程等待lock//3.1如果有线程等待此lock，那么依次更新lock2thread和thread2locks} else {//说明tid想要获取lock，那么这个操作是可能导致死锁的if (lock2thread.find(lock) != lock2thread.end()) {//说明该锁已经被占⽤，那么可能引起死锁int nexttid = 0;//当前线程依赖的下⼀个线程int nextlock = lock;while(1) {nexttid = lock2thread[nextlock];if (nexttid == tid) return true;//发⽣死锁//查看nexttid在等待哪个资源if (waitedthread2lock.find(nexttid) != waitedthread2lock.end()) {nextlock = waitedthread2lock[nexttid];} else {//说明没有环路，不发⽣死锁更新waitedthread2lock;break;}}} else {//说明lock空闲，直接获取更新lock2thread和thread2locks;}}}}2.死锁预防：银⾏家算法思路很简单，只有当资源池中有充⾜的资源时才将资源分配给进程，否则便认为可能存在死锁的风险.具体可参考这篇简单明了的⽂章：。

死锁百科名片所谓死锁：是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。

此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

由于资源占用是互斥的，当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继续运行，这就产生了一种特殊现象死锁。

deadlocks（死锁）死锁的规范定义：集合中的每一个进程都在等待只能由本集合中的其他进程才能引发的事件，那么该组进程是死锁的。

一种情形，此时执行程序中两个或多个线程发生永久堵塞（等待），每个线程都在等待被其他线程占用并堵塞了的资源。

例如，如果线程A锁住了记录1并等待记录2，而线程B锁住了记录2并等待记录1，这样两个线程就发生了死锁现象。

计算机系统中，如果系统的资源分配策略不当，更常见的可能是程序员写的程序有错误等，则会导致进程因竞争资源不当而产生死锁的现象。

在两个或多个任务中，如果每个任务锁定了其他任务试图锁定的资源，此时会造成这些任务永久阻塞，从而出现死锁。

例如：事务A 获取了行 1 的共享锁。

事务 B 获取了行 2 的共享锁。

现在，事务 A 请求行 2 的排他锁，但在事务 B 完成并释放其对行 2 持有的共享锁之前被阻塞。

现在，事务 B 请求行 1 的排他锁，但在事务 A 完成并释放其对行 1 持有的共享锁之前被阻塞。

事务 B 完成之后事务 A 才能完成，但是事务 B 由事务 A 阻塞。

该条件也称为循环依赖关系：事务 A 依赖于事务B，事务 B 通过对事务 A 的依赖关系关闭循环。

除非某个外部进程断开死锁，否则死锁中的两个事务都将无限期等待下去。

Microsoft SQL Server 数据库引擎死锁监视器定期检查陷入死锁的任务。

如果监视器检测到循环依赖关系，将选择其中一个任务作为牺牲品，然后终止其事务并提示错误。

这样，其他任务就可以完成其事务。