Category: 

What Is a Free List?

Article Details
  • Written By: Eugene P.
  • Edited By: A. Joseph
  • Last Modified Date: 25 August 2016
  • Copyright Protected:
    2003-2016
    Conjecture Corporation
  • Print this Article
Free Widgets for your Site/Blog
The atmosphere of Jupiter's moon Io collapses every time it is eclipsed by the planet.   more...

September 29 ,  2008 :  The Dow Jones Industrial Average experienced its largest one-day drop in history.  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

exception 'Exception' with message 'error writing captcha: Duplicate entry '2147483647' for key 'PRIMARY'' in /ssd/www/wisegeek/public_html/_core/classes/public/Captcha.php:44
Stack trace:
#0 /ssd/www/wisegeek/public_html/_core/controls/public/ControlDiscussionPostBox.php(324): Captcha->createCaptcha()
#1 /ssd/www/wisegeek/public_html/framework/classes/Control.php(104): ControlDiscussionPostBox->preRender(false)
#2 /ssd/www/wisegeek/public_html/framework/classes/Control.php(149): Control->render()
#3 /ssd/www/wisegeek/public_html/tpl/default-nocustom-lu/pages/public/article/article.htm(526): Control->__toString()
#4 /ssd/www/wisegeek/public_html/framework/classes/Control.php(300): require('/ssd/www/wisege...')
#5 /ssd/www/wisegeek/public_html/framework/classes/Control.php(309): Control->requireTpl('pages/public/ar...', Object(PageArticleCom), true)
#6 /ssd/www/wisegeek/public_html/framework/classes/Control.php(131): Control->renderTpl('pages/public/ar...', Object(PageArticleCom))
#7 /ssd/www/wisegeek/public_html/framework/classes/FormDataControl.php(87): Control->renderTemplate()
#8 /ssd/www/wisegeek/public_html/framework/classes/Control.php(109): FormDataControl->renderTemplate()
#9 /ssd/www/wisegeek/public_html/framework/classes/ScriptPage.php(50): Control->render(false)
#10 /ssd/www/wisegeek/public_html/framework/classes/Control.php(149): ScriptPage->render()
#11 /ssd/www/wisegeek/public_html/framework/classes/Page.php(97): Control->__toString()
#12 /ssd/www/wisegeek/public_html/_core/classes/public/PublicFrontController.php(443): Page->processRequest()
#13 /ssd/www/wisegeek/public_html/_core/classes/public/PublicFrontController.php(7): PublicFrontController->renderPage()
#14 /ssd/www/wisegeek/public_html/index.php(11): PublicFrontController::run()
#15 {main}