[發明專利]并行微觀交通仿真中非阻塞式的車輛移動方法

有效

• 申請號: 201510051451.2
• 申請日: 2015-02-01
• 公開（公告）號: CN104778299B
• 公開（公告）日: 2017-08-25
• 發明（設計）人: 張子健;陸宇飛;陳奇;江潔羽
• 申請（專利權）人: 浙江成功軟件開發有限公司
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 杭州求是專利事務所有限公司33200
• 代理人: 邱啟旺

技術領域

本發明涉及系統仿真領域、微觀交通仿真領域，尤其涉及一種并行環境下的微觀交通仿真中非阻塞式的車輛移動方法。

背景技術

交通問題一直是一個嚴重的社會問題，制約著城市的發展。由于道路交通系統是一個復雜的巨系統，單純的理論研究或實驗方法都不能很好的勝任，而基于計算機仿真技術的微觀交通仿真系統則是分析和解決交通問題的有效手段。由于微觀交通仿真系統需要模擬每一輛車的行為，因此對計算機的性能要求較高，傳統的微觀交通仿真系統不能仿真大范圍的交通系統。

目前已有的并行微觀交通仿真方法分兩類，一類是創建多個線程，每個線程完成特定的工作，但線程是非對稱的，也就是每個線程負責不同的任務，因此難以平衡線程之間的負載，也不能使線程數量根據CPU核心數靈活增減；另一類并行仿真方法線程是對等的，但是在控制線程相互作用時使用了鎖，即阻塞式的同步方案。無論哪種方案，都還沒有達到硬件性能的極限，影響微觀仿真系統性能的進一步提升。

發明內容

本發明的目的在于針對現有技術的不足，提供一種并行微觀交通仿真中非阻塞式的車輛移動方法。

本發明的目的是通過以下技術方案來實現的：一種并行微觀交通仿真中非阻塞式的車輛移動方法，包括以下步驟：

(1)仿真初始化階段，包括以下子步驟：

(1.1)為每一個路段中的每一條車道創建一個車輛管理裝置(以下簡稱LVC)；

(1.2)將每一個路段映射到一個線程；

(2)仿真進行階段，若車輛僅在路段內部移動，則不涉及線程間的交互，否則，若車輛從上游路段的車道進入下游路段中的車道，由于不同路段分屬于不同的線程，因此會產生并發和競爭，此時需要執行以下操作：

(2.1)上游路段所處的線程將車輛從當前車道的LVC中除去，并將車輛標記為游離狀態，表示車輛不再屬于任何路段；

(2.2)上游路段所處的線程將車輛提交到下游車道的緩沖區中；

(2.3)下游路段的線程從緩沖區中提取車輛并把車輛加入到下游車道的LVC中，從而在并發環境下高性能地實現車輛的跨路段移動。

進一步地，所述步驟1.1中，每個LVC與每個路段中的每條車道是一一對應關系，用于管理車道上的車輛，LVC由兩部分組成：一個緩沖區，最多容納一個車輛對象的指針，用于保存剛剛從車道上游新進入的車輛；一個車輛容器，用于保存車道上的車輛，車輛按位置的先后順序排序。

進一步地，所述步驟1.2具體為：首先確定線程數量，用戶可通過參數指定線程數，若未指定，則默認線程數量即為CPU核心數量，假設線程數量為n，則創建n個線程，存放在線程池之中；接下來把整個路網包含的所有路段分為n組，每組固定分配給一個線程，組內所有路段中的車輛狀態更新由該線程驅動；路段分組方法沒有特殊要求，只需要保證每個組的路段數盡可能相等，以使每個線程負載均衡。

進一步地，所述步驟2.2中，所述下游路段車道對應的緩沖區屬于臨界資源，上游線程將車輛提交到該緩沖區使用的是一種基于沖突檢測的樂觀并發策略，也就是非阻塞式同步(Non-Blocking Synchronization)方案，不使用鎖，具體為：利用CAS指令，上游線程將車輛與緩沖區中的值進行一次原子交換，若交換得到空值，則表示原緩沖區為空，表示車輛已經成功置入緩沖區中；否則上游線程交換得到另一輛車，說明緩沖區中已有其它車輛，表示車輛發生碰撞，流程終止；所述CAS(compare-and-swap)指令為硬件級的原子指令，CAS指令包含3個操作數：內存地址V，舊的預期值A，新值B，當且僅當V中原有的值和A值相等時，處理器用B值更新V中存儲的值，否則就不執行更新，指令的返回值視硬件的不同或者返回一個布爾值表示是否更新成功，或者返回V中的舊值(不是新值B)，上述整個操作是原子性的。

進一步地，所述步驟2.3中，下游路段所處的線程從緩沖區中獲取車輛同樣使用CAS指令，具體為：下游線程將空值與緩存區中的值進行一次原子交換，交換后下游線程得到原緩沖區中的值(車輛)，而緩沖區被置空；若下游線程交換后仍為空值，說明緩存區中原本就沒有車，此時終止流程；否則，下游線程得到從上游線程駛入的車輛，此時應將車輛加入到下游車道的LVC的車輛容器中，并更新車輛的位置狀態為隸屬于下游車道，同時進行安全性檢查；安全性檢查指的是判斷車輛位置是否與前面車輛重疊，若重疊表示車輛發生碰撞，此時終止流程。