當(dāng)今世界多核硬件的高速發(fā)展使得多線程程序逐漸被廣泛使用,但是往往由于線程之間交錯(cuò)模式的不確定性,多線程程序易于遭遇多線程缺陷,因而保證多線程程序的正確性及其重要而又及其富有挑戰(zhàn)性。定位到多線程程序中導(dǎo)致缺陷發(fā)生的代碼位置,并且理清導(dǎo)致缺陷發(fā)生的根本原因,通常需要程序開發(fā)人員話花費(fèi)較多的時(shí)間和精力。在這篇文章中,我們?cè)贒elta-Debugging算法的基礎(chǔ)上,基于內(nèi)存讀寫模式的抽象表達(dá),提出了一種對(duì)多線程程序缺陷的自動(dòng)化檢測和缺陷原因分析方法DDM。我們的核心思想是找到導(dǎo)致缺陷發(fā)生的最小的內(nèi)存讀寫模式集合,從而達(dá)到精準(zhǔn)定位和準(zhǔn)確分析的目標(biāo)。首先,當(dāng)給出一個(gè)被測的有缺陷的程序,我們記錄程序運(yùn)行過程中每一步的線程調(diào)度執(zhí)行,然后從所有的執(zhí)行步驟中抽離出所有可能的內(nèi)存讀寫模式,首先找出內(nèi)存讀寫模式集最接近的一對(duì)失敗和成功執(zhí)行序列,這兩個(gè)集合之間的差異我們叫做差異集。接下來,進(jìn)一步我們擴(kuò)展Delta-Debugging算法,并將其應(yīng)用到多線程程序的內(nèi)存讀寫模式中,進(jìn)行缺陷檢測。我們利用Java Pathfinder對(duì)差異集中的內(nèi)存讀寫模式進(jìn)行打斷再執(zhí)行,從而驗(yàn)證它們是否會(huì)導(dǎo)致缺陷發(fā)生。由于多線程程序的內(nèi)存讀寫模式彼此互相關(guān)聯(lián),有黏性,因而將Delta-Debugging算法應(yīng)用到多線程程序有一定的難度。因此針對(duì)多線程程序的線程調(diào)度方案,我們提出了一個(gè)新的函數(shù)test(U,f)進(jìn)行實(shí)現(xiàn)。最后,我們將這個(gè)想法用真實(shí)的程序進(jìn)行實(shí)驗(yàn)驗(yàn)證和多維度研究。實(shí)驗(yàn)驗(yàn)證過程以SIR中的程序?yàn)槔?將我們的方法應(yīng)用于26個(gè)多線程缺陷上,通過與其他經(jīng)典的方法進(jìn)行對(duì)比,實(shí)驗(yàn)結(jié)果表明我們的方法可以有效地給出導(dǎo)致多線程缺陷的最小內(nèi)存讀寫模式集合。此外,通過與經(jīng)典方法的結(jié)合,我們的方法還可對(duì)已有方法的定位結(jié)果進(jìn)行改進(jìn)。
【學(xué)位單位】：天津大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2018
【中圖分類】：TP311.53
【部分圖文】：

