第五章 处理机管理 CPU Scheduling 处理机调度类型和模型 调度算法的选择和评价 调度算法

优先级调度算法 Priority Scheduling 作业调度： 从后备作业队列中选择优先级最高且系统能满足其资源要求的作业装入内存 进程调度： 选择就绪队列中优先级最高的进程分配处理机

Priority Scheduling调度方式 非抢占式优先级算法 进程一旦获得处理机就一直运行下去直至完成或因某事件发生而等待，些时才再次进行进程调度 一般用于批处理系统、分时系统 抢占式优先级算法 一旦出现一个新的就绪进程且其优先级比当前进程高，就立即停止当前运行的进程而调入新进 即当有新的就绪进程就进行进程调度，与当前运行进程的优先级对比，以决定是否调度新进程

优先数的类型 静态优先级 动态优先级 创建进程时确定进程的优先数，且在进程的整个运行期间保持不变（假设小的数优先级低） 确定优先级的依据 进程的类型 进程对资源的需求 根据用户的要求 动态优先级 创建时赋予一个初始优先级，但可随进程的执行情况的变化而改变，以获得更好的调度性能 例，设0为最低优先级，每隔1分钟优先级加1，若有一长作业初值为0，在队列中等了1小时，其优先级就增加到60，从而被调度。 在抢占式调度中也可规定正在执行的进程优先数以某个速率下降，防止一个长作业长期占用处理机

Priority Scheduling 的例子

时间片轮转调度算法Round Robin Each process gets a small unit of CPU time (time slice), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue. If there are n processes in the ready queue and the time slice is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units. Performance q large  FIFO q small  q must be large with respect to context switch, otherwise overhead is too high.

Example of RR with Time Slice= 1 时间片为1时的例子 Process Arrival Time Service P1 P2 P3 P4 P5 2 4 6 8 3 5

Time Quantum and Context Switch Time 时间片的选择与进程转换时间 time slice( quantum 数量/定量)

时间片的选择 must be substantially(充分的) larger than the time required to handle the clock interrupt and dispatching(调度) should be larger then the typical interaction (but not much more to avoid penalizing(不利于) I/O bound processes) 时间片大于典型 的交互时间 响应时间 响应时间 时间片 被抢占 时间片小于典型 的交互时间

时间片的选择时考虑的因素 系统对响应时间的要求 就绪队列中进程的数目 系统的处理能力

多级反馈队列调度算法 Multilevel Feedback Scheduling Preemptive scheduling with dynamic priorities 动态优先级的抢占式调度 Several ready to execute queues with decreasing priorities: 按优先级构成多个就绪队列 P(RQ0) > P(RQ1) > ... > P(RQn) New process are placed in RQ0 新进程放入优先级为0（高优先级）的队列 When they reach the time quantum, they are placed in RQ1. If they reach it again, they are place in RQ2... until they reach RQn 时间片用完将被放入下一级就绪队列直到第n级队列 I/O-bound processes will stay in higher priority queues. CPU-bound jobs will drift downward. I/O进程将保持在较高优先级队列中，而计算型将降级 Dispatcher chooses a process for execution in RQi only if RQi-1 to RQ0 are empty 仅当0至i-1级队列中无进程时才调度i级队列的进程

各级队列具有大小不同的时间片，0级时间片最小，各级逐渐递增 新进程进入较高优先级的空就绪队列时重新调度，抢占处理 Windows NT中就采用该算法

MFS调度算法的性能 能照顾到短型作业用户的要求（如终端用户） 能照顾到短批处理型作业用户的要求 能照顾到输入/输出型作业用户的要求 能照顾到计算机型作业用户的要求 常辅以定时提升队列，以获得服务

实时调度算法 Real-Time Scheduling 实时调度是为了完成实时处理任务而分配计算机处理器的调度方法。实时处理任务要求计算机在用户允许的时限范围内给出计算机的响应信号。 实时系统的分类 硬实时系统Hard real-time systems – required to complete a critical task within a guaranteed amount of time. 软时实系统Soft real-time computing – requires that critical processes receive priority over less fortunate ones. 硬实时系统要求计算机系统必须在用户给定的时限内完成，软时实系统允许计算机系统在用户给定的时限左右处理完毕

