Consider a memory in which contiguous segments S1, S2, …, Sn are placed in their order of creation from one end of the store to the other, as suggested by the following figure:

When segment Sn+1 is being created, it is placed immediately after segment Sn even though some of the segments S1, S2, …, Sn may already have been deleted. When the boundary between segments (in use or deleted) and the hole reaches the other end of the memory, the segments in use are compacted.

a. Show that the fraction of time F spent on compacting obeys the following inequality:

Where

s = average length of a segment, in words

t = average lifetime of a segment, in memory references

f = fraction of the memory that is unused under equilibrium conditions

b. Find F for f = 0.2, t = 1,000, and s = 50.

S2 Sn Hole fi where k= 1 " > 1 + kf 2s