操作系统原理第3章 处理器调度

1、操作系统原理操作系统原理 Operating System Principles 四川大学计算机学院 段 磊 2014 Spring 第第3章章 处理器调度处理器调度 n 处理器调度指在多道程序环境下将处理器分配给各 进程。 n 在处理器调度中，合理的调度算法能够提高处理器 的处理能力和系统性能，满足用户需求。 2021-6-23计算机操作系统- 第3章3/98 本章目录 n3.1 处理器调度的层次 n3.2 评价调度算法的准则 n3.3 调度算法 n3.4 线程调度 n3.5 实时调度 n3.6 多处理器调度 n3.7 Windows 2000/XP系统的处理器调度 2021-6-23计算机

2、操作系统- 第3章4/98 3.1 处理器调度的层次 2021-6-23计算机操作系统- 第3章5/98 3.1 处理器调度的层次 2021-6-23计算机操作系统- 第3章6/98 调度的概念与本质 n调度： n系统将计算机资源分配给进程。 n单道程序环境与多道程序环境 n处理器调度： n多道程序环境下将处理器分配给各进程 2021-6-23计算机操作系统- 第3章7/98 调度要解决的问题： nWHAT：按什么原则分配CPU n调度算法 nWHEN：何时分配CPU n调度的时机 nHOW： 如何分配CPU n调度过程 调度的概念与本质 2021-6-23计算机操作系统- 第3章8/98 处

3、理器调度的层次 n处理机是计算机系统中的重要资源 n处理机调度算法对整个计算机系统的综合性能指 标有重要影响 n处理机调度的三个层次： n高级调度 n中级调度 n低级调度 高级调度也称为作业调度或宏观调度高级调度也称为作业调度或宏观调度 高级调度的时间尺度通常是分钟、小时或天高级调度的时间尺度通常是分钟、小时或天 中级调度涉及进程在内外存间的交换中级调度涉及进程在内外存间的交换 从存储器资源管理的角度来看，把进程的部分从存储器资源管理的角度来看，把进程的部分 或全部换出到外存上，可为当前运行进程的执或全部换出到外存上，可为当前运行进程的执 行提供所需内存空间，将当前进程所需部分换行提供所需内存

4、空间，将当前进程所需部分换 入到内存。指令和数据必须在内存里才能被处入到内存。指令和数据必须在内存里才能被处 理机直接访问理机直接访问 低级调度也称微观调度低级调度也称微观调度 从处理机资源分配的角度来看，处理机需要经从处理机资源分配的角度来看，处理机需要经 常选择就绪进程或线程进入运行状态，低级调常选择就绪进程或线程进入运行状态，低级调 度的时间尺度通常是毫秒级的。度的时间尺度通常是毫秒级的。 由于低级调度算法的频繁使用，要求在实现时由于低级调度算法的频繁使用，要求在实现时 做到高效。做到高效。 2021-6-23计算机操作系统- 第3章9/98 高级调度-作业的概念与分类 n概念： n作业

5、由一组统一管理和操作的进程集合构成，是用户 要求计算机系统完成的一项相对独立的工作。 n作业可以是完成了编译、链接之后的一个用户程序， 也可以是用各种命令构成的一个脚本。 n分类： n根据需要处理工作的类型，分为计算型作业和I/O型 作业。 n按照作业提交方式，分为批处理作业和终端型作业。 n一个系统能够同时接纳作业的个数称为系统的多 道程序度。 2021-6-23计算机操作系统- 第3章10/98 作业的状态作业的状态： 提交状态提交状态 后备状态后备状态 执行状态执行状态 完成状态完成状态 高级调度-作业的概念与分类 作业被调度到内存，为作业分配资源并为其创建作业被调度到内存，为作业分配资

6、源并为其创建 与之对应的进程，进程获得与之对应的进程，进程获得CPUCPU，开始运行。，开始运行。 从作业的第一个进程完成开始，直到作业所有的从作业的第一个进程完成开始，直到作业所有的 进程完成，释放作业进程完成，释放作业所所占用的资源，退出系统的占用的资源，退出系统的 整个进程。整个进程。 系统接收输入的用户作业，并将其放入计算机磁系统接收输入的用户作业，并将其放入计算机磁 盘。作业在磁盘上以后备队列形式进行组织，等盘。作业在磁盘上以后备队列形式进行组织，等 待作业调度程序将作业调度到内存。待作业调度程序将作业调度到内存。 用户将作业提交给操作系统，等待输入程序和数用户将作业提交给操作系统，

7、等待输入程序和数 据到磁盘。据到磁盘。 2021-6-23计算机操作系统- 第3章11/98 高级调度-概念与模型 n作业调度概念： n按照操作系统预先规定的策略，从磁盘的作业后备队 列中选择作业调入内存，为作业分配所需要的资源并 建立与作业相对应的进程。 n当作业运行的准备工作完成后，作业调度启动作业运 行。 n在作业运行结束后，作业调度归还并释放作业占用的 资源，结束作业。 n模型： 2021-6-23计算机操作系统- 第3章12/98 高级调度-策略与因素 n接纳多少个作业 n作业数目太多时，可能会影响到系统的服务质量; n作业的数量太少时，又会导致系统的资源利用率和系 统吞吐量太低 n

