Concurrency
Developing single-threaded Java applications is rarely feasible. Therefore, most of your projects will be multithreaded (that is, they will run in a multithreaded environment). This means that, sooner or later, you'll have to tackle certain multithreading problems. In other words, at some point, you'll have to get your hands dirty with code that manipulates Java threads directly or via dedicated APIs.
This chapter covers the most popular questions about Java concurrency (multithreading) that occur in general interviews about the Java language. As usual, we will start with a brief introduction that covers the main aspects of Java concurrency. Therefore, our agenda is straightforward, covering the following topics:
- Java concurrency (multithreading) in a nutshell
- Questions and coding challenges
Let's begin with the fundamental knowledge of our topic, Java concurrency. Use the following nutshell section to extract answers to some basic questions about concurrency, such as What is concurrency?, What is a Java thread?, What is multithreading?, and more.
Technical Requirements
The codes used in this chapter can be found on GitHub on: https://github.com/PacktPublishing/The-Complete-Coding-Interview-Guide-in-Java/tree/master/Chapter16
Java concurrency (multithreading) in a nutshell
Our computers can run multiple programs or applications at the same time (for example, we can listen to music on a media player and navigate the internet at the same time). A process is an executing instance of a program or application (for example, by double-clicking on the NetBeans icon on your computer, you start a process that will run the NetBeans program). Additionally, a thread is a lightweight subprocess that represents the smallest executable unit of work of a process. A Java thread has relatively low overhead, and it shares common memory space with other threads. A process can have multiple threads with one main thread.
Important note
The main difference between processes and threads is the fact that threads share common memory space while processes don't. By sharing memory, threads shave off lots of overhead.
Concurrency is the ability of an application to handle the multiple tasks it works on. The program or application can process one task at a time (sequential processing) or process multiple tasks at the same time (concurrent processing).
Do not confuse concurrency with parallelism. Parallelism is the ability of an application to handle each individual task. The application can process each task serially, or it can split the task up into subtasks that can be processed in parallel.
Important note
Concurrency is about handling (not doing) lots of things at once, while parallelism is about doing lots of things at once.
Concurrency is achieved via multithreading. Multithreading is a technique that enables a program or application to handle more than one task at a time and to also synchronize those tasks. This means that multithreading allows the maximum utilization of a CPU by executing two or more tasks virtually at the same time. We say virtually at the same time here because the tasks only look like they are running simultaneously; however, essentially, they cannot do that. They take advantage of CPU context switching or the time slicing feature of the operating system. In other words, CPU time is shared across all running tasks, and each task is scheduled to run for a certain period of time. Hence, multithreading is the key to multitasking.
Important note
With a single-core CPU, we may achieve concurrency but not parallelism.
In conclusion, threads can create the illusion of multitasking; however, at any given point in time, the CPU is executing only one thread. The CPU switches control between the threads so quickly that it creates the illusion that the tasks are executed (or advance) in parallel. Actually, they are executed concurrently. Nevertheless, with advances in hardware technology, it is now common to have multi-core machines and computers. This means that applications can take advantage of these architectures and have a dedicated CPU running each thread.
The following diagram clarifies the confusion between concurrency and parallelism via four threads (T1, T2, T3, and T4):
16.1 – Concurrency versus parallelism
So, an application can be one of the following:
- Concurrent but not parallel: It executes more than one task at the same time, but no two tasks are executed at the same time.
- Parallel but not concurrent: It executes multiple subtasks of a task in a multi-core CPU at the same time.
- Neither parallel nor concurrent: It executes all of the tasks one at a time (sequential execution).
- Both parallel and concurrent: It executes multiple tasks concurrently in a multi-core CPU at the same time.
A set of homogenous worker threads that are assigned to execute tasks is called a thread pool. A worker thread that finishes a task is returned to the pool. Typically, thread pools are bound to a queue of tasks and can be tuned to the size of the threads they hold. Commonly, for optimal performance, the size of a thread pool is equal to the number of CPU cores.
The synchronization of a multithreaded environment is achieved via locking. Locking is used to orchestrate and limit access to a resource in a multithreaded environment.
If multiple threads can access the same resource without causing errors or unpredictable behaviors/results, then we are in a thread-safe context. Thread safety can be achieved via various synchronization techniques (for example, the Java synchronized keyword).
Next, let's tackle several questions and coding challenges regarding concurrency in Java.
Questions and coding challenges
In this section, we will cover 20 concurrency questions and coding challenges that are very popular in interviews.
You should be aware that Java concurrency is a wide and complex topic that needs to be covered in great detail by any Java developer. Having fundamental insights about Java concurrency should be enough to pass a general Java language interview, but it is not enough for specific interviews (for example, if you apply for a job that will imply developing a concurrency API, then you must deep dive into this topic and learn advanced concepts – most probably, the interview will be concurrency-centric).
Coding challenge 1 – Thread life cycle states
Problem: Enumerate and explain, in a few sentences, the states of a Java Thread.
Solution: The states of a Java thread are available via the Thread.State enumeration. The possible states of a Java thread can be seen in the following diagram:
16.2 – Java thread states
The different lifecycle states of a Java Thread are as follows:
- The NEW state: A thread that is created but not started (this is the state until the Thread#start() method is invoked).
- The RUNNABLE state: By calling the Thread#start() method, the thread passes from NEW to RUNNABLE. In the RUNNABLE state, a thread can be running or ready to run. A thread that is waiting for the JVM (Java Virtual Machine) thread scheduler to allocate the necessary resources and time to run is ready to run, but it is not running yet. As soon as the CPU is available, the thread scheduler will run the thread.
- The BLOCKED state: A thread that executes synchronized blocks or I/O tasks may enter the BLOCKED state. For example, if a thread, t1, attempts to enter into a synchronized block of code (for example, a block of code marked synchronized) that is already being accessed by another thread, t2, then t1 is held in the BLOCKED state until it can acquire the required lock.
- The WAITING state: A thread, t1, that waits (without having set an explicit timeout period) for another thread, t2, to finish its job is in the WAITING state.
- The TIMED WAITING state: A thread, t1, that waits for an explicit period of time (typically, this is specified in milliseconds or seconds) for another thread, t2, to finish its job is in the TIMED_WAITING state.
- The TERMINATED state: A Java thread that is abnormally interrupted or successfully finishes its job is in the TERMINATE state.
Besides describing the possible states of a Java thread, the interviewer might ask you to code an example for each state. This is why I highly recommended that you take your time and analyze the application named ThreadLifecycleState (for brevity, the code is not listed in the book). The application is structured in a very intuitive way, and the leading comments explain each scenario/state.
Coding challenge 2 – Deadlocks
Problem: Explain deadlock to us and we'll hire you!
Solution: Hire me, and I'll explain it to you.
Here, we've just described a deadlock.
A deadlock can be explained like this: thread T1 holds the lock, P, and is trying to acquire the lock, Q. At the same time, there is thread T2 that holds the lock, Q, and is trying to acquire the lock, P. This kind of deadlock is known as circular wait or deadly embrace.
Java doesn't provide deadlock detection and/or a resolving mechanism (like databases have, for example). This means that a deadlock can be very embarrassing for an application. A deadlock can partially or completely block an application. This leads to significant performance penalties, unexpected behaviors/results, and more. Commonly, deadlocks are hard to find and debug, and they force you to restart the application.
The best way to avoid race deadlocks is to avoid using nested locks or unnecessary locks. Nested locks are quite prone to deadlocks.
A common problem of simulating a deadlock is The Dining Philosophers problem. You can find a detailed explanation and implementation of this problem in the Java Coding Problems book (https://www.packtpub.com/programming/java-coding-problems). Java Coding Problems contains two chapters that are dedicated to Java concurrency and are meant to dive deep into this topic using specific problems.
In the code bundle for this book, you can find a simple example of causing a deadlock named Deadlock.
Coding challenge 3 – Race conditions
Problem: Explain what race conditions are.
Solution: First of all, we must mention that a snippet/block of code that can be executed by multiple threads (that is, executed concurrently) and exposes shared resources (for example, shared data) is known as a critical section.
Race conditions occur when threads pass through such critical sections without thread synchronization. The threads race through the critical section attempting to read/write shared resources. Depending on the order in which threads finish this race, the application's output changes (two runs of the application may produce different outputs). This leads to inconsistent behavior in the application.
The best way to avoid race conditions involves the proper synchronization of critical sections by using locks, synchronized blocks, atomic/volatile variables, synchronizers, and/or message passing.
Coding challenge 4 – reentrant locking
Problem: Explain what is the reentrant locking concept.
Solution: Generally speaking, reentrant locking refers to a process that can acquire a lock multiple times without deadlocking itself. If a lock is not reentrant, then the process can still acquire it. However, when the process tries to acquire the lock again, it will be blocked (deadlock). A reentrant lock can be acquired by another thread or recursively by the same thread.
A reentrant lock can be used for a piece of code that doesn't contain updates that could break it. If the code contains a shared state that can be updated, then acquiring the lock again will corrupt the shared state since the code is called while it is executing.
In Java, a reentrant lock is implemented via the ReentrantLock class. A reentrant lock acts like this: when the thread enters the lock for the first time, a hold count is set to one. Before unlocking, the thread can re-enter the lock causing the hold count to be incremented by one for each entry. Each unlock request decrements the hold count by one, and, when the hold count is zero, the locked resource is opened.
Coding challenge 5 – Executor and ExecutorService
Problem: What are Executor and ExecutorService?
Solution: In the java.util.concurrent package, there are a number of interfaces that are dedicated to executing tasks. The simplest one is named Executor. This interface exposes a single method named execute (Runnable command).
A more complex and comprehensive interface, which provides many additional methods, is ExecutorService. This is an enriched version of Executor. Java comes with a full-fledged implementation of ExecutorService, named ThreadPoolExecutor.
In the code bundle for this book, you can find simple examples of using Executor and ThreadPoolExecutor in the application named ExecutorAndExecutorService.
Coding challenge 6 – Runnable versus Callable
Problem: What is the difference between the Callable interface and the Runnable interface?
Solution: The Runnable interface is a functional interface that contains a single method named run(). The run() method doesn't take any parameters and returns void. Moreover, it cannot throw checked exceptions (only RuntimeException). These statements make Runnable suitable in scenarios where we are not looking for the result of the thread execution. The run() signature is as follows:
void run()
On the other hand, the Callable interface is a functional interface that contains a single method named call(). The call() method returns a generic value and can throw checked exceptions. Typically, Callable is used in ExecutorService instances. It is useful for starting an asynchronous task and then calling the returned Future instance to get its value. The Future interface defines methods for obtaining the result generated by a Callable object and for managing its state. The call() signature is as follows:
V call() throws Exception
Notice that both of these interfaces represent a task that is intended to be executed concurrently by a separate thread.
In the code bundle for this book, you can find simple examples of using Runnable and Callable in the application named RunnableAndCallable.
Coding challenge 7 – Starvation
Problem: Explain what thread starvation is.
Solution: A thread that never (or very rarely) gets CPU time or access to the shared resources is a thread that experiences starvation. Since it cannot obtain regular access to shared resources, this thread cannot progress its job. This happens because other threads (so-called greedy threads) get access before this thread and make the resources unavailable for long periods of time.
The best way to avoid thread starvation is to use fair locks, such as Java ReentrantLock. A fair lock grants access to the thread that has been waiting the longest. Having multiple threads run at once while preventing starvation can be accomplished via Java Semaphore. A fair Semaphore guarantees the granting of permits under contention using FIFO.
Coding challenge 8 – Livelocks
Problem: Explain what thread livelock is.
Solution: A livelock takes place when two threads keep taking actions in response to another thread. The threads don't make any progress with their own jobs. Notice that the threads are not blocked; both of them are too busy responding to each other to resume work.
Here is an example of a livelock: imagine two people trying to cross each other in a hallway. Mark moves to his right to let Oliver pass, and Oliver moves to his left to let Mark pass. Both are now blocking each other. Mark sees that he's blocking Oliver and moves to his left, and Oliver moves to his right after seeing that he's blocking Mark. They never manage to cross each other and keep blocking each other.
We can avoid livelocks via ReentrantLock. This way, we can determine which thread has been waiting the longest and assign it a lock. If a thread can't acquire a lock, it should release the previously acquired locks and try again later.
Coding challenge 9 – Start() versus run()
Problem: Explain the main differences between the start() method and the run() method in a Java Thread.
Solution: The main difference between start() and run() is the fact that the start() method creates a new thread while the run() method doesn't. The start() method creates a new thread and calls the block of code written inside the run() method of this new thread. The run() method executes that code on the same thread (that is, the calling thread) without creating a new thread.
Another difference is that calling start() twice on the thread object will throw an IllegalStateException. On the other hand, calling the run() method twice doesn't lead to an exception.
Typically, novices ignore these differences, and, since the start() method eventually calls the run() method, they believe there is no reason to call the start() method. Therefore, they call the run() method directly.
Coding challenge 10 – Thread versus Runnable
Problem: To implement a thread, should we extend Thread or implement Runnable?
Solution: As the question suggests, implementing a Java thread can be accomplished by extending java.lang.Thread or by implementing java.lang.Runnable. The preferred way to go is to implement Runnable.
Most of the time, we implement a thread just to give it something to run, not to overwrite the behavior of the Thread. As long as all we want is to give something to run to a thread, we definitely should stick to implementing Runnable. In fact, using Callable or FutureTask is an even better choice.
In addition to this, by implementing Runnable, you can still extend another class. By extending Thread, you cannot extend another class since Java doesn't support multiple inheritances.
Finally, by implementing Runnable, we separate the task definition from the task execution.
Coding challenge 11 – CountDownLatch versus CyclicBarrier
Problem: Explain the main differences between CountDownLatch and CyclicBarrier.
Solution: CountDownLatch and CyclicBarrier are two of the five Java synchronizers next to Exchanger, Semaphore, and Phaser.
The main difference between CountDownLatch and CyclicBarrier is the fact that a CountDownLatch instance cannot be reused once the countdown reaches zero. On the other hand, a CyclicBarrier instance is reusable. A CyclicBarrier instance is cyclical because it can be reset and reused. To do this, call the reset() method after all of the threads waiting at the barrier are released; otherwise, BrokenBarrierException will be thrown.
Coding challenge 12 – wait() versus sleep()
Problem: Explain the main differences between the wait() method and the sleep() method.
Solution: The main difference between the wait() method and the sleep() method is that wait() must be called from a synchronized context (for example, from a synchronized method), while the sleep() method doesn't need a synchronized context. Calling wait() from a non-synchronized context will throw an IllegalMonitorStateException.
Additionally, it is important to mention that wait() works on Object, while sleep() works on the current thread. Essentially, wait() is a non-static method defined in java.lang.Object, while sleep() is a static method defined in java.lang.Thread.
Moreover, the wait() method releases the lock, while the sleep() method doesn't release the lock. The sleep() method only pauses the current thread for a certain period of time. Both of them throw IntrupptedException and can be interrupted.
Finally, the wait() method should be called in a loop that decides when the lock should be released. On the other hand, it is not recommended that you call the sleep() method in a loop.
Coding challenge 13 – ConcurrentHashMap versus Hashtable
Problem: Why is ConcurrentHashMap faster than Hashtable?
Solution: ConcurrentHashMap is faster than Hashtable because of its special internal design. ConcurrentHashMap internally divides a map into segments (or buckets), and it locks only a particular segment during an update operation. On the other hand, Hashtable locks the whole map during an update operation. So, Hashtable uses a single lock for the whole data, while ConcurrentHashMap uses multiple locks on different segments (buckets).
Moreover, reading from a ConcurrentHashMap using get() is lock-free (no locks), while all the Hashtable operations are simply synchronized.
Coding challenge 14 – ThreadLocal
Problem: What is Java ThreadLocal?
Solution: Java threads share the same memory. However, sometimes, we need to have dedicated memory for each thread. Java provides ThreadLocal as a means to store and retrieve values for each thread separately. A single instance of ThreadLocal can store and retrieve the values of multiple threads. If thread A stores the x value and thread B stores the y value in the same instance of ThreadLocal, then, later on, thread A retrieves the x value, and thread B retrieves the y value. Java ThreadLocal is typically used in the following two scenarios:
Coding challenge 15 – submit() versus execute()
Problem: Explain the main differences between the ExecutorService#submit() and Executor#execute() methods.
Solution: While both of these methods are used to submit a Runnable task for execution, they are not the same. The main difference can be observed by simply checking their signatures. Notice that submit() returns a result (that is, a Future object representing the task), while execute() returns void. The returned Future object can be used to programmatically cancel the running thread later on (prematurely). Moreover, by using the Future#get() method, we can wait for the task to complete. If we submit a Callable, then the Future#get() method will return the result of calling the Callable#call() method.
Coding challenge 16 – interrupted() and isInterrupted()
Problem: Explain the main differences between the interrupted() and isInterrupted() methods.
Solution: The Java multithreading interrupt technique uses an internal flag known as the interrupt status. The Thread.interrupt() method interrupts the current thread and sets this flag to true.
The main difference between the interrupted() and isInterrupted() methods is the fact that the interrupted() method clears the interrupt status while isInterrupted() doesn't.
If the thread was interrupted, then Thread.interrupted() will return true. However, besides testing, if the current thread was interrupted, Thread.interrupted() clears the interrupted status of the thread (that is, sets it to false).
The non-static isInterrupted() method doesn't change the interrupt status flag.
As a rule of thumb, after catching InterruptedException, don't forget to restore the interrupt by calling Thread.currentThread().interrupt(). This way, the caller of our code will be aware of the interruption.
Coding challenge 17 – Canceling a thread
Problem: How can we stop or cancel a thread?
Solution: Java doesn't provide a preemptive way of stopping a thread. Therefore, to cancel a task, a common practice is to rely on a loop that uses a flag condition. The task's responsibility is to check this flag periodically, and when it finds the flag set, then it should stop as quickly as possible. Notice that this flag is commonly declared as volatile (also known as the lightweight synchronization mechanism). Being a volatile flag, it is not cached by threads, and operations on it are not reordered in memory; therefore, a thread cannot see an old value. Any thread that reads a volatile field will see the most recently written value. This is exactly what we need in order to communicate the cancellation action to all running threads that are interested in this action. The following diagram illustrates this:
16.3 – Volatile flag read/write
Notice that the volatile variables are not a good fit for read-modify-write scenarios. For such scenarios, we will rely on atomic variables (for example, AtomicBoolean, AtomicInteger, and AtomicReference).
In the code bundle for this book, you can find an example of canceling a thread. The application is named CancelThread.
Coding challenge 18 – sharing data between threads
Problem: How can we share data between two threads?
Solution: Sharing data between two (or more) threads can be done via thread-safe shared objects or data structures. Java comes with a built-in set of thread-safe data structures such as BlockingQueue, LinkedBlockingQueue, and ConcurrentLinkedDeque. It is very convenient to rely on these data structures to share data between threads because you don't have to bother about thread safety and inter-thread communication.
Coding challenge 19 – ReadWriteLock
Problem: Explain what ReadWriteLock is in Java.
Solution: The main purpose of ReadWriteLock is to sustain the efficiency and thread safety of reading and writing operations in a concurrent environment. It accomplishes this goal via the lock striping concept. In other words, ReadWriteLock uses separate locks for reads and writes. More precisely, ReadWriteLock keeps a pair of locks: one for read-only operations and one for writing operations. As long as there are no writer threads, multiple reader threads can hold the read lock simultaneously (shared pessimistic lock). A single writer can write at a time (exclusive/pessimistic locking). So, ReadWriteLock can significantly improve the performance of the application.
Besides ReadWriteLock, Java comes with ReentrantReadWriteLock and StampedLock. The ReentrantReadWriteLock class adds the reentrant locking concept (refer to Coding challenge 4) to ReadWriteLock. On the other hand, StampedLock performs better than ReentrantReadWriteLock and supports optimistic reads. But it is not reentrant; therefore, it is prone to deadlocks.
Coding challenge 20 – Producer-Consumer
Problem: Provide an implementation for the famous Producer-Consumer problem.
Note
This is a favorite problem during any Java multithreading interview!
Solution: The Producer-Consumer problem is a design pattern that can be represented as follows:
16.4 – Producer-Consumer design pattern
Most commonly, in this pattern, the producer thread and the consumer thread communicate via a queue (the producer enqueues data and the consumer dequeues data) and a set of rules specific to the modeled business. This queue is known as the data buffer. Of course, depending on the process design, other data structures can play the role of data buffer as well.
Now, let's assume the following scenario (set of rules):
- If the data buffer is empty, then the producer produces one product (by adding it to the data buffer).
- If the data buffer is not empty, then the consumer consumes one product (by removing it from the data buffer).
- As long as the data buffer is not empty, the producer waits.
- As long as the data buffer is empty, the consumer waits.
Next, let's solve this scenario via two common approaches. We will start with a solution that is based on the wait() and notify() methods.
Producer-Consumer via wait() and notify()
Some interviewers may ask you to implement a Producer-Consumer application using the wait() and notify() methods. In other words, they don't allow you to use a built-in thread-safe queue such as BlockingQueue.
For example, let's consider that the data buffer (queue) is represented by a LinkedList, that is, a non-thread-safe data structure. To ensure that this shared LinkedList is accessible in a thread-safe manner by the producer and the consumer, we rely on the synchronized keyword.
The producer
If the queue is not empty, then the producer waits until the consumer finishes. To do this, the producer relies on the wait() method, as follows:
synchronized (queue) {
while (!queue.isEmpty()) {
logger.info("Queue is not empty ...");
queue.wait();
}
}
On the other hand, if the queue is empty, then the producer enqueues one product and notifies the consumer thread via notify(), as follows:
synchronized (queue) {
String product = "product-" + rnd.nextInt(1000);
// simulate the production time
Thread.sleep(rnd.nextInt(MAX_PROD_TIME_MS));
queue.add(product);
logger.info(() -> "Produced: " + product);
queue.notify();
}
After adding a product to the queue, the consumer should be ready to consume it.
The consumer
If the queue is empty, then the consumer waits until the producer finishes. For this, the producer relies on the wait() method, as follows:
synchronized (queue) {
while (queue.isEmpty()) {
logger.info("Queue is empty ...");
queue.wait();
}
}
On the other hand, if the queue is not empty, then the consumer dequeues one product and notifies the producer thread via notify(), as follows:
synchronized (queue) {
String product = queue.remove(0);
if (product != null) {
// simulate consuming time
Thread.sleep(rnd.nextInt(MAX_CONS_TIME_MS));
logger.info(() -> "Consumed: " + product);
queue.notify();
}
}
The complete code is available in the bundled code, ProducerConsumerWaitNotify.
Producer-Consumer via built-in blocking queues
If you can use a built-in blocking queue, then you can choose a BlockingQueue or even a TransferQueue. Both of them are thread-safe. In the following code, we use a TransferQueue or, more precisely, a LinkedTransferQueue.
The producer
The producer waits for the consumer to be available via hasWaitingConsumer():
while (queue.hasWaitingConsumer()) {
String product = "product-" + rnd.nextInt(1000);
// simulate the production time
Thread.sleep(rnd.nextInt(MAX_PROD_TIME_MS));
queue.add(product);
logger.info(() -> "Produced: " + product);
}
After adding a product to the queue, the consumer should be ready to consume it.
The consumer
The consumer uses the poll() method with a timeout to extract the product:
// MAX_PROD_TIME_MS * 2, just give enough time to the producer
String product = queue.poll(
MAX_PROD_TIME_MS * 2, TimeUnit.MILLISECONDS);
if (product != null) {
// simulate consuming time
Thread.sleep(rnd.nextInt(MAX_CONS_TIME_MS));
logger.info(() -> "Consumed: " + product);
}
The complete code is available in the bundled code, ProducerConsumerQueue
Summary
In this chapter, we covered the most popular questions that occur in Java multithreading interviews. Nevertheless, Java concurrency is a vast topic, and it is very important to deep dive into it. I strongly suggest that you read Java Concurrency in Practice by Brian Goetz. This is a must-read for any Java developer.
In the next chapter, we will cover a hot topic: Java functional-style programming.