ForkJoinPool and RecursiveTask lead to deadlock when join is called in a different thread than fork

Cause of the deadlock

The problem was caused because I didn't understand how RecursiveTask.join works.

Here is simpler example:

1. There is Thread 1 in ForkJoinPool thread pool
2. Thread 1 executes Task 1
3. Task 1 calls join on Task 2
4. Task 1 is blocked now, so Thread 1 must find another task
5. Thread 1 executes Task 3 (unrelated task)
6. Task 3 calls join on Task 4
7. Task 3 is blocked now, so Thread 1 must fund another task
8. Task 2 was completed in another thread, so Task 1 is unblocked now

Now in theory Thread 1 can proceed with Task 1, but it's not true! When RecursiveTask.join is called, the new available task is called in the same thread without clearing stacktrace (in Debugger you can see that that stacktrace is growing).

Stacktrace of Thread 1 is looking like that (from top to bottom):

task1.compute()
task2.join()
task3.compute()
task4.join()

Thread 1 cannot go back to Task 1. Thread 1 must wait until task4.join() is completed, and then wait until task3.compute() is completed. After that stacktrace looks like that:

task1.compute()
task2.join()

task2.join() is completed and task1.compute() can be proceeded.

Deadlock in my code

Here is the overview of stacktraces (from top to bottom) on both threads from my example program:

Even if value FibonacciTask(4) was already calculated on Thread 36, Thread 35 cannot proceed with calculation, because Thread 35 still needs to complete methods lower in the stacktrace. But Thread 35 cannot complete methods from the bottom of stacktrace, because Thread 35 is still waiting on Thread 36. And Thread 36 cannot complete its work, because it's waiting until method from middle of Thread 35 stacktrace is completed. Deadlock!

Solution using Virtual threads

This problem can be solved using virtual threads. Virtual threads (unlike ForkJoinPool) clear the stacktrace and load a new stacktrace during task switching (virtual threads are using ContinuationScope under the hood).

Here is my program rewritten using virtual threads:

void main() throws ExecutionException, InterruptedException {
    try (Fibonacci fibonacci = new Fibonacci()) {
        IO.println(fibonacci.calculate(9));
    }
}
public static class Fibonacci implements AutoCloseable {
    private final ConcurrentHashMap cache;
    private final ExecutorService pool;
    public Fibonacci() {
        cache = new ConcurrentHashMap();
        pool = Executors.newVirtualThreadPerTaskExecutor();
    }
    public long calculate(int n) throws ExecutionException, InterruptedException {
        return pool.submit(() -> new FibonacciTask(n).compute()).get();
    }
    private class FibonacciTask {
        private final int n;
        private volatile Future future;
        private FibonacciTask(int n) {
            this.n = n;
        }
        protected Long compute() throws ExecutionException, InterruptedException {
            IO.println("[%d] Start".formatted(n));
            if (n < 3) {
                IO.println("[%d] End".formatted(n));
                return 1L;
            }
            FibonacciTask previousValue = cache.putIfAbsent(n, this);
            if (previousValue != null) {
                IO.println("[%d] Wait".formatted(n));
                while (previousValue.future == null) {
                    Thread.onSpinWait();
                }
                long cachedValue = previousValue.future.get();
                IO.println("[%d] Got value".formatted(n));
                return cachedValue;
            }
            future = pool.submit(() -> {
                FibonacciTask a = new FibonacciTask(n - 2);
                FibonacciTask b = new FibonacciTask(n - 1);
                return a.compute() + b.compute();
            });
            IO.println("[%d] End".formatted(n));
            return future.get();
        }
    }
    @Override
    public void close() {
        if (pool != null) {
            pool.close();
        }
    }
}

Comparison of ForkJoinPool and Virtual threads

Virtual threads and ForkJoinPool are very similar:

1. Both ForkJoinPool and virtual threads create an unlimited number of tasks executed by a limited number of platform threads. ForkJoinPool creates an unlimited number of tasks (RecursiveTask) executed on a limited number of platform threads (in this case, two). Similarly, the solution based on virtual threads also creates an unlimited number of tasks (virtual threads) executed on a limited number of platform threads (the number of threads depends on the JVM configuration, but it is finite).

2. Both ForkJoinPool and virtual threads rely on the work-stealing algorithm (virtual threads are implemented underneath based on ForkJoinPool).

3. Both ForkJoinPool and virtual threads juggle a very large (unlimited) number of tasks while having only a finite number of platform threads at their disposal.

4. Both ForkJoinPool and virtual threads can switch to another task if the current task is blocked.

And now the most important question: Since both ForkJoinPool and virtual threads can handle an unlimited number of tasks on a limited number of platform threads, and both can interrupt work on a blocked task to start work on another task, why does the ForkJoinPool-based solution run into a deadlock, while the virtual thread-based solution does not?

Answer: A platform thread working on a virtual thread is always able (unless it is "pinned") to switch to another virtual thread because virtual threads can copy their stack aside and then restore it. In contrast, ForkJoinPool cannot switch to another task if it would require stepping back in the stack trace.

In other words: Virtual Threads = ForkJoinPool + ContinuationScope. Virtual threads are implemented underneath using ForkJoinPool and ContinuationScope. It is precisely this ContinuationScope (which allows you to save and restore the stack) that prevents the virtual thread-based solution from leading to a deadlock.