8、接纳哪些作业 n先来先服务调度算法 n短作业优先调度算法 n基于作业优先级的调度算法 n响应比高者优先的调度算法 2021-6-23计算机操作系统- 第3章13/98 高级调度-OS任务 n作业调度中操作系统需要完成如下主要工作： n确定作业的数据结构 n确定作业的调度算法 n为作业分配资源 n回收作业资源 操作系统为每个进入系统的操作系统为每个进入系统的 作业分配一个与进程控制块（作业分配一个与进程控制块（PCBPCB） 类似的作业控制块（类似的作业控制块（JCBJCB） JCBJCB是作业的标志，是作业的标志，OSOS根据根据 JCBJCB中的信息对作业进行调度和管中的信息对作业进行调度和

9、管 理。理。 作业运行需要各种资源，包括硬作业运行需要各种资源，包括硬 件资源和软件资源。硬件资源有内存、件资源和软件资源。硬件资源有内存、 处理器和各种输入输出设备。软件资处理器和各种输入输出设备。软件资 源有各种共享变量等。源有各种共享变量等。 作业的资源分配策略主要考虑的作业的资源分配策略主要考虑的 是作业所包含的进程所需要的资源，是作业所包含的进程所需要的资源， 在一般情况下，资源按照进程需求进在一般情况下，资源按照进程需求进 行分配。资源分配中需要避免由进程行分配。资源分配中需要避免由进程 之间的资源竞争而造成的死锁等现象。之间的资源竞争而造成的死锁等现象。 作业完成后，作业调度程序

10、除了要输出相关的作业信息之外，作业完成后，作业调度程序除了要输出相关的作业信息之外， 还要回收作业所占用的全部资源，撤销与作业相关的进程和作业控还要回收作业所占用的全部资源，撤销与作业相关的进程和作业控 制块。制块。 在作业调度工作中，大多数工作由作业的调度程序完成。在作业调度工作中，大多数工作由作业的调度程序完成。 内存和输入输出设备的分配和释放不是由作业调度程序完成，内存和输入输出设备的分配和释放不是由作业调度程序完成， 而是由存储器管理和设备管理程序完成的。而是由存储器管理和设备管理程序完成的。 作业调度程序只是将作业对内存的要求和对设备的要求转交给作业调度程序只是将作业对内存的要求和对

11、设备的要求转交给 相应的内存管理程序和设备管理程序，由内存管理程序和设备管理相应的内存管理程序和设备管理程序，由内存管理程序和设备管理 程序完成内存和设备的分配与回收。程序完成内存和设备的分配与回收。 2021-6-23计算机操作系统- 第3章14/98 高级调度-作业状态转换 n作业调度将作业从后备状态转换到内存执行状态 n作业执行状态包含作业所对应进程的就绪、运行 和阻塞状态 2021-6-23计算机操作系统- 第3章15/98 3.1 处理器调度的层次 2021-6-23计算机操作系统- 第3章16/98 中级调度-概念与功能 n又称为中程调度，是为了提高内存利用率和平衡系统负 载而采取

12、的一种利用外存补充内存的措施。 n多进程环境下，内存中存在多个进程，其中有些进程可 能需要挂起，这些进程暂时不参与对处理器的竞争。 n为了充分利用内存资源，系统会采用进程对换的方法将 进程换出到外存，将这些进程占用的内存空间释放，让 内存能够接纳新的进程或使得内存中的进程能够更快推 进。当被换出到外存中的进程挂起时间到时，又需要将 这些进程换入到内存。 n中级调度是在换出内存的进程中确定需要进入内存的进中级调度是在换出内存的进程中确定需要进入内存的进 程的一种调度操作。程的一种调度操作。 2021-6-23计算机操作系统- 第3章17/98 3.1 处理器调度的层次 2021-6-23计算机操

13、作系统- 第3章18/98 低级调度-概念与功能 n又称为进程调度、短程调度 n按照一定的调度算法从内存的就绪进程队列中选 择进程，为进程分配处理器，避免进程对处理器 竞争的方法。 n与作业调度和中级调度比较，进程调度发生的频 率最高，作业调度发生的频率最低，中级调度主 要用于内存管理，特别是虚拟存储器管理。 2021-6-23计算机操作系统- 第3章19/98 3.1.2 进程调度模型 只有进程调度的调度队列模型 低级调度-模型 2021-6-23计算机操作系统- 第3章20/98 3.1.2 进程调度模型 具有高、低两级调度的调度队列模型 低级调度-模型 2021-6-23计算机操作系统-

14、 第3章21/98 具有三级调度时的调度队列模型 3.1.2 进程调度模型 低级调度-模型 2021-6-23计算机操作系统- 第3章22/98 低级调度-原因与机制 n引起进程调度的主要原因如下： n处理器执行的进程完成任务，处理器空闲 n处理器执行的进程转入阻塞状态，此时处理器空闲 n处理器执行的进程被其它进程抢占 n处理器执行的进程被挂起 n机制： n排队器 n分派器 n上下文切换机制 2021-6-23计算机操作系统- 第3章23/98 低级调度-调度方式 n非抢占方式： n简单，实时性差 n抢占方式 n时间片原则 n优先权原则 n短作业优先原则 如果执行进程正好在执行一个如果执行进程

15、正好在执行一个 没有资源的无限循环，则执行进没有资源的无限循环，则执行进 程不会放弃处理器，所有的就绪程不会放弃处理器，所有的就绪 进程会永久等待，系统进入了一进程会永久等待，系统进入了一 种僵持的状态。种僵持的状态。 指一个进程正在处理器中运行指一个进程正在处理器中运行 时，操作系统可以根据规定的抢时，操作系统可以根据规定的抢 占原则，将已经分配给进程的处占原则，将已经分配给进程的处 理器从进程剥夺，并分配给其他理器从进程剥夺，并分配给其他 的进程。的进程。 在系统允许抢占调度，并满足在系统允许抢占调度，并满足 抢占条件的情况下，系统才可以抢占条件的情况下，系统才可以 采用抢占调度方式。采用

