Sitemap
CodeX

Everything connected with Tech & Code. Follow to join our 1M+ monthly readers

Understanding Java Concurrency: The Theory Behind Threads, Race Conditions, Monitors, and Deadlock

From Dijkstra’s mutual exclusion to Hoare’s monitors and Coffman’s four deadlock conditions — the ideas behind today’s Java code

13 min read8 hours ago

--

Press enter or click to view image in full size
Blue wireframe blueprint showing four threads converging on a shared cube, with two interlocked padlocks beside it.
Four threads, one shared value, and decades of research behind why it goes wrong.
class Print1To10 implements Runnable {
public int sum = 0;

public void run() {
for (int i = 1; i <= 10; i++) {
System.out.println("Thread Name: " + Thread.currentThread().getName() + ", task value: " + i);
sum += i;
}
}
}

class PrintEven implements Runnable {
public void run() {
for (int i = 2; i <= 20; i += 2) {
System.out.println("Thread Name: " + Thread.currentThread().getName() + ", task value: " + i);
}
}
}

class PrintOdd implements Runnable {
public void run() {
for (int i = 1; i < 20; i += 2) {
System.out.println("Thread Name: " + Thread.currentThread().getName() + ", task value: " + i);
}
}
}

class IncrementCounter {
protected int counter = 0;
public int incrementCount = 100000;

public int getCounterValue() {
return counter;
}
}

class IncrementCounterUnsynchronized extends IncrementCounter implements Runnable{
public void run() {
for (int i = 0; i < incrementCount; i++) {
counter++;
}
}
}

class IncrementCounterSynchronized extends IncrementCounter implements Runnable {
private final Object lockCounter = new Object();

public void run() {
for (int i = 0; i < incrementCount; i++) {
synchronized (lockCounter) {
counter++;
}
}
}
}

