Resource allocation graph

As explained in Learn Concurrent Programming with Go

A resource allocation graph is a directed graph whose nodes represent executions and resources and whose edges represent resource requests and assignments.

A resource allocation graph (RAG) makes a deadlock visible. It is a directed graph whose nodes are executions and resources: use circles for executions such as goroutines and rectangles for resources such as exclusive locks. Edges show the current relationship between them, so the graph captures who holds a resource and who is waiting for one. section 11.1.1 section 11.5

Read the direction of each edge carefully:

• Execution → resource: the execution is requesting that resource. section 11.1.1
• Resource → execution: that execution is currently using or holding the resource. section 11.1.1
• A cycle means the system is deadlocked: each execution in the cycle is waiting for a resource held by another. section 11.1.1 section 11.5

Two locks, two goroutines

Suppose blue() holds lock 2 and requests lock 1, while red() holds lock 1 and requests lock 2. The graph alternates between goroutine and lock nodes until it returns to its start. Neither goroutine can acquire its second lock, so both wait forever. The same pattern can involve more participants: ledger transfers create a cycle among goroutines 0, 2, and 3, while another goroutine is blocked trying to reach an affected account lock. section 11.1.1 section 11.1.2

Figure 11.2 Resource allocation graph of the red() and blue() goroutines

Inspect the solid resource-to-goroutine edges and dashed goroutine-to-resource edges to trace the circular wait. section 11.1.1

RAGs support more than manual diagnosis. A system can build a graph of its executions and allocated resources, then run cycle detection. A depth-first traversal can track visited nodes; encountering an already visited node identifies a cycle. This is more complete than relying only on Go runtime detection, which reports deadlock only when all goroutines are blocked. Systems may terminate stuck executions or return an error when a request would create a deadlock. section 11.2.1 section 11.2.1

Use the graph as a design check whenever work needs multiple exclusive resources. Consistent predefined resource ordering can prevent circular waits. Treat channel capacity as a mutually exclusive resource too, and avoid circular message flows; separate goroutines or select-based channel operations can help break such waits. section 11.5 section 11.5

How Learn Concurrent Programming with Go covers it

How deep it goes

Defines node and edge semantics, explains cycles through examples, and outlines depth-first cycle detection.

Examples

Uses two opposing lock acquisitions, ledger transfers, rail crossings, and MySQL transaction errors.

What you can do after

Diagnose/debug deadlocks by tracing wait cycles or applying cycle detection to execution-resource relationships.

How it connects

Connects deadlocks with goroutines, mutexes, graph cycles, depth-first search, channels, and resource ordering.

liveBookmanning.com

Read Learn Concurrent Programming with Go on liveBook Get the book at manning.com

Related concepts

• cycle detectionused by · Cycle detection is a graph-analysis technique for identifying whether traversal returns to a previously visited node, forming a cycle.
• deadlock detectionused by · Deadlock detection is the process of identifying states in which concurrent processes or tasks are indefinitely blocked by circular dependencies on resources.
• deadlockmeasures · A deadlock is a state in concurrent execution where two or more activities are indefinitely blocked by dependencies on resources, events, or progress that cannot become available.
• cyclehas part · A cycle is a recurring sequence of connected elements or events that returns to an earlier point, forming a loop.

This explainer was generated by Manning's knowledge graph from the text of Learn Concurrent Programming with Go. The section links point to the parts of the book it draws on.