16、抢占调度方式。 满足抢占条件的进程能够抢占满足抢占条件的进程能够抢占 当前正在执行进程的处理器。被当前正在执行进程的处理器。被 抢占的进程状态从执行状态变为抢占的进程状态从执行状态变为 就绪状态，其进程控制块进入到就绪状态，其进程控制块进入到 进程就绪队列。进程就绪队列。 思考：“抢占”可能带来的问题及原因？ 2021-6-23计算机操作系统- 第3章24/98 本章目录 n3.1 处理器调度的层次 n3.2 评价调度算法的准则 n3.3 调度算法 n3.4 线程调度 n3.5 实时调度 n3.6 多处理器调度 n3.7 Windows 2000/XP系统的处理器调度 2021-6-23计算机

17、操作系统- 第3章25/98 3.2 评价调度算法的准则 2021-6-23计算机操作系统- 第3章26/98 调度算法的评价准则 n基本原则： n具有公平性 n资源利用率高（特别是 CPU利用率） n在交互式系统情况下要追 求响应时间（越短越好） n在批处理系统情况下要追 求系统吞吐量 n面向系统的准则： n系统吞吐量高； n处理机利用率好； n各类资源的平衡利用 n面向用户的准则： n周转时间短； n响应时间快； n截止时间的保证； n优先权准则 2021-6-23计算机操作系统- 第3章27/98 n处理器利用率 nCPU utilization n响应时间 nresponse time

18、 n周转时间 nturnaround time n系统吞吐量 nthroughput 处理器利用率为处理器利用率为CPUCPU有效工作时间与有效工作时间与CPUCPU总的运行总的运行 时间之比，即：时间之比，即： CPUCPU利用率利用率 = CPU = CPU有效工作时间有效工作时间/CPU/CPU总的运行时间总的运行时间 CPUCPU总的运行时间总的运行时间 = CPU = CPU的有效工作时间的有效工作时间 + CPU + CPU的空的空 闲时间闲时间 响应时间是交互环境下用户从键盘提交第响应时间是交互环境下用户从键盘提交第1 1个请个请 求开始，到系统首次产生响应为止的时间，或者是屏求

19、开始，到系统首次产生响应为止的时间，或者是屏 幕上显示出结果为止的时间。幕上显示出结果为止的时间。 响应时间响应时间 = = 从终端键盘输入的请求信息传送到处理从终端键盘输入的请求信息传送到处理 机的时间机的时间 + + 处理机对请求信息的处理时间处理机对请求信息的处理时间 + + 生成的生成的 响应信息回送到终端显示器的时间响应信息回送到终端显示器的时间 周转时间指用户作业提交给操作系统开始到作业周转时间指用户作业提交给操作系统开始到作业 完成为止的时间。周转时间通常是评价批处理系统性完成为止的时间。周转时间通常是评价批处理系统性 能、选择作业调度方式与算法的重要准则之一。能、选择作业调度方

20、式与算法的重要准则之一。 周转时间周转时间TiTi = = 作业在后备队列中的等待调度时间作业在后备队列中的等待调度时间+ +进进 程在就绪队列上等待调度的时间程在就绪队列上等待调度的时间+ +进程在进程在CPUCPU上的运行上的运行 时间时间 + + 进程等待进程等待I/OI/O或其他事件发生的时间或其他事件发生的时间 作业的带权周转时间作业的带权周转时间TfTf = = 作业的周转时间作业的周转时间Ti/Ti/系统为系统为 作业提供的服务时间作业提供的服务时间TsiTsi n i si i d T T n T 1 1 n i i T n T 1 1 单位时间内处理的进程数目为单位时间内处理

21、的进程数目为CPUCPU的工作成效，的工作成效， 单位时间内完成的进程数目为系统的吞吐量。单位时间内完成的进程数目为系统的吞吐量。 在选择处理器的调度算法时，用户希望在选择处理器的调度算法时，用户希望CPUCPU利用率和系利用率和系 统吞吐量越大越好，响应时间和周转时间越小越好。统吞吐量越大越好，响应时间和周转时间越小越好。 但是，通常情况下，系统希望的是能够合理利用处理但是，通常情况下，系统希望的是能够合理利用处理 器和各类资源，使作业的平均周转时间或带权周转时间小器和各类资源，使作业的平均周转时间或带权周转时间小 的调度算法。的调度算法。 对于实时系统，作业调度的关键在于能否满足作业的对于

22、实时系统，作业调度的关键在于能否满足作业的 实时要求，对周转时间等指标并不特别着重。实时要求，对周转时间等指标并不特别着重。 调度算法的评价指标 2021-6-23计算机操作系统- 第3章28/98 本章目录 n3.1 处理器调度的层次 n3.2 评价调度算法的准则 n3.3 调度算法 n3.4 线程调度 n3.5 实时调度 n3.6 多处理器调度 n3.7 Windows 2000/XP系统的处理器调度 2021-6-23计算机操作系统- 第3章29/98 3.3 调度算法 2021-6-23计算机操作系统- 第3章30/98 3.3 调度算法 2021-6-23计算机操作系统- 第3章31

