This project explores dynamic memory allocation strategies in C by simulating how memory is managed in systems with a fixed-size memory region. The goal is to evaluate different allocation strategies and understand their trade-offs in terms of fragmentation, utilization, and allocation success. The program processes a sequence of allocation and deallocation requests and reports whether each request can be satisfied. At the end of execution, it prints a detailed summary of memory usage and allocation state.
In C, memory allocation typically works by requesting portions of a larger memory block (identified by a starting address and size). On virtual memory systems, the heap can grow dynamically. On embedded or constrained systems (e.g., IoT devices, automotive systems), memory is fixed and all allocations must come from a predefined block. Each allocation is satisfied by carving out a portion of the available memory. When memory is freed, it may later be reused for new allocation requests.
However, several challenges arise:
- Requested allocation sizes often differ.
- Memory becomes fragmented over time.
- Adjacent free chunks should ideally be merged (coalesced).
- Allocation metadata introduces overhead.
This project focuses on how different allocation strategies handle these challenges.
#Allocation Strategies Implemented
- First Fit: Uses the first available free chunk that is large enough. If the chunk is larger than needed, it is split. Fast, but can lead to fragmentation.
- Best Fit: Chooses the free chunk that results in the least wasted space. Reduces fragmentation but may be slower due to searching.
- Worst Fit: Chooses the free chunk that results in the most leftover space. Attempts to avoid creating tiny unusable fragments.
#Program Overview
Written in C Uses a provided main() function to ensure consistent command-line behavior Simulates memory allocation within a fixed-size memory region Tracks allocated and free chunks Supports allocation and deallocation via an input file At the end of execution, the program prints a SUMMARY including:
Total bytes allocated Total bytes free A list of all memory chunks and their states
Input File Format Allocation Requests Allocation lines begin with A and include: An ID A size (decimal or hexadecimal) An optional paint character
Format: A::[:<paint_char>]
Examples:
A:11:1231 A:12:0x0200:+
If no paint character is provided, ~ is used by default.
IDs are guaranteed to be unique in valid input files.
Deallocation Requests
Deallocation lines begin with F (free) or R (release) and include: The ID of the allocation to free Format: F: R:
Examples: F:1 R:2
If an ID does not exist (e.g., allocation previously failed), the program reports the issue but continues execution.
Sample Execution $ ./allocator -m 4096 -s first smalltest.txt alloc 1024 bytes : SUCCESS - return location 0 alloc 2048 bytes : SUCCESS - return location 1024 alloc 2048 bytes : FAIL alloc 512 bytes : SUCCESS - return location 3072 free location 1024 free location 0 alloc 4096 bytes : FAIL alloc 3000 bytes : SUCCESS - return location 0 SUMMARY: 3512 bytes allocated 584 bytes free 4 allocation chunks: chunk 0 location 0:3000 bytes - allocated chunk 1 location 3000:72 bytes - free chunk 2 location 3072:512 bytes - allocated chunk 3 location 3584:512 bytes - free
Learning Outcomes: This project demonstrates: Low-level memory management Trade-offs between allocation strategies Fragmentation and reuse of memory Practical systems programming in C Debugging memory layouts