Processes and Segmentation

Question

The following problem was on my final and in Gate 2006, but I don't understand how to solve it:

Different methods of memory management have different overheads:

• 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 in the concurrent execution of the processes below?

(a) $P < S < T \hspace{2em}$
(b) $S < P < T\hspace{2em}$
(c) $S < T < P\hspace{2em}$
(d) $T < S < P$

Process    Total Size (in KB)    Number of segments  
 P1              195                    4  
 P2              254                    5  
 P3               45                    3  
 P4              364                    8  

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

Answer 1

I am guessing that overheads P, S, and T exclude per page/segment overheads and are per-process overheads (if they are per-system overheads, the adjustments are obvious), so the overhead of each process would be P + page_count * 4 bytes for paging, S + segment_count * 8 bytes for segmentation, and T + segment_count * 8 bytes + page_count * 4 bytes for segmentation and paging.

(The inclusion of a maximum segment size is confusing since insufficient information is provided to determine if any of the 8 segments in process P4 are larger than 256 KB, though at most one segment can be. Since the mean segment size is significantly less than the maximum allowed size, I just assume that no segment needs to use two segment table entries.)

It might help clarify the equations to substitute A < B < C with A = B + k1 = C + k1 + k2 (where k1 and k2 are greater than zero). It should then be straightforward to determine what values of k1 and k2 are needed for equality and so derive the conditions under which each memory management method has greater overhead (with negative values for k1 or k2, of course, being impossible).