Memory management is the act of managing computer memory

Computer memory

In computing, memory refers to the physical devices used to store programs or data on a temporary or permanent basis for use in a computer or other digital electronic device. The term primary memory is used for the information in physical systems which are fast In computing, memory refers to the...

. 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 the computer system.

Several methods have been devised, that increase the effectiveness of memory management. Virtual memory

Virtual memory

In computing, virtual memory is a memory management technique developed for multitasking kernels. This technique virtualizes a computer architecture's various forms of computer data storage , allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which...

 systems separate the memory addresses used by a process from actual physical addresses, allowing separation of processes and increasing the effectively available amount of RAM using paging

Paging

In computer operating systems, paging is one of the memory-management schemes by which a computer can store and retrieve data from secondary storage for use in main memory. In the paging memory-management scheme, the operating system retrieves data from secondary storage in same-size blocks called...

 or swapping to secondary storage. The quality of the virtual memory manager can have a big impact on overall system performance.

Details

The task of fulfilling an allocation request consists of finding a block of unused memory of sufficient size. Even though this task seems simple, several issues make the implementation complex. One of such problems is internal and external fragmentation

Fragmentation (computer)

In computer storage, fragmentation is a phenomenon in which storage space is used inefficiently, reducing storage capacity and in most cases reducing the performance. The term is also used to denote the wasted space itself....

, which arises when there are many small gaps between allocated memory blocks, which are insufficient to fulfill the request. Another is that allocator's metadata can inflate the size of (individually) small allocations; this effect can be reduced by Chunking

Chunking (computing)

-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. Heap management involves some computation time and can be a performance issue...

.

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 pointer reference

Reference (computer science)

In computer science, a reference is a value that enables a program to indirectly access a particular data item, such as a variable or a record, in the computer's memory or in some other storage device. The reference is said to refer to the data item, and accessing those data is called...

. 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.

Efficiency

The dynamic memory allocation algorithm actually used can impact performance significantly and a study conducted in 1994 by Digital Equipment Corporation

Digital Equipment Corporation

Digital Equipment Corporation was a major American company in the computer industry and a leading vendor of computer systems, software and peripherals from the 1960s to the 1990s...

 illustrates the overhead

Computational overhead

In computer science, overhead is generally considered any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to attain a particular goal...

s involved for a variety of allocators. The lowest average instruction path length

Instruction path length

In computer performance, the instruction path length is the number of machine code instructions required to execute a section of a computer program. The total path length for the entire program could be deemed a measure of the algorithm's performance on a particular computer hardware...

 required to allocate a single memory slot was 52 (as measured with an instruction level profiler on a variety of software).

Fixed-size-blocks allocation

Fixed-size-blocks allocation, also called memory pool allocation, uses a free list

Free list

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...

 of fixed-size blocks of memory (often all of the same size). This works well for simple embedded system

Embedded system

An embedded system is a computer system designed for specific control functions within a larger system. often with real-time computing constraints. It is embedded as part of a complete device often including hardware and mechanical parts. By contrast, a general-purpose computer, such as a personal...

s where no large objects need to be allocated, but it suffers from fragmentation.

Buddy blocks

In this system, memory is allocated from several pools of memory instead of just one, where each pool represents blocks of memory of a certain power of two

Power of two

In mathematics, a power of two means a number of the form 2n where n is an integer, i.e. the result of exponentiation with as base the number two and as exponent the integer n....

 in size. If a smaller size is requested than is available, the smallest available size is selected and it is then broken in two. One of the resulting halves is selected, and the process repeats (checking the size again and splitting if needed) until the block is just large enough. All new blocks that are formed during these splits are added to their respective memory pools for later use.

All the blocks of a particular size are kept in a sorted linked list

Linked list

In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...

 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).

Systems with virtual memory

Virtual memory

Virtual memory

In computing, virtual memory is a memory management technique developed for multitasking kernels. This technique virtualizes a computer architecture's various forms of computer data storage , allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which...

 is a method of decoupling the memory organisation from the actual physical hardware. The applications operate memory via virtual adresses. Each time an attempt to access the actual data is made, virtual memory subsystem translates the virtual address to a physical address, which corresponds to the address of the data as seen by the hardware. The address translation process itself is managed by the operating system. In this way addition of virtual memory enables granular control over the main memory and ways to access it. This can be used to increase the effectiveness of memory management.

