《现代操作系统》-读书笔记-第八章-多处理机系统

《现代操作系统》-读书笔记-第八章-多处理机系统

多处理机

共享存储器多处理机(或以后简称为多处理机,multiprocessor)是这样一种计算机系统,其两个或更多的 CPU 全部共享访问一个公用的 RAM。运行在任何一个 CPU 上的程序都看到一个普通(通常是分页)的虚拟地址空间。这个系统唯一特别的性质是,CPU 可对存储器的某个字写入某个值,然后读回该字,并得到一个不同的值(因为另一个 CPU 改写了它)。在进行恰当组织时,这种性质构成了处理器间通信的基础:一个 CPU 向存储器写入某些数据而另一个读取这些数据。

至于最重要的部分,多处理机操作系统只是通常的操作系统。它们处理系统调用,进行存储器管理,提供文件系统并管理 IO 设备。不过,在某些领域里它们还是有一些独特的性质。这包括进程同步、资源管理以及调度。下面首先概要地介绍多处理机的硬件,然后进入有关操作系统的问题。

多处理机硬件

所有的多处理机都具有每个 CPU 可访问全部存储器的性质,而有些多处理机仍有一些其他的特性,即读出每个存储器字的速度是一样快的。这些机器称为 UMA (Uniform Memory Access,统一存储器访问)多处理机。相反,NUMA (Nonuniform Memory Acces,非一致存储器访问)多处理机就没有这种特性。至于为何有这种差别,稍后会加以说明。我们将首先考察 UMA 多处理机,然后讨论 NUMA 多处理机。

  1. 基于总线的 UMA 多处理机体系结构

最简单的多处理机是基于单总线的,参见图 8-2 a。两个或更多的 CPU 以及一个或多个存储器模块都使用同一个总线进行通信。当一个 CPU 需要读一个存储器字(memory word)时,它首先检査总线忙否。如果总线空闲,该 CPU 把所需字的地址放到总线上,发出若干控制信号,然后等待存储器把所需的字放到总线上

当某个 CPU 需要读写存储器时,如果总线忙,CPU 只是等待,直到总线空闲。这种设计存在问题。在只有两三个 CPU 时,对总线的争夺还可以管理;若有 32 个或 64 个 CPU 时,就不可忍受了。这种系统完全受到总线带宽的限制,多数 CPU 在大部分时间里是空闲的

这一问题的解决方案是为每个 CPU 添加一个高速缓存(cache),如图 8-2 b 所示。这个高速缓存可以位于 CPU 芯片的内部、CPU 附近、在处理器板上或所有这三种方式的组合。由于许多读操作可以从本地高速缓存上得到满足,总线流量就大大减少了,这样系统就能够支持更多的 CPU。一般而言,高速缓存不以单个字为基础,而是以 32 字节或 64 字节块为基础。当引用一个字时,它所在的整个数据块(叫作一个 cache 行)被取到使用它的 CPU 的高速缓存当中。

每一个高速缓存块或者被标记为只读(在这种情况下,它可以同时存在于多个高速缓存中),或者标记为读写(在这种情况下,它不能在其他高速缓存中存在)。如果 CPU 试图在一个或多个远程高速缓存中写入一个字,总线硬件检测到写,并把一个信号放到总线上通知所有其他的高速缓存。如果其他高速缓存有个“干净”的副本,也就是同存储器内容完全一样的副本,那么它们可以丢弃该副本并让写者在修改之前从存储器取出高速缓存块。如果某些其他高速缓存有“脏”(被修改过)副本,它必须在处理写之前把数据写回存储器或者把它通过总线直接传送到写者上。高速缓存这一套规则被称为高速缓存一致性协议,它是诸多协议之一。

  1. 使用交叉开关的 UMA 多处理机

即使有最好的高速缓存,单个总线的使用还是把 UMA 多处理机的数量限制在 16 至 32 个 CPU。要超过这个数量,就需要新的互连网络。连接 n 个 CPU 到 k 个存储器的最简单的电路是交叉开关。交叉开关在电话交换系统中已经采用了几十年,用于把一组进线以任意方式连接到一组出线上。

  1. 使用多级交换网络的 UMA 多处理机
  2. NUMA 多处理机
  3. 多核芯片
  4. 众核芯片

“多核”只是简单地表示核的数量多于一个,但是当核的数目继续增加时,我们会使用另一个名称“众核”。众核芯片是指包括几十、几百甚至成千上万个核心的多核处理器。尽管并没有严格的界限来区分什么情况下叫“多核”、什么情况下叫“众核”,但一个简单的区分方式是,如果你不介意损失一两个核心,这时候你使用的就是“众核”了。

  1. 异构多核

