A deadlock occurs when concurrent computations wait indefinitely for one another to release resources or make progress. In functional parallelism, a common cause is submitting a computation from a worker that blocks while waiting for another computation, leaving no worker available to run it. section 7.3.3
A single-thread pool
Create a fixed thread pool with one thread and compare a computation with its forked version. The outer computation occupies the only worker, submits an inner computation, and blocks on its result. Because the inner computation cannot start, both computations wait indefinitely. The same pattern generalizes: a fixed-size pool can deadlock when nested fork operations outnumber available threads. section 7.3.3 section 7.9
val a = lazyUnit(42 + 1) val es = Executors.newFixedThreadPool(1) println(Par.equal(es)(a, fork(a)))
Use the listing to inspect the minimal failure: a one-thread executor evaluates a computation alongside its forked form, exposing the difference between logical parallelism and available worker capacity. section 7.3.3
Preventing or reasoning about deadlock requires:
- Checking the laws of parallel combinators, because an unsound fork implementation can make reusable operations such as parMap dangerous. section 7.3.3
- Tracking blocking dependencies: every occupied worker may wait for another computation that is queued behind it. section 7.3.3 section 7.9
