Information about Heap (programming)
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 is a way of distributing ownership of limited memory resources among many pieces of data and code. Importantly, the amount of memory allocated is determined by the program at the time of allocation and need not be known in advance. A dynamic allocation exists until it is explicitly released, either by the programmer or by a garbage collector; this is notably different from automatic and static memory allocation, which require advance knowledge of the required amount of memory and have a fixed duration. It is said that an object so allocated has dynamic lifetime.
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.
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)
Buddy block allocators are used both in real-time operating systems and in general-purpose operating systems (such as Microsoft Windows and Linux).
..... Click the link for more information.
Details
The task of fulfilling an allocation request, which involves finding a block of unused memory of sufficient size, is complicated by the need to avoid both internal and external fragmentation while keeping both allocation and deallocation efficient. Also, the 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
This scheme 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
- For more details on this topic, see Buddy memory allocation.
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)
Buddy block allocators are used both in real-time operating systems and in general-purpose operating systems (such as Microsoft Windows and Linux).
References
- Donald Knuth. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.4: Dynamic Storage Allocation, pp.435–456.
- Herbert Glarner's visualized Dynamic Storage Allocation, describing efficient techniques
- Simple Memory Allocation Algorithms on OSDEV Community
External links
See also
- Allocation algorithms
- malloc
- bsdmalloc
- mtmalloc
- umem alloc
- Vmalloc
- Slab allocation
- mmap
- hazard pointer
- Heap Layers
- Hoard memory allocator
- Memory pool
- obstack
- Stack-based memory allocation
Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems.
..... Click the link for more information.
..... Click the link for more information.
Computer data storage, computer memory, and often casually storage or memory refer to computer components, devices and recording media that retain digital data used for computing for some interval of time.
..... Click the link for more information.
..... Click the link for more information.
A computer program is one or more instructions that are intended for execution by a computer. Specifically, it is a symbol or combination of symbols forming an algorithm that may or may not terminate, and that algorithm is written in a programming language.
..... Click the link for more information.
..... Click the link for more information.
In computer science, runtime or run time describes the operation of a computer program, the duration of its execution, from beginning to termination (compare compile time).
..... Click the link for more information.
..... Click the link for more information.
In computer science, garbage collection (GC) is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory used by objects that will never be accessed or mutated again by the application.
..... Click the link for more information.
..... Click the link for more information.
..... Click the link for more information.
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.
..... Click the link for more information.
..... Click the link for more information.
Fragmentation is a phenomenon that leads to inefficiency in many forms of computer storage. There are three different but related uses of the term: external fragmentation, internal fragmentation, and data fragmentation.
..... Click the link for more information.
..... Click the link for more information.
Metadata is data about data. An item of metadata may describe an individual datum, or content item, or a collection of data including multiple content items.
Metadata (sometimes written 'meta data') is used to facilitate the understanding, use and management of data.
..... Click the link for more information.
Metadata (sometimes written 'meta data') is used to facilitate the understanding, use and management of data.
..... Click the link for more information.
In computer programming, chunking has multiple meanings.
..... Click the link for more information.
In memory management
Typical modern software systems allocate memory dynamically from structures known as heaps. Calls are made to heap-management routines to allocate and free memory...... Click the link for more information.
reference is an object containing information which refers to data stored elsewhere, as opposed to containing the data itself. Accessing the value referred to by a reference is called dereferencing it.
..... Click the link for more information.
..... Click the link for more information.
A free list 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.
..... Click the link for more information.
..... Click the link for more information.
An embedded system is a special-purpose computer system designed to perform one or a few dedicated functions.[1] It is usually embedded as part of a complete device including hardware and mechanical parts.
..... Click the link for more information.
..... Click the link for more information.
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.
..... Click the link for more information.
..... Click the link for more information.
power of two is any of the integer powers of the number two;[1] in other words, two multiplied by itself a certain number of times.[2] Note that one is a power (the zeroth power) of two. Written in binary, a power of two always has the form 100...
..... Click the link for more information.
..... Click the link for more information.
tree is a widely-used data structure that emulates a tree structure with a set of linked nodes.
..... Click the link for more information.
Nodes
A node may contain a value or a condition or represents a separate data structure or a tree of its own...... Click the link for more information.
A real-time operating system (RTOS) is a multitasking operating system intended for real-time applications. Such applications include embedded systems (programmable thermostats, household appliance controllers, mobile telephones), industrial robots, spacecraft, industrial
..... Click the link for more information.
..... Click the link for more information.
An operating system (OS) is the software that manages the sharing of the resources of a computer. An operating system processes system data and user input, and responds by allocating and managing tasks and internal system resources as a service to users and programs of the
..... Click the link for more information.
..... Click the link for more information.
Microsoft Windows
Screenshot of Windows Vista Ultimate, the latest version of Microsoft Windows.
Company/developer: Microsoft Corporation
OS family: MS-DOS/9x-based, Windows CE, Windows NT
Source model: Closed source
..... Click the link for more information.
Screenshot of Windows Vista Ultimate, the latest version of Microsoft Windows.
Company/developer: Microsoft Corporation
OS family: MS-DOS/9x-based, Windows CE, Windows NT
Source model: Closed source
..... Click the link for more information.
Linux (pronunciation: IPA: /ˈlɪnʊks/, lin-uks) is a Unix-like computer operating system. Linux is one of the most prominent examples of free software and open source development; its underlying source code can be
..... Click the link for more information.
..... Click the link for more information.
Donald Ervin Knuth
Photographed by Jacob Appelbaum, 25 October 2005
Born January 10 1938
..... Click the link for more information.
Photographed by Jacob Appelbaum, 25 October 2005
Born January 10 1938
..... Click the link for more information.
There are various ways in which memory can be managed and allocated.
In the most general sense, dynamic memory allocation is achieved using a heap. This heap may be represented as one or more regions of memory, which may then be subdivided by some means into any number of blocks or
..... Click the link for more information.
In the most general sense, dynamic memory allocation is achieved using a heap. This heap may be represented as one or more regions of memory, which may then be subdivided by some means into any number of blocks or
..... Click the link for more information.
In computing,
..... Click the link for more information.
malloc is a subroutine provided in the C programming language's and C++ programming language's standard library for performing dynamic memory allocation...... Click the link for more information.
In computer science, the slab allocation algorithm manages memory in such a way as to solve the problem of internal memory fragmentation. Internal memory fragmentation results from allocating a block of memory much larger than the requested memory (see Buddy memory allocation).
..... Click the link for more information.
..... Click the link for more information.
mmap is a POSIX-compliant Unix system call that maps files or devices into memory. It is a method of memory-mapped file I/O. It naturally implements demand paging, because initially file contents are not entirely read from disk and don't use physical RAM at all.
..... Click the link for more information.
..... Click the link for more information.
In a multithreaded computing environment, a hazard pointer is an element used by a methodology that allows the memory allocated to the nodes of lock-free dynamic shared objects to be reclaimed.
..... Click the link for more information.
..... Click the link for more information.
The Hoard memory allocator, or Hoard, is a memory allocator for Linux, Solaris, Microsoft Windows and other operating systems. Hoard can improve the performance of multithreaded applications by providing fast, scalable memory management functions (malloc and free).
..... Click the link for more information.
..... Click the link for more information.
Memory pools 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 them in a real time system due to performance.
..... Click the link for more information.
..... Click the link for more information.
An obstack is a stack of objects (data items) which is grown dynamically.
Obstack code typically provides C language macros which take care of memory allocation and management for you.
..... Click the link for more information.
Obstack code typically provides C language macros which take care of memory allocation and management for you.
..... Click the link for more information.
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.
..... Click the link for more information.
In most modern computer systems, each thread has a reserved region of memory referred to as its stack.
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
