OS——死锁的避免与银行家算法

OS——死锁的避免与银行家算法

最近一直在忙申请外宿的事情，挺多天没写博客了，其实根本原因是因为数据结构最近进度趋于停滞，OS还好，昨天把死锁这部分看完了，其中死锁的避免这一块格外重要，所以今天就把它拿出来说一说。

安全状态与不安全状态

首先来看，什么是状态即当前给进程分配的资源情况称为系统的状态，而系统状态又分为安全状态和不安全状态，我们先来看安全状态：

安全状态即系统能按某种进程推进顺序，为每个进程分配所需资源，直至满足每个进程对资源的最大需求，使每个进程都顺利完成。若能找到这样的推进顺序，称其为安全序列，若找不到，则系统处于不安全状态。

定义总是这样枯燥且难懂，所以我们还是举栗子🌰，结合例子再来回归定义：

假设你是一个手持100元资金的银行家，有三个企业想找你贷款，分别是企业B，企业A和企业T，企业B表示最多借70元，企业A表示最多借40元，企业T表示最多借50元，然而江湖中有个做梦也不敢这么玩的规矩：如果你向企业借的钱达不到企业的最大借钱需求，那么你之前向企业借的钱就都拿不回来了。刚开始，BAT企业分别借走了20元，10元，30元。

通过最大需求 - 已借走 ，我们可以算出每个企业最多还会借多少钱。而我们手中原本有100元，分别借给三个企业一部分后，最后剩余40元。我们不妨来试想这样两种情况：

• 若企业B此时想找你借30元，这能借吗?
  • 此时我们手中还有40元，假设借给B30元，手中还剩余10元，此时如果A或T再向你借，你便没有能力再去借。而且因为借给B的钱没有达到B的最大借钱需求，所以B也不会还钱。
• 若企业A此时想找你借30元，这能借吗？
  • 同样我们若借给企业A30元，此时手里还剩10元，若B或T再向你借，你也没钱再借，但我们可以等企业A还钱，因为此时已经达到了A的最大借钱数，等A还钱后，我们还剩10+40=50元，就有能力借B或T了，只需先借其中一家，它还钱后再借另一家即可。

这样的银行家借钱的问题就像系统中的进程，进程每次都需要拿到全部的资源才会运行，最终运行结束归还，如果没拿到全部的资源就会阻塞自己，且不归还已拿到的资源。

像上述例2中，我们可以找到一种借钱顺序，使最终可以达到三个企业的借钱需求，我们就称这样一种序列为安全序列，所以借给A30元后，系统处于安全状态，但例1中：我们借给B30元后发现找不到一种借钱顺序使我们最终可以满足三个企业的借钱需求，所以我们说借给B企业30元后会导致系统处于不安全状态。

因此可以在资源分配之前先判断这次分配是否会导致系统进入不安全序列，以此来决定是否答应资源的分配请求。

了解了什么是安全状态与非安全状态后，有这样几点是我们需要知道的：

• 安全序列可以不是唯一的：参考例2，等A还钱后我们可以先借给企业B ，也可以先借给企业T，两种顺序都可以使系统处于安全状态
• 系统处于安全状态就一定可以避免死锁
• 系统处于不安全状态未必导致死锁：因为在实际的执行时，进程申请的资源数目不一定达到其最大需求量

银行家算法

银行家又是这位荷兰大佬Dijkstra设计的，原本是为银行系统设计的，后来应用于操作系统中来避免死锁。

核心思想：在进程提出资源申请后，先判断此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就先不答应这次请求，让进程先等待。

问题所在：在银行家借钱问题中，需要的资源只有一个——钱，但在操作系统中，一个进程可能会申请多种资源，该如何把算法从一个资源扩展到多种资源呢？

这里我们引入向量，假设系统中有进程P0，三种资源R0-R2，初始数量为（10,5,7）

那么引入了向量后，我们该如何找出是否有安全序列呢？其实方法和一维的时候相同，这里我们还是先举栗子🌰再说结论：

假设系统中有5个进程P0-P4，三种资源R0-R2，初始数量为（10,5,7），已分配情况如下表：

• 首先，把全部已分配的资源求和可以得到（7,2,5）即当前已经分配出去的资源，用总资源 - 已经分配出去的资源 = （3,3,2），即是当前系统所剩的资源。
• 从P0开始从上往下扫描：判断所剩资源是否满足进程还需要的资源，发现P1是满足的，那我们将资源借给P1，达到P1的最大需求量，待P1还回资源后我们的资源总数班委（5,3,2）即为所剩资源+已分配给P1的资源
• 用同样的方法我们可以依次检查剩余资源是否满足剩余进程的需求，如果满足就将资源分配给他，等他还回来后再重复这样的操作。

以上就是银行家算法的一个基本思想，以及是如何应用到避免死锁，关于代码实现部分就留到下一篇文章啦~