Title:

Determinism Should Ensure Deadlock-Freedom

Author(s):

Vasudevan, Nalini
Edwards, Stephen A.

Date:

2010

Type:

Articles

Department:

Computer Science

Permanent URL:

http://hdl.handle.net/10022/AC:P:10857

Book/Journal Title:

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

Publisher:

USENIX

Publisher Location:

Berkeley

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:

89

Metadata:

description

View | Download