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.
Section 2.5: Dynamic Storage Allocation
Exercise 1. [**] [20] What simplifications can be made to the reservation and liberation algorithms of this section, if storage requests always appear in a "last-in-first-out" manner, that is, if no reserved block is freed until after all blocks that were reserved subsequently have already been freed?
Exercises
Verified: yes
Solve time: 1m50s
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. Consequently, the boundary-tag structure and the searching, splitting, and coalescing operations of the general dynamic-storage algorithms are unnecessary.
Maintain a single pointer $TOP$ to the first free location. To reserve a block of size $n$,
$TOP \leftarrow TOP+n.$
The block returned is the $n$ locations immediately preceding the new value of $TOP$.
To liberate a block of size $n$, the block being liberated is necessarily the most recently reserved block, so its storage is adjacent to the free region. Hence liberation is simply
$TOP \leftarrow TOP-n.$
Each reservation requires exactly one replacement, and each liberation requires exactly one replacement. No free-list links, boundary tags, searches, merges, or block subdivisions are needed. The storage allocator reduces to an ordinary stack discipline.