计算机操作系统第四版第3章处理机调度与死锁

1、第三章 处理机调度与死锁 第三章处理机调度与死锁 3.1 处理机调度的层次处理机调度的层次3.2 调度队列模型和调度算法的目标调度队列模型和调度算法的目标3.3 调度算法调度算法3.4 实时调度实时调度 （不讲）（不讲）3.5 死锁概述死锁概述3.6 预防死锁预防死锁3.7 避免死锁避免死锁3.8 死锁的检测与解除死锁的检测与解除 第三章 处理机调度与死锁 （1 1）作业）作业 作业是一个比程序更为广泛的概念，它不仅包含作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份了通常的程序和数据，而且还应配有一份作业说作业说明书明书，系统根据该说明书来对程序的运行进行控系统

2、根据该说明书来对程序的运行进行控制制。 在批处理系统中，是以作业为基本单位从外存调在批处理系统中，是以作业为基本单位从外存调入内存的。入内存的。 批处理系统作业处理作业的基本概念第三章 处理机调度与死锁 （2）作业步 在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，把其中的每一个加工步骤称为一个作业步。 典型的作业控制过程： “编译”、“链接装配”、“运行”批处理系统作业处理作业的基本概念第三章 处理机调度与死锁 典型的作业步典型的作业步编译编译连接装配连接装配运行运行目标目标程序程序段段目标目标程序程序源程序源程序输入数据输入数据子程序子程序库函数库函

3、数动态库函数动态库函数计算结果计算结果作业的基本概念第三章 处理机调度与死锁 （3）作业流 若干个作业进入系统后，被依次存放在外存上，这便形成了输入作业流； 在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。批处理系统作业处理作业的基本概念第三章 处理机调度与死锁 （1）作业控制语言作业说明书是用户用于描述批处理作业处理过程控制意图的一种特殊程序。书写作业说明书的语言称为作业控制语言（JCL）（2）作业控制语言的类别 包括：I/O命令、编译命令、操作命令以及条件命令等（3）作业说明书表达用户对作业的控制意图内容：作业的基本描述作业控制描述资源要求描述批处理作业控制语言与作业说明书第

4、三章 处理机调度与死锁 （1）作业控制块（JCB：Job Control Block）是批处理作业在系统中存在的标志，保存有系统对于作业进行管理和调度所需的全部信息，位于磁盘区域中。作业控制块JCB和作业：一一对应关系（2）作业控制块的内容作业控制块中所包含的信息数量及内容因系统而异作业控制块与作业表作业标识作业标识用户名称用户名称用户帐号用户帐号调度信息调度信息资源需求资源需求作业状态作业状态作业类型作业类型输入井地址输入井地址输出井地址输出井地址进入系统时间进入系统时间开始处理时间开始处理时间作业完成时间作业完成时间作业退出时间作业退出时间资源使用情况资源使用情况第三章 处理机调度与死锁

5、（3）作业控制块的建立 当作业开始由输入设备向磁盘的输入井传输时，作业注册程序为其建立一个作业控制块，进行初始化，初始化的大部分信息取自作业说明书。（4）作业控制块的使用需要访问作业控制块的程序：作业注册程序作业调度程序作业控制程序系统输出程序 终止作业程序作业控制块与作业表第三章 处理机调度与死锁 （5）作业控制块的撤消作业执行完成后，其作业控制块由系统撤消作业控制块被撤消后其作业也不复存在（6）作业表 每个作业有个作业控制块 所有作业JCB构成一个作业表 作业表存放在外存固定区域中，长度是固定的 限制了系统所能同时容纳的作业数量JCB1 JCB2 JCBi JCBn 作业表作业表作业控制块

6、与作业表第三章 处理机调度与死锁 一个作业从进入系统到运行结束，需要经历三个阶段，处于三种状态： “收容” “后备” “运行” “运行” “完成” “完成” 批处理作业的状态及转换第三章 处理机调度与死锁 作业和进程的状态转换图作业和进程的状态转换图数据数据完成状态完成状态后备状态后备状态运行状态运行状态作业控制进程作业控制进程 输入设备输入设备数据数据源程序源程序输出设备输出设备作业说作业说明书明书输输入入井井运行运行等待等待就绪就绪输输出出井井输输入入程程序序输输出出程程序序作作业业调调度度进程进程调度调度批处理作业的状态及转换第三章 处理机调度与死锁 分时系统中用户控制作业的执行大致有四

