Question on the memory allocation algorithm

[tungsten]

With only two header items for a block (size and next_pointer) how can you tell whether a block has been allocated? The only thing I can think of is adding another header item 'is_free'. Thus when the algorithm is traversing the blocks in the heap, it can check whether a block is the right size and also whether it's available. The lectures and other discussions on this forum hint that the two given fields are enough. So I'm not sure what I'm failing to grasp.

[cadet1620]

If the allocated and free blocks are stored densely in the heap memory, then the next pointer can be used to compute the actual size of the block, including its header: block.next - address_of(block). Free blocks then have block.size set to the available user space in the block, and allocated blocks have block.size = 0.

This scheme is not as fast as traditional free list schemes because one must search through allocated blocks as well as free blocks to find a large enough free block to satisfy the allocation request.

Ponder this: When deallocating a block, it is difficult to find the preceding block to check if it is free and should be merged with the block being freed. In this scheme, can merging free blocks be completely ignored by deAlloc() and handled during alloc()'s block list scan when it sees 2 free blocks in a row?

This will slow down all alloc() calls slightly, but saves a list scan in deAlloc(). Since alloc() and deAlloc() calls occur in parity (hopefully 8^), this should be a win.

-----

If you don't want to use densely packed memory blocks, a simple trick is to invert the block size for allocated blocks; the sign bit serves as your allocated flag. (Using invert instead of negate allows you to support size 0 allocated blocks if block.size is the user-available size.)

--Mark

[tungsten]

Thanks Mark. I'll chew on this for a bit.

[tungsten]

I think I got it. Thanks again.