存档

文章标签 ‘存储一致性’

存储一致性之处理机一致性(Processor consistency)和PRAM一致性(PRAM consistency)

2011年5月6日 751 条评论 68,066 views

Goodman于1989年提出处理机一致性(processor consistency)。

处理机一致性的定义是:

由一个处理机发出的写以他们所发出的同样次序被观察到。但是,从两个进程写的次序出现作为由它们自身或第三个处理机所观察到的次序不一定相同。即从不同的处理机的同时对同样的位置的两个读可以产生不同的结果。

顺序一致性相比,只需要同一个处理器的写操作或者不同处理器对同一地址的写操作在所有的处理器看到的顺序是一致的即可以(顺序一致性要求读写都一样)。

PRAM (Pipelined RAM)意为管道式或流水线式存储器,因为一个进程的写能被管道化,故进程不需要等待每次写的完成就可启动下一个操作。

Lipton和Sandberg (1988)给PRAM一致性存储器模型下了如下定义:

Writes done by a single process are received by all other processes in the order in which they were issued, but writes from different processes may be seen in a different order by different processes.

中译为:

单一进程完成的写操作被所有进程以这些操作发出的次序所接纳,但不同进程的写操作可被不同的进程以不同的次序所看到。

PRAM一致性和处理器一致性如此接近,以至于有的作者认为他们实际是一样的(如,Attiya和Friedman,1992;以及Bitar,1990)。Goodman通过一个例子证明在处理器一致的存储器还有一个附加条件,即存储相关性。PRAM一致性,对于任意存储器地址x,对于写入x的顺序有个全局约定。写入不同地址(即使是同一进程写),对于不同进程来看,不需要相同顺序。

PRAM一致和因果一致的对比如下图所示。这里的时间顺序在PRAM一致的存储器中是允许的,而在其他更强的模式下都不允许。

处理器一致性(以及PRAM一致性)的优点是允许硬件隐藏写操作的延迟。当写的内容还在写缓冲区并没有被其他处理器看见时,此处理器可发出并完成对它的读操作。允许在一个处理器内读操作可跨过前面的还在缓冲的写操作先于完成,会给处理器以及整个系统的性能改善带来实质性的支持。

处理器一致性(以及PRAM一致性)的优点是允许硬件隐藏写操作的延迟。当写的内容还在写缓冲区并没有被其他处理器看见时,此处理器可发出并完成对它的读操作。允许在一个处理器内读操作可跨过前面的还在缓冲的写操作先于完成,会给处理器以及整个系统的性能改善带来实质性的支持。

PRAM一致由于易于应用而得到关注。事实上它不保证不同进程看到的写操作顺序是一致的,除非是同一个源的一个或多个写操作,才必须按次序到达,就好像在管道中。换而言之,在这种模式中,由不同进程产生的写操作是并发的。这种模型可以通过如下方法实现:简单地使用(进程,序列号)对偶作为每个操作的标签,并根据序列号执行每个进程的写操作。

存储一致性之一般一致性(General Consistency)和因果一致性(Causal Consistency)

2011年5月6日 651 条评论 88,209 views

相比于严格一致性顺序一致性虽然放松了限制条件,但是对性能的影响还是很大,因此出现了一般一致性和因果一致性。 一般一致性的定义是:

一个系统支持一般一致性,当每个处理机所执行的所有写已被完成时,如果一个内存位置的所有副本最终地包含同样的数据。

  因果一致模型(Hutto和Ahamad,1990)是顺序一致的淡化,它按有无可能的潜在因果联系来区分各事件。 假设进程P1写变量x,然后P2读出x,写入y。这里读出x和写入y之间可能有潜在的因果联系,因为y的计算很可能决定于P2读到的x值(即P1写入的值)。 另一方面,若两进程自然而同时地写两个变量,就没有因果联系。先有读操作之后执行写操作,两个事件就可能有因果联系。相似的,读和提供所读数据的写有因果关系。没有因果关系的操作称为并发的(concurrent)。 因果一致性定义:

A system provides causal consistency if memory operations that potentially are causally related are seen by every node of the system in the same order. Concurrent writes (i.e. ones that are not causally related) may be seen in different order by different nodes.

中译为:

因果一致的存储器应遵守以下条件:可能因果相关的写操作应对所有进程可见,且顺序一致。并发写操作在不同机器看来顺序可能是不同的。

