Paging
Paging is a memory-management technique that allows a process to be stored in non-contiguous locations in physical memory.
Paging divides logical memory into fixed-size blocks called pages and physical memory into fixed-size blocks called frames.
The important idea is:
Process → Pages RAM → Frames
Pages can be placed into any available frames.
1. Why Do We Need Paging?
With contiguous memory allocation, a process needs one large continuous block.
Suppose a process needs 100 MB, but RAM has:
+----------------+ | P1 | +----------------+ | Free 40 MB | +----------------+ | P2 | +----------------+ | Free 30 MB | +----------------+ | P3 | +----------------+ | Free 50 MB | +----------------+
Total free memory:
40 + 30 + 50 = 120 MB
But there is no single 100 MB block.
So the process cannot be allocated contiguously.
Paging solves this problem by dividing the process into smaller pieces.
2. Basic Idea of Paging
Suppose:
Process size = 16 KB Page size = 4 KB
Then:
16 KB / 4 KB = 4 pages
The process becomes:
+--------+ | Page 0 | +--------+ | Page 1 | +--------+ | Page 2 | +--------+ | Page 3 | +--------+
Physical memory is divided into frames:
+---------+ | Frame 0 | +---------+ | Frame 1 | +---------+ | Frame 2 | +---------+ | Frame 3 | +---------+ | Frame 4 | +---------+ | Frame 5 | +---------+ ...
The pages don't have to be placed next to each other.
For example:
Page 0 → Frame 5 Page 1 → Frame 1 Page 2 → Frame 7 Page 3 → Frame 3
3. Page vs Frame
This is one of the most important concepts.
Page
A page is a fixed-size block of logical/virtual memory.
Frame
A frame is a fixed-size block of physical memory (RAM).
Virtual Memory Physical Memory +---------+ +---------+ | Page 0 | ──────────────→ | Frame 5 | +---------+ +---------+ | Page 1 | ──────────────→ | Frame 1 | +---------+ +---------+ | Page 2 | ──────────────→ | Frame 7 | +---------+ +---------+ | Page 3 | ──────────────→ | Frame 3 | +---------+ +---------+
Easy memory trick:
Page = Program's virtual memory
Frame = Physical RAM
4. Page Size and Frame Size
The size of a page is always equal to the size of a frame.
For example:
Page size = 4 KB Frame size = 4 KB
or:
Page size = 8 KB Frame size = 8 KB
Why?
Because one page must fit exactly into one frame.
5. Page Table
How does the OS know where each page is stored?
It uses a page table.
Example:
| Page Number | Frame Number |
|---|---|
| 0 | 5 |
| 1 | 1 |
| 2 | 7 |
| 3 | 3 |
The page table maps:
Page → Frame
For example:
Page 0 → Frame 5 Page 1 → Frame 1 Page 2 → Frame 7 Page 3 → Frame 3
6. Complete Paging Structure
CPU | ↓ Logical Address | +------+------+ | | ↓ ↓ Page Number Offset | ↓ Page Table | ↓ Frame Number | +------ Offset | ↓ Physical Address | ↓ RAM
This is the heart of paging.
7. Logical Address
A logical address in paging is divided into two parts:
Logical Address | +----------------+ | | ↓ ↓ Page Number Offset
For example:
Logical address = 13 bits +-----------+--------+ | Page No. | Offset | +-----------+--------+
The page number identifies the page.
The offset identifies the exact location inside that page.
8. What Is an Offset?
Suppose page size is:
4 KB
A page contains:
4096 bytes
Therefore, the offset needs to identify one of:
0 → 4095
Number of bits required:
log₂(4096) = 12 bits
Therefore:
Offset = 12 bits
9. Address Format
Suppose:
Logical address = 16 bits Page size = 4 KB
Since:
4 KB = 4096 bytes = 2¹²
Offset:
12 bits
Therefore page number:
16 - 12 = 4 bits
Address format:
16-bit Logical Address +----------+--------------+ | Page No. | Offset | | 4 bits | 12 bits | +----------+--------------+
Number of pages:
2⁴ = 16 pages
10. Physical Address
The physical address is also divided conceptually into:
Frame Number + Offset
The important point is:
Page Number → Frame Number
The offset remains unchanged.
Example:
Logical address: Page 2 + Offset 100 Page table: Page 2 → Frame 7 Physical address: Frame 7 + Offset 100
11. Address Translation Example
Suppose:
Page size = 100 bytes Logical address = 250
Find:
Page number Offset
Formula:
Page Number = Logical Address / Page Size
Integer division:
250 / 100 = 2
So:
Page Number = 2
Offset:
250 % 100 = 50
Therefore:
Page = 2 Offset = 50
Suppose page table says:
Page 2 → Frame 7
Then physical address:
Frame × Page Size + Offset = 7 × 100 + 50 = 750
Therefore:
Physical address = 750
12. Another Numerical Example
Suppose:
Page size = 1 KB Logical address = 2500
Since:
1 KB = 1024 bytes
Page number:
2500 / 1024 = 2
Offset:
2500 % 1024 = 452
Therefore:
Page number = 2 Offset = 452
Suppose:
Page 2 → Frame 5
Physical address:
5 × 1024 + 452 = 5120 + 452 = 5572
Therefore:
Physical Address = 5572
13. Important Paging Formulas
Page number
Page Number = Logical Address ÷ Page Size
Take the integer part.
Offset
Offset = Logical Address % Page Size
Physical address
Physical Address = Frame Number × Page Size + Offset
These formulas are very important for numerical questions.
14. Number of Pages
Suppose:
Process size = 20 KB Page size = 4 KB
Number of pages:
20 / 4 = 5 pages
Therefore:
P0 P1 P2 P3 P4
15. When Process Size Is Not a Multiple of Page Size
Suppose:
Process size = 18 KB Page size = 4 KB
Then:
18 / 4 = 4.5
So we need:
5 pages
Memory allocated:
5 × 4 = 20 KB
Unused:
20 - 18 = 2 KB
That unused space is internal fragmentation.
Therefore paging can cause some internal fragmentation, especially in the final page.
16. Paging and Fragmentation
Paging eliminates the major problem of external fragmentation associated with contiguous allocation.
Why?
Because pages can be placed in any available frame.
Example:
Free Frames: F1 F4 F8 F10
Pages can use them:
P0 → F8 P1 → F1 P2 → F10 P3 → F4
They don't need to be adjacent.
However:
Paging can still produce internal fragmentation.
Usually the last page of a process may not be completely full.
17. Advantages of Paging
1. Eliminates external fragmentation
A process does not need one continuous memory block.
2. Supports non-contiguous allocation
Pages can be placed anywhere.
3. Supports virtual memory
Paging is fundamental to many virtual-memory systems.
4. Better memory utilization
Free frames can be used independently.
5. Supports process isolation
Different processes can have separate page tables and permissions.
6. Easy allocation
Physical frames can be allocated independently.
18. Disadvantages of Paging
1. Page table overhead
Every process may require a page table.
Large address spaces can require substantial page-table memory.
2. Address translation overhead
The system needs to translate:
Page → Frame
3. Internal fragmentation
The final page may not be completely used.
4. Memory access can become more expensive
Without caching mechanisms, translation may add overhead.
5. Page-table management complexity
Large systems require more sophisticated structures.
19. TLB
To speed up address translation, processors commonly use a:
TLB = Translation Lookaside Buffer
The TLB is a fast cache that stores recent page-to-frame mappings.
Without TLB:
CPU ↓ Page Table ↓ Frame ↓ RAM
With TLB:
CPU ↓ TLB ↓ Found? ├── Yes → Frame └── No → Page Table ↓ Frame
20. TLB Hit
Suppose CPU needs:
Page 5
And TLB already contains:
Page 5 → Frame 10
Then:
TLB → Frame 10
This is a:
TLB hit
It avoids having to look up the page table for that translation.
21. TLB Miss
Suppose CPU needs:
Page 8
But TLB doesn't contain it.
Then:
CPU ↓ TLB ↓ Miss ↓ Page Table ↓ Frame Number
This is a:
TLB miss
The translation can then be placed into the TLB for future use, depending on the hardware/OS design.
22. Page Table Entry
A page table doesn't necessarily contain only a frame number.
A page table entry (PTE) may contain information such as:
+-------------------+ | Frame Number | | Present/Valid | | Read/Write | | User/Supervisor | | Accessed | | Dirty | | Other flags | +-------------------+
Important bits include:
Present/Valid bit
Indicates whether the page is currently mapped/present as required.
Protection bits
Determine whether the page can be:
Read Write Execute
Dirty bit
Indicates whether a page has been modified.
Accessed/Reference bit
Indicates that the page has been accessed.
23. Multi-Level Page Tables
A huge page table can consume a lot of memory.
Instead of having one enormous page table, modern systems can use multi-level page tables.
Conceptually:
Virtual Address | ↓ +-------------+ | Level 1 | +-------------+ | ↓ +-------------+ | Level 2 | +-------------+ | ↓ +-------------+ | Level 3 | +-------------+ | ↓ Frame
Only the portions needed for the address space have to be allocated.
24. Page Table and Process
Each process can have its own virtual address space and page-table mappings.
Example:
Process A Virtual Page 0 → Frame 5 Virtual Page 1 → Frame 8 Process B Virtual Page 0 → Frame 2 Virtual Page 1 → Frame 9
Both processes can have a virtual address such as:
Page 0
but it can map to different physical frames.
This provides process isolation.
25. Shared Pages
Paging can also support shared memory.
For example:
Process A Page 5 ─────┐ ↓ Frame 20 ↑ Process B │ Page 8 ──────┘
Both processes can map a page to the same physical frame.
This can be useful for:
- Shared libraries
- Inter-process communication
- Shared memory
- Copy-on-write mechanisms
26. Copy-on-Write
Copy-on-write, commonly abbreviated COW, is an important optimization.
Suppose:
Process A | ↓ Shared physical page ↑ | Process B
Initially both can share the same physical page.
If one process tries to modify it:
Process A writes ↓ Page copied ↓ A gets its own copy ↓ B keeps original
This avoids unnecessary copying when the data is only being read.
27. Paging and Virtual Memory
Paging is strongly connected with virtual memory.
Suppose:
Virtual Memory = 16 GB Physical RAM = 4 GB
The entire virtual address space doesn't have to be physically present in RAM at once.
Only currently needed pages may be in RAM.
Virtual Memory +----+----+----+----+----+----+ | P0 | P1 | P2 | P3 | P4 | P5 | +----+----+----+----+----+----+ ↓ selected pages RAM +----+----+----+----+ | P0 | P3 | P5 | ...| +----+----+----+----+
When a required page isn't available, a page fault can occur.
28. Page Fault
A page fault happens when the CPU references a virtual page that is not currently available in the required physical-memory state.
Simplified flow:
CPU requests page ↓ Page table checked ↓ Page present? / \ Yes No | | ↓ ↓ Continue Page Fault ↓ OS handles fault ↓ Find/load required page ↓ Update page table ↓ Retry
Page faults are normal in virtual-memory systems.
However, excessive page faults can cause poor performance.
29. Paging vs Segmentation
| Paging | Segmentation |
|---|---|
| Fixed-size pages | Variable-size segments |
| Physical memory divided into frames | Memory divided into logical segments |
| Page size = frame size | Segment size can vary |
| Programmer usually doesn't see pages directly | Segments correspond more naturally to logical program units |
| No external fragmentation in basic paging | Can suffer external fragmentation |
| Can have internal fragmentation | Can have external fragmentation |
| Uses page table | Uses segment table |
30. Paging vs Contiguous Allocation
| Feature | Contiguous Allocation | Paging |
|---|---|---|
| Process location | Continuous | Non-continuous |
| External fragmentation | Possible | Eliminated in basic paging |
| Internal fragmentation | Possible | Possible |
| Allocation | More difficult with scattered holes | Frames can be independently allocated |
| Address translation | Simpler | Page-table based |
| Virtual memory | Limited/older approach | Fundamental technique |
31. Complete Paging Example
Suppose:
Logical memory = 16 KB Physical memory = 32 KB Page size = 4 KB
Number of pages
16 / 4 = 4 pages
P0 P1 P2 P3
Number of frames
32 / 4 = 8 frames
F0 F1 F2 F3 F4 F5 F6 F7
Suppose page table:
| Page | Frame |
|---|---|
| P0 | F5 |
| P1 | F2 |
| P2 | F7 |
| P3 | F1 |
Memory might look like:
Physical RAM F0 → Free F1 → P3 F2 → P1 F3 → Free F4 → Free F5 → P0 F6 → Free F7 → P2
Notice:
P0 → F5 P1 → F2 P2 → F7 P3 → F1
The process is completely non-contiguous.
32. Important Numerical Formula
If:
Logical address = LA Page size = S
Then:
Page number = floor(LA / S) Offset = LA mod S
If:
Page number → Frame number F
then:
Physical address = F × S + Offset
33. Bit Calculation
Suppose:
Logical address = 32 bits Page size = 4 KB
Since:
4 KB = 4096 bytes = 2¹² bytes
Therefore:
Offset = 12 bits
Remaining:
32 - 12 = 20 bits
So:
+--------------------+------------+ | Page Number | Offset | | 20 bits | 12 bits | +--------------------+------------+
Number of virtual pages:
2²⁰ pages
34. Another Bit Example
Suppose:
Logical address = 16 bits Page size = 1 KB
1 KB:
1024 = 2¹⁰
Therefore:
Offset = 10 bits
Page number:
16 - 10 = 6 bits
Number of pages:
2⁶ = 64 pages
So:
+----------+------------+ | Page No. | Offset | | 6 bits | 10 bits | +----------+------------+
35. Why Page Size Matters
Page size affects the system in several ways.
Small pages
Advantages:
- Less internal fragmentation
- Finer-grained memory management
Disadvantages:
- More pages
- Larger page tables
- Potentially more translation overhead
Large pages
Advantages:
- Smaller page tables
- Can improve translation efficiency in some situations
Disadvantages:
- More internal fragmentation
- Less fine-grained memory management
Modern systems can support multiple page sizes for different workloads.
36. Advantages and Disadvantages Summary
Advantages
✓ No external fragmentation ✓ Non-contiguous allocation ✓ Supports virtual memory ✓ Easy frame allocation ✓ Process isolation ✓ Memory sharing ✓ Efficient physical-memory utilization
Disadvantages
✗ Page-table overhead ✗ Internal fragmentation ✗ Address translation overhead ✗ Page faults can be expensive ✗ More complex memory management
🧠 Exam Revision
Definition
Paging is a non-contiguous memory-management technique in which logical memory is divided into fixed-size pages and physical memory is divided into equal-size frames. A page table maps pages to frames.
Remember:
Logical Memory → Pages Physical Memory → Frames Page → Page Table → Frame
Most important concepts:
Paging │ ├── Page ├── Frame ├── Page Table ├── Logical Address │ ├── Page Number │ └── Offset ├── Physical Address │ ├── Frame Number │ └── Offset ├── Address Translation ├── TLB ├── Page Table Entry ├── Multi-Level Page Table ├── Page Fault ├── Virtual Memory ├── Internal Fragmentation └── Copy-on-Write
One-line memory trick:
“Page tells WHERE in virtual memory; frame tells WHERE in RAM; offset tells EXACTLY WHERE inside it.”