Database for Hard Real time Systems

Databases for real time systems are meant for the use of both hard and soft systems. Since hard real time systems needs strict timing constraints, conventional disk based databases are not suitable, but soft real time systems makes use of disk based systems through FCFS, Elevator or scan policy algorithm.

There should be some solution for Hard Real time systems with high performance and guaranteed response time constraints. MDARTS (Multiprocessor Database Architecture for Real Time System) is one such main memory database which uses VME based processors.

Features


  • This is for Hard Real time Systems

  • It is a main memory database (the entire database resides on the main memory)

  • Object oriented database (C++ elements)

  • Supports explicit declaration of real time constraints and semantic constraints within the application code.
    Constraints Specifications
    Access time ”write <=80usec ; read<=50usec” Staleness ”stale<=20msec” Persistence ”volatile”

  • The above are the constraints which can be included in the application code directly without the recompilation of the MDARTS library.

  • Supports direct, concurrent, shared memory data access.

Shared Memory Objects



  • This is suitable for NGC (Next generation Workstation/machine controller) for automated factories
  • The timing constraints of some real time applications are such that database transactions on the order of tens of microseconds may be needed
  • The above diagram shows the access to the data from the shared memory
  • The control task is periodic with hard deadline every msec. Each time the control task runs, it extracts the current sensor values from the database and computes new control signals for the actuators.
  • Data accessed extremely high speed must be stored in the physical shared memory as the virtual memory and disk based databases may generate the page faults which should not be generated for main memory.
  • Applications need not know whether the database access is local or remote. The database handler hides the information of being remote. Remote access achieved through Remote Procedure calls (RPC). There may be some communication delay when the data is accessed remotely.
  • The shared data manager (SDM) tracks the location and identity of the shared memory objects and also constructs its own database handle for each object to service remote requests.

Databases for Soft Real Time System

In disk based scheduling, the disks are located and traced by traversing the sectors and tracks. Tracks are concentric circles and sectors are just originating from the center of the disks.
So, disk scheduling algorithms are slower when compared with the memory based scheduling. Under disk based scheduling
Ta=Tw+Tp+Tt
Ta is the access time
Tw is the time spent in queue
Tp is the time to position the arm to locate the sectors and track
Tt is the time taken to transfer the block of data.
Since Tp is in the order of few milliseconds, but CPU time is hardly around 50nano seconds, so disk based scheduling algorithms are not suitable for hard real time systems. However these algorithms, can be made useful for soft real time systems. Disk based scheduling will be useful for Soft Real time system based on the following algorithms
First Come First Serve (FCFS)

The task or transaction which comes first will be scheduled and then the next, here the main problem is if the requests are huge then this algorithm is not suitable.
Elevator or Scan policy

Scans in one direction and serves the requests, if not then comes to starting position and runs again from the beginning. In the following diagram, the requests are dark lines and servings are given in dotted arrow lines. In this first case, the order of servings will be 3,4,5,9,1,1,2 (as 3,4,5,9 are over, it comes back to its position and starts from 1 and 1 and then 2) the other method will be scans in one direction and serves the requests, if not reverse the direction and serves the request and comes to starting position and then starts for the next cycle . The following example depicts both. In this the order of serving will be 3,4,5,9,2,1,1 (after 3,4,5 and9, the servings are reversing, so that 2,1,1) or the third method will be allocation of priority to requests. But who will give and how to set priority to the new requests.




Concurrency Control Issues

  • Pessimistic Concurrency Control
    • The transactions are been checking for violating the serialization consistency before letting it execute is called pessimistic concurrency control
      • Two phase locking Scheme
        • Read /Write lock as a phase
        • Unlock – another phase
        • Both the above phases wont interleave, because of this, there may be deadlock, which can be detected by means of deadlock detection algorithm and if deadlock is there, one of the transactions is aborted with the nearer timestamp.
      • Multiversion Scheme
        • There are three locks Read, Write and Certify
        • Read lock – Read the needed data from the database
        • Write lock – Writing to its own private space
        • Certify lock – Updates to the database, this stage is the committed stage.

      General locking Rules

