《现代操作系统》-读书笔记-第六章-死锁

《现代操作系统》-读书笔记-第六章-死锁

在计算机系统中有很多独占性的资源,在任一时刻它们都只能被一个进程使用。常见的有打印机磁带以及系统内部表中的表项。打印机同时让两个进程打印将造成混乱的打印结果;两个进程同时使用同一文件系统表中的表项会引起文件系统的瘫痪。正因为如此,操作系统都具有授权一个进程(临时)排他地访问某一种资源的能力。

两个进程被相互阻塞,并且一直处于这样的状态,称之为死锁(deadlock)

死锁也可能发生在机器之间。比如多台电脑争用一个设备资源。除了请求独占性的I/O设备之外,别的情况也有可能引起死锁。例如,在一个数据库系统中,为了避免竞争,可对若干记录加锁。如果进程 A 对记录 R1 加了锁,进程 B 对记录 R2 加了锁,接着,这两个进程又试图各自把对方的记录也加锁,这时也会产生死锁。所以,软硬件资源都有可能出现死锁。

资源

大部分死锁都和资源相关,所以我们首先来看看资源是什么。在进程对设备、文件等取得了排他性访问权时,有可能会出现死锁。为了尽可能使关于死锁的讨论通用,我们把这类需要排他性使用的对象称为资源(resource)。资源可以是硬件设备(如蓝光驱动器)或是一组信息(如数据库中一个加锁的记录)。通常在计算机中有多种(可获取的)资源。一些类型的资源会有若干个相同的实例,如三台蓝光驱动器。当某一资源有若干实例时,其中任何一个都可以用来满足对资源的请求。简单来说,资源就是随着时间的推移,必须能获得、使用以及释放的任何东西。

可抢占资源和不可抢占资源

资源分为两类:可抢占的和不可抢占的。可抢占资源(preemptable resource)可以从拥有它的进程中抢占而不会产生任何副作用,存储器就是一类可抢占的资源。

相反,不可抢占资源(nonpreemptable resource)是指在不引起相关的计算失败的情况下,无法把它从占有它的进程处抢占过来。如果一个进程已开始刻盘,突然将蓝光光盘刻录机分配给另一个进程,那么将划坏蓝光光盘。在任何时刻蓝光光盘刻录机都是不可抢占的。

某个资源是否可抢占取决于上下文环境。在一台标准的 PC 中,内存中的页面总是可以置换到磁盘中并置换回来,故内存是可抢占的。但是在一部不支持交换和页面调度的智能机上,仅通过将内存消耗大户交换出来是不能避免死锁的。

总的来说,死锁与不可抢占资源有关,有关可抢占资源的潜在死锁通常可以通过在进程之间重新分配资源而化解。所以,我们的重点放在不可抢占资源上。

使用一个资源所需要的事件顺序可以用抽象的形式表示如下:

1) 请求资源

2) 使用资源。

3) 释放资源

若请求时资源不可用,则请求进程被迫等待。在一些操作系统中,资源请求失败时进程会自动被阻塞,在资源可用时再唤醒它。在其他的系统中,资源请求失败会返回一个错误代码,请求的进程会等待段时间,然后重试。

当一个进程请求资源失败时,它通常会处于这样一个小循环中:请求资源,休眠,再请求。这个进程虽然没有被阻塞,但是从各角度来说,它不能做任何有价值的工作,实际和阻塞状态一样。在后面的讨论中,我们假设如果某个进程请求资源失败,那么它就进入休眠状态。

请求资源的过程是非常依赖于系统的。在某些系统中,提供了request 系统调用,用于允许进程资源请求。在另一些系统中,操作系统只知道资源是一些特殊文件,在任何时刻它们最多只能被一个进程打开。一般情况下,这些特殊文件用 open 调用打开。如果这些文件正在被使用,那么,发出 open 调用的进程会被阻塞,一直到文件的当前使用者关闭该文件为止。

资源获取

对于数据库系统中的记录这类资源,应该由用户进程来管理其使用。一种允许用户管理资源的可能方法是为每一个资源配置一个信号量。这些信号量都被初始化为 1。互斥信号量也能起到相同的作用。

死锁简介

死锁的规范定义如下:如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件,那么,该进程集合就是死锁的。

资源死锁的条件

Coffman 等人(1971) 总结了发生(资源)死锁的四个必要条件:

