This page is not yet finished.

Introduction

This is a course project for 18613 Foundations of Computer System at Carnegie Mellon University.

Concept

C dynamic memory allocation refers to performing manual memory management for dynamic memory allocation in the C programming language via a group of functions in the C standard library, namely malloc, realloc, calloc and free.

Programmers use dynamic memory allocators to acquire virtual memory(VM) at run time. Dynamic memory allocator manages an area of process VM known as heap.

General dynamic memory allocator provides two major function: malloc(size) and free(memory)

• malloc(size): Request a block of memory from VM that is at least size bytes.
• free(memory): Return a block of memory to VM that was previously requested.

Project Objectives

• Learn the internal mechanisms of Dynamic Memory Allocation library.
• Familiar with debug tools (GNU debugger).
• Practice efficient data structures and their applications.
• Know the utilization & throughput trade off.

Key Challenges

• How to track and manage memory fragmentation

  When assigning a block of memory to user, we could not know when it will be freed. Also, we could not predict how what size of block that user will request in its next request. What’s the best strategy under these limitations?

• How to push throughput and memory utilization to limit

  To push the performance of dynamic memory allocator, advanced data structures and algorithm will be used. However, more complex method takes more time and will affect system throughput. How to keep a balance between throughput and memory utilization?

Design

The sole responsibility for a dynamic memory allocator is managing memory blocks.