Lock Already Set

Lock Requested

Read

Write

Certify

Read

Granted

Granted

Blocked

Write

Granted

Granted

Granted

Certify

Blocked

Granted

Blocked


 

Locking rules for priority Inversion

Lock Already Set by a Low Priority Transaction

Lock Requested by a High Priority Transaction

Read

Write

Certify

Read

Granted

L-Aborted

Can't Occur*

Write

Granted/Blocked#

Granted

Granted

Certify

Conversion

Granted

Conversion

In the above table,

L-Aborted - Low Priority Transaction Aborted

Conversion – Low Priority Transaction is converted to write lock

* - already the transaction is aborted, so no reading lock set.


 

If we reduce transaction abortion, then in the above table, L-aborted may be when the HPT requesting the certify lock, while the HPT requesting Write lock which will be granted.


 

Lock Already Set by a High Priority Transaction

Lock Requested by a Low Priority Transaction

Read

Write

Certify

Read

Granted

Granted

Blocked

Write

Blocked

Granted

Granted/Blocked#

Certify

Blocked

Granted

Blocked

# - depending on the implementaion


 

  • Optimistic Concurrency Control
    • The transactions are first allowed to run, after that they are checked for violating the Serialization Consistency
      • Read Phase
        • Reads from the database and writes to its own private address space
      • Validation Phase
        • Checked for violating the serialization consistency.
      • Write Phase (if needed)
        • If the Serialization consistency is not violated in the above phase, then this phase is needed to update to the database
    • So this method is optimistic in the sense that, the transaction are execute and put into the private address space where it is checked for violating the serialization consistency.
    • A and T are two transactions where A's timestamp precedes T's timestamp. The serialization consistency is not violated due to T if the following conditions are true.
      • A has completed its write phase before T starts its read phase.
      • The write set of A is distinct from both the read and write set of T.
    • If the above conditions are not satisfied, then T will be aborted as its timestamp is nearer.

Transaction Abortions

Transaction Abortions

Transaction abortion is of two types, either

  • Termination abortion or
    • The Transaction which is aborted in this way won't be restarted
    • Example: An attempt to divide by zero error
  • Non Termination Abortion
    • The transaction which will be restarted after it is being aborted
    • Example: data conflict due to a deadlock, If two transactions are involved in a deadlock, one of the transaction will be aborted and will be restarted

Transaction Priorities

Transaction Priorities

  • Transactions are granted access to the processors based on their priorities.
  • All the transactions in the real time DB are associated with a deadline, hence Earliest Deadline First (EDF) algorithm finds a greater solution to schedule those transactions. But EDF algorithm will be working efficiently if the number of transactions are moderate. But usually the DB transactions are huge in a systems and EDF may not be suitable which leads to congestion.
  • To avoid the above solution an algorithm Adaptive Earliest Deadline (AED) algorithm which uses congestion control and also can process huge number of transactions. It uses two groups HIT and MISS group.
  • All the transactions in the HIT group will be meeting their deadlines, if by chance any transaction does not meets its deadline, then that transaction will be aborted.

Operation of AED

  • When a transaction arrives, the system randomly inserts it in a list of pending transactions, if the assigned transaction is in the list 1…..H (H is any parameter), then it will be put in the HIT list else MISS group.
  • The objective is to try to meet all the deadlines of the HIT group and if any time left over, then the MISS group transaction may be executed.
  • Transactions within the HIT group are scheduled using EDF. If a transaction is completed, it will be removed from the list.
  • The transaction from one Group won't move to other groups.
  • The H value can be set adaptively according to the following algorithms


     

Success (HIT) = the ratio of Number of Transactions in HIT class that meet their deadlines to Total number of transactions in the HIT class.

Success (ALL) = the ratio of Number of Transactions that meet their deadlines to Total number of transactions.

The above parameters are measured repeatedly.

Main Memory Databases

