Operating Systems:

Semester 3
Course Code BCS303 CIE Marks 50
Memory Management: Memory management strategies: Background; Swapping;
Contiguous memory allocation; Paging; Structure of page table; Segmentation.
Virtual Memory Management: Background; Demand paging; Copy-on-write; Page
replacement; Allocation of frames; Thrashing.

Q. 07 a What is TLB? Explain TLB in detail with a paging system with a neat diagram.

b With the help of a neat diagram, explain the various steps of address binding.

c Consider the page reference string: 1,0,7,1,0,2,1,2,3,0,3,2,4,0,3,6,2,1 for a memory with

three frames. Determine the number of page faults using the FIFO, Optimal, and LRU
replacement algorithms. Which algorithm is most efficient?

Q. 08 a What is demand paging? Explain the steps in handling page faults using the appropriate
diagram.

b What is segmentation? Explain the basic method of segmentation with an example.

c Discuss the structure of the page table with a suitable diagram.

Q.7 a. What is paging? Explain with neat diagram paging hardware with TLB?

b. What are the commonly used strategies to select a free hole from the available holes?

c. Explain fragmentation in detail.

q.8. a. With a neat diagram? Describe the steps in handling the page fault.

b. Consider the page reference string: 1, 0, 7, 1, 0, 2, 1, 2, 3, 0, 3, 2, 4, 0, 3, 6, 2, 1 for a

memory with 3 frames. Determine the number of page faults using F1, F0, optimal and LRU
replacement algorithms which algorithm is more efficient.

1|Page
Introduction to memory and memory units

Memory is the storage space in a computer where data and instructions are kept. It is divided into
small units called cells, and each cell has a unique address.

Storage element (Cell): Stores 1 bit of data. Register: A memory location made of cells.

Capacity: Total number of bits a memory can store. Reading: Retrieving data. Writing: Storing data.

Memory is essential because it allows computers to store both temporary data (used while processing)
and permanent data (like system programs).

Read and Write Operation

A word is a group of bits where a memory unit stores binary information. A word with a group of 8
bits is called a byte.

A memory unit consists of data lines, address selection lines, and control lines that specify the
direction of transfer.

The block diagram of a memory unit is shown below:

Data lines provide the information to be stored in memory. The control inputs specify the direct
transfer. The k-address lines specify the word chosen.

When there are k address lines, 2k memory words can be accessed.

2|Page
Types of Computer Memory

Types of Computer Memory

1. Cache Memory: Very fast storage, close to CPU, stores frequently used data.
2. RAM (Random Access Memory): Volatile, read/write, temporary data storage on motherboard.

DRAM: Uses capacitors, slower, needs refreshing.

SRAM: Uses flip-flops, faster, retains data as long as power is on.

3. ROM (Read Only Memory): Non-volatile, stores permanent system instructions, read-only.

MROM: Pre-programmed, low-cost.

PROM: User programmable once.

EPROM: Can be erased using UV light and reprogrammed.

EEPROM: Electrically erasable and reprogrammable, faster, reusable up to ~10,000 times.

4. Virtual Memory: Uses secondary storage as an extension of RAM.

5. Flash Memory: Non-volatile, fast, used in SSDs, USBs, memory cards.

6. Hybrid Memory: Combines RAM and Flash for efficiency and reduced power use.

What is Primary Memory?

It is also referred to as main memory or internal memory. It is a computer system's temporary storage
component which is directly accessible by the central processing unit (CPU). It houses data for
immediate processing.

Characteristics

volatile: Data is lost upon power loss.

High-speed access.

3|Page
Limited capacity relative to secondary storage.

Examples: Random Access Memory (RAM), Read-Only Memory, Cache memory.

Advantages

High-speed access: Data can be retrieved and stored very quickly.

Directly accessible by CPU: No intermediate steps are required for data transfer.

Disadvantages

Volatile: Data is lost when power is turned off.

Limited storage capacity: compared to secondary storage, primary memory is relatively small.

Expensive: Cost per unit is higher than secondary storage.

What is Secondary Memory?

Secondary memory or external memory serves as long-term storage for data and programs. Unlike
primary memory, it is not directly accessible by the CPU and requires input/output operations.

Characteristics

Non-volatile: Data persists even when the system is powered off.

slower access speeds compared to primary memory.

High storage capacity.

Examples: Hard Disk Drives(HDD), Solid-State Drives(SSD), Optical drives(CD, DVD, Blu-ray).

Advantages

Non-volatile: Data persists even when the power is turned off.

Large storage capacity: can store vast amount of data.

Relatively Inexpensive: cost-effective for storing large volumes of data.

Disadvantages

Slower access time: Data retrieval is slower compared to primary memory.

Requires input/output operations: Data transfer involves additional steps.

Read more about - Difference between Primary and Secondary Memory

Functions of Memory Unit

The memory unit of a computer has several functions:

Data Storage: Store temporary data (RAM) and permanent data (ROM).

Quick Access: CPU retrieves stored data and instructions for fast processing.

Data Transfer: Move data between CPU, RAM, and storage devices.

Program Execution: Provide instructions and space for active processes.

4|Page
Reliability: Non-volatile memory (ROM/EEPROM) keeps data safe even without power.

The size of the memory unit affects its speed, power, and capabilities. without a memory unit, the
processor would have to wait longer for data retrieval.

Memory Management in Operating System

Memory management is a critical aspect of operating systems that ensures efficient use of the
computer's memory resources. It controls how memory is allocated and deallocated to processes,
which is key to both performance and stability. Below is a detailed overview of the various
components and techniques involved in memory management.

Memory Management

Why Memory Management is Required?

Allocate and de-allocate memory before and after process execution.

To keep track of used memory space by processes.

To minimize fragmentation issues.

To proper utilization of main memory.

To maintain data integrity while executing of process.

Logical and Physical Address Space

Logical Address Space: The logical address space is the set of all addresses that a process can generate
using its CPU. It defines the range of memory locations available to the process from its perspective.

Physical Address Space: The physical address space is the set of all actual memory addresses in the
main memory (RAM). It represents the real locations where data and instructions are stored.

5|Page
Static and Dynamic Loading

Loading a process into the main memory is done by a loader. There are two different types of loading
:

Static Loading: Static Loading is basically loading the entire program into a fixed address. It requires
more memory space.

Dynamic Loading: Dynamic loading loads program routines into memory only when they are needed.
This saves memory by not loading unused routines. The routines remain on disk in relocatable(can be
loaded at any memory location) format until called. It allows better memory utilization, especially for
large programs.

Static and Dynamic Linking

A linker combines object files into a single executable.

Static Linking: All required modules are combined into one executable. No runtime dependency; some
OSes support only this method.

Dynamic Linking: Uses a stub (small code) for library calls. At runtime, the stub checks if the routine is
in memory; if not, it loads it.

Swapping

Swapping moves processes between main memory and secondary memory to manage limited
memory space. It allows multiple processes to run by temporarily swapping out lower priority
processes for higher priority ones. The swapped-out process resumes once it's loaded back. Transfer
time depends on the amount of data swapped.

Swapping

Memory Management Techniques

Memory management techniques are methods used by an operating system to efficiently allocate,
utilize, and manage memory resources for processes. Various techniques help the operating system
manage memory effectively. They can be broadly categorized into:

6|Page
Memory Management with Monoprogramming (Without Swapping)

This is the simplest memory management approach the memory is divided into two sections: One
part of the operating system. The second part of the user program

Memory Management Techniques

The OS is loaded either at the bottom or the top of memory.

Since interrupt vectors are usually placed in low memory, the OS is often loaded there.

In a single-process system, sharing code or data is unnecessary.

The OS is protected from user programs using a fence register.

Multiprogramming with Fixed Partitions (Without Swapping)

A memory partition scheme with a fixed number of partitions was introduced to support
multiprogramming. this scheme is based on contiguous allocation

Each partition is a block of contiguous memory

Memory is partitioned into a fixed number of partitions.

Each partition is of fixed size

Partition Table: Once partitions are defined operating system keeps track of the status of memory
partitions it is done through a data structure called a partition table.

Starting Address of Partition Size of Partition Status

0k 200k allocated
200k 100k free
300k 150k free
450k 250k allocated

7|Page
Contiguous Memory Allocation

