8.2k views

For each of the four processes $P_1, P_2, P_3,$ and $P_4$. The total size in kilobytes $(KB)$ and the number of segments are given below.$$\small \begin{array}{|c|c|c|}\hline \textbf{Process} & \textbf{Total size (in KB)} & \textbf{Number of segments} \\\hline \text{P_1} & \text{195}& \text{4}\\\hline \text{P_2} & \text{254} & \text{5}\\\hline \text{P_3} & \text{45}& \text{3} \\\hline \text{P_4} & \text{364}& \text{8} \\\hline \end{array}$$The page size is $1$ $\text{KB}$. The size of an entry in the page table is $4$ $\text{bytes}$. The size of an entry in the segment table is $8$ $\text{bytes}$. The maximum size of a segment is $256$ $\text{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. $\text{P < S < T}$
2. $\text{S < P < T}$
3. $\text{S < T < P}$
4. $\text{T < S < P}$

edited | 8.2k views
0
So the answer is B or C?
+2

The storage overhead for the segmentation and paging method is T.

Means Segmented paging.

+14

I think we have to compare overhead of Two Level Paging, Segmentation and Segmented Paging.

Let us try to find find optimal answer for all three cases -

Case 1(Two Level Paging):

Assuming outer page tables are not page aligned. But inner one is page aligned.

For $P_{1}$

Size of entries in second level  = 195*4 B = 780 B ~= 1KB

Size of entries in first level  =  4 B

For $P_{2}$

Size of entries in second level  = 254*4 B = 1016 B ~= 1KB

Size of entries in first level  = 4 B

For $P_{3}$

Size of entries in second level  = 45*4 B = 180 B ~= 1 KB ( Because 1 Page is  enough)

Size of entries in first level  = 4 B

For $P_{4}$

Size of entries in second level  = 364*4 B = 1465 B ~= 2 KB

Size of entries in first level  =  8 B

So P = 5*1024 + 20  = 5140 B

Case 2 (Segmentation):

Assuming segment table is not page aligned -

S = (4+5+3+8)*8 = 160 B

Here i am still not sure why @Arjun sir not counting for all segment table ?

Case 3 (Segmented Paging):

Assuming page table is not page aligned.

For $P_{1}$

Size of segment table  = 4*8 B

Size of entries in page table entries corresponding to all segment  = 195*4 B = 780 B ~= 1KB (We can address in power of 2)

For $P_{2}$

Size of segment table  = 5*8 B

Size of entries in page table entries corresponding to all segment  = 254*4 B = 1016 B ~= 1KB

For $P_{3}$

Size of segment table  = 3*8 B

Size of entries in page table entries corresponding to all segment  = 45*4 B = 180 B ~= 0.25 KB

For $P_{4}$

Size of segment table  = 8*8 B

Size of entries in page table entries corresponding to all segment  = 364*4 B = 1465 B ~= 2 KB (We can address in power of 2)

So T = 160 + 4.25*1024 = 4512 B

Here also i am  still not sure, why is @Arjun sir just counting page table overhead corresponding to one segment ?(multiple segment may have small -2 part.)

Please correct if something is not proper.

+1
@chhotu

very good attempt

Put it as ans :)
+3

a:) For 2 level paging,in the outer most level you are taking,4B,4B,4B,8B at first level,i think it will consume one entire page?

b:)In segmented paging:

For P1:

Size of segment table  = 4*8 B .. this is fine

Size of entries in page table entries corresponding to all segment  = 195*4 B = 780 B ~= 1KB (We can address in power of 2)

Here i have doubt, how did you get 195 entries in page table? If there are 4 segments for a process as mentioned.And process taking 195KB only means ,process is not using segments completely because max. segment size is 256Kb and process is less than one segment size and it is using 4 segments. Here you have taken the process and divided it into pages$(195KB/1KB=195)$.

