Understanding Thread Synchronization
Working through a university level exam problem using Semaphores and synchronized blocks!
Why do we need synchronization?
Imagine what driving would be like if there were no traffic lights, no street signs or any driving rules to help regulate the flow of traffic. Chaotic would be one way to describe it. The same kind of chaos would happen in a multi-thread environment if there was no synchronization and mutual exclusion. In this article, I will show you the importance of protecting shared resources between threads and how to regulate communications between them.
Disclaimer: The example problem I will be explaining is a bit intermediate and I'll be using only Semaphores and synchronized blocks. If you are unfamiliar with the basic concepts of synchronization and Semaphores, I suggest you read up on them and then return to this example. I have linked some useful articles and literature at the end for you to check out!
With that out of the way, let's get started!
The problem:
Today we’re going to implement a system for synchronizing a basketball tournament, here is the information and rules we must follow:
- There are 50 players participating in the tournament grouped in arbitrary teams
- At most 10 players can enter the arena at once. After he enters, a player should print “Player enters the arena…”
- After entering the arena, the players enter the locker room where they get ready for the game. The locker room has a capacity of 5 meaning that at most 5 players can be in the dressing room at once. When a player enters, he should print “Player in locker room…”.
- Once ready, the player exits the locker room and waits for the other players to finish getting ready.
- After all 10 players are ready, the game can start and every player should print “Playing basketball…”
- After the game is over, all players should print “Stopped playing…” and the last player should print “Game finished.” denoting that the arena is free for another 10 players to enter and play their game.
For this problem I will be using Java, which is my preferred programming language. You can recreate this problem in any language that supports multithreading.
The code below is our starter code. It represents a basketball player in the tournament. However in order to achieve our goal, we have to make some modifications.
class BasketballPlayer {
public void execute() throws InterruptedException {
// at most, 10 players should print this in parallel
System.out.println("Player enters the arena…”);
// at most 5 players may enter in the locker room in parallel
System.out.println("Player in locker room…");
Thread.sleep(10); // this represents the dressing time
// after all players are ready, they should start with the game together
System.out.println("Playing basketball…”);
Thread.sleep(100); // this represents the game duration
// after the game is over, each player announces that they have stopped
System.out.println("Stopped playing…");
// only one player should print the next line,
// representing that the game has finished
System.out.println("Game finished.");
}
}
For starters, we need our BasketballPlayer class to extend the Thread class (in order to become a thread itself). Next we need to override the run() method and call the execute() method (which represents all of the logic in this example). Also, I will delete the comments from the started code to make it easier to read.
public class BasketballPlayer extends Thread{
public void execute() throws InterruptedException {
System.out.println("Player enters the arena…");
System.out.println("Player in locker room…");
Thread.sleep(10); // this represents the dressing time
System.out.println("Playing basketball…");
Thread.sleep(100); // this represent the game duration
System.out.println("Stopped playing…");
System.out.println("Game finished.");
}
@Override
public void run() {
try {
execute();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
Next up, we’re going to create another class called Counter to help us keep track of the players entering and leaving the locker room, as well as the players playing and after the game, leaving the arena. In total, we have to keep track of 4 different events, but this is achieved using only 1 counter variable.
public class Counter {
private int count;
public Counter() {
this.count = 0;
}
public synchronized void setCount(int c) {
this.count = c;
}
public synchronized int getCount() {
return this.count;
}
public synchronized void increment() {
this.count++;
}
public synchronized void decrement() {
this.count--;
}
}
You might have noticed the key word synchronized, this is very important! The counter is going to be a shared resource, meaning multiple threads will try to change its value at the same time, we must regulate that! Java provides a way of synchronizing a thread’s task by using synchronized blocks. Multiple synchronized blocks on the same object cannot be executed simultaneously, you can only have one thread executing them at a single moment. All other threads attempting to enter the synchronized block are blocked until the thread inside exits. If you need to read more about this concept, check out this article from GeeksforGeeks.
And now, let's welcome the stars of our show, the Semaphores! We'll declare them in our BasketballPlayer class and we'll also need two Counters.
private static Semaphore arena = new Semaphore(10);
private static Semaphore lockerRoom = new Semaphore(5);
private static Semaphore gameWhistle = new Semaphore(1);
private static Counter playersInLockerRoom = new Counter();
private static Counter playersOnTheCourt = new Counter();
We initialize our arena Semaphore with 10 permits, because a maximum of 10 players are allowed to enter the arena at once.
Same thing goes for our lockerRoom Semaphore, the locker room has a capacity of 5, so at most we can have 5 players in there at once.
Finally, our gameWhistle Semaphore will regulate the start and end of a basketball game.
The best way to tackle this problem, is to divide it into key parts.
First, the players try to enter the arena.
arena.acquire();
// at most, 10 players should print this in parallel
System.out.println("Player enters the arena…");
Next, the players try to enter the locker room.
lockerRoom.acquire();
// at most 5 players may enter in the locker room in parallel
System.out.println("Player in locker room…");
Now, our playersInLockerRoom counter comes into play!
When a player enters the locker room, we increment the counter. If it equals 5, that means we have reached our limit of players and any subsequent players that try to enter our locker room are blocked by the lockerRoom Semaphore.
After the first 5 are done, we then release another 5 players who have been blocked by our lockerRoom Semaphore and allow them to enter so they can get ready. At this moment, we also have to reset our playersInLockerRoom counter.
playersInLockerRoom.increment();
if (playersInLockerRoom.getCount() == 5) {
playersInLockerRoom.setCount(0); // resetting the counter for the new 5 players
lockerRoom.release(5);
}
// this represents the dressing time,
// be careful where you place it!
Thread.sleep(10);
After a player is done getting ready, he steps onto the court.
We're almost done! I'll explain this last bit after the code, so check it out and see you down below!
// after a player is ready, he steps onto the court and waits for the other players.
playersOnTheCourt.increment();
if (playersOnTheCourt.getCount() == 10) {
gameWhistle.acquire(); // game started
}
// after all players are ready, they should start with the game together
System.out.println("Playing basketball…");
Thread.sleep(100); // this represents the game duration
// after the game is over, each player announces that they have stopped
System.out.println("Stopped playing…");
playersOnTheCourt.decrement(); // players leaving the court...
if (playersOnTheCourt.getCount() == 0) {
// only one player should print the next line, representing that the game has finished
System.out.println("Game finished.");
gameWhistle.release();
arena.release(10);
}
Similarly like with the locker room, we need to keep track of the players exiting the locker room and stepping on the court, this is why we created our playersOnTheCourt counter.
When the number of players on the court is 10 (meaning all 10 players are done getting ready in the locker room) the game can start. We try to acquire() the start of our game and start playing basketball!
We put all of our threads to sleep for 100ms to simulate the game, once that’s over they stop playing and start leaving the court.
Once all the players have left (playersOnTheCourt == 0), the last player prints out that the game is over and he releases the gameWhistle Semaphore indicating the court is free for the next players to play. Furthermore, we release another 10 players into the arena, their turn to play has finally arrived!
Final look at our BasketballPlayer class
public class BasketballPlayer extends Thread {
private static Semaphore arena = new Semaphore(10);
private static Semaphore lockerRoom = new Semaphore(5);
private static Semaphore gameWhistle = new Semaphore(1);
private static Counter playersInLockerRoom = new Counter();
private static Counter playersOnTheCourt = new Counter();
public void execute() throws InterruptedException {
arena.acquire();
// at most, 10 players should print this in parallel
System.out.println("Player enters the arena…");
lockerRoom.acquire();
// at most 5 players may enter in the locker room in parallel
System.out.println("Player in locker room…");
playersInLockerRoom.increment();
if (playersInLockerRoom.getCount() == 5) {
playersInLockerRoom.setCount(0);
lockerRoom.release(5);
}
Thread.sleep(10); // this represents the dressing time
// after a player is ready, he steps onto the court and waits for the other players.
playersOnTheCourt.increment();
if (playersOnTheCourt.getCount() == 10) {
gameWhistle.acquire(); // game started!
}
// after all players are ready, they should start with the game together
System.out.println("Playing basketball…");
Thread.sleep(100); // this represents the game duration
// after the game is over, each player announces that they have stopped
System.out.println("Stopped playing…");
playersOnTheCourt.decrement(); // players leaving the court...
if (playersOnTheCourt.getCount() == 0) {
// only one player should print the next line,
// representing that the game has finished
System.out.println("Game finished.");
gameWhistle.release();
arena.release(10);
}
}
@Override
public void run() {
try {
execute();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
Finally, let's quickly write our main so we can test out our solution.
public class BasketballTournament {
public static void main(String[] args) {
HashSet<BasketballPlayer> threads = new HashSet<>();
for (int i = 0; i < 100; i++) {
BasketballPlayer bp = new BasketballPlayer();
threads.add(bp);
}
// run all threads in background
for (BasketballPlayer bp : threads) {
bp.start();
}
// once all of them are started,
// wait a maximum of 5000 ms for each of them to finish
for (BasketballPlayer bp : threads) {
try {
bp.join(5000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
// check each thread and terminate it if it has not finished
for (BasketballPlayer bp : threads) {
if (bp.isAlive()) {
System.out.println("Possible deadlock!");
bp.interrupt();
}
}
System.out.println("Tournament finished.");
}
}
Conclusion
Whew well that was a long one. If you made it to the end, congratulations and thank you for your attention!
I hope that you understood the analogies in this problem, I'll now quickly explain them and the rest of the solution.
The players are threads, the arena and locker room are shared resources.
The restriction "at most 10 players can enter the arena" and "the locker room has a capacity of 5" tell us that we need to have Semaphores regulating the shared resource. The arena Semaphore is initialized with 10 permits and the locker room Semaphore is initialized with 5 permits.
Finally we have one more restriction that we have to take care of. In the text of the problem, it's stated that "After all 10 players are ready, the game can start". We need one more Semaphore initialized with 1 permit that regulates the start of our game. Note: because the Semaphore has only one permit, we can also use a Lock in its place.
That takes care of the Semaphores, let's quickly explain the counters.
They are also a shared resource, just like the arena and locker room, so the same logic applies. In this case we could've also used Semaphores (with 1 permit) or Locks, but I decided to use the keyword synchronized. This keyword makes our methods mutually exclusive (accessible to only one thread at a time). This way, it's so much easier and we don't have to worry about acquiring and releasing Semaphores/Locks.
Final words and bonus reading material
I could've gone into more depth about this problem and the solution, but this article would've been way too long. If you have any questions, please don't hesitate to leave them in the comment section or email me. I'll be more than happy to explain any ambiguities you might have!
Hope I helped you understand thread synchronization a little bit better.
Once again thank you for your time and see you in the next article!
P.S: Here are some links to articles and documentation explaining Semaphores and the synchronized keyword in more detail. Also, make sure to check out my previous article about processes and threads!
Semaphores
Synchronized Methods
Synchronization in Java