The Gateway to Computer Science Excellence
+32 votes

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 minimum number of page colours needed to guarantee that no two synonyms map to different sets in the processor cache of this computer?

  1. $2$
  2. $4$
  3. $8$
  4. $16$
in Operating System by Veteran (106k points)
edited by | 9.8k views

Can it be written this way: 

PA bits - ( cache indexing + cache offset + page offset) = page color bits

32 - (10 + 6 + 13) = 3 

Thus 23 = 8 colors


Important point --> virtually indexed physically tagged cache

@Tuhin its not PTE bits.Its Physical address bits

Great explanation here.


Very well explained the issue with virtually accessed cache.

how to find page offset? tuhin

1 Answer

+42 votes
Best answer

Let the page size be $x$.

Since virtual address is $46$ bits, we have total number of pages $ = \frac{2^{46}}{x}$

We should have an entry for each page in last level page table which here is $T3$. So,

Number of entries in $T3$ (sum of entries across all possible $T3$ tables) $ = \frac{2^{46}}{x}$

Each entry takes $32$ bits $= 4$ bytes. So, total size of $T3$ tables $= \frac{2^{46}}{x} \times 4 = \frac{2^{48}}{x}$ bytes

Now, no. of $T3$ tables will be Total size of $T3$ tables/page table size  and for each of these page tables, we must have a $T2$ entry. Taking $T3$ size as page size, no. of entries across all $T2$ tables
$= \frac{\frac{2^{48}}{x}}{x} = \frac{2^{48}}{x^2} $

Now, no. of T2 tables (assuming T2 size as pagesize) = $\frac{2^{48}}{x^2}  \times 4$ bytes = $\frac{\frac{2^{50}}{x^2}} {x}  = \frac{2^{50}}{x^3}$.

Now, for each of these page table, we must have an entry in $T1$. So, number of entries in $T1$


And size of $T1$ $=\frac{2^{50}}{x^3} \times 4  =\frac{2^{52}}{x^3} $

Given in question, size of $T1$ is page size which we took as $x$. So,

$x = \frac{2^{52}}{x^3}$

$\implies x^4 =2^{52}$

$\implies x = 2^{13} = 8KB$

Min. no. of page color bits $=$ No. of set index bits $+$ no. of offset bits $-$ no. of page index bits (This ensures no synonym maps to different sets in the cache)

We have $1$MB cache and $64$B cache block size. So,

number of sets $= 1$MB$/(64$ B $\times$ Number of blocks in each set$) = 16K/16 (16$ way set associative) $= 1K = 2^{10}.$

So, we need $10$ index bits. Now, each block being $64 (2^6)$ bytes means we need 6 offset bits. 

And we already found page size $= 8KB = 2^{13}$, so $13$ bits to index a page

Thus, no. of page color bits $= 10 + 6 - 13 = 3. $

With 3 page color bits we need to have $2^3 = 8$ different page colors

More Explanation: 

A synonym is a physical page having multiple virtual addresses referring to it. So, what we want is no two synonym virtual addresses to map to two different sets, which would mean a physical page could be in two different cache sets. This problem never occurs in a physically indexed cache as indexing happens via physical address bits and so one physical page can never go to two different sets in cache. In virtually indexed cache, we can avoid this problem by ensuring that the bits used for locating a cache block (index+offset) of the virtual and physical addresses are the same. 

In our case we have $6$ offset bits $+ 10$ bits for indexing. So, we want to make these $16$ bits same for both physical and virtual address. One thing is that the page offset bits $- 13$ bits for $8$ KB page, is always the same for physical and virtual addresses as they are never translated. So, we don't need to make these $13$ bits same. We have to only make the remaining $10 + 6 - 13 = 3$ bits same. Page coloring is a way to do this. Here, all the physical pages are colored and a physical page of one color is mapped to a virtual address by OS in such a way that a set in cache always gets pages of the same color. So, in order to make the $3$ bits same, we take all combinations of it $(2^3 = 8)$ and colors the physical pages with $8$ colors and a cache set always gets a page of one color only. (In page coloring, it is the job of OS to ensure that the $3$ bits are the same).

Correct Answer: $C$

by Veteran (434k points)
edited by
sir,is this page colouring thing in syllabus?
is this in syllabus??
sir ,in physical indexed and virtual taged  cache we can access  TLB and  cache in parllel.
in virtually index physically tagged cache we access tlb and cache paralley i don't know about physical indexed and virtual taged  cache!
@Arjun Sir,

I am not getting explanation from here.Any book where i can read this topic in bit detail?
sir.. for set indexing 10 bits. for offset in block 6 bits. but to identify one of the 16 block from a set? why did we not take that 4 bits in count during comparision?
for that part tag will be needed which we will get after address translation.

@Sheshang  This is because it is Virtually indexed Physically tagged cache so we will do indexing to a particular set using virtual address so we need 10 bits to index into a particular set and then we will take all the 16 blocks of this indexed set, then which particular block to be picked from this set will be decided by comparing tags of all the blocks by taking taking tag bits from physical address(bcoz it is physically tagged ) and after selecting a particular block we will need 6 bits to choose a particular byte(i.e block offset) and this 6 bits will again be taken from virtual address


 a cache set always gets a page of one color only. 

Can two different cache sets get same color pages?

Because we have 2^10 sets and only 8 colors?


I'm not getting this part.

no. of page color bits = 10 + 6 - 13 = 3. 

why are page bits subtracted from (indexing+offset) of cache? 


In virtually indexed cache, we can avoid this problem by ensuring that the bits used for locating a cache block (index+offset) of the virtual and physical addresses are the same. 

I am unable to understand how this will work. Not getting the exact picture ! When OS translates the VA to PA and if these bits remain the same how its ensuring that cache will not have multiple copies.

@Arjun sir, I got where the problem is. But I need more clarity on this.

Could you give an example in form of like 2 virtual address, size of the cache, associativity given, and those 2 virtual address end up placing the same physical block of main memory into different set or line of cache
To prevent aliasing, the maximum number of sets that can be allowed should be $2^7$

Hence, the maximum allowable cache size to prevent aliasing problem must be $2^7*2^4*2^6=128KB$

if u got it,  can u pls explain this Ayush Upadhyaya ;

because am not getting it how there are 8 colors needed for this!!

@Gate Fever-because 3 bits of the set index come from the virtual page address.

Check Udacity video on this Topic. You'll get more.
actually that i got!

what i didn't get is why 10+6-13 is done ;

pls tell me that!

in this it is given that no 2 synonyms maps to 2 different sets; so cant we just find the no of sets and tell that this much different colors are required!!(each set is colored differently)
@Gate fever - I am trying to get a logical diagram for this. Will make soon. Currently, I am unable to imagine it.

See what is happening is here your 3 bits (Infact 3 Most significant bits) of the cache set index are dependent on the 3 Lower order bits of the virtual page number and that is the problem. This can result in a problem where two different virtual pages who map to the same physical page, end up loading the same physical page into 2 different sets of the cache, resulting in data inconsistency and moreover, you'll never be able to find such blocks(it is very difficult).

So, how many virtual pages can do this? $2^3=8$ and so you need 8 colors.

To prevent this, all of your cache index+word offset bits must solely come from the page offset bits and they must not depend on the virtual page number.
right now am not able to get it!

pls if u are able to make its logical diagram,then pls upload it!!

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,833 questions
57,733 answers
107,887 users