通信开销为零的机群系统全局逻辑时钟.pdf

高技术通讯2004·增刊 通信开销为零的机群系统全局逻辑时钟① 刘 建⑦余宏亮 沈美明 郑纬民 (清华大学计算机科学与技术系高性能计算技术研究所 北京100084) 摘 要 机群系统没有统一的全局时钟，逻辑时钟是机群系统中实现事件排序的主要方 法。经典逻辑时钟实现时，采取时钟信息和发送消息捆绑传送(piggyback)的方法，增加了 额外的通信开销。提出的基于相关计数器的机群系统逻辑时钟，采用在本地记录相关计 数器的方法，避免了时钟信息的额外发送。给出了偏序关系提取算法和逻辑时钟维护规 则，并用一个简单的例子说明算法和规则的具体应用。 关键词机群系统，全局时钟，逻辑时钟，偏序关系 ae2 个逻辑时钟具有一致性，如果映射规则满足：el 0 引言 具有强时钟一致性。 机群系统中，计算由相互通信的异步进程协同 具体说来，要构造一个逻辑时钟系统，需要做两 完成，这些异步进程通常分布在不同的机器上，每个 件事：一是要确定每个进程上用什么样的数据结构 机器都有自己的时钟，对整个系统而言，不存在全局 来表示逻辑时间(包括定义关系7c)，二是要制定一 时钟，也没有硬件机制让所有机器的局部时钟保持 组规则来维护逻辑时钟，使得它满足前面所述的一 同步。由于各个机器的局部时钟不一致，各事件发 致性条件。 生的时间无法进行比较，以确定先后顺序。 每个进程Pi上表示逻辑时间的数据结构应该 根据不同的需要，人们从两条途径出发试图解 包含两方面的内容：一方面，它应该包含一个局部的 决这个问题。一条途径是对物理时钟进行软件同 逻辑时钟LCi，用以表示本进程中事件发生的顺序； 步，使得它们之间的偏差限制在一个可以接受的范 另一方面，它还包含一个全局的逻辑时钟GCi，表示 围之内，在需要具体时间值的时候，通常采用这种方 从该进程角度看来的全局逻辑时间。通常LCi是 法；另一条途径是采用逻辑时钟，逻辑时钟往往不表 GCi的一部分。逻辑时钟的维护规则也包括局部逻 示具体的时间值，但是可以表示不同进程中事件之 辑时钟的维护规则和全局逻辑时钟的维护规则，我 间的先后顺序，在对时间值不敏感，但要保持事件顺 们分别称之为L规则和G规则。 序的时候，通常采用逻辑时钟。 (1)L规贝Ij描述：一个进程在产生一个事件时 如何修改局部逻辑时钟，以保证进程内部事件之间 l 机群系统的逻辑时钟 的时间顺序； (2)G规则描述：当一个进程与另一个进程进 逻辑时钟不对事件发生的时间进行量化，而是 行通信时，如何修改本进程和接收进程的全局逻辑 对事件之间的因果关系进行量化。 时钟，以保证时钟一致性或强一致性，通常是发送方 把自己的与全局逻辑时间有关的信息和消息一起发 逻辑时钟c是一个从事件集合∑={el， e2…．，e／t}到时间域T={c1，c2…．，饥}的单值映给接收方，后者则根据这些信息作相应的处理。 射C：ci=C(ei)，取不同的F和不同的映射规则C， 目前，有4种逻辑时钟：标量时钟…1，区间时 便可得到不同的逻辑时钟系统。