23、/98 作业调度算法 n概念回顾 n作业调度是在资源满足的条件下，将处于后备状态的 作业调入内存，同时生成与作业相对应的进程，并为 这些进程提供所需要的资源。 n作业调度程序只保证被调度的作业有获得处理器的资 格，而处理器的分配则需要进程调度才能完成。 n主要算法 nFCFS：先来先服务（First-Come First-Served) nSJF：短作业优先（Shortest-Job-First） nHRRF：响应比高者优先 nHPF：优先权高者优先（ Highest-Priority-First) n分类调度 2021-6-23计算机操作系统- 第3章32/98 FCFS：先来先服务 n基本

24、思想 n遵循先进入后备队列的作业，先进行调度的原则。 n非抢占式算法 n简单，易于编码实现 n优先考虑作业的等待时间，没有考虑作业的执行时间 长短、作业的运行特性和作业对资源的要求 n算法评价 n有利于长作业，不利于短作业 n有利于CPU繁忙的作业，不利于I/O繁忙的作业 n举例？ 2021-6-23计算机操作系统- 第3章33/98 FCFS：先来先服务-例1 n作业J1、J2、J3、J4依次到达作业后备队列，需要处 理时间分别如下：J1为15ms，J2为5ms，J3为10ms， J4为3ms。 n请给出作业执行的图示（横轴为时间，纵轴为作业） n请计算每个作业的等待时间和周转时间 n请计算

25、上述作业的平均等待时间和平均周转时间 2021-6-23计算机操作系统- 第3章34/98 FCFS：先来先服务-例2 n如果4个作业A、B、C、D到达系统磁盘后备队列 的顺序和需要执行的时间如下表所示。 作业到达时间（ms）需要执行时间（ms） A020 B515 C1010 D155 请给出作业执行的图示（横轴为时间，纵轴为作业）请给出作业执行的图示（横轴为时间，纵轴为作业） 请计算每个作业的周转时间和带权周转时间请计算每个作业的周转时间和带权周转时间 请计算上述作业的平均周转时间和平均带权周转时间请计算上述作业的平均周转时间和平均带权周转时间 2021-6-23计算机操作系统- 第3章3

26、5/98 SJF：短作业优先 n基本思想 n根据作业控制块中作业申请时指出的执行时间，选取 执行时间最短的作业优先调度。 n抢占调度方式：只要就绪队列中出现了需要执行时间 比当前正在运行作业的剩余处理时间更短的作业，则 该作业会抢占当前正在运行的作业。 n算法评价 n克服FCFS调度算法对短作业不利的缺点，效率高，易 于编程实现 n不利于长作业 n预先估计作业的执行时间 n举例？ 2021-6-23计算机操作系统- 第3章36/98 SJF：短作业优先-例3 n作业A、B、C、D需要处理的时间分别为20ms、 15ms、10ms、5ms。 n如果这4个作业同时到达作业后备队列 n请给出采用短作

27、业优先调度算法的作业执行图示 n请计算平均周转时间和平均带权周转时间 如果这如果这4个作业不是同时到达，个作业不是同时到达，A作业在作业在0时间到达，时间到达，B 作业在作业在A作业之后作业之后5ms达到，达到，C作业在作业在A作业之后作业之后10ms 达到，达到，D作业在作业在A作业之后作业之后15ms达到达到 请给出采用短作业优先调度算法的作业执行图示请给出采用短作业优先调度算法的作业执行图示 请计算平均周转时间和平均带权周转时间请计算平均周转时间和平均带权周转时间 如果如果A作业到达的时间为作业到达的时间为0，B、C、D作业达到系统的作业达到系统的 时间分别改为时间分别改为1ms、2ms

28、、3ms 请给出采用短作业优先调度算法的作业执行图示请给出采用短作业优先调度算法的作业执行图示 请计算平均周转时间和平均带权周转时间请计算平均周转时间和平均带权周转时间 2021-6-23计算机操作系统- 第3章37/98 HRRF：响应比高者优先 n初衷 nFCFS调度算法只片面地考虑了作业的进入时间，短 作业优先调度算法考虑了作业的运行时间而忽略了 作业的等待时间。 n响应比高者优先调度算法为这两种算法的折中。 n响应比计算 n作业的响应时间与作业需要处理的时间之比。 n作业的响应时间为作业进入系统后的等待时间与作 业要求处理器处理的时间之和。 n抢占调度方式 处理时间 等待时间 处理时间

29、 处理时间等待时间 处理时间 响应时间 响应比 1 2021-6-23计算机操作系统- 第3章38/98 HRRF：响应比高者优先 n分析与评价 n响应比高，可能是因为作业等待时间长，也可能是 因为作业需要处理时间短。 n响应比高优先调度算法不仅体现了等待时间长的作 业会优先调度，而且还体现了处理时间短的作业也 会优先调度。 n该算法能够客观地对待长作业和短作业。 n举例？ 2021-6-23计算机操作系统- 第3章39/98 HRRF：响应比高者优先-例4 n如果4个作业A、B、C、D到达系统磁盘后备队列 的顺序和需要执行的时间如下表所示。 作业到达时间（ms）需要执行时间（ms） A020

30、 B515 C1010 D155 计算各时间点的响应比及调度情况。计算各时间点的响应比及调度情况。 请给出作业执行的图示（横轴为时间，纵轴为作业）请给出作业执行的图示（横轴为时间，纵轴为作业） 请计算上述作业的平均周转时间和平均带权周转时间请计算上述作业的平均周转时间和平均带权周转时间 2021-6-23计算机操作系统- 第3章40/98 FCFS、SJF、HRRF：比较 作业到达时间 需要处理 时间 FCFS周 转时间 SJF周转 时间 HRRF调 度算法 A020202020 B515304530 C1010352540 D155351025 平均周转时间 30.0025.0028.75

