Operating Systems: Deadlock Principles

Week 6 Agenda

• This week's topics will include principles of deadlock, deadlock prevention, deadlock avoidance, and deadlock detection
• An integrated deadlock strategy will be covered

Deadlock Defined

• Processes can become permanently blocked when competing for system resources or communicating with each other
• A set of processes becomes deadlocked when each process is blocked
• Each blocked process is waiting for an event triggered by another blocked process within the set
• Deadlock is permanent due to none of the events ever being triggered
• There is no efficient solution to deadlock in the general case

Illustration of Deadlock (Figure 6.1)

• Deadlock can occur in situations such as traffic intersections or processes competing for resources
• Deadlock is possible when processes (or cars) are in a configuration where they could potentially block each other
• Deadlock occurs when processes (or cars) are actually blocking each other, preventing any further progress

Processes P and Q

• Consider two processes P and Q
• Each process requires exclusive access to resources A and B for a period of time

Joint Progress Diagram with Uniprocessor (Figure 6.2)

• Both processes P and Q want resource A
• Deadlock is inevitable
• Both processes P and Q also want resource B

Joint Progress Diagram illustrating no Deadlock (Figure 6.3)

• P and Q both want resource A
• P and Q both want B
• This is an example of no deadlock when the paths of execution don't lead to a blocking scenario

Resource Categories: Reusable

• Reusable resources can be safely used by only one process at a time
• They are not depleted by that use
• Examples of reusable resources include processors, I/O channels, main and secondary memory, devices, data structures, files, databases, and semaphores

Resource Categories: Consumable

• Consumable resources can be created (produced) and destroyed (consumed)
• Examples: interrupts, signals, messages, and info in I/O buffers

Example of Reuse Deadlock with Processes P and Q (Figure 6.4)

• Deadlock occurs when each process holds one resource and requests the other
• Process P's steps include requesting and locking resource D, requesting and locking resource T, performing a function, and then unlocking D and T
• Process Q's steps mirror P's but with the resources reversed (T then D)
• This creates a situation where each process is waiting for the other to release a resource

Memory Request Example

• Currently, a total of 200 Kbytes of memory is available in the system for allocation to various processes. This memory allocation is crucial for ensuring that processes can function effectively within the system's resources.
• However, complications arise when two processes simultaneously request memory. A deadlock occurs in situations where each process is holding part of the requested memory while waiting for the remaining memory to become available. This prevents either process from progressing, leading to a standstill.
• Process P1 initiates its operation by requesting 80 Kbytes of memory. After successfully obtaining this initial allocation, it then makes a subsequent request for an additional 60 Kbytes. This pattern of memory allocation illustrates the sequential nature of this process.
• In contrast, Process P2 begins by requesting 70 Kbytes. Once this allocation is secured, it follows up with a request for 80 Kbytes. The differing sizes requested by P1 and P2 can contribute significantly to the potential for deadlock in a concurrent processing environment.

Consumable Resources Deadlock

• Consider a pair of processes where each tries to receive a message from, and then send a message to, the other
• Process P1 receives from P2 and sends to P2 (message M1)
• Process P2 receives from P1 and sends to P1 (message M2)
• Deadlock results if the "Receive" operation is blocking, thus halting progress
• Deadlock may result from a rare sequence of events

Resource Allocation Graphs

• Graphs visually represent the state of system resources and processes
• Nodes represent processes and resources
• Edges show requests and allocations (who is holding what and what is being requested)
• A resource can be requested and not held
• A resource can be "held-by" a process
• Circular wait and deadlock can be visualized
• Absence of circular wait indicates no deadlock

Conditions for Deadlock

• Mutual Exclusion condition, ensuring that only one process may use a resource at a time
• No process may access a resource until it has been allocated to another process
• Hold-and-Wait condition occurs when a process may hold allocated resources while awaiting assignment of other resources
• No Preemption condition, meaning resources cannot be forcibly removed from a process holding it
• Circular Wait condition: A closed chain of processes exists, such that each process holds at least one resource needed by the next process in the chain

Deadlock Approaches

• No single strategy effectively handles all types of deadlock
• The three common approaches include deadlock prevention, deadlock avoidance, and deadlock detection

Deadlock Avoidance Strategy

• Do not grant a resource request if the allocation could lead to deadlock

Deadlock Prevention Strategy

• Disallow one of the three necessary conditions for deadlock occurrence
• Prevent a circular wait condition from happening

Deadlock Detection Strategy

• Grant resource requests when possible while periodically checking for deadlock to recover from

Prevention: Design to Exclude Deadlock

• Design systems to exclude the possibility of deadlock
• Two main methods are indirect and direct

Prevention Indirect Method

• Prevent the occurrence of one of the three necessary conditions

Prevention: Direct Method

• Prevent the occurrence of circular wait

