小说网站建设的支柱,免费空间申请free,如何优化网站关键词排名,公司注册要求文章目录 0.前言7.1 系统模型7.2 死锁特征7.2.1 必要条件7.2.2 资源分配图 7.3 死锁处理方法7.4 死锁预防#xff08;deadlock prevention#xff09;7.4.1 互斥7.4.2 占有并等待7.4.3 非抢占7.4.4 循环等待 7.5 死锁避免#xff08;deadlock-avoidance#xff09;7.5.1 安… 文章目录 0.前言7.1 系统模型7.2 死锁特征7.2.1 必要条件7.2.2 资源分配图 7.3 死锁处理方法7.4 死锁预防deadlock prevention7.4.1 互斥7.4.2 占有并等待7.4.3 非抢占7.4.4 循环等待 7.5 死锁避免deadlock-avoidance7.5.1 安全状态7.5.2 资源分配图算法7.5.3 银行家算法 7.6 死锁检测7.6.1 每种资源类型只有单个实例7.6.2 每种资源类型可有多个实例7.6.3 应用检测算法 7.7 死锁恢复 0.前言 在多道程序环境中多个进程可以竞争有限数量的资源。当一个进程申请资源时如果这时没有可用资源那么这个进程进入等待状态。又是如果所申请资源被其他等待进程占有那么该等待进程有可能再也无法改变状态。这种情况称为死锁(deadlock)。 死锁最好的例证时Kansas立法机构在20世纪初通过的一项法律其中说到 ”当两辆列车在十字路口逼近时它们应完全停下来并且在一列列车开走之前另一列列车不能再次启动”。 本章目标
解释死锁即一组并发进程不能完成执行任务。提出一些方法以便预防或避免计算机系统内的死锁。
7.1 系统模型
进程在使用资源之前必须先申请资源在使用资源之后要释放资源。进程所申请的资源数量不能超过系统所有资源的总量。
某系统拥有一定数量的资源分布在若干竞争进程之间。这些资源可以分成多种类型每种类型有一定数量的实例。
在正常操作模式下进程只能按如下顺序使用资源
申请如果申请不能立即被允许那么申请进程必须等待直到它获得该资源为止。使用进程对资源进行操作。释放进程释放资源
资源的申请与释放为系统调用。其他资源的申请与释放可以通过信号量的wait与signal操作或通过互斥锁的获取与释放来完成。因此对于进程和线程的每次使用操作系统会检查以确保使用进程已经申请并获得了资源。
系统表记录了每个资源是否空闲或已被分配分配给了哪个进程。如果进程正在申请的资源正在为其他进程所使用那么该进程会增加到该资源的等待队列。
当一组进程的每个进程都在等待一个事件而这个事件只能由这一组进程的另一个进程所引起那么这组进程就处于死锁状态。
死锁也可设计不同的资源类型。多线程可能因为竞争共享资源而容易产生死锁。
7.2 死锁特征
当出现死锁时进程永远不能完成并且系统资源被阻碍使用阻止了其他作业开始执行。
7.2.1 必要条件
如果在一个系统中下面四个条件同时满足那么会引起死锁。 互斥(mutual exclusion) 至少有一个资源必须处于非共享模式即一次只有一个进程使用如果另一个进程申请该资源那么申请进程必须等到该资源被释放为止。 占有并等待(hold and wait) 一个进程必须占有至少一个资源并等待另一资源而该资源为其他进程所占有。 非抢占(no preemption) 资源不能被抢占即资源只能在进程完成任务后自动释放。 循环等待(circular wait) 有一组等待进程P0,P1,P2,P3…,Pn,P0等待的资源被P1等待P等待的资源被P2所占有……Pn−1等待的资源为Pn所占有Pn所等待的资源被P0所占有。
个条件必须同时满足才会出现死锁循环等待条件意味着占有并等待条件这样四个条件并不完全独立。
7.2.2 资源分配图
死锁问题可用称为系统资源分配图的有向图进行更为精确地描述。 这种图由一个节点集合和一个边集合组成。节点集合可以分成两种类型的节点 P1P2…Pn系统活动进程的集合 R1R2…Rn系统所有资源的集合 Pi→Rj 表示进程Pi已经申请了资源类型为Rj的一个实例称为申请边 Rj→Pi 表示资源类型Rj已经分配给进程Pi称为分配边 可以证明 如果分配图没有环那么系统就没有进程死锁。如果分配图有环那么可能存在死锁。如果每个类型只有一个实例环是死锁存在的充分必要条件。不过每个类型不止一个实例环是死锁的必要条件。 存在死锁的资源分配图 存在环但是没有死锁的资源分配图:
7.3 死锁处理方法 有三种方法 可使用协议以预防或避免死锁确保系统不会进入死锁状态。可允许系统进入死锁状态然后检测它并加以修复。可忽略这个问题认为死锁不可能在系统内发生。 第三种方法为绝大多数操作系统所用因此应用程序开发人员需要自己来处理死锁。 为了确保死锁不会发生系统可以采用死锁预防或死锁避免方案: 死锁预防deadlock prevention 是一组方法以确保至少一个必要条件不成立。这些方法通过限制如何申请资源的方法来预防死锁。 死锁避免deadlock avoidance 要求操作系统事先得到有关进程申请资源和使用资源的额外信息。有了这些额外信息系统可以确定对于一个申请进程是否应等待。为了确定当前申请是允许还是延迟系统必须考虑可用资源已经分配给每个进程的资源每个进程将来申请和释放的资源。
除此之外系统还可以提供一个算法来检查系统状态来确定死锁是否发生并提供另一个算法来从死锁中恢复。
预防死锁的副作用是降低设备的使用率和系统的吞吐率。
缺点是低设备使用率和系统吞吐率。
7.4 死锁预防deadlock prevention
出现死锁有四个必要条件只要保证至少一个条件不成立就能预防死锁的发生。
7.4.1 互斥
对于非共享资源必须要有互斥条件如打印机。另一方面共享资源不要求互斥访问因此不会涉及死锁如只读文件。
故通常不能通过否定互斥条件来预防死锁有的资源本身就是非共享的。
7.4.2 占有并等待
为了确保占有并等待条件不会在系统内出现必须保证当一个进程申请一个资源时就不能占有其他资源。 方法一可以通过要求申请资源的系统调用在所有其使用的协议是每个进程在执行前申请并获得所有资源。他系统调用之前进行。 方法二允许进程在没有资源时才可申请资源一个进程可申请一些资源并使用它们然而在它申请更多其他资源之前它必须释放其现已分配的所有资源。
这两种协议有两个主要缺点 第一资源利用率resource utilization可能比较低因为很多资源可能已分配但长时间没有被使用。 第二可能发生饥饿。一个进程如需要多个常用资源可能会永久等待比如因为其所需要的资源中至少一个总是分配给其他的进程。
7.4.3 非抢占
为确保这一条件不成立可使用如下协议
即可以抢占如果一个进程占用资源并申请另一个不能立即分配的资源那么其现已分配的资源都可被抢占即这些资源被隐式地释放了。只有当进程获得其原有资源和所申请的新资源时进程才可以重新执行。
或者说如果一个进程申请一些资源首先检查是否可用如果可用就分配它们如果不可用那么检查这些资源是否已分配给其他等待额外资源的进程。如果是就抢占这些资源并分配给申请进程。如果资源不可用且也不可被其他等待进程占有那么申请进程必须等待。当一个进程处于等待时如果其他进程申请其拥有的资源那么该进程部分资源可以被抢占。一个进程要重新执行他必须分配到其所申请的资源并恢复其在等待时被抢占的资源。
这个协议通常用于状态可以保存和恢复的资源如CPU寄存器和内存一般不适用其他资源如打印机和磁带驱动器。
7.4.4 循环等待
一个确保此条件不成立的方法是对所有资源类型进行完全排序且要求每个进程按递增顺序来申请资源。
设R1R2R3…Rn为资源类型的的集合。为每个资源类型分配一个唯一整数来允许比较两个资源以确定其先后顺序。可定义一个函数R→N ,其中是自然数集合例如tapedrive1 diskdrive5 printer12
每个进程只按照递增顺序申请资源即一个进程开始可以申请任意数量的资源类型为的实例。之后当且仅当RjRi时该进程可以申请资源Rj的实例。如果需要同一资源类型的多个实例那么对它们必须一起申请。
例如对于以上给定函数一个进程如果同时需要打印机和磁带驱动器那么就必须先申请磁带驱动器再申请打印机。换句话说要求当一个进程申请资源类型Rj时必须先释放所有Ri[RiRj]
可以使用反证法证明使用这两个协议那么循环等待就不可能成立。
设计一个完全排序或层析并不能防止死锁而是要靠应用程序员来按顺序编写程序。另外函数应该根据系统内资源使用的正常顺序来定义。例如由于磁带通常在打印机之前使用所以定义tapedriveprinter较为合理。
7.5 死锁避免deadlock-avoidance
避免死锁的另外一种方法是获得以后如何申请资源的附加信息。
不同的算法所要求的信息量和信息的类型上有所不同最为简单和最为常用的模型要求每个进程说明可能需要的每种资源类型实例的最大需求。根据每个进程可能申请的每种资源类型实例的最大需求的事先信息可以构造一个算法以确保系统绝不会进入死锁状态。这种算法定义了死锁避免deadlock-avoidance方法。
死锁避免算法动态地检测资源分配状态以确保循环等待条件不可能成立。资源分配状态是由可用资源和已分配资源以及进程最大需求所决定的。
7.5.1 安全状态
如果系统能按某个顺序为每个进程分配资源不超过其最大值并能避免死锁那么系统状态就是安全的。即如果存在一个安全序列那么系统处于安全状态。如果没有这样的顺序存在那么系统处于不安全状态。
进程顺序{P1,P2,…,Pn}如果对于每个PiPi仍然可以申请的资源数小于当前可用资源加上所有进程Pj其中j小于i所占用资源那么这一顺序称为安全序列。
在这种情况下进程Pi所需要的资源即使不能立即使用那么Pi等待直到所有Pj释放其资源当它们完成时Pi可得到其所需要的所有资源完成其给定任务。
安全状态不是死锁状态相反死锁状态是不安全状态。然而不是所有不安全状态都能够导致死锁状态。
只要状态为安全操作系统就能避免不安全和死锁状态。在不安全情况下操作系统不能阻止进程以会导致死锁的方式申请资源。进程行为控制了不安全状态。 有了安全状态的概念可定义避免算法确保系统不会死锁即确保系统处于安全状态开始系统处于安全状态当进程申请一个可用资源时系统必须确定这一资源申请是可以立即分配还是要等待即便现在资源可用也只有分配后系统仍处于安全状态才允许申请。
也因此采用这种方法和没有采用死锁避免算法相比资源使用率可能更低。
7.5.2 资源分配图算法
利用资源分配图引入需求边Pi→Rj 表示进程Pi可能在将来某个时候申请资源Rj。只有申请边变为分配边而不会导致资源分配图形成环时才允许申请。
如果没有环存在那么会使得系统处于安全状态如果有环存在则分配会导致系统处于不安全状态。
7.5.3 银行家算法
银行家算法 对于每种资源类型有多个实例的资源分配系统资源分配图就不再适用。使用银行家算法但是效率比资源分配图方案低。
当新进程进入系统时它必须说明其可能需要的各种类型资源实例的最大数量这一数量不能超过当前系统资源的总和。当用户申请一组资源时系统必须确定这些资源的分配是否仍会使系统出于安全状态如果是就分配资源否则进程必须等待直到某个其他进程释放足够资源为止。 实现银行家算法必须有几个数据结构AvailableMaxAllocationNeed。 这些数据结构对资源分配系统的状态进行了记录。设为系统的进程的个数为资源类型的种类 Available 长度为m的向量表示每种资源类型的现有实例的数量。如果Available[j] k则说明资源类型Rj有现有个实例。 Max ×矩阵定义每个进程的最大需求如果Max[][] k那么进程Pi最多申请个资源类型Rj的实例。 Allocation ×矩阵定义每个进程现在所分配的各种资源类型的实例数量例如Allocation[][] k那么进程Pi现在已经分配了个资源类型Rj的实例。 Need ×矩阵表示每个进程还需要的剩余的资源。如果Need[][] k那么进程Pi还需要申请个资源类型Rj的实例。并且Need[][] Max[][] - Allocation[][] 这些数据结构的大小和值会随着时间而改变。 为了简化银行家算法的描述
设为长度为n的向量那么X≤Y 当且仅当对所有的i1,2,3…,nX[i]≤Y[i]如果X≤Y 并且!,那么Y小于X。
可以将矩阵Allocation 和Need的每行作为向量并分别用Allocationi 和Needi来表示。 向量Allocationi表示分配给进程Pi的资源Needi表示进程Pi 为完成其任务可能仍然需要申请的额外资源。
安全性算法 确定计算机是否处于安全状态需要以下几步 创建Work 和 Finish 向量长度分别为m,n并且Work Avallable将Finish的每一项置为false查找是否存在这样的i使得满足 Finish[i] false Needi Work
如果不存在则跳到第四步。 Work Work Allocationi Finish[i] true 跳回第二步 如果对所有的Finish[i] true,那么系统处于安全状态。 2. 资源请求算法 设Requesti为进程Pi的请求向量。即如果Requesti[j]k 那么Pi所需要资源类型Rj的实例数量为k。 当进程Pi做出资源申请时采取如下动作 如果RequestiNeedi那么进行下一步否则产生出错条件因为已经超过了其最大请求。如果RequestiAvailable那么进行下一步否则Pi必须等待因为没有可用的资源。假定系统可以分配给进程Pi所需的资源并按如下方式修改状态 AvailableAvailable−Requesti AllocationiAllocationiRequesti NeediNeedi−Requesti 如果所产生的资源分配状态是安全的那么交易完成且进程Pi可分配到其所需要的资源。
然而如果新状态不安全那么进程Pi必须等待Requesti并回复到原资源分配状态。
7.6 死锁检测
如果一个系统既不采用死锁预防算法也不采用死锁避免算法那么死锁可能出现。在这种情况下系统可以提供
一个用来检查系统状态从而确定是否出现死锁的算法一个用来从死锁状态恢复的算法
7.6.1 每种资源类型只有单个实例
如果所有资源类型只有单个实例我们可以定义这样一个死锁检测算法该算法使用了资源分配图的一个变形称为等待图(wait-for)。
7.6.2 每种资源类型可有多个实例 7.6.3 应用检测算法 7.7 死锁恢复
一种措施是通知操作员死锁已发生以便操作人员人工处理死锁。
另一种措施是让系统从死锁状态中自动恢复过来。 打破死锁有两种方法 一个方法是简单地终止或多个进程以打破循环等待。 另一个方法是从一个或多个死锁进程那里抢占一个或多个资源。 进程终止
一是终止所有死锁进程这种方式虽然终止了死锁循环代价太大。 二是一次只终止一个进程直到取消死锁循环为止这种方法的开销会很大因为每次终止一个进程就需要调用死锁检测算法以确定进程是否仍处于死锁。 资源抢占
这里有三个问题需要处理
①选择一个牺牲品抢占哪些资源和哪个进程必须确定抢占顺序以使代价最小化。
②回滚如果从一个进程那里抢占一个资源那么应对该进程做些什么安排必须将这个进程回滚到某个安全状态以便以后重启进程。
最简单的方法是完全回滚终止进程并重新执行。更为有效的方法是将进程回滚到足够打破死锁。另一方面这种方法要求系统维护有关运行进程状态的更多信息。
③饥饿如何确保不会发生饥饿最为常用的方法是在代价因素中加上回滚次数。
