存档

文章标签 ‘存储一致性’

程序的正确性的一些理解–再谈一致性协议

2011年8月27日 sigma 没有评论 4,786 views

这几天,看论文,有个东西一直困惑我。那就是,如何判断程序是正确的,又如何判断程序的执行是正确的。下面谈谈我个人很直白,很初级的理解

个人以为,简单直白讲,程序正确,就是程序能做程序员预期希望做的事;程序执行正确,就是程序能够在一定输入下,输出程序员(设计者)所希望的输出。

个人以为,对于冯诺依曼机器,程序的输入包括:

整个程序空间的内存初始值以及任何改变程序空间内存的事件。

    对串行程序,上面的输入很好理解,其实就是内存初始值,以及各种外部改变内存的IO事件。一句话,串行程序的输入,其实就是内存输入(包括初始值以及外部改变的值)。并且,前述的输入可以确定地决定程序的输出。
    对串行程序,正确的程序,个人以为,就是能够处理程序员所定义的所有输入并得到期望的输出;程序的正确执行,也就是计算机能够将正确的程序得到期望的输出。其实,这里的正确,是基于程序员和计算机的一种协定,即计算机的指令集及每条指令的功能;正确的程序强调的是,程序元能用这套指令集实现所期望的功能;正确的执行,强调的是,计算机能够按指令定义及规范正确的执行每一条指令。
    而对于并行程序,理论上输入也只有这些,但是,现代的并行机器(多核,多处理机),由于同一份内存有多个备份,这时候,程序内部的内存改变,也是影响程序最终的输出。因为,不同备份的内存会出现不一致的情况,而消除不一致的值传播却不是瞬间的,甚至不是固定时间的。也就是说,不同备份内存值改变(包括因为其他备份传播导致的值更新)的时间也能成为一个伪输入,影响最终的结果。
    这时候,程序员和计算机,除了指令集约定,就需要新的约定,那就是一致性约定。对于计算机(或者对于计算机设计者)来说,希望这个值传播能够随意传播,时间没有限制,顺序也没有限制,因为,这样可以乱序执行,可以不用等待,可以提高计算机性能。而对于程序员,希望这个值传播是瞬间的,每个线程,只需要一改写内存,其他的内存备份,马上得到更新。

程序员所希望的一致性协议,叫做严格一致性,但是,这是这从物理上都是不可实现的,计算机肯定更无法实现。而计算机希望的一致性,则是不靠谱的,因为,那种情况下,程序员无法写出具有确定性输出的程序,因为很可能,在程序执行完毕后,同一地址对应不同的内存备份不一样,这时候,到底取哪个值,是一个问题。对于这种计算机来说,并行程序已经无所谓正确与否了。

阅读全文…

存储一致性总结

2011年5月6日 sigma 4 条评论 63,906 views

严格一致性其实从物理定律上来说就是不能实现的(它要求写操作能够瞬间传播出去)。

顺序一致性是可行的,在编程人员中很流行且广泛应用。但是它的性能很差。解决这个问题的方法是放宽一致性的模型。下表以限制程度递减的顺序给出了几种可能的模型。

一致性 说明
严格 所有的共享访问事件都有绝对时间顺序
顺序 所有进程都以相同的顺序检测到所有的共享访问事件
因果 所有进程都以相同的顺序检测到所有因果联系的事件
处理器 PRAM一致性+存储相关性
PRAM 所有的进程按照预定的顺序检测到来自一个处理器的写操作,来自其他处理器的写操作不必以相同的顺序出现

另一措施是引入了明确的同步变量,正如弱一致性释放一致性入口一致性所做的那样。下表总结了这三种模式。当进程对普通共享数据变量执行操作时,不能保证它们何时对于其他进程是可见的。只有当访问同步变量后,变化才能传播出去。

一致性 说明
同步完成后,共享数据才可能保持一致
释放 当离开临界区时,共享数据就保持一致
入口 当进入临界区时,和该临界区相关的共享数据保持一致

这三种模型的不同在于其同步机制如何工作。但在这三种情况中,它们都可在一个临界区中执行多重的读写操作,而不引起数据传输。当临界区的操作完成后,最后结果或者广播发送给其他进程或准备就绪在其他进程需要时再发送出去。

