• / 12
  • 下載費用:30 金幣  

一種基于并發控制流圖的JAVA并發程序路徑剖析方法.pdf

摘要
申請專利號:

CN201610577045.4

申請日:

2016.07.20

公開號:

CN106257425A

公開日:

2016.12.28

當前法律狀態:

實審

有效性:

審中

法律詳情: 授權|||實質審查的生效IPC(主分類):G06F 9/52申請日:20160720|||公開
IPC分類號: G06F9/52 主分類號: G06F9/52
申請人: 東南大學
發明人: 王璐璐; 李必信; 廖力; 周穎
地址: 211103 江蘇省南京市江寧區東山街道萬安西路59號
優先權:
專利代理機構: 南京瑞弘專利商標事務所(普通合伙) 32249 代理人: 楊曉玲
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201610577045.4

授權公告號:

||||||

法律狀態公告日:

2019.04.09|||2017.01.25|||2016.12.28

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

本發明公布了一種基于并發控制流圖的Java并發程序路徑剖析方法,通過分析Java源碼中的線程內控制流關系和線程間的聯系(包括線程的創建和各類同步關系),構建Java并發控制流圖;在Java并發控制流圖上實施并發路徑剖析算法,并按照算法結果對Java源碼進行插樁,使得插樁后的源碼在執行過程中能夠生成并發程序的路徑剖析結果。

權利要求書

1.一種基于并發控制流圖的Java并發程序路徑剖析方法,其特征在于,該方法包括如
下步驟:
步驟1)從Java并發程序源碼中獲取各個線程內部的控制流結構和線程之間的并發關
系;
步驟2)首先在各個線程內部的控制流結構的基礎之上,按照線程之間的并發關系類
型,對不同的并發元素分別做如下處理,最終構建得到并發控制流圖:
a)對于線程創建關系,增加從線程創建節點到被創建線程入口節點的控制流邊;
b)對于“通知-阻塞”的線程同步關系,識別同步控制語句,按照每條同步控制語句的含
義,刪除線程內部因同步而消失的控制流圖結構,增加線程之間因同步而出現的控制流圖
結構,使得并發控制流圖正確表示線程中每條語句的執行先后次序;
c)對于FutureGet機制的線程同步關系,則在并發控制流圖中增加通知節點到被通知
節點的控制流邊,并刪去被通知節點在線程內部的所有出邊;
步驟3)在所述步驟2獲得的并發控制流圖中實施剖析算法,并將所需探針語句插樁到
原并發程序中,保證插樁后的并發程序在任意的執行情況下,每個線程的執行軌跡均由唯
一的路徑編碼標識;
步驟4)執行插樁后的程序,在程序執行過程中,通過所插樁的探針語句計算路徑編碼
并統計路徑頻率,作為最終的剖析結果。
2.根據權利要求1所述的基于并發控制流圖的Java并發程序路徑剖析方法,其特征是,
所述步驟3)中所需探針語句使用多個探針變量,在插樁到原并發程序的過程中按照Java線
程ID來動態分配每個線程唯一的探針變量。
3.根據權利要求1或2所述的基于并發控制流圖的Java并發程序路徑剖析方法,其特征
是,所述步驟3中的所需探針語句根據全路徑剖析法計算得到。

說明書

一種基于并發控制流圖的Java并發程序路徑剖析方法

技術領域

本發明屬于動態程序分析領域,涉及一種基于并發控制流圖的Java并發程序路徑
剖析方法。

背景技術

動態程序分析是基于程序執行的分析技術,所以收集程序的執行信息是動態分析
方法不可缺少的一部分。為了高效的收集路徑的執行信息,現有技術普遍采用路徑編碼的
方式,將每條路徑映射到一個或一組整數,以快速的判斷當前執行的路徑是否與已執行的
某條路徑相同,方便的進行執行次數的累加。相應的,為了實現路徑的編碼,在程序執行之
前,首先要對程序進行插樁,在分析程序的控制流圖(CFG,control flow graph)的基礎上,
在程序的相關位置插入一個或多個探針變量的值操作語句及相關的邏輯控制、探針收集等
語句。這樣當程序每一次執行完畢之后,所收集的路徑編碼計算結果就唯一確定該次執行
的路徑。

