Home

Determinism Should Ensure Deadlock-Freedom

Nalini Vasudevan; Stephen A. Edwards

Title:
Determinism Should Ensure Deadlock-Freedom
Author(s):
Vasudevan, Nalini
Edwards, Stephen A.
Date:
Type:
Articles
Department:
Computer Science
Permanent URL:
Book/Journal Title:
2nd USENIX Workshop on Hot Topics in Parallelism (HotPar'10)
Publisher:
USENIX
Abstract:
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.
Subject(s):
Computer science
Item views:
125
Metadata:
text | xml

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use