A deadlock refers to a situation of no progress that can happen in a multi-process systems, such as

an operating system. It occurs when two or more entities (processes in the case of an OS) are each
waiting indefinitely for resources held by each other. Read this chapter to understand what is
deadlock, how it occurs in an operating system, effects of deadlock, and how to prevent it.

What is Deadlock in an OS?

In an operating system, deadlock is a state in which two or more processes are unable to proceed
because each is waiting for a resource that the other holds, resulting in a cycle of dependencies. The
processes involved in the deadlock situation are said to be deadlocked because they cannot continue
execution without intervention from the operating system.

The image below shows a deadlock situation between two processes P1 and P2 −

In this example, Process P1 holds Resource R2 and is waiting for Resource R1 to be ready.
Meanwhile, Process P2 holds Resource R1 and is waiting for Resource R2 to be ready. That's the
deadlock situation.

Conditions for Deadlock in Operating System

In an operating system, a deadlock occurs when a set of processes are blocked, each waiting for a
resource held by another process in the set, leading to a situation where no process can proceed.

For a deadlock to happen, certain conditions must be met. These conditions are commonly referred
to as the deadlock conditions and are based on the Coffman conditions, which describe the
necessary circumstances for a deadlock to occur.

• Mutual Exclusion

• Hold and Wait

• No Preemption

• Circular Wait
Mutual Exclusion
Mutual Exclusion is a condition that states to occur deadlock in an operating system, at least one
resource must be held in a non-shareable mode, meaning that only one process can use that
resource at any given time. If another process requests the same resource, it must wait for the
resource to be released. For example, a printer is a non-shareable resource only one process can
print at a time. When the chrome browser is using the printer to print a page, the PDF viewer must
wait for the printer to be released before it can print its document.

Hold and Wait

Hold and Wait is a condition that occurs when a process holding at least one resource is waiting to
acquire additional resources that are currently being held by other processes. This means that a
process that already has resources may request more resources, which it cannot obtain because they
are held by other processes.

The image show a scenario of Hold and Wait happening between a printer and a scanner.

Here, Process A holds a printer and waits for a scanner, while Process B holds a scanner and waits for
the printer. Both processes are holding resources and waiting for resources held by the other
process, leading to a potential deadlock situation.

No Preemption
No Preemption is a condition that states resources cannot be forcibly taken away from a process
holding them. A process must release the resource voluntarily when it is no longer needed. If a
process is holding a resource and is waiting for another resource, it cannot be preempted (i.e., it
cannot be forced to release the resource until it finishes its task).

For example, if Process A is holding a printer and is waiting for a scanner, the system cannot force
Process A to give up the printer. Process A must release the printer voluntarily once it has completed
its task.

Circular Wait
Circular Wait is a condition where a set of processes exist such that each process in the set is waiting
for a resource that another process in the set holds, forming a cycle of dependencies. In other words,
there is a circular chain of processes where each process is waiting for a resource held by the next
process in the chain.

For example, Process A waits for a resource held by Process B, Process B waits for a resource held by
Process C, and Process C waits for a resource held by Process A, forming a cycle of waiting processes.

How to Avoid Deadlocks?

To avoid deadlock, the operating system can take measures to prevent one or more of the four
necessary conditions from occurring. This can be done in the following ways −

• Prevent Mutual Exclusion − This is generally not feasible because many resources (like
printers, files, or memory) must be used exclusively by one process at a time. However, for
some resources (like read-only resources), multiple processes can access them
simultaneously.

• Prevent Hold and Wait − Require processes to request all resources they will need at once
before starting execution. This is called the "all-or-nothing" approach. Another option is to
require processes to release all the resources they currently hold before requesting new
ones.

• Prevent No Preemption − Allow preemption of resources. If a process holding some

resources is waiting for additional resources, the operating system can preempt the
resources currently held by the process and assign them to other processes.

Methods to Handle a Deadlock in OS

To handle deadlock, an operating system can use one of the following methods −

• Deadlock Prevention
 • Deadlock Avoidance

• Deadlock Detection and Recovery

• Ignoring Deadlock

How to Prevent Deadlock in an Operating System?

A deadlock will occur only if all the following four necessary conditions are occurring simultaneously
in the system −

• Mutual Exclusion

• Hold and Wait

• No Preemption

• Circular Wait

To prevent a deadlock, the operating system just needs to ensure that at least one of the above four
conditions never takes place. In the next section, we will see how to prevent each of these conditions
from occurring.

Prevent Mutual Exclusion

Mutual Exclusion is a condition that states to occur deadlock in an operating system, at least one
resource must be held in a non-shareable mode, meaning that only one process can use that
resource at any given time. If another process requests the same resource, it must wait for the
resource to be released.

To prevent occurring of mutual exclusion, the operating system can make resources
shareable whenever possible. For example, read-only resources such as files can be shared among
multiple processes simultaneously without causing any issues. But writeable resources like printers
or memory cannot be shared to multiple processes at the same time. Because when two processes
try to write data to the same resource simultaneously, it can cause data corruption and
inconsistency.

So preventing mutual exclusion is not always a choice for deadlock prevention. But whenever
possible, the operating system should make resources shareable to avoid deadlock.

Prevent Hold and Wait

Hold and Wait is a condition that occurs when a process holding at least one resource is waiting to
get additional resources that are currently being held by other processes. This means that a process
that already has resources may request more resources, which it cannot obtain because they are
held by other processes.

To prevent hold and wait, the operating system can use one of the following two strategies −

• Declare the Needed Resources Upfront − Before a process starts executing, it must request
and be allocated all the resources it will need during its execution. This is known as the "all-
or-nothing" approach. If all the requested resources are not available, the process should
wait until they are available.
 • Release Resources Before Requesting New Ones − If at any point during its execution, a
process needs additional resources, it must first release all the resources it currently holds
before requesting the new ones. This ensures that a process does not hold onto resources
while waiting for others.

Both of these strategies can help prevent hold and wait. However, they can also lead to decreased
resource utilization and increased waiting times for processes. So, the operating system must
carefully consider the trade-offs when implementing these strategies. End of the day, preventing
preventing deadlock comes with some cost.

Prevent No Preemption

No Preemption is a condition that states resources cannot be taken away from a process holding
them. Meaning a process must release the resource voluntarily when it is no longer needed.

To prevent no preemption condition, the operating system can allow preemption of resources. If a
process holding some resources is waiting for additional resources, the operating system can
preempt the resources currently held by the process and assign them to other processes. The
preempted process can be restarted later when it can get all the resources it needs.

However, preempting resources can lead to issues such as data inconsistency and starvation. So, the
operating system must carefully manage the preemption process to ensure that it does not lead to
other problems.

Prevent Circular Wait

Circular Wait says that a set of processes exist such that each process in the set is waiting for a
resource that another process in the set holds, thus forming a cycle of waiting. It can be visualized as
in the diagram below −
To prevent circular wait, the operating system can implement a total ordering method. In this
method, all resource types are assigned a unique numerical order. Each process is required to
request resources in an increasing order of their enumeration. This means that a process can only
request a resource with a higher number than the resources it currently holds. By implementing this
order, the operating system can prevent the formation of circular wait conditions among processes.

The Banker's Algorithm

Banker's Algorithm is a resource allocation and deadlock avoidance algorithm used in operating
systems. It ensures that a system remains in a safe state by carefully allocating resources to processes
while avoiding unsafe states that could lead to deadlocks.

• The Banker's Algorithm is a smart way for computer systems to manage how programs use
resources, like memory or CPU time.

• It helps prevent situations where programs get stuck and can not finish their tasks. This
condition is known as deadlock.

• By keeping track of what resources each program needs and what's available, the banker
algorithm makes sure that programs only get what they need in a safe order.

Components of the Banker's Algorithm

The following Data structures are used to implement the Banker’s Algorithm:

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

1. Available

• It is a 1-D array of size 'm' indicating the number of available resources of each type.

• Available [ j] = k means there are 'k' instances of resource type Rj

2. Max

• It is a 2-d array of size 'n*m' that defines the maximum demand of each process in a system.

• Max[ i, j ] = k means process Pi may request at most 'k' instances of resource type Rj.
3. Allocation

• It is a 2-d array of size 'n*m' that defines the number of resources of each type currently
allocated to each process.

• Allocation[ i, j] = k means process Pi is currently allocated 'k' instances of resource type Rj

4. Need

• It is a 2-d array of size 'n*m' that indicates the remaining resource need of each process.

• Need [ i, j] = k means process Pi currently needs 'k' instances of resource type Rj

