Monday, 24 June 2013

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/p2 + ½ = 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