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.

In other words

Let

s = size of average process

e = bytes required for each page table entry

p = size of page, in bytes

s/p = Number of pages per process

es/p = Size of page table

p/2 = space wasted due to internal fragmentation

overhead = se/p + p/2

Want to choose p to minimize overhead.

Take derivative w.r.t. p and set to zero

-se/p^2 + 1/2 = 0

Solving for p...

p = sqrt (2se)

Let

s = size of average process= 1MB

e = bytes required for each page table entry= 8 bytes

p = size of page, in bytes

Solving for p...

p = sqrt (2se)

Example:

p = sqrt (2 * 1MB * 8) = 4K

s = size of average process= 8MB

e = bytes required for each page table entry= 4 bytes

p = size of page, in bytes

Solving for p...

p = sqrt (2se)

Example:

p = sqrt (2 * 8MB * 4) = 8K