edited by
28,645 views
68 votes
68 votes

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 by

6 Answers

Best answer
112 votes
112 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

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

selected by
14 votes
14 votes

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. 

edited by
7 votes
7 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)

edited by
3 votes
3 votes

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

Answer:

Related questions

38 votes
38 votes
3 answers
1
Ishrat Jahan asked Oct 31, 2014
10,362 views
When multiplicand $Y$ is multiplied by multiplier $X = x_{n - 1}x_{n-2} \dots x_0$ using bit-pair recoding in Booth's algorithm, partial products are generated according ...
30 votes
30 votes
4 answers
4
Ishrat Jahan asked Oct 31, 2014
12,619 views
The arrival time, priority, and duration of the CPU and I/O bursts for each of three processes $P_1, P_2 $ and $P_3$ are given in the table below. Each process has a CPU ...