《计算机操作系统 普通高等教育十一五 国家级规划教材 教学课件 ppt 作者 刘循 朱敏 文艺 第5章死锁》由会员分享，可在线阅读，更多相关《计算机操作系统 普通高等教育十一五 国家级规划教材 教学课件 ppt 作者 刘循 朱敏 文艺 第5章死锁（83页珍藏版）》请在金锄头文库上搜索。
1、计算机操作系统 主讲: 四川大学计算机学院 刘 循,第5章 死锁,从进程同步的概念可以知道，当并发进程需要竞争使用资源或需要相互协作向前推进时，如果不采取同步措施，或同步措施不恰当，则很容易导致并发进程不能向前推进而陷入僵局，即死锁现象。 死锁是发生在一组相互竞争或协作的进程与线程之间的一个非正常现象。 死锁是所有操作系统都面临着的潜在问题，操作系统除了需要预防死锁、避免死锁外，还需要能够检测死锁，并从死锁中进行恢复。,本章的主要内容如下： 死锁的产生； 死锁的预防； 死锁的避免； 死锁的检测和解除； 线程死锁。,第5章 死锁,5.1 死锁的产生,死锁是指多个进程因为竞争资源而造成的一种僵局。
2、如果没有外力的作用，这些进程将永远不能再向前推进。 互斥共享资源是临界资源，在一段时间内只允许一个进程使用，只有当一个进程使用完并释放后，其他的进程才能使用。 每一个进程使用临界资源都需要经历三个阶段：申请、使用、归还。,5.1.1 死锁产生的原因,死锁产生的原因有两个：并发进程对临界资源的竞争和并发进程推进顺序不当。 1.在进程并发环境下进程之间对资源的竞争 生产者与消费者问题 当缓冲区为空时，如果消费者进程进入了缓冲区；或者当缓冲区为满时，如果生产者进程进入了缓冲区，这两种情况都会发生死锁。 哲学家进餐问题 如果5个哲学家都同时去拿叉子，则每个哲学家都只能拿到一把叉子，每个哲学家又都会等待
3、另一把无法得到的叉子，这样的资源竞争引起了死锁。,5.1.1 死锁产生的原因（续）,2.进程推进顺序不当 如果系统中有三个进程P1、P2和P3，相互之间需要传递消息S1、S2、S3，即：进程P1发送消息S1给进程P2，进程P2发送消息S2给进程P3，进程P3发送消息S3给进程P1，如果每个进程都要发送消息和接收消息成功后才能向前推进，则可能有如下情况: P1：send（S1），receive（S3）； P2：send（S2），receive（S1）； P3：send（S3），receive（S2）； 则P1、P2、P3能够顺利发送并得到所需信息，都能够向前推进。,但是，如果 P1：receiv
4、e（S3），send（S1）； P2：receive（S1），send（S2）； P3：receive（S2），send（S3）； 则P1、P2、P3都需要先接收消息后才能发送消息。显然，在这种情况下，它们永远都不能接收到所需要的信息，不能向前推进，发生了死锁。 进程对资源的竞争和进程推进顺序不当可能会发生死锁。,5.1.1 死锁产生的原因（续）,5.1.2 死锁产生的条件,1971年，Coffman等人通过研究死锁，总结出死锁发生的四个必要条件。 （1）互斥条件 资源的使用是互斥的。每个资源要么已经分配给进程，要么能够提供给进程。如果资源已经被一个进程占有，则再请求资源的进程只能等待，直到占
5、有资源的进程用完后归还资源。 （2）占有并请求条件 一个进程得到资源并再请求资源时，请求的资源不能得到，已得到的资源也不会释放。 （3）不剥夺条件 当进程得到资源后，只能由进程自身主动释放。进程不能剥夺其他进程已经获得的资源。,5.1.2 死锁产生的条件,（4）环路等待条件 每个进程都在等待下一个进程已经获得的资源，所有等待的进程构成一个环路，形成永远等待。 这四个条件是死锁发生的必要条件，必须同时具备这四个条件才会发生死锁。其中任意一条不满足，都不会发生死锁。但这四个条件并不是死锁发生的充分条件，可能四个条件都成立，但系统中并无死锁。,5.1.3 处理死锁的基本方法,处理死锁的基本方法可以归
6、结为如下四种： 1预防死锁 通过破坏死锁的四个必要条件中的一个或几个来防止死锁的发生，是一种在实际中比较现实的方法，已经被广泛采用。最常采用的破坏死锁的方法为消除“占有并请求条件”或“环路等待条件”。但是，这样破坏死锁会引起系统的资源利用率低。 2避免死锁 指在资源的动态分配过程中，通过合理的调节各并发进程的资源分配和推进顺序，防止系统进入不安全状态，从而避免死锁的发生。目前，在较多系统中采用此方法来避免死锁的发生。该方法存在的问题是需要预先安排进程的推进顺序。,5.1.3 处理死锁的基本方法（续）,3检测死锁 不采取任何限制性措施，允许系统发生死锁。死锁发生后，通过系统设置的检测机构，及时地
7、检测出死锁的发生，精确地确定与死锁相关的进程和资源情况。 4解除死锁 解除死锁是检测死锁的目的。在已经检测到死锁的基础上，针对死锁，采取适当措施，从系统中将已经发生的死锁消除。解除死锁会影响并发进程的执行。,5.1.4 资源分配图,为了精确地描述死锁，Holt在1974年用有向图表示资源分配情况，这种有向图被称为资源分配图。 资源分配图用于描述进程已经分配的资源和正在请求的资源。通过对资源分配图中各进程资源分配情况的分析，可以判别是否具备死锁发生的条件。 资源分配图由一系列顶点和边组成。顶点由所有活动进程集合和所有资源类型集合构成。进程顶点用圆圈表示，资源顶点用方块表示，方块中的一个点表示一个
8、资源。有向线段连接进程到资源。箭头从进程指向资源，表示进程正在等待资源；箭头从资源指向进程，表示进程已经获得资源。,5.1.4 资源分配图,如果资源分配图中没有构成环，则不存在死锁；如果构成环，且死锁发生必要条件的其他三个条件（主要是占有并等待条件，因为互斥条件和不剥夺条件肯定是具备的。）存在，则可能发生死锁。,5.1.4 资源分配图（续）,图5.1 无环路无死锁的资源分配图,图5.2 有环路无死锁的资源分配图,图5.3、图5.4是可能发生死锁的资源分配图。这两个资源分配图中不但有环构成， 而且死锁发生的其他三个必要条件也具备。,图5.3 有死锁的资源分配图,图5.4 有死锁的资源分配图,5.
9、1.4 资源分配图（续）,5.2 死 锁 预 防,在进程并发时，只有死锁发生的四个必要条件同时具备时才可能发生死锁。因此，死锁预防策略是通过设计协同资源管理程序，在进程运行期间，破坏死锁产生的四个条件之中的任何一个，使之不成立。预防死锁是一种比较容易实现的方法，故被广泛采用。,5.2 死 锁 预 防,1破坏互斥条件 互斥条件是资源被一个进程独自占有，破坏互斥条件是让进程不独自占有资源。 但是，从资源本身来讲，要让多个进程同时使用是不现实的，正如多个进程同时使用打印机，会造成打印机使用混乱一样。 因此，对大多数资源来讲，破坏互斥条件根本不现实。,2破坏占有并请求 破坏占有并请求条件是预防死锁中最
10、有希望实现的方法。只要禁止已经得到资源的进程再请求其他资源便可以避免死锁的发生。 破坏占有并请求有两种实现方式。 （1）静态分配策略 静态分配策略是指一个进程所需要的全部资源必须在该进程执行前申请并得到后，进程才能执行。如果进程不能得到全部所需要的资源，则系统不对进程进行资源分配，进程必须等待获得全部所需要的资源。 对于批处理系统，则可以采用静态分配策略预防死锁。,5.2 死 锁 预 防（续）,5.2 死 锁 预 防（续）,静态分配策略存在的问题： 很多系统难以实现静态分配 特别是交互系统，如分时系统，用户在一个会话的任何时刻，都可能创建新的进程，执行产生新进程的命令，系统在交互之前并不知道用
11、户所有的输入命令，也不可能知道用户要执行的所有进程，不可能采用静态分配策略。 对于批处理系统，则可以采用静态分配策略预防死锁。但是，作业的周转时间非常长。,（2）动态分配策略 动态分配策略是指一个进程每次在申请新的资源前，必须释放原来已经获得的所有资源，然后与所有需要资源的进程竞争分配自己所释的全部资源。 动态分配策略能够满足进程动态确定所需要资源的要求，能够消除占用并请求条件，达到预防死锁的目的。 动态分配策略使得进程付出的代价更高。进程可能释放了资源而不能得到资源： 进程会发生饥饿现象； 系统的资源利用率低,5.2 死 锁 预 防（续）,对于交互系统，可以用动态分配策略消除占有并请求资源条
12、件，预防死锁。 但是，每当进程在请求新的资源时，进程当前所获得的所有资源都必须释放。 如果当前打开了一个文件，则需要关闭文件；如果当前加载了一个设备，则需要卸载该设备。将进程变回原来没有获得任何资源的状态。这样，系统需要付出的开销很大，不现实。,5.2 死 锁 预 防（续）,3阻止环路等待 环路等待是所有资源都被进程占有，但进程又请求另一个进程所占有的不能释放的资源。图5.5所示是有两个环路的进程等待情况。,图5.5 有两个环路的进程等待,5.2 死 锁 预 防（续）,层次分配策略的目的是阻止“环路等待条件”的形成。 层次分配策略的思想如下： 首先将资源分成多个层次； 一个进程得到某一层次的资
13、源后，只能申请更高层次的资源； 当一个进程释放某层的一个资源时，必须先释放所占有的更高层的资源； 一个进程获得了某一层的资源后，如果要再申请该层中的另一个资源，必须先释放该层中的已占有的资源。,5.2 死 锁 预 防（续）,层次分配策略形成的资源分配图中，不会出现环路等待 因为总有一个进程占据了较高层次的资源，它再请求资源时，可能是同层，可能是更高层的。当同层资源已经分配完后，则一定向更高层申请，而更高层资源一定是空闲的，阻止环路等待可以得到满足。因此，进程可以一直向前推进，从而，不会形成环路。,5.2 死 锁 预 防（续）,在哲学家进餐问题上，可以采用层次分配策略阻止死锁的发生。 为所有的叉
14、子建立一个层次关系，如规定所有哲学家右手边的叉子为一个层次，左手边的叉子为另一个层次； 只有左右手的叉子都得到才能拿起叉子就餐。如果只得到右手边的叉子，不能得到左手边的叉子，则需要放弃右手边的叉子。 这样，避免了哲学家拿到右手边的叉子又等待左手边的叉子，而左手边的叉子已经被另外的哲学家得到的情况，从而阻止了环路等待现象的发生，预防了死锁。,5.2 死 锁 预 防（续）,层次分配策略存在的问题: 需要系统资源相对稳定，才能按照层次分配。如果系统需要增加新设备，则会引起层次的变换，造成层次的不稳定。 存在进程使用资源的层次顺序与系统对资源的层次分配顺序不同，造成系统资源浪费的情况。如某进程先申请打
15、印机，后申请磁带机，而按照系统资源层次分配是磁带机在下层，打印机在上层，这样会造成磁带机闲置。 层次分配策略要求编制程序代码时，需要设置条件，增加了程序编制的复杂性，对用户的程序编制有一定的限制。,5.2 死 锁 预 防（续）,4允许剥夺 允许剥夺是指如果进程请求的资源当前不可使用，允许进程“收回”请求。 如果一个进程请求资源，系统会立即响应，或者为进程分配资源，或者指明没有足够的资源来满足进程请求。在进程不能得到请求的资源情况下，或者进程继续请求，直到得到需要的资源；或者进程放弃请求，去完成其他的事情。 因此，允许剥夺并不是指允许进程去剥夺其他进程已经获得的资源，而是允许进程在不能得到资源的
16、情况下，放弃请求。在程序编码实现上，要求每次资源申请时，都需要判别能否得到资源，如果不能，则退回到请求资源前的情况。,5.2 死 锁 预 防（续）,允许剥夺在实现上并不一定有效，特别是进程在请求资源不成又退回请求的情况下，有可能陷入一种在很长的时间内无事可做的状态。 总之，预防死锁的方法较多，在实际应用中需要根据具体的情况选择一个适合的方法。,5.2 死 锁 预 防（续）,5.3 死 锁 避 免,死锁避免方法首先判断资源的分配是否会发生死锁，在确定不会发生死锁的情况下，才将资源真正分配给进程。 与死锁预防策略一样，死锁避免也是一种保守的处理死锁方法。 在死锁避免方法中需要分析系统的状态，分析系统是否存在一个并发进程的状态序列，以保证并发进程不会产生死锁。因此，在死锁避免方法中需要将系统状态分为不安全状态和安全状态，系统处于不安全状态则可能会发生死锁，系统处于安全状态则一定不会发生死锁。,5.3.1 系统的安全状态,系统的安全状态是指系统能够将并发进程按照某种顺序为每个进程分配其所需要的资源，直到满足最大需求为止，每个进程都可以顺利完成。如果系统存在这样的并发进程序