Contiguous memory allocation is a memory management method where each process is given a single,
continuous block of memory. This means all the data for a process is stored in adjacent memory
locations.

Non-Contiguous Memory Allocation

This method allows processes to be broken into smaller parts, which are placed in different, non-
adjacent memory locations. Techniques for non-contiguous memory allocation include:

Paging: The process is divided into fixed-size blocks called "pages," and the memory is divided into
blocks of the same size called "frames." The operating system keeps a page table to map logical pages
to physical frames.

Segmentation: The process is divided into segments of varying sizes, such as code, data, stack, etc. The
operating system maintains a segment table to map logical segments to physical memory.

Fragmentation

Fragmentation occurs when processes are loaded and removed from memory, leaving small
unusable gaps. These gaps cannot be allocated to new processes because they are either too small
or scattered.

Types of Fragmentation:

Internal Fragmentation: Wasted space inside allocated memory blocks when a process is given more
memory than it needs.

External Fragmentation: Free memory exists but is divided into small scattered blocks, preventing
allocation of large contiguous space.

Memory Allocation Strategies

Efficient memory allocation is essential for optimal performance. There are several strategies for
allocating memory blocks:

1. Fixed Partition Allocation: Memory is divided into fixed-sized partitions, and each partition can
hold only one process. The OS keeps track of free and occupied partitions using a partition table.

2. Dynamic Partition Allocation: Memory is divided into variable-sized partitions based on the size of
the processes. This helps avoid wastage of memory but can result in fragmentation.

3. Placement Algorithms: When allocating memory, the OS uses placement algorithms to decide
which free block should be assigned to a process:

First Fit: Allocates the first available partition large enough to hold the process.

Best Fit: Allocates the smallest available partition that fits the process, reducing wasted space.

Worst Fit: Allocates the largest available partition, leaving the largest remaining space.

Next Fit: Similar to First Fit but starts searching for free memory from the point of the last allocation.

8|Page
Logical and Physical Address in Operating System

In operating systems, memory is accessed using logical (virtual) addresses and physical addresses,
which the Memory Management Unit (MMU) maps to manage memory efficiently.

Logical Address

A logical address is generated by the CPU while a program runs. It represents the address from the
process’s perspective and does not exist physically, hence it is also called a virtual address.

The logical address space is the set of all logical addresses a process can generate. Programs use logical
addresses to reference memory, and the MMU translates them into physical addresses when
accessing actual memory.

Physical Address

A physical address is the real location in main memory (RAM) where data or instructions are stored.
The physical address space consists of all physical addresses corresponding to logical addresses.

The MMU performs address translation using a page table, mapping each logical page to a physical
frame. This allows processes to access memory transparently, without knowing actual memory
locations.

Similarities Between Logical and Physical Addresses in the Operating System

Both logical and physical addresses are used to identify a specific location in memory.

Both logical and physical addresses can be represented in different formats, such as binary,
hexadecimal, or decimal.

Both logical and physical addresses have a finite range, which is determined by the number of bits
used to represent them.

Memory Management Unit

The Memory Management Unit (MMU) is a hardware component in the computer system that
handles all memory and caching operations associated with the CPU. Its main function is to
translate logical (virtual) addresses generated by the CPU into physical addresses in main memory.

Important Points about Logical and Physical Addresses in Operating Systems

Logical addresses provide abstraction, so processes don’t need to know physical locations.

Logical addresses are mapped to physical addresses via the page table.

Translation is transparent and handled by hardware (MMU).

Enables efficient memory management through paging and segmentation.

9|Page
 Memory Management

Difference Between Logical address and Physical Address

Parameter LOGICAL ADDRESS PHYSICAL ADDRESS

Basic generated by CPU location in a memory unit
Address Logical Address Space is set of all Physical Address is set of all physical
Space logical addresses generated by CPU in addresses mapped to the corresponding
reference to a program. logical addresses.
Visibility User can view the logical address of a User can never view physical address of
program. program.
Generation generated by the CPU Computed by MMU
Access The user can use the logical address to The user can indirectly access physical
access the physical address. address but not directly.
Editable Logical address can be change. Physical address will not change.
Also called virtual address. real address.

Implementation of Contiguous Memory Management Techniques

Memory Management Techniques are basic techniques that are used in managing the memory in
the operating system. They are classified broadly into two categories:

Contiguous and Non-contiguous

Contiguous memory allocation is a memory allocation strategy. As the name implies, we utilize this
technique to assign contiguous blocks of memory to each task. Thus, whenever a process asks to
access the main memory, we allocate a continuous segment from the empty region to the process
based on its size. In this technique, memory is allotted in a continuous way to the processes.
Contiguous Memory Management has two types:

 Fixed (or Static) Partition

 Variable (or Dynamic) Partitioning

10 | P a g e
Lets understand these in detail.

Types of Memory Management Techniques

Fixed Partition Scheme

In the fixed partition scheme, memory is divided into fixed number of partitions. Fixed means
number of partitions are fixed in the memory. In the fixed partition, in every partition only one
process will be accommodated. Degree of multi-programming is restricted by number of partitions
in the memory. Maximum size of the process is restricted by maximum size of the partition. Every
partition is associated with the limit registers.

Limit Registers has two limits:

 Lower Limit which is the starting address of the partition.

 Upper Limit which is ending address of the partition.

Internal Fragmentation in Fixed Partition Scheme

Disadvantages Fix partition scheme

Maximum process size should always be less than equal to maximum partition size.

The degree of multiprogramming is directly proportional to the number of partitions.

If a process of 19kb wants to allocate and we have free space which is not continuous we are not able
to allocate the space.

11 | P a g e
Internal Fragmentation is found in fixed partition scheme. To overcome the problem of internal
fragmentation, instead of fixed partition scheme, variable partition scheme is used.

Variable Partition Scheme

In the variable partition scheme, initially memory will be single continuous free block. Whenever the
request by the process arrives, accordingly partition will be made in the memory. If the smaller
processes keep on coming then the larger partitions will be made into smaller partitions.

In variable partition schema initially, the memory will be full contiguous free block

Memory divided into partitions according to the process size where process size will vary.

One partition is allocated to each active partition.

External Fragmentation is found in variable partition scheme.

Advantages of Variable Partition Scheme

Portion size = process size

There is no internal fragmentation (which is the drawback of fixed partition schema).

Degree of multiprogramming varies and is directly proportional to a number of processes.

Disadvantage Variable Partition Scheme

External fragmentation is still there.

External Fragmentation in Variable Partition Scheme

Solution of External Fragmentation

To overcome the problem of external fragmentation, following techniques are used:

1. Compaction

Moving all the processes toward the top or towards the bottom to make free available memory in a
single continuous place is called compaction. Compaction is undesirable to implement because it
interrupts all the running processes in the memory. It also consumes CPU time (overhead).

12 | P a g e
2. Non-contiguous memory allocation

Physical address space: Main memory (physical memory) is divided into blocks of the same size called
frames. frame size is defined by the operating system by comparing it with the size of the process.

Logical Address space: Logical memory is divided into blocks of the same size called process pages.
page size is defined by hardware system and these pages are stored in the main memory during the
process in non-contiguous frames.

Internal Fragmentation in OS

Internal Fragmentation is the wastage of memory that occurs when fixed-sized memory blocks are
allocated to processes, but the process does not use the entire allocated block. The unused portion
inside the allocated block remains idle, resulting in poor memory utilization.

How Internal Fragmentation is Caused?

Fixed Block Allocation: When processes request memory, they are often assigned blocks larger than
required. The unused space within the block is wasted.

Uniform Block Sizes: If all processes get the same memory size, smaller processes leave large unused
portions.

Management Overheads: Some systems reserve extra memory for bookkeeping, which also adds to
internal fragmentation.

Example: Let's assume that the system that is being used assigns the memory in blocks of sizes being
multiples of 4(like 12, 24, 32,..). In this system when a process P1 requests an amount of memory that
is not a multiple of 4, it is assigned a memory block of value of the nearest higher multiple.

13 | P a g e
A process requests 29 KB.

It will be assigned 32 KB (nearest multiple of 4).

The extra 3 KB remains unused.

This 3 KB loss is internal fragmentation.

Effect of Internal Fragmentation

Due to Internal Fragmentation various types of effects occurs:

