操作系统课程第3章处理机调度

《操作系统课程第3章处理机调度》由会员分享，可在线阅读，更多相关《操作系统课程第3章处理机调度（161页珍藏版）》请在金锄头文库上搜索。

1、Page 1,2018/9/1,第三章 处理机调度与死锁,Page 2,2018/9/1,第三章 处理机调度与死锁,处理机调度的基本概念 处理机调度的目标 充分有效地利用处理机（CPU）资源调度算法 实时调度 产生死锁的原因和必要条件 预防死锁的方法 死锁的检测与解除,Page 3,2018/9/1,3.1 处理机调度的基本概念,操作系统调度级别 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则,Page 4,2018/9/1,3.1 处理机调度的基本概念,3.1.1 操作系统调度级别,1. 高级调度,2. 低级调度,3. 中级调度,Page 5,2

2、018/9/1,3.1.1 高级、中级和低级调度,1.高级调度又称作业调度 主要任务是按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业分配内存、输入/输出设备等必要的资源，并建立相应的进程，插入就绪队列，以使该作业的进程获得竞争处理机的权利,作 业 调 度,作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及命令等 作业状态:作业从提交给系统， 直到完成任务后退出系统前， 在整个活动过程中它会处于不同的状态。 通常， 作业状态分为四种： 提交、 后备、 执行和完成， 如图3-1所示。,Page 7,2018/9/1,作 业 调 度,后备状

3、态,完成状态,就绪,阻塞,执行,I/O完成,I/O请求,时间片完,作业状态间转换,图3-1 作业的基本状态,Page 8,2018/9/1,（1） 提交状态即用户向系统提交一个作业时， 该作业所处的状态。 （2） 后备状态即用户作业经输入设备（如读卡机）送入输入井（磁盘）中存放， 等待进入内存时所处的状况。 （3） 执行状态即作业分配到所需的资源， 被调入内存， 并且在处理机（CPU）上执行相应的程序时所处的状况。 （4） 完成状态即作业完成了计算任务， 结果由打印机输出， 最后由系统回收分配给它的全部资源， 准备退出系统时的作业状况。,作业状态,作业控制块（JCB）在多道批处理系统中通常有上

4、百个作业被收容在输入井（磁盘）中。 为了管理和调度作业， 系统为每个作业设置了一个作业控制块（JCB）， 它记录该作业的有关信息。 JCB的主要内容如图3-2所示。,作 业 调 度,图3-2 作业控制块,作业调度的功能作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转换。(1) 记录系统中各个作业的情况。 (2) 按照某种调度算法从后备作业队列中挑选作业。(3) 为选中的作业分配内存和外设等资源。(4) 为选中的作业建立相应的进程。(5) 作业结束后进行善后处理工作， 如输出必要的信息， 收回该作业所占用的全部资源， 撤消与该作业相关的全部进程和该作业的JCB。,Pag

5、e 13,2018/9/1,高级、中级和低级调度,在每次作业调度时，须决定： 接纳多少个作业即允许多少个作业同时在内存中运行 作业太多 服务质量下降 作业太少 资源利用率低 接纳哪些作业 取决于作业调度算法 先来先服务 短作业优先 作业优先权调度 响应比调度,周转时间太长,系统吞吐量太低,适当的折衷,周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔。 吞吐量：是指在单位时间内系统所完成的作业数。,Page 14,2018/9/1,3.1.1 高级、中级和低级调度,2.中级调度 目的：是为了提高内存利用率和系统吞吐量。 功能：暂时不能运行的进程挂起，释放宝贵的内存资源。具备条件时：

6、把外存上的就绪进程，重新调入内存，挂在就绪队列上等待进程调度。,Page 15,2018/9/1,3.1.1 高级、中级和低级调度,3.低级调度进程调度 主要任务是按照某种策略和方法选取一个处于就绪状态的进程，将处理机分配给它 常见的低级调度有非抢占式和抢占式两种,Page 16,2018/9/1,处理机调度的层次,Page 17,2018/9/1,作业调度又称为1，它决定将那些在外存储器上的处于2状态的作业调入主机内存，系统经作业调度程序选中一个或多个作业后，就为它们分配必要的内存、设备及软资源。然后控制权就交给了3，由3将它们变为一个或一组4。1( )：A、高级调度 B、低级调度 C、中级

7、调度 D、进城调度2（ ）：A、就绪 B、阻塞 C、提交 D、后备3（ ）：A、存储管理模块 B、处理机管理模块C、文件管理模块 D、设备管理模块4（ ）：A、指令 B、子程序 C、进程 D、程序段,Page 18,2018/9/1,处于后备状态的作业存放在（ ）中。A、外存 B、内存 C、A和B D、扩展内存在操作系统中，作业处于（ ）状态时，已处于进程的管理之下。 A、后备 B、阻塞 C、执行 D、完成,Page 19,2018/9/1,3.1处理机调度的基本概念,高级、中级和低级调度进程调度的任务确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则,Page 20,20

8、18/9/1,3.1.2 进程调度的任务,进程调度的任务是控制、协调进程对CPU的竞争,即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程,Page 21,2018/9/1,处理机调度的基本概念,高级、中级和低级调度进程调度的任务确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则,Page 22,2018/9/1,3.1.3 确定算法的原则,具有公平性资源利用率高（特别是CPU利用率）在交互式系统情况下要追求响应时间（越短越好）在批处理系统情况下要追求系统吞吐量,Page 23,2018/9/1,处理机调度的基本概念,高级、中级和低级调度进程调度的