public class java_15ThreadsRaces {
public static void main(String[] args) {
Print1To10 print1To10 = new Print1To10();

Thread print1To10Task = new Thread(print1To10);
Thread printEvenTask = new Thread(new PrintEven());
Thread printOddTask = new Thread(new PrintOdd());

Thread print5Multiple = new Thread(() -> {
for (int i = 5; i <= 50; i += 5) {
System.out.println("Thread Name: " + Thread.currentThread().getName() + ", task value: " + i);
}
});

print1To10Task.start();
printEvenTask.start();
printOddTask.start();
print5Multiple.start();

try {
print1To10Task.join();
printEvenTask.join();
printOddTask.join();
print5Multiple.join();
} catch (InterruptedException e) {
System.out.println("Exception Occurred: " + e);
}

boolean print1To10TaskCompleted = print1To10Task.isAlive();
boolean printEvenTaskCompleted = printEvenTask.isAlive();
boolean printOddTaskCompleted = printOddTask.isAlive();
boolean print5MultipleCompleted = print5Multiple.isAlive();

System.out.println(
!print1To10TaskCompleted &&
!printEvenTaskCompleted &&
!printOddTaskCompleted &&
!print5MultipleCompleted ? "All tasks complete. Result of Print1To10Numbers: " + print1To10.sum : "Tasks still pending"
);

System.out.println();
System.out.println("unsynchronized [5+ runs, showing some incorrect] Unsynchronized Run + ==================== +");
for (int i = 0; i < 5; i++) {
IncrementCounterUnsynchronized unsynchronizedIncrement = new IncrementCounterUnsynchronized();
int incrementCountUnsynchronized = unsynchronizedIncrement.incrementCount;

Thread unsyncThread1 = new Thread(unsynchronizedIncrement);
Thread unsyncThread2 = new Thread(unsynchronizedIncrement);
Thread unsyncThread3 = new Thread(unsynchronizedIncrement);
Thread unsyncThread4 = new Thread(unsynchronizedIncrement);

unsyncThread1.start();
unsyncThread2.start();
unsyncThread3.start();
unsyncThread4.start();

try {
unsyncThread1.join();
unsyncThread2.join();
unsyncThread3.join();
unsyncThread4.join();
} catch (InterruptedException e) {
System.out.println("Exception Occurred: " + e);
}

System.out.println("Counter Value Expected (4 threads times " + incrementCountUnsynchronized + "): " + 4 * incrementCountUnsynchronized);
System.out.println("Counter Value Actual (Run " + (i+1) + "): " + unsynchronizedIncrement.getCounterValue());
}
System.out.println(" + ==================== + Unsynchronized Run ");

// This works because synchronized locks another thread to interrupt 3 step process of increment
// ReentrantLock was not used due to not requiring much of the methods available by it and synchronized can handle this task efficiently
System.out.println("\nfixed [5+ runs, all exactly correct] Synchronized Run + ==================== +");
for (int i = 0; i < 5; i++) {
IncrementCounterSynchronized synchronizedIncrement = new IncrementCounterSynchronized();
int incrementCountSynchronized = synchronizedIncrement.incrementCount;

Thread syncThread1 = new Thread(synchronizedIncrement);
Thread syncThread2 = new Thread(synchronizedIncrement);
Thread syncThread3 = new Thread(synchronizedIncrement);
Thread syncThread4 = new Thread(synchronizedIncrement);

syncThread1.start();
syncThread2.start();
syncThread3.start();
syncThread4.start();

try {
syncThread1.join();
syncThread2.join();
syncThread3.join();
syncThread4.join();
} catch (InterruptedException e) {
System.out.println("Exception Occurred: " + e);
}

System.out.println("Counter Value Expected (4 threads times " + incrementCountSynchronized + "): " + 4 * incrementCountSynchronized);
System.out.println("Counter Value Actual (Run " + (i+1) + "): " + synchronizedIncrement.getCounterValue());
}
System.out.println(" + ==================== + Synchronized Run ");

final Object lockA = new Object();
final Object lockB = new Object();

System.out.println();
System.out.println("=== 1. DEMONSTRATING DEADLOCK ===");
Thread deadlockIncorrectA = new Thread(() -> {
try {
synchronized (lockA) {
System.out.println(Thread.currentThread().getName() + " acquired Lock A");
Thread.sleep(50);

synchronized (lockB) {
System.out.println(Thread.currentThread().getName() + " acquired Lock B");
}
}
} catch (InterruptedException e) {
System.out.println("Exception Occured: " + e);
}
});

Thread deadlockIncorrectB = new Thread(() -> {
try {
synchronized (lockB) {
System.out.println(Thread.currentThread().getName() + " acquired Lock B");
Thread.sleep(50);

synchronized (lockA) {
System.out.println(Thread.currentThread().getName() + " acquired Lock A");
}
}
} catch (InterruptedException e) {
System.out.println("Exception Occured: " + e);
}
});

deadlockIncorrectA.setDaemon(true);
deadlockIncorrectB.setDaemon(true);

deadlockIncorrectA.start();
deadlockIncorrectB.start();

try {
deadlockIncorrectA.join(2000);
deadlockIncorrectB.join(2000);
} catch (InterruptedException e) {
System.out.println("Exception Occured: " + e);
}

boolean thread1Alive = deadlockIncorrectA.isAlive();
boolean thread2Alive = deadlockIncorrectB.isAlive();

System.out.println("Timeout expired. Thread 1 alive? " + thread1Alive);
System.out.println("Timeout expired. Thread 2 alive? " + thread2Alive);
System.out.println(thread1Alive && thread2Alive ? "-> Result: Deadlock successfully occurred!\n" : "-> Result: Threads finished.\n");

final Object lockC = new Object();
final Object lockD = new Object();
// NOTE: not using locks A and B as they are deadlocked until main is completed,
// Therefore using the same locks will show the same output and not provide a solution to deadlock

System.out.println("=== 2. FIXING THE DEADLOCK (Consistent Order) ===");
Thread deadlockCorrectA = new Thread(() -> {
try {
synchronized (lockC) {
System.out.println(Thread.currentThread().getName() + " acquired Lock C");
Thread.sleep(50);

synchronized (lockD) {
System.out.println(Thread.currentThread().getName() + " acquired Lock D");
}
}
} catch (InterruptedException e) {
System.out.println("Exception Occured: " + e);
}
});

Thread deadlockCorrectB = new Thread(() -> {
try {
synchronized (lockC) {
System.out.println(Thread.currentThread().getName() + " acquired Lock C");
Thread.sleep(50);

synchronized (lockD) {
System.out.println(Thread.currentThread().getName() + " acquired Lock D");
}
}
} catch (InterruptedException e) {
System.out.println("Exception Occured: " + e);
}
});

long startTime = System.currentTimeMillis();

deadlockCorrectA.start();
deadlockCorrectB.start();

try {
deadlockCorrectA.join(2000);
deadlockCorrectB.join(2000);
} catch (InterruptedException e) {
System.out.println("Exception Occured: " + e);
}

long elapsedTime = System.currentTimeMillis() - startTime;
boolean fixedThread1Alive = deadlockCorrectA.isAlive();
boolean fixedThread2Alive = deadlockCorrectB.isAlive();

System.out.println("Elapsed time: " + elapsedTime + " ms");
System.out.println("Timeout expired. Thread 1 alive? " + fixedThread1Alive);
System.out.println("Timeout expired. Thread 2 alive? " + fixedThread2Alive);
System.out.println(fixedThread1Alive && fixedThread2Alive ? "-> Result: Deadlock successfully occurred!\n" : "-> Result: Threads finished.\n");
}
}