Inefficient Memory Utilization: Wasted space reduces overall usable memory.

Performance Degradation: More I/O operations due to scattered partially filled blocks.

Virtual Memory Issues: Partially filled pages can increase page faults.

Why Internal Fragmentation is Allowed?

As Internal Fragmentation is nothing but a problem there isn't any significant advantage that it
provides to the system. But there are a couple of things that favor causing it, which are:

As the allocation always occurs in a fixed size only the allocation becomes fast and simple.

When the overhead calculation for the system is done it outputs to be pretty predictable which in
return gives a predictable performance. The overhead calculation is accurate as the overhead caused
by the Internal Fragmentation is already well known.

Ways to Avoid Internal Fragmentation

There are several ways to avoid Internal fragmentation. Some of them are mentioned below.

Variable-Sized Blocks: Create memory blocks of different sizes and allocate the best-fit block for each
process, reducing unused space.

Dynamic Memory Allocation: Assign only the exact memory required by a process, so little to no
memory is wasted.

External Fragmentation in OS

External fragmentation is a problem in memory management where free memory is divided into
small, non-contiguous blocks. Even though there may be enough total free memory to run a new
program, the memory is scattered in tiny pieces, so it's impossible to find a single, large block for the
program to use. This leads to wasted memory and poor system performance.

Why Does It Happen?

External fragmentation is caused by the dynamic allocation and deallocation of processes. Imagine
memory as a long parking lot.

A few cars (processes) park in different spots.

Then, some of these cars leave, creating empty spaces (free memory).

These empty spaces are of different sizes and are scattered throughout the lot.

14 | P a g e
If a new, large truck (a new process) arrives, it can't find a single, continuous space big enough to
park, even though the total empty space in the lot is more than enough.

This is exactly how external fragmentation works. The "holes" in the memory are too small and
separated to be useful for larger processes.

How to Avoid External Fragmentation?

To avoid external fragmentation in an operating system:

Paging/Segmentation: Paging allocates memory in fixed-size pages, avoiding external fragmentation.

Segmentation uses variable-sized blocks but may still leave some gaps.

Compaction: Rearranges processes in memory to merge free spaces into larger contiguous blocks.

Best-Fit Allocation: Assigns the smallest available block that fits a process, reducing wasted space
(though not eliminating fragmentation completely).

Illustrative Example of External Fragmentation

Lets consider a memory space having 4 processes, each of them requires different amount of
memory to execute, as shown in Figure 1.

Figure 1

Now suppose Process 1 and Process 3 have been completed, so now there are free places available,
as shown in Figure 2.

Figure 2

Now, if we want to run another process (Process 5) requiring memory 50 KB, we will not be able to
do it, although there is enough memory to run Process 5 as the memory is not contiguous, as shown
in Figure 3.

15 | P a g e
 Figure 3

That's how external fragmentation occurs.

Causes of External Fragmentation

The primary causes of external fragmentation include:

Variable Process Sizes: Different processes need different amounts of memory, leaving uneven gaps
when loaded/unloaded.

Allocation & Deallocation: When processes finish, freed blocks may not be adjacent, creating
scattered holes.

Non-Uniform Release: Memory released at irregular points leads to gaps of unpredictable sizes.

Allocation Strategies: Best-fit and worst-fit may worsen fragmentation by leaving behind many small
unusable holes.

Fixed Partitioning: Fixed-sized partitions cause mismatches between process size and partition size,
leading to internal and external fragmentation.

High Process Turnover: Frequent loading and removal of processes leaves memory fragmented over
time.

Solution of External Fragmentation

Below mentioned are the solutions of External Fragmentation that are mentioned below.

1. Memory Compaction

Memory compaction includes rearranging the items in memory to unite free memory hinders and
make bigger contiguous memory regions. This is the closely guarded secret:

Process Relocation: Moves processes closer together to eliminate or reduce gaps, creating larger
contiguous free memory blocks.

Benefits: Directly reduces external fragmentation, increasing the chance of allocating memory
without gaps.

Challenges: Can be resource-intensive, may disrupt running processes, and frequent compaction can
impact system performance.

16 | P a g e
2. Paging

Paging is a memory management technique that divides physical memory into fixed-size blocks called
pages. It helps overcome external fragmentation and simplifies memory allocation.

Page Size: Memory is divided into equal-sized pages, preventing small unusable gaps.

Virtual Memory: Allows processes to use non-contiguous physical memory while seeing it as a single
contiguous space.

Page Table: The OS maintains a page table that maps virtual addresses to physical addresses.

Page Replacement: When memory is full, pages can be swapped between main memory and disk to
free space.

Advantages of External Fragmentation

Flexibility: Variable-sized allocation lets processes request memory as needed, not limited to fixed
blocks.

Efficient Utilization: Small gaps may appear, but overall memory use can still be better than fixed-sized
allocation.

Simplicity: Strategies like first-fit or best-fit are easy and fast to implement, reducing overhead.

Dynamic Growth: Supports applications that expand memory usage over time by allocating differently
sized blocks.

Disadvantages of External Fragmentation

Memory Consumption: Small, unusable intervals of memory accumulate, making it difficult to allocate
large chunks of memory even if there is sufficient free space

Reduced Performance: Over time, fragmentation can slow down memory allocation processes, as the
system must search for enough free space.

Need for Constant Wear: To prevent cracking, the system control may need to rotate (compress)
repeatedly, which can take time to wear down

Limits Program Growth : As memory fragmentation occurs, it can prevent the memory usage of
programs from expanding, causing inefficiency or corruption

Buddy System - Memory Allocation Technique

The Buddy Allocation System is a memory management technique that divides a large memory block
into smaller power-of-two blocks called buddies.

If a request comes in, the block is repeatedly split until a suitable size is reached.

When memory is freed, its buddy is checked — if also free, they merge back to form a larger block.

This makes memory reuse fast and reduces fragmentation.

Algorithm of Buddy System

Below are the steps involved in the Buddy System Memory Allocation Technique:

17 | P a g e
Divide memory into blocks of size power-of-two (2, 4, 8, 16, 32, 64, …).

Label each block with its size and ID.

Initially, all blocks are free and maintained in a tree-like structure.

On a request, find the smallest block that fits. If too large, split until the required size is reached.

Allocate one block, keep the other free.

On deallocation, check if the buddy is free → merge to form a larger block.

Illustration

Problem: A system with 128 KB memory receives a request of 18 KB.

Solution: Nearest power of 2 ≥ 18 KB = 32 KB.

We can see that if we further divide 32 in half it will be 16, which is less than 18 i.e. insufficient to
store 18, therefore we can't split the memory further and 32 will become our leaf node.

Features of Buddy System

Scalability: Handles large memory efficiently by splitting into smaller blocks and adjusting dynamically.

Efficient Splitting & Merging: Blocks split into equal buddies when allocated; merged back when both
are free.

Reduced Fragmentation: Merges adjacent free blocks, minimizing wasted gaps.

Fast Allocation: Quick allocation/deallocation with low overhead.

Power-of-Two Blocks: Memory divided into 1KB, 2KB, 4KB… simplifies splitting and merging.

Buddy System Advantages & Drawbacks

Efficient memory use, reduced fragmentation, and fast allocation/deallocation. Drawback: internal
fragmentation (allocated block may be larger than needed). Useful for OS, especially in embedded
systems with limited memory.

Example of Buddy System Allocation

Let total memory = 2U2U and a request of size SS. It will be handled as:

If 2U−1<S≤2U⇒Allocate block of size 2UIf 2U−1<S≤2U⇒Allocate block of size 2U

18 | P a g e
Else, recursively divide the block into two equal buddies until the smallest suitable block is found.

The system also keeps a record of all the unallocated blocks and can merge these different-sized blocks
to make one big chunk.

Additional rules:

Request Handling: Requests are served first-come, first-served.

Splitting Rule: Always allocate the left buddy (lower address) first.

Merging Rule: Freed blocks merge with their buddy if possible.

The following figure illustrates the implementation of buddy system, considering a 1024k (1-
megabyte) initial block and the process requests as shown at the left of the table.

Flow of allocation

Explanation of the Table:

Start: One free block of 1024 KB.

A = 70 KB: Split → allocate 128 KB block for A.

B = 35 KB: Split → allocate 64 KB block for B.

