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

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