Dynamic Memory Management

1) What are the approaches for dynamic memory management?

Explicit: Explicit memory allocation and de-allocation using malloc() and free() by the programmer, this can be very efficient, but its error prone, when a programmer forgets to free the allocated memory.

Automatic: In this approach the programmer allocates the memory but the run time system takes care of claiming the un-used memory (garbage collection). This kind of method is used in languages such as Java, this can be very simple for the programmer but it can lead to slow performance, since run time system needs to decide which memory to be reclaimed.

2) How does malloc work?

Before calling main(), C runtime system asks OS for large chunk of memory. This will serve as the heap for that program. Malloc() carves out a piece of the heap records the fact that it is allocated, so subsequent calls to malloc will not use this storage. When free() is called, records the fact that piece of heap is no longer allocated, subsequent calls to malloc can use it.

3) How does malloc manage the Heap?

• Free data is arranged in a linked list (free list)
• Next pointer embedded in free data itself (rather than building a separate “list” structure as shown in figure
• Each chunk is “tagged” with size (prefix or auxiliary table)
• When malloc called,
• Scan list for sufficiently large chunk, Chunk may need to be split
• Returned chunk also “tagged” with size

• When Free is called,
• Adds chunk of data back onto the free list (at head)
• Size available in “tag”

 

4) What are the problems associated with Malloc() and Free()

a. What if wrong address is freed?
- Consider the following code example,

p = malloc(x);
p++;
free(p);

In this case the size info will be wrong!, and hence the program will likely (later) fail in mysterious ways

b. What if same chunk is freed twice?
- Often results in free-list cycle

5) More Problems

a) Fragmentation
 • After a while, we end up with lots of small chunks
 • May have enough memory for some request, but not contiguous
 • Solutions

1) Allow heap to grow (ask OS for more memory)
2) Choose chunks wisely: best fit v. first fit

b) Slow allocation
 • Must traverse long list to find suitable chunk of memory
 • Solutions

1) Sort free list (now free is slower)
2) Multiple free lists (e.g., one for large chunks, one for small, etc.)

c) Bugs
 • Wild writes can corrupt size or next pointers
 • Solution?

1) Use auxiliary structure to record size (doesn’t actually solve problem)
2) Valgrind (provides its own implementation of malloc)