时间触发分布式实时系统容错时钟同步算法设计

关博文，朱长昊，张凤登

（上海理工大学光电信息与计算机工程学院，上海 200093）

0 引言

随着计算机系统以及大规模集成电路的不断发展，分布式系统越来越多地应用在人们的日常生活及工业生产中［1-2］。分布式系统从网络类型上可分为时间触发（Time Trigger，TT）系统和事件触发（Event Trigger，ET）系统［3］。事件触发系统基于事件的发生触发动作，时间触发系统基于既定的时刻表或事件调度器的调度，在某个精确时刻触发动作。为保证系统的实时性以及应对突发事件的鲁棒性，通常会同时采用这两种结构，如FlexRay 与Ethernet 网络等。从时域上分布式系统又可分为实时系统与非实时系统，实时系统又可进一步分为强实时系统和弱实时系统［4］。本文所研究的是在时间触发分布式实时系统环境下的时钟同步算法。

在时间触发分布式实时系统中，各个节点通常需要大致同时执行某些动作。在这样的系统中，每个处理器通常都拥有自己的独立物理时钟，它们相对于实时都具有一定的偏移率［5-6］。即使让所有节点的物理时钟同时启动，随着时间的推移，这些节点上的物理时钟也会偏移实时时间。因此，时钟必须定期重新同步。在进行设计时钟同步算法时，不仅要考虑因时钟老化等物理因素引起的时钟不同步问题，还要考虑节点的时钟出现故障或者节点本身出现故障的问题。本文将节点和链路故障进行简化，统一假设为节点的时钟故障问题［7］。此外，还要容忍系统中的节点为拜占庭将军问题时的情况。……