并行微观交通仿真中非阻塞式的车辆移动方法
[0028](2)仿真行进阶段，当车辆在路段之内移动时，不产生进程间的交互，故不需要额外的同步措施。但是当车辆从一个路段进入另一个路段时，由于不同路段分属于不同的线程，因此会产生并发和竞争，此时需要执行以下步骤，即完成非阻塞式的车辆移动:
[0029](2.1)上游路段所处的线程将车辆从当前车道的LVC中除去，并将车辆标记为游离状态，表示车辆不再属于任何路段。
[0030]上游线程将车辆从上游车道的LVC中删除，并将车辆位置更新为游离状态，表示不再属于任何路段。车辆在跨路段移动过程中是不属于任何路段的，只有在移动完成后才会属于某个特定的路段。因此在移动开始时需要先把车辆的位置更新为游离状态。
[0031](2.2)上游路段所处的线程将车辆提交到下游车道的缓冲区中。
[0032]下游车道LVC的缓冲区属于临界资源，上游线程将车辆提交到该缓冲区时本发明使用的是一种基于冲突检测的乐观并发策略，也就是非阻塞式同步(Non-BlockingSynchronizat1n)方案，不使用锁。具体为:
[0033]i)利用一条硬件级的原子指令:comp are-and-s wap (CAS)指令，CAS指令包含3个操作数:内存地址V，旧的预期值A，新值B，当且仅当V中原有的值和A值相等时，处理器用B值更新V中存储的值，否则就不执行更新，指令的返回值视硬件的不同或者返回一个布尔值表示是否更新成功，或者返回V中的旧值(不是新值B)，最后上述整个操作是原子性的。目前大部分微处理器都已经提供了 CAS指令，如x86，IA64中的CMPXCHG指令。
[0034]ii)利用CAS指令，上游线程将车辆与缓冲区中的值进行一次原子交换。若交换得到空值，则表示原缓冲区为空，表示车辆已经成功置入缓冲区中；否则上游线程交换得到另一辆车，说明缓冲区中已有其它车辆，表示车辆发生碰撞，流程终止。
[0035]步骤(2.1)、(2.2)的过程如图2所示。
[0036](2.3)下游路段所处的线程从缓冲区中获取车辆并把车辆加入到LVC中。
[0037]下游线程从缓冲区提取车辆也是使用CAS指令，下游线程将空值与缓存区中的值进行一次原子交换，交换后下游线程得到原缓冲区中的值(车辆)，而缓冲区被置空。另一方面，若下游线程交换后仍为空值，说明缓存区中原本就没有车，此时应该终止流程。否则，下游线程得到从上游线程驶入的车辆，此时应将车辆加入到下游车道的LVC的车辆容器中，并更新车辆状态，同时进行安全性检查。其中更新车辆状态指的是将车辆位置更新为属于下游路段，安全性检查检查指的是判断车辆位置是否与前面车辆重叠，若重叠表示车辆发生碰撞，此时应终止流程。整个过程如图3所示。
【主权项】
1.一种并行微观交通仿真中非阻塞式的车辆移动方法，其特征在于，包括以下步骤: (1)仿真初始化阶段，包括以下子步骤: (1.1)为每一个路段中的每一条车道创建一个车辆管理装置(LVC); (1.2)将每一个路段映射到一个线程； (2)仿真进行阶段，若车辆仅在路段内部移动，则不涉及线程间的交互，否则，若车辆从上游路段的车道进入下游路段中的车道，执行以下操作: (2.1)上游路段所处的线程将车辆从当前车道的LVC中除去，并将车辆标记为游离状态，表示车辆不再属于任何路段； (2.2)上游路段所处的线程将车辆提交到下游车道的缓冲区中； (2.3)下游路段的线程从缓冲区中提取车辆并把车辆加入到下游车道的LVC中，从而在并发环境下高性能地实现车辆的跨路段移动。
2.根据权利要求1所述的并行微观交通仿真中非阻塞式的车辆移动方法，其特征在于，所述步骤1.1中，每个LVC与每个路段中的每条车道是一一对应关系，用于管理车道上的车辆，LVC由两部分组成:一个缓冲区，最多容纳一个车辆对象的指针，用于保存刚刚从车道上游新进入的车辆；一个车辆容器，用于保存车道上的车辆，车辆按位置的先后顺序排序。
3.根据权利要求1所述的并行微观交通仿真中非阻塞式的车辆移动方法，其特征在于，所述步骤1.2具体为:首先确定线程数量，用户可通过参数指定线程数，若未指定，则默认线程数量即为CPU核心数量，假设线程数量为n，则创建η个线程，存放在线程池之中；接下来把整个路网包含的所有路段分为η组，每组固定分配给一个线程，组内所有路段中的车辆状态更新由该线程驱动；路段分组方法需保证每个组的路段数尽可能相等，以使每个线程负载均衡。
4.根据权利要求1所述的并行微观交通仿真中非阻塞式的车辆移动方法，其特征在于，所述步骤2.2具体为:利用compare-and-swap (CAS)指令，上游线程将车辆与下游车道缓冲区中的值进行一次原子交换，若交换得到空值，则表示原缓冲区为空，表示车辆已经成功放入缓冲区中；否则上游线程交换得到另一辆车，说明缓冲区中已有其它车辆，表示车辆发生碰撞，流程终止。
5.根据权利要求1所述的并行微观交通仿真中非阻塞式的车辆移动方法，其特征在于，所述步骤2.3具体为:利用CAS指令，下游线程将空值与缓存区中的值进行一次原子交换，交换后下游线程得到缓冲区中的值(车辆或空值)，而缓冲区被换入空值；交换得到两种结果:a)若下游线程交换得到空值，说明缓冲区中原本就没有车辆，此时终止流程；b)若下游线程交换得到的值非空，则该值即为从上游车道驶入的车辆，此时将车辆加入到下游车道的LVC中，将车辆状态更新为属于下游路段。
【专利摘要】本发明公开了一种并行微观交通仿真中非阻塞式的车辆移动方法，该方法首先为每个路段中的车道创建一个车辆管理装置，用于管理车道上的车辆，并将组成路网的所有路段划分成多个组，每个组分配一个线程负责仿真车辆的状态。当车辆跨路段行驶时，则会带来并发与线程竞争问题，为解决这个问题，本方法利用一条硬件级的原子指令CAS指令，实现基于冲突检测的乐观并发策略，也就是非阻塞式的同步方案，避免了锁的使用，降低了并发仿真环境下线程间交互的性能损耗，使得整个微观交通仿真系统的性能有了明显提升，满足了城市规模道路交通系统的实时仿真需要。
【IPC分类】G06F17-50
【公开号】CN104778299
【申请号】CN201510051451
【发明人】张子健, 陆宇飞, 陈奇, 江洁羽
【申请人】浙江成功软件开发有限公司
【公开日】2015年7月15日
【申请日】2015年2月1日
文档序号 :
【 8457398 】
技术研发人员：张子健,陆宇飞,陈奇,江洁羽
技术所有人：浙江成功软件开发有限公司
备 注：该技术已申请专利，仅供学习研究，如用于商业用途，请联系技术所有人。
声 明 ：此信息收集于网络，如果你是此专利的发明人不想本网站收录此信息请联系我们，我们会在第一时间删除
技术研发人员：张子健,陆宇飞,陈奇,江洁羽
技术所有人：浙江成功软件开发有限公司
备 注：该技术已申请专利，仅供学习研究，如用于商业用途，请联系技术所有人。
声 明 ：此信息收集于网络，如果你是此专利的发明人不想本网站收录此信息请联系我们，我们会在第一时间删除