时间推进（精选2篇）
时间推进 篇1
1 引言
并行离散事件仿真(Parallel Discrete Event Simulation,PDES)，是指在多处理器系统或网络工作站上并行执行离散事件仿真程序。如何将不同类型的仿真系统的内部时间协调一致，是保证仿真正确运行的基本前提条件，这也正是PDES过去20年努力解决的问题。随着近年来计算机仿真技术中高层体系结构(High Level Architecture,HLA)的飞速发展，作为HLA时间管理算法直接来源的PDES中的时间推进算法，对其的研究又掀起了新的高潮。
PDES中关键的时间推进同步算法始终是仿真界公认的重点和难点问题。目前PDES主要采取两类同步算法。保守算法严格禁止发生因果关系错误，确保不会失序地处理非独立事件，也就是保证依据时间的逻辑先后顺序在并行机上处理事件，但可能发生死锁。乐观算法充分利用系统平台的并行计算能力，设定分布在每个处理机上的逻辑进程可以按任意顺序在空闲的处理机上执行，一旦出现任何一个关系错误即发生同步错误，则及时进行回退，并且恢复系统上一时刻的状态。本文重点研究PDES时间推进中的保守算法。
2 PDES时间推进中保守算法的研究
2.1 保守（Conservative）策略
PDES中保守算法的基本思想是：假设物理系统满足可实现性(Realizability)和可预测性(Predictability)，并且在遵守本地因果约束条件(Local Causality Constraint)的前提下，可以实现对系统的正确仿真。
可实现性保证系统发出的t时刻消息仅依赖于t时刻以前接收到的消息状态，可预测性保证系统能够在t时刻预测出t+ε时刻的消息(ε>0)。
本地因果约束条件是指由一组逻辑进程组成的离散事件仿真系统，当且仅当每个逻辑进程按非递减的时戳顺序处理事件，则系统遵守本地因果约束条件。
保守策略严格禁止发生因果错误，即保证按时间先后顺序在并行机上处理各类事件。保守策略的主要任务是确定何时能“保险”地执行某一事件，它常常依赖于仿真模型行为的信息，如模型的可预测性等来确定哪个事件能被“保险”地执行。
在保守算法中，到达每个进程输入通道的消息按时戳顺序存储，一个进程发送给另外一个进程的消息被保存在一个先进先出(FIFO)的队列中。对每个通道都有自己的通道时钟，时钟的取值按照三条原则：
原则1：仿真开始时，各个时钟取值为零;
原则2：如果队列不为空，则时钟取值为队列中第一个消息的时戳，第一个消息是该队列中时戳最小的消息;
原则3：如果队列为空，则时钟取值为最后一次接收到的消息时戳。
进程循环选出时钟值最小的输入通道，并且当该通道队列中有消息时，处理时戳最小的消息。如果这个通道队列是空的，那么这个进程会被阻塞。这样就保证了每次每个进程都能按时戳递增的顺序处理一个事件，因而遵守了本地因果关系约束条件。
一个保守进程处理消息的过程可用下列算法表示。
算法1：进程处理消息过程
While(仿真没有结束){
等待直到每个FIFO队列都至少包含一个消息;
找出所有队列中的最小的时戳消息M，并从相应的队列中删除;
时钟Clock：=消息M的时戳;
处理消息M;
}
2.2 保守算法的死锁问题
保守方法严格遵守本地因果约束条件，总是不断地判断何时可以安全处理事件，当不能确保任何可能影响事件处理的所有事件都己处理完时，进程将被阻塞，因此在保守方法中，可能发生死锁现象。具体地说，如果进程含有一个未处理的事件E1，其时戳为T1，(并且在进程中不再有更小的时戳)，进程可以确定的是，以后它不可能收到比T1更小时戳的事件，处理E1不会在将来发生本地因果关系的冲突，因此进程可以安全处理E1。如果进程无法确认这一点，就必须被阻塞。如果一直没有适当的前因激活进程，系统可能导致死锁。
在PDES中，常见的死锁情况是，如果通道时钟较小的空队列形成回路，回路中的每个进程都被阻塞，整个系统中的所有进程均处于等待状态，因此仿真发生死锁。
图1描述了三个进程处于死锁等待状态的情形，虽然在每个进程的其他输入队列中有等待处理的事件消息，但由于进程循环选出时钟值最小的输入通道，并且当该通道队列中有消息时，处理时戳最小的消息。如果这个通道队列是空的，那么这个进程会被阻塞。假如此时具有最小通道时钟的输入通道队列是空队列，那么每个进程都在等待消息的到来，此时进程A等待来自进程B的消息，进程B等待来自进程C的消息，进程C等待来自进程A的消息，即三个进程之间形成了一个圈，则发生死锁。
2.3 保守算法的死锁解决方法
由于在上述情况下，PDES的保守机制可能发生死锁，所以在实际仿真中，就必须采取一些措施，打破死锁，推进仿真时钟。目前一般使用三种解决死锁的方法：空消息法、命令驱动的空消息法、死锁的探测和恢复机制。本文主要研究使用最为广泛的空消息法。
Chandy和Misra提出了第一个保守算法，即Chandy/Misra算法，首次提出了前瞻值的概念，并提出了用于解决死锁问题的空消息法(Null Message)。空消息法本质上就是一种基于前瞻值的方法。
空消息法基于下列几个假设：
假设1：每个进程预先知道需要向哪些进程发送消息，以及从哪些进程接收消息;
假设2：每个进程以非递减的时戳序发送消息;
假设3：网络能够确保先发送的消息被先接收到(FIFO);
假设4：网络是可靠的。
这种算法限定了信息按时间戳顺序到达进程的接受队列中，一个进程从另外一个进程接收到的最后一个消息表明该进程再不会接收到小于该消息时戳的消息，最后一个消息的时戳表明了以后所能够接收到的消息的时戳下界。即假设LPi发给LPj一种新的消息(T,Null)，其含义是：到T时刻为止，LPi不会发送任何消息给LPj，因此以后发出的任何消息时戳均大于T。该消息排在通道的最后，而且只有这个消息可能是空消息。
图1所示的死锁可以用如下方法解决：假设进程之间的网络延迟为3个仿真时间单位，进程C的当前仿真时间为5，那么不论进程C将要发送什么消息，进程B一定在仿真时间8(8=5+3)之后才能够收到来自进程C的消息。虽然进程B收到时戳为8的消息，但仍无法处理FIFO队列中的时戳为10的消息，可是进程B知道它的下一个消息的时戳至少为8，进程A一定在仿真时间11(11=8+3)之后才能够收到来自进程B的消息。这样进程A就可以安全地处理FIFO队列中的消息9了。也就是说，在进程A，进程B和进程C的输入通道环中，始终有一个空消息在循环流动，其时戳值不断累加。这样，就避免了死锁的发生。整个过程如图2所示。
图2中的进程之间发送的消息仅仅用于进程同步，不是仿真系统中实际发生的事件，不需要消息体，因此将这类消息称之为“空消息”，相应的算法称之为空消息法。空消息用来表示进程之间“发送消息”时的一种承诺，表示不会发送时戳低于某一下界的消息。更一般地讲，空消息法实际上是一种基于前瞻值的一种算法。上述“进程之间的网络延迟”的“3个仿真时间单位”即为前瞻值。
当进程处理完事件，就向每个输出端口发出空消息，通知这个下限，于是收到空消息的接收方就能根据这个信息，计算出它的输出通道的新的下限，并把该信息通知它的邻居。
从接收方而言，处理空消息的方法和处理其他消息的方法一样：该消息都会使逻辑进程更新内部状态，以及仿真时钟，并在必要的情况下发出消息。
Chandy/Misra空消息法可参见算法2:
算法2:Chandy/Misra空消息法
While(仿真没有结束){
等待直到每个FIFO队列都至少包含一个消息;
找出所有队列中的最小的时戳消息M，并从相应的队列中删除;
时钟Clock：=消息M的时戳;
处理消息M;
向相邻进程发送空消息，空消息的时戳为Clock+Lookahead。
}
3 算法实现
基于保守算法，我们采用C#.net编写程序，构建了用空消息法实现保守时间推进策略的系统。
系统的初始界面如图3所示，界面左边三栏分别显示三个进程通道中的当前状态，主要是收发消息(包括带有具体内容的实消息和只带有时戳的空消息)和处理消息的过程，右边一栏显示的是各个进程当前的进程时钟和当前接收通道中接收其他进程发送的消息时戳(包括带有具体内容的实消息和只带有时戳的空消息)。本系统的前瞻量设定为3个仿真时间单位。点击“Start”键系统开始运行，点击“Reset”键系统重启。
当系统运行时，带有“message”字样的消息表示具有实际内容的实消息的发送，括号里的数字表示该消息的时戳。带有“empty message”字样的消息表示只具有时戳的空消息的发送，括号里的数字表示空消息的时戳。无论空消息或者实消息被处理后，系统都对该消息打上“handled”标记。如图4所示，此时进程A,B,C的仿真时钟已分别推进到“9”，“8”，“8”。
依此类推，系统总是保证每次每个进程都能按时戳递增的顺序处理一个事件。当某一进程处理完一个事件后，就向每个输出端口发出空消息，空消息的时戳为当前进程时钟值Clock+Lookahead，通知其他进程不会再发送时戳低于Clock+Lookahead的消息了。因而遵守了本地因果关系约束条件。
4 结束语
实现的具体代码在此就不一一列出了，有需要的同仁可直接向作者索取。空消息法最大的优点是简单，只需要对源代码作少量修改，增加空消息的发送就可以了。此外，对进程间的通讯缓存区也没有额外的要求，如果进程间的缓存区的大小有限，发送消息的进程只需等到有空余缓存区的时候，再发送消息，得到的仿真结果是一样的。
该方法最大的缺点是将产生大量的空消息，增加了网络负载，降低了算法性能。另外，对于处于环中进程的时间前瞻值大于0的情况，这种机制可以避免死锁。但这种方法不能解决所有的死锁问题，如时间前瞻值为0的情况，因此空消息不能解决那些最小服务时间为0的队列型网络仿真中的死锁。所以，在HLA的保守时间推进算法中，采取了查询前瞻量和计算最大可用逻辑时间相结合的方法，有效地避免了这一缺陷。
参考文献
[1]Richard Fujimoto.Parallel Discrete Event Simulation[J].Communications of the ACM,1990,33(10).
[2]欧阳伶俐.并行离散事件仿真算法及其在HLA时间管理中的应用[D].北京:航天二院,1999.
[3]欧阳伶俐,宋星,卿杜政,等.HLA时间管理与PDES仿真算法研究[J].系统仿真学报,2000,12(3):237-240.
[4]蔡吉淼,汪厚祥.保守PDES中时间管理问题研究[J].计算机工程与设计,2007,28(14):3536-3538.
时间推进 篇2
发布时间：20
为了进一步加强学风建设，培育优良学风，优化育人环境，营造良好的学习氛围，音乐学院紧抓2017级本科生入学的关键时期，以角色转变为重心，以入学教育为抓手，以学习引领为切入点，采取了一系列措施，力求将学风建设落到实处。
以迎新工作为起点，打好学风建设前站。良好的开始是成功的一半，入学初的正确引导，对于良好学风的形成乃至对学生在整个大学阶段的成长具有举足轻重的意义。音乐学院精心筹划，周密部署，将学风建设作为迎新工作的第一要务。在迎新筹备阶段，音乐学院成立了以党委书记惠刚、院长张君仁为组长的迎新工作领导小组，制定了《陕西师范大学音乐学院2017年迎新工作方案》，编印了《音乐学院学生宿舍文明卫生细则》、《给大学新生的五十个忠告》、《音乐学院关于加强学生管理的十条规定》、《温馨备忘录》、《音乐学院2017级本科新生入学活动》等系列迎新资料，为音乐学院的闪闪star深入了解学院的各项规定，打下了坚实的基础。
同时，2017级新生辅导员张仪提前建立了新生QQ群和新生家长QQ群，及时与新生和家长进行交流沟通，耐心回答问题，解读政策，并通过学院官方微信公众平台“陕师大乐舞飞扬”及时推送《开学季-你对陕师大音乐学院知多少》、《开学季-生活指南》、《开学季-关于入学报到你必须知道的那些事》等一系列迎新特辑，第一时间架起了学院与新生之间交流的桥梁，打好学风建设前站。
以入学见面会为契机，师生家长共促学风。为更加有效地加强与新生家长的沟通，家长和师生联动促学风，共同打造良好的育人环境，音乐学院在终南音乐厅召开了家长见面会、新生动员大会，四百余名新生和家长以及学院全体班子成员、系主任参会。会上，音乐学院院长张君仁致辞。他指出，读书是一种习惯，是提高自身修为最有效、最理想的途径，对于当代的年轻人来讲，养成阅读的习惯是在大学期间最重要的任务。新的生活已经开始，祝愿新同学们优雅地做人，健康快乐地成长，尽情挥洒青春，完善人生。学院党委书记惠刚向新生及家长强调了艺术学习和修养提升的重要性，希望各位同学扬起立志的风帆，砥砺品行，勇猛精进，使老师放心，使父母放心，也使祖辈放心，祝愿同学们在陕西师范大学音乐学院茁壮成长，学有所成，不负自己，更不负家族的希望。最后，音乐学院党委副书记范玮熠向新生和家长介绍了校、院的学风建设工作和重要规章制度。他号召同学们尽快完成角色转变，努力适应新的大学生活，摒弃不良习惯，严格要求自己，做一名合格的大学生；同时也希望各位家长积极配合学院的学生管理工作，为学生的成长成才保驾护航，携手共进。
以入学教育为抓手，强化制度培育学风。新生入学教育是学生大学生活重要的第一课，音乐学院通过开展一系列的入学教育活动，旨在帮助新生尽快了解大学学习与生活的基本特点和要求，树立远大理想，制定学业规划，迈出成长成才的坚实第一步。
——校纪院规与安全教育。学院党委副书记范玮熠组织大一新生系统学习了学校、学院制定的各项规定和管理制度，重点强调了学校的《学生管理规定》、《本科生学业警示实施办法》、《学生违纪处分规定》、《学生考试违纪、作弊处理办法》以及音乐学院制定的《加强学生管理十条规定》、《宿舍文明卫生细则》等，让新生熟悉规章制度的同时，也明确了遵守纪律的重要性，提高了遵纪守法的自觉性，为形成良好的学风、班风、舍风奠定了坚实基础。
——专业学习指导教育。学院教学副院长王拥军、刘姬娜向学生充分说明了学院的办学特色、学科专业情况，让新生了解本专业知识结构、学习方法和专业发展前景，帮助新生端正专业思想，增强了专业学习的信心和动力。两位副院长也表达了对同学们的殷切期待，希望他们能学好专业，锻炼团队协作意识和奉献精神，凡事多参与，追寻人生的无限可能。
——心理健康教育。为将心理健康教育工作前置，学院邀请学校学生心理健康教育（咨询）指导中心的孙晨莉老师对新生进行了较为系统的心理健康知识教育，引导同学们以良好的心态面对崭新的学习、人际关系以及可能出现的各种困难。孙老师还通过手指小游戏等环节与同学们进行了充分互动，现场笑声不断，欢乐满满。
——大学适应性教育。音乐学院邀请青年教师康瑛和优秀学长代表为同学们如何适应大学学习生活进行了悉心指导。康老师与同学们进行了深入交流，使新生认识到大学与高中在学习方法上的差异，尽快适应大学学习的特点和要求，掌握大学的学习规律。另外，两位优秀研究生学姐也跟同学们讲述了自己在本科阶段的学习和生活经历，如何在种种不适应中克服困难并取得优异成绩。
——学业发展规划教育以及琴房、乐器使用规范教育。学院教学秘书朱琳解读了学生培养方案，介绍专业教学计划和课程，说明了课程修读的注意事项，确保每一位同学都能保质保量地完成学业。学院实验中心主任金鑫则强调了教室和琴房的使用细则，以及使用钢琴等乐器的注意事项。
以学习引领为切入点，多措并举狠抓学风。一方面，音乐学院在新生入学后，对各专业学生分批进行了专业测试，目的是对全体学生的专业基本功进行摸底，并从一进校就让学生养成良好的专业学习习惯。各系主任和专业老师全程参加了专业测评，经过严格有序的考核，让同学们看清了在专业学习上自身存在的差距，有助于激发学生的学习积极性和学习热情，对于学生掌握学习策略、培养自主学习能力具有积极意义。
另一方面，音乐学院组织新生参观了学校图书馆和学院教学场所，号召大家养成良好的阅读和学习习惯。大部分同学是第一次进入长安校区图书馆，激动的心情溢于言表。在图书馆志愿者的讲解下，同学们对图书馆的发展历史、图书种类、馆内管理规定等都有了深入的了解。学院还组织新生参观了学院汉唐乐器陈列室、图书资料室、琴房等教学场所和设施，良好的教学环境、完善的教学设备给同学们留下了深刻的印象，也让同学们坚定了努力学习的信念。