Starvation occurs when one or more threads of execution are prevented from proceeding beyond a given point due to a predicate that will never be satisfied. Deadlock is a special form of starvation where threads of execution are prevented from making progress due to predicate conditions that are directly dependent on them. To illustrate, consider threads A and B, with shared resources R1 and R2. If thread A holds resource R1, and thread B holds resource R2; a deadlock will occur if thread A needs resource R2 to proceed and thread B is waiting on thread A to release resource R1. Since neither thread releases the resource it is holding, and both need each other’s resource to continue, they both become engaged in a deadly embrace and cannot proceed any further.
Considering that parallel threads of execution quite often have to rely on shared/mutual state, and that locking is used as the predominant means of preventing destructive updates, it is not surprising that deadlocks are an issue that multi-threaded application developers have to contend with at some point or another.
The adage “prevention is better than cure” is rather prescient when considering the problem of deadlocks. Actually, anyone who has had the displeasure of diagnosing deadlock will probably agree that the British and Australian version “an ounce of prevention is more valuable than a pound of cure” probably does a better job of emphasizing the contrast between the effort involved in preventing and fixing deadlocks respectively.
Thankfully (or sadly, depending on which way you look at it), deadlocks are mostly “man made” i.e. down to programmer error. Thus, preventing them can simply be a case of avoiding concurrency anti-patterns that have been shown to trigger them. We know from E.G. Coffman’s 1971 article that there must be four conditions for a deadlock to take place. These are:
Thus, preventing deadlock can be as simple as ensuring that all of the above four conditions never hold at the same time. Unfortunately life is not that simple. In reality, the first three conditions are actually quite useful for a variety of reasons which most concurrent application developers are fully aware off. For this reason, deadlock prevention often centres on preventing the final condition taking root.
In the following series of posts, I will explore three concurrency anti-patterns that can lead to circular wait conditions. In addition to describing these anti-patterns, this series will also show code samples to illustrate each one, and discuss solutions and workarounds to counteract them. Please note that the aim of this series is not to be a comprehensive collection of anti-patterns, but rather to encourage discussion around the topic. As such, readers are invited to contribute additional anti-patterns that they have come across—preferably with code samples.
This series is hands-on, so you are advised to download the companion source code archive, located at http://www.javaworld.com/javaworld/jw-03-2009/hpj032309-src.zip [1], and load the source files into your favourite IDE.
For this installment, let us begin with a relatively simple anti pattern, which I refer to as the ‘No Arbitration’ pattern.
For a rather amusing take on deadlock-making functional requirements, examine this piece of legislation passed in the Midwestern US State of Kansas: "When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone".
One can only speculate as to the sequence of events that occurred the first time that two trains did actually happen upon each other at a crossing or indeed how long this statute lasted on the books.
The pertinent question however is: what would happen if we modelled this statute in software? To answer that question, we will use the example.noarbitration package in the companion source archive. The package consists of the following compilation units:
+example.noarbitration
-CrossingSimulator.java
-Train.java
-CrossingSimulator2.java
-Train2.java
-TrainArbitrator.java
We will first of all explore the Train class which extends java.lang.Thread and which, as its name implies, models the behaviour of a train. This class is outlined in listing 1.
public class Train extends Thread
{
private Train other;
protected boolean stopped;
private String trainId;
public Train(String trainId)
public void setOther(Train other)
protected synchronized void waitUntilMoved()
protected synchronized void moveTrain()
@Override
public void run()
{
System.out.println( this + " reached barrier...");
try
{
other.waitUntilMoved();
moveTrain();
}
catch (InterruptedException exce)
{
System.out.println("Thread halted ...");
}
}
}
Observe that the other attribute holds a reference to the other train at the crossing. As dictated by the statute, the run method models what takes place the moment the train arrives at the crossing. It waits for the other train to move before it itself starts to move.
We use the CrossingSimulator class, shown in listing 2, to encapsulate the behaviour of both trains as it relates to the crossing. As can be seen from the listing, the code creates and starts two train simulators (one southbound and the other eastbound).
public class CrossingSimulator
{
public static void main(String[] args)
{
Train train1 = new Train("Southbound Train");
Train train2 = new Train("Eastbound Train");
train1.setOther(train2);
train2.setOther(train1);
train1.start();
train2.start();
}
}If we run the code in the previous listing, we should get the following output:
Southbound Train reached barrier...
Eastbound Train reached barrier...Not surprisingly, our trains never go anywhere once they reach the crossing; both threads quite simply deadlock, each waiting for the other to move. A rather perfect example of how not to run trains!
The question then is: what exactly is wrong with the model of concurrency on which this example is built? The answer in this particular case is quite simple; there is no arbitration between the trains to decide who gets to go first when conflict occurs. A situation that can quite easily occur when building systems based on independent and co-operative processes of equal priority and which rely on each other's internal state for deciding direction.
More formally, when there is contention between different threads of execution, a means must be present to determine the order in which the threads are granted access to the area or state in contention.
A simple solution is to introduce an arbitrator, which, when contention of this nature is detected, decides, based on some well defined scheme, which of the competing processes gains the upper hand. To apply this to the example model, some modifications are required to the Train and CrossingSimulator class logic, as well as some dedicated logic to provide arbitration.
The Train class is extended by Train2, as shown in listing 3, in order to provide three methods which play a key part in arbitration.
public class Train2 extends Train
{
private long arrivalTime;
public synchronized boolean isStopped()
protected void forceTrainToMove()
public long getArrivalTime()
}
The isStopped() method indicates that the train is stationary; and forceTrainToMove() is invoked by the arbitrator to force the train to move. Finally, getArrivalTime() provides the time at which the train arrived at the crossing.
The arbitrator implementation is encapsulated in class TrainArbitrator, and is shown in listing 4. As is evident from the run() method, the arbitrator simply forces the train which has been at the crossing the longest to start moving. This will, in turn, enable the other train to move also.
public class TrainArbitrator extends Thread
{
private Train2 trainA;
private Train2 trainB;
public TrainArbitrator( Train2 trainA,
Train2 trainB)
public void run()
{
while (trainA.isStopped() && trainB.isStopped())
{
if (trainA.getArrivalTime()
<trainB.getArrivalTime())
{
trainA.forceTrainToMove();
break;
}
else
{
trainB.forceTrainToMove();
break;
}
}
}
}
The executor class CrossingSimulator is also replaced by CrossingSimulator2, which is detailed in listing 5.
public class CrossingSimulator2
{
public static void main(String[] args) throws InterruptedException
{
Train2 train1 = new Train2("Southbound Train");
Train2 train2 = new Train2("Eastbound Train");
train1.setOther(train2);
train2.setOther(train1);
train1.start();
train2.start();
Thread.sleep(1000);
TrainArbitrator arbitrator = new
TrainArbitrator(train1,train2);
arbitrator.start();
}
}
If we execute CrossingSimulator2, we should get the following output:
Southbound Train reached barrier...
Eastbound Train reached barrier...
Eastbound Train now moving ..
Southbound Train now moving ..The output shows that when the arbitrator thread starts, it detects that both trains are standstill, and forces the eastbound train to move on, thus opening up the crossing for the second train.
Please note that the term arbitrator is used here in an abstract context. There are many ways to implement/achieve the same behaviour, and in fact, you may be able to achieve the same effect using concurrency constructs available in standard edition Java—depending of course on the structure of your problem and solution.
In the next installment, we will examine the Worker Aggregation anti-pattern.
Links:
[1] http://www.javaworld.com/javaworld/jw-03-2009/hpj032309-src.zip