logo slogan

Safety Critical Applications benefit from Embedded Databases


In memory database management systems can provide both deterministic timing and the controls needed for safe memory allocation – both essential for safety critical systems.


Chris Hills, Phaedrus Systems

 

Any system has to handle data. Input data from sensors, human interfaces or other systems has to correlated, merged or compared across all data objects and across time, for filtering or analysis and to trigger actions. And database management systems (DBMS) are designed to carry out just this work. But traditionally the DBMS runs on a hard disk, is large, complex, slow and non-deterministic. And for safety critical systems, time is a major issue, since they are normally also real-time systems.


Time dependent


For real-time applications the state of the data in the database has to be as close to the state of the real world as is required by the application (hard real-time is more demanding than soft real-time). Traditional databases are designed for maximising throughput, with performance measured in transactions per time unit. For real-time applications, however, an important measure is normally the number of transactions that violate the timing constraints: that is transactions that are not completed within a pre-determined deadline. Depending on the environment that the system is working in, the cost of missing this deadline will vary. A third time element is predictability: measures of average response times are adequate in non real-time databases, but for real-time responses have to be predictable to guarantee the completion of time-critical transactions.


To meet these constraints, a real-time database has to avoid using components that introduce unpredictable latencies, such as disk I/O operations, message passing or garbage collection. Instead of disks, a real-time database is best implemented as an in-memory system. There is no disk, so no disk I/O, and a simpler design than conventional databases minimises message passing.


Since the data in the database has to represent the real world, and the data may be compromised if it is not updated fast enough to reflect real-world events, the DBMS transaction manager has to be aware of time or, at the very least, should provide some way of prioritising the transactions.


A softer approach


Off-the-shelf databases are suitable for the majority of real-time systems, generally called soft real-time, where violation of timing constraints results in degraded quality but is to some degree tolerable. Unlike the hard real-time systems, soft real-time systems can be event-driven and priority scheduled. It is in this area that recently there has been a growth in innovation in creating commercially available Real Time Database Systems (RTDBS) designed to run on off-the-shelf hardware and other elements.


Complex soft real-time systems need databases to support concurrent data access and provide well-defined interfaces between software modules, while supporting levels of performance and predictability lacking in traditional databases. The traditional databases are disk-based and cannot achieve predictable response times in the microseconds or milliseconds range. A main-memory databases, or an in-memory database systems (IMDS) can achieve this predictability and main-memory DBMS are at the heart of real-time databases. They take advantage of the research and development in main-memory database theory and implementation that has been undertaken since the mid-eighties. They also exploit inexpensive memory and the use of 64-bit addressing that have become common in embedded systems.


Memory allocation


Another issue is memory allocation. Application developers often don’t know how much memory program variables will require. Declaring memory prior to compilation means estimating: underestimating constrains he application and overestimating wastes memory. While C and C++ use dynamic memory allocation to hand over memory as needed, freeing this memory is not always carried out successfully. This can mean unused memory is not available for allocation (memory leaks) or the memory that is available is scattered in small sections, none of which is big enough to be usable (memory fragmentation). The problems of freeing memory after use can introduce unpredictability and make applications unstable – neither desirable characteristics of a safety critical application. In fact dynamic memory allocation is actually prohibited by DO178-B.


There is another way to solve the problem, using a custom allocator for the applications that sets aside a buffer for the exclusive use of that task, and satisfies all memory allocation requests out of that buffer. If the memory reserved for this buffer is exhausted, the application is informed, and can then free up memory within the buffer or find more memory to devote to the task. Exhausting the memory in this dedicated pool has no impact on other parts of the system.


The customer allocator can use one of several techniques to manage the memory: for example block allocation, where a block of memory is divided into equal sized pieces. A requirement for memory is assigned a piece. If there are no pieces left, another block is used. As pieces become free they are available for further use. Since the pieces are all the same size, memory fragmentation is not an issue.


For more flexibility, it would be possible to create several blocks, with different sized pieces in each block, so that piece allocation would match closely the application memory requirement.


Instead of creating the custom allocator an alternative would be to use third party code. Since we are talking about in-memory IMDSs obviously we feel that this task can be carried out by an IMDS, and specifically the McObject eXtremeDB IMDS, in-memory database system (IMDS), which was designed to operate in resource-constrained embedded systems, with efficient custom algorithms for allocating precious memory and no reliance on the general-purpose C runtime allocator


How it works


With eXtremeDB, the programmer defines a class or classes in a database schema file, and pre-processes the file with a schema compiler that produces a .C and a .H file. The .H file contains type definitions (typedefs) and function prototypes for working with the defined classes. For example, the code might defines a class called Sensor and declares an instance of Sensor (theSensor) in the function body, along with a variable to hold return codes, and a handle to a transaction. 