C = 80 KB: Split → allocate 128 KB block for C.

A ends: Block of 128 KB freed.

D = 60 KB: Allocated in a free 64 KB block.

B ends: 64 KB freed → can merge with buddy.

D ends: Freed → merge with buddy, coalescing larger blocks.

C ends: Freed → memory fully restored to 1024 KB.

19 | P a g e
Types of Buddy System

The Buddy System is a memory allocation method where blocks are split and merged for efficient use.
Different types of Buddy Systems exist to suit specific needs and optimizations in various systems.

 Binary buddy system

 Fibonacci buddy system
 Weighted buddy system
 Tertiary buddy system

1. Binary buddy system

Memory is split into blocks of size power of two.

On request, the nearest larger block is chosen and split repeatedly into equal halves (buddies) until
the required size is reached.

Freed buddies can merge back to form larger blocks (coalescing).

Example: If total memory = 256KB and request = 25KB nearest power of two is 32KB.

256KB split into 128KB + 128KB

128KB split into 64KB + 64KB

64KB split into 32KB + 32KB

One 32KB block is allocated (25KB fits inside).

2. Fibonacci buddy system

A variation of the buddy system where memory blocks are divided into sizes based on Fibonacci
numbers instead of powers of two.

Block sizes follow the relation:

Zi = Z(i-1)+Z(i-2)

Example sequence: 1, 2, 3, 5, 8, 13, 21, 34 …

On a memory request, the system finds the smallest Fibonacci block that can satisfy it.

Like binary buddies, free blocks can be merged (coalesced) into larger Fibonacci-sized blocks.

3. Weighted Buddy System

In a weighted peer system, each memory block is associated with a weight, which represents its size
relative to other blocks. When a memory allocation request occurs, the system searches for the
appropriate block considering the size of the requested memory and the weight of the available
blocks.

4. Tertiary Buddy System

In a traditional buddy system, memory is divided into blocks of fixed size, usually a power of 2, and
allocated to these blocks but the tertiary buddy system introduces a third memory structure, which
allows flexibility large in memory allocation.

20 | P a g e
Advantages

Efficient use of memory.

Fast allocation and deallocation.

Coalescing reduces fragmentation.

Drawbacks

Internal fragmentation (block may be bigger than request).

Limited flexibility due to power-of-two constraint.

Non-Contiguous Allocation in Operating System

Non-contiguous allocation, also known as dynamic or linked allocation, is a technique used in

operating systems to allocate memory to processes that do not require a contiguous block of memory.
Here a process is divided into parts and stored in different free blocks of main memory, not necessarily
consecutive:

Process is split into smaller units (pages/segments).

These parts are placed in available free blocks (frames) of memory.

OS maintains mapping through page tables or segment tables

Note: These non-contiguous blocks of memory can be located anywhere in the physical memory.

Fundamental Approaches of Implementing Non-Contiguous Memory Allocation

Non-contiguous allocation involves the use of pointers to link the non-contiguous memory blocks
allocated to a process. These pointers are used to keep track of the memory blocks allocated to the
process and to locate them during the execution of the process.

There are two fundamental approaches to implement non-contiguous memory allocation:

Non-Contiguous Allocation

21 | P a g e
Paging: It breaks processes into equal-sized pages and maps them to memory frames, mainly to
eliminate external fragmentation.

Segmentation: It divides processes into variable-sized logical segments (like code, data, stack),
supporting protection, sharing, and logical organization.

Segmented Paging: A hybrid technique that first divides processes into logical segments and then
splits each segment into fixed-size pages, combining the benefits of segmentation and paging.

It has the advantage of reducing memory wastage but it increases the overheads due to address
translation, which results in slow execution.

Note: Paging avoids external fragmentation but may suffer from internal fragmentation.

How Does Non-Contiguous Memory Allocation Work?

A process is divided into parts that can be stored in different free spaces of main memory (not
necessarily consecutive).

Example: If a process P=4KBP=4KB and memory has two free slots of 2KB2KB each, contiguous
allocation fails (no spanning allowed). In non-contiguous allocation, PP is split into two 2KB2KB parts,
each fitting into the free slots.

In contiguous allocation:

Space in memory should be allocated to the whole process.

If not, then that space remains unallocated.

In Non-Contiguous allocation:

The process can be divided into different parts hence filling the space in the main memory.

In this example, process PP can be divided into two parts of equal size -> 2KB2KB.

Hence one part of process PP can be allocated to the first 2KB2KB space of main memory and the
other part of the process can be allocated to the second 2KB2KB space of main memory.

The below diagram will explain in a better way:

How Non Contiguous Allocation work

22 | P a g e
In what manner we divide a process to allocate them into main memory? The process is divided after
analyzing the number of empty spaces and their size in the main memory. But, it has some challenge:

Dividing processes dynamically based on changing free space is time-consuming as their sizes changing
every time due to execution of already present processes in main memory.

In order to avoid this time-consuming process, we divide our process in secondary memory in advance
before reaching the main memory for its execution. Every process is divided into various parts of equal
size called Pages. We also divide our main memory into different parts of equal size called Frames. It
is important to understand that:

Rule: pageSize=frameSize.

Example with Paging: If frame size = 2KB2KB, processes P1P1 and P2P2 (22 pages each) can be stored
alternately across free frames in memory.

Page Mapping with Frames

Resolvent main memory, In main memory the sequence of storage of pages are: First page of P1 ->
First page of P2 -> Second page of P1 -> Second page of P2

23 | P a g e
Pages Distribution

Note: Non-contiguous allocation (via paging) divides processes into pages and memory into frames,
ensuring flexible and efficient use of memory without requiring consecutive space.

Pros of Non-Contiguous Allocation

Reduced Internal Fragmentation : Memory blocks are allocated as per process needs; unused space
inside blocks is minimized.

Flexible Allocation : Processes can be loaded wherever free memory is available, without requiring a
large continuous block.

Better Memory Utilization : Small gaps in memory can be efficiently used to fit parts of different
processes.

Supports Dynamic Loading & Growth : Processes that expand (like stack/heap) can take memory from
scattered free blocks.

Multiprogramming Support : More processes can reside in memory simultaneously, as allocation is

more flexible.

Enables Virtual Memory : Forms the basis of schemes like paging and segmentation, allowing
processes to use more memory than physically available.

Cons of Non-Contiguous Allocation

External Fragmentation : Free memory may be broken into many small scattered blocks, making it
hard to allocate large memory requests.

Overhead of Address Mapping : Requires complex data structures (page tables, segment tables or
linked lists) to keep track of allocated blocks.

Slower Access : Address translation and pointer chasing increase access time compared to contiguous
allocation.

Memory Management Overhead : Additional hardware (MMU : Memory Management Unit) and OS
routines are needed for mapping logical to physical addresses.

Complex Deallocation : Releasing and merging free memory blocks is more complicated, increasing OS
overhead.

Possibility of Page Faults (in Paging-based systems) : Since data is scattered, a needed page may not
be in memory, causing delays.

24 | P a g e
Paging in Operating System

Paging is the process of moving parts of a program, called pages, from secondary storage into the main
memory (RAM). The main idea behind paging is to break a program into smaller fixed-size blocks called
pages.

Process does not have to be allocated in a contiguous memory space.

The whole process does not have to be in main memory, some pages can be present and some pages
can be loaded when needed. It allows more processes and even processes larger than main memory
to run.

Memory allocation is simplified as memory is always allocated in fixed sized pages.

Paging in Operating System

To keep track of where each page is stored in memory, the operating system uses a page table. This
table shows the connection between the logical page numbers and the physical page frames (actual
locations in RAM).

Note: The memory management unit uses the page table to convert logical addresses into physical
addresses, so the program can access the correct data in memory.

Paging in Memory Management

Paging addresses common challenges in allocating and managing memory efficiently. Why paging is
needed as a Memory Management technique:

Memory isn’t always available in a single block: Programs often need more memory than what is
available in a single continuous block. Paging breaks memory into smaller, fixed-size pieces, making it
easier to allocate scattered free spaces.

Processes size can increase or decrease: programs don’t need to occupy continuous memory, so they
can grow dynamically without the need to be moved.

25 | P a g e
Terminologies Associated with Memory Control

