第4章 操作系统

《第4章 操作系统》由会员分享，可在线阅读，更多相关《第4章 操作系统（64页珍藏版）》请在金锄头文库上搜索。

1、第四章第四章 处理机调度与死锁处理机调度与死锁4.1 4.1 处理机调度的层次和调度算法的目标处理机调度的层次和调度算法的目标4.2 4.2 作业与作业调度作业与作业调度4.3 4.3 进程调度进程调度4.4 4.4 实时调度实时调度4.5 4.5 死锁概述死锁概述4.6 4.6 预防死锁预防死锁4.7 4.7 避免死锁避免死锁4.8 4.8 死锁的检测与解除死锁的检测与解除第四章第四章 处理机调度与死锁处理机调度与死锁4.1 4.1 处理机调度的层次处理机调度的层次 和调度算法的目标和调度算法的目标1. 处理机调度的层次 高高级调度度 又称长程调度或作业调度。根据某种算法，决定将外存上处于后

2、备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。高级调度主要用于多道批处理系统中。 低低级调度度 又称为进程调度或短程调度。根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序，将处理机分配给被选中的进程。进程调度是最基本的一种调度。 中中级调度度 又称为内存调度。引入中级调度的主要目的是，提高内存利用率和系统吞吐量。把那些暂时不能运行的进程，调至外存等待，把外存上的那些已具备运行条件的就绪进程，再重新调入内存。中级调度实际上就是存储器管理中的对换功能。2. 处理机调度算法的目标 处理机调度算法的共同目标处理机调度算法的共同目标 资源利用率：为提

3、高系统的资源利用率，应使系统中的处理机和其他所有资源都尽可能地保持忙碌状态，其中最重要的、处理机的利用率可用以下方法计算： 公平性：指应使诸进程都获得合理的CPU 时间，不会发生进程饥饿现象。 平衡性：使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。 策略强制执行：对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。2. 处理机调度算法的目标 批处理系统的目标批处理系统的目标 平均周转时间短：平均周转时间短：使作业周转时间和作业的平均周转时间尽可能短。否则，会使许多用户的等待时间过长，这将会引起他们，特

4、别是短作业用户的不满。可把平均周转时间描述为： 作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间。而平均带权周转时间则可表示为： 系统吞吐量高：系统吞吐量高：吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理作业的平均长度有关。事实上，如果单纯是为了获得高的系统吞吐量，就应尽量多的选择短作业运行。 处理机利用率好：处理机利用率好：对于大、中型计算机，CPU价格十分昂贵，调度方式和算法又对处理机的利用率，起着十分重要的作用。如果单纯是为使处理机利用率高。应尽量多的选择计算量大的作业运行。由上所述可以看出，这些要求之间是存在着一定矛盾的。 分分时系系统的目的

5、目标 响应时间快：响应时间，是从用户通过键盘提交一个请求开始，直到屏幕上显示出处理结果为止的一段时间间隔。它包括三部分时间：请求信息从键盘输入开始，直至传送到处理机的时间，处理机对请求信息进行处理的时间，以及将所形成的响应信息回送到终端显示器的时间。 均衡性：所谓均衡性是指，系统响应时间的快慢应与用户所请求服务的复杂性相适应。 返回2. 处理机调度算法的目标 实时系系统的目的目标 截止时间的保证：对于HRT任务，其调度方式和调度算法必须确保对截止时间的要求，否则将可能造成难以预料的后果；而对于SRT任务，其调度方式和调度算法也应基本上能保证对截止时间的要求。 可预测性：在实时系统中，可预测性显

6、得非常重要。第四章第四章 处理机调度与死锁处理机调度与死锁4.2 4.2 作业与作业调度作业与作业调度4.2.1 批处理系统中的作业及调度 1.1.作作业和作和作业步步 作业：作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位，从外存调入内存的。 作业步：在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果。我们把其中的每一个加工步骤称一个作业步，各作业步之间存在着相互联系，往往是上一个作业步的输出作为下一个作业步的输入。 2.2.作作业控制控制块

