GATE CSE 2015 | Set 2 | Question: 47

Question

A computer system implements $8\;\text{kilobyte}$ pages and a $32\text{-bit}$ physical address space. Each page table entry contains a valid bit, a dirty bit, three permission bits, and the translation. If the maximum size of the page table of a process is $24\;\text{megabytes}$, the length of the virtual address supported by the system is _______ bits.

Comments

Each Page Table Entry (PTE): \(19 + 1 + 1 + 3 = 24~\text{bits} = 3~\text{bytes}\)

Maximum page table size = \(24~\text{MB}\)
\(= 24×2^{20}\) bytes

\(\Rightarrow\)

\[ \text{No of PTEs} = \frac{24×2^{20}}{3} = 2^{23} \]

Each entry corresponds to one page, so, Number of pages  $= 2^{23} $.
Hence Bits needed for Page number $(p) = 23$.

Virtual address = Page number bits + Offset bits \[ p + 13 = 23 + 13 = \boxed{36~\text{bits}} \]

Check Complete Detailed Answer Here

---

PTS =  Pages * PTE 
24 * 2^20  =  2^x  *  3
2^23  = 2^x
x = 23 bits requires for pages 

LA = 23 + 13 => 36 bits

---

MISTAKE to avoid: Reversing the logic and assuming that because the Physical Address Space gives you 19 bits for the frame number, the page table must have a maximum of $2^{19}$ entries.

Answer 1

$8\;\textsf{KB}$ pages means $13$ offset bits.

For $32$ bit physical address, $32 - 13 = 19$ page frame bits must be there in each PTE (Page Table Entry).

We also have $1$ valid bit, $1$ dirty bit and $3$ permission bits.

So, total size of a PTE (Page Table Entry) $= 19 + 5 = 24$ bits $= 3$ bytes.

​Given in question, maximum page table size $= 24\;\textsf{MB}$

Page table size $=$ No. of PTEs $\times$ size of an entry

So, no. of PTEs $= 24\;\textsf{ MB} / 3\;\textsf{B} = 8\;\textsf{M}$

Virtual address supported $=$ No. of PTEs $\ast$ Page size (As we need a PTE for each page and assuming single-level paging)

$= 8\;\textsf{M} \ast 8\;\textsf{KB}$

$= 64\;\textsf{GB} = 2^{36}$ Bytes

So, length of virtual address supported $= 36$ bits (assuming byte addressing)

Comments

Hi All,  In this question what is mean by translation . Is it the frame numbers bits?

Please confirm 

---

@Nandhakumar Yes bro. 

---

to find no. of bits to point to any frame  = Physical address bits - frame offset bits  

 32-23 = 19 bits

 

PTE(entry size) = bits to point to any frame + bits for storing other information

PTE = 19 + 5 = 24 bits = 3 Bytes

 

no. of entries in a Page tabe = Page table size / PTE

  24MB / 3B = 2^ 23 Bytes.

It means there are 2^23 page or frame in Physical address

 

So, virtual adress = page no. * page size = 2^23 * 2^13 = 2^36 Bytes.

virtual address bits = 36 bits.

 

Answer 2

The page size is \( 8~\text{KB} = 2^{13} \) bytes.
Hence, the offset part of the address requires 13 bits.

The total physical address size is \( 32~\text{bits} \).

Therefore: \( \text{Frame number bits} = 32 - 13 = 19 \)

19

13

Frame
Number

Page
Offset

Physical Address = 32 bits

---

Assume Page number = p bits.
Hence, total number of pages = \( 2^p \).

If the number of entries in the page table equals the number of pages,

\( \text{Number of pages} = \text{Number of entries in page table} = 2^p \)

We can find \( p \) using the given page table size.

p

13

Page
Number

Page
Offset

Virtual Address = (p + 13) bits

---

Each Page Table Entry (PTE) consists of the following fields:

\[ \text{PTE size} = \underbrace{19}_{\text{Frame no. bits}} + \underbrace{1}_{\text{Valid bit}} + \underbrace{1}_{\text{Dirty bit}} + \underbrace{3}_{\text{Permission bits}} = 24~\text{bits} = 3~\text{bytes} \]

Maximum page table size = \( 24~\text{MB} = 24 \times 2^{20} \) bytes

Number of Page Table Entries = \( \dfrac{24 \times 2^{20}}{3} = 2^{23} \Rightarrow p = 23 \)

---

Total Virtual Address bits = \( 23 + 13 = 36 \).

Thus, the system supports a 36-bit virtual address space.

23

13

Page
Number

Page
Offset

Total = 36 bits

Comments

Very clearly described in a storytelling formate.

Answer 3

Ans 36 bits

 

Assume Virtual Address = x bits

entry size in page table = 19(frame bits)+5(permission bits) = 24 bits = 3 Bytes

2^(x-13)*3 = 24*2^(20)

solving we get x = 36 bits

Comments

Refer this,

Answer 4

 THe Easiest way

Comments

Perfect way to approach this question

---

EXCELLENT EXPLANATION

---

Best approach

Answer 5

let 2^x pages in pg table
2^x * (frame size + book keeping)= 24MB
2^x * (19+5) = 2^20 * 24
x=23

virtual address = page no bits + offset = 23 +13 = 36

Ans : - 36

Comments

2^x * (19+5) = 2^20 * 24
x=23
explain

---

Bro The mistake is
No of Pages * ( 19 + 5 ) bits = 24 Mega Bytes

here 19+5 gives you bits so you have convert it into BYTE
19+ 5 =24 bits =  3 Byte

So the actual Equation is
2^p ( 3) Byte = 24 Mega Byte
2^p = 24 Mega / 3
2^p = 8 Mega
p = 23 bits

Answer 6

we know page size in virtual address is equal to page size in physical address
 

so , 32bit physical address where each page is 8kb (2^13) so no.of frames in physical address is 2^32 / 2 ^13 = 2^19.

19 bits in page table entry and 1 valid bit , 1 dirty bit , 3 permission bits total 24 bits in page table entry

page table size is 24mb and each page table entry has 24 bits means 3 bytes
now Number of entries in page table = size of table/ size of each entry

24mb / 3 bytes = 800000 entries in page table

8000000 can be represented by 23bits
page number is 23 bits and page size is 8kb (2 ^ 13)

we know if a size of virtual address is 2^m has a page of size 2^n
then m-n bits of logical address represent page number and n bits offset

if m-n = 23

n = 13

m = 23 + 13

m = 36 bits of virtual address