分散系统的典型构造

强结合系统和弱结合系统在把数台计算机投入系统使用时，必须先决定它们的连接形式即构造。构造也是分散型系统的固有问题。计算机的连接种类，多数要考虑到通信的信息量和必

要的速度，以及计算机的台数。首先进行的一大分类，是依据数台计算机(CPU)是否共有存贮器来分类。如果有共用存贮器，则称计算机的连接为强结合系统，反之，则称为弱结合系统(图6.9).

()强结合系统(b)弱结合系统

图6.9强结合系统和弱结合系统

在强结合系统中，由于主存贮器里有几个CPU相连接，所以在各个存贮器存取中有必要同步进行，所以存在着所谓总线仲裁问题(busarbitration),一般采用分时制总线，即在CPU和共用总线之间建立一个缓冲区，然后根据为满足总线使用要求而设计的总线分配器(busarbiter),进行开关控制，图6.10的例子是根据所谓数据收集判决链(daisy-chain)按优先程度工作的多处理器系统。最近在一些处理器中，也有将这一功能存放到集成片子中的.

作为其它具有代表性共用存贮器的实现方法，尚有交叉、多接口存贮器等。所谓交叉，是指像图6.11中所表示的那样，有规则的加一些总线。N×M交叉行列，包括N个处理器和M个存贮器。由于它的开关部分的构造变得较为复杂，许多处理器和存贮器之间可以同时进行数据通信，因此可构造成一个功能非常强的系统。它的典型例子是众所周知的Carnegie-Mellon大学的C.mmp,它是用16×16的交叉开关，把16台PDP-11和16个存贮单元结合而成的，其中开关延迟约2500ns,可参考共用存贮器。

因为多接口存贮器把所谓总线分配器的功能包括在存贮器中，所以存贮器有数个接口。作为下位处理器和上位处理器的命令交换场所，图6.12给出了一种最简单的可供利用的结构方案。我们称这种使用方法为嵌入箱法，由于使用多接口存贮器，可以明显提高CPU的容量，但是由于系统的构造受存贮器接口数量的限制，在某种程度上限制了系统的灵活性。

强结合系统基本上是通过系统总线进行通信，由于它把数个CPU结合起来，所以其相互之间的通信速度比我们下面将要介绍的弱结合系统要高得多，所谓强结合系统中的分散，其中一点是功能的分散，即由数个CPU并行处理给定任务，使之达到高速化。另外一点就是并行处理提高了可靠性，这一点我们还将要在6.3节中详细阐述。此外基于总线的电气特性，强结合系统不能适用于大范围系统。(最多限制在数米的空间范围以内，对于高于这一空闻规模的系统，因为计算机是分散配置的，所以必须采取弱结合系统.)

另外，由于弱结合系统的通信需要通过I/0设备进行，所以在通信中需要的经费总额较大，但与强结合相比，它在有关各计算机同步方面，实现起来较为简单，在弱结合中，只要使连接的基本规格一致，就能完全自由地和对方任何一种机种相连接。在只有一条通信线路(位串行)时，最容易连接。当通信线路为多条时(多

数情况为8位),只有并行时，才能实现高速通信。采用符号交换等方法时，接收数据必须同步进行，但是如果这一过程过于复杂化，反而会使通信速度阵低。

首先，让我们着一看图6.13所示的一般的弱结合系统的典型连接形式。最单纯的是象(a)那样通过1对1的通信线路，把所有部分结合起来；但是，这种方式需要aC₂个通信线路；并且其数量随着N的增加将加倍地增大。所以通过某种手段，实现多台计算机共用一条通信线路技术实属必要。

(b)称作星型构造，它以在中央放置一交换机而构成。因为星型构造系统所传送的信息全部要通过位于中心的交换机，所以系统的可靠性几乎全部由中央计算机的可靠性来决定。此外，当然中央计算机的负荷很大，其规模也必然会变得很大：

(c)不需要象(a)那样与全部的计算机直接连接，它是经过几个计算机来传达信息，与几个同样规模的计算机连接使用。这种情况下使用的技术是信息包交换(packetswitching)技术。送信方的计算机将信息分成若于个小的组成部分，在各个组成部分上分别加入标头(header)、发信地址及收信地址，并且附加上纠错符号，编成发送信息包(packet),然后把它们按随机方向发出。计算机在收到分组发出的信息包后，进行辨别，把发给自己的信息包收下，不是自己的信息包则送到其它方向去。按照这一规则，信息包经过几个计算机送到收信处，收信处的计算机还可以将这些信息包按照正确的顺序号进行排列，把信息复原，最初采用这种连接方式的是阿判特ARPANET,它把全美国约20所大学和研究所等联结成一个规模相当大的网络。虽然这种结构非常灵活，但它的通信控制变得很复杂，所以未必适合于机械电子学机器，因此未被广泛使用。