7、个阶段：终端的连接用户登录控制作业执行用户退出分时系统的作业管理第三章 处理机调度与死锁 (1) 终端的连接必须使终端设备与计算机系统在线路上接通近程终端是直接与计算机系统连接的，当终端设备加电后，终端就与计算机系统在线路上接通了远程终端通过租用专线或交换线接到计算机系统，在终端加电后用户还需通过电话拨号进行呼叫，直到接通分时系统的作业管理第三章 处理机调度与死锁 (2) 用户登录用户必须向系统登录用户首先输入“登录”命令（LOGON）命令 系统会向询问用户名、作业名、口令和资源需求等经过识别用户、核对口令，系统在终端上显示“已登录”和进入系统的时间等信息若口令不对或资源暂时不能满足时，则系统

8、在终端上显示“登录不成功”并给出登录失败的原因用户的登录过程可看作是对终端作业的作业调度分时系统的作业管理第三章 处理机调度与死锁 (3) 控制作业执行登录成功的终端用户可从终端上输入作业的程序和数据使用系统提供的命令语言或会话语句控制作业执行每输入一命令或一会话语句后，由系统解释执行且在终端上显示执行成功或问题由用户决定下一步命令或会话直到作业完成分时系统的作业管理第三章 处理机调度与死锁 (4) 用户退出用户输入“退出”命令（LOGOFF 命令）请求退出系统系统接收命令后就收回该用户所占的资源让其退出同时在终端上显示“退出时间”或“使用系统时间”分时系统的作业管理第三章 处理机调度与死锁

9、处理机调度即对处理机进行分配。处理机调度即对处理机进行分配。 批处理系统中，一个作业，从进入系统并驻留在外存的后备队列上开始，直到作业运行完成，可能要经历三级处理机调度：高级调度高级调度中级调度中级调度低级调度低级调度3.1 处理机调度的层次处理机调度的层次第三章 处理机调度与死锁 1、高级调度、高级调度(High-Level Scheduling) 又称为作业调度、长程调度、接纳调度。 任务任务：（1）根据作业控制块中的信息，审查系统中的资源能否满足用户作业对资源的需求。（2）按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就

10、绪队列，准备执行。 两个决定两个决定：（1）接纳多少个作业取决于多道程序度（2）接纳哪些作业取决于所采用的调度算法第三章 处理机调度与死锁 2、低级调度、低级调度(Low-Level Scheduling) 又称为进程调度、短程调度。 主要功能主要功能：(1) 保存当前进程的处理机的现场信息。(2) 按某种算法从就绪队列中选取一个进程，把它的状态改为运行状态，并准备把处理机分配给它。 (3) 把处理器分配给进程。由分派程序把处理器分配给被选中的进程。为选中的进程恢复处理机现场，把处理器的控制权交给该进程。第三章 处理机调度与死锁 (1) 排队器 排队器把系统中的所有就绪进程按照一定策略排成一个

11、或多个队列。(2) 分派器(分派程序)。分派器把由进程调度程序所选定的进程，从就绪队列中取出，然后进行上下文切换，将处理机分配给它 (3) 上下文切换器第一对：当前进程上下文分派程序上下文第二对：分派程序上下文新选进程上下文进程调度中的三个基本机制进程调度中的三个基本机制第三章 处理机调度与死锁 进程调度方式进程调度方式1 1非抢占方式（非剥夺式调度）非抢占方式（非剥夺式调度） 原理：一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其他进程，决不允许某进程抢占已经分配出去的处理机。 引起进程调度的原因：（1）正在执行的进程执行完毕或因发生

12、某事件而无法再继续运行；（2）正在执行的进程提出I/O请求而暂停执行；（3） 进程通信或同步过程中，执行了某种原语操作（Block）。 特点：实现简单，系统开销较小，但不能反映各个进程重要、紧急程度的差异，难以满足紧急任务的要求。第三章 处理机调度与死锁 进程调度方式进程调度方式2 2抢占方式（剥夺式调度）抢占方式（剥夺式调度）原理：允许调度程序根据某种原则，暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。抢占原则：（1）优先权原则（2）短进程优先原则 （3）时间片原则特点：反映了进程的优先级特征，系统能及时处理紧急事件，但可能导致较大的系统开销，算法也相对复杂一些。第三章