If the program that uses malloc/free is multi-threaded and threads will share the Sensor object, the developer must implement concurrency control to regulate access to that object. With an in-memory database, concurrency control is automatic: interaction is carried out in the context of a database transaction, which guarantees atomicity (everything within the scope of the transaction succeeds or fails together) and isolation (transactions execute separately).


Upon beginning a transaction, the program calls Sensor_new(), which creates space in the in-memory database for a new Sensor object. The arguments are the transaction handle returned from mco_trans_start and the address of a handle to a Sensor object. This is the functional equivalent of malloc() in the C program.


Unlike malloc(), Sensor_new() returns a handle to an object in the database. So whereas the C program works directly with the structure’s member fields, the eXtremeDB-based program works through the interfaces generated by the schema compiler, for instance Sensor_s_id_put() and Sensor_sub_nbr_put().
When the C program is finished with the Sensor structure, free() returns memory to the heap. When the eXtremeDB-based program is finished, the space in the database is relinquished by the call to Sensor_delete(), which passes in the handle of the object to be removed from the database, and ends the transaction (mco_trans_commit()). (Both examples omit error handling, for brevity.)


While the database, like the program as a whole, can run low on memory, this would result in a “database full” error message that can be dealt with programmatically, rather than the much more dangerous and unpredictable scenario of heap memory fragmentation and leakage—which is obviously unacceptable in safety-critical military systems. Meanwhile, the allocation/de-allocation accomplished by the IMDS relies on custom allocators optimized for the given pattern of allocation.


The custom allocators work with memory that was dedicated to the in-memory database, but eXtremeDB doesn’t care how the memory is obtained. It could be global memory, heap memory, or in a flat memory model architecture (such as VxWorks 5.5), just a dedicated region of memory in a fashion similar to a video buffer or keyboard buffer. Using the IMDS retains the advantages of dynamic memory allocation while avoiding the DO-178B proscription on it.  


A commercial database


McObject’s eXtremeDB is an example of a database designed from the ground up for real-time embedded systems. The design was driven by the need to eliminate performance overhead while providing a predictable and reliable transactional model for applications such as telecommunications equipment, factory floor automation systems, process control, zero-latency consumer electronics devices, and medical equipment. Unlike traditional systems it has a very small code foot-print – typically less than 100K in RAM.
eXtremeDB maps its database directly into the application’s address space, providing applications with direct pointers to the data elements, eliminating expensive buffer management. A data element takes only a three stage journey from database to application, in contrast to a traditional database where the journey can include as many as six stages, each with its own variable latency. Access to data is further improved as the associated access structures are placed on the application’s stack.


Runtime code is directly linked with the application, eliminating remote procedure calls, and the execution path generally requires just a few CPU instructions. To improve still further the predictability and performance of database read and write operations, eXtremeDB never relies on the operating system’s memory management and instead uses its own highly optimized memory manager that is responsible for all allocations and de-allocations made by the database. As the database is in main-memory, there is no bottleneck created by paging data in and out during I/O operations.


One of the important facets of a database is it interfacing to the rest of the world.  eXtremeDB has SQL and ODBC interfaces as well as two APIs. One API static and the other is a dynamic navigational API that can be configured to fit closely to the application. It also has optional XML extensions for retrieving XML objects from external source, creating them in the database, and generating an XML schema for each class in the database.


eXtremeDB does not require an operating system, running happily on bare bones boards, but if an operating system is available, eXtremeDB can take advantage of it. It is currently available on many embedded platforms, including VxWorks, Integrity, QNX, real-time Linux distributions, Lynx, Windows embedded, eCos, Nucleus and others. And it can be run on server and desktop platforms, such as Sun Solaris, HP-UG, SGI Altix, Linux distribution and Classic Windows platforms. It is comfortable with most development environments, from the gnu tool chain through to Tornado, QNX Momentics, Metrowerks’ CodeWarrior, GreenHills’ Multi and Microsoft’s Visual Studio.


Fits the task


Database systems are designed to manage persistent data shared among multiple tasks and are built so that transactions maintain the ACID (Atomicity, Consistency, Isolation and Durability) of data. Real-time systems add temporal characteristics. In the majority of real-time systems, expired or missed transactions do not lead to catastrophic consequences, they simply have no value. For these soft real-time systems modern commercial main-memory database technology such as McObject’s eXtremeDB, can provide an effective solution.


It used to be unusual to buy an RTOS: in-house development was the way to go. Now there is a range of RTOSs available to match specific requirements, allowing developers to concentrate on the differentiating features of their application. With the increasing availability of real-time databases, the same changes are taking place for all except the hardest of hard real-time systems.


Chris Hills is founder and CTO of Phaedrus Systems Limited, a specialist in high integrity and safety critical domains. His experience covers a wide range of applications.