OPERATING SYSTEMS (UE24CS242B) • The program can access any physical memory address.

Unit-3: Memory Management • The system creates the illusion that the program has full control over the machine.

Lecture 1 - Main Memory – Hardware and Control Structures However, this approach wastes CPU time when the program performs I/O operations.

1. Background 4. Multiprogramming

Memory is one of the most important components of a computer system. It consists of a large Modern operating systems use multiprogramming, where multiple processes are loaded into
array of bytes, where each byte has its own unique address. These addresses allow the CPU to memory simultaneously.
locate and access specific data or instructions stored in memory. In such systems:
When a program executes, the CPU performs a sequence of operations: • Several processes share the CPU.
1. Fetch – The CPU fetches an instruction from memory. • One process executes while others wait for I/O operations.
2. Decode – The fetched instruction is decoded to determine the required operation. This creates new challenges:
3. Operand Fetch – Required operands are fetched either from registers or memory. 1. Protection of the operating system from user processes.
4. Execute – The instruction is executed. 2. Protection of processes from each other.
5. Store Result – The result is stored back in memory or registers. Since the CPU directly accesses memory, protection must be implemented by hardware
From the perspective of the memory unit (MU), it only sees a continuous stream of memory mechanisms, not by the operating system software alone.
addresses. It does not know how these addresses were generated or which instructions caused 5. Base and Limit Registers
them.
One common hardware protection mechanism uses two registers:
2. Basic Hardware
• Base register
Before a program can execute, it must be loaded from disk into main memory. Once loaded, it
is placed in the ready queue, waiting to be scheduled by the CPU. • Limit register

The CPU can directly access only two types of storage: These registers define the logical address space available to a process.

• CPU registers Base Register - The base register contains the smallest legal physical address that a process
can access.
• Main memory
Limit Register - The limit register specifies the size of the allowed memory region.
Registers provide extremely fast access and can be accessed within one CPU clock cycle or
less. However, main memory access is slower and may require several cycles. This delay can Every memory access generated by a process must satisfy:
cause the CPU to stall. Base ≤ Address < Base + Limit
To improve performance, a cache memory is placed between CPU registers and main memory. If the address falls outside this range, the hardware generates a trap to the operating system,
Cache stores frequently used instructions and data, allowing faster access. preventing illegal memory access.
Another important requirement in modern systems is memory protection. Protection ensures Base and Limit Address Protection
that a program does not accidentally or intentionally modify memory belonging to other
programs or the operating system.
3. Uniprogramming
In early computer systems, uniprogramming was used. In this approach, only one program
runs in memory at a time.
Characteristics of uniprogramming include:
• The program always runs at the same location in physical memory.
• Since no other program exists in memory, there is no need for protection mechanisms.

Pavan A C (pavanac@[Link]) 1 Pavan A C (pavanac@[Link]) 2

6. Hardware Address Protection The final address is determined when the program is loaded into memory.
The base and limit registers prevent a user program from modifying: Execution-Time Binding - If the process may move during execution, binding must occur at
run time.
• Operating system code
This requires special hardware support such as a Memory Management Unit (MMU).
• Data structures of other processes
9. Multistep Processing of a User Program
• Memory belonging to other users
A program undergoes several steps before execution:
Only the operating system can modify these registers. This is achieved using privileged
instructions, which can execute only in kernel mode. 1. Source Program (written in high-level language)
User programs running in user mode cannot change these register values. 2. Compiler converts it to object code
3. Linker combines modules and libraries
4. Loader places program into memory
5. Execution begins
At each step, addresses are translated from one format to another.
10. Memory Management Unit (MMU)
The Memory Management Unit (MMU) is a hardware device that performs address translation.
It maps logical addresses generated by the CPU into physical addresses used by the memory
unit.
7. Address Binding
For example:
Programs are stored on disk as binary executable files and are loaded into memory before
execution. Physical Address = Logical Address + Relocation Register
During execution, processes may move between disk and memory. A process does not The MMU performs this translation dynamically at runtime.
necessarily start at memory location 0. Instead, it can be placed anywhere in physical memory.
11. Logical vs Physical Address Space
Address binding refers to the process of mapping one address space to another.
Understanding logical and physical addresses is central to memory management.
Types of Addresses
Logical Address
1. Symbolic addresses - Used in source code (e.g., variable names).
• Generated by the CPU
2. Relocatable addresses - Generated by the compiler relative to the start of the program.
• Also called virtual address
3. Absolute addresses - Actual physical memory addresses.
Physical Address
The compiler, linker, and loader convert symbolic addresses step by step into physical
• Actual address in main memory
addresses.
• Used by the memory hardware
8. Address Binding Stages
Logical and physical addresses are identical in compile-time and load-time binding, but they
Address binding can occur at three different stages.
differ in execution-time binding.
Compile-Time Binding - If the starting memory location of a program is known at compile
12. Dynamic Linking
time, the compiler generates absolute code.
Linking is the process of combining program code with library functions.
However, if the starting address changes, the program must be recompiled.
Static Linking - In static linking, system libraries are combined with the program during
Load-Time Binding - If the starting location is not known at compile time, the compiler
compilation or loading.
generates relocatable code.
Disadvantage:

Pavan A C (pavanac@[Link]) 3 Pavan A C (pavanac@[Link]) 4

 • Each program contains its own copy of library functions, wasting memory. OPERATING SYSTEMS (UE24CS242B)
Dynamic Linking - In dynamic linking, linking occurs during execution. Instead of embedding Unit-3: Memory Management
full library code, a small piece of code called a stub is included.
Lecture 2 - Swapping, Memory Allocation, Fragmentation
The stub:
1. Swapping
1. Locates the required library function.
Swapping is a memory-management technique where a process is temporarily moved from
2. Replaces itself with the address of that function. main memory to secondary storage (disk) and later brought back into memory to continue
3. Transfers control to the library routine. execution. This technique allows the system to run more processes than the available physical
memory can accommodate.
Dynamic linking allows shared libraries, which improves memory efficiency.
The secondary storage used for this purpose is called the backing store. The backing store must
13. Dynamic Linking in Linux be large enough to hold copies of all memory images of processes and must allow direct access
Linux implements dynamic linking through a special linker library. to these memory images.

