Simulators

Explicit Free List

In an explicit free list, you store explicit references to the next and previous free blocks as well, which is where the "explicit" in the name comes from, as you keep explicit references to other free blocks. In contrast to an implicit free list, this means you can iterate over just the free blocks, skipping the allocated blocks entirely.

To house this additional data, you need to allocate a minimum of 16 bytes (4 for each of the header, prev, next, and footer words) instead of the 8 needed for the implicit free list.

• The simplest way is to bump both the minimum block size and the alignment size from 8 to 16 bytes (what this implementation does). This makes the logic very simple (as all blocks will be a multiple of 16 bytes), but you'll end up with more internal fragmentation.
• Another approach is to take the largest multiple of 8 as before, so long as its above 16 bytes. This allows for less internal fragmentation in the general case, but there are a few edges cases you must consider when it comes to blocks that are slightly too big for the data, yet too small to split (e.g. needing 16 bytes but having 24 available).

Additionally, to fully avoid iterating over any allocated blocks whatsoever, we must maintain some reference to the first explicit free list node. This can either be a global variable or a special node at the start of the heap. For the purpose of this simulation, I'll opt for the first option of putting it outside of the heap inside of a global variable.

Another consideration is, since you now explicitly define what the previous and next elements are for each free block, what order do you put them in?

• One approach is order entries by address, which is more intuitive to visualize, and has good memory utilization, but needs to compute the correct place to put a newly freed block (can be linear time in the worst case).
• Another approach is to maintain entries in LIFO order, and put newly freed blocks at the front of the list. This has the benefit of making free very quick.

For this implementation, the explicit free list entries are maintained in address order for the best viewing experience.