Q4Operating System

Paging is a memory management scheme that allows the physical address space of a process to be non-contiguous. Logical memory is divided into fixed-size blocks called pages (typically 4KB), and physical memory is divided into fixed-size blocks called frames of the same size. When a process is to be executed, its pages are loaded into any available memory frames.

A logical address generated by the CPU is divided into two parts: Page Number (p) — used as an index into the page table to find the corresponding frame number. Page Offset (d) — combined with the frame base address to form the physical address. Physical Address = Frame Base Address + Offset.

The page table is a per-process data structure that maps page numbers to frame numbers. Each entry (Page Table Entry — PTE) contains:

• Frame Number: The physical frame where the page resides.
• Valid/Invalid Bit: Indicates whether the page is currently in physical memory (valid) or on disk (invalid — causes page fault).
• Protection Bits: Read, write, execute permissions.
• Dirty Bit (Modified Bit): Set when the page has been written to. Used to decide if the page must be written to disk when replaced.
• Reference Bit (Accessed Bit): Set when the page is accessed. Used by page replacement algorithms.

• Simple (Single-Level) Page Table: One table for the entire address space. For 32-bit address space with 4KB pages, the page table has 2^20 ≈ 1M entries — too large.
• Two-Level (Hierarchical) Page Table: The page table itself is paged. Used in 32-bit x86 (two levels). Reduces memory required for page tables using outer and inner page tables.
• Hashed Page Table: A hash table used for address spaces > 32 bits. The page number is hashed to find the frame number.
• Inverted Page Table: One entry per physical frame (not per logical page). Reduces page table memory but increases search time. Used in IBM and PowerPC.

Accessing the page table in main memory for every memory reference doubles the memory access time. The Translation Lookaside Buffer (TLB) is a fast, small hardware cache (typically 64–1024 entries) inside the MMU that stores recently used page-to-frame mappings.

• TLB Hit: If the page number is found in the TLB, the frame number is obtained directly. Access time ≈ TLB access time + memory access time.
• TLB Miss: If not found in TLB, the page table in memory must be accessed, then the TLB is updated with the new mapping. Access time ≈ 2 × memory access time (page table + actual access).
• Hit Ratio (α): The fraction of times a page number is found in the TLB. Effective Access Time (EAT) = α(TLB time + mem time) + (1-α)(TLB time + 2 × mem time).
• ASID (Address Space ID): TLBs may store ASIDs to differentiate between entries of different processes, avoiding TLB flush on context switches.

Example: TLB access time = 20ns, memory access time = 100ns, hit ratio α = 0.80. EAT = 0.80 × (20+100) + 0.20 × (20+200) = 96 + 44 = 140ns (vs 200ns without TLB). TLB dramatically reduces effective memory access time, making paging practical.