死锁的总结

哲学家死锁造成的原因：我有你需要的，但你已经有了

饥饿与死锁的区别

死锁一旦发生一定又饥饿现象，但是饥饿现象产生不一定是死锁

历史上对于死锁的声音

死锁的方案

前面两个都是不允许死锁出现

前面都是概念性的东西

后面我们研究如何破坏死锁

保守派思想：

保守派是如何解决死锁的，根据前面，我们知道他们的思想是从源头切断死锁的出现

我们根据锁的特性进行判断

第一个互斥使用，如果我们让进程之间不互斥使用，那么如果有相同堆的资源，我们可以共享的，那么可能会出现数据冲突。

第二个不可剥夺，如果进程内的资源可以被任意抢夺，那么如果一个进程在运行，那么资源被随意抢占了，如何确保资源不会出错，就算保存资源，那么大量的进程切换一样会浪费大量资源。

第三个占有和等待，如果p1进程一直占用p2进程想要的资源，那么我将p1进程中p2需要的资源释放出来，让给p2，这样就可以解决p1占用资源和p2一直等待资源的问题，这个模型貌似是可行的。

第四个循环等待，和上面那个差不多，其他资源被占用，导致有进程一直循环等待资源释放，但这里的循环等待是一直循环等待，根本拿不到资源，解决掉他也能解决死锁。

上面这些特性有两个貌似是可以从根源上解决死锁的，但我们发现如果根据这些特性去编写程序，那么自由度，以及开发成本会直线上升，这不符合商业逻辑。

进步派思想：

死锁的避免

安全算法

我们先学一个银行杠杆模型

银行给借款人一个credits，达到credits立刻还款。

下图推演过程

假设一开始我们借给tom3万，bob4万，银行还剩三万。

我们需要推演，ben现在是否能向银行申请一万的借款

ben现在向银行申请一万的借款，那么银行批准之后，再向tom借款两万，立刻回笼五万。

回笼五万又向bob借款四万，立刻回笼八万。

然后银行借给ben6万，回笼7万。

最后得到ben可以得到这一万的借款。

注：给ben申请之后，需要严格按照推演流程进行贷款（这里不考虑借贷人是否有还款能力）。

假设ben要申请两万，那么银行会否让ben申请呢？

这个情况下银行应该是不会借给ben钱，而且会要求ben降额。

我们可以根据前面的模型将银行抽象成系统，将钱抽象成资源。

演算过程就是算法。

 

 

安全状态

我们需要给进步派思想的安全状态做个定义

我这里翻译一下第一句，可能不太准确。

在某一个特定的顺序，每个进程都能拿到它所需要的最大资源量，且避免出现死锁的情况，那么这个系统的状态就是安全的。正式一点来说，当且仅当存在一个安全的进程序列。

总之安全状态就是在一个状态下，有一串进程序列运行，这些进程不会产生死锁

不安全状态就是这个进程序列运行时会产生死锁。

我们需要根据银行算法来寻找这个系统存在的安全序列，去运行特定的程序。

 

银行家算法数据结构

 

 

我们根据max（需要的）的矩阵减去allocation（已有的）得到need矩阵，得到进程执行需要的资源矩阵。

算法如下

第一步：我们可以找到332资源可以先分配给p1和p3，我们先选择从p1开始

第二步：我们为将资源分配给p1，然后返回332+200等到可用资源532

第三步：532可以分配给p3和p4，我们选择p3

第四步：532分配给p3，我们得到532+211=743，现在我们需要的所有资源都可以被分配了，也就不需要继续向下分析了，大家可以自己分析一下。

我们可以根据上面的分析证明这个系统不止一个安全序列

这里我们要注意如果系统进程算法是可抢夺的，如果执行这条进程序列时有外部进程进来，系统会从插入的地方开始继续计算是否让这个进程插入序列。

此算法的优缺点

 

 

缺点最明显的就是顺序是固定的，我们前面研究了司机和售票员进程，售票员的进程是不可以在司机前的，所以如果是这个算法就有问题，其次就是运行前要用大量资源，以及进入系统的进程个数资源（进程序列）是规定好的，如果有新的进程进来，重新算又要耗费资源。

上面的算法模型是理论模型

佛系派

允许死锁发生，发生系统去解锁（系统去检测）。

 

死锁发生检测并解锁

用图例分析锁

第一个图p3执行完将资源归还给R4和R2，p2拿到p3归还的R2，p2执行完将资源归还给R1和R3，p1拿到p2归还给R1的资源，p1执行完归还R1和R3的资源，无环无锁。

第二个图p3得不到R3的资源无法归还R2，p2拿不到R2的资源无法归还R3，p1拿不到R1的资源无法归还R3，反之亦然，这里可以看出有环且有死锁。

第三个图大家自己分析一下

环

 

图例申请和分配简化

 

 

初步分析

p1无法消去，因为有一个申请边资源被占用

p2可以消去

p3和p1一样

p4可以消去

 

消去p4和p2的边可以得到，p1和p3也可以消去。

 

上面的各节点可以叫做孤立节点

 

死锁定理

学习完上面的这些理论，我们再对死锁的解决办法进行总结

讲了这么多我们如何解除死锁

如果我们不检测、解开死锁，会产生更多死锁，然后系统崩溃，需要重启

最后一句虽然这个方法并非可行方案，但是这个方法被广泛应用

死锁发生的概率是很少的