Steps include: One variation of swapping is called roll-out, roll-in, which is commonly used with priority-
based scheduling algorithms. In this method, a low-priority process is swapped out of memory
1. Program contains a small statically linked function. so that a higher-priority process can be loaded and executed.
2. When the program starts, this function loads required libraries into memory. The total time required for swapping depends mainly on the amount of memory being
3. The dynamic linker resolves references to functions and variables. transferred. Since swapping involves disk I/O, the transfer time forms the major part of the
swap time.
Shared libraries are compiled using Position Independent Code (PIC) so they can be loaded
anywhere in memory. The operating system maintains a ready queue containing processes that are ready to execute
but whose memory images are stored on disk.
2. Schematic View of Swapping
In standard swapping, entire processes are moved between main memory and the backing
store.
Working Principle
1. When memory becomes full, some inactive processes are swapped out to disk.
2. This frees memory space for active processes.
3. If a swapped-out process becomes active again, it must be swapped back into memory
before execution.
This mechanism allows the operating system to oversubscribe physical memory, meaning
the total memory required by all processes can exceed the actual physical memory.
Idle or inactive processes are ideal candidates for swapping because their memory space can
be temporarily reassigned to other processes.

Pavan A C (pavanac@[Link]) 5 Pavan A C (pavanac@[Link]) 1

3. Context Switch Time Including Swapping In this approach, each process occupies a single contiguous block of memory. The memory
layout typically consists of two main partitions:
Normally, a context switch involves saving the state of one process and loading the state of
another. However, if the next process to execute is not present in main memory, swapping 1. Operating System region - Usually stored in low memory and contains interrupt
must occur before the context switch. vectors and system code.
This significantly increases the context-switch time. 2. User processes region - Located in high memory.
Example Each process is placed in a continuous memory region adjacent to other processes.
Process size = 100 MB, Disk transfer rate = 50 MB/sec
Swap-out time:
100 MB / 50 MB/sec = 2 seconds
Swap-in time = 2 seconds
Total swapping overhead during context switch:
Swap out + Swap in = 4 seconds
If the process size is 3 GB:
3 GB ≈ 3000 MB, 3000 MB / 50 MB/sec = 60 seconds
Thus, swapping large processes is extremely slow.
4. Limitations of Swapping 7. Interrupt Vector
Swapping introduces several practical issues:
An interrupt vector is a memory location that stores the starting address of an interrupt service
1. Pending I/O Problem routine (ISR).

A process waiting for I/O cannot be swapped out easily because the I/O operation may write The interrupt vector table is usually stored in the first 1024 bytes of memory.
data to a memory location that no longer belongs to that process. Key characteristics:
To avoid this problem, some systems use double buffering, where data is first transferred to
• Contains 256 interrupt vectors
kernel space before moving to process memory. However, this increases overhead.
• Each vector is 4 bytes
2. Performance Overhead
• Stores the address of the ISR
Since disk access is much slower than memory access, swapping entire processes can
significantly reduce system performance. Address range: 000000H – 0003FFH
Because of these limitations, standard whole-process swapping is rarely used in modern 8. Relocation and Limit Registers
operating systems.
In contiguous allocation, relocation (base) registers and limit registers are used for protection
5. Swapping in Modern Systems (Linux Perspective) and address translation.
Modern operating systems like Linux use demand paging instead of whole-process Relocation Register - Stores the starting physical address of a process.
swapping.
Limit Register - Specifies the maximum logical address range that the process can access.
Instead of swapping entire processes, Linux swaps only small blocks of memory called pages
When the CPU scheduler selects a process for execution, the dispatcher loads these registers
(typically 4 KB each). This technique improves performance and reduces disk I/O overhead.
during the context switch.
6. Contiguous Memory Allocation
The MMU then dynamically converts logical addresses into physical addresses.
Contiguous allocation is one of the earliest memory allocation techniques.
9. Multiple-Partition Allocation
To improve memory utilization, memory can be divided into multiple partitions.

Pavan A C (pavanac@[Link]) 2 Pavan A C (pavanac@[Link]) 3

Two approaches exist: Advantages:
Fixed Partitioning • Leaves large remaining holes
Memory is divided into fixed-size partitions. Disadvantages:
Characteristics: • Inefficient memory utilization.
• Each partition holds exactly one process. Generally, first-fit and best-fit perform better than worst-fit.
• Degree of multiprogramming is limited by the number of partitions. 11. Linux Memory Allocation (Buddy System)
This technique was used in early systems such as IBM OS/360. Modern operating systems such as Linux avoid traditional first-fit or best-fit strategies.
Variable Partitioning Instead, Linux uses the Buddy Allocator.
Partitions are created dynamically based on process size. Key idea:
The operating system maintains a table containing: • Memory blocks are divided into sizes that are powers of two.
• Allocated partitions Example block sizes:
• Free partitions (holes) 4 KB
8 KB
A hole is a block of available memory that can accommodate new processes.
16 KB
When a process terminates, its partition becomes free and may be merged with adjacent holes. 32 KB
64 KB
10. Dynamic Storage Allocation Problem
When memory is allocated or freed, blocks can easily be split or merged, making allocation
When a process requests memory, the operating system must decide which free memory block fast and efficient.
should be allocated.
12. Fragmentation
Three common strategies exist.
Fragmentation occurs when memory space is used inefficiently.
1. First-Fit
Two types exist.
The system allocates the first hole that is large enough to satisfy the request.
Internal Fragmentation
Advantages:
Internal fragmentation occurs when the allocated memory block is slightly larger than the
• Fast allocation requested memory.
Disadvantages: Example:
• May lead to fragmentation near the beginning of memory. Process requires 400 KB, but partition size is 512 KB.
2. Best-Fit Unused memory inside the partition becomes wasted space.
The system allocates the smallest hole that is large enough. External Fragmentation
Advantages: External fragmentation occurs when total free memory exists but is not contiguous.
• Minimizes leftover space For example, free memory may be split into several small holes that cannot satisfy a large
Disadvantages: request.