• Need [ i, j ] = Max [ i, j] – Allocation [ i,j]

Allocation specifies the resources currently allocated to process Pi and Need specifies the additional
resources that process Pi may still request to complete its task.

Key Concepts in Banker's Algorithm

• Safe State: There exists at least one sequence of processes such that each process can obtain
the needed resources, complete its execution, release its resources, and thus allow other
processes to eventually complete without entering a deadlock.

• Unsafe State: Even though the system can still allocate resources to some processes, there is
no guarantee that all processes can finish without potentially causing a deadlock.

Example of Unsafe State

Consider a system with three processes (P1, P2, P3) and 6 instances of a resource. Let's say:

1. The available instances of the resource are: 1

2. The current allocation of resources to processes is:

• P1: 2

• P2: 3

• P3: 1

3. The maximum demand (maximum resources each process may eventually request) is:

• P1: 4

• P2: 5

• P3: 3

In this situation:
• Need = Maximum Demand – Allocation
Process Maximum Demand Allocation Need

P1 4 2 2

P2 5 3 2

P3 3 1 2

• P1 may need 2 more resources to complete.

• P2 may need 2 more resource to complete.

• P3 may need 2 more resources to complete.

However, there is only 1 resource available. Even though none of the processes
are currently deadlocked, the system is in an unsafe state because there is no
sequence of resource allocation that guarantees all processes can complete.

Banker's algorithm consists of a Safety algorithm and a Resource request

algorithm.

Types of Banker’s Algorithm

The Banker’s Algorithm is made up of two parts:

1. Safety Algorithm

2. Resource Request Algorithm

1. Safety Algorithm

The safety algorithm checks whether the system is in a safe state-meaning all processes can
complete without causing deadlock.
Steps:

1. Initialize:

• Work = Available (resources currently available)

• Finish[i] = false for all processes (none have finished yet)

2. Look for a process Pi such that:

• Finish[i] = false

• Need[i] ≤ Work (resources required can be satisfied)

3. If such a process is found:

• Pretend to allocate resources to it: Work = Work + Allocation[i]

• Mark the process finished: Finish[i] = true

• Repeat step 2 for remaining processes

4. If all processes are marked finished (Finish[i] = true for all), the system is safe.

Essentially, the algorithm simulates process completion to verify that all processes can finish safely.

2. Resource Request Algorithm

This algorithm decides if a process’s resource request can be granted safely.

Steps:

1. Check if the request exceeds the process’s maximum need: If Request[i] ≤ Need[i], continue;
otherwise, error.

2. Check if resources are available: If Request[i] ≤ Available, continue; otherwise, the process waits.

3. Temporarily allocate the resources:

• Available = Available - Request[i]

• Allocation[i] = Allocation[i] + Request[i]

• Need[i] = Need[i] - Request[i]

4. Run the Safety Algorithm:

• If the new state is safe, grant the request.

• If unsafe, roll back and make the process wait.

In short, the resource-request algorithm ensures resources are only granted if the system remains
safe, preventing deadlock.

Example: Considering a system with five processes P0 through P4 and three resources of type A, B, C.
Resource type A has 10 instances, B has 5 instances and type C has 7 instances. Suppose at time
t0 following snapshot of the system has been taken:
Need Matrix

Need [i, j] = Max [i, j] – Allocation [i, j]

So, the content of Need Matrix is:

Safe State and Safe Sequence Analysis

Applying the Safety algorithm on the given system,

Impact of P1’s Resource Request

We must determine whether this new system state is safe. To do so, we again execute Safety
algorithm on the above data structures.
Deadlock Detection in Operating System

The deadlock detection is a mechanism implemented in operating systems to identify deadlocks. It

works by periodically running a deadlock detection algorithm in the system. It analyzes the current
state of resource allocation and process states to identify if a deadlock has occurred.

There are several algorithms used for deadlock detection, including –

 • Resource Allocation Graph (RAG) Algorithm

• Wait-for Graph Algorithm

• Banker's Algorithm for Deadlock Detection

Resource Allocation Graph (RAG) Algorithm

The Resource Allocation Graph (RAG) is a directed graph that represents the allocation of resources to
processes and the requests made by processes for resources. In this graph, processes and resources
are represented as nodes. Edges from a process to a resource represent a request for that resource,
and edges from a resource to a process represent the allocation of that resource to the process.

To detect deadlock using RAG, the operating system looks for cycles in the graph. If a cycle is found, it
indicates that a deadlock has occurred among the processes involved in the cycle.

The image below shows a Resource Allocation Graph with a deadlock situation –

In this example, Process P1 holds Resource R2 and is waiting for Resource R1 to be ready. Meanwhile,
Process P2 holds Resource R1 and is waiting for Resource R2 to be ready. This creates a cycle in the
graph, P1 -> R1 -> P2 -> R2 -> P1, indicating a deadlock situation.

Wait-for Graph Algorithm

The Wait-for Graph is a simplified version of the Resource Allocation Graph. In this graph, only
processes are represented as nodes, and edges represent the waiting relationships between processes.
An edge from process P1 to process P2 indicates that P1 is waiting for a resource held by P2.

To detect deadlock using the Wait-for Graph, the operating system looks for cycles in the graph. If a
cycle is found, it indicates that a deadlock has occurred among the processes involved in the cycle.

The image below shows corresponding Wait-for Graph for the previous example –
In this wait-for graph, there is a cycle P1 -> P2 -> P1, indicating a deadlock situation between
processes P1 and P2.

Deadlock Recovery in Operating System

Once a deadlock is detected in a system, the operating system take few actions to recover from the
deadlock. The section below discusses the approaches used for deadlock recovery -

1. Process Termination

When a deadlock is detected, one way to recover from it is to terminate one or more processes
involved in the deadlock. The os will terminate the processes one by one until the deadlock is
resolved. The resources held by the terminated processes are then released and can be allocated to
other processes.

For example, consider three processes P1, P2, and P3 involved in a deadlock.

P1 - Holding R1, Waiting for R2

P2 - Holding R2, Waiting for R3

P3 - Holding R3, Waiting for R1

To recover from the deadlock, the operating system can terminate process P1. This will release
resource R1, allowing process P3 to proceed and complete its execution. Once P3 completes, it
releases resource R3, allowing process P2 to proceed and complete its execution as well.

2. Resource Preemption

Another approach to recover from deadlock is to take back the resources from the processes involved
in the deadlock. The is called resource preemption. The preempted resources are then allocated to
other processes involved in the deadlock. This process continues until the deadlock is resolved.

For example, consider the same three processes P1, P2, and P3 involved in a deadlock as mentioned
above.

P1 - Holding R1, Waiting for R2

P2 - Holding R2, Waiting for R3

P3 - Holding R3, Waiting for R1

To recover from the deadlock, the operating system can take back resource R1 from process P1 and
allocate it to process P3. So P3 can proceed and complete its execution. Once P3 completes, it releases
resource R3, so P2 can complete its execution as well. Finally, P1 can get resource R2 and complete its
execution.

Deadlock Ignorance in Operating System

Deadlocks are so rare in modern operating systems that sometimes ignoring them altogether can be
the best strategy. This approach can simplify system design and improve performance by avoiding the
overhead associated with deadlock detection and recovery mechanisms.

The approach of ignoring deadlock is called the ostrich algorithm. This idea came from the myth that
ostriches bury their heads in the sand to avoid a potential danger, an analogy for ignoring a problem
in the hope that it will go away on its own.

When to Ignore a Deadlock

There are several reasons why some operating systems choose to ignore deadlocks −

• Less likely to occur − If the systems is designed properly, the chances of deadlock occurring
can be very low. At any stage if deadlock occurs, it can be resolved by simply restarting the
system or terminating a few processes.

• Cost of Prevention and Detection − The deadlock prevention and detection mechanisms can
add significant overhead to the system. Sometimes, the cost of implementing these
mechanisms may become higher than the cost of dealing with deadlock when it occurs.

• Programmer Responsibility − In some systems, the programmers are needed to design their
applications in a way that minimizes the chances of deadlock occurring. System will kill the
process if it causes deadlock.

• Non Critical Systems − Mostly, deadlock is ignored in non-critical systems like personal
computers. Critical systems like banking systems, flight operating systems, etc., usually
implement deadlock prevention or detection mechanisms.

• Simplicity − Ignoring deadlock can simplify the design of the operating system.

When a Deadlock Can't be Ignored

A deadlock cannot be ignored all the time. In some situations, ignoring deadlock can lead to serious
consequences like data corruption, system crashes, and loss of important information. For example,
imagine a flight control system end up in a deadlock situation during mid air. The operating system will
not respond and may lead to crash landing of the aircraft.

