Dynamic memory allocation is when an executing program requests that the operating system give it a block of main memory. The program then uses this memory for some purpose. Usually the purpose is to add a node to a data structure. In object oriented languages, dynamic memory allocation is used to get the memory for a new object.
The memory comes from above the static part of the data segment. Programs may request memory and may also return previously dynamically allocated memory. Memory may be returned whenever it is no longer needed. Memory can be returned in any order without any relation to the order in which it was allocated. The heap may develop "holes" where previously allocated memory has been returned between blocks of memory still in use.A new dynamic request for memory might return a range of addresses out of one of the holes. But it might not use up all the hole, so further dynamic requests might be satisfied out of the original hole.
If too many small holes develop, memory is wasted because the total memory used by the holes may be large, but the holes cannot be used to satisfy dynamic requests. This situation is called memory fragmentation. Keeping track of allocated and deallocated memory is complicated. A modern operating system does all this.
Dynamic Memory Allocation and Fragmentation in C and C++
In C and C++, it can be very convenient to allocate and de-allocate blocks of memory as and when needed. This is certainly standard practice in both languages and almost unavoidable in C++. However, the handling of such dynamic memory can be problematic and inefficient. For desktop applications, where memory is freely available, these difficulties can be ignored. For embedded - generally real time - applications, ignoring the issues is not an option.
Dynamic memory allocation tends to be nondeterministic; the time taken to allocate memory may not be predictable and the memory pool may become fragmented, resulting in unexpected allocation failures. In this session the problems will be outlined in detail and an approach to deterministic dynamic memory allocation detailed.
C/C++ Memory Spaces
Data memory in C and C++ as being divided into three separate spaces: -
Static memory
This is where variables, which are defined outside of functions, are located. The keyword static does not generally affect where such variables are located; it specifies their scope to be local to the current module. Variables that are defined inside of a function, which are explicitly declared static, are also stored in static memory. Commonly, static memory is located at the beginning of the RAM area. The actual allocation of addresses to variables is performed by the embedded software development toolkit: a collaboration between the compiler and the linker. Normally, program sections are used to control placement, but more advanced techniques, like Fine Grain Allocation, give more control. Commonly, all the remaining memory, which is not used for static storage, is used to constitute the dynamic storage area, which accommodates the other two memory spaces
Automatic variables
Variables defined inside a function, which are not declared static, are automatic. There is a keyword to explicitly declare such a variable – auto – but it is almost never used. Automatic variables (and function parameters) are usually stored on the stack. The stack is normally located using the linker. The end of the dynamic storage area is typically used for the stack. Compiler optimizations may result in variables being stored in registers for part or all of their lifetimes; this may also be suggested by using the keyword register.
Dynamic Memory in C
In C, dynamic memory is allocated from the heap using some standard library functions. The two key dynamic memory functions are malloc() and free().
The malloc() function takes a single parameter, which is the size of the requested memory area in bytes. It returns a pointer to the allocated memory. If the allocation fails, it returns NULL. The prototype for the standard library function is like this:
void *malloc(size_t size);
The free() function takes the pointer returned by malloc() and de-allocates the memory. No indication of success or failure is returned. The function prototype is like this:
void free(void *pointer);
There are two other variants of the malloc() function: calloc() and realloc().
The calloc() function does basically the same job as malloc(), except that it takes two parameters – the number of array elements and the size of each element – instead of a single parameter (which is the product of these two values). The allocated memory is also initialized to zeros. Here is the prototype:
void *calloc(size_t nelements, size_t elementSize);
The realloc() function resizes a memory allocation previously made by malloc(). It takes as parameters a pointer to the memory area and the new size that is required. If the size is reduced, data may be lost. If the size is increased and the function is unable to extend the existing allocation, it will automatically allocate a new memory area and copy data across. In any case, it returns a pointer to the allocated memory. Here is the prototype:
void *realloc(void *pointer, size_t size);
Memory, Cache, Registers
Computers have three locations for storing data - physical memory, cache, and registers. Memory is usually large compared with the other two types of storage. Each memory cell is accessed using an address, and the memory does not have to be consecutive. On various architectures, certain parts of the memory are used to access devices (this is called memory-mapped I/O). other parts of memory might not even be mapped into any physical memory at all.
Cache is a smaller version of memory, stored either directly in the CPU (level 1 cache), or on the motherboard (level 2 cache). It stores a copy of recently used parts of the main memory, in a location that can be accessed much faster. Usually, because the cache is hidden from our our programs by the hardware, we do not need only worry about the cache unless we're dealing with kernel.
Registers are storage units inside the CPU with very fast access. They can be accessed much faster than memory, and are often used to store data that is needed for a short calculation, such as contents of local variables in a function, or intermediate results of arithmetic calculations. the keyword register, when used when defining a local variable, can be a hint to the compiler to assign that variable to a register, rather than to a memory cell. Since modern compilers are well optimized, it might be better to let the compiler decide which variables should be kept in registers.
Sources of Memory Problems
The memory handling in C/C++ gives us a control as well as performance, but it comes with dangers: -
* Memory Leaks : - Memory leaks occur when data that are allocated at runtime but not deallocated once they are no longer needed. A program which forgets to deallocate a block is said to have a memory leak which may or may not be a serious problem. The result will be that the heap gradually fill up as there continue to be allocation requests, but no deallocation requests to return blocks for reuse. For a program which runs, computes something, and exits immediately, memory leaks are not usually a concern. Such a one shot program could omit all of its deallocation requests and still mostly work. Memory leaks are more of a problem for a program which runs for an indeterminate amount of time. In that case, the memory leaks can gradually fill the heap until allocation requests cannot be satisfied, and the program stops working or crashes.
Many commercial programs have memory leaks, so that when run for long enough, or with large data-sets, it will consume memory resource, and eventually it will slow down our machine because of page swapping. Then, we get failure with an out-of-memory error.
Finding those leaks with normal debugger is very tough because there is no clear faulty line of code.
Often the error detection and avoidance code for the heap-full error condition is not well tested, precisely because the case is rarely encountered with short runs of the program - that's why filling the heap often results in a real crash instead of a polite error message. Most compilers have a heap debugging utility which adds debugging code to a program to track every allocation and deallocation. When an allocation has no matching deallocation, that's a leak, and the heap debugger can help us find them.
* Buffer Overruns : - Buffer overruns occur when memory outside of the allocated boundaries is overwritten. We call it data corruption. This is nasty because it may not become visible at the place where the memory is overwritten. It may appear when we access that memory address, which can happen much later part of code. When it happens, our program behaves strangely because the memory location has wrong value.
* Uninitialized Memory : - Since C/C++ allows us to create variables without an initial value, we may try to read data not initialized. The memory allocation function malloc() and operator new do not the allocated memory.
* Incorrect Memory Management : - This can occur when we call free() more than once, access memory after freeing it, or free a memory block that was never allocated as shown in the code below:
Dynamic memory in C++
* The stack: All variables declared inside the function will take up memory from the stack.
* The heap: This is unused memory of the program and can be used to allocate the memory dynamically when program runs.
Programs need to dynamically allocate memory, for which the C++ language integrates the operators new and delete.
Operators new and new[]
Dynamic memory is allocated using operator new. new is followed by a data type specifier and, if a sequence of more than one element is required, the number of these within brackets []. It returns a pointer to the beginning of the new block of memory allocated. Its syntax is:
pointer = new type
pointer = new type [number_of_elements]
The first expression is used to allocate memory to contain one single element of type type. The second one is used to allocate a block (an array) of elements of type type, where number_of_elements is an integer value representing the amount of these.
There is a substantial difference between declaring a normal array and allocating dynamic memory for a block of memory using new. The most important difference is that the size of a regular array needs to be a constant expression, and thus its size has to be determined at the moment of designing the program, before it is run, whereas the dynamic memory allocation performed by new allows to assign memory during runtime using any variable value as size.
The dynamic memory requested by our program is allocated by the system from the memory heap. However, computer memory is a limited resource, and it can be exhausted. Therefore, there are no guarantees that all requests to allocate memory using operator new are going to be granted by the system.
C++ provides two standard mechanisms to check if the allocation was successful:
One is by handling exceptions. Using this method, an exception of type bad_alloc is thrown when the allocation fails. Exceptions are a powerful C++ feature explained later in these tutorials. But for now, you should know that if this exception is thrown and it is not handled by a specific handler, the program execution is terminated.
This exception method is the method used by default by new, and is the one used in a declaration like:
foo = new int [5]; // if allocation fails, an exception is thrown
The other method is known as nothrow, and what happens when it is used is that when a memory allocation fails, instead of throwing a bad_alloc exception or terminating the program, the pointer returned by new is a null pointer, and the program continues its execution normally.
This method can be specified by using a special object called nothrow, declared in header
foo = new (nothrow) int [5];
In this case, if the allocation of this block of memory fails, the failure can be detected by checking if foo is a null pointer:
int * foo;
foo = new (nothrow) int [5];
if (foo == nullptr) {
// error assigning memory. Take measures.
}
* operator new : - Allocate storage space (function )
* operator delete[] : - Deallocate storage space of array (function )
* nothrow : - Nothrow constant (constant )
* bad_alloc : - Exception thrown on failure allocating memory (class )
Example: -
// operator new[]
#include < iostream > // std::cout
#include < new > // ::operator new[]
struct MyClass {
int data;
MyClass() {std::cout << '*';} // print an asterisk for each construction
};
int main () {
std::cout << "constructions (1): ";
// allocates and constructs five objects:
MyClass * p1 = new MyClass[5];
std::cout << '\n';
std::cout << "constructions (2): ";
// allocates and constructs five objects (nothrow):
MyClass * p2 = new (std::nothrow) MyClass[5];
std::cout << '\n';
std::cout << "constructions (3): ";
// allocates storage for five objects, but does not construct them:
MyClass * p3 = static_cast
std::cout << '\n';
std::cout << "constructions (4): ";
// constructs five objects at p3, but does not allocate:
new (p3) MyClass[5];
std::cout << '\n';
delete[] p3;
delete[] p2;
delete[] p1;
return 0;
}
constructions (1): *****
constructions (2): *****
constructions (3):
constructions (4): *****
Operators delete and delete[]
In most cases, memory allocated dynamically is only needed during specific periods of time within a program; once it is no longer needed, it can be freed so that the memory becomes available again for other requests of dynamic memory. This is the purpose of operator delete, whose syntax is:
delete pointer;
delete[] pointer;
The first statement releases the memory of a single element allocated using new, and the second one releases the memory allocated for arrays of elements using new and a size in brackets ([]).
The value passed as argument to delete shall be either a pointer to a memory block previously allocated with new, or a null pointer (in the case of a null pointer, delete produces no effect).
// rememb-o-matic
#include < iostream >
#include < new > using namespace std;
int main ()
{
int i,n;
int * p;
cout << "How many numbers would you like to type? ";
cin >> i;
p= new (nothrow) int[i];
if (p == nullptr)
cout << "Error: memory could not be allocated";
else
{
for (n=0; n
cout << "Enter number: ";
cin >> p[n];
}
cout << "You have entered: ";
for (n=0; n
delete[] p;
}
return 0;
}
How many numbers would you like to type? 5
Enter number : 75
Enter number : 436
Enter number : 1067
Enter number : 8
Enter number : 32
You have entered: 75, 436, 1067, 8, 32,
Conclusions
C and C++ use memory in various ways, both static and dynamic. Dynamic memory includes stack and heap.
Dynamic behavior in embedded real time systems is generally a source of concern, as it tends to be non-deterministic and failure is hard to contain.
Using the facilities provided by most real time operating systems, a dynamic memory facility may be implemented which is deterministic, immune from fragmentation and with good error handling.
