GATE - 2013 | OS | A computer uses 46-bit virtual address, 32-bit physical address, and

GATE - 2013 [Operating System]

Question:

A computer uses 46-bit virtual address, 32-bit physical address, and a three-level paged page table organization. The page table base register stores the base address of the first-level table (T1), which occupies exactly one page. Each entry of T1 stores the base address of a page of the second-level table (T2). Each entry of T2 stores the base address of a page of the third-level table (T3). Each entry of T3 stores a page table entry (PTE). The PTE is 32 bits in size. The processor used in the computer has a 1 MB 16-way set associative virtually indexed physically tagged cache. The cache block size is 64 bytes.

What is the size of a page in KB in this computer?

(A) 2
(B) 4
(C) 8
(D) 16

Solution:

Option (C) is Correct.

Let the size of page is = 2^p B

So the no. of entries in one page is 2^p/4, where 4 is the page table entry size given in the question.

So we know that process size or virtual address space size is equal to
No. of entries × Page size

So total no. of entries for 3 level page table is,
(2^p/4)×(2^p/4)×(2^p/4)

So, No. of entries × Page size = VAS
(2^p/4)×(2^p/4)×(2^p/4)× (2^p) = 2⁴⁶
2^4p = 2⁵²
4p = 52
p = 13

∴ Page size = 2¹³   

= 8 KB

------------------------------------------------------

 

Architecture of physically indexed cache:

Architecture of virtual indexed physically tagged (VIPT):

VIPT cache and aliasing effect and synonym.
Alias: Same physical address can be mapped to multiple virtual addresses.
Synonym: Different virtual addresses mapped to same physical address (for data sharing).
So these synonyms should be in same set to avoid write-update problems.
In our problem VA = 46bits

We are using 16bits for indexing into cache.
To have two synonym is same set we need to have same 16 bits index for PA & VA.
Assume that physical pages are colored and each set should have pages of same color so that any synonyms are in same set.
Since page size = 8KB ⇒ 13bits
These 13bits are not translated during VA→PA. So 13bits are same out of 16 Index bits, 13 are same we need to make 3bits (16-13) same now.
3bits can produce, 2³ = 8 combinations which can be mapped on the different sets, so we need 8 different colors to color our pages. >br> In physically indexed cache indexing is done via physical address bits, but in virtual indexed cache, cache is indexed from (offset + set) bits. In physical Index cache indexing is done one to one (1 index maps to one page in one block of cache). In VIPT we have more/ extra bits, so mapping is not one-one. Hence these extra bits have to be taken care, such that if two virtual address refers to same page in cache block of different sets then they have to be assumed same i.e., we say of same color and put same color page in one set to avoid write update problems.