Chapter 4 Exam

What is a Deadlock?

A deadlock in a computer system occurs when a set of processes is blocked because each process is holding a resource and waiting for a resource held by another process in the set. This situation creates a cycle of dependencies where no process can proceed.

Examples of Deadlock in a Computer System

1. Database Systems: Two transactions A and B each require two locks. Transaction A holds the lock on resource X and waits for resource Y, while transaction B holds the lock on resource Y and waits for resource X. This creates a deadlock, as neither transaction can proceed.

2. Operating Systems: A system with multiple processes and printers. Process A holds the CPU but needs access to the printer, while Process B holds the printer but needs access to the CPU. Neither process can proceed, causing a deadlock.

Deadlock Characterization – 4 Necessary Conditions

For deadlock to occur, all four of the following conditions must hold simultaneously:

1. Mutual Exclusion: At least one resource must be held in a non-shareable mode, meaning only one process can use the resource at a time.

2. Hold and Wait: A process that is holding at least one resource is waiting for additional resources held by other processes.

3. No Preemption: Resources cannot be forcibly taken from a process; they must be released voluntarily by the process holding them.

4. Circular Wait: A set of processes exist such that each process is waiting for a resource that is held by the next process in the set, forming a circular chain.

Representation of System State: Resource Allocation Graph

A Resource Allocation Graph (RAG) is a graphical representation used to model the state of the system with respect to resource allocation:

• Nodes:

  • Processes (denoted by circles).

  • Resources (denoted by rectangles), with a count of the available instances of each resource.

• Edges:

  • Request edges: A directed edge from a process to a resource, indicating that the process is requesting the resource.

  • Assignment edges: A directed edge from a resource to a process, indicating that the process is holding the resource.

Approaches for Handling Deadlock

There are three main approaches to handle deadlock:

1. Deadlock Prevention: Preventing deadlock by ensuring that at least one of the necessary conditions for deadlock is never satisfied.

2. Deadlock Avoidance: Ensuring that the system never enters an unsafe state by making resource allocation decisions based on the knowledge of future requests.

3. Deadlock Detection/Recovery: Allowing the system to enter a deadlock state but detecting it and recovering from it once it occurs.

Deadlock Prevention

In deadlock prevention, the goal is to design the system to ensure that at least one of the four necessary conditions for deadlock is not met. Two conditions are commonly addressed:

• Hold and Wait: One way to prevent this condition is to require that a process must request all resources it needs at once. If it doesn't get all the resources, it must wait until all are available.

  • Outcome: This can lead to inefficiency and resource starvation, as processes may have to wait for long periods without being able to execute.

• Circular Wait: To avoid this, a total ordering of resources can be imposed. Each process must request resources in a specific order. This eliminates circular chains of waiting processes.

  • Outcome: Although effective, this can also lead to inefficiency, as processes might have to wait longer for resources that could have been allocated more flexibly.

The other two conditions (mutual exclusion and no preemption) cannot be easily eliminated because:

• Mutual Exclusion: This is intrinsic to certain types of resources, such as printers or disk drives, where multiple processes cannot use the same resource simultaneously.

• No Preemption: Some resources (e.g., CPU) cannot be preempted from a process without causing instability.

Deadlock Avoidance

Deadlock avoidance strategies involve ensuring that a system never enters an unsafe state, where deadlock is possible. To do this, systems use a priori information about the maximum resource needs of processes to make safe allocation decisions.

Safe-State Checking Algorithms:

1. System with Single Instance of Every Resource Type:

   • Resource-Allocation Graph Algorithm: This algorithm can be used to check if the system will enter a deadlock state. If a cycle is detected in the resource allocation graph, the system is in an unsafe state.

2. System with Multiple Instances of Resource Types:

   • Banker’s Algorithm: This algorithm is used for deadlock avoidance by allocating resources in a way that ensures the system remains in a safe state. It checks if the system can allocate resources in a way that allows all processes to finish without deadlock, considering the maximum potential requests of processes.

Deadlock Detection/Recovery

This approach allows the system to enter a deadlock state but then provides mechanisms to detect and recover from it.

Deadlock Detection Algorithms:

1. System with Single Instance of Every Resource Type:

   • Cycle Detection in the Wait-for Graph: A deadlock detection algorithm searches for cycles in the wait-for graph. If a cycle exists, a deadlock is present.

   • Time Complexity: The time complexity is generally O(P + R), where P is the number of processes and R is the number of resources.

2. System with Multiple Instances of Resource Types:

   • Graph Reduction Algorithm: This algorithm reduces the wait-for graph by eliminating processes that can finish and release their resources, checking for cycles.

   • Time Complexity: The time complexity is O(P * R), where P is the number of processes and R is the number of resources.

Schemes for Deadlock Recovery:

Once deadlock is detected, there are several ways to recover from it:

1. Abort Process(es):

   • Abort one or more processes to break the deadlock. The choice of which process to abort depends on various factors like priority, resource usage, and cost of restarting the process.

2. Rollback:

   • Rollback a process to a safe state (e.g., using checkpoints). This allows the process to restart and potentially avoid the deadlock.

   • Checkpointing: Requires saving the state of processes periodically, so they can be restarted from a known state.

3. Factors for Selecting Victims:

   • Priority: Aborting lower-priority processes might minimize disruption.

   • Process Execution Time: Aborting processes that have been running for a shorter time may be less costly.

   • Resources Utilized: Processes holding resources that are essential for other processes may be selected as victims.

   • Process Recovery Time: Choosing processes that can be restarted quickly without significant overhead can help minimize the cost of recovery.