[操作系统]死锁章节总结

虽然了解代码运行中的死锁的含义和解决方案,但底层概念总是一段时间就忘记,趁这次复习总结一下:(以下内容都是自我总结,不是官方标准)

死锁概念:

当多个进程争夺一个资源时,占用资源的进程长时间不释放,其他进程则一直循环请求资源,都无法进行下一步,产生的现象叫做死锁。

死锁产生的原因:

一是资源分配给进程时出现失误,进程之间抢夺资源造成的问题;二是多道程序运行时,进程执行顺序不合理。

死锁产生的必要条件:

  1. 互斥条件:资源是独占的且排他使用的,则同一时刻一个资源只能被一个进程而使用,如果有多个进程需要的时候,除使用者以外的进程则进入无限期的等待直到使用者释放时争夺使用。
  2. 不可剥夺条件:指资源在使用完毕之前不能被其他进程强行争夺,只能等使用者自愿释放。
  3. 请求和保持条件:进程在需要多个资源的时候,进程在申请下一个资源的时候,已申请的资源则继续占用使用。
  4. 循环等待条件:发生死锁时,必然存在一个等待队列,队列呈环形,比如:P1等待P2的资源 P2等待P3的资源 P3等待P1的资源(可能是P1占用的部分资源)

解决死锁的方式:

  1. 预防死锁:通过严格限制死锁产生的必要条件的产生,而防止死锁的出现。
  2. 避免死锁:在分配资源的时候动态监测死锁是否会产生。
  3. 检测与接触死锁:在运行过程中,定时检测死锁是否真的产生,并且精准的找到与死锁有关的进程和资源,然后采取措施解除死锁,将进程从死锁状态中解脱出来。
  4. 忽略死锁:对于发生几率较低,而解决死锁成本较大或暂时无法解决的死锁选择忽略。

死锁预防概念:

死锁的基本思想就是防范于未然;在事先确定资源分配的算法,限制进程对资源的申请,从而保证不会产生死锁;具体做法就是破坏死锁产生的四个必要条件。

死锁预防的方式:

  1. 若一个进程已经占用了部分资源,又要申请某个资源的时候不能立刻得到满足的话,在陷入等待状态前则释放已经申请到的资源。
  2. 若一个进程申请某个资源的时候,如果资源空闲则占用,如果已经被其他进程占用的话,可判断占用进程是否处于等待状态,如果处于等待状态则剥夺过来使用,不然则等待释放。在等待状态的时候已占用的资源可能也会被其他进程剥夺。
  3. 每个进程开始前则一次性申请它所需的全部资源。仅当满足进程的全部资源可进行申请的时候进程才开始执行。
  4. 当资源没有占用资源时才允许它申请资源,如果进程已经占用了某些资源而又要再申请资源时,则必须要先归还已占有的资源(这个是不是和条件3配合?)

死锁避免概念:

当进程申请一个资源的时候进行动态检,并根据检测结果决定是否分配,如果分配后系统可能产生死锁,则不予分配否则分配,这是一个保证分配的动态策略。

避免和预防的死锁区别在于:预防是比较严格的限制死锁的产生的四个必要条件,而避免则不严格限制四个必要条件的存在,因为即使必要的条件存在也不一定会产生死锁。死锁避免则是在运行过程中注意避免死锁的最终发生。

如果操作系统能保证所有进程在有限时间内得到需要的全部资源,则称系统处于“安全状态”,否则是不安全状态,不安全状态不一定产生死锁,但产生死锁的话一定处于不安全状态。

银行家算法概念(自己总结):

当资源需要分配给进程的时候,需要考虑到分配后的资源是否满足与进程且进程完毕后需要归还。如果不能满足则不给予分配;

示例:如果进程1需要2个A资源1个B资源,进程2需要2个B资源,进程3已经占用1个A资源和2个B资源需要1个A资源,此时给进程3分配1个A资源后进程3就能释放1个A资源2个B资源,那么释放后的资源仅能满足进程1,进程1满足后释放后的资源则满足进程2(一般按轮流顺序 理论也可以分配给进程2再给进程1

死锁预防和死锁避免两种方式都比较保守,都是以牺牲系统效率和浪费资源为代价,这反而以操作系统设计目标相违背;

死锁检测与解除概念:

死锁检测是在进程分配给资源时不采取任何措施减少因为避免和预防死锁的产生而导致的性能浪费,在运行过程中通过监督和资源占用状态判断是否产生是否,并且产生死锁时采用措施解除死锁,以最小的代价使系统恢复正常。

死锁检测的算法:

  1. 给每个进程和资源标记唯一编号
  2. 建立资源分配表,包含了资源号和进程号,分配表记录了每个资源被哪个进程使用
  3. 建立一个进程等待分配表,包含了每个进程号所等待的资源号
  4. 算法规则:进程在申请一个已经被其他进程占用的资源的时候,进行死锁检测,通过反复查找资源分配表和进程等待分配表来确定进程请求资源是否形成环路,若是则确定出现死锁

死锁解除的方法:

  1. 剥夺资源:
    • 剥夺它们占用的资源给死锁进程,以解除死锁,待其他条件满足时再激活被挂起的进程。
  2. 撤销进程:
    • 撤销死锁进程,将它们占用的资源分配给一些死锁进程,直到死锁解除为止。

剥夺资源的时候需要考虑以下几个问题:

  1. 选择一个牺牲进程,即要确定剥夺哪个进程的哪些资源。
  2. 重新运行或退回到某一个开始继续运行。则回滚进程进度,但进程要为回滚做些什么处理。
  3. 怎样保证不发生“饿死”、“饥饿”的情况。
  4. “最小代价“,怎么做才能使代价或开销最小化。

资源分配图:

资源分配图是一个有向图,圆形图代表进程,长方形图代表资源,长方形图里的实心小点则代表每个资源实例。

资源分配图示例