Select Page

eXtremeDB/rt Transaction Scheduling

Scheduling transactions in a real-time database system is not a simple task and is quite different from scheduling transactions in a non-real-time database system. There are quite a few challenges, but let’s emphasize two of the most challenging:

  • Non-real-time database systems optimize for the number of transactions per second or the average query time. A real-time database system’s performance is judged by its worst-case transaction time. This is a key differentiator between real-time and non-real-time database systems. For instance, the worst-case transaction time for a non-real-time DBMS is something that most users don’t care about (and is not specified). On the other hand, the number of transactions per second (TPS) is an often bragged about benchmark for many traditional DBMS.
  • Non-real-time databases use transactions to enforce logical consistency, which presents a view on data consistent with some predefined constraints of the database. Each real-time transaction is assigned an execution deadline to make sure that the data used by them reflects the current physical environment. These deadlines can be successfully satisfied, or missed (in which case the transaction is aborted). In a real-time database system, transactions must never pass their assigned deadlines. The eXtremeDB/rt database kernel guarantees the database’s logical consistency, and schedule transactions to meet their deadlines, all while minimizing the number of transactions that miss their deadlines.

Furthermore, real-time transaction scheduling goals vary from application to application. For example, one application could seek to schedule transactions to minimize the number of “aborted” transactions (those that “miss” their deadlines) and may or may not allow preemption by a “higher priority” transaction; another application could aim to maximize the total “weight” (deadline + priority) of successful transactions while another application might simply prioritize transactions with the earliest deadline.

eXtremeDB/rt provides two alternative implementations of transaction managers (schedulers). Both managers are based on the standard eXtremeDB MURSIW (Multiple Read Single Write) policy.

High Priority Earliest Deadline First (EDF) algorithm

The eXtremeDB/rt EDF-TM (Earliest Deadline First Transaction Manager) implements a wait-list of transactions, in other words a “transaction queue“ in the database kernel. Transaction requests are sorted first on their priority and then within the same priority by deadline.

Priority Inheritance (PI) algorithm

The eXtremeDB/rt PI-TM (Priority Inheritance Transaction Manager) relies on the underlying real-time operating system’s scheduling, and provides necessary “hints” via specific usage of the RTOS’s synchronization primitives: Upon the start of a transaction, the thread grabs one or more mutex and releases them when the transaction ends. As a result, the underlying operating system scheduler is fully aware of which thread holds a mutex that is needed for a high-priority transaction and may apply the “priority inheritance” algorithm when necessary, i.e. temporarily raise the priority of a thread that is “in the way” to let it finish the transaction “faster” so it can release the “highly needed” mutex.

EDF- based vs PI-based transaction managers — which is better and when?

The major difference between the EDF and PI TMs is that in the case of the EDF manager, the database kernel organizes the queue and determines transaction execution order. In the PI-TM case, the execution order is determined by the operating system and is normally based on the corresponding OS task priorities. Different application patterns can take advantage of different transaction schedulers.

First, let’s consider a pattern that promotes the use of the PI-TM. Suppose the application has three threads: a high priority thread (let’s call it H_DB) that performs transactions with the database, a low priority thread that also performs transactions (L_DB), and a mid-priority thread that does not work with the database (M). The L_DB starts a transaction. After that M comes in and (having a higher priority) preempts the L_DB taking it “off the CPU” and putting it on hold. Next, H_DB arrives but is unable to start a transaction because L_DB is in the way. Essentially, with MURSIW the highest priority thread H_DB will have to wait until the lowest priority thread L_DB completes its transaction, which in turn has to wait for M to yield. However, with PI-TM the operating system will be able to raise L_DB’s priority up to H_DB’s priority at the moment when H_DB arrives, thus allowing L_DB to preempt M, allowing L_DB to complete its transaction and free the way for H_DB.

