基于向量时钟的动态自适应同步策略研究*

王艺遥，齐和平，李学艳，毛玉辉，柴 彪

（北方自动控制技术研究所，太原 030006）

0 引言

分布式仿真的主要思想是将单个仿真程序并行地在多个处理器上并发运行，提高并行性以打破仿真顺序中时间和空间的局限，满足仿真性能要求。分布式仿真致力于提高系统并发性，不可避免地会因为网络延迟、时钟不一致、节点掉线等各种问题造成因果顺序错乱。在理想条件下，仿真事件推进和通信的时延应当与实际系统事件发生的时延一致，但是实际仿真过程中，信息传输延迟并不是稳定的，通常不可预测，且整个仿真系统的各个组成部分不能确保完全一致的系统时间，因此，可能出现因果紊乱的情况。

为解决这一问题，保证仿真结果的真实性、可靠性与可读性，需要对并行仿真系统做因果关系约束。并行仿真系统通过多个带有时间戳的逻辑进程完成消息通信，处理器的性能和复杂的网络架构造成了消息通信的随机性，需要通过消息传输策略维护并发事件之间的逻辑关系，这种方法被称为同步策略。

1 基本原理

典型的同步策略有保守策略和乐观策略。最早的保守策略由Chandy、Misra 和Bryant 3 人提出，因此，称为CMB 协议。在CMB 协议中，各个逻辑进程的事件都带有时间戳，每个消息都需要保证时间戳不会小于本地局部仿真时间，才可执行当前事件。由此，所有事件都会严格按照顺序执行，整个仿真系统的因果性得到保证。由于保守策略对时序的严格要求，需要不断判断事件是否可以执行，若有一个处理器上事件为空，逻辑进程将等待，直到事件不为空，这可能导致循环等待，进而产生死锁。解决死锁的方法有死锁恢复法和死锁避免法，死锁恢复法需要系统有死锁检测机制，当产生死锁时，逻辑进程检测到死锁并打开死锁，执行事件；死锁避免法的一个典型案例为空消息法，逻辑进程不会发送小于空消息时间戳的消息，事件执行完成后，逻辑进程会发送一个空消息，来保证事件的正常执行，空消息的时间戳一般为当前事件结束时间加一较小常量。

乐观策略与保守策略相反，它并不严格遵守因果逻辑，而是在因果错误发生后，采用回退机制来修复错误，典型的乐观策略是由Jefferson 和Sowizral提出的Time Warp 机制。各处理器上的逻辑进程执行本地事件，执行完毕后向其他逻辑进程发送事件消息，当某逻辑进程收到时间戳小于本身事件时间戳的消息A 时，发生了因果错误，该逻辑进程需要将事件回退至消息A 的时间戳前，并需要向其他逻辑进程发送回退事件的逆消息，以撤销事件执行时发送的消息。由此可见，为保证整个仿真系统的因果性，每个处理器需要记录逻辑进程执行过的事件，否则难以精确回退，这需要占用大量资源存储信息。为此，需要给整个系统设定一个全局虚拟时间，超过这一时间的事件信息认定不会回退，即可删除这一时间前的事件，回收内存。乐观策略的回退机制会占用一定系统资源导致效率下降，因此，考虑对乐观策略作一定限制，根据限制方法不同，产生了基于窗口的策略、基于惩罚的策略、基于概率的策略等。同时，也可以对回退机制进行限制，如惰性取消策略，在产生因果错误后，逻辑进程回退后先进行模拟，将模拟产生的消息与原发送消息对比，若二者不同再发送逆消息，这有利于提高效率。保守策略与乐观策略的对比如表1 所示。

表1 保守策略与乐观策略对比

2 动态自适应策略

以上策略都是静态策略，设定好后难以根据仿真系统状态变化实时调整，动态自适应策略通过动态调整参数解决了问题，其性能曲线如图1 所示。图1 中实线为执行时间，虚线为资源消耗，曲线①由于极端保守，阻塞严重，资源消耗增加；曲线②由于过度乐观，不断产生回退，资源消耗增大。

图1 动态自适应策略性能曲线

动态自适应策略分为两类，一类是基于局部状态的策略，如自适应有界时间窗（adaptive bounded time window，ABTW）。这一策略的思想是限定一个时间段，仿真系统在这一时间段内按照乐观策略执行事件，借助时间窗来控制乐观策略，防止回退次数过多，增加系统资源开销。时间窗的大小根据系统实际情况动态调整，调整的依据是逻辑进程的有用工作。有用工作是反映逻辑进程所做有效工作的函数，其参数有执行任务率、任务重新执行次数、平均重新执行长度以及发送的反消息数。

