计算机操作系统课件(第四版)第三章

《计算机操作系统课件(第四版)第三章》由会员分享，可在线阅读，更多相关《计算机操作系统课件(第四版)第三章（75页珍藏版）》请在金锄头文库上搜索。

1、第三章 处理机调度与死锁,第一节 处理机调度的层次 第二节 调度队列模型和调度准则 第三节 调度算法 第四节 实时调度 第五节 产生死锁的原因和必要条件 第六节 预防死锁的方法 第七节 死锁的检测和解除,3.1 处理机调度的层次,高级调度 低级调度 中级调度,3.1.1、高级调度,高级调度（作业调度/ 长程调度） 决定把外存上处于后备队列中的哪些作业调入内存。 调度对象：作业,1、作业和作业步 作业：程序 + 数据 + 作业说明书 作业步：作业运行期间的每个加工步骤,例如：编译 连结装配 运行,2、作业控制块 （ JCB ） JCB：保存了系统对作业进行管理和调度所需的全部信息。作业在系统中存

2、在的标志。 JCB包含的内容有：作业标识、用户名称、用户账号、作业类型、作业状态、调度信息、资源需求、时间信息、资源使用情况等。 JCB的创建和回收,3、高级调度（作业 / 长程 / 接纳调度） 概念：决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，准备执行。 多用于批处理系统 每次调度时要考虑： (1)接纳多少作业：取决于多道程序度 (2)接纳哪些作业：取决于调度算法 作业调度运行频率低，几分钟一次,低级调度（进程 / 短程调度） 决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作 是最基本的调度，在三种类型的OS中都必须

3、配置,3.1.2、低级调度,1、低级调度的功能 保存处理机的现场信息 按照某种算法选取进程 把处理机分配给进程,2、进程调度中的三个基本机制 排队器 分派器（分派程序） 上下文切换机制,3、进程调度方式 非抢占方式 抢占方式,1）非抢占方式： 一旦进程获得处理机，则一直执行，直到该进程完成或被阻塞 此方式下，可能引起进程调度的因素： （1）正在执行的进程执行完毕，或因发生某事件不能再继续执行 （2）执行中的进程因提出I/O请求而暂停执行 （3）在进程通信或同步过程中执行了某原语，P操作等 优点：简单、系统开销小，适合大多数批处理系统 缺点：无法满足紧急任务的需要，不适合实时系统,2）抢占方式：

4、 允许调度程序根据某原则，暂停正在执行的进程，将处理机重新分配 抢占原则： 优先权原则 就绪的高优先权进程有权抢占低优先权进程的CPU 短作业优先原则 就绪的短作业(进程)有权抢占长作业(进程)的CPU 时间片原则 一个时间片用完后，系统重新进行进程调度,中级调度（中程调度） 目的：提高内存利用率和系统吞吐量 按一定的算法将外存上已具备运行条件的挂起进程换入内存，挂到就绪队列上，准备执行；而将内存中处于阻塞状态的某些进程换出至外存。,3.1.3、中级调度,调度队列模型 选择调度方式和调度算法的若干准则,3.2、调度队列模型,3.2.1、调度队列模型,3.2.2、选择调度方式和算法的选择准则,1

5、、面向用户的准则 （1）周转时间短评价批处理系统 周转时间：是指从作业被提交系统开始，到作业完成为止的这段时间间隔。,包括四部分时间： 1）等待作业调度时间 2）等待进程调度时间 3）执行时间 4）进程等待I/O操作完成时间,（2）响应时间快评价分时系统 响应时间：从用户通过键盘提交一个请求开始直至系统首次产生响应为止。 包括三部分时间： 1）从键盘输入的请求信息传送到处理机的时间 2）处理时间 3）响应信息回送终端的时间,（3）截止时间保证评价实时系统 截止时间：任务必须开始执行的最迟时间，或必须完成的最迟时间。 （4）优先权准则三种系统中皆适用,2、面向系统的准则 系统吞吐量高评价批处理系