一些芯片会把一个 GPU 和一些通用处理器核封装在一起,许多片上系统在通用处理器核之外还包括个或多个特殊用途的处理器。在一块芯片上封装了不同类型的处理器的系统被统称为异构多核处理器。

  1. 在多核上编程

硬件领先软件的情况过去就时常出现,尽管多核芯片现在已经出现了,我们却还不能为它们编写应用程序。当前的编程语言并不适合编写高度并行的程序,好的编译器和调试工具也很少见,程序员很少

有并行编程的经验,大多数人甚至不知道可以把任务划分为多个模块来并行执行。同步、消除资源竟争条件和避免死锁等问题就像噩梦一般,更不幸的是,如果不处理好这些问题性能就会受到严重影响,信号量也不能很好地解决问题。

除了这些问题,我们还不清楚究竟什么样的应用オ需要成百个(更不用说上千个)处理器核一尤其是在家用环境下。当然另一方面,在大规模服务器集群中,通常是有很多需要大量处理器核的任务的。比如一个热门服务器可以很简单地为每一个客户端请求使用不同的处理器核,同样上一节讨论过的云提供商也可以在这些核心上提供大量的虚拟机来出租给需要计算能力的客户们。

多处理机操作系统类型

  1. 每个 CPU 有自己的操作系统

组织一个多处理机操作系统的可能的最简单的方法是,静态地把存储器划分成和 CPU 一样多的各个部分,为每个 CPU 提供其私有存储器以及操作系统的各自私有副本。实际上 n 个 CPU 以 n 个独立计算机的形式运行。这样做一个明显的优点是,允许所有的 CPU 共享操作系统的代码,而且只需要提供数据的私有副本。这种模型很少被使用。

  1. 主从多处理机

在这种模型中,操作系统的一个副本及其数据表都在 CPU1 上,而不是在其他所有 CPU 上。为了在该 CPU1 上进行处理,所有的系统调用都重定向到 CPU1 上。如果有剩余的 CPU 时间,还可以在 CPU1 上运行用户进程。这种模型称为主从模型(master- slave),因为 CPU1 是主 CPU,而其他的都是从属 CPU。

这种模型虽然很简单,而且对小型多处理机是可行的,但不能用于大型处理机。

  1. 对称多处理机

我们的第三种模型,即对称多处理机(Symmetric MultiProcessor, SMP),消除了上述的不对称性。在存储器中有操作系统的一个副本,但任何 CPU 都可以运行它。在有系统调用时,进行系统调用的 CPU 陷人内核并处理系统调用。图 8-9 是对 SMP 模式的说明。

这个模型动态地平衡进程和存储器,因为它只有一套操作系统数据表。它还消除了主 CPU 的瓶颈,因为不存在主 CPU;但是这个模型也带来了自身的问题。特别是,当两个或更多的 CPU 同时运行操作系统代码时,就会出现灾难。想象有两个 CPU 同时选择相同的进程运行或请求同一个空闲存储器页面。处理这些问题的最简单方法是在操作系统中使用互斥信号量(锁),使整个系统成为一个大临界区。当一个 CPU 要运行操作系统时,它必须首先获得互斥信号量。如果互斥信号量被锁住,就得等待。按照这种方式,任何 CPU 都可以运行操作系统,但在任-时刻只有一个 CPU 可运行操作系统。这一方法称为大内核锁(Big KernelLock, BLK)。

这个模型是可以工作的,但是它几乎同主从模式一样糟糕。同样假设,如果所有时间的 10%花费在操作系统内部。那么在有 20 个 CPU 时,会出现等待进入的 CPU 长队。幸运的是,这个模型比较容易改进。操作系统中的很多部分是彼此独立的。例如,在一个 CPU 运行调度程序时,另一个 CPU 则处理文件系统的调用,而第三个在处理一个缺页异常,这种运行方式是没有问题的。

由于这一事实,可以把操作系统分割成互不影响的临界区。每个临界区由其互斥信号量保护,所以一次只有一个 CPU 可执行它。采用这种方式,可以实现更多的并行操作。而某些表格,如进程表,可能恰巧被多个临界区使用。例如,在调度时需要进程表,在系统 fork 调用和信号处理时也都需要进程表。多临界区使用的每个表格,都需要有各自的互斥信号量。通过这种方式,可以做到每个临界区在任一个时刻只被一个 CPU 执行,而且在任一个时刻每个临界表(critical table)也只被一个 CPU 访问。

