第10章 多处理器和实时调度 主要内容： 多处理器调度 实时调度 操作系统调度例 分类与粒度 设计问题 进程调度 实时进程的要求与特点 线程调度的本质 实时调度的方法——限时调度、速率单调调度 操作系统调度例 Linux调度 Unix SVR4调度 Unix FreeBSD调度 Windows调度 Unix虚拟机进程调度

10.1 多处理器调度 多处理器系统分类 松耦合（loosely coupled）、分布式多处理器、机群（cluster）：由一系列相对自治的系统组成，每个处理器有自己的内存和I/O通道（见第16章） 专门功能处理器：如I/O处理器，受通用的主处理器控制，为主处理器提供服务（见第11章） 紧耦合多处理器：由一系列共享内存的处理器组成（如多核）（本章讨论）

10.1.1 粒度 系统中进程间的同步粒度（synchronization granularity）或同步率（frequency of synchronization）——可用于刻画多处理器及与其他架构的比较 可根据粒度的不同划分5类并行度 无约束（independent）并行性——进程相互独立，无显式同步 非常粗粒度（very coarse grained）并行性——只在非常粗的级别上存在同步，一般不需修改用户软件 粗粒度（coarse grained）并行性——只在粗的级别上存在同步，只需对用户软件进行很少的修改 中等粒度（medium-grain）并行性——进程中的一组线程，需要高度的合作与交互 细粒度（fine-grained）并行性——线程内的并行，使用复杂 前三种对进程调度的影响不大，最后一种迄今研究不够

同步粒度与进程 粒度大小 说明 同步间隔(指令数) 细 单指令流中固有的并行 <20 中等 单独应用中的并行和多任务处理 20~200 粗 并发进程的多处理 200~2000 非常粗 网络节点上的分布式处理 2000~1M 无约束 无关进程 不适用

10.1.2 设计问题 多处理器调度设计的三个相互关联的问题 把进程分配到处理器 对称多处理器的调度——把处理器视为一个资源池，将进程分配到处理器 静态分配——一个进程从激活到完成，一直分配给同一处理器，每个处理器有一个专门的短程队列。调度开销小，但可能出现有的处理器空闲而有的处理器繁忙的问题 动态分配——使用一个全局性的公共队列，在一个进程的生命周期中，不同的时间可在不同的处理器上执行。在紧耦合对称多处理器结构（如多核）中，进程调度的开销与被调度到哪个处理器无关 动态负载平衡——线程可在各处理器的短程队列间转移，如Linux 在单个处理器上使用多道程序设计——对运行于有众多处理器的系统中的中等粒度应用程序，让每个处理器繁忙不再是首要目标，更关注如何为应用程序提供最好的平衡性能 一个进程的实际分派——使用优先级和其他复杂的高级调度算法，对多处理器系统可能会起到相反的效果，简单的调度方法可能会更有效

10.1.3 进程调度 在多处理器调度中，一般进程不是指定给某个特定处理器，也不是所有处理器只有一个队列，而是有多条基于优先级的队列。多处理器系统可视为一种多服务器排队结构 在多处理器系统中，调度原则和算法的选择没有在单处理器中的重要。使用FCFS往往就足够了

单处理器和双处理器的调度性能比较 变化系数Cs = σs / Ts 其中：σs为服务时间的标准差、Ts为平均服务时间

10.1.4 线程调度 一个应用程序可实现为一组线程，它们可在同一地址空间中协作和并发执行 在多处理器系统中，线程可用于开发应用程序的真正并行性，线程的全部能力可得到更好的展现 多处理器线程调度和处理器分配的主要方案 负载共享（load sharing） 组调度（gang scheduling） 专用处理器分配（dedicated processor assignment） 动态调度（dynamic scheduling）

负载共享 最简单，可从单处理器直接移植，目前使用最多 优点 缺点 负载被均衡分布到各个处理器上 不需要集中调度器（操作系统的调度例程可在任何空闲的处理器上运行） 可使用单处理器的各种调度算法（如FCFS，它甚至优于[可抢占的]最少线程数优先） 缺点 在处理器众多时，互斥访问内存可能出现瓶颈 被抢占的线程可能在另一个处理器上恢复执行，处理器的本地高速缓存效率低 线程池中不区分进程，同一进程的所有线程不可能同时获得处理器的使用权，这对需要高度合作的线程，所涉及的进程切换会严重影响性能

