The performance of a precedence-based queuing discipline

ABSTRACT

A queuing system with infinitely many servers, and with the following queuing discipline is considered: For any two jobs i and j in the system, such that i arrived later than j, there is a fixed probability p that i will have to wait for j's execution to terminate before i starts executing. This queuing system is a very simple model for database concurrency control via “static” locking, as well as of parallel execution of programs consisting of several interdependent processes. The problem of determining the maximum arrival rate (as a function of p) that can be sustained before this system becomes unstable is studied. It is shown that this rate is inversely proportional to p, and close upper and lower bounds on the constant for the case of deterministic departures are found. The result suggests that the degree of multiprogramming of multiuser databases, or the level of parallelism of concurrent programs, is inversely proportional to the probability of conflict, and that the constant is small and known within a factor of 2. The technique used involves the computation of certain asymptotic parameters of a random infinite directed acyclic graph (dag) that seem of interest by themselves.

REFERENCES

• 1: ALDOUS, D., AND PITMAN, J. The asymptotic speed and shape of a particle system. In Probability, Statistics and Analysis, J. F. C. Kingman and G. E. H. Reuter, Eds. Cambridge University Press, Cambridge, England, 1983.
• 1a: Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
• 2: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 3: Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
• 4: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

General Terms:
Design, Management, Performance, Theory, Verification