CN1971548A - 用于对固定等待时间互连进行锁步处理的方法和装置 - Google Patents

Abstract

描述并请求保护通过在每个设备上产生请求、比较这些请求、并向服务节点提交匹配的请求来以锁步的模式运行两个或多个设备的方法。还描述并请求保护了采用所述方法的冗余执行系统。

Description

用于对固定等待时间互连进行锁步处理的方法和装置

技术领域

本发明涉及冗余处理。尤其是，本发明涉及保持冗余处理器与以锁步操作的其它设备之间的同步。

背景技术

计算机系统常常在不友好的环境中执行临界控制、分析、通信及其他功能。当这些系统在物理上难于或不可能达到的时候，提供充分的冗余以便对故障和伪错误进行检测和自动恢复是很重要的。保护计算机系统不出现错误的一种常见的方法是采用双模块冗余度或三模块冗余度：以锁步模式来操作两个或三个(或更多)系统模块并比较它们的行为。如果几个相同的模块执行相同的操作，那么理论上，该模块的行为之间的任何差异都可能表示一个或多个模块出现了故障。理论上仅仅通过对系统中某个关键点处(例如在地址和数据总线)存在的信号进行比较并且无论何时检测到不匹配都启动错误恢复程序，从而再次检测差异。

实践中，时钟脉冲相位差和类似的影响会引起信号不匹配，即使当该模块是处于适当操作时也是如此。由于错误恢复可能是计算代价很大的处理，所以错误锁步失败信号会严重地降低系统性能。同样地，错误恢复可包含每个模块上的不同操作，以及可以没有有效的冗余系统来保护所述恢复防止随后发生错误。此外，传统的锁步冗余系统包含专门的硬件电路以执行信号比较。这些电路降低了系统在不需要冗余处理时作为普通多处理器系统来操作的灵活性。

附图说明

用附图中的图形以举例说明的方式说明了本发明的实施例，本发明的实施例不限制于附图中的图形，其中相同的参考标记表示类似的元件。应当注意在说明书中提到“一”或“一个”实施例不必然是同一个实施例，这些说法意味着“至少一个”。

图1显示了实现本发明实施例的系统的逻辑概观图。

图2是两个锁步处理器可执行以确保它们发出的请求是正确的程序的流程图。

图3是允许两个锁步处理器接收消息并且开始同时处理其内容的程序的流程图。

图4是一个由以锁步运行的“从属”设备所进行的类似程序的流程图。

图5是从属锁步设备的另一个程序的流程图。

图6显示了一个示例系统，其包括实现采用本发明实施例的使用功能的逻辑模块。

具体实施方式

本发明的实施例把处理器、存储器和其它设备放在围绕着固定等待时间、环形互连网络的位置上。网络的每个节点可向任一其它节点发送消息，并且网络的固定等待时间性能允许发送者确定要用多长时间把这个消息送达目的节点。系统部件的这种结构支持可操作的范例，所述范例包括普通多处理以及冗余、锁步处理。在锁步模式中，系统自动地过滤出由于时钟脉冲相位差所引起的许多无害的计时误差。大多数发出信号的错误表示真正的数据差异。

图1显示了结合本发明实施例的系统的图。环100表示固定等待时间、无缓冲、环形的通信网络。连接于该网络的设备可把消息放到环上或者从环上移除消息。例如170和180这样的消息以顺时针方向在环上前进，从发送节点到目的节点。如果目的节点不能接受该消息(例如，因为它正忙或者因为它没有空闲的缓冲空间)，则该消息继续在环上绕行直到目的节点变为能够接受它。只要没有消息正在由该节点进行传递，该节点就可以在环上放置一个消息。环同步地进行操作，同时消息以规则的间隔从一个节点移动到下一个节点。因而，知道它的目标位于环上多远的发送者可确定把消息送到那里要花多少时间。(当然，当消息到达时目标可能不能接受该消息；发送者必须计算这种可能性)。尽管这个图显示了等于节点数目的多个消息和空消息位置，但是实际的设备可允许在环上放更多的消息。然而，网络是无缓冲的，所以其容量是没有弹性的。

与本发明的实施例有关的通信网络的特征在于发送者可以确定消息传播到接收者要花多少时间。被显示为元件100的固定等待时间的无缓冲环形网络具有这种特征，并且提供了一种易于理解的结构以供以下的说明所用。然而，实施例并不限制于环拓扑网络，或者甚至不限制于固定等待时间互连，只要该网络允许用已知等待时间来传送确认信号。

可以把一系列设备放在环100的节点上。在图1中，显示了三个中央处理单元(CPU)110、120和130。两个存储模块140和150以及存储设备160也围绕着环而设置。通信网络的说明和描述指的是网络的逻辑结构，而不是它的物理结构。实际的设备可能会把环形通信网络全部放在单个微电子电路内或者把它分配给两个或多个电路，只要所描述的通信能力是可用的。

