In this article, we will discuss some threading best practices to avoid deadlocks.
Necessary Conditions
A deadlock situation can arise only if all of the following conditions hold simultaneously in a system:[3]
- Mutual Exclusion: At least, one resource must be non-shareable. Only one process can use the resource at any given instant of time.
- Hold and Wait: A process is currently holding at least one resource and requesting additional resources which are being held by other processes.
- No Preemption: The operation system can de-allocate resources once they have been allocated. They must released by the holding process voluntarily.
- Circular Wait: A process waiting for a resource which is being held by another process, which in turn is waiting for another process to release a resource.
How to Avoid Deadlocks
Invoking an alien method with a lock held is asking for liveness trouble. The alien method might acquire other locks (risking deadlock) or block for an unexpectedly long time, stalling other threads that need the lock you hold.
In other words, inside a synchronized region, do not invoke a method that is designed to be overridden, or one provided by a client in the form of a function object (i.e., object references used to implement the Strategy pattern). The class has no knowledge of what the alien method does and has no control over it. If you do call an alien method from within a synchronized region, you open the opportunities of deadlocks by allowing the following conditions to hold:
- Hold and Wait
- Circular Wait
Calling a method with no locks held is called an open call[6], and classes that rely on open calls are more well-behaved and composable than classes that make calls with locks held.
More generally, try to limit the amount of work that you do from within synchronized regions. When you are designing a mutable class, think about whether it should do its own synchronization. Synchronize your class internally only if there is a good reason to do so, and document your decision clearly.
Ensure that resources are always acquired in some well-defined order[7]
Deadlocks can be avoided by assigning a partial order to the resources, and establishing the convention that all resources will be requested in order, and released in reverse order, and that no two resources unrelated by order will ever be used by a single unit of work at the same time. This solution to the dining philosophers problem was originally proposed by Dijkstra.
There are different approaches to enforce a partial order to the resources:
- If resources are static and known in advanced
- Just stick to a programming policy (i.e., all programmers apply the policy of acquiring the locks in some well-defined order)
- Provide a method that combines acquisition and release of the multiple locks in the correct way (see here for an example)
- If resources are not known in advanced or acquired dynamically
- We have to explicitly define some way of ordering them. For example,
- If locking will only exist for the lifetime of the application
- We can use the identity hash code (System.identityHashCode(r)) of the two objects.
- In the rare case that two objects have the same hash code, we must use an arbitrary means of ordering the lock acquisitions, and this reintroduces the possibility of deadlock. To prevent inconsistent lock ordering in this case, a third tie breaking lock can be used[6].
- If locking will only exist for the lifetime of the application
- We have to explicitly define some way of ordering them. For example,
Removing the mutual exclusion condition means that no process will have exclusive access to a resource. This proves impossible for resources that cannot be spooled. But even with spooled resources, deadlock could still occur. Algorithms that avoid mutual exclusion are called non-blocking synchronization algorithms.
For example, optimistic concurrency control[9] uses a pair of consistency markers in the data structure. Processes reading the data structure first read one consistency marker, then read the relevant data into an internal buffer, then read the other marker, and then compare the markers. The data is consistent if the two markers are identical. Markers may be non-identical when the read is interrupted by another process updating the data structure. In such a case, the process discards the data in the internal buffer and tries again.
Finally, immutability is great for multi-threading. Instances of immutable class appear constant. Therefore, no external synchronization is necessary. Examples include String, Long, and BigInteger.
Using timed lock acquisition to acquire multiple locks[6]
Another technique for detecting and recovering from deadlocks is to use the timed tryLock feature of the explicit Lock classes instead of intrinsic locking.
If a lock acquisition times out, you can release the locks, back off and wait for a while, and try again, possibly clearing the deadlock condition and allowing the program to recover. However, this technique works only when the two locks are acquired together; if multiple locks are acquired due to the nesting of method calls, you cannot just release the outer lock, even if you know you hold it.
Conclusion
We conclude this article by quoting Goetz et al.[6]:
Like many other concurrency hazards, deadlocks rarely manifest themselves immediately. The fact that a class has a potential deadlock doesn’t mean that it ever will deadlock, just that it can. When deadlocks do manifest themselves, it is often at the worst possible time—under heavy production load.References
- Dining philosophers problem
- Deadlock
- Advanced Synchronization in Java Threads by Scott Oaks and Henry Wong
- Effective Java by Joshua Block
- Threading Best Practices
- Java Concurrency in Practice by Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes and Doug Lea
- Deadlock Tutorial
- The Java Tutorial (Concurrency)
- Optimistic concurrency control
- Concurrency: State Models & Java Programs (2nd Edition), by Jeff Magee and Jeff Kramer.
- Java Concurrent Animated
- Analyze Hanging Programs Using Java Thread Traces (Xml and More)
No comments:
Post a Comment