3.8 Deadlock - Java Threads, Third Edition

3.8 Deadlock

We have mentioned deadlock a few times in this chapter, and we'll examine the concept in detail in Chapter 6. For now, we just need to understand what it is and why it is a problem.

Simplistically, deadlock occurs when two or more threads are waiting for two or more locks to be freed and the circumstances in the program are such that the locks are never freed. Interestingly, it is possible to deadlock even if no synchronization locks are involved. A deadlock situation involves threads waiting for conditions; this includes waiting to acquire a lock and also waiting for variables to be in a particular state. On the other hand, it is not possible to deadlock if only one thread is involved, as Java allows nested lock acquisition. If a single user thread deadlocks, a system thread must also be involved.

Let's examine a simple example. To do this, we revisit and break one of our classes—the AnimatedCharacterDisplayCanvas class. This class uses a done flag to determine whether the animation should be stopped. The previous example of this class declares the done flag as volatile. This step was necessary to allow atomic access to the variable to function correctly. In this example, we incorrectly synchronize the methods.

package javathreads.examples.ch03.example6;

...

public class AnimatedCharacterDisplayCanvas extends CharacterDisplayCanvas 

                   implements CharacterListener, Runnable {

    private boolean done = false;

    ...

    protected synchronized void paintComponent(Graphics gc) {

        ...

    }



    public synchronized void run( ) {

        while (!done) {

            repaint( );

            try {

                Thread.sleep(100);

            } catch (InterruptedException ie) {

                return;

            }

        }

    }



    public synchronized void setDone(boolean b) {

        done = b;

    }

}

Two threads are involved here: the thread created by this class and the event-dispatching thread that eventually calls the setDone() method. Only one lock is shared between these threads: the lock attached to the object (the instance of the AnimatedCharacterDisplayCanvas class) that is being synchronized. The done flag is more interesting. It is a data variable that the run() method uses to determine whether it should exit. In essence, the run() method is waiting for the done flag to be set to true.

When the animation thread is started, the object lock is grabbed by the run() method. The method does not release the object lock until it has completed—which is determined by the done flag. Later, the user presses the Stop button; this generates a call to the setDone() method. The setDone() method now tries to acquire the object lock. The object lock can't be acquired until the run() methods exits. The run() method does not exit until the done flag is set. And the done flag can't be set until the setDone() method executes. This is obviously a catch-22 situation: a deadlock is created.

