Determinism Should Ensure Deadlock-Freedom

Vasudevan, Nalini; Edwards, Stephen A.

The advent of multicore processors has made concurrent programming models mandatory. However, most concurrent programming models come with two major pitfalls: non-determinism and deadlocks. By determinism, we mean the output behavior of the program is independent of the scheduling choices (e.g., the operating system) and depends only on the input behavior. A few concurrent models provide deterministic behavior by providing constructs that impose additional synchronization, but improper or out-of-order use of these constructs leads to problems like deadlocks. In this paper, we argue for both determinism and deadlock-freedom. We propose a design of a deterministic, deadlock-free model. Any program that uses this model is guaranteed to produce the same output for a given input. Additionally, the program will never deadlock: the program will either terminate or run forever.



  • thumnail for vasudevan2010determinism.pdf vasudevan2010determinism.pdf application/pdf 55.9 KB Download File

Also Published In

2nd USENIX Workshop on Hot Topics in Parallelism (HotPar'10)

More About This Work

Academic Units
Computer Science
Published Here
August 9, 2011