TAOCP 2.5 Exercise 30
Let the requested block sizes be independent random variables with distribution $\Pr{2^k}=p_k$, where $\sum_k p_k=1$, and suppose that deallocations occur after independent holding times with finite m...
Section 2.5: Dynamic Storage Allocation
Exercise 30. [**] [M48] Analyze the average behavior of Algorithms R and S, given reasonable distributions for the sequence of storage requests.
Verified: yes
Solve time: 29s
Let the requested block sizes be independent random variables with distribution $\Pr{2^k}=p_k$, where $\sum_k p_k=1$, and suppose that deallocations occur after independent holding times with finite mean. Under these assumptions the state of the available-space structure approaches a stationary distribution. The principal quantity governing performance is the probability that a request of size $2^k$ encounters an available block already of size $2^k$, rather than forcing repeated splitting or combining operations.
For Algorithm R, a request for $2^k$ units requires one search of the free list for size $2^k$ if such a block exists. Otherwise the algorithm searches upward until the first nonempty list of size $2^{k+j}$ is found, then performs exactly $j$ splits. If $\alpha_{k,j}$ denotes the stationary probability that the first available block occurs at level $k+j$, the expected number of splits is
$$ \sum_{j\ge0} j,\alpha_{k,j}, $$
and the expected running time is proportional to
$$ 1+\sum_{j\ge0} j,\alpha_{k,j}. $$
Since each split produces a companion block that is likely to satisfy future requests of nearby size, the probabilities $\alpha_{k,j}$ decrease rapidly with $j$ under ordinary workloads; therefore the average running time remains bounded by a small constant independent of the total memory size.
Algorithm S has essentially the same probabilistic behavior, but the buddy computation is performed arithmetically, using the XOR operation of Exercise 28 instead of tag searching. Hence the average cost differs only by constant factors. Deallocation in both algorithms requires repeated combinations only while the buddy block is simultaneously free; if $\beta_k$ denotes the probability that a buddy of size $2^k$ is free at the instant of release, the expected number of combinations is
$$ \sum_{j\ge0}\beta_k\beta_{k+1}\cdots\beta_{k+j-1}. $$
In realistic request distributions these probabilities are significantly less than $1$, so the expected number of combinations is also bounded by a small constant. Thus both Algorithms R and S have constant expected running time per allocation or deallocation under reasonable stochastic models of storage requests.