Main Memory Databases

  • The entire database is residing on the main memory is the concept behind main memory databases. But there are some problems like data backups and storing logs. So Main memory databases are to rely on Disk based systems to store logs and backups.
  • General purpose databases are really huge to sit in to the main memory and they just rely on disk based systems, but real time databases are small and even if it is moderate size, it still sits on the main memory because of speed and cheaper solution.
  • Main memory can be used to write log once a transaction commits. The entire log is huge to sit in the main memory, so it is necessary to store logs in the disks at batch mode or by transaction by transactions. In the former case (batch mode), the buffer store upto a volume of logs, then at a stretch it will store in the disks.
  • Pointers
    are used to access record or data in main memory Databases because of cheaper solutions and speed. If there are multiple copies of the same data available, then only one copy of the item is stored and have pointers to it (for accessing multiple copies).
  • Indexing scheme
    in the disk systems are B trees and B+ Trees. In these mechanisms, the deeper levels are slowly indexed because of the disk accesses and other time consuming parameters. Hence Indexing scheme in Main memory databases uses T trees which are very faster even at the deeper level indexing
  • In disk based systems, if single disk unit fails, then the data on the other units are not affected and even sometimes RAID arrays are used in Disk systems to take multiple backups of same data. But if a main memory DB fails, then it should be powered down and the entire main memory restored.

Installing NS2 under Ubuntu 8.04.1, 8.10, 9.04

  1. Download NS2 from the following Website, I tried version ns-allinone-2.33.tar.gz.
  2. Put the file under /home/pradeep/ (my user login is pradeep, you may try with your username)
  3. go the folder in the shell prompt by issuing the following command cd /home/pradeep/
  4. Since installation of NS2 simulator needs some autoconfiguration files which will need to be installed. To download those packages, just execute the following commands $ sudo apt-get install build-essential autoconf automake libxmu-dev
  5. it will take some time to download and install.
  6. Now execute the following steps so that NS2 will be installed $ tar zxvf ns-allinone-2.33.tar.gz $ cd ns-allinone-2.33 $ ./install
  7. After the above three steps, NS2 will give the path information which needs to be set in the PATH variable
  8. Open the file .bashrc which is available under the folder /home/pradeep/ (if you try to install in root user /root/.bashrc). Use the following command to open the .bashrc file $ gedit /home/pradeep/.bashrc
  9. edit the above file and set the following paths over there export PATH=$PATH:/home/pradeep/ns-allinone-2.33/bin:/home/pradeep/ns-allinone-2.33/tcl8.4.18/unix:/home/pradeep/ns-allinone-2.33/tk8.4.18/unix export LD_LIBRARY_PATH= /home/pradeep/ns-allinone-2.33/otcl-1.13, /home/pradeep/ns-allinone-2.33/lib
  10. Thats it!!! save the file, logout and login with the username.
  11. open the shell prompt and type $ ns (you will get a % indicating that the installation is working correctly) $ nam ( a window will be opened showing the network animator)
  12. For running examples in TCL, click here

Real Time Vs General Purpose Databases

The queries associated with a Real time databases are associated with a deadline, there may be some response after the queries passed the deadlines.

The data returned in response to a query must have absolute and relative consistency.


 

Absolute Vs Relative Consistency

Absolute consistency is accuracy. The data returned in response to a query must be close to the results expected. If temperature or pressure is interrogated in a chemical vessel, we want the data returned to be close to the current temperature or pressure.


 

Relative consistency means that for multiple data, the data must have been collected reasonably close to one another.


 

Need for Response Time predictability

There are many factors that affect the response time predictability

  • The requirement to meet the ACID properties will entail a overhead.
  • Transactions may be aborted one or more times to avoid deadlock and to maintain serialization consistency. So transaction abortion leads to a delay.
  • Databases are often quite large to fit in the main memory and therefore rely mainly on the disk based systems. Page faults are the problem creators if the requested record is not in the main memory.
  • Transaction access are data dependant. The transaction to deduct an amount from a database which has lower balance is faster whereas the higher balance leads to slowness.
  • Transaction may suffer with a delay in accessing a data which is being locked by some other transactions.


 