7、JCBJCB 在多道批处理系统中，为每个作业设置了一个作业控制块JCB，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。在作业运行期间，系统就按照JCB中的信息，和作业说明书对作业进行控制。 3.3.作作业运行的三个运行的三个阶段和三种状段和三种状态 作业从进入系统到运行结束，通常需要经历收容、运行和完成三个阶段。相应的作业也就有“后备状态”、“运行状态”和“完成状态”。 收收容容阶阶段段：操作员把用户提交的作业，通过某种输入方式或SPOOLing系统，输入到硬盘上，再为该作业建立JCB，并把它放入作业后备队列中，相应的，此时作业的状态为“后备状态后备状态”。 运

8、运行行阶阶段段：当作业被作业调度选中后，便为它分配必要的资源和建立进程，并将它放入就绪队列。一个作业从第一次进入就绪状态开始，直到它运行结束前，在此期间都处于“运行状态运行状态”。 完完成成阶阶段段：当作业运行完成、或发生异常情况而提前结束时，作业便进入完成阶段，相应的作业状态为“完完成成状状态态”。此时系统中的“终止作业”程序，将会回收已分配给该作业的作业控制块和所有资源，并将作业运行结果信息形成输出文件后输出。4.2.1 批处理系统中的作业及调度 作作业调度的主要任度的主要任务 也也称为接纳调度，根据JCB中的信息，检查系统中的资源，能否满足作业对资源的需求，以及按照一定的调度算法，从外存

9、的后备队列中，选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程，排在就绪队列上等待调度。因此，也把作业调度（Admission Scheduling）。 在每次执行作业调度时，都须做出以下两个决定在每次执行作业调度时，都须做出以下两个决定 接纳多少个作业接纳多少个作业 取决于多道程序度，即允许多少个作业同时在内存中运行。 接纳哪些作业接纳哪些作业 取决于所采用的调度算法。4.2.1 批处理系统中的作业及调度4.2.2 先来先服务和短作业优先调度算法 1.1.先来先服先来先服务FCFSFCFS（first-come first-servedfirst-come fir

10、st-served）调度算法度算法 该算法总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便执行下去，直到该进程完成或阻塞时，才释放处理机。 优点优点: :实现简单。 缺点缺点: :没考虑进程的优先级。 2.2.短作短作业优先先SJFSJF（short job firstshort job first）的）的调度算法度算法 该算法从就绪队列中选出“下一个CPU执行期”最短的进程，为之分配处理机。 缺点：缺点： 必须预知作业的运行时间； 对长作业非常不利； 在采用FCFS算法时，人机无法实现交互； 该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理。4.2.

11、3 优先级调度算法和高响应比优先调度算法 1.1.优先先级调度算法度算法(priority-scheduling algorithm)(priority-scheduling algorithm) 基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法是根据该优先级进行调度的。这样就可以保证紧迫性作业优先运行。 2.2.高响高响应比比优先先调度算法度算法 高响应比优先调度算法则是既考虑了作业的等待时间，又考虑作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机调度的性能。 高响应比优先算法的实现高响应比优先算法的实现 优先级的变化规律可描述为： 由于等待

12、时间与服务时间之和，就是系统对该作业的响应时间，故该优先级又相当于响应比RP。据此，又可表示为： 返回第四章第四章 处理机调度与死锁处理机调度与死锁4.3 4.3 进程调度进程调度4.3.1 进程调度的任务、机制和方式 1.1.进程调度任务进程调度任务 保存处理机的现场信息保存处理机的现场信息：在进行调度时首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等。 按某种算法选取进程：按某种算法选取进程：调度程序按某种算法，从就绪队列中选取一个进程，将其状态改为运行状态，并准备把处理机分配给它。 把处理器分配给进程：把处理器分配给进程：由分派程序把处理器分配给该进程。此时

13、需要将选中进程的进程控制块内有关处理机现场的信息，装入处理器相应的各个寄存器中，把处理器的控制权交予该进程，让它从上次的断点处恢复运行。4.3.1 进程调度的任务、机制和方式 2.2.进程调度机制进程调度机制 排队器：事先将系统中的所有就绪进程，按照一定的策略，排成一个或多个队列。以便调度程序能最快地找到它。以后每当有一个进程转变为就绪状态时，排队器便将它插入到相应的就绪队列。 分派器：依据进程调度程序所选定的进程，将其从就绪队列中取出，然后进行进程间的上下文切换，将处理机分配给新选出的进程。 上下文切换器：在对处理机进行切换时，会发生： 第一对上下文切换时，OS将保存当前进程的上下文，装入分

