MODULE – IV : Deadlocks & Memory Management

Define Deadlock and Explain System Model

Explanation

In a computer system, multiple processes often need resources such as CPU, memory, files,
printers, or I/O devices to complete their execution. Sometimes, a situation arises where each
process is waiting for a resource that is held by another process, and none of them can
proceed. This situation is called deadlock.

Deadlock is dangerous because once it occurs, the system may stop making progress, and
the affected processes remain blocked forever unless the operating system intervenes.

Example

Imagine four students sitting in a circle, each holding one book and waiting for the next
student’s book to complete their assignment.
Since no one is willing to release their book first, all students keep waiting forever.

Similarly, in an operating system, processes wait indefinitely for resources held by each
other, leading to deadlock.

Main Answer

Definition of Deadlock

A deadlock is a situation in which a set of processes are permanently blocked because

each process is holding at least one resource and waiting for additional resources that
are held by other processes in the set.

System Model
To understand deadlock, the operating system uses a system model that describes how
processes request and use resources.
1. Resources in a System

A system consists of a finite number of resource types, such as:

 CPU cycles
 Memory space
 I/O devices (printer, disk, etc.)
 Files

Each resource type may have:

 One instance (e.g., a printer)

 Multiple instances (e.g., memory blocks)

2. Resource Usage Cycle

A process uses a resource in the following sequence:

1. Request
The process requests a resource. If the resource is not available, the process waits.
2. Use
The process uses the allocated resource.
3. Release
After using the resource, the process releases it.

This cycle is repeated until the process completes execution.

3. Resource Allocation Graph

The system model uses a resource allocation graph to represent deadlocks:

 Processes are represented as circles

 Resources are represented as squares
 Request edge (P → R) indicates a process requesting a resource
 Assignment edge (R → P) indicates a resource allocated to a process

If the resource allocation graph contains a cycle, a deadlock may or may not exist,
depending on the number of resource instances.
Explain Deadlock Characterization OR Explain Necessary Conditions for
Deadlock

Explanation

To understand why deadlock happens, we must study the conditions under which a
deadlock can occur. Deadlock does not happen randomly; it occurs only when certain
specific conditions are satisfied simultaneously. These conditions together are called
deadlock characterization.

By learning deadlock characterization, students can clearly understand:

 How deadlock situations arise

 Why some systems never face deadlock
 How operating systems design techniques to handle deadlock

Example

Imagine two people working on a project:

1. Person A holds a pen and waits for a paper

2. Person B holds the paper and waits for the pen

Neither person is willing to give up what they already have.

Both keep waiting forever → this is a deadlock.

This situation occurs because all deadlock conditions are satisfied.

Main Answer

Deadlock characterization describes the necessary conditions that must hold

simultaneously for a deadlock to occur in a system.

There are four necessary conditions for deadlock:

1. Mutual Exclusion
At least one resource must be held in a non-sharable mode.

 Only one process can use the resource at a time.

  If another process requests the same resource, it must wait.

Example:
A printer can be used by only one process at a time.

2. Hold and Wait

A process must be holding at least one resource and waiting to acquire additional
resources that are currently held by other processes.

Example:
A process holds a disk and waits for a printer that is held by another process.

3. No Preemption
Resources cannot be forcibly taken away from a process.

 A resource can be released only voluntarily by the process holding it.

Example:
The OS cannot forcefully remove a printer from a process while it is printing.

4. Circular Wait
A circular chain of processes exists where:

 Each process is waiting for a resource held by the next process in the chain.

Example:
P1 waits for P2 → P2 waits for P3 → P3 waits for P1

This creates a cycle of waiting.

Explain Resource Allocation Graph and Deadlock Detection

Explanation
When several processes are competing for system resources, the operating system needs a
clear way to visualize who is holding what and who is waiting for what. For this purpose,
the concept of a Resource Allocation Graph (RAG) is used.

