Stability of a Queueing System with Concurrent Service and Locking

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