• Requires searching the entire memory list. 13. Fragmentation Rule (0.5N Rule)

3. Worst-Fit According to the 0.5N rule:

The system allocates the largest available hole. For every N blocks allocated, about 0.5N blocks are lost due to fragmentation.
This means roughly:

Pavan A C (pavanac@[Link]) 4 Pavan A C (pavanac@[Link]) 5

 • 66% memory is allocated to processes OPERATING SYSTEMS (UE24CS242B)
• 33% becomes fragmented memory Unit-3: Memory Management
14. Compaction Lecture 3 - Segmentation
Compaction is a technique used to reduce external fragmentation. 1. Segmentation
In this method: Segmentation is a memory-management scheme that supports the user’s logical view of
1. Memory contents are rearranged. memory. Instead of treating memory as a single linear array of bytes, segmentation divides a
program into logical units called segments.
2. All free memory blocks are combined into a single large block.
A program is naturally composed of multiple logical components, and segmentation maps these
However, compaction has several disadvantages: components directly into memory segments. Each segment corresponds to a meaningful
• Requires dynamic relocation program structure.

• Introduces large CPU overhead Examples of segments include:

• Involves copying large memory blocks • Main program

Because of these limitations, compaction is rarely used in modern systems. • Procedure

• Function
• Method
• Object
• Local variables
• Global variables
• Stack
• Arrays
• Symbol table
• Common block
Programmers generally think about programs in terms of these logical components rather than
as a continuous block of memory. Segmentation therefore provides a memory model that
closely matches the programmer’s view.
2. User’s View of a Program
Segmentation supports the natural way programmers organize programs. Each program is
divided into separate segments, each having its own name and length.
A logical address in segmentation is expressed as:
Segment number + Offset
The segment number identifies the segment, while the offset identifies the location within that
segment.
For example:
<segment, offset>

Pavan A C (pavanac@[Link]) 6 Pavan A C (pavanac@[Link]) 1

This means that the CPU must first identify the segment and then calculate the exact address 1. Segment Base - Starting physical address of the segment in memory.
inside that segment.
2. Segment Limit - Length of the segment.
3. Logical View of Segmentation
Two special registers support segmentation:
A logical address space in segmentation consists of a collection of segments.
Segment-Table Base Register (STBR)
From the user’s perspective:
• Points to the location of the segment table in memory.
• Programs appear as independent logical blocks
Segment-Table Length Register (STLR)
• Segments may vary in size
• Indicates the number of segments used by the program.
• Segments can be placed anywhere in physical memory
The segment number s must satisfy:
Thus, segmentation allows a program’s logical structure to remain intact even though its
s < STLR
segments may be stored at different locations in physical memory.
If this condition is violated, the system generates an exception.
6. Segmentation Hardware
When the CPU generates a logical address <s, d>:
1. The segment number (s) is used as an index into the segment table.
2. The offset (d) is compared with the segment limit.
3. If the offset exceeds the segment limit, the system generates a trap to the operating
system (segmentation fault).
4. If the offset is valid, it is added to the segment base address.
Physical address calculation:
This illustrates that logical segments do not need to be stored contiguously in physical memory.
Physical Address = Segment Base + Offset
4. Segmentation Basics
Thus, the segment table acts like an array of base-limit register pairs.
Segmentation divides memory into logical pieces, where each piece contains related
information.
Typical segmentation structure:
• Code segment → program instructions
• Data segment → global variables
• Stack segment → function calls and local variables
• Heap segment → dynamic memory allocation
This structure allows different segments of a process to be stored in different locations of
physical memory, making segmentation a non-contiguous memory allocation technique.
5. Segmentation Architecture
In segmentation, the logical address generated by the CPU consists of two components:
7. Segmentation Example
<segment number (s), offset (d)>
Suppose a program contains five segments numbered 0 to 4.
The system uses a segment table to translate this logical address into a physical address.
Each segment table entry stores:
Each entry in the segment table contains:

Pavan A C (pavanac@[Link]) 2 Pavan A C (pavanac@[Link]) 3

 • Base (starting physical address) Two processes can share the same segment by pointing their segment table entries to the same
base address.
• Limit (segment length)
Example uses:
Example logical address:
• Shared libraries
<segment, offset>
• Shared data structures
The offset must be less than the segment limit. If the offset exceeds the limit, the address is
invalid. • Interprocess communication
8. Example Problem Because the same physical memory is referenced by multiple processes, memory sharing
becomes efficient.
Segment table:
10. Disadvantages of Segmentation
Segment Base Limit
The major disadvantage of segmentation is:
0 219 600
External Fragmentation
1 2300 14
Since segments are variable in size, free memory becomes scattered across the system. Even if
2 90 100 enough total memory exists, a process may not be allocated memory because the free space is
not contiguous.
3 1327 580
This limitation led to the development of paging, which divides memory into fixed-size blocks
4 1952 96 to eliminate external fragmentation.

Find the physical address for the following logical addresses.

a) (0, 430)
Physical Address = 219 + 430 = 649
b) (1, 10)
Physical Address = 2300 + 10 = 2310
c) (2, 500)
Segment limit = 100, Offset = 500
Since:
500 > 100
This is an illegal address → segmentation fault.
d) (3, 400)
Physical Address = 1327 + 400 = 1727
e) (4, 112)
Segment limit = 96, Offset = 112
112 > 96
This is an illegal address.
9. Shared Segments
Segmentation also supports shared memory.