1) 互斥条件。每个资源要么已经分配给了一个进程,要么就是可用的。

2) 占有和等待条件。已经得到了某个资源的进程可以再请求新的资源。

3) 不可抢占条件。已经分配给一个进程的资源不能强制性地被抢占,它只能被占有它的进程显式地释放。

4) 环路等待条件。死锁发生时,系统中一定有由两个或两个以上的进程组成的一条环路,该环路中的每个进程都在等待着下一个进程所占有的资源。

死锁发生时,以上四个条件一定是同时满足的。如果其中任何一个条件不成立,死锁就不会发生。值得注意的是,每一个条件都与系统的一种可选策略相关。一种资源能否同时分配给不同的进程?一个进程能否在占有一个资源的同时请求另一个资源?资源能否被抢占?循环等待环路是否存在?我们在后面会看到怎样通过破坏上述条件来预防死锁。

死锁建模

Holt (1972) 指出如何用有向图建立上述四个条件的模型。在有向图中有两类节点:用圆形表示的进程,用方形表示的资源。从资源节点到进程节点的有向边代表该资源已被请求、授权并被进程占用。

在图 6-3 a 中,当前资源 R 正被进程 A 占用。

由进程节点到资源节点的有向边表明当前进程正在请求该资源,并且该进程已被阻塞,处于等待该资源的状态。在图 6-3 b 中,进程 B 正等待着资源 S。图 6 -3 c 说明进入了死锁状态:进程 C 等待着资源 T,资源 T 被进程 D 占用着,进程 D 又等待着由进程 C 占用着的资源 U。这样两个进程都得等待下去。图中的环表示与这些进程和资源有关的死锁。在本例中,环是 C-T-D-U-C。

总而言之,有四种处理死锁的策略:

1) 忽略该问题。也许如果你忽略它,它也会忽略你。

2) 检测死锁并恢复。让死锁发生,检测它们是否发生,一旦发生死锁,采取行动解决问题。

3) 仔细对资源进行分配,动态地避免死锁。

4) 通过破坏引起死锁的四个必要条件之一,防止死锁的产生。

鸵鸟算法

最简单的解决方法是鸵鸟算法:把头埋到沙子里,假装根本没有问题发生。每个人对该方法的看法都不相同。数学家认为这种方法根本不能接受,不论代价有多大,都要彻底防止死锁的产生;工程师们想要了解死锁发生的频度、系统因各种原因崩溃的发生次数以及死锁的严重性。如果死锁平均每 5 年发生一次,而每个月系统都会因硬件故障、编译器错误或者操作系统故障而崩溃一次,那么大多数的工程师不会以性能损失和可用性的代价去防止死锁。

为了能够让这一对比更具体,考虑如下情况的操作系统:当一个 open 系统调用因物理设备(例如蓝光驱动器或者打印机)忙而不能得到响应的时候,操作系统会阻塞调用该系统调用的进程。通常是由设备驱动来决定在这种情况下应该采取何种措施。显然,阻塞或者返回一个错误代码是两种选择。如果一个进程成功地打开了蓝光驱动器,而另一个进程成功地打开了打印机,这时每个进程都会试图去打开另外一个设备,系统会阻塞这种尝试,从而发生死锁。现有系统很少能够检测到这种死锁。

死锁检测和死锁恢复

第二种技术是死锁检测和恢复。在使用这种技术时,系统并不试图阻止死锁的产生,而是允许死锁发生,当检测到死锁发生后,采取措施进行恢复。

每种类型一个资源的死锁检测

我们从最简单的例子开始,即每种资源类型只有一个资源。这样的系统可能有扫描仪、蓝光光盘刻录机、绘图仪和磁带机,但每种设备都不超过一个,即排除了同时有两台打印机的情况。

可以对这样的系统构造一~张资源分配图,如图 6-3 所示。如果这张图包含了一个或一个以上的环,那么死锁就存在。在此环中的任何一个进程都是死锁进程。如果没有这样的环,系统就没有发生死锁。

我们讨论一下更复杂的情况,假设-一个系统包括 A 到 G 共 7 个进程,R 到 W 共 6 种资源。资源的占有情况和进程对资源的请求情况如下:

1) A 进程持有 R 资源,且需要 S 资源。

2) B 进程不持有任何资源,但需要 T 资源。

3) C 进程不持有任何资源,但需要 S 资源。