14、派程序的上下文，以便分派程序运行； 第二对上下文切换是移出分派程序的上下文，装入新选进程上下文。4.3.1 进程调度的任务、机制和方式 3.3.进程调度方式进程调度方式 非抢占方式非抢占方式 一旦把处理机分配给某进程后，就一直让它运行下去，决不会因为时钟中断，或任何其它原因，去抢占该正在运行进程的处理机，直至该进程完成，或发生某事件而被阻塞时，才把处理机分配给其它进程。 采用这种方式时，可能引起进程调度的因素可归结为： 正在执行的进程运行完毕，或因发生某事件而使其无法再继续运行； 正在执行中的进程，因提出I/O请求而暂停执行； 在进程通信或同步过程中，执行了某种原语操作，如Block原语。 优

15、点：优点：是实现简单、系统开销小，适用于大多数的批处理系统。 缺点：缺点：但它不能用于分时系统和大多数实时系统。3.进程调度方式 抢占方式抢占方式 允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机，重新分配给另一进程。 抢占方式能满足实时任务的需求。但抢占方式比较复杂，所需付出统开销也较大。 “抢占抢占” 必须遵循的原则必须遵循的原则 优先权原则：允许优先级高的新到进程，抢占当前进程的处理机； 短进程优先原则：许新到的短进程，可以抢占当前长进程的处理机； 时间片原则：各进程按时间片轮转运行时，当正在执行的进程的一个时间片用完后，便停止该进程的执行而重新进行调度。4.

16、3.2 轮转调度算法 1.1.轮转法的基本原理轮转法的基本原理 系统将所有的就绪进程按FCFS策略，排成一个就绪队列。系统可设置每隔一定时间（如30ms），便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片。当它运行完后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。 2.2.进程切换时机进程切换时机 若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首进程运行，并启动一个新的时间片。 在一个时间片用完时，此时计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序把它送往就绪队列的

17、末尾。 4.3.2 轮转调度算法 3.3.时间片大小的确定时间片大小的确定 在轮转算法中，时间片的大小，对系统性能有很大的影响。 若选择很小的时间片，将有利于短作业，因为它能在该时间片内完成。 但时间片小，意味着会频繁地执行进程调度，和进程上下文的切换，这无疑会增加系统的开销。 若时间片选择得太长，且为使每个进程，都能在一个时间片内完成，RR算法便退化为FCFS算法，无法满足短作业和交互式用户的需求。 一个较为可取的时间片大小是，略大于一次典型的交互所需要的时间，使大多数交互式进程，能在一个时间片内完成，从而可以获得很小的响应时间。3.时间片大小的确定 3.3.时间片大小的确定时间片大小的确定

18、 下左图示出了时间片大小对响应时间的影响，其中图a是时间片略大于典型交互的时间，其中图b是时间片小于典型交互的时间。 下右图示出了时间片分别为q=1和q=4时对平均周转时间的影响。4.3.3 优先级调度算法 1.1.优先级调度算法的类型优先级调度算法的类型 把处理机分配给就绪队列中优先级最高的进程。 非抢占式优先级调度算法：非抢占式优先级调度算法：一旦把处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去直至完成，或者因该进程发生某事件而放弃处理机时，系统方可将处理机重新分配给另一优先级最高的进程。 抢占式优先级调度算法：抢占式优先级调度算法：把处理机分配给优先级最高的进程，使之执行

19、。但在其执行期间，只要出现了另一个其优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的进程。 2.2.优先级的类型优先级的类型 静态优先级：静态优先级：静态优先级是在创建进程时确定的，在进程的整个运行期间保持不变。优先级是利用某一范围内的一个整数来表示的，例如0255中的某一整数，又把该整数称为优先数。确定进程优先级大小的依据有如下三个：进程类型、进程对资源的需求、 用户要求。 动态优先级：动态优先级：动态优先级是指在创建进程之初，先赋予其一个优先级，然后其值随进程的推进，或等待时间的增加而改变，以便获得更好的调度性能。4.3.4 多级反馈队列调度算法 算法思想算法思想 将就绪队列分

20、为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间越长，级别越小，时间片越小，最后一级采用时间片轮转，其他队列采用先进先出； 系统从第一级调度，当第一级为空时，系统转向第二个队列，.当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列。 算法要点算法要点 * 首先系统中设置多个就绪队列； * 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大； * 各个队列按照先进先出调度算法； * 一个新进程就绪后进入第一级队列； * 进程由于等待而放弃CPU后，进入等待队列，一

