1、1第三章 处理机调度与死锁3.13.1 处理机调度的层次3.2 3.2 调度队列模型和调度准则 3.3 3.3 调度算法 3.4 3.4 实时调度 3.5 3.5 产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法 3.7 3.7 死锁的检测与解除 2整 体 概 述THE FIRST PART OF THE OVERALL OVERVIEW,P L E A S E S U M M A R I Z E T H E C O N T E N T第一部分33.1 3.1 处理机调度的层次处理机三级调度1.1.高级调度作业调度 在批处理系统中，作业是先驻留在外存的输入井上的，因此需要有作业调度。然
2、而在分时系统中，通过键盘输入的命令和数据直接进入内存，无需作业调度。2.2.低级调度进程调度 进程调度决定就绪队列中哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。进程调度是最基本的调度，任何操作系统都有进程调度。3.3.中级调度对换 引入中级调度的目的是为了提高主存利用率和系统吞吐量。由于在进程并发执行过程中，为了充分发挥内存的效能，需将那些暂时不能运行的进程从内存调到外存盘交换区去等待，而将那些在盘交换区的等待事件已经发生急需调度运行的进程从盘交换区调入内存。4（1 1）作业 一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所作的有关该次业务处理的全部工作，
3、称为一个作业。（打印一个文件，发送一个E-mailE-mail）（2 2）作业步 一个作业可划分成若干部分，称为一个作业步。典型的作业控制过程分：“编译”“连接装配”“运行”1.1.作业的基本概念编译连接装配运行目标程序段目标程序源程序输入数据子程序库函数动态库函数计算结果（3 3）作业流3.1.1 3.1.1 高级调度5（1 1）作业说明书：表达用户对作业的控制意图。包括：作业的基本描述 作业控制描述 作业资源要求描述（2 2）作业控制语言：书写作业说明书的语言称为作业控制语言（JCLJCL）。包括：I/OI/O命令 编译命令 操作命令 条件命令2.2.批处理系统的作业管理6（3 3）作业控
4、制块（JCBJCB：Job Control BlockJob Control Block）v作业控制块是批处理作业存在的标 志,保存有系统对于作业进行管理所 需要的全部信息,位于磁盘区域中。v包含的信息数量及内容因系统而异v作业开始，系统输入程序为其建立 一个作业控制块，进行初始化，大 部分信息取自作业说明书。v系统输入程序、作业调度程序、作 业控制程序、系统输出程序等需要 访问作业控制块。v作业完成后，其作业控制块由系统 输出程序撤消。作业标知用户名称用户帐号调度信息资源需求作业状态作业类别输入井地址输出井地址进入系统时间开始处理时间作业完成时间作业退出时间资源使用情况 作业控制块JCB7（
5、4 4）作业表v每个作业有一个作业控制块v所有作业JCBJCB构成一个作业表v作业表存放在外存固定区域中，长度是固定v限制了系统所能同时容纳的作业数量 JCB1 JCB2 JCBi JCBn 作业表84.4.批处理作业的状态及转换 一个作业从进入系统到运行结束，经历“进入”、“后备”、“运行”、“完成”四个不同的状态。作业和进程的状态转换图数据进入状态退出状态后备状态运行状态作业控制进程 输入设备数据源程序输出设备作业说明书输入井运行等待就绪输出井输入程序输出程序作业调度进程调度95.5.作业的建立一个作业建立过程包括两个子过程：（1 1）作业的输入 将作业程序、数据和作业说明书从输入设备（例
6、如键盘）输入到外存，并形成初始信息。（2 2）JCBJCB的建立：JCBJCB包含对作业进行管理所必须的信息（作业名，估计执行时间，建立时间，优先数，内存、外设要求）JCBJCB表的数量是一个常数；外存输入井的大小有限，因此只有在获得JCBJCB表项和足够输入井空间后，作业才可能创建成功。106.6.作业调度 在每次执行作业调度时，都须做出以下两个决定。1)1)决定接纳多少个作业 2)2)决定接纳哪些作业 113.1.2 3.1.2 低级调度 进程调度的任务是控制协调进程（或内核级线程）对CPUCPU的竞争，即按一定的调度算法从就绪队列中选中一个进程，把CPUCPU的使用权交给被选中的进程。1
7、.1.低级调度的功能n保存处理机的现场信息；n按某种算法选取进程；n把处理机分配给进程。122.2.进程调度中的三个基本机制（1 1）排队器。把所有就绪进程按照一定方式排成一个或多个队列。（2 2）分派器（分派程序）。从就绪队列中选出进程，进行上下文切换，分配处理机。（3 3）上下文切换机制。发生两对上下文切换操作：操作系统保存当前进程的上下文，装入分派程序的上下文，以便分派程序运行；移出分派程序，把新选进程的CPUCPU现场信息装入处理机相应寄存器中。13可能引起进程调度的因素有：当一个进程运行完毕，或由于某种错误而终止运行当一个进程在运行中处于等待状态（等待I/OI/O）在进程通信中，执行
8、中的进程执行了某种原语操作（P P操作，阻塞原语，唤醒原语）分时系统中时间片到当有一个优先级更高的进程就绪3.3.进程调度方式1)非抢占方式(Non-preemptive Mode)(Non-preemptive Mode)2)抢占方式(Preemptive Mode)(Preemptive Mode)优先权原则。短作业(进程)优先原则。时间片原则。143.2 3.2 调度队列模型和调度准则 1.1.仅有进程调度的调度队列模型 仅具有进程调度的调度队列模型 3.2.1 3.2.1 调度队列模型 如分时系统。就 绪 队 列阻 塞 队 列进程调度CPU进程完成等待事件交互用户事件出现时间片完152
9、.2.具有高级和低级调度的调度队列模型 具有高、低两级调度的调度队列模型 就 绪 队 列进程调度CPU进程完成等待事件1作业调度事件1出现时间片完等待事件2事件2出现等待事件 n事件n出现后 备 队 列163.3.同时具有三级调度的调度队列模型 具有三级调度时的调度队列模型 就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现173.2.2 3.2.2 选择调度方式和调度算法的若干准则 1.1.面向用户的准则 (1)(1)周转时间短。n作业平均周转时间:T T（）niTi1n1n 周转时间:作业提交作业
10、完成之间的时间其中 n 作业流中的作业数Ti 第i个作业周转时间Ti=Ei Si其中 Ei 作业i提交时间Si 作业i完成时间182.2.面向系统的准则 系统吞吐量高。(2)处理机利用率好。(3)各类资源的平衡利用。(2)响应时间快。(3)截止时间的保证。(4)优先权准则。n平均带权周转时间 W W（）()()niriTi1n1其中 ri ri 某作业i i的实际执行时间n1niWi1193.3 3.3 调度算法1.先来先服务算法 FCFS：First Come First Serve 先来先服务算法是最简单的调度方法。其基本原则是按照作业到达系统的先后次序来选择。FCFS 策略是属于不可抢占
11、策略。3.3.1 3.3.1 调度算法20例：假设在单道批处理环境下有四个作业，已知它们进 入系统的时间、估计运行时间，应用先来先服务 算法，分别计算出作业的平均周转时间和带权的平 均周转时间。作作 业业进进 入入 时时 间间估估 计计 运运 行行时时 间间（分分 钟钟）开开 始始 时时 间间结结 束束 时时 间间周周 转转 时时 间间（分分 钟钟）带带 权权 周周 转转时时 间间JOB18：001208：0010：001201JOB28：505010：0010：501202.4JOB39：001010：5011：0012012JOB49：502011：0011：20904.5作作 业业 平平
12、 均均 周周 转转 时时 间间 T=112.5作作 业业 带带 权权 平平 均均 周周 转转 时时 间间 W =4.97545019.9先来先服务调度算法计算结果21 从表面上来说，对于所有进程和作业都是公平的，并且一个作业的等待时间是可以估计的。另一方面来说这个方法也不见得公平，当一个大作业先到达系统时就会使许多小作业等待很长时间，提高了平均的作业周转时间，会使许多小作业的用户不满。先来先服务算法已很少作主要的调度策略，常被结合在其它的调度策略中使用。例如，在使用优先级作为调度策略的系统中，往往对许多具有相同优先级的进程，使用先来先服务的原则。222.最短作业优先算法 SJF：Shortes
13、t Job First 以要求运行时间长短进行调度，即启动要求运行时间最短的作业。这个估计运行时间在作业的JCB中。假设系统中所有作业同时到达，可以证明采用SJF能得到最短的作业平均周转时间。23最短作业优先作业算法计算结果作作 业业进进 入入 时时 间间估估 计计 运运 行行时时 间间（分分 钟钟）开开 始始 时时 间间结结 束束 时时 间间周周 转转 时时 间间（分分 钟钟）带带 权权 周周 转转时时 间间JOB18：001208：0010：001201JOB28：505010：3011：201503JOB39：001010：0010：10707JOB49：502010：1010：3040
14、2作作 业业 平平 均均 周周 转转 时时 间间 T=95作作 业业 带带 权权 平平 均均 周周 转转 时时 间间 W =3.2538013例：假设在单道批处理环境下有四个作业，已知它们进 入系统的时间、估计运行时间，应用最短作业优先 算法，分别计算出作业的平均周转时间和带权的平 均周转时间。243.最高响应比优先算法 HRN：Highest Response Ratio Next 最高响应比优先作业算法计算结果作作 业业进进 入入 时时 间间估估 计计 运运 行行时时 间间（分分 钟钟）开开 始始 时时 间间结结 束束 时时 间间周周 转转 时时 间间（分分 钟钟）带带 权权 周周 转转时
15、时 间间JOB18：001208：0010：001201JOB28：503010：1011：00701.4JOB39：001010：0010：10707JOB49：502011：0011：20904.5作作 业业 平平 均均 周周 转转 时时 间间 T=87.5作作 业业 带带 权权 平平 均均 周周 转转 时时 间间 W =4.07535016.3例：25如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。对于长作业，作业的优先级可以随等待时间的增加而提
16、高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。高响应比优先算法特点：264.高优先权调度算法 （HPF：Highest Priority First）1）非抢占优先权算法 2）抢占式优先权算法优先权类型：静态优先权：在进程创建时指定优先数，在进程运 行时优先数不变。动态优先权：在进程创建时创立一个优先数，但在 其生命周期内优先数可以动态变化。如等待时间长优先数可改变。27基本思想：n根据系统运行情况和作业属性将作业分类n轮流从不同的作业类中挑选作业5.均衡调度算法(分类排队算法)例：将待处理作业分成如下队列：队列1 1：计算量大的作业 队列2 2：I/OI/O量大的作业
17、队列3 3：计算量与I/OI/O量均衡的作业v调度时，在三个队列中各取一些作业,在内存中的作业有的使用处理机,有的使用外部设备v使得系统的各种资源能得到充分利用28例：将待处理作业分成如下三个队列：队列1 1：长作业 队列2 2：中等长度作业 队列3 3：短作业v调度时取队列1 1一个作业，队列2 2一个作业，队列3 3一个作业v长作业用户和短作业用户均比较满意29例：在两道环境下有四个作业，已知它们进入系统 的时间、估计运行时间。系统采用短作业优先 作业调度算法，作业被调度运行后不再退出。当一新作业投入运行后，可按照作业运行时间 长短调整作业执行的次序。请给出这四个作业 的执行时间序列，并计
18、算出平均周转时间及带 权平均周转时间。补充：30作作 业业进进 入入 时时 间间估估 计计 运运 行行时时 间间（分分 钟钟）开开 始始 时时 间间结结 束束 时时 间间周周 转转 时时 间间（分分 钟钟）带带 权权 周周 转转时时 间间JOB110：003010：0011：05654.167JOB210：052010：0510：25201JOB310：10510：2510：30204JOB410：201010：3010：40202作作 业业 平平 均均 周周 转转 时时 间间 T=31.25作作 业业 带带 权权 平平 均均 周周 转转 时时 间间 W =2.7912511.167两道批处理
19、系统中最短作业优先算法计算结果四个作业的执行时间序列为：JOB1JOB1：1010：00100010：0505，1010：40114011：0505JOB2JOB2：1010：05100510：2525JOB3JOB3：1010：25102510：3030JOB4JOB4：1010：30103010：404031例1:1:有三个作业A A（到达时间8:508:50，执行时间1.51.5小 时）、B B（到达时间9:009:00，执行时间0.40.4小时）、C C（到达时间9:309:30，执行时间1 1小时）。当作业 全部到达后，单道批处理系统按照响应比高者 优先算法进行调度，则作业被选中的次
20、序是（）。A（ABC）B（BAC）C（BCA）D（CBA）E（CAB）F（ACB）A32解：作业运行情况见下表：当作业全部到达后，也就是9:30，系统开始调度。此刻各作 业的等待时间是，A为40分钟（0.67小时）、B为0.5小时、C为0小时。其响应比分别为：A=1+0.67/1.5=1.4；B=1+0.5/0.4=1.25；C=1+0/1=1系统首先选A运行，至11:00运行结束。各作业的等待时间是，B为2小时，C为1.5小时。其响应比分别修改为：B=1+2/0.4=6；C=1+1.5/1=2.5系统再选B运行，至11:24运行结束。最后选择C运行至12:24结束。因此，本题的正确答案应当是
21、A。进程到达时间运行长度开始时间结束时间A8:501.59:3011:00B9:000.411:0011:24C9:30111:2412:2433例2 2：有5 5个任务A A，B B，C C，D D，E E，它们几乎同时到达，预计 它们的运行时间为1010，6 6，2 2，4 4，8min8min。其优先级分 别为3 3，5 5，2 2，1 1和4 4，这里5 5为最高优先级。对于下列 每一种调度算法，计算其平均周转时间.(1)(1)先来先服务（按A A，B B，C C，D D，E E）算法。(2)(2)优先级调度算法。34 采用先来先服务（FCFS）调度算法时，5个任务在系统 中的执行顺序
22、、完成时间及周转时间如下表所示：执行次序运行时间优先数等待时间周转时间A103010B651016C221618D411822E842230根据表中的计算结果，5个进程的平均周转时间T为：T=（10+16+18+22+30）/5=19.2min35(2)采用最高优先级调度（HPF）算法时，5个任务在系统 中的执行顺序、完成时间及周转时间如下表所示：执行次序运行时间优先数等待时间周转时间B6506E84614A1031424C222426D112627它们的平均周转时间为：T=（6+14+24+26+27）/5=19.4min363.3.3 3.3.3 基于时间片的轮转调度算法 1.1.时间片轮
23、转法 把CPUCPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPUCPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPUCPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行。1)1)基本原理2)2)时间片大小确定 过大过小均不可取，较为可取的大小是，时间片略大于一次典型的交互所需要的时间，大多数进程可在一个时间片内完成。37 多级反馈队列就是综合了、和的 一种进程调度算法，其基本思想如下：（）系统按优先级别设置个就绪进程队列，第一级队列的优先级最高，以下逐级降低，第级队列的优先级最低；（）每个就绪队列对应有一个时间片Si（i，2,，n），且有，
24、以缓和低优先级队列中的进程不易获得调度而感到的不公平；（）除对第级队列按调度外，对其余各级队列均按调度；2.2.多队列反馈调度算法 38 （）系统每次总是调度级别较高的队列中的进程，仅当该队列为空时，才去 调度下一级队列中的进程；（）当现行进程正在执行它的周期时，如果发生了时间片中断或有进 程进入更高级的就绪队列时将引起剥夺，对前一种情况，现行进程将进入下一 级队列，对后一种情况，现行进程则进入本级队列末尾。当一进程被唤醒时，它进入的是原先离开的那个队列，即与其当前优先级对应的就绪队列。可见，一个进程的优先级被降低，仅发生在因时间片中断而被剥夺的时候。39多级反馈队列403.3.多级反馈队列调
25、度算法的性能 终端型作业用户。大多属于交互式作业，一个时间片内完成。短批处理作业用户。长批处理作业用户。不必担心长期得不到处理。413.4 3.4 实时调度 3.4.1 3.4.1 实现实时调度的基本条件 1.1.提供必要的信息 就绪时间。(2)开始截止时间和完成截止时间。(3)处理时间。(4)资源要求。(5)优先级。422.2.系统处理能力强 在实时系统中，通常都有着多个实时任务。假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件系统才是可调度的：miiiPC11 假如系统中有6个硬实时任务，它们的周期时间都是 50
26、 ms，而每次的处理时间为 10 ms，则不难算出，此时是不能满足上式的，因而系统是不可调度的。43补充：n 周期性实时任务：外部设备周期性的发出激励信号给计算机，要求它按指定周期循环执行，以便周期性地控制某外部设备。n 非周期性实时任务：外部设备所发出的激励信号并无明显的周期性，但都必须联系着一个截止时间(Deadline)。（开始截止时间任务在某时间以前必须开始执行；完成截止时间任务在某时间以前必须完成。）n 硬实时任务：系统必须满足任务对截止时间的要求，否则可能出现难以预测的结果。n 软实时任务：它也联系着一个截止时间，但并不严格，若偶尔错过了任务的截止时间，对系统产生的影响也不会太大。
27、443.3.采用抢占式调度机制 当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。对于一些小的实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制，以简化调度程序和对任务调度时所花费的系统开销。4.4.具有快速切换机制 (1)对外部中断的快速响应能力。(2)快速的任务分派能力。453.4.2 3.4.2 实时调度算法的分类 1.1.非抢占式调度算法 非抢占式轮转调度算法。(2)非抢占式优先调度算法。2.2.抢占式调度算法 (1)基于时钟中断的抢占式优先权调度算法。(2)
28、立即抢占的优先权调度算法。46图 实时进程调度(b)非抢占优先权调度当前进程实时进程实时进程请求调度当前进程运行完成调度时间当前进程实时进程实时进程请求调度实时进程枪占当前进程，并立即执行(d)立即抢占的优先权调度调度时间(a)非抢占轮转调度调度时间进程 1进程 2实时进程要求调度进程 n实时进程调度实时进程运行当前进程实时进程请求调度时钟中断到来时调度时间(c)基于时钟中断抢占的优先权抢占调度实时进程47 早期的操作系统对申请某种资源的进程，若该资源尚未分配时，立即将该资源分配给这个进程。后来发现，对资源不加限制地分配可能导致进程间由于竞争资源而相互制约以至于无法继续运行的局面，人们把这种局
29、面称为死锁(deadlock)。死锁问题在1965年由Dijkstra 发现，并随着计算机技术的发展，逐渐成为人们关心的问题。那么，什么是死锁？其确切的定义是什么？死锁是怎么产生的？用什么方法来解决死锁？3.5 3.5 产生死锁的原因和必要条件48死锁的示例例：日常生活中常有许多有关死锁。显然各路车队等待的事件都不会发生。(假设它们都不改变行车方向)这样若不采用特殊方法，它们将永远停留在这“井”字形的路上，而处于死锁状态。49 在计算机系统中，进程发生死锁与上述事例实质上是一样的。进程是因相互竞争资源而导致死锁的，与四路车队(可视为进程)竞争路口(可视为资源)类似。计算机系统中有各种资源，如外
30、设、数据、文件、程序等。死锁是指在多道程序系统中，一组进程中的每一个进程均无限期的等待被该组进程中的另一个进程占有且永远不会释放的资源，这种现象成系统处于死锁状态，处于死锁状态的进程称为死锁进程。死锁定义：503.5.1 3.5.1 产生死锁的原因1.1.竞争资源引起死锁v永久性资源（可重用资源）：可以被多个进程多次使用可抢占资源(CPUCPU、内存等)不可抢占资源(打印机、磁带机等)v临时性资源（消耗性资源）：只可使用一次的资源（信 号量,中断信号，同步信号等）2.2.进程推进顺序不合理引起死锁 在多道程序系统中，并发执行的进程推进序列不可予测，有些推进顺序，进程可以顺利完成，这些推进顺序是
31、合法的；而有的推进顺序会引起进程无限期地等待永远不会发生的条件而不能向前推进，造成了死锁。51Process P Process QProcess P Process Q.Get A Get BGet A Get B.Get B Get AGet B Get A.Release A Release BRelease A Release B.Release B Release ARelease B Release A.进程推进顺序不当引起死锁例：52Q进程P 和 Q申请 A死锁不可避免P 和 Q申请 BP进程获得A获得B释放A 释放B进程P P和Q Q按路径1,2,5,61,2,5,6推进顺序合
32、法，按3,43,4推进顺序非法释放A释放B获得A获得B申请A申请B申请B申请A53无死锁情况Q进程释放A释放B获得A获得B申请A申请BP 和 Q申请 AP 和 Q申请 BP进程获得A释放A获得B释放B申请A申请B543.3.产生死锁的例子v 申请不同类型资源产生死锁P1P1：申请打印机申请扫描仪使用释放打印机释放扫描仪P2P2：申请扫描仪申请打印机使用释放打印机释放扫描仪打印机扫描仪P1P2占有占有申请申请55v申请同类资源产生死锁（如内存）设有资源R R，R R有m m个分配单位，由n n个进程P P1 1,P,P2 2,P,Pn n（n mn m）共享。假设每个进程对R R的申请和释放符合
33、下列原则：*一次只能申请一个单位 *满足总申请后才能使用 *使用完后一次性释放vP、V操作不当产生死锁 如生产者-消费者 生产者进程 消费者进程 p(mutex);p(mutex);p(mutex);p(mutex);p(empty);p(full);p(empty);p(full);56v对临时性资源使用不当产生死锁 如进程间通信 若进程执行顺序如下：P1P1：请求S3S3，释放S1S1；P2P2：请求S1S1，释放S2S2；P3P3：请求S2S2，释放S3S3；S3P3S1P2P1S257n互斥（Mutual exclusion ）条件：一个资源一次只能被一个进程所使用，即是排它性使用。n
34、请求和保持（Hold-and-wait）条件：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已经获得的其它资源保持不放。n不剥夺（No preemption）条件：一个资源仅能被占有它的进程所释放，而不能被别的进程强占。n环路等待（Circular wait）条件：在出现死锁的系统中，一定存在一个进程资源的环形请求链。3.5.2 3.5.2 产生死锁的必要条件P0P1P2Pn.581.1.死锁的预防 静态方法：在进程执行前采取的措施，通过设置某些限制条件，去破坏产生死锁的四个必要条件之一，防止发生死锁。2.2.死锁的避免 动态方法：在进
35、程执行过程中采取的措施，不需事先采取限制措施破坏产生死锁的必要条件，而是在进程申请资源时用某种方法去防止系统进入不安全状态，从而避免发生死锁。3.4.3.4.死锁的检测和解除 这种方法预先并不采用任何限制措施，允许系统在运行过程中发生死锁，但可通过系统设置的检测机构及时检测死锁的发生，如果检测到死锁，则死锁解除方法使系统正常工作。3.5.3 3.5.3 处理死锁的基本方法593.6 3.6 预防死锁的方法(1)破坏“互斥”条件 对于临界资源必须互斥访问，这是某些资源使用时所必须要求的，不能加以改变，所以不易有解决方案。(2)破坏“不可剥夺”条件 在允许进程动态申请资源的前提下，规定一个进程在请
36、求新资源不能立即得到满足而变为等待状态，它必须释放已占有的全部资源；若需要，再重新申请新资源和已释放的资源。换言之，一个进程在使用某资源过程可以暂时放弃该资源，即允许其他进程剥夺使用该资源，从而破坏了“不剥夺”条件的出现。该策略实现起来相当困难，为了保护在自动放弃资源时的现场以及以后的恢复现场，需要付出很高的代价。特别是可能出现进程反复地申请和释放某些资源而被无限延迟执行。60()破坏“请求和保持”条件v进程申请到它所需要的所有资源后，才能开始运行，又称预先静态分配法。资源的利用率低；由于资源不能全部满足，而使作业无限期延长。v进程提出申请资源前必须释放已占有的一切资源。资源的利用率低 61(
37、4)破坏“环路等待”条件q给系统中的资源编号(唯一)，例如输入机，打 印机，磁带机，磁盘机等等q寻找一个函数F：RN(R：表资源类集合)即 r1,r2,ri 12iF(ri)=iq每个进程只能按序号由小到大的顺序申请资源，否则系统不予分配。采用资源顺序分配法，可以破坏循环等待条件。62比如：某一进程已占有资源r1,r2,ri，又申请ri+1，资源分配程序则检查是否有 j 1,2,i，有 F(rj)F(rj+1)，若不满足则拒绝分配。采用资源顺序分配法，系统不会出现循环等待。因为在任何时刻，总有一个进程占有较高序号的资源，该进程继续请示的资源必然是空闲的。故该进程可一直向前推进。(换言之，系统中
38、总有进程可以顺序运行完毕，这个进程执行结束后会释放它所占有的全部资源唤醒等待中的进程或满足其它进程的请求。)优点：有序资源分配法提高了资源利用率缺点：顺序号与实际需要资源的顺序不一致，导致资源的浪费。633.6.2 3.6.2 死锁的避免 该方法允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统从安全状态向不安全状态转换，便可将资源分配给进程；否则不分配资源，进程必须阻塞等待。从而避免发生死锁。安全状态:在此状态系统能按某种顺序P1,P2 Pn来为各个进程分配其所需资源，使每个进程都可顺序地一个个地完成。这个序列P1,P2.Pn称为安全序列。不安全状
39、态:系统不存在任何一个安全序列。安全序列P1、P2Pn：对于每一个进程P Pi i(1(1i in n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程P Pj j(j i)(j i)当前占有资源量之和。64例：假如系统中有P P1 1、P P2 2和P P3 3三个进程和1212台磁带机。各进程最大需求和T T0 0时刻分配状态如下：进程 最大需求 已分配 还需请求 剩余 P P1 1 10 10 5 5 5 5 3 3 P P2 2 4 4 2 2 2 2 P P3 3 9 9 2 2 7 7T T0 0状态，可以找到一个安全序列PP2 2、P P1 1、P P3 3 如果在T T
40、0 0 状态不按安全序列进行分配，可能会导致 系统进入一个不安全状态.65假设:在T T0 0状态下P P3 3中申请1 1台磁带机。系统实施此次分配使系统状态由T T0 0变为T T1 1 T1 T1时刻状态：进程 最大需求 已分配 还需请求 剩余 P P1 1 10 10 5 5 5 5 P P2 2 4 4 2 2 2 2 P P3 3 9 9 3 63 6 因为找不到一个安全序列使所有进程顺序地一个个地运行完毕，所以T1T1状态是不安全状态由于实施分配给1 1台磁带机给P3P3的操作会引起系统状态由安全状态T0T0向不安全状态下的转换，所以为了避免死锁，上述的分配只是安全检测，检测后判
41、定这样的申请不能满足，P3P3为申请1 1台磁带机而必须阻塞等待。663.6.3 3.6.3 利用银行家算法避免死锁v银行家算法的数据结构可用资源向量 Available mAvailable m m m为系统中资源种类数，Availablej=kAvailablej=k表示系统中第j j 类资源数为k k个。最大需求矩阵MaxnmMaxnm n n为系统中进程数，Maxij=kMaxij=k表示进程i i对j j类资源的 最大需求数为k k。分配矩阵AllocationnmAllocationnm Allocationij=k Allocationij=k表示进程i i已分得j j类资源的数
42、目为 k k个。需求矩阵NeednmNeednm Needij=k Needij=k 表示进程i i还需要j j类资源k k个。Needij=Maxij-AllocationijNeedij=Maxij-Allocationij最具代表的避免死锁算法是DijkstraDijkstra的银行家算法，这是由于该算法用于银行系统现金贷款的发放而得名。67v银行家算法介绍 假设在进程并发执行时进程i i提出请求j j类资源k k个后，表示为RequestRequesti ij=k,j=k,系统按下述步骤进行安全检查：如果RequestRequesti iNeedNeedi i则继续以下检查，否则显示需
43、求申请超出最大需求值的错误。如果RequestRequesti iAvailableAvailable则继续以下检查，否则显示系统无足够资源，P Pi i阻塞等待。系统试探把要求的资源分配给进程i i并修改有关数据结构的值：Available=Available-Request Available=Available-Requesti i；AllocationAllocationi i=Allocation=Allocationi i+Request+Requesti i ；NeedNeedi i=Need=Needi i-Request-Requesti i ；系统执行安全性算法，检查此次资
44、源分配后，系统是否处于安全状态，若安全，才正式将资源分配给进程i i，以完成本次分配；否则将试探分配作废，恢复原来的资源分配状态，让进程P Pi i等待。68安全性算法:A.A.设置WorkmWorkm表示系统可提供给进程的各类资源数目。初始化：Work=AvailableWork=Available，设置完成标志向量 FinishnFinishn。初始化：Finishi=falseFinishi=false表示i i进程尚末完成B.B.从进程集合n n中找到一个能满足下述二个条件:Finishi=falseFinishi=false，NeedNeedi iWorkWork如找到则执行步骤C
45、C，找不到则执行步骤D DC.C.当进程i i获得资源后可顺利执行直到完成，并释放出分配给它的资源，表示如下：work=work+Allocationwork=work+Allocationi i；Finishi=true Finishi=true；转执行步骤B B。D.D.如果所有的FinishiFinishitureture，则表示系统处于安全状态，否则系统处于不安全状态。69v银行家算法实例：假定系统中有五个进程P0、P1、P2、P3、P4和三种类型资源A、B、C，每一种资源的数量分别为10、5、7。各进程的最大需求、T0时刻资源分配情况如下 所示。MaxMax Allocation N
46、eed Available A B CA B C A B C A B C P0 7 5 3 0 1 0 7 4 3 10 4 7 P1 3 2 22 0 0 1 2 2 3 3 2 P2 9 0 2 3 0 2 6 0 0 7 4 5 P3 2 2 2 2 1 1 0 1 1 5 3 2 P4 4 3 3 0 0 2 4 3 1 7 4 3 试问：T T0 0时刻是否安全？P P1 1请求资源RequestRequest1 1(1,0,2)(1,0,2)是否允许？P P4 4请求资源RequestRequest4 4(3,3,0)(3,3,0)是否允许？70T T0 0时刻是否安全？从表中可找
47、出一个序列P1、P3、P4、P2、P0 使各进程 顺序地一个个地执行完成。workwork need Alocationwork+Alocation Finish P1 3 3 2 1 2 2 2 0 0 5 3 2 TrueP1 5 3 2 0 1 1 2 1 1 7 4 3 True P2 7 4 3 4 3 1 0 0 2 7 4 5 True P3 7 4 5 6 0 0 3 0 2 10 4 7 TrueP4 10 4 7 7 4 3 0 1 0 10 5 7 True安全序列为P1、P3、P4、P2、P0，T0时刻系统是安全的。71(1)Request(1)Request1 1(1
48、,0,2)Need(1,0,2)Need1 1(1,2,2)(1,2,2)(2)Request(2)Request1 1(1,0,2)Available(3,3,2)(1,0,2)Available(3,3,2)(3)(3)试探把要求的资源分配给进程P1并修改有关数据结构Available=Available(3,3,2)-Rquest1(1,0,2)=Available(2,3,0)；Need1=Need1(1,2,2)Request1(1,0,2)=Need1(0,2,0)；Allocation1=Allocation1(2,0,0)+Request1(1,0,2)=Allocation1
49、(3,0,2)；P P1 1请求资源RequestRequest1 1(1,0,2)(1,0,2)可否允许？可找到安全序列P1,P3,P4,P2,P0,可将资源分配给进程P1.T1时刻资源分配情况如下 所示:MaxMax Allocation Need Available A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 2 3 0 P1 3 2 2 3 0 2 0 2 0P2 9 0 2 3 0 2 6 0 0P3 2 2 2 2 1 1 0 1 1P4 4 3 3 0 0 2 4 3 172 P P4 4请求资源RequestRequest4 4(3
50、,3,0)(3,3,0)是否允许？(1)Request(1)Request4 4(3,3,0)Need(3,3,0)Need4 4(4,3,1).(4,3,1).(2)Request(2)Request4 4(3,3,0)Available(2,3,0)(3,3,0)Available(2,3,0)不成立，即可用 资源暂不能满足P P4 4请求资源需要，P P4 4阻塞等待。733.7 3.7 死锁的检测与解除v允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生，一旦死锁发生则采取专门的 措施，解除死锁，并以最小的代价恢复操作系统 运行。74(1)资源分配图系统资源分配图 SRAG=
