Paged virtual memory

Selecting a page size

Important consideration is size of pages to use. OS often has choice in this matter---many MMUs allow various different page sizes.

small size: less wasted space due to internal fragmentation; fewer unused pages in memory.
large page size: more efficient disk I/O, smaller page tables

If average process segment size is s; page table entry size is e bytes; page size is p,

Average amount of internal fragmentation per segment is p/2.

Average # pages per process segment is s/p. Each page requires 'e' bytes of page table, so each process segment requires page table size of es/p bytes.

Total overhead per segment, therefore, due to internal fragmentation and page table entries, is

se/p + p/2

To minimise the overhead, differentiate with respect to page size, p, and equate to 0:

-se/p² + ½ = 0
=> p = sqrt(2se)

So for example, if the average segment size were 256K, and the page table entry size were 8 bytes, the optimum page size, to minimise overhead due to page table entries and internal fragmentation, would be sqrt(2 × 256K × 8) = 2048 = 2K.

Note that this calculation ignores the need to keep page sizes large in order to speed up paging operations; it only considers memory overheads.

last updated 18 March 1998