Articles

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.

Subjects

Files

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

Also Published In

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

More About This Work

Academic Units
Computer Science
Published Here
August 9, 2011