Operating System Deadlocks and Memory Management

Posted on Jun 18, 2026 in Computers

Deadlock Characterization

A deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource held by some other process in the set.

The Four Necessary Conditions

A deadlock can arise if and only if the following four conditions hold simultaneously in a system:

• Mutual Exclusion: At least one resource must be held in a non-shareable mode. Only one process can use the resource at any given instant.
• Hold and Wait: A process must currently hold at least one resource and be waiting to acquire additional resources that are being held by other processes.
• No Preemption: Resources cannot be forcibly taken from a process. A resource can be released only voluntarily by the process holding it, after that process has finished its task.
• Circular Wait: A closed chain of processes exists such that each process holds one or more resources that are needed by the next process in the chain.

Resource-Allocation Graph (RAG)

Deadlocks can be verified visually using a directed graph called a Resource-Allocation Graph.

• Vertices (V): Divided into two types:
  • P = {P₁, P₂, …, P_n} (Processes, represented as circles)
  • R = {R₁, R₂, …, R_m} (Resources, represented as rectangles with dots inside indicating resource instances)
• Edges (E):
  • Request Edge: Directed edge P_i → R_j (Process P_i is waiting for resource R_j).
  • Assignment Edge: Directed edge R_j → P_i (An instance of resource R_j has been allocated to process P_i).

Exam Rule of Thumb: If the RAG contains no cycles, the system is definitely not deadlocked. If the graph contains a cycle and resources have single instances, a deadlock exists. If resources have multiple instances, a cycle indicates a potential deadlock but not a guaranteed one.

Methods for Handling Deadlocks

Operating systems use three primary strategies to deal with deadlocks:

1. Deadlock Prevention or Avoidance: Ensuring that the system will never enter a deadlocked state.
2. Deadlock Detection and Recovery: Allowing the system to enter a deadlocked state, detecting it, and applying recovery mechanisms.
3. Ignore the Problem Entirely: Used by most modern operating systems (including UNIX, Linux, and Windows). It assumes deadlocks are rare, and the cost of prevention/detection is too high. This is famously known as the Ostrich Algorithm.

Deadlock Prevention

Deadlock prevention consists of a set of methods ensuring that at least one of the four necessary conditions cannot hold. By breaking a condition, deadlocks become impossible.

• Eliminating Mutual Exclusion: Shared resources (like read-only files) do not require exclusive access. However, some resources (like printers or hardware registers) are inherently non-shareable.
• Eliminating Hold and Wait: A process must request and be allocated all its required resources before it begins execution, or it can request resources only when it holds none. Disadvantage: Low resource utilization and potential starvation.
• Eliminating No Preemption: If a process holding some resources requests another resource that cannot be immediately allocated, all resources currently held by that process are preempted (released automatically).
• Eliminating Circular Wait: Impose a total ordering on all resource types. A process can only request resources in an increasing order of enumeration.

Deadlock Avoidance

Deadlock avoidance requires the operating system to have a priori information about the maximum resources a process will ever request. With this information, the OS decides for every request whether allocating the resource is safe.

Safe vs. Unsafe States

• Safe State: A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock. This order is called a Safe Sequence.
• Unsafe State: A state where the system cannot guarantee that all processes can finish without deadlocking. An unsafe state is not a deadlock, but a deadlock is a subset of unsafe states.

Banker’s Algorithm (For Multiple Instances)

When resources have multiple instances, the Banker’s Algorithm is used. It tests every request by pretending to allocate resources and checking if the resulting system state is safe.

Data Structures Used:

• Available[m]: Vector indicating available instances of each resource.
• Max[n][m]: Matrix defining the maximum demand of each process.
• Allocation[n][m]: Matrix defining resources currently allocated.
• Need[n][m]: Matrix defining the remaining resource need.

Memory Management Strategies

Operating systems use various strategies to track, allocate, and optimize physical memory (RAM).

Single-User vs. Multiuser Systems

• Single-User Systems: Memory is split into two parts: one for the Resident OS and one for the active user program.
• Multiuser Systems: Supports multiprogramming. The OS must manage memory allocation, reclamation, and protection between multiple processes.

Contiguous Memory Allocation

In early multiprogramming systems, memory was allocated contiguously.

• Fixed (Static) Partitioning: Memory is divided into fixed-sized regions. Problem: Internal fragmentation.
• Dynamic Partitioning: Partitions are created as needed. Problem: External fragmentation. Solution: Compaction.

Swapping

When physical memory is full, the OS swaps processes out to a backing store (SSD/HDD) to make room for active processes. Bottleneck: Transfer time between RAM and disk is slow.

Non-Contiguous Strategies

Modern systems use non-contiguous allocation to eliminate external fragmentation.

• Paging: Breaks memory into fixed-size Pages (logical) and Frames (physical). Uses a Page Table for mapping. Eliminates external fragmentation.
• Segmentation: Allocates memory based on the logical view of a program (e.g., functions, stacks). Reintroduces external fragmentation but allows better protection of logical blocks.

Comparison: Paging vs. Segmentation