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.

Green — Running transaction

Blue — Non-database activity

Red — Waiting to start a transaction

Yellow — Preempted by other task

Click image to enlarge

eXtremeDB/rt EDF- based vs PI-based transaction managers

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.

Green — Running transaction

Blue — Non-database activity

Red — Waiting to start a transaction

Yellow — Preempted by other task

Click image to enlarge

eXtremeDB/rt EDF- based vs PI-based transaction managers pt. 2

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.

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

i

Review the eXtremeDB/rt data sheet

U

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

In the News

Real time tasks need real time data, Blog post by McObject COO Chris Mureen
I
Deterministic Database Management in Mission-Critical Applications, A Carnegie Mellon University Database Group talk by McObject CTO Andrei Gorine
eXtremeDB/rt deterministic DBMS

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.

Send us an email

Give us a call

+1-425-888-8505

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.

Send us an email

Give us a call

+1-425-888-8505