This example has other problems as well. When the system needs to draw the canvas, it calls the paintComponent() method from the event-dispatching thread. That thread must acquire the lock on the canvas in order to execute the paintComponent() method. Since that lock is already held by the animation thread itself, the paintComponent() method never has the opportunity to execute. When you press the Start button on the application, nothing happens (other than the application becoming totally unresponsive — you'll have to press Ctrl-C to quit).

To fix this problem, we reduce the scope of the lock used by the run() method. One way to do that is by introducing a new synchronized method that accesses the done flag:

package javathreads.examples.ch03.example7;

...

public class AnimatedCharacterDisplayCanvas extends CharacterDisplayCanvas 

                   implements CharacterListener, Runnable {

    ...

    public void run( ) {

        while (!getDone( )) {

        ...

        }

    }

    public synchronized boolean getDone( ) {

        return done;

    }

    ...

}

Now that the run() method is synchronized only while it is executing the getDone() method, the other methods have the opportunity to grab the object lock, and the program executes as desired.

This is a simple example, but, as you can see, a deadlock can occur even with simple examples. The reason that a deadlock is a problem is obvious — it prevents the application from executing correctly. Unfortunately, there is another issue; deadlocks can be very difficult to detect, particularly as a program gets more complex. Making the example even slightly more complex can obscure the deadlock. To demonstrate, we break our application further by using explicit locks within the ScoreLabel class.

package javathreads.examples.ch03.example8;

...

public class ScoreLabel extends JLabel implements CharacterListener {

    ...

    private Lock adminLock = new ReentrantLock( );

    private Lock charLock = new ReentrantLock( );

    private Lock scoreLock = new ReentrantLock( );

    ...

    public void resetGenerator(CharacterSource newGenerator) {

        try {

            adminLock.lock( );

            if (generator != null)

                generator.removeCharacterListener(this);



            generator = newGenerator;

            if (generator != null)

                generator.addCharacterListener(this);

        } finally {

            adminLock.unlock( );

        }

    }



    public void resetTypist(CharacterSource newTypist) {

        try {

            adminLock.lock( );

            if (typist != null)

                typist.removeCharacterListener(this);



            typist = newTypist;

            if (typist != null)

                typist.addCharacterListener(this);

        } finally {

            adminLock.unlock( );

        }

    }

    ...

    public void newCharacter(CharacterEvent ce) {

        try {

            scoreLock.lock( );

            charLock.lock( );

            // Previous character not typed correctly: 1-point penalty

            if (ce.source == generator) {

                if (char2type != -1) {

                    score--;

                    setScore( );

                }

                char2type = ce.character;

            }



            // If character is extraneous: 1-point penalty

            // If character does not match: 1-point penalty

            else {

                if (char2type != ce.character) {

                    score--;

                } else {

                    score++;

                    char2type = -1;

                }

                setScore( );

            }

        } finally {

            scoreLock.unlock( );

            charLock.unlock( );

        }

    } 



    public void resetScore( ) {

        try {

            charLock.lock( );

            scoreLock.lock( );

            score = 0;

            char2type = -1;

            setScore( );

        } finally {

            charLock.unlock( );

            scoreLock.unlock( );

        }

    }

}

Upon examining our ScoreLabel class, we got a very good idea. We noticed that the resetGenerator() and resetTypist() methods don't change the score or the character to be typed. In order to be more efficient, we create a lock just for these two methods — a lock that is used only by the administration methods. We further create a separate lock to distinguish the score and the character; this is just in case we need to modify one variable without the other at a later date. This is a good idea because it reduces contention for the locks, which can increase the efficiency of our program.

Unfortunately, during implementation we created a problem. Like our previous example, there is now a deadlock present in the code. Unlike the previous example, it may not be detected in testing. In fact, it may not be detected at all, as the resetScore() method is not called frequently enough for the problem to show up in testing. In our previous example, the problem manifested itself as soon as the application was started. In this example, the program can run correctly for millions of iterations, only to fail in production when the user presses the Stop or Start buttons in a certain way. Since this deadlock is dependent on the timing of the threads, it may never fail on the testing system due to the timing of the test scripts and other features of the underlying implementation. Our more complex example has a deadlock that is not consistent, making detection incredibly difficult.

So, where is the deadlock? It is related to the differences in lock acquisition between the resetScore() and newCharacter() methods. The newCharacter() method grabs the score lock first while the resetScore() method grabs the character lock first. It is now possible for one method to be called which grabs one lock, but, before it can grab the other lock, the other method is called which grabs the other lock. Both methods are waiting to grab the other lock while holding one of the locks.

Let's look at a possible run of this implementation as outlined in Figure 3-2. The thread (thread 1) that generates the random characters calls the newCharacter() method. This method first grabs the score lock (L1) and then is about to grab the character lock. At the same time, the user presses the Start button, generating a call to the resetScore() method. The event-dispatching thread (thread 2) that handles the buttons calls the resetScore( ) method. Thread 2 grabs the character lock (L2) successfully but fails to grab the score lock (L1) — it then waits for the score lock to be released. After thread 1 grabs the score lock, it then tries to grab the character lock (L2). Since the character lock is already held, it waits for it to be released. The first thread is waiting for the second thread to release the second lock while the second thread is waiting for the first thread to release the first lock. Neither can release their respective locks until they are able to acquire the other lock. This generates a catch-22 situation: a deadlock has occurred.

Figure 3-2. Deadlock in the ScoreLabel class

Can the system somehow resolve this deadlock, just as it is able to avoid the potential deadlock when a thread tries to grab the same lock again? Unfortunately, this problem is different. Unlike the case of the nested locks, where a single thread is trying to grab a single lock multiple times, this case involves two separate threads trying to grab two different locks. Since a thread owns one of the locks involved, it may have already made changes that make it impossible for it to free the lock. To be able to fix this problem at the system level, Java would need a system where the first lock can't be grabbed until it is safe from deadlock or provide a way for the deadlock to be resolved once it occurs. Either case is very complex and may be more complex than just having the developer design the program correctly.

In general, deadlocks can be very difficult to resolve. It is possible to have a deadlock that developers can't fix without a complete design overhaul. Given this complexity, it is not possible, or fair, to expect the underlying system to resolve deadlocks automatically. As for the developer, we look at the design issues related to deadlock prevention and even develop a tool that can be used to detect a deadlock in Chapter 6.

The technique used to fix the problem in Chapter 6 is to make sure that the resetScore() method acquires the locks in the same order as the newCharacter() method:

package javathreads.examples.ch03.example9;

...

public class ScoreLabel extends JLabel implements CharacterListener {

    ...

    public void resetScore( ) {

        try {

            scoreLock.lock( );

            charLock.lock( );

            score = 0;

            char2type = -1;

            setScore( );

        } finally {

            charLock.unlock( );

            scoreLock.unlock( );

        }

    }

}