Introduction
Demand Paging is a more efficient memory management technique than swapping. Instead of moving entire processes, demand paging moves individual pages (fixed-size memory blocks, typically 4 KB) between memory and disk. Pages are loaded on demand — only when the process actually accesses them.
Why Demand Paging Over Swapping?
| Aspect | Swapping | Demand Paging |
|---|---|---|
| Unit of transfer | Entire process | Single page (4 KB) |
| Granularity | Coarse | Fine |
| I/O overhead | High (large transfers) | Low (small transfers) |
| Startup time | Must load entire process | Load only needed pages |
| Memory utilization | Wastes memory (unused parts loaded) | Efficient (only active pages in memory) |
| Suitable for | Small processes, limited hardware | Large processes, modern hardware |
Key Data Structures for Demand Paging
---
1. Page Table Entry (PTE)
Each process has a page table that maps virtual pages to physical frames. Each entry in the page table is a Page Table Entry (PTE).
PTE Fields:
| Field | Description |
|---|---|
| Physical Frame Number | The physical memory frame where this page is loaded |
| Valid Bit (V) | 1 = page is in physical memory; 0 = page is NOT in memory (on disk) |
| Protection Bits | Read / Write / Execute permissions |
| Reference Bit (R) | Set by hardware when the page is accessed (read or write) |
| Modify Bit (M) / Dirty Bit | Set by hardware when the page is written to |
| Copy-on-Write Bit | Page is shared; copy only when a process tries to write |
| Age | Used by page replacement algorithms (how long since last access) |
| Swap Address | Location on the swap device where this page is stored (when not in memory) |
Example Page Table:
Virtual Physical Valid Ref Modify Protection
Page # Frame #
0 12 1 1 0 R-X (code page, in memory)
1 -- 0 0 0 R-X (code page, on disk)
2 45 1 1 1 RW- (data page, modified)
3 -- 0 0 0 RW- (data page, on disk)
4 78 1 0 0 RW- (stack page, in memory)---
2. Page Frame Data Table (pfdata)
The kernel maintains a page frame data table (pfdata) — a global table with one entry per physical memory frame. It describes the current state of every frame in physical memory.
pfdata Entry Fields:
| Field | Description |
|---|---|
| State | Free, on free list, in use, on hash queue |
| Reference Count | Number of processes referencing this frame |
| Logical Device / Block | Identifies the data on disk (for page-in/page-out) |
| Page Number | Virtual page number currently mapped to this frame |
| Pointers | Hash queue pointers, free list pointers |
Pfdata States:
┌─────────────────┐
│ In Use │ → Being used by a process
├─────────────────┤
│ On Free List │ → Available for allocation
├─────────────────┤
│ On Hash Queue │ → Contains valid data, can be reclaimed
└─────────────────┘- When a page is freed, its frame goes on the free list but the data remains.
- If the page is needed again before the frame is reused, it can be reclaimed from the hash queue without disk I/O — this is called page reclaim.
---
3. Disk Block Descriptor
Each page in a process's virtual address space has a disk block descriptor that tells the kernel where to find the page's data on disk.
Disk Block Descriptor Fields:
| Field | Description |
|---|---|
| Swap Device | Which swap device holds this page |
| Block Number | Block number on the swap device |
| Type | Swap file, executable file, or demand-zero |
Types of Pages:
- Demand Fill (from executable): Page is loaded from the executable file on disk.
- Demand Zero: Page is initialized with zeros (BSS, new heap pages).
- Swap: Page has been written to the swap device previously.
---
4. Swap Use Table
- Tracks the number of references to each page on the swap device.
- When a page is copied to swap, the reference count is set.
- When all references are gone (all processes have loaded/freed the page), the swap space is freed.
Relationship Between Data Structures
Process Page Table pfdata Table
┌────────────────────┐ ┌────────────────────┐
│ VPage 0 → Frame 12│────────►│ Frame 12: In Use │
│ VPage 1 → (on disk)│ │ ref_count = 1 │
│ VPage 2 → Frame 45│────────►│ Frame 45: In Use │
│ VPage 3 → (on disk)│ │ ref_count = 1 │
│ VPage 4 → Frame 78│────────►│ Frame 78: In Use │
└────────────────────┘ └────────────────────┘
Disk Block Descriptors Swap Device
┌────────────────────┐ ┌────────────────────┐
│ VPage 1 → Block 200│────────►│ Block 200: data │
│ VPage 3 → Block 340│────────►│ Block 340: data │
└────────────────────┘ └────────────────────┘Summary
- Page Table Entries map virtual pages to physical frames with status bits (valid, reference, modify).
- pfdata tracks the state of every physical memory frame.
- Disk Block Descriptors tell the kernel where to find each page on disk.
- Swap Use Table tracks references to pages on the swap device.
- Page reclaim allows reuse of freed pages without disk I/O if the frame hasn't been overwritten.