Logical Address Space or Virtual Address Space: The Logical Address Space, refers to the set of all
possible logical addresses that a process can generate during its execution.

Physical Address Space: The Physical Address Space refers to the total range of addresses available in
a computer's physical memory (RAM).

Important Features of Paging

Logical to physical address mapping: Paging divides a process's logical address space into fixed-size
pages. Each page maps to a frame in physical memory, enabling flexible memory management.

Fixed page and frame size: Pages and frames have the same fixed size. This simplifies memory
management and improves system performance.

Page table entries: Each logical page is represented by a page table entry (PTE). A PTE stores the
corresponding frame number and control bits.

Number of page table entries: The page table has one entry per logical page. Thus, its size equals the
number of pages in the process's address space.

Page table stored in main memory: The page table is kept in main memory. This can add overhead
when processes are swapped in or out.

Working of Paging

When a process requests memory, the operating system allocates one or more page frames to the
process and maps the process's logical pages to the physical page frames. When a program runs, its
pages are loaded into any available frames in the physical memory.

Working of Paging

26 | P a g e
Each program has a page table, which the operating system uses to keep track of where each page is
stored in physical memory. When a program accesses data, the system uses this table to convert the
program's address into a physical memory address.

Steps Involved in Paging :

Step 1 Divide Memory : Logical -> Pages, Physical -> Frames .

Step 2 Allocate Pages : Load pages into available frames.

Step 3 Page Table : Map logical pages to physical frames.

Step 4 Translate Address : Convert logical to physical address.

Step 5 Handle Page Fault : Load missing pages from disk.

Step 6 Run Program : CPU uses page table during execution.

If Logical Address Space = 128 M words = 27 * 220 words, then Logical Address = log2 227 = 27 bits
If Physical Address Space = 16 M words = 24 * 220 words, then Physical Address = log2 224 = 24 bits

The mapping from virtual to physical address is done by the Memory Management Unit
(MMU) which is a hardware device and this mapping is known as the paging technique.

The Physical Address Space is conceptually divided into a number of fixed-size blocks, called frames.

The Logical Address Space is also split into fixed-size blocks, called pages.

Page Size = Frame Size

Example

Physical Address = 12 bits, then Physical Address Space = 4 K words

Logical Address = 13 bits, then Logical Address Space = 8 K words

Page size = frame size = 1 K words (assumption)

Number of frames = Physical Address Space / Frame Size = 4K / 1K = 4 = 22

Number of Pages = Logical Address Space / Page Size = 8K / 1K = 23The address generated by the
CPU is divided into:

Page number(p): Number of bits required to represent the pages in Logical Address Space or Page
number

Page offset(d): Number of bits required to represent a particular word in a page or page size of
Logical Address Space or word number of a page or page offset.

A Physical Address is divided into two main parts:

Frame Number(f): Number of bits required to represent the frame of Physical Address Space or
Frame number frame

Frame Offset(d): Number of bits required to represent a particular word in a frame or frame size of
Physical Address Space or word number of a frame or frame offset.

Physical Address = (Frame Number << Number of Bits in Frame Offset) + Frame Offset
where "<<" represents a bitwise left shift operation.

27 | P a g e
Hardware implementation of Paging

The hardware implementation of the page table can be done by using dedicated registers. But the
usage of the register for the page table is satisfactory only if the page table is small. If the page table
contains a large number of entries then we can use TLB(translation Look-aside buffer), a special, small,
fast look-up hardware cache.

Page Table with TLB

The TLB is associative, high-speed memory.

Each entry in TLB consists of two parts: a tag and a value.

When this memory is used, then an item is compared with all tags simultaneously. If the item is found,
then the corresponding value is returned.

Main memory access time = m, If page table are kept in main memory, Effective access time = m(for
page table) + m(for particular page in page table)

Advantages of Paging

Eliminates External Fragmentation: Paging divides memory into fixed-size blocks (pages and frames),
so processes can be loaded wherever there is free space in memory. This prevents wasted space due
to fragmentation.

Efficient Memory Utilization: Since pages can be placed in non-contiguous memory locations, even
small free spaces can be utilized, leading to better memory allocation.

Supports Virtual Memory: Paging enables the implementation of virtual memory, allowing processes
to use more memory than physically available by swapping pages between RAM and secondary
storage.

Ease of Swapping: Individual pages can be moved between physical memory and disk (swap space)
without affecting the entire process, making swapping faster and more efficient.

Improved Security and Isolation: Each process works within its own set of pages, preventing one
process from accessing another's memory space.

28 | P a g e
Disadvantages of Paging

Internal Fragmentation: If the size of a process is not a perfect multiple of the page size, the unused
space in the last page results in internal fragmentation.

Increased Overhead: Maintaining the Page Table requires additional memory and processing. For
large processes, the page table can grow significantly, consuming valuable memory resources.

Page Table Lookup Time: Accessing memory requires translating logical addresses to physical
addresses using the page table. This step increases memory access time, although TLBs can help
reduce the impact.

I/O Overhead During Page Faults: When a required page is not in physical memory (page fault), it
needs to be fetched from secondary storage, causing delays and increased I/O operations.

Complexity in Implementation: Paging requires sophisticated hardware and software support,

including the MMU and algorithms for page replacement, which add complexity to the system.

Segmentation

Segmentation is a memory management technique where a process is divided into variable-sized

chunks called segments. Unlike paging, segmentation matches the user’s logical view of a program
(functions, arrays, modules) to physical memory.

It reflects the user’s view of memory rather than the computer’s physical organization, making it easier
to manage and protect processes.

Key Features of Segmentation

1. Variable-sized divisions: Segments can have different lengths, depending on the program’s
requirements.
2. Logical division of memory: Segments represent meaningful units like code, stack, data, or modules.
3. Two-part address: A logical address consists of:

Segment number (s): Identifies which segment is being referred to.

Offset (d): Specifies the exact location within that segment.

Logical Address = ⟨Segment number, Offset⟩

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

5. No internal fragmentation: Since segments are not fixed in size.

6. External fragmentation: Can occur when free memory is divided into small scattered blocks.

Types of Segmentation in Operating Systems

Virtual Memory Segmentation: Each process is divided into a number of segments, but the
segmentation is not done all at once. This segmentation may or may not take place at the run time of
the program.

Simple Segmentation: Each process is divided into a number of segments, all of which are loaded into
memory at run time, though not necessarily contiguously.

29 | P a g e
There is no simple relationship between logical addresses and physical addresses in segmentation. A
table stores the information about all such segments and is called Segment Table.

What is Segment Table?

It maps a two-dimensional Logical address into a one-dimensional Physical address. It's each table
entry has:

Base Address: It contains the starting physical address where the segments reside in memory.

Segment Limit: Also known as segment offset. It specifies the length of the segment.

Segmentation

Translation of Two-dimensional Logical Address to Dimensional Physical Address.

30 | P a g e
The address generated by the CPU is divided into:

Segment number (s): Number of bits required to represent the segment.

Segment offset (d): Number of bits required to represent the position of data within a
segment.

Advantages of Segmentation in Operating System

Reduced Internal Fragmentation: Segments are sized as per program needs, minimizing wasted
space.

Smaller Segment Table: Requires less space compared to page tables.

Better CPU Utilization: Entire modules are loaded at once, improving performance.

Closer to User’s View: Programs can be divided into logical modules, matching how users think.

User-Controlled Size: Segment size is defined by the user, unlike fixed page size in paging.

Security & Separation: Segments help isolate sensitive data and operations.

Disadvantages of Segmentation in Operating System

External Fragmentation: Free memory gets scattered, leading to wasted space.

Overhead: Maintaining segment tables requires extra memory and management.

Slower Access: Two memory lookups (segment table + main memory) increase access time.

Complexity: Managing multiple variable-sized segments is harder than paging.

Segmentation Faults: Errors may occur if a program tries to access memory outside its segment.

Page Table

A Page Table is a data structure that maps virtual addresses (used by processes) to physical addresses
(actual locations in memory). The size and format of a PTE vary by system architecture and OS, but it
always contains enough information for efficient memory management and protection.

Note: Each mapping in the table is stored in a Page Table Entry (PTE), which Information Stored in
Page Table Entry

