implement race detection functionality inXThreadDebugger base on pluggable modulesystem

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：5

、訪客IP：3.128.199.162

姓名

梁穎睿(Ying-Ruei Liang) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

(implement race detection functionality inXThreadDebugger base on pluggable modulesystem)

相關論文

★ 使用PolyTraceAid進行程式文件覆蓋率計算與分群	★ Support Visual Debugging in Electronic Design Automation Software by xDIVA
★ 設計與實作視覺化追蹤點以支援xDIVA進行程式動畫	★ Combine Internal Test Oracles and Capture/Replay GUI Testing for Precise Replay and Higher Validation Power
★ Dissimilarity of Polymorphic Execution Sequences	★ The Analysis of Capturing System Test Cases into Unit Test Cases
★ 動態延遲載入的測試覆蓋率	★ 建構於JMeter之自動化分散式壓力測試架構
★ 模組化因修改具耦合的程式碼所伴隨的成本漣漪	★ Design a Pluggable Architecture for Layout Algorithms in xDIVA
★ 重複性程式碼檢測之外掛模組設計	★ Visual Perception of Realistic Rendering in xDiva 3D Environment
★ Why and When GUI Test Automation Fails in Practice and Our Solutions to The Problem	★ Why and When GUI Test Automation Fails in Practice and Our Solutions to The Problem
★ Very High Precision Optical Character Recognition For Clean-Fixed-Sized True Type Characters	★ Enhance Korat by Branch Capability in Capture/Replay User Scenario to Industrial Test Case Automation

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

“Multithreading Is Today′s GOTO” - Jos de Jong 2013
隨著硬體以及軟體架構的發展,加上人們對於效能的需求,多執行緒或是所謂的並行程式
已經成為一種無可避免的趨勢,無論是遊戲,伺服器甚至是手機端程式,都對 CPU 效能有所
需求。但是程式語言的發展是早於多執行緒的概念的,既有的程式語言多半是增加了對多執行
緒能力的支援,卻無法避免掉它們帶來的錯誤,舉凡最簡單的 data race 到複雜難以發現
的 atomic variable memory ordering 導致的錯誤,這些問題在根本上需要相對應的
知識才得以避免,也需要等值的經驗才有辦法除錯,也就是說,處理多執行緒程式是一件難事,
不論使用的語言為何。
是的,除錯很難,除多執行緒程式的錯更是難上加難,為了輔助既有程式語言以及對多執
行緒程式的除錯,開發者需要仰賴工具來協助它們,而當中的其中一個幫手便是 data race
detector。
本研究提出了一個建立在實驗室專案 , XThreadDebugger , 上的 dynamic race
detector。藉由搭配 XThreadDebugger 提供的 exhaustive testing,來對待測程式
進行更高覆蓋率的測試,藉此偵測更多的 data race,作為一個對過去 race detector
的新嘗試。實作方面,XThreadDebugger 使用中斷點來對程式碼進行 interleaving 的
控制,本研究也將善用這點,在動態時期針對真正有被共享的變數去進行監控,藉此達到偵測
data race 的功能,同時減少不必要的效能開銷。而在架構方面,本研究則提出了 Module
層的概念,提供 XThreadDebugger 未來開發者一個適合且低成本的框架,以便未來開發之
需求,我們所提出的 data race detector 便是在該框架下建構的。

摘要(英)

“Multithreading Is Today′s GOTO” - Jos de Jong 2013
Concurrency programming paradigm is the trend, not only because
people′s need for performance, but the evolution of hardware as well.
From video games industry, server to even mobile application, they
all benefit from it. But the history of programming language is
earlier than the concept of parallel programming. Even thought most
of language got the ability to write parallel code, it’s still hard
to avoid the complexity. To solve them the developers require certain
knowledge and experience. In the other word, dealing with parallel
program is tough no mater which language you use.
Debugging is hard, debugging parallel program is even harder. To
assist the debugging process developers need tools. Race detector is
one of them.
This research proposes a dynamic race detector which builds on
XThreadDebugger, a tool to help developers debugging thread related
problem which was developed by our lab. Combine with the “exhaustive
testing” ability from XThreadDebugger, we expect to run tests with
higher testing coverage and capture more data race at run time.

關鍵字(中)

★ 並行
★ 資料競爭

關鍵字(英)

★ concurrency
★ data race

論文目次