Following are some situations where a deadlock cannot be ignored −

• Critical Systems − Critical systems are the systems where safety and reliability are important.
For example, medical devices, aerospace systems, and financial systems. Here proper deadlock
detection and recovery mechanisms must be implemented.

• High Resource Utilization − If the system has high resource utilization, the chances of deadlock
will also increase. In such cases, ignoring deadlock can lead to performance degradation and
instability of the system.
 • Real-Time Systems − Real-time systems refer to the systems where tasks must be completed
within a specific time frame. So there is no room for delays caused by deadlock. Therefore,
real-time systems must implement deadlock prevention or avoidance mechanisms.

• Long-Running Processes − In systems with long-running processes, the cost of deadlock can
be significant. Therefore, these systems may choose to implement deadlock detection and
recovery mechanisms.

Examples of Deadlock Ignoring Operating Systems

Many modern operating systems choose to ignore deadlock as a strategy for handling it. Some
examples of such operating systems include −

• Windows Operating System − Microsoft Windows operating system generally ignores

deadlock. You might have seen messages like "The program is not responding" or "The
application has stopped working" in your computer. These messages may indicate that a
deadlock may have occurred. You can forcefully close the program or restart your computer to
resolve the issue.

• Linux Operating System − Linux operating system also follows the approach of ignoring
deadlock. Similar to Windows, if a deadlock occurs, the system may become unresponsive.
The user can terminate the process or restart the system.

• macOS Operating System: Apple's macOS operating system also ignores deadlock similarly to
Windows and Linux.
 Memory Management
Memory management is the functionality of an operating system which handles or manages primary
memory and moves processes back and forth between main memory and disk during execution.
Memory management keeps track of each and every memory location, regardless of either it is
allocated to some process or it is free. It checks how much memory is to be allocated to processes. It
decides which process will get memory at what time. It tracks whenever some memory gets freed or
unallocated and correspondingly it updates the status.

Process Address Space

The process address space is the set of logical addresses that a process references in its code. For
example, when 32-bit addressing is in use, addresses can range from 0 to 0x7fffffff; that is, 231 possible
numbers, for a total theoretical size of 2 gigabytes.

The operating system takes care of mapping the logical addresses to physical addresses at the time of
memory allocation to the program. There are three types of addresses used in a program before and
after memory is allocated –

Symbolic addresses

The addresses used in a source code. The variable names, constants, and instruction labels are the
basic elements of the symbolic address space.

Relative addresses

At the time of compilation, a compiler converts symbolic addresses into relative addresses.

Physical addresses

The loader generates these addresses at the time when a program is loaded into main memory.

Virtual and physical addresses are the same in compile-time and load-time address-binding schemes.
Virtual and physical addresses differ in execution-time address-binding scheme.

The set of all logical addresses generated by a program is referred to as a logical address space. The
set of all physical addresses corresponding to these logical addresses is referred to as a physical
address space.

The runtime mapping from virtual to physical address is done by the memory management unit
(MMU) which is a hardware device. MMU uses following mechanism to convert virtual address to
physical address.

Static vs Dynamic Loading

The choice between Static or Dynamic Loading is to be made at the time of computer program being
developed. If you have to load your program statically, then at the time of compilation, the complete
programs will be compiled and linked without leaving any external program or module dependency.
The linker combines the object program with other necessary object modules into an absolute
program, which also includes logical addresses.

If you are writing a Dynamically loaded program, then your compiler will compile the program and for
all the modules which you want to include dynamically, only references will be provided and rest of
the work will be done at the time of execution.
At the time of loading, with static loading, the absolute program (and data) is loaded into memory in
order for execution to start.

If you are using dynamic loading, dynamic routines of the library are stored on a disk in relocatable
form and are loaded into memory only when they are needed by the program.

Static vs Dynamic Linking

As explained above, when static linking is used, the linker combines all other modules needed by a
program into a single executable program to avoid any runtime dependency.

When dynamic linking is used, it is not required to link the actual module or library with the program,
rather a reference to the dynamic module is provided at the time of compilation and linking. Dynamic
Link Libraries (DLL) in Windows and Shared Objects in Unix are good examples of dynamic libraries.

Swapping
Swapping is a mechanism in which a process can be swapped temporarily out of main memory (or
move) to secondary storage (disk) and make that memory available to other processes. At some later
time, the system swaps back the process from the secondary storage to main memory.

Though performance is usually affected by swapping process but it helps in running multiple and big
processes in parallel and that's the reason Swapping is also known as a technique for memory
compaction.

The total time taken by swapping process includes the time it takes to move the entire process to a
secondary disk and then to copy the process back to memory, as well as the time the process takes
to regain main memory.
Let us assume that the user process is of size 2048KB and on a standard hard disk where swapping
will take place has a data transfer rate around 1 MB per second. The actual transfer of the 1000K
process to or from memory will take

2048KB / 1024KB per second

= 2 seconds

= 2000 milliseconds

Now considering in and out time, it will take complete 4000 milliseconds plus other overhead where
the process competes to regain main memory.

In the context of operating systems, memory allocation refers to the process of assigning blocks of
memory to various programs and processes running on a computer. The blocks of memory can be
allocated continuously or non-continuously. Based on this, we have two types of memory allocation
techniques: contiguous memory allocation and non-contiguous memory allocation.

Contiguous Memory Allocation

Contiguous memory allocation as the name suggests, allocates a single continuous block of memory
to a process. The block of memory is allocated to a process is enough to hold the entire process. This
means that the process can access all its memory locations without any interruptions.

The image below shows the main memory allocates storage to three processes P1, P2, and P3 using
contiguous memory allocation −

In the image above, the process P1 is allocated 3 blocks of memory (F1, F2, and F3). P2 is allocated 2
blocks of memory (F5 and F6). Similarly, P3 is allocated 1 block of memory (F8). There some gaps in
between the allocated memory blocks ( at F4 and F7 ). How these gaps are formed even though we
are continuously allocating memory? To understand this, read our chapter on Fragmentation.

We have two types of contiguous memory allocation techniques −

• Fixed Partitioning (Static)

• Dynamic Partitioning (Variable)

Fixed Partitioning in Contiguous Memory Allocation

The fixed partitioning or static partitioning is a memory allocation technique where the main
memory is divided into partitions of fixed sizes. Each partition can hold exactly one process.
When a new process loaded into memory, it is allocated a partition of fixed size. If the
process is smaller than the partition size, the remaining memory in the partition will be
wasted. If the process is larger than the partition size, it cannot be loaded into memory.
The image below shows internal fragmentation happening in main memory during fixed
partitioning –

As the image above shows, one of main drawbacks of fixed partitioning is internal
fragmentation. We can see that process are not using the entire allocated memory. This will
lead to a situation where even though there is enough total memory available, it may not be
possible to allocate memory to a new process, because the available memory may not be
contiguous.
Dynamic Partitioning in Contiguous Memory Allocation
The dynamic partitioning or variable partitioning is a memory allocation technique where the main
memory is divided into partitions of varying sizes depending on the size of the processes being loaded
into memory. When a new process is loaded into memory, it is allocated to the first available partition
that is large enough to hold the process. If no such partition is available, the process has to wait until
a partition becomes free.

The image below shows external fragmentation happening in main memory during dynamic
partitioning –

The major issue with dynamic partitioning is external fragmentation. In the image above, we can see
that there are some gaps in the memory after allocating and deallocating memory to various
processes. This situation happens when a process is terminated from memory, and it's neighboring
processes are still running.

These gaps will add up over time as more processes are loaded and unloaded from memory. In such
case, you need to restart the system to make the main memory free again.
Advantages of Contiguous Memory Allocation
The contiguous memory allocation technique is preferred in some scenarios due to the following
advantages −

• Simplicity − Contiguous memory allocation is simple to implement and manage. The operating
system can easily keep track of the memory blocks allocated to each process.

• Fast Access − The entire process is stored in a single block of memory. No any calculation is
needed to find the memory location of a process. So overall access time is faster.

• Low Overhead − Contiguous memory allocation has low overhead as there is no need for
complex data structures to manage memory allocation.

Disadvantages of Contiguous Memory Allocation

Even though contiguous memory allocation is simple and fast, it comes with some drawbacks −

• Wastage of Memory − During contiguous memory allocation, there are gaps created in
memory due loading and unloading of processes. This can lead to wastage of memory.

• Fragmentation − Contiguous memory allocation can lead to internal and external

fragmentation. This reduce the overall efficiency of memory usage.

