Table of contents
Managing free space can be very easy especially when dealing with memory space which is divided into fixed-sized units compared to managing variable-divided space. When one uses the malloc and free function from the user-level memory allocation library, in C programming, for example, variable-sized unit division is used. Segmentation of memory by the OS managing the physical memory causes a problem called external fragmentation, in which the memory space is chopped into little pieces of different sizes and therefore fragmented. If there is a request from a program for more memory by calling malloc, the request can fail as a result of a lack of contiguous space to fulfil such a request.
One interesting thing about OS is having strong fundamentals in a low-level programming language because you can relate better to the theoretical part of operating systems. Let's discuss the malloc and free functions in C to understand what they do.
void *malloc(size t size)
This takes in a size_t parameter specifying the number of bytes to be allocated to a pointer if the memory request is granted or NULL.
void free (void* ptr)
The free function takes a pointer to allocated memory and frees the location when called.
Both functions that the library manages interact with a space called the heap. The generic data structure used to manage this free space is the Free list.
Additionally, we'll assume that memory cannot be moved to a different position in memory once it has been assigned to a client. For instance, when a program uses malloc() to allocate memory and provides a reference to a certain area of the heap, that memory chunk is effectively "owned" by the application and cannot be moved by the library until it is used in a corresponding call to free() to return it. As a result, open space cannot be compacted, which would help prevent fragmentation.
Imagine trying to access an empty spot in a sparsely populated car park. Yes, you can see the space but you need to be told whether or not the space is free, which is the job of an OS. So how do we easily locate free space in memory?
The Free list is a structure containing references to the memory location of all free chunks of space in the managed region of memory. Although the name includes a list, it does not mean that the data structure is an actual list but some kind of structure that can track free spaces.
Mechanisms Applied In Allocating Memory:
Splitting And Coalescing
In memory allocation, two crucial mechanisms are splitting and coalescing, which manage free space in a heap effectively. Splitting occurs when a memory request is smaller than an available free chunk, dividing the chunk into the requested size and a smaller remainder.
For example, given a 30-byte heap with two free chunks of 10 bytes each at addresses 0-9 and 20-29, if a request for 1 byte is made, an allocator can split the second chunk. The request returns address 20, and the free list updates to show the new free chunk starting at 21 with a length of 9 bytes. Conversely, coalescing merges adjacent free chunks into a larger block when space is freed. The free list initially shows three separate 10-byte chunks if the middle 10-byte chunk is freed in the same heap. Coalescing combines these adjacent free chunks into a single 30-byte chunk, restoring the heap to its original state and ensuring larger contiguous memory spaces are available for future allocations. This combination of splitting and coalescing optimizes memory utilization and prevents fragmentation, maintaining efficient allocation and deallocation processes.
Heap growth
In addition to splitting and coalescing, another crucial mechanism for managing memory in allocation libraries is heap growth. When the heap runs out of space, the allocator can request more memory from the operating system rather than simply failing. This process typically involves a system call, such as sbrk on UNIX systems, which extends the heap by allocating additional physical memory pages and mapping them into the process's address space.
For example, suppose an application initially has a 30-byte heap that is fully utilized. Upon requesting more memory (e.g., 20 bytes), the allocator recognizes that the heap space is insufficient. Instead of returning NULL and indicating failure, the allocator can make a system call to request additional memory. The operating system then locates free physical pages, maps them to the process's address space, and updates the end of the heap to reflect this growth. The heap might expand from 30 to 50 bytes to accommodate the new memory request.
This mechanism allows for dynamic heap expansion, enabling applications to handle larger workloads and data sets without being constrained by the initial heap size. It ensures that the allocator can continue servicing memory requests as long as the system has available resources.
Other mechanisms for managing memory are:
Buddy allocation
Segregated List
The following strategies can be used to manage free space on a free list:
Best Fit - This approach finds free memory chunks larger or larger than the requested size in the free list and returns the smallest of these.
Worst Fit - This is the opposite of best fit; it finds the largest free chunk and returns the requested amount keeping the remainder on the free list.
First Fit - Find the first block of free memory that is large enough.
Next Fit - Instead of beginning the first fit search at the beginning of the list, the next-fit algorithm keeps an extra pointer to the location within the list where one was looking last spreading the search for free space more uniformly.
As we discussed in this article, the Operating System manages free memory space through several mechanisms and strategies. Hopefully, we now have a better understanding of how memory management works.