存储一致性之入口一致性(Entry Consistency)

2011年5月6日 sigma 没有评论 25,759 views

另一种使用临界区的一致模型是入口一致性(Bershad等,1993)。和释放一致性的两个变体一样,它也需要编程人员或编译器在临界区的首尾分别使用获取和释放操作。然而,与释放一致性不同的是,入口一致性要求每个普通的共享数据都要与某种同步变量如锁(lock)或屏障(barrier)相关联。

若并行访问数组元素,不同的数组元素就需要与不同的锁相联系。在对一个同步变量执行获取操作时,只保证与这个同步变量有关的共享数据一致。入口一致性与懒惰释放一致性不同在于,后者没有将共享数据与锁或屏障相连系,做获取操作时必须凭经验确认它需要哪些变量。

将每个同步变量与一组共享变量相连,可减少获取访问和释放访问一个同步变量时的开销,因为只有极少数共享变量需同步。它还允许包含不相关共享变量的多个临界区同时执行同步,增加了并行度。代价是将每个共享数据变量与同步变量相联系,这要求额外的开销,且增加了复杂度。这样编程更为复杂且更易于出错。

其定义为:

a memory exhibits entry consistency if it meets all the following conditions :

  1. An acquire access of a synchronization variable is not allowed to perform with respect to a process until all updates to the guarded shared data have been performed with respect to that process.
  2. Before an exclusive mode access to a synchronization variable by a process is allowed to perform with respect to that process, no other process may hold the synchronization variable, not even in nonexclusive mode.
  3. After an exclusive mode access to a synchronization variable has been performed, any other process next nonexclusive mode access to that synchronization variable may not be performed until it has performed with respect to that variable’s owner.

中译为:

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

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

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

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

第一个条件说明,当进程执行获取访问时,该操作在所有保护的共享变量均更新后才能结束(即将控制权交给下一条语句)。也就是说,在获取操作时,所有被保护数据的远程修改都必须是可见的。

第二个条件说明,在更新一个共享变量前,进程必须以互斥方式进入临界区,以确定没有其他进程同时更新它。

第三个条件说明,若进程试图以非互斥方式进入临界区,它必须与保护此临界区的同步变量的拥有者核查,以获得被保护共享变量的最新拷贝。

最后,附一张入口一致性的示意图:

存储一致性之释放一致性(Release Consistency)

2011年5月6日 sigma 1 条评论 26,768 views

倘若在弱一致性中,存储器能够区分进入还是离开临界区的话,应用起来会更有效。鉴于此,我们需要两种类型而非一个同步变量或操作。

释放一致性(Gharachorloo等,1990)提供了这样两种操作:

•获取(acquire)操作是用于通知数据存储进程进入临界区的操作。

•释放(release)操作是表明进程刚退出临界区。

释放一致性本质上和弱一致性相同,但是同步访问必须仅是处理机一致的。同步操作被分裂成获得(acquire)和释放(release)操作。

共享存储器在遵守以下规定时就是释放一致的:

  1. 在访问共享变量前,进程所有先前的获取操作都必须成功地完成;
  2. 在允许释放操作前,进程先前的所有读写操作都必须完成;
  3. 获取操作和释放操作必须是顺序一致的(这是胡老师《共享存储体系结构》一书的讲法,夏老师课件里讲的是顺序一致,具体哪种有待考证)。

存储器和软件的协议说明,当软件执行获取操作时,存储器会根据需要确保被保护数据的所有本地拷贝被更新为最新数据,并和远程数据拷贝保持一致。当执行释放操作时,修改的被保护变量要传送到其他机器上。执行获取操作并不能保证本地所作的修改会立即传送到其他本地拷贝。类似地,执行释放操作也不会必然地从其它拷贝引入所做的改变。

上图是释放一致性下的一个有效事件顺序。进程P1执行获取操作,两次改变共享变量x的值,然后执行释放操作。进程P2执行获取操作,并读取x。它应在释放操作时得到x的值为b(除非P2的获取操作先于P1的获取操作)。若P2的获取操作在P1的释放操作之前,则它必须等待到P1执行了释放操作。因为P3在读共享变量前没有执行获取操作,存储器不必给它x的当前值,因此返回a是允许的。