在一些系统中，通信网络可以是双向的，其中消息可以绕着环顺时针或逆时针进行传播。(这种系统可被分析成双叠加无向环)。为了简要和易于理解起见，然而，以下大部分例子会假定单个、无向、固定等待时间、无缓冲通信结构。

具有这两种情况的环上部件的系统可以以锁步、冗余模式来操作部件，并且如果部件把不同的消息放在环上，尽管接收相同消息，则仍发出可能锁步错误信号。因而，例如，存储器140和150可以以锁步模式来操作，并且如果该存储器响应不同，则检测仅影响一个存储器的伪错误。

具有三种或更多种环上部件的系统可执行相同的锁步处理，但是也能够通过采用投票协议来确定哪个部件失败了或者经历了错误：如果三种情况中的两种一致(或者，更一般地，如果多种情况一致)，那么该系统如大部分消息表示的那样来进行。

图2的流程图显示了以锁步模式运行的两个CPU怎样发送请求到固定等待时间通信网络上的另一个设备。把该CPU指定为“较近”和“较远”以表示相对于目的设备而言它们在环上的位置。这两个CPU都产生到该设备的访问请求(210a、210b)，所述CPU以接近同步(但是有可能不精确)的方式来执行相同的指令。如果CPU独立地操作，则每个CPU会简单地把消息放在环上并且把它发送给该设备，该设备将通过把适当地答复放在环上来响应每个消息。然而，在锁步模式中，“较远”CPU把请求发送给“较近”CPU(220)。消息绕着环传播到较近CPU(230)，同时较近CPU等候该消息(240)。最终，较近CPU接收到请求(250)并且将其与它本身的本地产生请求相比较(260)。如果请求匹配，则较近CPU向该设备发送单个合并请求(270)。如果请求不匹配，则较近处理器发出锁步错误信号(280)以初始化锁步恢复程序。这个请求本身可以将从存储器或者其它设备中获得数据，或者在存储器中存储数据或者把数据发送给该设备。在这方面，请求可以对应于普通的存储器读或写周期，或者对应于I/O端口“IN”和“OUT”操作。

这个程序相对于计时误差是有弹性的：如果较远处理器在较近处理器之前产生并发送请求，那么该请求只是在环上传播直到较近处理器发现并准备接收和比较该请求。如果较近处理器在前，那么它会等候直到较远处理器发现并发送请求。在每一种情况中，如果看门狗计时器逻辑电路检测到任一个处理器花费太久来等待另一个处理器发现，则看门狗计时器逻辑电路能产生锁步错误信号。

用于接收指向两个或更多锁步部件的消息的程序稍微更复杂一些，因为希望该部件同时开始处理消息。图3显示了如何实现这一点。

向锁步部件发送消息的设备把消息放在环上，发送到部件之一(310)。例如，如果该设备响应合并消息，它的传送已经参考图2进行了描述，则可以将答复发送给那个图中标记为“较远”的处理器，因为在无向环上，“较远”处理器实际上是与该设备比较近的。较远和较近处理器都等待答复(315a、315b)。

较远处理器接收该消息(320)但是不立即开始对消息进行处理。而是它分配缓冲区以保存确认(330)并且把该消息重新传送给它的锁步配对，“较近”处理器(340)。较近处理器接收该消息(350)并且向较远处理器传送确认(360)。一旦它在环上传递，较远处理器就能够接收到该确认(370)，因为它已经预先分配了缓冲区来保存该确认。两个处理器都开始处理消息(380a、380b)。例如，该消息可包含处理器正在执行的计算所需的数据，或者可包含用于处理器执行的指令。处理同时开始，因为较近处理器能够根据固定等待时间网络的速度和较近处理器与较远处理器之间的节点数来计算出适当的等待时间(390)。回想一下，本发明的实施例可采用非环形和/或可变等待时间网络，只要发送者能够计算出确认消息的等待时间。那个等待时间是该适当的等候时间390，并且对它的确认就是允许较近和较远处理器同时开始处理消息。

虽然前面描述的流程图集中于具有两个锁步CPU的本发明的实施例的操作，所述CPU发送请求或者从单个设备中接收响应，但是也可以对协议进行操作以允许处理器(或者一组锁步处理器)与冗余锁步设备进行交互作用。例如，为了在存储器中获得或存储数据，自一个处理器的请求、或者来自两个或更多锁步处理器的合并请求可以被指向两个或更多锁步存储器。通过按照图3的流程图，两个存储器可设置来同时执行取出或存储操作，如图4所描述的那样。

