Summary of Virtual Memory (Chapter 10)
Key Concepts & Definitions
1. Virtual Memory
o Allows execution of processes not entirely in memory.
o Abstracts physical memory into a large uniform storage array.
o Benefits:
Programs can exceed physical memory size.
More efficient CPU utilization and throughput.
Shared libraries and memory between processes.
2. Demand Paging
o Pages are loaded only when needed (on demand).
o Page Fault: Occurs when a page is not in memory.
Steps:
1. Check validity of memory access.
2. Find a free frame (or replace one).
3. Read page from disk.
4. Update page table and restart instruction.
o Performance Impact:
Effective Access Time
= (1−p)×memory access+p×page fault time(1−p)×memory a
ccess+p×page fault time.
3. Copy-on-Write (COW)
o Parent and child processes share pages initially.
o Pages are copied only when modified.
o Used in fork() to optimize process creation.
4. Page Replacement Algorithms
o FIFO: Replaces oldest page (suffers from Belady’s anomaly).
o Optimal (OPT): Replaces page not used for longest time
(theoretical).
o LRU: Replaces least recently used page (approximated using
counters or stacks).
o Second-Chance/Clock: Uses reference bit to approximate LRU.
o LFU/MFU: Based on frequency of use (rarely used).
5. Thrashing
o Excessive paging due to insufficient frames.
o Working-Set Model: Tracks pages used in
recent ΔΔ references.
o Page-Fault Frequency (PFF): Adjusts frame allocation based
on fault rate.
6. Memory Compression
o Alternative to swapping; compresses pages into fewer frames.
o Used in mobile OS (Android, iOS) and macOS/Windows.
7. Kernel Memory Allocation
o Buddy System: Allocates power-of-2 sized blocks (coalesces
free blocks).
o Slab Allocation: Pre-allocates objects in caches (reduces
fragmentation).
8. TLB Reach
o Amount of memory accessible via TLB = (TLB entries × page
size).
o Increased by larger pages or multiple page sizes (e.g., Linux
huge pages).
9. NUMA (Non-Uniform Memory Access)
o CPUs access local memory faster than remote memory.
o OS allocates frames "close" to the requesting CPU.
10. Operating System Examples
o Linux: Uses active/inactive lists for page replacement.
o Windows: Uses working-set trimming and clustering.
o Solaris: Uses two-handed clock algorithm with scanrate
adjustment.
Flashcards (Fill-in-the-Blank)
1. Virtual Memory allows processes to execute even if they are not
entirely in __________.
o Answer: physical memory
2. A __________ occurs when a process references a page not currently in
memory.
o Answer: page fault
3. The __________ page-replacement algorithm suffers from Belady’s
anomaly.
o Answer: FIFO
4. In the __________ algorithm, the page not used for the longest time is
replaced.
o Answer: Optimal (OPT)
5. The __________ bit is used to avoid writing unmodified pages to disk
during replacement.
o Answer: modify (or dirty)
6. __________ allows parent and child processes to share pages until
modification occurs.
o Answer: Copy-on-Write (COW)
7. Thrashing occurs when a system spends more time paging than
__________.
o Answer: executing
8. The __________ model defines a set of pages used by a process in the
last ΔΔ references.
o Answer: working-set
9. In the __________ algorithm, pages are arranged in a circular queue with
a reference bit.
o Answer: second-chance (or clock)
10. __________ is an alternative to paging that compresses multiple
pages into a single frame.
Answer: Memory compression
11. The __________ system allocates memory in power-of-2 blocks for
kernel memory.
Answer: buddy
12. __________ allocation uses caches for kernel objects to reduce
fragmentation.
Answer: Slab
13. TLB reach is calculated as (TLB entries × __________).
Answer: page size
14. In NUMA systems, memory access time depends on the
__________ of the CPU.
Answer: locality (or proximity)
15. Linux uses __________ and __________ lists to manage page
replacement.
Answer: active, inactive
16. Windows uses __________ to adjust the number of frames
allocated to processes.
Answer: working-set trimming
17. Solaris’s pageout algorithm uses a __________ scanrate to
manage free memory.
Answer: two-handed clock
18. A __________ fault occurs when a page is in memory but not
mapped to the process.
Answer: minor
19. The __________ replacement policy is used in mobile OS due to
lack of swap space.
Answer: memory compression
20. The __________ bit indicates whether a page has been referenced
recently.
Answer: reference
Examples & Rules
Belady’s Anomaly: FIFO can increase page faults with more frames
(e.g., reference string 1,2,3,4,1,2,5,1,2,3,4,5).
LRU Approximation: Second-chance algorithm uses a reference bit to
simulate LRU.
Working Set: If Δ=10Δ=10, WS at time t1t1 for references
2,6,1,5,7,7,7,5,1,6 is {1,2,5,6,7}.
Slab Allocator: Kernel objects (e.g., task_struct in Linux) are cached
for fast allocation.
This summary and flashcards cover all major concepts, definitions, and
examples from the chapter. Let me know if you'd like additional details!