Multithreading in Java for dummies (part 2)

In the first post of the series we saw some basic multithreading concepts using a practical approach. With the implementation of a Ping Pong game in mind, we'll continue introducing new improvements that we'll use to explain some additional concepts that everybody should know when implementing concurrent applications in Java.

The starting point of this post will be one of the last versions we discussed in the first post:

public class Player implements Runnable {

    private final String text;

    private Player nextPlayer;

    private volatile boolean mustPlay = false;

    public Player(String text) {
        this.text = text;
    }

    @Override
    public void run() {
        while(!Thread.interrupted()) {
            while (!mustPlay);

            System.out.println(text);

            this.mustPlay = false;
            nextPlayer.mustPlay = true;

        }
    }

    public void setNextPlayer(Player nextPlayer) {
        this.nextPlayer = nextPlayer;
    }

    public void setMustPlay(boolean mustPlay) {
        this.mustPlay = mustPlay;
    }
}

This version is quite horrible actually. We can never justify doing something like this in our code:

while(!mustPlay);

Busy waiting

This statement is an example of Busy Waiting, and it's nothing but an infinite check of a condition, avoiding the progress of the app until the condition is true. The problem of this approach is that our thread is overloading the CPU, because the Thread Scheduler does not detect anything blocking the execution of such thread, so there will be always resources keeping the thread in "Running" state (you can find a good thread state diagram here). The result is an excessive and unjustified use of resources.

I'll tell you a fun story about this. When I implemented the sample code for this series, I left my IDE open with the application running (and the busy waiting, of course). The result was that my battery, which usually lasts between 6 and 8 hours was drained in less than 2. Let's think about the consequences of this kind of faulty design in serious enterprise applications!

Locking

The easiest way to get rid of this busy waiting is using Locks. In a few words locking is a mechanism that allows us to implement exclusion policies in concurrent applications when there are resources which state can be shared an modified by different threads.

This state which can be modified by more than one thread must be protected using a critical section. Java offers different mechanisms to implement critical sections, and we'll see the most important ones in this post.

Version 3: Intrinsic Locking

The oldest mechanism in Java to create critical sections is known as Intrinsic Locking, or Monitor Locking. Each object created in Java has a lock associated (intrinsic lock or monitor lock), which can be used with exclusion goals in our threads through the use of the keyword synchronized:

//...
Object myObject = new Object();
//...
synchronized(myObject) {
    //critical section
}

In this example we're using an instance of Object as lock, so that every thread that wants to access the critical section must obtain the lock, which is what we attempt to do in the synchronized statement. If the lock is available, the thread obtains it and it won't be available for any other thread. If a new thread attempts to obtain the lock, it will fail, and its state will be set to "Blocked" by the Thread Scheduler.

Internet is full of examples about the use of synchronized, so I won't get into many details here in relation to best practices. I'll just add a few points to consider:

• It's quite usual to synchronize on this (synchronized(this)), so the own instance is using itself as lock to protect its clients from concurrency problems. However, we must be very careful if we do this because our clients could synchronize in the same instance, causing a DeadLock
• A better practice would be using a private lock (like the one we used in the code snippet above). This way we're not exposing the locking mechanism used to the outside world, because it is encapsulated in the own class
• synchronized has another goal apart from exclusion , and it's visibility. In the same way that keyword volatile ensures the immediate visibility of the modified variable, synchronized ensures the visibility of the state of the object used as lock (so the scope if bigger). This visibility is guaranteed by the Java Memory Model

Waiting mechanisms

If we use locking mechanisms only we won't be able to remove the busy waiting completely in our application. We need something else, and this is known as waiting mechanisms.

Every object exposes a method, wait(). When this method is invoked by a thread it makes the Thread Scheduler to suspend it, changing its state to "Waiting", i.e.:

//the thread state at this point is Running
i++
lock.wait(); // => thread state changes to Waiting

This example is a bit flaky, because we should never invoke wait this way. The appropriate idiom when implementing waiting mechanisms is:

