基于自動(dòng)化靜態(tài)分析工具對(duì)鎖使用模式的研究.pdf

1、如今,隨著計(jì)算機(jī)硬件以及網(wǎng)絡(luò)技術(shù)的發(fā)展,并發(fā)程序在提高計(jì)算效率上發(fā)揮著越來(lái)越重要的作用。然而編寫(xiě)高質(zhì)量的并發(fā)程序?qū)τ诔绦騿T而言并不是一件簡(jiǎn)單的事。與此同時(shí),并發(fā)程序的線程調(diào)度復(fù)雜度高的特性使得并發(fā)程序的調(diào)試、測(cè)試遇到許多問(wèn)題。目前,學(xué)術(shù)界各個(gè)領(lǐng)域已有大量對(duì)并發(fā)程序的研究,比如并發(fā)程序測(cè)試、模型檢測(cè)、數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)等。但目前的研究都會(huì)遇到各種各樣的問(wèn)題,例如部分研究的擴(kuò)展性不高以致無(wú)法有效分析大型并發(fā)程序,如符號(hào)執(zhí)行工具KLEE無(wú)法有效分析

2、Apache等程序中鎖配對(duì)問(wèn)題,而部分研究成果則會(huì)產(chǎn)生大量的誤報(bào),如Inspector對(duì)數(shù)據(jù)競(jìng)爭(zhēng)的誤報(bào)率達(dá)88.7％。考慮到鎖被廣泛使用在對(duì)共享內(nèi)存的訪問(wèn)上,如果能對(duì)真實(shí)并發(fā)程序中鎖的使用情況有較深入的了解,那么將會(huì)對(duì)已有或者將來(lái)的并發(fā)程序的研究產(chǎn)生重大意義。
　　本文的主要貢獻(xiàn)由以下部分組成:
　　(1)首先,本文實(shí)現(xiàn)了一個(gè)基于LLVM、靜態(tài)的、保守的、低開(kāi)銷的、能夠自動(dòng)化分析并發(fā)程序中鎖使用模式的工具LUPA,并通過(guò)案例

3、分析與實(shí)驗(yàn)對(duì)LUPA的準(zhǔn)確性與性能分別進(jìn)行了分析說(shuō)明。
　　(2)其次,本文在LUPA的輔助下,結(jié)合人工檢驗(yàn)首次對(duì)并發(fā)程序中與鎖相關(guān)的語(yǔ)言特性、所使用的鎖模式、不同版本之間對(duì)鎖使用的演化情況,這幾個(gè)方面的一般性規(guī)律分別進(jìn)行了研究。
　　通過(guò)實(shí)驗(yàn)可以知道LUPA對(duì)目標(biāo)程序的平均分析時(shí)間為413557毫秒,而對(duì)大型程序如MySQL等的分析能在20分鐘內(nèi)完成。同時(shí)LUPA對(duì)特殊鎖模式的識(shí)別率達(dá)到97.2%。
　　在本文的研究

4、里,MySQL, Apache, Aget, Pbzip2等開(kāi)源并發(fā)程序被選為目標(biāo)分析程序,通過(guò)對(duì)這幾個(gè)程序中鎖使用情況的分析,本文得出了一般鎖使用的規(guī)律,使得能夠有效地對(duì)并發(fā)程序分析工具的設(shè)計(jì)與實(shí)現(xiàn)進(jìn)行改進(jìn),以及對(duì)程序員編寫(xiě)并發(fā)程序提出有用建議,其中一些較為重要的發(fā)現(xiàn)如下:(a)80.5%的鎖敏感函數(shù)中只會(huì)持有1把鎖;(b)相比其他鎖模式,直接鎖模式在并發(fā)程序中出現(xiàn)的比率最高,為54.5%。(c)在所分析的527個(gè)鎖模式中只有12個(gè)鎖