Operating Systems: Deadlocks and Memory Management

Deadlock Characterization

A deadlock is a situation where a set of processes is 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, making this condition impossible to eliminate completely.
• 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 (e.g., F(Disk Drive) = 1, F(Printer) = 5). A process can only request resources in an increasing order of enumeration. If it holds resource R₅, it cannot request R₁ without releasing R₅ first. This completely eliminates mathematical cycles.

Deadlock Avoidance

Deadlock avoidance requires the operating system to have a priori information about the maximum resources a process will ever request during its lifetime. 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.

┌────────────────────────────────────────┐
│         UNSAFE STATES                  │
│   ┌──────────────────────────────┐   │
│   │          DEADLOCK            │   │
│   └──────────────────────────────┘   │
└────────────────────────────────────────┘
┌────────────────────────────────────────┐
│               SAFE 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:

Let n be the number of processes and m be the number of resource types.

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

Here is a breakdown of the core Memory Management Strategies used by operating systems to track, allocate, and optimize physical memory (RAM).

1. Single-User vs. Multiuser Operating Systems

Single-User Systems

In early or simpler operating systems (like MS-DOS), memory management is straightforward because only one user program runs at a time.

• Structure: Memory is generally split into two parts: one for the Resident OS (low or high memory) and one for the active user program.
• Allocation: The program gets access to all remaining available memory.
• Protection: Minimal protection is needed because there are no other user programs to overwrite or interfere with.

Multiuser Systems

Modern operating systems (like Windows, Linux, macOS) support multiple users and multiprogramming (running many processes simultaneously).

• Complexity: The OS must constantly decide which process gets how much memory, where to put it, and how to reclaim it when the process finishes.
• Protection: Highly critical. The OS must prevent Process A from reading or modifying the memory space of Process B or the OS itself.

2. Contiguous Memory Allocation & Partitioning

In early multiprogramming systems, memory was allocated contiguously. This means each process is loaded into a single, continuous block of memory.

Fixed (Static) Partitioning

Memory is divided into fixed-sized, permanent regions at startup.

• How it works: A process is assigned to a partition that is big enough to hold it.
• The Problem (Internal Fragmentation): If a process is 8 MB but the partition is 10 MB, the leftover 2 MB is wasted. It cannot be used by any other process because that partition is locked.

Dynamic Partitioning

Partitions are created dynamically as processes request memory; they are given exactly what they need.

• The Problem (External Fragmentation): As processes are loaded and deleted over time, memory gets broken up into small, scattered holes.
• Example: You might have 50 MB of total free memory, but it is split into five 10 MB scattered holes. If a new process requires 20 MB of contiguous space, it cannot be loaded, even though 50 MB is free.
• Solution: Compaction (shuffling memory contents to place all free memory together in one large block), though this requires heavy CPU overhead.

3. Swapping

When physical memory is full, the OS needs a way to make room for active processes.

• Concept: A process can be swapped temporarily out of main memory to a backing store (like an SSD/HDD swap space) and then brought back into memory later for continued execution.
• Roll-out, Roll-in: A variant used for priority-based scheduling; lower-priority processes are swapped out so higher-priority processes can be loaded and executed.
• Bottleneck: The major cost of swapping is transfer time. Copying large blocks of data between RAM and a disk is relatively slow.

4. Non-Contiguous Strategies: Paging and Segmentation

To eliminate external fragmentation and the requirement for compaction, modern systems use non-contiguous memory allocation. This allows a program's memory to be scattered throughout physical RAM.

Paging

Paging breaks down both logical memory (the program's view) and physical memory (RAM) into fixed-size blocks.

• Pages: Fixed-size blocks of logical memory.
• Frames: Fixed-size blocks of physical memory (same size as pages).
• Page Table: A hardware-supported lookup table managed by the OS. It maps a program's Page to the actual physical Frame in RAM.
• How it helps: Because any page can fit into any available frame, external fragmentation is completely eliminated. However, a small amount of internal fragmentation can still occur on the very last page of a process if it doesn't perfectly fill the fixed block.

Segmentation

While paging is convenient for hardware, it cuts programs into arbitrary sizes without respecting the structure of the code. Segmentation allocates memory based on the user/programmer's view of a program.

• Segments: Logical, variable-length units of a program (e.g., Main Program, Functions, Objects, Stack, Global Variables).
• Segment Table: Maps a logical segment (by number and offset) to its physical base address and length (limit) in RAM.
• Pros & Cons: It protects logical blocks of code much better (e.g., setting a "read-only" attribute on the code segment). However, because segments are variable in length, it reintroduces the problem of external fragmentation in physical RAM.

Quick Comparison: Paging vs. Segmentation