Taming implicit synchronizations in concurrent programs

Xiong, Weiwei

Permalink

https://hdl.handle.net/2142/45345 Copy

Description

Title

Taming implicit synchronizations in concurrent programs

Author(s)

Xiong, Weiwei

Issue Date

2013-08-22T16:37:18Z

Director of Research (if dissertation) or Advisor (if thesis)

Zhou, Yuanyuan

Doctoral Committee Chair(s)

Zhou, Yuanyuan

Committee Member(s)

• King, Samuel T.
• Marinov, Darko
• Voelker, Geoffrey M.

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Synchronizations
• Concurrent program reliability
• Data race
• Deadlock
• Ad hoc synchronization
• Address transfer
• Program analysis

Abstract

Synchronization takes an important role in multi-threaded programs. Due to the non-deterministic nature of concurrency, it is always difficult for developers to make synchronizations correct. As a consequence, concurrent programs are vulnerable to concurrency bugs and fail during run-time. Many synchronizations in existing multithreaded programs are implicit. They are either implemented in an ad hoc way, or customized by programmers to be application specific. These implicit synchronizations are difficult to be recognized by programmers or automatic program analysis tools. As a result, they often cause critical reliability problems to concurrent programs, and also make concurrent program analysis tools to be less effective. Unfortunately, this type of synchronizations has significantly been under-studied. This dissertation makes three major contributions towards studying and improving implicit synchronizations in multi-threaded programs. The first contribution is a comprehensive characteristic study of ad hoc synchronizations. By studying 229 ad hoc synchronizations in 12 programs of various types (server, desktop and scientific), including Apache, MySQL, Mozilla, etc., we find several interesting and perhaps alarming characteristics: (1) Every studied application uses ad hoc synchronizations. Specifically, there are 6-83 ad hoc synchronizations in each program. (2) ad hoc synchronizations are error-prone. Significant percentages (22-67%) of these ad hoc synchronizations introduced bugs or severe performance issues. (3) Ad hoc synchronization implementations are diverse and many of them cannot be easily recognized as synchronizations, i.e., have poor readability and maintainability. The second contribution is a tool called SyncFinder to automatically identify and annotate ad hoc synchronizations in concurrent programs written in C/C++ to assist programmers in porting their code to better structured implementations, while also enabling other tools to recognize them as synchronizations. Our evaluation using 25 concurrent programs shows that, on average, SyncFinder can automatically identify 96% of ad hoc synchronizations with 6% false positives. The dissertation also uses two use cases to leverage SyncFinder’s auto-annotation. The first one uses annotation to detect 5 deadlocks (including 2 new ones) and 16 potential issues missed by previous analysis tools in Apache, MySQL and Mozilla. The second use case reduces Valgrind data race checker’s false positive rates by 43–86%. The third contribution of this dissertation is to remove false positives of state-of-the-art data race detectors by detecting address transfer, a major cause of false positives in data race detections. Most data race detectors require the accurate knowledge of synchronizations in the programs and cannot recognize implicit synchronizations , thus suffer from false positives which limit their usability. To address this problem, some tools such as Intel Inspector provide mechanisms for suppressing false positives and/or annotating synchronizations not automatically recognized by the tools. However, they require users’ input or even changes of the source code. This dissertation approaches this problem in a different way. The dissertation first uses a state-of-the-art commercial data race detector, namely Intel Inspector on 17 applications of various types including 5 servers, 5 client/desktop applications, and 7 scientific ones, without utilizing any suppression or annotation mechanisms provided by the product that need users’ input. By examining a total of 1420 false data races, the dissertation identifies two major root causes including address transfer, where one thread passes memory address to another thread. It is revealed that more than 62% false data races were caused by address transfer. Based on this observation, this dissertation invents a tool called ATDetector that automatically identifies address transfer and uses the information to prune the false data races. The evaluation with 8 real-world applications shows that it can effectively prune all false data races caused by unrecognized address transfers, without eliminating any true data race that was originally reported.

Graduation Semester

2013-08

Permalink

http://hdl.handle.net/2142/45345

Copyright and License Information

Copyright 2013 Weiwei Xiong

Owning Collections