Memory Fragmentation

For this example, it is assumed hat there is a 10K heap. 

First, an area of 3K is requested, thus:

         #define K (1024)
         char *p1;
         p1 = malloc(3*K);

Then, a further 4K is requested:

        p2 = malloc(4*K);

3K of memory is now free.

       free(p1);

This leaves 6K of memory free in two 3K chunks, because, 3K allocated and released + 3K free.

 A further request for a 4K allocation is issued:

       p1 = malloc(4*K);

This results in a failure – NULL is returned into p1 – because, even though 6K of memory is available, there is not a 4K contiguous block available. This is memory fragmentation.

It would seem that an obvious solution would be to de-fragment the memory, merging the two 3K blocks to make a single one of 6K. 

In other languages (such as Visual Basic, Java and C#), there are defragmentation (or “garbage collection”) facilities. 

There is no defragmentation in the C++ heap because the application is free to keep pointers to allocated memory. Thus the heap manager cannot move memory around that is already allocated. The only "defragmentation" possible is if you free two adjacent blocks. Then the heap manager will combine the two blocks to a single larger free block that can be used for allocation again.

The only way to really avoid heap fragmentation, is to do memory management yourself, keep track of all the pointers you use, and defragment your heap from time to time. But be aware that there is a reason why this is not done: It does not pay off. The effort in code and performance you need to spend on defragmenting your heap is way too large. ===================== the best-fit algorithm is used in VxWorks 6. Now all free blocks are stored in a binary tree, sorted according to their size. When allocating it simply traverse the tree, looking for a free block big enough, after splitting the block in two, the free block left over will be added to the binary tree. To maintain the binary tree is a little more complex and needs a little more overhead than it does for the first-fit algorithm, =================