Question

A computer system supports a logical address space of \( 2^{32} \) bytes. It uses two-level hierarchical paging with a page size of 4096 bytes. A logical address is divided into a \( b \)-bit index to the outer page table, an offset within the page of the inner page table, and an offset within the desired page. Each entry of the inner page table uses eight bytes. All the pages in the system have the same size. The value of \( b \) is ___________ . (Answer in integer)

Hint:

To determine the number of bits required for indexing, break the logical address into page offset, inner table index, and outer table index.

Answer 1

Correct Answer: 11

The address space spans \(2^{32}\) bytes, so each logical address is 32 bits long. Since a page contains \(4096 = 2^{12}\) bytes, the lower 12 bits of the address specify the position within a page.

Each entry of an inner page table occupies 8 bytes. A single page can therefore store \(4096/8 = 512 = 2^9\) such entries. This means that 9 bits of the logical address are used to select an entry in the inner page table.

After accounting for the offset and the inner-level indexing, the remaining bits of the logical address must identify the entry in the outer page table.

\(32 - (12 + 9) = 11\)

Hence, the outer page table is indexed using \(\boxed{11}\) bits.