21、旦等待的事件发生，则回到原来的就绪队列； * 当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾； * 当第一级队列空时，就去调度第二级队列，如此类推； * 当时间片到后，进程放弃CPU，回到下一级队列。4.3.4 多级反馈队列调度算法 算法的性能算法的性能 终端型用户：终端型用户：由于终端型用户提交的作业多属于交互型作业，通常较小，系统只要能使这些作业在第一队列规定的时间片内完成，便可使终端型用户感到满意。 短批处理作业用户：短批处理作业用户：如果可在第一队列中执行完成，便获得与终端型作业一样的响应时间。对于稍长的短作业，也只需在第二和第三队列各执行一时间片完

22、成，其周转时间仍然较短。 长批处理作业用户：长批处理作业用户：将依次在第1，2，n个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。4.3.5 基于公平原则的调度算法 1.1.保证调度算法保证调度算法 保证调度算法向用户所做出的是明确的性能保证，该算法可以做到调度的公平性，如处理机分配的公平性。 在实施公平调度算法时系统中必须具有这样一些功能： （1）跟踪计算每个进程自创建以来已经执行的处理时间； （2）计算每个进程应获得的处理机时间，即自创建以来的时间除以n。 （3）计算进程获得处理机时间的比率。 （4）比较各进程获得处理机时间的比率。 （5）调度程序应选择比率最小的进程

23、，将处理机分配给它，并让该进程一直运行，直到超过最接近它的进程比率为止。 2.2.公平分享调度算法公平分享调度算法 在该调度算法中，调度的公平性主要是针对用户，使所有用户能获得相同的处理机时间，或所要求的时间比例。然而调度又是以进程为基本单位。为此，必须考虑到每一个用户所拥有的进程数目。返回第四章第四章 处理机调度与死锁处理机调度与死锁4.4 4.4 实时调度实时调度4.4.1 实现实时调度的基本条件 1.1.提供必要的信息提供必要的信息 系统应向调度程序提供有关任务的信息：就绪时间、开始截止时间和完成截止时间、处理时间、优先级。 2.2.系统处理能力强系统处理能力强 在实时系统中，若处理机的

24、处理能力不够强，则有可能因处理机忙不过，而致使某些实时任务不能得到及时处理，从而导致发生难以预料的后果： 单处理机系统增强； 多处理机系统：将上述的限制条件改为： 3.3.采用抢占式调度机制采用抢占式调度机制 在含有HRT任务的实时系统中，广泛采用抢占机制。这样便可满足HRT任务对截止时间的要求。 4.4.具有快速切换机制具有快速切换机制 该机制应具有如下两方面的能力： （1）对中断的快速响应能力：具有快速硬件中断机构，禁止中断的时间间隔尽量短； （2）快速的任务分派能力：使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。4.4.2 实时调度算法的分类 对实时调度算法对实时调度算法

25、的分类的分类 根据实时任务性质，可将实时调度的算法分为硬实时调度算法和软实时调度算法； 按调度方式，则可分为非抢占调度算法和抢占调度算法。 1. 1.非抢占式调度算法非抢占式调度算法 非抢占式轮转调度算法：将所有实时任务排成一个轮转队列，调度程序每次选择队列中的第一个任务投入运行，当该任务完成后，便把它挂在轮转队列的末尾等待。这种调度算法可获得数秒至数十秒的响应时间。 非抢占式优先调度算法：当较高优先级的实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后，便可去调度执行队首的高优先进程。使其响应时间减少到数秒至数百ms。 2. 2.抢占式调度算法抢占式调度算法 基于时

26、钟中断的抢占式优先级调度算法：在某实时任务到达后，如果它的优先级高于当前任务的优先级，这时并不立即抢占当前任务的处理机，而是等到时钟中断发生时，调度程序才剥夺当前任务的执行，将处理机分配给新到的高优先级任务。该算法调度延迟可降为几十至几ms。 立即抢占的优先级调度算法：在这种调度策略中，要求操作系统具有快速响应外部事件中断的能力。一旦出现外部中断，只要当前任务未处于临界区，便能立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。这种算法把调度延迟降低到几ms至100微秒。4.4.2 实时调度算法的分类4.4.3 最早截止时间优先算法 该算法是根据任务的截止时间确定任务的优先级，具有最早截