But what we need to do is take a segment and divide it into pages.Now we don't no how much a segment contains,upper bound gives segment of 256KB. Now $256KB/1KB$ =256 will be number of entries  in page table of segment and each entry 4B =256*4B for one table and since there are 4 segments and each has its own table so 256*4*4B=${2^{12}}$=4KB for process 1 and similarly for other we can find.Please see if am wrong anywhere.

+1

Hi @rahul sharma 5 ji,

a:) For 2 level paging,in the outer most level you are taking,4B,4B,4B,8B at first level,i think it will consume one entire page?

For one or Two entries why do you want to use whole page ?

Here i have doubt, how did you get 195 entries in page table?

I think even if  10000 segments are present then also we need only 195 entries only (Bcz of total size). Now 195 entries may be present in parts or entirely they may go in one segment because segment size is 256 KB.

0

For the first point i think you are right.They have not given that we need to use entire page table.

For second also,you are right,:p

Suppose 195KB is in 4 segments in a way as:50Kb,50KB,50KB,45KB. Now when we page the respective segments  we will get 195(50,50,50,45) entries only

1. SO you have considered page table overhead for all the segments in case 3,right?

2. In the case 2 you said:- Here i am still not sure why @Arjun sir not counting for all segment table ?But arjun sir did the same way you did(160B)

3.you case 1 and case 3 overhead has a difference of 700 B approx. Do you think the approximation of 1KB  that you used above everywhere can change the answer?

0

Hi @rahul sharma 5 ji,

1. SO you have considered page table overhead for all the segments in case 3,right?

YES

2. In the case 2 you said:- Here i am still not sure why @Arjun sir not counting for all segment table ?But arjun sir did the same way you did(160B)

That part is crossed in mentioned answer.

0

Actually when you  mark a answer as wrong.It puts a cross in answer. What i am saying that you answer is same as arjun sir for part (ii) and both of you have considered all the four segments.So why did you mention

Here i am still not sure why @Arjun sir not counting for all segment table ?

Is this reference to case(ii) or case(iii).Also ,your answer seems fine,you can convert it to answer.We can continue discussion below the answer if required.

0

you can convert it to answer

@rahul sharma 5 ji, Done.

PS: Conversion of Answer to Comment is possible but vice-versa is not possible. :(

+1
We need not have a separate page table for every segment?
+3
+1
In segmented paging

it is not required, that every segment should contain 1 page table. In fact if there is no need of page table, that segment could be empty

What I mean P1 has 4 segment, but only 1 segment in use, then only that segment will add a page table. Other 3 segment could be empty.

Also it could be non page aligned fashion
0

For P1

Size of entries in second level  = 195*4 B = 780 B ~= 1KB

Size of entries in first level  =  4 B

But still here first level also contain atleast 1 Page Table for that 1 entry=1024 B

Because P1 contains separate segment table for each pricess

So, P1 also must contain a separate page table for it

So total size for P1= 2KB+4*8 =2KB+32B

+1

@srestha  shouldn't each segment have a separate page table  in paged segmentation? thus 4 page table each of size 1KB for first process accounting overhead of 4KB and so on for each process.

0
@srestha  but what if for process all its segments are required to be in memory so all segment's page table must also be in memory hence we should consider worst case so each segment will and it separate page table.
0
Why we are adding 20 in case 1? 5 * 1024= 5120 what is that extra 20?
0
0
you have considered 45*4=180B as .25 KB in solving segmentation with paging but while doing pure paging you have approximated 180 B as 1024 B as one page.

Different assumption of page alignment will give both P>T or T>P.

what to do?
0

yes the approximations can change the answer for P and T. Don't you think its ambiguous?

0

@Arjun Sir

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

Ref: http://web.cs.wpi.edu/~cs3013/b02/week6-segmentation/week6-segmentation.html

$P_1$ uses $4$ segments $\rightarrow 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 $4$ page table of size $1KB$ for the $4$ segments. Similarly,

$P_2 - 40$ bytes and $5\;KB$
$P_3 - 24$ bytes and $3\;KB$
$P_4 - 64$ bytes and $8\;KB$.

Thus total overhead $= 160$ bytes $4\;KB+5\;KB+3\;KB+8\;KB = 20480+160 = 20640$ bytes.

So, $T = 20640 B$.

So, answer will be (B)- $S < P < T$.

by Veteran (431k points)
edited by
0
@rahul

ya. But in chhotu's answer , 1st level page table entry size for P4 is taken as 8B (ie total 1KB + 8B) and in arjun sir's answer its taken as 1KB (ie, total 2KB + 1KB).

which is the right one?
+1
Since it is not mentioned that we need to use entire page frame to fit the page.So we should take whatever memory is required.

Generally if question says what is page table size?What do we do?

Number of entries * PTE

So he has used the same thing

This answer is marked wrong.Now i am not sure which particular thing is wrong here.
0

Here https://gateoverflow.in/490/gate2008-67,in answer there is a statement

page table size need not be same as page size unless told so in the question

0

ya,right. thanks :-)