Pavan A C (pavanac@[Link]) 4 Pavan A C (pavanac@[Link]) 5

 OPERATING SYSTEMS (UE24CS242B) • 1 GB

Unit-3: Memory Management 3. Paging Model of Logical and Physical Memory

Lecture 4 – Paging Paging allows logical memory to be mapped to physical memory in a non-contiguous
manner.
1. Introduction to Paging
This means that consecutive logical pages do not have to be stored in consecutive physical
Paging is a memory-management technique that allows the physical address space of a frames.
process to be non-contiguous. Similar to segmentation, paging removes the requirement that
an entire process must occupy a single continuous block of memory. Example mapping:

One of the main motivations behind paging is to eliminate the problem of external Logical Pages
fragmentation that occurs in contiguous memory allocation. Since memory is divided into Page 0
fixed-size blocks, paging ensures that free memory can always be allocated efficiently without Page 1
requiring compaction. Page 2
Paging also simplifies the management of memory on the backing store (disk). In earlier Page 3
techniques, storing memory chunks of varying sizes created complexity. Paging solves this by may be stored in physical memory frames as:
handling memory in uniform units.
Frame 5
However, while paging removes external fragmentation, it may still introduce internal Frame 2
fragmentation, where a page may not fully utilize the allocated frame. Frame 7
2. Basic Method of Paging Frame 1

The basic idea of paging is to divide both logical and physical memory into equal-sized blocks. The operating system keeps track of this mapping through the page table.

• Physical memory is divided into fixed-size blocks called frames.

• Logical memory is divided into blocks of the same size called pages.
The size of pages and frames is determined by the hardware architecture and is always equal.
When a program needs to execute:
1. The operating system divides the program into pages.
2. It searches for free frames in physical memory.
3. Each page is loaded into one of the available frames.
4. The operating system maintains a page table that maps pages to frames.
If a program contains N pages, the operating system must locate N free frames to store those 4. Paging Hardware
pages.
Paging requires special hardware support to translate addresses quickly.
Checking Page Size in Linux
The key hardware component used is the Memory Management Unit (MMU).
The page size supported by a system can be checked using the command:
The MMU performs address translation using the page table. The CPU generates a logical
getconf PAGESIZE address, and the MMU converts it into a physical address using the mapping information stored
in the page table.
Typical page sizes include:
The operating system stores the page table in memory, and a page table base register (PTBR)
• 4 KB points to its location.
• 8 KB
• 2 MB

Pavan A C (pavanac@[Link]) 1 Pavan A C (pavanac@[Link]) 2

 Logical Address = 16 bits
Page Size = 4 KB (2^12)

Page number = 4 bits

Offset = 12 bits
This division allows the system to locate the page and the exact byte within the page.
7. Paging Example
Consider the following example:
Logical address parameters:
m=4
n=2
Page size:
5. Address Translation Scheme
2^2 = 4 bytes
In paging, the logical address generated by the CPU is divided into two parts:
Logical address space:
Logical Address = Page Number + Page Offset
2^4 = 16 bytes
Page Number (p)
Physical memory size:
• Identifies which page in the logical address space is being referenced.
32 bytes
• Used as an index into the page table.
Number of frames:
Page Offset (d)
32 / 4 = 8 frames
• Specifies the exact location within the page.
Thus:
• Logical memory = 4 pages
• Physical memory = 8 frames
Since frames and pages have fixed sizes, external fragmentation does not occur. However,
The page table entry provides the frame number, which is combined with the offset to the last page may not be completely filled, causing internal fragmentation.
generate the physical address.
8. Free Frames
Physical Address Calculation
The operating system maintains a list of free frames in physical memory.
Physical Address = Frame Number + Offset
Before a process is loaded:
6. Address Structure
• Frames are marked as free.
If:
When a process is loaded:
• Logical address space = 2𝑚
• Required frames are allocated.
• Page size = 2𝑛
• The page table is updated to reflect page-to-frame mapping.
Then:
Example:
• High-order (m − n) bits represent the page number.
Before allocation:
• Low-order n bits represent the offset.
Frame 0 – Free
Example: Frame 1 – Free

Pavan A C (pavanac@[Link]) 3 Pavan A C (pavanac@[Link]) 4

 Frame 2 – Free 3. If not found (TLB miss), the system must access the page table in memory.
Frame 3 – Free
Using a TLB significantly improves address translation speed.
After allocation:
11. Fragmentation in Paging
Frame 0 – Page 0
Paging eliminates external fragmentation because all frames are of equal size.
Frame 1 – Page 1
Frame 2 – Page 2 However, internal fragmentation may still occur.
Frame 3 – Page 3
Example:
Page size = 4 KB
Process requires 10 KB
Memory allocation:
Page 1 → 4 KB
Page 2 → 4 KB
Page 3 → 4 KB
Total allocated = 12 KB
Unused memory = 2 KB (internal fragmentation).
12. Advantages of Paging
Paging provides several advantages:
• Eliminates external fragmentation
• Allows efficient use of memory
9. Page Table Management
• Enables non-contiguous allocation
The operating system maintains a separate page table for each process.
• Simplifies memory allocation
The page table performs two important functions:
• Supports virtual memory systems
1. Address Translation - Converts logical addresses generated by the CPU into physical
13. Disadvantages of Paging
addresses.
Despite its advantages, paging has some drawbacks:
2. Memory Protection - Ensures that processes access only their allocated memory
frames. • Page table requires additional memory
During a context switch, the CPU dispatcher loads the page table of the new process into the • Address translation introduces overhead
hardware registers.
• Internal fragmentation may occur
However, this increases the context switch time because the system must update the page table
information. • Context switching becomes more complex

10. Reducing Context Switch Overhead (TLB)

To reduce the overhead of frequent page table accesses, systems use a hardware cache called
the Translation Lookaside Buffer (TLB).
The TLB stores recently used page table entries.
When the CPU generates a logical address:
1. The system first checks the TLB.
2. If the mapping is found (TLB hit), address translation is very fast.