27、止时间的任务排在队列的前面。 1.1.非抢占式调度方式用于非周期实时任务非抢占式调度方式用于非周期实时任务 4.4.3 最早截止时间优先算法 2.2.抢占式调度方式用于周期实时任务抢占式调度方式用于周期实时任务4.4.4 最低松弛度优先算法 该算法在确定任务的优先级时，根据的是任务的紧急（或松弛）程度。任务紧急程度愈高，赋予该任务的优先级就愈高，以使之优先执行。松弛度计算公式松弛度计算公式进程的松弛度进程的松弛度= =必须完成时间其本身的运行时间当前时间必须完成时间其本身的运行时间当前时间A A和和B B任务任务每次必须每次必须完成的时间完成的时间 利用利用ELLFELLF算法算法进行调度的情

28、况进行调度的情况 4.4.5 优先级倒置 1.1.优先级倒置的形成优先级倒置的形成 “优先级倒置优先级倒置”的现象的现象 高优先级进程（或线程）被低优先级进程（或线程）延迟或阻塞。 例子例子 有三个完全独立的进程P1、P2和P3，P1的优先级最高，P2次之，P3最低。P1和P2通过共享的一个临界资源进行交互。下面是一段代码： P1： P（mutex）； CS-1； V(mutex)； P2： program2； P3： P（mutex）； CS-3； V(mutex) ；4.4.5 优先级倒置 2.2.优先级倒置的解决方法优先级倒置的解决方法 一种简单的解决方法一种简单的解决方法 假如进程P3

29、在进入临界区后，P3所占用的处理机就不允许被抢占。 如果系统中的临界区都较短且不多，该方法是可行的。反之，如果P3临界区非常长，则高优先级进程P1仍会等待很长的时间，其效果是无法令人满意的。 一个比较实用的方法一个比较实用的方法 当高优先级进程P1要进入临界区，去使用临界资源R，如果已有一个低优先级进程P3，正在使用该资源，此时一方面P1被阻塞，另一方面由P3继承P1的优先级，并一直保持到P3退出临界区。返回第四章第四章 处理机调度与死锁处理机调度与死锁4.5 4.5 死锁概述死锁概述4.5.1 资源问题 在系统中有许多不同类型的资源，其中可以引起死锁的主要是，需要采用互斥访问方法的、不可以被

30、抢占的资源，即在前面介绍的临界资源。 1.1.可重用资源和消耗性资源可重用资源和消耗性资源 可重用资源可重用资源 一种可供用户重复使用多次的资源。 性质：性质： 每一个可重用资源中的单元，只能分配给一个进程使用，不允许多个进程共享； 进程在对可重用资源的使用时，须按照请求资源、使用资源、释放资源这样的顺序。 系统中每一类可重用资源中的单元数目是相对固定的，进程在运行期间，既不能创建，也不能删除。 对资源的请求和释放通常都是利用系统调用来实现的。计算机系统中大多数资源都属于可重用资源。1.可重用资源和消耗性资源 可消耗资源可消耗资源 又称为临时性资源，它是在进程运行期间，由进程动态的创建和消耗的

31、。 性质： 每一类可消耗性资源的单元数目，在进程运行期间是可以不断变化的，有时它可以有许多，有时可能为0； 进程在运行过程中，可以不断地创造可消耗性资源的单元，将它们放入该资源类的缓冲区中，以增加该资源类的单元数目。 进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己消耗，不再将它们返回给该资源类中。 可消耗资源通常是由生产者进程创建，由消费者进程消耗。最典型的可消耗资源，就是用于进程间通信的消息等。4.5.1 资源问题 2.2.可抢占资源和不可抢占资源可抢占资源和不可抢占资源 可抢占资源可抢占资源 指某进程在获得这类资源后，该资源可以再被其他进程或系统抢占。对于这类资源是不会引起

32、死锁的。 CPU和主存均属于可抢占性资源。 不可抢占资源不可抢占资源 一旦系统把某资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放。 磁带机、刻录机、打印机等也都属于不可抢占性资源。 4.5.2 计算机系统中的死锁 死锁的起因，通常是源于多个进程对资源的争夺，不仅对不可抢占资源进行争夺时，会引起死锁，而且对可消耗资源进行争夺时，也会引起死锁。 1.1.竞争不可抢占资源引起死锁竞争不可抢占资源引起死锁 共享文件时的死锁情况共享文件时的死锁情况 进程之间通信时的死锁进程之间通信时的死锁 2.2.竞争可消耗资源引起死锁竞争可消耗资源引起死锁顺序顺序1 1：P1P1： send sen

