Memory allocation is a critical process in computer systems, enabling efficient management of memory resources for running applications, especially for AI model training and inferencing in this era. Allocation algorithms determine how memory is divided, assigned, and freed for use by various programs. These algorithms ensure optimal use of limited memory while minimising fragmentation and performance bottlenecks.

Why is it Important?

• Efficiency: Efficient memory allocation maximises the use of available RAM, allowing multiple programs to run smoothly without crashing.
• Performance: The speed at which programs access and use memory directly impacts overall system performance.

Fragmentation

Before diving into specific algorithms, let’s understand fragmentation:

• Internal Fragmentation: Occurs when a process is allocated more memory than it needs. The unused portion within the allocated block is wasted.
• External Fragmentation: Occurs when there are many small, free blocks of memory scattered throughout the memory space, but no single block is large enough to satisfy a request, even though the total free space may be sufficient.

Coalescing

Coalescing is a technique used to mitigate external fragmentation. It involves combining adjacent free blocks of memory into larger, more usable blocks. This increases the likelihood of finding a suitable block for future allocations and improves memory utilization.

Algorithms

Fast-Fit

The First-Fit method simply finds the first block that is big enough and returns the requested amount to the user. As before, the remaining free space is kept free for subsequent requests.

Best-Fit

The Best-Fit searches for the smallest available block of memory that can satisfy the request.

Worst-Fit

The Worst-Fit selects the largest available block, hoping to leave a large contiguous block for future, potentially larger allocations.

Next-Fit

Next-fit is a memory allocation algorithm that’s a variation of the first-fit algorithm. It aims to improve upon first-fit by reducing fragmentation in certain scenarios.

How it Works:

1. Initial Search: Like first-fit, next-fit starts searching for a free block of memory from the beginning of the memory space.
2. Subsequent Searches: Unlike first-fit, which always starts from the beginning, next-fit remembers the last allocated block. It begins its subsequent searches from the block after the last allocated block. This creates a “moving window” effect.

Buddy System

The buddy memory allocation system is an efficient method for managing memory that equally divides memory into partitions (blocks) of sizes that are powers of two.

TBC