Extra Credit 3
Due: May 23, 2022
Remember, you must justify all your answers.
- (20 points) Consider a memory in which contiguous segments S1, …, Sn are placed strictly in their order of creation from one end of the store to the other. That is, when segment Sn+1 is being created, it is placed immediately after segment Sn even though some of the segments S1, …, Sn may have already been deleted. When the boundary between segments (in use or deleted) and the hole reaches the other end of the store, the segments in use are compacted. Let s and t denote the average length and lifetime of a segment (measured in words and memory references). Let f denote the fraction of the memory which is unused under equilibrium conditions.
Show that the fraction of time F spent on compacting is constrained by
1−f⁄1+kf, where k =
Hint: Find the average speed at which the boundary crosses the memory and assume that copying of a single word requires at least two memory references.