• Limited Flexibility − Contiguous memory allocation is not suitable for virtual memory systems
and in the case where process are larger than the available memory itself.

Non-Contiguous Memory Allocation

Non-contiguous memory allocation is a memory allocation technique where a process is allocated
multiple blocks of memory at different locations in the main memory. Sometimes the entire process
may not be stored in the main memory. i.e., some parts of the process may be stored in the secondary
storage (like hard disk). When the process needs to access a part of the program that is not in the main
memory, the OS will immediately swap that part to the main memory.

The image below shows the main memory allocating storage to three processes P1, P2, and P3 using
non-contiguous memory allocation −

In the image above, the process is divided into pages (Page 1, Page 2, Page 3, ... page 7). The first 2
pages are loaded into the physical memory (RAM), and rest are stored in the hard disk.
We have two types of non-contiguous memory allocation techniques −

• Paging

• Segmentation

Paging in Non-Contiguous Memory Allocation

Paging is a memory management technique used by modern operating systems to manage the
allocation of memory to processes. In this technique, the physical memory (i.e., the RAM) is divided
into blocks of fixed size called frames, and the logical memory (i.e., the memory where the process is
stored) is divided into blocks of the same size called pages. When a process is executed, its pages are
loaded into available frames in the physical memory.

The image below shows working of paging in operating system −

• The idea behind implementing paging is to store the part of the program that is currently in
use in the physical memory (RAM) and keep the rest of the program in the hard disk.

• When the process needs to access a part of the program, the OS will check page table to see
if the page is in the physical memory or not.

• If the page is in the physical memory, the CPU can directly access it. If not, a page fault will
occur. So the OS will load the page from the hard disk into the physical memory and update
the page table.
 • While loading a new page into the physical memory, if the space is full, the OS will use a page
replacement algorithm to decide which page to remove and make space for the new page in
RAM.

Segmentation in Non-Contiguous Memory Allocation

Segmentation is another memory management technique used by modern operating systems to
manage the allocation of memory to processes. Here, the logical memory (i.e., the memory where the
process is stored) is divided into variable-sized segments based on the logical structure of a program,
such as code segment, data segment, stack segment, etc. The physical memory (i.e., the RAM) is also
divided into variable-sized blocks called segments. When a process is executed, its segments are
loaded into available segments in the physical memory.

The main difference between paging and segmentation is that in paging, the memory is divided into
fixed-size blocks. In segmentation, the memory is divided into blocks of variable size based on the
logical structure of a program.

Features of Segmentation

The key features of segmentation are −

• Logical division of memory − Segments represent meaningful units like code, stack, data, or
modules.

• Variable-sized divisions − Segments can have different lengths, depending on the program's
requirements.

• No internal fragmentation − Since segments are not fixed in size.

• External fragmentation − Can occur when free memory is divided into small scattered blocks.

• Protection and sharing − Different segments can have access rights (read, write, execute) and
can be shared among processes.

Advantages of Non-Contiguous Memory Allocation

Most of the modern operating systems uses non-contiguous memory allocation technique. It have
several advantages over contiguous memory allocation technique. Some of the key advantages are −

• Reduced Memory Wastage − The chances of fragmentation are reduced in non-contiguous

memory allocation. This will eliminate memory wastage issues and improve overall memory
utilization.

• Run Large Processes − By implementing non-contiguous memory allocation, the operating

system can run processes that are larger than the available physical memory (RAM). This is
done by storing some parts of the process in the secondary storage (like hard disk).

• Flexibility − Non-contiguous memory allocation provides more flexibility in memory

management.

Disadvantages of Non-Contiguous Memory Allocation

Even though non-contiguous memory allocation has several advantages, it also comes with some
drawbacks. Some of the key disadvantages are −
 • Complexity − Non-contiguous memory allocation is more complex to implement and manage
compared to contiguous memory allocation. The operating system needs to maintain data
structures like page tables and segment tables to keep track of the memory blocks.

• Slower Access Time − Due to repeated swapping of pages/segments and additional lookups in
page/segment tables, the overall access time may be slower.

• Overhead − Non-contiguous memory allocation has higher overhead due to the need for
additional data structures and algorithms to manage memory allocation.

The First Fit Algorithm is a memory allocation strategy used in contiguous memory allocation systems.
This chapter will explain the First Fit Algorithm, how it works, and its implementation in operating
systems.

What is First Fit Algorithm?

The First Fit Algorithm allocates the first available block of memory that is large enough to
accommodate the process. Meaning, the algorithm scans the memory from the starting and allocates
the first block that is big enough for the processes need. If no suitable block is found, the process is
marked as "Not Allocated". So the process needs to wait until a suitable block becomes free.

Steps to Implement First Fit Algorithm

The First Fit Algorithm can be implemented using the following steps:

• Initialize a pointer to keep track of the last allocated block.

• For each process, start searching for a suitable hole from the beginning of the memory.

• If a suitable hole is found, allocate the process to that hole.

• On reaching the end of the memory, if no suitable hole is found, mark the process as "Not
Allocated".

Advantages of First Fit Algorithm

The First Fit Algorithm is considered as a simple and efficient memory allocation strategy. Some of its
advantages are:

• Speed − The First Fit Algorithm is generally faster than other algorithms like Best Fit and Worst
Fit because it allocates the first suitable block it finds.

• No Complex Data Structures − The First Fit Algorithm does not require any complex data
structures or any other complex calculations.

• Reduced Fragmentation − The First Fit Algorithm leaves larger gaps in memory compared to
other algorithms. This will help in reducing fragmentation.

Disadvantages of First Fit Algorithm

Sometimes, the First Fit Algorithm is not preferred, due to the following drawbacks −

• Wasted Memory − The First Fit Algorithm can lead to wastage of memory as it may leave large
unusable gaps in memory.
 • Poor Utilization − The First Fit Algorithm is considered as worst in term of memory utilization
compared to other algorithms like Best Fit and Worst Fit.

• Not Optimal − The First Fit Algorithm does not guarantee optimal memory allocation. It may
lead to situations where a process cannot be allocated memory even though there is enough
total memory available.

What is Next Fit Algorithm?

The Next Fit Algorithm is a memory allocation strategy similar to the First Fit Algorithm. In Next Fit,
the search for a free memory block starts from the location of the last allocated block, instead of
starting from the beginning of the memory.

The algorithm scans for the next available hole that is large enough to accommodate the process. If a
suitable hole is found, then the process is allocated to that hole. If no suitable hole is found by the end
of the memory, then the searching pointer moves to the beginning of the memory and continues
searching until it reaches the starting point of the search.

Steps to Implement Next Fit Algorithm

The Next Fit Algorithm can be implemented using the following steps −

• Initialize a pointer to keep track of the last allocated block.

• For each process, start searching for a suitable hole from the last allocated block.

• If a suitable hole is found, allocate the process to that hole and update the pointer to the
current block.

• If no suitable hole is found by the end of the memory, move to the beginning of the memory
and continue searching until reaching the starting point of the search.

• If no suitable hole is found after a complete scan, mark the process as "Not Allocated".

Advantages of Next Fit Algorithm

The Next Fit Algorithm is considered as an improvement over the First Fit Algorithm and have several
advantages −

• Reduced Search Time − By starting the search from the last allocated block, Next Fit can reduce
the time taken to find a suitable hole for allocation.

• Better Memory Utilization − Next Fit can ensure maximum utilization of memory by avoiding
the allocation of large holes to small processes.

• Less Fragmentation − Next Fit can help in reducing fragmentation.

Disadvantages of Next Fit Algorithm

Sometimes, the Next Fit Algorithm is not preferred, because of −

• Longer Wait Times − In some cases, Next Fit may lead to longer wait times for processes to be
allocated memory.
 • Not Always Optimal − Next Fit may not always find the best fit for a process. In some cases, it
may skip over suitable holes that are located before the last allocated block.

What is Best Fit Algorithm?

The Best Fit Algorithm allocates searches the entire memory to find the smallest available block that
is large enough to accommodate the process. This means that, the algorithm looks for the block that
will leave the least amount of unused space after allocation. The main aim of the Best Fit Algorithm is
reduce fragmentation and wastage of memory.

Example

Consider the following example where we have five memory blocks of sizes 6, 5, 50, 20, and 14 units,
and five processes of sizes 4, 10, 15, 20, and 23 units respectively. We will allocate memory to these
processes using the Best Fit Algorithm.

When process 4 comes to memory allocation, it is allocated to block of size 5, as it is the smallest block
that can accommodate the process. Similarly, process 10 is allocated to block of size 14, and process
15 is allocated to block of size 20.