33、d（p2 , m1p2 , m1）；）； receivereceive（p3, m3p3, m3）；）； P2P2： send send（p3 , m2p3 , m2）；）； receivereceive（p1, m1p1, m1）；）； P3P3： send send（p1 , m3p1 , m3）；）； receivereceive（p2, m2p2, m2）；）； 顺序顺序2 2：P1P1： receive receive（p3, m3p3, m3）；）； sendsend（p2 , m1p2 , m1）；）； P2P2： receive receive（p1, m1p1, m1）；）；

34、 sendsend（p3 , m2p3 , m2）；）； P3P3： receive receive（p2, m2p2, m2）；）； sendsend（p1 , m3p1 , m3）；）； 死锁死锁4.5.3 死锁的定义、必要条件和处理方法 1.1.死锁的定义死锁的定义 如果一组进程中的每一个进程都在等待，仅由该组进程中的其它进程才能如果一组进程中的每一个进程都在等待，仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的。引发的事件，那么该组进程是死锁的。 2.2.产生死锁的必要条件产生死锁的必要条件 互斥条件：互斥条件：进程对所分配到的资源进行排它性使用。 请求和保持条件：请求和保

35、持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。 不可抢占条件不可抢占条件：进程已获得的资源，在未使用完之前不能被抢占，只能在进程使用完时由自己释放。 循环等待条件：循环等待条件：指在发生死锁时，必然存在一个进程资源的循环链，即进程集合P0，P1，P2，Pn中的P0，正在等待一个P1占用的资源， P1正在等待P2占用的资源，Pn正在等待已被P0占用的资源。4.5.3 死锁的定义、必要条件和处理方法 3.3.处理死锁的方法处理死锁的方法 预防死锁：预防死锁：这是一种较简单和直观的事先预防方法。该方法是通过设置

36、某些限制条件，去破坏产生死锁四个必要条件中的一个或几个来预防产生死锁。预防死锁是一种较易实现的方法，已被广泛使用。 避免死锁：避免死锁：同样是属于事先预防策略，但它并不是事先采取各种限制措施，去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而可以避免发生死锁。 检测死锁：检测死锁：这种方法无须事先采取任何限制性措施，允许进程在运行过程中发生死锁。但可通过检测机构，及时地检测出死锁的发生，然后采取适当措施，把进程中从死锁中解脱出来。 解除死锁：解除死锁：当检测到系统中已发生死锁时，就采取相应措施，将进程从死锁状态中解脱出来。常用的方法是撤消一些进程，

37、回收它们的资源，将它们分配给已处于阻塞状态的进程，使其能继续运行。返回第四章第四章 处理机调度与死锁处理机调度与死锁4.6 4.6 预防死锁预防死锁1. 破坏“请求和保持”条件 第一种协议第一种协议 该协议规定，所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。 优点：优点：简单、易行且安全。 缺点：缺点： 资源被严重浪费，严重地恶化了资源的利用率。 使进程经常会发生饥饿现象。 第二种协议第二种协议 允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再请求新的所需资源。 能使进程更快的完成任务，提高设备的

38、利用率，还可减少进程发生饥饿的机率。2. 破坏“不可抢占”条件 为了能破坏“不可抢占”条件，协议中规定，当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着进程已占有的资源会被暂时地释放，或者说是被抢占了，从而破坏了“不可抢占”条件。 缺点：缺点： 实现复杂，需付出很大的代价。 因为反复地申请和释放资源，致使进程的执行被无限地推迟，这不仅延长了进程的周转时间，而且也增加了系统开销，降低了系统吞吐量。3. 破坏“循环等待”条件 一个能保证“循环等待”条件不成立的方法是，对系统所有资源类型进行线性排序，并赋予不同

39、的序号。设R=（R1，R2，R3,，Rm）为资源类型的集合，为每个资源类型赋予唯一的序号。如果系统中有磁带驱动器、硬盘驱动器、打印机，则函数F可按如下来定义： F（tape drive）= 1； F (disk drive) = 5； F (printer) =12； 在对系统所有资源类型进行线性排序后，便可采用这样的预防协议：规定规定每个进程，必须按序号递增的顺序请求资源。每个进程，必须按序号递增的顺序请求资源。一个进程在开始时，可以请求某类资源Ri的单元。以后，当且仅当F(Rj)F(Ri)时，进程才可以请求资源Rj的单元。如果需要多个同类资源单元，则必须一起请求。 在采用这种策略时，应如何

