Reliable and Efficient Multithreading

The advent of multicore architecture has increased the demand for multithreaded programs. It is notoriously far more challenging to write parallel programs correctly and efficiently than sequential ones because of the wide range of concurrency errors and performance problems. In this thesis, I developed a series of runtime systems and tools to combat concurrency errors and performance problems of multithreaded programs. The first system, Dthreads, automatically ensures determinism for unmodified C/C++ applications using the pthreads library without requiring programmer intervention and hardware support. Dthreads greatly simplifies the understanding and debugging of multithreaded programs. Dthreads often matches or even exceeds the performance of standard thread libraries, making deterministic multithreading a practical alternative for the first time. The second system attacks one notorious performance problem of multithreaded programs: false sharing. We provide the first accurate and precise detection tool, Sheriff-Detect, which can pinpoint the name of global variables or the allocation context of heap objects that involve in false sharing problems, without false positives. However, rewriting a program to fix false sharing can be infeasible when source code is unavailable, or undesirable when padding objects can increase excessive memory consumption or further worsen runtime performance. To resolve this problem, we provide a runtime system, Sheriff-Protect, to automatically boost the performance of programs with false sharing problems. The third system, Predator, improves the effectiveness of false sharing detection. It can detect one more type of false sharing: read-write false sharing. Also, it can even detect false sharing problems without occurrences, thus overcomes a shortcoming of all existing tools: they can only detect those observed false sharing problems