Dynamic memory allocation

Dynamic memory allocation

In computer science, dynamic memory allocation is the allocation of memory storage for use in a computer program during the runtime of that program. It can be seen also as a way of distributing ownership of limited memory resources among many pieces of data and code.

Dynamically allocated memory exists until it is released either explicitly by the programmer, exiting a block, or by the garbage collector. This is in contrast to static memory allocation, which has a fixed duration. It is said that an object so allocated has a "dynamic lifetime".

Details

* The task of fulfilling allocation request
** Finding a block of unused memory of sufficient size

* Problems during fulfilling allocation request
** Internal and external fragmentation.
*** Reduction needs special care, thus making implementation more complex (see algorithm efficiency).
** Allocator's metadata can inflate the size of (individually) small allocations;
*** Chunking attempts to reduce this effect.

Usually, memory is allocated from a large pool of unused memory area called the heap (also called the free store). Since the precise location of the allocation is not known in advance, the memory is accessed indirectly, usually via a reference. The precise algorithm used to organize the memory area and allocate and deallocate chunks is hidden behind an abstract interface and may use any of the methods described below.

Implementations

Fixed-size-blocks allocation

Fixed-size-blocks allocation, also called memory pool allocation, uses a free list of fixed-size blocks of memory (often all of the same size). This works well for simple embedded systems.

Buddy blocks

In this system, memory is allocated from a large block in a memory that is a power of two in size. If the block is more than twice as large as desired, it is broken in two. One of the halves is selected, and the process repeats (checking the size again and splitting if needed) until the block is just large enough.

All the blocks of a particular size are kept in a sorted linked list or tree. When a block is freed, it is compared to its buddy. If they are both free, they are combined and placed in the next-largest size buddy-block list. (When a block is allocated, the allocator will start with the smallest sufficiently large block avoiding needlessly breaking blocks)

ee also

* Hazard pointer
* Heap overflow
* Hoard memory allocator
* malloc
* Memory pool
* mmap
* obstack
* Slab allocation
* Stack-based memory allocation

References

* Donald Knuth. "Fundamental Algorithms", Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.5: Dynamic Storage Allocation, pp.435–456.
* Herbert Glarner's visualized [http://herbert.gandraxa.com/herbert/dsa.asp Dynamic Storage Allocation] , describing efficient techniques
* [http://www.osdcom.info/content/view/31/39/ Simple Memory Allocation Algorithms] on OSDEV Community
* cite journal
author = Wilson, P.R.
coauthors = Johnstone, M.S.; Neely, M.; Boles, D.
year = 1995
title = Dynamic Storage Allocation: A Survey and Critical Review
journal = Memory Management: International Workshop, Iwmm'95, Kinross, Uk, September 27-29, 1995: Proceedings
url = http://books.google.com/books?hl=en&lr=&ie=UTF-8&id=m0yZN2bA3TcC&oi=fnd&pg=PA1&dq=paul+wilson&ots=H28axwHr6U&sig=cCCwN72PZFqLtnjRWhIvpbXbc0c
accessdate = 2008-01-06
* cite journal
author = Berger, E.D.
coauthors = Zorn, B.G.; McKinley, K.S.
year = 2001
title = Composing high-performance memory allocators
journal = ACM SIGPLAN Notices
volume = 36
issue = 5
pages = 114–124
url = http://portal.acm.org/citation.cfm?id=381694.378821
doi = 10.1145/381694
* cite conference
author = Berger, E.D.
coauthors = Zorn, B.G.; McKinley, K.S.
year = 2002
title = Reconsidering custom memory allocation
conference =
booktitle = Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications
pages = 1-12
publisher = ACM Press New York, NY, USA
url = http://portal.acm.org/citation.cfm?id=582419.582421
conferenceurl =

External links

* [http://geocities.com/malbrain/arena2_c.html Sample bit-mapped arena memory allocator in C]
* [http://rtportal.upv.es/rtmalloc TLSF: a constant time allocator for real-time systems]
* [https://users.cs.jmu.edu/bernstdh/web/common/lectures/slides_cpp_dynamic-memory.php Slides for knowing about Dynamic memory allocation]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Dynamic Memory Allocation —   [dt. »dynamische Speicherzuweisung«], Speicherverwaltung …   Universal-Lexikon

  • dynamic memory allocation — dinaminis atminties paskyrimas statusas T sritis informatika apibrėžtis ↑Atminties paskyrimas ↑dinaminiam kintamajam veikiant programai, tada kai jos prireikia. Atmintis paskiriama pradėjus veikti ↑ paprogramei, kurioje aprašytas kintamasis.… …   Enciklopedinis kompiuterijos žodynas

  • C dynamic memory allocation — C Standard Library Data types Character classification Strings Mathematics File input/output Date/time Localization …   Wikipedia

  • Static memory allocation — refers to the process of allocating memory at compile time before the associated program is executed, unlike dynamic memory allocation or automatic memory allocation where memory is allocated as required at run time. An application of this… …   Wikipedia

  • Stack-based memory allocation — Stacks in computing architectures are regions of memory where data is added or removed in a Last In First Out manner.In most modern computer systems, each thread has a reserved region of memory referred to as its stack. When a function executes,… …   Wikipedia

  • Buddy memory allocation — The buddy memory allocation technique is a memory allocation technique 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 …   Wikipedia

  • Memory management — is the act of managing computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and freeing it for reuse when no longer needed. This is critical to …   Wikipedia

  • Memory pool — Memory pools, also called fixed size blocks allocation, allow dynamic memory allocation comparable to malloc or C++ s operator new. As those implementations suffer from fragmentation because of variable block sizes, it can be impossible to use… …   Wikipedia

  • Memory segmentation — is the division of computer memory into segments or sections. Segments or sections are also used in object files of compiled programs when they are linked together into a program image, or the image is loaded into memory. In a computer system… …   Wikipedia

  • Memory debugger — A memory debugger is a programming tool for finding memory leaks and buffer overflows. These are due to bugs related to the allocation and deallocation of dynamic memory. Programs written in languages that have garbage collection, such as managed …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”