RD21: Memory Allocation II

Allocation Strategies, Alocation and Splitting, Freeing and Coalescing, Explicit Free List Intro

What are the three allocation strategies for an allocation request (when searching for a suitable free block)?

First fit, Next fit, and Best fit.

What is the “First fit” allocation strategy?

Searches the list from the beginning and returns the first free block that is large enough.

What is the “Next fit” allocation strategy?

Searches the list starting from where the last search finished and returns the first free block that is large enough (wrapping around at the end of the heap).

What is the “Best fit” allocation strategy?

Searches through the whole list and returns the free block that is “best” - large enough to fulfill the request, but minimal external fragmentation.

What’s the tradeoff of the allocation strategies?

Strategies that are completed quickly have worse fragmentation and vice versa.

Example of the allocation strategies:

Where would “First fit” allocate?

First fit would allocate after B1, since we search from the start of the heap.

Where would “Next fit” allocate?

Next fit would allocate after B5, since we search from the end of B5, the last fulfilled request.

Where would “Best fit” allocate?

Best fit would allocate after B3, since the available space is the closest fit to the requested payload size.

What’s the first step to fulfilling an allocation request?

1. Compute the necessary block size, based on the payload, metadata, and padding for alignment.

What’s the second step to fulfilling an allocation request?

Search for a suitable free block using the allocator’s allocation strategy. If found, continue. If not found, return NULL.

What’s the third step to fulfilling an allocation request?

Compare the necessary block size against the size of the chosen block. If equal, continue. If not, split off the excess and convert it into a new free block.

What’s the fourth step to fulfilling an allocation request?

Allocate the block and return the address of the beginning of the payload.

What are the two ways the allocator’s chosen alignment affects heap blocks?

1. The address of the beginning of the payload must be a multiple of the alignment size.

2. The total size of the block will be padded out to be a multiple of the alignment size.

What is the minimum block size determined by?

The larger requirements between allocated and free blocks in our allocator implementation.

How does minimum block size relate to the computation of the necessary block size (step 1) and splitting (step 3)?

1. The computed necessary block size will be padded out to the minimum block size.

3. If the remaining free space after splitting is less than the minimum block size, then it’s included as padding in the allocated block.

An example of Implicit Free List Block Size:

Referring to the Implicit Free List example, if the request was instead malloc(1) and the same free block was chosen, what would the header of the newly-allocated block be?

“16|1. The minimum block size is 16 bytes, so it will split the free block into an allocated block of size 16 followed by a free block of size 32.”

How can you simply free an allocated block?

Flip its is-allocated flag.

What’s a potential issue with flipping the is-allocated flag?

The block becomes unusable due to external fragmentation.

What is coalescing?

Coalescing is combining neighboring free blocks into a single, larger free block.

When do we coalesce?

We coalesce when we free an allocated block in order to maximize the allocator’s ability to fulfill future allocation requests.

Example of coalescing:

What is a footer block?

A copy of the header information except at the end of hte block so it can be read by the following block.

What do footer blocks allow us to do?

Footer blocks allows backward coalescing and traversal of the heap blocks in the reverse direction.

What are the header and footer collectively known as?

The boundary tags.

How many possible scenarios are there when freeing a block? Why?

4 possible scenarios based on whether the preceding and following blocks are free or allocated.

Examples of the 4 cases when freeing a block:

For an implicit free list with 16-byte alignment and 8-byte boundary tags (8 bytes each for the header and footer), what is the minimum block size (in bytes)?

“32. We need 16 bytes for the boundary tags, but a 0-byte payload is not practical, so we need more space. Since the alignment requirement is 16 bytes, we need pad out to the next multiple of 16, which is 32 bytes.”

What does an explicit free list do?

An explicit free list traverses its free blocks using a doubly-linked list data structure, done by adding next and prev pointers in the free blocks.

What blocks can fulfill an allocation request?

Free blocks!