edited by
28,659 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

2 votes
2 votes

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.

–2 votes
–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)
Answer:

Related questions

38 votes
38 votes
3 answers
1
Ishrat Jahan asked Oct 31, 2014
10,366 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,631 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 ...