1. Introduction
Contiguous memory allocation suffers from external fragmentation, where free memory exists but cannot be used efficiently because it is scattered into non-contiguous blocks.
To overcome this limitation, operating systems use Paging.
Paging is a memory management technique that divides both logical memory and physical memory into fixed-size blocks and maps them efficiently.
It is one of the most important concepts in modern operating systems because it forms the foundation of virtual memory.
2. What is Paging?
Paging is a memory management scheme in which:
Logical memory is divided into pages
Physical memory is divided into frames
Pages are mapped to frames
Key Idea
Logical Memory → Pages
Physical Memory → Frames
Pages mapped to Frames
A process no longer needs a single contiguous block of memory.
Its pages can be stored anywhere in RAM.
3. Basic Concept of Paging
Suppose a process occupies:
16 KB
and page size is:
4 KB
Then the process is divided into:
Page 0
Page 1
Page 2
Page 3
Similarly, physical memory is divided into fixed-size frames:
Frame 0
Frame 1
Frame 2
Frame 3
...
The operating system places pages into any available frames.
4. Basic Terminology
4.1 Page
A Page is a fixed-size block of logical memory.
Example
Page Size = 4 KB
Pages belong to a process.
4.2 Frame
A Frame is a fixed-size block of physical memory.
Example
Frame Size = 4 KB
Frames belong to RAM.
4.3 Page Size
The size of each page and frame.
Usually chosen as a power of 2.
Common values:
4 KB
8 KB
16 KB
64 KB
Key Insight
Page Size = Frame Size
This equality makes mapping simple.
5. Paging Memory Layout
Logical Memory
+---------+
| Page 0 |
+---------+
| Page 1 |
+---------+
| Page 2 |
+---------+
| Page 3 |
+---------+
Physical Memory
+----------+
| Frame 0 |
+----------+
| Frame 1 |
+----------+
| Frame 2 |
+----------+
| Frame 3 |
+----------+
| Frame 4 |
+----------+
| Frame 5 |
+----------+
Pages can be loaded into any free frame.
6. How Paging Works
Step 1
Process is divided into pages.
Example
Process Size = 12 KB
Page Size = 4 KB
Number of pages:
12 / 4 = 3 Pages
Step 2
Operating system searches for free frames.
Suppose:
Frame 2
Frame 5
Frame 8
are available.
Step 3
Pages are loaded.
Page 0 → Frame 5
Page 1 → Frame 2
Page 2 → Frame 8
Step 4
This mapping is stored in the Page Table.
7. Page Table
A Page Table is a data structure used to store the mapping between page numbers and frame numbers.
Example
| Page Number | Frame Number |
|---|---|
| 0 | 5 |
| 1 | 2 |
| 2 | 8 |
This table is maintained by the operating system.
Key Purpose
Convert logical addresses into physical addresses.
8. Logical Address Structure
In paging, every logical address is divided into two parts:
Logical Address
=
Page Number + Offset
Components
Page Number (p)
Identifies which page contains the required data.
Offset (d)
Identifies the exact location within that page.
9. Example of Logical Address
Suppose:
Logical Address = (2, 100)
Where:
Page Number = 2
Offset = 100
Meaning:
Byte 100 inside Page 2
10. Address Translation in Paging
Address translation occurs in two steps.
Step 1
Use page number to access page table.
Page 2 → Frame 8
Step 2
Combine frame number and offset.
Frame Number = 8
Offset = 100
Physical Address becomes:
(Frame 8, Offset 100)
Translation Flow
Logical Address
↓
Page Number
↓
Page Table
↓
Frame Number
↓
Physical Address
11. Numerical Example
Suppose:
Page Size = 1024 Bytes
Logical Address:
2500
Find Page Number
2500 / 1024 = 2
Page Number:
2
Find Offset
2500 mod 1024 = 452
Offset:
452
Logical Address:
(Page 2, Offset 452)
If:
Page 2 → Frame 8
Then:
Physical Address
=
8 × 1024 + 452
=
8644
12. Why Paging is Important
12.1 Eliminates External Fragmentation
Pages can be placed in any available frame.
No contiguous memory block is required.
12.2 Efficient Memory Utilization
Small free frames can still be used.
Memory wastage is reduced.
12.3 Supports Multiprogramming
Many processes can coexist efficiently.
12.4 Enables Virtual Memory
Programs larger than RAM can execute.
This is the foundation of modern operating systems.
12.5 Simplifies Allocation
Operating system only needs free frames.
No complex contiguous allocation is required.
13. Does Paging Have Fragmentation?
Yes.
Paging eliminates external fragmentation but may still suffer from internal fragmentation.
14. Internal Fragmentation in Paging
The last page of a process may not be completely filled.
Example
Page Size = 4 KB
Process Size = 18 KB
Pages Required:
18/4 = 4.5
Therefore:
5 Pages
Allocated Memory:
5 × 4 KB = 20 KB
Unused Memory:
20 KB - 18 KB = 2 KB
Internal Fragmentation:
2 KB
Key Insight
Paging removes External Fragmentation
but may cause Internal Fragmentation
15. Advantages of Paging
No External Fragmentation
Processes do not require contiguous memory.
Better Memory Utilization
Small free frames remain useful.
Easy Memory Allocation
OS allocates frames independently.
Supports Virtual Memory
Allows large programs to execute.
Improved Multiprogramming
More processes can reside in memory.
Process Isolation
Each process has its own page table.
16. Disadvantages of Paging
Page Table Overhead
Additional memory is needed to store page tables.
Address Translation Overhead
Every memory access requires translation.
Internal Fragmentation
Unused space may exist in the final page.
Increased Complexity
Requires hardware support such as MMU.
17. Paging vs Contiguous Allocation
| Feature | Contiguous Allocation | Paging |
|---|---|---|
| Memory Requirement | Contiguous | Non-Contiguous |
| External Fragmentation | Yes | No |
| Internal Fragmentation | Possible | Possible |
| Allocation Complexity | High | Low |
| Flexibility | Low | High |
| Virtual Memory Support | No | Yes |
18. Real-World Analogy
Imagine a book.
Without Paging
The entire book must be stored on one shelf.
If one large shelf is unavailable:
Cannot Store Book
With Paging
The book is divided into pages.
Pages can be placed on different shelves.
Page 1 → Shelf A
Page 2 → Shelf D
Page 3 → Shelf F
An index tells you where each page is stored.
This index is exactly like a Page Table.
Most Important Point
Paging is a memory management technique that divides logical memory into pages and physical memory into frames, allowing non-contiguous allocation while completely eliminating external fragmentation.