Multi-level page tables - hierarchical paging

operating-system paging virtual-address-space
Bobby S picture Bobby S · Apr 5, 2011 · Viewed 26k times · Source

Example question from a past operating system final, how do I calculate this kind of question?

A computer has a 64-bit virtual address space and 2048-byte pages. A page table entry takes 4 bytes. A multi-level page table is used because each table must be contained within a page. How many levels are required?

How would I calculate this?

Answer

bsantos picture bsantos · Apr 6, 2011

Since page table must fit in a page, page table size is 2048 bytes and each entry is 4 bytes thus a table holds 2048/4=512 entries. To address 512 entries it requires log2(512)=9 bits. The total number of bits available to encode the entry for each page level is 64-log2(2048)=53 bits (the number of bits of address space minus the page offset bits). Thus the total number of levels required is 53/9=6 (rounded up).

The x86-64 default page table size is 4096 bytes, each page table must fit in a page and a page table entry is 8 bytes. Current CPUs only implement 48 bits of virtual address space. How many page table levels are required?

Related questions

How does multi-level page table save memory space?

I am trying to understand how multi-level page table saves memory. As per my understanding, Multi-level page table in total consumes more memory than single-level page table. Example : Consider a memory system with page size 64KB and 32-bit processor. Each …

Read More
What is page table entry size?

I found this example. Consider a system with a 32-bit logical address space. If the page size in such a system is 4 KB (2^12), then a page table may consist of up to 1 million entries (2^32/2^12). Assuming that each entry consists of 4 …

Read More
Differences or similarities between Segmented paging and Paged segmentation?

I was studying combined paging/segmentation systems and in my book there were two approaches to this : 1.paged segmentation 2.segmented paging I could not make out the difference between the two. I think in paged segmentation the segment is divided …

Read More