Algorithm 版 (精华区)

发信人: sigmod (sigmod), 信区: Algorithm
标  题: 存储一致性模型
发信站: 哈工大紫丁香 (2001年11月14日12:31:03 星期三), 站内信件

所谓存储一致性模型，实际上是系统设计者与应用程序员之间的一种约定。如果应用软
件遵从一定的规则访问虚拟内存系统，则应用软件可以获得正确的存储访问结果；反之
，如果破坏了约定的规则，则存储访问的正确性不受保证。
从某种意义上来讲，存储一致性模型对共享存储系统中的多处理机的访存次序作了限制
。从而对性能有一些影响。分布式共享系统的一个根本目标就是让一个通过局域网连接
起来的工作站机群可以共享单一的虚拟地址空间，使之在工作站机群之上运行程序的效
果类似工作站机群，共享单一的虚拟地址空间，使在其上运行程序的效果等同于程序在
单机上的运行。在最简单的变体中，每页存在于一个确定的机器当中，对本地页面的查
询速度等同于对内存的访问速度，而访问远程机器的页面查询请求将引发段违例。这会
使程序陷入到操作系统，由操作系统来处理缺页中断。操作系统随之发送一个消息至远
程机器以找到所需要的页面，同时等待远程机器将该页面回送到本地。本地机器获得远
程页面以后，引发段违例的指令会被重置，继续向下执行。为了达到这一目标，需要构
造一个虚拟内存子系统，由它来捕获在DSM系统中的页面访问错误以及负责从网络上的其
他节点处取回数据并完成必要的同步操作。
在网络文件系统AFS的构建中，对文件的一致性采用了类似的处理方法，它实现了两个软
件模块Vice和Venus，以UNIX进程的形式存在，Vice作为服务器端在服务器机器上作为用
户级进程运行，Venus作为客户端，在客户端机器上运行，响应远程的文件操作请求。
在前面所叙述的DSM系统中，某一个只读页面可能在多个节点上均存在副本，而对于可写
页面，一般都由一个宿主来维护其一致性，远程访问的时候，有远程节点向宿主节点发
出访问请求并从宿主节点处取回该可写页面。通常情况下，对一个可写的页面，DSM系统
中最多只能有一个副本。当应用程序的相关性比较大的时候，这种对每一可写页面仅仅
维护一个副本的策略就会引发严重的性能瓶颈。维护多个副本的策略可以减缓性能上的
瓶颈效应，但是又会带来新的问题，即如何在多个副本之间维护数据的一致性？为了解
决这个问题，提出了一致性存储模型。
大致来说，按照一致性从强到弱的顺序，可以区别为下面几种类别。
3．1严格一致性模型
这是对一致性要求最严格的一种模型，它由下面的条件来描述：任何对内存位置X的读操
作将返回最近位置对X进行写操作的值。
在DSM系统中，这是一种理想的模型，但是受到网络延迟的影响而不可能实现。在DSM系
统中实现的多种一致性模型，都是对严格一致性模型在不同程度上的放松。而在单机环
境下，任何存储访问序列都满足严格一致性要求。
3．2顺序一致性模型
顺序一致性对存储器的限制比严格一致性要弱一些，顺序一致性的存储器要满足以下的
条件：
（1） 每个进程的内部操作顺序是确定不变的；
（2） 假如所有的CPU上的进程都对某一个存储单元执行操作，那么，它们的操作顺序是
确定的，即任一进程都可以感知到这些进程同样的操作顺序。
上述条件的含义是指，当多个进程分别在不同的机器上并发执行的时候，只要所有的进
程都保持同样的顺序访问存储器，那么，任何有效的交叉访问执行都是可以接受的。在
顺序一致性模型中，时间不再是影响一致性的因素，它关心的是：所有进程都必须能够
感受到一直的内存访问序列。
顺序一致性模型不确保进程的一次读操作可以返回由另一进程所写入的最新值。在没有
显式的同步操作的情况下，再一次运行同样的程序不能保证获得同样的结果。
3．3因果一致性模型
因果一致性模型是对顺序一致性的弱化，它要求在具有潜在因果关系（Happened - Bef
ore）的操作之间保持其一致的顺序。一般性的描述如下：有潜在性因果相关的写操作必
须以同样的顺序被各个进程所感知，而并发的写操作在不同的机器上有不同的顺序。在
基于因果顺序一致性模型的存储管理系统中合法的操作序列在顺序一致性或者严格一致
性模型中可能会成为非法操作。
3．4管道一致性模型
管道一致性模型是在因果一致性模型上的进一步弱化，它满足下面的条件：由某一个进
程完成的写操作可以被其他所有的进程按照顺序的感知到，而从不同进程中来的写操作
对不同的进程可以有不同的顺序。
管道一致性模型相对来说比较容易实现，所以在应用中具有一定的吸引力。实际上，它
对于不同进程所感知到的写操作顺序并没有保证，除非是从同一个进程源来的写操作，
则必须按照顺序到达别的所有的进程，类似于它们处在一条管道中一样。除此以外在管
道一致性   模型中，有不同进程产生的写操作完全是并行的。
3．5弱一致性模型
尽管管道一致性模型与较之严格的一致性模型相比，能够获得更好的性能。但因为它对
同一个进程(源)所产生的结果仍然作了必须按序送达到所有别的进程的要求，所以在很
多应用方面仍然受到了模型的限制。并非所有的进程都要求看到所有的写操作的结果，
让他们按照顺序看到写操作的结果更是没有必要。这样处理，模型的开销会严重影响应
用程序的性能。考虑到运算的中间结果在大多数情况下并没有必须传送出去的必要的具
体情况，我们必须对一致性要求作进一步的放松，修改为只有在需要传播写操作的结果
的时候才将结果传送出去，除此之外，一切读写操作都完全是并行的。为了达到同步操
作的目的，在弱一致性模型中引入了同步变量。
弱一致性模型必须满足的条件有下面几点:
l 对同步变量的访问满足一致性的要求
l 对同步变量的访问，只有在以前的写操作在各处都完成之后才能完成。
l 对数据的操作（读或写），只有在以前的对同步变量的操作完成之才能完成。
第一点说明所有的进程都能以同样的顺序感知到所有对同步变量的访问。当一个进程访
问某同步变量时，它会把对该同步变量的访问广播出去，在该进程对该同步变量访问操
作成功之前，任何别的进程对同步变量的访问都将被阻塞。
第二点说明对同步变量的访问会导致对内存进行刷新的结果。当一个同步访问完成之后
，那么，所有先前的写操作可以同时确保完成。当某进程对一个共享数据作了更新之后
面，它可以通过同步操作将新值传播出去。
第三点说明当一个进程在读一个共享数据（非同步变量）时，通过同步操作，它能获得
该共享数据的最新值。
3．6释放一致性模型
对于同步变量的访问，弱一致性模型存在一个问题：无法区分进程是准备进入临界区还
是已经完成对共享变量的操作而准备退出临界区，其结果就是进程在以下两种情况下都
必须采取同步操作：
l 将局部写操作的结果传播出去
l 从别的机器上收集共享数据的最新值
如果将进入和退出临界区这两个动作区分，则可以实现一种更为高效的存储一致性模型
--释放一致性模型。释放一致性模型提供了两类同步操作：Acquire和Release。某进程
将要进入临界区时执行Acquire操作，退出时执行Release操作。也可以不用临界区而用
栅栏（Barrier）同步来实现释放的一致性协议。栅栏是一种同步机制，它要求所有的进
程全都到达程序的某一点后，各个进程才能继续往下执行。
借助于Acquire和Release操作，我们可以把某些特殊的共享变量保护起来，并维护它们
的一致性。当然，应用程序必须确知它需要维护其一致性的数据，这也给应用程序的编
制增加了一些协议开销，但是整体性能提高了。
通常，如果一个分布式共享存储系统满足释放一致性，则它必须遵守以下的规则：
l 某进程只有在成功完成Acquire操作之后，才能确保对一般共享变量（非共享同步变量
）访问的正确性。
l 某进程只有在完成对共享数据的读写操作之后，Release操作才能完成。
l Acquire和Release操作必须满足管道一致性要求。
为了更进一步提高性能，另外一种实现释放一致性模型的协议被称之为懒惰释放一致性
（Lazy Release Consistency），与之对应，一般的实现被称为勤释放一致性（Eager
Release Consistency）。它们之间的区别在于，勤释放一致性协议在Release操作结束
之后，将所有已修改的数据传送给所有的别的进程。这样，别的进程都将拥有此最新数
据的一个副本并可在本地访问它们。但实际情况是有可能别的进程并不需要该共享数据
，这样就浪费了带宽并给程序带来不必要的延迟。懒惰释放一致性协议在Release操作结
束之后，并不急于传送新的数据，而是在别的进程执行Acquire操作之后，由别的进程向
它提出获取新的数据的请求时，它响应该请求并把共享数据的最新值传送给特定的进程
，这样系统的性能又获得了提高。
3．7单项一致性模型
另外一种用于提高临界区操作并行性的一致性模型是单项一致性模型。和释放一致性类
似，它要求编程人员在临界区的开始和结束时使用Acquire和Release操作，但与释放一
致性不同的是，它要求每个共享变量都与某同步变量相关联，同步变量可以是锁或者栅
栏。以并行访问一个数组的不同元素为例，它要求给不同的数组元素加不同的锁，只有
当对同步变量的Acquire操作完成之后，相关的共享数据才得到一致性保证。单项一致性
模型也不同于懒惰释放一致性模型，后者并不将共享数据与锁或栅栏相关联，而是在对
同步变量作Acquire操作之后，才能确定它需要那些共享数据。
满足单项一致性的条件是;
l 在当前拥有者对数据的更新操作为完成之前，不能执行另一个进程对同步变量的Acqu
ire操作。
l 如果某一个进程正以互斥模式访问某同步变量。则在该进程释放此同步变量之前，任
何别的进程即使在非互斥模式下都将无法获得该同步变量。
l 如果某进程正以互斥模式访问一个同步变量，则在该进程完成操作之后，任何进程在
以后对此同步变量的非互斥访问，都只有在成为同步变量的拥有者之后才能完成。 

--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]