大多数的现代多处理机都采用这种管理方式。为这类机器编写操作系统的困难,不在于其实际的代码与普通的操作系统有多大的不同,而在于如何将其划分为可以由不同的 CPU 并行执行的临界区而互不干扰,即使以细小的、间接的方式。另外,对于被两个或多个临界区使用的表必须通过互斥信号量分别加以保护,而且使用这些表的代码必须正确地运用互斥信号量。

更进一步,必须格外小心地避免死锁。如果两个临界区都需要表 A 和表 B,其中一个首先申请 A,另一个首先申请 B,那么迟早会发生死锁,而且没有人知道为什么会发生死锁。理论上,所有的表可以被赋予整数值,而且所有的临界区都应该以升序的方式获得表。这一策略避免了死锁,但是需要程序员非常仔细地考虑每个临界区需要哪个表,以便按照正确的次序安排请求。

由于代码是随着时间演化的,所以也许有个临界区需要一张过去不需要的新表。如果程序员是新接手工作的,他不了解系统的整个逻辑,那么可能只是在他需要的时候获得表,并且在不需要时释放掉,尽管这看起来是合理的,但是可能会导致死锁,即用户会觉察到系统被凝固住了。要做正确并不容易,而且要在程序员不断更换的数年时间之内始终保持正确性太困难了。

多处理机同步

1、使用TSL指令

2、自旋与切换

多处理机调度

1、分时

2、空间共享

3、群调度

多计算机

多计算机硬件

1、互连技术

2、网络接口

底层通信软件

用户通信软件

远程过程调用

程序调用位于其他 CPU 中的过程。当机器 1 的进程调用机器 2 的过程时,在机器 1 中的调用进程被挂起,在机器 2 中被调用的过程执行。可以在参数中传递从调用者到被调用者的信息,并且可在过程的处理结果中返回信息。根本不存在对程序员可见的消息传递或 I/O。这种技术即是所谓的远程过程调用 (Remote Procedure Call, RPC),并且已经成为大量多计算机的软件的基础。习惯上,称发出调用的过程为客户机,而称被调用的过程为服务器,我们在这里也将采用这些名称。

RPC 背后的思想是尽可能使远程过程调用像本地调用。在最简单的情形下,要调用一个远程过程,客户程序必须被绑定在一个称为客户端存根(client stub)的小型库过程上,它在客户机地址空间中代表服务器过程。类似地,服务器程序也绑定在一个称为服务器端存根(server stub)的过程上。这些过程隐藏了这样一个事实,即从客户机到服务器的过程调用并不是本地调用。

分布式共享存储器

多计算机调度

负载平衡

分布式系统

到此为止有关多核、多处理机和多计算机的讨论就结束了,现在应该转向最后一种多处理机系统,即分布式系统(distributed system)。这些系统与多计算机类似,每个节点都有自己的私有存储器,整个系统中没有共享的物理存储器。但是,分布式系统与多计算机相比,耦合度更加松散。

网络硬件

1、以太网

2、因特网

网络服务和协议

基于文档的中间件

现在我们已经有了一些有关网络和协议的背景知识,可以开始讨论不同的中间件层了。这些中间件层位于基础网络。上,为应用程序和用户提供一-致的范型。我们将从一个简单但是却非常著名的例子开始:万维网(World Wide Web)。Web 是由在欧洲核子中心(CERN)工作的 Tim Berners-Lee 于 1989 年发明的,从那以后 Web 就像野火样传遍了全世界。

Web 背后的原始范型是非常简单的:每个计算机可以持有一个或多个文档,称为 Web 页面(Web page)。在每个页面中有文本、图像、图标、声音、电影等,还有到其他页面的超链接(hyperlink)(指针)。当用户使用一个称为 Web 浏览器(Web browser)的程序请求一个 Web 页面时,该页面就显示在用户的屏幕上。点击一个超链接会使得屏幕上的当前页面被所指向的页面替代。尽管近来在 Web 上添加了许多的花哨名堂,但是其底层的范型仍旧很清楚地存在着:Web 是一个由文档构成的巨大有向图,其中文档可以指向其他的文档。