另一类是基于全局状态的策略，这一策略的典型代表是近于完美状态信息算法。算法实现依靠获取的近于完美的状态信息，这些信息来自完整的仿真系统。算法定义了错误潜在参数，每个逻辑进程都有一个对应的错误潜在参数，在弹性时间算法中，错误潜在参数指逻辑进程的下一个待处理事件的时间戳，与全球虚拟时间设定的最早未处理时间戳下限之间的差值，在事件运行过程中加入等待时间，等待时间与错误潜在参数有一定函数关系，错误潜在参数越大，等待时间越长，进而控制了逻辑进程的乐观策略。

3 基于向量时钟的自适应有界时间窗算法

以上两类策略中，基于全局状态的策略的状态信息过于冗杂，带来了较大资源开销，因此，考虑基于局部状态的策略。

移动时间窗算法（moving time window，MTW）是限制乐观策略的算法，其主要思想是对逻辑进程仿真时间超过其他逻辑进程仿真时间的上限进行设置，在上限前，系统按照乐观策略进行仿真，某逻辑进程达到上限时，便对其进行阻塞，直到其他逻辑进程全部达到上限。时间窗的下限为全局虚拟时间（global virtual time，GVT），时间窗上限为GVT+W，W 为设定的时间窗值，随着全局虚拟时间推进，时间窗也在推进，但逻辑进程不能超过时间窗上限，由此限制了各逻辑进程的推进，避免发生因果错误时产生过多回退。但时间窗值设定好后无法在运行中修改，且增加了各逻辑进程间同步全局虚拟时间的开销。

据此提出了基于向量时钟的动态自适应有界时间窗算法，算法思路如下。

3.1 向量时钟

对整个仿真系统建模如下：G=（V，E，M）表示整个仿真系统的通信部分，其中，V 表示所有逻辑进程（logical process，LP）的集合，E 表示所有逻辑进程间信道的集合，即所有的通信连接，M 表示所有消息的集合。对于消息m和m，若两者从同一个节点发出，且m发出后的下一条消息为m，或两者从不同节点发出，且m是m被接收后的下一个消息，称m和m存在因果关系，可记为m→m，即m是事件的原因，m是事件的结果。显然因果关系是传递，非对称、不可自反的。记S（m，u，v）表示节点u 通过信道（u，v）发送消息m，R（m，u，v）表示节点v 通过信道（u，v）接收消息m。显然S（m，u，v）对R（m，u，v）是发生在先的，可记为S（m，u，v）＜R（m，u，v）。则因果异常可表示为：若m→m，但R（m，c，v）＜R（m，c，v），其中，c 表示任意节点。将因果异常记为A（m，m，v），其中，m→m，v 为接收节点。记（u，v）为节点u 到节点v 的直接连接，［u，v］为节点u 到节点v 的间接连接。由此可知，当A（m，m，v），存在［u，v］。

分布式仿真中没有内在的物理时钟，只能对此进行近似，在逻辑进程中，可以通过事件因果关系确定事件顺序，各进程之间的时序共享则通过逻辑时钟实现。逻辑时钟（logical clock，LC）由Lamport 提出，每个逻辑进程LP有一个逻辑时钟LC，将逻辑进程发出的消息记为一个三元组（m，LC，i），即为消息内容，逻辑时钟，进程序号。逻辑时钟的更新原理如下。

在发生事件前，逻辑进程LP更新逻辑时钟LC=LC+x，x 为根据实际情况设置的定值，当逻辑进程LP收到其他逻辑进程LP的消息（m，LC，j）时，根据LC=max（LC，LC）+x 进行更新。这种逻辑时钟是线性的，可以解决互斥问题，但其不具有强一致性，在高并发的情况下不够完备。为弥补逻辑时钟的缺点，提出向量时钟（vector clock，VC）的观点，使用n 维整数向量表示时间，每个逻辑进程LP关联一个向量LC［1，…，n］，LC［i］表示逻辑进程本身的信息，LC［j］表示逻辑进程i 关于逻辑进程j 的信息，由此LC［1，…，n］就表明了逻辑进程i 关于全局的信息。由于逻辑进程LP推进向量时钟的第i 个分量，即逻辑进程LP总是对向量时钟第i 个分量有最精确的了解，则对逻辑进程LP恒有LC［j］≤LC［i］。

