并發(fā)程序切片系統(tǒng)的研究與實(shí)現(xiàn).pdf

1、并發(fā)程序切片是一種重要的并發(fā)程序分析手段。不同并發(fā)單元中并發(fā)執(zhí)行語句之間的數(shù)據(jù)依賴（干擾依賴）使得并發(fā)程序語句間的依賴關(guān)系具有不可傳遞性，直接遍歷依賴圖，程序切片精度較低?，F(xiàn)有并發(fā)程序切片方法主要通過判斷依賴路徑可行性等方法提高程序切片精度，但未能從根本上解決并發(fā)程序依賴關(guān)系不可傳遞性問題。
　　為進(jìn)一步提高并發(fā)程序切片精度，我們提出了一種基于程序可達(dá)圖的并發(fā)程序切片方法，該方法基于程序可達(dá)圖從全局分析并發(fā)程序的依賴關(guān)系，構(gòu)造一種

2、以程序狀態(tài)和語句二元組為節(jié)點(diǎn)的、依賴關(guān)系具有可傳遞性的并發(fā)程序依賴圖MSDG，較好地解決了依賴關(guān)系不可傳遞性問題，提高了切片精度。為驗(yàn)證該方法的有效性，本文在前期理論研究的基礎(chǔ)上，針對Java并發(fā)程序，通過開源工具Soot獲取程序基本信息，實(shí)現(xiàn)基于程序可達(dá)圖的Java并發(fā)程序切片系統(tǒng)以及兩種有代表性的并發(fā)程序切片方法，并進(jìn)行了相應(yīng)的實(shí)驗(yàn)研究，主要取得了以下研究成果:
　　(1)采用Soot抽取Java程序的控制流信息，并通過指針分

3、析和逃逸分析獲取數(shù)據(jù)定義和使用信息，構(gòu)造并發(fā)程序中各線程的系統(tǒng)依賴圖(SDG)，在此基礎(chǔ)上添加干擾依賴邊構(gòu)造線程間系統(tǒng)依賴圖(TSDG)。
　　(2)實(shí)現(xiàn)M.Nanda提出的三色兩趟式并發(fā)程序切片方法和基于拓?fù)涮柕牟l(fā)程序切片方法。三色兩趟式并發(fā)程序切片方法是上下文不敏感的，且未考慮語句間的先后時序關(guān)系，切片結(jié)果不準(zhǔn)確。基于拓?fù)涮柕牟l(fā)程序切片方法確保依賴序列中屬于同一線程的語句形成一個可執(zhí)行路徑，解決了上下文不敏感問題和語句間時

4、序不可達(dá)問題。
　　(3)實(shí)現(xiàn)基于程序可達(dá)圖的Java并發(fā)程序切片系統(tǒng)。在該系統(tǒng)中，我們以各線程控制流圖為輸入構(gòu)造線程交互圖(TIG)，進(jìn)而構(gòu)造線程交互可達(dá)圖（TIRG），然后基于TIRG圖進(jìn)行全局依賴性分析構(gòu)造并發(fā)程序依賴圖(MSDG)。在不影響切片精度的前提下，為了提高切片效率，我們采用一種混合式的程序切片方法——三趟式并發(fā)子程序間切片方法。該方法對不涉及線程間交互的子程序采用組合式子程序間切片方法，對涉及線程間交互的子程序進(jìn)

5、行內(nèi)聯(lián)，然后基于MSDG圖進(jìn)行計(jì)算切片。
　　(4)使用基于穩(wěn)固集和睡眠集的偏序約簡技術(shù)對線程交互可達(dá)圖進(jìn)行約簡。實(shí)驗(yàn)結(jié)果表明，約簡后TIRG圖和基于約簡后TIRG圖構(gòu)造的MSDG圖的規(guī)模顯著減小，切片效率也有相應(yīng)地提高，且基于約簡和未約簡的線程交互可達(dá)圖構(gòu)造的MSDG圖在計(jì)算并發(fā)程序切片時是等價的。
　　(5)開展切片實(shí)驗(yàn)研究，實(shí)驗(yàn)結(jié)果表明，基于程序可達(dá)圖的并發(fā)程序切片方法較其他方法能獲得精度更高的切片，且在大部分實(shí)驗(yàn)中切