A Page Table Entry (PTE) stores the necessary metadata about a page, allowing the system to manage
memory safely and efficiently. The exact format and size of a PTE depend on the system’s architecture
(32-bit, 64-bit) and the operating system implementation, but typical fields include the following:

1. Frame Number

Identifies the frame in physical memory where the page is stored.

Number of bits required =log⁡2(Size of Physical MemoryFrame Size)=log2

(Frame SizeSize of Physical Memory)

2. Present/Absent Bit (Valid/Invalid Bit)

Indicates whether the page is currently loaded in memory or not.

31 | P a g e
Present (1): Page is in physical memory.

Absent (0): Page fault occurs when accessed and the OS must load it from disk.

3. Protection Bits

Define the allowed operations on the page:

Read (R)

Execute (X)

These bits prevent unauthorized memory access

Control access permissions (read, write, execute).

Helps protect memory from unauthorized access.

4. Referenced Bit

Set automatically by hardware when the page is accessed (read or written).

Used by page replacement algorithms (e.g., LRU – Least Recently Used).

5. Caching Enabled/Disabled

Determines whether the page should be cached.

Use case example: Disable caching for memory-mapped I/O (keyboard or hardware registers) to
always get fresh data.

6. Modified Bit (Dirty Bit)

Indicates if the page has been written to.

If set (1), the page must be written back to disk when evicted; otherwise, it can be discarded.

Example: For a 32-bit virtual address space with 4KB4KB pages:

Number of Pages=Total WordsWords per PageNumber of Pages=Words per PageTotal Words

Here for words per page we have 4KB

i.e 4KB = 210×22=210+2=212210×22=210+2=212

12 bits words per page.

Number of pages = 232212=220(about 1 million entries) = 212232=220(about 1 million entries)

If each PTE takes 4 bytes, total Page Table size ≈220×4 bytes=4 MB≈220×4 bytes=4 MB

Note: For 64-bit systems, a flat page table becomes too large, so hierarchical structures (multi-level
page tables) are used to manage memory efficiently.

Pros of Using a Page Table in a Virtual Memory

Efficient Memory Use: Only allocates frames for pages that are actually used.

Protection: Control over access permissions helps prevent illegal memory access.

Flexibility: Supports multiple processes safely accessing different address spaces.

32 | P a g e
Address Translation: Seamless mapping of virtual to physical addresses with little programmer
involvement.

Scalability: Hierarchical page tables (e.g., 4-level page table in x86-64) handle huge address spaces
without huge memory overhead.

Virtual Memory in Operating System

Virtual memory is a memory management technique used by operating systems to give the
appearance of a large, continuous block of memory to applications, even if the physical memory (RAM)
is limited and not necessarily allocated in contiguous manner. The main idea is to divide the process
in pages, use disk space to move out the pages if space in main memory is required and bring back the
pages when needed.

Objectives of Virtual Memory

A program doesn’t need to be fully loaded in memory to run. Only the needed parts are loaded.

Programs can be bigger than the physical memory available in the system.

Virtual memory creates the illusion of a large memory, even if the actual memory (RAM) is small.

It uses both RAM and disk storage to manage memory, loading only parts of programs into RAM as
needed.

This allows the system to run more programs at once and manage memory more efficiently.

How Virtual Memory Works

Virtual memory uses both hardware and software to manage memory.

When a program runs, it uses virtual addresses (not real memory locations).

The computer system converts these virtual addresses into physical addresses (actual locations in
RAM) while the program runs.

33 | P a g e
Types of Virtual Memory

In a computer, virtual memory is managed by the Memory Management Unit (MMU), which is often
built into the CPU. The CPU generates virtual addresses that the MMU translates into physical
addresses. There are two main types of virtual memory: Paging and Segmentation

1. Paging

Paging divides memory into small fixed-size blocks called pages. When the computer runs out of RAM,
pages that aren't currently in use are moved to the hard drive, into an area called a swap file. Here,

The swap file acts as an extension of RAM.

When a page is needed again, it is swapped back into RAM, a process known as page swapping.

This ensures that the operating system (OS) and applications have enough memory to run.

Page Fault Service Time: The time taken to service the page fault is called page fault service time. The
page fault service time includes the time taken to perform all the above six steps.

Let Main memory access time is: mm

Page fault service time is: ss

Page fault rate is : pp

Then, Effective memory access time = (p∗s)+(1−p)∗m(p∗s)+(1−p)∗m

Page and Frame: Page is a fixed size block of data in virtual memory and a frame is a fixed size block
of physical memory in RAM where these pages are loaded.

Think of a page as a piece of a puzzle (virtual memory) While, a frame as the spot where it fits on the
board (physical memory).

When a program runs its pages are mapped to available frames so the program can run even if the
program size is larger than physical memory.

2. Segmentation

Segmentation divides virtual memory into segments of different sizes. Segments that aren't currently
needed can be moved to the hard drive. Here,

The system uses a segment table to keep track of each segment's status, including whether it's in
memory, if it's been modified and its physical address.

Segments are mapped into a process's address space only when needed.

Read more about - Segmentation

Applications of Virtual memory

Virtual memory has the following important characteristics that increase the capabilities of the
computer system.

Increased Effective Memory: It enables a computer to have more memory than the physical memory
using the disk space. This allows for the running of larger applications.

34 | P a g e
Memory Isolation: Virtual memory allocates a unique address space to each process, such separation
increases safety and reliability based on the fact that one process cannot interact with another.

Efficient Memory Management: Virtual memory also helps in better utilization of the physical
memories through methods that include paging and segmentation.

Simplified Program Development: For case of programmers, they can program ‘as if’ there is one big
block of memory and this makes the programming easier and more efficient in delivering more
complex applications.

Management of Virtual Memory

Here are 5 key points on how to manage virtual memory:

1. Adjust the Page File Size

Automatic Management: All contemporary OS including Windows contain the auto-configuration

option for the size of the empirical page file. But depending on the size of the RAM, they are set
automatically, although the user can manually adjust the page file size if required.

Manual Configuration: For tuned up users, the setting of the custom size can sometimes boost up the
performance of the system. The initial size is usually advised to be set to the minimum value of 1.

2. Place the Page File on a Fast Drive

SSD Placement: If this is feasible, the page file should be stored in the SSD instead of the HDD as a
storage device. It has better read and write times and the virtual memory may prove beneficial in an
SSD.

Separate Drive: Regarding systems having multiple drives involved, the page file needs to be placed
on a different drive than the OS and that shall in turn improve its performance.

3. Monitor and Optimize Usage

Performance Monitoring: Employ the software tools used in monitoring the performance of the
system in tracking the amounts of virtual memory.

Regular Maintenance: Make sure there is no toolbar or other application running in the background,
take time and uninstall all the tool bars to free virtual memory.

4. Disable Virtual Memory for SSD

Sufficient RAM: If for instance your system has a big physical memory,

Example: 16GB and above then it would be advised to freeze the page file in order to
minimize SSD usage. But it should be done, carefully and only if the additional signals that one decides
to feed into his applications should not likely use all the available RAM.

5. Optimize System Settings

System Configuration: Change some general properties of the system concerning virtual memory
efficiency. This also involves enabling additional control options in Windows.

Regular Updates: Ensure that your drivers are run in their newest version because new releases
contain some enhancements and issues regarding memory management.

35 | P a g e
Benefits of Using Virtual Memory

Supports Multiprogramming & Larger Programs : Virtual memory allows multiple processes to reside
in memory at once by using demand paging. Even programs larger than physical memory can be
executed efficiently.

Maximizes Application Capacity : With virtual memory, systems can run more applications
simultaneously, including multiple large ones. It also allows only portions of programs to be loaded at
a time, improving speed and reducing memory overhead.

Eliminates Physical Memory Limitations : There's no immediate need to upgrade RAM as virtual
memory compensates using disk space.

Boosts Security & Isolation : By isolating the memory space for each process, virtual memory enhances
system security. This prevents interference between applications and reduces the risk of data
corruption or unauthorized access.

Improves CPU & System Performance: Virtual memory helps the CPU by managing logical
partitions and memory usage more effectively. It allows for cost-effective, flexible resource allocation,
keeping CPU workloads optimized and ensuring smoother multitasking.

Enhances Memory Management Efficiency : Virtual memory automates memory allocation,

including moving data between RAM and disk without user intervention. It also avoids external
fragmentation, using more of the available memory effectively and simplifying OS-level memory
management.

