操作系统——死锁的产生与预防

产生死锁的四个必要条件:产生死锁的四个必要条件:

  1. 互斥:一个资源同一时间只能被一个进程使用

  2. 请求与保持:一个进程因请求资源而阻塞,一个进程对已获得的资源保持不释放

  3. 不可剥夺:对已获得资源的进程,在未使用完之前不能强行剥夺

  4. 循环等待条件:两个或两个以上的进程形成一种头尾相接的循环等待资源的关系。

死锁的预防:

由于产生死锁的四个必要条件缺一不可,因此只要破坏其中的一个就可以预防死锁的产生。 原理:设计不同的资源分配算法,来保证不发生死锁。

  • 破环互斥: 如果资源不需要互斥访问,那么就能破坏互斥条件。对于某些硬件资源,看可以采用特殊的技术实现同时访问。

缺点:对软件资源无法实现

  • 破环请求与保持:

即在进程运行时不在提出资源请求。系统要求所有进程要一次性的申请在整个运行过程中所需要的全部资源。若系统没有足够的资源进行分配,在等待时不保持任何资源。

优点:简单,易于实现 缺点: 一个用户在作业运行之前可能提不出他的作业将要使用的资源。 一些额外资源长期占用,浪费系统资源

  • 破坏不可剥夺:

一个已经拥有资源的进程,若它再提出新资源要求得不到满足时,它必须立即释放已有的资源。等以后需要的时候再进行申请。

缺点:实现难度大

  • 破坏循环等待 系统将资源按类型进行线性排序,并赋予不同的序号,所有进程对资源的提出都必须按照资源序号递增的次序提出。

优点:和之前的两种方法相比,资源利用率和系统吞吐量有了明显的改善。

缺点:进程实际需要资源的顺序不一定与资源的编号一致,因此仍会造成资源浪费;资源的序号必须相对稳定,从而限制了新设备的增加。

系统的安全状态:

  • 如果系统能按某种顺序为每个进程依次分配其所需的资源,直至所有进程都能运行完成,称此时系统处于安全状态

  • 这种进程的顺序,如P4,P1,…,Pn, 称为安全序列

  • 若不存在这样一个安全序列称此时系统处于不安全状态

  • 如果不按安全序列分配资源,则系统可能会由安全状态进入不安全状态。

例子:当前有三个进程P1,P2,P3 12份资源 P1需要10份, p2需要4份, p3需要9份

在某一时刻,P1,P2,P3分别获得5,2,2份,尚有三份可分配

https://img-blog.csdn.net/20180722111940410?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbmlhY3h4/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70

注意:

  • 不安全状态≠死锁 处于不安全状态的系统不一定会发生死锁 处于安全状态的系统一定不会发生死锁

  • 系统处于安全与不安全状态都是对静态进行的评价

银行家算法

银行家算法(Banker’s Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。   在银行中,客户申请贷款的数量是有限的,每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量,在满足所有贷款要求时,客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时,都应尽量满足客户的需要。在这样的描述中,银行家就好比操作系统,资金就是资源,客户就相当于要申请资源的进程。 银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。为实现银行家算法,系统必须设置若干数据结构。

  • 可利用资源向量Available 是一个含有m个元素的数组,其中每个元素代表一类资源的可利用的数目
  • 最大需求矩阵Max n×m矩阵,n为当前系统进程的数目,m为系统资源种类数。Max[i,j]为第i个进程对j类资源的最大需求
  • 分配矩阵Allocation n×m矩阵,表示每个进程已分配的每类资源数
  • 需求矩阵Need n×m矩阵,表示每个进程还需要各类资源数

算法流程: https://img-blog.csdn.net/20180722114245297?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbmlhY3h4/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70

参考文章:

https://blog.csdn.net/maniacxx/article/details/81154239 https://blog.csdn.net/qq_36260974/article/details/84404369

end

评论