4) D 进程持有 U 资源,且需要 S 资源和 T 资源。

5) E 进程持有 T 资源,且需要 V 资源。

6) F 进程持有 W 资源,且需要 S 资源。

7) G 进程持有 V 资源,且需要 U 资源。

即处问题是:“系统是否存在死锁?如果存在的话,死锁涉及了哪些进程?”

要理要回答这一问题,我们可以构造一张资源分配图,如图 6-5 a 所示。可以直接观察到这张图中包含了一个环,如图 6-5 b 所示。在这个环中,我们可以看出进程 D、E、G 已经死锁。进程 A、C、F 没有死锁,这是因为可把 S 资源分配给它们中的任一个,而且它们中的任一进程完成后都能释放 S,于是其他两个进程可依次执行,直至执行完毕。(请注意,为了让这个例子更有趣,我们允许进程 D 每次请求两个资源。)

虽然通过观察一张简单的图就能够很容易地找出死锁进程,但为了实用,我们仍然需要一个正规的算法来检测死锁。众所周知,有很多检测有向图环路的方法。下面将给出一个简单的算法,这种算法对有向图进行检测,并在发现图中有环路存在或确定无环路时结束。这一算法使用了数据结构 L,L 代表一些节点的集合。在这一算法中,对已经检查过的弧(有向边)进行标记,以免重复检查。

每种类型多个资源的死锁检测

如果有多种相同的资源存在,就需要采用另一种方法来检测死锁。现在我们提供一种基于矩阵的算法来检测从 P 到 P,这 n 个进程中的死锁。假设资源的类型数为 m, E 代表资源类型 1,Ez 代表资源类型 2,E;代表资源类型 i (1 <i <m)。E 是现有资源向量(existing resource vector),代表每种已存在的资源总数。比如,如果资源类型 1 代表磁带机,那么 E=2 就表示系统有两台磁带机。

在任意时刻,某些资源已被分配所以不可用。假设 A 是可用资源向量(available resource vector),那么 A,表示当前可供使用的资源数(即没有被分配的资源)。如果仅有的两台磁带机都已经分配出去了,那么 A,的值为 0。

现在我们需要两个数组:C 代表当前分配矩阵(current allocation matrix),R 代表请求矩阵(request matrix)。C 的第 i 行代表 P;当前所持有的每一种类型资源的资源数。所以,Cij 代表进程 i 所持有的资源的数量。同理,Rij;代表 Pi;所需要的资源 j 的数量。这四种数据结构如图 6-6 所示。

从死锁中恢复

假设我们的死锁检测算法已成功地检测到了死锁,那么下一步该怎么办?当然需要一些方法使系统重新正常工作。在本小节中,我们会讨论各种从死锁中恢复的方法,尽管这些方法看起来都不那么令人满意。

1、利用抢占恢复

在某些情况下,可能会临时将某个资源从它的当前所有者那里转移给另一个进程。许多情况下,尤其是对运行在大型主机上的批处理操作系统来说,需要人工进行干预。

2、利用回滚恢复

如果系统设计人员以及主机操作员了解到死锁有可能发生,他们就可以周期性地对进程进行检查点检查(checkpointed)。进程检查点检查就是将进程的状态写人一个文件以备以后重启。该检查点中不仅包括存储映像,还包括了资源状态,即哪些资源分配给了该进程。为了使这一过程更有效,新的检查点不应覆盖原有的文件,而应写到新文件中。这样,当进程执行时,将会有一系列的检查点文件被累积起来。

一旦检测到死锁,就很容易发现需要哪些资源。为了进行恢复,要从一个较早的检查点上开始,这样拥有所需要资源的进程会回滚到一个时间点,在此时间点之前该进程获得了一些其他的资源。在该检查点后所做的所有工作都丢失。(例如,检查点之后的输出必须丢弃,因为它们还会被重新输出。)实际上,是将该进程复位到一个更早的状态,那时它还没有取得所需的资源,接着就把这个资源分配给一个死锁进程。如果复位后的进程试图重新获得对该资源的控制,它就必须一直等到该资源可用时为止。

3、通过杀死进程恢复

最直接也是最简单的解决死锁的方法是杀死一个或若干个进程。一种方法是杀掉环中的一个进程。如果走运的话,其他进程将可以继续。如果这样做行不通的话,就需要继续杀死别的进程直到打破死锁环。

