Deadlock in GCD

The term ‘structured concurrency’ did not originate with Swift or on iOS. (See this wikipedia article for some history.) But it has become prominent in Swift. Here and here. One reason that Swift has developed this ‘structured concurrency’ syntax is, I gather, to help eliminate programming errors that have to do with concurrency and which can be difficult to debug once they are buried in thousands of lines of code in a large codebase. One such problem is a particular case of deadlock. Typically, deadlock involves two concurrent tasks both of which might be waiting on the other to complete. (Perhaps like so, where there are at least two characters: the hungry duck and the restaurant manager.) But, in a philosophically trippy way, could you be deadlocked with your own self?! Indeed you could.

The problem, one that predates Swift’s structured concurrency, predates because it uses Grand Central Dispatch (GCD), and exactly the type of problem that structured concurrency has been designed to help eliminate:

import Foundation

let q = DispatchQueue(label: "a serial dispatch queue")

q.sync {
    q.sync {}
}

Two things are true of the Swift code above. The first is that it illustrates a deadlock. The second is that, if you try to run it, it crashes. But how could both of these things be true? After all, if you deadlock, shouldn’t you hang? And yet we don’t hang, we crash. That’s the first small puzzle.

Unless there is some runtime cleverness I don’t know about (which is a possibility), I would expect that the code above does indeed hang. I assume that the system (or, to be more specific, its watchdog process) then terminates the process because the process is unresponsive.

Let’s assume that is so. The second small puzzle is then understanding why the code above would hang in the first place. Consider an analogy: you wake up in the morning but refuse to get out of bed until someone brings you breakfast. That might be fine and you might indeed get out of bed unless either there is no one to bring you breakfast or, worse still, that someone is you. If that someone is you, then the situation becomes: you wake up in the morning but refuse to get out of bed until you bring yourself breakfast. To bring breakfast, you would first need to get out of bed. But to get out of bed, you need to be brought breakfast. In other words, (a) for yourself to bring you breakfast, you would have to first get out of bed while (b) getting out of bed requires that very breakfast, the one to be brought to you by you. You will thus wait for yourself indefinitely.

another way to frame the problem

What would the following program print?

print("1")
q.sync {
    print("2")
    q.sync {
        print("3")
    }
    print("4")
}
print("5")

If you said, “1 followed by 2”, you are correct! You will never see “3”, “4”, or “5” because it is on the after print("2") that the program will hang.

A more technical explanation

The reason this deadlocks is because (i) we are using the same dispatch queue in both cases, (ii) it is a serial queue rather than a concurrent queue, and (iii) the call to the queue is sync rather than async. “Sync” is a synchronous call, which means that it is a blocking call. q.sync waits for the closure passed to it to complete—the closure inside which is the instruction to print “3”—and only once the closure has returned will the next call (which is to print “4”) be executed.

syntax

As a sidenote, to help demistify the code above, remember that the following:

dispatchQueue.sync {
    print("hello")
}

is equivalent to:

dispatchQueue.sync(execute: {
    print("hello")
})

See ‘trailing closures’ at swift.org.

The idiomatic dispatchqueue.main.async

The deadlock problem above is also why we don’t ever want to synchronously dispatch to the main thread. The problem is that if we happen to be on the main thread already, we will deadlock. Namely, it would then be equivalent to the above where q is DispatchQueue.main. For example, this is clearly the same as the problem at the top of this blog post because the main dispatch queue is also a serial queue (with the main thread dequeing instructions from it):

let q = DispatchQueue.main // main dispatch queue
q.sync {
    q.sync {}
}

Hence, even though they are quite urgent, the pattern of dispatching UI updates to the main thread asynchronously. It’s always DispatchQueue.main.async {…} instead of DispatchQueue.main.sync {…}, where … is some UI updates.

How to fix the deadlock?

Translating this familiar idiomatic usage back to our problem, we can conclude the following (just as we can conclude it by remember that async is not a blocking call). In our example with our private dispatch queue, the following code would run just fine, even if the order of execution would not be determinstic:

q.sync {
    q.async {}
}

By ‘deterministic’, I mean that, if we sprinkled in some print statements, it would sometimes print in one order, sometimes in another.

bigger picture

Is our example involving a serial dispatch queue the only way deadlock can arise? No, clearly not. In Computer Science, a classic example of deadlock is Dijkstra’s Dining Philosophers Problem, where all philosophers, sadly, starve. Much to our relief, however, Dijkstra did not intend his thought experiment involving philosophers to be a metaphor for philosophers. Rather, he meant philosophers to model computers or, more precisely, the dining philosophers to model computers competing for resources (where the resources happen to be tape drivers).