GATE CSE 1999 | Question: 19

Question

A certain computer system has the segmented paging architecture for virtual memory. The memory is byte addressable. Both virtual and physical address spaces contain $2^{16}$ bytes each. The virtual address space is divided into $8$ non-overlapping equal size segments. The memory management unit (MMU) has a hardware segment table, each entry of which contains the physical address of the page table for the segment. Page tables are stored in the main memory and consists of $2$ byte page table entries.

1. What is the minimum page size in bytes so that the page table for a segment requires at most one page to store it? Assume that the page size can only be a power of $2$.

2. Now suppose that the pages size is $512$ bytes. It is proposed to provide a TLB (Transaction look-aside buffer) for speeding up address translation. The proposed TLB will be capable of storing page table entries for $16$ recently referenced virtual pages, in a fast cache that will use the direct mapping scheme. What is the number of tag bits that will need to be associated with each cache entry?

3. Assume that each page table entry contains (besides other information) $1$ valid bit, $3$ bits for page protection and $1$ dirty bit. How many bits are available in page table entry for storing the aging information for the page? Assume that the page size is $512$ bytes.

Comments

for part B:

TLB stores page table entries, it is given that page table entry size = 2B = 16 bits
#Pages = $\frac{2^{13}}{2^9} = 2^4$ so, 4 bits represents page number.
also, the virtual page address it contain will also have 9 bits to represent Page offset.

Rest we are left with tag bits, which are = 16 - 9 - 4 = 3 bits

---

For part B, note

The TLB is placed after the segment table.

so we 2^13 and not 2^16 is taken, ($2^3$ segments already present, 3 bits gone in addressing it)

---

@amarVashishth

That’s the wrong way to do , why would you consider page table entry with tag . As page table entry contains frame number + additional bits . From this we cannot find tag bits . Answer is correct because virtual address space is also here 16 . We should be comparing it with virtual address space bits , because they’re the one being mapped . Also we should refrain from doing this way, as there could be additional bits such as valid , dirty and so on.  which are useless for tag part of a virtual address.

Correct , me if I’m wrong and also do check the answer that I’ve given because if my understanding is wrong then the answer I’ve given is also wrong.

Answer 1

1. $\text{Size of each segment} = \frac{2^{16}}{8}=2^{13}$
   
   Let the size of page be $2^k$ bytes
   
   We need a page table entry for each page. For a segment of size $2^{13}$, number of pages required will be
   
   $2^{13-k}$ and so we need $2^{13-k}$ page table entries. Now, the size of these many entries must be less than or equal to the page size, for the page table of a segment to be requiring at most one page. So,
   
   $2^{13-k} \times 2 = 2^k$ (As a page table entry size is 2 bytes)
   
   $k=7$ bits
   
   So, $\text{ page size } = 2^7 =  128$ bytes
    
2. The TLB is placed after the segment table.
   
   Each segment will have $\frac{2^{13}}{2^9}=2^4$ page table entries
   
   So, all page table entries of a segment will reside in the cache and segment number will differentiate between page table entry of each segment in the TLB cache.
   
   $\text{Total segments}= 8 $
   
   Therefore $3$ bits of tag is required
    
3. $\text{Number of Pages for a segment} =\frac{2^{16}}{2^9} =2^7$
   $\text{Bits needed for page frame identification}$
   $\qquad = 7 \text{ bits} $
   $\qquad +1 \text{ valid bit} $
   $\qquad +3\text{ page protection bits}$
   $\qquad  +1 \text{ dirty bit}$
   $\qquad= 12 \text{ bits needed for a page table entry}$
   
   $\text{Size of each page table entry} = 2$ bytes $=16$ bits
   
   $\text{Number of bits left for aging} = 16-12 = 4$ bits

Comments

@Arjun SIr please check

---

@csegate2 then number of tag bits will be 4.

---

A TLB can have all the pages of a single segment or,many pages of difft segment?

Plz reply Sir

---

@arjun sir in the answer given is not conforming to the question, there are 8 segments, so no of pte bits will be  = log(2^13/2^9) + 5 = 9 bits?????? each segment has a seperate page table and each page table entry in that page table  requires 9 bits. why is he considering the entire segment as 1,there are 8 segments....

---

@resilient a, b, c are 3 separate questions. Which part are you referring to?

---

sir i am tlking about c, its given 8 segments so 2^16/8, each segment 2^13 B segmet size  i presume? and only after getting the segments i can page them to a page table i presume? so 2^13/2^9  ..so 4 bits for the entries plus the extra 5 bits, so total 9 bits.

---

In the question it is mentioned that VM is partitioned to 8 non overlapping segments. But what about physical memory? If that is also partitioned then what you telling is correct. But such a partition is never common nor mentioned in question. So as common in most system we must assume that each segment can address any part of physical memory.