Pavan A C (pavanac@[Link]) 5 Pavan A C (pavanac@[Link]) 6

 OPERATING SYSTEMS (UE24CS242B) Typical characteristics of a TLB:

Unit-3: Memory Management • Contains 64 to 1024 entries

Lecture 5 – Structure of the Page Table • Implemented using associative memory

1. Hardware Support for Page Tables • Significantly speeds up address translation

The page table is a key data structure used in paging systems to map logical pages to physical Address-Space Identifiers (ASIDs)
frames. Since address translation occurs for every memory reference, hardware support is Some TLBs store Address-Space Identifiers (ASIDs) with each entry.
required to make the translation process efficient.
ASIDs help distinguish page-table entries belonging to different processes. Without ASIDs, the
One possible implementation is to store the page table directly in CPU registers. In this TLB would have to be flushed during every context switch to prevent incorrect mappings.
approach, each page-table entry is stored in a dedicated hardware register. This method allows
extremely fast address translation because the CPU can access registers quickly. With ASIDs, entries for multiple processes can remain in the TLB simultaneously.

However, this approach is practical only when the page table is very small. Modern systems TLB Miss
may have thousands or millions of pages, making it impractical to store the entire page table in If the page number is not found in the TLB (called a TLB miss), the system:
registers.
1. Accesses the page table in memory.
To overcome this limitation, systems use a special hardware cache called the Translation
Lookaside Buffer (TLB). The TLB is a small, fast associative memory used to store recently 2. Retrieves the frame number.
used page-table entries. 3. Inserts this mapping into the TLB for faster future access.
2. Page Table Stored in Main Memory Replacement policies such as LRU or FIFO may be used when the TLB becomes full.
In most systems, the page table is stored in main memory rather than in CPU registers. Some critical entries can be wired down, meaning they remain permanently in the TLB for
Two important registers help manage the page table: fast access.

Page Table Base Register (PTBR) - The PTBR contains the starting address of the 4. Paging Hardware with TLB
page table in memory. The address translation process using a TLB works as follows:
Page Table Length Register (PTLR) - The PTLR specifies the size of the page 1. CPU generates a logical address (page number + offset).
table, indicating how many page entries exist.
2. Page number is searched in the TLB.
Two-Memory-Access Problem
3. If found, the frame number is obtained immediately.
When the page table is stored in memory, every memory reference requires two memory
accesses: 4. Physical address is formed by combining the frame number with the offset.

1. Access the page table to obtain the frame number. If the TLB does not contain the page entry:

2. Access the actual data or instruction in memory. 1. The page table is accessed in main memory.

Thus, one logical memory reference becomes two physical memory accesses, which slows 2. The mapping is inserted into the TLB.
down the system.
3. Physical address is calculated.
3. Translation Lookaside Buffer (TLB)
To improve performance, systems use the Translation Lookaside Buffer (TLB).
The TLB is a small, fast hardware cache that stores recently used page-table entries. When
the CPU generates a logical address, the system first checks whether the page number exists in
the TLB.
If the page number is found in the TLB, the frame number can be obtained quickly without
accessing the page table in memory.

Pavan A C (pavanac@[Link]) 1 Pavan A C (pavanac@[Link]) 2

 This produces only about 1% slowdown, showing the effectiveness of TLB.
6. TLB vs CPU Cache
Although TLB and CPU cache both improve performance, they serve different purposes.
TLB
• Speeds up address translation
• Reduces page-table lookups
• Works with virtual memory system
CPU Cache
• Speeds up data access
5. Effective Access Time (EAT) • Reduces main memory latency
Because TLB improves address translation, we calculate system performance using Effective • Stores frequently used instructions or data
Access Time (EAT).
TLB operates during address translation, while CPU cache operates during memory access.
Hit Ratio
7. Memory Protection in Paging
Hit ratio refers to the percentage of memory references found in the TLB.
Memory protection can be implemented by associating protection bits with each page-table
Example: entry.
Hit ratio = 80% Examples of protection bits include:
Memory access time = 10 ns • Read-only
If the page is found in the TLB: • Read-write
Access time = 10 ns • Execute-only
If the page is not found in the TLB: If a process attempts an illegal operation (such as writing to a read-only page), the hardware
generates a trap to the operating system.
Page table access = 10 ns
Memory access = 10 ns Valid-Invalid Bit
Total = 20 ns
Each page-table entry contains a valid-invalid bit.
Effective Access Time Formula
• Valid bit → Page belongs to the process’s logical address space.
EAT = (Hit Ratio × Memory Access Time) + (Miss Ratio × Two Memory Access Time)
• Invalid bit → Page is not part of the process’s address space.
Example:
If a process accesses an invalid page, a trap occurs, often called a page fault.
EAT = 0.80 × 10 + 0.20 × 20
EAT = 8 + 4
EAT = 12 ns
This represents a 20% slowdown compared to direct memory access.
Realistic Example
If hit ratio = 99%:
EAT = 0.99 × 10 + 0.01 × 20
EAT = 9.9 + 0.2
EAT = 10.1 ns

Pavan A C (pavanac@[Link]) 3 Pavan A C (pavanac@[Link]) 4

8. Demand Paging
Demand paging uses the valid-invalid bit intentionally.
Initially, many pages are marked invalid. When the program tries to access such a page:
1. A page fault occurs.
2. The operating system loads the required page from disk into memory.
3. The page table is updated.
4. Execution resumes.
This allows memory to be allocated only when actually needed, improving memory
utilization.
9. Shared Pages
Paging makes it easy to share memory between processes.
For example, suppose 40 users run the same text editor.
Program size:
• Code = 150 KB
• Data = 50 KB
Without sharing:
Total memory = (150 + 50) × 40
= 8000 KB
With shared code:
Code = 150 KB (shared once)
Data = 50 × 40 = 2000 KB
Total = 2150 KB 10. Large Page Tables Problem