By studying this graph, the operating system (and students) can:

 Understand how resources are allocated

 Identify waiting relationships
 Detect whether a deadlock has occurred

Deadlock detection is the technique used to check the system state and determine whether
processes are stuck permanently due to circular waiting.

Example
Assume:

 Process P1 holds a printer and waits for a scanner

 Process P2 holds a scanner and waits for a printer

Both processes keep waiting for each other forever.

This situation can be clearly shown using a resource allocation graph, where a cycle
appears, indicating deadlock.

Main Answer
Resource Allocation Graph (RAG)
A resource allocation graph is a directed graph that represents the allocation and request
of resources in a system.

Graph Components

1. Process Nodes (P)

o Represented by circles
 oEach circle denotes a process (P₁, P₂, …)
2. Resource Nodes (R)
o Represented by rectangles
o Each rectangle represents a resource type
o Dots inside the rectangle represent instances of the resource
3. Edges
o Request Edge (P → R):
Indicates that a process is requesting a resource
o Assignment Edge (R → P):
Indicates that a resource has been allocated to a process

Deadlock Detection Using Resource Allocation Graph

Case 1: Single Instance of Each Resource

 If the resource allocation graph contains a cycle, then

 Deadlock definitely exists

Reason:
Each process in the cycle is waiting for a resource held by another process in the same cycle.

Case 2: Multiple Instances of Resources

 If a cycle exists:

 Deadlock may or may not exist

 Additional checks are required using deadlock detection algorithms

Deadlock Detection
Deadlock detection involves:

 Examining the current allocation of resources

 Checking whether a set of processes are waiting indefinitely

The operating system periodically runs a deadlock detection algorithm to:

 Identify deadlocked processes

 Decide recovery actions (termination, resource preemption, etc.)
Explain Deadlock Prevention Strategies

Explanation
Deadlock occurs only when all four necessary conditions (mutual exclusion, hold and wait,
no preemption, circular wait) exist at the same time.
The idea behind deadlock prevention is very simple:

Design the system in such a way that at least one of these conditions can never occur.

If even one condition is eliminated, deadlock becomes impossible.

Deadlock prevention is a static approach, meaning rules are decided before execution, not
after deadlock occurs.

Example
Imagine a college lab where:

 Students are allowed to collect all required equipment at once, or

 Students must return current equipment before asking for new ones

Because of these strict rules, no student ends up waiting forever.

Similarly, operating systems apply strict policies to prevent deadlock.

Main Answer
Deadlock prevention is a set of strategies used by the operating system to ensure that at
least one of the necessary deadlock conditions never holds, thereby preventing deadlock.

Deadlock prevention strategies are explained by eliminating each deadlock condition as

follows:

1. Eliminating Mutual Exclusion

Concept

 Mutual exclusion requires resources to be non-sharable.

 Deadlock can be prevented by making resources sharable wherever possible.
How it works

 Allow multiple processes to use the same resource simultaneously.

Example

 Read-only files can be shared by many processes at the same time.

Limitation

 Not all resources can be shared (e.g., printers, CPU).

2. Eliminating Hold and Wait

Concept

 Prevent processes from holding one resource while waiting for others.

Methods

1. Request all resources at once before execution begins

2. Release all resources before requesting new ones

Example

 A process must request CPU, memory, and I/O devices together.

Limitation

 Low resource utilization

 Possible starvation

3. Eliminating No Preemption
Concept

 Allow the operating system to preempt resources.

How it works

 If a process holding resources requests another unavailable resource:

o The OS forces it to release its currently held resources

o The process is restarted later
Example

 CPU registers can be saved and reassigned.

Limitation

 Not suitable for all resources

 Overhead due to process rollback

4. Eliminating Circular Wait

Concept

 Prevent circular dependency among processes.

Method

 Impose a total ordering on resources

 Processes must request resources in increasing order only

Example

 Resource order: R1 → R2 → R3
 A process holding R2 cannot request R1

Advantage