synchronized (lock) {
    try {
        while (!condition)
            lock.wait();

        //Execute code after waiting for condition

    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }

In the code we see that:

1. It's necessary to acquire the lock on the object we want to invoke wait
2. That wait implies that we're waiting for "something". That something is a condition (condition predicate), which can be true before having to wait. Therefore, we check that condition before invoking wait
3. The waiting is done in a loop and not in an if sentence for several reasons. The most important one is known as "spurious wakeups". From its name it's easy to deduce what it is, sometimes a thread wakes up from "Waiting" state without anybody asking it to do it, so it can happen that the condition is not true yet and it must wait again
4. Last, but not least, wait throws InterruptedException, which we handle as discussed in the first part of this series

Having seen this, we have a thread changing to "Waiting" state expecting a condition to be true, but somebody should inform that one or more threads should wake up...Well, this is done through the methods notify and notifyAll, which, as you have probably deduced, asks to one or all the threads waiting on a lock to wake up and check the condition. The idiom is:

synchronized(lock) {
    //....
    condition = true;
    lock.notifyAll(); //or lock.notify();
}

Again, we need to be in possession of the lock to invoke the methods on the object. There are tons of articles written about the use of notify and notifyAll, it depends on the intention of each application. Precisely, the usage of notifyAllis one of the reasons why waiting for the condition to be true is done in a loop, in occasions just a single thread from all the threads waiting can progress when the condition is true.

Let's see finally how our Ping Pong app would look like after applying all the concepts we have seen:

public class Player implements Runnable {

    private final String text;

    private final Object lock;

    private Player nextPlayer;

    private volatile boolean play = false;

    public Player(String text,
                  Object lock) {
        this.text = text;
        this.lock = lock;
    }

    @Override
    public void run() {
        while(!Thread.interrupted()) {
            synchronized (lock) {
                try {
                    while (!play)
                        lock.wait();

                    System.out.println(text);

                    this.play = false;
                    nextPlayer.play = true;

                    lock.notifyAll();

                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }
    }

    public void setNextPlayer(Player nextPlayer) {
        this.nextPlayer = nextPlayer;
    }

    public void setPlay(boolean play) {
        this.play = play;
    }
}

The lock in this app could be considered the ball in the game, which in every turn can be in possession of one player only. We also see that, after printing the text in the standard output, the player notifies the other one that he can play. I have used notifyAll, but it could be notify too.

The main class doesn't vary too much over the last version of the first post in the series:

public class Game {

    public static void main(String[] args) {

        Object lock = new Object();

        Player player1 = new Player("ping", lock);
        Player player2 = new Player("pong", lock);

        player1.setNextPlayer(player2);
        player2.setNextPlayer(player1);

        System.out.println("Game starting...!");

        player1.setPlay(true);

        Thread thread2 = new Thread(player2);
        thread2.start();
        Thread thread1 = new Thread(player1);
        thread1.start();

        //Let the players play!
        try {
            Thread.sleep(2);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        //Tell the players to stop
        thread1.interrupt();
        thread2.interrupt();

        //Wait until players finish
        try {
            thread1.join();
            thread2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("Game finished!");
    }

}

Version 4: Explicit locks and conditions

Java exposes in its concurrency API an interface, Lock, which allows us to implement the same exclusion mechanisms that we have seen before using intrinsic locks, but through a different approach.

The main implementation of Lock is ReentrantLock. It has this name because the locks in Java are reentrant. This means that, once a lock is acquired by a thread, if the same thread attempts to acquire the same lock it succeeds. We're going to implement the same examples seen above using this API.

Critical sections

Lock lock = new ReentrantLock();
//...
lock.lock();
try {
    //critical section...
} finally {
    lock.unlock();
}

Easy, we only have to bear in mind that we must invoke the method unlock in the finally clause to ensure that the lock is released even in case of error.

Personally, I wouldn't say that this mechanism is better than the one offered by synchronized, as the latter is more compact. The biggest advantage of using Lock is that it comes with a bunch of methods enabling the implementation of more complex locking policies, like:

• tryLock(): we try to acquire the lock, but the thread is not blocked if it doesn't succeed
• fairness: we can create a lock as "fair". By default locks in Java are not fair, so a thread waiting can be chosen to acquire the lock even though is the last one to arrive. With a fair lock a FIFO locking will be implemented

I would advice you to have a look at the API, for further info.

Waiting mechanisms

The implementation of these mechanisms is done using the class Condition. The creation of a Condition instance must be done from a Lock:

Condition condition = lock.newCondition();

The class Condition exposes two methods, await() and signal(), with are kind of equivalent to wait() and notify() in intrinsic locks. Moreover, we can use methods such as:

• await(long time, TimeUnit unit): it waits for a condition a maximum time
• awaitUninterruptibly(): non-interruptible version of await(). This means that, if the tread that is suspended waiting for a condition is interrupted, this method won't throw the well known InterruptedException. The only way to activate it is through signal() / signalAll() on the condition (spurious wakeups apart)

In general, for waiting mechanisms I would say that the usage of Condition offers a series of very interesting features. In addition, it allows us to create different conditions associated to the same lock, which is not possible with intrinsic locks.

Let's see the aspect of our applications after adding Lock and Condition API:

public class Player implements Runnable {

    private final String text;

    private final Lock lock;
    private final Condition myTurn;
    private Condition nextTurn;

    private Player nextPlayer;

    private volatile boolean play = false;

    public Player(String text,
                  Lock lock) {
        this.text = text;
        this.lock = lock;
        this.myTurn = lock.newCondition();
    }

    @Override
    public void run() {
        while(!Thread.interrupted()) {
            lock.lock();

            try {
                while (!play)
                    myTurn.awaitUninterruptibly();

                System.out.println(text);

                this.play = false;
                nextPlayer.play = true;

                nextTurn.signal();
            } finally {
                lock.unlock();
            }
        }
    }

    public void setNextPlayer(Player nextPlayer) {
        this.nextPlayer = nextPlayer;
        this.nextTurn = nextPlayer.myTurn;
    }

    public void setPlay(boolean play) {
        this.play = play;
    }
}

We can see that the use of Condition makes the code more readable. We have used the method awaitUninterruptibly, this ensures that both players play the last turn when the main thread interrupts the threads (NOTE: There's an issue with this approach, which is discussed in the comments section).

public class Game {

    public static void main(String[] args) {
        Lock lock = new ReentrantLock();

        Player player1 = new Player("ping", lock);
        Player player2 = new Player("pong", lock);

        player1.setNextPlayer(player2);
        player2.setNextPlayer(player1);

        System.out.println("Game starting...!");

        player1.setPlay(true);

        Thread thread2 = new Thread(player2);
        thread2.start();
        Thread thread1 = new Thread(player1);
        thread1.start();

        //Let the players play!
        try {
            Thread.sleep(2);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        //Tell the players to stop
        thread1.interrupt();
        thread2.interrupt();

        //Wait until players finish
        try {
            thread1.join();
            thread2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("Game finished!");
    }
}

Bonus, scaling to N players

Let's see how easy it is to scale the game to many players, so they pass the ball between them in a particular order (this wouldn't be Ping Pong anymore :)). The output of the application would be something like this:

Game starting...!
player0
player1
player2
player3
player4
player5
...
Game finished!

It turns out we don't need to modify the class Player at all! Indeed, every player must be aware of the next player in the game only, so the only changes will have to be done in the class Game:

public class GameScale {

    public static final int NUM_PLAYERS = 6;

    public static void main(String[] args) {
        Lock lock = new ReentrantLock();

        int length = NUM_PLAYERS;

        Player[] players = new Player[length];

        for (int i=0; i < length; i++) {
            Player player = new Player("player"+i, lock);
            players[i] = player;
        }

        for (int i=0; i < length - 1; i++) {
            players[i].setNextPlayer(players[i+1]);
        }
        players[length - 1].setNextPlayer(players[0]);

        System.out.println("Game starting...!");

        players[0].setPlay(true);

        //Threads creation
        Thread[] threads = new Thread[length];
        for (int i=0; i < length; i++) {
            Thread thread = new Thread(players[i]);
            threads[i] = thread;
            thread.start();
        }

        //Let the players play!
        try {
            Thread.sleep(2);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        //Tell the players to stop
        for (Thread thread : threads) {
            thread.interrupt();
        }

        //Don't progress main thread until all players have finished
        try {
            for (Thread thread : threads) {
                thread.join();
            }
        }  catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("Game finished!");
    }

}

The code is a bit more complex, but I think it's easy to understand. Changing the constant we can scale the game as much as we want, and concurrency will ensure the turns are taken in the right order.

In the last post of the series we'll focus on the creation and management of threads, so that the class Game is less cryptic than it is now.

(All the code can be found in this GitHub repository)

Comments

[Dan]

It's a great tutorial, thank you.

I observed a problem, sometimes multi player game stuck, in my case I used 6 players and every time stuck after player4. Give me please some ticks about how to debug it ?

public void run() {
        while(!Thread.interrupted()) {
            lock.lock();
            System.out.println(text + " lock");
            try {
                System.out.println(text + " mustplay");
                while (!mustPlay)
                    myTurn.awaitUninterruptibly();

                System.out.println(text);
                this.mustPlay = false;
                nextPlayer.mustPlay = true;
                nextTurn.signal();
                System.out.println(text + " signal");
            } finally {
                System.out.println(text + " unlock");
                lock.unlock();
            }
        }
    }

Output:

player0 lock
player0 mustplay
player0
player0 signal
player0 unlock
player1
player1 signal
player1 unlock
player1 lock
player1 mustplay
player2
player2 signal
player2 unlock
player2 lock
player2 mustplay
player3
player3 signal
player3 unlock
player4
player4 signal
player4 unlock
player4 lock
player4 mustplay
player3 lock
player3 mustplay
player5
player5 signal
player5 unlock
player5 lock
player5 mustplay
player0 lock
player0 mustplay
player0
player0 signal
player0 unlock
player1
player1 signal
player1 unlock
player1 lock
player1 mustplay
player2
player2 signal
player2 unlock
player2 lock
player2 mustplay
player3
player3 signal
player3 unlock
player4
player4 signal
player4 unlock
player4 lock
player4 mustplay
player5
player5 signal
player5 unlock

[Raúl Ávila]

Thanks for your message, you have discovered a bug in my implementation, which reveals how hard it is to work with concurrent systems.

The problem is in myTurn.awaitUninterruptibly(), as its name expresses, this method is not interruptible, so when the main class interrupts all the threads, if one of the threads is blocked due to the call to this awaitUninterruptibly method, then the thread won't wake up. This situation is not extremely likely, in fact it didn't happen to me when I implemented the example, but I was able to reproduce it after reading your message.

Debugging this kind of issues is quite hard, and it took me some time to understand what was going on. The only solution that comes to my mind at the moment is changing the call to awaitUninterruptibly to await, which receives a timeout. We can configure a long timeout if we want, but for this case 1 minute is more than enough, in fact the timeout will never happen, as the method will be interrupted:

     while(!Thread.interrupted()) {
            lock.lock();

            try {
                while (!play)
                    myTurn.await(1, TimeUnit.MINUTES);

                this.play = false;
                nextPlayer.play = true;

                nextTurn.signal();

            } catch(InterruptedException e) {
                Thread.currentThread().interrupt();
            }
            finally {
                lock.unlock();
            }
        }

Note that we need to catch InterruptedException and propagate the interruption to the thread, so the loop exits normally.

I hope it makes sense, and again, thanks for your message!!!

[Ismail Ibrahim]

This has been a great post so far. I have one worry though. I've tried using 2ms when invoking sleep() but the main thread terminates even before the thread1 and thread2 starts executing.

[Raúl Ávila]

If I understood correctly, I think that means the Thread scheduler does not start the two "players" in those 2ms, so the main thread requests the interruption before they can enter in the loop to play. It's weird, but it can happen. Have you tried increasing the sleep time to let's say, 10 or 20ms?

[Ismail Ibrahim]

Exactly. I thought so too. It works well with 10.👍