Q:

Data Structure Used by OS to Implement Heap for Dynamic Memory Management?

Which Data Structure is used by the OS to implement the Heap Memory used in Dynamic Memory Menagement?

A:

I have found that a derivative of a linked list is a good candidate for heap management.
On embedded systems with very small confined memory areas, different memory pools are more efficients.  One memory pool could be for small (byte unit) allocations and use a bit-vector to tell which blocks are allocated.  Another memory pool for medium or frequently allocated blocks and the remaining area for infrequently allocated blocks.  
The idea is to efficiently allocate blocks of memory with low memory overhead and to reduce fragmentation.  
Some OSes use a concept of virtual memory in which memory is paged out to an external device, such as a hard drive.  When the OS receives a page fault, indicate an access outside the memory page, it loads in a page from the external device.
Hope that helps.

