GATE IT 2006 | Question: 56

Question

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?

• A. $\text{P < S < T}$
• B. $\text{S < P < T}$
• C. $\text{S < T < P}$
• D. $\text{T < S < P}$

Comments

Can refer this for easy understanding, 

---

• might be helpful

---

nice explaination with good and attractive handwriting

Answer 1

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$.

Comments

I am not getting one thing for P part, considering process P1 as example, the size of Page Table 1 turns out to be 195*4B = 780B ≈ 1kB which is ≤ Page/Frame Size, so if just 1 PT was sufficient enough to hold the entries of entire process why do we need to perfom one more paging, for 2nd level?

---

I think here page table entry(4B) is not used in the segementation with paging method.

Instead they assumed 1 Byte for page table entry. If we take PTE as 4B then i'm getting 20 pages(20KB) to store paging on segmentation tables. Still answer remains same.

---

@ASV simply cause it's given in question :)

 

Answer 2

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. 

Comments

@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?

---

@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

---

add this to answer..

Answer 3

there is very simple and logical answer to thiis – 

in paging we have page table for all process that we know are too big and we have to use multilevel paging

in segmentation we have segment table of a process in which we have entries of total segments the process is divided in so maximum a process will be divided in 10 or 20 segment which not that much in compare to page entry so segment table overhead is much less than page table 

in segment paging we have segments which are divided into pages each segment have its own page table then we have segment table which is again divided into pages and we have page table of segment table, so ultimately we have segment table overhead as well as page table overhead. means the answer will be

2-S < P < T

Comments

This is logical and seems correct and I guess this was meant to be solved without using pen.

---

Very apt answer without any confusion and pretty much time saving.

Answer 4

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)

Comments

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 ?

---

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.

Which make Answer as B

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

Answer 5

This question confused me for a long time. Now I am going to explain what I have learned about how to solve this question..

---

Page table entry size = 4B

Segment table entry size = 8B

Page table size = 1KB

Segment table size = 256KB

---

→ CASE1 : (Paging)

P1 : → 195KB/1 KB = 195 entries ;

       → Maximum number of entries allowed in page table = 1K/4 = 256 entries.

       → But we need 195 only, so we need 1KB(level1) and 1KB(level2) or 1+1 = 2KB page table overhead for P1.

Similarly for P2, and P3 we need 2KB and for P4 we need 3 KB.

So, P = 2 + 2 + 2 + 3 = 9KB

---

→ CASE2 : (Segmentation)

P1 : → we have 4 segments here and each one needs 8B. implies we need 4*8B of overhead in the main segment table for this process.

Similarly, we need 5*8, 3*8, and 8*8 for other processes.

So, S = 160B 

---

→ CASE3 : (Segmentation + Paging)

P1 : → 4 segements each of size 256KB, 

→ 256KB/1KB = 256 entries we want & we have 1KB/4B = 256(max entries in Page table).

→ So, we need a 1-page table per segment.

layout : 

Process → Segmentation → Paging

195KB → break it into 4 segments (4 * 256KB) → 4* 1KB

So, T = 4KB(P1) + 5KB(P2) + 3KB(P3) + 8KB(P4) + (4*8 + 5*8 + 3*8 + 8*8)(Segment table size) = 20640B

---

Hence we can conclude that (S < P < T), Option B.

Answer 6

Let's break down the problem step by step to calculate the storage overheads for:

• Paging only (P)

• Segmentation only (S)

• Segmentation + Paging (T)

---

🔹 Given:

• Page size = 1 KB

• Size of entry in page table = 4 bytes

• Size of entry in segment table = 8 bytes

• Max segment size = 256 KB

We are given sizes and number of segments for 4 processes.

---

 Overhead Calculations

---

1. Paging only (P):

Each process size is divided into 1 KB pages, so:

Overhead=Number of pages×4 bytes

Let’s compute:

• P₁ = 195 KB → 195 pages → 195 * 4 = 780 bytes

• P₂ = 254 KB → 254 pages → 254 * 4 = 1016 bytes

• P₃ = 45 KB → 45 pages → 45 * 4 = 180 bytes

• P₄ = 364 KB → 364 pages → 364 * 4 = 1456 bytes

Total P = 780 + 1016 + 180 + 1456 = 3432 bytes

---

2. Segmentation only (S):

Overhead = No. of segments × 8 bytes

• P₁ = 4 segments → 4 * 8 = 32 bytes

• P₂ = 5 segments → 5 * 8 = 40 bytes

• P₃ = 3 segments → 3 * 8 = 24 bytes

• P₄ = 8 segments → 8 * 8 = 64 bytes

Total S = 32 + 40 + 24 + 64 = 160 bytes

---

3. Segmentation + Paging (T):

Each segment is paged → So for each segment:

• One segment table entry = 8 bytes

• Number of pages per segment = (segment size in KB / 1 KB)

• Max segment size = 256 KB ⇒ Worst case: each segment = 256 pages = 256 * 4 = 1024 bytes per segment in page table.

Steps:

1. First, divide total process size by number of segments to get average segment size.

2. Then compute pages per segment → Page table entries → Overhead.

Let's compute for each process:

P₁: 195 KB, 4 segments

• Avg seg size = 195 / 4 = 48.75 KB → ~49 pages → 49 * 4 = 196 bytes

• Per segment: 8 + 196 = 204 bytes

• Total: 4 * 204 = 816 bytes

P₂: 254 KB, 5 segments

• 254 / 5 = 50.8 KB → ~51 pages → 51 * 4 = 204 bytes

• Per segment: 8 + 204 = 212 bytes

• Total: 5 * 212 = 1060 bytes

P₃: 45 KB, 3 segments

• 15 KB each → 15 pages → 15 * 4 = 60 bytes

• Per segment: 8 + 60 = 68 bytes

• Total: 3 * 68 = 204 bytes

P₄: 364 KB, 8 segments

• 45.5 KB each → 46 pages → 46 * 4 = 184 bytes

• Per segment: 8 + 184 = 192 bytes

• Total: 8 * 192 = 1536 bytes

Total T = 816 + 1060 + 204 + 1536 = 3616 bytes

---

 Final Overhead Comparison:

• P = 3432 bytes

• S = 160 bytes

• T = 3616 bytes

So the relation is:

S<P<T