# Temporal Consistency and Transaction Schedulers

> 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.

> Let’s emphasise two challenges:

> - A real-time database system’s performance is judged by the number of transactions that successfully meet their deadline versus the number of transactions that miss their deadline. Transactions ‘meet’ their deadline when they are able to be successfully committed before the deadline. Transactions ‘miss’ their deadline when the real-time database system recognises that the transaction cannot complete within the deadline and forces it to rollback. In a real-time database system, transactions can never be ‘late’ (run past their deadline).

>   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 schedules transactions to meet their deadlines, all while minimising the number of transactions that miss their deadlines.

> - 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 (named EDF-TM and PI-TM below). Both implementations are based on the standard eXtremeDB MURSIW (Multiple Read Single Write) manager.

> ## High Priority Earliest Deadline First

> Meeting the requirements of real-time applications demands predictable yet flexible transaction management algorithms. One widely used approach is the High-Priority Earliest Deadline First (EDF) algorithm. In this method, transaction requests are organized in a wait-list that is first sorted by priority and then, within the same priority level, ordered by deadline.

> The eXtremeDB/rt EDF-TM (Earliest Deadline First Transaction Manager) ensures efficient transaction scheduling by prioritising tasks based on their deadlines, reducing the likelihood of missed deadlines. It offers high responsiveness for time-critical transactions and supports both periodic and aperiodic transactions, making it well-suited for a broad range of real-time systems.

> However, EDF has a potential drawback—it can suffer from priority inversion. A lower-priority transaction that is currently executing may block a higher-priority transaction, preventing it from meeting its deadline. This can lead to deadline violations, impacting system reliability in critical applications.

> ## Priority Inheritance (PI) Algorithm

> The eXtremeDB/rt PI-TM (Priority Inheritance Transaction Manager) relies on the underlying real-time operating system’s scheduling, and resolves the “priority inversion” problem by providing necessary “hints” via specific usage of the RTOS’s synchronisation primitives.

> A fixed-size set of these primitives is allocated at the time a database is created. They are used as mutexes: upon the start of a transaction, the thread grabs one or more mutexes (one for a Read-Only transaction, chosen randomly; all mutexes for a Read-Write transaction, in the order that prevents deadlocks) and releases them when the transaction ends.

> As a result, the underlying operating system scheduler is fully aware 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.

> The number of synchronization primitives is set by mco_db_params_t.`max_pi_readers` and effectively defines the maximal number of Read-Only transactions running in parallel. The default value is 1 meaning that PI-TM will behave as EXCL (`mcotexcl`).

> It is generally recommended to choose a value for `max_pi_readers` no greater than the number of CPU cores.

> If many READ-ONLY transactions are started, `max_pi_readers` of them will work, the rest of them will wait until at least one working transaction finishes.

> PI-TM (`mcotmpi`) is available on Linux, LynxOS-178®, FreeRTOS, embOS, INTEGRITY™ and VxWorks™.

> ## 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 the fact that it has arrived into the system after the second one because its deadline is shorter. As a result, both would fit into their deadlines.

> ## Transaction Preemption

> Once a transaction has been scheduled, its execution is controlled by the transaction manager. The manager enforces strict serialization rules: read-write transactions are executed one at a time, while read-only transactions may execute in parallel as long as no read-write transaction is active. Preemption behavior depends on the transaction manager in use. With EDF-TM, the rules are checked once, when a new transaction arrives and is placed into the waiting queue. With PI-TM, the rules are checked both when a new transaction arrives and again when an existing transaction finishes.

> The preemption rules are straightforward: a new transaction preempts all currently active transactions if every active transaction has a lower priority and if each of their rollback times is shorter than the new transaction’s deadline. For read-only transactions, rollback time is considered zero.

> Preemptive mode is enabled by default, but it can be disabled at the time the database is created by setting the flag `MCO_DB_DISABLE_PREEMPTION` in the database parameters:

> `

>         db_params.mode_mask |= MCO_DB_DISABLE_PREEMPTION;

> `

> Disabling preemption may be desirable in cases where developers want simpler, strictly queue-based scheduling (FIFO within priority groups). In such configurations, transactions are not displaced once scheduled, which can lead to more predictable execution patterns in certain workloads.

> Earlier versions of eXtremeDB/rt sometimes referred to the elapsed running time of a transaction when describing preemption. This was a legacy simplification from when rollback was assumed to take as long as the time already spent executing the transaction. In current versions, the function mco_trans_rt_estimate_rollback_time() is used instead, providing an estimated rollback time. This estimate, rather than elapsed running time, determines whether preemption would allow the higher-priority transaction to complete before its deadline.

> An additional nuance applies to PI-TM: if a higher-priority read-only transaction completes before other, lower-priority read-only transactions that are still running in parallel, a waiting read-write transaction will preempt those remaining read-only transactions. By contrast, under MURSIW once a transaction has entered the queue it will simply wait its turn, regardless of subsequent arrivals.

> To enforce deadlines reliably, the eXtremeDB/rt transaction manager performs frequent verification checkpoints during execution, comparing each transaction’s runtime against its deadline. If a transaction exceeds its allocated time slice, the manager assigns it the special status `MCO_E_INTERRUPTED` and returns control to the application. The application is then expected to initiate a rollback. The transaction manager guarantees that rollback will complete within the deadline, ensuring that the database remains consistent (for more information see Transaction Deadline Policies article). A transaction may therefore miss its deadline by being interrupted, but it is never “late.” Rollback is deterministic, bounded, and safe, ensuring that even in cases of preemption or interruption, the database always returns to a consistent state.