fredag 16 december 2011

w1d4: Buddy chunk/free list

The buddy allocator allocates chunks of memory which is then split as needed. Each chunk is a even multiple of 2^k * MIN_CHUNK_SIZE. This leads to wasting memory, which is called internal fragmentation. Chunks are stored on a free list for each k, which itself is a list.

An item contains k, pointer to smaller item and the free list which is a pointer to a chunk.
A chunk contains a, b of size k and a pointer to the next chunk.

The root item is the largest chunk size available rounded up to the nearest power of 2. New chunks are fit into the proper k' by log2(n/MIN_CHUNK_SIZE). If there is no such k' yet, a new item is created with the smaller k' (iteratively, if k-k'>1) and new chunks created by splitting one of  the larger chunk's a or b members in half.

Work log
Item, chunk, constructors, destructors, splitting next. Unit tests for init functions written.

Inga kommentarer:

Skicka en kommentar