[發明專利]一種并發分析的方法及裝置

有效

• 申請號: 201310262639.2
• 申請日: 2013-06-27
• 公開（公告）號: CN104252346B
• 公開（公告）日: 2017-08-29
• 發明（設計）人: 陳聰明;霍瑋;李豐;馮曉兵
• 申請（專利權）人: 華為技術有限公司;中國科學院計算技術研究所
• 主分類號: G06F9/44
• 分類號: G06F9/44;G06F17/30
• 代理公司: 北京中博世達專利商標代理有限公司11274
• 代理人: 申健

技術領域

本發明涉及程序分析技術領域，尤其涉及一種并發分析的方法及裝置。

背景技術

可能并發分析用于判斷給定的一個并發程序中的兩條語句是否可能在運行時并發執行，其結果可以服務于其他類型的程序分析技術例如指針分析，也可服務于并發程序的編譯優化，同時還可以服務于并發錯誤的檢測，比如說，如果預先知曉一個并發程序中的哪些部分之間是可能并發的，則可以顯著減少數據競爭這類錯誤的誤報信息。所以說可能并發分析是并發程序分析領域中一類重要的程序分析方法。

現有技術基于迭代數據流的方法進行可能并發分析，在該分析方法中，根據不同語句的并發語義為其定義相應的數據流方程，之后在迭代過程中計算得到所有語句的可能并發集合。具體的，該方法首先需要構造并發程序的控制流圖，之后根據控制流圖構造并發執行圖(Parallel Execution Graph，PEG)，該并發執行圖為控制流圖的程序表示。在PEG上標注含有不同并發語義的節點。并發語義包括線程創建，線程注銷以及線程間通信等等，其中，線程創建的并發語義代表新的可能并發信息的產生，線程注銷的并發語義代表消除已有的可能并發信息，線程間通信的并發語義代表線程間時序關系的存在。不同的并發語義可定義不同的數據流方程。由于PEG基于并發控制流圖構建，因此最終的分析結構就轉換為求解PEG上分屬不同線程的不同節點之間是否并發。在迭代過程中，以工作集的方式保存PEG節點信息，每次迭代處理工作集中的一個節點，按照預先定義的數據流方程計算可能并發信息時會有新的節點加入。重復此過程，直到工作集為空，得到最終的分析結果。

在實現上述現有技術的過程中，發明人發現至少存在如下問題：在分析PEG上不同節點之間是否并發的過程中，處理過程繁瑣，從而導致并發分析的效率低。

發明內容

本發明的實施例提供一種并發分析的方法及裝置，在對PEG上不同節點間進行并發分析的過程中，簡化處理了過程，解決了并發分析效率低的問題。

為達到上述目的，本發明的實施例采用如下技術方案：

第一方面，提供了一種并發分析的方法，包括：

獲取由并發執行圖PEG中的節點組成的待處理序列，所述待處理序列為減少所述節點重復次數的嚴格拓撲序列；

根據預設規則對所述待處理序列中的節點進行遍歷，所述預設規則用于尋找待遍歷的節點。

在第一方面的第一種可能實現方式中，所述獲取待處理序列包括：

獲取所述PEG的根節點，并將所述根節點壓入預設棧中，所述預設棧用于存儲所述PEG中的根節點和/或所述PEG中入度為0的節點；

獲取所述預設棧的棧頂節點，將所述棧頂節點加入所述待處理序列；

獲取所述棧頂節點的后繼節點，并在所述PEG中刪除所述棧頂節點與所述后繼節點組成的邊。

結合第一方面、第一方面的第一種可能實現方式，在第一方面的第二中可能實現方式中，獲取所述棧頂節點的后繼節點，具體包括：

當確定所述棧頂節點為線程創建點時，獲取并刪除所述棧頂節點先創建的線程的首節點與所述棧頂節點組成的邊，并將所述首節點壓入所述預設棧；

當確定所述棧頂節點不是線程創建點時，獲取并刪除所述棧頂節點的所有后繼節點與所述棧頂節點組成的邊，并將所述后繼節點中入度為0的所述后繼節點壓入所述預設棧中。

結合第一方面或第一方面的第一種可能實現方式或第一方面的第二種可能實現方式中任意一種實現方式，在第一方面的第三種可能實現方式中，還包括：

為所述PEG中的線程設置并行層次，所述并行層次表示所述PEG中線程之間的關系。

結合第一方面、第一方面的第一種可能實現方式、第一方面的第二種可能實現方式、第一放方面的第三種可能實現方式，在第一方面的第四種可能實現方式中，還包括：

確定當前遍歷的節點在所述待處理序列中的第一位置；

在所述待處理序列中，且在所述第一位置之后，查找包含于工作集中的節點；

當查找到包含于所述工作集中的節點時，確定所述工作集中的節點在所述待處理序列中的位置為第二位置；

當未查找到包含于所述工作集中的節點時，從所述待處理序列中的第一個節點開始向后查找。

第二方面，提供了一種并發分析的裝置，包括：

獲取單元，用于由獲取PEG中節點組成的待處理序列，所述待處理序列為減少所述節點重復次數的嚴格拓撲序列；

遍歷單元，用于根據預設規則對所述獲取單元獲取到的所述待處理序列中的節點進行遍歷，所述預設規則用于尋找待遍歷的節點。