Paged Virtual Memory Addressing
Introduction
Paged virtual memory is a memory
management technique used in modern
operating systems to provide an
abstraction of memory that allows
processes to run as if they have a large
contiguous address space, even when
physical memory is fragmented. This
technique helps in efficient memory
utilization, process isolation, and security.
The key components of paged virtual
memory include:
1. Page Tables A data structure that
maps virtual addresses to physical
addresses.
2. Page Faults Events triggered when a
process accesses a page that is not
currently in physical memory.
3. Page Replacement Algorithms
Strategies to decide which page to remove
from physical memory when new pages
need to be loaded.
---
1. Page Tables
A page table is a crucial data structure in
paged virtual memory that stores mappings
between virtual page numbers (VPNs)and
physical frame numbers (PFNs).Each
process has its own page table maintained
by the operating system.
1.1 Structure of a Page Table Entry (PTE)
Each entry in a page table contains:
- Virtual Page Number (VPN): The logical
address of a page in a process's address
space.
- Physical Frame Number (PFN): The
actual physical memory location where the
page is stored.
- Present Bit: Indicates whether the page is
in physical memory.
- Access Control Bits: Determines
permissions (read, write, execute).
- Dirty Bit: Indicates if the page has been
modified.
1.2 Multi-level Page Tables
To reduce the size of page tables, modern
systems use hierarchical or multi-level
paging:
- Single-level paging: A simple array
structure (inefficient for large address
spaces).
- Two-level or multi-level paging: Breaks
the page table into smaller chunks,
reducing memory overhead.
- Inverted page tables: Uses a hash table
to store page mappings, reducing size but
increasing lookup time.
---
2. Page Faults
A page fault occurs when a process tries to
access a page that is not currently in
physical memory. The CPU generates a
trap to the operating system, which then
handles the page fault.
2.1 Page Fault Handling Process
1. The CPU detects an invalid page
reference and triggers a page fault.
2. The OS suspends the process and
checks whether the page exists in
secondary storage (disk or SSD).
3. If the page is valid but not in memory, it
is loaded from disk into RAM.
4. The page table is updated with the new
mapping.
5. The process resumes execution.
2.2 Performance Impact
- Minor Page Fault: The page is already in
memory but was not marked as present
(e.g., swapped out).
- Major Page Fault: The page is not in
memory and needs to be fetched from
secondary storage, which is slow.
- Thrashing: If too many page faults occur
in a short time, the system spends more
time swapping pages than executing
processes.
---
3. Page Replacement Algorithms
When physical memory is full, the OS must
replace an existing page to load a new
one. Page replacement algorithms decide
which page to evict.
3.1 Common Page Replacement
Algorithms
1. First-In-First-Out (FIFO)
- Removes the oldest page in memory.
- Simple but may evict frequently used
pages.
2. Least Recently Used (LRU)
- Removes the page that was least
recently accessed.
- More efficient but requires additional
tracking overhead.
3. Optimal Page Replacement (OPT)
- Replaces the page that will not be used
for the longest time.
- Provides the best performance but is
not feasible in real-world scenarios.
4. Clock (Second-Chance) Algorithm
- Uses a circular queue with a reference
bit to give pages a "second chance" before
eviction.
- Efficient and commonly used in
real-world systems.
3.2 Working Set Model
- The working set of a process is the set of
pages it needs for efficient execution.
- If the working set does not fit in memory,
thrashingcan occur.
- The working set algorithm dynamically
allocates memory based on process
demand.
---
4. Summary
Paged virtual memory allows efficient
memory utilization and process isolation
through page tables. Page faults occur
when a page is not in memory, and page
replacement algorithms determine which
pages to evict when memory is full.
Optimizing page replacement policies can
significantly impact system performance.
---
References
1. Tanenbaum, A. S., & Bos, H. (2015).
Modern Operating Systems (4th ed.).
Pearson.
2. Silberschatz, A., Galvin, P. B., & Gagne,
G. (2018). Operating System Concepts
(10th ed.). Wiley.
3. Stallings, W. (2017). Operating Systems:
Internals and Design Principles (9th ed.).
Pearson.