Limitation of Virtual Memory

Slower Performance: Virtual memory can slow down the system, because it often needs to move data
between RAM and the hard drive.

Risk of Data Loss: There is a higher risk of losing data if something goes wrong, like a power failure or
hard disk crash, while the system is moving data between RAM and the disk.

More Complex System: Managing virtual memory makes the operating system more complex. It has
to keep track of both real memory (RAM) and virtual memory and make sure everything is in the right
place.

Virtual Memory vs Physical Memory

Feature Virtual Memory Physical Memory (RAM)

Definition An abstraction that extends the The actual hardware (RAM) that stores data
available memory by using disk and instructions currently being used by the
storage CPU
Location On the hard drive or SSD On the computer's motherboard
Speed Slower (due to disk I/O operations) Faster (accessed directly by the CPU)
Capacity Larger, limited by disk space Smaller, limited by the amount of RAM
installed
Cost Lower (cost of additional disk Higher (cost of RAM modules)
storage)
Data Indirect (via paging and swapping) Direct (CPU can access data directly)
Access
Volatility Non-volatile (data persists on disk) Volatile (data is lost when power is off)

36 | P a g e
What is Demand Paging in Operating System?

Demand paging is a technique used in virtual memory systems where pages enter main memory only
when requested or needed by the CPU. OS loads only the necessary pages of a program into memory
at runtime, instead of loading the entire program into memory at the start. Here, A page fault
occurred when the program needed to access a page that is not currently in memory.

The operating system then loads the required pages from the disk into memory and updates the page
tables accordingly.

This process is transparent to the running program and it continues to run as if the page had always
been in memory.

Pure Demand Paging

Pure demand paging is a specific implementation of demand paging. In on-demand paging only, no
pages are initially loaded into memory when the program starts and all pages are initially marked as
being on disk.

Operating systems that use pure demand paging as a memory management strategy do so without
preloading any pages into physical memory prior to the commencement of a task.

Demand paging loads a process's whole address space into memory one step at a time, bringing just
the parts of the process that are actively being used into memory from disc as needed.

It is useful for executing huge programs that might not fit totally in memory or for computers with
limited physical memory. If the program accesses a lot of pages that are not in memory right now, it
could also result in a rise in page faults and possible performance overhead.

Operating systems frequently use caching techniques and improve page replacement algorithms to
lessen the negative effects of page faults on system performance as a whole.

Working Process of Demand Paging: Let us understand this with the help of an example. Suppose we
want to run a process P which have four pages P0, P1, P2 and P3. Currently, in the page table, we have
pages P1 and P3.

37 | P a g e
The operating system's demand paging mechanism follows a few steps in its operation:

Program Execution: Upon launching a program, the operating system allocates a certain amount of
memory to the program and establishes a process for it.

Creating Page Tables: To keep track of which program pages are currently in memory and which are
on disk, the operating system makes page tables for each process.

Handling Page Fault: When a program tries to access a page that isn't in memory at the moment, a
page fault happens. In order to determine whether the necessary page is on disk, the operating system
pauses the application and consults the page tables.

Page Fetch: The operating system loads the necessary page into memory by retrieving it from the disk
if it is there.

The page's new location in memory is then reflected in the page table.

Resuming The Program: The operating system picks up where it left off when the necessary pages are
loaded into memory.

Page Replacement: If there is not enough free memory to hold all the pages a program needs, the
operating system may need to replace one or more pages currently in memory with pages currently
in memory. on the disk. The page replacement algorithm used by the operating system determines
which pages are selected for replacement.

Page Cleanup: When a process terminates, the operating system frees the memory allocated to the
process and cleans up the corresponding entries in the page tables.

How Demand Paging in OS Affects System Performance?

Demand paging can improve system performance by reducing the memory needed for programs and
allowing multiple programs to run simultaneously.

If not implemented properly, it can cause performance issues.

When a program needs a part that isn’t in the main memory, the operating system must fetch it from
the hard disk, which takes time and pauses the program.

This can cause delays and if the system runs out of memory, it will need to frequently swap pages in
and out, increasing delays and reducing performance.

Common Algorithms Used for Demand Paging in OS

If a program needs a page that isn’t currently in memory, the system fetches it from the hard disk.
Several algorithms manage this process:

FIFO (First-In-First-Out): Replaces the oldest page in memory with a new one. It’s simple but can cause
issues if pages are frequently swapped in and out, leading to thrashing.

LRU (Least Recently Used): Replaces the page that hasn’t been used for the longest time. It reduces
thrashing more effectively than FIFO but is more complex to implement.

LFU (Least Frequently Used): Replaces the page used the least number of times. It helps reduce
thrashing but requires extra tracking of how often each page is used.

38 | P a g e
MRU (Most Recently Used): Replaces the page that was most recently used. It’s simpler than LRU but
not as effective in reducing thrashing.

Random: Randomly selects a page to replace. It’s easy to implement but unpredictable in
performance.

Demand Paging in OS vs Pre-Paging

Demand paging

It loads pages from disk into main memory only when they are needed by a program.

This approach saves memory space by keeping only the required pages in memory, reducing memory
allocation costs and improving memory use.

However, the initial access time for pages not in memory can delay program execution.

Pre-paging

It loads multiple pages into main memory before they are needed by a program.

It assumes that if one page is needed, nearby pages will also be needed soon.

Pre-paging can speed up program execution by reducing delays caused by demand paging but can lead
to unnecessary memory allocation and waste.

Page Fault Handling in Operating System

A page fault occurs when a program attempts to access data or code that is in its address space but is
not currently located in the system RAM. This triggers a sequence of events where the operating
system must manage the fault by loading the required data from secondary storage into RAM.

Note: Page faults are essential for implementing virtual memory systems that provide the illusion of
a larger contiguous memory space.

39 | P a g e
Steps for Page Fault Handling

Trap to Kernel: The computer hardware traps to the kernel and program counter (PC) is saved on the
stack. Current instruction state information is saved in CPU registers. The hardware detects the page
fault when the CPU attempts to access a virtual page that is not currently in physical memory (RAM).

Save State Information: An assembly program is started to save the general registers and other volatile
information to keep the OS from destroying it.

Determine Cause of Fault: Operating system finds that a page fault has occurred and tries to find out
which virtual page is needed. Sometimes hardware register contains this required information. If not,
the operating system must retrieve PC, fetch instruction and find out what it was doing when the fault
occurred.

Validate Address: Once virtual address caused page fault is known, system checks to see if address is
valid and checks if there is no protection access problem.

Allocate Page Frame: If the virtual address is valid, the system checks to see if a page frame is free. If
no frames are free, the page replacement algorithm is run to remove a page.

Handle Dirty Pages: If frame selected is dirty, page is scheduled for transfer to disk, context switch
takes place, fault process is suspended and another process is made to run until disk transfer is
completed.

Load Page into Memory: As soon as page frame is clean, operating system looks up disk address where
needed page is, schedules disk operation to bring it in.

Update Page Table: When disk interrupt indicates page has arrived, page tables are updated to reflect
its position, and frame marked as being in normal state.

Restore State and Continue Execution: Faulting instruction is backed up to state it had when it began,
and PC is reset. Faulting is scheduled, operating system returns to routine that called it. Assembly
Routine reloads register and other state information, returns to user space to continue execution.

Causes of Page Faults

There are several reasons of causing Page faults:

Demand Paging: Accessing the page that is not currently loaded in the memory (RAM).

Invalid Memory Access, it occurs when a program tries to access that memory which is it's beyond
access boundaries or not allocated.

Process Violation: when a process tries to write to a read-only page or otherwise violates memory
protection rules.

Types of Page Fault

Minor Page Fault: Occurs when the required page is in memory but not in current process's page table.

Major Page Fault: Occurs when the page is not in memory and must be fetched from disk.

Invalid Page Fault: It happens when the process tries to access an invalid memory address.

Impact of Page Faults or System Performance

Page Fault impact the system if it occurs frequently

40 | P a g e
Thrashing: If occurrence of page fault is frequent then the system spends more time to handle it than
executing the processes, and because of which overall performance also degrades.

Increased Latency: Fetching pages from disk takes more time than accessing them in memory, which
causes to more delays.