Today’s program is short, but nearly every line in it answers a question that computer scientists were asking before most programmers alive today were born. Why can two correct pieces of code produce a wrong answer together? What does it mean to take turns safely? What exactly has to be true for two threads to freeze each other?

This article is the theory companion to the practical walkthrough of today’s code. Last lesson, we looked at the theory behind lazy evaluation, folds, and Optional, and the Streams guide showed it in code. Streams were about values flowing through a pipeline. Today is about what happens when several flows touch the same value at the same time.

Sequential Processes and the Problem of Interleaving

Why the output of four threads has no fixed order

In the 1960s, Edsger W. Dijkstra’s essay “Cooperating Sequential Processes” (EWD123, 1965) framed concurrent programs as a set of ordinary sequential processes that occasionally need to coordinate. A key idea was that the relative speeds of those processes are unknown and arbitrary. A correct program may not depend on one process being faster than another.

That idea is what the first block of our program demonstrates:

print1To10Task.start();
printEvenTask.start();
printOddTask.start();
print5Multiple.start();

Each Thread is a sequential process. Within Thread-1, 2 is always printed before 4. Across threads, the JVM scheduler and the operating system decide who runs when, so the lines may appear grouped or mixed, and either is a valid outcome. Programs that only work because one thread happened to be quicker are exactly what Dijkstra's principle rules out.

The same line of thinking explains why join() exists. It is the point where one process waits for another to finish, so main can safely read print1To10.sum afterwards.

Critical Sections and Mutual Exclusion

The problem that gave counter++ its danger

In 1965, Dijkstra published “Solution of a Problem in Concurrent Programming Control” in Communications of the ACM (volume 8, issue 9). The problem it stated is one that still defines the field: several processes, each with a stretch of code that must never run in two places at once. That stretch is called a critical section, and keeping processes out of each other’s critical sections is called mutual exclusion. Dijkstra’s paper gave a solution using only ordinary reads and writes of shared variables.

In our code, the critical section is one line:

for (int i = 0; i < incrementCount; i++) {
counter++;
}

The line looks tiny, but it contains three separate actions: read counter, add one, write the result back. If two threads are between "read" and "write" at the same moment, each overwrites the other's work. In the language of the theory, the critical section was not protected, so the final total is no longer the sum of the work done.

Races, Atomicity, and the Java Memory Model

Why 400,000 became 135,072

One recorded run of the unsynchronized version produced this:

Counter Value Expected (4 threads times 100000): 400000
Counter Value Actual (Run 1): 135072

Brian Goetz and co-authors, in Java Concurrency in Practice (Addison-Wesley, 2006), call this pattern a read-modify-write sequence and explain that it is a race condition: the result depends on the unlucky timing of threads. The fix needs the three steps to be atomic, meaning indivisible from the viewpoint of every other thread.

There is a second, deeper problem hiding in this code. Chapter 17 of the Java Language Specification defines what a thread is guaranteed to see when another thread writes a value. It does this through a relation called happens-before, a term borrowed from Leslie Lamport’s 1978 paper “Time, Clocks, and the Ordering of Events in a Distributed System” in Communications of the ACM. The Java Memory Model itself is described by Jeremy Manson, William Pugh, and Sarita Adve in “The Java Memory Model” (POPL 2005). When two threads access the same variable, at least one access is a write, and nothing orders the accesses by happens-before, the specification calls it a data race. Our unprotected counter is exactly that. It is not only that the arithmetic can be lost, but that one thread is not even promised to see another's latest write.

