The response-time distribution in a real-time database with optimistic concurrency control and general execution times

For a real-time shared-memory database with optimistic concurrency control, an approximation for the distribution of the transaction response time and thus for the deadline miss probability is obtained. Transactions arrive at the database according to a Poisson process. There is a limited number of CPUs that can handle transactions in parallel. Transactions have soft deadlines, and the probability of data conflicts is equal for all transactions. No restrictive assumptions are needed about the execution time of transactions: it can have any general probability distribution. We approximate the behavior of the system by a multi-server queue with a special type of feedback. The analysis of this queueing system is based on an interpolation of the corresponding systems with constant and exponential execution times. Numerical experiments, which compare the approximative analysis with a simulation of the database, show that the approximation of the response-time distribution is quite accurate and thus very useful for real-time database design.