113 views
Suppose you have a computer system with a $48-bi$t logical address, page size of $16K$ and $4 bytes$ per page table entry. If we have a $48MB$ program such that the entire program and all necessary page tables are in memory. How much memory is used by program, including its page tables?

retagged | 113 views
0
48 MB + 12 KB = 48. 01172 MB ?
0
Please edit page size from 16K to 16KB.

+1 vote

Total memory requirements of 48 MB of program = 48 MB (program's usage in physical memory) + Page table entries corresponding to pages for 48 MB

Considering 1 level paging-

p | d = 34 | 14
#Pages required for 48 MB in logical space=48 MB/16K =3145.728 =~3146

Page table entries corresponding to 3KB pages=3146*4=12.28KB

Total=48MB +12.28KB=48.01MB

On the other side, there is a catch in question-- "all necessary page tables are in memory"

This means we should consider multilevel paging here -

Logical address' bits will be paged as- p1 | p2 | p3 | d = 10 | 12 | 12 | 14  [considering outermost page table fits in single page size]

A page table is stored in a page i.e 2^14, but since each entry requires 4 bytes, so effectively #pages in one table=2^14/4=2^12

We have 3146 pages, so total page tables needed in the third level=3146/2^12=0.76 =~1 page table

To point 1 page table of third level, #page table needed in the second level=1 page table

To point 1 page table of second level, #page table needed in the first or outermost level=1 page table

Total page tables needed=3

Total memory acquired by 3 page tables=3*2^14=48KB

Total memory needed by program=48MB+48KB=48.046MB

by Active (2.9k points)
edited
+1

** 3K pages..

0
Oh! misread that, but anyhow that won't cause much difference.
0
0

The reason is -

1. I have considered the best case of page tables i.e all the pages are available in consecutive entries of a page table.

2. I have assumed that the outermost page table fits completely in a single page.

Since nothing is mentioned in the question about that.

I tried doing this in worst case, as follows-

Logical address' bits will be paged as- p1 | p2 | p3 | p4 | d = 4 | 10 |10 |10 |14  [uniformly distributing page bits into 4 levels]

We have 3146 pages, so #page tables needed in the fourth level at max=3146 page table [scattering each page entry into different page table]

For 3146 page tables of the fourth level, #page tables needed the in third level at max=3146 page table

For 3146 page tables of the third level, #page tables needed the in the second level at max=3146 page table

Finally at first level, we can have #page tables atmost = 1 page table

Total=3146+3146+3146+1=9439

Memory required by 9439 page tables=9439*2^14=147.48MB

Total memory required by program=48+147.48=195.48MB

There is a slight difference in the answers but this is the best I could come up with. However unless mentioned in the question, we should use the best case.

0
48.01MB is right. They have calculated the maximum memory space of a page table which will be 2^16
0

But shouldn't 48.046MB would be more appropriate as they have said: "all necessary page tables are in memory".

Please justify, how did (3121)*2^16 is equivalent to 48.01 MB.

0
thanks
0

@Mamta , here Size of innermost page table = 48*26*22 B which is less than Page size 16 KB..so it will be fitted in one page..So why we need multilevel page tables ?  could u please explain ?

0

How did you get innermost page table = 48*26*22 B ?

0

@Mamta ,here program size = 48 MB = 48*220 B..So we divide it into pages..since page size = 16 KB = 214 B..So , number of pages = (48*220 ) / 214 = 48*26 ...now since page table entry size = 4 B...So, Page Table size = 48*26 * 4 B = 48*26*22 B ..Please correct me where am wrong.

+1

You are right but since ques asked for "How much memory is used by the program, including its page tables?" , we'll add 48 MB of program execution too, making a total of 48*220 + 48*26*22 B ~= 48.01 MB.

Back to your question-"Size of innermost page table = 48*26*22 B which is less than Page size 16 KB..so it will be fitted in one page.So why we need multilevel page tables ?"

Yes, it is less than a page size and the answer is perfect.On the other hand, I think the question is giving us hint to make it multilevel paging by saying "all necessary page tables are in memory." This is the reason why I have answered in both ways.