What is a Race in a Program and when Can We Detect It?Computer Research Laboratory, University of California, Santa Cruz, 1993 - Debugging in computer science - 20 pages |
From inside the book
Results 1-3 of 5
Page 10
... synchronization used . Theorem 1 : Deciding if there exists a race between two conflicting statements in an arbi ... Monotonically Synchronized Excluding arbitrary loops is necessary to avoid termination problems and undecidability ...
... synchronization used . Theorem 1 : Deciding if there exists a race between two conflicting statements in an arbi ... Monotonically Synchronized Excluding arbitrary loops is necessary to avoid termination problems and undecidability ...
Page 13
... Monotonically Synchronized We proved in a previous paper [ HM93 ] that computing the precise ordering relationships between events in branch - free monotonically synchronized programs can be done in polyno- mial time . For completeness ...
... Monotonically Synchronized We proved in a previous paper [ HM93 ] that computing the precise ordering relationships between events in branch - free monotonically synchronized programs can be done in polyno- mial time . For completeness ...
Page 14
David Helmbold. 4.5 No Branches and Non - monotonically Synchronized Similar to Sections 4.1 and 4.3 most results in ... synchronizes using only a single semaphore can be done in O ( n1 - 5p ) time [ LKN93 ] where n is the number of ...
David Helmbold. 4.5 No Branches and Non - monotonically Synchronized Similar to Sections 4.1 and 4.3 most results in ... synchronizes using only a single semaphore can be done in O ( n1 - 5p ) time [ LKN93 ] where n is the number of ...
Common terms and phrases
3SAT accesses to shared algorithm analysis approach artifact race atomic operations branch conditions branch-free program Co-NP combinations of branches Computer conflicting statements contain a race contain synchronization containing semaphore synchronization control flow data race Definition detecting races e₁ and e2 e2 occur e2 overlap event ordering event pairs events are ordered events forming races exact solution execute concurrently exist executions fixed input free program infeasible races lock covers message passing Monotonically Synchronized mortem trace nesting depth Netzer Non-Monotonically Synchronized NP-hard Thm number of events on-the-fly ordered critical sections ordering relationships original program pairs of events partial order particular input polynomial possible input Post and Wait post Ct end post/wait no clear Post/Wait/Clear problem program/input pair race conditions race detection race statement races between events schedule shared memory parallel shared variable single semaphore statement instances synchronization constructs synchronization operations taxonomy Theorem type of synchronization unordered races updates XisT yes y/n y/n