31、平均带权周转时间 3.381.973.00 思考：对上述比较结果进行分析和评价。 2021-6-23计算机操作系统- 第3章41/98 HPF：优先权高者优先 n基本思想 n根据作业的优先权进行作业调度，每次总是选取优 先权高的作业调度。 n作业的优先数可由系统或用户给定。 n评价 n综合考虑了作业的执行时间和等待时间的长短、作 业的缓急程度、作业对外部设备的使用情况等因素 n根据系统设计目标和运行环境而给定各作业的优先 权，决定作业调度的先后顺序。 n举例？ 2021-6-23计算机操作系统- 第3章42/98 HPF：优先权高者优先-例5 n作业A、B、C、D一起达到，需要处理的时间分 别

32、为25ms、5ms、10ms、3ms，优先数分别为154、 139、149、130，优先数越大、优先级越低。 n请给出采用优先权高者优先调度算法的作业执行图示 n请计算平均周转时间和平均带权周转时间 n静态优先权 n动态优先权 思考：动态优先权的“动态性”体现？ 2021-6-23计算机操作系统- 第3章43/98 综合：分类调度算法 n目的： n均衡使用系统资源 n兼顾不同大小的作业 n基本思想 n按照使用系统资源或作业的大小的不同 n首先分别对作业进行分类 n然后再根据作业的类型进行调度 n还可以进一步将同一类别的作业再按照优先级进行 排队 2021-6-23计算机操作系统- 第3章44/

33、98 3.3 调度算法 2021-6-23计算机操作系统- 第3章45/98 进度调度算法 n概念回顾 n进程调度算法是低级调度算法。 n在传统操作系统中，进程为资源分配和调度的基本单 位，是操作系统中发生频率最高的调度。 n主要算法 nFCFS：先来先服务（略） nTRR：时间片轮转调度算法 n优先级调度算法 nMQ：多级队列调度算法 nMFQ：多级反馈队列调度算法 2021-6-23计算机操作系统- 第3章46/98 TRR：时间片轮转调度算法 n基本思想 n分时思想 n首先将处理器的处理时间划分为大小相等的时间片。 n调度程序每次从就绪队列中选择队首的进程，为之分 配处理器的一个时间片并

34、让进程运行。 n当进程运行的时间片到时，强迫进程放弃处理器，到 就绪队列中再次排队，并将处理器的下一个时间片分 配给就绪队列中队首的进程。 n所有就绪队列中的进程按照这样的形式轮转使用处理 器时间片。 n举例? 2021-6-23计算机操作系统- 第3章47/98 TRR：时间片轮转调度算法-例6 n进程A、B、C、D需要处理的时间分别为20ms、 10ms、15ms、5ms，在0时间达到。达到的先后 顺序为ABCD。 n请给出不同时间片下的调度图示； n请计算不同时间片下的平均周转时间。 nA：时间片为1 nA：时间片为5 nA：时间片为10 思考：时间片大小与平均周转时间的关系？ 2021

35、-6-23计算机操作系统- 第3章48/98 TRR：时间片轮转调度算法 n分析与评价 n抢占式调度算法 n进程切换以时间片为单位，系统的花销主要体现在进 程切换上。 n当时间片很小时，切换的频率高，时间片花销大。 n当时间片过大时，进程切换开销减小，但是进程轮转 一次需要的等待时间增加，周转时间增加。 n当时间片大到每个进程足以完成时，时间片调度算法 便退化为FCFS算法。 n时间片大小的取值需要考虑系统中进程个数、进程切 换开销、响应时间、系统效率等多种因素。 思考：固定大小时间片与可变大小时间片？ 2021-6-23计算机操作系统- 第3章49/98 优先级调度算法-例7 n同时达到的进

36、程P1、P2、P3、P4，它们的优先数 分别为80、70、75、65，数字越大表示进程优先 级越高，需要处理的时间分别是20ms、15ms、 25ms、30ms。 n请给出采用优先级算法的调度图示； n请计算平均周转时间和平均带权周转时间。 2021-6-23计算机操作系统- 第3章50/98 MQ：多级队列调度算法 n基本思想 n根据进程的类型不同，将进程就绪队列分为若干个独 立的就绪队列，不同的就绪队列采用不同的调度算法， 同一个就绪队列采用同一种进程调度算法。 n主要用于有多组就绪进程的操作系统，如有批处理用 户作业的进程和终端用户进程，批处理用户作业的进 程运行在后台，终端用户的进程运

37、行在前台。 n一个作业的进程固定划分到一个就绪队列中。按照用 户作业的性质不同，就绪队列进行不同组织。 2021-6-23计算机操作系统- 第3章51/98 作业-进程调度 n某多道程序设计系统中配有一台处理器CPU和两台输入/ 输出设备IO1和IO2。现有优先级由高到低的3个进程P1、 P2、P3同时存在，它们使用资源的先后顺序和占用时间 分别是： n进程P1： n进程P2： n进程P3： IO2(30ms)-CPU(10ms)-IO1(30ms)-CPU(10ms)-IO2(10ms) IO1(20ms)-CPU(20ms)-IO1(40ms) CPU(30ms)-IO2(20ms) 若进

