Paging in OS

Paging

What is Paging?

• A memory management technique that allows processes to use non-contiguous physical memory.
• Divides memory into fixed-size blocks:
  • Pages: Logical memory blocks (virtual memory)
  • Frames: Physical memory blocks
• Example: Think of a book (logical memory) split into pages. The library (physical memory) stores these pages on different shelves (frames), not necessarily in order.

Why Do We Need Paging?

1. Solves external fragmentation (free memory gaps too small to be useful)
2. Allows efficient memory allocation (OS can use any free frame)
3. Simplifies memory management with fixed-size blocks
4. Enables virtual memory (run programs larger than physical RAM)

Key Components

Page Table

• A per-process lookup table that maps page numbers to frame numbers
• Managed by the Operating System (OS)
• Structure:
  | Page No. | Frame No. | Flags (R/W) |
  |----------|-----------|------------|
  | 0        | 3         | 1          |
  | 1        | 7         | 0          |
  | 2        | 2         | 1          |

Frame

• Physical memory block of fixed size (e.g., 4KB)
• All frames are identical in size to pages

Page vs Frame

Address Translation

Logical Address Structure

• Split into two parts:
  1. Page Number (p): Index in page table
  2. Page Offset (d): Position within page

Example: For 16-bit address with 4KB page size:

| Page Number (4 bits) | Offset (12 bits) |
| p=4 bits             | d=12 bits        |

Conversion Process

1. Extract page number from logical address
2. Look up frame number in page table
3. Combine frame number with offset to get physical address

Example Conversion:

• Logical address: 0x2468 (hex)
• Page size: 4KB (4096 bytes)
• Convert to binary: 0010 0100 0110 1000
• Split into p=4 bits, d=12 bits: p = 0010 (page 2) d = 010001101000 (offset 1128)
• Page table shows page 2 → frame 7
• Physical address = (7 * 4096) + 1128 = 28672 + 1128 = 29800

Thrashing

What is Thrashing?

• Severe performance degradation when the OS spends more time swapping pages than executing instructions
• Occurs when total memory demand >> available physical memory

Why Does Thrashing Happen?

• Example: System has 4GB RAM but processes need 6GB total
• OS constantly swaps pages between RAM and disk (page faults skyrocket)
• CPU utilization drops dramatically

Solutions to Thrashing

1. Increase physical memory
2. Use working set model to keep active pages in memory
3. Reduce number of concurrent processes (adjust multiprogramming degree)
4. Implement priority-based page replacement

Example Scenario

• Program A uses pages 0-3 (frames 3,7,2,5)
• Program B uses pages 0-2 (frames 1,4,6)
• Page Table for Program A:
  | Page | Frame |
  | 0    | 3     |
  | 1    | 7     |
  | 2    | 2     |
  | 3    | 5     |

When Program A accesses logical address 0x1004:

• Page number = 1 (0x1004 / 4096 = 1)
• Offset = 0x004
• Physical address = (7 * 4096) + 4 = 28672 + 4 = 28676