Category: 

What Is a Free List?

Article Details
  • Written By: Eugene P.
  • Edited By: A. Joseph
  • Last Modified Date: 13 November 2016
  • Copyright Protected:
    2003-2016
    Conjecture Corporation
  • Print this Article
Free Widgets for your Site/Blog
The Argentinian resort town of Epecuén was submerged by flooding for years; it is now populated by one elderly man.  more...

December 5 ,  1933 :  Prohibition ended in the US.  more...

A free list is a‭ ‬data structure that holds the addresses of computer memory locations‭ ‬that are available for use by a running program when using dynamic memory allocation.‭ ‬The list becomes necessary when a program must‭ ‬allocate‭ ‬space from an area of free memory called the heap.‭ ‬The‭ ‬implementation of a free list‭ ‬can be‭ ‬a‭ ‬simple‭ ‬linked list ‬or could be a more complex‭ ‬data‭ ‬structure such as a sort tree.‭ ‬Most high-level computer programming languages automatically‭ ‬handle the free list,‭ ‬removing the need for manual management.‭

When a program requires‭ ‬space to store information during program execution,‭ ‬it must request a specific amount of memory from the underlying operating system.‭ ‬The locations of‭ ‬memory‭ ‬blocks that can be utilized are stored in the free list.‭ For the allocation to be successful,‭ ‬the amount of requested memory needs to be available in one or more‭ ‬of these‭ ‬blocks.‭ When a pointer‭ ‬to‭ ‬an appropriate memory location is returned,‭ ‬that‭ ‬element of the list is removed.

After a program is done using the‭ ‬memory,‭ ‬it can de-allocate it.‭ ‬This involves passing the pointer to the memory‭ ‬block back into the free list, where it will become available the next time an allocation is attempted.‭ ‬It is possible for memory allocation to fail because the‭ ‬list is empty or because there are no available memory blocks large enough to fulfill the program‭’‬s request.

Ad

The‭ ‬simplest form of memory management is called the first fit system.‭ ‬This system maintains a single‭ ‬list of free memory locations.‭ ‬When a request for memory is sent,‭ ‬the list is traversed and the first block that is large enough is returned.‭ ‬If the block is more than twice the‭ ‬requested size,‭ ‬then it is halved, and the unused half is added back to the‭ ‬list.‭ ‬This method trades simple coding for the risk of having fragmented memory areas that might never be returned to the list.‭

A different form of memory management is called the buddy allocation system.‭ ‬Unlike the first fit system,‭ ‬buddy allocation keeps several‭ ‬free lists,‭ ‬each one holding open blocks of only one particular size.‭ ‬This means that when an allocation request is received,‭ ‬the list that holds blocks that are just large enough to fill the request is consulted, and an open location is returned.‭ ‬If no‭ ‬free‭ ‬blocks that are less than twice the size requested are available,‭ ‬a larger block is split in two to fulfill the requirements.

The term "free list" can refer to either a single linked list of memory addresses,‭ ‬or it can refer to a much more complex type of data structure.‭ ‬Different types of sort trees,‭ ‬if kept simple and balanced,‭ ‬can help increase the speed of finding open memory blocks at the expense of‭ ‬complicating the source code.‭ ‬A linked list can be slower than a specialized sort tree ‬but creates programming code that is far easier to read,‭ ‬debug and modify.

Some programming languages and operating systems make use of a special mechanism called garbage collection.‭ ‬This is a process‭ ‬that can help take the different entries on a free list and consolidate the free spaces so that they are contiguous.‭ ‬This has the effect of preventing‭ ‬fragmentation and allowing for larger blocks of memory to be allocated.

Ad

You might also Like

Recommended

Discuss this Article

Post your comments

Post Anonymously

Login

username
password
forgot password?

Register

username
password
confirm
email