A model is developed for representing computations that arise when deterministic algorithms process workloads whose detailed structure is uncertain. The new computational model, which is based upon the notion of loosely constrained deterministic systems (LCD systems), incorporates a characterization of uncertainty that is expressed entirely in terms of observable properties of the computation itself. This provides a number of advantages over traditional probabilistic models. In addition to providing a more direct link to problems that arise in practical settings, LCD models offer a new perspective on the analysis of risk and support a new method for improving the efficiency of certain computer driven simulations.

Expressions are presented for RPS reconnect delays in three basic cases: single path, multiple path with static reconnect, multiple path with dynamic reconnect. The assumption of homogeneous reconnects, which is introduced in the analysis, is shown to be implicit in many prior analyses. This assumption simplifies the resulting equations, but more general equations are also presented for the case where homogeneous reconnects are not assumed. These general results have not appeared previously. This paper also uses the assumption of constrained independence to derive a result for static reconnect which has only been derived previously using the maximum entropy principle. In the case of dynamic reconnect, constrained independence yields an entirely new closed form result. In addition to being a consistent extension of the static reconnect case, this new result is the only closed form expression for dynamic reconnect that yields a correct solution in certain saturated cases. Constrained independence can provide a useful alternative assumption in many other cases where complete independence is known to be only approximately correct.

This tutorial will present techniques for modeling the performance of I/O subsystems that incorporate channels, control units, string controllers and direct access devices. The presentation will focus on the general principles involved in analyses of this type, and will explore the strengths and weaknesses of alternative assumptions. Attendees should gain an overall understanding of basic analysis procedures so they can deal with alternative I/O architectures that are not treated explicitly in the presentation.The material in this tutorial is mathematically oriented, and attendees should have some familiarity with basic queueing theory. However, the presentation is almost entirely self contained, and all important concepts and equations will be fully explained. Operational analysis will be used throughout to simplify the derivation of major results and clarify the assumptions required at each stage.

Response Time Preservation (RTP) is introduced as a general technique for developing approximate analysis procedures for queueing networks. The underlying idea is to replace a subsystem by an equivalent server whose response time in isolation equals that of the entire subsystem in isolation. The RTP based approximations, which belong to the class of decomposition approximations, can be viewed as a dual of the Norton's Theorem approach for solving queueing networks since it matches response times rather than throughputs. The generality of the RTP technique is illustrated by developing solution procedures for several important queueing systems which violate product form assumptions. Examples include FCFS servers with general service times, FCFS servers with different service times for multiple classes, priority scheduling, and distributed systems.

Token rings and multipoint polled lines are two widely used network interconnection techniques. The general concept of cyclic allocation processes is defined and used to characterize token passing and polling in these networks. Scan time, the time to poll all nodes at least once, is an important quantity in the response time analysis of such networks. We derive expressions for the mean and variance of scan times using a direct, operational approach. Resulting expressions are general and are applicable to both exhaustive and non-exhaustive service. The effect of higher level protocols is easily incorporated in the analysis via calculations of constituent quantities. The expression for mean scan time is exact and depends only on the means of message transmission times and arrival rates. The approximate analysis of variance takes into account the correlation between message transmissions at different nodes. Expected level of accuracy is indicated by an example.

Approximations are given for the mean response times of each priority level in a multiple-class multiserver M/G/m queue operating under preemptive resume scheduling. The results have been tested against simulations of systems with two and three priority classes and different numbers of servers.

An important problem in queueing network modeling is that of characterizing and analyzing relationships among alternative models of a single system. The problem is approached by developing the concept of a state space transformation, which is a mechanism for expressing the way one model can be mapped into another. After discussing state space transformations in general terms, some important transformations are presented. The usefulness of the technique is demonstrated by developing state space transformations for the shadow CPU technique for analyzing preemptive priority scheduling and the aggregate server method for modeling serialization delays.

Method for Analyzing Computer SystemsThe aggregate server method is an approximate, iterative technique for analyzing the delays that programs encounter while waiting to enter critical sections, non-reentrant subroutines, and similar software structures that cause processing to become serialized.The method employs a conventional product form queuing network comprised of servers that represent actual I/O devices and processors, plus additional aggregate servers that represent serialized processing activity.The parameters of the product form network are adjusted iteratively to account for contention among serialized and nonserialized customers at each physical device.The algorithm is developed for single-class closed queuing networks with load-independent servers employing processor sharing scheduling disciplines.Validations based on comparisons with exact numerical solutions are presented, and some factors affecting the accuracy of the method are discussed.Extensions to multiclass queuing networks, variable rate servers, and other scheduling disciplines are also suggested.

A number of laws are derived which establish relationships between throughput, response time, device utilization, space-time products and various other factors related to computer system performance. These laws are obtained by using the operational method of computer system analysis. The operational method, which differs significantly from the conventional stochastic modeling approach, is based on a set of concepts that correspond naturally and directly to observed properties of real computer systems. Except for measurement errors, the operational laws presented in this paper apply with complete precision to all collections of observational data, and they are similar to fundamental laws found in other areas of engineering and applied science.

Queueing network models are well suited for analyzing certain resource allocation problems associated with operating system design. An example of such a problem is the selection of the level of multiprogramming in virtual memory systems. If the number of programs actively competing for main memory is allowed to reach too high a value, trashing will occur and performance will be seriously degraded. On the other hand, performance may also suffer if the level of multiprogramming drops too low since system resources can become seriously under utilized in this case. Thus it is important for virtual memory systems to maintain optimal or near optimal levels of multiprogramming at all times.