因?yàn)樗遣l(fā)缺陷的檢測、規(guī)避和修復(fù)操作的前提準(zhǔn)備。對(duì)于大多數(shù)的并發(fā)缺陷來說，如果在并發(fā)程序執(zhí)行過程中不對(duì)線程的交錯(cuò)進(jìn)行任何人為干擾的話，是很難暴露出并發(fā)缺陷的。壓力測試是一個(gè)常用而且傳統(tǒng)的暴露并發(fā)缺陷的方法，但是壓力測試是不充分的，因?yàn)閴毫y試趨向于基于一個(gè)相同的輸入，重復(fù)測試相似的線程。因此，通過壓力測試來暴露出一個(gè)不易發(fā)生的并發(fā)缺陷是幾乎不可能的。并發(fā)缺陷通常被暴露的概率很低，總共有以下幾個(gè)原因：（1）線程交錯(cuò)空間巨大，并且隨著代碼行數(shù)的增加，線程交錯(cuò)空間呈指數(shù)倍增加。（2）并發(fā)缺陷通常都隱藏在某些不常見或者特殊的內(nèi)存讀寫線程交錯(cuò)模式中。（3）如果沒有額外的線程交錯(cuò)干擾，多線程程序通常都會(huì)按照相同的線程交錯(cuò)模式執(zhí)行。為了克服這些難題，研究學(xué)者們做了大量的工作并且提出了不同的解決方法。一個(gè)好的并發(fā)缺陷暴露方法必須是有效的，高效的而且是可重復(fù)使用的，這樣才可以被大多數(shù)的程序開發(fā)人員所接受。圖 1-1 展示了多線程缺陷暴露方法的流程。多線程程序首先被經(jīng)過分析來確定可疑的線程交錯(cuò)。然后被測程序會(huì)被應(yīng)用一個(gè)可控的測試方法，并且施加不同的策略，從而可以暴露并發(fā)缺陷。

第 1 章 緒論了減少誤報(bào)率和漏報(bào)率，并且提出有效的缺陷自動(dòng)檢測方法，已經(jīng)有許多方法被提出。圖 1-2 展示了并發(fā)缺陷檢測過程的完整步驟。給出一個(gè)多線程程序 P 和測試用例集 T，可以應(yīng)用不同的方法來檢測并發(fā)缺陷。基于檢測過程中被測程序是否被執(zhí)行過，我們把所有的檢測方法分成三類：靜態(tài)方法，動(dòng)態(tài)方法和混合方法。

2.2 多線程程序缺陷的分類和特點(diǎn)Tan 等人[23]對(duì)一共 2060 個(gè)真實(shí)程序中的軟件缺陷進(jìn)行了一個(gè)研究，并將所有缺陷分為四大類：內(nèi)存缺陷，語義缺陷，并發(fā)缺陷和性能缺陷。在所有缺陷中，本文開展的研究集中于并發(fā)缺陷，而并發(fā)缺陷又可分為四類：數(shù)據(jù)競爭（dataraces），原子性違背（atomicity violations），順序違背（order violations）和死鎖（deadlocks）。數(shù)據(jù)競爭缺陷定義為當(dāng)有兩個(gè)并發(fā)的內(nèi)存訪問操作都針對(duì)同一個(gè)內(nèi)存地址，且這兩個(gè)操作分別來自兩個(gè)線程，其中至少有一個(gè)操作必須為寫操作。圖 2-1 展示了一個(gè)數(shù)據(jù)競爭缺陷的例子，我們截取自快速傅里葉變換（fast Fouriertransform，簡稱 FFT）這個(gè)算法[24]。在這個(gè)例子中，程序開發(fā)人員原本計(jì)劃在執(zhí)行線程 1 的 S1 語句之前執(zhí)行線程 2 中的 S2 語句。但是由于相應(yīng)的保證程序按照特定順序執(zhí)行的同步語句的缺失，這個(gè)確定的順序不能完全被保證。結(jié)果，在某些情況中，S1可能會(huì)在S2之前執(zhí)行，而這樣的順序必將導(dǎo)致一個(gè)錯(cuò)誤的結(jié)果。
【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 ;你的腦袋有幾根線[J];廣東第二課堂(下半月中學(xué)生閱讀);2016年10期

2 張蕊;;計(jì)算機(jī)中的多線程問題[J];科技傳播;2013年22期

3 張紅斌;李廣麗;劉覺夫;;網(wǎng)絡(luò)機(jī)器人多線程爬行的研究與實(shí)現(xiàn)[J];計(jì)算機(jī)應(yīng)用與軟件;2010年01期

4 潘海波;;多線程掃描局域網(wǎng)內(nèi)的計(jì)算機(jī)[J];黑龍江科技信息;2009年19期

5 張?jiān)圃?Java多線程并發(fā)技術(shù)的實(shí)現(xiàn)[J];電腦開發(fā)與應(yīng)用;2004年09期

