Please use this identifier to cite or link to this item:
|Title:||Detection of races and control-flow nondeterminism||Authors:||Feng, M.
|Issue Date:||1998||Citation:||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.
checked on Nov 9, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.