盟员自己创建一个网站

Vol.
15,No.
32004JournalofSoftware软件学报1000-9825/2004/15(03)0338RTI中乐观推进机制的实现刘步权+,王怀民,姚益平(国防科学技术大学计算机学院,湖南长沙410073)ImplementationofOptimisticAdvancingMechanisminRTILIUBu-Quan+,WANGHuai-Min,YAOYi-Ping(SchoolofComputer,NationalUniversityofDefenseTechnology,Changsha410073,China)+Correspondingauthor:Phn:+86-731-4573697,E-mail:bqliu@nudt.
edu.
cn,http://www.
nudt.
edu.
cnReceived2003-11-07;Accepted2003-11-27LiuBQ,WangHM,YaoYP.
ImplementationofoptimisticadvancingmechanisminRTI.
JournalofSoftware,2004,15(3):338~347.
http://www.
jos.
org.
cn/1000-9825/15/338.
htmAbstract:Indistributedmodelingandsimulationarea,itisintractabletocomprehendthefundamentalprinciplesofoptimisticadvancingmechanismandimplementtheoptimisticadvancingservicesinRTI(runtimeinfrastructure)accordingtoHLA(highlevelarchitecture)specifications.
ThispaperintroducestwodifferentoptimisticadvancingmechanismsinPDES(paralleldiscreteeventsimulation)andHLA,andrevealssomeimportantdifferencesbetweenthem.
Forexample,thevirtualtimecanberolledbackinPDES,thelogicaltimecannotberolledbackinHLA,andanoptimisticfederatecanonlyrollbackitsmessage-schedulingtimeandmustensurethatitsrollbackwon'tinfluencetheadvancingofconservativefederates.
RollbackoccursinalogicalprocessinPDES,butitcanonlyoccurinafederateratherthanRTIinHLA.
Inaddition,anewimplementationmechanismcalledZero-Savingisproposedinthispaper.
Withthismechanism,aRTIdoesnotneedtosaveanyexecutionstateswhenoptimisticadvancingservicesareimplemented.
ThismechanismhassuccessfullybeenappliedtoaRTInamedStarLink.
TheZero-SavingmechanismaddstwonewvariablesintothemessageretractionhandletypeRTI::MessageRetractionHandlewhichisadatatypedefinedbyIEEE1516.
1.
OnevariablerepresentsthetimestampofthesentTSO(timestamporder)message,andtheotherisusedtosaveallfederateswhichreceivethemessage.
WhenaTSOmessageissenttoRTI,RTIreturnsthesendingfederateamessageretractionhandlewithallmessage-receivedfederates.
SoRTIknowswhichfederatesshouldbenotifiedtoretractthereceivedmessageswheneverthesendingfederateusesamessageretractionhandletoaskRTItoretractaTSOmessage.
ThefundamentalprinciplesandimplementationofoptimisticadvancingservicesintroducedinthispaperareusefulforRTIdevelopers.
SupportedbytheNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.
2001AA115127(国家高技术研究发展计划(863));theNationalGrandFundamentalResearch973ProgramofChinaunderGrantNo.
G1999032703(国家重点基础研究发展规划(973))作者简介:刘步权(1969-),男,江苏姜堰人,博士生,讲师,主要研究领域为分布式仿真,分布对象技术,操作系统;王怀民(1962-),男,博士,教授,博士生导师,主要研究领域为分布计算技术,信息安全;姚益平(1963-),男,博士,研究员,主要研究领域为分布式仿真,虚拟现实.
刘步权等:RTI中乐观推进机制的实现339Keywords:paralleldiscreteeventsimulation;highlevelarchitecture;timemanagement;optimisticadvancingmechanism;zero-saving摘要:正确理解乐观推进机制的基本原理,并按照高层体系结构HLA(highlevelarchitecture)规范实现RTI(runtimeinfrastructure)中的乐观推进服务一直是分布式仿真领域关注的难点问题.
介绍了并行离散事件仿真PDES(paralleldiscreteeventsimulation)和HLA中的乐观推进机制,并指出了它们之间的重要差异,例如PDES中的虚拟时间(virtualtime)可以回卷(rollback),回卷发生在进程中;而HLA中的逻辑时间不能够回卷,但乐观盟员在不影响保守盟员推进的情况下可以回卷自己调度事件的时间,回卷发生在盟员内而不是RTI内.
另外,提出了在实现乐观推进服务时,不需要RTI作任何保存操作的"零保存"技术,并成功地将该技术应用到RTI软件StarLink中.
"零保存"技术通过在消息句柄类型RTI::MessageRetractionHandle定义中增加两个变量,一个表示TSO(timestamporder)消息的时标,另一个表示所有接收该消息的盟员(RTI::MessageRetractionHandle为IEEE1516.
1定义的数据类型),RTI将具有此类型的消息句柄返回给发送TSO消息的盟员保存,当发送盟员再次使用消息句柄撤消(retract)消息时,RTI从消息句柄中就可以知道并通知接收盟员撤消消息.
对于理解和开发RTI中的乐观推进服务具有重要的现实意义.
关键词:并行离散事件仿真;高层体系结构;时间管理;乐观推进机制;零保存中图法分类号:TP391文献标识码:A为了保证仿真的正确执行和消息之间的因果关系,高层体系结构HLA[1](highlevelarchitecture)引入了时间管理服务[2].
时间管理服务的本质是通过逻辑时间对分布式仿真中的消息进行排序,因此时间管理也可以理解为"时序管理".
在并行离散事件仿真PDES[3](paralleldiscreteeventsimulation)的基础上,HLA提出了保守时间推进和乐观时间推进两种方式,并支持这两种方式的混合推进.
保守推进机制要求RTI(runtimeinfrastructure)必须严格保证盟员(federate)按照时标序大小接收消息,因此,盟员在推进的过程中永远不会产生冲突.
然而,即使两个消息的时标不同,但是它们之间却未必存在因果关系;如果两个连续的消息不存在因果关系,却不一定需要按照时标序大小来调度它们.
因此,保守推进机制以"时标序"来确定"因果序"是一种过度"保守"的消息处理机制.
鉴于保守推进机制的不足,HLA引入了乐观推进机制.
在乐观推进机制下,盟员总是"乐观地"认为下一个消息的到来不会与当前的系统状态产生冲突,然而这种"赌博"不可避免地会存在一定的风险,风险的程度依赖于特定的应用.
一旦出现冲突,乐观盟员需要通过"回卷"(rollback)机制来解决这种冲突.
乐观机制在处理器的设计、操作系统中的页面调度、分布式数据库中的事务处理以及并行编译等领域都有很重要的应用.
20多年来,国内外一直关注乐观推进技术的研究.
但国外大多在PDES领域进行研究,即使在HLA标准发布之后,我们也很少看到针对HLA乐观推进机制的研究文章.
在PDES领域,研究的是纯乐观推进技术,与保守推进技术基本不相关;而在HLA领域,却存在保守推进机制和乐观推进机制的协同问题.
自从HLA标准公布之后,国内的众多科研单位就展开了HLA技术的研究和RTI软件的开发.
时间管理服务一直是RTI开发的重点和难点,国内在这方面的研究也比较多[4~8].
但就乐观推进机制而言,除了文献[4,5]的作者结合自己的实际工作在学术方面做了较好的研究以外,我们尚没有看到其他更深入的文章,特别是在RTI中如何实现乐观推进服务方面.
而理解HLA规范并在RTI中实现乐观推进服务正是本文所要研究和解决的问题.
StarLink是我们在国家"863"计划资助下,按照IEEE1516系列标准[1]并基于CORBA[9]中间件技术研制成功的RTI软件.
为了更好地说明RTI中乐观推进服务的实现技术,本文以集中式体系结构的StarLink为例来说明(StarLink的另一版本为基于多个RTI服务器互连的层次式体系结构[10,11]).
在集中式体系结构下,所有盟员的状态信息(包括TSO队列、RO队列)都保存在中央RTI服务器,底层消息的传输由CORBA中间件自动解决并对StarLink设计者透明,盟员由于没有LRC(localRTIcomponent)而不能够实现相互间的直接通信,因此一个盟员发送的TSO消息必须通过中央RTI服务器才能够发送到接收盟员.
集中式体系结构对于设计者按照HLA标准实现RTI以及初学者理解HLA规范都要比其他RTI体系结构方便和简单.
340JournalofSoftware软件学报2004,15(3)我们认为,乐观推进机制的实现需要建立在正确理解HLA规范的基础上,但是对于HLA规范的理解不能够仅停留在规范本身,而需要结合PDES中的乐观推进机制进行.
然而,HLA中的乐观推进机制虽然来源于PDES,但与PDES中的乐观推进机制相比却存在巨大的差异.
本文在分析和比较了两种乐观推进机制的差异之后,提出了不需要RTI作任何保存工作的"零保存(zero-saving)"机制,并将其成功地应用到StarLink软件的实现中.
1两种乐观机制的比较就我们开发RTI的经验可知,能否正确区分PDES和HLA中的乐观推进机制对于实现RTI乐观推进服务至关重要.
在这一节,我们主要讨论下列内容:PDES中的乐观推进机制、HLA中的乐观推进机制、两种推进机制的比较、RTI中的消息重构问题、HLA仿真中用户如何使用乐观推进机制进行程序设计.
1.
1PDES中的乐观机制Jefferson首次提出了基于TimeWarp机制[12]的乐观推进算法,在文献[12]中提出的许多概念一直为以后的乐观推进算法所沿用,文献[5]对其基本原理进行了很好的介绍.
本文将结合一个实例来说明PDES中的乐观推进机制,更详细的讨论可参见文献[13].
StatebeforeprocessingmessageUnprocessedmessageProcessedmessageBX=1Y=2Z=3AX=0Y=0Z=012X:=1Y:=2Z:=318StatebeforeprocessingmessageUnprocessedmessageProcessedmessage18DX=5Y=9Z=3CX=4Y=2Z=335X:=5Y:=9BX=1Y=2Z=321X:=4AX=0Y=0Z=012X:=1Y:=2Z:=341Fig.
1Processstateofstragglermessagearriving图1"过时"消息到达时的进程状态Fig.
2Processstateafterrollback图2回卷后的进程状态图1描述了进程"冒进"处理消息的过程(PDES中的"进程"类似于HLA中的"盟员").
在图1中,一个进程的状态用3个变量X,Y和Z表示.
进程起始状态A为X=0,Y=0,Z=0;处理完时标为12的消息(简称消息12)后,进程状态B为X=1,Y=2,Z=3;消息21只改变X的内容,该消息处理后的进程状态C为X=4,Y=2,Z=3;处理完消息35后,进程状态D为X=5,Y=9,Z=3;此时将要处理下一个消息41,但是因为该进程收到一个其他进程发来的较小消息18,因此进程必须先处理消息18.
我们看到一个有趣的现象,如果消息18只是改变Z的值,而消息21和35都没有改变Z的值,因此在处理完消息35后,不需要回卷状态就可以"安全"地处理消息18;如果消息18只是改变Y的值,而消息21并没有改变Y的值,因此进程可以回卷到状态C,再继续处理消息18;同样,如果消息18需要改变X的值,则进程需要回卷到状态B,图2描述了这样的状态,此时队列中的下一个待处理消息为18.
对于PDES中的乐观推进机制,我们获得了如下一些有用的结论:命题1.
PDES中的虚拟时间可以回卷.
在PDES中,保守机制使用逻辑时间[14]的概念,而乐观机制采用虚拟时间[12]的概念,本质上都是对仿真时间的抽象表示,只是习惯用法不同而已.
在HLA中,由RTI统一负责时间管理;但在PDES中却没有进行时间管理的中心机构,时间管理和时间推进均由进程负责,当发生冲突时可以回卷进程的虚拟时间.
命题2.
PDES中的进程只能撤消(retract)自己发送给其他进程的消息.
图1中进程处理到消息18时需要回卷状态,假设回卷到状态B.
此时进程只需要撤消在消息21和35处理期间发送给其他进程的消息,消息21和35是否撤消取决于其他进程的行为,但不能够由该进程撤消.
以消息21刘步权等:RTI中乐观推进机制的实现341为例说明,假设本进程为P,发送消息21的进程为Q.
进程P处理完消息18后,给进程Q发送了一个消息m,与前面的论述相同,m可能导致进程Q发生冲突而撤消消息21,也可能因为没有发生冲突而不会撤消消息21.
如果消息21没有被撤消,那么消息21仍然保留在进程P的消息队列中.
1.
2HLA中的乐观机制按照IEEE1516系列标准,HLA中的乐观机制由下列3个服务组成,前两个为盟员调用RTI的服务,由RTI负责实现;后一个为RTI回调盟员的服务,由盟员负责实现.
(1)盟员请求RTI推进服务flushQueueRequest,简记为FQR;(2)盟员请求RTI撤消消息服务retract;(3)RTI请求盟员撤消消息服务requestRetraction.
HLA乐观推进机制的大致过程为:首先由盟员通过FQR服务向RTI请求消息,RTI将该盟员TSO消息队列中的所有消息发送给该盟员;盟员将接收到的消息存放到程序的消息队列中并按照时标序大小依次处理消息(参见第1.
5节),当出现冲突时,调用RTI的retract服务请求撤消自己发送的TSO消息;RTI收到retract服务时,如果消息已经发送给其他盟员,则向其他盟员发送requestRetraction回调服务.
对于HLA中的乐观推进机制,我们获得了如下一些有用的结论:命题3.
HLA中的盟员调度时间可以回卷.
为了论述方便,本文引进术语"调度时间(message-schedulingtime)".
调度时间是指盟员处理一个消息时该消息所具有的时标.
在PDES中,当进程处理一个消息时,该进程就推进到该消息的时标处.
因此,在HLA的盟员中,我们也认为当盟员处理一个消息时,该盟员的调度时间就推进到该消息的时标处.
通俗地讲,调度时间指的是"什么时候的事就什么时候调度".
对于保守盟员而言,调度时间≤当前逻辑时间;对于乐观盟员而言,调度时间可以≤当前逻辑时间(不会发生回卷),但调度时间通常≥当前逻辑时间(有可能导致回卷).
命题4.
HLA中的逻辑时间不能够回卷.
盟员和RTI都不能够回卷逻辑时间,这里所说的逻辑时间是指任意时刻盟员的当前逻辑时间,即可以通过queryLogicalTime服务调用的时间.
对于盟员而言,盟员的逻辑时间是由RTI控制的,盟员只能够请求RTI向前推进逻辑时间,如果请求推进的逻辑时间(T+Lookahead)的消息(如果盟员处于Grant状态,那么T表示盟员的当前逻辑时间;如果盟员处于请求推进状态,那么T表示盟员请求推进的逻辑时间).
另外,标准还规定retract服务只能由校准盟员(regulatingfederate)调用,因此保守盟员的最大可用逻辑时间GALT[8](greatestavailablelogicaltime)一定≤回卷盟员的(T+Lookahead),这样,乐观盟员想要撤消的消息一定是保守盟员还没有收到的消息,保证了两类盟员能够"和平共处".
IEEE1516系列标准中的最大可用逻辑时间GALT与HLA1.
3中的LBTS[15](lowerboundtimestamp)意义相同.
命题5.
HLA中约束盟员(constrainedfederate)的逻辑时间一定≤GALT.
首先对保守盟员而言,该命题显然成立,否则该盟员是不安全的.
其次由IEEE1516.
1标准可知:盟员调用FQR(Trequest)请求推进到Trequest时,RTI允许该盟员推进到Tgrant:Tgrant=min{minTSO,GALT,Trequest}.
这里的minTSO表示TSO队列中的最小消息的时标.
因此,Tgrant≤GALT.
盟员使用乐观推进服务FQR推进时,其逻辑时间总是安全的.
本命题讨论的是约束盟员的情形.
对于非约束盟员而言,盟员只能接收RO消息而无法接收TSO消息,因此非约束盟员使用时间推进服务时意义不大,GALT的取值依赖于特定的RTI软件.
命题6.
HLA中的回卷发生在盟员内而不是RTI内.
342JournalofSoftware软件学报2004,15(3)IEEE1516系列标准是关于互操作平台RTI的标准,而不是上层应用即盟员的标准.
在标准中自始至终都没有出现"rollback"或"rollback"等表示"回卷"的词汇,而是用"retract"表示盟员请求RTI撤消一个已经发送的消息;至于是否发送retract服务则取决于盟员.
命题7.
HLA中的盟员只能撤消自己发送给RTI的消息.
该命题本身就是retract服务的前提条件之一.
1.
3推进机制的比较在前面讨论的基础上,两种乐观推进机制的比较可归纳为表1.
Table1Comparisonoftwooptimisticmechanisms表1两种乐观机制的比较OptimisticmechanismPDESHLATimemanagementControlledbylogicalprocessControlledbyRTITimeadvancingControlledbylogicalprocessFederaterequestsRTItoadvanceOccurinlogicalprocessOccurinfederate,notRTIRollbackVirtualtimecanberolledbackMessage-Schedulingtimecanberolledback;logicaltimecan'tberolledbackAlogicalprocessorfederatecanonlyretractmessagessentbyitselfMessageretractionSendanti-message[12]SendmessageretractionhandleRelationwithconservativemechanismIrrelatedPeacefullycoexist1.
4两个有争议的问题要实现RTI,还必须搞清两个问题,即是否允许RTI通知接收盟员撤消RO消息是否允许RTI进行消息重构由于IEEE1516系列标准并没有明确地说明,因此我们认为RTI赞成和不赞成这两个观点都是可以的,但一定要给出一个明确的答复,因为对这两个问题的回答与RTI中数据结构的设计以及TSO消息队列的维护直接相关.
下面两个命题表明了StarLink的观点.
命题8.
RTI应当通知接收盟员撤消RO消息.
该命题的意思是说,一个乐观盟员调用retract服务撤消一个消息m时,消息m可能被多个定购盟员所接收;在这些盟员中有些是以TSO方式接收的,有些是以RO方式接收的;在消息m被撤消时,RTI显然要调用requestRetraction服务通知那些以TSO方式接收的盟员,但RTI是否要通知那些以RO方式接收的盟员呢StarLink支持这一命题,因为requestRetraction服务是由盟员方实现的,如果盟员不需要处理这样的情形,那么它可以不实现该服务,RTI的通知就无效;如果盟员实现该服务,则表明它支持这一结论,RTI的通知就有效.
因此支持这一命题具有一定的灵活性.
命题9.
RTI不负责乐观盟员的消息重构.
以图1为例,假设图1是基于HLA的乐观推进机制.
当盟员处理完消息35后,收到了小时标的消息18,需要回卷到状态B.
此时盟员可以采取两种方式:(1)清除盟员消息队列中保存在消息18之后的所有消息(注意,这里的消息队列并不是保存在RTI中的TSO消息队列).
(2)不清除盟员消息队列中保存在消息18之后的所有消息,只有收到RTI发送的requestRetraction服务时才从队列中删除相应的消息.
对于第1种情形,既增加了RTI设计的复杂性,又增加了盟员程序的复杂性,降低了盟员程序的效率.
与PDES中介绍的情形类似,如果处理完消息18后,消息21没有被发送者撤消,那么该盟员下一个要处理的消息就是消息21,但按照方法(1),当队列清空后怎样才能再次获得消息21呢这就需要RTI来保存该消息,增加了RTI设计的复杂性.
第2种情形实际上借用了PDES所使用的方法,由盟员自己建立并维护消息队列,RTI在收到来自盟员的FQR请求时,一次性地将TSO队列中的所有消息发送到盟员并清空TSO队列,盟员将接收到的消息存放到自己的队列中.
这种方法对于RTI和盟员来说都很方便.
本文提出的"零保存"机制必须建立在该命题的基础之上.
刘步权等:RTI中乐观推进机制的实现3431.
5盟员程序如何应用乐观推进机制由于HLA将时间管理机制与上层应用即盟员分开,通常我们讨论更多的是如何按照标准实现RTI.
但是用户应该如何使用乐观推进机制设计应用程序呢本文建议使用下列算法:(1)建立一个接收消息队列A.
该队列用来保存来自RTI的所有消息,包括TSO消息和RO消息.
(2)建立一个消息句柄队列B.
该队列用来记录所有状态下发送给RTI的TSO消息的消息句柄,供撤消消息时使用.
(3)建立一个状态队列C.
该队列用来保存程序的状态空间.
(4)设置一个后台线程(或者使用Windows系统下的定时器).
后台线程每隔一定的时间间隔保存一次程序状态(注意:不需要每处理一个消息就保存一次程序状态,否则保存操作会导致过多的存储开销,也会降低程序的执行效率).
假设盟员的当前逻辑时间为T,则因为盟员采用FQR请求推进时,RTI总是同意其推进,并把当前逻辑时间返回给该盟员.
采用T回收状态空间要比采用GALT要强,因为后者需要不断地调用queryGALT服务来查询GALT值,增加了不必要的开销.
另外,后台线程在回收状态空间的同时还需要清理队列A和B中与被回收状态空间对应的所有不需要保存的队列元素.
(5)盟员使用FQR向RTI请求消息,将收到的消息存放到消息队列A中,并依次处理各个消息.
(6)当盟员收到requestRetraction回调服务时,从消息队列中查找该消息,若该消息尚未被处理则从队列中删除;否则,判断是否需要回卷程序状态.
(7)若需要回卷程序状态,则向RTI发送retract服务撤消所有在"冒进"状态下发送的消息,这些消息的句柄被保存在队列B中.
(8)最后回卷程序状态.
回卷可能是个连锁反应的过程.
2乐观机制的实现在前面讨论的基础上,本节给出集中式StarLink乐观推进机制的实现方法.
正如前面所言,RTI只需要实现FQR和retract两个服务.
本节主要讨论下列内容:管道机制和可靠性、RTI服务器的总体结构、FQR服务的实现和retract服务的实现.
在讨论retract服务时,本文给出一种称为"零保存"的实现方法,该方法不需要RTI保存任何状态.
"零保存"机制同样适用于类似DMSORTI体系结构[14]的分布式RTI软件的开发.
2.
1管道机制和可靠性管道机制是指,在RTI和盟员之间传输消息时遵循"先发送的消息最先被接收到"的原则.
对于时间管理服务而言,管道机制尤为重要.
如果RTI软件在实现时间管理服务时不遵循管道机制,那么无论是盟员调用RTI还是RTI调用盟员时都会导致消息的混乱和时序不一致现象.
实现时间管理服务的另外一个要求是传输的可靠性.
例如,对于保守盟员而言,如果推进请求被网络丢弃了,则该盟员会因为等待RTI的同意而处于无限等待状态,其他保守盟员也会因为该盟员无法推进而处于等待状态,这样就导致仿真无法继续进行.
TCP传输协议能够有效地解决这两个问题,而UDP传输协议则难以解决.
StarLink是在国产CORBA中间件StarBus[16]的基础上实现的,StarBus在实现时只采用了TCP协议而没有混杂UDP协议.
虽然StarBus为上层应用程序提供了可靠和不可靠两种消息传输方式,但是这两种方式都是基于TCP协议实现的.
StarLink调用StarBus来实现消息在分布式系统中的传输,传输过程对StarLink开发者透明,StarLink调用StarBus与盟员调用RTI服务类似.
2.
2RTI的总体结构如图3所示,集中式StarLink实现时的总体结构由3个大的类对象组成.
RTIambassador对象包含多个Federate对象,每个Federate对象包含一个CallbackThread对象.
每个对象的作用如下:(1)RTIambassador对象.
该对象包含一个FederateList类型的变量,用来指向所有Federate对象实例的存储344JournalofSoftware软件学报2004,15(3)空间.
另外,还包含RTI提供给盟员调用的所有HLA服务,包括乐观推进机制的FQR和retract服务.
RTIambassador对象还包含实现时间管理服务时必不可少的两个私有函数:用于计算GALT的countGALT函数和用于推动其他盟员前进的pushFederates函数.
RTIambassadorFederateList_federatesflushQueueRequest()retract()countGALT()pushFederates()CallbackThreadMessageQueue_queuepushMessage()sendMessages()FederateTSOqueue_TSOqueueROqueue_ROqueuePendingStatus_statuspushROMessage()pushTSOMessage()sendROMessages()sendTSOMessages()getMinTSOTime()*1*11111Fig.
3DatastructureofStarLinkwithcentralRTIarchitecture图3集中式StarLink的数据结构(2)Federate对象.
该对象用来保存盟员的执行状态,图中包含3个变量:TSO消息队列、RO消息队列和表明盟员是否处于挂起状态的布尔变量.
因为盟员在使用乐观推进服务FQR时不会被挂起,所以盟员只会因为使用保守推进服务时而被挂起.
当盟员被挂起时,按照HLA标准规定,盟员在RTI同意其推进之前不能够再调用各类服务请求推进(包括FQR).
Federate对象包含5个函数,两个push函数用于将RO和TSO消息分别放入到盟员的RO和TSO消息队列中,两个send函数用来从相应的队列中取出消息并将其放入到后台线程CallbackThread的队列中.
getMinTSOTime函数用来返回TSO消息队列中最小消息的时标.
(3)CallbackThread对象.
当盟员加入到RTI时,RTI为每个盟员生成一个Federate对象实例,该实例自动创建一个后台线程用于将来自RTI的消息(包括RO和TSO消息)传输给盟员.
由此可以看出,StarLink采用的是一种基于多线程的并发传输技术.
当CallbackThread收到来自Federate对象的消息时,一个信号量被触发,表明收到一个消息,于是立即将其发送到盟员.
2.
3推进服务的实现推进服务FQR的函数原型为voidflushQueueRequest(RTI::LogicalTimetheTime).
FQR服务的实现算法如下:(1)处理异常.
如果盟员没有加入联盟或者已经处于挂起状态(_status变量为真),则引发异常;如果请求推进的逻辑时间theTime小于盟员的当前逻辑时间,则引发异常.
(2)计算GALT.
盟员GALT的计算方法可参见文献[8],GALT的计算与推进服务的类型、盟员所处的状态、Lookahead以及TSO队列中的最小时标消息等因素相关;但绝不能简单地归结为min{Ti+Li}(Ti为盟员i的当前逻辑时间;Li为盟员i的Lookahead).
(3)重新计算当前逻辑时间T.
如果盟员不是约束盟员(constrainedfederate),则T=theTime;否则T=min{minTSO,GALT,theTime}.
其中,theTime为调用服务的参数,minTSO为通过getMinTSOTime函数获得的盟员TSO队列中最小消息的时标.
(4)处理Lookahead.
如果调用modifyLookahead服务降低盟员的Lookahead,则Lookahead只能在推进的过程中逐渐变小.
此时必须检查盟员是否处于这样的一种状态,并重新计算Lookahead.
(5)发送RO消息.
调用Federate对象的sendROMessages函数,将所有RO消息放入到后台线程的消息队列中,后台线程立即将其发送到盟员.
(6)发送TSO消息.
调用Federate对象的sendTSOMessages函数,将所有TSO消息依时标序大小放入到后台线程的消息队列中,后台线程立即将其发送到盟员.
(7)同意盟员推进.
调用timeAdvanceGrant回调服务,允许盟员推进到逻辑时间T.
(8)推动其他盟员前进.
如果盟员为校准盟员,则检查所有因推进请求而没有得到RTI同意的盟员,重新计算它们的GALT,看能否因为本盟员的推进而使得它们获得前进.
刘步权等:RTI中乐观推进机制的实现3452.
4撤消服务的实现撤消服务的函数原型为voidretract(constRTI::MessageRetractionHandle&theHandle).
2.
4.
1两个问题要实现该服务必须解决好两个问题:"定购者"问题和"拆包"问题.
"定购者"问题.
当RTI收到盟员的撤消消息服务retract时,RTI是如何知道theHandle参数所表示的消息被哪些定购者接收了呢一种方法是建立一个队列,队列中的每个元素是消息句柄到接收者集合的映射.
然而要维护该队列将是复杂的,具体体现在:在盟员加入联盟时需要创建该队列;在盟员退出联盟时需要清除和摧毁该队列;在盟员发送TSO消息时需要加入新的元素;在盟员撤消消息时需要删除已有元素;在盟员前进时需要清理该队列;在盟员变为非校准盟员时也需要清理该队列等诸多情形.
StarLink提出的"零保存"方法可以有效地解决这一难题(该术语与操作系统中的"零拷贝zero-copy"[17]术语类似).
"拆包"问题.
按照HLA规范,乐观盟员A发送的一个TSO消息有可能被拆成4个消息发送给定购盟员B.
这4种消息类型为:可靠的RO消息、不可靠的RO消息、可靠的TSO消息和不可靠的TSO消息.
按照命题8,如果RTI在撤消RO消息时也需要通知盟员,那么假如4个消息全部保存在RO或TSO消息队列中(还没有发送到盟员B),则将4个消息从消息队列中删除即可,就不需要回调requestRetraction服务通知盟员B;但如果仅有部分消息保存在消息队列中,其他消息已经发送到盟员B,那么除了清除保存在消息队列中的消息之外,还必须通知盟员B撤消其他消息.
StarLink对"拆包"问题进行了简化处理:一个对象只要有一个属性为可靠传输,则所有属性都采用可靠传输;否则采用不可靠传输.
这样,当乐观盟员A发送的一个TSO消息在传输给定购盟员B时,最多只能被拆分成一个RO消息和一个TSO消息.
2.
4.
2"零保存"机制下面介绍"零保存"机制的基本原理.
(1)在StarLink中,RTI::MessageRetractionHandle类型用接口定义语言IDL[18]描述如下:structMessageRetractionHandle{UniqueIDtheSerialNumber;FederateHandlesendingFederate;LogicalTimetheTime;FederateHandleSeqreceivingFederates;};该类型包含4个变量:惟一标识一个消息的序数theSerialNumber,发送TSO消息的盟员sendingFederate,消息的时标theTime,以及接收该消息的所有盟员集合receivingFederates.
与DMSO开发的RTI相比,这里的定义多了后两个变量.
RTI::MessageRetractionHandle类型对应于HLA1.
3中的RTI::EventRetractionHandle类型,IEEE1516系列标准严格区分了"event"和"message"这两个概念,前者为内部行为,后者为网络行为.
当盟员A发送了一个TSO消息时,RTI必须将RTI::MessageRetractionHandle类型的消息句柄返回给发送盟员A.
消息句柄的设置方法为:theSerialNumber为一个计数器,用来区分不同的TSO发送消息,每发送一个TSO消息,计数器加1;sendingFederate和theTime分别设置为发送盟员的句柄和消息的时标;如果一个句柄为h的盟员B接收了TSO消息,则将h加入到集合receivingFederates中;如果接收了RO消息,则将(1000000+h)加入到集合receivingFederates中.
(2)"零保存"机制的基本思想是:由消息句柄携带所有的接收盟员,并将消息句柄返回给发送者保存.
这样,发送者在使用retract服务向RTI请求撤消消息时,RTI根据消息句柄中保存的接收盟员集合就可以知道究竟有哪些盟员接收了该消息(RTI能够区分RO消息和TSO消息).
当然,该机制必须建立在命题9的基础之上.
2.
4.
3retract服务的实现使用"零保存"机制实现retract服务的过程非常简单,算法如下:346JournalofSoftware软件学报2004,15(3)(1)处理异常.
如果盟员没有加入联盟,盟员不是校准盟员,theHandle.
SendingFederate不等于调用retract服务的盟员,则引发异常(theHandle为retract服务携带的消息句柄);如果theHandle.
theTime≤(T+Lookahead)也要引发异常,以保证不会撤消保守盟员已经收到的消息(如果盟员处于Grant状态,则T表示盟员的当前逻辑时间;如果盟员处于推进状态,则T表示请求推进的时间).
这样就实现了乐观盟员和保守盟员的"和平共处".
(2)令集合Φ为空,集合Φ用来保存所有应该通知撤消消息的盟员.
依次处理theHandle.
receivingFederates集合中的每个元素h:如果h<1000000,则表明盟员h接收了TSO消息.
如果theHandle所指定的消息在盟员h的TSO队列中,则删除此消息;否则将h加入到集合Φ.
如果h≥1000000,则令h=h1000000,表明盟员h接收了RO消息.
如果theHandle所指定的消息在盟员h的RO队列中,则删除此消息;否则将h加入到集合Φ.
(3)依次向集合Φ中的所有盟员发送requestRetraction(theHandle)回调服务.
这里令参数theHandle中的receivingFederates集合为空,以节约网络带宽.
注意,即使一个盟员同时接收了TSO和RO消息,也只需要通知一次即可.
接收盟员通过theHandle.
theSerialNumber匹配消息,以决定撤消消息和回卷操作.
对于类似DMSORTI体系结构的分布式RTI而言,消息句柄theHandle从LRC返回给发送盟员时需要携带receivingFederates集合,在LRC之间传输时可令receivingFederates集合为空.
命题10.
HLA中的保守盟员也能够撤消消息.
参照retract服务的前提条件可以知道:虽然保守盟员没有使用FQR服务推进,但仍然可以撤消自己发送的TSO消息.
另外,一个程序可以同时采用包括FQR在内的多种时间推进服务,没有必要因为某个盟员采用了FQR服务推进逻辑时间就将其称之为乐观盟员,或者说使用了乐观推进机制;即使一个盟员采用了FQR服务,如果该盟员的TSO队列中的消息都是安全的,则该盟员一定不会因为本次推进请求而发生回卷.
因此,我们不主张过分区分HLA中的保守推进机制和乐观推进机制,否则会与HLA能够适应各种类型仿真的"框架"思想相违背.
3结束语自从HLA标准发布之后,时间管理服务一直是仿真界关注的焦点问题之一.
但基于HLA乐观推进机制的研究还不够深入,特别是在RTI中如何实现乐观推进服务,盟员如何使用乐观推进机制进行程序设计等问题都让RTI设计者和仿真应用开发者感到困惑.
本文在深入研究PDES和HLA两种乐观推进机制的基础上,结合多年RTI开发经验,对两种不同的推进机制进行了分析和比较,指出了它们之间的差异,给出了仿真应用程序的开发方法,为基于HLA规范实现乐观推进服务提供了理论基础.
另外,本文还按照IEEE1516系列标准给出了乐观推进服务在集中式StarLink中的完整实现,提出了简化RTI设计的"零保存"机制,并成功地将其运用到StarLink中.
实际上,"零保存"机制能够有效地应用于不同体系结构的RTI软件的开发.
References:[1]SimulationInteroperabilityStandardsCommittee(SISC)oftheIEEEComputerSociety.
IEEEStandardforModelingandSimulation(M&S)HighLevelArchitecture(HLA)IEEEStd1516-2000,1516.
1-2000,1516.
2-2000.
NewYork:InstituteofElectricalandElectronicsEngineersInc.
,2000.
[2]FujimotoRM.
Timemanagementinthehighlevelarchitecture.
Simulation,1998,71(6):388~400.
[3]FujimotoRM.
Parallelanddistributedsimulationsystems.
In:PetersBA,SmithJS,MedeirosDJ,RohrerMW,eds.
Proc.
ofthe33ndConf.
WinterSimulation.
Washington:IEEEComputerSociety,2001.
147~157.
[4]YaoXY,HuangKD.
Algorithmsofreal-timecontrolandoptimistictimesynchronizationbasedontimemanagementinHLA.
JournalofNationalUniversityofDefenseTechnology,1999,21(6):84~87(inChinesewithEnglishabstract).
[5]OuyangLL,SongX,QingDZ,HaoJB,WangJ.
ResearchoftimemanagementinHLAandsimulationalgorithmsofPDES.
JournalofSystemSimulation,2000,12(3):237~240(inChinesewithEnglishabstract).
刘步权等:RTI中乐观推进机制的实现347[6]ZhangL,YinWJ,ChaiXD,LiuM.
InvestigationontimemanagementofRTI.
JournalofSystemSimulation,2000,12(5):494~498(inChinesewithEnglishabstract).
[7]HuangJ,HuangKD.
Timemanagementinthehighlevelarchitecture.
ComputerSimulation,2000,17(4):69~73(inChinesewithEnglishabstract).
[8]LiuBQ,WangHM,YaoYP.
Anon-deadlocktimemanagementalgorithm.
JournalofSoftware,2003,14(9):1515~1522(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/14/1515.
htm[9]2003.
http://www.
corba.
org/[10]LiuBQ,WangHM,YaoYP.
Keytechniquesofahierarchicalsimulationruntimeinfrastructure--StarLink.
JournalofSoftware,2004,15(1):9~16(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/15/9.
htm[11]YaoYP,LuXC,WangHM.
DesignandimplementationofhierarchicalRTIserver.
ChineseJournalofComputers,2003,26(6):716~721(inChinesewithEnglishabstract).
[12]JeffersonDR.
Virtualtime.
ACMTrans.
onProgrammingLanguagesandSystems,1985,7(3):404~425.
[13]FujimotoRM.
ParallelandDistributedSimulationSystems.
NewYork:JohnWiley&Sons,Inc.
,2000.
97~136.
[14]LamportL.
Time,clocks,andtheorderingofeventsinadistributedsystem.
CommunicationsoftheACM,1978,21(7):558~565.
[15]DepartmentofDefenseModelingandSimulationOffice.
RTI1.
3-NextGenerationProgrammer'sGuideVersion4.
2001.
http://www.
dmso.
mil[16]2002.
http://www.
863.
org.
cn/863_95/indust/ind24.
html[17]1996.
http://citeseer.
nj.
nec.
com/chu96zerocopy.
html[18]2003.
http://www.
service-architecture.
com/web-services/articles/omg_interface_definition_language_idl.
html附中文参考文献:[4]姚新宇,黄柯棣.
基于HLA时间管理的实时时间控制和乐观时间同步算法设计.
国防科学技术大学学报,1999,21(6):84~87.
[5]欧阳伶俐,宋星,卿杜政,郝江波,王锦.
HLA时间管理与PDES仿真算法研究.
系统仿真学报,2000,12(3):237~240.
[6]张龙,尹文君,柴旭东,刘民.
RTI系统时间管理算法研究.
系统仿真学报,2000,12(5):494~498.
[7]黄健,黄柯棣.
HLA中的时间管理.
计算机仿真,2000,17(4):69~73.
[8]刘步权,王怀民,姚益平.
一种无死锁的时间管理算法.
软件学报,2003,14(9):1515~1522.
http://www.
jos.
org.
cn/1000-9825/14/1515.
htm[10]刘步权,王怀民,姚益平.
层次式仿真运行支撑环境StarLink中的关键技术.
软件学报,2004,15(1):9~16.
http://www.
jos.
org.
cn/1000-9825/15/9.
htm[11]姚益平,卢锡城,王怀民.
层次式RTI服务器的设计与实现.
计算机学报,2003,26(6):716~721.