The process size 23 cannot be allocated as there is no block large enough to accommodate it.

The Best Fit Algorithm can be implemented using the following steps −

• Initialize a pointer to keep track of the last allocated block.

• For each process, search the entire memory to find the smallest block that is large enough to
hold the process.

• If a suitable block is found, allocate the process to that block.

• After searching the entire memory, if no suitable block is found, mark the process as "Not
Allocated".

Advantages of Best Fit Algorithm

The Best Fit Algorithm have the following advantages −

• Reduced External Fragmentation − By allocating the smallest possible block to a process, the
Best Fit Algorithm helps in reducing external fragmentation.

• Efficient Memory Utilization − The Best Fit Algorithm ensures that memory is utilized
efficiently by minimizing the amount of wasted space after allocation.

• Best for Small Processes − The Best Fit Algorithm is considered to be more suitable for small
processes.

Disadvantages of Best Fit Algorithm

The Best Fit Algorithm has some drawbacks −

• High Search Time − The Best Fit Algorithm requires searching the entire memory for the
smallest suitable block, which can increase allocation time.
 • Fragmentation − Even though it reduces external fragmentation, it can cause internal
fragmentation. Because processes may not fully utilize the allocated blocks.

• Not Suitable for Large Processes − The Best Fit Algorithm may struggle to find suitable blocks
for larger processes. This leads to more "Not Allocated" statuses.

What is Worst Fit Algorithm?

The Worst Fit Algorithm is just the opposite of the best fit algorithm. Here, the memory manager
allocates the largest available block to the process that requests memory. The main idea behind this
approach is to leave smaller holes that may be more suitable for future processes. Sometimes, if all
the available blocks are smaller than the process size, then the process is marked as "Not Allocated".
So the process needs to wait until a suitable block becomes available.

Example

Consider the following example where we have five memory blocks of sizes 6, 5, 50, 20, and 16 units,
and five processes of sizes 4, 10, 15, 20, and 23 units respectively. We will allocate memory to these
processes using the Worst Fit Algorithm.

When process 1 comes to memory allocation, it is allocated to block of size 50, as it is the largest block
available. Similarly, process 10 is allocated to block of size 20, and process 15 is allocated to block of
size 16.

The process sizes 20 and 23 cannot be allocated as there is no block large enough to accommodate
them.

Steps to Implement Worst Fit Algorithm

The Worst Fit Algorithm can be implemented using the following steps −

• Initialize a pointer to keep track of the last allocated block.

• For each process, search the entire memory to find the largest available block that is large
enough to hold the process.

• If a suitable block is found, allocate the process to that block.

• After searching the entire memory, if no suitable block is found, mark the process as "Not
Allocated".

Advantages of Worst Fit Algorithm

The Worst Fit Algorithm have following advantages −

• Reduces External Fragmentation − Worst Fit Algorithm allocates the largest available block to
a process. This way it leaves smaller holes that may be more suitable for future processes.

• Simplicity − The Worst Fit Algorithm is simple to implement and understand.

• Better Utilization of Memory − The worst Fit Algorithm help in better utilization of memory.
Disadvantages of Worst Fit Algorithm

Worst Fit Algorithm also comes with some disadvantages:

• Increased Internal Fragmentation − By allocating the largest block to a process, most of the
time it leads memory wastage and internal fragmentation.

• Slower Allocation − The Worst Fit Algorithm requires searching the entire memory to find the
largest block. This process can be slower compared to other algorithms like First Fit.

• Not Suitable for All Scenarios − The Worst Fit Algorithm may not be suitable for all types of
memory allocation patterns.

Fragmentation in a memory is a condition where the available memory is divided into small and non-
contiguous blocks after allocating and deallocating memory to various processes. In simpler words,
fragmentation means there are some gaps in the memory after running multiple processes at random
memory locations.

Fragmentation can lead to wastage of memory. Even though there is enough total memory available,
it may not be possible to allocate memory to a new process due to fragmentation. The image below
shows fragmentation happening in main memory −

This is an example of external fragmentation. Here the process P1 is allocated three frames of memory
(F1, F2, and F3). P2 is allocated two frames of memory (F5 and F6). Similarly, P3 is allocated F8 frame.

Now, if a new process P4 requires three frames of memory, it cannot be allocated memory even
though there are three free frames (F4, F7, and F9) available in the memory. This is because these free
frames are not contiguous.

Types of Fragmentation

Fragmentation can be classified into two types −

• Internal Fragmentation

• External Fragmentation
Internal Fragmentation

Internal fragmentation occurs when a process gets more memory than it actually needed. The
operating system allocates memory in fixed size blocks or frames. If a process uses only a part of the
allocated memory, then some memory will be wasted. This can happen for large number of processes
running in the system, which will lead to wastage of large amount of memory.

The following image shows internal fragmentation taking place in main memory −

In the above image, the process P1 is allocated F1, F2, and F3 frames of memory. But it is only using
F1 and F2 frames. The F3 frame is wasted because the process does not need it. Similarly, the F6, F7,
and F9 frames are also wasted because the processes P2 and P3 are holding them.

Causes of Internal Fragmentation

Internal fragmentation can occur due to the following reasons −

• Fixed Size Memory Allocation − Some operating systems allocate memory in fixed size blocks
or frames. If a process requires less memory than the allocated block size, then the remaining
memory will be wasted. For example, consider a system that allocates memory to all the
processes in blocks of 4 KB. If a process requires 6 KB of memory, then OS should allocate 8 KB
of memory (2 blocks) to it. So 2 KB of memory will be wasted.

• Management Overheads − Some systems reserve a part of the allocated memory for purpose
like bookkeeping and management. Sometimes this reserved memory may not be used by the
process.

• Memory Alignment − Some systems require memory to be aligned to certain boundaries (like
4-byte or 8-byte boundaries). This can lead to wastage of memory and internal fragmentation.

External Fragmentation

External fragmentation refers to gaps generated in memory when multiple processes are loaded and
unloaded from memory. To understand this, suppose that a process P1 is allocated with 3 frames of
memory (F1, F2, and F3). P2 allocated with 1 frame F4 and P3 allocated with 2 frames F5 and F6. Now,
if P2 is terminated, then the frame F4 will be free. But this introduced a gap in memory between the
memory allocated to P1 and P3.

The following image shows how external fragmentnation takes place −

The gaps generated in memory will add up over time as more processes are loaded and unloaded from
memory. This can lead to a situation where even though there is enough total memory available, the
system will not be able to allocate memory to a new process. Because the available memory is
scattered in small non-contiguous blocks.

Causes of External Fragmentation

External fragmentation can occur due to the following reasons −

• Dynamic Memory Allocation − Some systems use dynamic memory allocation. In such
systems, memory is allocated to processes when they request it and deallocated when they
are done. This can cause fragmentation as there is no rule to allocate memory.

• Process Termination − When a process is completed, it will be terminated from memory. This
will create gaps in memory, if the terminated process was allocated memory in between other
processes.

• Variable Size Memory Allocation − Some systems allocate memory to processes in variable
sizes. This can lead to fragmentation as there is no rule to allocate memory. For example, if a
process requires 5 KB of memory, then OS should allocate 8 KB of memory (2 blocks of 4 KB)
to it. So 3 KB of memory will be wasted.

How to Reduce Fragmentation?

There are several techniques to reduce fragmentation in memory. Some of the common techniques
are:
 • Compaction − Compaction is a technique where the operating system rearranges the memory
contents to place all free memory together in one large block. This will remove the gaps in
memory and reduce fragmentation.

• Paging − Paging is a memory management technique that uses virtual memory to store the
process and then maps it to frames of physical memory. This will eliminate external
fragmentation as the process can be stored in non-contiguous frames of memory.

• Segmentation − Segmentation divides memory into variable sized segments based on the
logical structure of a program. This will reduce fragmentation as the segments can be allocated
in non-contiguous memory locations.

Virtual memory is a memory management technique used by modern operating systems to create
an illusion of a having a large and continuous memory space, even when the physical memory (RAM)
is less. A part of the hard disk is used as the physical memory to store data and programs that are not
currently in use. The operating system will store the mapping between the virtual addresses and
physical addresses in a data structure called page table.

The image below shows how operating system splits the process between physical memory (RAM) and
hard disk using virtual memory −

In the image above, the process is divided into pages (Page 1, Page 2, Page 3, ... page 7). The first 2
pages are loaded into the physical memory (RAM), and rest are stored in the hard disk. When the
process needs to access a page that is not in the physical memory, the OS will swap the required
page from the hard disk into the physical memory.