1 more doubt

for P3's page table size- in case1 he approximated 180 KB to 1KB but in case2, he took is as 180KB itself (0.25KB). He had mentioned the reason also- In case1, "outer page tables are not page aligned. but  inner one is page aligned" ..and in case 3, "page table is not page aligned"

Why so?

0
I am also getting confused now.:). When initially i attempted this question i have taken the page tables are page aligned but now looking at his explanation it also seems correct as i mentioned above.YOu should put your comment under his answer if you think that is write.He should be able to defend his answer and answer your queries.
0
ok.. ya, i was also trying to solve this by taking all page tables to be page aligned. but now i got confused.
0
+1
It is not correct. I'll correct it by tomorrow.
0
0
@Arjun sir what is correct explaination
0
@ Arjun sir is their is no use of number of segment given for each and every process while calculating the T.
0

I am having the same doubt as cseyg.

Another thing, since 2-level paging is done do we need to consider that during segmented paging also?

+1
One doubt I have here is that
Process $P_2$ has 5 segments, so 3 segment bits will be needed to index into the segment table

So, number of entries in segment table of process $P_2$ will be 8, but only 5 of them will be valid.

But still the size of the segment table for process $P_2$, should be $2^3*2^3B=64Bytes$
0
@ Arjun sir ,
For segmentation and paging for P4 process
Instead of  P4- 64 B+ 1KB it may be P4-64B+2KB beacuse P4 has 364 entities and max  segment entire is 256 so it can't fit in 1 page we required 2pages .
0

I have posted here...

https://gateoverflow.in/259633/doubt-paging

0
In segmented paging , paging will be done on each segment. Then the total number of page tables will be = number of segments ( in case of 1-level paging) . But in the answer only one page table is considered for a process. Why is that so?
0

@sushmita Have a look at the updated answer.

0

In process $p_{4}$, the inner level pagetable requires 1456B which is greater than one page size, i.e it can't be allocated in one page as well as memory.

then while summing up, why 1B + 2B is taken, because this 1456 B can't be loaded into memory, right???

0
@Arjun sir please can u clarify my doubt

In paging method only one level page table was enough to address all the pages of P1 (since 195 entries × 4 = 780 bytes < 1024 bytes). So why have u considered second level page table also. Shouldn't the overhead for paging of P1, P2 and P3 be 1KB?
0

@Arjun

Sir

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

because,

"upper bound gives segment of 256KB. Now 256KB/1KB =256 will be number of entries  in page table of segment"

right??

I think Answer is option (C).

I think we have to compare overhead of Two Level Paging, Segmentation and Segmented Paging.

Let us try to find find optimal answer for all three cases -

Case 1(Two Level Paging):

Assuming outer page tables are not page aligned. But inner one is page aligned.

For $P_{1}$

Size of entries in second level  = 195*4 B = 780 B ~= 1KB

Size of entries in first level  =  4 B

For $P_{2}$

Size of entries in second level  = 254*4 B = 1016 B ~= 1KB

Size of entries in first level  = 4 B

For $P_{3}$

Size of entries in second level  = 45*4 B = 180 B ~= 1 KB ( Because 1 Page is  enough)

