Virtual Memory + Page Replacement Flashcards
(14 cards)
Page Tables & Virtual Memory
Each process has its own Page Table, mapping virtual memory to physical memory.
Virtual memory can be much larger than physical memory.
Physical memory can store pages in any order, even non-contiguously.
If a process accesses a page not currently in memory, it causes a Page Fault.
Page Fault Handling (Step-by-Step)
Page Fault occurs – the page is not in physical memory.
Find a victim page to replace (using replacement algorithm).
Check Dirty flag – if the victim page was changed, save it to disk.
Invalidate the victim’s page table entry.
Load needed page from disk into memory.
Update the page table to point to the new location.
Resume the process from where it left off.
Multiple Processes
Each process has its own view of memory.
Same physical memory is shared between processes using different mappings.
Pages can be swapped in and out as needed using swap space (disk storage).
Page Replacement (dividing memory)
Each process gets the same number of frames.
Easy but unfair—some processes may need more memory than others.
– Equal allocation
– Each process gets m/n frames, for memory size m
– Unfair as processes will have different requirements
page replacement (memory allocation)
Memory is divided based on process size.
If process pi has size si, and total size of all processes is S, then:
Thrashing
If a process is allocated too few frames
– Experience high number of page faults
– CPU utilisation drops sharply
– spend time paging in/ out
Limit thrashing by using local replacement algorithm
Contrast with Global Replacement:
Pages can be replaced across processes → can cause widespread thrashing
Page Replacement Speed-Up
Keep a Free Page – Use it instantly on fault, write old page later.
Write Queue – Save likely victims during idle time for faster recovery (soft fault if still around).
Page Replacement
Algorithms
When memory is full, we need to choose a page to remove (a “victim”) to make room for a new one. This is called page replacement.
FIFO (First-In, First-Out)
Remove the oldest page.
Simple, but might kick out important pages.
LRU (Least Recently Used)
Remove the page that hasn’t been used in the longest time.
More accurate but harder to implement
Clock / Second Chance
Circular list of pages.
Give each page a “second chance” using an Accessed bit.
LFU (Least Frequently Used)
Replace pages used least often.
Tracks how often pages are accessed.
Key Concepts:
Working Set = pages a process actively needs.
Resident Set = pages currently in memory.
Thrashing = too many page faults, system keeps swapping.
Performance Tricks:
Use Accessed and Dirty bits to track use.
Do Soft Page Faults if the page is already queued to return.
Monitor Page Fault Frequency to decide if a process needs more or fewer pages.
