Chapter 9, Problem 9.16HW

Program Plan Intro

Dynamic allocator:

Dynamic allocator keeps the heap as a group of several size blocks; each block is an attached portion of virtual memory which is allocated or free.

• An allocated block has been clearly kept for use by the application.
• A free block is offered to be allocated.

Two types of allocators:

1. 1. Explicit allocators
2. 2. Implicit allocators

Explicit allocators:

Explicit allocators need the application to explicitly free any allocated blocks.

Implicit allocators:

Implicit allocators is the method of automatically releasing vacant allocated blocks. This is also known as garbage collection.

Explicit free list:

In this method, a block contains one word header, payload and additional padding. The header encrypts the block size which contains header and padding; and also check the block is allocated or free.

• The heap can be organized doubly linked list by including predecessor and successor pointer in each free block.
• This method reduces the allocation time when compared to implicit free list.
• If the arrangement is single-word, the block size is constantly a multiple of “4” and the low-order bits of the block size are always zero.
• If the arrangement is double-word, the block size is constantly a multiple of “8” and the low-order bits of the block size are always zero.