對于單線程程序,在其控制流分析的基礎上,現有的技術可以將每條可執行路徑
編碼為一個唯一的非負整數或一串唯一的整數集合;為了實現該種路徑編碼,在程序中插
樁的語句需要隨著目標程序的執行而執行,在執行完畢時計算出最終的路徑編碼。

對于并發程序,傳統的剖析方法難以實施的困難主要有二:并發程序增加了線程
的創建、終止和交互機制,導致控制流結構和執行空間都與單線程程序有很大的不同;并發
程序中各個線程交替混合執行,導致探針變量的計算語句也可能發生亂序的情況,難以處
理。

在實際的Java軟件中,并發機制的應用較為廣泛,多個線程之間的復雜關系會導
致其控制流圖執行混亂,因此,針對并發程序的實用剖析方案不可缺少。

發明內容

技術問題:本發明提供一種其中探針計算與路徑編碼方式能夠保證并發程序中每
個線程的執行路徑的編碼具有唯一性,達到能夠精確收集并發程序執行信息的效果的基于
并發控制流圖的Java并發程序路徑剖析方法。

技術方案:本發明的基于并發控制流圖的Java并發程序路徑剖析方法,包括如下
步驟:

步驟1)從Java并發程序源碼中獲取各個線程內部的控制流結構和線程之間的并
發關系;

步驟2)首先在各個線程內部的控制流結構的基礎之上,按照線程之間的并發關系
類型,對不同的并發元素分別做如下處理,最終構建得到并發控制流圖:

a)對于線程創建關系,增加從線程創建節點到被創建線程入口節點的控制流邊;

b)對于“通知-阻塞”的線程同步關系,識別同步控制語句,按照每條同步控制語句
的含義,刪除線程內部因同步而消失的控制流圖結構,增加線程之間因同步而出現的控制
流圖結構,使得并發控制流圖正確表示線程中每條語句的執行先后次序;

c)對于FutureGet機制的線程同步關系,增加通知節點到被通知節點的控制流邊,
并被通知節點在線程內部的所有出邊;

步驟3)在所述步驟2獲得的并發控制流圖中實施剖析算法,并將所需探針語句插
樁到原并發程序中,保證插樁后的并發程序在任意的執行情況下,每個線程的執行軌跡均
由唯一的路徑編碼標識;

步驟4)執行插樁后的程序,在程序執行過程中,通過所插樁的探針語句計算路徑
編碼并統計路徑頻率,作為最終的剖析結果。

進一步的,本發明方法中,步驟3)中所需探針語句使用多個探針變量,在插樁到原
并發程序的過程中按照Java線程ID來動態分配每個線程唯一的探針變量。

進一步的,本發明方法中,步驟3中的所需探針語句根據全路徑剖析法計算得到。

本發明提出了一種基于并發控制流圖的Java并發程序路徑剖析方法,主要是在合
并多個線程內部控制流圖的基礎上,通過分析并發相關代碼,增加、刪除相應的控制流邊,
以構建并發控制流圖,進而在并發控制流圖的基礎上實施路徑剖析方法。

有益效果:本發明與現有技術相比,具有以下優點:

(1)現有的路徑剖析技術未能構建線程之間的控制流關系,亦缺乏對并發程序中
每個線程的剖析能力。本發明由于增加了對線程間創建關系和同步關系等信息的處理,構
建了并發控制流圖,能夠在執行過程中區分每個線程執行過程中和其他線程的不同同步狀
態,進而使得所編碼的路徑信息能夠包含每個線程的創建、執行和終止,保證了準確剖析并
發Java程序的能力。

(2)現有的路徑剖析技術普遍采用單變量作為探針變量,導致多個線程的探針語
句執行互相影響,難以區分。本發明方法利用了Java語言的線程ID機制,針對每個線程按照
其線程ID動態分配一個特有的探針變量進行編碼計算,各個線程之間的執行過程中的路徑
編碼操作互不影響,能夠處理并發程序中同時執行的多個線程。即使是由同一段代碼創建
的不同線程,由于其線程ID不同,故也能夠在剖析過程中明確地區分,獲取每個線程相應的
剖析結果。

附圖說明

圖1是本發明的體系結構。

圖2是并發控制流圖構造中對線程創建關系的處理示意圖。

圖3是并發控制流圖構造中對線程“通知-阻塞”同步關系的處理示意圖。

圖4是并發控制流圖構造中對線程“FutureGet”同步關系的處理示意圖。