1. Simple and effective

2. Completely prevents circular wait

Explain Deadlock Avoidance

Explanation
Deadlock avoidance is a dynamic approach used by the operating system to ensure that the
system never enters a deadlock state.
Unlike deadlock prevention (which applies strict rules in advance), deadlock avoidance
examines each resource request at runtime and decides whether granting the request is
safe.

The key idea is:

Allow resource allocation only if the system remains in a safe state.

Example
Imagine a bank giving loans to customers:

 The bank checks whether giving a loan to a new customer will still allow it to satisfy
all existing customers.
 If granting the loan risks the bank running out of money, the request is denied.

Similarly, the operating system checks whether allocating a resource to a process will keep
the system safe. If not, the process must wait.

Main Answer
Deadlock avoidance is a technique in which the operating system dynamically examines
resource allocation requests and grants a request only if it does not lead the system into
a deadlock.

This approach requires the operating system to have advance information about:

 The maximum resource requirements of each process.

Safe State Concept

A system is said to be in a safe state if there exists at least one sequence of processes such
that:

 Each process can obtain its maximum required resources

 All processes can complete execution without deadlock

If no such sequence exists, the system is in an unsafe state, which may lead to deadlock.

Important for students:

 1.
Safe state → No deadlock
2.
Unsafe state → Deadlock may occur (but not guaranteed)

Deadlock Avoidance Algorithms

1. Resource-Allocation Graph Algorithm

 Used when each resource type has only one instance

 Adds a claim edge to indicate future possible resource requests
 A request is granted only if it does not create a cycle

2. Banker’s Algorithm

 Used when each resource type has multiple instances

 Requires knowledge of:
o Maximum demand
o Current allocation
o Available resources
 Simulates allocation to check if the system remains safe

Why “Banker”?
Because it is similar to how a banker ensures safe loan allocation.
PART B – (Memory Management)

Explain Memory Management Background

Explanation
A computer system runs multiple programs at the same time, and each program needs
memory to store its instructions and data. However, main memory (RAM) is limited, and
the operating system must manage it efficiently so that:

1. Programs execute correctly

2. Memory is shared safely
3. CPU utilization is maximized

This responsibility of the operating system is known as memory management.

Before studying advanced techniques like paging or segmentation, it is important to
understand the background concepts of memory management—why it is needed and what
problems it solves.

Example
Think of a college library with limited study tables:

1. Many students want to study at the same time

2. Each student needs a table for some duration
3. The librarian decides:
o Who gets a table
o When a student must leave
o How to avoid clashes

Similarly, the operating system acts like a memory manager, deciding:

1. Which process gets memory

2. How much memory it gets
3. When memory is released

Main Answer
Memory Management
Memory management is the function of the operating system that controls and coordinates
the use of main memory, ensuring that each process gets the memory it needs while
preventing interference between processes.

Memory Management Background Concepts

1. Main Memory

 Main memory (RAM) is a large array of bytes, each with a unique address.
 It is a shared resource used by:

o The operating system

o User processes

The CPU can access only main memory directly, so all programs must be loaded into
memory before execution.

2. Program Execution and Memory

For a program to execute:

1. Program must be loaded from disk into main memory

2. CPU fetches instructions from memory
3. Data is read and written during execution

Thus, efficient memory usage is critical for system performance.

3. Multiprogramming and Memory Sharing

Modern systems use multiprogramming, where multiple processes reside in memory at the
same time.

Benefits:

 Better CPU utilization

 Faster response time

Challenge:

 Processes must be isolated so that one process does not access or modify another
process’s memory.
4. Address Binding

Memory addresses used by a program go through different forms:

 Logical address – Generated by the CPU

 Physical address – Actual location in main memory

The operating system and hardware handle mapping between logical and physical
addresses.

5. Memory Protection

Memory management must ensure:

 A process accesses only its allocated memory

 Operating system memory is protected from user processes