组调度 gang scheduling 优点 用于同时调度组成一个进程的一组线程 对中等和细粒度的并行应用程序非常必要，可避免性能的严重下降 紧密相关的进程并行执行时，同步阻塞减小、进程切换很少、性能提高 调度开销减少，一个决策影响许多处理器和进程 用于同时调度组成一个进程的一组线程 对中等和细粒度的并行应用程序非常必要，可避免性能的严重下降 已被广泛认同，并已在许多多处理器操作系统中实现

专用处理器分配 组调度的一种极端形式 应用程序的每个线程被固定分配给一个处理器，该处理器专门运行此线程，直到应用程序结束 属于单道程序设计，似乎极其浪费处理器时间 采用此策略的原因 在一个有众多（几十或几百个）处理器的高度并行系统（如GPU流处理器、向量并行机）中，每个处理器只占系统总代价的一小部分，单个处理器的利用率不再是衡量有效性和性能的重要因素 在应用程序的生命周期中，避免进程切换可加快程序的运行速度

多处理器调度问题似内存分配问题 组调度和专用处理器分配，在解决处理器分配问题时，都对传统的单处理器调度策略和算法进行了抨击 多处理器系统中的处理器分配问题，不同于单处理器的调度问题，而是类似于单处理器的内存分配问题 在给定时刻给一个程序分配多少个处理器，类似于给定时刻给一个进程分配多少个页帧 （借用虚拟内存术语）活动工作集——为保证应用程序以可接受的速度运行，在处理器池中必须同时调度的最少数目的活动线程 存在类似的处理器抖动和处理器碎片等问题，可用组调度和专用处理器分配来避免

动态调度 应用程序可能允许动态改变进程中的线程数目，使得操作系统可通过调整负载来提高利用率 操作系统只负责把处理器分配给作业，由作业负责将其的一部分可运行的任务映射到线程，并使用当前划分给它的处理器来执行这些任务 将如何选择运行的子集、在进程被抢占时挂起那个线程等决策，留给应用程序 不适用于所有应用程序 对可以采用这种动态调度的应用程序，下面的算法优于组调度和专用处理器分配，但开销较大

动态调度算法 操作系统的调度责任主要局限于处理器分配 操作系统的动态调度算法 当一个作业请求若干处理器时（或因为作业第一次到达、或因为其请求发生了改变）： 若有足够的空闲处理器，则满足请求 否则，若发请求的作业是新到达的，则从已经分配了多个处理器的作业中，分出一个处理器给该作业 若该请求的任何分配都得不到满足，则它保持未完成状态，直到有一个处理器变成空闲可用，或者该作业取消了它的请求 当释放了若干处理器（包括作业离开）时： 为这些处理器扫描当前未得到满足的请求队列，给表中当前还没有处理器的作业（即处于等待状态的新到达作业）分配一个处理器 然后再次扫描该表，按FCFS原则分配剩下的处理器

10.2 实时调度 实时计算越来越重要。实时系统的应用越来越广泛——过程控制、机器人、交通管制、电信、军事指挥、自动驾驶、智能生产等等 操作系统，尤其是调度程序，是实时系统中的最主要组件 实时计算——系统的正确性不仅取决于计算的逻辑结果，而且还依赖于产生结果的时间 可通过定义实时进程或实时任务来定义实时系统 在实时系统中，某些任务是实时任务，具有一定的紧急程度

实时任务 试图控制外部世界发生的事件，或者对这些事件做出反应 由于这些事件是“实时”发生的，因此实时任务必须跟得上它所关注的事件 通常给特定的任务制定一个最后的期限，指定其开始时间或结束时间。可以是非周期性的或周期性的（每隔周期T一次或每隔T个单位一次） 任务的分类 硬实时任务——必须满足最后期限，否则会给系统带来不可接受的破坏或致命的错误 软实时任务——希望满足最后期限的要求，但并不是强制的。即使超过了最后期限，调度和完成任务仍有意义

实时操作系统的要求 实时操作系统应该具备如下5个方面的要求： 可确定性（determinism）——可按固定的、预先确定的时间或时间间隔执行操作。可用从最高优先级设备中断到达到开始服务之间的延迟来度量（非实时系统为几十到几百毫秒，实时系统为几微秒到1毫秒）。关注操作系统获知有一个中断发生之前的延迟 可响应性（responsiveness）——关注在知道中断之后，操作系统为中断提供服务的时间 用户控制（user control）——实时系统中允许用户细粒度地控制任务的优先级是必不可少的，还可以设置其它特性，如使用页面调度或进程交换、哪个进程必须常驻内存、使用何种磁盘算法、不同优先级的进程各有哪些权限 可靠性（reliability）——比非实时系统要求高，系统的故障、性能的损失或降低，都会产生灾难性的后果 故障弱化操作（fail-soft operation）——系统在故障时尽可能多地保存其性能和数据的能力。其一个重要特征为稳定性——优先满足最重要、优先级最高任务的最后期限

