# Processes and Segmentation

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

## migrated from cstheory.stackexchange.comNov 24 '12 at 8:56

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

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

-

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. So, total overhead for their concurrent execution $= 2\times 3 + 3 = 9KB$.

Thus $P = 9KB$.

For Segmentation method

http://people.csail.mit.edu/rinard/osnotes/h15.html

$P_1$ uses 4 segments -> 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 1 page table of size 1KB. Similarly,

$P_2 -$ 40 bytes and 1KB $P_3 -$ 24 bytes and 1KB $P_4 -$ 64 bytes and 1KB.

Thus total overhead = 160 bytes + 4KB = 4096+160 = 4256 bytes.

So, $T = 4256 B$.

So, answer would be C- $S < T < P$.

http://gateoverflow.in/3600/gate2006-it_56

-