GATE CSE
First time here? Checkout the FAQ!
x
+14 votes
1.9k 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 (20.9k points)   | 1.9k views
So the answer is B or C?

3 Answers

+23 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 (295k points)  
Sir,

we can store segment table using set of registers or we need to store in main memory.

if we are storing in main memory,

i) we need to store segment table for each process in separate page to provide security.

2) even segment table size is very less ( eg. P1 size 32 bytes ) , we need to allocate for it one complete page 1 KB .

so over head will become 1 KB rather just 32 bytes for segment table for P1 , like this for others also.
@Arjun sir if P1 size is only 195KB and can have atmost 195 pages then how its page table has 256 entry for paging and segmentation case ,shouldn't this max segment size criteria should be consider only for P4
In segmentation with paging, won't there be a page table for each segment of a process?

Like if the first process has 4 segments:

ST size = 4*8 =32 bytes

Now each segment will be divided into pages, so each ST entry would refer to a separate page table. Hence there will be 4 page tables for this process occupying 4 KB (each page table being 1KB large)

Am I doing wrong in assuming the separate page table for each segment concept?
WHY WE NEED 4 DIFFERENT PAGE TABLE FOR SEGMENTATION AND PAGING .ALL THE SEGMENT TABLE IS 160B(OF ALL 4 PROCESSES) WHICH CAN BE KEPT IN 1 PAGE.

each segment will be paged separately so here (4+5+3+8)=20 page tables are required for paging of segments in segmented paging. This will make segmented paging memory overhead higher than all.

While paging, we need one page table for P1,P2 and P3 and 2 page tables for P4. What I have understood from the question is that these comprise of the second level and the first level page stores entries for all these 5 pages. So giving a total of 6 pages = 6KB.

But in sol. for every process 2 level paging is considered. I fail to undertand that. P1,P2 and P3 will never require 2 level paging! Somebody please explain
shalini in quetion he define 2 level page table used so we have to use it anyway either needed or not.

In previous year gate they explicitly said that how many level of page table used.
for P4 why do we need 3 page tables?
Because there are 2 second level page tables. A single second level page table can point to only 256 unique pages but we need 364 pages for P4.
In your answer for 2-level paging, you are saying that no. of pages of process p1 = 195, so 195 entries are required in the page table of 1st level. And so, PT1 Size = 195*4 = 780 bytes < Page Size(or frame size as u have assumed). So why will 2nd level be required at all ? Same doubt for process P2 and p3.

@arjun sir, @Habibkhan
@Arjun Sir or @Habibkhan, Could you please help with this query on this question -

Regarding the architecture of Segmentation with paging ( Segmented Paging) the segments are divided into pages and each segment will have its own page table. Let us assume we have 4 segments for process 1 namely CodeSeg, DataSeg, StackSeg, HeapSeg. CodeSeg is divided into pages and each entry in pagetable of CodeSeg will point to one of the page of CodeSegment. Now,   Each entry in the Segment table will point to the corresponding page table of that segment. For ex, One entry will point to Code Segment Page Table, other will point to Stack Segment Page table etc.

So now for P1, there are 4 segments so Segment table will contain 4 entries of 8B each = 32 Bytes

Since there are 4 segments and size of seg = 256KB and page size is 1 KB. Each segment will be divided into 256 pages and therefore is corresponding page table will contain 256 entries * 4 B = 1 KB

Thus for p1 overhead = 4 KB  + 32 B

For p2 overhead = 5KB + 40B

For p3 overhead = 3KB + 24B

Could you please help why have you taken only one page for each process in Segmented Paging architecture?
same way i did.then answer is B
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.

+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.3k 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,
–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 (443 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



Top Users Sep 2017
  1. Habibkhan

    7166 Points

  2. Warrior

    2640 Points

  3. Arjun

    2574 Points

  4. rishu_darkshadow

    2520 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,144 questions
33,726 answers
79,957 comments
31,116 users