Paging βββ
Paging βββ¶
Overview¶
Paging is a memory management technique that divides physical memory into fixed-size blocks (frames) and the logical address space of processes into blocks of the same size (pages), allowing non-contiguous allocation. It completely eliminates external fragmentation.
Table of Contents¶
- Basic Concepts of Paging
- Address Translation
- Page Table
- TLB (Translation Lookaside Buffer)
- Multi-level Page Tables
- Hashed Page Tables
- Inverted Page Tables
- Practice Problems
1. Basic Concepts of Paging¶
1.1 Pages and Frames¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Basic Structure of Paging β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Logical Address Space (Process) Physical Address Space (RAM) β
β β
β ββββββββββββββββββ ββββββββββββββββββ β
β β Page 0 β βββββββββββββββββββΆ β Frame 1 β β
β ββββββββββββββββββ€ ββββββββββββββββββ€ β
β β Page 1 β ββββββ β Frame 2 β β
β ββββββββββββββββββ€ β ββββββββββββββββββ€ β
β β Page 2 β ββββ β β Frame 3 β ββββββββββ β
β ββββββββββββββββββ€ β β ββββββββββββββββββ€ β β
β β Page 3 β ββ β ββββββββββββββΆ β Frame 4 β β β
β ββββββββββββββββββ β β ββββββββββββββββββ€ β β
β β β β Frame 5 β βββββββ β β
β β β ββββββββββββββββββ€ β β β
β β βββββββββββββββββΆβ Frame 6 β β β β
β β ββββββββββββββββββ€ β β β
β βββββββββββββββββββΆβ Frame 7 β β β β
β ββββββββββββββββββ β β β
β β β β
β Page size = Frame size (e.g., 4KB) β β β
β Pages can be placed in any frame! β β β
β No external fragmentation! β β β
β β β β
β Other process pages ββββββββββββββββββββββββββββββββββββββββββββββ β β
β (Sharing the same physical memory) β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
1.2 Key Terms¶
| Term | Description |
|---|---|
| Page | Fixed-size block of logical address space |
| Frame | Fixed-size block of physical memory |
| Page Table | Page β Frame mapping information |
| Page Number (p) | Identifies page in logical address |
| Offset (d) | Position within page/frame |
2. Address Translation¶
2.1 Logical Address Structure¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Logical Address Structure (32-bit example) β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 32-bit Logical Address β
β βββββββββββββββββββββββββββββββ¬ββββββββββββββββββ β
β β Page Number (p) β Offset (d) β β
β β 20 bits β 12 bits β β
β βββββββββββββββββββββββββββββββ΄ββββββββββββββββββ β
β β
β Page size = 2^12 = 4KB β
β Maximum pages = 2^20 = ~1 million β
β Maximum address space = 2^32 = 4GB β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
2.2 Address Translation Process¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Address Translation Process β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Logical address: 0x00005A34 β
β β
β 1. Separate address (Page size: 4KB = 0x1000) β
β βββββββββββββββββββββββββββββββββββββββββ β
β β 0x00005A34 β β
β β = 0x00005 (page number) + 0xA34 (offset)β β
β βββββββββββββββββββββββββββββββββββββββββ β
β β
β 2. Look up page table β
β ββββββββββββββ¬βββββββββββββ β
β β Page Numberβ Frame Numberβ β
β ββββββββββββββΌβββββββββββββ€ β
β β 0 β 2 β β
β β 1 β 7 β β
β β 2 β 1 β β
β β 3 β 5 β β
β β 4 β 8 β β
β β 5 β 3 β βββ Page 5 β Frame 3 β
β ββββββββββββββ΄βββββββββββββ β
β β
β 3. Calculate physical address β
β Physical address = (frame number Γ page size) + offset β
β = (3 Γ 0x1000) + 0xA34 β
β = 0x3000 + 0xA34 β
β = 0x3A34 β
β β
β Result: Logical address 0x5A34 β Physical address 0x3A34 β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
2.3 C Language Implementation¶
#include <stdio.h>
#include <stdint.h>
#define PAGE_SIZE 4096 // 4KB
#define PAGE_BITS 12 // log2(4096)
#define NUM_PAGES 1024 // Number of page table entries
typedef struct {
uint32_t frame_number;
uint8_t valid; // Valid bit
uint8_t read_only; // Read-only
uint8_t modified; // Modified (dirty bit)
} PageTableEntry;
PageTableEntry page_table[NUM_PAGES];
// Logical address β Physical address translation
uint32_t translate_address(uint32_t logical_address) {
// 1. Separate page number and offset
uint32_t page_number = logical_address >> PAGE_BITS;
uint32_t offset = logical_address & (PAGE_SIZE - 1);
printf("Logical address: 0x%08X\n", logical_address);
printf("Page number: %u, Offset: 0x%X\n", page_number, offset);
// 2. Check page table bounds
if (page_number >= NUM_PAGES) {
printf("ERROR: Page number out of bounds!\n");
return -1;
}
// 3. Check valid bit
if (!page_table[page_number].valid) {
printf("PAGE FAULT: Page %u is not in memory\n", page_number);
return -1; // Page fault handling required
}
// 4. Calculate physical address
uint32_t frame_number = page_table[page_number].frame_number;
uint32_t physical_address = (frame_number << PAGE_BITS) | offset;
printf("Frame number: %u\n", frame_number);
printf("Physical address: 0x%08X\n", physical_address);
return physical_address;
}
int main() {
// Initialize page table
page_table[0] = (PageTableEntry){.frame_number = 2, .valid = 1};
page_table[1] = (PageTableEntry){.frame_number = 7, .valid = 1};
page_table[2] = (PageTableEntry){.frame_number = 1, .valid = 1};
page_table[5] = (PageTableEntry){.frame_number = 3, .valid = 1};
// Test address translation
translate_address(0x00000A34); // Page 0
printf("\n");
translate_address(0x00005A34); // Page 5
return 0;
}
2.4 Calculation Example¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Address Translation Example β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Problem: Page size = 1KB, Logical address = 4500 β
β β
β Solution: β
β 1. Page size = 1024 = 2^10 bytes β
β β Offset = 10 bits β
β β
β 2. Separate logical address: β
β Page number = 4500 / 1024 = 4 (integer division) β
β Offset = 4500 % 1024 = 404 β
β β
β Verification: 4 Γ 1024 + 404 = 4096 + 404 = 4500 β β
β β
β 3. Look up page table: Page 4 β Frame 7 β
β β
β 4. Physical address = Frame 7 Γ 1024 + 404 β
β = 7168 + 404 β
β = 7572 β
β β
β Binary verification: β
β - Logical address 4500 = 0001 0001 1001 0100 β
β βββββββββββ€βββββββββββ€ β
β Page 4 Offset 404 β
β β
β - Physical address 7572 = 0001 1101 1001 0100 β
β βββββββββββ€βββββββββββ€ β
β Frame 7 Offset 404 (same!) β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
3. Page Table¶
3.1 Page Table Entry (PTE)¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Page Table Entry Structure (32-bit) β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 31 12 11 4 3 2 1 0 β
β ββββββββββββββββββββββββββββββββββββ¬βββββββββββ¬ββ¬ββ¬ββ¬ββ β
β β Frame Number (20 bits) β Reserved βDβAβUβVβ β
β ββββββββββββββββββββββββββββββββββββ΄βββββββββββ΄ββ΄ββ΄ββ΄ββ β
β β
β V (Valid): Valid bit β
β 0 = Page not in memory (page fault occurs) β
β 1 = Page is in memory β
β β
β U (User): User access allowed β
β 0 = Kernel mode only β
β 1 = User mode access allowed β
β β
β A (Accessed): Accessed bit β
β Hardware sets to 1 on access β
β Used by page replacement algorithms β
β β
β D (Dirty): Modified bit β
β Hardware sets to 1 on write β
β Determines if page needs to be written to disk on eviction β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
3.2 Page Table Storage Location¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Page Table and PTBR β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β CPU β
β ββββββββββββββββββββββββββββββββββββββββββ β
β β β β
β β PTBR (Page Table Base Register) β β
β β ββββββββββββββββββββββββββββββββββ β β
β β β 0x00100000 βββββΌββββββββ β
β β ββββββββββββββββββββββββββββββββββ β β β
β β β β β
β β PTLR (Page Table Length Register) β β β
β β ββββββββββββββββββββββββββββββββββ β β β
β β β 1024 β β β β
β β ββββββββββββββββββββββββββββββββββ β β β
β β β β β
β ββββββββββββββββββββββββββββββββββββββββββ β β
β β β
β βΌ β
β Physical Memory β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β β
β β Address 0x00100000 β β
β β βββββββββββββββββββββββββββββββββββββββββββββ β β
β β β Page Table (Process A) β β β
β β β ββββββββββββββββ¬βββββββββββββββββββββ β β β
β β β β Page 0 β Frame 5 | V=1 β β β β
β β β β Page 1 β Frame 2 | V=1 β β β β
β β β β Page 2 β Frame 8 | V=1 β β β β
β β β β ... β ... β β β β
β β β ββββββββββββββββ΄βββββββββββββββββββββ β β β
β β βββββββββββββββββββββββββββββββββββββββββββββ β β
β β β β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β On context switch: Change PTBR value to new process's page table addr β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
3.3 Memory Access Problem¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Two Memory Access Problem β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Memory access when using paging: β
β β
β CPU βββΆ Generate logical address β
β β β
β βΌ β
β [1] Access page table (Memory access #1) β
β β β
β βΌ β
β Get frame number β
β β β
β βΌ β
β [2] Access actual data (Memory access #2) β
β β β
β βΌ β
β Get data β
β β
β Problem: Memory access becomes 2x slower! β
β Solution: Use TLB (Translation Lookaside Buffer) β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
4. TLB (Translation Lookaside Buffer)¶
4.1 TLB Concept¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β TLB Structure β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β High-speed cache inside CPU or MMU β
β β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β TLB β β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€ β
β β Page Number β Frame Number β ASID β Valid β β
β ββββββββββββββββββββΌββββββββββββββββββββΌβββββββββββββΌββββββββββ€ β
β β 5 β 3 β 1 β 1 β β
β β 2 β 7 β 1 β 1 β β
β β 12 β 9 β 2 β 1 β β
β β 0 β 1 β 1 β 1 β β
β β ... β ... β ... β ... β β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β ASID (Address Space ID): Process identifier β
β β No need to flush entire TLB on context switch β
β β
β Entry count: Usually 64 ~ 1024 entries (very small, but very fast) β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
4.2 Address Translation Using TLB¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Address Translation Using TLB β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Logical address β
β β β
β βΌ β
β βββββββββββββββββββββββββββββββββββ β
β β Extract page number β β
β βββββββββββββββββββββββββββββββββββ β
β β β
β βΌ β
β βββββββββββββββββββββββββββββββββββ β
β β Search in TLB β β
β βββββββββββββββββββββββββββββββββββ β
β β β
β βββββββββββββββββββββββββββββββββββββ β
β β β β
β TLB Hit TLB Miss β
β β β β
β βΌ βΌ β
β Frame number Access page table β
β immediately obtained (memory access) β
β β β β
β β βΌ β
β β Update TLB β
β β β β
β βββββββββββββββββββββββββββββββββββββ β
β β β
β βΌ β
β Calculate physical address β
β β β
β βΌ β
β Memory access β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
4.3 Effective Access Time (EAT)¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Effective Access Time Calculation β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Parameters: β
β - TLB search time: Ξ΅ (e.g., 10ns) β
β - Memory access time: m (e.g., 100ns) β
β - TLB hit ratio: Ξ± (e.g., 0.98 = 98%) β
β β
β EAT formula: β
β EAT = Ξ± Γ (Ξ΅ + m) + (1-Ξ±) Γ (Ξ΅ + 2m) β
β β TLB Hit β TLB Miss β
β β
β Example calculation: β
β Ξ΅ = 10ns, m = 100ns, Ξ± = 0.98 β
β β
β EAT = 0.98 Γ (10 + 100) + 0.02 Γ (10 + 200) β
β = 0.98 Γ 110 + 0.02 Γ 210 β
β = 107.8 + 4.2 β
β = 112ns β
β β
β Comparison: β
β - Without TLB: 200ns (2 memory accesses) β
β - With TLB: 112ns β
β - Performance improvement: ~44% β
β β
β Higher TLB hit ratio results in greater performance improvement β
β Ξ± = 0.99: EAT = 0.99Γ110 + 0.01Γ210 = 112ns β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
5. Multi-level Page Tables¶
5.1 Problem¶
For 32-bit address space with 4KB page size: - Number of pages = 2^32 / 2^12 = 2^20 = ~1 million - PTE size = 4 bytes - Page table size = 1 million Γ 4 = 4MB (per process!)
5.2 Two-Level Page Table¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Two-Level Page Table β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 32-bit logical address: β
β ββββββββββββββββ¬βββββββββββββββ¬βββββββββββββββ β
β β p1 (10bits) β p2 (10bits) β d (12bits) β β
β β Outer page β Inner page β Offset β β
β ββββββββββββββββ΄βββββββββββββββ΄βββββββββββββββ β
β β β β β
β β β β β
β βΌ β β β
β ββββββββββββββ β β β
β β Outer Page β β β β
β β Table β β β β
β β (Level 1) β β β β
β ββββββββββββββ€ β β β
β β ... β β β β
β β p1 entry ββββββββββΌβββββββ β β
β β ... β β β β β
β ββββββββββββββ β β β β
β β βΌ β β
β β ββββββββββββββ β
β β β Inner Page β β
β β β Table β β
β β β (Level 2) β β
β β ββββββββββββββ€ β
β β β ... β β
β ββΆ β p2 entry βββββΆ Frame number β
β β ... β β β
β ββββββββββββββ β β
β β β
β βΌ β
β Physical addr = Frame Γ 4KB + d β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
5.3 Four-Level Page Table for 64-bit Systems¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β 64-bit 4-Level Page Table (x86-64) β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 64-bit virtual address (actual usage: 48 bits) β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Unused β PML4 β PDPT β PD β PT β Offset β β
β β (16) β (9) β (9) β (9) β (9) β (12) β β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β β β β β
β βΌ βΌ βΌ βΌ β β
β βββββββββ βββββββββ βββββββββ βββββββββ β β
β CR3 βββΆ β PML4 βββΆβ PDPT βββΆβ PD βββΆβ PT βββββΌββββΆ Physical addrβ
β β Table β β Tableβ β Table β β Table β β β
β βββββββββ βββββββββ βββββββββ βββββββββ β β
β β β
β Each level: 512 entries (2^9), 8 bytes/entry β β
β Table size: 512 Γ 8 = 4KB (= 1 page) β β
β β β
β PML4: Page Map Level 4 β β
β PDPT: Page Directory Pointer Table β β
β PD: Page Directory β β
β PT: Page Table β β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
5.4 Advantages of Multi-level Tables¶
// Memory savings with multi-level page tables
// Process memory usage:
// - Code: 0x00000000 ~ 0x00100000 (1MB, 256 pages)
// - Stack: 0xBFF00000 ~ 0xC0000000 (1MB, 256 pages)
// Single page table: 4MB needed (all 1 million entries)
// Two-level page table:
// - Level 1 table: 4KB (1024 entries)
// - Level 2 tables: Only what's needed!
// - Code region: 1 Γ 4KB
// - Stack region: 1 Γ 4KB
// Total: 4KB + 4KB + 4KB = 12KB (saved from 4MB to 12KB!)
typedef struct {
uint32_t present : 1;
uint32_t writable : 1;
uint32_t user : 1;
uint32_t reserved : 9;
uint32_t frame : 20; // Next level table or frame
} PageTableEntry;
// Two-level address translation
uint32_t translate_two_level(uint32_t virtual_addr) {
uint32_t p1 = (virtual_addr >> 22) & 0x3FF; // Upper 10 bits
uint32_t p2 = (virtual_addr >> 12) & 0x3FF; // Middle 10 bits
uint32_t offset = virtual_addr & 0xFFF; // Lower 12 bits
// Access level 1 table
PageTableEntry* level1 = (PageTableEntry*)PTBR;
if (!level1[p1].present) {
// Level 2 table doesn't exist
page_fault_handler();
return -1;
}
// Access level 2 table
PageTableEntry* level2 = (PageTableEntry*)(level1[p1].frame << 12);
if (!level2[p2].present) {
// Page not in memory
page_fault_handler();
return -1;
}
// Calculate physical address
uint32_t frame = level2[p2].frame;
return (frame << 12) | offset;
}
6. Hashed Page Tables¶
6.1 Structure¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Hashed Page Table β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Virtual page number β
β β β
β βΌ β
β βββββββββββββββ β
β β Hash func β β
β βββββββββββββββ β
β β β
β βΌ β
β Hash table β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Index β Chain β β
β ββββββββββΌββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€ β
β β 0 β [p=102, f=5] β [p=2050, f=12] β NULL β β
β β 1 β NULL β β
β β 2 β [p=55, f=8] β NULL β β
β β 3 β [p=1003, f=3] β [p=7, f=22] β [p=4099, f=1] β NULL β β
β β ... β ... β β
β ββββββββββ΄ββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β p = Virtual page number β
β f = Physical frame number β
β β
β Advantage: Efficient for sparse address spaces (64-bit systems) β
β Disadvantage: Chain search required on hash collision β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
6.2 Implementation¶
#define HASH_TABLE_SIZE 1024
typedef struct HashEntry {
uint64_t virtual_page;
uint64_t physical_frame;
struct HashEntry* next;
} HashEntry;
HashEntry* hash_table[HASH_TABLE_SIZE];
// Hash function
uint32_t hash(uint64_t virtual_page) {
return virtual_page % HASH_TABLE_SIZE;
}
// Search for frame number
int64_t lookup(uint64_t virtual_page) {
uint32_t index = hash(virtual_page);
HashEntry* entry = hash_table[index];
while (entry != NULL) {
if (entry->virtual_page == virtual_page) {
return entry->physical_frame;
}
entry = entry->next;
}
return -1; // Page fault
}
// Add mapping
void insert(uint64_t virtual_page, uint64_t physical_frame) {
uint32_t index = hash(virtual_page);
HashEntry* new_entry = malloc(sizeof(HashEntry));
new_entry->virtual_page = virtual_page;
new_entry->physical_frame = physical_frame;
new_entry->next = hash_table[index];
hash_table[index] = new_entry;
}
7. Inverted Page Tables¶
7.1 Concept¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Inverted Page Table β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Traditional page table: β
β - Separate table per process β
β - Virtual address β Physical address mapping β
β - Table size proportional to virtual address space β
β β
β Inverted page table: β
β - One table for entire system β
β - Entry per physical frame β
β - Table size proportional to physical memory size β
β β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Frame Number β PID β Virtual Page Number β Protection β β
β βββββββββββββββΌββββββββββββΌββββββββββββββββββββΌββββββββββββββββ€ β
β β 0 β 1 β 0x1234 β R/W β β
β β 1 β 2 β 0x0001 β R/W β β
β β 2 β 1 β 0x1235 β R/O β β
β β 3 β 3 β 0x5678 β R/W β β
β β ... β ... β ... β ... β β
β β N β 2 β 0x0002 β R/W β β
β βββββββββββββββ΄ββββββββββββ΄ββββββββββββββββββββ΄ββββββββββββββββ β
β β
β Search: (PID, virtual page number) to find frame number β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
7.2 Advantages and Disadvantages¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Inverted Page Table Pros/Cons β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Advantages: β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β 1. Memory savings β β
β β - Physical memory 4GB, frame 4KB β β
β β - Entry count = 4GB / 4KB = 1M entries β β
β β - 16 bytes per entry β Total 16MB (independent of # processes!)β β
β β β β
β β 2. Efficient for 64-bit systems β β
β β - Virtual address space is very large but β β
β β - Physical memory is relatively small β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Disadvantages: β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β 1. Search time β β
β β - Sequential search: O(n) - too slow β β
β β - Hash table required β β
β β β β
β β 2. Difficult to share memory β β
β β - Only one (PID, page) pair per frame β β
β β - Shared memory implementation complex β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Usage examples: IBM PowerPC, UltraSPARC, IA-64 β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Practice Problems¶
Problem 1: Address Translation¶
Calculate the physical address given the following conditions with a page size of 4KB:
- Logical address: 25000
- Page table: Page 6 β Frame 4
Show Answer
1. Page size = 4KB = 4096 bytes
2. Page number = 25000 / 4096 = 6 (integer division)
Offset = 25000 % 4096 = 424
Verification: 6 Γ 4096 + 424 = 24576 + 424 = 25000 β
3. Look up page table: Page 6 β Frame 4
4. Physical address = Frame 4 Γ 4096 + 424
= 16384 + 424
= 16808
Problem 2: TLB EAT Calculation¶
Calculate the Effective Access Time (EAT) given:
- TLB access time: 20ns
- Memory access time: 100ns
- TLB hit ratio: 95%
Show Answer
EAT = Ξ± Γ (Ξ΅ + m) + (1-Ξ±) Γ (Ξ΅ + 2m)
= 0.95 Γ (20 + 100) + 0.05 Γ (20 + 200)
= 0.95 Γ 120 + 0.05 Γ 220
= 114 + 11
= 125ns
Comparison: Without TLB 200ns, With TLB 125ns (37.5% improvement)
Problem 3: Page Table Size¶
For a system with 32-bit virtual address space, 4KB pages, and 4-byte PTEs: 1. What is the size of a single page table? 2. How would address bits be allocated for a two-level page table?
Show Answer
1. Single page table:
- Number of pages = 2^32 / 2^12 = 2^20 (~1 million)
- PTE size = 4 bytes
- Table size = 2^20 Γ 4 = 4MB
2. Two-level page table:
- Total 32 bits = offset(12 bits) + page table(20 bits)
- Split 20 bits into two levels: 10 bits + 10 bits
Address structure: [p1: 10 bits][p2: 10 bits][offset: 12 bits]
Each level table:
- Entry count = 2^10 = 1024
- Table size = 1024 Γ 4 = 4KB (fits exactly in 1 page)
Problem 4: Multi-level Table Memory¶
Calculate the total size of a two-level page table when a process uses only these regions:
- Code: 0x00000000 ~ 0x00400000 (4MB)
- Data: 0x10000000 ~ 0x10100000 (1MB)
- Stack: 0xBFF00000 ~ 0xC0000000 (1MB)
Show Answer
Page size = 4KB, two-level table (10 bits + 10 bits + 12 bits)
Level 1 index analysis:
- Code (0x00000000~0x00400000): p1 = 0
- Data (0x10000000~0x10100000): p1 = 64
- Stack (0xBFF00000~0xC0000000): p1 = 767
Required tables:
- Level 1 table: 1 Γ 4KB = 4KB
- Level 2 tables: 3 Γ 4KB = 12KB (for indices 0, 64, 767)
Total size = 4KB + 12KB = 16KB
Comparison: Would need 4MB for single table
Savings: (4MB - 16KB) / 4MB = 99.6% savings!
Problem 5: Inverted Page Table Design¶
Design an inverted page table for a system with 1GB physical memory and 8KB page size. - Fields and sizes required in entry - Total size of table
Show Answer
1. Frame count = 1GB / 8KB = 2^30 / 2^13 = 2^17 = 131,072 frames
2. Entry structure:
- PID: 16 bits (max 65536 processes)
- Virtual page number: 51 bits (64-bit addr - 13-bit offset)
- Protection bits: 4 bits (R/W/X/Valid)
- Other: 9 bits (spare)
Total: 80 bits = 10 bytes (or pad to 16 bytes)
3. Table size:
- Entry count: 131,072
- Entry size: 16 bytes
- Total size: 131,072 Γ 16 = 2MB
This is 0.2% of physical memory (1GB)
Next Steps¶
Let's learn about segment-based memory management in 13_Segmentation.md!
References¶
- Silberschatz, "Operating System Concepts" Chapter 9
- Intel 64 and IA-32 Architectures Software Developer's Manual
- AMD64 Architecture Programmer's Manual
- Linux kernel source:
arch/x86/mm/pgtable.c