Now, let’s consider a pattern when all thread priorities are the same and the underlying OS gets access to the database lock in FIFO order. The picture illustrates an execution scenario in which two transactions have arrived while a single transaction (the lowest one on the picture) is executing. In this scenario the PI-TM would execute all three in the order they were registered with the system. Yet it is possible that the deadline of the third transaction (the highest on the picture) is lower than the deadline of the second transaction. It will be aborted then. If on the other hand the EDF-TM is used, the third transaction will be allowed to run despite that fact it has arrived into the system after the second one because its deadline is shorter. As a result both would fit into their deadlines.

Watch a brief video about these transaction scheduling policies.

Preemption rules

Once scheduled, a transaction’s execution is controlled by the transaction manager, which ensures proper serialization (“read-write” transactions are executed sequentially and “read-only” transactions are executed in parallel while no “read-write” transactions are executing). EDF-TM verifies the rules just once at the time a new transaction arrives (is entered into the waiting queue), while PI-TM checks the rules also when a transaction is finalized.

The preemption rules are as follows:

  • A higher priority Read-Write transaction preempts all running lower priority Read-Only transactions (causing them to rollback, first) unless there is also a running Read-Only transaction with equal or higher priority than this read-write transaction has. In this case, the Read-Write transaction will be placed at the appropriate location in the queue according to its priority and deadline.
  • A higher priority Read-Only or Read-Write transaction preempts a lower priority Read-Write transaction (causing it to rollback, first) if the elapsed running time (and, consequently, the time of termination via rollback ) of the running transaction is less than the new transaction’s deadline. In other words, if the time required to preempt the running transaction, including rolling it back, would preclude the higher priority transaction being able to commit before its deadline, then the currently running transaction will not be preempted because the result would be two rolled back transactions.

Click image to enlarge

eXtremeDB/rt read-write and read-only rules

Related Resources

Documentation & Collateral

b

Review the eXtremeDB/rt data sheet

U

Learn more about eXtremeDB/rt in our on-line documentation

To Err is Human. The Case for Buy Over Build in Hard Real-time Database Management Systems

t

eXtremeDB/rt Q & A: what distinguishes a true real-time database?

eXtremeDB/rt offers deterministic ACID-compliant transactions
Real-time transaction timeline

Chart from the white paper, “Real-time Deterministic Database Management” about the objectives of deterministic, predictable database management in the context of real-time application design.

In the News

Tailored to your needs


The nature of eXtremeDB/rt’s tight integration with the RTOS and target hardware requires that each evaluation package be assembled uniquely for your needs.  Please contact us so that we can gather information on your RTOS vendor, version, target hardware, tool chain, and so on.

View the ever-expanding list of supported real-time operating systems.

Send us an email

Give us a call

+1-425-888-8505

Desktop distributions

Free desktop evaluation packages of eXtremeDB/rt for Linux, MacOS, QNX and Windows platforms are available for immediate no-hassle download. Learn more about the programming interface and various real-time and non-real-time features of eXtremeDB/rt. After you have tried the desktop version, we hope you’ll contact us for a free trial of eXtremeDB/rt tailored to the needs of your RTOS.

You are also welcome to contact us, and we will send you a download of eXtremeDB/rt running in the FreeRTOS simulator.

News and articles about real-time database management.

COTS Cover photo July 2022

"Soft v Hard Real-time Systems" Embedded Computing, November 4, 2022

Real-time transaction timeline

"Embedded Databases in Real-Time Systems" CircuitCellar.com, March 14, 2022

Steve Graves, President and CEO, McObject

"Embedded Executive: Steve Graves, President and CEO, McObject" EmbeddedComputing.com, January, 2022 An interview reviewing key concepts in real-time computing.

COTS article about eXtremeDB/rt

"Databases in Hard Real Time" McObject Launches True Real-Time Deterministic Database for embOS Real-time Operating System Applications, Wilmott.com, October 15, 2021

COTS article about eXtremeDB/rt