---

sir in part a and part b we are assuming segment size as 2^ 13 but here 2^16, then in part a and part b also can we say each segment can address any part of physical memory? i am  a bit confused here sir.

---

What does a page table do?

It provides a mapping from "virtual address" to "physical address".

In parts a and b, we are interested in the number of entries in page table/TLB which should be there for every possible page (virtual). And we are given in the question that the virtual address space is divided into 8 non-overlapping segments and hence we didivded by 8.

In 3rd part, we are finding the no. of bits in each page table entry and this is based on the physical address space. We are not dividing by 8 because we are not told that physical address space is divided into 8.

---

Thank you sir for clearing this concept,now every thing is falling into place,crystal clear.

---

For part B, can I that the 16 bits in VAS would be divided as 

Tag	Cache Block	Block Offset
3	4 ( as there will be 16 entries)	9

And for part A, it will be as

Segment No	Segment Offset	Page Offset
3	6	7

Please suggest whether my understanding is correct?

---

But I think there is a problem with part c because  @danish has taken 7 bits for page identification but there no such field in page table entry but this field is present in TLB.

PTE= Bits Required for storing the  frame no to which particular page of the particular segment corresponding to this Page table is mapped + bits required for aging +1 valid bit+3 page protection bits+1 dirty bit==16 bit                                                                      

No of frames in physical memory=2¹⁶ / 2⁹ = 2⁷

So 7 bits are required to specify Frame no

PTE=7(for frame no)+1 valid bit+3 page protection bits+1 dirty bit+Bits for Aging=16 bits                                       7+1+3+1+Bits for aging=16           , So Bits for Aging=16-12=4 bits            

---

At last, someone has written things correctly.

Thankx @akb1115 for 

No of frames in physical memory=2¹⁶ / 2⁹ = 2⁷

So 7 bits are required to specify Frame no

In Selected answer  

Number of Pages for a segment=$2^{16}/2^{9}=2^{7}$

This line is written is wrong and also misleading, as no. of pages for segment would be $2^{13}/2^{9}=2^{4}$ 

Every segment will have sperate Page Table in Main Memory but a page table entry contains Frame Number, not a Page number, No. of pages will decide "How many entries will be present the Page table which will be 2^4".  

And Each entry in the table will contain a Frame Number i.e 7 bit and other stuff.

---

Hi , @Arjun sir you replied to @csegate2 comment but unfortunately it looks like he removed that comment

For part b

My doubt is "Is separate TLB is maintained for each segment" If No then your answer is correct

If yes , then answer would be.

Size of each page 512, and as PTE is 2 byte. No of entries 256

these 256 entries are mapped to 16 places of TLB

hence each  place in TLB is mapped to 16 entries. Hence Tag bit size is 4 bit

and PTE present in TLB will be 13 bit instead of 16 bit
Please correct me If My answer is wrong

---

There is only a single TLB in a system. (I think atleast upto the complexity of Computer Arch. we are studying for GATE)

---

Exactly this is making more sense please update that line, part a and b can be simply understood if you have clear knowledge of paging and segmentation . Please refer William stalling page 357. In part c catch is Physical space divided to achieve bits needed for frame nos as page table entry contains frame now + other bits + aging bits= 16.

So 7+5+ aging bits=16 further u can do the maths. Thanks for such beautiful answers.

---

I think saying that

The TLB is placed after the segment table.

is incorrect. Because such assumption will lower the efficiency that we might get from TLB. And that statement isn't t really needed to solve that question too. It is simply that there are $\frac{2^{16}}{2^{9}} = 2^{7} \, pages.$

That means 7bit address for pages. Address%16 will decide the set, and therefore last 4 bits will decide set and first 3 bits for TAG

---

Just wanted to clarify part B :

The proposed TLB will be capable of storing page table entries for 1616 recently referenced virtual pages, in a fast cache that will use the direct mapping scheme.

 

1. First, let me clarify that TLB is a “ translation look-aside buffer “ which is used to address translation from virtual to physical address.
2. Each page table of segments have 16-page table entries and the fast cache that is TLB has also 16 entries space and there are only 16 frames in memory which means that the entire page table of a segment can be stored at once in TLB. But there are more segments.
3. TLB uses Direct mapping here. And, tag bits in this TLB is used for finding the PTE stored in a particular entry in TLB belongs to which segment as there is only one TLB used for all segments.
4. So, tag bits only require identifying the segment number which requires 3 bits as there are 8 segments.
5. Extra tips: If TLB is not directly mapped or the number of PTE > 16 then tag bits will need extra bits to identify it. So, think about what if the associate mapping is used or what if there are more PTE???? 
6.  Any corrections are welcomed

 

---

@Ashish Kubade 

