The Gateway to Computer Science Excellence

0 votes

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?

+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

0

Please check updated answer above, but even that doesn't match with your answer.

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

Your answer was 3121 *2^16=195.06MB

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

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

@Mamta , here Size of innermost page table = 48*2^{6}*2^{2} 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

@Mamta ,here program size = 48 MB = 48*2^{20} B..So we divide it into pages..since page size = 16 KB = 2^{14} B..So , number of pages = (48*2^{20} ) / 2^{14} = 48*2^{6} ...now since page table entry size = 4 B...So, Page Table size = 48*2^{6} * 4 B = 48*2^{6}*2^{2} 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*2^{20 }+ 48*2^{6}*2^{2} B ~= 48.01 MB.

Back to your question-"Size of innermost page table = 48*2^{6}*2^{2} 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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,729 answers

199,453 comments

107,868 users