第四章 调度与死锁

Resource = (R1, R2, … ，Rm) Available = (V1, V2, … ，Vm)
Max =
M11 M12 … M1m M21 M22 … M2m …… …… Mn1 Mn2 … Mnm C11 C12 … C1m C21 C22 … C2m …… …… Cn1 Cn2 … Cnm A11 A12 … A1m A21 A22 … A2m …… …… An1 An2 … Anm
存在安全序列<P2,P1,P3> 存在安全序列
安全状态
——实例
系统有三个进程P1、 、 ，共有12台磁带机 台磁带机， 系统有三个进程 、P2、P3，共有 台磁带机，进程 P1要求 台，P2要求 台，P3要求 台。在T0时刻， 要求10台 要求4台 要求9台 时刻， 要求 要求 要求 时刻 进程P1、 、 已获得 已获得7、 、 台 尚有1台未分配 台未分配， 进程 、P2、P3已获得 、2、2台，尚有 台未分配， 系统是否处于安全状态？ 问：系统是否处于安全状态？ 进程 P1 P2 P3 最大需求 10 4 9 已分配 7 2 2 可用 1
第4 章
调度与死锁
●调度类型与准则
本章要点
●调度算法
●死锁的基本概念 ●死锁的预防与避免 ●死锁的检测与解除
●
4.3 死锁的基本概念
一组竞争系统资源或相互通信的进程相互的“永久” 一组竞争系统资源或相互通信的进程相互的“永久” 阻塞。若无外力作用，这组进程将永远不能继续执行。 阻塞。若无外力作用，这组进程将永远不能继续执行。
不存在安全序列， 不存在安全序列，系统处于不安全状态
死锁的避免
●不安全状态：可能死锁 不安全状态： ●安全状态：一定能避免死锁 安全状态：

时间片完 进程调度 进程完成
就 绪 队 列
CPU
事件1出现
等待事件 1
事件2出现
… … …
等待事件 2
…
等待事件 n 事件n 出现
图 3-3 具有高、低两级调度的调度队列模型
4 同时具有三级调度的调度队列模型
在通用系统的多模式OS中，一般采用具有三级调
度的调度队列模型，由于多ቤተ መጻሕፍቲ ባይዱ式OS同时支持批处理、
外存、I/O设备等）也是一个重要指标，对于微型机
和某些实时系统，该准则也不重要。
3.3 调 度 算 法
3.3.1 先来先服务First-Come-First-Served （FCFS）
（作业／进程）调度算法
FCFS是一种最简单的调度算法，可用于作业 或进程调度。此算法的原则是按照作业到达后备作 业队列（或进程进入就绪队列）的先后次序来选择 作业（或进程）。
请看下例：
3.3.2 短作业／进程优先(Shortest Process First)调度
算法
短进程(SPF)的调度算法从内存就绪队列中选则一个
运行时间最短的进程到处理机中执行。
对作业调度来说，是指从作业的后备队列中选则一
个或若干个短作业到内存就绪队列。
短作业(SJF)的调度算法可以照顾实际上占很大比例
3 具有高级调度和低级调度的调度队列模型
在多道批处理系统中，一般处理机管理设臵作业和
进程两级调度。它比第一个模型增加了高级调度。 模型增加了在磁盘的作业后备队列，作业调度的任 务是从作业后备队列中选一个作业为它创建至少一 个进程，并分配资源，将它排入内存进程就绪队列 末尾。如下图所示：
作业 调度 后 备 队 列
第三章 调度和死锁 (Scheduling and Deadlock )

第四章一.选择题1.预防死锁不可以去掉以下__A__条件。

A．互斥 B.请求与保持 C.不可剥夺 D.环路2.资源分配图是否可以完全简化是判断死锁的_C__。

A．充分条件 B.必要条件 C.充分必要条件 D.什么也不是3.设有4个作业同时到达，每个作业的执行时间是2min，它们在一台处理机上按单道方式运行，则平均周转时间为_B__。

A．1min B.5min C.2.5min D.8min4.若系统中有8台绘图仪，有多个进程均需要使用两台，规定每个进程一次仅允许申请一台，则至多允许_C__各进程参与竞争，而不会发生死锁。

A.5 B .6 C .7 D .85.响应比高者优先作业调度算法除了考虑进程在CPU上的运行时间，还考虑以下__D_因素。

A.输入时间B.完成时间C.周转时间D.等待时间6.产生系统死锁的原因可能是_B__。

A.一个进程进入死循环B.多个进程竞争资源出现了循环等待C.进程释放资源D.多个进程竞争共享型设备7.以下_B__方法可以解除死锁。

A.挂起进程B.剥夺资源C.提高进程优先级D.降低进程优先级8.采用有序分配资源的策略可以破坏产生死锁的__D_。

A.互斥条件B.请求与保持条件C.不可剥夺条件D.环路条件9.连个进程争夺同一个资源_B__。

A.一定死锁B.不一定死锁C.不死锁D.以上说法都不对10.以下解决死锁的方法中，属于预防策略的是_C__。

A.化简资源分配图B.银行家算法C.资源的有序分配D.死锁检测法11.下面__D_说法是对可剥夺系统的正确描述。

A.时间片轮转法是一种可剥夺式调度B.进程因等待某一事件而引起系统调度是一种可剥夺式调度C.实时系统采用可剥夺式调度D.优先级低的进程放弃CPU，让优先级高的进程运行12.以下关于调度的说法__A__正确。

A.进程通过调度得到CPUB.优先级是进程调度的主要依据，一旦确定就不能改变C.在单CPU的系统中，任何时刻都有一个进程处于运行状态D.进程申请CPU得不到时，其状态为阻塞13.既考虑进程的等待时间，又考虑进程的执行时间的调度算法是__A__。

SPN
缺点
– – – – 对长作业不利 完全不考虑紧迫程度，使紧急事件得不到处理。 完全不考虑紧迫程度，使紧急事件得不到处理。 作业或进程的长短只能估计，不准确。 作业或进程的长短只能估计，不准确。 极端情况下，长作业得不到调度。 极端情况下，长作业得不到调度。
2.短作业优先 短作业优先SPN 短作业优先 短作业优先算法的变种： 短作业优先算法的变种： 最短剩余时间优先SRT 最短剩余时间优先
完成时间＝ 前一个作业完成时间＋ 完成时间＝ 前一个作业完成时间＋服务时间 周转时间＝完成时间－ 周转时间＝完成时间－到达时间 带权周转时间＝ 带权周转时间＝周转时间 / 服务时间
2.短作业优先 短作业优先SPN 短作业优先 算法基本思想
– 对短作业或短进程优先调度
SPN
方法
– 对于作业调度，从后备队列中选择估计运行时 对于作业调度， 间最短的作业，将它们调入内存。 间最短的作业，将它们调入内存。 – 对于进程调度，从就绪队列中选择估计运行时 对于进程调度， 间最短的进程，将处理机分配给它， 间最短的进程，将处理机分配给它，使之执行 并一直到完成或因发生某事件而阻塞放弃处理 机时，再重新调度。 机时，再重新调度。
●是一种较好的进程调度算法
多级反馈队列调度算法MFQ 多级反馈队列调度算法
S1 新进程 就绪队列1 S2 就绪队列2 S3 就绪队列3 …… Sn 就绪队列n 时间片 S1 < S2 < S3< … < Sn
CPU

退出
CPU
退出
● ——
作业
P108/
●
5
确定因素：进程类型、进程对资源的需求、用户要求。 确定因素：进程类型、进程对资源的需求、用户要求。