圖5是示例程序對應的單線程控制流圖。

圖6是針對圖5生成的并發控制流圖。

具體實施方式

下面結合實施例和說明書附圖對本發明作進一步的說明。

技術中的探針計算和路徑編碼是密不可分的兩個部分,路徑的編碼與插樁的探針
語句相對應,而探針語句又由所插樁的探針語句在目標程序執行過程中計算得出。精確的
路徑編碼要求任一路徑的編碼具有唯一性,相應的,不同路徑上所執行的的探針語句也必
須計算出不同的變量取值。

本發明方法的基礎在于并發控制流圖的構建,該圖描述了線程內部的控制流關系
和線程之間的同步執行關系;在并發控制流圖模型上實施相應的探針插樁方法,該方法保
證了并發執行路徑編碼的唯一性,并能夠簡明的得以實現。

一、體系結構

圖1給出了本方法的體系結構。下面給出幾個主要部分的具體說明。

1并發控制流分析

該部分的功能在于從源代碼中獲取線程內部的控制流關系和線程之間的同步執
行關系等相關信息,以應用于探針插樁方法。在本發明中需要的控制流信息主要包括單個
方法內部的控制流圖、方法之間的調用關系以及線程之間的控制流關系。

a)對于線程創建關系,如果存在A線程控制流圖中的Ax節點創建了線程B,線程B的
入口節點為B1,那么在并發控制流圖中增加控制流邊(Ax,B1),如圖2所示:圖左側是線程A和
線程B的控制流圖以及A對B的創建關系描述,右側是相應生成的并發控制流圖。

b)對于“通知-阻塞”的線程同步關系,通過識別同步控制語句修正并發控制流圖。
在“通知-阻塞”中通知節點分為4類:(1)繼承自Object基類的notify、notifyAll;(2)
countdown機制的刪減語句;(3)條件變量的signal、signalAll;(4)通過Phaser類實現的
arrive通知語句。與通知節點對應的阻塞節點分別為wait,await,await,awaitAdvance。在
并發控制流圖中,構建與阻塞語句相對應的通知語句節點到該阻塞語句后續執行節點的控
制流邊,同時在線程內部的控制流結構中刪除阻塞語句與其后續執行節點的控制流邊,如
圖3所示(圖中含義同圖2)。

c)對于FutureGet機制的線程同步關系,如果存在A線程控制流圖中的Ax節點調用
了線程B的get()或join()方法,線程B的出口節點為By,那么在并發控制流圖中增加控制流
邊(By,Ax),并刪去A線程控制流圖中的Ax節點的出邊,如圖4所示(圖中含義同圖2)。

2并發路徑剖析算法

在單個過程的控制流中,探針計算方式需要能夠區分不同的路徑。傳統的單線程
路徑剖析算法計算方式為:輸入控制流圖,通過分析控制流圖的結構決定如何進行插樁。所
插樁的語句定義了個整數類型的探針變量r,在程序的不同位置插樁r相關的操作語句(即
探針,包含對r的賦值、累加和累乘等操作),使r的值隨著程序執行而變化,與路徑編碼相對
應。

在此基礎上,本發明的并發路徑剖析算法改進包括兩部分:

a)控制流圖的改進。有別于傳統路徑剖析算法以單線程控制流圖作為輸入,本發
明通過前一步驟生成了并發控制流圖,進而在并發控制流圖上實施傳統的單線程路徑剖析
算法,保證單個線程的剖析能夠正確完成。

b)插裝方式的改進。有別于傳統路徑剖析算法使用單一變量作為探針變量,本發
明使用的探針變量為一組整數類型的變量ri,對于并發控制流圖中的每一個可能執行的線
程使用一個變量作為其探針變量,避免并發機制中的無序執行對探針計算的干擾,保證不
同線程所執行的路徑編碼互不干涉。

具體的計算方式是:所有探針變量由一個整數類型的變量數組實現;每個線程創
建時,根據線程編號i申請本線程的探針變量ri,并初始化ri;在線程執行過程中,每個線程
的探針語句通過當前線程編號區分,不會互相影響,進而保證整個并發程序的路徑剖析能
夠正確實施。

3執行與路徑編碼

對于靜態路徑有限的控制流圖,本發明采用的路徑編碼方式是:在目標程序執行
之前,枚舉所有靜態無環路徑,并建立每條路徑與其編碼的一一對應關系表;在每次執行完
畢時,按照所收集的編碼查表即可得知所執行的路徑。