Thus, memory usage is greatly reduced. Page tables can become extremely large in modern systems.

Reentrant Code Example:

Shared code must be reentrant. 32-bit address space

Page size = 4 KB
Reentrant code:
Number of pages = 2³² / 2¹²
• Can be executed by multiple processes simultaneously = 2²⁰
• Does not modify itself during execution = about 1 million pages

• Is read-only If each entry is 4 bytes:

Examples include: Page table size = 4 MB

• Shared libraries This is a large amount of memory for a single process.

• System utilities 11. Hierarchical Page Tables

• Standard library functions To reduce memory usage, page tables can be organized hierarchically.
Instead of one large page table, the table is divided into multiple levels.

Pavan A C (pavanac@[Link]) 5 Pavan A C (pavanac@[Link]) 6

Example: The page number is hashed to find a corresponding entry in a hash table that stores:
Two-level paging. • Virtual page number
The page number is divided into: • Frame number
• Outer page table index This reduces the search space and speeds up lookup.
• Inner page table index
Logical Address Format

• p1 → index into outer page table

• p2 → index into inner page table
• offset → location inside the page
14. Inverted Page Tables
This approach allows page tables to be allocated only when required, saving memory.
Inverted page tables reduce memory usage by storing one entry for each physical frame
instead of one entry per virtual page.
Each entry contains:
• Virtual address
• Process identifier
• Frame number
Advantages:
• Page table size depends on physical memory, not virtual memory.
Disadvantages:
• Searching the table may take longer.
• Hashing is often used to improve lookup speed.
12. Multi-Level Paging in Modern Systems
Modern systems use three-level, four-level, or five-level paging.
Example:
x86-64 Linux uses:
• 4-level paging
• Optionally 5-level paging for very large address spaces.
However, multi-level paging increases the number of memory accesses required for address
translation.
13. Hashed Page Tables
Hashed page tables are used for very large address spaces, such as 64-bit systems.

Pavan A C (pavanac@[Link]) 7 Pavan A C (pavanac@[Link]) 8

15. Shared Memory Issues in Inverted Tables OPERATING SYSTEMS (UE24CS242B)
In inverted page tables, each physical page has only one entry. This creates difficulty when Unit-3: Memory Management
multiple virtual addresses must map to the same physical page.
Lecture 6 – Virtual Memory and Copy-on-Write
To solve this, systems allow multiple virtual addresses to map to one physical address,
while maintaining appropriate reference structures. 1. Introduction to Virtual Memory

16. Linux Optimization: Huge Pages Virtual memory is a memory-management technique that allows a process to execute even
when the entire program is not loaded into physical memory. Instead of loading the complete
Modern Linux systems address TLB limitations using Huge Pages. program into RAM, only the required portions are loaded while the rest remain on secondary
Standard page size = 4 KB storage (disk).

Huge pages may be: The main advantage of virtual memory is that program size is no longer limited by the size of
physical memory. Programs can be larger than the available RAM because only a portion of
• 2 MB the program needs to be in memory at any given time.
• 1 GB Virtual memory also improves system efficiency by allowing more processes to run
Using huge pages allows a single TLB entry to cover much larger memory regions, reducing simultaneously. Since each process occupies only part of the memory, the operating system can
TLB misses. increase CPU utilization and throughput without increasing response time.
Another benefit is easy sharing of files and memory between processes, which is useful for
shared libraries and interprocess communication.
2. Motivation for Virtual Memory
In real applications, most programs do not use all their code simultaneously. Some parts of
the program are rarely executed.
Examples include:
• Error-handling routines
• Debugging functions
• Rarely used modules
• Large data structures
Loading the entire program into memory wastes space because these sections may never be
used.
Virtual memory solves this problem by allowing partial program loading. Only the portions
that are actually required during execution are loaded into memory.
This approach provides several advantages:
• Programs are not constrained by RAM size.
• Memory usage per program is reduced.
• More programs can run simultaneously.
• CPU utilization improves.
3. Separation of Logical and Physical Memory
Virtual memory separates logical memory from physical memory.

Pavan A C (pavanac@[Link]) 9 Pavan A C (pavanac@[Link]) 1

Logical Memory - Logical memory (also called virtual address space) is the memory view • Stack growth
seen by the process. It usually starts from address 0 and extends continuously up to the
• Heap growth
maximum address.
6. Shared Libraries Using Virtual Memory
Physical Memory - Physical memory refers to the actual RAM installed in the computer,
which is divided into page frames. Virtual memory allows multiple processes to share the same physical memory pages.
The Memory Management Unit (MMU) is responsible for translating logical addresses into
physical addresses.
Virtual memory is commonly implemented using:
• Demand Paging
• Demand Segmentation
Most modern operating systems use demand paging.
4. Virtual Address Space
A process’s virtual address space represents how the program logically appears in memory.
Typically, the memory layout is organized so that: For example, if multiple programs use the same library:

• Heap grows upward • Only one copy of the library code is loaded into memory.

• Stack grows downward • All processes reference that same code.

This layout maximizes memory usage and leaves unused space between them. This reduces memory consumption and improves efficiency.
Shared memory can also be implemented by mapping the same physical pages into multiple
virtual address spaces.
7. Demand Paging
Demand paging is a technique where pages are loaded into memory only when they are
needed.

The unused space between heap and stack allows them to grow dynamically.
5. Sparse Address Space
Virtual memory allows sparse address spaces, where large sections of the logical address
space remain unused.
These unused regions are called holes. They allow memory to grow dynamically when
required.
Sparse address spaces are useful for: Instead of loading an entire process during program startup, the operating system loads pages
only when they are referenced.
• Dynamic memory allocation
Advantages of demand paging:
• Dynamically linked libraries

Pavan A C (pavanac@[Link]) 2 Pavan A C (pavanac@[Link]) 3

 • Reduced memory usage
