The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
2.4k views

For each of the four processes P1, P2, P3 and P4. The total size in kilobytes (KB) and the number of segments are given below.

Process Total size (in KB) Number of segments
P1 195 4
P2 254 5
P3 45 3
P4 364 8

 

The page size is 1 KB. The size of an entry in the page table is 4 bytes. The size of an entry in the segment table is 8 bytes. The maximum size of a segment is 256 KB. The paging method for memory management uses two-level paging, and its storage overhead is P. The storage overhead for the segmentation method is S. The storage overhead for the segmentation and paging method is T. What is the relation among the overheads for the different methods of memory management in the concurrent execution of the above four processes ?

  1. P < S < T
  2. S < P < T
  3. S < T < P
  4. T < S < P
asked in Operating System by Veteran (21.5k points) | 2.4k views
So the answer is B or C?

3 Answers

+30 votes
For 2-level paging.

Page size is 1KB. So, no. of pages required for $P_1$ = 195. An entry in page table is of size 4 bytes and assuming an inner level page table takes the size of a page (this information is not given in question), we can have up to 256 entries in a second level page table and we require only 195 for $P_1$. Thus only 1 second level page table is enough. So, memory overhead = 1KB (for first level) (again assumed as page size as not explicitly told in question) + 1KB for second level = 2KB.

For $P_2$ and $P_3$ also, we get 2KB each and for $P_4$ we get 1 + 2 = 3KB as it requires 1 first level page table and 2 second level page tables (364 > 256). So, total overhead for their concurrent execution $= 2\times 3 + 3 = 9KB$.  

Thus $P = 9KB$.

For Segmentation method

http://people.csail.mit.edu/rinard/osnotes/h15.html

$P_1$ uses 4 segments -> 4 entries in segment table $= 4 \times 8 = 32$ bytes.

Similarly, for $P_2,P_3$ and $P_4$ we get $5 \times 8$, $3 \times 8$ and $8 \times 8$ bytes respectively and the total overhead will be $32 + 40 + 24 + 64 = 160$ bytes.

So, $S = 160B$.

For Segmentation with Paging

Here we segment first and then page. So, we need the page table size. We are given maximum size of a segment is 256 KB and page size is 1KB and thus we require 256 entries in the page table. So, total size of page table $ = 256 \times 4 = 1024$ bytes (exactly 1 page size).

So, now for $P_1$ we require 1 segment table of size 32 bytes plus 1 page table of size 1KB. Similarly,

$P_2 - $ 40 bytes and 1KB
$P_3 - $ 24 bytes and 1KB
$P_4 - $ 64 bytes and 1KB.

Thus total overhead = 160 bytes + 4KB = 4096+160 = 4256 bytes.  

So, $T = 4256 B$.

So, answer would be C- $S < T < P$.
answered by Veteran (327k points)
In simple paging we consider 2 levels but in segmentation with paging we consider single level.Why is there inconsistency in assumption?

Nice explanation Arju sir.

Just one doubt:-

For 2 level paging scheme 

So, no. of pages required for P1= 195.

This P1 is inner page table right? Because if we page Process p1 it will result in 195 entries at the second level page table and these can be easily accomodated in one frame ,but for first level we need just one enty pointing to second level

for process P1 since it has got 4 segments each of max size 256 KB, hence 256 entries are required for it, but since it contain 4 segments we must need 4 pages for it?? Why have u taken only 1 page??

 

Similarly 1 segment table will need complete 1 page overhead just like page table, why have u not considered that?

Please resolve these doubts. Its creating confusion.
@sushmita For your second query

Segmentation is done with the help of hardware meaning the segmentation table is independent of page table and so for a segment table, we do not need the size of a page.

For the first part, I'll explain it in detail in the answer. Your doubt should be correct.
thanks sir. Segmentation part is clear. But i am still unclear about the segmented paging part??

"Here we segment first and then page. So, we need the page table size. We are given maximum size of a segment is 256 KB and page size is 1KB and thus we require 256 entries in the page table. So, total size of page table =256×4=1024=256×4=1024 bytes (exactly 1 page size)."