6 曹軍梅,張貞,楊東風(fēng);一種實(shí)現(xiàn)多線程的方法[J];延安大學(xué)學(xué)報(bào)(自然科學(xué)版);2002年02期

7 應(yīng)榮軍;;MFC多線程用事件(EVENT)同步的探討[J];中文信息;2002年08期

8 羅宇,商臨鋒;操作系統(tǒng)多線程實(shí)現(xiàn)技術(shù)研究[J];小型微型計(jì)算機(jī)系統(tǒng);2000年05期

9 田曉紅;國產(chǎn)多線程瀏覽器“七仙女”的靚點(diǎn)[J];電腦愛好者;2000年24期

10 宋燕紅,馬禮;多線程并發(fā)服務(wù)器的設(shè)計(jì)與實(shí)現(xiàn)[J];華北工學(xué)院學(xué)報(bào);1998年02期

相關(guān)博士學(xué)位論文 前10條

1 朱亮;基于NUMA架構(gòu)的多線程程序性能和能耗研究[D];華中科技大學(xué);2016年

2 吳振東;并行程序中bug檢測技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2015年

3 趙榮彩;多線程低功耗編譯優(yōu)化技術(shù)研究[D];中國科學(xué)院研究生院（計(jì)算技術(shù)研究所）;2002年

4 楊華;片上多線程體系結(jié)構(gòu)資源分配策略的研究[D];哈爾濱工業(yè)大學(xué);2006年

5 鄭龍;多線程鎖同步運(yùn)行時(shí)特征分析與調(diào)優(yōu)機(jī)制研究[D];華中科技大學(xué);2016年

6 鄧鹍;前瞻多線程編譯優(yōu)化技術(shù)的研究與實(shí)現(xiàn)[D];國防科學(xué)技術(shù)大學(xué);2001年

7 逄龍;多線程程序中關(guān)聯(lián)變量原子性驗(yàn)證關(guān)鍵技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2015年

8 陳沉;面向多線程程序的確定性并行關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2015年

9 徐海峰;多線程的內(nèi)存調(diào)度[D];浙江大學(xué);2011年

10 林英;多核軟件形式化建模、驗(yàn)證及性能評(píng)價(jià)方法研究[D];云南大學(xué);2013年

相關(guān)碩士學(xué)位論文 前10條

1 傅浩杰;基于Delta-Debugging算法的多線程程序缺陷定位方法研究[D];天津大學(xué);2018年

2 朱欣;基于單指令集異構(gòu)多核架構(gòu)的單核多線程性能建模[D];東南大學(xué);2017年

3 繆磊;網(wǎng)絡(luò)處理引擎性能評(píng)估技術(shù)研究[D];西安電子科技大學(xué);2018年

4 潘有順;嵌入式多線程程序數(shù)據(jù)競態(tài)條件的分析與研究[D];昆明理工大學(xué);2015年

5 簡道紅;多線程程序數(shù)據(jù)競爭靜態(tài)檢測方法研究[D];大連理工大學(xué);2013年

6 徐超;基于動(dòng)態(tài)二進(jìn)制翻譯的多線程程序數(shù)據(jù)競爭檢測方法研究[D];上海交通大學(xué);2010年

7 殷紹劍;嵌入式多線程遠(yuǎn)程調(diào)試器研究與實(shí)現(xiàn)[D];電子科技大學(xué);2013年

8 白哥樂;基于靜態(tài)源碼分析的多線程死鎖檢測方法研究[D];北京郵電大學(xué);2011年

9 祝帥君;多核多線程虛擬化中斷系統(tǒng)的研究與實(shí)現(xiàn)[D];國防科學(xué)技術(shù)大學(xué);2008年

10 許先超;龍芯2號(hào)多線程擴(kuò)展的研究與設(shè)計(jì)[D];中國科學(xué)院研究生院（計(jì)算技術(shù)研究所）;2005年

本文編號(hào)：2887964