Question$4$

The following problem concerns dynamic storage allocation.

Consider an allocator that uses an implicit free list. The layout of each allocated and free memory block

is as follows:

$31210$

Header $|$ Block Size $($bytes$)||$

$|||$

$||$

$||$

$||$

$||$

$||$

$||$

Footer $|$ Block Size $($bytes$)||$

$|||$

Each memory block, either allocated or free, has a size that is a multiple of eight bytes. Thus, only the $29$

higher order bits in the header and footer are needed to record block size, which includes the header and

footer. The usage of the remaining $3$ lower order bits is as follows:

bit $0$ indicates the use of the current block: $1$ for allocated, $0$ for free.

bit $1$ indicates the use of the previous adjacent block: $1$ for allocated, $0$ for free.

bit $2$ is unused and is always set to be $0.$