How Virtual Memory Works?

The steps below explain how virtual memory works in Paging systems −
 • The idea behind implementing virtual memory is to store the part of the program that is
currently in use in the physical memory (RAM) and keep the rest of the program in the hard
disk.

• When the process needs to access a part of the program, the OS will check page table to see
if the page is in the physical memory or not.

• If the page is in the physical memory, the CPU can directly access it. If not, a page fault will
occur. So the OS will load the page from the hard disk into the physical memory and update
the page table.

• While loading a new page into the physical memory, if the space is full, the OS will use a page
replacement algorithm to decide which page to remove and make space for the new page in
RAM.

Types of Virtual Memory

Modern operating systems use two types of techniques to create virtual memory −

• Paging

• Segmentation

Virtual Memory in Paging

Paging is a memory management technique used by modern operating systems to manage the
allocation of memory to processes. In this technique, the physical memory (i.e., the RAM) is divided
into blocks of fixed size called frames, and the logical memory (i.e., the memory where the process is
stored) is divided into blocks of the same size called pages. When a process is executed, its pages are
loaded into available frames in the physical memory.

The image below shows working of paging in operating system −

Virtual Memory in Segmentation

Segmentation is another memory management technique used by modern operating systems to

manage the allocation of memory to processes. Here, the logical memory (i.e., the memory where the
process is stored) is divided into variable-sized segments based on the logical structure of a program,
such as code segment, data segment, stack segment, etc. The physical memory (i.e., the RAM) is also
divided into variable-sized blocks called segments. When a process is executed, its segments are
loaded into available segments in the physical memory.

The main difference between paging and segmentation is that in paging, the memory is divided into
fixed-size blocks. In segmentation, the memory is divided into blocks of variable size based on the
logical structure of a program.

Features of Segmentation

The key features of segmentation are −

• Logical division of memory − Segments represent meaningful units like code, stack, data, or
modules.

• Variable-sized divisions − Segments can have different lengths, depending on the program's
requirements.

• No internal fragmentation − Since segments are not fixed in size.

• External fragmentation − Can occur when free memory is divided into small scattered blocks.

• Protection and sharing − Different segments can have access rights (read, write, execute) and
can be shared among processes.

Advantages of Virtual Memory

The benefits of using virtual memory are −

• Increased memory capacity − Virtual memory creates an illusion of having a large memory
space. This will help to run applications that are larger than the physical memory (RAM)
available in the system.

• Efficient memory Usage − Virtual memory improves the efficiency of memory usage by
loading only the required pages into physical memory. This will reduce wastage of memory
and improve system performance.

• Isolation of Memory − Virtual memory allocates a unique address space to each process. This
will improve the safety and security of the system by preventing one process from accessing
the memory of another process.

• Quick swapping of pages − OS swap pages between physical memory and disk quickly, such
that the process execution is just like it is running in physical memory.

Limitations of Virtual Memory

The virtual memory also comes with limitations such as −

 • Complexity − It is very difficult to implement virtual memory systems. The operating system
needs to manage the mapping between virtual addresses and physical addresses, also handle
page faults and page replacement. Only experienced developers can handle this complexity.

• Performance Issues − Accessing data from the hard disk is much slower than accessing data
from RAM. So, if a process frequently accesses pages that are not in physical memory, it can
lead to slow running of the process.

• Thrashing − Thrashing occurs when the system spends more time swapping pages in and out
of physical memory than executing the process. This can happen when the size of RAM is very
small compared to what the process needs.

Applications of Virtual Memory

Most of the modern operating systems use virtual memory technique to manage memory system.
Some of the popular operating systems that use virtual memory are −

• Microsoft Windows

• Linux

• macOS

• Unix

• Android

Virtual Memory vs Physical Memory

The table below shows the key differences between virtual memory and physical memory –

Criteria Virtual Memory Physical Memory

Virtual memory is a memory management technique Physical memory is the actual hardware
Definition that creates an illusion of having a large and continuous component (RAM) that stores data and
memory space. programs currently in use.

Storage It uses both RAM and a portion of the hard disk. The part It is located on the computer's motherboard as
Location of process not currently in use is stored on the hard disk. RAM modules.

The capacity is limited to the size of the installed

Capacity High capacity as it combines RAM and hard disk space.
RAM in the system.

It uses techniques like paging and segmentation to

Management It is managed by the operating system.
manage memory allocation to processes.
What is Segmentation?

Segmentation is a memory management technique that divides a program's memory into different
segments based on the logical divisions of the program. Each segment is used to store a specific part
of the program, such as functions, code, or variables. This is different from paging, where memory is
divided into fixed-size blocks. Here, the segments match the user's logical view of a program (functions,
arrays, modules) to physical memory.

The image below shows how segmentation works in an operating system −

In the image, there are three segments - Segment 0, Segment 1, and Segment 2 in logical memory.
Each segment has a base address and unit size in physical memory, these values are stored in
the segment table. When a program accesses a memory location, the operating system uses the
segment table to translate the logical address into a physical address.

For example, the base address of Segment 0 is 500, and the unit size is 600. So the physical address for
logical address (0, 600) will be calculated as −

Physical Address = Base Address + Offset

= 500 + 600

= 1100

Features of Segmentation

Here are some key features related to segmentation −

• Variable sized segments: Each segment can have a different size based on the program's
requirements. Each segments represent meaningful units like code, stack, data, or modules.

• Logical Addressing: In segmentation, a logical address is represented as a tuple (segment

number, offset) where the segment number identifies the segment and the offset specifies the
location within that segment.

• Segment Table: The operating system maintains a segment table that maps segment numbers
to physical memory addresses. Each entry in the segment table contains the base address and
limit (size) of the segment.
 • Protection and Sharing: Different segments can have access rights (read, write, execute) and
can be shared among processes.

• Fragmentation: Segmentation can lead to external fragmentation, because of loading and

unloading of segments of variable sizes. But it does not suffer from internal fragmentation
since segments are not fixed in size.

How Segmentation Works?

• Before a program is loaded into memory, the operating system divides it into segments based
on its logical structure. For example, a program may be divided into code segment, data
segment, stack segment, etc.

• When a program is executed, the operating system allocates memory for each segment in
the physical memory (RAM) based on the size of the segment.

• The operating system keeps a data structure called the segment table that maps each segment
number to its corresponding base address and limit in physical memory.

• When a program accesses a memory location, it provides a logical address consisting of

a segment number and an offset. The operating system uses the segment table to translate
the logical address into a physical address by adding the base address of the segment to the
offset.

• If the offset exceeds the limit of the segment, then a segmentation fault occurs. This will
prevent the program from accessing memory outside its allocated segment.

The Segment Table

The segment table is a data structure used by the operating system to keep track of the segments
allocated to a process. It maps two-dimensional logical addresses into one-dimensional physical
addresses. Each entry in the segment table contains the following information −

• Segment Number − A unique identifier for each segment.

• Base Address − The starting physical address of the segment in memory.

• Limit − The size of the segment, which defines the maximum offset that can be accessed within
the segment.

Example

Here is an example of a segment table −

Segment Number Base Address Limit

0 1000 500

1 2000 300
 2 3000 400

Paging vs Segmentation

Here is a comparison between paging and segmentation −

Feature Paging Segmentation

Memory management technique that divides Memory management technique that divides
Definition memory into fixed-size pages that are mapped memory into variable-size segments based on the
to physical frames. logical divisions of a program.

Division of
Fixed-size pages Variable-size segments
Memory

Addressing One-dimensional (page number, offset) Two-dimensional (segment number, offset)

Fragmentation Likely to suffer from internal fragmentation May suffer from external fragmentation

Matches logical structure of program, i.e., functions,

Logical Structure No relation to logical structure of program
modules etc

Protection and
Less protection and sharing capabilities Better protection and sharing capabilities
Sharing

Pros and Cons of Segmentation

The segmentation technique following advantages −

• Logical Organization − Segmentation allows programs to be divided into logical units. This
makes it easier to manage and understand the program structure.

• Protection and Sharing − Sometimes in programs, different segments can have different
access rights. Segmentation can ensure this by various segments having different protection
levels.

• Dynamic Growth − Segments can grow or shrink dynamically as needed. This is useful for data
structures like stacks and heaps.

However, segmentation also comes with following drawbacks −

• External Fragmentation − When segments are loaded and unloaded from memory for long
time, the memory blocks become fragmented. This can leads to wastage of memory.

• Complexity − The management of variable-sized segments can be more complex than fixed-
size pages, leading to increased overhead in the memory management system.