This is achieved using:

 Base and limit registers

 Hardware support (MMU)

6. Memory Allocation

The OS decides:

 How much memory to allocate to a process

 Where to place the process in memory
 How to reclaim memory after process termination

Poor allocation leads to:

 Fragmentation
 Wasted memory
 Reduced performance
Explain Contiguous Memory Allocation Techniques

Explanation
When a program is loaded into main memory, the operating system must decide where to
place it.
One simple approach is to allocate one continuous block of memory to each process. This
approach is called contiguous memory allocation.

In this method:

 Each process occupies a single, contiguous (adjacent) region of memory

 Once allocated, the process executes entirely within that block

Understanding contiguous memory allocation is important because it is the starting point for
learning advanced memory management techniques like paging and segmentation.

Example
Think of a train with consecutive seats:

 Each passenger group must be seated together

 If there are no adjacent seats available, the group cannot be seated—even if empty
seats exist elsewhere

Similarly, in contiguous memory allocation, a process is loaded only if a sufficiently large

continuous block of memory is available.

Answer
Contiguous Memory Allocation

Contiguous memory allocation is a memory management technique in which each process

is allocated a single contiguous block of physical memory.

The operating system maintains information about which parts of memory are free and
which are occupied.

Types of Contiguous Memory Allocation

1. Single-Partition Allocation

 Memory is divided into:

o One region for the operating system
o One region for one user process
 Only one process can reside in memory at a time

Limitation:
Poor CPU utilization and no multiprogramming.

2. Multiple-Partition Allocation

Main memory is divided into multiple partitions, allowing multiple processes to reside in
memory simultaneously.

This technique is further classified into:

a) Fixed Partition Allocation

Explanation

 Memory is divided into a fixed number of partitions

 Partition sizes are predefined
 Each partition holds one process

Problem

 Internal fragmentation:
Unused memory inside a partition if the process is smaller than the partition size

b) Variable Partition Allocation

Explanation

 Memory is divided dynamically based on process size

 Each process gets exactly the memory it needs

Problem

 External fragmentation:
Free memory exists, but not in one contiguous block large enough for a process
Memory Allocation Strategies
To choose a suitable free memory block, the operating system uses the following strategies:

1. First Fit

 Allocates the first free block that is large enough

 Fast and simple
 May lead to external fragmentation

2. Best Fit

 Allocates the smallest free block that is sufficient

 Reduces wasted space
 Slower due to full memory search

3. Worst Fit

 Allocates the largest free block

 Leaves large remaining blocks
 Generally inefficient

Fragmentation in Contiguous Allocation

Internal Fragmentation

 Occurs in fixed partitioning

 Memory inside a partition remains unused

External Fragmentation

 Occurs in variable partitioning

 Free memory scattered across memory

Compaction
  A technique used to reduce external fragmentation
 Moves processes so that free memory becomes contiguous
 Requires relocation support

Explain Internal and External Fragmentation with Examples

Explanation
When the operating system allocates memory to processes, it tries to use the available main
memory efficiently. However, due to the way memory is divided and assigned, some
memory space may get wasted. This wastage of memory is called fragmentation.

Fragmentation is mainly of two types:

 Internal Fragmentation
 External Fragmentation

Understanding these two concepts is very important because they explain why simple
memory allocation techniques fail and why advanced techniques like paging are required.

Example
Imagine memory as a row of storage boxes:

 Sometimes a box is bigger than what is needed, so space inside is wasted.

 Sometimes enough space exists, but it is scattered, so a large item cannot be placed.

These two situations directly correspond to internal and external fragmentation.

Main Answer
Internal Fragmentation

Explanation

Internal fragmentation occurs when memory allocated to a process is larger than the
memory actually required, and the unused space inside the allocated block is wasted.
This happens mainly in:

1. Fixed partition allocation

2. Systems where memory is allocated in fixed-size blocks

Example

Suppose:

1. Partition size = 100 KB

