死锁,死锁的简单例子


死锁

这个概念是操作系统里面很重要的内容,前阵子面试字节被问到了,太久没复习,面经变凉经。

 

死锁(Deadlock),又被翻译为死结。是操作系统或软件运行的一种状态,在多任务系统下,当一个或多个进程等待系统资源、而资源又被进程本事或其他进程占用,就形成了死锁。现如今的操作系统都是多任务执行,只有可以协调好不同的进程,才可以让系统运行流畅不卡顿。

 

插入图片

 

起因

如果系统只有一个进程在运行,当然不会产生死锁,就像独生子女在家似的。不过这是理想状态,在现实中可遇不可求。

死锁的四个条件:

  • 禁止抢占 (No preemption) : 系统资源不能被强制从一个进程中退出
  • 持有和等待 (Hold and wait) : 一个进程可以在等待时有系统资源
  • 互斥 (Mutual exclusion) : 资源只能同时分配给一进程,无法多个进程共享,比如驱动器、打印机等
  • 循环等待 (Circular waiting) :一系列进程互相持有其他进程所需要的资源

 

死锁只有在四个条件(必要条件)同时发生,防止死锁发生只需要破坏其中一项。一般的,解决死锁的方法分为死锁的预防、避免、检测与恢复三种。

 

死锁的预防

死锁的预防是保证系统不进入死锁状态的一种策略。方法就是要求进程在创建时服从某种协议,从而打破产生死锁的四个必要条件。

 

死锁的避免

该策略不限制进程有关申请资源的命令,而是对进程所发出的每一个申请资源命令加以动态检查,并根据检查结果决定是否进行资源分配。

 

该策略用到一个著名的避免死锁的算法--银行家算法,由Dijstra提出并加以解决的。具体分析这里不展开了,简要概括下该算法:银行家算法允许死锁必要条件重的互斥条件、占有且申请条件、不可抢占条件的存在,这样它与预防死锁的方法相比限制较少,资源利用程度高了。

算法的缺点如下:

 

检测与恢复

死锁检测:

if 每种资源类型只有一个实例:{

  构建资源分配图,采用DFS确定是否由环路

} else if {

  每种资源类型还有多个实例的情况:

  构建向量矩阵

}

最简单的消除死锁的办法是重启~没有重启解决不了的事情,如果有,就重买台机器。

逃)

 

死锁恢复:

附加:

如果一个进程被多次回滚,迟迟不能占用必须的系统资源,可能会导致资源匮乏 (resource starvation)。

 

Resource starvation is a problem encounterd in concurrent computing where a process is perpetually denied necessary resources to process its work. Starvation may be caused by errors in a scheduling or mutual exclusion algorithm. Also, it can be caused by resource leaks.

 

Then what is resorce leaks? Resource leaks are particular type of resource consumption by a computer program where the program does not release resources it has acquired. Also, resource leaks are particularly a problem for resources avaliable in very low quantities. Leaking a unique resource, such as a lock, is pretty serious, as this causes immediate resource starvation and cause deadlock.

 

活锁

活锁(livelock),与死锁相似,死锁是进程都在等待对方先释放资源,而活锁则是进程彼此释放资源后同时占用对方释放的资源。当此情况持续发生时,尽管资源的状态不断改变,但每个形成都无法获取所需资源,使得事情没有任何进展。

相关内容

    暂无相关文章