整个系统按如下方式结合在一起:Web 根本上是一个客户机一服务器系统,用户是客户端,而 Web 站点则是服务器。当用户给浏览器提供一个 URL 时(或者键入 URL,或者点击当前页面上的某个超链接),浏览器则按照一定的步骤调取所请求的 Web 页面。作为一个例子,假设提供的 URL 是 http: //www. Minix3. org/getting -started/index. Html。浏览器按照下面的步骤取得所需的页面。

1) 浏览器向 DNS 询问 www. Minix3. Org 的 IP 地址。

2) DNS 的回答是 66.147.238.215。

3) 浏览器建立一个到 66.147.238.215 上端口 80 的 TCP 连接。

4) 接着浏览器发送对文件 getting -started/index. Html的请求。

5) www.acm.org服务器发送文件getting-started/index . html。

6)浏览器显示getting-started/index. Html 文件中的所有内容。

7) 同时,浏览器获取并显示页面中的所有图像。

8) 释放 TCP 连接。

大体上,这就是 Web 的基础以及它是如何工作的。许多其他的功能已经添加在了上述基本 Web 功能之上了,包括样式表、可以在运行中生成的动态网页、带有可在客户机上执行的小程序或脚本的页面等,不过对它们的讨论超出了本书的范围。

基于文件系统的中间件

分布式系统采用一个文件系统模型意味着只存在一个全局文件系统,全世界的用户都能够读写他们各自具有授权的文件。通过一个进程将数据写入文件而另一个进程把数据读出的办法可以实现通信。由此产生了标准文件系统中的许多问题,但是也有一些与分布性相关的新问题。

1、传输模式

第一个问题是,在上传/下载模式(upload/ download model)和远程访问模式之间的选择问题。

2、目录层次

3、命名透明性

这里把前面讨论过的内容加以简要的总结,在分布式系统中处理文件和目录命名的方式通常有以下三种:

1) 机器+路径名,如/ machine/path 或 machine: path。

2) 将远程文件系统安装在本地文件层次中。

3) 在所有的机器上看来都相同的单一名字空间。

前两种方式很容易实现,特别是作为将原本不是为分布式应用而设计的已有系统连接起来的方式时是这样。而第三种方式的实现则是困难的,并且需要仔细的设计,但是它能够减轻了程序员和用户的负担。

4、文件共享的语义

当两个或多个用户共享同一个文件时,为了避免出现问题有必要精确地定义读和写的语义。在单处理器系统中,通常,语义是如下表述的,在一个 read 系统调用跟随一个 write 系统调用时,则 read 返回刚才写入的值,如图 8-35 a 所示。类似地,当两个 write 连续出现,后跟随一个 read 时,则读出的值是后一个写操作所存入的值。实际上,系统强制所有的系统调用有序,并且所有的处理器都看到同样的顺序。我们将这种模型称为顺序一致性(sequential consistency)。

在分布式系统中,只要只有一个文件服务器而且客户机不缓存文件,那么顺序一致性是很容易实现的。所有的 read 和 write 直接发送到这个文件服务器上,而该服务器严格地按顺序执行它们。

基于对象的中间件

基于协作的中间件

1、Linda

当两个或多个用户共享同一个文件时,为了避免出现问题有必要精确地定义读和写的语义。在单处理器系统中,通常,语义是如下表述的,在一个 read 系统调用跟随一个 write 系统调用时,则 read 返回刚才写入的值,如图 8-35 a 所示。类似地,当两个 write 连续出现,后跟随一个 read 时,则读出的值是后一个写操作所存入的值。实际上,系统强制所有的系统调用有序,并且所有的处理器都看到同样的顺序。我们将这种模型称为顺序一致性(sequential consistency)。

在分布式系统中,只要只有一个文件服务器而且客户机不缓存文件,那么顺序一致性是很容易实现的。所有的 read 和 write 直接发送到这个文件服务器上,而该服务器严格地按顺序执行它们。

2、发布/订阅

由于受到 Lindal的启发,出现了基于协作的模型的一个例子,称作发布/订阅(Oki等人,1993)。它由大量通过广播网网络互联的进程组成。毎个进程可以是一个信息生产者、信息消费者或两者都是

当一个信息生产者有了一条新的信息(例如,一个新的股票价格)后,它就把该信息作为一个元组在网络上广播。这种行为称为发布(publishing)。在每个元组中有一个分层的主题行,其中有多个用圆点(英文句号)分隔的域。对特定信息感兴趣的进程可以订阅(subscribe)特定的专题,这包括在主题行中使用通配符。在同一台机器上,只要通知一个元组守护进程就可以完成订阅工作,该守护进程监测已出版的元组并査找所需要的专题。

