21

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?

Greg Hewgill
  • 951,095
  • 183
  • 1,149
  • 1,285
Bobby S
  • 4,006
  • 9
  • 42
  • 61

2 Answers2

33

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?

Isuru
  • 700
  • 9
  • 22
bsantos
  • 346
  • 3
  • 3
  • 2
    4096/8 = 512 entries; To address 512 entries log2(512) = 9 bits. The total number of bits to encode each page level is 48 - log2(4096) = 36 bits. Thus the total number of levels required is 36/9 = 4. – Bobby S Apr 06 '11 at 02:24
  • Since the 2048 is in bytes, shouldn't it be converted to bits, which would make it 50/9 = 6 rounded up? – Bobby S Apr 07 '11 at 00:08
  • No, because you what to know how many bits are required to address 2048 bytes and not bits. – bsantos May 09 '11 at 20:30
  • I might be answering in 2014, but big THANKS!! – Hans Jan 17 '14 at 10:15
9
  • Logical Address bit=64,
  • Number of page will be= 2^64/2048 = 2^64/2^11 = 2^53
  • Pages we have entry sine of page table= 4 Byte ,
  • Number of Entry in 1 Page will be= 2048/4=>512,
  • bit To represent one Entry=Log(512)=9bit,
  • and bit for Page is= 53bit
  • Therefore Number of Level =53/9=>6 Level Page Table
Stephan
  • 41,764
  • 65
  • 238
  • 329
Jay Singh
  • 181
  • 2
  • 6