What is the Structure of a Page Table?
Learn how a page table is structured: present, dirty, accessed, and protection bits, and why flat tables do not scale.
Expected Interview Answer
A page table is a per-process data structure maintained by the operating system that maps virtual page numbers to physical frame numbers, with each entry also carrying metadata bits such as present/valid, dirty, accessed, and protection flags that the MMU consults on every memory access.
In its simplest form, a page table is a flat array indexed directly by virtual page number, where entry i holds the physical frame number that virtual page i maps to, plus control bits. A present/valid bit tells the MMU whether the page is actually in physical memory right now or must trigger a page fault; a dirty bit tracks whether the page has been written to since it was loaded, so the OS knows whether it must be written back to disk before eviction; an accessed/referenced bit helps replacement algorithms like clock/second-chance approximate recency of use; and protection bits (read/write/execute, user/supervisor) let the MMU enforce access control and catch illegal accesses as faults. A flat table for a 64-bit address space would be astronomically large, which is exactly why multi-level and inverted page tables exist as space-efficient alternatives to the naive flat structure, but the per-entry metadata bits — present, dirty, accessed, protection — remain conceptually the same across all these structures.
- Defines the exact contract the MMU relies on for every memory access
- Explains why present, dirty, and accessed bits exist
- Sets up why flat tables do not scale to large address spaces
- Foundation for understanding multi-level and inverted page tables
AI Mentor Explanation
A page table is like a groundstaff master list where each numbered pitch square maps to an actual physical strip of turf, and every entry also carries a flag for whether that strip is currently prepared (present), whether it was used since last mowing (dirty), and who is allowed to bowl there (protection). The umpire checks this list before every delivery to confirm the strip is real and legal to use. Without those flags, the groundstaff would have no way to know which strips need re-preparation before the next match.
Step-by-Step Explanation
Step 1
Index by virtual page number
The MMU uses the virtual page number as an index into the page table.
Step 2
Read the entry
The entry provides the physical frame number plus present, dirty, accessed, and protection bits.
Step 3
Check present bit
If not present, a page fault is raised so the OS can load the page and update the entry.
Step 4
Enforce protection
The MMU checks read/write/execute and user/supervisor bits, faulting on illegal accesses.
What Interviewer Expects
- A clear description of what a page table entry contains
- Understanding of the present, dirty, and accessed bits and their purpose
- Awareness that a flat table does not scale to large address spaces
- Ability to connect this to why multi-level/inverted structures exist
Common Mistakes
- Describing a page table entry as just a physical address with no metadata
- Confusing the dirty bit with the present bit
- Not knowing the accessed bit is used by replacement algorithms
- Assuming every process shares one global page table
Best Answer (HR Friendly)
“A page table is the operating system's lookup structure that tells the hardware where each piece of a program's virtual memory actually lives in physical RAM, along with extra flags noting whether that memory is currently loaded, has been changed, and who is allowed to access it. It is the foundation that makes virtual memory and memory protection work, and its simplest flat form gets replaced by smarter, more compact structures once address spaces get large.”
Code Example
struct pte {
unsigned frame : 20; /* physical frame number */
unsigned present : 1; /* is the page in RAM? */
unsigned dirty : 1; /* written since loaded? */
unsigned accessed : 1; /* referenced recently? */
unsigned writable : 1; /* read/write permission */
unsigned user_mode : 1; /* user vs supervisor only */
};
#define NUM_VPAGES 1048576
struct pte page_table[NUM_VPAGES]; /* flat, indexed by VPN */
unsigned translate(unsigned vpn, unsigned offset) {
struct pte *e = &page_table[vpn];
if (!e->present) handle_page_fault(vpn);
e->accessed = 1;
return (e->frame << 12) | offset;
}Follow-up Questions
- Why does a flat page table not scale to a 64-bit address space?
- How is the dirty bit used during page eviction?
- What is the difference between the accessed bit and the dirty bit?
- How do multi-level page tables reduce memory overhead versus a flat table?
MCQ Practice
1. What does the present (valid) bit in a page table entry indicate?
The present bit tells the MMU whether the mapped page is actually in RAM right now, or whether a page fault must be raised.
2. What is the dirty bit used for?
The dirty bit lets the OS avoid an unnecessary disk write-back for clean (unmodified) pages during eviction.
3. Why is a naive flat page table impractical for a 64-bit address space?
A flat table sized for a full 64-bit space would need far more memory than exists, since it must cover every possible page even if unused, motivating multi-level and inverted designs.
Flash Cards
What does a page table map? — Virtual page numbers to physical frame numbers, plus metadata bits.
What does the present bit control? — Whether the page is currently in physical RAM or must trigger a page fault.
What does the dirty bit control? — Whether a modified page must be written back to disk before eviction.
Why is a flat page table impractical for large address spaces? — It would need a huge, mostly-empty array sized to the entire virtual address space.