The only guide you’ll need on concurrency & multithreading for senior engineers. Pressure test your skills with real-world practice problems from top companies.

Concurrency in Java is one of the most complex and advanced topics brought up during senior engineering interviews. Knowledge of concurrency and multithreading can put interviewees at a considerable advantage. This course lays the foundations of advanced concurrency and multithreading and explains concepts such as Monitors and Deferred Callbacks in depth. It also builds simple and complete solutions to popular concurrency problems that can be asked about in interviews like the Reader-Writer Problem and the Dining Philosopher Problem. While prior knowledge of concurrency is not required to follow through with this course, familiarity with the very basics of concurrency would be helpful.

Java Multithreading for Senior Engineering Interviews

# Problem Statement
Java does provide its own implementation of Semaphore, however, Java's semaphore is initialized with an initial number of permits, rather than the maximum possible permits and the developer is expected to take care of always releasing the intended number of maximum permits. Briefly, a semaphore is a construct that allows some threads to access a fixed set of resources in parallel. Always think of a semaphore as having a fixed number of permits to give out. Once all the permits are given out, requesting threads, need to wait for a permit to be returned before proceeding forward.
Your task is to implement a semaphore which takes in its constructor the maximum number of permits allowed and is also initialized with the same number of permits.

# Solution
Given the above definition we can now start to think of what functions our Semaphore class will need to expose. We need a function to "gain the permit" and a function to "return the permit".

<ol>
 <li><code class="mthd">acquire()</code> function to simulate gaining a permit</li>
 <li><code class="mthd">release()</code> function to simulate releasing a permit</li>
 </ol>

The constructor accepts an integer parameter defining the number of permits available with the semaphore. Internally we need to store a count which keeps track of the permits given out so far.

The skeleton for our Semaphore class looks something like this so far.


```java
public class CountingSemaphore {

 int usedPermits = 0; // permits given out
 int maxCount; // max permits to give out

 public CountingSemaphore(int count) {
 this.maxCount = count;
 }

 public synchronized void acquire() throws InterruptedException {
 }

 public synchronized void release() throws InterruptedException {
 }
}
```
 

Note we have added the <code class="clazz">synchronized</code> keyword to both the class methods. Adding the synchronized keyword causes only a single thread to execute either of the methods. If a thread is currently executing <code class="mthd">acquire()</code> then another thread can't execute <code class="mthd">release()</code> on the same semaphore object. Note this will guarantee that the <code class="mthd">usedPermits</code> variable is correctly incremented or decremented.
The astute observer would question why we don't take the locking to finer grained level and use java's lock so that multiple threads can call either of the two functions. With <code class="clazz">synchronized</code> only one thread can call either release or acquire. However, the counter to that is, even with finer grained locking the entire code blocks within the two methods will be guarded by a single lock and that would pretty much be the same as putting synchronized on the methods definitions. 

Now let us fill in the implementation for our acquire method. When can a thread not be allowed to acquire a semaphore? When all the permits are out! This implies we'll need to <code class="mthd">wait()</code> when <code class="mthd"> usedPermits == maxCount</code> If this condition isn't true we simply increment <code class="mthd">usedPermits</code> to simulate giving out a permit.

The implementation of the acquire method appears below. Note that we are also <code class="mthd">notify()</code>-ing at the end of the method. We'll talk shortly, about why we need it.


```java
1. public class CountingSemaphore {
2. 
3. int usedPermits = 0; // permits given out
4. int maxCount; // max permits to give out
5. 
6. public CountingSemaphore(int count) {
7. this.maxCount = count;
8. }
9. 
10. public synchronized void acquire() throws InterruptedException {
11.
12. while (usedPermits == maxCount)
13. wait();
14.
15. usedPermits++;
16. notify();
17. }
18.
19. public synchronized void release() throws InterruptedException {
20. }
21. }
```
 