2. Process requires = 70 KB

Allocated memory = 100 KB

Unused memory = 30 KB

This unused 30 KB inside the partition cannot be used by other processes.

 This wasted space is called internal fragmentation.

External Fragmentation

Explanation

External fragmentation occurs when free memory is available in the system, but it is
divided into small non-contiguous blocks, making it impossible to allocate a large
contiguous block to a process.

This happens mainly in:

 Variable partition allocation

Example

Suppose free memory blocks are:

1. 20 KB
2. 30 KB
3. 25 KB

Total free memory = 75 KB

If a process requires 50 KB, it cannot be allocated, even though enough total memory exists,
because no single contiguous block is large enough.
  This situation is called external fragmentation.

Explain Paging and Address Translation

Explanation
In contiguous memory allocation, a process must be placed in one continuous block of
memory, which leads to problems like external fragmentation. To overcome this limitation,
modern operating systems use a memory management technique called paging.

Paging allows a process to be divided into small fixed-size parts and loaded into any
available memory locations, thereby making memory utilization efficient and flexible.
To make this work, the operating system must also translate the addresses generated by the
CPU into actual physical memory addresses. This process is called address translation.

Example
Imagine a large textbook divided into equal-sized pages:

 You don’t need to keep all pages together on one shelf

 Pages can be placed anywhere, as long as you know which page is where

Similarly:

 A program is divided into pages

 Memory is divided into frames
 A page table keeps track of where each page is stored in memory

Main Answer
Paging
Paging is a memory management scheme that eliminates the need for contiguous memory
allocation by dividing:

 Logical memory into fixed-size blocks called pages

 Physical memory into fixed-size blocks called frames
The size of a page and a frame is the same.

Key Characteristics of Paging

1. A process is divided into multiple pages

2. Pages can be loaded into any free frames
3. No external fragmentation
4. Internal fragmentation may occur (last page partially used)

Paging Data Structures

Page Table

 Maintained by the operating system

 Maps page numbers to frame numbers
 One page table per process

Address Translation in Paging

Logical Address

A logical address generated by the CPU consists of:

 Page number (p) – identifies the page

 Page offset (d) – identifies the position within the page

Logical Address = ⟨p, d⟩

Physical Address

The physical address consists of:

 Frame number (f) – obtained from page table

 Offset (d) – same as logical offset

Physical Address = ⟨f, d⟩

Steps in Address Translation
1. CPU generates a logical address ⟨p, d⟩
2. Page number p is used as an index into the page table
3. The page table returns the corresponding frame number f
4. Physical address is formed as ⟨f, d⟩
5. Memory access is performed using the physical address

This translation is handled by the Memory Management Unit (MMU).

Explain Translation Lookaside Buffer (TLB)

Explanation
In a paging system, every time the CPU accesses memory, it must first translate a logical
address into a physical address using the page table.
However, page tables are stored in main memory, so this translation itself takes extra time.

To speed up address translation, the operating system uses a special high-speed hardware
cache called the Translation Lookaside Buffer (TLB).

The main goal of TLB is:

 Reduce memory access time by avoiding repeated page-table lookups.

Example
Think of a dictionary app on your phone:

 Frequently searched words appear instantly because they are cached

 Rarely searched words take longer to load

Similarly:

 Frequently used page table entries are stored in the TLB

 Rare entries are fetched from main memory

This makes memory access much faster.

Answer
Translation Lookaside Buffer (TLB)

A Translation Lookaside Buffer (TLB) is a small, fast associative memory that stores a
subset of page table entries to speed up logical-to-physical address translation.

It is located inside the Memory Management Unit (MMU).

Working of TLB
When the CPU generates a logical address ⟨p, d⟩:

Step-by-Step Operation

1. The page number (p) is searched in the TLB

2. If found (TLB hit):
o Frame number is obtained directly
o Physical address is formed immediately
3. If not found (TLB miss):
o Page table in main memory is accessed
o Entry is loaded into the TLB
o Physical address is generated