• Size Limitations − Each segment has a size limit, which may restrict the amount of memory
that can be allocated to a particular segment.
The kernel is core of the operating system and it needs some amount of memory to perform its
functions, such as managing processes, handling interrupts, and managing hardware resources. So it
is duty of the operating system to allocate memory to the kernel and other system components.

There are two main techniques for allocating kernel memory: Buddy System and Slab Allocation.

What is Buddy System?

The Buddy System refers to a memory allocation technique that divides large block of memory into
smaller powers of two sized blocks to satisfy memory requests. This means that when a process
requests memory, the Buddy System will find the smallest block of memory that is a power of two and
is large enough to satisfy the request. If the available block is larger than the requested size, it will be
split into two smaller blocks, called buddies. This spilt will happen until a block of the appropriate size
is obtained.

To understand better, consider the following image −

In the image the process requests 10 bytes of memory and memory block available is of size 128 bytes,
then the Buddy System will divide the 128 bytes block into two 64 bytes blocks, then one of the 64
bytes blocks will be divided into two 32 bytes blocks, and so on until a block of size 16 bytes is
obtained. Finally, the 16 bytes block will be allocated to the process. Further division is not possible as
the next power of two is 8 bytes which is less than the requested size of 10 bytes.

Features of Buddy System

• Simple − The Buddy System divides memory into blocks of sizes that are powers of two (e.g.,
1, 2, 4, 8, 16, etc.). This simplifies the allocation and deallocation process.

• Buddies − Each block of memory has a "buddy" block of the same size. When a block is freed,
the system checks if its buddy is also free. If both are free, they are merged back into a larger
block.

• Fragmentation − The Buddy System can suffer from internal fragmentation. Because the
memory requests are not always powers of two. So the allocated block may be larger than the
requested size.
 • Quick Allocation − The Buddy System are designed to provide fast memory allocation and
deallocation. The splitting and merging of blocks can be done quickly.

• Memory Utilization − The Buddy System can lead to better memory utilization compared to
other allocation methods.

What is Slab Allocation?

Slab Allocation is a memory management technique used by kernel of modern operating systems such
as Linux to efficiently allocate memory for frequently used objects like file descriptors, inodes, and
network buffers. The idea behind slab allocation is to introduce a cache for each type of object that
the kernel frequently uses. Each cache consists pre allocated memory chunks called slabs. These slabs
are divided into smaller fixed-size blocks called objects. The object can be quickly allocated and
deallocated from the slab cache without causing fragmentation and memory wastage.

The image below shows the hierarchy of slab allocation in an operating system −

Structure of Slab Allocation

As depicted in the image, slab allocation consists of three main components −

• Cache − A cache is a group of slabs that store objects of the same type. There different caches
are created for different types of objects used by the kernel.

• Slab − A slab is a contiguous block of memory that contains multiple objects of the same type.
Each slab is divided into smaller fixed-size blocks called objects.

• Object − An object is a fixed-size block of memory that is allocated from a slab. Each object
maps to a specific data structure used by the kernel.

Each of the slab can be in one of the following three states: Full - all objects are allocated, Partial -
some objects are allocated, and Empty - no objects are allocated. The slab allocator uses partial slabs
first to satisfy allocation requests. This way fragmentation is minimized. If no partial slabs are available,
a new slab is created from the buddy system.

Paging is a memory management technique used by modern operating systems to manage the
allocation of memory to processes. In this technique, the physical memory (i.e., the RAM) is divided
into blocks of fixed size called frames, and the logical memory (i.e., the memory where the process is
stored) is divided into blocks of the same size called pages. When a process is executed, its pages are
loaded into available frames in the physical memory.

The image below shows working of paging in operating system –

Key Concepts Related to Paging

Here are some key concepts related to paging −

• Logical Address Space − The logical address space is the set of all logical addresses generated
by a process in hard disk. It is divided into pages.

• Physical Address Space − The physical address space refers to the set of all physical addresses
in the main memory (RAM). It is divided into frames.

• Page Table − A page table is a data structure used by the operating system to direct logical
addresses to physical addresses. It stores information such as the location of each page in the
physical memory.

• Page Number − The page number is the index of a page in the logical address space.

• Frame Number − The frame number is the index of a frame in the physical address space.

• Page Size − The page size is the size of each page and frame. It is usually represented as a
power of 2, For example, 4KB, 8KB, etc.
Address Translation in Paging

When a process generates a logical address, the operating system uses the page table to translate it
into a physical address. This process is known as address translation. The logical address is divided
into two parts −

• The page number

• The offset within the page

The page number is used to search the corresponding frame number in the page table, and
the offset is the location within that frame. The physical address is then calculated by combining the
frame number and the offset. Here is the formula to calculate the physical address:

Physical Address=(Frame Number × Page Size )+Offset

Page Table in Paging

The page table is a data structure inside the operating system that maps logical addresses and physical
addresses. Each entry in the page table contains the following information:

• Frame Number − The frame number refer to the location of the page in physical memory.

• Valid/Invalid Bit − This bit is used to know if the page is in memory (valid) or not (invalid).

• Protection Bits − Bits that is used to indicate the permission of accessing the page (e.g., read,
write, execute).

• Dirty Bit − A bit that is used to indicate if the page has been modified since it was loaded into
memory.

• Reference Bit − A bit that is used to indicate whether the page has been accessed recently.

Example: Structure of a Page Table

Consider a system with following configuration −

• System A 32-bit system with a 4KB (212 bytes) page size.

• Logical Address Space 232 bytes (4GB).

• Physical Address Space 230 bytes (1GB).

• Number of Pages 232 / 212 = 220 pages.

In this case, the page table will have 220 entries. Each entry in the page table will contain the frame
number, valid/invalid bit, protection bits, dirty bit, and reference bit. Consider that each entry takes 4
bytes, the total size of the page table will be −

Size of Page Table=Number of Pages×Size of Each Entry

=220 ×4 bytes=4 MB

Address Translation − Suppose a virtual address like 0 × 100000 is generated by a process. The page
number can be calculated as:
 𝑉𝑖𝑟𝑡𝑢𝑎𝑙 𝐴𝑑𝑑𝑟𝑒𝑠𝑠 0𝑥100000
𝑃𝑎𝑔𝑒 𝑁𝑢𝑚𝑏𝑒𝑟 = =
𝑃𝑎𝑔𝑒 𝑆𝑖𝑧𝑒 0𝑥1000

= 0x 100

The offset within the page can be calculated as −

Offset=Virtual Address mod Page Size

=0×100000 mod 0×1000=0×000

So, the virtual address 0x100000 refers to,

• Page Number: 0x100 (256 in decimal)

• Offset: 0x000 (0 in decimal)

The operating system will look up the page table entry for page number 0x100 to find the
corresponding frame number. If the page is in memory (valid), it will get the frame number and
calculate the physical address using the formula mentioned earlier.

Translation Lookaside Buffer (TLB)

The Translation Lookaside Buffer (TLB) is a high speed cache inside CPU that stores recent values of
translation made from virtual addresses to physical addresses. This will help to reduce the time taken
for address translation, as it will store the most frequently used page table entries.

When a virtual address is generated, the TLB is checked first. If the entry is found in the TLB (a TLB
hit occurs), the physical address can be obtained directly from the TLB. If the entry is not found in the
TLB (a TLB miss occurs), the page table is used to get the frame number, and then the TLB is updated
with this new entry.

Effective Access Time (EAT)

The Effective Access Time (EAT) is the average time taken to access a memory location, by considering
both TLB hits and TLB misses. It can be calculated using the following formula −

𝐸𝐴𝑇 = (𝐻 × 𝑇) + (𝑀 × (𝑇 + 𝑀. 𝐴. 𝑇))

Where,

• H = TLB Hit Ratio − The percentage of memory accesses that leads to TLB hit.
 • M = TLB Miss Ratio − The percentage of memory accesses that leads to TLB miss (1 - TLB Hit
Ratio).

• T = TLB Access Time − The time taken to access the TLB.

• M.A.T = Memory Access Time − The time taken to access the main memory.

For example, if the TLB hit ratio is 90%, TLB access time is 10 nanoseconds, and memory access time
is 100 nanoseconds, the EAT can be calculated as follows −

𝐸𝐴𝑇 = (0.9 × 10 𝑛𝑠) + (0.1 × (10 𝑛𝑠 + 100 𝑛𝑠))

= 9 𝑛𝑠 + 11 𝑛𝑠 = 20 𝑛𝑠

So, the effective access time in this case is 20 nanoseconds.

Pros and Cons of Paging

