Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/99498
Title: Detection of races and control-flow nondeterminism
Authors: Feng, M. 
Yuen, C.K. 
Issue Date: 1998
Source: Feng, M.,Yuen, C.K. (1998). Detection of races and control-flow nondeterminism. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 1511 LNCS : 351-358. ScholarBank@NUS Repository.
Abstract: When either of two concurrent accesses of the same data is not in its critical section, a "race condition" occurs. Previous race-detection techniques are only applicable to parallel programs without using critical sections, or to parallel programs with critical sections implemented by mutex locks. This paper presents a race-detection algo- rithm, called the Protect algorithm, for parallel programs where critical sections are defined in a higher-level programming construct -"critical region". Both the time and space complexity of the Protect algorithm is improved over ones of the previous race-detection algorithms. If the control-flow of a parallel execution on a given input is deterministic, then a single-run of any race-detection algorithm guarantees to find out all races. In the presence of nondeterministic control-flow, a single-run of any race-detection algorithm cannot find out all races. We present another algorithm, called the Alter algorithm, which either guarantees to detect any nondeterministic control-flow in a program using critical regions, or certifies that the program is control-flow deterministic, thereafter all races can be detected by the Protect algorithm. © Springer-Verlag Berlin Heidelberg 1998.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/99498
ISBN: 3540651721
ISSN: 03029743
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

19
checked on Feb 16, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.