CPU Utilization: If the Page fault occur excessively than it can reduce CPU Utilization as the processor
waits for for memory operations to complete or remain idle which is not efficient.

Swap Space in Operating System

Modern operating systems use both physical memory (RAM) and virtual memory to manage processes
efficiently. Swap space (also called paging space or swap file) plays a key role in this memory
management strategy. It is a dedicated area on the hard disk used by the operating system as an
extension of physical RAM

Swapping

Note: Swap space enables the OS to handle memory more flexibly, supporting the illusion of a larger
memory than physically available, thus improving multitasking and stability of the system.

Working of Swap Space

When physical memory (RAM) is full, the OS selects some memory pages that are inactive or least
recently used (using algorithms like LRU – Least Recently Used).

These pages are written from RAM to the swap space on the disk.

When those pages are needed again, they are read back from the swap space into RAM.

This process of moving pages between RAM and disk is called swapping or paging.

Note: Despite its usefulness, accessing swap space is much slower than RAM due to disk I/O delays.

41 | P a g e
Optimal Swap Space Size

A general rule of thumb recommends swap space size to be about 1.5 times the size of physical RAM.
However, the exact swap size depends on the system's use case:

Systems with high RAM and low memory usage may need less swap.

Memory-intensive applications or environments with many background processes may require more
swap.

Note: Modern systems with large amounts of RAM often use much smaller swap sizes, just to handle
exceptional cases.

Swap Space vs Virtual Memory

Feature Swap Space Virtual Memory

Definition Physical disk space used for Abstract combination of physical RAM
swapping memory pages and swap space
Role Storage area for inactive pages Provides an abstraction of larger
memory to applications
Performance Slow access (due to disk I/O) Appears seamless to applications
Implementation Typically a swap partition or swap Managed by OS using page tables
file

Pros of Swap Space

Virtual Memory Extension: Allows processes to operate as if there is more memory available than the
system physically has.

Increased System Stability: Prevents system crashes when RAM is exhausted by providing additional
space.

Efficient Multitasking: Frees up physical memory for more active processes and critical operations.

Supports Memory-Intensive Applications: Enables running large applications that require more
memory than physically available.

Cons of Swap Space

Performance Degradation: Reading from and writing to swap space is orders of magnitude slower than
accessing RAM.

Disk Space Consumption: Swap space occupies significant hard disk space, which may reduce space
available for files and applications.

Thrashing: Excessive swapping (when the system spends most of its time swapping pages rather than
executing useful tasks) severely hampers performance.

Data Loss Risk: If a power failure occurs while a page is in swap space and not yet committed back to
disk, data may be lost.

42 | P a g e
Page Replacement Algorithms in Operating Systems

In an operating system that uses paging, a page replacement algorithm is needed when a page fault
occurs and no free page frame is available. In this case, one of the existing pages in memory must be
replaced with the new page.

The virtual memory manager performs this by: Selecting a victim page using a page replacement
algorithm. Marking its page table entry as “not present.” If the page was modified (dirty), writing it
back to disk before replacement.

The efficiency of a page replacement algorithm directly affects the page fault rate, which in turn
impacts system performance.

Common Page Replacement Techniques

 First In First Out (FIFO)

 Optimal Page replacement
 Least Recently Used (LRU)
 Most Recently Used (MRU)

1. First In First Out (FIFO)

This is the simplest page replacement algorithm. In this algorithm, the operating system keeps track
of all pages in the memory in a queue, the oldest page is in the front of the queue. When a page needs
to be replaced page in the front of the queue is selected for removal.

Example 1: Consider page reference string 1, 3, 0, 3, 5, 6, 3 with 3-page frames. Find the number of
page faults using FIFO Page Replacement Algorithm.

FIFO - Page Replacement

Initially, all slots are empty, so when 1, 3, 0 came they are allocated to the empty slots ---> 3 Page
Faults.

When 3 comes, it is already in memory so ---> 0 Page Faults.

Then 5 comes, it is not available in memory, so it replaces the oldest page slot i.e 1. ---> 1 Page Fault.

6 comes, it is also not available in memory, so it replaces the oldest page slot i.e 3 ---> 1 Page Fault.

Finally, when 3 come it is not available, so it replaces 0 1-page fault.

Program for Page Replacement Algorithm (FIFO)

43 | P a g e
2. Optimal Page Replacement

In this algorithm, pages are replaced which would not be used for the longest duration of time in the
future. Example: Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4-page frame.
Find number of page fault using Optimal Page Replacement Algorithm.

Optimal Page Replacement

Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots ---> 4 Page faults

0 is already there so ---> 0 Page fault. when 3 came it will take the place of 7 because it is not used for
the longest duration of time in the future---> 1 Page fault.

0 is already there so ---> 0 Page fault. 4 will takes place of 1 ---> 1 Page Fault.

Now for the further page reference string ---> 0 Page fault because they are already available in the
memory. Optimal page replacement is perfect, but not possible in practice as the operating system
cannot know future requests. The use of Optimal Page replacement is to set up a benchmark so that
other replacement algorithms can be analyzed against it.

3. Least Recently Used

In this algorithm, page will be replaced which is least recently used. Example Consider the page
reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4-page frames. Find number of page faults
using LRU Page Replacement Algorithm.

Least Recently Used - Page Replacement

44 | P a g e
Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots ---> 4 Page faults.

0 is already there so ---> 0 Page fault. when 3 came it will take the place of 7 because it is least recently
used ---> 1 Page fault.

0 is already in memory so ---> 0 Page fault.

4 will takes place of 1 ---> 1 Page Fault.

Now for the further page reference string ---> 0 Page fault because they are already available in the
memory.

4. Most Recently Used (MRU)

In this algorithm, page will be replaced which has been used recently. Belady's anomaly can occur in
this algorithm.

Example 4: Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4-page frames.

Find number of page faults using MRU Page Replacement Algorithm.

Most Recently Used - Page Replacement

Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots ---> 4 Page faults

0 is already their so--> 0 page fault

when 3 comes it will take place of 0 because it is most recently used ---> 1 Page fault

when 0 comes it will take place of 3 ---> 1 Page fault

when 4 comes it will take place of 0 ---> 1 Page fault

2 is already in memory so ---> 0 Page fault

when 3 comes it will take place of 2 ---> 1 Page fault

when 0 comes it will take place of 3 ---> 1 Page fault

when 3 comes it will take place of 0 ---> 1 Page fault

when 2 comes it will take place of 3 ---> 1 Page fault

when 3 comes it will take place of 2 ---> 1 Page fault

45 | P a g e
Thrashing

Thrashing occurs when the operating system spends more time swapping pages between main
memory and disk than executing processes. This leads to excessive page faults and a significant drop
in CPU utilization.

The cycle works like this:

High degree of multiprogramming: Too many processes are loaded into memory.

Lack of frames: Each process gets fewer frames than needed.

Page replacement policy: Frequent replacements increase page faults.

This repeated cycle of low CPU utilization → more processes → more page faults is called Thrashing.

Locality Model

The concept of locality of reference helps explain thrashing:

A locality is a set of pages that a program actively uses together.

For example, when a function is called, instructions, local variables, and global references define a
locality.

If the number of frames allocated to a process covers its current locality → few page faults.

If frames are fewer than the locality size → frequent page faults → thrashing.

Thrashing happens when active localities of multiple processes cannot fit into memory
simultaneously.

Techniques to Handle Thrashing

1. Working Set Model

Based on the Locality Model: a process uses a set of pages (locality) actively at a time.

If enough frames are allocated to cover the current locality few page faults.

If frames < locality size process will thrash.

46 | P a g e
Working Set (WSSᵢ) = pages referenced in the last Δ references (window size).

Total demand: D = Σ WSSᵢ

Cases:

If D > m (m = available frames) i.e Thrashing occurs.

If D ≤ m i.e No thrashing.

Accuracy depends on Δ:

Large Δ, overlapping working sets.

Small Δ, locality may not be fully captured.

2. Page Fault Frequency

PFF is a technique to control thrashing by directly monitoring the page fault rate of processes.

Working:

Define an upper limit and a lower limit for acceptable page fault rate.

If fault rate > upper limit, give more frames to the process.

If fault rate < lower limit, take away frames.

If no free frames are available suspend some processes and reallocate frames.

47 | P a g e