首先，处理器(或较近处理器)向较近存储器发送存储器请求(410)。较近存储器接收该请求(420)，分配确认缓冲区(430)，以及向其锁步配对存储器重新传送该请求(440)。该锁步配对接收请求(450)并且返回确认(460)。较近存储器接收确认(470)，并且两个存储器都同时开始取出或存储操作(480a、480b)。锁步配对能够根据固定等待时间网络的速度和确认要到达其目的地所必须经过的节点数来计算出适当的等待时间(490)。

此外，这两个存储器可遵循类似于关于图2所描述的协议以把验证答复发送给请求处理器(一个或多个)。这是在图5中显示：两个存储器都准备响应(510a、510b)。因为两个存储器都以锁步模式来操作，并且如上所述它们同时开始取出或存储操作，所以基本上同时产生响应。较远存储器把它的响应发送给较近的(520)，并且在较近存储器等候(540)的同时，该响应绕着环传播(530)。较近存储器接收响应(550)并且把它与其本身的响应相比较以确定它们是否匹配(560)。如果响应匹配，则向请求处理器发送合并响应(570)。如果存在差别，则产生锁步错误信号(580)以触发错误恢复程序。

前面的讨论把在网络上传送和接收的消息指定了例如“请求”、“响应”、“确认”之类的语义名称。然而应当清楚，“请求”消息不同于“响应”消息仅仅在于请求发生在响应之前，并且引起一些设备或锁步设备组通过发送响应来答复。对于就所涉及的网络而言，请求、响应、以及确认都仅仅是从源节点到目的节点的消息。

图6显示了实现本发明实施例的多处理器系统的一些逻辑部件。CPU内核610和620可以是独立的物理设备或者可以是单个“多核”处理的全部自主或部分自主的部分。一些系统可能具有不止两个物理CPU，在单个处理器中不止两个核、或者不止一个多核处理器。CPU作为网络630的节点那样安装。网络可以在单独的电路中实现，或者可以多核处理器的子部件或者另一个处理器支持电路存在。消息绕着网络传播并且可由目的节点处的设备来移除。节点能够计算至少一些消息的等待时间。这个系统仅包含一个存储器680和一个I/O设备690，并且CPU内核与存储器或设备之间的通信是经由桥接器670来路由的，但是根据本发明的实施例的方法可以由其包含多个存储器和/或设备、具有或不具有桥接设备的系统来使用。

系统包含映射逻辑电路640以确定网络630上节点的相对位置，以及识别两个节点中的哪一个离第三节点比较近。每个处理器610和620都包括请求逻辑电路612、622以在处理器以锁步模式运行时协调从处理器到存储器680或I/O设备690的请求。请求逻辑电路612、622通过从较远处理器向较近处理器发送请求、把该请求与较近处理器产生的请求相比较、以及向目的地发送合并请求来实现参考图2所说明的程序。在包含多个锁步存储器或I/O设备的系统中，那些设备将包含对应于请求逻辑电路612、622的逻辑电路以实现图5的程序，并且允许锁步存储器或I/O设备协调对该处理器(一个或多个)的响应。

处理器610和620还包括响应逻辑电路615、625以协调处理器对来自存储器或I/O设备的响应的处理。响应逻辑电路实现参考图3所描述的程序。对应于响应逻辑电路615、625的逻辑电路也处于系统的存储器和I/O设备中，所述系统具有这些部件的多种冗余例子。

请求验证逻辑电路618、628把从另一个处理器中接收的消息与本地产生消息相比较，并且如果消息不匹配则发出锁步错误信号；以及锁步恢复逻辑电路650允许处理器(或者适当的系统中其它锁步设备)从锁步错误中恢复。

所示的各种逻辑模块可被实现成硬件实现的电路单元、微代码或类似的固件或软件，或者实现成硬件与软件的组合。图6所示系统还包括锁步禁止逻辑电路660以禁止锁步失败信号和其他有利于锁步的逻辑特征。这允许处理器、存储器以及I/O设备作为普通的多处理器系统来操作，其中每个处理器独立地执行它自己的指令流，并且不执行冗余检验。

如图6所示，CPU内核610和620以及网络630和各个逻辑元件，例示于单个、单片、多核CPU设备(参见短划线666)中。在这样的实施例中，多核CPU可直接替换系统中的普通(非锁步)多核CPU。这种替换允许系统以冗余处理模式进行操作以便提高可靠性，或者(当禁止锁步逻辑时)作为正常的多处理器系统。存储器680可以采用纠错码(“ECC”)电路或者其他类似的技术而不是多个冗余单元来实现可比较的可靠性。

本发明的实施例可以是一种机器可读介质，其上存储了使处理器执行如上所述操作的指令。在其他实施例中，该操作可以由包含硬件逻辑电路的特定硬件部件来执行。那些操作可以替换地由可编程计算机元件和常规硬件元件的任意组合来执行。

