The Concurrency Control (CC) scheme employed can profoundly affect the performance of transaction-processing systems. In this paper, a simple unified approximate analysis methodology to model the effect on system performance of data contention under different CC schemes and for different system structures is developed. This paper concentrates on modeling data contention and then, as others have done in other papers, the solutions of the data contention model are coupled with a standard hardware resource contention model through an iteration. The methodology goes beyond previously published methods for analyzing CC schemes in terms of the generality of CC schemes and system structures that are handled. The methodology is applied to analyze the performance of centralized transaction processing systems using various optimistic- and pessimistic-type CC schemes and for both fixed-length and variable-length transactions. The accuracy of the analysis is demonstrated by comparison with simulations. It is also shown how the methodology can be applied to analyze the performance of distributed transaction-processing systems with replicated data.

A new computational algorithm called distribution analysis by chain (DAC) is developed. This algorithm computes joint queue-length distributions for product-form queuing networks with single-server fixed rate, infinite server, and queue-dependent service centers. Joint distributions are essential in problems such as the calculation of availability measures using queuing network models. The algorithm is efficient since the cost to evaluate joint queue-length probabilities is of the same order as the number of these probabilities. This contrasts with the cost of evaluating these probabilities using previous algorithms. The DAC algorithm also computes mean queue lengths and throughputs more efficiently than the recently proposed RECAL and MVAC algorithms. Furthermore, the algorithm is numerically stable and its recursion is surprisingly simple.

A computational algorithm is developed for closed multichain product-form queueing networks. For networks that consist of only single-server fixed rate and infinite-server service centers, it involves only mean performance measures. The algorithm, called mean value analysis by chain (MVAC), is based on a recursion that is quite different in form from the recursion used in the well-known mean value analysis (MVA) algorithm and has quite different computational and storage costs. For networks with few service centers and many chains, MVAC typically has much lower costs than MVA, although it becomes more costly than MVA as the number of service centers increases. The MVAC recursion is similar in structure to a recursion involving normalizing constants that was derived by A.E. Conway and N.D. Georganas (1986). That recursion formed the basis for their recursion by chain (RECAL) algorithm for computing the normalizing constant and from it the mean performance measures. The computational and storage costs for MVAC are shown to be similar to those for RECAL.>