I think there is a small correction needed in your Part A diagram 

Reference: william stallings 

Answer 2

I’m just leaving the answer for part (b) & (c) , if someone is confused ( like I was): 

Part (b):

VA , is the address generated by the CPU , it is basically the address of the word of a program which is virtually addressed .

VAS ( Virtual address space ) = 16 bits . So, program size at max could be 2^16.

And , in part (b) it’s given that size of page = 512 Bytes.

Also , in the question it’s given that program is divided into equally 8 non-overlapping segments. So size of each segment = 2^16 / 8 = 2^13

Now , no. of pages in a segment = 2^13 / (page size) = 2^13 / 2^9 = 2^4

And no. of cache lines given are 16.

Also tying up with COA , where block numbers are used . Here page numbers will be used , as here no. of memory blocks are nothing but no. of total pages(because we are mapping pages to cache)

So , total no. of pages = No. of Segments * No. of pages in each segment. =  8 * 2^4 = 2^7

---

Directly Mapped Cache :

This means for every page there’s only one cache line to which it can go.

In case of directly mapped we can find tag bits two way :

1st Way : 

No. of memory blocks / no . of cache lines (COA terms)

Here it’s like : No. of pages / no. of cache lines

Therefore , Tag bits = log(2^7 / 2^4) = 3

2nd Way : 

We could’ve directly find  by : 

Tag bits = 16(Total bits) – 9 (page offset) – 4 (cache line 2^4)  = 3

We’re subtracting cache addressing bits because in directly cached , each page has only one cache line to go.

---

Fully Associative :

In fully associative any block can go to any cache line. So , here any page can go to any cache line.

Hence , to differentiate between pages we need to save whole page number in tag . 

Therefore , tag bits = log(Total number of pages) = log(2^7) = 7 

---

2-Way Set associative:

No. of sets = No . of cache line / no. of set per cache line = 16/2 = 8

Now here each page can map to at most 2 cache lines .

Here also we can do it 2 ways like we did previously in directly mapped:

1st Way :

Tag bits =log( No. of block / No. of sets) [COA terms]

So , here : Tag bits : = log(No. of pages / no. of sets) = log(2^7 / 2^3 ) = 4 bits

2nd Way :

Bits used in set = 3

Therefore :

Tag bits = Total – offset – set bits = 16 – 9 – 3 = 4

---

 

For part c)  :

They're asking the aging bits. And Page table entry(PTE) contains frame number and some additional bits.

So No. of frames = 2^16 / 2^9 = 2^7

Therefore aging bits = Total bits – frame number bits – additional bits = 16-7-1-3-1 = 4 bits.

Answer 3

1. $VAS=PAS=2^{16}B$
2. $8-Segments(equal-sized)$
3. $PTE=2B$

$a)\ \frac{2^{16}B}{segment\ size}=8$

$segment-size=2^{13}B$

minimum page size in bytes so that the page table for a segment requires at most one page to store it.

$\frac{2^{13}}{2^x}\times 2B=2^x$

$2^{14}=2^{2x}$

$x=14$

$page-size=2^7=128B$

$b)\ 16-bit\ VA$

$tag$	$line-offset$	$word-offset$
$3-Bits$	$4-bits$	$9-bits$

$c)$

$\frac{2^{16}B}{2^9B}=2^7$

7-bits for frame identification.

1 valid bit, 3 bits for page protection and 1 dirty bit.

Total$=7+1+3+1=12-bits$

$PTE=2B$

How many bits are available in page table entry for storing the aging information for the page?

$=\left\{(16-Bits)-(12-bits)\right\}=4-bits$

Comments

Is the TLB used for all the page tables at once? If it is used for only 1 Page table at a time(contents flushed for next use) then tag would be 1 since all page table entries can be put in tlb right?

---

there’s a typo in part a:

x=14

it is 2x = 14

Answer 4

My thought process for part (a):

Given:

          Virtual/Physical address space = $2^{16}$ B

          Memory is byte-addressable.

          No. of segments = $8$ $\implies$ Segment size = $\frac{2^{16}}{2^{3}} = 2^{13}$ memory words

          Size of each page table entry = $2$ B

 

Let each page contains $X$ memory words.

Then, one segment contains $\frac{2^{13}}{X}$ pages.

$\implies$ The corresponding page table for one segment will contain $\frac{2^{13}}{X}$ entries.

And, since, each entry of the PT is of $2$ B, the total size of the PT (for one segment) is $\left(2\cdot\frac{2^{13}}{X}\right)$ B

By the given constraint, 

$2\cdot\frac{2^{13}}{X}$ B = $X$ B

$\implies X^{2} = 2^{14} \implies X = 2^{7}$

Thus, Page size = $2^{7}$ x $1$ B = $2^{7}$ B = $128$ B