Relaxing the ACID Properties

    General purpose databases always obey the ACID properties, but Real Time databases often relaxing the ACID properties or even sometime violates the ACID properties.


 

In Machine tool Control System, the current tool position is not regarded as durable data and is discarded after it become outdated. In such an application, data durability is not worth maintaining if new measurements are frequently collected.


 

Sometimes even serialization consistency is also violated. Maintain serialization consistency leads to avoid concurrent transactions.


 

For example,

A and B are two airports. Users can book the tickets online to travel to the destination. For example,

  • if more than or equal to 100 passengers are allotted in a flight, then there should be 5 flight attendants else only 3 flight attendants
  • if less than 85 passengers (after cancellation) there should be only 3 flight attendants.

In such a case, assume if there is already 99 tickets booked for particular flight, and there will be one reservation and one cancellation

  • If reservation happens first, then 100 tickets sold and 5 flight attendants
  • Then cancellation happens, 99 tickets with the same 5 flight attendants (only if less than 85, flight attendants will be 3)

In second case,

  • If cancellation first, 98 tickets with 3 flight attendants
  • Reservation next, 99 tickets with the same 3 flight attendants

If the above cases, since both the reservation and cancellation happens to be running serially (one after other) to maintain serialization consistency, it may be decided to interleave both the transactions and the second transaction can be aborted to maintain serialization consistency.


 

Introduction to Real Time Databases

Transaction

It is said to be set of read or write operations

Query

A Transaction is said to be a query if it contains either a read or update operation


 

Commit is a point of no return, once a transaction is commited we are certain that, the changes to the database are permanent


 

ACID Properties of a General Purpose Databases

Atomicity

    An action is said to be atomic, if it either completely done or not at all.

Consistency

    A transaction transforms the database from one consistent state to another consistent state. A state is said to be a set of transactions.

Isolation

    Until and unless a transaction is committed, the actions of it are not visible to any other transactions

Durability

    After commit, the changes made to the databases are permanent


 

Conventional Databases will follow the ACID properties and it never violates

Timing Specifications Needed for a Real Time Language

A Good Real time Programming language should specify various timing specifications for the entities in the System. But none of the languages does this. Following are some of the specifications needed for a good real time programming language

Specify

  • the duration between two events is no longer than the specified maximum and no shorter than the specified minimum.
  • the maximum runtime for a particular task, if the run time is not met, then an exception is generated.
  • the absolute time at which a task is to begin.
  • how soon a message is to be received after it is sent
  • how soon after receipt a message must be processed by the receiving task
  • periodic scheduling of the task
  • maximum time allocated for a loop to execute

upper bounds on the size of dynamic data structures

How Priority is Assigned to Tasks in ADA

procedure PRIORITY is

task A

task body A is

pragma PRIORITY(5);

begin

end A;

task B

task body B is

pragma PRIORITY(2);

begin

end B;

task C

task body C is

pragma PRIORITY(1);

begin

end C;

begin

–Procedure body

end PRIORITY

The above ADA code shows that static Priority of A is higher than B and B Over C. If two tasks have same priority then, the order of preference will be taken randomly.

Example 2 – Tasking in ADA

task ALARM is

entry AWAKE;

task body ALARM is

begin

loop

select

accept AWAKE;

or

delay 50.0;

SIGNAL_ALARM;

end select;

end loop;

end ALARM;


 

The above code shows that whether an operator is awake or not. If the operator is awake, then the AWAKE button is pressed every 50 sec. if not, the after a delay of 50 seconds, an ALARM will be sounded indicating the operator is away or AWAKE button is not pressed.

If the operator pressing the AWAKE button at 0 seconds or even at 49 seconds, the SIGNAL_ALARM procedure wont be executed at all. because the AWAKE button should be pressed once every 50 sec.

Example 1 – Tasking in ADA

task SERVER is

entry TASK_A(A,B:float);

entry TASK_B(A,B:float);

task body SERVER is

begin

loop

select

accept TASK_A(A,B:float);

or

accept TASK_B(A,B:float);

or

terminate;

end select;

end loop;