Size of entries in first level  = 4 B

For $P_{4}$

Size of entries in second level  = 364*4 B = 1465 B ~= 2 KB

Size of entries in first level  =  8 B

So P = 5*1024 + 20  = 5140 B

Case 2 (Segmentation):

Assuming segment table is not page aligned -

S = (4+5+3+8)*8 = 160 B

Case 3 (Segmented Paging):

Assuming page table is not page aligned.

For $P_{1}$

Size of segment table  = 4*8 B

Size of entries in page table entries corresponding to all segment  = 195*4 B = 780 B ~= 1KB (We can address in power of 2)

For $P_{2}$

Size of segment table  = 5*8 B

Size of entries in page table entries corresponding to all segment  = 254*4 B = 1016 B ~= 1KB

For $P_{3}$

Size of segment table  = 3*8 B

Size of entries in page table entries corresponding to all segment  = 45*4 B = 180 B ~= 0.25 KB

For $P_{4}$

Size of segment table  = 8*8 B

Size of entries in page table entries corresponding to all segment  = 364*4 B = 1465 B ~= 2 KB (We can address in power of 2)

So T = 160 + 4.25*1024 = 4512 B

Please correct if something is not proper.

by Boss (13.7k points)
edited by
0

Also,mention the option which is satisfying the answer:)

See this => https://gateoverflow.in/43578/gate2003-79

Only 3 entries for first level page table but we considered entire page in first level

0

See this => https://gateoverflow.in/43578/gate2003-79

I think small difference is there. Do not you think so @rahul sharma 5 ji ?

0

Actually my main concern is if we consider outer page table as page aligned then the answer will change.As its 1KB size.And will be added to for all 4 processes

One more case:- https://gateoverflow.in/379/gate2013-52

Nothing is mentioned and we consider page aligned.I am not sure myself:(

0

@chhotu

for P3's page table size- in case1 you approximated 180 KB to 1KB but in case2, its taken as 180KB itself (0.25KB). The reason you've mentioned as- In case1, "outer page tables are not page aligned. but  inner one is page aligned" ..and in case 3, "page table is not page aligned"

Why so?

+1

@chhotu, your concept is 100% correct but still I have some objections with your answer.Let me put these as following points:(I am comparing only pure-paging and segmented paging)

1) first of all If I follow the same method as you did but I am doing exact calculation without any round-off.

Paging method: $(195*4+4) + (254*4+4)+(45*4+4)+(365*4+8)=3456$

Segmented paging:$(195*4+32) + (254*4+40)+(45*4+24)+(365*4+64)=3596$

okay then if my calculation is correct then it means segmented-Paging memory overhead is greater than paging overhead(I am not considering any kind of memory wastage due to internal/external fragmentation).

2) and if we consider that one page table will take one whole frame then in paging we will required total $9$ frames (including both outer and inner level PTs)

and in segmentation if we consider that PT of each segment will take entire frame then total $20$ segments so total $20$ frames and +1 segment table.

here also segmented paging has more memory overhead.

But still I feel taking size of outer PT as $4B$ is not logical. we should have given with more information about architecture of machine. see this

0

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)

by Loyal (7.8k points)
edited
+2
For segmentation with paging, there is no need of 2-level paging.
0
But if the architecture is for 2 level paging it will maintain it EVEN though there is just one page or even not needed !!
0
I don't think that is implied in question. Have you seen a similar question in any book where it is done like that?
0
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?
0
@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
0
+6
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 ......
+3
Even I have the same doubt as @bad_engineer . @Arjun sir please explain
+1
Someone should clear this doubt.Everyone is having the same doubt,
0
I did not understand the segmented paging part. Someone care to share some reliable resource for it ?
+1

Each Segment has a page table which means every program has multiple page tables.

I don't know why some people are not considering this fact.

https://www.javatpoint.com/os-segmented-paging

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)
by Junior (595 points)
+3
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.

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.
0
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??
–1
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.
0
@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.
0