Automatic Detection and Resolution of Deadlocks in Go Programs

The Go programming language is acquiring momentum in the development of concurrent software. Even though Go supports the shared-memory model, the message-passing alternative is the favoured idiomatic approach. Naturally, this practice is not exempt of the usual difficulties: programs may deadlock and the language run-time has only very basic support for deadlock detection. Moreover, there are no safety guarantees at compile-time (apart from the usual data type-safety one). Previous research on deadlock detection mainly focused on shared-memory concurrency models. For mainstream languages, tools and approaches specific to the message-passing paradigm are scarce and incipient. There is however a large body of work on models of concurrency that only recently started to be applied to languages like Go. Since the Go run-time lets many deadlocks pass unnoticed, and the existing solutions provided by third party tools detect many deadlocks but only try to fix a limited set of specific patterns, imposing severe conditions to do so, there is a clear need for more general deadlock resolution strategies, going beyond prevention and avoidance. To address deadlock detection and resolution, we developed an algorithm that takes an abstraction of the communica- tion behaviour of the program and, when all the communication opera- tions on channels necessary for progress are present, but a deadlock is possible, presents the problem and offers a code snippet to substitute the part with the error. Building on previous work, we deal with real world situations and go beyond the state-of-the-art, as we offer solutions for situations other approaches do not deal with.