The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
103 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?
in Operating System by (55 points)
retagged by | 103 views
0
48 MB + 12 KB = 48. 01172 MB ?
0
Please edit page size from 16K to 16KB.

1 Answer

+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.8k points)
edited by
+1

** 3K pages..

0
Oh! misread that, but anyhow that won't cause much difference.
0
but answer given is 2^16(3121)
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
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.

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,093 questions
55,333 answers
190,852 comments
86,257 users