The past few years have witnessed an increasing number of large distributed computer system implementations based on local area networks. In these systems a number of resources (CPU's, file servers, disks, etc.) are shared among jobs originating at different sites. Evaluating the performance of such large systems typically requires the solution of a queueing network model with a large number of closed chains, which precludes the use of exact solution techniques. Therefore, it is important to develop accurate and cost-effective methods for the approximate analysis of closed queueing networks with many chains. In this paper, we present an approach based on the clustering of chains and service centers. The method is applicable to queueing networks with single server fixed rate, infimite server and multiple server service centers. We present the results obtained when the method is used to solve large queueing network models. Extensive comparison of this method to existing approximation techniques indicates that the approach has better accuracy/cost characteristics.

We consider a probabilistic model of locking in a database system in which an arriving transaction is blocked and lost when its lock requests conflict with the locks held by currently executing transactions. Both exclusive and shared locks are considered. We derive a simple asymptotic expression for the probability of blocking which is exact to order 1/N where N is the number of lockable items in the database. This expression reduces to one recently derived by Mitra and Weinberger for the special case where all locks are exclusive.

The quantitative evaluation of computer performance is needed during the entire life cycle of a computer system. We survey the major quantitative methods used in computer performance evaluation, focusing on post-1970 developments and emphasizing trends and challenges. We divide the methods used into three main areas, namely performance measurement, analytic performance modeling, and simulation performance modeling, which we survey in the three main sections of the paper. Although we concentrate on the methods per se, rather than on the results of applying the methods, numerous application examples are cited. The methods to be covered have been applied across the entire spectrum of computer systems from personal computers to large mainframes and supercomputers, including both centralized and distributed systems. The application of these methods has certainly not decreased over the years and we anticipate their continued use as well as their enhancement when needed to evaluate future systems.

article Free Access Share on Corrigendum: `` Mean-Value Analysis of Closed Multichain Queuing Networks'' Authors: M. Reiser View Profile , S. S. Lavenberg View Profile Authors Info & Claims Journal of the ACMVolume 28Issue 301 July 1981https://doi.org/10.1145/322261.322275Published:01 July 1981Publication History 6citation363DownloadsMetricsTotal Citations6Total Downloads363Last 12 Months6Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

It is shown that mean queue sizes, mean waiting times, and throughputs in closed multiple-chain queuing networks which have product-form solution can be computed recursively without computing product terms and normalization constants. The resulting computational procedures have improved properties (avoidance of numerical problems and, in some cases, fewer operations) compared to previous algorithms. Furthermore, the new algorithms have a physically meaningful interpretation which provides the basis for heuristic extensions that allow the approximate solution of networks with a very large number of closed chains, and which is shown to be asymptotically valid for large chain populations.

Closed queuing networks arise naturally as models of multiprogrammed computer systems and subsystems. Techniques for the efficient simulation of such models can be obtained from analytical results on the stochastic structure of the queuing networks. In this paper, confidence intervals are derived for a class of new work rate estimators in a closed queuing network. Numerical results are given which demonstrate that a substantial reduction in the length of confidence intervals is obtainable by use of the proposed estimators.

We formulate a class of closed queueing network models which can be used to represent certain features of multiprogrammed computer systems having multilevel storage hierarchies. The resources which comprise the system are described by a network of interconnected multiserver stages where each stage can provide more than one type of service. The sequence of services required by a program executing in the system is described by a finite Markov chain over the service types. This description permits an explicit representation in the model of the data transfers which occur as determined by the data transfer rules and data paths in the hierarchy. The queueing discipline at each stage is nonpreemptive priority among the types of service provided by the stage, and first-come first-served within a service type. We derive simple expressions relating the work rates for different stages and obtain simple upper bounds on the work rates. These results are valid for general service time distributions. We then apply a model in this class to the analysis of a multiprogrammed three level staging hierarchy. Under the assumption that all service time distributions are exponential, we numerically investigate the effects on system performance of different service priorities and of varying the program load parameters and level of multiprogramming.

Several feedback coding schemes considered recently are repetitive signaling schemes. The sender retransmits the message, if necessary, on the basis of information received over the feedback channel. This paper considers a repetitive signaling scheme in which the user's estimate of the transmitted message is sent over the feedback channel to the sender with high energy if the user is uncertain of the estimate and with lower energy if otherwise. The sender retransmits the message with high energy if it decides the user's estimate is incorrect. This scheme is applied to a wide-band, additive-white-Gaussian-noise, average-power-constrained feedback communication system. Orthogonal signals are used for transmission over both forward and feedback channels. A lower bound is obtained for the probability of error when arbitrary decision rules are used. This lower bound is achieved asymptotically for long block duration by using decision rules implemented with correlation receivers. The resulting asymptotic error performance is superior to that of any feedback coding scheme previously considered for use in a wide-band additive-white-Gaussian-noise system for any values of the forward and feedback channel capacities.

A partition of the channel output space, which has the property that no other partition yields both a smaller probability of erasure and a smaller probability of error, is obtained and compared with a previous result due to Forney.

We consider a feedback communication system in which the forward and feedback channels are disturbed by additive noise and constrained in average power. Two block coding schemes are proposed in which the signals are orthogonal waveforms. A finite number of forward and feedback transmissions per message is made. Information received over the feedback channel is used to reduce the expected value of forward signal energy on all iterations after the first. Similarly, the expected value of feedback signal energy is reduced on all iterations after the first. These schemes, which are modifications of a feedback coding scheme due to Kramer, obtain improved error performance over one-way coding at all rates up to the forward channel capacity, provided only that the feedback channel capacity is greater than the forward channel capacity. They require less feedback power than existing feedback coding schemes to achieve a given error performance.