13、 处理机调度与死锁 3、中级调度、中级调度(Intermediate-Level Scheduling) 又称为中程调度、内存调度。 引入了挂起状态的操作系统中有中级调度。 中级调度：用来决定把外存上的哪些又具备运行条件的静止就绪进程，重新调入内存，并修改其状态为活动就绪状态，挂在活动就绪队列上等待进程调度。第三章 处理机调度与死锁 3.2 调度队列模型和调度算法的目调度队列模型和调度算法的目标标3.2.1调度队列模型调度队列模型三种类型的调度队列模型：一仅有进程调度的调度队列模型二具有高级调度和低级调度的调度队列模型三同时具有三级调度的调度队列模型 第三章 处理机调度与死锁 一仅有进程调度的

14、调度队列模型分时系统 在分时系统中，用户键入的命令和数据，都直接送入内存。对于命令，由OS为之建立的一个进程。 仅有进程调度的调度队列模型：就 绪 队 列阻 塞 队 列进程调度CPU进程完成等待事件交互用户事件出现时间片完第三章 处理机调度与死锁 二具有高级调度和低级调度的调度队列模型批处理系统就 绪 队 列进程调度CPU进程完成等待事件 1作业调度事件1出现时间片完等待事件 2事件2出现等待事件 n事件n出现后 备 队 列第三章 处理机调度与死锁 三同时具有三级调度的调度队列模型就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队

15、列批量作业挂起事件出现事件出现第三章 处理机调度与死锁 3.2.2处理机调度算法的目标处理机调度算法的目标一、一、共同目标共同目标 1资源利用率 2公平性 3平衡性 4策略强制执行第三章 处理机调度与死锁 3.2.2处理机调度算法的目标处理机调度算法的目标二二批处理系统的目标批处理系统的目标 1平均周转时间短平均周转时间短 所谓周转时间周转时间，是指从作业提交给系统开始，到作业完成为止的这段时间间隔。它包括： （1）作业在外存后备队列上等待调度的时间； （2）进程在就绪队列上等待进程调度的时间； （3）进程在CPU上执行的时间； （4）进程等待I/O操作完成的时间。第三章 处理机调度与死锁 平

16、均周转时间平均周转时间可描述为：T=(Ti)/n; (i=1,2,.,n) 作业的周转时间T与系统为它提供的实际服务时间Ts之比，即W=T/Ts称为带权周转时间带权周转时间。 平均带权周转时间平均带权周转时间可表示为：W=(Ti/Tsi)/n; (i=1,2,.,n) 3.2.2处理机调度算法的目标处理机调度算法的目标二二批处理系统的目标批处理系统的目标 第三章 处理机调度与死锁 3.2.2处理机调度算法的目标处理机调度算法的目标二二批处理系统的目标批处理系统的目标 2系统吞吐量高系统吞吐量高3 处理机利用率高处理机利用率高第三章 处理机调度与死锁 3.2.2处理机调度算法的目标处理机调度算法