有关多处理机系统的研究

操作系统领域的其他方面研究很少像多核、多处理器和分布式系统那样流行。这个领域除了解决如何将操作系统的功能在多个处理核心上运行这个最直接的问题外,还涉及同步、一致性保证以及如何使系统变得更快更可靠这样一系列操作系统的研究问题。

一些研究致力于重新设计一个专门针对多核硬件的操作系统。例如 Corey 操作系统解决了由于多核之间共享数据结构所带来的性能问题(Boyd- Wickner 等人,2008)。通过仔细设计内核数据结构来消除数据间的共享,这样许多相关的瓶颈问题就消失了。与之类似的针对核数目快速增长和硬件多样化问题的新型操作系统还有 Barrelfish (Baumann 等人,2009),它在分布式系统中使用的通信模型是消息传播模型而不是共享内存模型。此外还有一些操作系统关注可扩展性和性能。Fos (Wentzlaff 等人,2010) 是一个针对可扩展性所设计的操作系统,它可以从很小的规模(多核 CPU)扩展到很大的规模(云)。此外,Newtos (Hruby 等人,2012、2013) 是一个致力于可靠性(通过模块化的设计和许多基于 Minix 3 的组件)和性能(通常是模块化多服务器系统的弱点)的多服务器操作系统。

针对多核的研究工作中也不全是重新设计的系统。Boyd- Wickizer 等人(2010) 在尝试研究和消除将 Linux 扩展到 48 核机器时遇到的瓶颈。在此过程中他们发现这一类系统如果仔细设计,也可以达到很好的可扩展性。Clements 等人(2013) 研究了决定一个 API 是否被设计为可扩展的一些基本准则。结果表明无论接口操作何时进行通信,都存在着一个可扩展的实现方法。有了以上的知识,操作系统的设计者可以实现更具扩展性的操作系统。

近些年来很多系统方面的研究关注如何使大型应用可以在多核和多处理器的环境下进行扩展。其中的一个例子是 Salomie 等人(2011) 介绍了一种可扩展的数据库引擎。同样,他们的解决方案也是通过复制数据库而不是隐藏硬件并行特性的方法来达到可扩展性。

调试并行应用是一件困难的事情,并且一些竞争条件很难重现。Viennots 等人(2013) 提出了一种通过回访的机制来调试多核系统软件的方法。Kasikcie 等人(2012) 提出了一种不仅能检测竞争条件而且还能分辨竟争条件好坏的工具。

最后还有很多降低多处理器系统功耗的工作。Chen 等人(2013) 提出了利用电量容器来提供细粒度电量和功耗管理的方法。

小结

采用多个 CPU 可以把计算机系统建造得更快更可靠。CPU 的四种组织形式是多处理器、多计算机、虚拟机和分布式系统。其中的每一种都有其自己的特性和问题。

一个多处理器包括两个或多个 CPU,它们共享一个公共的 RAM,通常这些 CPU 本身由多核组成,这些核和 CPU 可以通过总线、交叉开关或一个多级交换网络互连起来。各种操作系统的配置都是可能的,包括给每个 CPU 配一个各自的操作系统、配置一个主操作系统而其他是从属的操作系统或者是一个对称多处理器,在每个 CPU上都可运行的操作系统的一个副本。在后一种情形下,需要用锁提供同步。当没有可用的锁时,一个 CPU 会空转或者进行上下文切换。各种调度算法都是可能的,包括分时、空间分割以及群调度。

多计算机也有两个或更多的 CPU,但是这些 CPU 有自己的私有存储器。它们没有任何公共的 RAM,所以全部的通信通过消息传递完成。在有些情形下,网络接口板有自己的 CPU,此时在主 CPU 和接口板上的 CPU 之间的通信必须仔细地组织,以避免竞争条件的出现。在多计算机中的用户级通信常常使用远程过程调用,但也可以使用分布式共享存储器。这里进程的负载平衡是一个问题,有多种算法用以解决该问题,包括发送者一驱动算法、接收者一驱动算法以及竞标算法等。

分布式系统是一个松散耦合的系统,其中每个节点是一台完整的计算机,配有全部的外部设备以及自己的操作系统。这些系统常常分布在较大的地理区域内。在操作系统上通常设计有中间件,从而提供一个统一的层次以方便与应用程序的交互。中间件的类型包括基于文档、基于文件、基于对象以及基于协调的中间件。有关的一些例子有 World Wide Web、CORBA 以及 Linda。

说点什么

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
提醒