调度期Dispatch Latency 事件 响应事件 中断 处理 调度周期 时实进 程执行 调度

对实时系统的要求 提供必要的调度信息 调度方式 具有快速响应外部中断的能力 进程的就绪时间 进程开始执行截止时间和完成执行截止时间 进程处理所需时间 进程的资源要求 进程优先级 调度方式 具有快速响应外部中断的能力

实时调度算法 Real-Time Scheduling 时间片轮转调度算法 这是一种常用于分时系统的调度算法，它只能适用于一般实时信息处理系统，而不能用于实时要求严格的实时控制系统。 秒级的响应时间 非抢占的优先级调度算法 常用于多道批处理系统的调度算法，也可用于实时要求不太严格的实时控制系统 数百毫秒级的响应时间 基于时钟中断抢占的优先级调度算法 用于大多数的实时系统中 几毫秒级的响应时间 立即抢占的优先级调度算法 这种算法适用于实时要求比较严格的实时控制系统 上百微秒级的响应时间

实时调度实例 在事前能知道各实时任务的开始截止时间，且对调度时延要求 不太严格的情况下可以采用最早截止时间优先的非剥夺性调度策略 1 3 4 2 开始截止时间 执行任务 1 3 4 2 t 任务到达 4 1 2 3 系统首先调度任务1执行，在任务1执行期间，任务2、3 先后到达，由于任务3的截止时间早于任务2的，故系统在 任务1后将调度任务3执行。

Windows NT Priority Relationship Process Priority Thread’s Base Thread’s Dynamic 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 base priority highest above normal normal below normal lowest

多处理机调度 什么是多处理机系统 多处理机操作系统的分类 多处理机系统调度策略

1.什么是多处理机系统 多处理机系统：是一个具有两个或多个处理机并能相互进行通信以协同一个大的给定问题求解的计算机系统。 特点： 1）  有两个或多个处理机 2）  共享主存或高速通信网络 3）  共享输入输出子系统 4）  有单一完整的操作系统 5）  各级硬件和软件相互作用

主要功能： ●进程分配 ●更好的利用多机硬件 ●资源在处理机之间的分配 ●改善程序的响应时间 ●处理机的负载平衡 ●处理机间的协调和同步 ●因处理机故障引起的系统重组

广义上说，使用多处理机协调工作，来完成用户所要求任务的计算机系统。这包扩了并行处理系统（parallel processing system），例如数据流机(dataflow machine)和细胞阵列处理机(Celluar array processors)等,也包扩了在物理上分散且通过不同的物理传输媒体传输数据的计算机网络系统和计算机网络为基础的,对用户透明的分布式系统,以及在同一的计算机系统里共享内存的多处理机系统. 广义的计算机系统的一个共同的特点是有n个处理器(n>1),能做到真正的并行处理,也就是能同时执行n条指令.

2.多处理机操作系统的分类 本节所介绍的多处理机操作系统是指那些用来并行执行用户的几个程序，以提高系统的吞吐率；或 并行操作以提高系统可靠性的多处理操作系统。这种系统由共享公共内存和外设的n(n>1)个 CPU组成。 从概念上说，在多处理机系统中的各进程的行为与在单机系统下的行为相同。因此，对多处理机操作系统的要求与对多道程序的批处理系统没有太多的区别。但是，多处理环境下，进程可在各处理机间进行透明迁移，从而，由进程上下文切换等带来的系统开销将使得多处理机操作系统的复杂度大大增加。另外，由于多处理机系统并行地执行用户的几个程序（进程），这又带来了多处理机条件下的并发执行问题。

(1) 主从式（master-slave configuration） (2) 独立监控系统(Separate supervisor) 使用多处理机系统的主要原因是提高系统的可靠性和在发生故障时能降级使用；另一个原因是提高系统吞吐 。因此，一个多处理机操作系统除了提高资原分配和管理，进程和处理机管理，内存和数据集保护以及文件系统等功能之外，还能提供系统结构重组的能力，以支持系统的降级使用。因此，多处理机的调度策略也必须考虑到降级使用和结构重组问题。 目前多处理机操作系统可以分为三类： (1) 主从式（master-slave configuration） (2) 独立监控系统(Separate supervisor) (3) 移动式监控系统(floating supervisor)

