分布式操作系统中的共享存储器.ppt

多处理机系统的共享存储,2019/7/14,2,多处理机系统的概念 多处理机的分类 集中式共享存储器结构 分布式共享存储器结构,2019/7/14,3,使用多个处理机组成一个并行计算机(parallel computer)是提高系统性能的有效方法。一个并行计算机是多个处理部件(processing element)的集合，所有的处理部件通过相互通信，协同解决复杂的问题。处理部件之间由互联网络连接，这种并行的优点是可以利用现有的高性能处理机，加上快速互联网络构成高性能并行系统。 多个处理机及存储器模块构成的并行处理机被称为多处理机系统(multiprocessor system)，简称多处理机。处理机之间的通信通过共享存储器(shared memory)进行。,2019/7/14,4,多处理机系统概念,广义上说，使用多台计算机协同工作来完成所要求的任务的计算机系统都是多处理机系统。 传统的狭义多处理机系统的作用是利用系统内的多个CPU来并行执行用户的几个程序，以提高系统的吞吐量或用来进行冗余操作以提高系统的可靠性。多个处理机(器)在物理位置上处于同一机壳中，有一个单一的系统物理地址空间和每一个处理机均可访问系统内的所有存储器是它的特点。,2019/7/14,5,多处理机的分类,一个多处理机有一个可以被所有处理机访问的存储系统（实现享）。存储器系统由一个或多个存储器模块组成，所有的存储器模块使用一个统一编址的地址空间。处理机可以用不同的地址访问不同的存储器模块。 根据系统中处理器个数的多少，可把现有的MIMD（多指令多数据流，实现作业,任务,指令等各级全面并行）计算机分为两类，每一类代表了一种存储器的结构个互联策略 。由于多处理机的规模大小这个概念的含义是随时间的变化的，所以我们用存储结构来区分这些机器。 第一类：集中式共享存储器结构 第二类：分布式共享存储器结构,2019/7/14,6,集中式共享存储器(Centralized Shared-memory Architecture),这类多处理机在目前至多有几十个处理器。由于处理器数目较小，可通过大容量的Cache和总线互连使各处理器共享一个单独的集中式存储器。因为只有一个单独的主存，而且从各处理器访问该存储器的时间是相同的，所以这类机器有时被称为UMA(Uniform Memory Access)机器。这类集中式共享存储器结构是目前最流行的结构。图1为此类机器结构的示意图。 图中多个处理器-Cache子系统共享同一个物理存储器，其连接一般采用一条或多条总线。,2019/7/14,7,图1 基于总线带缓存的多处理器,总线,2019/7/14,8,这种体系结构支持对共享数据和私有数据的Cache缓存。私有数据供一个单独的处理器使用，而共享数据供多个处理器使用。共享数据主要是用来供处理器之间通过读写它们进行通信。私有数据缓冲在Cache中降低了平均访存时间和对存储器带宽的要求，使程序的行为类似于单机。共享数据可能会在多个Cache中被复制，这样做除了可降低访存时间和对存储器带宽的要求外，还可减少多个处理器同时读共享数据所产生的冲突。但共享数据进入Cache也产生了一个新的问题，即Cache的一致性问题。,2019/7/14,9,多处理机的一致性（Coherence）,对于在多处理机上的数据共享，不同处理器的Cache都保存有对应存储器单元的内容，因而在操作中就可能产生数据的不一致。表1通过两个处理器Cache对应同一存储器单元产生出不同的值的例子说明了这个问题，这通常称为Cache一致性问题。,2019/7/14,10,由两个处理器(A和B)读写引起的Cache一致性问题,0时间：X单元数据为 1 1时间：CPU A 将X中数据1读入Cache 2时间：CPU B 将X中数据1读入Cache 3时间：CPU A将0写入X中。 此时Cache A与X中数据一致为0，与Cache B 不一致,2019/7/14,11,存储器一致性满足条件,若一个存储器满足以下三点，则称该存储器是一致的。 (1) 处理器P对X进行一次写之后又对X进行读，读和写之间没有其它处理器对X进行写，则读的返回值总是写进的值。 (2) 一个处理器对X进行写之后，另一处理器对X进行读，读和写之间无其它写，则读X的返回值应为写进的值。 (3) 对同一单元的写是顺序化的，即任意两个处理器对同一单元的两次写，从所有处理器看来顺序都应是相同的。例如，对同一地址先写1，再写2，任何处理器均不会先读到2，然后又读到1。,2019/7/14,12,注释,第一条属性保持了程序的顺序，即使在单机中我们也要求如此。 第二条属性给出了存储器一致性的概念。如果一个处理器不断读取旧的数据，则可以肯定认为这个存储器是不一致的。 第三条属性要求写操作的顺序化要求更严格。处理器P1对X单元进行一次写，接着处理器P2对X也进行一次写，如果不保证写操作顺序化，就可能出现这种情况：某个处理器先看到P2写的值而后看到P1写的值。解决这个问题最简单的方法就是写操作顺序化，使同一地址所有写的顺序对任何处理器看来是相同的。这种属性称为写顺序化。,2019/7/14,13,实现一致性的基本方案,在一致的多处理机中，Cache提供了共享数据的迁移和复制(Migration and Replication)功能。共享数据的迁移是把远程的共享数据项拷贝放在本处理器局部的Cache中使用，从而降低了对远程共享数据的访问延迟。共享数据的复制是把多个处理器需要同时读取的共享数据项的拷贝放在各自局部Cache中使用，复制不仅降低了访存的延迟，也减少了访问共享数据所产生的冲突。一般情况下小规模多处理机不是采用软件而是采用硬件技术实现Cache一致性。,2019/7/14,14,对多个处理器维护一致性的协议称为Cache一致性协议(Cache-coherent protocol)。实现Cache一致性协议的关键是跟踪共享数据块的状态。目前有两类协议，它们采用了不同的共享数据状态跟踪技术： (1) 目录(Directory) 物理存储器中共享数据块的状态及相关信息均被保存在一个称为目录的地方。 (2) 监听(Snooping) 每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信 息。Cache通常连在共享存储器的总线上，各个Cache控制器通过监听总线来判断它们是否 有总线上请求的数据块。 在使用多个处理器，每个Cache都与单个共享存储器相连组成的多处理机中，一般都采用监听协议，因为这种协议可利用已有的物理连接(总线到存储器)来修改Cache中的状态信息。 可用以下两种方法（协议）来维持上面所讲的一致性要求。,2019/7/14,15,两种协议,写作废（Write invalidate）协议 在一个处理器写某个数据项之前保证它对该数据项有唯一的访问权。 它是目前应用最普遍的协议。唯一的访问权保证了在进行写后不存 在其它的可读或可写的拷贝存在：别的所有的拷贝全部作废了。既 既然写要求唯一的访问权，那么其他处理器上的拷贝已作废，因此 当其他处理器再次进行读操作时，就会产生读失效，从而取 出新的数据拷贝。要保证进行写的处理器具有唯一的访问权，必须 禁止别的处理器和它同时写。如果两个处理器同时写数据，那么竞 争胜者就将另一个处理器的拷贝作废，当胜者完成写后另一个处理 器要进行写时，它必须先取一个新的数据拷贝，即已被更新的数据。 因此，这种协议保证了顺序写。,2019/7/14,16,写更新协议(write update) 当一个处理器写某数据项时，通过广播使其它Cache中所有对应的 该数据项拷贝进行更新。为减少协议所需的带宽，应知道Cache该 数据项是否为共享状态，也就是别的Cache中是否存在该数据项拷 贝。如果不是共享的，则写时无需进行广播,2019/7/14,17,分布式共享存储器,第二类机器具有分布的物理存储器。为支持较大数目的处理器，存储器必须分布到各个处理器上，而非采用集中式，否则存储器系统将不能满足处理器带宽的要求。系统中每个结点包含了处理器、存储器、I/O以及互连网络接口。随着处理器性能的迅速提高和处理器对存储器带宽要求的不断增加，甚至在中小规模的多处理机系统中，也逐渐开始采用分布式存储器结构同时，分布式存储器结构需要高带宽的互连。 图2给出了此类机器的结构。,2019/7/14,18,图2 分布式共享存储结构,2019/7/14,19,1. 如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求； 2. 对局部存储器的访问延迟低。 分布式存储器体系结构最主要的缺点是处理器之间的通信较为复杂，且各处理器之间访问延迟较大。 通常情况下，I/O和存储器一样也分布于多处理机的各结点当中。每个结点内还可能包含较小数目(28)的处理器，这些处理器之间可采用另一种技术（例如通过总线）互连形成簇(cluster)，这样形成的结点叫做超结点。采用超结点对机器的基本运行原理没有影响。由于采用分布式存储器结构的机器之间的主要差别在于通信方法和分布式存储器的逻辑结构方面，所以讨论中我们设每个结点只有一个处理器的机器。,存储器分布到各结点有两个好处：,2019/7/14,20,处理器之间的通信,大规模的多处理机必须采用多个存储器，它们在物理上分布于各个 处理结点中。在各个处理器之间通信的实现上，目前有两种可供选 择的方案。 (1) 第一种方案：物理上分离的多个存储器作为一个逻辑上共享的存储空间进行编址。这类机器的结构被称为分布式共享存储器(DSM，Distributed Shared-Memory)或可缩放共享存储器(SSM， Scalable Shared-Memory)体系结构。此处共享指的是地址空间的共享，即两个处理器相同的物理地址指向分布存储器中的同一个单元。 ( 2) 第二种方案：整个地址空间由多个独立的地址空间构成，它们在逻辑上也是独立的，远程的处理器不能对其直接寻址。在这种机器的不同处理器中，相同的物理地址指向不同存储器的不同单元，每一个处理器 - 存储器模块实际上是一个单独的计算机，因而这种机器也称为多计算机(Multicomputers)。它完全可以由多个独立的计算机通过局域网相连构成。如果应用要求的通信较少或无需通信，那么采用这种方案只需将机器连结成簇来支持应用，是一种很经济的途径。,2019/7/14,21,两种方案,对应于上述两种地址空间的组织方案，分别有相应的通信机制。 (1) 共享地址空间的机器：可利用Load和Store指令中的地址隐含地进行数据通信，因而可称为共享存储器机器。 (2) 多个地址空间的机器：数据通信要通过处理器间显式地传递消息完成，因而这种机器常称为消息传递机器（消息可以看成是一个远程进程调用 ）。 共享存储器通信主要有以下优点 (1) 与常用的集中式多处理机使用的通信机制兼容。 (2) 当处理器通信方式复杂或程序执行动态变化时易于编程，同时在简化编译器设计方面也占有优势。 (3) 当通信数据较小时，通信开销较低，带宽利用较好。 (4) 通过硬件控制的Cache减少了远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。,2019/7/14,22,分布式共享一致性,支持共享存储器的可缩放机器既可以支持也可以不支持Cache一致性。从硬件简单的角度出发，可以不支持Cache一致性，而着重于存储器系统的可缩放性上。在这类机器中，存储器分布于各结点中，所有的结点通过网络互连。访问可以是本地的，也可是远程的，由结点内的控制器根据地址决定数据是驻留在本地存储器还是在远程存储器，如果是后者，则发送消息给远程存储器的控制器来访问数据。这些系统都有Cache，为了解决一致性问题，规定共享数据不进入Cache，仅私有数据才能保存在Cache中。当然也可以通过软件显式地来控制一致性。这种机制的优点是所需的硬件支持很少，因为远程访问存取量仅是一个字(或双字)而不是一个Cache块。,2019/7/14,23,将Cache一致性共享存储器模式拓展到大规模多处理机面临着新的挑战。尽管可以用缩放性更好的网络来取代总线，将存储器分布开来，从而使存储器的带宽具有缩放性，但是监听一致性协议机制本身的可缩放性较差。所以，在支持Cache一致性的可缩放的共享存储器体系结构中，关键是寻找替代监听协议的一致性协议。一种可供选择的协议是目录协议，目录是用一种专用的存储器所记录的数据结构，它记录着可以进入Cache的每个数据块的访问状态、该块在各个处理器的共享状态以及是否修改过等信息。目前目录协议的实现是对每个存储器块分配一个目录项，目录的信息量与存储器块的数量和处理器数量的乘积成比例。对于少于100个处理器的机器这不成问题，因为由目录操作引起的延迟开销可以忍受。而对于较大规模的机器，由于目录内容较多，就需要寻找更有效的目录结构。例如只保存少量的块(比如只保存Cache中的块而非全部的存储器块)的信息或者每个目录项保存较少的状态位等。 为防止目录成为瓶颈，目录一般与存储器一起分布在系统中，从而对于不同目录内容的访问可以在不同的结点进行，正如对不同的存储器的访问一样。分布式目录中将数据块的共享状况保存在一个固定的单元中，从而使一致性协议避免了广播操作。,2019/7/14,24,基于目录的