A free list (or freelist) is a data structure used in a scheme for
dynamic memory allocation. It operates by connecting unallocated regions of memory together in a
linked list, using the first word of each unallocated region as a pointer to the next. It is most suitable for allocating from a
memory pool
Memory pools, also called fixed-size blocks allocation, is the use of pools for memory management that allows dynamic memory allocation comparable to malloc or C++'s operator new. As those implementations suffer from fragmentation because of ...
, where all objects have the same size.
Free lists make the allocation and deallocation operations very simple. To free a region, one would just link it to the free list. To allocate a region, one would simply remove a single region from the end of the free list and use it. If the regions are variable-sized, one may have to search for a region of large enough size, which can be expensive.
Free lists have the disadvantage, inherited from linked lists, of poor
locality of reference and so poor
data cache
A CPU cache is a hardware cache used by the central processing unit (CPU) of a computer to reduce the average cost (time or energy) to access data from the main memory. A cache is a smaller, faster memory, located closer to a processor core, which ...
utilization, and they do not automatically consolidate adjacent regions to fulfill allocation requests for large regions, unlike the
buddy allocation system. Nevertheless, they are still useful in a variety of simple applications where a full-blown memory allocator is unnecessary or requires too much overhead.
The
OCaml
OCaml ( , formerly Objective Caml) is a general-purpose, multi-paradigm programming language which extends the Caml dialect of ML with object-oriented features. OCaml was created in 1996 by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Di ...
runtime uses free lists to satisfy allocation requests.
See also
*
Buddy memory allocation
The buddy memory allocation technique is a memory allocation algorithm that divides memory into partitions to try to satisfy a memory request as suitably as possible. This system makes use of splitting memory into halves to try to give a best fit. ...
References
Further reading
The Memory Management GlossaryMemory Allocation Lecture Slides (ppt)
Memory management
Linked lists
{{operating-system-stub