Extra Credit 3

Due: May 23, 2022
Points: 20

Remember, you must justify all your answers.

1. (20 points) Consider a memory in which contiguous segments S₁, …, S_n are placed strictly in their order of creation from one end of the store to the other. That is, when segment S_n+1 is being created, it is placed immediately after segment S_n even though some of the segments S₁, …, S_n 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 F ≥
   1−f⁄1+kf
   , where k =
   t⁄2s
   −1.

   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.

Matt Bishop Office: 2209 Watershed Sciences Phone: +1 (530) 752-8060 Email: mabishop@ucdavis.edu

ECS 150, Operating Systems Version of May 13, 2022 at 9:43PM

You can also obtain a PDF version of this.