操作系统教程—Linux实例分析 孟庆昌 第9章 多处理器系.ppt

第第9 9章章 多处理器系统多处理器系统 第第9章章 多处理器系统多处理器系统 9.1 概述概述 9.2 多处理器结构多处理器结构 9.3 多处理器操作系统类型多处理器操作系统类型 9.4 多处理器调度和同步多处理器调度和同步 习题习题 第第9 9章章 多处理器系统多处理器系统 9.1 概概 述述 通常所说的多CPU系统，其实包括四种类型，即多处理器系统（Multiprocessor Systems）、多计算机系统（Multicomputer Systems）、网络系统（Network Systems）和分布式系统（Distributed Systems）。由于网络系统和分布式系统都具有通过网络互连的分布属性，因此往往又把二者统归为分布式系统。图9-1示出多处理器系统、多计算机系统和分布式系统的一般模型。第第9 9章章 多处理器系统多处理器系统 图9-1 各系统的一般模型(a)多处理器系统；(b)多计算机系统；(c)分布式系统第第9 9章章 多处理器系统多处理器系统 图9-1(a)示出了共享内存的多处理器系统的模型。从图(a)中可以看出，它的每个节点只有一个CPU，所有外部设备都是共享的。图9-1(b)示出了传送消息的多计算机系统的模型。这种系统又称为集群计算机（Cluster Computers）系统或COWS（Clusters of Workstations）系统。图9-1(c)示出了广域分布式系统的模型。每个节点是一个完整的计算机，不仅有CPU、内存，还有完整的一组设备，即各自是一个自治系统。第第9 9章章 多处理器系统多处理器系统 9.2 多处理器结构多处理器结构 一般认为，多处理器的概念应包含以下几点：（1）包含两台或多台功能相近的处理器，且彼此可交换数据；（2）所有处理器共享内存；（3）所有处理器都共享I/O通道、控制器和外部设备；第第9 9章章 多处理器系统多处理器系统 （4）整个系统由统一的操作系统控制，在处理器和程序之间实现作业、任务、程序段、数组及其元素各级的全面并行。第第9 9章章 多处理器系统多处理器系统 9.2.1 UMA多处理器结构 1.基于总线的UMA SMP结构 最简单的多处理器结构是基于单一总线的结构，如图9-2(a)所示。问题的一种解决办法是对每个CPU增加一个高速缓存（Cache），如图9-2(b)所示。图9-2(c)是另一种设计，其中每个CPU不仅有缓存，而且还有本地私有的内存，通过专用总线进行存取。第第9 9章章 多处理器系统多处理器系统 图9-2 基于总线的三种多处理器(a)没有缓存；(b)有缓存；(c)有缓存和私有内存第第9 9章章 多处理器系统多处理器系统 2.利用交叉开关的UMA多处理器 利用缓存可以改善总线的传输压力，但是单个总线仍把UMA多处理器的水平限制在16个或32个CPU的范围内。为了超越这个限制，就需要采用不同类型的互连网络。把n个CPU连到k个内存中的最简单的电路是交叉开关，如图9-3所示。第第9 9章章 多处理器系统多处理器系统 图9-3 交叉开关的互连方式(a)88交叉开关；(b)打开的交叉点；(c)闭合的交叉点第第9 9章章 多处理器系统多处理器系统 3.利用多级开关网络的UMA多处理器 另一种完全不同的设计方式是基于低档的22开关，有两个输入端和两个输出端，到达任一输入端的消息都可被切换到任一输出端，如图9-4(a)所示。因此，消息由四个部分组成，如图9-4(b)所示。其中“模块”字段表示使用哪个内存；“地址”部分指定模块中的地址；“操作码”给出具体操作，如READ或WRITE；“值”字段是可选的，包括一个操作数，如要写出的一个32位的字。这种开关检查模块字段，用来确定消息是送往X端还是Y端。第第9 9章章 多处理器系统多处理器系统 图9-4 基于低档的22开关设计方式 (a)22开关；(b)消息格式第第9 9章章 多处理器系统多处理器系统 利用这种22开关可以构造更大型的多级开关网络，方法很多。如图9-5所示的称为omega网络的模型。其中有8个CPU连到8个内存中，使用12个开关。更一般的关系是，如果CPU和内存分别有n个，则需要设立的级数为lg2n，每级的开关个数为n/2个，总开关数为(n/2)lg2n。很显然，这比n2个交叉点要少得多，尤其当n值较大时。第第9 9章章 多处理器系统多处理器系统 图9-5 omega开关网络 第第9 9章章 多处理器系统多处理器系统 omega网络的连线方式往往称为“洗牌”，因为每一级的信号混合起来，类似于插入一半牌，然后再混合起来。其工作过程是：设CPU 011要从内存模块110中读取一个字。该CPU向开关1D发送一个READ消息，其中的模块字段包含110。这个开关取出110的第一位（最左位），用它进行寻径，规则是：“0”切换到输出高端，“1”切换到输出低端。然后依次取第二位、第三位。因而，从CPU 011到内存模块110的路径是1D2D3D。在图9-5中用字母a表示。回答时使用011（CPU号码）寻径，并且要反过来读：从右至左。第第9 9章章 多处理器系统多处理器系统 9.2.2 NUMA多处理器结构 NUMA机器有三个关键性质，这些性质区别于其他多处理器。它们是：（1）有单一地址空间，对所有CPU可见；（2）通过LOAD和STORE指令存取远程内存；（3）存取远程内存比存取本地内存要慢。第第9 9章章 多处理器系统多处理器系统 图9-6 大型CC-NUMA多处理器(a)基于目录的处理器；(b)32位内存地址的结构；(c)节点36的目录第第9 9章章 多处理器系统多处理器系统 9.3 多处理器操作系统类型多处理器操作系统类型 9.3.1 多处理器系统的问题 多处理器操作系统在功能上与多道程序操作系统有很多相似之处，例如二者都要解决以下问题：（1）资源分配和管理；（2）各种表格和数据集的保护；（3）防止出现系统死锁；（4）非正常终止；（5）进程间的通信。第第9 9章章 多处理器系统多处理器系统 多处理器系统中出现的新问题概括起来有以下几个方面：（1）各处理器任务的分派和调度；（2）处理器间的通信管理；（3）处理器失效的检测、诊断和校正；（4）并行进程对共享数据存取时的保护。第第9 9章章 多处理器系统多处理器系统 9.3.2 多处理器操作系统类型 1.主/从结构 主/从系统的体系结构如图9-7所示。只有主控机能执行其操作系统（在核心态下工作），而从机仅能执行用户程序（在用户态下工作）。第第9 9章章 多处理器系统多处理器系统 图9-7 主/从多处理器系统模型 第第9 9章章 多处理器系统多处理器系统 2.对称结构 对称结构是最难实现的一种多处理器体系结构，其功能也最强。如图9-8所示。与主/从结构不同，在这种结构中，所有的处理器都一样。该系统的操作系统管理一个由各个处理器组成的组合体，其中任一成员都可控制I/O设备或对内存单元进行访问。第第9 9章章 多处理器系统多处理器系统 图9-8 对称多处理器模型 第第9 9章章 多处理器系统多处理器系统 3.非对称结构 在非对称多处理器（ASMP）系统中，每个处理器都可运行自己的操作系统或一个操作系统的某一部分，负责本机用户的中断处理及其所属资源的管理，这类似于单机操作系统的功能，如各自的操作系统对本机进程进行调度，对自己的文件系统和I/O设备进行控制、管理。第第9 9章章 多处理器系统多处理器系统 9.4 多处理器调度和同步多处理器调度和同步 9.4.1 多处理器调度 在单处理器系统中调度是一维的，就是说只考虑“下面让哪个进程运行”即可。而在多处理器系统中调度是二维的，即调度程序不仅要选择让哪个进程运行，还要决定它在哪个CPU上运行，因而增加了调度的复杂性。第第9 9章章 多处理器系统多处理器系统 1.时间共享 这种算法解决单独进程（即彼此无关）的调度问题，它是最简单的一种算法：整个系统有一个表示就绪进程的数据结构，如多级队列法那样，依进程优先级的高低设立不同的队列，在同一就绪队列中的进程有相同的优先级，如图9-9(a)所示。第第9 9章章 多处理器系统多处理器系统 设有16个CPU当前都在忙，有14个进程正等待运行。设4号CPU首先完成当前工作（或者进程阻塞），它就封锁调度队列，并从中选取一个优先级最高的进程（如A），如图9-9(b)所示。接着12号CPU空闲，则选择进程B在其上运行，如图9-9(c)所示。可见，只要各进程是完全无关的，那么这种调度方式是可行的。第第9 9章章 多处理器系统多处理器系统 图9-9 使用单一数据结构对多处理器进行调度第第9 9章章 多处理器系统多处理器系统 2.空间共享 空间共享常用于相关进程的调度。因为有些进程彼此间是有关联的，如并发make的例子。此外，一个进程也往往创建多个线程。其工作过程是：设有一组相关线程同时创建，此时，调度程序查看系统中空闲CPU的个数是否与刚创建的线程数一样多或者更多。第第9 9章章 多处理器系统多处理器系统 图9-10 CPU分区第第9 9章章 多处理器系统多处理器系统 3.合伙调度 空间共享一个明显的优点是消除了多道程序设计，这也就消除了上下文切换的负担。然而，它也带来了明显的特点，即浪费时间，当CPU上的线程阻塞时则无事可做，直至该线程再次成为就绪为止。后来人们找到一种新算法，把时间和空间的调度结合起来，这就是合伙（Gang）调度。第第9 9章章 多处理器系统多处理器系统 在一个进程的多个线程被单独调度的情况下，设有两个进程A和B，且A和B各自有两个线程A0和A1，B0和B1。A0和B0在0号CPU上分时运行，A1和B1在1号CPU上分时运行。A0和A1需要经常通信，且采用请求应答方式，其通信过程如图9-11所示。由图9-11可见，每200 ms才完成一次请求应答，不是很好。第第9 9章章 多处理器系统多处理器系统 图9-11 进程A的两个线程间的通信第第9 9章章 多处理器系统多处理器系统 采用合伙调度方式可解决这类问题。合伙调度的思想是：（1）相关线程组成一伙（小群体），作为一个调度单位。（2）所有的同伙成员同时运行在不同的CPU上，按时间共享的方式。（3）所有的同伙成员一起开始和结束它们的时间片。第第9 9章章 多处理器系统多处理器系统 图9-12 合伙调度 第第9 9章章 多处理器系统多处理器系统 9.4.2 多处理器同步 在多处理器中各CPU之间经常需要同步，如对核心临界区和表格的访问要互斥执行。在单CPU系统中，对核心表格的互斥访问只需在存取表格前禁止中断即可。而在多处理器系统中，简单地禁止中断只对实施禁止的CPU起作用，而对其他CPU不起作用，它们照样可以进入临界资源操作。第第9 9章章 多处理器系统多处理器系统 在单CPU系统中，利用测试并上锁（TSL，Test and Set Lock）指令可以实现对临界资源的互斥操作。类似2.4.3节所讲的锁操作，互斥操作将一个内存字读到一个寄存器中，然后在该内存地址上存放一个非零值（如1）。读数和写数操作各自占用一个总线周期。只要不中途打断该指令，就能正常工作。第第9 9章章 多处理器系统多处理器系统 习习 题题 1.什么是多处理器系统？为什么要引入多处理器系统？2.多CPU系统通常包含哪几种类型？3.什么是UMA？什么是NUMA？4.UMA多处理器结构主要有哪几种？5.多处理器操作系统主要解决的问题有哪些？第第9 9章章 多处理器系统多处理器系统 6.多处理器操作系统的类型主要有哪些？7.多处理器调度算法主要有哪几种？各自的基本思想是什么？8.多处理器系统中能否直接用2.4.3节中的锁操作原语实现互斥？为什么？试设计一种改进方案。