在下图(a)中,W(x)b可能决定于W(x)a,因为 b可能是R(x)a所读的值计算的结果,两个写操作是因果联系的,所有进程必须视它们为同一顺序。因此(a)不正确。(b)中,读被取掉,W(x)a和W(x)b变为并发事件。因果一致性存储器不要求并发写有全局一致的次序,因此(b)是正确的。   实现因果一致性需要由记录来跟踪哪个进程看到哪个写操作。这要建立和维护一个依赖图:即一个操作依赖于其他什么操作。一种实现方法是使用向量时间戳。这样做需要一些额外的开销。

存储一致性之顺序一致性(Sequential consistency)

2011年5月6日 727 条评论 30,523 views

定义(Lamport ,1979):

the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program

中译为:

任意一次执行的结果都像所有处理器的操作以某种顺序的次序执行所得到的一样,而且各处理器的操作都按照各自程序所指定的次序出现在这个顺序中。

这个定义意味着,当程序在各个机器上并行运行时,任何一种有效的交错存储器访问顺序都是可认可的行为,但所有处理器必须看见的是同样的访问顺序。如果一个进程(处理器)看见的是一种交错,另一进程看见的是另一种交错,则这样的存储器不是一个顺序一致性的存储器。然而,同一程序再次并行运行,其存储器访问的交错次序会不同于上次的交错次序,这是允许的。在一块存储器中,若一个进程(或处理机)看到一种交错,另一进程看到另一个交错,这就不是顺序一致存储器。注意,这与时间无关,没有最近存入的概念。在这里,进程可以看到所有进程写,但只能看到本进程读。

在顺序一致性中衍生了一个可线性化概念:

线性化是一种弱于严格一致性但又强于顺序一致性的一致性模型。这种模型假设操作具有一个全局的时间戳。设TSop(x)表示在x上的操作op执行时的时间戳, op可以是读操作,也可以是写操作。如果TSop1(x)< TSop2(y),则在顺序一致性模型中的读/写操作顺序下,操作op1(x)必须在操作op2(y)之前。

线性化的数据存储也是顺序一致的。它们的区别在于:线性化是根据时间戳确定操作顺序的。在实际应用中,线性化主要用于并发算法的形式验证。线性化的实现比顺序一致性的实现开销更大。

最后,给一张顺序一致性的示意图:

存储一致性之严格一致性(Strict Consistency)

2011年5月6日 387 条评论 72,391 views

定义:

Any read to a memory location X returns the value stored by the most recent write operation to X.

中译为(看起来真简洁,不得不感慨下汉语的简洁性,不过和简洁相伴的往往是不准确性):

从存储器地址X处读出的值为最近写入X的值。

严格一致性要求具有决定最近写的能力,因此它蕴涵请求的全序。

传统意义上,单处理机遵守严格一致性,单处理机的编程者正希望这样。但是在分布式计算机系统中为每个与准确的全局时间对应的操作分配惟一的时间戳是不可能的。

可以放宽条件,将时间分割成一系列连续的、不重叠的时间间隔。假设每个操作发生在一个时间间隔内,并获得与那个时间间隔对应的时间戳。

但是无法保证每个时间间隔内最多只发生一个单一操作。因此,仍需要处理在同一时间间隔内所发生的多个操作。如果同一时间间隔内的两个操作是对相同数据进行操作,并且其中一个操作是写操作,那么称这两个操作是冲突的。

另一方面,编程人员却希望能够满足严格一致性。如果不支持严格一致性,程序发生问题就很难说是那方面的问题。定义一致性模型的一个重要问题就是准确定义出现冲突时,哪些行为是可接受的。

如果一个进程的两个事件发生如此之快,以致其他进程不能在此之间执行任何操作,那可能会带来麻烦。相反,通常的编程方式是:语句执行的确切时间(实际上是存储器访问)并不重要,而当事件(读或写)的顺序是至关重要时,可以使用信号量等方法实现同步操作。接受这种意见意味着采用较弱的一致性模式来编程。经过几次实践,大多数并行程序编写人员都能适应这种模式。因此,程序设计者使用较弱的一致性模式同样可以使存储器正常工作。这些工作将在后面几篇文章介绍。

总之,对于严格一致性的存储器,写操作在任一时刻对所有进程都是可见的,同时维护一个绝对全局时间顺序。一旦存储器中的值改变,不管读写之间的事件间隔多小,不管哪个进程执行读操作,也不管进程在何处,以后读出的都是新更改的值。同样,如果执行了读操作,不管后面的写操作有多迅速,该读操作仍应读出原来的值。