Implementing the release method should require a simple decrement of the <code class="mthd">usedPermits</code> variable. However when should we block a thread from proceeding forward like we did in <code class="mthd">acquire()</code> method? If <code class="mthd">usedPermits == 0</code> then it won't make sense to decrement <code class="mthd">usedPermits</code> and we should block at this condition. This might seem counter-intuitive, you might ask why would someone call <code class="mthd">release()</code> before calling <code class="mthd">acquire()</code> - This is entirely possible since semaphore can also be used for signalling between threads. A thread can call <code class="mthd">release()</code> on a semaphore object before another thread calls <code class="mthd">acquire()</code> on the same semaphore object. There is no concept of ownership for a semaphore ! Hence different threads can call acquire or release methods as they deem fit. This also means that whenever we decrement or increment the <code class="mthd">usedPermits</code> variable we need to call <code class="mthd">notify()</code> so that any waiting thread in the other method is able to move forward. The full implementation appears below


```java
1. public class CountingSemaphore {
2. 
3. int usedPermits = 0; // permits given out
4. int maxCount; // max permits to give out
5. 
6. public CountingSemaphore(int count) {
7. this.maxCount = count;
8. 
9. }
10.
11. public synchronized void acquire() throws InterruptedException {
12.
13. while (usedPermits == maxCount)
14. wait();
15.
16. usedPermits++;
17. notify();
18. }
19. 
20. public synchronized void release() throws InterruptedException {
21.
22. while (usedPermitsls == 0)
23. wait();
24.
25. usedPermits--;
26. notify();
27. }
28. }
```


As a follow-up, notice that we increment/decrement the <code class="mthd">usedPermits</code> variable on line 16 and 25 respectively and then call <code class="mthd">notify()</code>. Does it matter if we switch the order of the two statements, i.e. call <code class="mthd">notify()</code> first and then manipulate <code class="mthd">usedPermits</code> ? The answer is no.

When <code class="mthd">notify()</code> is called, the executing thread is still synchronized on the semaphore object and any other thread will not be scheduled until the executing thread exists the <code class="mthd">release()</code> or <code class="mthd">acquire()</code> method and by then the <code class="mthd">usedPermits</code> variable has already been incremented or decremented even though that is the last statement in each method.

Also, remember that semaphores solve the problem of missed signals between cooperating threads. Imagine a producer/consumer application where the producer wants to notify the consumer of available content for consumption. The producer can call <code class="mthd">acquire()</code> on a binary semaphore (one with max permits = 1) and the consumer can call <code class="mthd">release()</code> before attempting to consume. This way the "signal" is in a sense stored for the consumer whenever the producer produces something.
</div>
</div>

# Solution
Given the above definition we can now start to think of what functions our Semaphore class will need to expose. We need a function to "gain the permit" and a function to "return the permit".

<ol>
 <li><code>acquire()</code> function to simulate gaining a permit</li>
 <li><code>release()</code> function to simulate releasing a permit</li>
 </ol>

The constructor accepts an integer parameter defining the number of permits available with the semaphore. Internally we need to store a count which keeps track of the permits given out so far.

The skeleton for our Semaphore class looks something like this so far.


```java
public class CountingSemaphore {

 int usedPermits = 0; // permits given out
 int maxCount; // max permits to give out

 public CountingSemaphore(int count) {
 this.maxCount = count;
 }

 public synchronized void acquire() throws InterruptedException {
 }

 public synchronized void release() throws InterruptedException {
 }
}
```
 

Note we have added the <code>synchronized</code> keyword to both the class methods. Adding the synchronized keyword causes only a single thread to execute either of the methods. If a thread is currently executing <code>acquire()</code> then another thread can't execute <code>release()</code> on the same semaphore object. Note this will guarantee that the <code>usedPermits</code> variable is correctly incremented or decremented.
The astute observer would question why we don't take the locking to finer grained level and use java's lock so that multiple threads can call either of the two functions. With <code>synchronized</code> only one thread can call either release or acquire. However, the counter to that is, even with finer grained locking the entire code blocks within the two methods will be guarded by a single lock and that would pretty much be the same as putting synchronized on the methods definitions. 

