多处理器与实时调度.pptVIP

第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）并行性——线程内的并行，使用复杂 前三种对进程调度的影响不大，最后一种迄今研究不够 同步粒度与进程 10.1.2 设计问题 多处理器调度设计的三个相互关联的问题 把进程分配到处理器 对称多处理器的调度——把处理器视为一个资源池，将进程分配到处理器 静态分配——一个进程从激活到完成，一直分配给同一处理器，每个处理器有一个专门的短程队列。调度开销小，但可能出现有的处理器空闲而有的处理器繁忙的问题 动态分配——使用一个全局性的公共队列，在一个进程的生命周期中，不同的时间可在不同的处理器上执行。在紧耦合对称多处理器结构（如多核）中，进程调度的开销与被调度到哪个处理器无关 动态负载平衡——线程可在各处理器的短程队列间转移，如Linux 在单个处理器上使用多道程序设计——对运行于有众多处理器的系统中的中等粒度应用程序，让每个处理器繁忙不再是首要目标，更关注如何为应用程序提供最好的平衡性能 一个进程的实际分派——使用优先级和其他复杂的高级调度算法，对多处理器系统可能会起到相反的效果，简单的调度方法可能会更有效 10.1.3 进程调度 在多处理器调度中，一般进程不是指定给某个特定处理器，也不是所有处理器只有一个队列，而是有多条基于优先级的队列。多处理器系统可视为一种多服务器排队结构 在多处理器系统中，调度原则和算法的选择没有在单处理器中的重要。使用FCFS往往就足够了 单处理器和双处理器的调度性能比较 10.1.4 线程调度 一个应用程序可实现为一组线程，它们可在同一地址空间中协作和并发执行 在多处理器系统中，线程可用于开发应用程序的真正并行性，线程的全部能力可得到更好的展现 多处理器线程调度和处理器分配的主要方案 负载共享（load sharing） 组调度（gang scheduling） 专用处理器分配（dedicated processor assignment） 动态调度（dynamic scheduling） 负载共享 最简单，可从单处理器直接移植，目前使用最多 优点 负载被均衡分布到各个处理器上 不需要集中调度器（操作系统的调度例程可在任何空闲的处理器上运行） 可使用单处理器的各种调度算法（如FCFS，它甚至优于[可抢占的]最少线程数优先） 缺点 在处理器众多时，互斥访问内存可能出现瓶颈 被抢占的线程可能在另一个处理器上恢复执行，处理器的本地高速缓存效率低 线程池中不区分进程，同一进程的所有线程不可能同时获得处理器的使用权，这对需要高度合作的线程，所涉及的进程切换会严重影响性能 组调度 gang scheduling 优点 紧密相关的进程并行执行时，同步阻塞减小、进程切换很少、性能提高 调度开销减少，一个决策影响许多处理器和进程 用于同时调度组成一个进程的一组线程 对中等和细粒度的并行应用程序非常必要，可避免性能的严重下降 已被广泛认同，并已在许多多处理器操作系统中实现 专用处理器分配 组调度的一种极端形式 应用程序的每个线程被固定分配给一个处理器，该处理器专门运行此线程，直到应用程序结束 属于单道程序设计，似乎极其浪费处理器时间 采用此策略的原因 在一个有众多（几十或几百个）处理器的高度并行系统（如显卡流处理器、向量并行机）中，每个处理器只