(d)被称作环路型。它是将(c)的构造适当简化得到的，这时可使通信路线形成环路，发送数据由各计算机做中继，最后再回到发信处。

(e)称作总线型或共用线型。在共用总线上送出的信号，传

送到所有计算机后，在总线终端消失；因为环路型和总线型的构造比前面所介绍的两种简单，所以在小规模的系统中使用较多.因此作为机械电子学机器的通信系统，它是最重要的。下面就这两种型式做一些较详细的说明。

环型网路环形网路，可以根据它的使用形式分成New-hall型和Pierce型两大类型。前一种只有在有发信权时，计算机才能发送新的信息，否则只能做中继传递信息。在环路中只放置一个有发信权的计算机，然后让计算机之间依次进行相互间的信息传递(图14(a))。后一种是在环型线路中按固定的时间划分成数个时隙，当识别出空隙时，计算机便可以输人信息(图6.14(b)).前一种可以传送可变长信息，说明它具有灵活性特点，但它在无发信权时，尽管线路空闲也无法利用，因此它的利用率并不高。与前者相反，后者的信息长度是被固定的。

环型结构完全可以按与接口数成比例的价格进行构造，不需要路经控制等繁琐手续，并且由于发信方面完全可以不必考虑收信方面具体在什么位置就可以发信，所以系统扩展也很容易，此

外，官还具有可以利用高密度的通信电路等优点。但是另一方面，因为信息要通过数个接口，所以必须对其可靠性予以特别关注，

环路型网络的可靠性，就其本身而言属于串联系统，因此随着计算机台数的增加，其可靠性将按幂级数下降。

因此，对于环型网络，可以叫做第二原理的故障排除功能的设计是不可缺少的。作为典型的故障排除功能，可以举回送和节点迁回两种功能。为了实现回送，如图6.15(a)所示，必须使环路二重化。通常情况下只使用环路的单一方向，即按箭头所示方向传送信息。比如现在在图6.15(b)所示有×记号的部分发生故障，由节点0把它检测了出来。这时节点0立即通知所有的节点，让它们构成闭环，各节点按(c)那样转换通信线路，然后首先设置个别环路，再像(d)那样将环路中的节点数不断增加，直至增加到发生故障，最后设置一个像()那样的迁回环路，环路被恢复，操作可以继续执行。

节点迁回大体上也是基于同样的考虑，在检测异常现象的同时，设定所有节点迁回的路径，然后顺次把节点纳入环路中，这时再次发生故障的地方自然就是故障节点了。最后只把有故障节点排除在环路以外，环路才能被恢复(图6.16)。

总线型网络这时系统的物理构造从本质上讲与共有存贮器情况是一致的，但是从判断的方法来讲，它具有较大的灵活性，其典型的型式是：(1)数个节点可以主动地向系统发送信息，允许在总线上采用信息冲突的方式(CSMA,cartiersensemulcipleaccess);(2)设定节点的发信权(对话),只有获得发信权的节点才能进行发信的方式；(3)采用固定地按每一个节点分配时隙的方式等。

(1)CSMA方式

CSMA方式中，只要节点不使用共用总线，就自动开始发送信息。这一方式的最明显的特点是，因为有信息的冲突，所以通信线路的工作具有随机的性质。就是说在CSMA中，从原理上讲通信线路不会100%地被信息占用。(即使在不使用总线的情况下，也只能采取按概率P进行发信的方式，这种方式叫P-persistentCSMA,P-persistentCSMA的优点是可以减少信息冲突，通常情况下CSMA的P-1.)

那么CSMA能达到何等程度的通信效率呢?现在我们设每

一节点单位时间内随机发送的信息为λ个。假如系统里有k个节点，那么共用总线上每单位时间产生的信意数，为：

实际上因为有冲突发生，所以通过共用总线的信息实际量R要比r多。假如发送一条信息所需要的时间为r,那么至少在2r时间内不能再发送其它信息。现在如果我们近似地将再发送的信息按指数分布规律考虑，则其信息产生冲突的概率P为：