對于有循環語句、遞歸調用或循環線程依賴的情況下,靜態路徑數目無限,無法枚
舉。這樣在目標程序執行之前,無法列出路徑編碼與路徑的一一對應表。為了從路徑編碼的
統計結果得出相應的路徑執行結果,需要采用現有剖析領域中的路徑回溯的方法獲取編碼
所對應的路徑。

在插樁后的代碼中,探針語句隨著并發程序的執行過程不斷計算各個線程的路徑
編碼,在線程終止及程序終止時,使用的探針變量個數即為所執行的線程數目,每個探針變
量的值即為每個線程執行路徑的編碼。

二、方法流程

本方法通過對目標程序控制流結構的分析,計算出需要在程序源碼中插樁的探
針,然后通過目標程序的執行以收集路徑編碼,得出最后的執行結果。具體的步驟如下:

步驟1)從程序源碼中獲取各個線程內部和線程之間的控制結構,構造并發控制流
圖;

步驟2)對于并發控制流圖實施并發路徑剖析算法,計算相應的探針并插樁到程序
源碼之中;

步驟3)執行插樁后的程序,并收集相應的路徑編碼及其頻率;

步驟4)由收集到的信息在并發控制流圖上進行回溯,將路徑編碼轉化為路徑,以
獲取并發路徑的執行結果。

實施例:

為了方便描述,我們假定有如下簡化的應用實例,目標并發程序的源碼如下所示:


該代碼功能為:生產者Producer和消費者Comsumer并發執行,Producer向
Container的棧中壓入數據,Consumer從Container的棧中取出數據,如果棧滿,則Producer
線程等待,如果棧空,則Consumer線程等待。

該程序的單線程中方法內和方法間的控制流結構如圖5所示。

按照本發明的并發控制流圖構造方法,在圖5的基礎上做如下修正(參見圖6):

1.分析線程創建關系,增加線程創建邊:4→28,5→-39;

2.分析線程“通知-阻塞”關系,可知程序中通知節點為16和22,相應的阻塞節點為
20和13,而阻塞節點的后繼節點為21和14。因此增加邊16→21,22→14,刪除邊13→14,21→
22。

在并發控制流圖上插樁的探針如下(每個線程使用自身ID申請、使用唯一的探針
變量ri):

12→14:ri=ri*2;

22→14:ri=ri*2+1;

19→21:ri=ri*2;

16→21:ri=ri*2+1;

4→28:ri=ri*2;

31→28:ri=ri*2+1;

30→31:ri=ri*2;

16→31:ri=ri*2+1;

5→39:ri=ri*2;

42→39:ri=ri*2+1;

41→42:ri=ri*2;

23→42:ri=ri*2+1。

假設有如下執行過程:



執行過程中依次運行了如下邊上的探針(計算后的探針變量的值在括號中):

Producer:(r2=0)4→28(r2=0),12→14(r2=0),16→31(r2=1),31→28(r2=3),
22→14(r2=7),16→31(r2=15)

Consumer:(r3=0)5→39(r3=0),19→21(r3=0),23→42(r3=1),42→39(r3=3),
19→21(r3=6),23→42(r3=13)

相應的路徑編碼:Producer線程為15,Consumer線程為13。

如果另一次執行過程為:



那么執行過程中依次運行了如下探針:

Producer:(r2=0)4→28(r2=0),12→14(r2=0),16→31(r2=1),31→28(r2=3),
22→14(r2=7),16→31(r2=15)

Consumer:(r3=0)5→39(r3=0),19→21(r3=0),23→42(r3=1),42→39(r3=3),
16→21(r3=7),23→42(r3=15)

相應的路徑編碼:Producer線程為15,Consumer線程為15。

上述實施例僅是本發明的優選實施方式,應當指出:對于本技術領域的普通技術
人員來說,在不脫離本發明原理的前提下,還可以做出若干改進和等同替換,這些對本發明
權利要求進行改進和等同替換后的技術方案,均落入本發明的保護范圍。

關 鍵 詞:
一種 基于 并發 控制 JAVA 程序 路徑 剖析 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:一種基于并發控制流圖的JAVA并發程序路徑剖析方法.pdf
鏈接地址:http://www.rgyfuv.icu/p-6100717.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
山东11选5中奖结果走势图