实时操作系统的特点 为满足以上要求，实时操作系统包括如下典型特点： 快速的进程或线程切换 小巧（只具备最小限度的功能） 迅速响应外部中断的能力 通过信号（量）和事件之类的进程间通信工具实现多任务处理 使用可快速存储数据的特殊顺序文件 基于优先级的抢占式调度 最小化禁止中断的时间间隔 使任务延迟一段固定时间或暂停/恢复任务的原语 特别的警报和超时设定

实时系统 实时系统的核心是短程任务调度 调度的公平性和最小平均响应时间并不是最重要的，最重要的是保证所有硬实时任务都能够在它们的最后期限内完成（或开始），尽可能多的软实时任务也可在它们的最后期限内完成（或开始） 大多数当代实时操作系统，都不能直接处理最后期限，而是实际成尽可能地对实时任务做出响应，一般是微秒级和毫秒级的。常常采用立即抢占方式，操作系统几乎是立即响应中断

实时调度 静态表法 静态优先级抢占法 基于动态规划的调度法 动态尽力调度法

限期调度（Deadline Scheduling） 实时操作系统的设计目标——尽可能快地启动实时任务，强调快速中断处理和任务分派 实时应用程序并不关心绝对速度，而是关注在最有价值的时间（既不要太早，也不要太晚）完成（或启动）任务 实时调度依赖任务的额外信息 就绪时间 启动或完成的最后期限 处理时间 资源需求 优先级——指导调度程序 子任务结构——只有必须执行的子任务才拥有硬最后期限

速率单调调度 Rate Monotonic Scheduling（RMS） 针对周期性任务 最短任务具有最高优先级 优先级是速率的单调增加函数 已被广泛用于工业应用 优势 性能差别少，利用率常达90% 大多数硬实时系统也有软实时部件，非关键性任务可在低优先级上运行 易于实现稳定性

优先级反转（Priority Inversion） 基于优先级的可抢占调度中发生的一种现象，与实时调度的上下文关联很大 在优先级调度方案中，系统应该执行具有最高优先级的任务 当系统环境迫使较高优先级的任务等待较低优先级的任务时（例如被同一个资源阻塞），优先级反转发生 无界限（unbounded）优先级反转——优先级的反转的持续时间不仅依赖于处理共享资源的时间，还依赖于其他不相关任务的不可预测的行为

10.3 Linux调度 2.4及更早版本的Linux采用传统Unix的非实时调度算法，其实时调度程序与非实时的耦合在一起 SCHED_FIFO：先进先出实时线程 SCHED_RR：轮转实时线程 SCHED_OTHER：其他非实时线程 每个调度类都使用了多优先级（共140个），实时类的100个优先级（0~99）高于非实时类的40个优先级（100~139）

非实时调度 2.4及以前的Linux，非实时调度随着处理器和程序的数目增加而性能下降 其调度程序的缺点： 对SMP（对称多处理器）使用单个队列，一个任务可以调度到任何一个处理器上运行。有利于负载均衡，但是不利于高速缓存 使用一个运行队列锁，单个处理器选择任务执行的动作，会阻止其他处理器从该队列中调度任务 采用非抢占的调度策略，高优先级的任务必须等待低优先级的任务结束才能执行

Linux 2.6的O(1)调度策略 设计目标——不论系统负载和处理器数目如何变化，选择一个合适的进程并分配给一个处理器的时间是恒定的 为每个处理器维护两套调度用的数据结构 140个活动队列——就绪的进程被放入合适的活动优先级队列，并被赋予一个合适的时间片。一个140比特的位图数组——其中的每个比特表示对应优先级的活动队列是否为空 140个过期队列——完成时间片的任务被放入合适的过期优先级队列，并被赋予一个新的时间片。一个140比特的位图数组——其中的每个比特表示对应优先级的过期队列是否为空

调度数据结构

调度方法 简单有效，虚拟轮转，对I/O密集型任务有利 对给定处理器，选择具有最高优先级的非空活动队列（~辅助队列） ；如果所有活动队列都为空，则选择具有最高优先级的非空过期队列（~就绪队列） 如果一个队列中有多个任务，采用轮转方式调度 在时间片完成之前（如因I/O）被抢占的任务，以后返回活动优先队列；完成时间片的任务，进入过期优先级队列 周期地检查分配给每个处理器的任务是否平衡。为平衡负载，会将一些高优先级的任务从一个处理器转移到另一个处理器 实时任务的优先级为0~99、非实时任务的优先级为100 ~139（默认为120）。静态优先级由用户指定，动态优先级由（一个关于进程等待和运行时间的表格）计算得出 时间片大小为10~200ms

