Finding the Optimal Page Size in Memory Management: Balancing Overhead and Page Faults

Explore the factors influencing the choice of optimal page size in operating systems using paging. This guide explains the trade-off between page table size (memory overhead) and page faults, providing a framework for determining an efficient page size.

Finding the Optimal Page Size in Memory Management

The Page Table Size and its Overhead

In operating systems using paging for memory management, the page table is a crucial data structure mapping logical addresses (used by programs) to physical addresses (locations in RAM). A larger page table requires more memory, increasing system overhead. The goal is to find a page size that minimizes this overhead while keeping page faults low.

Calculating Page Table Size

The size of the page table is calculated as:

Page Table Size = (Number of page entries) * (Size of one page table entry)

Example: Impact of Page Size on Page Table Size

Consider a virtual address space of 2GB (2 * 230 bytes).

Scenario 1: Page Size = 2KB (2 * 210 bytes)

Number of pages = (2 * 230) / (2 * 210) = 220 = 1,048,576 pages

Scenario 2: Page Size = 2MB (2 * 220 bytes)

Number of pages = (2 * 230) / (2 * 220) = 210 = 1024 pages

Increasing the page size reduces the number of pages and, therefore, the size of the page table.

Internal Fragmentation Due to Page Size

There's always some wasted space (internal fragmentation) at the end of the last page unless the virtual address space is a multiple of the page size. For example, a 17KB virtual address space and a 2KB page size mean 9 pages are needed; the ninth page contains only 1KB, wasting 1KB.

Calculating Overhead

Let's define:

  • p: Page size (bytes)
  • e: Page table entry size (bytes)
  • S: Virtual address space size (bytes)

Then the overhead (O) is approximately:

O = (S / p) * e + p / 2

On average, the wasted space per page is half the page size (p/2).

Minimizing Overhead

To minimize overhead, we take the derivative of the overhead function with respect to the page size and set it equal to zero:

∂O/∂p = -S / p2 + 1/2 = 0

Solving for p (page size):

p = √(2Se)

This formula gives an approximation of the optimal page size to minimize overhead.