Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.
share|improve this question
add comment

migrated from cstheory.stackexchange.com Nov 24 '12 at 8:56

This question came from our site for theoretical computer scientists and researchers in related fields.

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.