40、来规定每种资源的序号是十分重要的。通常应根据大多数进程需要资源的先后顺序来确定。 这种预防死锁的策略与前两种策略比较，其资源利用率和系统吞吐量，都有较明显的改善。但也存在下述问题： 限制了新类型设备的增加； 作业使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费。 限制了用户简单、自主地编程。返回第四章第四章 处理机调度与死锁处理机调度与死锁4.7 4.7 避免死锁避免死锁4.7.1系统安全状态 1.1.安全状态安全状态 指系统能按某种进程推进顺序（指系统能按某种进程推进顺序（P1P1，P2P2，PnPn），为每个进程），为每个进程PiPi分配其分配其所需资源，直至满足每个进程对资源的最

41、大需求，使每个进程都可顺利地完成。所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。此时称（此时称（P1P1，P2P2，PnPn）为安全序列。如果系统无法找到这样一个安全序列，）为安全序列。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。则称系统处于不安全状态。 2.2.安全状态之例安全状态之例 假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：进程进程最最 大大 需需 求求已已 分分 配配可用可用

42、P P1 110105 53 3P P2 24 42 2P P3 39 92 24.7.1系统安全状态 3.3.由安全状态向不安全状态的转换由安全状态向不安全状态的转换 如果不按照安全序分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。 因为，此时也无法再找到一个安全序列， 例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。 4.7.2 利

43、用银行家算法避免死锁 银行家算法中的数据结构银行家算法中的数据结构 (1)(1)可利用资源向量可利用资源向量AvailableAvailable：是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K，则表示系统中现有Rj类资源K个。 (2)(2)最大需求矩阵最大需求矩阵MaxMax：是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。 (3) (3) 分配矩阵分配矩阵Allo

44、cationAllocation：也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的数目为K。 (4) (4)需求矩阵需求矩阵NeedNeed：也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 NeedNeedi,ji,j=Max=Maxi,ji,j-Allocation-Allocationi,ji,j 4.7.2 利用银行家算法避免死锁 银行家算法银行家算法 设Requesti是进程Pi的请求向量，如果Request