6、统 处理机利用率好针对大中型系统 各类资源的平衡利用对大中型系统,3.3 调度算法,先来先服务和短作业（进程）优先调度算法 高优先权先调度算法 基于时间片的轮转调度算法,3.2.1、先来先服务和短作业（进程）优先调度算法,1、先来先服务（FCFS）调度算法 可用于作业调度和进程调度 用于作业调度： 每次从后备作业队列中选择最先进入的作业，将它们调入内存，为它们分配资源、创建进程，然后挂到就绪进程队列上。,用于进程调度： 每次从就绪进程队列中选择最先进入的进程，为之分配处理机，使之投入运行。 直到运行完成进程才会让出处理机-非抢占式。 有利于长作业，而不利于短作业。,性能评价： 周转时间 = 完

7、成时间 到达时间 带权周转时间 = 周转时间 / 服务（运行）时间,2、短作业 / 进程优先（SJF/SPF）,短作业优先（SJF） 从后备队列中选择估计运行时间最短的作业，调入内存运行。 短进程优先（SPF） 从就绪队列中选出估计运行时间最短的进程，将处理机分配给它，使它立即执行。 直到运行完成进程才会让出处理机-非抢占式。 缺点： 对长作业不利，有可能长期不被调度； 完全没考虑作业的紧迫程度（某些特殊的）； 用户做出的估计时间带有很大的主观性。,3.5,14,18,4,4,E,2,10,12,5,2,C,2,6,7,3,1,B,5.5,11,14,2,3,D,2.1,1,带权周转时间,8,

8、4,周转时间,4,完成时间,FJS,2.8,1,带权周转时间,9,4,周转时间,4,完成时间,FCFS,4,服务时间,0,到达时间,平均,A,进程名,作 调 业 度 情 算 况 法,周转时间 = 完成时间 到达时间 带权周转时间 = 周转时间 / 服务时间,3.3.2、高优先权先调度算法,既能用于作业调度，也可用于进程调度。 作业调度：从后备队列中选择若干个优先权最高的作业装入内存。 进程调度：把处理机分配给就绪队列中优先权最高的进程 两种占用CPU的方式：非抢占式优先权算法 抢占式优先权算法,1、优先权调度算法的类型,非抢占式优先权算法 系统一旦把处理机分配给就绪队列中优先权最高的进程后，该

9、进程就一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。 主要用于批处理系统,抢占式优先权算法 新的就绪进程i，优先权Pi。正在执行的进程j，优先权Pj。若PiPj，做进程切换。新进程i执行。 优点：能更好的满足紧迫作业的要求。主要用于比较严格的实时系统。,2、优先权的类型 1）静态优先权 在进程创建时确定的，在进程整个运行期间保持不变,优先权利用某一范围的整数来表示，该整数称为优先数。如：07，0255,确定优先权的依据： （1）进程类型 （2）进程对资源的需求 （3）用户要求,注：规定优先数越小，其优先权越高,3,3,4,C,4,

10、8,2,B,1,1,8,D,带权周转时间,周转时间,完成时间,2,优先权,非抢占式优先权算法,5,服务时间,0,到达时间,A,进程名,作 调 业 度 情 算 况 法,平均,6.25,1.3,例：非抢占式优先权算法,2) 动态优先权 在进程创建时创立的优先权，可随进程的推进或等待时间的增加而改变。如等待时间长，优先权升高。,等待时间 + 要求服务时间 优先权 = - 要求服务时间 等待时间 + 要求服务时间 响应时间 响应比(Rp) = - = - 要求服务时间 要求服务时间,3、高响应比优先调度算法(HRRN) 为每个进程引入动态优先权，随着等待时间增加优先权提高。,优点： 等待时间相同，短作

