Paging in Memory Management

1. Definition

Paging is a non-contiguous memory allocation technique that eliminates external fragmentation. It divides both logical (virtual) address space and physical memory into fixed-size blocks:

• Pages: Fixed-size blocks of logical/virtual memory (e.g., 4 KB)
• Frames (Page Frames): Same-size blocks of physical memory
• Page Table: Data structure maintained by OS that maps page number -> frame number. Each process has its own page table base register (PTBR).

Logical address = $(p, d)$ where $p$ = page number (index into page table), $d$ = offset within page.

Physical address = $(f, d)$ where $f$ = frame number from page table entry.

Translation:

Logical Addr (e.g., 16-bit with 1K page): 
 |  page p  | offset d |
      |           |-------> offset passes unchanged
      v
 Page Table[p] -> frame f
      |
 Physical Addr = f * page_size + d

With TLB (Translation Lookaside Buffer) caching recent translations for speed.

Example: Page size 4KB, 32-bit VA: 20-bit $p$, 12-bit $d$. Logical addr 0x00403ABC : $p=0x00403$, $d=0xABC$ -> if PageTable[0x00403]=0x07F1A then physical = 0x07F1AABC.

If page not in memory, page fault occurs - OS loads page from disk (demand paging, virtual memory).

2. Diagram

  Process Virtual Memory              Page Table               Physical Memory
  +---------------+               +------------+             +---------------+
  | Page 0        |-------------->| Frame 2    |------------>| Frame 0       |
  +---------------+               +------------+             +---------------+
  | Page 1        |-------------->| Frame 5    |------------>| Frame 1       |
  +---------------+               +------------+             +---------------+
  | Page 2        |               | invalid    |             | Frame 2: Pg0  |
  +---------------+               +------------+             +---------------+
  | Page 3        |-------------->| Frame 1    |             | Frame 3       |
  +---------------+               +------------+             +---------------+
                                                                 Frame 5: Pg1

3. Advantages of Paging

1. No External Fragmentation: Any free frame can be allocated to any page; memory is used efficiently. Compaction not needed.

2. Supports Virtual Memory: Allows process size > physical memory via demand paging; only needed pages loaded, rest on disk.

3. Simplifies Memory Management: Fixed-size blocks easy to manage with free-frame list; allocation/deallocation fast.

4. Allows Sharing: Shared pages (common code/libraries) can map to same frame in different processes - saves memory.

5. Memory Protection: Page table entry contains protection bits (R/W/X, user/supervisor) - prevents illegal access; invalid entries cause trap.

6. Supports Multiprogramming: Multiple processes can reside in fragmented physical frames simultaneously.

7. Efficient Swapping: Swapping whole pages is easy; copy-on-write optimization possible.

Disadvantage (for completeness): Internal fragmentation (last page may be partially unused ~ half page average), and page table overhead (+ TLB needed) and extra memory reference if TLB miss (2 accesses).