Protection

In virtual memory systems the operating system controls the ways a process can access the memory. This feature can be used to disallow a process to read or write to memory that is not allocated to the said process, essentially prevents malicious or malfunctioning code in one program from interfering with the operation of other running programs.

Sharing

Even though the memory for different processes is normally protected from each other, different processes sometimes need to be able to share information. One way to provide this is to allow the processes to access the same part of memory. Shared memory is one of the fastest techniques for Inter-process communication

Inter-process communication

In computing, Inter-process communication is a set of methods for the exchange of data among multiple threads in one or more processes. Processes may be running on one or more computers connected by a network. IPC methods are divided into methods for message passing, synchronization, shared...

.

Physical organization

Memory is usually divided into fast primary storage and slow secondary storage. Memory management in the operating system handles moving information between these two levels of memory.

See also

• Heap (data structure)
  Heap (data structure)
  In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key ≥ key. This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap...
  
  
• Automatic memory allocation
  Automatic memory allocation
  In computer programming, an automatic variable is a lexically-scoped variable which is allocated and de-allocated automatically when program flow enters and leaves the variable's scope...
  
  
• Dynamic array
  Dynamic array
  In computer science, a dynamic array, growable array, resizable array, dynamic table, or array list is a random access, variable-size list data structure that allows elements to be added or removed...
  
  
• Garbage collection
  Garbage collection (computer science)
  In computer science, garbage collection is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program...
  
  
• Memory pool
  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 them in a real time system due to performance...
  
  
• Region-based memory management
  Region-based memory management
  In computer science, region-based memory management is a type of memory management in which each allocated object is assigned to a region. A region, also called a zone, arena, or memory context, is a collection of allocated objects that can be efficiently deallocated all at once...
  
  
• Slab allocation
  Slab allocation
  Slab allocation is a memory management mechanism intended for the efficient memory allocation of kernel objects which displays the desirable property of eliminating fragmentation caused by allocations and deallocations. The technique is used to retain allocated memory that contains a data object of...
  
  
• Stack-based memory allocation
  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, it may add some of its state data to the top of the...
  
  
• Demand paging
  Demand paging
  In computer operating systems, demand paging is an application of virtual memory. In a system that uses demand paging, the operating system copies a disk page into physical memory only if an attempt is made to access it...
  
  
• Memory management unit
  Memory management unit
  A memory management unit , sometimes called paged memory management unit , is a computer hardware component responsible for handling accesses to memory requested by the CPU...
  
   (MMU)
• Page table
  Page table
  A page table is the data structure used by a virtual memory system in a computer operating system to store the mapping between virtual addresses and physical addresses. Virtual addresses are those unique to the accessing process...
  
  
• Paging
  Paging
  In computer operating systems, paging is one of the memory-management schemes by which a computer can store and retrieve data from secondary storage for use in main memory. In the paging memory-management scheme, the operating system retrieves data from secondary storage in same-size blocks called...
  
  
• Pointer
• Virtual memory
  Virtual memory
  In computing, virtual memory is a memory management technique developed for multitasking kernels. This technique virtualizes a computer architecture's various forms of computer data storage , allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which...
  
  

Further reading

• "Dynamic Storage Allocation: A Survey and Critical Review", Department of Computer Sciences University of Texas at Austin
  University of Texas at Austin
  The University of Texas at Austin is a state research university located in Austin, Texas, USA, and is the flagship institution of the The University of Texas System. Founded in 1883, its campus is located approximately from the Texas State Capitol in Austin...
  
  

External links

• Sample bit-mapped arena memory allocator in C
• TLSF: a constant time allocator for real-time systems
• Slides for knowing about Dynamic memory allocation
• Inside A Storage Allocator
• The Memory Management Reference
• Linux Memory Management
• Memory Management For System Programmers
• "Generic Memory Manager" C++ library