Written Assignment 5

Question 1

There are 3 different ways to keep track of free blocks:

Implicit Free List

In implicit free list implementation, any block in heap is linked using the block size stored in header. To find a free block, a pointer must traverse from prologue to epilogue by reading the block size in the header of each block and jump to the next block by adding the block size to the current address. The header also store the allocation status of the current block in lower bits (as the lower 4 bits are always 0 if the block size is multiple of 16) for the application to determine if the block is free.

Pros:

• simple to implement

• not required to occupy freed payload

• no need to store additional address data

Cons:

• really bad throughput because we are working with almost-full heap all the time and traverse takes $O(n)$ where $n$ is the number of all blocks.

Explicit Free List

In explicit free list implementation, instead of using block size, free block stores additional 2 address (in total of 16 byte in x86-64, since the client does not use the payload of freed block) in the location of payload. To find a free block, a pointer must traverse through the list by jumping to the next address indicated in the payload. All other operations, such as free and coalesce, must keep the this data structure of linked list.

Pros:

• simple to implement

• traverse takes $O(f)$ where $f$ is the number of free blocks.

Cons:

• required to occupy freed payload

• need to store additional address data

• more operations used to keep data structure of linked list

• increase the minimum size of free block, may lead to more fragmentation

• traverse takes $O(f)$ where $f$ is the number of free blocks. (could be more efficient)

Segregated Free List

Segregated free list is a set of explicit free list each dedicated to store the address of linked list of freed blocks of similar size. In some list of smaller block size, typically only one linked list is dedicated to one size of block. In some list of bigger block size, the size of blocks increases by power of two. To find a free block, the program must traverse the linked list of corresponding block size. If none of the free block has size bigger than required, the program must go to the linked list of bigger block size to traverse again, until it run out of freed blocks or find a free block that fits.

Pros: simple to implement

• potentially $O(log(f))$ where $f$ is the number of free blocks.

• first-fit search approximates a best-fit search of explicit free list as the number of linked-list increases

Cons:

• required to occupy freed payload

• need to store additional address data

• increase the minimum size of free block, may lead to more fragmentation

• more operations used to keep data structure of linked list

Question 2

See image below (perhaps next page)