edited by
25,127 views
46 votes
46 votes

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.

edited by

4 Answers

Best answer
40 votes
40 votes
  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
edited by
5 votes
5 votes

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.

edited by
4 votes
4 votes
  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$

1 votes
1 votes

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

edited by

Related questions

36 votes
36 votes
3 answers
1
Kathleen asked Sep 23, 2014
12,637 views
A multi-user, multi-processing operating system cannot be implemented on hardware that does not supportAddress translationDMA for disk transferAt least two modes of CPU e...
41 votes
41 votes
4 answers
2
18 votes
18 votes
2 answers
3
Kathleen asked Sep 23, 2014
6,925 views
Listed below are some operating system abstractions (in the left column) and the hardware components (in the right column)$$\small \begin{array}{cl|cl}\hline \text{(A)}& ...