Here are some advantages of implementing paging in operating systems −

• Remove External Fragmentation − Paging helps to reduce external fragmentation issues by

dividing memory into fixed-size pages and frames.

• Efficient Memory Utilization − By implementing paging, memory can be utilized more

efficiently, because pages can be loaded into any available frame in physical memory.

• Simplified Memory Management − Paging simplifies management of memory inside the

operating system. It eliminates the need for contiguous allocation of memory.

• Extra Physical Memory − Paging allows the use of secondary storage (like hard disk) as an
extension of physical memory, which is known as virtual memory.

Paging comes with some disadvantages as well, such as −

• Overhead of Page Table − If the size of the page table is large, it will consume large amount of
memory and can lead to performance issues.

• Increased Memory Access Time − During address translation, if there is a TLB miss, then it will
take more time to access the page table, which can increase the overall memory access time.

• Extra Complexity − Implementing paging adds extra complexity while creating operating
system.

If an operating system uses paging for memory management, there is a chance for page faults to occur.
During a page fault, if no free frame is available in physical memory(RAM), the operating system should
decide which page to remove from physical memory to make space for the new page. This decision is
made using a page replacement algorithms.

There are several page replacement algorithms used by operating systems. Some of these algorithms
are good at reducing the number of page faults and some are easy to implement. So the choice of page
replacement algorithm can affect the performance of your system. In this chapter, we will discuss
following page replacement algorithms −

• First-In-First-Out (FIFO) Page Replacement

• Least Recently Used (LRU) Page Replacement

 • Least Frequently Used (LFU) Page Replacement

• Optimal Page Replacement

First-In-First-Out (FIFO) Page Replacement

In the FIFO page replacement algorithm, the page that has entered in the memory earliest will be
replaced first. Meaning the oldest page in memory will be removed to make space for the new page.
This algorithm is simple to implement using a queue data structure. The operating system maintains a
queue of pages in memory. When a page needs to be replaced, the page at the front of the queue (i.e.,
the oldest page) is removed, and the new page is added to the back of the queue.

Example

The image below shows how main memory behaves when a page reference string of 5, 0, 1, 7, 2, 0, 2,
8 is processed using FIFO page replacement algorithm with 4 frames −

In this example, the initial pages 5, 0, 1, 7 are loaded directly into the empty frames. Then, the next
page 2 is referenced. Now, the frames are full, so according to FIFO, the oldest page 5 will be removed
and 2 will be loaded into its place.

This process continues for the rest of the page references. The table below shows each step of the
process, including the current page reference –

Step Reference Frames (Oldest to Newest) Page fault? Removed page

1 5 5 Yes (1)  

2 0 5, 0 Yes (2)  

3 1 5, 0, 1 Yes (3)  

 4 7 5, 0, 1, 7 Yes (4)  

5 2 0, 1, 7, 2 Yes (5) 5 (oldest)

6 0 0, 1, 7, 2 No  

7 2 0, 1, 7, 2 No  

8 8 1, 7, 2, 8 Yes (6) 0 (oldest)

• Total Page Faults = 6

• Page Fault Rate = 6/8 = 75%

• Pages Removed = 5, 0

Least Recently Used (LRU) Page Replacement

The LRU is another popular page replacement algorithm. In this algorithm, the page that has not been
used for the longest period of time will be replaced first. Meaning, the page that was least recently
used will be removed to make space for the new page. This work like memory cache, where the item
that has not been touched for the longest time is removed first.

This algorithm uses timestamps to keep track of page usage. When a page is accessed, its timestamp
is updated to the current time. When a page needs to be replaced, the page with the oldest timestamp
(i.e., the least recently used page) is removed from memory. That's how the LRU algorithm works.

Example

Consider the a page reference string of 1, 2, 3, 1, 4, 5 and with 3 frames of physical memory. That is,

Page Reference String: 1, 2, 3, 1, 4, 5

Number of Frames: 3

The initial pages 1, 2, 3 are loaded directly into the 3 empty frames. When the next page 1 is
referenced, it is already in memory, so no page fault occurs. Next, page 4 is referenced, this can cause
a page fault. So the LRU algorithm will remove page 2. (If it was FIFO, it would have removed page 1,
because 2 is least recently used and 1 is oldest page).

This process continues for the rest of the page references. The table below shows all the steps of the
process −

Step Reference Frames (Oldest to Newest) Page fault? Removed page

1 1 1 Yes (1)  

 2 2 1, 2 Yes (2)  

3 3 1, 2, 3 Yes (3)  

4 1 1, 2, 3 No  

5 4 1, 3, 4 Yes (4) 2

6 5 3, 4, 5 Yes (5) 1

• Total Page Faults = 5

• Page Fault Rate = 5/6 = 83.33%

• Pages Removed = 2, 1

The main drawback of LRU algorithm is that it can be expensive and difficult to implement. We need
to keep track of the order of page usage, which requires data structures like stacks or linked lists. Also,
updating the timestamps for each page access can be costly in terms of time and space complexity.
However, LRU is the most popular page replacement algorithm used in many operating systems.

Least Frequently Used (LFU) Page Replacement

The LFU page replacement algorithm removes the page that has been used the least number of
times. In this algorithm, each page has a counter that keeps track of how many times it has been
accessed. When a page needs to be replaced, the page with the lowest access count is removed from
memory. If the access counts are the same, then you can use FIFO or LRU to break the tie ( depending
on the implementation).

Example

Consider the following page reference string and frames –

Reference string: 1, 2, 3, 1, 2, 4, 1, 2, 5

Frames = 3

The initial pages 1, 2, 3 are loaded directly into the empty frames. All of these pages will have an access
count of 1. When the next page 1 and 2 are referenced, they are already in memory, so their access
counts will be incremented to 2. Next page 4 is referenced, which causes a page fault. So the LFU
algorithm will remove page 3 since the access count of page 3 is 1 (lowest).

This process continues for the rest of the page references. The table below shows all the steps of the
process. Here the 1:2 means page 1 has a frequency of 2.

Step Reference Frequency Table (1,2,3,4,5) Frames Page Fault?

 1 1 1:1 1 Yes

2 2 1:1, 2:1 1,2 Yes

3 3 1:1, 2:1, 3:1 1,2,3 Yes

4 1 1:2, 2:1, 3:1 1,2,3 No

5 2 1:2, 2:2, 3:1 1,2,3 No

6 4 1:2, 2:2, 3:1 → Remove 3 (lowest freq=1) 1,2,4 Yes

7 1 1:3, 2:2, 4:1 1,2,4 No

8 2 1:3, 2:3, 4:1 1,2,4 No

9 5 1:3, 2:3, 4:1 → Remove 4 (lowest freq=1) 1,2,5 Yes

• Total Page Faults = 5

• Page Fault Rate = 5/9 = 55.56%

• Pages Removed = 3, 4

Compared to FIFO and LRU, the LFU algorithm have improved page fault rate (55.56% vs 75% and
83.33%). But there is a drawback of LFU algorithm. It can lead to starvation of pages that are not
regularly used. For example, if a page is accessed once at the beginning and then not used again, it will
hard to get back into memory because its access count will remain low.

Optimal Page Replacement

The optimal page replacement algorithm is a theoretical concept which is very difficult to be
implemented in real operating systems. This algorithm works by replacing the page that will not be
used for the longest period of time in the future. Meaning, it involves predicting what pages will be
used in the future and replacing the one that will not be used for the longest time. This is considered
as the best page replacement algorithm.

Let's solve an example that involves the optimal page replacement algorithm to understand how it
works.

Example

Consider the following page reference string and frames –

Page Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3

Frames: 4
Here, the first four pages 7, 0, 1, 2 are loaded directly into the first four empty frames. When the next
page 0 is referenced, it is already in memory, so no page fault occurs. Next, page 3 is referenced, which
causes a page fault. So the optimal algorithm will remove page 1 since it will not be used for the longest
period of time in the future (it won't be used again).

The table below shows all the steps of the process −

7 0 1 2 0 3 0 4 2 3 0 3 2 3

2 2 2 2 2 2 2 2 2 2

1 1 1 1 1 4 4 4 4 4 4 4

0 0 0 0 0 0 0 0 0 0 0 0 0 0

7 7 7 7 7 3 3 3 3 3 3 3 3 3

Miss Miss Miss Miss Hit Miss Hit Miss Hit Hit Hit Hit Hit Hit

We are able to implement this algorithm as we already know the entire page reference string. But that
will not be the case in real-world scenarios. You never know what pages will be referenced in the
future. That's why we told earlier that this algorithm is just a theoretical model.