Thread Synchronization and the volatile Keyword
A recursive thread may be many calls deep when a stop request arrives, so the request must be carried back up through every waiting call.
A Sort That Can Be Stopped
Imagine a program that sorts a list of colors into rainbow order while you watch. The sorting runs slowly enough that you can follow each swap, and a button labeled Start begins the process. Partway through, the button changes its label to Finish, giving you a way to stop the sort before it completes on its own. This sounds like a small user-interface detail, but it raises a real design question: what does it take to stop a thread that is in the middle of a recursive algorithm?
The sorting example comes from a demonstration program, QuicksortThreadDemo.java, that animates the recursive QuickSort algorithm. Its colors are shuffled at the start and then gradually arranged from red through violet. The goal of this section is to follow the logic of the Finish button from the moment it is clicked to the moment the thread has fully ended, because that path reveals a general technique for stopping recursive work.
Why a Flag Alone Cannot Stop the Work
A recursive algorithm solves a problem by calling itself on smaller pieces of the problem. Each call waits for its smaller calls to finish before it can complete. At any moment during the sort, the thread is therefore inside a stack of unfinished method calls, and the depth of that stack depends on how far the recursion has gone. A click on the Finish button might arrive when the sort is only one call deep, or when it is many levels down.
This is what makes stopping hard. A thread cannot simply vanish from the middle of a recursive chain, because the methods still on the stack hold their own pending work. Nothing in the chain knows about the button, so the stop request has to be noticed at some point and then carried all the way back up to the start of the thread. The diagram below shows a hypothetical stack of recursive calls for a deep sort. The labels are illustrative names rather than the names used in the demonstration program.
What do you think happens?
If the Finish click arrives while the sort is four calls deep, does the flag stop the thread at the moment of the click?
Reveal answer
No, the request is noticed only at the next check and must then travel back up the stack
Setting the flag is passive. It records a request but does not interrupt any method in the middle of its work. The thread reads the flag the next time it checks, and the stop request then has to be carried up through every waiting call to the thread's outermost code.
The Volatile Flag as a Passive Signal
The first piece of the solution is a shared signal. Clicking Finish sets a boolean variable named running to false. The variable is declared volatile, a Java keyword that tells the runtime the value may be changed by another thread and that every read should see the latest value rather than a possibly stale copy. Without that guarantee, the animation thread could keep running on a cached value and never notice that the button was clicked.
A volatile boolean flag, such as running, is a shared variable declared with the volatile keyword. One thread writes to it, another thread reads it, and the volatile declaration ensures that reads see the latest written value rather than a possibly stale copy.
The flag is deliberately passive. Setting running to false does not interrupt any method in the middle of its work. It simply leaves a message that the thread can read the next time it checks. Some part of the program has to perform that check regularly, and the demonstration places the check inside a delay method that the sorting animation calls between steps.
The Check Inside the Delay Method
The check inside the delay method looks at running. If the value is still true, the method returns normally and the sort continues. If the value is false, the method throws a custom exception. The demonstration program defines this exception class for the purpose and names it ThreadTerminationException.
Throwing an exception is a useful way to leave a deep recursion because an exception does not return normally from one method. Instead, it travels upward, leaving each method that is waiting on a call. A normal return would have to pass through each waiting frame one at a time, and a stop request would have to be written into every level's return path. The exception carries the stop request through every layer at once, without any of those layers needing to know about the button.
The flag only records the request. The check turns that record into an action, and the custom exception is the mechanism that carries the action through the whole recursive chain.
Tracing the Unwinding Through the Stack
Each recursive call on the stack is exited in turn, from the deepest frame back toward the first. Once the exception reaches the code that started the thread's work, the animation thread can end. The flowchart below follows the same path for a click that arrives while the sort is four calls deep.
A Finish click during a four-level sort
The sort is four calls deep when the Finish button sets running to false. Trace what happens to the thread from the next check onward. The depths are illustrative.
- 1Set the flag
The button handler writes false to the volatile running variable. No method on the stack is interrupted, so all four calls keep their pending work.
- 2Reach the next check
The deepest call,
quickSortdepth 4, calls the delay method between animation steps. The delay method reads running and sees false. - 3Throw instead of returning
Because the value is false,
delay()throwsThreadTerminationExceptionrather than returning normally. The sort does not take its next step. - 4Unwind the frames
The exception leaves
quickSortdepth 4, then depth 3, then depth 2, then depth 1. Each frame that was waiting on a smaller call is discarded in turn. - 5Stop at the outermost code
The exception reaches the code that started the thread's work. Nothing further runs in the sort, and the animation thread can end.
The stop request, recorded as a single false value, ends a four-level recursion through one exception that passes through every waiting call.
Mistakes When Stopping a Deep Thread
The design above depends on the exception travelling all the way to the outermost code. Several natural-looking changes break that path, and each one leaves the thread running or leaves the stop request stranded at the wrong level.
Common mistake Checking the flag only at the top level
What it looks likeThe check is placed in startSort(), so the top call looks at running once and then the recursion runs without any further checks.
Why it failsA top-level check cannot see the call that is currently deep in the recursion. The request is only noticed when control returns to the top, which may be far too late.
Do this insteadPlace the check where the work repeats, such as inside the delay method the sort calls between steps, so the request is noticed at the depth where the thread actually is.
Common mistake Catching the exception inside the recursion
What it looks likeA try block inside quickSort catches ThreadTerminationException and simply returns from that one call.
Why it failsThe exception stops at that level, so the calls above it keep running as if nothing happened. The stop request never reaches the thread's exit.
Do this insteadLeave the exception uncaught inside the recursion so it can travel up to the thread's outermost code.
Common mistake Assuming setting the flag stops the thread immediately
Why it failsSetting running to false is passive. It does not interrupt a method in the middle of its work, so the thread continues until its next check.
Common mistake Declaring the flag without volatile
Why it failsWithout the volatile guarantee, the worker may keep reading a stale copy of the value and never notice that the button was clicked.
| Design choice | Where the stop request is noticed | What happens to the recursion |
|---|---|---|
| Volatile flag checked in delay(), exception left uncaught | At the deepest call's next check | Every waiting call is discarded in turn and the thread ends |
| Flag checked only in startSort() | Only when control returns to the top level | The deep recursion keeps running until it finishes on its own |
| Exception caught inside quickSort | At the deepest call, then caught there | Only that call exits; the calls above it continue |
Comparing a correct propagation design with two faulty alternatives
Practicing the Stop Request Trace
A Finish click arrives while the sort is only one call deep. Describe which frames are discarded, in what order, and where the thread ends. Then explain whether the answer would change if the same click arrived while the sort was six calls deep.
Hints
- Start from the frame that is currently running and work toward the top-level call.
- The depth changes how many frames are discarded, not the order or the place where the thread ends.
- Ask what would happen if the exception were caught inside one of the recursive calls.
Key Takeaways
- A recursive thread may be many calls deep when a stop request arrives, so the request must be carried back up through every waiting call.
- Setting a volatile boolean flag such as running records a stop request but does not interrupt work by itself; the volatile keyword ensures the worker sees the latest value.
- A regular check that throws a custom exception such as
ThreadTerminationExceptionunwinds the recursion from the deepest frame back toward the start of the thread and ends it. - The exception should be left uncaught inside the recursion; catching it at a deeper level, or checking only at the top level, prevents the stop request from reaching the thread's exit.