38、程采用若进程采用“可抢占的最高优先级可抢占的最高优先级”调度算法，且忽略调度等所需的时调度算法，且忽略调度等所需的时 间，请回答有下列问题：间，请回答有下列问题： 1）进程）进程P1、P2、P3从开始到完成所用的时间分别是多少（要求用坐标从开始到完成所用的时间分别是多少（要求用坐标 画出三个进程的工作过程，其中横坐标表示时间，纵坐标表示画出三个进程的工作过程，其中横坐标表示时间，纵坐标表示CPU和和IO 设备）。设备）。 2）这三个进程从开始到全部完成时）这三个进程从开始到全部完成时CPU的利用率是多少？的利用率是多少？IO1和和IO2 的利用率是多少？的利用率是多少？ 2021-6-23计算

39、机操作系统- 第3章52/98 本章目录 n3.1 处理器调度的层次 n3.2 评价调度算法的准则 n3.3 调度算法 n3.4 线程调度 n3.5 实时调度 n3.6 多处理器调度 n3.7 Windows 2000/XP系统的处理器调度 2021-6-23计算机操作系统- 第3章53/98 线程调度 n现代OS中，进程是资源分配的基本单位， 线程是调度的基本单位。因此，低级调度为 线程调度。 n由于线程需要进程环境的支撑，因此，线程 调度与线程和进程之间的关系有关。 n线程的实现方式有: n用户级线程 n内核级线程 2021-6-23计算机操作系统- 第3章54/98 线程调度 n现代OS

40、中，进程是资源分配的基本单位， 线程是调度的基本单位。因此，低级调度为 线程调度。 n由于线程需要进程环境的支撑，因此，线程 调度与线程和进程之间的关系有关。 n线程的实现方式有: n用户级线程 n内核级线程 2021-6-23计算机操作系统- 第3章55/98 用户级线程 n内核看不见用户级线程，内核按照进程调度 分配处理器。 n用户级线程存在于用户地址空间 n内核在进程调度时，根据相应的进程调度算 法。在每个进程分得的时间片中，由线程调 度算法决定该进程中的线程怎样共享这个时 间片，决定哪个线程首先被处理器运行。 n线程调度算法与进程调度算法没有关系 n为实现简单，线程调度算法会选择FCF

41、S的方式。 2021-6-23计算机操作系统- 第3章56/98 用户级线程 n内核看不见用户级线程，内核按照进程调度 分配处理器。 n用户级线程存在于用户地址空间 n内核在进程调度时，根据相应的进程调度算 法。在每个进程分得的时间片中，由线程调 度算法决定该进程中的线程怎样共享这个时 间片，决定哪个线程首先被处理器运行。 n线程调度算法与进程调度算法没有关系 n为实现简单，线程调度算法会选择FCFS的方式。 2021-6-23计算机操作系统- 第3章57/98 内核级线程 n线程调度在处理器调度中起决定作用。 n内核会根据线程调度算法选择一个处于就绪 状态的内核级线程运行。 n在选择线程时，

42、内核不会考虑该线程属于哪 一个进程，对所有进程的所有线程都公平对 待，任何一个线程都被看作一个独立的线程。 n线程最大的优势在于应用在多处理器环境下 2021-6-23计算机操作系统- 第3章58/98 内核级线程 n线程调度在处理器调度中起决定作用。 n内核会根据线程调度算法选择一个处于就绪 状态的内核级线程运行。 n在选择线程时，内核不会考虑该线程属于哪 一个进程，对所有进程的所有线程都公平对 待，任何一个线程都被看作一个独立的线程。 n线程最大的优势在于应用在多处理器环境下 2021-6-23计算机操作系统- 第3章59/98 本章目录 n3.1 处理器调度的层次 n3.2 评价调度算法

43、的准则 n3.3 调度算法 n3.4 线程调度 n3.5 实时调度 n3.6 多处理器调度 n3.7 Windows 2000/XP系统的处理器调度 2021-6-23计算机操作系统- 第3章60/98 实时调度 n实时操作系统中的处理器调度为实时调度。 n实时调度要求能够控制实时进程，满足实时 任务的时间限制。 n在实时系统中，衡量调度性能的指标不是周 转时间和等待时间，而是能否满足实时任务 的截止时间要求。 2021-6-23计算机操作系统- 第3章61/98 3.5.1 实时调度需要满足的条件 n实时任务截止时间是实时调度的基本指标。 n实时调度需要满足如下条件： n系统向实时调度提供与

44、实时任务相关的信息 n对系统处理能力的衡量 n抢占调度和快速切换机制 2021-6-23计算机操作系统- 第3章62/98 与实时任务相关的信息（1） n就绪起始时间 n实时任务对应的进程被创建并加入到进程就绪队列 n如果实时任务是周期任务，就绪起始时间是一个时间串 n如果实时任务是非周期任务，就绪起始时间是一个预知 的值 n截止时间 n当实时系统中的实时任务发生时，实时系统中的就绪进 程按照进程的截止时间进行排列 n对于周期性实时任务，截止时间为下一次任务发生的时 间 n对于非周期性实时任务，任务的所有者需要提供截止时 间 2021-6-23计算机操作系统- 第3章63/98 与实时任务相关