17、的目标三三分时系统的目标分时系统的目标 1响应时间快响应时间快 是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或说直到在屏幕上显示出结果为止的一段时间间隔。它包括：(1）从键盘输入的请求信息传送到处理机的时间； (2）处理机对请求信息进行处理的时间； (3）将所形成的响应回送到终端显示器的时间。2均衡性均衡性 是指系统响应时间的快慢应与用户所是指系统响应时间的快慢应与用户所请求服务的复杂性相适应。请求服务的复杂性相适应。第三章 处理机调度与死锁 3.2.2处理机调度算法的目标处理机调度算法的目标四四实时系统的目标实时系统的目标 1.截止时间的保证截止时间的保证 所谓截止时间

18、截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。2.可预测性可预测性第三章 处理机调度与死锁 3.3调度算法调度算法 作业调度的职责作业调度的职责就是根据一定的算法，从多个在外存上处于后备队列中的作业中选择其中一些调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行。 进程调度的职责进程调度的职责就是根据一定的算法，从多个就绪进程中选择其中之一来占用CPU。从宏观上讲，进程调度把一个物理上的CPU变为多个逻辑上的CPU。第三章 处理机调度与死锁 3.3调度算法调度算法 先来先服务(First Come First Served,FCFS)

19、 短作业(进程) 优先(Shortest Job First,SJF或Shortest Process First,SPF) 时间片轮转调度算法(Round Robin ,RR) 优先级调度算法(Priority-Scheduling Algorithm,PSA) 高响应比优先调度算法 (Highest Response Ratio Next, HRRF) 多队列调度算法 多级反馈队列调度算法第三章 处理机调度与死锁 先来先服务调度算法（先来先服务调度算法（FCFS） FCFS调度算法最简单，既适合于作业调度，又适合于进程调度。 作业调度：每次调度是从后备作业队列中，选择一个或多个最先进入该队

20、列的作业，将它们调入内存，为它们分配资源、创建进程，然后放人就绪队列。 进程调度：每次调度是从就绪队列中，选择一个最先进入该队列的进程，把处理机分配给它，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后，才放弃处理机。第三章 处理机调度与死锁 先来先服务调度算法（先来先服务调度算法（FCFS） 特点：有利于长作业（进程），不利于短作业（进程），有利于CPU繁忙型的作业，不利于I/O繁忙型的作业。 CPU繁忙型作业繁忙型作业：需要大量的 CPU时间进行计算 I/O繁忙型作业繁忙型作业：需频繁地请求I/O，每次I/O的操作时间很短 例：下表列出了A、B、C、D四个作业第三章 处理机调度与死锁

21、 例考虑5个进程P1，P2，P3，P4，P5，见下表。规定进程的优先数越小，优先级越高。试描述在采用先来先服务调度算法时各个进程运行过程，并计算进程平均周转时间。假设忽略进程的调度时间。第三章 处理机调度与死锁 短作业（进程）优先调度算法（短作业（进程）优先调度算法（SJPF） 对短作业或短进程优先调度。 短作业优先调度算法短作业优先调度算法 每次调度是从后备作业队列中，选择一个或多个估计运行时间最短的作业，将它们调入内存，为它们分配资源、创建进程，然后放人就绪队列。 短进程优先调度算法短进程优先调度算法每次调度是从就绪队列中，选择一个估计运行时间最短的进程，把处理机分配给它，使之投入运行。该

22、进程一直运行到完成或发生某事件而阻塞后，才放弃处理机。第三章 处理机调度与死锁 例：下表列出了例：下表列出了A A、B B、C C、D D、E E五个作业五个作业FCFS和和SJPF比较比较 第三章 处理机调度与死锁 SJPF算法的特点算法的特点 SJPF算法优点算法优点：能有效地降低作业的平均等待时间，提高系统吞吐量。 SJPF算法缺点算法缺点：(1) 对长作业不利，可能导致长作业（进程）长期不被调度。(2) 完全没有考虑到作业的紧迫程度，因而不能保证紧迫作业（进程）会被及时处理。(3)该算法不一定能真正做到短作业优先调度。第三章 处理机调度与死锁 优先级调度算法优先级调度算法 既可用于作业

23、调度，也可用于进程调度。 作业调度作业调度：系统为每个作业设置一个优先数（对应一个优先权），每次调度是从后备作业队列中，选择若干个优先权最优先权最高高的作业，将它们调入内存，为它们分配资源、创建进程，然后放人就绪队列。 进程调度进程调度：系统为每个进程设置一个优先数（对应一个优先权），每次调度是从就绪队列中，选择一个优先权最高优先权最高的进程，把处理机分配给它，使之投入运行。可进一步把该算法分为非抢占(非剥夺)式优先级调度算法和抢占(剥夺)式优先级调度算法。第三章 处理机调度与死锁 优先级调度算法优先级调度算法 非抢占式优先权调度非抢占式优先权调度：系统一旦把CPU分配给优先权最高的进程后，该

24、进程便一直执行下去，仅当该进程运行结束或因发生某事件不能继续运行时，系统才进行重新调度。 优缺点：进程切换次数少，系统开销小；可能导致优先级低的进程长期抢占不到CPU。 抢占式优先权调度抢占式优先权调度：系统把CPU分配给优先权最高的进程，使之执行。但在其执行期间，当系统中有另一优先权更高的进程变成就绪状态时，系统就立即剥夺现运行进程占用CPU的权力，使新到的优先权更高的进程投入运行。 优缺点：反映了进程的优先权特征，使系统能及时处理紧急事件；系统开销较大。第三章 处理机调度与死锁 例考虑5个进程P1，P2，P3，P4，P5，见下表。规定进程的优先数越小，优先级越高。试描述在采用下述几种调度算

25、法时各个进程运行过程，并计算采用每种算法时的进程平均周转时间。假设忽略进程的调度时间。（1）非剥夺(非抢占)式优先级调度等法；（2）剥夺(抢占)式优先级调度算法。第三章 处理机调度与死锁 优先级调度算法优先级调度算法 优先级优先级是利用某一范围内的一个整数来表示。例如，07或0255中的某一整数，又称该整数为优先数优先数。 优先级调度算法优先级调度算法的关键关键： 优先级的类型(静态优先级、动态优先级) 如何确定进程的优先级。 确定进程优先级的依据确定进程优先级的依据有：（1）进程类型进程类型。系统进程的优先权高于一般用户进程的优先权。（2）进程对资源的需求进程对资源的需求。如估计执行时间短及

26、资源需求量少的进程，应赋予较高的优先权。（3）用户要求用户要求。由用户进程的紧迫程度及用户所付费用的多少来定第三章 处理机调度与死锁 优先级调度算法优先级调度算法优先级的类型优先级的类型1静态优先级静态优先级是在创建进程时确定的，且规定它在进程的整个运行期间保持不变。 静态优先级法简单易行、系统开销小，但不够精确，很可能出现优先级低的作业（进程）长期没有被调度的情况，仅在要求不太高的系统中使用。 第三章 处理机调度与死锁 优先级调度算法优先级调度算法优先级的类型优先级的类型2动态优先级动态优先级是指在创建进程时所赋予的优先级，是可以随进程的推进或随其等待时间的增加而改变的。 在就绪队列中的进程

27、，随其等待时间的增长，其优先级以在就绪队列中的进程，随其等待时间的增长，其优先级以速率速率a增加。增加。优先级较低的进程在等待足够的时间后，其优先级将提高到可被调度执行。 若所有进程具有相同的优先级初值，相当于FCFS算法。 若所有进程具有各不相同的优先级初值，对于优先级初值低的进程，在等待足够的时间后，其优先级便可能升为最高，从而可以获得处理机执行。 进程每执行一个时间片，其优先级就以速率进程每执行一个时间片，其优先级就以速率b下降下降，从而一个进程持续执行时，其优先级将降低到出让CPU。防止一个长作业长期地垄断处理机。第三章 处理机调度与死锁 高响应比优先调度算法高响应比优先调度算法 既可

28、用于作业调度，也可用于进程调度。 高响应比优先调度算法高响应比优先调度算法把短作业优先调度算法和动态动态优先级机制优先级机制结合起来。作业优先级的变化规律描述为 等待时间加上要求服务时间，就是系统对该作业的响应时响应时间间，故该优先级又相当于响应比Rp。即第三章 处理机调度与死锁 高响应比优先调度算法高响应比优先调度算法 作业调度作业调度：系统为每个作业设置一个响应比，作业的等待时间越长，响应比越高。每次调度是从后备作业队列中，选择若干个响应比最高响应比最高的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。 进程调度进程调度：系统为每个进程设置一个响应比。每次调度是从就绪队列

29、中，选择一个响应比最高响应比最高的进程，把处理机分配给它，使之投入运行。 每当要进行调度之前，先做响应比的计算。 当响应比相同时，第一时间调度的必然是最短的作业。第三章 处理机调度与死锁 高响应比优先调度算法的特点高响应比优先调度算法的特点高响应比优先调度算法高响应比优先调度算法 (1)如果作业的等待时间相同，则要求服务的时间愈短，其响应比愈高，因而该算法有利短作业。 (2)当要求服务的时间相同时，作业的响应比决定于其等待时间。因此它实现的是先来先服务。 (3)对于长作业，作业的响应比可以随着等待时间的增加而以速率a提高，也可获得处理机。 既照顾了短作业，又不致使长作业的等待时间过长，从而改善

30、了处理机调度性能。第三章 处理机调度与死锁 例有三个作业A(到达时间8:50，执行时间1.5小时)、B(到达时间9:30，执行时间0.4小时)、C(到达时间9:30，执行时间1小时)。当作业全部到达后，批处理单道系统按照响应比高者优先算法进行调度，则作业被选中的次序是（）A、(ABC) B、(BAC) C、(BCA) D、(CBA) E、(CAB) F、(ACB)高响应比优先调度算法高响应比优先调度算法第三章 处理机调度与死锁 时间片轮转调度算法时间片轮转调度算法(RR)基本思想基本思想： 系统将所有的就绪进程按先来先服务的原则，排成一个队列，并把CPU的处理时间划分成一个个时间片，就绪队列中

31、的每个进程轮流运行一个时间片。 当执行的时间片用完时，由一个计时器发出时钟中断请求，去激活进程调度程序进行调度。调度程序便据此中断信号来停止当前进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。 时间片大小的选择非常重要。一个较为可取的大小是，时间片略大于一次典型的交互所需要的时间。这样可使大多数进程在一个时间片内完成，获得很小的响应时间。第三章 处理机调度与死锁 例考虑5个进程P1，P2，P3，P4，P5，见下表。试描述在采用时间片轮转调度算法（时间片为1ns）时各个进程运行过程，并计算进程平均周转时间。假设忽略进程的调度时间。第三

32、章 处理机调度与死锁 基本思想基本思想： 设置多个就绪队列，将不同类型或性质的进程固定分配在不同的就绪队列； 不同的就绪队列采用不同的调度算法； 一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。优点：系统可以针对不同用户进程的需求，提供多种调度策略。多队列调度算法多队列调度算法（多处理机系统使用）（多处理机系统使用）第三章 处理机调度与死锁 设置多个就绪队列设置多个就绪队列，分别赋予不同的优先级，如逐级降低。每个队列中进程执行时间片的长度也不同，优先级越低，时间片越长。每个队列都采用每个队列都采用FCFSFCFS算法。算法。当一个新进程进入内存后，先将它放入

33、第一个队列的末尾，按FCFS算法调度；若在第一个队列的一个时间片未能执行完，则降低投入到第二个队列的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按时间片轮转算法调度直到完成。按队列优先级调度。按队列优先级调度。仅当较高优先级的队列空闲时，调度程序才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。调度机制：调度机制：多级反馈队列调度算法多级反馈队列调度算法第三章 处理机调度与死锁 终端型进程(属于交互型进程，通常较小）:让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可在最高

34、优先级队列所规定的时间片内处理完一次I/O请求的数据，然后转入到阻塞队列。其周转时间很短。 短批处理型进程：通常只需在前几个队列中各执行一个时间片即可完成，其周转时间仍然很短。 长批处理型(计算型)进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片按轮转方式来执行，以减少调度次数。多级反馈队列调度算法的性能多级反馈队列调度算法的性能第三章 处理机调度与死锁 习题习题1、有5个待运行作业J1、J2、J3、J4、J5，各自预计运行时间分别是9、6、3、5、7。假定这些作业同时到达，并且在一台处理机上按单道方式执行。讨论采用哪种调度算法和哪种运行次序将使平均周转时间最短，平均周转时间为多少

35、？2、有5个任务A、B、C、D、E，它们几乎同时到达，预计它们的运行时间为10、6、2、4、8min。其优先权分别为3、5、2、1、4，这里5为最高优先权。对于下列每一种调度算法，计算其平均进程周转时间(进程切换开销可不考虑)。(1)先来先服务(按A、B、C、D、E)算法(2)优先权调度算法(3)时间片轮转算法第三章 处理机调度与死锁 3.5死锁概述死锁概述3.5.1 资源问题资源问题可重用性资源和可消耗性资源 可重用性资源是指可供用户重复使用多次的资源。系统中大多数资源都属于此类。 可消耗性资源又称临时性资源，是指在进程运行期间，由进程动态的创建和消耗的。第三章 处理机调度与死锁 3.5.1

36、 资源问题资源问题可抢占性资源和不可抢占性资源 可抢占性资源是指某进程在获得这类资源后，该资源可以再被其他进程或系统抢占。如：CPU和主存都属于可抢占性资源。 不可抢占性资源是指系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。第三章 处理机调度与死锁 3.5.2产生死锁的原因产生死锁的原因产生死锁的原因可归结为：（1）竞争不可抢占性资源（2）竞争可消耗性资源（3）进程推进顺序不当第三章 处理机调度与死锁 例：有两个进程PA和PB，它们在运行的过程中要共享使用两个独占设备R1和R2。设SR1：表示设备R1可用，初值为1；SR2表示设备R2可用，两个进程

37、并发执行的程序如下：PAPB3.5.2产生死锁的原因产生死锁的原因竞争不可抢占性资源第三章 处理机调度与死锁 进程推进顺序非法引起死锁进程推进顺序非法引起死锁1、进程推进顺序合法、进程推进顺序合法不会引起进程死锁的推进顺序2、进程推进顺序非法、进程推进顺序非法PAPBPAPB第三章 处理机调度与死锁 死锁的定义死锁的定义 死锁死锁就是两个或两个以上的进程等候着一个永远不会发生的事件时所处的一种系统状态。 两个或两个以上并发进程，如果每个进程持有某种资源，而又等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。此时，每个进程都占用了一定的资源，但又都不能向前推进。这种现象称为死锁死锁

38、。 死锁死锁是指多个进程在运行过程中因竞争资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。 （教材）（教材）如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么这组进程是死锁死锁的。第三章 处理机调度与死锁 产生死锁的必要条件产生死锁的必要条件1互斥条件互斥条件进程对所分配到的资源进行排它性使用 2请求和保持条件请求和保持条件进程处于等待资源状态但又对自己已获得的资源保持不放。 3不可抢占条件不可抢占条件进程已获得的资源，在未使用完之前，不能被抢占，只能在使用完时由自己释放。 4循环等待条件循环等待条件在发生死锁时，必然存在一个进

39、程资源的环形链，即存在一组进程P1，P2，Pn，其中每一个进程都在等待另一个进程占用的资源，即P1等待P2占用的资源，P2等待P3占用的资源，P（n-1）等待Pn占用的资源，而Pn又等待P1所占用的资源。第三章 处理机调度与死锁 处理死锁的方法处理死锁的方法1预防死锁预防死锁 通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。 预防死锁是一种较简单和直观的事先预防的方法，但由于其所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量降低。第三章 处理机调度与死锁 处理死锁的方法处理死锁的方法2避免死锁避免死锁 在资源的动态分配过程中，用某种方法去防

40、止系统进入不安全状态，从而避免发生死锁。 避免死锁也是一种事先预防的方法，但较难实现。它只需事先加以较弱的限制条件，便可获得较高的资源利用率和系统吞吐量。第三章 处理机调度与死锁 处理死锁的方法处理死锁的方法3检测死锁检测死锁允许系统在运行过程中发生死锁，但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；然后解除死锁。4解除死锁解除死锁当检测到系统中已发生死锁时，采取相应措施，将进程从死锁状态中解脱出来。常用的方法是撤消或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。第三章 处理机调度与死锁 3.6

41、预防死锁预防死锁 预防死锁的方法预防死锁的方法是使产生死锁的四个必要条件使产生死锁的四个必要条件中的第中的第2 2、3 3、4 4条件之一不能成立条件之一不能成立。 具体的方法有一、破坏“请求和保持”条件二、破坏”不可抢占”条件 三、破坏“循环等待”条件第三章 处理机调度与死锁 破坏破坏“请求和保持请求和保持”条件条件静态分配资源静态分配资源 静态分配静态分配就是要求每一个进程在开始执行前就一次性地申请它在整个执行过程中所需要的全部资源，仅当系统能满足进程资源申请要求且把资源分配给进程后，该进程才能开始执行。这种策略也称预分配资源。 实现简单，易行且安全。但降低了资源的利用率，并且使得进程延迟

42、运行。第三章 处理机调度与死锁 破坏破坏“不可抢占不可抢占”条件条件抢占式分配资源法抢占式分配资源法： 在采用这种方法时，进程是逐个地提出对资源的要求的。 如果一个进程已经占有了某些不可抢占性资源又要申请新的资源，而新的资源请求不能立即得到满足必须等待时，它必须释放已经保持的所有资源，待以后需要时再重新申请。 目前抢占式分配策略只适用于主存空间和处理器，而对打印机、磁带机等不能采用这种分配策略。第三章 处理机调度与死锁 破坏破坏“循环等待循环等待”条件条件采用按序分配资源法： 把系统中所有资源按类型排一个顺序，并赋予每一个资源一个确定编号(例如打印机为1、磁带机为2、磁盘为3、等等)，规定任何

43、一个进程申请两个以上的资源时，总是先申请编号小的资源，再申请编号大的资源。第三章 处理机调度与死锁 例如，系统共有m个资源，假定编号为1，2，m，于是这m个资源是 r1，r2， rm 任何一个进程在得到了资源ri之后，若再申请资源rj，则必定是ij。可以证明按这种策略分配资源时不会出现循环等待资源的情况。 可用反证法，假定有循环等待资源的情况，则一定存在一组进程p1，p2，pn，其中每一个进程Pi（i=1，2，nl）都在等待资源rki（lkim），而资源rki已被进程pi+1占用， pn等待的资源被P1占用。依照按序分配的资源分配原则可推出knk1k2k(n-1)kn于是，发生了knk1而k1

44、kn的矛盾。故存在循环等待资源的假设是不能成立的。三、摒弃三、摒弃“环路等待环路等待”条件条件第三章 处理机调度与死锁 在避免死锁避免死锁的方法中，允许进程动态地申请资源，但把系统的状态分为安全状态和不安全状态。系统在进程资源分配之前，应先计算此次资源分配的安全性，若此次分配不会导致系统进入不安全状态，则将资源分配给进程，否则等待。只要能使系统始终都处于安全状态，便可避免发生死锁。3.7 避免死锁避免死锁第三章 处理机调度与死锁 所谓安全状态安全状态，是指系统能按某种顺序如(称序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。 若系统

45、不存在这样一个安全序列，称系统处于不安全状态不安全状态。 虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。 避免死锁的实质避免死锁的实质在于：如何使系统不进入不安全状态。3.7.1 系统安全状态系统安全状态 第三章 处理机调度与死锁 假定系统有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。设在T0时刻，进程Pl、P2和P3已分别获得5台、2台和2台，尚有3台空闲未分，如下表所示： 进程 最大需求 已分配 可用P1 10 5 3P2 4 2P3 9

46、 2在T0时刻，系统是否存在安全序列？系统是否安全？安全状态之例安全状态之例 第三章 处理机调度与死锁 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。 避免死锁的基本思想避免死锁的基本思想：确保系统始终处于安全状态。由安全状态向不安全状态的转换由安全状态向不安全状态的转换 第三章 处理机调度与死锁 3.7.2 利用银行家算法避免死锁利用银行家算法避免死锁 避免死锁算法中最有代表性的算法是Dijkstra E.W 于1968年提出的银行家算法。 为实现银行家算法，每一个新进程在进入系统时，它必须申明在运行过程中，可能需要的每种资源类型的最大数目，其数目不应超过系统所拥有的资源

47、总量。 银行家算法：当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它；否则，让进程等待。第三章 处理机调度与死锁 1.可利用资源向量可利用资源向量AvailableAvailable 是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。2.最大需求矩阵最大需求矩阵MaxMax 是个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi，jk，表示进程i需要Rj类资源的最大数目为k。3.分配矩阵分配矩阵AllocationAllocat

48、ion是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每个进程的资源数。如果Allocationi,jk，表示进程i当前已分得Rj类资源的数目为k。4.需求矩阵需求矩阵NeedNeed是一个nm的矩阵，用以表示每一个进程尚需的各类资源数，如果Needi,j=k，表示进程i还需要Rj类资源k个，方能完成其任务。三矩阵间存在下述关系：三矩阵间存在下述关系：Needi,j = Maxi,j- Allocationi,jNeedi,j = Maxi,j- Allocationi,j一、银行家算法中的数据结构一、银行家算法中的数据结构第三章 处理机调度与死锁 设Requesti是进程是进程Pi的请

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

50、stij;Needi,j := Needi,j - Requestij;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。二、银行家算法二、银行家算法 第三章 处理机调度与死锁 (1)设置两个向量设置两个向量、工作向量工作向量Work表示系统可提供给进程继续运行所需要的各类资源数目，它含有m个元素，开始时，Work := Available。、Finish表示系统是否有足够的资源分配给进程，使之运行完成，开始时Finishi:=false ；当有足够资源时，令Fi

51、nishi:=true 。(2)从进程集合中找到一个能满足下述条件的进程从进程集合中找到一个能满足下述条件的进程： Finishi:=false Needi,j=workj如找到，执行步骤(3)；否则，执行步骤(4)。(3)当进程当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：的资源，故应执行：Workj:= Workj+ Allocationi,j ;Finishi:=true go to step 2；(4)如果所有进程的如果所有进程的Finishi=true，则表示系统处于安全状态；否则，则表示系统处于安全状

52、态；否则，系统处于不安全状态。系统处于不安全状态。三、安全性算法三、安全性算法 第三章 处理机调度与死锁 假定系统中有五个进程：P0，P1，P2，P3，P4和三种类型的资源A，B，C，每一种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图315所示。 资源情况进程MAXABCAllocationABCNeedABCAvailableABCP0753010743332(230)P1322200122(302)(020)P2902302600P3222211011P4433002431问：问：（1）当前系统是否是安全的？（2）如果进程P1已发出资源请求向量(1，0，2)，系统能否将资源分配给它？若进程P4发出资源请求向量(3，3，0)呢？若进程P0发出资源请求向量(0，2，0)呢？四、银行家算法之例四、银行家算法之例第三章 处理机调度与死锁 当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段。 操作系统应能够检测出系统是否发生了死锁，并且能够识别出处于死锁中的进程和资源。主要方法是资源分配图法。 3.8 死锁的检测和解除死锁的检测和解除死锁的检测死锁的检测 第三章 处理机调度与死锁 资源分配图资源分配图是