HOME

TheInfoList



OR:

Memory management is a form of
resource management In organizational studies, resource management is the efficient and effective development of an organization's resources when they are needed. Such resources may include the financial resources, inventory, human skills, production resources, or i ...
applied to
computer memory In computing, memory is a device or system that is used to store information for immediate use in a computer or related computer hardware and digital electronic devices. The term ''memory'' is often synonymous with the term ''primary storage ...
. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and free it for reuse when no longer needed. This is critical to any advanced computer system where more than a single
process A process is a series or set of activities that interact to produce a result; it may occur once-only or be recurrent or periodic. Things called a process include: Business and management *Business process, activities that produce a specific se ...
might be underway at any time. Several methods have been devised that increase the effectiveness of memory management.
Virtual memory In computing, virtual memory, or virtual storage is a memory management technique that provides an "idealized abstraction of the storage resources that are actually available on a given machine" which "creates the illusion to users of a very l ...
systems separate the
memory address In computing, a memory address is a reference to a specific memory location used at various levels by software and hardware. Memory addresses are fixed-length sequences of digits conventionally displayed and manipulated as unsigned integers. Su ...
es used by a process from actual physical addresses, allowing separation of processes and increasing the size of the
virtual address space In computing, a virtual address space (VAS) or address space is the set of ranges of virtual addresses that an operating system makes available to a process. The range of virtual addresses usually starts at a low address and can extend to the hig ...
beyond the available amount of
RAM Ram, ram, or RAM may refer to: Animals * A male sheep * Ram cichlid, a freshwater tropical fish People * Ram (given name) * Ram (surname) * Ram (director) (Ramsubramaniam), an Indian Tamil film director * RAM (musician) (born 1974), Dutch * ...
using
paging In computer operating systems, memory paging is a memory management scheme by which a computer stores and retrieves data from secondary storage for use in main memory. In this scheme, the operating system retrieves data from secondary storage ...
or swapping to
secondary storage Computer data storage is a technology consisting of computer components and recording media that are used to retain digital data. It is a core function and fundamental component of computers. The central processing unit (CPU) of a computer ...
. The quality of the virtual memory manager can have an extensive effect on overall system
performance A performance is an act of staging or presenting a play, concert, or other form of entertainment. It is also defined as the action or process of carrying out or accomplishing an action, task, or function. Management science In the work place ...
. In some
operating system An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs. Time-sharing operating systems schedule tasks for efficient use of the system and may also in ...
s, e.g.
OS/360 and successors OS/360, officially known as IBM System/360 Operating System, is a discontinued batch processing operating system developed by IBM for their then-new System/360 mainframe computer, announced in 1964; it was influenced by the earlier IBSYS/IBJOB ...
, memory is managed by the operating system. In other operating systems, e.g.
Unix-like A Unix-like (sometimes referred to as UN*X or *nix) operating system is one that behaves in a manner similar to a Unix system, although not necessarily conforming to or being certified to any version of the Single UNIX Specification. A Unix-li ...
operating systems, memory is managed at the application level. Memory management within an address space is generally categorized as either
manual memory management In computer science, manual memory management refers to the usage of manual instructions by the programmer to identify and deallocate unused objects, or garbage. Up until the mid-1990s, the majority of programming languages used in industry supp ...
or
automatic memory management In computer science, garbage collection (GC) is a form of automatic memory management. The ''garbage collector'' attempts to reclaim memory which was allocated by the program, but is no longer referenced; such memory is called '' garbage''. ...
.


Manual memory management