• Reduced disk I/O
• Faster program startup
• Ability to support more users simultaneously
In demand paging:
• The component responsible for managing pages is called the pager.
• A lazy swapper loads pages only when required.
8. Demand Paging Concept
Two situations can occur when a page is referenced:
Case 1: Page is already in memory 10. Page Fault
Execution continues normally. A page fault occurs when the CPU tries to access a page that is not currently in main
memory.
Case 2: Page is not in memory
When this happens, the operating system must load the required page from secondary storage
A page fault occurs and the operating system must load the page from disk.
into RAM.
The operating system detects this situation automatically without requiring changes to the
11. Steps in Handling a Page Fault
program.
When a page fault occurs, the operating system performs the following steps:
9. Valid–Invalid Bit
1. CPU detects page fault and traps to the OS.
Each entry in the page table contains a valid-invalid bit.
2. The operating system checks if the reference is valid.
• Valid (v) → Page is present in memory.
3. If the reference is illegal → terminate the process.
• Invalid (i) → Page is not currently in memory.
4. If the page is valid but not in memory:
Initially, all page table entries may be marked invalid.
o Find a free frame in memory.
o Read the required page from disk.

When the CPU references a page marked invalid, the system generates a page fault
interrupt.

Pavan A C (pavanac@[Link]) 4 Pavan A C (pavanac@[Link]) 5

 5. Update the page table entry. • 𝑝 = 1→ every memory access causes a page fault
6. Set the valid bit to v. 16. Effective Access Time (EAT)
7. Restart the instruction that caused the fault. Effective access time measures the average time required to access memory considering page
faults.
12. Pure Demand Paging
Formula:
In the extreme case of pure demand paging, the process starts with no pages in memory.
EAT = (1 − p) × memory access time
When the first instruction is executed, it causes a page fault, and the required page is loaded.
+ p × page fault service time
Subsequent page faults occur as the program accesses new pages.
17. Example Calculation
Although many faults occur initially, performance improves later due to locality of
Given:
reference.
Memory access time = 200 ns
13. Locality of Reference
Page fault service time = 8 ms
Programs tend to access the same set of memory locations repeatedly during execution.
Convert:
This behavior is called locality of reference.
8 ms = 8,000,000 ns
Two types exist:
Thus:
Temporal Locality
EAT = 200 + p × 7,999,800
Recently used data is likely to be accessed again soon.
If:
Spatial Locality
p = 0.001
Memory locations near recently accessed locations are likely to be accessed soon.
Then:
Locality reduces the frequency of page faults once the necessary pages are loaded.
EAT = 8200 ns
14. Instruction Restart
This means memory access becomes 40 times slower.
After a page fault occurs, the operating system must restart the instruction that caused the
To maintain good performance, page fault rate must be extremely small.
fault.
18. Demand Paging Optimizations
To achieve this:
To improve demand paging performance, operating systems use swap space.
• CPU registers are saved.
Swap space is a reserved disk area used for temporarily storing memory pages when RAM is
• Process state is preserved.
insufficient.
• Program counter is restored.
Characteristics of swap space:
After the required page is loaded, the instruction is executed again.
• Usually equal to or double the size of RAM.
This ensures that program execution continues correctly.
• Faster than file system storage.
15. Performance of Demand Paging
• Used to store pages not currently needed in memory.
Demand paging performance depends heavily on the page fault rate.
19. Modern Demand Paging Systems
Let:
Modern systems optimize demand paging further.
p = probability of a page fault
Examples include:
Where:
• Demand paging from executable files
• 𝑝 = 0→ no page faults
• Anonymous memory pages (stack and heap)

Pavan A C (pavanac@[Link]) 6 Pavan A C (pavanac@[Link]) 7

 • Reclaiming read-only pages when memory is low • Prevent memory over-allocation
Mobile systems often avoid swapping completely and instead reload code pages from storage • Maintain system performance
when necessary.
• Enable large virtual memory
19. Copy-on-Write (COW)
Dirty Bit (Modify Bit)
Copy-on-Write is an optimization used during process creation (fork()).
Each page has a dirty bit:
Instead of copying all pages:
• If set → page modified → must be written to disk
• Parent and child share pages initially
• If not set → page can be replaced directly
• Pages are marked read-only
This reduces disk I/O.
If a process modifies a page:
21. Basic Page Replacement Algorithm
• A copy is created
Steps:
• Only that page is duplicated
1. Locate required page on disk
Advantages of COW
2. Check for free frame
• Faster process creation
If free frame exists:
• Reduced memory usage
• Load page directly
• Efficient use of resources
If no free frame:
• Select victim page
• Write to disk if dirty
• Load new page
3. Update page table
4. Restart instruction

20. Page Replacement

When memory is full:
• No free frames are available
• OS must replace an existing page
This is called page replacement.
Purpose

Pavan A C (pavanac@[Link]) 8 Pavan A C (pavanac@[Link]) 9

 OPERATING SYSTEMS (UE24CS242B) 4. First-In-First-Out (FIFO) Algorithm

Unit-3: Memory Management FIFO is the simplest page replacement algorithm.

Lecture 7 – Page Replacement Algorithms Working Principle

1. Introduction to Page Replacement • Pages are replaced in the order they were loaded into memory

Page replacement algorithms are used when main memory is full and a new page needs to • The oldest page is removed first
be loaded. Since no free frames are available, the operating system must decide which This is implemented using a queue:
existing page should be removed from memory.
• New pages are added at the rear
Two important decisions are involved:
• Old pages are removed from the front
1. Frame Allocation Algorithm
Determines how many frames each process should receive. Example

2. Page Replacement Algorithm Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

Determines which page should be replaced. Frames = 3
The primary goal of any page replacement algorithm is to: FIFO replaces the oldest page whenever a new page must be loaded.
Minimize the number of page faults
A good algorithm reduces disk I/O operations and improves overall system performance.
2. Evaluation of Page Replacement Algorithms
Page replacement algorithms are evaluated using a reference string, which is a sequence of
page numbers accessed by a process.
Example reference string:
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1 Disadvantage

