Virtual Memory βββ
Virtual Memory βββ¶
Overview¶
Virtual Memory is a memory management technique that allows programs larger than physical memory to run. We'll learn core concepts including demand paging, page fault handling, and Copy-on-Write.
Table of Contents¶
- Virtual Memory Concept
- Demand Paging
- Page Fault
- Copy-on-Write
- Memory Mapped Files
- Performance Analysis
- Practice Problems
1. Virtual Memory Concept¶
1.1 What is Virtual Memory?¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Virtual Memory Concept β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Process perspective: Actual situation: β
β β
β "I have exclusive Physical memory: 2GB β
β use of 4GB memory!" + Disk swap: 8GB β
β β
β ββββββββββββββββββββ ββββββββββββββββββββ β
β β Virtual address β β Physical RAM β β
β β space (4GB) β β (2GB) β β
β β β β β β
β β ββββββββββββββββ β Only some β ββββββββββββββββ β β
β β β Page 0 βββΌβββin memoryβββΆβ β Frame 100 β β β
β β ββββββββββββββββ€ β β ββββββββββββββββ€ β β
β β β Page 1 βββΌββββββββββββββΆβ β Frame 205 β β β
β β ββββββββββββββββ€ β β ββββββββββββββββ€ β β
β β β Page 2 β β β β Other processβ β β
β β ββββββββββββββββ€ β β β ... β β β
β β β ... β β β ββββββββββββββββ β β
β β β (most on β β β β
β β β disk) β β ββββββββββββββββββββ β
β β ββββββββββββββββ€ β β Disk β β
β β β Page N β β Rest on β (Swap area) β β
β β ββββββββββββββββ β disk β β β
β ββββββββββββββββββββ βββββββΆ β Page 2, 3... β β
β ββββββββββββββββββββ β
β β
β Key: Frequently used parts in memory, rest on disk β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
1.2 Advantages of Virtual Memory¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Virtual Memory Advantages β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 1. Run programs larger than physical memory β
β - Run 4GB program on 2GB RAM β
β - Load only necessary parts into memory β
β β
β 2. Run more processes simultaneously β
β - Each process doesn't use entire memory β
β - Improved multiprogramming level β
β β
β 3. Easy memory sharing β
β - Shared libraries (libc.so etc) β
β - Shared memory IPC β
β - Copy-on-Write after fork() β
β β
β 4. Accelerate process creation β
β - fork(): Copy only page tables β
β - exec(): Load only needed pages β
β β
β 5. I/O optimization β
β - Map files to memory (mmap) β
β - Reduce unnecessary copying β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
2. Demand Paging¶
2.1 Concept¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Demand Paging β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Traditional approach: Demand paging: β
β ββββββββββββββββββββ ββββββββββββββββββββ β
β β At program start β β At program start β β
β β Load entire β β Load nothing β β
β β program to memoryβ β β β
β ββββββββββββββββββββ ββββββββββββββββββββ β
β β β
β βΌ β
β ββββββββββββββββββββ β
β β First instructionβ β
β β β Page fault β β
β β β Load that page β β
β β β β
β ββββββββββββββββββββ β
β β β
β βΌ β
β ββββββββββββββββββββ β
β β Continue running β β
β β Load only needed β β
β β pages β β
β ββββββββββββββββββββ β
β β
β Lazy Loading: "Load when needed" β
β Pure Demand Paging: Never preload β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
2.2 Valid/Invalid Bit¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Page Table and Valid Bit β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Page Table β
β ββββββββββββββ¬βββββββββββββ¬ββββββββββ β
β β Page NumberβFrame Numberβ V bit β β
β ββββββββββββββΌβββββββββββββΌββββββββββ€ β
β β 0 β 4 β 1 β β In memory β
β β 1 β - β 0 β β On disk (page fault) β
β β 2 β 7 β 1 β β In memory β
β β 3 β - β 0 β β Not allocated yet β
β β 4 β 2 β 1 β β In memory β
β β 5 β - β 0 β β On disk β
β β 6 β - β i β β Invalid (illegal access) β
β ββββββββββββββ΄βββββββββββββ΄ββββββββββ β
β β
β V=1: Valid - Page is in memory β
β V=0: Invalid - Page is not in memory β
β β
β Invalid cases: β
β 1. In disk swap area β Need to load β
β 2. Never accessed yet β Need to allocate β
β 3. Invalid address β Segmentation Fault β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
3. Page Fault¶
3.1 Page Fault Handling Process (10 Steps)¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Page Fault Handling Process β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β β
β β 1. CPU references memory β Page table lookup β β
β β β β β
β β 2. Valid bit = 0 detected β Page fault trap β β
β β β β β
β β 3. OS gains control β β
β β - Save registers, process state β β
β β β β β
β β 4. Address validity check β β
β β - Terminate process if illegal address β β
β β - Continue if valid β β
β β β β β
β β 5. Find free frame β β
β β - If none, perform page replacement β β
β β β β β
β β 6. Start reading page from disk β β
β β - Disk I/O request β β
β β - Process goes to waiting state β β
β β β β β
β β 7. CPU executes other process β β
β β - Context switch β β
β β β β β
β β 8. Disk I/O complete interrupt β β
β β - Page loaded to frame β β
β β β β β
β β 9. Update page table β β
β β - Record frame number β β
β β - Valid bit = 1 β β
β β β β β
β β 10. Restart original instruction β β
β β - Resume process β β
β β - No page fault this time β β
β β β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
3.2 Hardware Support Requirements¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Hardware Requirements for Page Fault Handling β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 1. Page Table β
β - Valid/invalid bit support β
β - Reference bit, dirty bit β
β β
β 2. Secondary Memory (Swap space) β
β - Disk space for storing pages β
β - Faster access than regular file system β
β β
β 3. Instruction Restart β
β - Re-execute same instruction after page fault β
β - Recover partially executed instruction β
β β
β Example: ADD instruction causes page fault β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β ADD R1, [A], [B] ; Add values at A and B, store in R1 β β
β β β β
β β 1. Page fault during [A] fetch β Restart from beginning β β
β β 2. Page fault during [B] fetch β Must re-fetch A β β
β β β β
β β Complex case: β β
β β MVC (Move Character) - Block copy instruction β β
β β - Page fault during copy β Need to undo partial copy β β
β β - More complex if source and destination overlap β β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
3.3 Page Fault Handler Code (Pseudocode)¶
#include <stdint.h>
#include <stdbool.h>
#define NUM_FRAMES 1024
#define PAGE_SIZE 4096
typedef struct {
uint32_t frame_number;
bool valid;
bool dirty;
bool referenced;
} PageTableEntry;
typedef struct {
bool allocated;
int process_id;
int page_number;
} Frame;
Frame frame_table[NUM_FRAMES];
PageTableEntry* current_page_table;
int current_process_id;
// Page fault handler
void page_fault_handler(uint32_t virtual_address) {
uint32_t page_number = virtual_address / PAGE_SIZE;
printf("[Page Fault] Process %d, Page %u\n",
current_process_id, page_number);
// 1. Address validity check
if (!is_valid_address(current_process_id, virtual_address)) {
// Illegal access - terminate process
printf("Segmentation Fault!\n");
terminate_process(current_process_id);
return;
}
// 2. Find free frame
int frame = find_free_frame();
if (frame == -1) {
// No free frame - need page replacement
frame = select_victim_frame(); // Use LRU etc
evict_page(frame); // Remove victim page
}
// 3. Load page from disk
uint32_t disk_address = get_disk_address(current_process_id, page_number);
schedule_disk_read(disk_address, frame);
// 4. Transition process to waiting state
block_process(current_process_id);
// 5. Execute other process (scheduler)
schedule_next_process();
// --- After disk I/O completes in interrupt handler ---
}
// Disk I/O complete interrupt handler
void disk_io_complete_handler(int frame, int process_id, int page_number) {
// 6. Update page table
PageTableEntry* pte = get_page_table_entry(process_id, page_number);
pte->frame_number = frame;
pte->valid = true;
pte->dirty = false;
pte->referenced = true;
// 7. Update frame table
frame_table[frame].allocated = true;
frame_table[frame].process_id = process_id;
frame_table[frame].page_number = page_number;
// 8. Transition process to ready state
unblock_process(process_id);
// When process is rescheduled, instruction restarts
}
4. Copy-on-Write¶
4.1 Concept¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Copy-on-Write (COW) β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Traditional approach on fork(): β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β β
β β Parent process Child process β β
β β ββββββββββββββββ ββββββββββββββββ β β
β β β Memory space β Copy β Memory space β β β
β β β (100MB) β βββββββΆ β (100MB copy) β β β
β β ββββββββββββββββ ββββββββββββββββ β β
β β β β
β β Problem: 200MB memory usage β β
β β All copied memory wasted if child calls exec()! β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Copy-on-Write approach: β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β β
β β After fork(): β β
β β Parent PT Child PT Physical Memory β β
β β ββββββββ ββββββββ ββββββββββββββββ β β
β β β Page 0ββββΌβββββββΌββββββββββββΆβ Shared page 0β (read-only) β β
β β β Page 1ββββΌβββββββΌββββββββββββΆβ Shared page 1β (read-only) β β
β β β Page 2ββββΌβββββββΌββββββββββββΆβ Shared page 2β (read-only) β β
β β ββββββββ ββββββββ ββββββββββββββββ β β
β β β β
β β Memory usage: 100MB (shared!) β β
β β β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
4.2 Copy on Write¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β COW Page Copy on Write β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Child attempts to write to page 1: β
β β
β 1. Write protection violation (page is read-only) β
β 2. OS confirms it's a COW page β
β 3. Allocate and copy new page β
β 4. Update child's page table β
β 5. Execute write β
β β
β Result: β
β Parent PT Child PT Physical Memory β
β ββββββββ ββββββββ ββββββββββββββββ β
β β Page 0ββββΌβββββββΌββββββββββββΆβ Shared page 0β (read-only) β
β β Page 1ββββΌβββββββΌβββ ββββββββββββββββ€ β
β β Page 2ββββΌβββββββΌβββΌββββββββΆβ Shared page 2β (read-only) β
β ββββββββ βββββ¬βββ β ββββββββββββββββ β
β β β β
β β ββββββββββΆββββββββββββββββ β
β β β Parent page 1β (read/write) β
β β ββββββββββββββββ β
β β β
β ββββββββββββββββΆββββββββββββββββ β
β β Child page 1 β (read/write) β
β β (copy) β β
β ββββββββββββββββ β
β β
β Now page 1 is independent, pages 0,2 still shared β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
4.3 COW Implementation¶
// COW page fault handler (on write)
void cow_page_fault_handler(int process_id, uint32_t virtual_address) {
uint32_t page_number = virtual_address / PAGE_SIZE;
PageTableEntry* pte = get_page_table_entry(process_id, page_number);
// Check if COW page
if (!pte->cow_flag) {
// Real protection violation - terminate process
terminate_process(process_id);
return;
}
int old_frame = pte->frame_number;
int ref_count = get_reference_count(old_frame);
if (ref_count > 1) {
// Other process also using this page - need copy
int new_frame = allocate_frame();
if (new_frame == -1) {
new_frame = select_victim_and_evict();
}
// Copy page contents
memcpy(frame_to_address(new_frame),
frame_to_address(old_frame),
PAGE_SIZE);
// Decrement reference count
decrement_reference_count(old_frame);
// Update page table
pte->frame_number = new_frame;
pte->cow_flag = false;
pte->writable = true;
// New frame reference count = 1
set_reference_count(new_frame, 1);
} else {
// Only this process using - no copy needed, allow write
pte->cow_flag = false;
pte->writable = true;
}
// Invalidate TLB
invalidate_tlb_entry(virtual_address);
}
5. Memory Mapped Files¶
5.1 mmap() Concept¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Memory Mapped File (mmap) β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Traditional file I/O: β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β β
β β Process Kernel Disk β β
β β ββββββββββββ ββββββββββββ ββββββββββββ β β
β β β Buffer ββββ read()ββ Kernel βββββββββββββ File β β β
β β ββββββββββββ β buffer β ββββββββββββ β β
β β ββββββββββββ β β
β β β β
β β 1. System call overhead β β
β β 2. Data copied twice (diskβkernelβuser) β β
β β β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Memory mapping: β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β β
β β Process virtual address space β β
β β ββββββββββββββββββββββββββββββββββββββββββββββββ β β
β β β ... β β β
β β ββββββββββββββββββββββββββββββββββββββββββββββββ€ β β
β β β Mapped region β β β
β β β ββββββββββββββββββββββββββββββββββββββ β β β
β β β β File contents βββββββΌββ β β
β β β β (direct access) β β β β β
β β β ββββββββββββββββββββββββββββββββββββββ β β β β
β β ββββββββββββββββββββββββββββββββββββββββββββββββ€ β β β
β β β ... β β β β
β β ββββββββββββββββββββββββββββββββββββββββββββββββ β β β
β β β Auto loadβ β
β β Disk β by page β β
β β ββββββββββββββββββββββββββββββββββββββββββββββββ β fault β β
β β β File βββ β β
β β ββββββββββββββββββββββββββββββββββββββββββββββββ β β
β β β β
β β Advantages: β β
β β - No copying (Zero-Copy) β β
β β - Direct pointer access β β
β β - Multiple processes can share file β β
β β β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
5.2 mmap() Usage Example¶
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <string.h>
// Read file example
void read_file_with_mmap(const char* filename) {
int fd = open(filename, O_RDONLY);
if (fd == -1) {
perror("open");
return;
}
// Get file size
struct stat sb;
fstat(fd, &sb);
// Map file to memory
char* addr = mmap(NULL, // Kernel chooses address
sb.st_size, // Mapping size
PROT_READ, // Read-only
MAP_PRIVATE, // Private mapping
fd, // File descriptor
0); // Offset
if (addr == MAP_FAILED) {
perror("mmap");
close(fd);
return;
}
// Now can directly access file contents via addr
printf("File size: %ld bytes\n", sb.st_size);
printf("First 100 bytes:\n%.100s\n", addr);
// Unmap
munmap(addr, sb.st_size);
close(fd);
}
// File modification example (shared mapping)
void modify_file_with_mmap(const char* filename) {
int fd = open(filename, O_RDWR);
if (fd == -1) {
perror("open");
return;
}
struct stat sb;
fstat(fd, &sb);
// Shared mapping - changes reflected to file
char* addr = mmap(NULL, sb.st_size,
PROT_READ | PROT_WRITE,
MAP_SHARED, // Shared mapping!
fd, 0);
if (addr == MAP_FAILED) {
perror("mmap");
close(fd);
return;
}
// Modify file contents
if (sb.st_size >= 5) {
memcpy(addr, "Hello", 5); // Change first 5 bytes
}
// Force sync changes
msync(addr, sb.st_size, MS_SYNC);
munmap(addr, sb.st_size);
close(fd);
printf("File modification complete\n");
}
// Anonymous mapping (for shared memory)
void* create_shared_memory(size_t size) {
void* addr = mmap(NULL, size,
PROT_READ | PROT_WRITE,
MAP_SHARED | MAP_ANONYMOUS, // Map without file
-1, 0);
if (addr == MAP_FAILED) {
return NULL;
}
return addr;
}
int main() {
read_file_with_mmap("/etc/passwd");
return 0;
}
5.3 Mapping Options¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β mmap() Options β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Protection flags (prot): β
β βββββββββββββββββ¬βββββββββββββββββββββββββββββββββββββ β
β β PROT_READ β Read allowed β β
β β PROT_WRITE β Write allowed β β
β β PROT_EXEC β Execute allowed β β
β β PROT_NONE β No access (guard page) β β
β βββββββββββββββββ΄βββββββββββββββββββββββββββββββββββββ β
β β
β Flags: β
β βββββββββββββββββ¬βββββββββββββββββββββββββββββββββββββ β
β β MAP_SHARED β Changes reflected to file, shareableβ β
β β MAP_PRIVATE β COW - changes visible to self only β β
β β MAP_ANONYMOUS β Memory only without file (fd=-1) β β
β β MAP_FIXED β Map at exact specified address β β
β β MAP_LOCKED β Lock pages in memory (no swap) β β
β βββββββββββββββββ΄βββββββββββββββββββββββββββββββββββββ β
β β
β Usage examples: β
β - Load executable: MAP_PRIVATE, PROT_READ|PROT_EXEC β
β - Data file: MAP_SHARED, PROT_READ|PROT_WRITE β
β - Heap expansion: MAP_PRIVATE|MAP_ANONYMOUS β
β - Shared memory: MAP_SHARED|MAP_ANONYMOUS β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
6. Performance Analysis¶
6.1 Effective Access Time (With Page Fault)¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Effective Access Time With Page Fault β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Parameters: β
β - p: Page fault probability (0 β€ p β€ 1) β
β - ma: Memory access time (e.g., 100ns) β
β - pft: Page fault service time (e.g., 8ms = 8,000,000ns) β
β β
β Effective Access Time (EAT): β
β EAT = (1 - p) Γ ma + p Γ pft β
β β
β Example: β
β ma = 100ns, pft = 8ms, allow 10% performance degradation β
β β
β Acceptable EAT = 100ns Γ 1.1 = 110ns β
β β
β 110 = (1-p) Γ 100 + p Γ 8,000,000 β
β 110 = 100 - 100p + 8,000,000p β
β 10 = 7,999,900p β
β p = 10 / 7,999,900 β
β p β 0.00000125 β
β p β 1/800,000 β
β β
β Conclusion: Allow only 1 page fault per 800,000 accesses! β
β β
β This is why page replacement algorithms are important β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
6.2 Page Fault Time Breakdown¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Page Fault Service Time Breakdown β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β β
β β 1. Interrupt handling 1-100 ΞΌs β β
β β - Trap occurs β β
β β - Save registers/state β β
β β β β
β β 2. Page fault processing 1-100 ΞΌs β β
β β - Address validity check β β
β β - Find free frame β β
β β β β
β β 3. Disk I/O 8-10 ms βββ Most time! β β
β β - Seek time β β
β β - Rotational latency β β
β β - Transfer time β β
β β β β
β β 4. Interrupt handling 1-100 ΞΌs β β
β β - I/O complete interrupt β β
β β - Update tables β β
β β β β
β β 5. Process restart 1-100 ΞΌs β β
β β - Restore registers β β
β β - Restart instruction β β
β β β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Total time: About 8-10ms (mostly disk I/O) β
β β
β With SSD: Reduced significantly to 0.1-0.5ms β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Practice Problems¶
Problem 1: Page Fault Scenario¶
A process accesses pages in the following order. With 3 frames in memory and all initially empty, calculate the number of page faults.
Access sequence: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Show Answer
Assuming FIFO replacement:
Access Memory(3 frames) Fault?
1 [1, -, -] Fault
2 [1, 2, -] Fault
3 [1, 2, 3] Fault
4 [4, 2, 3] Fault (replace 1)
1 [4, 1, 3] Fault (replace 2)
2 [4, 1, 2] Fault (replace 3)
5 [5, 1, 2] Fault (replace 4)
1 [5, 1, 2] Hit
2 [5, 1, 2] Hit
3 [3, 1, 2] Fault (replace 5)
4 [3, 4, 2] Fault (replace 1)
5 [3, 4, 5] Fault (replace 2)
Total page faults: 10
Problem 2: EAT Calculation¶
If memory access time is 50ns and page fault service time is 10ms, what should the page fault probability be to keep performance degradation within 5%?
Show Answer
ma = 50ns
pft = 10ms = 10,000,000ns
Acceptable EAT = 50 Γ 1.05 = 52.5ns
EAT = (1-p) Γ ma + p Γ pft
52.5 = (1-p) Γ 50 + p Γ 10,000,000
52.5 = 50 - 50p + 10,000,000p
2.5 = 9,999,950p
p = 2.5 / 9,999,950
p β 2.5 Γ 10^-7
p β 1 / 4,000,000
Conclusion: At most 1 page fault per 4 million accesses
Problem 3: Copy-on-Write¶
A parent process has 100 pages and calls fork(). After the child modifies 10 pages and terminates, how many pages physically exist?
Show Answer
1. After fork():
- 100 pages shared between parent and child (read-only)
- Physical pages: 100
2. After child modifies 10 pages:
- COW occurs on each modification, allocate new page
- Physical pages: 100(original) + 10(copies) = 110
3. After child terminates:
- Child's 10 copies freed
- Shared 90 pages' reference count decreases (to 1)
- Physical pages: 100 (only parent remains)
Physical pages at each point:
- After fork(): 100
- After child modification: 110
- After child termination: 100
Problem 4: mmap() Analysis¶
Predict the output of the following code.
int fd = open("test.txt", O_RDWR); // Contents: "AAAAAAAAAA"
char* p1 = mmap(NULL, 10, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
char* p2 = mmap(NULL, 10, PROT_READ|PROT_WRITE, MAP_PRIVATE, fd, 0);
p1[0] = 'B';
p2[1] = 'C';
printf("p1: %.10s\n", p1);
printf("p2: %.10s\n", p2);
// What if we re-read the file?
Show Answer
p1: MAP_SHARED - changes reflected to file
p2: MAP_PRIVATE - changes visible only within process (COW)
p1[0] = 'B':
- First character of file changed to B
- p1 shares with file, so change is reflected
p2[1] = 'C':
- COW occurs - p2's page copied
- Second character of copy changed to C
- File not changed
Output:
p1: BAAAAAAAAA (p1[0] is B, file also changed)
p2: BCAAAAAAAA (p1's change + p2's own change)
Re-reading file: BAAAAAAAAA
(p2's C is visible only within process, not reflected to file)
Problem 5: Demand Paging Design¶
When designing a new OS, you're deciding whether to use Pure Demand Paging or Prefetching. Explain the pros and cons of each approach.
Show Answer
Pure Demand Paging:
Pros:
- No unnecessary page loading (only exactly what's needed)
- Minimize initial memory usage
- Simple implementation
Cons:
- Many page faults at program start
- Performance degradation with non-local access patterns
Prefetching:
Pros:
- Preload expected pages to reduce faults
- Effective for sequential access patterns
- Utilize locality principle
Cons:
- Memory waste on prediction failures
- Complex implementation (need good prediction algorithm)
- Possible unnecessary I/O
Real systems:
- Linux: Uses both
- Default: Demand paging
- On sequential access detection: readahead (prefetch)
- madvise(MADV_SEQUENTIAL): Prefetch hint
Recommendation:
- Default to demand paging
- Adaptive prefetching when sequential access pattern detected
Next Steps¶
Learn about page replacement algorithms in 15_Page_Replacement.md!
References¶
- Silberschatz, "Operating System Concepts" Chapter 10
- Linux man pages:
mmap(2),fork(2) - Tanenbaum, "Modern Operating Systems" Chapter 3
- Linux kernel source:
mm/memory.c,mm/mmap.c