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 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 F
    1−f1+kf
    , where k =
    t2s
    −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.


UC Davis sigil
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.

Valid HTML 4.01 Transitional Built with BBEdit Built on a Macintosh