实时任务调度 实时任务只有静态优先级，不动态改变 SCHED_FIFO任务没有时间片（~FCFS），阻塞解除后仍然返回同一活动优先级队列 SCHED_RR任务分配了时间片，且不会转移到过期队列。时间片用完后仍然返回同一活动优先级队列，而且不改变时间片的大小

10.4 Unix SVR4 调度 对传统的Unix调度算法进行了全面的修改 增加了可抢占的静态优先级调度程序，引入160种优先级（0~159，数目越大优先的级别越高！），划分成三类： 实时（159~100）60级 内核（99~60）40级 分时（用户态进程）（59~0）60级 插入了可抢占点——内核代码中可以被安全中断的位置 分时类进程的优先级是可变的，完成时间片后会降低（~多级队列反馈），在事件/资源上阻塞后会提高 分时进程的时间片大小与优先级的高低相关，优先级别越高，时间片越短。59级10ms、0级100ms 实时进程的优先级和时间片都是固定不变的

10.5 Unix FreeBSD调度 是教材的第7版新增加的 优先级分成5类256级（级数越小级别越高）： 0~63（64级）：内核底层（由中断调度，可因等待资源阻塞） 64~127 （64级） ：内核高层（运行直到被阻塞或完成，可因等待资源阻塞） 128~159 （32级） ：实时用户（总是运行直到被阻塞或有更高优先级的线程可用。抢占式调度） 160~223 （64级）：分时用户（基于处理器的使用情况调整优先级） 224~255（32级）：空闲用户（只在没有分时或实时线程可运行时才能运行）

SMP与多核支持 关注处理器亲和（processor affinity）的需求 对多核系统上的多线程更好的支持 处理器亲和——只有在为了避免处理器空闲时，才将线程从一个处理器转移到另一个处理器（称之为线程移动[migration]）。原因为本地高速缓存只能用于单个处理器，移动线程的开销大 对多核系统上的多线程更好的支持 改进调度算法的性能，使其不再是系统中线程数的函数 新调度程序的关键特性 队列结构——为每个处理器维护三个队列，两个（当前/下一）运行队列用于内核、实时和分时调度类，第三个只用于空闲类 交互式计分——主动睡眠时间与运行时间的比值低于一个特定的阈值的线程被认为是交互式的 线程移动（migration）——为了平衡负载，调度程序支持两种机制： 拉机制（pull mechanism）——空闲处理器从非空闲处理器偷线程 推机制（push mechanism）——一个周期性的调度程序任务，评估当前的负载情况并使其平衡。该任务每秒2次挑选系统中负载最重和最轻的处理器，并平衡它们的运行队列

10.6 Windows调度 设计目标——在高度交互环境或作为服务器，尽可能地响应单个用户的需求 实现了具有灵活优先级系统的抢占式调度程序，包括在每个级别内采用轮转调度、基于当前线程活动来对某些级别的优先级进行动态改变 调度单位是线程而不是进程 优先级分成两类：实时的和可变的 每类有16种优先级别，级数越大级别越高（似Unix SVR4）。实时类的优先级（16~31）高于可变类的优先级（0~15） 实时类的优先级是固定不变的，可变类的优先级可以改变（但不能超过15） 每个优先级都有一个FIFO队列

可变优先级 可变类线程的初始优先级，由进程的基本优先级和线程的基本优先级确定： 线程初始优先级 = 进程基本优先级 + 线程基本优先级 进程的基本优先级是进程对象的属性，取值0~15 线程的基本优先级是相对于进程的优先级别，取值在±2之间 线程被阻塞后，会被调度程序提高优先级别；线程用完时间片后，会被调度程序降低优先级别 线程的当前优先级只能在进程基本优先级-2~15之间波动，不能超过这一范围 处理器密集型线程的优先级低、I/O密集型线程的优先级高、交互式线程的优先级最高

可变类线程优先级的变化

处理器调度 多处理器调度 单处理器调度 N个处理器 N个优先级最高的线程被分配给处理器 优先运行优先级最高的线程，除非它被阻塞 若有多个线程具有相同的最高优先级，则处理器被它们循环共享 多处理器调度 N个处理器 N个优先级最高的线程被分配给处理器 若一个线程准备运行，但唯一可用的处理器不是其亲和集中的，则该线程被迫等待。下一个线程被调度到该处理器运行

10.7 Linux虚拟机进程调度 也是教材的第7版新增加的 Linux VServer虚拟机 参见2.11（P71）

习题（选做） 10.1 10.2 10.3 10.5