幻读

死锁

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

 

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

 

 

起因

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

死锁的四个条件:

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

 

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

 

死锁的预防

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

  1.  打破禁止抢占条件:允许进程强行从占有者那里夺取资源。
  2. 打破持有和等待条件:实行资源预先分配的策略。
  3. 打破互斥条件:允许进程同时访问某些资源。但是某些资源(如打印机)不可以被同时访问,这是由于资源本身的属性所决定的,所以该方法价值不大
  4. 打破循环等待条件:实行资源有序分配策略。即把资源事先分类编号,按号分配,这样不会因为资源分配形成环路

 

死锁的避免

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

 

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

算法的缺点如下:

  1. 算法要求客户数保持不变,这在实际使用操作系统中很难实现。
  2. 这个算法保证客户在有限时间内得到满足。但是实时客户要求快速响应,所以要考虑这个因素。
  3. 寻找安全序列的过程中,实际上增加了系统开销。

 

检测与恢复

死锁检测:

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

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

} else if {

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

  构建向量矩阵

}

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

逃)

 

死锁恢复:

  1. 抢占:不通知原进程的情况下,将某一资源从一个进程强行取走给另一个进程使用,然后将资源再送回。
  2. 回滚:周期性对进程进行检查点检查,即将进程的状态写入一个文件以备以后重启,包括存储映像、资源状态。新的检查点不覆盖原有文件,而是写到新文件中。
  3. 杀死进程:杀死环中的一个或多个进程;

附加:

如果一个进程被多次回滚,迟迟不能占用必须的系统资源,可能会导致资源匮乏 (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),与死锁相似,死锁是进程都在等待对方先释放资源,而活锁则是进程彼此释放资源后同时占用对方释放的资源。当此情况持续发生时,尽管资源的状态不断改变,但每个形成都无法获取所需资源,使得事情没有任何进展。

以上是 幻读 的全部内容, 来源链接: utcz.com/a/55408.html

回到顶部