9、任务确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则,Page 24,2018/9/1,3.1.4进程调度方式,非抢占方式 抢占方式,Page 25,2018/9/1,进程调度方式,非抢占方式(Non-preemptive Mode)引起进程调度的因素 正在执行的进程执行完毕， 或因发生某事件而不能再继续执行 执行中的进程因提出I/O请求而暂停执行； 在进程通信或同步过程中执行了某种原语操作，如wait、Block、Wakeup原语,优点：算法简单，系统开销小 缺点：紧急任务不能及时响应；短进程到达要等待长进程运行结束,Page 26,2018/9/1,进程调度方式,抢占

10、方式抢占式调度主要有以下原则 优先权原则 允许高优先权的新到进程抢占当前进程的处理机 短作业(进程)优先原则允许执行时间短的新到进程抢占当前进程的处理机 时间片原则 时间片用完后停止执行，重新进行调度，适用于分时系统,优点：适于时间要求严格的实时系统 缺点：调度算法复杂，系统开销大,Page 27,2018/9/1,3.1处理机调度的基本概念,高级、中级和低级调度进程调度的任务确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则,Page 28,2018/9/1,3.1.5 调度队列模型,仅有进程调度的调度队列模型 具有高级和低级调度的调度队列模型 同时具有三级调度的调度队列

11、模型,Page 29,2018/9/1,3.1.5 调度队列模型,仅有进程调度的调度队列模型 在分时系统中，通常仅设有进程调度 系统把这些进程组织成一个就绪队列 每个进程在执行时，可能有以下几种情况 进程获得CPU正在执行 任务在给定时间片内已完成，释放处理机后为完成状态 任务在时间片内未完成，进入就绪队列末尾 在执行期间因某事件而阻塞,Page 30,2018/9/1,3.1.5 调度队列模型,仅有进程调度的调度队列模型,进程调度,进程完成,等待事件,交互用户,时间片完,Page 31,2018/9/1,3.1.5 调度队列模型,具有高级和低级调度的调度队列模型 在批处理系统中，不仅需要进程

12、调度，而且还要有作业调度 就绪队列的形式 在批处理系统中，常用高优先权队列。进程进入就绪队列时，按优先权高低插入相应位置，调度程序总是把处理机分配给就绪队首进程 设置多个阻塞队列 根据事件的不同设置多个队列提高效率,Page 32,2018/9/1,3.1.5 调度队列模型,进程调度,进程完成,时间片完,与上一模型的主要区别：就绪队列的形式；设置多个阻塞队列,Page 33,2018/9/1,3.1.5 调度队列模型,同时具有三级调度的调度队列模型,进程调度,中级调度,等待事件,进程完成,时间片完,作业调度,交互型作业,批量作业,挂起,事件出现,事件出现,Page 34,2018/9/1,3.

13、1 处理机调度的基本概念,高级、中级和低级调度进程调度的任务确定算法的原则进程调度方式调度队列模型 选择调度方式和调度算法的若干准则,如果你是用户，你希望系统如何为你服务，如何考虑？ 如果你是调度者，从系统整体角度出发，应如何考虑？,Page 35,2018/9/1,3.1.6 选择调度方式和调度算法的若干准则,1. 面向用户的准则,2. 面向系统的准则,Page 36,2018/9/1,3.1.6 选择调度方式和调度算法的若干准则,1. 面向用户的准则,(1) 周转时间短。,(2) 响应时间快。 (3) 截止时间的保证。 (4) 优先权准则。,Page 37,2018/9/1,选择调度方式和

14、调度算法的若干准则,面向用户的准则 周转时间短 平均周转时间,带权周转时间：进程（或作业）的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS 。而平均带权周转时间则可表示为:,Page 38,2018/9/1,通常把周转时间作为评价批处理系统的性能、选择作业调度方式与算法的准则。所谓周转时间，是指从作业提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)。 它包括：(1)作业在外存后备队列上等待(作业)调度的时间；(2)进程在就绪队列上等待进程调度的时间；(3)进程在CPU上执行的时间；(4)等待IO操作完成的时间。其中，第(2)、(3)、(4)项在一个作业的处理过程中，

15、可能发生多次。,Page 39,2018/9/1,可把平均周转时间描述为：,作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间，而平均带权周转时间则可表示为:,系统以多个用户都满意为目标,周转时间服务时间 周转时间完成时间到达时间,Page 40,2018/9/1,选择调度方式和调度算法的若干准则,面向用户的准则 响应时间快 响应时间是指从用户通过键盘提交一个请求开始，直至系统中首次产生响应为止的时间 截止时间保证 截止时间是指某任务必须开始执行的最迟时间或必须完成的最迟时间 截止时间是实时系统中的重要指标,Page 41,2018/9/1,选择调度方式和调度算法的若干准则,面向用户的准则 等待时间短 等待时间是在就绪队列中等待所花的时间 调度算法并不影响进程运行和执行I/O的时间量；只影响进程在就绪队列中等待所花费的时间 优先权准则 在批处理、实时和分时系统中都可以选择优先权准则，以便让紧急任务先处理 有时还选择抢占式调度方式,Page 42,2018/9/1,选择调度方式和调度算法的若干准则,面向系统的准则 系统吞吐量高 吞吐量指单位时间内系统所完成的作业数 作业调度的方式和算法对吞吐量的大小有较大影响 处理机利用率高 各类资源的平衡利用 使内存、外存和I/O设备的利用率高,基于这样的准则，你设计操作系统的调度策略应如何？,