Here above, you said one page table is required for one segment.

"So, now for P1P1 we require 1 segment table of size 32 bytes plus 1 page table of size 1KB. Similarly,

P2−P2− 40 bytes and 1KB
P3−P3− 24 bytes and 1KB
P4−P4− 64 bytes and 1KB."


If you see the question, P1 has 4 segments -> 4 page tables required = 4kB

P2 has P1 has 5 segments -> 5 page tables required = 5kB

P3 has 3 segments -> 3 page tables required = 3kB

P4 has 8 segments -> 8 page tables required = 8kB

Thus total overhead = 160 bytes + 20KB = 20kB

So the answer should be B) S < P < T

Please correct me if I am wrong.

we can have up to 256 entries in a second level page table 

Rishi yadav how?

@set2018

page size=1K B

PTE size = 4B

Max. no. of pages=1K/4 =2^8

Assuming an inner level page table takes the size of a page (this information is not given in question),

@Arjun sir 

Segmentation is done with the help of hardware meaning the segmentation table is independent of page table and so for a segment table, we do not need the size of a page. 

This makes sense to me in case of segmentation where the logical and physical address space is not divided into pages or frames  we just have segments.

But , what about segmented paging ? here, logical address space is segments but physical address space is frames i.e. Main memory is divided in frames and if the segment table is stored in main memory , it should be stored in the form of frames or we could say pages here.

So, in case of segmented paging we should need 1KB page each for storing 1 segment table.

@Arjun Sir please solve these doubt that everyone is facing

1.Is it required that there be a page table for every segment ?

2.If so would those page table require a different page for storage ?

3.If the answer to the above questions is "Yes" then would the answer be B or would it still be C. If so then how ?
+2 votes

Answer is (B)

According to me P=9 KB ,S = 4 KB, T =44 KB

Note that although in paging we have just one page at INNER level ,we need atleast one page at OUTER level to make this entry corresponding to inner page just because architecture is of Two Level Paging.

Each process's segment table needs just one page ,Therefore for all four process we need 4 KB. S=4KB

Now segmentation with paging works as follows:

First make a segment table: This will be same as in Segmentation . So each process need just 1KB for its ST.

After that each segment is divided into pages AND for each segment of a process we need a separate TWO LEVEL PAGING.

Since each segment is max of 256KB ,it has 256 pages of 1KB each. Inner PT has 256 entries each of 4 Bytes requiring 1024 Bytes or 1 KB. So just one page at this level.To store this page table entry corresponding to inner PT page ONLY one outer level PT is required. To sum up, for one segment ,we need 2 pages or 2 KB for Page Tables. P1 has 4 segments .Therefore 8 KB plus 1KB for Segment Table =9KB

P2 has 5 segments --> 11KB (you can verify)

P3 has 3 segments---> 6 KB+1 KB =7 KB

P4 has 8 segments  --> 16 KB + 1 KB =17 KB

therefore segmentation with paging require 9+11+7+17 KB = 44 KB

So , P= 9 KB, S= 4 KB ,  T= 44 KB  (S< P< T)

answered by Boss (7.4k points)
edited by
For segmentation with paging, there is no need of 2-level paging.
But if the architecture is for 2 level paging it will maintain it EVEN though there is just one page or even not needed !!
I don't think that is implied in question. Have you seen a similar question in any book where it is done like that?
Ya arjun sir these all 3 methods are independent. Its also written in last line 3 different methods.
 Can u plz explain overhead of segmentation + paging?
@arjun sir,

process p1 has 4 segments : each segment has 49 KB (approx) => 49 pages

each segment has its own page table with 49 * 4 =19 6 bytes which fits in single page.

as minimum size that we can allocate is a page. so  5 pages overhead

1 for segment table + 4 for page tables for each segment.

proceeding like this total overhead will be 24 KB for segmentation with paging.