另一种方法是选一个环外的进程作为牺牲品以释放该进程的资源。

死锁避免

我们假设当一个进程请求资源时,它一次就请求所有的资源(见图 6-6 中的矩阵R)

不过在大多数系统中,一次只请求一个资源。系统必须能够判断分配资源是否安全,并且只能在保证安全的条件下分配资源。问题是:是否存在一种算法总能做出正确的选择从而避免死锁?答案是肯定的,但条件是必须事先获得一些特定的信息。

资源轨迹图

避免死锁的主要算法是基于一个安全状态的概念。在描述算法前,我们先讨论有关安全的概念。通过图的方式,能更容易理解。虽然图的方式不能被直接翻译成有用的算法,但它给出了一个解决问题的直观感受。

安全状态和不安全的状态

我们将要研究的死锁避免算法使用了图 6-6 中的有关信息。在任何时刻,当前状态包括了 E、A、C 和 R。如果没有死锁发生,并且即使所有进程突然请求对资源的最大需求,也仍然存在某种调度次序能够使得每一个进程运行完毕,则称该状态是安全的。

单个资源的银行家算法

Dijkstra (1965) 提出了一种能够避免死锁的调度算法,称为银行家算法(banker’ s algorithm),这是 6.4.1 节中给出的死锁检测算法的扩展。该模型基于一个小城镇的银行家,他向一群客户分别承诺了定的贷款额度。算法要做的是判断对请求的满足是否会导致进入不安全状态。如果是,就拒绝请求;如果满足请求后系统仍然是安全的,就予以分配。

银行家算法就是对每一个请求进行检査,检查如果满足这一请求是否会达到安全状态。若是,那么就满足该请求;否则,就推迟对这一请求的满足。为了检査状态是否安全,银行家需要考虑他是否有足够的资源满足某一个客户。如果可以,那么这笔贷款就是能够收回的,并且接着检査最接近最大限额的,一个客户,以此类推。如果所有投资最终都能被收回,那么该状态是安全的,最初的请求可以批准。

多个资源的银行家算法

可以把银行家算法进行推广以处理多个资源。检查一个状态是否安全的算法如下:

1) 查找右边矩阵中是否有一行,其没有被满足的资源数均小于或等于 A。如果不存在这样的行,那么系统将会死锁,因为任何进程都无法运行结束(假定进程会一直占有资源直到它们终止为止)。

2) 假若找到这样一行,那么可以假设它获得所需的资源并运行结束,将该进程标记为终止,并将其资源加到向量 A上。

3) 重复以上两步,或者直到所有的进程都标记为终止,其初始状态是安全的;或者所有进程的资源需求都得不到满足,此时就是发生了死锁。

如果在第 1 步中同时有若干进程均符合条件,那么不管挑选哪一个运行都没有关系,因为可用资源或者会增多,或者至少保持不变。

死锁预防

通过前面的学习我们知道,死锁避免从本质上来说是不可能的,因为它需要获知未来的请求,而这些请求是不可知的。那么实际的系统又是如何避免死锁的呢?我们回顾 Coffman 等人(1971) 所述的四个条件,看是否能发现线索。如果能够保证四个条件中至少有一个不成立,那么死锁将不会产生(Havender, 1968)。

破坏互斥条件

先考虑破坏互斥使用条件。如果资源不被一个进程所独占,那么死锁肯定不会产生。当然,允许两个进程同时使用打印机会造成混乱,通过采用假脱机打印机(spooling printer)技术可以允许若干个进程同时产生输出。该模型中唯一真正请求使用物理打印机的进程是打印机守护进程,由于守护进程决不会请求别的资源,所以不会因打印机而产生死锁。

破坏占有并等待条件

Coffman 等表述的第二个条件似乎更有希望。只要禁止已持有资源的进程再等待其他资源便可以消除死锁。一种实现方法是规定所有进程在开始执行前请求所需的全部资源。如果所需的全部资源可用,那么就将它们分配给这个进程,于是该进程肯定能够运行结束。如果有一个或多个资源正被使用,那么就不进行分配,进程等待。

这种方法的一个直接问题是很多进程直到运行时才知道它需要多少资源。实际上,如果进程能够知道它需要多少资源,就可以使用银行家算法。另一个问题是这种方法的资源利用率不是最优的。例如,有一个进程先从输入磁带上读取数据,进行一小时的分析,最后会写到输出磁带上,同时会在绘图仪上绘出。如果所有资源都必须提前请求,这个进程就会把输出磁带机和绘图仪控制住一小时。