P=1—exp(—2kr)(6.5)

在产生冲突时，若再次发送信息，则其关系式为

R=r+R(1—exp(—2Rr))(6.6)这里设s=rr,S=Rr,S是每单位时间内共用总线被信息所占用的时间，如果总线全被信息占满而无空余时间，这时S=1.于是S代表总线的通信量。s代表其中用来实际进行传送信息的部分，即总线的利用率。由(6.6)式可以直接得到

=Sexp(—28)(6.7)图6.17表示的就是这一关系。该图明显表明，若对(6.7)式进行微分研究，则知当S=0.5时，s取最大值s=1/2e(=0.186).如果要发送的信息超过这个数量，势必要增加冲突的概率和再发送量，这样将进一步导致冲突概率增加，从而引起恶性循环。总之，对于CSMA型总线，其总线利用率最大不过0.186,例如使用具有1Mbps通信速度的总线，其有效通信最多只有186Kbps。

如果发信节点，在发信中也能经常监视总线中的混信现象.(CD,collisiondetction),一旦发生混信立即停止发信，在随机时间等待中，如果修正执行再发信算法，就可以减少总线上的冲突，这种方式叫做CSMA/CD.

(2)轮询方式

第二种方式是将总线进行集中分配，所以要设置中央总线控制器。这一控制器每隔一段时间(轮询间隔)向所有计算机发出是否要发信的询问，并根据要求分配总线。因为轮询大多要利用传送信息的总线，所以这时真正的通信速度与原来的总线容量相比要低。

在各计算机发送信息量较为平均时，轮询分配总线这一方法是行之有效的。但是在总线利用率不太高，各计算机的利用不均衡时，还是插人总线控制器启动较好，这时需要一条专用插人通信线路，整个系统的工作实质上和CSMA的专用插入通信线路是一致的。

(3)固定时隙方式

相反，固定时隙方式是一种比轮询更为固定的方式。它考虑了在各计算机上固定分配时隙的方法，同时它也考虑到像在冲突型中那样进行时隙争夺的方法等，以及各种时隙的管理方法，只要条件具备(即信息产生趋于乎均化而且具有很高的信息密度)这种具有微小时隙的管理方式是很有吸引力的。

5.2.3分散型系统的统一

分散型系统的统一前面讨论的是关于硬件等级的分散问题，但是要讨论计算机，就必须同时包括硬件、软件两个方面，所以还必须考虑到软件等级的分散。即使是对于精心设计的硬件(越是这样问题就越尖锐),如果不同时考虑软件，也不能说是全面的。最后，当以分散型方式设计系统时，由于采用了多台计算机，很自然地会产生一个疑问，即这时是否能达到控制动作的前后一致这一问题，即达到系统前后一致的问题，正是分散型系统的固有问

题，下面将论述确保分散型系统前后一致的基本理论。

关于最基本的有关通信的协议条款(通信规章：如果不遵守这些规章，计算机之间的信息交换将不可能进行),已经在网路构造中一起说明过。但只介绍那些是不够的。在分散型系统中，因为每个处理器的各种程序是非同步执行的，同一资源往往有多个处理器进行存取，所以对于这种要求如果不作一定安排，是不能保证整个系统圆满工作的。

作为最典型的资源，让我们来考虑有关分散型系统的文件使用问题。现在设某一处理器i使用了文件f.这时处理器i突然将文件于的内容进行存取，于是文件f的内容便被改写。此时，对于处理器i来讲，由于文件f的一部分内容突然产生了变化，因此，便不能保持处理中的一贯性，在最坏的情况下，还会导致计算结果的严重错误。因此，为了防止这种现象的产生，必需确立处理器使用文件f的优先权，即文件必须具有排它控制的特性。为此，一种方法是依据6.10所示的总线分配方式，可以考虑采用硬件手段，但一般情况多采用软件手段。

经常使用的是1968年由E.W.Dijkstra提出的信标概念。它将公用存贮器的一部分作为排它控制的信息标志来使用，并且规定文件只有在信标为0时才能使用。即应采用以下顺序：当存贮器要存取某文件时，首先要检验信标，如果信标等于1时，要等它变成0后，再置成1,这样才能确立文件的使用权(P操作)。当文件使用完后信标随之也恢复0位(V操作)。这样就能够实现以纯粹的软件文件进行排它控制。另外，信标不仅仅限于0,1.它也可以被扩充用来显示更多的信息。例如它可以有下列功能：