end SERVER;


 

The above program implements a server which serves the two Queues TASK_A and TASK_B through the float variable A and B. The Server is running with a infinite loop so the server is always serving either of the two queues. if the both the queues are empty, then the SERVER task will terminate. if both the queues are full, then the task will take from any one of the queue at a random fashion.

Multitasking in ADA

How multitasking is achieved in ADA. Please look at the following pseudo code


 

Procedure ABC

task A  

task body A is

——-

End A

task B

task body B is

——-

End A

task C  

task body Cis

——-

End C

Begin

–  Procedure ABC's statements

End ABC

 
 

In the above code, when the procedure begins all the three tasks A,B and C initiated concurrently and when the procedure ends, all the tasks completes their execution.  The three tasks does not have any relation with one another (means all are independent tasks)

 
 

Suppose if the tasks are having some relations between each other, then the following code depicts their behavior.

Procedure SHARING

Task A;

Task Body A is

B.BETA(X);

C.GAMMA(X);

End A;

Task B is

                Entry BETA(X:float);

Task Body B is

                Accept BETA(X:float);

End B;

Task C is

                Entry GAMMA(X:float);

Task Body C is

                Accept GAMMA(X:float);

End C;

Begin

End SHARING;

 
 

In the above code, the task A wants to share a float variable X at a point ALPHA with the tasks B and C at the points BETA and GAMMA respectively. When the procedure SHARING starts, all the three tasks initiated concurrently and if the task A reaches ALPHA first, it will to share the information with B and C and it will wait. If B reaches BETA first, it will also wait for ALPHA to reach. Similarly if C reaches GAMMA first, it will also wait for A and B to reach ALPHA and GAMMA respectively.

How to install Tracegraph in Linux (Fedora 9)

To Install Tracegraph in Fedora Linux (I used Fedora Core 9)

  1. Step download the Tracegraph software from this link

  2. Select Linux Version and download two files, mglinstaller.gz and tracegraph202.tar.gz

  3. copy the files under /home/pradeep/ (in my case it is /home/pradeep/)

  4. Untar the tracegraph202.tar.gz using the command tar zxvf tracegraph202.tar.gz

  5. A Folder tracegraph202/ will be created and go to the folder using the command cd tracegraph202 or cd /home/pradeep/tracegraph202

  6. copy the mglinstaller.gz file in the above said folder using the following command cp /home/pradeep/mglinstaller.gz /home/pradeep/tracegraph202

  7. now execute the command to unzip the mglinstaller.gz using the following command gzip -d mglinstaller.gz

  8. run the mglinstaller by executing the command ./mglinstaller

  9. the above command will create a folder within the bin folder and set the following lines to the LD_LIBRARY_PATH variable

  10. export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/home/pradeep/tracegraph202/bin/glnx86

  11. The above path will be set to the LD_LIBRARY_PATH Variable in the following file .bashrc which will be available at /home/pradeep (each username will have such a file in the corresponding folder, if you are using more number of users, each user should be set with the LD_LIBRARY_PATH, root will be having the .bash_profile at /root/.bashrc).

  12. To open this file type either vi /home/pradeep/.bashrc or gedit /home/pradeep/.bashrc and include the line of code given in step 10.

  13. Save the file, close and logout and login and go to the tracegraph202 folder and run ./trgraph (thats it!!!!)

  14. After step 13, some Linux versions will get an error called libXp.so.6 error, to overcome that give this command by connecting your machine to internet yum install libXp.so.6 or else download the package XFree86-libs-4.1.0-50.i386.rpm from the website http://rpm2html.osmirror.nl/redhat-archive/updates/7.1/en/os/i386/XFree86-libs-4.1.0-50.i386.html   and then install the package by giving rpm -ivh  XFree86-libs-4.1.0-50.i386.rpm and thats it.


(NB: My username in my System is /home/pradeep/, so all the above steps will be working for me, if your system contains other usernames, then please updated that and add to the paths) all the Best!!!!!!!!!

For More Doubts, ping me to tspembedded@gmail.com or just give me a comment