The task of fulfilling an allocation request consists of locating a block of unused memory of sufficient size. Memory requests are satisfied by allocating portions from a large pool of memory called the ''heap'' or ''free store''. At any given time, some parts of the heap are in use, while some are "free" (unused) and thus available for future allocations. Several issues complicate the implementation, such as external fragmentation, which arises when there are many small gaps between allocated memory blocks, which invalidates their use for an allocation request. The allocator's
metadata Metadata is "data that provides information about other data", but not the content of the data, such as the text of a message or the image itself. There are many distinct types of metadata, including: * Descriptive metadata – the descriptive ...
can also inflate the size of (individually) small allocations. This is often managed by chunking. The memory management system must track outstanding allocations to ensure that they do not overlap and that no memory is ever "lost" (i.e. that there are no "
memory leak In computer science, a memory leak is a type of resource leak that occurs when a computer program incorrectly manages memory allocations in a way that Computer memory, memory which is no longer needed is not released. A memory leak may also happe ...
s").


Efficiency

The specific dynamic memory allocation algorithm implemented can impact performance significantly. A study conducted in 1994 by
Digital Equipment Corporation Digital Equipment Corporation (DEC ), using the trademark Digital, was a major American company in the computer industry from the 1960s to the 1990s. The company was co-founded by Ken Olsen and Harlan Anderson in 1957. Olsen was president unt ...
illustrates the
overheads In business, overhead or overhead expense refers to an ongoing expense of operating a business. Overheads are the expenditure which cannot be conveniently traced to or identified with any particular revenue unit, unlike operating expenses such as r ...
involved for a variety of allocators. The lowest average
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 performa ...
required to allocate a single memory slot was 52 (as measured with an instruction level profiler on a variety of software).


Implementations

Since the precise location of the allocation is not known in advance, the memory is accessed indirectly, usually through a pointer
reference Reference is a relationship between objects in which one object designates, or acts as a means by which to connect to or link to, another object. The first object in this relation is said to ''refer to'' the second object. It is called a ''name'' ...
. The specific algorithm used to organize the memory area and allocate and deallocate chunks is interlinked with the
kernel Kernel may refer to: Computing * Kernel (operating system), the central component of most operating systems * Kernel (image processing), a matrix used for image convolution * Compute kernel, in GPGPU programming * Kernel method, in machine learnin ...
, and may use any of the following methods:


Fixed-size blocks allocation

Fixed-size blocks allocation, also called memory pool allocation, uses a
free list A free list (or freelist) 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 n ...
of fixed-size blocks of memory (often all of the same size). This works well for simple
embedded system An embedded system is a computer system—a combination of a computer processor, computer memory, and input/output peripheral devices—that has a dedicated function within a larger mechanical or electronic system. It is ''embedded'' as ...
s where no large objects need to be allocated, but suffers from fragmentation, especially with long memory addresses. However, due to the significantly reduced overhead this method can substantially improve performance for objects that need frequent allocation / de-allocation and is often used in
video games Video games, also known as computer games, are electronic games that involves interaction with a user interface or input device such as a joystick, game controller, controller, computer keyboard, keyboard, or motion sensing device to gener ...
.


Buddy blocks

In this system, memory is allocated into several pools of memory instead of just one, where each pool represents blocks of memory of a certain
power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer  as the exponent. In a context where only integers are considered, is restricted to non-negative ...
in size, or blocks of some other convenient size progression. All blocks of a particular size are kept in a sorted
linked list In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
or
tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
and all new blocks that are formed during allocation are added to their respective memory pools for later use. If a smaller size is requested than is available, the smallest available size is selected and split. One of the resulting parts is selected, and the process repeats until the request is complete. When a block is allocated, the allocator will start with the smallest sufficiently large block to avoid needlessly breaking blocks. When a block is freed, it is compared to its buddy. If they are both free, they are combined and placed in the correspondingly larger-sized buddy-block list.


Slab allocation

This memory allocation mechanism preallocates memory chunks suitable to fit objects of a certain type or size. These chunks are called caches and the allocator only has to keep track of a list of free cache slots. Constructing an object will use any one of the free cache slots and destructing an object will add a slot back to the free cache slot list. This technique alleviates memory fragmentation and is efficient as there is no need to search for a suitable portion of memory, as any open slot will suffice.


Stack allocation

Many
Unix-like A Unix-like (sometimes referred to as UN*X or *nix) operating system is one that behaves in a manner similar to a Unix system, although not necessarily conforming to or being certified to any version of the Single UNIX Specification. A Unix-li ...
systems as well as
Microsoft Windows Windows is a group of several proprietary graphical operating system families developed and marketed by Microsoft. Each family caters to a certain sector of the computing industry. For example, Windows NT for consumers, Windows Server for serv ...
implement a function called for dynamically allocating stack memory in a way similar to the heap-based . A compiler typically translates it to inlined instructions manipulating the stack pointer. Although there is no need of manually freeing memory allocated this way as it is automatically freed when the function that called returns, there exists a risk of overflow. And since alloca is an ''ad hoc'' expansion seen in many systems but never in POSIX or the C standard, its behavior in case of a stack overflow is undefined. A safer version of alloca called , which reports errors, exists on Microsoft Windows. It requires the use of .
gnulib Gnulib, also called the GNU portability library, is a collection of software subroutines which are designed to be usable on many operating systems. The goal of the project is to make it easy for free software authors to make their software run ...
provides an equivalent interface, albeit instead of throwing an SEH exception on overflow, it delegates to malloc when an overlarge size is detected. A similar feature can be emulated using manual accounting and size-checking, such as in the uses of in glibc.


Automatic memory management

In many programming language implementations, the runtime environment for the program automatically allocates memory in the
call stack In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or ma ...
for non-static
local variable In computer science, a local variable is a Variable (programming), variable that is given ''local scope (programming), scope''. A local variable reference in the subroutine, function or block (programming), block in which it is declared overrides ...
s of a
subroutine In computer programming, a function or subroutine is a sequence of program instructions that performs a specific task, packaged as a unit. This unit can then be used in programs wherever that particular task should be performed. Functions may ...
, called
automatic variable __NOTOC__ In computer programming, an automatic variable is a local variable which is allocated and deallocated automatically when program flow enters and leaves the variable's scope. The scope is the lexical context, particularly the function or b ...
s, when the subroutine is called, and automatically releases that memory when the subroutine is exited. Special declarations may allow local variables to retain values between invocations of the procedure, or may allow local variables to be accessed by other subroutines. The automatic allocation of local variables makes
recursion Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
possible, to a depth limited by available memory.


Garbage collection

Garbage collection is a strategy for automatically detecting memory allocated to objects that are no longer usable in a program, and returning that allocated memory to a pool of free memory locations. This method is in contrast to "manual" memory management where a programmer explicitly codes memory requests and memory releases in the program. While automatic garbage collection has the advantages of reducing programmer workload and preventing certain kinds of memory allocation bugs, garbage collection does require memory resources of its own, and can compete with the application program for processor time.


Systems with virtual memory

Virtual memory In computing, virtual memory, or virtual storage is a memory management technique that provides an "idealized abstraction of the storage resources that are actually available on a given machine" which "creates the illusion to users of a very l ...
is a method of decoupling the memory organization from the physical hardware. The applications operate on memory via ''virtual addresses''. Each attempt by the application to access a particular virtual memory address results in the virtual memory address being translated to an actual ''physical address''. In this way the addition of virtual memory enables granular control over memory systems and methods of access. In virtual memory systems the operating system limits how a
process A process is a series or set of activities that interact to produce a result; it may occur once-only or be recurrent or periodic. Things called a process include: Business and management *Business process, activities that produce a specific se ...
can access the memory. This feature, called
memory protection Memory protection is a way to control memory access rights on a computer, and is a part of most modern instruction set architectures and operating systems. The main purpose of memory protection is to prevent a process from accessing memory that ha ...
, can be used to disallow a process to read or write to memory that is not allocated to it, preventing malicious or malfunctioning code in one program from interfering with the operation of another. Even though the memory allocated for specific processes is normally isolated, processes sometimes need to be able to share information.
Shared memory In computer science, shared memory is memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies. Shared memory is an efficient means of passing data between progr ...
is one of the fastest techniques for
inter-process communication In computer science, inter-process communication or interprocess communication (IPC) refers specifically to the mechanisms an operating system provides to allow the processes to manage shared data. Typically, applications can use IPC, categori ...
. Memory is usually classified by access rate into
primary storage Computer data storage is a technology consisting of computer components and recording media that are used to retain digital data. It is a core function and fundamental component of computers. The central processing unit (CPU) of a computer ...
and
secondary storage Computer data storage is a technology consisting of computer components and recording media that are used to retain digital data. It is a core function and fundamental component of computers. The central processing unit (CPU) of a computer ...
. Memory management systems, among other operations, also handle the moving of information between these two levels of memory.


Memory management in OS/360 and successors

IBM
System/360 The IBM System/360 (S/360) is a family of mainframe computer systems that was announced by IBM on April 7, 1964, and delivered between 1965 and 1978. It was the first family of computers designed to cover both commercial and scientific applica ...
does not support virtual memory. Memory isolation of
jobs Jobs may refer to: * Job, an activity that people do for regular income gain People * Steve Jobs (1955–2011), co-founder and former CEO of Apple Inc ** Steve Jobs (disambiguation) * Laurene Powell Jobs (born 1963), widow of Steve Jobs * Lisa ...
is optionally accomplished using protection keys, assigning storage for each job a different key, 0 for the supervisor or 1–15. Memory management in
OS/360 OS/360, officially known as IBM System/360 Operating System, is a discontinued batch processing operating system developed by IBM for their then-new System/360 mainframe computer, announced in 1964; it was influenced by the earlier IBSYS/IBJOB ...
is a
supervisor A supervisor, or lead, (also known as foreman, boss, overseer, facilitator, monitor, area coordinator, line-manager or sometimes gaffer) is the job title of a lower-level management position that is primarily based on authority over workers or ...
function. Storage is requested using the GETMAIN macro and freed using the FREEMAIN macro, which result in a call to the supervisor ( SVC) to perform the operation. In OS/360 the details vary depending on how the system is generated, e.g., for PCP, MFT, MVT. In OS/360 MVT, suballocation within a job's ''region'' or the shared ''System Queue Area'' (SQA) is based on ''subpools'', areas a multiple of 2 KB in size—the size of an area protected by a protection key. Subpools are numbered 0–255. Within a region subpools are assigned either the job's storage protection or the supervisor's key, key 0. Subpools 0–127 receive the job's key. Initially only subpool zero is created, and all user storage requests are satisfied from subpool 0, unless another is specified in the memory request. Subpools 250–255 are created by memory requests by the supervisor on behalf of the job. Most of these are assigned key 0, although a few get the key of the job. Subpool numbers are also relevant in MFT, although the details are much simpler. MFT uses fixed ''partitions'' redefinable by the operator instead of dynamic regions and PCP has only a single partition. Each subpool is mapped by a list of control blocks identifying allocated and free memory blocks within the subpool. Memory is allocated by finding a free area of sufficient size, or by allocating additional blocks in the subpool, up to the region size of the job. It is possible to free all or part of an allocated memory area. The details for
OS/VS1 Operating System/Virtual Storage 1, or OS/VS1, is a discontinued IBM mainframe computer operating system designed to be run on IBM System/370 hardware. It was the successor to the OS/360 and successors#MFT, Multiprogramming with a Fixed number of ...
are similar to those for MFT and for MVT; the details for
OS/VS2 Operating System/Virtual Storage 2 (OS/VS2) is the successor operating system to OS/360 MVT in the OS/360 OS/360, officially known as IBM System/360 Operating System, is a discontinued batch processing operating system developed by IBM for thei ...
are similar to those for MVT, except that the page size is 4 KiB. For both OS/VS1 and OS/VS2 the shared ''System Queue Area'' (SQA) is nonpageable. In
MVS Multiple Virtual Storage, more commonly called MVS, was the most commonly used operating system on the System/370 and System/390 IBM mainframe computers. IBM developed MVS, along with OS/VS1 and SVS, as a successor to OS/360. It is unrelated ...
the address space includes an additional pageable shared area, the ''Common Storage Area'' (CSA), and an additional private area, the ''System Work area'' (SWA). Also, the storage keys 0-7 are all reserved for use by privileged code.


See also

*
Dynamic array In computer science, a dynamic array, growable array, resizable array, dynamic table, mutable array, or array list is a random access, variable-size list data structure that allows elements to be added or removed. It is supplied with standard lib ...
*
Garbage collection (computer science) In computer science, garbage collection (GC) is a form of automatic memory management. The ''garbage collector'' attempts to reclaim memory which was allocated by the program, but is no longer referenced; such memory is called '' garbage''. ...
*
Out of memory Out of memory (OOM) is an often undesired state of computer operation where no additional memory can be allocated for use by programs or the operating system. Such a system will be unable to load any additional programs, and since many programs ...
*
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, area, or memory context, is a collection of allocated objects that ca ...


Notes


References

; OS360Sup : ; OSVS1Dig :


Further reading

*
Donald Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
. ''Fundamental Algorithms'', Third Edition. Addison-Wesley, 1997. . Section 2.5: Dynamic Storage Allocation, pp. 435–456.
Simple Memory Allocation Algorithms
(originally published on OSDEV Community) * * * *


External links


"Generic Memory Manager" C++ library

Sample bit-mapped arena memory allocator in C

TLSF: a constant time allocator for real-time systems

Slides on Dynamic memory allocation



The Memory Management Reference
:


Linux Memory Management

Memory Management For System Programmers

VMem - general malloc/free replacement. Fast thread safe C++ allocator


{{Authority control Computer architecture