不过,一些大型机批处理系统要求用户在所提交的作业的第一行列出它们需要多少资源。然后,系统立即分配所需的全部资源,并且直到作业完成才回收资源。虽然这加重了编程人员的负担,也造成了资源的浪费,但这的确防止了死锁。

另一种破坏占有并等待条件的略有不同的方案是,要求当一个进程请求资源时,先暂时释放其当前占用的所有资源,然后再尝试一-次获得所需的全部资源。

破坏不可抢占条件

破坏第三个条件(不可抢占)也是可能的。假若一个进程已分配到一台打印机,且正在进行打印输出,如果由于它需要的绘图仪无法获得而强制性地把它占有的打印机抢占掉,会引起一片混乱。但是,一些资源可以通过虚拟化的方式来避免发生这样的情况。假脱机打印机向磁盘输出,并且只允许打印机守护进程访问真正的物理打印机,这种方式可以消除涉及打印机的死锁,然而却可能带来由磁盘空间导致的死锁。但是对于大容量磁盘,要消耗完所有的磁盘空间一般是不可能的。

然而,并不是所有的资源都可以进行类似的虚拟化。例如,数据库中的记录或者操作系统中的表都必须被锁定,因此存在出现死锁的可能。

破坏环路等待条件

现在只剩下一个条件了。消除环路等待有几种方法。一种是保证每一个进程在任何时刻只能占用一个资源,如果要请求另外一个资源,它必须先释放第一个资源。但假若进程正在把一个大文件从磁带机上读入并送到打印机打印,那么这种限制是不可接受的。

另一种避免出现环路等待的方法是将所有资源统一编号,如图 6-13 a 所示。现在的规则是:进程可以在任何时刻提出资源请求,但是所有请求必须按照资源编号的顺序(升序)提出。进程可以先请求打印机后请求磁带机,但不可以先请求绘图仪后请求打印机。若按此规则,资源分配图中肯定不会出现环。

死锁预防的各种方法:

其他问题

两阶段加锁

两阶段加锁(two-phase locking):在第一阶段,进程试图对所有所需的记录进行加锁,一次锁一个记录。如果第一阶段加锁成功,就开始第二阶段,完成更新然后释放锁。在第一阶段并没有做实际的工作。

如果在第一阶段某个进程需要的记录已经被加锁,那么该进程释放它所有加锁的记录,然后重新开始第一阶段。从某种意义上说,这种方法类似于提前或者至少是未实施一些不可逆的操作之前请求所有资源。在两阶段加锁的一些版本中,如果在第一阶段遇到了已加锁的记录,并不会释放锁然后重新开始,这就可能产生死锁。

不过,在一般意义下,这种策略并不通用。例如,在实时系统和进程控制系统中,由于一个进程缺少一个可用资源就半途中断它,并重新开始该进程,这是不可接受的。如果一个进程已经在网络上读写消息、更新文件或从事任何不能安全地重复做的事,那么重新运行进程也是不可接受的。只有当程序员仔细地安排了程序,使得在第一阶段程序可以在任意一点停下来,并重新开始而不会产生错误,这时这个算法才可行。但很多应用并不能按这种方式来设计。

通信死锁

到目前为止,我们的工作都集中在资源死锁上。若一个进程请求某个其他进程持有的资源,就必须等待直到其使用者释放资源。这些资源有时是硬件或软件对象,例如蓝光光驱或者数据库的记录,有时则是更抽象的。资源死锁是竞争性同步的问题。进程在执行过程中如果与竞争的进程无交叉,便会顺利执行。进程将资源加锁,是为了防止交替访问资源而产生不一-致的资源状态。交替访问加锁的资源将有可能产生死锁。在图 6-2 中我们看到了信号量作为资源而产生的死锁。信号量是比蓝光光驱更抽象的一种资源,但是在这个例子中,每个进程都成功获得了一个资源(一个信号量),并在请求另一个资源(另一个信号量)时产生死锁。这是一种典型的资源死锁。

尽管如此,但这并不是一个经典的资源死锁。A 没有占有 B 所需的资源,反之亦然。事实上,并没有完全可见的资源。但是,根据标谁的定义,在一系列进程中,每个进程因为等待另外一个进程引发的事件而产生阻塞,这就是一种死锁。相比于更加常见的资源死锁,我们把上面这种情况叫作通信死锁(communication deadlock)。通信死锁是协同同步的异常情况,处于这种死锁中的进程如果是各自独立执行的,则无法完成服务。

