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

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