（计算机科学与技术专业论文）hlarti时间管理服务的研究以及乐观时间推进机制的实现.pdf

北京邮l 扎大学硕士研究生学位论文h l a r t 时间管理服务的研究与乐观时间推进机制的实现 h l a r t l 时间管理服务的研究与乐观时间推进机制的实现 摘要 时间管理是h l a r t i 中的核心内容之一，它的基本原理和关键算 法的研究是分布式仿真领域的热点问题。其中，按照h l a 规范所实现 的乐观推进服务也一直足分布式仿真领域的难点问题。 本文对时间管理的两个关键变量：前瞻量l o o k a h e a d 和时戳下限 值l b t s 进行剖析研究。从前瞻量的引入开始，到不同类型仿真中的 设置方法，以及在r t i 软件中如何实现更改前瞻量服务等，还研究厂 零前瞻量的意义以及不同t t l a 服务在使用零前瞻量时的差别。本文研 究了早期的l b t s 算法，并探讨了它们的问题所在，分析了目前流行 f r e d e r i c k 算法及其不足之处；探索了死锁的规律性。 本文分析了现有的r t i 体系结构，提出本系统所使用的体系结 构，并说明采用该结构的原因和该结构所特有的优越性。 本文在研究p d e s 和h l a 两种乐观推进机制的基础上，根据实验 室的层次化分布式的r t i 系统结构，提出了一套完整的实现乐观时间 推进的解决方案，并详细描述了其中主要的数据结构、算法和接口。 关键词 r t i 时间管理前瞻量时间戳下限乐观时间推进机制死锁 北京邮电大学硕士研究生学位论文h l a r t i 时间管理服务的研究与乐观时间推进机制的实现 r e s e a r c h0 ft i m em a n a g e m 匣n ts e r v i c ei nh l a i u i a n di m p l e m e n t a t i o no fo p t i m i s t i ct i m e a d 、，a n c i n gm e c h a n i s m a b s t r a c t t i m e m a n a g e m e n ts e r v i c e i st h ec r i t i c a l t e c h n o l o g y i nh l a r t i t h e i m p l e m e n t a t i o no ft i m ea d v a n c i n gm e c h a n i s ma c c o r d i n gt oh l ai sa l s oap r o b l e mi n m o d e l i n ga n ds i m u l a t i o na r e a t h i sp a p e rs t u d i e sh o wt os e tt h ev a l u eo fl o o k a h e a di nd i f f e r e n ts i m u l a t i o n sa n d h o wt or e a l i z et h em o d i f i c a t i o no fl o o k a h e a di nr t i i ta l s os t u d i e st h em e a n i n go f z e r ol o o k a h e a da n dt h ed i f f e r e n c eo f d i f f e r e n t h l as e r v i c e st ou s ez e r o l o o k a h e a dt h i sp a p e ra l s os t u d i e sf o r m e ra l g o r i t h m so fl b t s ，a n a l y z e st h es h o r t a g e o ff r e d e r i c ha l g o r i t h ma n ds t u d i e st h er u l e so fd e a d l o c k t h i sp a p e ra n a l y z e sp r e s e n tr t ia r c h i t e c t u r e ，p r o p o s e st h ea r c h i t e c t u r ew eu s e a n de x p l a i n sw h yw eu s ei ta n di t sa d v a n t a g e s t h i sp a p e ra n a l y z e sa n dc o m p a r e st h et w od i f f e r e n c e sb e t w e e no p t i m i s t i c a d v a n c i n gm e c h a n i s m si np d e sa n dh l a a c c o r d i n gt ot h er t ia r c h i t e c t u r eo f o u r l a b ，t h i sp a p e rp r o p o s e sas o l u t i o no fr e a l i z i n gt h eo p t i m i s t i ca d v a n c i n gm e c h a n i s m a n dd e s c r i b e st h ek e yd a t as t r u c t u r e s ，a l g o r i t h m sa n di n t e r f a c e so fi t 砭e yw o r d s t i m em a n a g e m e n ts e r v i c er t il o o k a h e a dl b t s d e a d l o c h o p t i m i s t i c a d v a n c i n gm e c h a n i s m i i 北京邮电大学硕士研究生学位论文h l a r t i 时间管理服务的研究与乐观时间推进机制的实现 图表索弓 图2 一lh l a 仿真系统的层次结拘 图2 2h l a 仿真的逻辑结构 图2 3 联邦成员之间通过r t i 进行交互 表2 1 时问管理服务及其相应的功能 表2 2 发送消息的类型 表2 3 接收消息的类型一 表2 4 联邦成员在各个状态接收和发送消息的情况 图3 - 1 进程a 初始状态 图3 2 进程a 处理完消息5 之后的状态 图3 3 三个进程处于死锁状态 图3 - 4 基于空消息的死锁解除机制 图3 5 前瞻量为l 的示意图 图3 6l o o k a h e a d = ol o o k a h e a d o 图3 7 陡减前瞻量的后果 圈4 1l e t s 与l i t s 的区别 图4 2 基于n e r n e r a 的时问仿真 图4 3 基于y e r n e r a 的串行仿真 图4 - 4 采用p r e d er 1c k 算法的成员的n e r 推进图 图4 5f r e d e r ic k 算法的死锁问题 图4 - 6 死锁示意图 图5 1 系统模型 图6 1 保守联邦成员的推进方式 图6 2 “过时”消息到达时的进程状态 图6 - 3 无；十突不需要回滚进程状态 圈6 - 4 回滚后的进程状态 图6 5 回滚后但没有引起其他进程撤销发送的消息 表6 一l 两种乐观机制的比较 图6 - 6r t is e r v er 程序结构示意图 图6 7l r c 鲒构示意图 图6 8d o c k er 模块示意图 图6 9 时间管理系统模型示意图 固6 一l0l r c 的结构示意图 图6 i ll s 的结构。 图7 1m a 口数据结构示意图 v j幢u掩侣旧悖毖卯弛弛弘粥”们帖卯钉牿如弘巧卯卯强酊 独创性( 或创新性) 声明 本人声明所呈交的论文足本人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中特别加以标注和致 射中所罗列的内容以外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过的材 判。与我一同丁作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢 意。， 申请学位论文与资料若有不实之处， 本人签名：蒸勉 本人承担一切相关责任。 日期：j 妒吐j 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的仓部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：叁垒起日期：一型：! ：兰! 导师签名：聋乌z 乓一日期：口乱玉型l 一 北京州电大学硕士研究生学位论文h l m r t i 时间管理服务的研宄与乐删时间推进机制的实珊 h l a r t i 时间管理服务的研究与乐观时间推进机制的实现 第一章研究背景及工作内容 1 1 研究背景 随着仿真应用领域的拓宽，计算机仿真需要解决的问题也越来越复杂，许多 问题单靠单个仿真系统己无法解决，必须依靠多个仿真系统联合协同仿真。因此， 进入九十年代后分布交互仿真成为仿真技术发展的重点。与单个仿真系统仿真相 比，分布式仿真的关键问题是多个仿真系统间的互操作问题。分布式仿真技术经 历了s i m n e t ，d i s a l s p 等阶段，到目前已经发展到高层体系结构( h l a ，h i g h l e v e la r c h i t e c t u r e ) 。 1 9 8 3 年美国国防韶高级项目研究计划局( d a r p a ) 和美国陆军共同制定了 一个合作研究计划即s i m n e t ( s i m u l a t i o nn e t w o r k i n g ) 研究计划，其研究的主 要目的是将分敞在各地的多个地面车辆仿真器使用计算机网络连接起来，进行各 种复杂任务的训练，演示，并验证作战仿真和作战演习。从而形成了s i m n e t 分布仿真概念，第一次将多种仿真应用集中到同一个时空环境中。进而美国军方 和工业界在s i m n e t 的基础上，共同倡导并建立了异构网络互连的分布式交互 仿真( d i sd i s t r i b u t e di n t e r a c t i v es i m u l a t i o n ) 系统，其目的是将不同时期的仿 真技术，不同厂家的仿真产品和不同用途的仿真平台集成在一起，可以互相交互， 由一系列的应用协议与通信服务标准，推荐的演练策略和相关文档来确保互操作 能力。d i s 的基础是协议数据单元用来通过网络发送和接收数据。d i s 标准具 有定义简洁明了，容错性能好等优点，缺点是使用固定的p d u 格式使得d i s 灵 活性比较差，网络中冗余数据比较多，并且t t 。对军事领域，应用范围受到限制。 在d s 发展的同时，d a r p a 发起了一个聚合式分布式作战仿真的实验，随 后m i f r e 提出了聚合缴仿真协议( a l s p ， a g g r e s s i v e l e v e ls i m u l a t i o n p r o t o c 0 1 ) 。a l s p 的目标是使现有得多个聚合级作战仿真应用可以通过局域网或 广域网相互交互。在概念上，每个仿真控制其自身对象，并且共享有关自身与其 它仿真的信息。a l s p 吸取了s i m n e t 技术中一些原则，比如没有中心节点，地 理分布，自主属性和基于消息的协议等，同时发展了系列聚合级仿真所需要的技 术：时问管理、数据管理和体系结构。 s i m n e t ，d i s ，a l s p 都是同种功能仿真应用互联，只有有限的互操作性，不 能满足越来越复杂的作战仿真需求。为此，美国国防部9 5 年1 0 月发布的建模与 北京邮电大学硕士研究生学位论文h l a r t ( 时间管理服务的研究与乐现时间推进机制的实现 仿真主计划，决定在国防部范围内使用一个通用的仿真技术框架来保证国防部范 围内的各种仿真应用之间的互操作性，技术框架的核心是高层体系结构( h l a ) ， 其主要目的是促进仿真应用的互操作性和提高仿真资源的可重用性。1 9 9 6 年9 月，美国国防部建模和仿真办公室d m s o 正式颁布了h l a 标准1 0 ，并在随后 迅速推出了其后续修订版本，9 8 年，i e e e 通过了关于h l a 的标准草案：皿e e s t a n d a r d sp 1 5 1 6 d 1 h i g h l e v e la r c h i t e c t u r e ( d r a f t ) ，并在2 0 0 0 年9 月正式接纳为 标准。现在h l a f r t i 系统的研究和应用已经不仅仅限于军事仿真领域，其他领 域也有着广泛的应用前景。 高层体系结构( h l a ) 引入了时间管理服务，并支持多种时间管理策略。在仿 真开发过程中，时间管理服务是可选服务。但是对于大多数分布仿真系统来说， 时间却是它们的核心概念。为了保证仿真结果和事件之间因果关系的正确性，必 须引入时间管理服务。这是因为，联邦在运行时，可以看作是通过运行时支撑环 境( r t i ) 来传递消息的一组成员的集合。成员向r t i 发送消息，由r t i 将消息传 送给感兴趣的成员。在理想情况下，模型计算和消息传递的时延等于实际系统中 相应的时延。但是在实际情况下，通常两者的时延是不一致的，这将导致仿真结 果的不确定性，不可再现性，甚至出现严重偏离真实世界的错误。 而时间管理的目标就是要减少上述偏差的产生或降低此类偏差带来的不良 影响，主要任务是使仿真世界中事件发生的顺序与现实世界中事件发生的顺序一 致，保证各成员能以同样的顺序观察到事件的发生，并能协澜它们之间相关的活 动。时间管理主要面对联邦执行时的两个问题：是事件应该发生而没有发生： 二是事件没有按顺序发生。h l a 时间管理主要确保能完全解决第二个问题，即 确保事件发生的顺序或者放松对顺序的要求而不影响仿真效果。 h i ，a 提出了保守时间推进和乐观时间推进两种方式，并支持这两种方式的混 合推进。 保守推进机制要求r t i ( r u n t i m ei n f r a s t r u c t u r e ) 必, 须严格保证联邦成员( f e d e r a t e ) 按照时戳顺序大小接收消息，因此，联邦成员在推进的过程中永远不会产生冲突。 然而，即使两个消息的时戳不同，但是它们之间却未必存在因果关系；如果两个 连续的消息不存在因果关系，却不定需要按照时标序大小来调度它们。因此， 保守推进机制以“时戳序”来确定“因果序”是种过度“保守”的消息处理机 制。鉴于保守推进机制的不足，h l a 引入了乐观推进机制。 在乐观推进机制下，联邦成员总是“乐观地”认为下一个消息的到来不会与 当前的系统状态产生冲突，然而这种“赌博”不可避免地会存在一定的风险，风险 的程度依赖于特定的应用。一旦出现冲突，乐观联邦成员需要通过“回滚” ( r o l l b a c k ) 机制来解决这种冲突。乐观机制在处理器的设计、操作系统中的页面调 垄室些皇叁兰堡主堕壅竺兰堡堡垄h l a r t i 时间管理服务的研究与乐观时间推进机制的实现 度、分布式数据库中的事务处理以及并行编译等领域都有很重要的应用。 正确理解乐观推进机制的基本原理，并按照高层体系结构h l a ( h i g hl e v e l a r c h i t e c m r e ) 规范实现r t i ( n m t i m ei n f r a s t r u c t u r e ) 的乐观推进服务一直是分布式 仿真领域关注的难点问题。 1 2 当前的研究状况 2 0 多年来，国内外一直关注乐观推进技术的研究。但国外大多在p d e s 领域 进行研究，即使在h l a 标准发布之后，也很少看到针对h l a 乐观推进机制的 研究文章。在p d e s 领域，研究的是纯乐观推进技术，与保守推进技术基本不相 关；而在h l a 领域，却存在保守推进机制和乐观推进机制的协同问题。自从h l a 标准公布之后，国内的众多科研单位就展开了二a 技术的研究和r t i 软件的丌 发。时间管理服务一直是r t i 开发的重点和难点，特别是在r t i 中如何实现乐观 推进服务方面。而理解h l a 规范并在r t i 中实现乐观推进服务正是本论文所要 研究和解决的问题。 1 3 研究目标 本论文主要目标是重点分析三种r t i 平台实现的体系结构模型，以及存此基 础上时间管理模块的结构；对l o o k a b e a d 的设置和l 1 3 t s 的计算进行研究；并根 据对实验室最终确定的层次化、分布式的仿真运行时支撑环境( r t i ) 分析研究的 基础上，对r t i 时间管理服务中的乐观时间推进进行设计和实现。 1 ，4 工作内容和成果 基于上述研究目标，本文主要进行了以下几个方面的工作： 分析三种r t j 平台实现的体系结构模型，提出我们的体系结构。 研究分析分布式r t f 和在此结构下时间管理服务模块的体系结构。 针对时问管理中的乐观时间推进机制，提出自己的解决方案。 没计实现乐观刚间推进服务中的主要接口。 针对r t i 时间管理服务实现过程中的难点l b t s 和l o o k a h e a d 的计算进行分 折和研究。 1 5 论文的章节安排 本文主要有四个方面的内容。首先是对h l a r t | 一般知识的介绍，。然后对 h l a 中时间管理服务的相关概念作了详细的介绍。包括时间的概念，时间管理 北京邮电大学硕士研究生学位论文h l a r t i 时间管理服务的研究与乐观时间推进机制的实现 中的消息顺序，时间管理的设置策略，时间推进机制等。 其次我们在第三章中重点研究了时间管理服务中的重要变量：前瞻量 0 - o o k a h e a d ) ，从前瞻量的首次出现和第一个定义开始，到如何不同类型仿真中 的设置前瞻量，以及在r t i 软件中如何实现更改前瞻量服务等，还研究了零前瞻 量的意义以及不同h l a 服务在使用零前瞻量时的差别。 再次我们在第四章中重点研究了时间管理服务中的另一个重要变量：时间戳 下5 艮( l b t s ) ，本文分析了早期的l b t s 算法，着重剖析了目前流行f r e d e r i c k 算 法的不足之处；探索并证明了死锁的规律性。 最后，在经过大量的阅读和比较研究后，重点分析三种r t i 平台实现的体系 结构模型，提出我们的体系结构并分析在三种平台下时间管理模块的结构。根据 实验室的层次化分布式r t i 系统结构和消息的传递机制，提出了一套能和保守的 时间推进相协调的完整的实现乐观时间推进的解决方案，并详细描述了其中主要 的数据结构，算法和接口。 北京邮电大学硕士研究生学位论文h l a r t i 时间管理服务的研究与乐观时问推进机制的实现 第二章h l a 及r ti 时间管理服务 21h l a h l a 就是在体系结构上建立一个框架，它能尽量涵盖建模与仿真( m & s ) 领域中所涉及的各种不同类型的仿真系统，并利用它们之问的互操作性和重用 性。同时能利用不断发展的新技术，来满足复杂大系统的仿真需求。 h l a 按照面向对象的思想和方法来构建仿真系统，它是在面向对象分析与设 计的基础上划分仿真成员，构建仿真联邦。图2 1 展示了h l a 仿真系统的层次 结构。 图2 - ! h l a 仿真系统的层次结构 在基于h l a 的仿真系统中，联邦( f e d e r a t i o n ) 是指用于达到某一特定仿真 目的的分布仿真系统，它由若干个相互作用的联邦成员构成。所有参与仿真运行 的j 、i 用程序都可以成为联邦成员。联邦成员由若干相瓦作用的对象构成，h l a 定义了联邦和联邦成员构建、拙述和交互的基本准则和方法。需要说明的是，联 邦可以作为一个成员加入一个更大的联邦中。 211h l a 的主要特点 h l a 是一个开放的、支持面向对象的体系结构。它最显著的特点就是通过提 供通用的、相对独立的支撑服务程序，将应用层同底层支撑环境分离，即将具体 的仿真功能实现、仿真运行管理和底层通信三者分开，隐蔽各自的实现细节。从 而可以使各部分相对独立地进行开发，最大程度的利用各自领域的最新技术来实 现标准的功能和服务，适应新技术的发展。 h l a 既不规定对象由什么构成( 对象是被仿真的实际物体，例如坦克和导 北京邮电大学硕士研究生学位论文h l a r t i 时间管理服务的研究与乐观时阃推进机制的实现 弹) ，也不规定对象交互的规则，它考虑的重点是如何实现成员之间的互操作， 即如何将已有的联邦成员集成为联邦。 然而，h l a 的强大和灵活也有它的弱点，除非仿真系统中所有的联邦成员对 于一个单一的联邦对象模型( f o m ，f e d e r a t i o no b j e c tm o d e l ) 来说是一致的， 否则，即使联邦成员与h l a 是一致的，它们也不能互操作。 212h l a 的基本思想 h l a 主要考虑在联邦成员的基础上如何进行联邦集成，即如何设计联邦成员 间的交互以达到仿真的目的。正因为如此，所以把它称为“高级体系结构”。h l a 的基本思想就是采用面向对象的方法来设计、开发和实现仿真系统的对象模型 ( o m ，o b j e c tm o d e l ) ，以获得仿真联邦的高层次的互操作和重用。 在h l a 中，互操作定义为一个成员能向其他成员提供服务和接受其他成员 的服务。有成员构建联邦的关键是要求各成员之间可以互操作， 虽然h l a 本身并不能完全实现互操作，但它定义了实现联邦成员互操作的体系 结构和机制。除了方便成员之间的互操作外，h l a 还向联邦成员提供灵活的仿 真框架。在h l a 框架下，一个典型的仿真联邦的逻辑结构如图2 - 2 所示。 运行支撑环境r t i 底层通信支持系统( 网络通信或共享内存方式等) 图2 - 2h l a 仿真的逻辑结构 各联邦成员和运行支撑环境r t i ( r u n - t i m ei n f r a s t r u c t u r ：，也叫运行时间基 础结构或运行支撑系统) 一起构成一个开放的分布式仿真系统，整个系统具有可 扩充性。其中，联邦成员可以是真实实体仿真系统、构造或虚拟仿真系统以及一 些辅助性的仿真应用。 213h l a 的组成 h l a r t i 主要由三个部分组成 m o d e lt e m p l a t e ) 和接e l 规范( i s ， 规则( r u l e s ) 、对象模型模板( o m t ，o b j e c t i n t e r f a c es p e c i f i c a t i o n ) 。规则描述了联邦成 北京邮电j = 学硕士研究生学位论文h l a r t 时间管理服务的研究与乐观时间卡隹进机制的实观 员和运行支撑框架r t i 的责任和关系，是仿真实现正确交互的基础；对象模型模 板定义了描述h l a 对象模型的通用的方法，提供标准的格式记录对象模型信息， 以促进仿真应用的互操作性和可重用性；接口规范以服务的方式定义了联邦同联 邦成员进行信息交换的方式，包括可调用的服务和提供的回调服务。 h l a 的r t i 和联邦成员( f e d e r a t e ) 之间的接口主要分为六个服务部分组成， 这些也是r t i 提供给联邦成员使用的服务： 1 联邦管理。主要负责创建和删除联邦执行，联邦成员的加入和退出，控制点， 暂停恢复、重新开始等等。 2 声明管理。实现对象属性和交互的出版和订阅。 3 对象管理。创建删除对象实例，控制对象属性和交互的出版，创建和删除对 象属性的反映。 4 所有权管理。在联邦成员间传输对象和其属性的所有权。 5 时间管理。使仿真世界中事件发生顺序与真实世界中发生的顺序一致，保证 正确的因果关系。 6 数据分发管理。在实例属性层次上进一步增强联邦成员精简数据需求的 能力，目的在于减少无用数据的传输的接收，减少网络中数据的通信量，提高仿 真运行的效率。 从接口的调用方式来看可以把接口分为两个部分；r t i a m b a s s a & ) r 和 f e d e r a t e a m b a s s a d o r 。r t l a m b a s s a d o r 代表联邦成员能够调用的接口，通过 r t i a m b a s s a d o r 联邦成员向r t i 发送清求，比如联邦成员请求改变自己拥有的对 象实例状态，通过r t l a m b a s s a d o r 的u p d a t e a t t r i b u t e v a l u e s 接口服务就可以向r t i 发送请求。f e d e r a t e a m b a s s a d o r 是提供给r t i 向联邦成员回调的接口。r t i 获 知一个联邦成员某个对象状态的变化需要通知其它一些联邦成员时，可以通过调 用f e d e r a t e a m b a s s a d o r 的r e f l e c t a t t r i b u t e v a l u e s 接口服务。联邦成员和r t 之间 就是通过r t i a m b a s s a d o r 和f e d e r a t e a m b a s s a d o r 进行信息的交互。一个联邦成员 可以是一个运行的程序，也可以是一个系统，只要它和r t i 之问有接口可以通 信。 图2 - 3 阐述了联邦成员的构成以及联邦成员和r t i 之间的关系。 北京邮电大学硕士研究生学位论文h l a d r t i 时间管理服务的研究与乐观时间推进机制的实现 图2 - 3 联邦成员之问通过r t i 进行交互 概念 介绍了h l a 的组成部分之后，总结出几个h l a 中很重要的，论文需要经常 使用的定义： 联邦( f e d e r a t i o n ) ：是指用于达到某一特定仿真目的的分布式仿真系统。是一 个特殊的f o m ，一组特殊的联邦成员和r t i 服务的组合体。 联邦成员：是和r t i 连接的一个运行程序或系统。所有参与联邦运行的应用 程序都可以称为联邦成员。联邦成员由若干相互作用的对象构成，对象是联邦的 基本元素。 22 时间管理服务 时间是分布仿真中的核心概念，时间管理服务也是h l a 接口规范的重要组 成部分，它的本质是给具有时间意义的消息加上时戳，以使得消息以正确的因果 顺序被处理，从而保证仿真的执行结果与真实世界相一致，并且在同样的条件 下，具有可重复性，所以，时间管理电可称作“时序管理”，时间管理服务还能 实现仿真应用程序之间的同步。理解时间管理的基本原理以及采用不同时间管理 策略的成员间进行时间协凋的方式，对仿真开发来说是非常重要的。 2 21 时间管理服务 h l a 中的时间管理一共设计了2 3 个调用服务，其中r t i 提供给联邦成员调 用的服务为1 9 个，r t i 回调联邦成员的服务为4 个。前者由r t l 负责实现，后 者由联邦成员负责实现。表2 1 列出了所有的时间管理服务及其相应的功能。 北京邮电大学硕士研究生学位论文h l a r t i 时间管理服务的研究与乐观时间推进机制的实现 本文将r t i 提供的1 9 个调用服务分为4 类，设置策略服务、保守推进服务、乐 观机制服务以及其它服务。 表2 - 1 时间管理服务及真相应的功能 分组服务名称功能简介 e n a b l et i m er e g u l a t i o n 打开时间控制状态 t i m er e g u l a t i o ne n a b l e d + 时间控制状态许可( 回调函数) 设置策略服务 d i s a b l et i m er e g u l a t i o n 关闭时间控制状态 e n a b l et i m ec o n s t r a i n e d 打开时间时间受控状态 t i m ec o n s t r a i n e de n a b l e d + 时间时间受控状态许可f 回调函数) d i s a b l et i m ec o n s t r a i n e d 关闭时间时问受控状态 t i m ea d v a n c er e q u e s t 步进时间推进请求 t i m ea d v a n c er e q u e s ta v a i l a b l e 即时时间推进请求 i 保守推进服务 n e x te v e n tr e q u e s t 下一事件请求 n e x te v e n tr e q u e s ta v a i l a b l e 下一事件即时请求 t i m ea d v a n c eg r a n t + 时间推进许可( 回调函数) f l u s hq u e u er e q u e s t 清空队列请求 l 乐观推进服务r e t r a c t回滚 r e q u e s tr e t r a c t i o n 十 请求回滚 q u e r yl b t s 查询l b t s q u e r yf e d e r a t et i m e 查询成员逻辑时间 j 其他服务 q u e r ym i n i m u mn e x te v e n tt i m e 查询最小下事件时间 m o d i f yl o o k a h e a d 修改l o o k a h e a d q u e r yl o o k a h e a d 查询l o o k a h e a d e n a b l ea s y n c l l r o n o u sd e l i v e r y 打开异步传输方式 d i s a b l ea s y n c h r o n o u sd e l i v e r y 关闭异步传输方式 c h a n g ea t t r i b u t eo r d e r1 1 ，p e 改变属性的顺序类型 c h a n g ei n t e r a c t i o no r d e rt y p e 改变交互类的顺序类型 2 22 消息传递机制 h i a 时间管理服务协调时间的方式是通过相互发送“消息”来进行的。在 北京邮电大学硕士研究生学位论文h l a r t l 时间管理服务的研究与乐观时间推进机制的实现 i l a 的时间管理中，如果一个联邦成员激活“u p d a t ea t t r i b u t e ”服务、“s e n d i n t e r a c t i o n ”服务、“s e n d i n t e r a c t i o n 、v i m r e g i o n ”服务或者“d e l e t e o b j e c t i n s t a n c e ” 服务，则称该联邦成员发送了一个消息。而r t i 为一个联邦成员激活“r e f l e c t a t t r i b u t e v a l u e s + ”服务、“r e c e i v e i n t e r a c t i o n + ”服务或“r e m o v e o b j e c t i n s t a n c e + ”服务则称该联邦成员接收了一个消息。 联邦成员发送一个消息将导致一个或多个联邦成员接收到对应的消息，这种 发送和接收的对应关系要根据前面介绍的公布与定购关系来确定。在h l a 中， “消息”通常也称为“事件”。消息发送时可以打上“时戳”( t i m e s t a m p ，联邦 成员的仿真时间) ，以表明该事件( 或消息) 发生的时间。 消息的传递机制包括两方面的内容：消息传输方式和消息传递顺序。不同类 型的消息传递机制提供不同的可靠性或不同的传递顺序，其代价是资源( 如时延、 带宽等) 。 消息传输方式 消息的传输方式分为“可靠”限e l i a b l e ) 和“陕速”( b e s te f f o r t ) 两种，前者保 证可靠性，使消息最终能到达目的成员，但通常要增加时延；后者以减少传输时 延为主要目的，通常要降低可靠性。 消息的传递顺序 h l a1 3 规范和i e e e1 5 1 6 标准定义了两种消息序，即接收序r o ( r e c e i v e o r d e r ) * 口时戳序t s o ( t i m es t a m po r d e r ) 。r o 消息序和t s o 消息序的区别在于联 邦成员接收消息时是否需要按照时戳顺序对消息进行排序。r t i 在将多个r o 消 息发送到同一个联邦成员时，不需要对消息进行排序。然而，除非联邦成员使用 乐观推进机制，r t i 必须按照时戳顺序依次发送t s o 消息，但时戳相同的消息 则不必进行排序。 判断一个消息的消息序可根据下列因素进行： f 1 1 预定义的消息序类型 使用时间管理服务时，需要为每个对象类属性和交互类预先指定消息序类 型。 一个消息的消息序类型是在仿真试验前就已经定义好了的，对于i e e e l 5 1 6 标准而言，定义在联盟对象模型文档数据文件f d d 中；对于h l a l3 而言，则 定义在联盟执行数据文件f e d 中。另外，在联邦执行期间，联邦成员可以使用 c h a n g e a t t r i b u t e o r d e r t y p e 服务改变对象类属性的预定义类型；使用c l l a n g e i n t e r a c t i o n o r d e r t y p e 。服务改变交互类的预定义类型。 北京邮电大学硕士研究生学位论文h l a r t i 时问管理胀务的研究与乐观时间推进机制的实现 f 2 ) 所使用的服务 消息的消息序类型与所使用的服务是否带有时戳参数相关。用不带时戳参数 的服务发送的消息一定是r o 消息。 ( 3 1 联邦成员的状态 只有时间控制联邦成员( r e g u l a t i n g f e d e r a t e ) 才能够发送t s o 消息，当然时间控 制联邦成员也可以发送r o 消息。只有时间受控联邦成员( c o n s t r a i n e d f e d e r a t e ) 4 能够接收t s o 消息，当然时间受控联邦成员也可以接收r o 消息。 ( 4 ) 发送方的消息序类型 接收消息的消息序类型与发送方所使用的消息序类型相关。 表2 - 2 发迭消息的类型 i 预定义类型发送方式否发送消息是发送方的是否返 为时间控制否带时戳参消息类型回消息 联邦成员数句柄 r o n on o r on o r o n o y e sr on o r oy e s n or o n o fr o y e sv e s r on o t s on o n 0 r on o ) t s o n oy e sr on o t s oy e sn or on o t s oy e sy e st s oy e s 存i e e e i5 1 6 标准中，要判断一个联邦成员发送的消息是r o 消息还是t s o 消息，可以参考表2 2 ：要判断一个联邦成员以r o 方式接收消息还是以t s o 方 式接收消息，可以参考表2 - 3 。在r t 软件中可以这样进行，一个发送消息为t s o 三个条件： ( a ) 预定义类型为t s o ； ( b 1 发送方为时间控制联邦成员； f c ) 该消息携带逻辑时间。 除此之外的发送消息、为r o 消息。一个接收消息为t s o 消息必须满足两个条 件： ( d ) 由发送消息为t s o 消息； ( e 1 接收方为r 0 间受控酰邦成员。 北京邮电大学硕士研究生学位论文h l a r t i 时问管理服务的研究与乐观时间推进机制的实现 除此之外的接收消息为r o 消息。由此可以看出，若发送消息为t s o 消息， 但如果不满足条件( e ) ，则该t s o 消息会被r t i 转化为r o 消息发送给接收方： 但r o 消息却永远不会被转化为t s o 消息发送到接收方。 t s o 消息只能够在时间受控联邦成员向r t i 请求推进时才会被时间受控联邦 成员接收到，而r o 消息则有所不同。在r t 中为联邦成员设置了一个“异步消 息传送”开关，如果该开关关闭，则r o 消息与t s o 消息一样，只有在时间受 控联邦成员请求时间推进时才能够把r o 消息发送到时间受控联邦成员；如果该 开关打开，则r t i 一旦接收到发送联邦成员的消息，就会立即将r o 消息发送 给定购联邦成员。设置开关的时间管理服务分别为e n a b l e a s y n c h r o n o u s d e l i v e r y 和d i s a b l e a s y n c h r o n o u s d e l i v e r y 。 袁2 - 3 接收消息的类型 接收方是否相应的发送接收方的是否提 为时间受控消息类型消息类型供消息 联邦成员旬柄 n or or on o n ot s or oy e s y e s 。 r or on o y e st s ot s 0y e s 当联邦成员向r t i 发送t s o 消息时，r t i 会将一个唯一标识该消息的消息句 柄返回给发送联邦成员：同时r t i 也会将相应的消息句柄作为参数一起发送给接 收联邦成员，而不论接收联邦成员是否以t s o 方式接收消息。消息旬柄被定义 为一个简单的对象类型，至少包含两个变量，即唯一标识消息的序号和发送该消 息的联邦成员句柄。 2 23 时间管理策略 h l a 时洲管理具有支持不同仿真采用不同时间管理策略的能力，联邦成员可 以选择是否能够发送t s o 消息以及是否接收t s o 消息。h l a 时问管理支持下列 四种策略： ( 1 ) 既非时间控制也非时间受控 ( 2 ) 时间控制但非时间受控 ( 3 ) 时间受控但非时间控制 ( 4 ) 既时问控制又时间受控 2 北京邮电大学硕士研究生学位论文h l a r t i 时间管理服务的研究与乐观时问推进机制的实现 这里的“时间控制”( r e g u l a t i n g ) 是指联邦成员调用e n a b l e t i m e r e g u l a t i o n 服务 设置策略，r t i 若同意将其设置为时间控制联邦成员( r e g u l a t i n gf e d e r a t e l ，则使用 t i m e r e g u l a t i o n e n a b l e d + 回调服务通知联邦成员已被设置为时间控制联邦成员；否 则联邦成员将处于等待状态，r t i 在适当的时机会通知联邦成员被设置为时问控 制联邦成员。从表2 2 可以看出，只有时间控制联邦成员才能够发送t s o 消息。 这里的“时间受控”( c o n s t r a i n e d ) 是指联邦成员调用e n a b l e t i m e c o n s t r a i n e d 服务设置策略，r t i 使用t i m e c o n s t r a i n e d e n a b l e d + 回调服务通知联邦成员已被设 置为时间受控联邦成( c o n s t r a i n e df e d e r a t e ) 。从表2 3 可以看出，只有时间受控 联邦成员才能够接t s o 消息。另外，一个时间控制联邦成员可通过调用 d i s a b l e t i m e r e g u l a t i o n 服务将自己设置为非时间控制联邦成员，这样该联邦成员 就不能够再发送t s o 消息：一个时间受控联邦成员可通过调用 d i s a b l e t i m e c o n s t r a i n e d 服务将自己设置为非时间受控联邦成员，这样该联邦成员 就不能够再接收t s o 消息。 2 34 时间推进机制 h l a 时间管理机制是一种普遍适用的商级时间管理机制，支持保守同步机制 和乐观同步机制的统。在h i a 出现之前，保守同步机制和乐观同步机制是并 行离散事件仿真中的两个互不相关的机制。前者严格保证t s o 消息按照逻辑时 间的大小被接收方所接收：后者却无需做此假设，只是当接收方收到一个过时的 消启、时则进行回滚。然而h l a 却把这两种机制统- n 同一个舰范中，说明在一 个仿真中可以同时支持这两种同步方式，即基于保守同步机制的联邦成员之间、 基于乐观同步机制的联邦成员之间、保守同步机制的联邦成员与乐观同步机制的 联邦成员之间都可以发生信息的交互。 ( 1 ) 保守同步推进机制 从本质上讲，h l a 中的时间管理服务就是按照逻辑时间对分布式系统中的消 息进行排序。在整个仿真过程中，联邦成员不断地向前推进自己的逻辑时间；但 是联邦成员在推进自己的逻辑时间时必须得到r t i 的同意。r t i 必须保汪使用保 守推进机制的联邦成员一定不会收到过时的消息，即后来接收到的消息的逻辑时 问一定不小于先前接收到的消息的逻辑时间。因此，联邦成员使用保守推进机韦4 向前推进逻辑时间时，永远不会产生状态的冲突。 ( 2 1 乐观同步推进机制 保守同步推进机制虽然能够严