$(30)$ Consider a memory allocator with the following properties:

Allocations are $4-$byte aligned, for each memory block, either allocated or free

Allocator uses an implicit free list

Allocator uses immediate coalescing, that is$,$ adjacent free blocks are merged immediately

each time a block is freed

To find a free block, first fit method is used

The allocated and free blocks both have header and footer

The header and footer use:

the higher order $14$ bits to record block size $($block size includes the header and

footer$)$

the lower order $2$ bits to record allocation information:

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

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

If the heap starts at memory address $0b000,$ show the contents of heap after each of the

following requests. Note that the addresses grow from top down.

i$.$ Draw the heap

ii$.$ Indicate the memory location that $p1,p2,$ and $p3$ points at$.$

iii. Indicate each memory block either allocated or free.

iv$.$ Indicate the blocks that contain header and footer.

v$.$ Give the contents of header and footer for each block $($in hexadecimal$).$ Don't forget to

indicate the change in header and footer when there is a need.

a$)p1=$malloc$(3)$

b$)p2=$malloc$(5)$

c$)$ free $($p$1)$

d$)p3=$malloc$(9)$

e$)$ free $(p2)$

f$)p4=$ malloc $(4)$

Show all your work and briefly explain your answer! Your heap will be like the following, and you will draw the heap $5$ times $($i$.$e$.,$ for each request$).$ You

can insert more rows as you need.

Here is an example that shows what you will include in your answer. Note that this example is for a

totally different allocator.