分布式操作系统6(2)剖析

•在DSM系统中，每个只读页可以有多个拷贝，而每个可写页只能有一个拷贝。在最简单的实现方案中，机器远程访问一可写页会激活陷拼，然后获取该页。由于可写页经常共享，因此只允许有一个拷贝可能会带来严重的性能瓶颈。•只要能更新所有拷贝，允许多重拷贝就可以简化性能问题。但这又引起了新的问题:即如何保证所有拷贝的一致性。当拷贝分布于不同机器上，而机器间通信只能通过慢速的(和存储器速度相比)网络发送信包来完成时，维护绝对的一致性就显得尤其困难。•一致性模型本质上是软件与存储器间的协约问题它指的是，如果软件遵守约定的规则，存储器就能工作正常。如果软件违反了这些规定，存储器就不再保证操作的正确性。有些对软件只有少量限制，而有些则使普通编程几乎成为不可能。限制少的模型没有限制多的模型执行效果好。6。3一致性模型•严格一致性(StrictConsistency)最严格的一致性模型称为严格一致性，它由下述条件定义:从存储器地址x处读出的值为最近写入x的值。这个定义自然而明白，由于它假定了绝对全局时间的存在，“最近”访问的意义是明确的。传统意义上，单一处理机遵守严格一致性。•在一系统中编程如下:A=l;A=2;PRlNT(A);在DSM系统中，假设X是存在B机器上的变量。A机器上的进程在t1时刻读取X,即发送信包到B以读取X.稍后，在t2时刻，B机器上的进程写x.若遵守严格一致性，不管机器在哪里，相距多近，A都应该读出原来的值。然而，若t2-t1=1ns，而机器距离3米，从A到B传送读操作并使之先于写操作，信号则必须以十倍光速的速度传递，而这与爱因斯坦相对论矛盾。带来了存储器和软件的协约问题。若协约或明显或暗示地要求严格一致性，存储器则最好传送它。为使举例精确，我们需要一些特定符号。先规定一些符号:p1，p2，…代表不同的进程，在图中以不同的高度表示，每一进程完成的操作水平的显示时间轴向右增加，直线分割不同进程。符号W(x)a和R(y)b分别表示在x处写a和从y处读出值赋给b.本章所有图表中变量初值均为0。如图6-l0(a)，P1在x处写1之后，p2读x，返回1。对于严格一致性存储器，操作是正确的。•相反的，如图6-10(b)，P2在写之后读(或许是1纳秒之后，但仍在写之后)，返回值为0。之后又执行一次读操作，返回值为1。对于严格一致性的存储器，这个操作是不正确的。总之，对于严格一致性的存储器，写操作在任一时刻对所有进程都是可见的，同时维护一个绝对全局时间。一旦存储器中的值改变，不管读写之间的事件间隔多小，不管哪个进程执行读操作，也不管进程在何处，以后读出的都是新更改的值。同样，不管后面的写操作有多迅速，执行读操作仍应读出原来的值。•顺序一致性(SequentialConsistency)尽管严格一致性是理想的编程模式，但在分布系统申，这几乎不可能实现。经验表明，编程人员通常对弱模式掌握得较好。比如，所有操作系统课本中都谈到临界区和同步互斥的问题。人们认为编写这种正确的并行程序(如生产者一消费者问题)不应考虑进程间的相对速度以及语旬的执行在时间上如何交错。如果一个进程的两个事件发生如此之快，以致其他进程不能在此之间执行任何操作，那可能会带来麻烦。相反，读者的编程方式是:语句执行顺序(实际上是存储器访问)并不重要。如果事件顺序是必要的，必须要用到信号量或其他同步操作。接受这种意见意味着采用弱模式。经过儿次实践，大多数并行程序编写人员都能适应这种模式。•顺序一致是比严格一致稍弱的存储器模式，首先定义了顺序一致存储器应符合的条件:如果所有进程以一定的顺序执行操作，每一进程的操作都以程序规定的顺序出现，则任何操作的结果都是一样的。这个定义说明:对于在不同机器上并行运行的进程，任何有效的交错都是可以接受的行为，但所有进程必须遵守同一访问存储器顺序。在一块存储器中，若一个进程(或处理机)看到一种交错另一进程看到另一个交错，这就不是顺序一致存储器。注意，这与时间无关，没有最近存入的概念。在这里，进程可以看到所有进程写，但只能看到本进程读。顺序一致从图6-11可以看出这里不考虑时间。图6-11(a)表示的存储器行为是顺序一致的，尽管P2执行的第一次读操作返回初值0而不是新值l。图6-11运行同一个程序得到的两个可能的结果。顺序一致存储器不保证读返回的值是lns、lms甚至1分钟以前另一进程写入的。它只保证所有进程以相同的顺序看见存储器访问。如果根据图6-11(a)编写的程序在一次运行后，或许会得到图6-11(b)的结果。结果是不确定的。如果缺少明确的同步操作，在此运行程序或许不能得到相同的结果。P1:w(x)1P1:w(x)1P2:R(x)0R(x)1P2:R(x)1R(x)1图6-11运行同一个程序得到的两个可能的结果。三个并行运行的进程的代码。三个进程共享相同的顺序一致分布式共享存储器，并都访问变量a,b,c。从存储器访问的角度看，赋值应被看作写操作，打印应被看作同时读取它的两个参数。所有语句都是原子操作。各种交错执行的顺序都是可能的。六个独立的语句，将会有720(6!)种可能的执行顺序，尽管它们可能会破坏程序顺序。从a=I开始的考虑的顺序有120(5!)种。其中一半将在b=l前执行print(a，c)，这就打乱了程序次序。还有一半将在c=1前执行print(a，b),打乱程序次序。120中顺序中只有1/4即30个是有效的。另外30个有效顺序是以b=I开头的，还有30个以c=l开头。共有90个有效执行顺序。如图6-13(a)，三个进程以p1，p12、P3的次序运行，另三个例子(b)(c)(d)则不同，但同样是有效的，语句按时间交错执行，三个进程部打印两个参数。由于每个变量只可能是初值0或被赋值为1，每个进程产生一个二位字串。在print操作之后的数字是在输出设备上的实际输出。下面可以标记项而不用打印输出表示每个次序。若以这种次序顺序输出p1，p12、P3的结果，将得到六位字串，这标明了语句(以及存储器访问)的一个特定交错。这就是图6-13中的标记项(Signature)所写的字符串。并非所有64种标记项都是允许的。如000000就不允许，因为这意味着打印语句先于赋值执行，违反了关于语句必须按照程序顺序执行的规定。另一的例子是001001，前两位00即当p1打印时，b,c都是0。这种情况只发生在p1在p2,p3开始前执行所有语句。下面二位10，即p2必须在p1之后P3之前开始执行，最后两位01，即p3必须在开始之前完成。但我们已经看到p1必须先运行，因此001001是不可能的。总之，在假定顺序一致的情况下，90种不同的有效语句次序导致了不同的(但少于64种)运行结果，这些都是允许的。软件与存储器在这里的约定是:软件必须承认它们都是有效结果。也就是软件必须接受图6-13的4个结果以及其他有效结果为正确答案。若任何一种情况发生，这就仍须正常工作。•顺序一致存储器可在DSM或多处理机系统上实现。有很多正式系统使用了顺序存储器(和其他模式)思想。我们简单看一下Ahamad系统。在这种系统中，进程i读写操作顺序由Hi(Pi的历史)确定，图6-10b显示两种次序H1和H2，分别对应于p1和p2，表示如下:H1=W(x)1;H2=R(x)OR(x)1这种次序的集合称为H。为得到操作执行的相对顺序，必须合并H中的操作串为一个单独串S，每个操作在S中出现一次。S的合法值须遵守两个限制:(1)维持程序次序;(2)保证存储相关性。第一条限制:如果在H的字串中，读或写访问A出现在另一访问B之前，那么S中A也应出现于B之前。若所有操作遵守这个规定，则S中不会出现违反程序的执行顺序。第二条限制意味着在地址x处读出的值必须是最新写入的x,即在R(x)之前由最近的W(x)v写入的值v。图6-10(b)中，S只有一个合法值:s=R(x)0W(x)1R(x)1，对于更复杂的例子，S可能会有更多的合法值，若操作顺序是按照S的一些合法值进行的，则程序运行被认为是正确的。虽然顺序一致性是对编程人员友好的模式，但有严重的性能问题。若读时间为r写时间为w，节点间信包传输最小时间为t则总有r+w=t.换而言之也就是对所有顺序一致存储器来说，改变协议试图提高读性能只能导致写性能下降，反之亦然。•6·3·3因果一致性(CausaICons;stency)因果一致模型是顺序一致的淡化，它按有无可能的因果联系区分各事件。现在看看存储器的例子。假设进程P1写变量x然后P2读出x写入y。这里读出x和写入y之间可能有潜在的因果联系，因为y的计算很可能决定于P2读到的x值(即P1写入的值)。另一方面，若两进程自然而同时地写两个变量，就没有因果联系。先有读操作之后执行写操作，两个事件就可能有因果联系。相似的，读和提供所读数据的写有因果关系。没有因果关系的操作称为并发的(concurrent)。因果一致的存储器应遵守以下条件:可能因果相关的写操作应对所有进程可见，且顺序一致。并发写操作在不同机器看来顺序可能是不同的。图6.14是一个因果一致性的例子。这里我们有--个在因果一致存储器下允许的事件顺序，在顺序一致存储器和严格一致存储器中这是禁止的。要注意的是，W(X)2和W(x)3是并发的，所以不须所有进程将他们视为同一顺序。若不同进程以不同次序看待并发事件，而导致软件失败，则违反了因果存储器协约。P1:w(x)1w(x)3P2:R(x)1w(x)2P2:R(x)1R(x)3R(x)2P2:R(x)1R(x)2R(x)3图6.14因果一致性可，顺序一致不可图6-15(a)中，W(x)2可能决定于w(x)1，因为2可能是R(x)1所读的值计算的结果。两个写操作是因果联系的，所有进程必须视它们为同一顺序。因此6-15(a)不正确。6-15(b)中，读被取掉，w(x)1/和W(x)2变为并发事件。因果一致性存储器不要求并发写有全局一致的次序，因此6-15(b)是正确的。在因果一致性存储器中，所有机器看到的因果相关写操作的顺序是一致的，而并发写操作的顺序可以不同。进一步放松对存储器限制可以去掉前面的要求。这样就给出了PRAM一致(管道RAM)，它要遵守的条件是:一个进程的写操作可以被其他进程以指定的顺序接收到，但不同进程的写操作在不同进程看来次序可以是不同的。PRAM一致和因果一致的对比如图6-16所示。这里的时间顺序在PRAM一致的存储器中是允许的。PRAM一致性和处理器一致性PRAM一致由于易于应用而得到关注。它不保证不同进程看到的写操作顺序是一致的，除非是一个源的一个或多个写操作，才必须按次序到达，就好像在管道中。换而言之，在这种模式申，由不同进程产生的巧操作是并发的。图6-17，在PRAM一致下，不同进程所看到的语句执行顺序不同，如图6-17(a)显示p1怎样看到事件，而6-17(b)显示p2所看到的，6-17(c)则是P3所见。对于顺序一致存储器，三个不同显示是不允许的。我们使三个进程的输出顺序相接，得到结果为001001，正如我们早先看到的，这在顺序一致性下是不可能的。顺序一致与PRAM一致的关键不同在于:前者尽管末确定语句(和存储器访问)的执行顺序，但至少所有进程都遵守共同的顺序。后者就不遵守。不同进程看到的操作顺序不同。有时，PRAM一致导致的结果不那么直观。在下面的例子中提出了一种略微不同但仍支持PRAM一致的存储器形式。如图6-18，有人可能会天真地期待出现三种结果之一:P1被KlL；P2被KILL;或两者都不被KILL(如果两个赋值语句先执行了)。在PRAM一致下，可能两个进程都被KlLL，即若P1在看到P2中b赋值之前读取b,p2在看到P1中a赋值之前读取a.在顺序一致存储器下可能有6种语句交错，没有一种可以导致两进程都被KlLL。6.3.5弱一致性(WeekConsistency)•通过同步变量，可以让进程完成临界区操作以后，将最后结果发送到各处，而不必太关心甚至不用关心中间结果是否也按顺序发送到存储器。•Dubois定义这种模式为弱一致性，它有三个属性：–对同步变量的访问是顺序一致性的；–在所有先