11、业优先权高 (即SPF) 要求服务时间相同，等待时间长，优先权高(即FCFS) 对于长作业，在等待足够时间后，可获得处理机,2,8,E,4,4,C,1.17,7,9,6,2,B,5,6,D,2.14,1,带权周转时间,8,3,周转时间,3,完成时间,3,服务时间,0,到达时间,平均,A,进程名,作 调 业 度 情 算 况 法,执行顺序：ABCED,HRRN （R大， 优先权高）,3.3.3、基于时间片的轮转调度算法,1、时间片轮转法,1）基本原理 系统将所有的就绪进程按FIFO原则排成一个队列，将CPU分配给队首进程，执行一个时间片。在时间片内进程未完，则插入就绪队列未尾，CPU交给下一个进程

12、。,2）时间片大小的确定 时间片略大于一次典型的交互所需要的时间。,4,4,E,4,2,C,3,1,B,2,3,D,带权周转时间,周转时间,完成时间,RR q=4,带权周转时间,周转时间,完成时间,RR q=1,4,服务时间,0,到达时间,平均,A,进程名,作 调 业 度 情 算 况 法,周转时间 = 完成时间 到达时间 带权周转时间 = 周转时间 / 服务时间,2、多级反馈队列调度算法,原理： 设置多个就绪队列，并为各个队列赋予不同的优先级和不同长度的时间片； 新创建的进程挂到第一优先级的队列后，然后按 FCFS 原则排队等待调度。当轮到其执行时，如它能在时间片内完成，便撤离系统；如果不能完

13、成，便被挂入第二级队列后，最后一级队列采用时间片轮转法； 仅当第一级队列空闲时，调度程序才调度第二级队列中的进程运行，依次类推；新进程可抢占低级进程的处理机。,就,级,1,绪,队,列,空,就,级,2,绪,队,列,就,级,3,绪,队,列,运行,等待,时间片 小 大,优先级 高 低,多级反馈队列调度算法的性能 多级反馈队列调度算法能较好地满足各种类型用户（进程）的需要： 终端（交互）型作业用户 短批处理作业用户 长批处理作业用户,3.3.4、基于公平原则的调度算法,1、保证调度算法,如果系统中有n个相同类型的进程同时运行，保证每个进程都获得相同的处理机时间1/n。,2、公平分享调度算法 使所有用户

14、能获得相同的处理机时间。,3.4 实时调度,实现实时调度的基本概念和条件 实时调度算法的分类 常见的几种实时调度算法,选学,1.实时调度是为了完成实时处理任务而分配处理机的调度方法。,2.硬实时任务要求计算机系统必须在用户给定的时限内完成 3.软实时任务允许计算机系统在用户给定的时限左右处理完毕。,提供更详细的调度信息： 就绪时间、开始截止时间或完成截止时间、处理时间、资源要求、优先级等； 含有硬实时任务的实时系统中，广泛采用基于优先级的抢占式调度策略,实时调度算法分类：,非抢占式轮转调度算法：只适用于一般实时信息处理系统 非抢占式优先级调度算法：优先级最高的实时任务排在就绪队列队首，当前任务

15、终止或完成后才被调度。 基于时钟中断抢占式优先级调度算法：新到的实时任务的优先级高于当前任务时，并不立即抢占CPU，而是等到时钟中断到来，才进行切换。用于大多数的实时系统中。 立即抢占的优先级调度算法：这种算法适用于实时要求比较严格的实时控制系统。,常用的几种实时调度算法,1、最早截止时间优先算法（EDF） 该算法根据任务的开始截止时间来确定任务的优先级。截止时间越早，优先级越高。 该算法要求实时任务的就绪队列按任务截止时间的早晚排序。调度程序总选择队首的任务执行。 该算法可用于抢占式和非抢占式调度。,1,3,4,2,非抢占式调度方式,2、最低松弛度优先算法（LLF） 该算法根据任务的松弛度来确定任务的优先级。松弛度越低，优先级越高。 松弛度任务必须完成的时间运行时间当前时间 该算法要求实时任务的就绪队列按松弛度排序。调度程序总选择队首的任务执行。 该算法主要用于抢占式调度方式。,松弛度任务必须完成的时间运行时间当前时间,例：实时系统中有两个周期性实时任务A、B，任务A每20ms执行一次，执行时间10ms；任务B每50ms执行一次，执行时间