Coursera part 2 introduces a slight variation of the Heap Management algorithm presented in the book.
The significant changes are
Memory.alloc() changesThe search loop in Memory.alloc() remains the same—using either first-fit or best-fit, find a segment on the free list whose size is greater than or equal to the requested block size.
In the Book algorithm, once a large enough segment is found, the segment is either used in its entirety, or it is split into two segments. If the entire segment is used, the segment must be removed from the free list. This is a non-trivial operation because the search loop must keep track of two pointers during the linked-list search so that the segment that links to the segment to be removed can have its next pointer updated.
The Coursera algorithm vastly simplifies this by always spliting the found segment and using the newly created segment for the allocated block. The found segment is reduced in size but is never removed from the free list. Another useful effect of always splitting segments for allocation is that the free list will never be empty; the freeList pointer will never be null.
Memory.deAlloc() changesMemory.deAlloc() is simplified because the size field is already in the correct location and has the correct value. The deallocated segment just needs to be returned to the free list.
Allocated block headerThe Coursera algorithm sets the next pointer in the block header to null. An improvement would be to set it to a signature, a known value that is neither null nor a legal pointer value. This will allow dealloc() to check if the block being deallocated is an allocated block. (Double deallocation is a common programming error.)
The simplest signature scheme is to set the next field to an easily recognizable value like -31416.
An alternative is to set the next field to a value derived from the block size. This would help prevent allocated blocks that had their header overwritten from being placed on the free list and corrupting the heap. Setting the block size to not(block size) will form a suitable value that is an illegal address.
FragmentationThe Coursera algorithm is more susceptible to fragmentation than the Book algorithm because it always splits the heap segment that is used for a block allocation. This means that a block that is deallocated will be too small to satisfy a request for another block of the same size. A program that is repeatedly creating and disposing the same object will inevitably run out of memory.
DefragmentationDefragmentation is not required by the course, but may be necessary if you want to run your game using your OS. Here is a fairly easy way to do defragmentation in Memory.deAlloc().
To find the highest addressed segment that is less than the segment being deallocated, search the list for the first segment that has a next pointer that null or is greater that the deallocated segment's address.
deAlloc(Array o) segment = o-2 // Get heap segment from data block address prev_seg = free_list next_seg = prev_seg.next while next_seg != null and next_seg < segment prev_seg = next_seg next_seg = prev_seg.nextAt this point, prev_seg is the segment before the insertion point and next_seg is the segment after the insertion point. WARNING: next_seg may be null.
It is simple to insert the deallocated segment into the free list between prev_seg and next_seg
prev_seg.next = segment segment.next = next_seg
There are now three defragmentation cases that need to be handled.
// Combine segment with next_seg if contiguous. if (segment + segment.blockSize + 2) == next_seg segment.blockSize = segment.blockSize + next_seg.blockSize + 2; segment.next = next_seg.next; // Combine segment with prev_seg if contiguous. if (prev_seg + prev_seg.blockSize + 2) == segment prev_seg.blockSize = prev_seg.blockSize + segment.blockSize + 2; prev_seg.next = segment.next;
ResultsI wrote a test program that allocates 20 blocks randomly sized 200..600 words. It then runs 10,000 passes randomly deallocating 5 of the blocks then reallocating 5 new blocks. Increasing the block size by 25% (to 250..750) causes an allocation failure.
 If I did my math right, the mean and standard deviation for the sum of 20 uniform random integers is:
|Free forum by Nabble||Edit this page|