Memory management

This is critical to any advanced computer system where more than a single process might be underway at any time.

The quality of the virtual memory manager can have an extensive effect on overall system performance.

The task of fulfilling an allocation request consists of locating a block of unused memory of sufficient size.

The specific dynamic memory allocation algorithm implemented can impact performance significantly.

A study conducted in 1994 by Digital Equipment Corporation illustrates the overheads involved for a variety of allocators.

[1] Since the precise location of the allocation is not known in advance, the memory is accessed indirectly, usually through a pointer reference.

This works well for simple embedded systems 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 and deallocation, and so it is often used in video games.

Many Unix-like systems as well as Microsoft Windows implement a function called alloca for dynamically allocating stack memory in a way similar to the heap-based malloc.

A compiler typically translates it to inlined instructions manipulating the stack pointer.

[6] Although there is no need of manually freeing memory allocated this way as it is automatically freed when the function that called alloca 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 _malloca, which reports errors, exists on Microsoft Windows.

[7] gnulib provides an equivalent interface, albeit instead of throwing an SEH exception on overflow, it delegates to malloc when an overlarge size is detected.

The automatic allocation of local variables makes recursion possible, to a depth limited by available memory.

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.

Whenever a new pointer points to a piece of memory, the programmer is supposed to increase the counter.

Some reference counting systems require programmer involvement and some are implemented automatically by the compiler.

Each allocated block is managed by means of a segment descriptor,[12] a special control word containing relevant metadata about the segment including address, length, machine type, and the p-bit or ‘presence’ bit which indicates whether the block is in main memory or needs to be loaded from the address given in the descriptor.

Descriptors themselves are protected control words that cannot be manipulated except for specific elements of the MCP OS (enabled by the UNSAFE block directive in NEWP).

Donald Knuth describes a similar system in Section 2.5 ‘Dynamic Storage Allocation’ of ‘Fundamental Algorithms’.

User Application Operating system Hardware
An example of external fragmentation