Operating System代写：CMPSC473 Writing A Dynamic Storage Allocator

发表于   |   分类于

用C语言实现一个动态存储分配器（Dynamic Storage Allocator），需包含malloc、free和realloc等核心功能。要求设计高效的内存管理系统，处理不同分配模式并确保堆一致性。实现需包含初始化、内存分配/释放/调整及堆检查等功能，采用显式/隐式空闲链表管理内存碎片，并通过分割/合并策略优化性能。评估标准包括正确性、空间效率、吞吐量和代码质量。建议从基础功能开始逐步优化，利用测试工具验证各阶段实现。

Dynamic Storage Allocator

Introduction

This assignment requires you to implement a dynamic memory allocator in C that mimics the functionality of malloc, free, and realloc. You’ll need to create an efficient memory management system that can handle various allocation patterns while maintaining proper heap consistency.

The implementation will be evaluated based on correctness, space efficiency, and performance. You’ll submit your work through GitHub and demonstrate your solution to a TA during scheduled office hours.

Key Requirements

Your implementation must provide the following core functions:

  • bool mm_init(void): Initializes your allocator and returns true on success
  • void* malloc(size_t size): Allocates a block of at least size bytes with 16-byte alignment
  • void free(void* ptr): Releases previously allocated memory
  • void* realloc(void* oldptr, size_t size): Resizes an existing allocation
  • bool mm_checkheap(int line_number): Validates heap consistency

The allocator must operate entirely within the provided memory space without using any system memory management functions. You’ll need to carefully manage memory blocks, handle fragmentation, and implement efficient allocation strategies.

Implementation Approach

A successful implementation typically involves:

  1. Designing a block structure that includes size information and allocation status
  2. Implementing explicit or implicit free lists to track available memory
  3. Developing splitting and coalescing strategies to manage memory efficiently
  4. Creating search algorithms (first-fit, next-fit, best-fit) for allocation
  5. Building comprehensive consistency checks for debugging

The heap checker (mm_checkheap) is particularly important for verifying your implementation’s correctness. It should validate numerous invariants about your memory structure, including:

  • Proper block alignment and sizing
  • Correct free list linkages
  • Absence of overlapping blocks
  • Valid header/footer information
  • Appropriate boundary conditions

Development Strategy

Start by implementing basic functionality before optimizing:

  1. Begin with a simple implicit list implementation
  2. Add boundary tags to support coalescing
  3. Implement splitting of free blocks
  4. Add explicit free lists for faster allocation
  5. Consider segregated lists for improved performance
  6. Finally, optimize for both space and speed

Use the provided test drivers to validate your implementation at each stage. The mdriver program will evaluate your allocator against various allocation patterns, measuring both correctness and performance.

Evaluation Criteria

Your solution will be graded on:

  1. Correctness: Passing all test cases without errors
  2. Space Efficiency: Minimizing internal and external fragmentation
  3. Throughput: Handling allocation requests quickly
  4. Code Quality: Clean implementation with good documentation
  5. Heap Checker: Comprehensive consistency verification

The final submission requires both working code and clear explanations of your design choices during the TA demonstration.

Helpful Tips

  • Draw detailed diagrams of your memory layout
  • Encapsulate pointer arithmetic in helper functions
  • Use git to track your progress
  • Test with small cases before moving to large traces
  • Build your heap checker incrementally
  • Start early to allow time for debugging

Remember that dynamic memory allocation is challenging - take advantage of office hours if you get stuck. The skills you develop in this assignment are fundamental to systems programming and will serve you well in future courses and professional work.