Skip to content

Deadlock Detection

Deadlock detection is a method to solve the deadlock problem that is different from prevention and avoidance. It does not have strict restrictions on resource allocation, but regularly checks whether a deadlock has occurred during system operation. Once a deadlock is found, the system will take measures to resolve it. The following are the key points of this method:

Deadlock detection

  • Method: There are no excessive restrictions on resource allocation, and the system allows processes to freely apply for resources. However, the system will periodically run a "deadlock detection program" to check whether the system is in a deadlock state. If a deadlock is found, the system will take measures to solve the problem (such as killing a process, recycling resources, etc.).
  • Working principle:
  • The system describes the relationship between processes and resources through a process resource allocation graph. Each process and resource are connected by directed edges, indicating the application and allocation of resources.
  • Process resource allocation graph is a graph model Resource allocation graph Among them:
  • Process is a node in the graph, representing the resources requested or occupied by the process.
  • Resource is also a node, representing the resources available for the process to request and occupy in the system.
  • Direction of the edge: From the process to the resource, it means that the process is requesting the resource; from the resource to the process, it means that the resource has been allocated to the process.

Detection process

  1. Build a resource allocation graph: By recording the relationship between each process and resource, the system regularly builds a process resource allocation graph.
  2. Determine deadlock: Determine deadlock through the loop in the graph. If there is a loop in the graph, and each process in the loop waits for resources held by other processes in the loop, then these processes form a deadlock.
  3. Relieve deadlock: Once a deadlock is found, the system can take the following measures to resolve the deadlock:
  4. Terminate process: Select one or more processes to terminate, release resources, and break the deadlock.
  5. Rollback operation: Roll back the process to a safe state so that resources can be released and execution can be restarted.