sir , please correct if anything is wrong
I'm not getting your comment. Can you see my answer?
Segmented with Paging:

We require page table for each Segment of a process and Page tables and Segment table are overhead :

P1 : Page table Size is : 1 KB

Why We are not multiplying it with 4 as we have 4 page tables for 4 segments????

Similarly for P2, P3 and P4 ......
Even I have the same doubt as @bad_engineer . @Arjun sir please explain
Someone should clear this doubt.Everyone is having the same doubt,
I did not understand the segmented paging part. Someone care to share some reliable resource for it ?
–2 votes
I think option B is right answer, and i think there was a mistake in calculating the storage overhead for segmentation+paging portion. For rest calculations it is correct. So,P=9KB, S=4KB
First realize that in segmentation we divide a process into segments and we create page table for each segment of the process. Here as it is mentioned that 2 level paging has been used,so here it goes like this:
Note:- First see that max segment size can be=256KB so a segment can have max=256 pages, for 256 pages we need a page table of size=(256*4)=1024B=1KB=page size, so we need max 1 page to store the page table of a segment,but as it is 2 level paging we need atleast 2 pages i.e 2KB to store the page table of a segment.

for P1, no of segments=4,for each segment of the process we need a separate TWO LEVEL PAGING.so (4*2)KB=8KB for page table of P1 and for segment table we need another page,so another 1KB..so for P1 total 9KB

for P2, no of segments=5,for each segment of the process we need a separate TWO LEVEL PAGING.so (5*2)KB=10KB for page table of P2 and for segment table we need another page,so another 1KB..so for P2 total 11KB

for P3, no of segments=3,for each segment of the process we need a separate TWO LEVEL PAGING.so (3*2)KB=6KB for page table of P3 and for segment table we need another page,so another 1KB..so for P3 total 7KB

for P4, no of segments=8,for each segment of the process we need a separate TWO LEVEL PAGING.so (8*2)KB=16KB for page table of P4 and for segment table we need another page,so another 1KB..so for P4 total 17KB
So total, T=(9+11+7+17)KB=44KB

So, S<P<T option (B)
answered by Junior (517 points)
people over here are arguing that overhead for segmentation + paging should be 1KB per page and hence 4KB for P1, 5KB for P2 and so on. but here i am just trying to explain that why arjun sir's computation for segmentation+paging portion is right.

question asks that "memory overhead during execution" -> that is how much memory we have to access to get data (or anything).

then in segmentation+paging method, it is true that for every segment we need one page table size. so total pages needed = (no of segments * page table size) +  1 page for segmentation table. BUT this is OVERHEAD for STORAGE; NOT OVERHEAD for EXECUTION.

for execution after we searched whole segment table we just need to access a single page table of related segment.

that is why overhead for seg+paging have 1KB page table overhead only. and this makes option C right.

this is what intuition i got.
In segmentation+paging scheme,logical address=(segment no +Page no+page offset) So, you first access segment table by using the field "segment no",if there are k segments in a process there will be k entries in that segment table of that process. Now each corresponding entry of the segment table gives us the frame no./page no.of the page table of that respective segment of the process. Taking that frame no we go to that particular frame of the MM where we can get the total Page table of that particular segment of the process. Now using "page no" field of logical address we go to particular entry of that page table which we have got in our last step and get the frame no of the MM where that actual page of the process resides. And lastly, by using "page offset" we get the required byte/word of the process.
So, we need storage overhead for [a segmentation table(requires 1 page)+page tables for all the segments of the process]
Now got the idea??
yes that is what total storage overhead is. i did mistake there. so i added 1 more page for segment table in overhead. but if we talk about execution overhead than my point of view is proper. right? which tells how segmentation+paging overhead has 1 KB only rather than multiple pages.
@Sheshang, As per the logic you followed, our calculation for only paging method is wrong as we have calculated whole storage overhead not just execution overhead in paging.
Answer is B or C
Answer:

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

29,157 questions
36,984 answers
92,161 comments
34,824 users