通信死锁不能通过对资源排序(因为没有)或者通过仔细地安排调度来避免(因为任何时刻的请求都是不允许被延迟的)。幸运的是,另外一种技术通常可以用来中断通信死锁:超时。在大多数网络通信系统中,只要一个信息被发送至一个特定的地方,并等待其返回一个预期的回复,发送者就同时启动计时器。若计时器在回复到达前计时就停止了,则信息的发送者可以认定信息已经丢失,并重新发送(如果需要,则一直重复)。通过这种方式,可以避免死锁。换种说法就是,超时策略作为一种启发式方法可探测死锁并使进程恢复正常。这种方式也适用于资源死锁。另外,有些用户使用的设备驱动程序是多变的或者有漏洞的,会导致死锁或系统冻结,这些用户也要依赖于超时策略。

当然,如果原始信息没有丢失,而仅仅是回复延时,接收者可能收到两次或者更多次信息,甚至导致意想不到的结果。想象电子银行系统中包含付款说明的信息。很明显,不应该仅仅因为网速缓慢或者超时设定太短,就重复(并执行)多次。应该将通信规则—通常称为协议(protocol)一设计为让所有事情都正确,这是一个复杂的课题,超出了本书的范围。

并非所有在通信系统或者网络发生的死锁都是通信死锁。资源死锁也会发生,如图 6-15 中的网络。这张图是因特网的简化图(极其简化)。因特网由两类计算机组成:主机和路由器。主机(host)是一台用户计算机,可以是某人家里的 PC、公司的个人计算机,也可能是一个共享服务器。主机由人来操作。路由器(router)是专用的通信计算机,将数据包从源发送至目的地。每台主机都连接一个或更多的路由器,可以用一条 DSL 线、有线电视连接、局域网、拨号线路、无线网络、光纤等来连接。

当一个数据包从一个主机进入路由器时,它被放人一个缓冲区中,然后传输到另外一个路由器,再到另一个,直至目的地。这些缓冲区都是资源并且数目有限。在图 6-15 中,每个路由器都有 8 个缓冲器(实际应用中有数以百万计,但是并不能改变潜在死锁的本质,只是改变了它的频率)。假设路由器 A 的所有数据包需要发送到 B, B 的所有数据包需要发送到 C, C 的所有数据包需要发送到 D,然后 D 的所有数据包需要发送到 A。那么没有数据包可以移动,因为在另一端没有缓冲区。这就是一个典型的资源死锁,尽管它发生在通信系统中。

活锁

在某些情况下,当进程意识到它不能获取所需要的下一个锁时,就会尝试礼貌地释放已经获得的锁,然后等待 1 ms,再尝试一次。从理论上来说,这是用来检测并预防死锁的好方法。但是,如果另一个进程在相同的时刻做了相同的操作,那么就像两个人在一条路上相遇并同时给对方让路一样,相同的步调将导致双方都无法前进。

设想 try_lock 原语,调用进程可以检测互斥量,要么获取它,要么返回失败。换句话说,就是它不会阻塞。程序员可以将其与 acquire_lock 并用,后者也试图获得锁,但是如果不能获得就会产生阻塞。现在设想有一对并行运行的进程(可能在不同的 CPU 核上)用到了两个资源,如图 6-16 示。每一个进程都需要两个资源,并使用 try_lock 原语试图获取锁。如果获取失败,那么进程便会放弃它所持有的锁并再次尝试。在图 6-16 中,进程 A 运行时获得了资源 1, 进程 2 运行时获得了资源 2。接下来,它们分别试图获取另一个锁并都失败了。于是它们便会释放当前持有的锁,然后再试一次。这个过程会一直重复,直到有个无聊的用户(或者其他实体)前来解救其中的某个进程。很明显,这个过程中没有进程阻塞,甚至可以说进程正在活动,所以这不是死锁。然而,进程并不会继续往下执行,可以称之为活锁(livelock)。

饥饿

与死锁和活锁非常相似的一个问题是饥饿(starvation)。在动态运行的系统中,在任何时刻都可能请求资源。这就需要一些策略来决定在什么时候谁获得什么资源。虽然这个策略表面上很有道理,但依然有可能使一些进程永远得不到服务,虽然它们并不是死锁进程。

