Topic: race conditions

topics > computer science > Group: parallel processing

code optimization by flow analysis
concurrency control by monitors
critical regions
flavor analysis and typestates for supplementary type checking
lock-free concurrency
managing shared memory
models of parallel computation
process threads
shared objects
safety, liveness, and system properties
updating information with locking
Subtopic: race condition up

Quote: a race condition occurs when two threads update shared data simultaneously; difficult to catch; needs locks to avoid [»flanC6_2000]
Quote: if two processes modify overlapping regions of a page, have a data race without an intervening synchronization (i.e., an error)
Quote: example of race condition in java.util.vector; lastIndexOf and trimToSize may use elementCount without acquiring the lock [»flanC6_2000]
Quote: early writes OK if they do not depend on a read from a data race [»mansJ1_2005]

Subtopic: static race detection up

Quote: static race detection by protecting class fields with an external lock; no race checking for local objects and benign races [»flanC6_2000]
Quote: static race detection by conditional must not aliasing; sound analysis, found more races than another algorithm analysing likely races [»naikM1_2007]
Quote: Chord for race detection using lock-based, fork/join, and wait/notify synchronization; identified 18 bugs in jdbf [»naikM6_2006]
Quote: Chord computes reachable pairs, aliasing pairs, escaping pairs, and unlocked pairs; using call-graph, alias, thread-escape, and lock analysis [»naikM6_2006]

Subtopic: harmful vs. benign up

Quote: only 10% of true data races are harmful; triaging is tedious and hard to figure out; need an automatic test [»naraS6_2007]
Quote: use a replay log to distinguish benign data races from harmful ones; demonstrate the harmful data race; identify races with happens-before [»naraS6_2007]
Quote: Chord analyzes open programs and reports counterexamples; essential; detect races before deployment [»naikM6_2006]

Subtopic: concurrency errors up

Quote: simple analysis find obvious synchronization errors; programmers do not understand synchronization and they avoid using synchronization [»hoveD7_2004]
Quote: programming with threads is difficult; misuse of concurrency is widespread; use a bug checker to catch concurrency problems [»hoveD12_2004]
Quote: the Java memory model is not sequentially consistent; optimization and inlining can have non-local effects, making eyeballing race conditions very difficult [»hoveD7_2004]
Quote: disallow out-of-thin-air changes for incorrectly synchronized code; e.g., x,y=0; y=x and x=y; x==42 [»mansJ1_2005]
Quote: want guarantees that objects are properly initialized; but restrict data races to the low-level implementation of synchronization primitives [»pughW6_1999]

Subtopic: counterexample up

Quote: report counterexamples for each race, categorized by field and by object; which threads, which objects, and which locks [»naikM6_2006]

Subtopic: race avoidance up

Quote: assign a release and a termination time for tasks; inputs available at release, outputs available at termination; the actual timing does not matter; avoids race conditions [»henzTA6_2005]

Subtopic: atomic method up

Quote: use atomic methods to avoid unexpected thread interactions; race-detection is neither necessary nor sufficient [»flanC6_2003]

Subtopic: kill-safe up

Quote: an operation is kill-safe if it is atomic despite thread termination [»flatM6_2004]
Quote: how to extend a run-time system for kill-safe operations; only trusting the shared object
Quote: implement kill-safe by suspending an instance instead of killing it; a surviving task can resurrect the instance

Subtopic: thread-safe up

Quote: distinguish immutable classes, thread-safe classes, conditionally thread-safe, thread-compatible, and thread-hostile classes [»blocJ_2001]

Subtopic: relaxed memory consistency up

Quote: programmers can identify synchronization and data operations in performance-critical areas for weak order optimization; example of programmer-centric approach to relaxed memory consistency [»adveSV12_1996]
Quote: the concurrency model of Java makes it difficult to allow unsynchronized access to shared objects [»bacoDF10_2000]

Subtopic: model checker up

Quote: used a model checker to verify safety assertions written in temporal logic; found subtle discrepancies [»atleJM1_1993]

Subtopic: type annotation up

Quote: type annotation for static race detection; found errors in Java libraries; 20 annotations per 1000 lines [»flanC6_2000]
Quote: type annotations--'guarded_by lock' for fields and 'requires lock_list' for methods; 1000 lines per programmer hour [»flanC6_2000]
Quote: use Flanagan and Abadi's race-free type system to prove that Guava objects are never concurrently accessed [»bacoDF10_2000]

Subtopic: multiple-writer up

Quote: with a multiple-writer protocol provide change notification at synchronization time and update modified pages by exchanging diffs [»amzaC2_1996]

Subtopic: non-preemptive threads up

Quote: Amoeba avoids race conditions by letting all threads run to completion; non-preemptive, like co-routines [»taneAS12_1990]

Subtopic: self-stabilization up

Quote: self-stabilizing, token-based system with no race conditions; if multiple tokens, guaranteed to remove all but one from system [»browGM6_1989]

Subtopic: livelock and deadlock up

Quote: for meaningful, interprocess communication need: no livelock, no deadlock, all messages handled, concurrency is order independent, serialization

Related Topics up

Topic: code optimization by flow analysis (47 items)
Topic: concurrency control by monitors (24 items)
Topic: critical regions (58 items)
Topic: deadlocks (21 items)
Topic: flavor analysis and typestates for supplementary type checking (68 items)
Topic: lock-free concurrency (8 items)
Topic: managing shared memory (74 items)
Topic: models of parallel computation (33 items)
Topic: process threads (25 items)
Topic: shared objects (13 items)
Topic: safety, liveness, and system properties (22 items)
Topic: updating information with locking
(20 items)

Updated barberCB 11/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.