4.5 实时调度算法 实时调度是为了完成实时处理任务而分配计算机处理器的调度方法。实时处理任务要求计算机在用户允许的时限范围内给出计算机的响应信号。 实时处理任务可分为 硬实时任务（hard real-time task） 软实时任务（soft real-time task）。 其中，前者要求计算机系统必须在用户给定的时限内完成，后者允许计算机系统在用户给定的时限左右处理完毕。

⑴ 对实时系统的要求： 1提供必要的调度信息，如就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级； 2调度方式，广泛采用抢占调度方式，特别是在实时要求严格的实时系统； 3具有快速响应外部中断的能力； 4 很快的进程和线程切换速度。

⑵ 对几种调度算法的评述： 1 时间片轮转调度算法：这是一种常用于分时系统的调度算法，它只能适用于一般实时信息处理系统，而不能用于实时要求严格的实时控制系统。 2 非抢占的优先级调度算法：常用于多道批处理系统的调度算法，也可用于实时要求不太严格的实时控制系统。 3 基于时钟中断抢占的优先级调度算法：用于大多数的实时系统中。 4 立即抢占的优先级调度算法：这种算法适用于实时要求比较严格的实时控制系统。

⑶ 代表性的实时调度算法： 1 时限式调度法(deadline scheduling)：是一种以满足用户要求时限为调度原则的算法。有周期性调度和非周期性调度。时限有：处理开始时限（开始截止时间）和处理结束时限（完成截止时间）两种，在实际中可以使用任一种时限。 2 频率单调调度(rate monotonic scheduling)：是一种被广泛用于多周期性实时处理的调度算法。其基本原理是频率越长（周期越长）的任务优先级越低。

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

具有完成截止时间的周期性实时任务的调度 例：如果系统中有两个周期性的实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B要求每50ms执行一次，执行时间为25ms。任务A和B每次的开始截止时间分别为A1、A2、A3…和B1、B2、B3…见图。 为了保证不遗漏任何一次截止时间，应采用最早截止时间优先的剥夺策略。

思考：如果只考虑紧迫程度，调度图应该怎么画？ 开始截止时间 A1(10) A2(30) A3(50) A4(70) A5(90) A6(110) A7(130) A8 t 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 B1(25) B2(75) B3(125) A1 A2 A3 A4 A5 A6 A7 0 10 30 40 45 55 70 80 90 100 110 130 140 B1(20) B1(5) B2(15) B2(10) B3(20) 具有完成截止时间的周期性实时任务调度 A、B周期数相差太远，所以先执行B 思考：如果只考虑紧迫程度，调度图应该怎么画？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

作业 一个四道作业的操作系统中，设在一段时间内先后到达 6个作业，它们的提交时间和运行时间见表 作业号 提交时间 运行时间 JOB1 作业号 提交时间 运行时间 JOB1 JOB2 JOB3 JOB4 JOB5 JOB6 8:00 8:20 8:25 8:30 8:35 8:40 60 35 20 25 5 10 系统采用短作业优先的调度算法，作业被调度进入运行后不再 退出，但当一作业进入运行时，可以调整运行的优先次序。 1 按照所选择的调度算法，请分别给出上述6个作业的执行时间次序 2 计算在上述调度算法下作业的平均周转时间

作业 一个具有两道作业的批处理系统，作业调度采用短作业优先 的调度算法，进程调度采用以优先数为基础的抢占式调度算法 ，如下表的作业序列（表中所有作业优先数即为进程优先数， 数值越小优先级越高）。 1 列出所有作业进入内存时间及结束时间 2 计算平均周转时间 作业的执行时间 作业名 到达时间 估计运算时间 优先数 A 10：00 40分 5 B 10：20 30分 3 C 10：30 50分 4 D 10：50 20分 6

作业 有5个批处理作业（A、B、C、D、E）几乎同时到达一个计算 中心，估计的运行时间分别为2，4，6，8、10分钟，它们的 优先数分别为1，2，3，4，5（1为最低优先级），对下面的 每种调度算法，分别计算作业的平均周转时间。 1 最高优先级先 2 时间片轮转（时间片为2分钟） 3 FIFO（作业到达顺序为C、D、B、E、A） 4 短作业优先