The Gateway to Computer Science Excellence

+1 vote

For a computer architecture with multi level paging, a page size of $4 \hspace{0.1cm}KB$, and $64 \hspace{0.1cm} bit$ Physical and Virtual address:

- What is the smallest possible size for a page table entry, rounded up to a power of $2$?
- using your result above, and assuming a requirement that each page table fits into a single page, How many levels of Page tables would be required to completely map the $64 \hspace{0.1cm} bit$ virtual space?

0

Yes total 6 level Page tables would be required to completely map the 64 bit virtual space.

But i did not understand your approach in given answer.

i think @arungate has given the right approach .

0

for (b)

what i am getting is :

Total No. of Pages= 2^{52}

Page Size= 2^{12} Bytes and Entry size from part (a) 8 Bytes (64 Bits).

No. of Entries=Page Size/Entry Size=2^{12-3}=2^{9}

So Page Table Size=2^{52} * 8 Bytes = 2^{55} Bytes

Here we cannot fit Page Table into Single Page (2^{55} --> 2^{12})

So No. of Pages Required to fit a Page Table = 2^{55}/2^{12} = 2^{43} Pages

Here as per Question Each Page Table fits into Single Page so we would required 2^{43} Page Tables to Store 2^{55} Bytes.

Now No. of Levels in Paging:

Last Level : Total Page Table =2^{43}

Second Last Level : Total Page Table =2^{43}/2^{9} = 2^{34}

Third Last Level : Total Page Table =2^{34}/2^{9} = 2^{25}

Fourth Last Level : Total Page Table =2^{25}/2^{9} = 2^{16}

Fifth Level : Total Page Table =2^{16}/2^{9} = 2^{7}

**So Total No. of Levels=6**

0

part a is trivial that answer is $64$.

Part $b-:$

$\text{PTE(Page table entry size)=64 bits}=2^6 \text{bits}=2^3 \text{byte}$

for level $1$,

# of pages$=\frac{2^{64}}{2^{12}} $

size of page table $=\frac{2^{64}}{2^{12}} \times 2^3=2^ {64} \times (\frac{1}{2^{9}})$

According to question

$2^ {64} \times (\frac{1}{2^{9}})^{x}=2^ {12} \Rightarrow x=6$

Part $b-:$

$\text{PTE(Page table entry size)=64 bits}=2^6 \text{bits}=2^3 \text{byte}$

for level $1$,

# of pages$=\frac{2^{64}}{2^{12}} $

size of page table $=\frac{2^{64}}{2^{12}} \times 2^3=2^ {64} \times (\frac{1}{2^{9}})$

According to question

$2^ {64} \times (\frac{1}{2^{9}})^{x}=2^ {12} \Rightarrow x=6$

0

@ Anand. can we generalize this as below?:

If Each Page Table fits into a Single Page Then

$2^{LA} X (\frac{1}{2^{No. of Entries}})^{x}=Page Size$

Where, x is No. of Levels in Paging.

+1

It is not generalised like this .This form is due to the data given.I am writing each steps below

$\text{number of pages}=\frac{2^{64}}{2^{12}}$ as total size of Virtual address space is $2^{64} B$

and size of each page is $2^{12} B$

Now size of page table$=\text{number of entries in page table i.e number of pages} \times \text{size of each entry}$

$\text{size of each entry}=64 bits=2^3 B$ from part a)

suppose we have only single level,then size of page table $ =\frac{2^{64}}{2^{12}} \times 2^3=2^{64} \times (\frac{2^3}{2^{12}})$

for 2 level,

$=\frac{2^{64} \times (\frac{2^3}{2^{12}})}{2^{12}} \times 2^3=2^{64} \times (\frac{2^3}{2^{12}})^{2} $

In the question it is given that size of page table should fit into single page for x level

i.e $2^{64} \times (\frac{2^3}{2^{12}})^{x}=2^{12} \Rightarrow 2^{64} \times (\frac{1}{2^{9}})^{x}=2^{12}$

+1 vote

(a) Physical memory size = $2^{64}$ bytes

Page size = $4$ Kbytes

So, number of pages = $2^{64}$$/2^{12}$ = $2^{52}$

So, a page table entry should have atleast $52$ bits.

Rounding to the nearest power of two, the answer is $64$.

(b) According to our above result, a page table entry needs $64$ bits = $8$ bytes.

So, number of entries in one level of page table is $4$ KB$/$ $8$B $= 2^9$

So the first level can address $2^9$ x $2^{12}$ $=$ $2^{21}$ bytes

Remaining addresses $=$ $2^{64}$$/$$2^{21}$ $=$ $2^{43}$

For this, we need $43$$/$$9$ $=$ $5$ more levels.

Therefore, the required levels of page tables is 5 + 1 $=$ $6$.

Page size = $4$ Kbytes

So, number of pages = $2^{64}$$/2^{12}$ = $2^{52}$

So, a page table entry should have atleast $52$ bits.

Rounding to the nearest power of two, the answer is $64$.

(b) According to our above result, a page table entry needs $64$ bits = $8$ bytes.

So, number of entries in one level of page table is $4$ KB$/$ $8$B $= 2^9$

So the first level can address $2^9$ x $2^{12}$ $=$ $2^{21}$ bytes

Remaining addresses $=$ $2^{64}$$/$$2^{21}$ $=$ $2^{43}$

For this, we need $43$$/$$9$ $=$ $5$ more levels.

Therefore, the required levels of page tables is 5 + 1 $=$ $6$.

+1

@arungate you are correct

@ srestha Here Page Size= 4KB=2^{12}

so Page Offset (d)=12 bits

Now 64-12=52bits

so for Page Table entry 52bits are here for rounding of 2 it will be 64 Bits or 8Byte.

0 votes

Let size of a page table entry be x bytes

Page Table Size = 4 KByte = 2^{12}B - requires 12 bits for addressing.

Logical Address Space = 2^{64} B

Now, we know

Size of page table=(Logical Address Space/Page Size)*Page Table Entry Size

Size of 1st level page table = (2^{64}/2^{12})*x

Size of 2nd level page table = (2^{64}/(2^{12})^{2})*x^{2}

........................................................................

........................................................................

like that

Now, last level of page table fits into single page

So, (2^{64}/(2^{12})^{y})*x^{y }= 2^{12}

Using trial and error method and y=6

we get x^{6}=2^{24}

then x=2^{4}B=16 B

Size of PTE=16B

and 6 level of page table are required

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,167 answers

193,838 comments

94,005 users