机器可读介质包含用于以机器(例如计算机)可读的形式来存储或传送信息的任何机构，包括但不限于光盘只读存储器(CD-ROM)、只读存储器(ROM)、随机存取存储器(RAM)、可擦除可编程只读存储器(EPROM)、以及互联网上的传输。

主要通过参考特定实施例并且根据分配给某些硬件和/或软件部件的功能已描述了本发明的应用。然而本领域技术人员应当承认在可确定等待时间网络上建立的锁步电路操作还可以通过软件和硬件来产生，所述软件和硬件可不同于此处所描述那样来分配本发明实施例的功能。这种改变和实现应当理解为落入以下权利要求之中。

Claims (22)

1、一种方法，包括：

产生第一请求；

接收第二请求；

把该第一请求与该第二请求进行比较；以及

如果该第一请求与该第二请求相匹配，则发送合并请求。

2、权利要求1的方法，进一步包括：

如果该第一请求不同于该第二请求，则发出锁步失败信号。

3、权利要求1的方法，其中接收该第二请求包括：

经由固定等待时间互连来接收该第二请求。

4、权利要求1的方法，其中发送合并请求包括：

经由固定等待时间互连来发送该合并请求。

5、权利要求1的方法，其中该第一请求和该第二请求是为了从存储器中获得数据。

6、权利要求1的方法，其中该第一请求和该第二请求是为了与一部件交换数据；以及

其中该部件不同于以锁步进行操作的多个设备。

7、一种方法，包括：

从通信网络上的节点接收消息；

分配缓冲区以保存确认；

向多个设备中的一个发送该消息；

从多个设备中的一个中接收确认；以及

对该消息进行处理。

8、权利要求7的方法，其中分配操作发生在发送操作之前，以及处理操作发生在接收确认之后。

9、权利要求7的方法，其中对该消息进行处理包括至少以下之一：

执行指令；

对数据值进行操作；以及

存储数据值。

10、一种方法，包括：

从多个设备中的一个接收消息；

经由已知等待时间通信介质向多个设备中的一个发送确认；

等候预定的时间周期；以及

对该消息进行处理。

11、权利要求10的方法，其中，该预定的时间周期等于已知等待时间通信介质的等待时间。

12、权利要求10的方法，其中该消息包括来自不同于该多个设备的一个部件的数据。

13、权利要求10的方法，其中对该消息进行处理包括至少以下之一：

执行指令；

对数据值进行操作；以及

存储数据值。

14、一种处理器，包括：

互连网络；

连接于该网络的多个处理器内核，其中第一内核以与第二内核锁步的模式进行操作；

连接于该网络的设备；

映射逻辑电路，确定该第一内核、该第二内核及该设备在网络上的相对位置，以及识别该第一内核与第二内核中哪一个离内该设备较近以及哪一个离该设备较远；

请求逻辑电路，对从该第一内核和第二内核到该设备的请求进行协调；以及

响应逻辑电路，对从该设备到该第一内核和第二内核的响应进行协调。

15、权利要求14的处理器，进一步包括：

请求验证逻辑电路，将来自该第一内核的第一请求与来自该第二内核的第二请求进行比较；其中

如果该第一请求不与该第二请求相匹配，则该请求验证逻辑电路将发出锁步失败信号。

16、权利要求15的处理器，进一步包括：

锁步禁止逻辑电路，用于禁止锁步逻辑元件。

17、权利要求14的处理器，进一步包括：

锁步恢复逻辑电路，用于使该第一内核与该第二内核同步。

18、权利要求14的处理器，其中请求逻辑电路用于：

从该较远的内核向该较近的内核发送第一请求；

把该第一请求与该较近内核的第二请求进行比较；以及

从该较近内核向该设备发送合并请求。

19、权利要求14的处理器，其中响应逻辑电路将：

在该较近内核接收响应；

在该较近内核分配确认缓冲区；

向该较远内核发送该响应；以及

延迟响应处理直到从该较远内核接收到确认。

20、一种系统，包括：

多个中央处理单元(CPU)；

存储器；以及

用于在CPU与存储器之间承载数据的网络；其中

来自该存储器的消息经由网络到达第一CPU；

该第一CPU经由网络向第二CPU发送该消息；

该第二CPU经由网络向该第一CPU发送确认；以及

该第二CPU在发送该确认之后的预定时间周期开始对该消息进行处理。

21、权利要求20的系统，其中该第一CPU在收到该确认之后开始对该消息进行处理。

22、权利要求20的系统，其中该预定的时间周期等于该确认经由网络从该第二CPU传到该第一CPU的等待时间。

Images