TLB Hit and Miss

TLB Hit

 Page number found in TLB

 Very fast translation
 Only one memory access needed

TLB Miss

 Page number not found in TLB

 Requires page table lookup
 Slower than TLB hit

Effective Memory Access Time (Concept)

 Higher TLB hit ratio → faster system performance
  Modern systems achieve very high hit ratios

Explain Structure of Page Table

Explanation
In a paging system, a process is divided into pages and physical memory is divided into
frames.
To know where each page of a process is stored in memory, the operating system uses a
data structure called the page table.

The structure of the page table is important because it not only stores the page–frame
mapping, but also controls access, protection, and status of pages during program
execution.

Example
Think of a hostel room allotment register:

 Student roll number → room number

 Additional details: room occupied, access allowed, etc.

Similarly:

 Page number → frame number

 Additional control and status information

This register-like structure is the page table.

Answer
Page Table

A page table is a data structure maintained by the operating system that maps logical page
numbers to physical frame numbers.
Each process has its own page table.

Structure of a Page Table Entry (PTE)

Each entry in the page table is called a Page Table Entry (PTE).
A typical page table entry contains the following fields:

1. Frame Number

 Indicates the physical frame where the page is stored.

 Used to form the physical address during address translation.

2. Valid / Invalid Bit

 Valid bit = 1 → Page is present in memory

 Valid bit = 0 → Page is not in memory or not part of the process’s address space

Used for memory protection.

3. Protection Bits

 Define access rights of the page:

o Read
o Write
o Execute

Prevents illegal memory access.

4. Reference Bit (Accessed Bit)

 Set when the page is accessed

 Used by page replacement algorithms

5. Modified Bit (Dirty Bit)

  Set if the page has been modified
 Helps decide whether the page needs to be written back to disk

6. Caching / Control Bits (Optional)

 Control caching behavior

 Architecture dependent

Explain Different Methods for Structuring Page Tables

Explanation
In paging, each process maintains a page table that maps logical pages to physical frames.
For small address spaces, a simple page table works well. However, in modern systems,
processes may have very large virtual address spaces, which makes the page table very
large and memory-consuming.

To handle this problem efficiently, operating systems use different methods for structuring
page tables. These methods aim to:

 Reduce memory overhead

 Improve lookup efficiency
 Support large address spaces

Example
Imagine a huge library catalog:

 Keeping all book details in one big register is inefficient

 Instead, the library uses:

o Multiple-level indexes
o Section-wise directories
o Compact tables for frequently accessed books

Similarly, operating systems organize page tables in smarter ways.

Main Answer
The commonly used methods for structuring page tables are:

1. Multilevel (Hierarchical) Page Tables

2. Hashed Page Tables
3. Inverted Page Tables

1. Multilevel (Hierarchical) Page Tables

Explanation

In multilevel paging, the page table is divided into multiple levels.

Instead of keeping one large page table, the system uses a page directory that points to
smaller page tables.

Only the required portions of the page table are kept in memory.

Working

1. Logical address is divided into:

o Page directory index
o Page table index
o Offset
2. Page directory entry points to a page table
3. Page table entry gives the frame number

2. Hashed Page Tables

Explanation

Hashed page tables are used for very large address spaces, such as 64-bit systems.

 A hash function is applied to the page number

 The hash table stores a linked list of page table entries
 Each entry contains:

o Virtual page number

o Frame number
o Pointer to next entry
Working

1. Page number is hashed

2. Hash table is searched
3. Matching virtual page number gives the frame number

3. Inverted Page Tables

Explanation

In an inverted page table:

 There is one page table for the entire system

 Each entry corresponds to a physical frame, not a virtual page

Each entry stores:

 Process ID
 Virtual page number
 Control bits

Working

1. Logical address ⟨PID, page number, offset⟩

2. System searches inverted page table for a matching entry
3. Frame number is obtained