The Basics of Application Memory Management

Photo by Liam Briese on Unsplash

Have you ever wondered how memory is managed for a computer program? Perhaps you are new to programming, or have just started learning about memory, or maybe you’ve been programming for a while and would like a refresher … In any case, I hope this article will be able to satisfy your curiosity, as it explores a small fraction of the world of memory management (from a high-level perspective) with application memory management as its main focus.

ARTICLE CONTENT

Before we go into more detail about application memory management, we’ll cover some absolute basics, namely:

• What Is Memory?
• What Is The Memory Hierarchy?
• What Is A Program?
• How Is Machine Code Generated?
• How Does A Program Execute?
• Where Does The Program Get Stored?
• What is Primary Memory?
• What is Stack and Heap Memory?

And finally, we’ll dive into:

• How is Application Memory Managed?
• Manual Allocation Memory Management (MAMM)
• Automatic Allocation Memory Management (AAMM)
• AAMM Algorithms

WHAT IS THE MEMORY HIERARCHY?

The memory hierarchy categorises memory devices based on their response times (access time). This hierarchy is usually used in computational theory and hardware design. Figure 1 depicts how the hierarchy is organised and it illustrates the differences among the memory types in terms of: speed, cost and capacity/volume.

If you would like to learn more about memory hierarchy, I would recommend checking this out: https://www.tutorialspoint.com/what-is-memory-hierarchy.

Figure 1: Memory Hierarchy

WHAT IS A PROGRAM?

A program is simply a list of instructions that are written in machine language and each machine language instruction is stored as a binary sequence. There are different types of machine languages and each machine language is compatible with its specific operating system. For example: a Windows operating system will not natively be able to understand Linux machine language.

HOW IS MACHINE CODE GENERATED?

Compilers are responsible for transforming source code into machine code. They transform source code into object code. The object code is usually an intermediary object between source code and machine code. The object code is either similar to or the same as machine language. The object code is then transformed into machine language by means of assemblers, linkers, binders or loaders.

There is another way in which source code is transformed, and this is by an interpreter. The main difference between a compiler and an interpreter is that a compiler looks at the whole code and reorganises instructions, whereas an interpreter looks at and executes one line of code at a time.

HOW DOES A PROGRAM EXECUTE?

First, a program has to be loaded.

• For a program to be executed, its executable binaries and all its related resources (e.g. images and dlls) must be loaded from a hard-disk into RAM by a program loader.

Basically, the responsibilities of a loader are to:

• Prepare a program for execution by the operating system.
• To validate program requirements (e.g. memory and permissions)
• Load necessary resources.
• Copy required command-line arguments into stack memory.
• Link the entry-point of the program and other libraries.
• Initialise registers.
• Program loaders are usually a part of operating systems, however, this is not the case with Embedded systems. Embedded systems do not typically have program loaders and programs are executed from ROM,

After the program has been loaded, the loader hands over control by directing the CPU to the first instruction of the program, and then the program runs.

WHERE DOES ALL MY PROGRAMMING DATA GET STORED?

As previously mentioned, the executing program is stored in the primary memory, which is also known as the main memory. More specifically though, all variables, functions, parameters and the like are stored in stack or heap memory which is allocated in RAM segments within the primary memory. Figure 2 depicts, in a very simple manner, how the memory of a program looks after it has been loaded in RAM.

Figure 2: Memory Organisation of Running Program within RAM

WHAT IS PRIMARY MEMORY?

Primary memory has been mentioned a few times so far in this article, so next we’ll learn a bit more about this type of memory.

Primary memory is directly accessible by CPUs (processors) and it can be read from and written to quickly as shown in Figure 3. In the memory hierarchy, primary memory has a slower access compared to the access time of caches, but it has faster access time than that of secondary memory, as seen in Figure 1. In contrast, the storage capacity of primary memory is greater than that of caches, but it is less than that of secondary storage.

Figure 3: Memory to CPU Interaction

COMPOSITION:

In essence, Primary Memory is composed of RAM and ROM. Figure 4 shows some of the different subtypes of primary memory.

Figure 4: Types of Memory

CHARACTERISTICS:

· Physical electronic components that are used by an operating system to store information,

· Not disk storage,

· Limited,

· ROM is non-volatile and RAM is volatile,

· Execution memory, and

· Fast access.

WHAT IS STACK & HEAP MEMORY?

Stack memory is a region of memory that is allocated on contiguous blocks within RAM for a process. Furthermore it acts as a LIFO (last-in-first-out) buffer for data or instructions. So basically, if a variable is the last element in the stack, it will be the first to be removed when it is time for memory to be deallocated. Examples of data that are stored within the stack are: local variables, functions and pointer variables.

