Rules for Concurrent Software

Safety

A safety property is a property that something bad is not happening. A system is safe if nothing bad ever happens.

Race Conditions

A race condition (defined strictly) is when two threads access the same mutable state concurrently and at least one is modifying the state. We prevent race conditions through the following two principles:

1. Every piece of shared mutable state should be protected by exactly one lock.
2. Every access (read or write) to shared mutable state is executed in the dynamic context of a synchronization on its lock.

Atomicity Violations

An atomicity violation generally is where a series of concurrent accesses to state leave it in a state that could not be achieved if all the actions were considered atomic (serialized). Atomicity violations can thus be seen as examples of race conditions (defined broadly). For our purposes, an atomicity violation is using information acquired in a synchronization block after the block is finished to perform some action on the state, when the information could be incorrect because of actions in a concurrent thread. Atomicity violations can be prevented by:

1. Keep critical regions large enough: do not use information gathered in a previous synchronized block after the block is done (unless it is versioned, see 4).
2. If you need to use possibly stale information, add a version that is incremented on each change to state, and check the version in another synchronized block before using the information.

Liveness

A liveness property is one that asserts that something good will eventually happen. A system is live as long as there is a chance of the goals being met.

Deadlock

A severe liveness violation is deadlock when all threads are stopped while waiting for another thread to release a resource. A related state is ``livelock'' when no threads make any progress; they continually wake, attempt to get a resource, give up, wait for a while and try again. It is the ``busy wait'' equivalent of deadlock. Deadlock can be avoided by ordering resources, in particular:

1. Define an order on the locks, and acquire locks in order. This may require synchronizing on a lock ``earlier'' than needed.

Starvation

Starvation occurs when some thread never gets a chance to make progress. In order to prevent starvation, it is important not to engage in arbitrarily long computations while holding on to a resource:

1. Keep critical regions small enough: do not engage in any I/O, except logging, while holding on to any lock other than a lock protecting the I/O state itself. In particular, don't wait for user-input while holding a lock.
2. Observers may be called while the lock is held; listeners should be called when no lock is held.
3. If you make a private copy of shared mutable information (in a synchronized section), then you can do other operations at your leisure after the block is done.
4. Don't engage in long-running CPU-intensive code while in the ``paint'' thread or holding a lock needed by the ``paint'' thread.

Documentation

These properties are not enforced by the Java compiler, but should be documented so that a programmer can determine whether they are met.

1. Every pieces of shared mutable state should be documented as being protected by some lock.
2. If it is legal to acquire more than one lock at a time, the order of these locks must be declared.
3. A method may indicate in its precondition that various locks must or must not be held.

About this document