Skip to main content

Posts

Showing posts from March, 2009

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 …

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 algor…

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 SetLock RequestedReadWriteCertifyReadGrantedGrantedBlockedWriteGrantedGrantedGrantedCertifyBlockedGrantedBlocked
Locking rules for priority Inversion
Lock Already Set by a Low Priority TransactionLock Requested by a High Priority TransactionReadWrite…

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

Network Simulator 2 -Workshop

A One day workshop on Network Simulator 2 was conducted at Sri Vidya Niketan Engineering College, Tirupathi during March 2009. I have been invited there to give a guest lecture on Network Simulator 2. Topics covered on the day areIntroduction to NS2, Linux and TCLInstallation of NS2Wired and Wireless ExamplesRecompiling a New Linux Kernel

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

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 dat…

Installing NS2 under Ubuntu 8.04.1, 8.10, 9.04

Download NS2 from the following Website, I tried version ns-allinone-2.33.tar.gz.Put the file under /home/pradeep/ (my user login is pradeep, you may try with your username)go the folder in the shell prompt by issuing the following command cd /home/pradeep/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-devit will take some time to download and install.Now execute the following steps so that NS2 will be installed $ tar zxvf ns-allinone-2.33.tar.gz $ cd ns-allinone-2.33 $ ./installAfter the above three steps, NS2 will give the…

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 i…

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 po…

How to install Tracegraph in Linux (Fedora 9)

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

Step download the Tracegraph software from this link
Select Linux Version and download two files, mglinstaller.gz and tracegraph202.tar.gz
copy the files under /home/pradeep/ (in my case it is /home/pradeep/)
Untar the tracegraph202.tar.gz using the command tar zxvf tracegraph202.tar.gz
A Folder tracegraph202/ will be created and go to the folder using the command cd tracegraph202 or cd /home/pradeep/tracegraph202
copy the mglinstaller.gz file in the above said folder using the following command cp /home/pradeep/mglinstaller.gz /home/pradeep/tracegraph202
now execute the command to unzip the mglinstaller.gz using the following command gzip -d mglinstaller.gz
run the mglinstaller by executing the command ./mglinstaller
the above command will create a folder within the bin folder and set the following lines to the LD_LIBRARY_PATH variable
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/home/pradeep/tracegraph202/bin/glnx86
The above path will b…