Some of that ordering is provided for free. The specification states that all actions in a thread happen-before another thread successfully returns from join() on it. That is why this works:

print1To10Task.join();
// ...
System.out.println("... " + print1To10.sum);

The thread wrote sum, and join() creates the ordering that makes that write visible to main.

Monitors: Turning a Rule into a Language Feature

What synchronized really is

C. A. R. Hoare’s “Monitors: An Operating System Structuring Concept” (Communications of the ACM, October 1974, pp. 549–557) proposed gathering shared data together with the only code allowed to touch it, and having the system guarantee that one process at a time is inside. Per Brinch Hansen was developing the same idea at the same time, and the two are usually credited together. The point was to stop relying on programmers remembering to guard every access by hand.

Java adopted the monitor idea. The Java Language Specification, in its chapter on threads and locks, describes synchronization as implemented using monitors, with one monitor associated with every object. Our fix uses exactly that:

private final Object lockCounter = new Object();

public void run() {
for (int i = 0; i < incrementCount; i++) {
synchronized (lockCounter) {
counter++;
}
}
}

Entering the block acquires the monitor of lockCounter, and leaving it releases the monitor, even if an exception is thrown. This is where Java differs from Hoare's original design: Hoare bound a monitor to a data structure, whereas Java lets any object serve as the lock, and the programmer chooses which one. That freedom is also a responsibility. Protection only exists if every thread contending for the data uses the same lock object, which is why all four threads in our run share a single IncrementCounterSynchronized instance.

The monitor also carries the memory guarantee from the previous section. In the specification’s happens-before rules, releasing a monitor happens-before every later acquisition of the same monitor. So the lock does two jobs at once: it provides mutual exclusion, and it makes each thread’s write visible to the next. That second job is why every one of our synchronized runs reports exactly 400,000.

Deadlock and the Four Coffman Conditions

Exactly what has to be true for two threads to freeze

In 1971, E. G. Coffman, M. J. Elphick, and A. Shoshani published “System Deadlocks” in ACM Computing Surveys (volume 3, issue 2, pages 67–78). They identified four conditions that must all hold at the same time for a deadlock to occur. Each of them can be pointed to in the deadlock demo:

  • Mutual exclusion: a lock can be held by only one thread. This is the synchronized block itself.
  • Hold and wait: a thread holds one resource while waiting for another. Thread A holds lockA while it asks for lockB, and the Thread.sleep(50) makes sure that both threads reach this state.
  • No preemption: a resource cannot be taken away from its holder. A Java monitor is released only when the holding thread leaves its block, and a thread stuck waiting to enter a synchronized block cannot be talked out of it by an interrupt.
  • Circular wait: there is a closed chain of threads, each waiting for a resource held by the next. A waits for B’s lock, and B waits for A’s.
// Thread A                          // Thread B
synchronized (lockA) { synchronized (lockB) {
Thread.sleep(50); Thread.sleep(50);
synchronized (lockB) { ... } synchronized (lockA) { ... }
} }

The theory also explains the shape of the classic puzzle. Dijkstra set the dining philosophers problem as an exam question in 1965, and Hoare later gave it the form we know today: five philosophers, five forks, and each philosopher needs two forks to eat. If every philosopher picks up the left fork first, all of them can end up holding one fork and waiting forever. It is our two-lock program with more threads. Dijkstra’s treatment appeared in “Hierarchical Ordering of Sequential Processes” (Acta Informatica, volume 1, issue 2, 1971, pp. 115–138).

Breaking the Cycle: Why Lock Ordering Works

Removing one condition is enough

Because a deadlock needs all four conditions, removing any one of them prevents it. We cannot give up mutual exclusion, because that would bring back the race. We cannot cheaply give up hold-and-wait or no-preemption with plain synchronized. The practical condition to attack is circular wait, and the standard way is resource ordering: give every lock a rank and require everyone to acquire locks in rank order.

// Both threads now take lockC first, then lockD
synchronized (lockC) {
Thread.sleep(50);
synchronized (lockD) { ... }
}

