死锁

什么是死锁？

什么是死锁？你们一定知道，看图（原谅我这个gif拍的不怎么漂亮，伪装者24集27分）：

三人互指算不算死锁（斜眼笑），1让2放枪，2说要3先放，3说不放，emmmm，如果不太形象就当看热闹了叭！

还有几个例子可以看看：
哲学家进餐问题：一共五根筷子，五个哲学家 一人拿了一根，死锁了。
还有交通死锁：

所以什么是死锁呢？

• A set of processes is in a deadlocked state when every process in the set is waiting for an event that can be caused only by another process in the set.
• 王凯放下枪的条件是：胡歌放下枪。胡歌放下枪的条件是：王凯放下枪。有意思叭！！！
• 某一个哲学家能吃饭的条件是：另外一个哲学家能先把饭吃完，然后给他一根筷子，可是所有哲学家都只有一根筷子，所以死锁了。
• 某一辆车能行走的条件是：其他车辆走开给它让个道，可是其他车辆也需要另外的车辆走开让道，但是所有车都需要别的车让道，所以死锁了。

如何处理死锁呢？

1.忽略策略

佛性一点：我相信你们不会死锁的！ 那死锁了怎么办？不管它

主流操作系统Linux, Windows都是采用了该策略，发生死锁时，如何操作?交给用户。Windows下我们的方法是打开资源管理器，将无响应的应用杀掉就好了。

看到这里其实下面的内容可以不用看了（滑稽），因为我们的操作系统不会处理死锁的，交给用户啦。

下属内容也仅限于理论研究了，工程中并没有使用，下面重点关注银行家算法和死锁检测算法就OK了！

2.预防或避免策略

改变操作系统的资源使用策略，从而使系统永远都不可能进入死锁
首先我们要考虑下死锁的必要条件：

• 互斥：资源只能由一个进程使用（因为同步原因，正如单行道，只能一辆车通行）
• 请求和保持：需要资源是请求，请求后将资源锁住了，并且保持一段时间，知道用完该资源
• 不可抢占：只能自己主动释放资源（胡歌和王凯都没有把握把对方的枪抢下来，只能让对方主动放枪）
• 循环等待：可以找到一个进程资源的循环链

2.1预防策略

既然要进入死锁状态要满足以上必要条件，那么我们思考能不能破坏上述必要条件呢？

• 破坏互斥条件？ 这一点不可取，因为我们前面讲过，想要实现进程同步，必须互斥，不然多进程或多线程会跑乱掉。
• 破坏请求和保持条件？
  • 法一：一次请求所有资源，后面不再请求。
  • 法二：请求新资源时，释放已经持有的资源（王凯别闹了，你想让胡歌放枪，就先把自己的枪放下，虽然你放了他也不一定放，哈哈）
  • 这里举例说明一下：从DVD读文件进入磁盘，然后打印
  • 发生死锁的可能性：首先我申请了DVD和磁盘，将DVD数据读入到磁盘以后，忘记释放两个资源了。又写了另一个程序申请磁盘和打印机，从而实现打印功能，发现申请不了了，于是出问题了，如何用上述两种方法解决该问题呢？
  • 法一：一个程序，我把三个资源全申请过来，先从DVD读数据，读完直接打印。
  • 法二：先请求DVD和磁盘，用完释放。然后再请求磁盘和打印机，执行打印。
  • 这种方法虽然OK，但是有其缺点：资源利用率低，有可能出现饥饿。
• 破坏“不可抢占”条件？是可以的
  • 如何进程处于阻塞状态，那么他的资源可以分配给其他进程先使用
  • 但是需要注意：如果进程处于非阻塞状态，那么它的资源是不可以被抢占的，如果抢占了，那么该进程的正常功能会受到影响。
  • 该方法使用范围：内存、CPU寄存器、但是不能应用于信号量。
• 破坏“循环等待”条件？
  • 对资源编号，定义优先级
  • 约定每个进程必须先申请优先级低的资源，再申请优先级高的资源
  • 如果要申请同一优先级的多个资源，必须一次性申请
  • 优先级反应资源的使用次序

2.2避免策略

预防策略限制了资源利用率，过于保守，所以提出避免策略，避免策略添加的限制相对来说比较弱：