主从式中，指定一台特定的处理机为主处理机，由它负责对全系统的执行进行控制. (1)主从式（master-slave configuration） 主从式中，指定一台特定的处理机为主处理机，由它负责对全系统的执行进行控制. 在主从式操作系统中，主处理器上执行操作系统程序，以控制其它从处理机的状态，并为从处理机分配任务。DEC system 10 ,Cyber 170 以及多处理机UNIX系统MPX都是主从式结构.在主从式操作系统中,如果从处理机需要主处理机提供服务时,它们采用硬件中断方式中断处理机上执行的进程以要求主处理机提供服务.这种结构的操作系统一般重组功能较差,因为只有主处理机上执行操作系统程序.如果主处理机失败或发生不可恢复的错误时,整个系统将会瘫痪.

独立监控系统不像主从结构那样易于崩溃,但其监控程序在各处理机中的副本会占去大量的内存. (2)独立监控系统(Separate supervisor) 独立监控系统的监控程序在每个处理机上执行, 每个处理机为自己的需要提供服务又互相通报执行情况.一般来说,每个监控程序能重新装入或在不同的处理机上复制独立的副本. 独立监控系统不像主从结构那样易于崩溃,但其监控程序在各处理机中的副本会占去大量的内存. 列如: IBM 370/158

移动式监控系统：移动式监控系统把监控程序根据需要从一个处理机移到另一个处理机上.使所有资源有比较均衡的负载. (3)移动式监控系统(floating supervisor) 移动式监控系统：移动式监控系统把监控程序根据需要从一个处理机移到另一个处理机上.使所有资源有比较均衡的负载. 移动式监控系统的处理机调度以及服务请求冲突等大都采用优先级的方式来解决.所以 移动式监控系统是一种效率最高,实现最难的多处理操作系统. IBM 3081上运行的MVS,VM以及C·mmp上运行的Hydra

3. 多处理机系统调度策略 （1） 多处理机系统与单机调度的区别 多处理机调度与单机调度的主要区别涉及两个资源分配问题： 一是存放程序或数据的存储器分配及如何访问他们的问题。 在多机系统中，由于各进程在物理上也同时执行而不是单机系统那样的交叉执行，这些在物理上同时执行的进程可能同时访问物理存储器的同一地址。处理机对同一存储块的访问必须是顺序的。各进程同时访问物理存储器上的同一地址是不允许的。

二是将等待执行的就绪进程分配到哪一个处理机上执行的问题。 在单机系统中，由于只有一个处理机，在调度程序中选取了某个就绪状态的进程之后，不须再选择处理机。而在多机系统中，为了尽量做到让各处理机负荷平衡，可能会将处理机在进程之间进行多次切换。如果被切换进程正在执行其临界区部分或系统中进程数目相当多，这种频繁的上下文转换将会使系统效率大大下降。

为了解决进程对处理机的分配问题，在有的多处理机系统中采用了局部就绪对列的方法限制进程的转移。 局部就绪对列：就是把处于就绪状态的进程分成不同的组，并使每一组进程和一个处理机对应起来。这样，每个处理机只执行以其对应就绪对列中的进程。各个就绪对列中的进程不断发生横向转移。这种方法减少了调度程序的开销。但是，处理机的使用率却因此下降。例如：系统中某个局部就绪对列中因等待进程较多而使得对应的处理机十分繁忙，而另外的处理机则因就绪对列为空而处于空闲状态。

多处理机系统的调度目标是：以最高的可靠性，使用最少的处理机在最短的时间内完成最多的可以并行完成的进程。

（2）多处理机的调度评价 多处理机的调度有两种评价模型： 一种是确定性模型，另一种是随机性模性。 确定性模型：进程调度执性之前，估计出这些被调度进程所须要的执行时间，以及这些进程之间的相互关系。 调度程序的目的：是根据给定的执行时间和相互关系，确定出一个最佳的执行顺序。 因此，确定性模型只用来确定给定进程的执行顺序，而随机性模性则常被用来研究动态调度技术。 （2）多处理机的调度评价