Help me understand why page sizes are a power of 2?

Question

Answer I need help with is:

Recall that paging is implemented by breaking up an address into a page and offset number. It is most efficient to break the address into X page bits and Y offset bits, rather than perform arithmetic on the address to calculate the page number and offset. Because each bit position represents a power of 2, splitting an address between bits results in a page size that is a power of 2.

i don't quite understand this answer, can anyone give a simpler explanation?

Answer 1

If you are converting a (linear) address to page:offset, you want to divide the address by the page size and take the integer answer as the page, and the reminder as the offset.

This is done using integer division and modulus (MOD, "%") operators in your programming language.

A computer represents an address as a number, stored as binary bits.

Here's an example address: 12 is 1100 in binary.

If the page size is 3, then we'd need to calculate 12/3 and 12%3 to find the page and offset (4:0 respectively).

However, if the page size is 4 (a power of 2), then 4 in binary is 100, and integer division and modulus can be computed using special 'shortcuts': you can strip the last two binary digits to divide, and you can keep only the last two binary digits for modulus. So:

12/4 == 12>>2 (shifting to remove the last two digits)

12%4 == 12&(4-1) (4-1=3 is binary 11, and the '&' (AND) operator only keeps those)

Answer 2

If you have n binary digits at your disposal, then you can encode 2ⁿ different values.

Given an address, your description states some bits will be used for the page, and some for the offset. As you're using a whole number of binary bits for the for offset Y, then the page size is naturally a power of 2, specifically 2^Y.

Answer 3

Because the representation of the data. The page offset sets the size of the page, and since the data is represented in binary, you will have a number n of bits to define the offset, so you will have pages with a size of 2^n.

Let's suppose you have an address like this 10011001, and you split it in 1001:1001 for page:offset. Since you have 4 bits to define the offset, your page's size is 2⁴.

Answer 4

Working with powers of two leads to more efficient hardware so that's what hardware designers do. Consider a cpu with a 32-bit address, and an n-bit page number:

+----------------------+--------------------+
| page number (n bits) | byte offset (32-n) |
+----------------------+--------------------+

This address is sent to the virtual memory unit, which directly separates the page number and byte offset without any arithmetic operations at all. Ie, it treats the 32-bit value as an array of bits, and has (more or less) a wire running directly to each bit. This allows the memory hardware to extract the page number and byte offset in parallel, without performing any arithmetic operations.

At the same time, this approach requires splitting on a bit boundary, which leads directly to power-of-2 page sizes.