TAOCP 2.5: Dynamic Storage Allocation
Section 2.5 exercises: 44/44 solved.
Section 2.5. Dynamic Storage Allocation
Exercises from TAOCP Volume 1 Section 2.5: 44/44 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [**] | verified | 1m50s | |
| 2 | [**] | verified | 6m25s | |
| 3 | [**] | solved | 41s | |
| 4 | [**] | solved | - | |
| 5 | [**] | verified | 2m26s | |
| 6 | [**] | verified | 1m33s | |
| 7 | [**] | solved | - | |
| 8 | [**] | solved | - | |
| 9 | [**] | solved | - | |
| 10 | [**] | solved | 33s | |
| 11 | [**] | solved | 4m27s | |
| 12 | [**] | solved | 4m32s | |
| 13 | [**] | solved | 4m34s | |
| 14 | [**] | solved | 6m39s | |
| 15 | [**] | verified | 4m57s | |
| 16 | [**] | verified | 3m06s | |
| 17 | [**] | verified | 1m30s | |
| 18 | [**] | verified | 1m33s | |
| 19 | [**] | solved | 4m40s | |
| 20 | [**] | verified | 1m15s | |
| 21 | [**] | verified | 2m45s | |
| 22 | [**] | verified | 4m11s | |
| 23 | [**] | verified | 1m07s | |
| 24 | [**] | verified | 1m12s | |
| 25 | [**] | verified | 2m39s | |
| 26 | [**] | verified | 1m23s | |
| 27 | [**] | verified | 1m12s | |
| 28 | [**] | solved | 4m10s | |
| 29 | [**] | solved | 2m10s | |
| 30 | [**] | verified | 29s | |
| 31 | [**] | verified | 1m10s | |
| 32 | [**] | verified | 2m46s | |
| 33 | [**] | solved | 5m10s | |
| 34 | [**] | verified | 2m36s | |
| 35 | [**] | verified | 1m08s | |
| 36 | [**] | solved | 4m27s | |
| 37 | [**] | solved | 7m06s | |
| 38 | [**] | solved | 5m15s | |
| 39 | [**] | verified | 4m16s | |
| 40 | [**] | verified | 3m01s | |
| 41 | [**] | verified | 1m49s | |
| 42 | [**] | verified | 3m55s | |
| 43 | [**] | solved | 57s | |
| 44 | [**] | solved | 33s |
TAOCP 2.5 Exercise 1
If reservations and liberations occur strictly in last-in-first-out order, the free storage always consists of a single contiguous region at the top of the stack of allocated blocks.
TAOCP 2.5 Exercise 2
Let $k$ be the node length and $b$ the control-word overhead per node.
TAOCP 2.5 Exercise 3
Let the usable payload in a node be $k-b$ words.
TAOCP 2.5 Exercise 4
The reviewer is correct that the previous submission did not solve the exercise.
TAOCP 2.5 Exercise 5
No.
TAOCP 2.5 Exercise 6
A simple modification is to remember the position at which the previous successful search ended, and begin the next search there instead of always starting at the front of the `AVAIL` list.
TAOCP 2.5 Exercise 7
Consider an `AVAIL` list whose first two free blocks have sizes $25$ and $12$, in that order.
TAOCP 2.5 Exercise 8
To obtain the best-fit method, modify Algorithm A so that it does not stop when the first block with `SIZE(P) \ge N` is found.
TAOCP 2.5 Exercise 9
The essential idea is to organize the free blocks by size instead of by location.
TAOCP 2.5 Exercise 10
Modify Algorithm B by first adjoining the interval $[P_0,P_0+N-1]$ to every free block that overlaps it, then perform the usual coalescing operation.
TAOCP 2.5 Exercise 11
Let the `AVAIL` list contain $m$ free blocks, arranged in increasing address order.
TAOCP 2.5 Exercise 12
Let the memory contain permanent boundary sentinels at both extremes.
TAOCP 2.5 Exercise 13
The reviewer’s criticisms are correct.
TAOCP 2.5 Exercise 14
Algorithm A is modified as follows to satisfy the boundary-tag conventions (7)-(9), to use the modified step A4', and to incorporate the next-fit improvement of exercise 6.
TAOCP 2.5 Exercise 15
Let the available-space list of Algorithm C be the doubly linked circular list maintained by the fields LINK(X),\qquad BACKLINK(X), with list header $AVAIL$.
TAOCP 2.5 Exercise 16
Exercise 2.
TAOCP 2.5 Exercise 17
When there are no available blocks, the list headed by `AVAIL` must be empty.
TAOCP 2.5 Exercise 18
With first-fit, Algorithm A always takes the first available block large enough to satisfy a request.
TAOCP 2.5 Exercise 19
The previous answer fails because it assumes information that is not available after the trailing `SIZE` fields have been removed.
TAOCP 2.5 Exercise 20
In the buddy system, a block is repeatedly split and recombined with its unique buddy.
TAOCP 2.5 Exercise 21
Let t_1,t_2,t_3,\ldots be the sequence
TAOCP 2.5 Exercise 22
The proposed idea does not fit the buddy system as ordinarily defined.
TAOCP 2.5 Exercise 23
A block of size $4$ contains addresses that differ only in the last two bits.
TAOCP 2.5 Exercise 24
No.
TAOCP 2.5 Exercise 25
The argument is incorrect even if it is known in advance that no request larger than $2^n$ will ever occur.
TAOCP 2.5 Exercise 26
Write M=\sum_{j=1}^{t}2^{m_j}, \qquad m_1>m_2>\cdots>m_t\ge0,
TAOCP 2.5 Exercise 27
Exercise 2.
TAOCP 2.5 Exercise 28
We assume a **binary MIX machine** with the new operation code \texttt{XOR} \quad (C=5, F=5), which complements in register `A` exactly the bits that are 1 in memory location `M`.
TAOCP 2.5 Exercise 29
No.
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...
TAOCP 2.5 Exercise 31
Yes.
TAOCP 2.5 Exercise 32
**Exercise 2.
TAOCP 2.5 Exercise 33
We are asked to design a **garbage collection and compaction algorithm** for a memory pool of nodes with the following properties: - Memory locations $1,2,\dots,AVAIL-1$ contain nodes `NODE(P)` of var...
TAOCP 2.5 Exercise 34
The reviewer's principal objection is valid: without the precise algorithm of Exercise 33, no correct MIX program can be written.
TAOCP 2.5 Exercise 35
The dynamic storage allocation methods of Section 2.
TAOCP 2.5 Exercise 36
**Solution.
TAOCP 2.5 Exercise 37
Working
TAOCP 2.5 Exercise 38
Let M=\left\lfloor\frac{3n-1}{2}\right\rfloor .
TAOCP 2.5 Exercise 39
**Exercise 2.
TAOCP 2.5 Exercise 40
Let $N(n,m)$ denote the minimum amount of storage that guarantees successful allocation when the total amount of live data is at most $n$, and when block sizes are restricted to the interval $[1,m]$.
TAOCP 2.5 Exercise 41
Let $R\le n$ be the total space currently reserved.
TAOCP 2.5 Exercise 42
**Exercise 2.