Cycle detection identifies a closed path in a graph by tracking visited nodes during traversal. In concurrency, a resource allocation graph represents executions and resources as nodes; a cycle means each participant is waiting within a circular dependency. section 11.2.1 section 11.5
A practical detector modifies depth-first search: traverse the graph, record visited nodes, and report a cycle when traversal reaches a previously visited node. This turns an otherwise indefinite wait into a detectable deadlock condition. section 11.2.1
Two mutexes, two goroutines
One goroutine locks mutex A and waits for B while another locks B and waits for A. The resulting cycle prevents either goroutine from completing, so the wait group never finishes. Go reports the deadlock when every goroutine is blocked, but a sleeping main goroutine can allow the program to print "Done" without reporting it. section 11.2.1 section 11.5
Listing 11.6 Triggering Go’s deadlock detection
package main import ( "fmt" "sync" ) func lockBoth(lock1, lock2 *sync.Mutex, wg *sync.WaitGroup) { for i := 0; i < 10000; i++ { lock1.Lock(); lock2.Lock() #1 lock1.Unlock(); lock2.Unlock() #1 } wg.Done() #2 } func main() { lockA, lockB := sync.Mutex{}, sync.Mutex{} wg := sync.WaitGroup{} wg.Add(2) go lockBoth(&lockA, &lockB, &wg) #3 go lockBoth(&lockB, &lockA, &wg) #3 wg.Wait() #4 fmt.Println("Done") } #1 Locks and unlocks both mutexes #2 Marks the waitgroup as done #3 Starts two goroutines, locking both mutexes at the same time #4 Waits for the goroutine to terminate
Runnable Go code creates two goroutines that acquire the same mutexes in opposite order, making the circular wait observable through the runtime. section 11.2.1
Cycle detection supports several operational responses:
- Terminate executions trapped in the cycle, as Go terminates the entire process after detecting a complete runtime deadlock. section 11.2.1
- Return an error to the execution whose resource request creates the cycle, allowing resource release and retry. section 11.2.1
- Apply the same reasoning to database locks and channel communication, where circular waits can also produce deadlocks. section 11.2.1 section 11.5