Important points: FIFO may replace frequently used pages simply because they are old.

• Only page numbers are considered (not full addresses) 5. Belady’s Anomaly

• Repeated access to the same page does not cause a page fault FIFO suffers from a surprising problem called Belady’s Anomaly.

• The number of page faults depends on: Definition

o The algorithm used Increasing the number of frames can sometimes increase the number of page faults

o The number of frames available Example reference string:

3. Basic Page Replacement Concept 1,2,3,4,1,2,5,1,2,3,4,5

When a page fault occurs: With more frames, FIFO may produce more page faults.

1. Check if a free frame exists This behavior is undesirable and shows that FIFO is not always optimal.

2. If yes → load the page 6. Optimal Page Replacement Algorithm

3. If no → select a victim page using an algorithm The Optimal (OPT) algorithm replaces the page that will not be used for the longest time
in the future.
4. Replace victim page with new page
Working Principle
5. Update page table
• Look ahead in the reference string

Pavan A C (pavanac@[Link]) 1 Pavan A C (pavanac@[Link]) 2

 • Replace the page whose next use is farthest away Disadvantages
Advantages • Requires searching entire page table
• Produces the minimum possible number of page faults • High overhead
• Serves as a benchmark to evaluate other algorithms 2. Stack Implementation
Disadvantage • Maintain a stack (or list) of pages
• Cannot be implemented in real systems because it requires future knowledge • Most recently used page is moved to the top
Example Operation
For the given reference string and 3 frames: • On page reference → move page to top
Minimum page faults = 9 • Page at bottom → least recently used
Advantages
• No need to search for replacement
Disadvantages
• Requires multiple pointer updates
9. Stack Algorithms
Both Optimal and LRU belong to a class of algorithms called stack algorithms.
7. Least Recently Used (LRU) Algorithm
Property
LRU is one of the most important and widely used algorithms.
• The set of pages in memory with n frames is always a subset of pages with n+1
Working Principle frames

• Replace the page that has not been used for the longest time in the past Important Result

LRU uses past behavior to predict future usage. Stack algorithms do not suffer from Belady’s Anomaly
Thus, increasing frames will always reduce or maintain page faults.
10. Comparison of Algorithms

Algorithm Basis Advantage Disadvantage

FIFO Arrival order Simple Belady’s anomaly

Optimal Future use Minimum faults Not implementable

Key Idea
LRU Past use Good performance Overhead
Pages used recently are likely to be used again soon.
8. LRU Implementation Techniques
1. Counter Implementation
• Each page table entry has a counter
• Every time a page is accessed, the current time is stored
• The page with the smallest timestamp is replaced

Pavan A C (pavanac@[Link]) 3 Pavan A C (pavanac@[Link]) 4

 OPERATING SYSTEMS (UE24CS242B) Frames per process = m / n

Unit-3: Memory Management Example

Lecture 8 – Allocation of Frames & Thrashing • Frames = 93

1. Allocation of Frames • Processes = 5

In paging systems, memory is divided into fixed-size frames, and the OS must decide how to Each gets = 18 frames
distribute these frames among processes. Remaining = 3 frames (buffer pool)

The key challenge is: Drawback

How to allocate limited frames efficiently among multiple processes? • Ignores process size

Example • Large processes suffer → more page faults

• Total memory = 128 KB • Small processes waste memory

• Page size = 1 KB → 128 frames 3.2 Proportional Allocation

• OS uses = 35 frames Frames are allocated based on process size.

• Remaining = 93 frames ai = (si / S) × m

Under pure demand paging: Example

• First 93 page faults → use free frames • Total frames = 62

• After that → page replacement starts • Processes: 10 pages & 127 pages

When process terminates: 10/137 × 62 ≈ 4 frames

127/137 × 62 ≈ 57 frames
• Frames return to free-frame list
Advantage
2. Minimum Number of Frames
• Fair allocation
Each process must be allocated a minimum number of frames.
• Better performance
Why?
4. Global vs Local Replacement
• Some instructions need multiple pages simultaneously
4.1 Global Replacement
• If frames are insufficient:
• Process can replace any frame in system
o Instruction cannot complete
• Can take frames from other processes
o Page fault occurs → restart needed
Example
Key Points
• High-priority process steals frames from low-priority process
• Minimum frames → defined by hardware architecture
Pros
• Maximum frames → defined by available memory
• Higher throughput
• Between them → OS decides allocation
Cons
3. Frame Allocation Algorithms
• Unpredictable execution time
3.1 Equal Allocation
• Depends on other processes
Frames are divided equally among processes.
4.2 Local Replacement

Pavan A C (pavanac@[Link]) 1 Pavan A C (pavanac@[Link]) 2

 • Process replaces only its own frames Effects
Pros • Low CPU utilization
• Stable performance • High disk activity
• No interference • System slowdown
Cons 8. Thrashing Behavior
• Lower system utilization What happens?
Important Conclusion 1. Page fault occurs
Modern OS (like Linux) → Global Replacement (default) 2. Replace page
5. Linux Context 3. Needed page again → another fault
• Linux uses global replacement 4. Continuous swapping
• Can enforce limits using cgroups Result
This is important in: Process keeps swapping pages instead of executing
• Containers
• Cloud systems
6. Non-Uniform Memory Access (NUMA)
In multiprocessor systems:
• Some memory is closer to CPU
• Some memory is far away
Effect
• Local memory → fast
• Remote memory → slow
Problem
If OS ignores this:
• CPU waits longer
• Performance degrades
7. Thrashing
Definition
Thrashing is a condition where the system spends more time swapping pages than executing
processes.
Why it happens?
• Process does not have enough frames
• Very high page fault rate

Pavan A C (pavanac@[Link]) 3 Pavan A C (pavanac@[Link]) 4