释放一致性分为渴望释放一致和懒惰释放一致性:

渴望释放一致性在执行释放操作后,执行此操作的处理机将所有修改的数据传给所有那些已经有其缓冲拷贝且可能需要它的处理机。因为没有办法判断它们是否确实需要它,为安全起见,它们将获得所有修改过的数据。尽管这样将所有数据传输出去的方法很直接,但通常不够有效。

在懒惰释放一致性中,在执行释放时,不发送任何数据。相反,在执行获取操作时,处理机试图从拥有这些变量的机器上取得它们的最新值。时间戳协议可用来确定需传送哪些变量。

存储一致性之弱一致性(Weak Consistency)

2011年5月6日 sigma 1 条评论 27,904 views

弱一致性WC(Week Consistency)模型的提出,是人们观察到大多数并行程序排定几个进程对数据存取次序时都需要使用同步操作;而在同步操作之间,一个进程所进行的数据存取操作次序对其他进程会是不可见的。例如,某进程对同步变量实施加锁后进入临界段,已在临界段内所做的存储器数据读写操作,由于互斥性其他进程根本看不到,更不用说读写操作次序了。

只是在此进程解锁退出临界段,其对共享变量所做的修改结果应立即被其他进程所看到,基于上述观察,我们可放宽对非同步读写操作次序的限制而只对同步存储器操作施加顺序一致性,来解决存储器一致性问题。

Dubois等(1986)定义这种使用同步变量来部分地定义的一致性模型为弱一致性:

weak consistency, by saying that it has three properties:

  1. Accesses to synchronization variables are sequentially consistent.
  2. No access to a synchronization variable is allowed to be performed until all previous writes have completed everywhere.
  3. No data access ( read or write ) is allowed to be performed until all previous accesses to synchronization variables have been performed.

中译为:

弱一致性,它有三个属性:

a. 对同步变量的访问是顺序一致的;

b. 在所有先前的写操作完成之前,不能访问同步变量;

c. 在先前所有同步变量的访问完成前,不能访问(读或写)数据。

弱一致性要求同步访问(访问要求执行同步操作)是顺序一致的。在一个同步访问可以被执行之前,所有以前正常的数据访问必须完成。在一个正常的数据访问可以被执行之前,所有以前同步访问必须完成。这实质上把一致性问题留给程序员决定。在一个同步操作之后,内存将立即是一致的。

第一点指出所有过程以相同顺序看到对同步变量进行的所有操作。即,如果进程P1调用synchronize(S1),与此同时进程P2调用synchronize(S2),那么,实际效果好象是synchronize(S1)发生在synchronize(S2) 之前,或synchronize(S2)发生在synchronize(S1) 之前,但所有进程看到同样的顺序。实际上,一个同步变量的访问将立即被广播出去。在广播发送结束之前,任意其他进程不能访问其他同步变量。

第二点指出访问同步变量“刷新了管道”,它强迫在所有拷贝上完成所有程序中的写操作。其中包括正在执行的、部分完成的或已经在某些本地拷贝上完成却未在其它拷贝上完成的写操作。同步访问开始前,应保证先前所有的写操作已完成。在更新共享数据后做同步操作,进程可迫使将新值传遍到该存储的所有其它本地拷贝。

第三点指出访问一般(即非同步)变量,不管是读是写,只有在所有前序的同步操作结束后方可进行。在读共享数据前做同步操作,可以保证进程读到最新值。

从应用的角度来说,软件和存储器的协议指出,只有当访问同步变量时,存储器才需更新;新的写操作可以在前一写操作完成之前开始,在一些情况下可完全避免写。当然,此协议加重了编程人员的负担,但换来了优越的性能。

不同于以往的存储器模型,它是对一组操作的一致性约束,而不是单独的读或写。当很少单独而基本上以簇的形式(短时间内有很多访问,每一访问时间都不长)访问共亨变量时,这个模型更为有用。

弱一致性存在这样的问题,即当访问同步变量时,存储器并不知道这是因为进程已完成对共享数据的写操作还是要开始读共享数据。因此,它必须执行这两种情况要求的操作,也就是它要确保本地启动的写操作都已完成(即发送到其他所有的拷贝),同时还要收集其他机器执行的写操作。

弱一致性的示意图如下:

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