0:可以读出也可以写入

1:只能读出

2:不能读出也不能写入

即使是根据信标确立了文件的使用权，也没有解决全部问题，这时产生的新问题就象下述比喻那样，是一个颇为著名的问题。现在有N个哲学家围坐在圆桌周围，每天除了思考就是用餐，在他

们用餐时，面前摆好了食品，而且在他们之间各摆一支筷子。显然，即使是哲学家吃饭，也需要一双筷子才行，这样，便只能保证n/2个人同时同餐。如果都个人同时伸手将自已左边的筷子拿起，那么这时#个人便会每人左手拿着一支筷子，永远处于思考之中而无法用餐了。这与两个以上的处理器各自要求两个以上资源所产生的问题是相同的，这种情况称之为死锁，在系统产生了死锁时，在不做任何处理的前题下，系统的状态是不会产生其它变化的。

要想摆脱上述n个哲学家造成的死锁状况，只要有某一哲学家放下左侧的筷子就行了。这样一来，靠近他左侧的哲学家就可以开始用餐了。待他用餐完毕后，靠近他左侧的哲学家又可以开始用餐了，……于是这种过程便可以继续进行下去。总之，为了解决死锁状态，必须有一套保证资源开放的规则，从原理上讲，根据分析处理器之间的资源要求关系，当然可以检测死锁现象，但这需要花费很大的劳动，而且伴随着管理的增加，会导致效率下降的危险。因此，从现实来讲在确保一部分资源后，如果不能把剩下的资源保持到一定时间以上，则很容易将它们判断成死锁、但是，对于所有处理器，如果把这个一定时间都设置为相同的值，就会造成双方的要求与释放均在同一时间上重复，所以最好是每一个处理器都利用随机数，这时，再使判断标准作一些变动，也可以根据对随机数平均值的操作，在各处理器之间赋予不同的优先权。这方面的考虑方法与CSMA/CD的考虑方法是一致的。另外关于哪个处理器应该放弃权力的问题，一般多选择最后进入等待期的处理器。

层次控制的实现皮其原理下面让我们更深入地考虑一下涉及到处理内容的综合问题。在这里我们要特别以由M.D.Me-

saroric等人提出的层次系统综合理论为中心进行介绍。

现在让我们看一看图6.18(=)所示的简单例子，即考虑一个用两个系统控制过程P的问题。子系统1,2具有各自的目标函数JJ,假定它们都能够尽力争取实现各自目标函数的最优化，从

机能方面来看，这就实现了最单纯分散型系统的模式化，图中y₁表示子系统；对控制对象进行观测得到的观测量，表示控制输入量。

因为两个系统通过过程P相互产生作用，因此它们不是独立的。于是当像图6.18(b)那样，将过程一分为二，而以xi的组合表示两者的相互作用时，则在数学式子中，子系统主的行为就可以用具有下标：的变量描述了。也就是说从形式上看问题已分成了两个。

此外，本系统作为一个整体，具有前后一致的特性，因而存在着整体上的目标函数J,系统的目标正是使J达到最优化，而非其它。叫做上确界目标函数，与此相应，子系统的目标函数叫做下确界目标函数，就此意义而言，刚才叙述的子系统只不过解决了从

下确界意义上的问题，为了解决系统整体的前后一致性，有必要等待来自更高层(上确界单元)的输入r,这个r称做综合输人，借助于γ来确保系统的前后一致性，叫做综合过程。

特别是当上确界单元具有解r,而相对于γ又有根据下确界意义决定的问题解时，则称下确界意义决定的问题是可以综合的.

特别是将有关下确界意义决定问题与上确界意义解决问题综合起来时，即通常成为以整体意义决定问题解的时候，可以保持系统的一贯性，这称为一贯性公理。一贯性公理只有在下确界目标函数f、f₃和上确界目标函数f如图6.19所示，满足调和关系时才成立。但在多数情况下，上下两级目标函数很少是调和的，因此有必要以某种方式对下确界目标函数进行修正。这就叫做下确界性能修正。

那么下面我们考虑一下怎样具体地决定综合输入γ才是一种好方法。导致一贯性分散系统的一贯性被破坏的原因，是各子系统(下确界意义起决定作用单元)之间的相互作用被忽视，各个子系统都进行各自的最优化。所以上确界单元的作用之一是在下确界单元的相互作用变为希望的状态时，只对下确界单元施加影响。