Deadlock Condition Prevention: Mutual Exclusion

• If access to a resource requires mutual exclusion, it must be supported by the OS
• Some resources (like files) might allow multiple read accesses but require exclusive access for writes
• Deadlock can still occur with more than one process requires write permission

Deadlock Condition Prevention: Hold and Wait

• Can be prevented by requiring that a process request all needed resources at one time
• Block the process until all requests can be granted simultaneously

Deadlock Condition Prevention: No Preemption

• If a process holding resources is denied a further request, it must release its original resources and request them again
• The OS may preempt the second process and require it to release resources

Deadlock Condition Prevention: Circular Wait

• Prevented by defining a linear ordering of resource types

Deadlock Avoidance

• Allows the three necessary conditions for deadlock
• Judicious choices make sure that the deadlock point is never reached
• A decision must dynamically determine whether the current resource allocation, if granted, will potentially lead to a deadlock
• Knowledge of future process requests is needed

Two Approaches to Deadlock Avoidance

• Resource Allocation Denial
• Process Initiation Denial

Deadlock Avoidance: Resource Allocation Denial

• Resource allocation denial does not grant an incremental resource request to a process if this allocation might lead to deadlock
• It is referred to as the banker’s algorithm

System State

• This reflects the current allocation of resources to processes

Safe and Unsafe State Definitions

• A safe state is one where there is at least one sequence of resource allocations to processes that does not result in a deadlock
• An Unsafe state is a state that is not safe

Deadlock Avoidance: Process Initiation Denial

• Process initiation denial does not start a process if its demands might lead to deadlock

Determination of a Safe State (Figure 6.7) (REVIEW THIS)

• Matrices of resource allocation, claim, and available resources
• The initial state determines available and resource vectors
• Processes can run to completion, making state "safe"

Determination of an Unsafe State (Figure 6.8)

• Matrices of resource allocation, claim, and available resources
• Includes initial state and available resource vectors
• P1 requests one unit each of R1 and R3

Deadlock Avoidance Advantages

• No need to preempt and rollback processes
• Deadlock avoidance is less restrictive than deadlock prevention

Deadlock Avoidance Restrictions

• Requirement to state the maximum resource needs in advance
• Processes must be independent with no synchronization needs
• A fixed number of resources required to allocate
• No process may exit while holding resources

Strategies: Deadlock Prevention

• Deadlock prevention strategies are very conservative

Deadlock Prevention Strategies: Limit Access

• Limit access to resources by imposing restrictions on processes

Strategies: Deadlock Detection

• Deadlock detection strategies do the opposite

Deadlock Detection Strategies: Grant Requests

• Resource requests are granted whenever possible

Deadline Detection Algorithm Advantages

• This can lead to early detection
• The algorithm is relatively simple

Deadline Detection Algorithm Disadvantages

• Frequent checks uses considerable processor time

Example for Deadlock Detection (Figure 6.10)

• Includes request matrix, allocation matrix and allocation vector

Recovery Strategies Post-Detection

• Abort all deadlocked processes
• Back up each deadlocked process to a previously defined checkpoint and restart all processes
• Successively abort deadlocked processes until deadlock no longer exists
• Successively preempt resources until deadlock-no longer exists

Integrated Deadlock Strategy

• More efficient to use different strategies in different scenarios

Integrated Deadlock Strategy: Resource Grouping

• Group resources into differing resource classes

Integrated Deadlock Strategy: Prevent Circular Wait

• Use the linear ordering strategy to prevent circular wait between resource classes

Integrated Deadlock Strategy: Class-Specific Algorithms

• Use the most suitable algorithm within a resource class

Classes of Resources

• Swappable Space
• Process resources
• Main Memory
• Internal Resources

Class Strategies: Swappable Space

• Deadlock can be prevented by requiring that all resources be allocated at one time in a hold-and-wait prevention plan
• This strategy is reasonable if maximum storage requirements are known

Class Strategies: Process Resources

• Avoidance is effective when processes declare resource needs in advance
• Prevention is possible via resource ordering

Class Strategies: Main Memory

• Prevention is possible via preempting memory
• When a process loses memory, it swaps to secondary memory
• This frees up space for resolving a deadlock scenario

Class Strategies: Internal resources

• Prevention is possible via resource ordering

Summary

• Principles of deadlock including: Reusable/consumable resources, Resource allocation graphs, Conditions for deadlock
• Deadlock prevention, including: Mutual exclusion, Hold and wait, No preemption, Circular wait
• Deadlock avoidance including: Process initiation denial, Resource allocation denial
• Deadlock detection, including: Deadlock detection algorithm, Recovery
• Integrated deadlock strategy

Explore deadlock principles in operating systems. Learn about deadlock prevention, avoidance, and detection strategies. Understand how processes become permanently blocked and the conditions that lead to deadlock.