GATE CSE 2001 | Question: 2.21

Question

Consider a machine with $64$ MB physical memory and a $32$-bit virtual address space. If the page size s $4$ KB, what is the approximate size of the page table?

• A. $\text{16 MB}$
• B. $\text{8 MB}$
• C. $\text{2 MB}$
• D. $\text{24 MB}$

Comments

how to solve this ques........

Answer 1

Number of pages $= 2^{32} / 4KB = 2^{20}$ as we need to map every possible virtual address.

So, we need $2^{20}$ entries in the page table. Physical memory being $64 \ MB$, a physical address must be $26$ bits and a page (of size $4KB$) address  needs $26-12 = 14$ address bits. So, each page table entry must be at least $14$ bits.

So, total size of page table $= 2^{20} \times 14 \ bits ≈ 2 \ MB$ (assuming PTE is $2$ bytes)

Correct Answer: $C$

Comments

Why page entry include frame bits only? Page table entry contains page no. And the corresponding frame no.

---

Page in physical memory is page frame. And PTE (in last level page table) needs to identify frame only.

http://stackoverflow.com/questions/11783981/is-number-of-frame-number-of-pageslinux

---

4 KB = 2^2 KB = 2^2 * 2^10 B = 2^2 * 2^10 * 2^3 bits

---

One way to argue as to why the \(14\) bits is getting rounded off to \(16\) bits is that we generally aim for byte (word) alignment.

Ref. – https://www.cs.utexas.edu/~lorenzo/corsi/cs372/06F/hw/3sol.html from Arjun sir’s answer on https://gateoverflow.in/490/gate-cse-2008-question-67

Answer 2

Physical memory $=64MB=2^{26} B $

Size of frame$ =4KB =2^{12}B$

No. of frames $=  $physical memory/size of frame$ = \frac{2^{26}B}{2^{12}B}=2^{14}$

Frame number $=14 bits$

Virtual memory $=32 bits =2^{32}B$

Size of page $=$size of frame $=4KB =2^{12}B$

No. of pages$ =$virtual memory/size of page $=\frac{2^{32}B}{ {2^{12}B}} =2^{20} $

size of page table$=$Number of pages $\times$Size of each entry

size of page table$=$Number of pages $\times$Page table entry

size of page table$=$Number of pages $\times$Frame number

size of page table$=2^{20}\times 14 bits$

assume Frame number$=16bits$

size of page table$=2^{20}\times 16 bits\approx2MB$

Comments

Can we assume always 14=2B
But why assumed in Nat type question

---

You still did not get this.8 bits signify 1B, so 16 bits will signify 2B, here we are just taking 14 bits equals 2B.

---

size of page table =

Number of pages  * Size of each entry

---

Size of each entry should be 12 right? Why did you take 14. Please explain a little bit !

Answer 3

ans is C.

here page size is 4KB, which is 2^12 (12bits)

given is physical memory 64MB. therefore in bits f+d = f+12 bits

VAS is 32 bits therefore p+d=p+12 bits => p+12=32 => p=20

page table size = num of page table entries * size of each entry

here entry size is not given so we can directly take size of " f " in bits as entry size, which is 14 bit approx 2 bytes
no of pages = 2^32 / 4KB = 2^20
page table size = 2^20 * 2 bytes = 2MB

Comments

why f is 14 bits ?? shouldn't the page size and frame size are both equal ??  
shouldn't it be  12 bit(4 KB)

---

@Anjali :

Page size and frame size is same.

f here represents number of bits required to locate a single frame in the physical memory not the frame size.

Answer 4

Physical address space =64MB

No. of bits to represent the physical memory =26 bits

Logical address space =32 bits

page size =4 KB

So , the number of pages =2^32 /  2^12 = 2^20

Concept :  Page table only consist of frame number . So , page table size will depend on frame number and we don’t know how many bits do we require to represent the frame number in page table.

We know that , page offset = frame offset  and page offset =12 bits

bits req to represent the frame number = 26 -12 =14 bits

Additionally , In page table we have valid and invalid bit  , for that  we need 2 bits to represent valid (0) or invalid(1)

The bits now required in page table are = 14 + 2 bits =16 bits = 2 bytes

Total size of page table = 2^20 * 2 bytes = 2 MB