| Research |
| [ CSI ] [ ETH ] |
[ Lab Manager ]
| [ Publications ] [ Research Opportunities ] [ Partners & Supporters ] [ Earlier Work ] |
|
Detecting Synchronization Defects in Multi-Threaded Object-Oriented Programs |
| Christoph von Praun, Detecting Synchronization Defects in Multi-Threaded Object-Oriented Programs, Swiss Federal Institute of Technology, ETH Zurich. (Diss. ETH No. 15524), May 2004. [DISS_ETH_15524.pdf] |
| This dissertation describes an efficient and automated approach to determine synchronization defects in multi-threaded object-oriented programs. The approach is based on the key observation that object-oriented programs provide guarantees about data confinement and encapsulation that can be leveraged by the design of a static analysis and a runtime checker. To be practical, the techniques are demonstrated on the Java programming language. The static analysis operates on an abstract model of threads and data, and simulates the execution of a parallel program on these abstract domains. Thereby, precise information about locking, thread activity, object access, and object escape is recorded in a context-sensitive manner. This symbolic execution provides a general platform to assess properties of parallel programs. The focus of this dissertation is on the detection of three possible sources of errors: data races, methods that may not execute atomically, and deadlock. The static analysis of object-oriented languages is generally limited by the effects of aliasing and the resulting difficulty to disambiguate dynamically allocated data and locks. While approximations of the static analysis reduce the accuracy of the results, we have found the reports of potential synchronization defects to be highly useful in practice: Overreporting may occur, however at a rate that is amenable to manual inspection. True defects may be overlooked but such underreporting can be limited to certain cases that we observed rarely in practice. Two alternative software mechanisms are developed to assess concurrency and locking at runtime: First, object race detection checks if access to shared objects follows a locking discipline. Second, object consistency guarantees that threads behave so that access to individual objects is serializable and happens without harmful interference. Both mechanisms are implemented as a sparse program instrumentation that is guided by the static analysis and optimized with standard compiler techniques. The runtime overhead is very low (on average 44% for object race checking and 25% for object consistency) and well spent in the light of the benefits. The trend towards thread-level parallelism and multi-threaded computer systems make precise information about concurrency and synchronization indispensable for correct program translation, optimization, and execution. The techniques presented in this dissertation are promising steps towards providing this information and making the detection of synchronization defects a default option for compilers and runtime systems of multi-threaded object-oriented programs. |
| [ Publications ] [ Research Opportunities ] [ Partners & Supporters ] [ Earlier Work ] |