Hard real-time systems are characterized by their predictability. Such systems are guaranteed to perform intended action in a specified time interval. For example, a car airbag unit will deploy within 55 milliseconds even in the worst of system load. Even though hard-real time systems are not the fasted option available in the market but the guarantee of predictability is the reason why hard real-time systems are used in safety-critical industries. Where ever reliability and predictability are required we will find hard real-time systems deployed in such systems.
C++ and Predictability
From the point of view of predictability, C++ is a very good choice for developing applications and firmware. C++ is being used in embedded as well as non-embedded applications. C++ is already in use where real-time performance and flexibility of high-level language are needed. C++ is being in use in different industries from safety-critical from avionics to the medical domain. Having said that, C++ is not perfect considering its wider application in different sectors. Most of the facilities in the C++ language are predictable, including virtual function calls, but there are a few aspects that are not predictable. Those are
Free store (heap) allocation using new and delete
Exceptions
Dyamic_cast
Usually, these facilities are prohibited in hard real-time applications. For example, coding standard JSF++ strictly prohibits the usage of exception and free store in C++ codebase used in a fighter aircraft application. Due to the unpredictability of free stores, standard library std::string and containers like std::vector, std::map, etc should be prohibited as these facilities internally use new and delete, which make them unpredictable as well.
Similarly, the problem with exceptions is that when looking for a particular throw, the programmers can not know how long does it will take to find a matching catch or whether there is a catch block in code or not. This problem could be dealt with by a tool that can give details of how much time it takes for each throw in the codebase. Since this is still a research topic and considering hard real-time constraints, it's better to avoid exceptions and utilize a return code-based approach to detect and/or correct exception scenarios.
Problems with dynamic memory allocation
Dynamic memory allocation is usually banned or severely restricted in embedded systems and the main reasons are:
Predictability
Free store allocation is not predictable i.e it is not guaranteed to be constant time operation. In many implementations of new, the time needed to allocate new objects can increase dramatically after a few objects are deallocated and allocated.
Fragmentation
The free store has a limited size and it may get fragmented after allocating and deallocating objects. After allocation and deallocation of objects, it may happen some unused memory or space is left out. These unused holes or spaces in the heap are called memory fragmentation. Since these holes are small, such memory location could not be used to store new objects leading to wastage of memory space, and over time total usable free store is far less than the initial available free store.
The problem is not with new but the use of new and delete together, which results in a series of allocation and deallocation. Let's try to understand this issue with the help of a small example.
Message* get_data(Device&); // make a Message on the free store// snippet of usage part
while(condition_true)
{
Message* p = get_data(dev);
// some operation
Node* n1 = new Node(arg1,arg2);
// some operation
delete p;
Node* n2 = new Node (arg3,arg4);
// some operation
}Looking at the pseudo-code we might expect each loop iteration will consume 2*sizeof(Node) bytes of memory (plus free store overhead). Unfortunately, it is not guaranteed that the consumption or memory will be restricted to 2*sizeof(Node) bytes. If we consider Message is a bit large than Node, we could visualize memory utilization something like shown in the below image. Each white space denotes a memory hole.
So our above example is leaving behind some unused spaces on free store each time we execute the loop. Even though these unused spaces are only a few bytes long, we can not use these holes and it would be as bad as a memory leak. This is a serious problem for
essentially all long-running programs that use new and delete extensively; it is not uncommon to find unusable fragments taking up most of the memory.
This will dramatically increase the time needed to allocate memory on the free store as new has to search through the objects and fragments for a suitably sized chunk of memory. Couple this behavior with the hard real-time system requirements, we can easily conclude why the usage of the free stores i.e. new and delete are prohibited or restricted.
Alternatives to the general free store
Memory fragmentation occurs only when delete is used with new. So one of the workarounds could be banning delete which will ensure no memory holes and hence new operations would take the same amount of time. It may work in common implementation but it is not guaranteed by C++ standards. Another alternative could be to set aside global (static) memory for future usage but due to programing structure and other constraints, it's better to avoid global.
Let's look at two data structures that are particularly useful for predictable memory allocation.
Stacks
A stack is a data structure where you can allocate an arbitrary amount of memory (up to a given maximum size) and deallocate the last allocation (only); that is, a stack can grow and shrink only at the top. There can be no fragmentation because there can be no “hole” between two allocations. We can implement a stack using templated class as below.
template<int N>
class Stack // stack of N bytes
{
public:
Stack(); // make an N-byte stack
void* get(int n); // allocate n bytes from the stack;
// return 0 if no free space
void free(); // return the last value returned by get()
//to the stack
int available() const; // number of available bytes
private:
// space for char[N] and data to keep track of what is allocated
// and what is not (e.g., a top-of-stack pointer)
};Pools
A pool is a collection of objects of the same size. We can allocate and deallocate objects as long as we don’t allocate more objects than the pool can hold. There can be no fragmentation because all objects are of the same size. We can implement pool using templated class as below.
template<typename T, int N>
class Pool // Pool of N objects of type T
{
public:
Pool(); // make pool of N Ts
T* get(); // get a T from the pool; return 0 if no free Ts
void free(T*); // return a T given out by get() to the pool
int available() const; // number of free Ts
private:
// space for T[N] and data to keep track of which Ts are allocated
// and which are not (e.g., a list of free objects)
};Conclusion
From our short example, we've tried to understand why certain C++ facilities should be avoided in embedded or hard real-time systems and discussed other alternatives to such facilities which we can use to develop our application.
Comments