作为一个例子,考虑打印机分配。设想系统采用某种算法来保证打印机分配不产生死锁。现在假设若干进程同时都请求打印机,究竟哪一个进程能获得打印机呢?

一个可能的分配方案是把打印机分配给打印最小文件的进程(假设这个信息可知)。这个方法让尽量多的顾客满意,并且看起来很公平。我们考虑下面的情况:在一个繁忙的系统中,有一个进程有一个很大的文件要打印,每当打印机空闲,系统纵观所有进程,并把打印机分配给打印最小文件的进程。如果存在一个固定的进程流,其中的进程都是只打印小文件,那么,要打印大文件的进程永远也得不到打印机。很简单,它会“饥饿而死”(无限制地推后,尽管它没有被阻塞)。

饥饿可以通过先来先服务资源分配策略来避免。在这种机制下,等待最久的进程会是下一个被调度的进程。随着时间的推移,所有进程都会变成最“老”的,因而,最终能够获得资源而完成。

有关锁的研究

死锁这一问题在操作系统发展的早期就得到了详细的研究。原因在于死锁的检测是一个经典的图论问题,任何对数学有兴趣的研究生都可以做上 3~4 年的研究。所有相关算法都已经经过反复修正,但每次修正总是得到更古怪、更不现实的算法。很多研究工作都已经销声匿迹,但是仍然有很多关于死锁的论文发表。

近期关于死锁的研究方向之一是死锁避免(Jula 等人,2011)。这种方法的主要思想是,应用程序

在死锁发生的时候检测出死锁并且保存它们的特征,从而避免在之后的运行中发生相同的死锁。除此之外,Marino 等人(2013) 使用并发控制来确保死锁不会首次出现。

另外一个研究方向是死锁检测。近期关于死锁检测的工作是由 Pyla 和 Varadarajan (2012) 提出的 Cai 和 Chan (2012) 的研究工作提出了一种动态的死锁检测机制,能够送代地减少没有入边和出边的锁的依赖关系。

关于死锁的问题也逐渐渗透到各个领域。Wu 等人(2013) 描述了一种用于自动加工系统的死锁控制系统,其中使用 Petri 网来模拟系统,从而寻找允许自由死锁控制的充分和必要条件。

还有很多研究是关于分布式死锁检测的,尤其是在高性能计算领域。例如,有很多工作是基于死锁检测的调度。Wang 和 Lu (2013) 提出了一个在存储受限工作流计算中的调度算法。Hilbrich 等人(2013) 描述了用于 MPI 的运行时死锁检测。最后,还有很多关于分布式死锁检测的理论工作。这里就不做表述了,主要是因为:(1) 它们超出了本书的范围;(2) 这些研究在实际系统中的应用非常少,似乎只是为了让一些图论家有事可做罢了。

小结

死锁是任何操作系统中都存在的潜在问题。当一组进程中的每个进程都因等待由该组进程中的另进程所占有的资源而导致阻塞,死锁就发生了。这种情况会使所有的进程都处于无限等待的状态。一般来讲,这是进程一直等待被其他进程占用的某些资源释放的事件。死锁的另外一种可能情况是一组通信进程都在等待一个消息,而通信信道却是空的,并且也没有采用超时机制。

通过跟踪哪一个状态是安全状态,哪一个状态是不安全状态,可以避免资源死锁。安全状态就是这样一个状态:存在一个事件序列,保证所有的进程都能完成。不安全状态就没有这样的保证。银行家算法可以通过拒绝可能引起不安全状态的请求来避免死锁。

也可以在设计系统时从系统结构上预防资源死锁的发生,这样可以永久性地解决资源死锁问题。例如,只允许进程在任何时刻最多占有一个资源,这就破坏了循环等待环路。也可以将所有的资源编号规定进程按严格的升序请求资源,这样也能预防死锁。

资源死锁并不是唯一的一种死锁。尽管我们可以通过设置适当的超时机制来解决通信死锁,但它依然是某些系统中潜在的问题。

活锁和死锁的问题有些相似,那就是它也可以停止所有的转发进程,但是二者在技术上不同,由于活锁包含了一些实际上并没有锁住的进程,因此可以通过先来先服务的分配策略来避免饥饿。

说点什么

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
提醒