第 1 章緒論.......................................................1
1.1 研究背景......................................................1
1.2 研究動機......................................................3
1.3 研究方法與貢獻.................................................4
1.4 論文架構......................................................6
第 2 章相關研究探討................................................7
2.1 多執行緒程式之錯誤原因..........................................7
2.2 多執行緒程式之錯誤偵測..........................................9
2.2.1 Dynamic program analysis................................9
2.2.2 Static program analysis................................11
2.2.3 Type system – language level...........................13
2.2.4 小結...................................................14
2.3 dynamic data race detector 演算法............................14
2.3.1 Lockset................................................15
2.3.2 DJIT+..................................................16
2.3.3 小結...................................................19
第 3 章 XThreadDebugger 架構與擴充.................................20
3.1 XThreadDebugger.............................................20
3.1.1 Interleaving 控制能力...................................20
3.1.2 Exhaustive testing.....................................22
3.1.3 小結...................................................22
3.2 現有架構.....................................................22
3.3 擴充需求.....................................................23
3.4 架構設計 – 引入 module 層.....................................24
3.5 小結........................................................26
第 4 章在 Module 層上實作 dynamic data race detector..............27
4.1 Dynamic data race detector 概念.............................27
4.2 與 XThreadDebugger 之互動方式.................................28
4.2.1 共享變數之讀寫事件........................................28
4.2.2 同步物件之操作事件........................................28
4.3 定義 data race in C#........................................30
4.3.1 簡介 C# 語言變數之類型及特性...............................30
4.3.2 『區域』的『資料類型』之讀寫定義.........................31
4.3.3 『欄位』的『資料類型』之讀寫定義.........................32
4.3.4 『區域』的『參考類型』之讀寫定義.........................33
4.3.5 『欄位』的『參考類型』之讀寫定義.........................34
4.3.6 定義 data race.........................................35
4.4 捕捉所需之事件之實作...........................................36
4.4.1 同步物件操作事件.........................................37
4.4.2 共享變數讀寫事件.........................................38
第 5 章實例討論...................................................41
5.1 案例目的.....................................................41
5.2 第一個案例...................................................41
5.2.1 案例描述................................................41
5.2.2 執行案例................................................43
5.2.3 第一種 interleaving.....................................44
5.2.4 第二種 interleaving.....................................45
5.3 第二個案例...................................................46
5.3.1 案例描述................................................46
5.3.2 執行案例................................................47
5.3.3 第一種 interleaving.....................................47
5.3.4 第二種 interleaving.....................................48
5.4 加入 exhaustive testing 之輔助...............................49
5.5 結果評估.....................................................50
第 6 章結論與未來展望..............................................52
參考文獻............................................................54

參考文獻

[1] “Servo,” Mozilla foundation, [Online]. Available: https://servo.org/.
[Accessed 4 7 2018].
[2] “Roslyn,” Microsoft Corporation, [Online]. https://github.com/dotnet/
roslyn. [Accessed 4 7 2018].
[3] Gu, Rui, et al. "What change history tells us about thread
synchronization." Proceedings of the 2015 10th Joint Meeting on
Foundations of Software Engineering. ACM, 2015
[4] “rr,” Mozilla foundation. [Online]. Available: https://rr-project.org/.
[Accessed 4 7 2018].
[5] Nethercote, Nicholas, and Julian Seward. "Valgrind: a framework for
heavyweight dynamic binary instrumentation." ACM Sigplan notices.
Vol. 42. No. 6. ACM, 2007.
[6] “Helgrind,” Valgrind developers, [Online]. Available:
http://valgrind.org/docs/manual/hg-manual.html. [Accessed 4 7
2018].
[7] “DRD,” Valgrind developers, [Online]. Available:
http://valgrind.org/docs/manual/drd-manual.html. [Accessed 4 7
2018].
[8] “Clang ThreadSanitizer,” LLVM foundation, [Online]. Available:
https://clang.llvm.org/docs/ThreadSanitizer.html. [Accessed 4 7 2018].
[9] “Clang Thread Safety Analysis,” LLVM foundation, [Online]. Available:
https://clang.llvm.org/docs/ThreadSafetyAnalysis.html. [Accessed 4 7
2018].
[10] “RacerD,” Facebook Inc, [Online]. Available: http://fbinfer.com/docs/
racerd.html. [Accessed 4 7 2018].
[11] Boyapati, Chandrasekhar, Robert Lee, and Martin Rinard. "Ownership
types for safe programming: Preventing data races and deadlocks."
ACM Sigplan Notices. Vol. 37. No. 11. ACM, 2002.
[12] “Rust programming language,” Mozilla foundation, [Online].
Available: https://www.rust-lang.org. [Accessed 4 7 2018].
[13] Musuvathi, Madanlal, and Shaz Qadeer. "Iterative context bounding
for systematic testing of multithreaded programs." ACM Sigplan
Notices. Vol. 42. No. 6. ACM, 2007.
[14] Netzer, Robert HB, and Barton P. Miller. On the complexity of event
ordering for shared-memory parallel program executions. University
of Wisconsin-Madison, Computer Sciences Department, 1990.
[15] Netzer, Robert HB, and Barton P. Miller. "What are race conditions?:
Some issues and formalizations." ACM Letters on Programming
Languages and Systems (LOPLAS) 1.1 (1992): 74-88.
[16] Pozniansky, Eli, and Assaf Schuster. Efficient on-the-fly data race
detection in multithreaded C++ programs. Vol. 38. No. 10. ACM, 2003.
[17] Savage, Stefan, et al. "Eraser: A dynamic data race detector for
multithreaded programs." ACM Transactions on Computer Systems
(TOCS) 15.4 (1997): 391-411.
[18] Itzkovitz, Ayal, Assaf Schuster, and Oren Zeev-Ben-Mordehai. "Toward
integration of data race detection in DSM systems." Journal of Parallel
and Distributed Computing 59.2 (1999): 180-203.
[19] Mattern, Friedemann. "Virtual time and global states of distributed
systems." Parallel and Distributed Algorithms 1.23 (1989): 215-226.
[20] Flanagan, Cormac, and Stephen N. Freund. "FastTrack: efficient and
precise dynamic race detection." ACM Sigplan Notices. Vol. 44. No. 6.
ACM, 2009.

指導教授

鄭永斌

審核日期

2018-8-15

推文