向量时钟的更新规则为：LC［i］初始值为0，在发送和提交消息前增加时钟值，由此可以保证在同一逻辑进程，有因果关系的消息的时间单调递增。在事件发生前，更新LC［i］=LC［i］+x，当逻辑进程LP接收到消息（m，LC，j）时，消息的向量时间和逻辑进程的向量时间具有相同的结构和意义。因此，可以进行比较，为确定消息是否会引发因果异常，仅需考虑LC［k］和LC［k］，更新LC［k］=max（LC［k］，LC［k］），LC［i］=LC［i］+x。根据这一更新规则可知，由逻辑进程发送的消息在逻辑进程被接收时，若LC［j］≤LC［j］，则存在消息m已被接收提交，且有m→m，A（m，m，i）。使用向量时钟，可以降低消息之间的关联性，减少回退消息的数量，降低回退对仿真系统推进的影响。向量时钟由各节点的因果时间组成，对于监控节点，其向量时钟的各个向量只是表示其对系统其他节点的观测，不存在监控节点的本地时钟。仿真运行中，不需要比较各个消息的时间序，只需要将消息的时间与接收节点的时间比较，即可确定这一消息是否可以直接发送给目标节点。向量时钟的更新规则如图2 所示。

图2 向量时钟更新规则

3.2 算法周期运行

本文提出的基于向量时钟的动态自适应动态有界时间窗算法，简记为ABTW-VC 算法，这一算法以周期循环方式推进仿真运行，每个周期运行如下：

1）每个节点存在两个队列，一个先进先出队列，队列中的消息可以直接发送，即将消息放在先进先出队列中，就认为其可以发送给接收节点了。另一个是等待队列，用于存储先接收的消息，这些消息一般是结果信息，如果结果信息先于原因信息发送，则产生因果错误。因此，只有先进先出队列的消息可以发送，这个过程的流程图如图3 所示。

图3 消息发送流程图

2）当节点收到下一周期开始标志后，停止当前推进，向其他节点发送下一周期开始标志。

3）将节点先进先出队列中的消息按时间序发送，将等待队列中的消息按时序排列，判断是否所有节点都收到了下一周期开始标志，若收到，计算全局虚拟时钟，同步系统时间，等待下一周期执行。

4）开始下一周期。如图3 所示，每个节点要发送消息时，首先判断消息时间是否可能产生因果错误，如果不会产生因果错误，将消息送入先进先出队列，实时发送消息给其他节点；如果可能会发生因果错误，需要确认可能发生因果错误的原因消息，结果消息和消息发生的路径，然后在仿真运行过程中对相关路径进行监控。当收到结果消息时，接收节点判断消息时间与本身向量时钟的关系，如果结果消息先于原因消息，则结果消息在等待队列中等待，直到原因消息发出才进入先入先出队列。对于其他路径的消息，认为其在本节点不会发生因果错误，可直接提交，消息会直接进入先入先出队列，节点的向量时钟也向前推进，然后根据新向量时钟检验等待队列中的消息，由此保证系统的因果性。

这一过程的算法实现如下：

由此ABTW-VC 算法运行完毕，算法流程图如图4 所示。

图4 ABTW-VC 算法流程图

4 实验

本文采用2 台计算机模拟分布式仿真系统，一台计算机模拟服务器，一台计算机用程序模拟100个节点作为仿真成员，每个节点按照一定频率发送一定数量的消息模拟服务器与仿真成员之间的信息传输。消息设定为每发送一条原因消息，发送一条与之相对的结果消息，消息发送频率设定为每个节点每100 ms 发送一条消息。除本算法外，采用Time Warp 乐观策略，CMB 保守策略进行比对，结果如图5 所示。

图5 3 种算法结果图

由图5 可知，虽然在消息数量较少时，3 种算法的仿真时间十分接近，但随着仿真系统消息数量的增加，Time Warp 乐观策略和CMB 保守策略因存在缺陷而产生阻塞，ABTW-VC 算法仍可流畅运行，且运行时间短于另外两种策略。在发送100 万条消息时，本算法的运行时间比另外两者分别缩短了16.59%，24.41%。

5 结论

本文提出了基于向量时钟的自适应有界时间窗算法，在传输消息较多的仿真系统中，经验证可以减少系统运行时间，避免因果错误。采用这一算法虽然有优点，但也存在一些问题。从性能角度考虑，这一算法需要各逻辑进程大量记录事件时间信息，若仿真规模过大，事件发生过密集，存储事件时间就会占用较多存储资源，但不影响系统运行性能，可在指挥控制、火力控制等工程中应用推广。