Approximate analysis of reader and writer access to a shared resource

ABSTRACT

In this paper we present a queue that has two classes of customers: readers and writers. Readers access the resource concurrently and writers access the resource serially. The queue discipline is FCFS: readers must wait until all writers that arrived earlier have completed service, and vice versa. The approximation can predict both the expected waiting times for readers and writers and the capacity of the queue. The queue can be used for the analysis of operating system and software resources that can be accessed both serially and concurrently, such as shared files. We have used the queue to analyze the performance of concurrent B-tree algorithms.

REFERENCES

• 1: A. Chesnais , E. Gelenbe , I. Mitrani, On the modeling of parallel access to shared data, Communications of the ACM, v.26 n.3, p.196-202, March 1983 [doi>10.1145/358061.358073]
• 2: F. Baccelli , E. G. Coffman, A data base replication analysis using an M/M/m queue with service interruptions, ACM SIGMETRICS Performance Evaluation Review, v.11 n.4, December 1982
• 3: Jr. E. Coffman, E. Gelenbe, and B. Plateau. Optimization of the number of copies in a distributed database. IEEE Transactions on Software Engineering, 7(1):78-84, 1981.
• 4: E. Coffman et. al. An analysis of parallel-read sequential-write systems. Performance Evaluation, 1:62-69, 1981.
• 5: Theodore Johnson , Dennis Shasha, A framework for the performance analysis of concurrent B-tree algorithms, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.273-287, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298580]
• 6: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 7: R. Mickens. Difference Equations. Van Nostrand Reinhold, New Yo~k, 1987.
• 8: Robert J. T. Morris , Wing Shing Wong, Performance of Concurrency Control Algorithms with Nonexclusive Access, Proceedings of the Tenth International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.87-101, December 19-21, 1984
• 9: Randolph D. Nelson , Balakrishna R. Iyer, Analysis of a replicated data base, Performance Evaluation, v.5 n.3, p.133-148, Aug. 1985 [doi>10.1016/0166-5316(85)90008-2]
• 10: Y. C. Tay , Nathan Goodman , R. Suri, Locking performance in centralized databases, ACM Transactions on Database Systems (TODS), v.10 n.4, p.415-462, Dec. 1985 [doi>10.1145/4879.4880]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Measurement, Performance, Theory