45、的信息（2） n处理时间 n实时任务从开始到完成所需要的时间。可由实 时任务的所有者提供，也可以由系统提供 n实时任务的资源需求 n实时任务执行时所需要的一组资源 n实时任务的优先级 n用户或系统需要为每个实时任务指定优先级， 作为调度的依据 2021-6-23计算机操作系统- 第3章64/98 对系统处理能力的衡量 n实时系统中，可能因为处理器的处理能力不 足而影响实时任务的完成，或导致系统产生 故障。 n单处理器情况下系统对周期性的实时任务的 处理，必须满足下列条件： n其中，i表示周期事件，Pi为周期事件i发生 的周期，Ci为需要处理器的处理时间。 2021-6-23计算机操作系统- 第

46、3章65/98 对系统处理能力的衡量 n当系统不能调度这些周期性实时任务时，可 以通过提高处理器的处理能力的方法减少每 个周期任务的处理时间；或者采用多处理器 系统，提高处理能力。 n如果采用的处理器数目为N，则处理条件变 为： 2021-6-23计算机操作系统- 第3章66/98 抢占调度和快速切换机制 n在要求严格的实时系统中，允许一个优先权高的 实时任务抢占优先权低的实时任务 n在实际应用中，判断能否满足截止时间要求不是 一件容易的事 n快速切换机制可以实现对实时任务的快速切换 n快速切换机制用硬件装置实现快速中断机构，做到尽量 不漏掉实时任务的中断，禁止中断的时间越短越好 n在软件实现

47、上，也可以通过提高分派程序对任务 切换的速度，以提高系统的性能。 2021-6-23计算机操作系统- 第3章67/98 3.5.2 实时调度算法 n实时调度算法分为: n动态实时调度算法在实时任务运行时作出调度 决策。 n静态实时调度算法在系统启动实时任务之前作 出调度决策。 2021-6-23计算机操作系统- 第3章68/98 常用的实时调度算法 - 抢占式调度算法 n常用于要求严格的实时系统中 n基于时钟中断的优先权抢占调度算法 n如果某实时任务的优先级高于正在运行的任务，该实时任 务并不立刻抢占，而是等到时钟中断到来时，才抢占。 n立即抢占调度算法 n一旦出现外部中断，只要系统不处于临界

48、区，系统立即剥 夺当前执行的任务，把处理器分配给当前紧急的任务。 n单比率调度算法 n事先为每个实时任务分配一个与任务发生频率成正比的优 先级，运行频率越高的任务，其优先级越高。运行时优先 级高的任务可以抢占优先级低的任务。 2021-6-23计算机操作系统- 第3章69/98 常用的实时调度算法 - 非抢占式调度算法 n实时调度中，对于实时要求不太严格的系统，可 以采用非抢占式调度 n非抢占式轮转调度算法 n运行完一个对象的实时任务（将其挂在队列尾，等待下 次运行），再运行另一个对象的实时任务。所有实时任 务轮转。 n非抢占式优先级调度算法 n系统按照优先级进行非抢占调度。要求紧迫的实时任务

49、 赋予高的优先级，排在就绪队列队首，先进行调度。 n期限调度算法 n根据实时任务的截止期限进行就绪队列的排队，截至期 限短的实时任务排在队首，首先进行调度。 2021-6-23计算机操作系统- 第3章70/98 常用的实时调度算法举例 n实时系统中有一组实时任务A、B、C、D、E，CPU 处理时间分别为325ms、225ms、160ms、95ms、 420ms，截止时间分别为690ms、675ms、无期限、 135ms、1 100ms。 n如果采用最小截止期限优先调度算法，这些进程 调度的顺序为？ 2021-6-23计算机操作系统- 第3章71/98 常用的实时调度算法举例 n实时系统中有一组

50、实时任务A、B、C、D、E，CPU 处理时间分别为325ms、225ms、160ms、95ms、 420ms，截止时间分别为690ms、675ms、无期限、 135ms、1 100ms。 n采用最小截止期限优先调度算法，进程调度的顺 序为：DBAEC 2021-6-23计算机操作系统- 第3章72/98 本章目录 n3.1 处理器调度的层次 n3.2 评价调度算法的准则 n3.3 调度算法 n3.4 线程调度 n3.5 实时调度 n3.6 多处理器调度 n3.7 Windows 2000/XP系统的处理器调度 2021-6-23计算机操作系统- 第3章73/98 多处理器调度 n计算机系统有多

51、个处理器，多个处理器的调度称 为多处理器调度。多处理器调度与多处理器系统 的结构形式有关： n松耦合多处理器系统 n每个处理器相对独立，拥有自己的内存和I/O通道。多 处理器调度对系统中的每个处理器，采取与单处理器调 度相同的方法。 n紧耦合多处理器系统 n多个处理器共享内存和外围设备，处理器的相对独立性 差。在这种多处理器系统中，处理器调度方法比较复杂。 2021-6-23计算机操作系统- 第3章74/98 多核处理器 n多核处理器是在一个处理器中封装多个处理 核（单元），每个核都具有处理能力。 n多核处理器相当于共用内存和外围设备的多 处理器，在原理上多核处理器属于紧耦合多 处理器系统。

52、2021-6-23计算机操作系统- 第3章75/98 3.6.1 多处理器中同步的粒度 n在多处理器系统中，不但存在多处理器的并 行，还存在单处理器的并发。 n多处理器中同步的粒度指系统中的多个进程 或线程之间同步的频率，是描述多处理器系 统特征和进程并发度的重要指标。 n根据进程或线程之间同步的周期划分为5个 层次：细粒度并行、中粒度并行、粗粒度并 行、超粗粒度并行、独立并行。 2021-6-23计算机操作系统- 第3章76/98 同步的周期 n细粒度并行细粒度并行 n同步周期小于20条指令，非常复杂的并行操作，属于超高并行度应 用 n中粒度并行中粒度并行 n同步周期为20200条指令。此类