"Keeping A Mission-Critical Deterministic DBMS On Time" by McObject CTO Andrei Gorine EmbeddedComputing.com, September 20, 2021

COTS article about eXtremeDB/rt

"Real time tasks need real time data" Read the Wind River blog, September 7, 2021

We’re grateful for the partnerships we have with industry leaders, and invite you to read what they say about eXtremeDB/rt in our joint press releases.

Azure RTOS ThreadX

“Managing data with a hard real-time requirement is a challenge for developers,” comments Tony Shakib, Partner General Manager, Microsoft Azure IoT. “Developers have had to use current solutions that may not meet time constraints or write their own database system. eXtremeDB/rt brings a solution to Microsoft Azure developers that eliminates this trade off.”

Read the joint press release.

DDC-I’s Deos

eXtremeDB/rt provides an excellent option for developers of resource-constrained, mission-critical embedded systems who require a compact, real-time embedded database,” said Greg Rose, vice president of marketing and product management at DDC-I. “We look forward to working with McObject to offer eXtremeDB/rt to embedded developers utilizing our Deos real-time operating system.”

Read the joint press release.

embOS from SEGGER

SEGGER’s CEO, Ivo Geilenbruegge, had this to say: “We are excited that McObject has created a first-of-its-kind real-time database system to complement our embOS RTOS and extend support for hard real-time systems to include database operations. Real-time systems are following the trend of embedded systems in that they are being called upon to manage more (and more complex) data.”

Read the joint press release.

FreeRTOS

Richard Barry, FreeRTOS founder, said “It is good to have another high-quality option for FreeRTOS users, this time providing a real-time deterministic database which can, as just one example, fulfill a crucial role in the Industrial Internet of Things (IIoT): data collection, aggregation, and distribution in oil rig blow-out prevention (BOP) systems. A BOP is a specialized device equipped with sensors to detect a “kick” and actuate valves to prevent a catastrophic blowout.” Richard continued, “The need to detect and respond within deadlines is emblematic of real-time industrial systems.”

Read the press release.

INTEGRITY from Green Hills Software

Joe Fabbre, Global Technology Director for Green Hills had this to say: “McObject has created a unique real-time database that complements our INTEGRITY RTOS and extends hard real-time support to database operations. Advanced applications in real-time systems are being called upon to manage more (and more complex) data. eXtremeDB/rt gives developers of these systems an off the shelf solution for real-time data management.”

Read the joint press release.

LynxOS

“We were delighted to work with McObject to bring eXtremeDB/rt to the LynxOS partner ecosystem. Our companies share the vision that real-time systems are becoming more sophisticated and consequently have to manage more complex data. eXtremeDB/rt fills a critical gap in the technology stack,” said Pavan Singh, VP of product management, Lynx Software Technologies.

Read the joint press release.

QNX Neutrino RTOS

“Real-time performance can benefit embedded software developers in many market segments including autonomous systems, industrial control, robotics and medical devices,” said Romain Saha, Strategic Alliances Director at BlackBerry QNX: “McObject builds upon many years of QNX support by bringing eXtremeDB/rt to the latest version of the QNX Software Development Platform.”

Read the joint press release.

SIEMENS Nucleus RTOS

“McObject’s eXtremeDB/rt allows Nucleus customers to have a truly embedded database solution that allows them to meet the determinism they require in a commercial-off-the-shelf solution.” said Jeff Hancock, Siemens Embedded Senior Product Manager. “eXtremeDB/rt helps Nucleus customers manage ever-growing data requirements.”

Read the joint press release.

WindRiver VxWorks

“Through our work with McObject, we’re helping customers modernize and accelerate the delivery of reliable intelligent systems that demand real-time requirements,” said Michel Chabroux, Senior Director, Product Management, Wind River. “We look forward to building on our proven track record of success with McObject to help advance the next generation of cloud-connected intelligent systems with increasingly challenging edge compute needs.”

Read the joint press release.