# GATE - 2006 | OS | For each of the four processes P1, P2, P3 and P4. The total size in

## Question:

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.

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 ?

 A P < S < T B S < P < T C S < T < P D T < S < P

## Solution:

### Option (C) is Correct.

Case-1 (Two level paging):
For P1,
Page size is 1KB. So, no. of pages required for P1=195.

An entry in page table is of size 4 bytes and assuming an inner level page table takes the size of a page, we can have upto 256 entries in second level page table and we require only 195 for P1.

Thus only 1 second level page table is enough.

So, memory overhead = 1KB (for first level) + 1KB for second level = 2KB.

For P2 and P3 also, we get 2KB each and for P4 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×3+3 = 9KB. Thus P = 9KB.

Case-2 (For segmentation method):
P1 uses 4 segments → 4 entries in segment table = 4×8 = 32Bytes

Similarly, for P2, P3 and P4 we get 5×8, 3×8 and 8×8 Bytes respectively and the total overhead will be
32+40+24+64 = 160 Bytes

So, S = 160 Bytes

Case-3 (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 256KB and page size is 1KB and thus we require 256 entries in the page table.

So, total size of page table = 256 × 4 = 1024 Bytes (exactly one page size).

So, now for P1 we require 1 segment table of size 32 Bytes plus 1 page table of size 1KB.

Similarly,
P2 - 40 Bytes and 1 KB
P3 - 24 Bytes and 1 KB
P4 - 64 Bytes and 1KB

Thus, total overhead = 160 Bytes + 4KB = 4256 Bytes

So, T = 4256 Bytes

So, answer should be S < T < P.

Thank You