53、应用适合于多线程技术实现，多 线程并发执行，降低OS在进程切换上的开销。 n粗粒度并行粗粒度并行 n同步周期为2002 000条指令，此类应用适用于多进程并发实现。 n超粗粒度并行超粗粒度并行 n同步周期为2 000条指令以上，进程之间的交互频率非常小。 n独立并行独立并行 n进程之间没有明显的同步，每个进程都代表独立的应用或作业。 2021-6-23计算机操作系统- 第3章77/98 同步的周期 n一个具有细粒度和中粒度并行的线程应用， 由于线程之间的交互非常频繁，线程的调度 策略对整个系统的性能有很大影响。 n对具有独立并行的进程、具有粗粒度并行的 进程和超粗粒度并行的进程，进程的调度策

54、略与多道程序系统相似。 2021-6-23计算机操作系统- 第3章78/98 3.6.2 多处理器调度的设计要点 n多处理器调度策略的设计比单处理器复杂， 其设计要点包括： 1.多处理器分配策略 2.如何在每个处理器上支持多道线程 3.如何从就绪队列中指派进程 2021-6-23计算机操作系统- 第3章79/98 多处理器分配策略 （1）结构上多个处理器地位相同 n多处理器对内存和I/O设备的访问方式相同，地位相当 n所有处理器放在一个处理器池中 n静态分配策略 n在进程创建时系统把所创建的进程永久分配给一个处理 器，每个处理器对应一个进程调度队列。 n动态分配策略 n所有处理器共用一个进程就

55、绪队列，当某个处理器空闲 时，系统从进程就绪队列中调度一个进程运行。 n优点：实现简单，调度代价低 n缺点：容易造成处理器之间工作负 荷不均匀 2021-6-23计算机操作系统- 第3章80/98 多处理器分配策略 （1）结构上多个处理器地位相同 n多处理器对内存和I/O设备的访问方式相同，地位相当 n所有处理器放在一个处理器池中 n静态分配策略 n在进程创建时系统把所创建的进程永久分配给一个处理 器，每个处理器对应一个进程调度队列。 n动态分配策略 n所有处理器共用一个进程就绪队列，当某个处理器空闲 时，系统从进程就绪队列中调度一个进程运行。 n优点: 简单、方便，利于提高系统效率 n缺点:

56、 进程在不同处理器之间切换，系 统调度进程开销大 2021-6-23计算机操作系统- 第3章81/98 多处理器分配策略 （2）结构上多个处理器地位不同 n如果各处理器之间对内存和I/O设备的地位和访问 方式不相同，则系统可将多个处理器分为主处理 器和从处理器，主处理器管理从处理器。 nOS核心运行在主处理器上，所有的调度策略由主 处理器上的OS核心决定，多处理器调度需要考虑 每个处理器的工作负荷。 n优点: 处理器调度效率非常高，甚至比单处理器下 的多道程序系统还高。 n缺点: 整个系统过分依赖主处理器上运行的OS核心， 如果OS核心出现问题或主处理器出现问题，多处 理器系统会全面崩溃。 2

57、021-6-23计算机操作系统- 第3章82/98 多处理器分配策略 n多处理器系统如果不采用主从方式，可以采 用分布式管理结构。 n在分布式管理结构下，OS可以在所有处理 器上执行，每个处理器都可以自我调度，系 统的可靠性更高。 n缺点：实现非常复杂，在操作系统之间很难 保持同步。 2021-6-23计算机操作系统- 第3章83/98 多处理器分配策略 n综合主从式系统和分布式系统的优点，CMU 的Mach操作系统就是一个典范。 n支持线程的操作系统 n建立二级线程队列，实现多处理器下线程调度 n第1级为一个全局共享的就绪线程队列 n第2级为每一个处理器的局部就绪线程队列 n第2级队列中所有

58、线程都已调度完，系统才到全 局就绪线程队列中按照动态调度策略分配线程 2021-6-23计算机操作系统- 第3章84/98 如何在每个处理器上支持多道线程 n如何在多处理器系统的每个处理器上支持多 道线程，是多处理器系统调度的难点。 n（1）粗粒度并发、超粗粒度并发和独立并 发的进程 n一个处理器上实现多进程并发，在多个处理器 上实现多进程并行都是可能的 n（2）中粒度并发的进程，或细粒度并发的 线程 n调度方式需分别针对不同的线程实现进行分析 2021-6-23计算机操作系统- 第3章85/98 如何从就绪队列中指派进程 n对从就绪队列中选择哪个进程运行的问题， 在单处理器的进程调度算法中有

59、先来先服务、 优先级高者优先等很多方法。 n对多处理器系统，如果进程调度算法太复杂， 调度算法的实现会使系统付出过高的代价。 n因此，在选择调度算法上强调的是算法使系 统运行简单有效和代价低。 2021-6-23计算机操作系统- 第3章86/98 3.6.3 线程调度策略 n多处理器系统中，进程与线程并发，多处理 器调度中非常典型的是线程调度 1负载共享调度算法 2群调度算法 3处理器指定调度算法 4动态调度算法 2021-6-23计算机操作系统- 第3章87/98 负载共享调度算法 n如果多处理器系统是中粒度并发的进程，细粒度 并发的线程，当一个处理器空闲时，系统从全局 共享线程队列中选择一个就绪线程占有处理器运 行。线程调度的方法有： n先来先服务 n所有线程按照到来的