If every thread follows the same order, a cycle cannot form. A thread holding lockD can never be waiting for lockC, because no thread ever asks for lockC while already holding lockD. This ordering discipline is also the resource-hierarchy solution to the dining philosophers problem, and Java Concurrency in Practice devotes a chapter on liveness hazards to lock-ordering deadlocks.

Get Someone’s stories in your inbox

Join Medium for free to get updates from this writer.

There is a price. The two threads now run one after the other through the locked section, and the measured 102 ms is the two sleep(50) calls back to back. Prevention trades some concurrency for the guarantee that the system cannot freeze. For our program that is clearly worth it.

Proving a Deadlock Without Living Through It

Timeouts, daemon threads, and the limits of detection

The program has to prove a deadlock happened without hanging forever, and it does so in two ways:

deadlockIncorrectA.setDaemon(true);
deadlockIncorrectB.setDaemon(true);
// ...
deadlockIncorrectA.join(2000);
deadlockIncorrectB.join(2000);
System.out.println("Timeout expired. Thread 1 alive? " + deadlockIncorrectA.isAlive());

The Java Language Specification’s section on program exit says the JVM exits once every non-daemon thread has finished. By marking the stuck threads as daemons, main can finish and let the program end. The timed join and isAlive() are a practical detection method: if both threads are still alive after two seconds, they are blocked.

This is a timeout, not a proof. A slow thread and a deadlocked thread look identical from outside, which is why the theory prefers to detect the cycle itself. For monitor locks, the JVM can do this: a thread dump from jstack, or the ThreadMXBean API, can report that threads are deadlocked and name the locks involved.

Putting It Together

Each idea, its origin, and the line of code that carries it

Interleaving with unknown speeds comes from Dijkstra’s sequential-process model, and it shows up in the four start() calls. Critical sections and mutual exclusion come from Dijkstra's 1965 work, and they show up in counter++. Atomicity, data races, and happens-before come from the Java Language Specification and the Java Memory Model research, and they show up in the result 135072 and in the join() before sum is read. Monitors come from Hoare and Brinch Hansen, and they show up in synchronized (lockCounter). Deadlock and its four conditions come from Coffman, Elphick, and Shoshani, and they show up in lockA and lockB. Resource ordering comes from the dining philosophers literature, and it shows up in lockC and lockD.

The recurring theme of this series, behavior that is silently wrong, is at its sharpest here. A race condition raises no exception. A passing run proves nothing. The theory gives us a way to reason about correctness that does not depend on getting lucky.

Further Reading

Dijkstra, E. W. “Cooperating Sequential Processes” (EWD123), 1965.

Dijkstra, E. W. “Solution of a Problem in Concurrent Programming Control.” Communications of the ACM 8(9), 1965.

Dijkstra, E. W. “Hierarchical Ordering of Sequential Processes.” Acta Informatica 1(2), 1971, pp. 115–138.

Coffman, E. G., Elphick, M. J., and Shoshani, A. “System Deadlocks.” ACM Computing Surveys 3(2), 1971, pp. 67–78.

Hoare, C. A. R. “Monitors: An Operating System Structuring Concept.” Communications of the ACM, October 1974, pp. 549–557.

Lamport, L. “Time, Clocks, and the Ordering of Events in a Distributed System.” Communications of the ACM, 1978.

Manson, J., Pugh, W., and Adve, S. “The Java Memory Model.” POPL 2005.

Goetz, B. et al. Java Concurrency in Practice. Addison-Wesley, 2006.

The Java Language Specification, chapters 12 (program exit) and 17 (threads and locks).

The Arbiter Journey So Far

This is lesson 15 of the Arbiter Learning Journey, a Java-from-scratch series building toward Arbiter, a microservices-based test management platform. Every concept is written and tested by hand before the next one begins. A test platform runs many things at once, so the ideas in this article, safe shared state and lock discipline, will matter every time Arbiter’s services handle more than one request.

Arbiter YouTube Playlist

Arbiter on GitHub

Arbiter Lessons

Other series on this account

What’s Next

Our program created 48 Thread objects by hand. The next lesson hands that job to the JVM with ExecutorService and thread pools, followed by CompletableFuture for results that arrive later.

--

--

CodeX
CodeX

Published in CodeX

Everything connected with Tech & Code. Follow to join our 1M+ monthly readers