• 进程可动态申请资源
• 要求进程预先声明需要资源的最大数量
• 将系统划分成 安全状态和不安全状态
• 若某申请会导致系统进入不安全状态，则拒绝
• 实质是：保证系统不会进入不安全状态
• 预防策略与避免策略类似于红绿灯和交警的区别

关于安全状态

已知每个进程申请的资源数量的最大值。
一个状态被称为安全状态，当且仅当存在一个安全序列P1, P2, …, Pn使得：

• 对于任意一个进程Pi，Pi允许申请的最大资源数不超过系统剩余的资源加上所有Pj(j<i)所持有的资源。
• 意思是：Pi申请资源时要考虑如果全面的进程全都执行完毕以后，那么系统资源够不够用，如果这都不够用，那么说明不能保证安全性。
  

银行家算法

弄明白了安全状态以后，看下一个具体的算法：银行家算法

• 找到任意一个可以第一个完成的进程，删掉
• 找到任意二个可以第一个完成的进程，删掉
• …
• 如果找到了N个进程，说明是安全的，否则不存在安全序列，不是安全状态。

银行家算法仅仅是用来推测当前状态是否是安全状态的，并不是分配算法，但是可以辅助分配。

算法输入：

• 可利用资源向量Available：
  • 是一个含有m个元素的数组，Available[j]=k表示系统中有k个Rj资源
• 最大需求矩阵Max
  • 是一个n*m的矩阵，Max(i,j)=k表示进程i需要最多k个Rj类资源
• 分配矩阵Allocation
  • n*m矩阵，Allocation(i,j)=k表示给进程i已经分配k个Rj资源
• 需求矩阵Need
  • 即为Max-Allocation
  • Need(i,j)=k表示进程i还需要k个Rj资源

算法描述：

• 设置两个向量：
  • Work：系统当前资源数目Work=Avaliable
  • Finish：进程是否顺利运行结束。初始化：Finish[i]=false
• 寻找一个能满足下述条件的进程i:
  • Finish[i]=false, Need(i,j)<=Work(j)
  • 表示i还没运行完，i所需要的资源数少于当前可获得资源数
• 如果找到，运行：
  • Finish[i]=true; Work[j]+=Allocation(i,j)
  • 即将之前申请的资源还回去
  • 继续执行2
• 若所有进程均已结束，则安全，否则，不安全。

举例说明

示例一：

此时的状态是安全的：

• 如果此时P1再申请资源，还能给它吗？ 不能，因为就剩3个了，给它以后大家都吃不饱了。可以将资源分配给P1，然后使用银行家算法尝试可否推出安全状态。
• 此时只能将资源给P2，等待P2完全执行完毕，然后将资源全部释放出来，再考虑P1和P3

3.检测和恢复策略

检测到死锁以后进行恢复：比如交警发现交通死锁，赶紧去指挥，命令一些车辆倒车，或者做其他操作，从而将锁解开。
如何检测死锁？下面讲述死锁的检测算法

• Work=Avaliable; L为空集
• 找到一个不在L中，并且Requesti<=Work的进程i，将其加入L，并且设置Work=Work+Allocation(表示将资源归还)
• 重复2，知道不存在这样的进程
• 若还有不属于L的进程，说明这些进程处于死锁状态；否则，不存在死锁。

关于检测算法的问题：

• 合适启动检测算法呢？
  • 要考虑两点：死锁可能发生的频率，死锁可能影响的进程数量

银行家算法和本算法的区别：

• 银行家算法的作用是：在分配资源前运行，从而检查将资源分配后系统还能否运行。所谓银行家就是借钱之前得先评估你能否还得起。
• 死锁检测算法的作用是：当系统觉得某一天的某一刻可能会有死锁发生时，运行该算法，检测出哪个进程死锁了，然后采取措施将进程从死锁状态中恢复出来。

死锁的解除：

• 剥夺资源：
  • 从其他进程剥夺足够数量的资源给死锁进程，以解除死锁。
  • 但是这样会有问题：剥夺其他进程的资源会不会影响其他进程的运行呢？
• 撤销进程：
  • 强行关闭死锁进程
  • 按照某种顺序撤销进程，知道有足够的资源可给其他死锁进程使用，从而将死锁消除

本节很多内容都是理论探讨，笔者认为好无聊，写的没精打采！！！

如果觉得写的不错，对读者有帮助，可以给笔者点个赞，鼓励一下哦~

本系列博客目录
下一篇-线程