严格一致性的示意图:

共享存储和存储一致性概述

2011年5月6日 759 条评论 15,936 views

之前那篇关于并行加速的文章里讲到,有空会把各种存储一致性介绍下,趁着今天刚考完分布式操作系统,做各种存储一致性有点点了解,就趁热打铁,把各种一致性写下来,作为备忘。

需要强调的是,即将写关于存储一致性的几篇文章,大量的参考了夏道藏老师的《分布式操作系统》分布式共享内存一章的课件以及胡伟武老师的《共享存储系统结构》一书。

在本文中,主要概述下一致性,并且对各种一致性进行简要介绍,后面的几篇文章会稍微详细介绍下:

和消息传递相比,共享存储体系结构编程模型简单,程序访问在共享地址空间中的数据正如同访问在传统的虚存中的数据一样,不用考虑数据具体所在的位置。但共享存储有个问题就是可扩展性差,规模不能做的很大,因此,现在的机群基本都不采用这种结构,不过研究这个结构对于并行理论还是很有帮助的。

由于事实上共享存储系统里面存储的各部分是分布到各处的,访存还是需要通过低层的通讯(消息传递)完成的。最严重的是,由于数据在多处具有备份,导致数据在不同的备份会出现不一致的情况,存储一致性就是为了解决这个问题。

为了改善性能,共享存储系统依赖复制共享数据项(多个备份)和允许在许多结点上并发访问。但是,如果并发访问不仔细地加以控制,内存访问可能以不同于程序员所期望的次序被执行。非正式讲,一个内存是一致的,如果由读操作返回的值总归是程序员所期望的值。

一致性模型实质上是软件和存储器间的契约(Adve和Hill,1990),它是说,如果软件同意服从某模型给出的规则,则存储器允诺软件在这种模型下正确地工作;否则,存储器操作的正确性将得不到保证。

具体的常见的一致性协议主要有(本文只讲定义,后面的文章会具体分别介绍):

严格一致性(strict  consistency)

一个读返回最近写的值。严格一致性要求具有决定最近写的能力,依次它蕴涵请求的全序。

顺序的一致性(Sequential consistency)

如果所有进程以一定的顺序执行操作;每一进程的操作都以程序规定的顺序出现,则任何操作的结果都是一样的。

因果一致性(Causal Consistency)

可能因果相关的写操作应对所有进程可见,且顺序一致。并发写操作在不同机器看来顺序可能是不同的。

一般一致性(General Consistency)

一个系统支持一般一致性,当每个处理机所执行的所有写已被完成时,如果一个内存
位置的所有副本最终地包含同样的数据。

处理机一致性(Processor consistency)

由一个处理机发出的写以他们所发出的同样次序被观察到。但是,从两个进程写的次序出现作为由它们自身或第三个处理机所观察到的次序不一定相同。即从不同的处理机的同时对同样的位置的两个读可以产生不同的结果。

PRAM一致性(PRAM consistency,又名FIFO consistency)

一个过程的写操作可以被其他进程以指定的顺序接收到,但不同进程的写操作在不同进程看来次序可以是不同的。

以下几种一致性协议主要是针对增加了同步操作后的共享存储系统而言的。

弱一致性(Weak consistency)

同步访问(访问要求执行同步操作)是顺序一致的。在一个同步访问可以被执行之前,所有以前正常的数据访问必须完成。在一个正常的数据访问可以被执行之前,所有以前同步访问必须完成。

释放一致性(Release consistency)

共享存储在遵守以下规则时就是释放一致的:
a. 在访问共享变量前,进程所有先前的获取操作都必须成功地完成;
b. 在允许释放操作前,进程先前的所有读写操作都必须完成;
c. 获取操作和释放操作必须是FIFO一致的(此处有疑问,因为胡老师一书中说是顺序一致性,而夏老师课件中则是FIFO一致性)。

入口一致性(Entry Consistency)

当存储器满足下列所有条件时,就成为入口一致性存储器(Bershad和 Zekauskas,1991):

a. 只有某一进程的保护共享变量全部被更新以后,该进程方允许执行同步变量的获取访问;

b. 在一进程以互斥模式访问该进程的同步变量之前,不允许其他进程持有此同步变量,即使在非互斥模式下;

c. 在结束互斥模式下对一个同步变量的访问后,任意其他进程必须与该变量的拥有者核查,才能试图以非互斥模式访问该同步变量。

无觅相关文章插件,快速提升流量