Automatic Memory Management

AUTOMATIC MEMORY MANAGEMENT

Olexandr Kovalchuk

National Technique University of Ukraine Kyiv Polytechnic Institute; Faculty of the Informatics and Computer Techniques

 

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 free it for reuse when no longer necessary.

Memory management is usually divided into three areas: hardware, operating system, and application, although the distinctions are fuzzy.

Memory management at the hardware level is concerned with the electronic devices that actually store data. This includes things like random access memory and memory caches.

In the operating system, memory management is the functionality which handles or manages primary memory. Memory management keeps track of each end every memory location either it is allocated to some process or it is free. It checks how much memory is to be allocated to processes. It decides which process will get memory at what time. It tracks whenever some memory gets freed or unallocated and correspondingly it updates the status.

Application memory management involves supplying the memory needed for a program’s objects and data structures from the limited resources available, and recycling that memory for reuse when it is no longer required.

Application memory management combines two related tasks: allocation and recycling.

Allocation is subdividing the large blocks that the memory manager receives from the operating system into blocks suitable to the applications.

Recycling. When memory blocks have been allocated, but the data they contain is no longer needed by the program, the blocks can be recycled for reuse.

There are two types of application memory management: manual memory management and automated memory management. Sometimes the third type is distinguished: the garbage collection, but in general, garbage collection is a form of automatic 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 supported manual memory management.

Despite of the automated memory management system existence, all programming languages use manual techniques to determine when to allocate a new object from a free store. The main feature of the manual memory management is the direct control over when memory may be recycled. The memory manager does not recycle any memory without instruction to do that.

Automatic memory management is a general term for techniques that automatically recycle unused memory. Automatic memory managers usually do their job by recycling blocks that are unreachable from the program variables. Automatic memory management systems are often called garbage collectors, but that’s not correct. Garbage collector is a form of the automatic memory management system. But there are automatic memory managers that are different from garbage collectors (C++ RAII idiom).

There are many ways of performing automatic recycling of memory:

  • Tracing collectors
    • Mark-sweep collection
    • Copying collection
    • Incremental collection
    • Conservative collection
    • Reference counts
      • Simple reference counting
      • Deferred reference counting
      • One-bit reference counting
      • Weighted reference counting

Automatic memory managers that follow pointers to determine which blocks of memory are reachable from program variables are known as tracing collectors.

A reference count is a count of how many references there are to a particular memory block from other blocks. It is used as the basis for some automatic recycling techniques that do not rely on tracing.

The mark-and-sweep algorithm was the first garbage collection algorithm to be developed that is able to reclaim cyclic data structures. The mark-and-sweep algorithm consists of two phases. In the first phase, it finds and marks all accessible objects. The first phase is called the mark phase. In the second phase, the garbage collection algorithm scans through the heap and reclaims all the unmarked objects. The second phase is called the sweep phase.

The idea of the copying collection is:

  • Two “semi-spaces“ (From-space and To-space)
  • Only From-space is “active“
  • At GC time, copy the live nodes from From-Space to To-Space
  • Then “flip“ the spaces

Some tracing garbage collection algorithms can pause in the middle of a collection cycle while the mutator continues, without ending up with inconsistent data. Such collectors can operate incrementally and are suitable for use in an interactive system. This type of the collectors are called incremental collectors.

Conservative garbage collectors are garbage collectors that work without compiler cooperation. For this reason they must discover pointers on their own.

In a simple reference counting system, a reference count is kept for each object. If a reference count falls to zero, then the object is no longer required and can be recycled.

In the deferred reference counting only references from other objects are counted, and references from program variables are ignored.

Another variation on reference counting, called one-bit reference counting, uses a single bit flag to indicate whether each object has either «one» or «many» references.

Weighted reference counting. Inter-process references to objects are counted, but instead of simply counting the number of references, each reference is given a weight.

Conclusion:

  • Memory management is the act of managing computer memory.
  • Memory management is usually divided into three areas: hardware, operating system, and application.
  • There are two types of application memory management: manual memory management and automated memory management.
  • There are many ways of performing automatic recycling of memory.

 

References

The article about garbage collection in memory management:

http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)

The article about manual memory management on Wikipedia:

http://en.wikipedia.org/wiki/Manual_memory_management

The article about programming idiom RAII:

http://en.wikipedia.org/wiki/RAII

Lecture about garbage collection:

http://people.cs.umass.edu/~emery/classes/cmpsci691st/scribe/lecture4-gc.pdf

Article “Data Structures and Algorithms with Object-Oriented Design Patterns in Java”:

http://www.brpreiss.com/books/opus5/html/page424.html

Article “The Memory Management Reference Beginner’s Guide. Recycling”:

http://www.memorymanagement.org/articles/recycle.html

Glossary:

http://www.memorymanagement.org/glossary/.html

Presentation “Copying Garbage Collection”:

http://www.ps.uni-saarland.de/courses/gc-ws01/slides/copying_gc.pdf

Article about memory management in the operating system area on tutorialspoint:

http://www.tutorialspoint.com/operating_system/os_memory_management.htm

 

PowerPoint Presentation — click to download

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>