Page Size

Page Size

The page size is sometimes a parameter that can be chosen by the operating system. Even if the hardware has been designed with, for instance, 512-byte pages, the operating system can easily regard page pairs 0 and 1, 2 and 3, 4 and 5, and so on, as 1-KB pages by always allocating two consecutive 512-byte page frames for them.

Determining the best page size requires balancing various competing factors. As a result, there is no overall optimum. To start with, there are two factors that argue for a small page size. A randomly chosen text, data, or stack segment will not fill an integral number of pages. On the average, half of the final page will be empty. The extra space in that page is wasted. This wastage is called internal fragmentation. With n segments in memory and a page size of p bytes, np/2 bytes will be wasted on internal fragmentation. This reasoning argues for a small page size.

Another argument for a small page size becomes obvious if we think about a program consisting of eight sequential phases of 4-KB each. With a 32-KB page size, the program must be allocated 32-KB all the time. With a 16-KB page size, it requires only 16-KB. With a page size of 4-KB or smaller, it needs only 4-KB at any instant. Generally, a large page size will cause more unused program to be in memory than a small page size.

However, small pages mean that programs will need many pages, hence a large page table. A 32-KB program requires only four 8-KB pages, but 64 512-byte pages. Transfers to and from the disk are usually a page at a time, with most of the time being for the seek and rotational delay, so that transferring a small page takes almost as much time as transferring a large page. It might take 64 x 10 msec to load 64 512-byte pages, but only 4 x 12 msec to load four 8-KB pages.

On some machines, the page table must be loaded into hardware registers every time the CPU switches from one process to another. On these machines having a small page size means that the time required to load the page registers gets longer as the page size gets smaller. Moreover, the space occupied by the page table increases as the page size decreases.

This last point can be analyzed mathematically. Let the average process size be s bytes and the page size be p bytes.  Moreover, suppose that each page entry requires e bytes. The approximate number of pages required per process is then s/p, occupying se/p bytes of page table space. The wasted memory in the last page of the process due to internal fragmentation is p/2. In this way, the total overhead due to the page table and the internal fragmentation loss is given by the sum of these two terms:
       



The first term (page table size) is large when the page size is small. The second term (internal fragmentation) is large when the page size is large. The optimum must lie somewhere in between. By taking the first derivative with respect to p and equating it to zero, we get the equation



From this equation we can derive a formula that gives the optimum page size (considering only memory wasted in fragmentation and page table size). The result is:



For s = 1MB and e = 8 bytes per page table entry, the optimum page size is 4 KB. Commercially available computers have used page sizes ranging from 512 bytes to 64 KB. A typical value used to be 1 KB, but nowadays 4 KB or 8 KB is more common. As memories get larger, the page size tends to get larger as well (but not linearly). Quadrupling the RAM size rarely even doubles the page size.

Tags

page size, operating system, internal fragmentation, memory, rotational delay