下面介绍三种具有代表性的具体的上确界单元接入方法。(1)相互作用预测原理

作为用上确界单元的接人方法之一，考虑将相互作用x的预

测值a输入到下确界单元中去。这种情况对于下确界单元来说，可以解释为施加了相互作用，在这种条件下只要取下确界单元决定问题最优化就可以了。现在，在下确界问题的解为整体的解的情况下，其结果产生的实际的相互作用x;等于a;的时候，整个系统自然会达到最优化。这就是所谓相互作用预测原理，在此论述成立的条件下，就说相互作用预测原理是适用的。

为了便于理解，让我们用例题说明，首先举一个最优化失败的例子，然后再讨论为了使最优化成功，需要采用怎么样的下确界性能修正方法。例如，考虑其动态过程可以用下列关系式描述的系统：

(yisy₂)=(w₁,4m十x)(x₁,x₂)=(2,期1)

此时，设下确界目标函数为

J₁=+(yi—2)²

J₂四w²十y

并设上确界目标函数为

J-]+J₂

(6.8)(6.9)

(6.10)(6.11)

(6.12)

此外，这里我们设从上确界单元可以得到预测值(a₁,a₂)一(-4/17,1).于是在此条件下使J、J₂最小化的(m,2),在预测值a:将x替换后，就可将(6.8)式代入(6.10)和(6.11)式，从而求得

(m,4)=(1,—4/17)

而且因为它可以满足(6.9)式，所以预测是正确的。然而实际上将(6.8)式和(6.9)式代入(6.12)式，然后仅作为#1shz的函数直接

进行最小化，便可以得到

(4,N₂)=(34/35,—8/35)

它是从整体上讲的最优解。因此由于此例在相互作用预测原理上是不适用的，所以系统的综合是失败的。

因此，应对目标函数进行如下修正：

J*=Ji+βi#(6.13)

比如现在设

(β₁,β₂)=(2(a₂+4a),0)(6.14)

那么下确界问题的解就是

(M₁,2)=(34/35,—8/35)

这样一来，最初的下确界问题的解，就与上确界问题的解等同起来了.反过来说，如果这样的β)存在，则相互作用预测原理就适用于上述问题，综合使用就是成功的。实际上(6.14)式中的β:是在使控制输出w变化一个单位时，与相互作用变量变化部分对应的J的变化量(现在只取与x;有关的w作为变量(其它w为常数),并取J对的偏微分),βi被称做目标相互作用元素。此时对于上确界单元只要注意能否正确预测相互作用x;就可以了，当相互作用预测原理适用时，可以组成如图6.20那样的反馈系统，系统最优化设想是可以实现的。

(2)相互作用均衡原理

对于每一个下确界单元，设相互作用#可以自由设定，并且根据上确界单元输入的信息，在设定值变化时，它们和实际的值保持一致，则此时可以得到系统整体的最优解，这就叫做相互作用均衡原理。相互作用均衡原理的适用范围比相互作用预测原理要广。例如，在目标函数J=J₁十J₁时，只要它们之间存在着单调的函数

关系，相互作用均衡原理就完全可以适用。

就相互作用的为衡原理进行综合而言，下确界目标函数可以设为

J*=J士β₂x₂一β₁x₁(6.15)

J*=J₂+β₁x一β₂x₂(6,16)

式中，β₁、β₂为综合输人，下确界单元在综合输入的基础上，正好可以把x;做为独立变量进行最优化处理。现在假定x=x*为下确界单元解的结论。通常x*与实际的值是不同的。倘若上确界单元对此情况进行观测，如果x*>xi,则把β;加大，如果相反则把p;缩小，这样，在下确界单元的最优解中，x7就应该向接近于实际值的方向变化。因此，最后就有可能达到x?=x;,从而实现了系统整体的最优化。

如果相互作用均衡原理适用的话，就可以根据图6.21那样的反馈系统实现系统的最优化。

(3)相互作用估计原理

上确界单元不确定相互作用的预测值，但指定其变化范围，最后考虑下确界单元在上述条件约束下，进行最优化的综合法。根据这一原理，在可能进行综合的情况下，相互作用估计原理就是适用的。在以预测的变化范围为单变量时，相互作用估计原理就是相互作用预测原理。