How to Prioritize Database Transactions

Embedded / real-time systems most often consist of just a few concurrent tasks. An embedded database system can leverage this awareness by utilizing a simple approach to concurrency. In eXtremeDB, this is the MURSIW transaction manager. MURSIW = MUltiple Reader, SIngle Writer.

This transaction manager allows multiple tasks to read the database at the same time. A task that wants to write to the database is granted exclusive access to the database for the duration of its transaction; other read-only and read-write tasks wait.

To implement this strategy, eXtremeDB creates a transaction queue. When a task wants to use the database, it calls a function to start a transaction and indicates the type of access requested: read-only or read-write. If no other transaction is running, the task is given access to the database immediately. If another task is executing a read-only transaction, and this task is also requesting a read-only transaction, this task is again given immediate access to the database. If this task is requesting a read-write transaction, it is placed in the queue to wait for the read-only transaction(s) that are already executing. Likewise, if another task is executing a read-write transaction, then every other transaction request is placed in the queue to wait for the read-write transaction to finish.

Assuming that a read-write transaction is currently executing, the transaction queue can be visualized as:

Upon completion of the currently executing transaction, eXtremeDB will allow transactions 1 – 4 to execute, then #5, #6, #7, #s 8 & 9, #10, #s 11 – 15, #16, and finally #s 17 – 25, in turn.

Normally, the queue is first-in-first-out (FIFO). However, eXtremeDB allows developers to assign a transaction priority to each transaction. This will put a new transaction ahead of transactions with a lower priority in the queue. There are five classifications to prioritize database transactions, from lowest priority to highest:

IDLE

BACKGROUND

FOREGROUND

HIGH

ISR

Now, the transaction queue can be visualized as:

The MURSIW transaction manager will schedule transactions with ISR priority first, followed by HIGH, and so on. If the ISR and HIGH queues are empty so that the transaction manager is scheduling transactions from the NORMAL queue and a new ISR or HIGH transaction is started, it will be the next transaction scheduled (i.e. jump to the front of the queue of all transactions).

N.B. A parameter that is set at the time a database is opened determines whether a currently executing transaction can be preempted by a newly-started higher priority transaction. The default is that that running transactions are never preempted.

Care must be taken to harmonize eXtremeDB transaction priorities with the task’s RTOS priorities so as not to create a priority inversion.