Now let us fill in the implementation for our acquire method. When can a thread not be allowed to acquire a semaphore? When all the permits are out! This implies we'll need to <code>wait()</code> when <code> usedPermits == maxCount</code> If this condition isn't true we simply increment <code>usedPermits</code> to simulate giving out a permit.

The implementation of the acquire method appears below. Note that we are also <code>notify()</code>-ing at the end of the method. We'll talk shortly, about why we need it.


```java
1. public class CountingSemaphore {
2. 
3. int usedPermits = 0; // permits given out
4. int maxCount; // max permits to give out
5. 
6. public CountingSemaphore(int count) {
7. this.maxCount = count;
8. }
9. 
10. public synchronized void acquire() throws InterruptedException {
11.
12. while (usedPermits == maxCount)
13. wait();
14.
15. usedPermits++;
16. notify();
17. }
18.
19. public synchronized void release() throws InterruptedException {
20. }
21. }
```
 

Implementing the release method should require a simple decrement of the <code>usedPermits</code> variable. However when should we block a thread from proceeding forward like we did in <code>acquire()</code> method? If <code>usedPermits == 0</code> then it won't make sense to decrement <code>usedPermits</code> and we should block at this condition. This might seem counter-intuitive, you might ask why would someone call <code>release()</code> before calling <code>acquire()</code> - This is entirely possible since semaphore can also be used for signalling between threads. A thread can call <code>release()</code> on a semaphore object before another thread calls <code>acquire()</code> on the same semaphore object. There is no concept of ownership for a semaphore ! Hence different threads can call acquire or release methods as they deem fit. This also means that whenever we decrement or increment the <code>usedPermits</code> variable we need to call <code>notify()</code> so that any waiting thread in the other method is able to move forward. The full implementation appears below


```java
1. public class CountingSemaphore {
2. 
3. int usedPermits = 0; // permits given out
4. int maxCount; // max permits to give out
5. 
6. public CountingSemaphore(int count) {
7. this.maxCount = count;
8. 
9. }
10.
11. public synchronized void acquire() throws InterruptedException {
12.
13. while (usedPermits == maxCount)
14. wait();
15.
16. usedPermits++;
17. notify();
18. }
19. 
20. public synchronized void release() throws InterruptedException {
21.
22. while (usedPermitsls == 0)
23. wait();
24.
25. usedPermits--;
26. notify();
27. }
28. }
```


As a follow-up, notice that we increment/decrement the <code>usedPermits</code> variable on line 16 and 25 respectively and then call <code>notify()</code>. Does it matter if we switch the order of the two statements, i.e. call <code>notify()</code> first and then manipulate <code>usedPermits</code> ? The answer is no.

When <code>notify()</code> is called, the executing thread is still synchronized on the semaphore object and any other thread will not be scheduled until the executing thread exists the <code>release()</code> or <code>acquire()</code> method and by then the <code>usedPermits</code> variable has already been incremented or decremented even though that is the last statement in each method.

Also, remember that semaphores solve the problem of missed signals between cooperating threads. Imagine a producer/consumer application where the producer wants to notify the consumer of available content for consumption. The producer can call <code>acquire()</code> on a binary semaphore (one with max permits = 1) and the consumer can call <code>release()</code> before attempting to consume. This way the "signal" is in a sense stored for the consumer whenever the producer produces something.
</div>
</div>

Learn how to design and implement a simple semaphore class in Java.

The Basics

Multithreading in Java

Java's Memory Model

Interview Practice Problems

Bonus Questions

Beyond the Interview

Java Concurrency Reference

Revision & Quizzes

Implementing Semaphore

Problem Statement