Question $5[20$ Marks$]$

$($a$)$ Conceptually, the heap area of an execution image is in between the Data and Stack areas. This is because we would like to keep the stack at the high end of the virtual address space. In practice, the heap area can be located after the stack area, as shown below.

In this case, brk $()/$sbrk $()$ would extend the heap area toward the right. Assume that the maximal heap size is $16$ KB $.$

Design an algorithm for this kind of brk $()/$ sbrk $().$

$($b$)$ Design an algorithm for memory compaction for our kernel in real mode x$86.$ The algorithm will be used by kmalloc $(),$ i$.$e$.$ if there is not enough memory and there are multiple holes, move all the process images to the high end of memory and try to allocate memory again. Note that, if a process image is moved, its saved segment registers in both the PROC and user mode stack must be adjusted to suit the new segments.