45、ij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1)如果RequestijNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2)如果RequestijAvailablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 (3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij; (4)系统执行

46、安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 4.7.2 利用银行家算法避免死锁 安全性算法安全性算法 (1)设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false; 当有足够资源分配给进程时， 再令Finishi=true。 (2)从进程集合中找到一个能满足下

47、述条件的进程： Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。 (3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj=Worki+Allocationi,j; Finishi=true; go to step 2; (4)如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。 4.7.2 利用银行家算法避免死锁 银行家算法之例银行家算法之例 假定系统中有五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为10

48、、5、7，在T0时刻的资源分配情况如图 3-15 所示。 T T0 0时刻的资源分配表时刻的资源分配表银行家算法之例 银行家算法之例银行家算法之例 (1)T0(1)T0时刻的安全性：时刻的安全性： 银行家算法之例 银行家算法之例银行家算法之例 (1)T0(1)T0时刻的安全性：时刻的安全性： T T0 0时刻的安全序列时刻的安全序列银行家算法之例 (2)P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系统先假定可为P

49、1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如图 3-15 中的圆括号所示。 再利用安全性算法检查此时系统是否安全。 银行家算法之例 (3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查： Request4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0) Available(2, 3, 0)，让P4等待。 (4) P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查： Request0(0, 2, 0)Need0(7, 4, 3

50、); Request0(0, 2, 0)Available(2, 3, 0); 系统暂时先假定可为P0分配资源，并修改有关数据，如图所示。 返回第四章第四章 处理机调度与死锁处理机调度与死锁4.8 4.8 死锁的检测与解除死锁的检测与解除 4.8.1 死锁的检测 允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生。 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。 1.1.资源分配图资源分配图 该图是由一组结点N，和一组边E所组成的一个对偶G=（N，E），它具有下述形式的定义和限制： （1）把N分为两个互斥的子集，即一组进程结点P=p1，p2，pn和一组资源结点

51、R=r1，r2，rn，N=PR。在图3-19 所示的例子中，P=p1，p2，R=r1，r2，N=r1，r2p1，p2。 （2）凡属于E中的一个边eE，都连接着P中的一个结点和R中的一个结点，e=pi，rj是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的rj资源。e=rj，pi是资源分配边，由资源rj指向进程pi，它表示把一个单位的资源rj分配给进程pi。图4-18中示出了两个请求边和两个分配边，即E=（p1，r2），（r2，p2），（p2，r1），（r1，p1）。返回4.8.1 死锁的检测 允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生。 一旦死锁发生则采取专门

52、的措施，解除死锁并以最小的代价恢复操作系统运行。 1.1.资源分配图资源分配图 该图是由一组结点N，和一组边E所组成的一个对偶G=（N，E），它具有下述形式的定义和限制： 把N分为两个互斥的子集，即一组进程结点P=p1，p2，pn和一组资源结点R=r1，r2，rn，N=PR。在图3-19 所示的例子中，P=p1，p2，R=r1，r2，N=r1，r2p1，p2。 凡属于E中的一个边eE，都连接着P中的一个结点和R中的一个结点，e=pi，rj是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的rj资源。e=rj，pi是资源分配边，由资源rj指向进程pi，它表示把一个单位的资源rj分配

53、给进程pi。图中示出了两个请求边和两个分配边，即E=（p1，r2），（r2，p2），（p2，r1），（r1，p1）。 我们用圆圈代表一个进程，用方框代表一类资源。4.8.1 死锁的检测 2 2死锁定理死锁定理 我们可以利用把资源分配图加以简化的方法（下图），来检测当系统处于S状态时，是否为死锁状态。4.8.1 死锁的检测 简化方法简化方法 在资源分配图中，找出一个既不阻塞又非独立的进程结点Pi。在顺利的情况下，Pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去pi的请求边和分配边，使之成为孤立的结点。在图4-19（a）中，将p1的两个分配边和一个请求边消去，便形

54、成图（b）所示的情况。 p1释放资源后，便可使p2获得资源而继续运行，直至p2完成后又释放出它所占有的全部资源，形成图（c）所示的情况。 在进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。 对于较复杂的资源分配图，可能有多个既未阻塞，又非孤立的进程结点，不同的简化顺序，是否会得到不同的简化图 有关文献已经证明，所有的简化顺序，都将得到相同的不可简化图。 同样可以证明：S S为死锁状态的充分条件是：为死锁状态的充分条件是： 当且仅当当且仅当S S状态的资源分配图状态的资源分配图是不可完全

55、简化的。该充分条件被称为死锁定理。是不可完全简化的。该充分条件被称为死锁定理。4.8.1 死锁的检测 3 3死锁检测中的数据结构死锁检测中的数据结构 死锁检测中的数据结构，类似于银行家算法中的数据结构： 可利用资源向量Available，它表示了m类资源中每一类资源的可用数目。 把不占用资源的进程（向量Allocation=0）记入L表中，即LiL。 从进程集合中找到一个RequestiWork的进程，做如下处理：将其资源分配图简化，释放出资源，增加工作向量Work：=Work + Allocation i。将它记入L表中。 若不能把所有进程都记入L表中，便表明系统状态S的资源分配图是不可完全

56、简化的。因此，该系统状态将发生死锁。Work：=Available；L：=Li |Allocation i=0Request i=0for all Li L dobeginfor all Request iWork dobeginWork:=Work + Allocation i；LiL；endenddeadlock:=（L=p1，p2，pn）；4.8.2 死锁的解除 当发现有进程死锁后，便应立即把它从死锁状态中解脱出来，常采用的方法有： 剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态； 撤消进程：可以直接撤消死锁进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态消除为止。 1.1.终止进程的方法终止进程的方法 终止所有死锁进程：这是一种最简单的方法，即是终止所有的死锁进程，死锁自然也就解除了，但所付出的代价可能会很大。 逐个终止进程：稍微温和的方法是，按照某种顺序，逐个地终止进程，直至有足够的资源，以打破循环等待，把系统从死锁状态解脱出来为止。但该方法所付出的代价也可能很大。所谓代价是指优先级、运行代价、进程的重要所谓代价是指优先级、运行代价、进程的重要性和价值等。性和价值等。4.8.2 死锁的解除 2.2.付出代价最小的死锁解除算法付出代价最小的死锁解除算法 返回