Heap memory, like stack memory, is allocated within RAM. It is used for dynamic memory allocation and can be likened to a free pool. Complex data is stored here, such as: global variables, reference types, strings and maps.

STACK & HEAP MEMORY MANAGERS

Stack memory allocation and deallocation is managed by the operating system.

Whereas, heap memory allocation and deallocation is either managed automatically by something like garbage collectors, or manually by low-level programmers — if they use dynamic programming.

STACK & HEAP CAPACITY

• The capacity of the stack remains static while the program executes.
• Stack capacity is calculated prior to the execution of the program.
• The stack usually has a much lower capacity than the heap.
• Heap memory is not set to a fixed size and is physically limited by the RAM device.

STACK & HEAP SPEED

Stack memory has faster access time than heap memory. This is because stack memory is linear in structure and heap memory uses pointers that have to be looked up which may not necessarily be in the nearest block.

STACK & HEAP COMMON ERRORS

• One common error that developers run into is the stack overflow error. It occurs when the stack memory capacity is exceeded.
• Another common error that relates to heap memory is the fragmentation error. This occurs when there is enough heap space memory, but the blocks of memory are not big enough for the requested size. If a computer runs out of primary memory, the operating system will crash, so it is important to manage the heap memory efficiently.

HOW IS APPLICATION MEMORY MANAGED?

Application memory management deals with the allocation and deallocation of memory for program objects and data structures.

MEMORY ALLOCATION

Memory allocation is the process of assigning blocks of memory on request. The memory allocator is responsible for handling this process.

More about the process:

When a program is launched, the memory allocator receives a few large blocks of memory (RAM) from the operating system. The memory allocator then divides this memory into smaller blocks to satisfy memory allocation requests.

There are various memory allocation techniques used by the allocators, namely:

• First fit,
• Buddy system,
• Sub-allocators

MEMORY DEALLOCATION

When a program no longer requires some memory, it can either be freed for reuse automatically or manually — where a programmer defines where, when, and what should be deallocated.

MANUAL APPLICATION MEMORY MANAGEMENT (MAMM)

With manual memory management, when a programmer wants to use dynamic programming, they have to allocate and deallocate memory using pointers. For example in C and C++, the keywords: malloc, realloc, calloc and free are often used.

A commonly encountered problem, as a result of manually managing memory, are memory leaks. One strategy of avoiding this issue (and similar ones) is to use structures/classes and ensure that their constructors allocate memory and their destructors deallocate memory. The name of this strategy is Resource Acquisition is Initialisation (RAII).

Advantages of MAMM:

• It enables programmers to understand exactly what is going on w.r.t. memory allocation/deallocation.
• Applications can perform better (especially when there are tight memory restrictions).
• It enables programmers to have more control over the memory resources, and optimise system performance (e.g. game engines are often written in c++ and c).

Disadvantages of MAMM:

• Repetitive code (bookkeeping of memory).
• Memory management must form a significant part of any module interface.
• Requires more memory overhead per object.
• Bugs are common.

AUTOMATIC APPLICATION MEMORY MANAGEMENT (AAMM)

Although manual memory management seems simple, it can easily get complicated and in general, it is error prone and difficult to debug. The alternative, automatic memory management, is nowadays becoming more popular, as the newer, more modern and higher-level programming languages do not require developers to manage the memory of their applications.

What Is it?

• It is a service, a part of or an extension of a programming language.
• It recycles/deallocates blocks that are not reachable from the program.
  - Unreachable objects or memory once had pointers keeping track of them, but no longer do and they have not been freed for reuse.

By definition, object X is reachable if and only if:
- A register contains a pointer to X, or
- Another reachable object Y contains a pointer to X.

• Garbage collection is one of the most common methods of automatic memory management.
• It runs at certain intervals and these intervals introduce an overhead. This overhead is called a pause time.

Advantages of AAMM:

• Programmers don’t have to worry about managing memory.
• Programmers can spend more time working on the actual problem.
• AAMM is more beginner friendly than MAMM.
• Module interfaces tend to be cleaner.
• Fewer bugs.
• The efficiency of AAMM is generally on par with MAMM when there is a large amount of memory available.

Disadvantages of AAMM:

• Memory may be retained, as it may be reachable, but it’s not used.
• Limited availability — not every programming language supports AAMM.
• Overhead.

AAMM ALGORITHMS:

There are various garbage collection algorithms that help with the automatic memory management. In this section, we will discuss the popular mark-and-sweep algorithm, as well as the reference count algorithm.

For any garbage collection algorithm, two basic operations must be performed:

· The first operation is the detection of unreachable objects.

· The second operation is the release of unreachable objects.

Garbage Collection: Mark and Sweep

The Mark and Sweep is a two phase algorithm:

1. The Mark phase (trace)

• As objects are created, their mark bit flag is set to false or zero.
• During the phase, the mark bit of all reachable objects is set to true (one).

The following pseudo code shows what happens during the mark phase:

1. todo <- {all roots}
2.   While todo is not null do
3.       Pick block in todo
4.       todo <- todo – {block}
5.       If ismarked(block) = 0 then
6.           Mark(block) <- 1
7.           References <- references in block
8.           Todo <- todo union references
9.       End if
10. End while

2. The Sweep phase (collect)

• During the sweep phase, the garbage collector scans the entire heap searching for unreachable objects (mark bit == 0) and releases their memory.
• After cleaning the memory, it then reset each reachable objects mark bit back to false or zero.

The following pseudo code shows what happens during sweep phase:

1.  p <- bottom of heap
2.  While p < top of heap do
3.      If mark(p) = 1 then
4.          Mark(p)
5.      Else
6.          Add block p... (p+sizeof(p)-1) to free list
7.      End if
8.      p <- p + sizeof(p)
9.  End while

Figure 5 is a visual example of the mark and sweep algorithm. The blue blocks represent used memory and the green blocks represent free memory.

Figure 5: Mark and Sweep Example

Advantages:

• It handles cases of cyclic references and never ends up in an infinite loop.
• Objects are not moved, so there is no additional overhead.

Disadvantages

• While the garbage collector runs its algorithm, the normal program execution is paused.
• The algorithm runs through the whole heap.
• The algorithm must run to completion (atomic), or else it will rerun.
• The algorithm may cause the heap memory to fragment.

GARBAGE COLLECTION: REFERENCE COUNTING

This algorithm is relatively simple and has to do, as its name implies, with counting the number of reference pointers of each allocated object.

Essentially, each object contains a reference count and this count is incremented for each new reference and it is decremented if a reference is overwritten or the referencing object is freed. When the count reaches zero, the memory is freed.

Figure 6 and 7 below demonstrate how reference counting works in two different situations:

Figure 6: Reference Counting Example with No Cycles

Figure 7: Reference Counting Example with Cycle

Advantages:

• Simple.
• There are no large pauses, as garbage is collected incrementally.

Disadvantages:

• The main disadvantage with the reference counting algorithm is that it is not able to handle cyclic references, in other words, it is not able to reclaim cyclic storage.
• Difficult to implement efficiently.

Interesting Fact: PHP, Perl and Python use reference counting alongside some other algorithms to overcome the cycling referencing issue.

Thank you for reading this article. I hope you found it helpful. If you have any feedback, please leave a comment.

REFERENCES

https://web.stanford.edu/class/cs101/software-1.html

https://cementanswers.com/what-is-resource-allocation-in-operating-system/

https://isaaccomputerscience.org/concepts/sys_os_resource_management?examBoard=all&stage=all

https://isaaccomputerscience.org/concepts/sys_os_memory_management?examBoard=all&stage=all

https://www.techopedia.com/definition/8104/loader

https://embeddedartistry.com/fieldmanual-terms/program-loader/

https://www.geeksforgeeks.org/loader-in-c-c/

https://sites.harding.edu/dsteil/150/notes/compilers.htm

https://everythingwhat.com/how-are-programs-loaded-into-memory

https://people.cs.rutgers.edu/~pxk/416/notes/09-memory.html

https://math.hws.edu/eck/cs124/javanotes6/c1/s1.html

https://www.quora.com/How-a-program-is-loaded-into-memory-and-then-executed

https://www.sciencedirect.com/topics/engineering/stack-memory

https://www.javatpoint.com/stack-vs-heap-java

https://opendsa-server.cs.vt.edu/ODSA/Books/CS2/html/HeapMem.html

https://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap

http://www.maxi-pedia.com/what+is+heap+and+stack

https://icarus.cs.weber.edu/~dab/cs1410/textbook/4.Pointers/memory.html

Lecture 23: Memory Organization and Garbage Collection

🚀 Demystifying memory management in modern programming languages

Reference Counting - A Quick Primer on Garbage Collection Algorithms

https://lambda.uta.edu/cse5317/notes/node47.html

https://www.researchgate.net/publication/326369017_From_Manual_Memory_Management_to_Garbage_Collection

https://computerscience.chemeketa.edu/cs160Reader/ComputerArchitecture/MemoryHeirarchy.html

https://www.techtarget.com/searchstorage/definition/RAM-random-access-memory

Fig. 1 Typical structure of a computer memory hierarchy.

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80.4938&rep=rep1&type=pdf

How Important is Memory Management When Learning to Code?

Random Access Memory (RAM) and Read Only Memory (ROM) - GeeksforGeeks

https://www.memorymanagement.org/