Transaction processing monitors

ABSTRACT

A transaction processing (TP) application is a program that performs an administrative function by accessing a shared database on behalf of an on-line user. A TP system is an integrated set of products that supports TP applications. These products include both hardware, such as processors, memories, disks and communications controllers, and software such as operating systems (Oss), database management systems (DBMSs), computer networks and TP monitors. Much of the integration of these products is provided by TP monitors which coordinate the flow of transaction request between terminals that issue requests and TP applications that can process them.Today, TP represents over 25 percent of the computer systems market and is one of the growing segments of the computer business. TP applications appear in most sectors of large-scale enterprises such as airline reservation, electronic banking, securities trading, inventory and production control, communications switching, videotex, sales management, military command and control and government services. 84552 75 CACM 33 10 Consider a computer system having a CPU that feeds jobs to two input/output (I/O) devices having different speeds. Let &thgr; be the fraction of jobs routed to the first I/O device, so that 1 - &thgr; is the fraction routed to the second. Suppose that @@@@ = @@@@(&thgr;) is the steady-sate amount of time that a job spends in the system. Given that &thgr; is a decision variable, a designer might wish to minimize @@@@(&thgr;) over &thgr;. Since @@@@(·) is typically difficult to evaluate analytically, Monte Carlo optimization is an attractive methodology. By analogy with deterministic mathematical programming, efficient Monte Carlo gradient estimation is an important ingredient of simulation-based optimization algorithms. As a consequence, gradient estimation has recently attracted considerable attention in the simulation community. It is our goal, in this article, to describe one efficient method for estimating gradients in the Monte Carlo setting, namely the likelihood ratio method (also known as the efficient score method). This technique has been previously described (in less general settings than those developed in this article) in [6, 16, 18, 21]. An alternative gradient estimation procedure is infinitesimal perturbation analysis; see [11, 12] for an introduction. While it is typically more difficult to apply to a given application than the likelihood ratio technique of interest here, it often turns out to be statistically more accurate. In this article, we first describe two important problems which motivate our study of efficient gradient estimation algorithms. Next, we will present the likelihood ratio gradient estimator in a general setting in which the essential idea is most transparent. The section that follows then specializes the estimator to discrete-time stochastic processes. We derive likelihood-ratio-gradient estimators for both time-homogeneous and non-time homogeneous discrete-time Markov chains. Later, we discuss likelihood ratio gradient estimation in continuous time. As examples of our analysis, we present the gradient estimators for time-homogeneous continuous-time Markov chains; non-time homogeneous continuous-time Markov chains; semi-Markov processes; and generalized semi-Markov processes. (The analysis throughout these sections assumes the performance measure that defines @@@@(&thgr;) corresponds to a terminating simulation.) Finally, we conclude the article with a brief discussion of the basic issues that arise in extending the likelihood ratio gradient estimator to steady-state performance measures.

REFERENCES

• 1: Acker, R.D., and P.H. Seaman. Modeling distrihuted processing across multiple CICS/VS sites. IBM S3'st. J. 21, 4 (1982), 471-489.
• 2: Anderson, K.J. Bucket brigade computing. UNIX Rev 8, 3 (Aug. 1985), 58-64.
• 3: A measure of transaction processing power, Datamation, v.31 n.7, p.112-118, March 15, 1985
• 4: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 5: Philip A. Bernstein , Meichun Hsu , Bruce Mann, Implementing recoverable requests using queues, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.112-122, May 23-26, 1990, Atlantic City, New Jersey, United States
• 6: B. Bershad , T. Anderson , E. Lazowska , H. Levy, Lightweight remote procedure call, Proceedings of the twelfth ACM symposium on Operating systems principles, p.102-113, November 1989
• 7: Andrew D. Birrell , Bruce Jay Nelson, Implementing remote procedure calls, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.39-59, February 1984 [doi>10.1145/2080.357392]
• 8: Digital Equipment Corp. DEClntact Transaction Processing System.' Application Programming Guide. Order number AA-KZ03B-TE, Maynard, Mass., 1989.
• 9: Digital Equipment Corp. VAX ACMS Guide to Transaction Processing Programming. Order number AA- N691E-TE, Maynard, Mass., 1989.
• 10: Wayne V. Duquaine, LU 6.2 as a Network Standard for Transaction Processing, Proceedings of the 2nd International Workshop on High Performance Transaction Systems, p.20-37, September 28-30, 1987
• 11: International Business Machines. CICS/OS/VS Intercommunications Facilities Guide, Form SC33-0230, White Plains, New York, 1986.
• 12: Butler W Lampson, Designing a global name service, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.1-10, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10591]
• 13: Liskov, B.H., and Herlihy, M.P. Issues in process and communication structure for distributed programs. In Proceedings of the Third Symposium on Reliability in Distributed Software and Database Systems (October, 1983) IEEE Computer Society Press, pp. 123-132.
• 14: B. Liskov , L. Shrira, Promises: linguistic support for efficient asynchronous procedure calls in distributed systems, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.260-267, June 20-24, 1988, Atlanta, Georgia, United States
• 15: McGee, W.C. The information management system IMS/VS, Part V: Transaction processing facilities, IBM Svst. j. 16, 2 (1977), 148-168,
• 16: Pacifico Amarga Lim, CICS/VS command level with ANS COBOL examples (2nd ed.), Van Nostrand Reinhold Co., New York, NY, 1985
• 17: Serlin, O. Fauh-tolerant systems in commercial applications. IEEE Comput. 15, 8 (Aug. 1984), 19-30.
• 18: M. Schroeder , M. Burrows, Performance of Firefly RPC, Proceedings of the twelfth ACM symposium on Operating systems principles, p.83-90, November 1989
• 19: Siewiorek, D.P. Architecture of fault-tolerant computers. IEEE Comput. 15, 8 (Aug. 1984), 9-18.
• 20: Siwiec, J.E. A High-Performance DB/DC System. IBM Syst. J. 16, 2 (1977), 169-195.
• 21: Tandem Computers Inc. An Introduction to Pathway, Part: T82339, 1985, Cupertino, CA.
• 22: Wallace, J.J., and Barnes, W.W. Designing for Ultrahigh Availability: The Unix RTR operating system. IEEE Comput. 15, 8 (Aug. 1984), 31-39.
• 23: Arlene J. Wipfler, CICS: application development and programming, Macmillan Publishing Co., Inc., Indianapolis, IN, 1987
• 24: Arlene J. Wipfler, Distributed processing in the CICS environment: a guide to MRO/ISC, Intertext Publications, Inc.,/McGraw-Hill, Inc., New York, NY, 1989

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

General Terms:
Design, Management