Stability of a Queueing System with Concurrent Service and Locking
Authors:
- C. A. CourcoubetisCCC. A. Courcoubetis
- M. I. ReimanMRM. I. Reiman
- B. SimonBSB. Simon
- 1 February 1987
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 16 (1) , 169-178
Abstract
Resource sharing systems, such as database management systems, utilize various types of locking to maintain consistency. Most locking mechanisms cause some resources to remain idle at certain times when there is work for them to do, inducing a decrease in the system’s capacity. This decrease of capacity is reflected in the stability condition for the locking system as compared to the system without locking. We consider the following locking system. There are N servers operating in parallel and two types of incoming customers. The first type corresponds to simple customers, i.e., customers with no locking requirements, and the second corresponds to customers that have to be processed simultaneously by all N servers. When a server is ready to serve such a customer, it has to wait until all servers are ready to serve that same customer. We determine a necessary and sufficient condition for stability of this system, which can be expressed in terms of the mean of the maximum of N random variables, each representing the amount of work due to simple customers arriving at a station between successive locking customers. For a particular case we provide an asymptotic analysis which indicates that the wasted capacity in such a system grows as $\log N$.
Keywords
This publication has 8 references indexed in Scilit:
- A simple analytic model for performance of exclusive locking in database systems1983
- A data base replication analysis using an M/M/m queue with service interruptionsACM SIGMETRICS Performance Evaluation Review, 1982
- An analysis of parallel-read sequential-write systemsPerformance Evaluation, 1981
- A Queueing System in Which Customers Require a Random Number of ServersOperations Research, 1980
- Locking policies: Safety and freedom from deadlock1979
- Stochastic Processes in Queueing Theory1976
- Statistics of Extremes1958
- The theory of queues with a single serverMathematical Proceedings of the Cambridge Philosophical Society, 1952