THE UNIVERSITY OF MICHIGAN SYSTEMS ENGINEERING LABORATORY Department of Electrical Engineering College of Engineering SEL Technical Report NOQ 52 SOLUTION OF MARKOV RENEWAL DECISION PROCESSES WITH APPLICATION TO COMPUTER SYSTEM SCHEDULING by John Wesley Boyse under the direction of Professor Keki B. Irani June 1971 under contract with: ROME AIR DEVELOPMENT C Research and Technology Dir Griffiss Air Force Base, New York Contract No. F30602-69-C-0214

1;t~!t' tf X vt sK3w —;

AC KNOWLEDGE ME NTS During the course of this research, help was received from m any people. Professor K. B. Irani and the other members of my doctoral committee deserve special mention in this regard. Needed financial support was provided by Rome Air Development C enter (Contract No. F30602-69-C-0214). Finally, I thank my wife, Georgia, for her help in preparing the manuscript as well as for her support and encouragement.

TABLE OF CONTENTS Page LIST OF TABLES v LIST OF FIGURES vii ABSTRACT xi Chapter INTRODUCTION 1 1. 1 The Computer System 2 1. 2 Modelling Computers 9 1.3 Queues, Markov Processes, and Optimization 13 1. 4 Computer Performance Data 20 2 MARKOV RENEWAL DECISION PROCESSES 21 2. 1 Infinite Time Processes 25 2. 2 Transition-Optimal Problem 31 2.3 Time-Optimal Problem 46 2.4 Computational Considerations 79 3 MODELS FOR MULTIPROGRAMMING 83 3.1 Assumptions 86 3. 2 Mathematical Models 93 3.3 Regeneration and Decision Points 95 3.4 State Variables 100 3.5 Decision Variables 102 3.6 Submodels 106 3.7 Transition Probabilities 122 3.8 Reward Matrix 129 3.9 Overhead 130 3. 10 Summary 132 4 EFFECTS OF SCHEDULING AND SHARED INFORMATION 134 4. 1 Scheduled Tasks 134 4.2 Use of Reentrant Code 136 111

TABLE OF CONTENTS (continued) Page 4.3 CPU and I/O Interval Distributions 138 4.4 Pagirg 139 4.5 Number of CPU-I/O Intervals 142 4.6 Central Processors 143 4.7 Loading Scheduled Tasks 147 4. 8 MTS Results 148 4.9 Implementation 156 4. 10 Increased Multiprogramming 161 4. 11 Further Results 168 5 CONCLUSION 178 Appendix A: EXTENT OF PAGE SHARING IN MAIN MEMORY 184 A Appendix B: COMPUTATION OF e 195 Appendix C: DISPERSION OF MEMORY REQUIREMENTS WITH DEGREE OF MULTIPROGRAMMING 203 Appendix D: DATA COLLECTION AND ANALYSIS 208 D. 1 System Description 208 D. 2 General Data 209 D. 3 Analysis for Specific Types of Tasks 210 D. 4 Fortran Compiler (IBM Level G) 213 D. 5 Fortran Compiler (University of Waterloo) 219 D. 6 Assembler 220 D. 7 Line File Editor 225 D. 8 User-generated Tasks 230 Appendix E: REACHABILITY OF STATE m+(L-1)N 241 Appendix F: CONVERGENCE OF GAIN RATE BOUNDS IN SCHEDULING MODEL 249 Appendix G: SCHEDULING POLICIES 252 BIBLIOGRAPHY 283 iv

LIST OF TABLES Table Page 4.1 Parameter Values Derived From MTS Data 152 4o 2 Parameters For Results in Figure 4. 9 171 4.3 Parameters For Results of Figure 4. 10 173 4.4 Parameters For Results of Figure 4.11 177 A. 1 Pages Used By Single Task 192 D. 1 CPU Use During Data Collection (seconds) 209 D. 2 Fortran Execution Data 216 D. 3 Data for Figure D. 5 216 D. 4 Watfor Execution Data 219 D. 5 Assembler Execution Data 220 D. 6 Data For Figure D. 13 225 D. 7 Editor Execution Data 230 D. 8 User Program Execution Data 236 D. 9 Parameters For Figure D. 21 236 G. 1 Scheduling Policy For Figure 4. 5 (70 Pages, No Sharing) 253 G. 2 Scheduling Policy For Figure 4, 5 (70 Pages, Sharing) 256 Go 3 Scheduling Policy For Figure 4. 5 (90 Pages, No Sharing) and Figure 4. 6 (2) 260 G.4 Scheduling Policy For Figure 4. 5 (90 Pages, Sharing) and Figure 4. 6 (4) 264 G. 5 Scheduling Policy For Figure 4. 6 (6) 270

LIST OF TABLES (continued) Table Page G. 6 Scheduling Policy For Figure 4. 10 (1, 40 Pages) 274 G. 7 Scheduling Policy For Figure 4. 10 (1, 50 Pages) 275 G. 8 Scheduling Policy For Figure 4. 10 (3, 50 Pages) 277 G. 9 Scheduling Policy For Figure 4. 10 (3, 55 Pages) 278 G. 10 Scheduling Policy For Figure 4. 11 (60 Pages, No Sharing) 280 G. 11 Scheduling Policy For Figure 4. 11 (60 Pages, Sharing) 281

LIST OF FIGURES Figure Page 1.1 Cyclic Network of Queues and Services 15 1. 2 Replacement of Exponential Service With Exchange-2 Service 15 2. 1 Disjoint Recurrent Classes of States Under'Two Distinct Poiicies 40 2. 2 Two Recurrent Classes of States Under Policy (3 40 2.3 The Matrix U 57 2.4 The Howard Algorithm 81 3.1 System Block Diagram 85 3. 2 Task Flow in System 87 4.1 Cumulative Distribution of CPU Time (t) Used Between I/O Operations By Scheduled Tasks Other Than Fortran 140 4. 2 Cumulative Distribution of Time (t) Used Per I/O Request By Scheduled Tasks Other Than Fortran 141 4.3 Cumulative Distribution of Number (n) CPU-I/O Cycles Before Termination For Fortran Compiler 144 4,o4 Cumulative Distribution of Number (n) CPU-I/O Cycles Before Termination For Scheduled Tasks Other Than Fortran 145 4, 5 Comparison of Throughput Using Parameters Derived From MTS Data 149 4. 6 Throughput Using Parameters Derived From MTS Data 150 4.7 CPU Interval Between Page Faults As a Function of Mean Number Pages in Core During Interval 163

LIST OF FIGURES (continued) Figure Page 4.8 CPU Interval Between Page Faults As a Function of Mean Number Pages in Code During Interval 164 4.9 Variation of Throughput With Scheduling Policy and Relative Task Arrival Rates 170 4.10 Comparison of Throughput 174 4.11 Comparison of Throughput 176 B. 1 Maximum Possible Error in Any Element of Series Approximation to eA 198 B. 2 Matrix Multiplications to Compute eA Using BB /k.' 202 C. 1 Fraction of Memory Required in Excess of Mean Requirements 206 C. 2 Memory 10% in Excess of Mean Requirement 207 D. 1 Cumulative Distribution of Time (t) From Page Demand Until Page Available 211 D. 2 Cumulative Distribution of CPU Time (t) Used Between I/O Operations During Fortran Compilations 214 D. 3 Cumulative Distribution of Time (t) Used Per I/O Request During Fortran Compilations 215 D. 4 Cumulative Distribution of CPU Tim e (t) Used Between Page Faults During Fortran Compilations 217 Do 5 Cumulative Dis tribution ofC PU Tim e (t) Used Between Page Faults as a F unction of the Number of Pages in Core for Fortran Compilations 218 D. 6 Cumulative Dis tribution of C PU Time (t) Used Between I/O Operations During Watfor Executions 221 D. 7 Cumulative Distribution of Time (t) Used Per I/O Request During Watfor Executions 222 viii

LIST OF FIGURES (continued) Figure Page D. 8 Cumulative Distribution of CPU Time (t) Used Between Page Faults During Watfor Executions 223 D. 9 Cumulative Distribution of CPU Time (t) Used Between Page Faults As Function Number Pages in Core During Watf or Executions 224 D. 10 Cumulative Distribution of CPU Time (t) Used Between I/O Operations By Assembler 226 D. 11 Cumulative Distribution of Time (t) Used Between Page Faults by Assembler 228 D. 13 Cumulative Distribution of CPU Time (t) Used Between Page Faults As Function Number Pages in Core For Assembler 229 D. 14 Cumulative Distribution of CPU Time (t) Used Between I/O Operations By Editor 231 D. 15 Cumulative Distribution of Time (t) Used Per I/O Request By Editor 23 2 Do 16 Cumulative Distribution of CPU Time (t) Used Between Page Faults By Editor 233 D. 17 Cumulative Distribution of CPU Time (t) Between Page Faults As Function Number Pages in Core For Editor 234 D. 18 Cumulative Distribution of CPU Time (t) Used Between I/O Requests By User-generated Tasks 237 D. 19 Cumulative Distribution of Time (t) Used Per I/O Request By User-generated Tasks 238 Do 20 Cumulative Distribution of CPU Time (t) Used Between Page Faults By User-generated Tasks 239 D. 21 Cumulative Distribution of CPU Time (t) Used Between Page Faults By User-generated Tasks as Function Number Pages in Core 240 1Y

LIST OF FIGURES (continued) Figure Page Eo 1 Transition Tree 244 E. 2 Transition Tree Showing Alternatives Which Determine Possible Transitions 245

ABSTRACT In multiprogrammed computer systems, the way in which system resources are allocated among tasks can strongly influence system efficiency. In such systems, as opposed to monoprogrammed computers, separate but interdependent consideration must be given to scheduling of two critical system resources:main memory and the central processors. A rather wide class of scheduling procedures is available to the designer of such a system, and so it is useful to be able to determine task priority rules which allow the maximum number of task completions per unit time or throughput. This research pursues the theoretical development and application of Markov renewal decision processes for this purpose. A major effort is devoted to theoretical development of a new technique for finding the optimal stationary policy in a class of infinite time Markov renewal decision processes in which the criterion is either maximization of expected return per transition or maximization of expected return per unit time. The modeling of stochastic service systems with Markov renewal decision processes commonly leads to transition matrices which are sparse, and the derived optimization method offers definite computational advantages for this wide class of practical problems.

A Markov process is used to model a problem of current import in the software design of multiprogrammed computer systems; namely, the problem of assignment of central processors and main memory to those jobs requesting them. Application of the optimization method to this model allows the determination of scheduling rules which maximize throughput. An additional complexity in scheduling arises when tasks are allowed to share information with other tasks in main memory, and this problem is treated also. Parameters which may be varied in the model include the size of the main memory relative to the sizes of individual tasks, the execution characteristics of tasks themselves, the number of central processors, and the fraction of its total memory requirement each task may share with other tasks. Paging is important in many modern computer systems and is treated indirectly in the model by treating it as a special kind of input/output operation. Results for a range of values of parameters are presented which compare the throughput possible under optimal scheduling rules and under a good heuristic scheduling rule. In order to obtain results applicable to a typical general purpose multiprogrammed computer system, data from such a system were collected and analyzed in order to set appropriate values for parameters of the model and also to test the validity of certain assumptions made in the model. These data are general enough to be of interest in their own right and are therefore presented in the form of graphs and tables as part of this research effort. xii

Chapter 1 INT'RODUC TION The work reported here is organized around the problem of determining how much the efficiency or multiprogrammed computer systems may be increased by altering the scheduling rules in these systems and by the use or shared intormation (e. g. reentrant procedure). In particular, the efficiency is proportional to the throughput (number ot jobs processed per unit of time), and it is this quantity we determine as algorithms tor scheduling these jobs are varied. Also investigated is the change in throughput when jobs are allowed to share information with one another in the execution store of the computer. The effort expended in attacking the above problem may be divided into three major categories. 1) A suitable mathematical model was developed to allow comparison or scheduling rules and investigate the etfect of shared intormation. 2) Derivation ot an optimization technique was carried out which can be used to find scheduling algorithms which maximize throughput. This optimization method is applicable to a broader class ot problems than the one presented in this the sis. 3) Collection and analysis or data brom a large multiprogrammed computer system were carried out so that suitable values

could be given parameters of the mathematical model. An ancillary benefit of this effort was validation of some assumptions made in the mathematical model, In the following sections the work outlined above is placed in proper context for consideration in detail in other chapters. The problem of modelling a multiprogrammed computer system is placed in the milieu of current systems of this type, and then some previous computer models are reviewed and possible methods of modelling such systems are discussed. The computer model developed in this report is a Markovian queuing model and so for completeness pertinent definitions from queuing and Markov renewal theory are presented. The final section is a brief discussion of computer performance data. 1. 1 The Computer System In this work we are primarily concerned with characterizing multiprogrammed computer systems. Multiprogramming is the simultaneous residence of more than a single program or task in the execution store (core) ot the computer. Many modern computing systems operate in this mode in order to make more etficient use of system resources0 In older monoprogrammed systems it was tound that often the central processing unit (CPU) was idle a signiticant portion OI the time while a job was carrying on an input/output (I/O) operation. On the other hand, input/outpat devices were otten idle while processing was going on. Even overlapping processing with I/O left these devices unused asignificant time and so the high cost of having these devices stand idle (especially the central processor) led designers to systems which allow

more than a single job in main memory. This allows the CPU to switch to another task when the task currently in execution is held up by an I/O request. This may considerably increase CPU utilization and that of other devices as well. On the other hand, the amount of main memory required for successful multiprogramming is considerably greater than that required when only a single program is in core. Since core memory is also an expensive resource, it is desirable to use this as efficiently as possible as well. The key to efficient use of the main memory is the proper scheduling of tasks wishing to use this resource. In fact, getting the greatest possible system throughput or CPU utilization at peak load times requires careful choice of scheduling rules for both the main memory and central processors, and in order to attack the problem of making these choices intelligently, it is necessary to understand the structure and characteristics of multiprogrammed computer systems. The remainder of this section is devoted to a description of the structure of typical multiprogrammed computers as background for the computer system model which is developed in Chapter 3 and which is used to evaluate task scheduling rules in such computers. In many multiprogrammed computer systems many tasks require either identical procedure (code) or possiDly make use ot the same data as other tasks. In a general purpose computing system, this is most likely to occur because many users require the same routines such

as compilers and assemblerso In a more specialized environment, data bases may be required by multiple users. If two or more such tasks are multiprogrammed together then it may be possible for the two tasks to share a single core copy of the information common to both. This may result in significant savings ot memory. It should be noted, however, that the additional hardware and/or soItware needed to implement this capability may be non-trivial in some systems. Reentrant or pure procedure is procedure which does not modity itselt in the course of execution. This makes it possible tor more than one user to execute the same copy ot this code without fear that it has been modified by another user. There are other advantages to the use ot such procedure besides the savings in memory requirement. The traffic on the channel used to bring this procedure into memory is reduced because only one copy is brought in for multiple users. The traffic may be turther reduced because this intormation need never be removed trom main memory if the task is swapped or paged out. Since the procedure is never changed, a copy can be maintained external to main memory and the copy in main memory may simply be overwritten. Another advantage is the reduction in time required to load a task into the core when the procedure required by that task has already been loaded.'rhe same comments apply for the sharing oI data among tasks except that additional complexities may arise if some or all tasks are

allowed to make changes in these data. To avoid errors it may be necessary for a task making changes to the data to prevent other tasks from accessing the data until changes are complete. This level of detail is not considered further in this reporto It was mentioned above that the cost of sharing information among users may be the introduction of additional operating system overhead. Many multiprogrammed computers in use today, however, have features which minimize this additional cost; and in tact, were designed to make such sharing easy to implement. The two-level address translation hardware in use on many machines today facilitates the sharing of pages by users. This addressing structure and the hardware necessary to implement it are described in papers by Arden, et. al.[ 2] and by Dennis [14]. The IBM/360 Model 67 has such hardware. Machines like this also include the ability to maintain in core only' those parts of a program which are currently in use, and to use an address space much larger than the physical memory available. This separation ot the physical address from the logical address gives rise to the term virtual memory, Programs are broken into fixed-size units called pages and these units are brought into core when needed and removed from core when they are no longer being used. Commonly, pages of a task that are not in core are brought into core when they are referenced by the task. At this pointthe program is ineligible to execute until the page has been moved into main memory trom some secondary storage medium. This is, in essence, simply another input/output operation

although in this case the number of such input/output operations will depend on the memory management policies used by the operating system rather than solely on the program being run, Determining what pages to remove from core to make room for newly requested pages is more complex, but may involve attempting to identify and remove those pages which have been least recently referencedo Paging allows a greater number ot tasks to share core simultaneously than would be possible in a multiprogrammed system operating in a real core environment. In this sort of system the entire task must be in main memory before execution can begin although of course programmer controlled overlays are possible. The use of paging and virtual memory become especially attractive uwhen the multiprogrammed system is also time-shared. In a time-shared system, many of the terminal users are likely to be running highly interactive tasks during most of the time they spend at the terminal. With tasks like these, the mean real time between references to a page is long (seconds) even though the mean CPU time between such reterences may be short (milliseconds). This occurs because ot the long time required by users at terminals to make responses relative to response t imes of other input/ output devices, and also because an interactive task is quite likely to reference only a relatively small traction of its total pages between two te rllillnl inlteractions. Ttris is espe,cially lilkely, bor examp;ule, duringr: on-line debugging o1 a program, where the user may interrupt the program Irequently to displ>.a 2,e, al ~ziter varia l.es and where program in

terrupts may occur. In situations like this, the mean number oi pages in memory may be substantially less than the total number of pages the task has, and therefore a higher degree o1 multiprogramming (i. e. more programs may simultaneously share core) is possible than in a system where the entire task must be in core. Looked at in another way, only the pages requested for a single interaction need be swapped in and out of core, rather than the entire task. The mathematical model developed in this report applies to both virtual and real memory machines which may be multiprogrammed. Use of a real core machine is more likely in a batched system, and of course, this is a very important application of computer systems also. Other important facets of modern computing machines include the possibility ot multiple central processing units and a diversity of devices for input and output; neither of these causes any difficulty in the mathematical model. The strategies used by the operating system are also important to the characterization ot the computing system. In particular, the task scheduling strategies may be quite important to the system's operation. Scheduling of one form or another must occur whenever there are resources to be allocated; the three major classes of resources are the main memory, the central processors, and input/output channels and devices0 We are explicitly concerned with scheduling the first two of

these in this report. The scheduling of input/output devices may usually be treated satisfactorily as a problem local to that device: the diversity and complexity of many of these devices make it extremely difficult to treat them in detail in the context of the system as a whole. Good procedures for scheduling tasks become less obvious ao we move from monoprogrammed, batch systems up to multiprogrammed, time-shared systems with virtual memory. The rule may simply be first-come -first-serve (FCFS) in a monoprogrammed, batch system or, if job lengths can be determined a priori, a shortest job first policy may be followed since this minimizes mean turn -around time. In this system, memory scheduling and CPU scheduling are synonymous. If this system is time-shared, we may wish to give each queued job a short period of execution, called a time slice, then swap it out to make room for another it it has not terminated. This is called round-robin service and prevents a long job from causing a long delay to a short job although the mean response time to users remains about the same as ior FCFS service [221. The choice of time slice is important because there is an overhead time cost every time tasks are swapped while unhappy users may result if the time slice is too long. When we move to a multiprogrammed system, the problem increases in complexity because now the CPU and memory must be scheduled separately, although there is some interdependence since tasks not in memory cannot use the cerntral processor. FCFS queues may

be used, but it is not at all clear that this policy makes best use of system resources. In fact, a last-come-first-serve (LCFS) piodicy is used by the computing center at the University of Michigan because a job usually arrives at this queue after completion of an input or output operation and is theretore assumed likely to be an I/O bound job (i.e., a job wh ich uses large amounts of I/O time relative to CPU time used) which will relinquish the CPU atter a very short CPU interval, This prevents compute bound jobs from keeping I/Obound jobs queued at the CPU and therefore unable to carry out their IP operations. I t'the multiprogrammed system is time-shared as well, we may want to consider applying a time slice to tasks using the CPU and perhaps to the use of main memory as wello 1o 2 Modelling Computers Many mathematical models, both for computer systems as a whole and for selected aspects of computer systems (e. g. drums) have been developed and can provide valuable insight into the operating characteristics o1 such systems and subsystems0 These systems may generally be characterized as stochastic service systems and analytic or simulation models may be used to study relations between parameters of the systems. Analytic models, which usually tall into the class ot Markovianqueueing models, may be further subdivided into those which yield a closed form solution to quantities of interest in terms of input parameters, and those which do not yield to closed form analysis

in this way but may be solved using numerical methods. The model developed in this report falls into the latter class, The remainder of this section is devotedto a review of models which have some applicability to the problem attacked in this thesis; namely, the effects of shared information and scheduling rules on throughput of a multiprogrammed computer system. Few analytical results are available which are applicable to the problem of sharing in computer systems. Furthermore these re sults apply only to a monoprogrammed system where the saving trom using shared procedure accrues by not having to re -load procedure used by two successive arrivals to the system. A rather large volume of literature9, 25, 27, 35,44] has been published which gives analytical results from models of time-shared computer systems. Unfortunately, the results are generally for round-robin or some similar form of service in a monoprogrammed system, and so the results are not usetul for investigation of the additional complexities which arise with multiprogramming. Gaver [20] develops a cyclic queueing model of a multiprogrammed computer system. He assumes a fixed number of indistinguishable tasks in memory which alternate between periods of CPU use and I/O operations except where they are queued at these devices. Duration of I/O operations is assumed exponentially distributed, but several distributions are given for the duration of a CPU operation. Results are in terms of CPU

utilization which, after multiplication by a constant, may be equated directly to system throughput. Tables of results show CPU utilization as a function of number of I/O devices, number of tasks in memory,,/O device speed, and distribution on CPU interval length. Scheduling is not an issue in this model because tasks are indistirnguishable from one another. If we wish to investigate scheduling rules in a system in which tasks are differentiated, we must turn to a multi-queue model. Results are extremely limited and difficult to get. Eisenberg [ 15] and Leibowitz [31,32] both obtain results to multi-queue problems. Eisenberg's results are most useful for application to scheduling tasks although the results are again liited to a monoprogrammed computer system. Eisenberg treats the case of two queues with general distributions on the service time and Poisson arrivals to each queue. Only one job may receive service at a time. If at the completion of a task in one queue it is decided to service another task in the same queue, service begins immediately. If, on the other hand, it is decided to service a task in the other queue, a changeover time is required before service may begin in that queue. Applying this model to the problem of sharing in a monoprogrammed computer system, the two queues represent the two types of tasks which are arriving at the system. The time to move from service of queue 1 to queue 2 is ju,it the time required to

12 load the sharable information for task type 2 and vice-versa. The service time for a task is just the time to load the non-sharable information for that task and execute it. Eisenberg obtains expressions for the mean waiting times of tasks in each of the queues under two service disciplines: alternating priority and strict priority. Under alternating priority, tasks of one type are serviced until there are no more tasks ot that type in the system. A changeover to the other queue then occurs and service ot tasks in that queue proceeds until it is empty, etc. Under strict priority, queue 1 is always given priority over queue 2. The expressions for the mean waiting times are very complex, even for this case of only two queues (two types of tasks). These results and the difficulties encountered in obtaining them indicate the tutility of trying to obtain closed form results from a queueing model representative of a multiprogrammed computer with several types of tasks which may share information. One method of modelling which may be used to investigate scheduling policies when tasks are differentiated is simulation. Among others, PinkertonFl1 ] and.Nielsen [36] have both developed simulation models of multiprogrammed computer systems. Lasser [30], however, points out that a simulation model which attempts to account for both "macroqueuing" (e. g. queuing for memory) and "micro-queuing" (e. g. queuing for the CPU) may be very expensive to run because of the large number of "micro" events one must consider in order to obtain a sufficient

sample of "macro" events. Nielsen [361 reports using 5-10 minutes of Burroughs B5500 processor time to simulate each minute of operation of a Burroughs B6500 system. Furthermore, simulation models do not lend themselves easily to determination of optimal system configurations and operating policies. Simulation can, however, be a very useful tool, and can provide a level of detail in modelling not attainable by any other means. The approach to the problem taken in this report is to develop a large Markovian queueing model which yields the quantities bf interest by application of numerical methods. Wallace and Rosenberg [56] discuss this approach to modelling which represents a middle ground between closed form solution of queuing models and simulation. Furthermore, Markov models of this sort lend themselves to application ot optimization techniques if appropriate objectives can be tound. In this work the objective is maximization of system throughput which is linearly related to CPU utilization, and the problem is then formulated as a Markov renewal decision process (MRDP). L 3 Queues, Markorv Processes, and Optimization It is the purpose of this section to provide definitions and background for material which appears in later chapters. Some mathematical rigor may be sacrificed to simplify the exposition. A network of queues and service facilities may be used to characterize a computer system~ Queues may occur at central processors,

I/O devices, and at the main memory of the computer, which are in turn the service facilities; and these service facilities may: have; arbitrary probability distributions on their service times. These arbitrary distributions may often be reasonably approximated by a network of servers with exponentially distributed service times [34 ]; this is done to make the model Markovian and therefore tractable to analysis. As a simple example, consider the cyclic queuing system shown in Figure 1. 1. The circles indicate queues and each square an exponential server. The mean service times are 1/i and 1/a in service facilities 1 and 2 respectively. Whenever a service facility becomes free, a new customer immediately enters it providing, of course, that there is a customer enqueued. A state for this simple network can be specified by a single number giving the number of customers queued at or in service at service facility 1. Since the network is cyclic, there is a constant number of customers in the system (say N); and so with m customers at facility 1, there are N -m at facility 2. We have N+1 states, 0, 1, 0 0 a, N; and may be interested in determining, for example, the probability of being in state j at time t given that state i is occupied at time 0.. If service distributions are not exponential in the physical system being modelled, the exponential servers may be replaced by networks of exponential servers in ord er to approximate the desired distribution0 This is discussed in MIorse [34 and a simple example is shown in

ii i-i i1 5 QUEUE 1 SERVICE QUE UE 2 SERVICE FACILITY FACILITY 1 2 Figure 1. 1. Cyclic Network of Queues and Servers r-.........-...... I I SERVICE FACILITY 1 Figure 1. 2. Replacement of Exponential Service With Erlang - 2 Service

Figure 1. 2 where the exponential service facility 1 has been replaced by Erlang-2 service. The dashed lines are intended to indicate that only one of the servers may be occupied at any one time. The exponential server with mean service time 1/M has the useful p-pet- Zhat the remaining service time is exponentially distributed with mean 1/, independent of the quantity of service already received. This property makes probabilities of being in particular states at any time in the future dependent only on the current state, and not on any past history of the queuing network. This is the Markov property and is very useful and widely used in the modelling of stochastic service systems. The definition of a Markov process is formalized as follows [38 ]o In this work we consider only discrete state Markov processes (often called Markov chains) with a finite number of states. We may use the set of integers{O, 1, 0 0., N} to denumerate the states of the Markov process and denote the state of the process at time t by X(t)o If the state, X(t), is observed at any sequence of time instants 0 <t <tl2<. <tn, and the relation Pr [X(tn)= xn X(t) =X oo.,X(tn 1) = n-l] = Pr [X(tn) = x X(tn-) =x n-] (1. 1) holds, then the process is a continuous parameter Markov chain. When the ti are restricted to integer values, the process is called a discrete parameter Markov chain. If, in addition, the conditional probability in Equation (1. 1) is dependent only on the difference, t -t1 the Markov process is homogeneous and has stationary tranlsition probabilities.

Denote by p (t), the probability that at time t, state n is occupied in the example of Figure 10 1o The probability of going from state n to state n-1 (n>O) in a very short interval At is approximately 1 -e,At N ~At Using this approximation, the following equation may be written. P n (t + At) = Pn 1 (t) gAt + Pn (t) [ 1 - (, +a ) At] + Pn + 1 (t) a At; 0 <+n < N Taking lim we get At-O dpt n (t) = p (t)-(I+a), (t)+ p Pn+(t); < n < N Similarly, equations for n = 0 and n =N lead to dpo = - a po (t) + aPl (t) dt dPN(t)'PN1t)pNt dt = PN- 1 (t) - gP p -(t) Letting p(t) = o(t), Pl(t),... PN(t)), an N+1 dimensional row vector, and calling A the matrix of coefficients in the differential equations above, we have dp(t) = p (t) A dt The coefficients are called transition intensities and A a transition intensity matrix0 The procedure outlined above may be applied to more complex networks and the equations solved to find, bor example, the

probability that state j is occupied at time t given that state i is occupied at time 0, i.e. given that pi(O)=1. Solution to such systems of differential equations will be required in the computer system model developed in Chapter 3. We make use of Markov renewal processes as well as the continuous parameter Markov processes defined above where again only homogeneous processes with a finite number of states are of interest. Markov renewal processes are generalizations of the Markov chains discussed above. In Markov renewal processes the successive states form a Markov chain while the time between successive transitions is a random variable determined by a stationary probability distribution function which may depend on boththe current state and the state to which transition is made. In the Markov chain, the probability of making a transition from state i to state j may be denoted by Pijo The matrix of such transition probabilities, (Pij), is sufficient to generate successive states once the initial state is known, and these transition probabilities are independent of the length of the interval between successivci transitions. The distribution function used to determine the probability ilat the time required to make a transition directly from state i to state j is equal or less than T is denoted by F ij()o Thus, given that i-j transition is about to occur, the duration of this transition has probability distribution F.i (T) while the probability of making an i-j transition is Pij independent of the duration of the transition. These quantities are sufficient to define a Markov renewal

process which is a useful extension to the theory of Markov processes. Markov renewal processes are treated in detail in. [ 42]. In Chapter 3 a Markov renewal process with a finite number of states will form the computer system model. There is a one-one correspondence between a state in the model and a physical configuratio'n of the computer system only at the time points where state transitions occur (called regeneration points). A careful definition of system states is required to insure that the probability of making a transition to a particular state is dependent only on the current state and not on any other information about the past behavior of the system. After the states are defined it is necessary to find the transition probabilities among the states (pij) and the distributions on the intervals between transitions (Fij(r)). Determination of the transition probabilities necessitates the formation of a number of sub-models, each of which is a continuous parameter Markov chain. A return function, Rij (r), may also be defined for each transition i-j. It is then possible to determine both an average return per unit time or an average return per transition. If, in addition to this, choice of any one of several alternatives is available in each state, an optimization problem may be formulated. Suppose that in state i, alternatives 1, 2,..., K (i) are possibleuio, Fo (r), and R. (r) are the transition probability, distribution on transitiontime, and return using alternative k in state io

Optimization then involves choosing alternatives in each state to maximize expected return per unit time or per transition. These concepts are defined in more detail in Chapter 2. 1. 4 Computer Performance Data There is a paucity of data available which measure the performance of the various aspects of computer systems. One major reason for this is the difficulty and expense of collection and analysis of such data. Pre - viously published data on one aspect or another of system pertormance include Pinkerton [40, 41], and Walter and Wallace [ 57] at the University of Michigan, Varian and Coffman [ 10]; and Fine, Jackson, and McIsaac [18]. Data may be useful in providing parameter values to a model of a system and for validating assumptions made in a modelo Of course, this is true only in a limited sense, since one is not usually interested in modelling an existing system (the ultimate model has already been built) but in modelling a system similar to one in existence. Data available in the literature were not satistactory for the purposes of this study and so data were collected and analyzed yrom the Micnigan Terminal System (MTS). This is a large time-shared system implemented on an IBM System/360 Model 67 at the University of Michigan.

Chapter 2 MARKOV RENEWAL DECISION PROCESSES In this chapter we present a useful technique for the solution of a class of Markov-renewal decision processes (MRDP's) first formulated by Jewell [ 24. These processes are a generalization of the Markov decision processes described by Bellman[ 6] and Howard [23]. Briefly, MRDIP's are Markov-renewal processes with a finite number of states in which the parameters of the process (Pij and Fij(t)) are dependent on a controller which makes one of a finite number of choices at each transition. With each decision made by the controller are associated transition dependent rewards and the solution to the optimization problem consists of finding the set of decisions which maximizes the expected return as determined by the rewards. When occupying state i(i = 1,..., N), we choose one of a finite number of alternatives k(i) (k(i) = 1, 2,..., K(i)). For k(i) = k we have associated a transition probability pj, and distribution on transition interval, Fj(t). The reward under alternative k for making a transition from state i to state j is Rik (t |) where t < T is the elapsed time since the beginning of the transition interval which is of length T. Define R.k. ( R..(TT) Then

22 k 3 k o k Fk q 1 P.J T S R..J dF(T); (2.1) qi -Pij f eij( d ij j=1 o is the expected one transition return starting in state i and using alternative k. Note that if the transition interval is fixed and of length T then we have the special case N qk pk rij (2. 2) j=l k k where r.. = Rij (T). This is the case considered by Howard [ 23] 1] 1] and for this situation the more general rewards reduce to the above. We may define two distinct objectives for the controller. 1) Maximize the expected return per transition (called the transition-optimal problem here.) 2) Maximize the expected return per unit time (called the time-optimal problem here.) Bellman's "Principle of Optimality" [ 5 ] may be used to derive recurrence relations for these processes. These recurrence relations will specify the alternatives to be chosen at each transition in order to maximize expected returns. The recurrence relations for the two problems are given below. 1) The transition optimal problem. The recurrence relation is Vi(n) = max 4qi + 3 Pi. vj(n-1)] (2.3) k j=1 j

23 where vi(n) is the expected return given that an optimal policy is followed, we start in state i, and the process makes n transitions before terminating. vi(O) must be specified and is the boundary reward received for being in state i at the termination of the process. qk is the expected return for transition n as determined from Equation (2. 1). 2) The time-optimal problem. The recurrence relation is N oo wi(t)= max Pij { d Fij(7) [R + ( k j=1 t + d F(7) [R (7) + wj(t - 7) (2.4) wi(t) is the expected return given that an optimal policy is followed, we start in state i, and terminate the process after time interval t. w.(O)0 must be specified and is the boundary reward received for being in state i at termination of the process. k Sij (t, T) is a boundary reward received when the process terminates. It is a function of the two states involved in the transition which is interrupted at the time of termination and of the total time and elapsed time of this interrupted transition. The first term in the recurrence relation represents the expected

return if no transitions are made before the process terminates. The second term represents the return from one transition of time T < t plus the expected return in the remaining time, t - T. If there are no restrictions on the probability distribution functions, Fij t), it is clear that, in general, Equation (2.4) cannot be solved. Appropriate discrete approximations on the continuous time variable may, however, be made in order to obtain a solution. This is done by replacing the variable t by t=n A; n= 1, 2, 3,... and for some A>O; and by using the approximation nA n dF!] (T) W(. )F ((nA-))lw w(nA-Fka) 0 ij ()Wj(n- ) (2.5) With this restriction and approximation Equation (2.4) becomes N k wi(nA) -maxZ Pj {f dF i(T )[Ri(n AT) + Ski (nA, T) k j=1 nA + J dF ( T) Ri (T) 0 13 ij n + Fk [F. (A)-FFJ (CA-A)] w (nA-eA)} (2.6) which can be built up in the usual recursive manner. Of course, the accuracy of this approximation depends strongly on the choice of A. If all Fkj (t) are restricted to be lattice distributions with distribution spanml A, then the approximation becomes exact.

25 2. 1 Infinite Time Processes The recurrence relations given for the transition optimal and time optimal problems formulated in the preceding section provide a practical method of solution for these problems providing the number of iterations does not grow too large. In many practical problems, however, this is not the case and in fact we want to know the behavior of the recurrence equations as n-4oo and t-oo in Equations (2.3) and (2.4), respectively. The remainder of this chapter is devoted to solution of these problem s. Define a stationary policy, a, as an N-tuple which specifies a particular alternative in each of the N states. A recurrence equation for the expected return in n transitions when following stationary policy a may be written N a a aa v (n) q= + b ij v. (n-1) (2.7) Again, of course, a boundary rewardv a(0) must be specified for all i. Similarly, the expected return in time t when following stationary policy a is N w(t) = Pij {f dF (T)[Ii (t T) + (t, T) + ijt iJ ( t o dF (t T)] (2. 8)

26 It has been shown [ 24] t hat for reasonable restrictions (which will be given when needed in what follows) on the various parameters in (2. 7) and (2. 8) the following relations hold when a stationary policy is in use. vi (n)-> gan + vi as n -> c (2.9) w. (t)- > rat + w as t-> oo (2. 10) for all 1 < i < N and for appropriate constants v a and w. ga is called the gain or gain per transition, and eqthe gain rate or gain per unit time under policy a. For large n it is seen that ga is the expected return per transition, and for large t, 4'a is the expected return per unit time. Except in the unlikely event that ga or 1a equal zero, the total expected return, vi (n) and w. (t), both go to infinity as n and t go to infinity in Equations (2. 9) and (2. 10). Because it has been shown by Fife [ 16] that there exists an optimal stationary policy for each of the infinite stage and infinite time optimization problems, it is clear that the objective in these problems is to find that policy, a, which maximizes ga or VP in Equations (2. 9) or (2 10), respectively. The following theorem proves the result given in Equation (2.9) along with some related results which will be useful in the following sections. The result, given in Etluation (2. 10) is not needed in what follows but has been proved by Jewell [ 24].

27 Theorem 2. 1 Given a recurrence relation N vi(n) = q+ Pij vj (n- 1) (2. 11) vi(O) =ci; i= 2,..., N (2.12) in which the NxN stochastic matrix P=(p..) is acyclic and has a single closed communicating class of states so that there exists a vector of limiting state probabilities'r (11' * 9 *f. 7N) Such a recurrence relation could occur in a MRDP operating under a stationary policy, but no explicit indicator of policy is given in (2.11). Define gi(n) - (n) - vi(n-1); i=1, 2,..., N; n=1, 2,.... (2. 13) Then there exists a constant g such that N igi (n)= g for all n, (2. 14) i=l and furthermore the following equations must be true. lim [ vi(n) - gn-vi] =0 (2. 15) n — oO for all i and for some constant v.. N Z 7iqi =g (2.16) i =1

28 Proof Define a vector G (n) = (2.17) gN(n) and note that from the recurrence relation, the following equation must hold for all n. G (n) = PG (n-l) (2. 18) Pre-multiplying by the vector, 7r, get vr G (n) = ~i PG (n-l) By definition of the limiting state probabilities, the equation T = 7P must hold so that tG (n) = r G (n- 1) (2. 19) Since this is true for any n, it is clear that 7rG (n) is a constant independent of n which proves Equation (2. 14). Again, from the recurrence relation, it must be true that G(n) pn-1 G(1) and since lim pn = n - 3o

29 it is clear that lim gi(n) =g for all i. n — oo From the definition of gi(n), it follows that lim [ vi(n) - vi(n-1)] =g for all i (2. 20) n -- o and this can be true only if there is some constant vi such that lim [vi(n) - gn - vi] =0 (2. 15) n > oo In order to derive Equation (2. 16) it is convenient to define V (n) as a column vector of the vi(n), and Q as a column vector of the qi: V v(n); Q= vN(n) qN Then the following equations may be derived i teratively. V(n) = Q+ PV(n-1) V(n) = + PQ + P 2V(n-2) V(n) = Q+pQ+p2+ Q.+ pn-1 Q+pV(0)

30 Similarly, an equation for V(n-1) is written: V(n-1) = Q+pQp2Q+,+ p-Q+pn- v (O) These last two equations may be subtracted and since G(n) = V (n)-V(n- 1), we get G(n) = pn-1 Q + (n_pn- )V(0) (2. 21) Therefore, lim G(n) ( ) Q n Co T and each element of this vector equality gives the desired result, N g = Z iq. i=i Howard [ 23] obtains this last result in a different way. In the next two sections we make the recurrence relations given in Equations (2.3) and (2.4) useful for determining the policy to be used when the process is to run an infinite time in the transition-optimal or time-optimal problem. This is done by obtaining at each stage in the iteration an upper bound on the gain of the optimal policy and a lower bound on the gain of the current policy. It is shown that these bounds converge to the gain or gain rate of the optimal policy and that the difference between these bounds at each successive stage forms a monotone non-increasing sequence.

2. 2 Transition-Optimal Problem In this section we look at the problem of maximizing the gain per transition. We obtain bounds on the gain of both the current and the optimal policies and show that these bounds converge to one another as the number of transitions approaches infinity. In the recurrence relation vi(n) = max [q + Z pvj(n-], (2.3) k ~ j=1 the policy chosen at stage n may be denoted by the N-tuple (= (kl(n),..., kN(n)) and consists of the alternatives chosen in each of the N states at the n-th stage. Note that in (2. 3) policy a is chosen to maximize vi(n) for all i=1, 2,...,N and that in general greek superscripts specify policies while lower case roman superscripts specify alternatives. Define gi(n) = vi(n) - vi(n- 1) [k k k = max i j k maq + L pi. vj(n-1) + (Pii -1)vi(n-1)] ~~~k jfi~4j~~ ~(2.22) Let r- be the limiting state probability for state i under arbitrary policy 3 where, of course, N i=1 Also define gi(n) =qi+.Pivj(n-1) (Pi3-1) vi(n-1) (2.23)

32 which implies that gi(n) = max gi (n). (2. 24) Theorem 2. 1 shows that the gain under stationary policy,3, g, is g = iq Lemma 2. 2 N Tr. g (n) =g (2. 25) Proof From Equation( 2. 23) it fo llows that r g (n) [i q + i 7 p v (n- )+ (p v(n-)] (2. 26) Now iqi= g i Also, a finite Markov chain must satisfy the matrix equation r = r P where 7 = (1,... TN) is the vector of stationary state p robabilities and P =(Pij) is the transition probability m atrix. Using this equation it follows directly that ri(P _i1) -Zi 7T/ /P (2. 27) jfi jPji

33 Thus 1g(n) gl / [3 vj(n-1)ilra iv(n-1)]'n=gp i i j~gi L3JW i Pijv.(n-1) j rpJvi(n-1)I=g( (2. 28) Theorem 2.3 max gi(n) ]>g g (2. 29) i min rgi(n)] < g < g (2.30) where a is the policy chosen at stage n from the recurrence relation (Equation 2.3) and * is a stationary optimal policy. Proof First we note that gS(n) = gi(n) since a is the policy which maximizes gi(n) at the current stage. From Lemma 2. 2 and the fact that N i = 1 and T > 0, all i, i=l i-l1 - we have that gi(n) < ga for some i and gj(n) > ga for some j. This proves that part of the theorem which relates to the current policy, a. Suppose a is an optimal policy. Then proof of the theorem is complete at this point. Next suppose a is not an optimal policy. Then ga <g*. It must be shown that gi(n) P g* Vi and that gi(n) & g* Vi. First suppose gi(n) >g* FVi. But then ga = 5 r gi(n) >g* which is a contradiction.

34 Next suppose gi(n) < g*. Vi recalls k x~k k gi(n) = max[qk + Pij vj(n-1) + (ii 1) vi(n-1)] k j so that gi(n) >gi*(n) Vi. Therefore Zi* gi(n) > Ti* gi*(n) = g* and this contradicts the assumption that gi(n) < g* Vi. We have now shown that if one gi(n) is equal or less than g* then at least one gi(n) must be equal or greater than g* and conversely. This completes a proof of the theorem. We now would like to show that m ax [ gi(n)] min I gi(n)]-O as n — cx. The following theorem proves this. Theorem 2.4 If, in a MRDP, there exists a number M, such that under any sequence of policies, there exists a state m reachable with probability > r > 0 from any arbitrary state i in exactly M transitions; then max[gi(n)] - min[gi(n)] -O as n- co. (2.31) i i Proof The proof here follows a paper by White [ 58 ]. By hypothesis it is possible to reach state m in M transitions with probability > a O, independent of the policy sequence chosen. From the

35 equation vi(n) = max[qk+ j vj(n-1)] (2.3) k j it follows that gi(n) = vi(n) - vi(n- 1) max [Pijj gj(n-1)] (2.32) 1 k j gi(n) = vi(n) - vi(n-1) > mini pk (2*33) k j ij gj(-) We may iterate the expression (2.32) to get k k gi(n) < max[ pijl.. max [ C p Mj g (n-M)].. ] (2..34) k j 1 kM JM M- M M Similarly (2. 33) may be iterated to yield k kM gi(n) >min [ pil... min [ pM gj (n-M)]...] (2.35) 1 J1 1 kM JMJM-lJMJ M The Inequalities (2.34) and (2. 35) each determine a sequence of alternatives to be used on successive transitions in every state i; 1< i< N. This sequence of alternatives maximizes (minimizes) the right hand side of these expressions for every i. The set of alternatives to be used in all states at any given transition specifies a policy for that transition, and for the M successive transitions a M stage sequence of policies is determined by each of (2. 34) and (2. 35). Denote by A the M stage sequence of policies determined by Inequality (2.34) and by B the M stage sequence of policies determined by (2.35).

36 x Define pij (M), the M stage probability of transition from state i to state j given that policy sequence X is followed. That is, p j (M), is the probability that if we start in state i and follow -M stage policy sequence X, we will be in state j after the M transitions. We have (M) = 1 Vi, X (2.36) Pij and by hypothesis there exists an e > 0 such that Pim (M) =+ e > > 0 Vi, X (2.37) Using this notation, we get the following inequality from (2. 34) A gi(n) -< E Pi (M)gj(n-M) = agm(n-M) + e gm(n-M) + L pA (M) g.(n-M) <c gm(n-M) + (1-0) max[gj(n-M)] (2.38) Similarly from (2.35) we get gi(n) cr ag(n-M) + (1 -C ) min[gj(n-M)] (2.39) Taking the maximum and minimum, respectively, of gi(n) in the two expressions we get max[gi(n) ] < gm(n-M) + (1 -- ) max[gj(n-M) ] (2.40) i j min[gi(n)] _ crgi(n-M) + (1 - o) min[g.(n-M)] (2.41) 3

37 Subtracting (2.41) from (2.40) and shifting the argunnts of the gi, we get max[gi(M)]- min[gi(M)] < (1 -a) (max[g(0)] - min[gj(0)]) 1 i j] j3 This may be iterated r times to yield max[gi(rM)] - min[gi(rM)] < (1 ) r (max[g.(0)] - min[gj(0) ]) and so lim[max gi(rM) - min gi(rM)] = 0. (2.42) r —oo i i This completes the proof of the theorem. The two theorems just proved provide a practical method for use of the recurrence relation, (2.3), to determine an optimal or near optimal policy and to determine the gain of that policy to any desired accuracy in the infinite time transition optimal MRDP. The computational advantages of this method of solution are discussed in more detail later. It should be noted that the hypothesis in Theorem 2.4 give sufficient conditions for the convergence of max gi(n) - min gi(n) as n — oo. i 1 Convergence may occur even when the theorem hypothesis is not satisfied, and in fact examples of this have been constructed. On the other hand, if we wish to determine whether convergence is assured we may find it difficult to determine whether or not the

38 hypothesis of the theorem is indeed satisfied. Therefore the remainder of this section is devoted to finding a necessary condition (Theorem 2. 6) and a sufficient condition (Theorem 2. 7) for satisfaction of the hypothesis. It should be straightforward to determine from physical aspects of the situation being modeled whether of not these conditions are satisfied. We also (Theorem 2. 8) give special conditions under which the process may be altered to assure convergence without affecting the optimal gain or the optimal policy. First we give some definitions from Markov chain theory [ 38] In a Markov chain a state j is reachable (accessible) from state i if for some number of transitions n > 1, Pij (n) > 0 where pij(n) is the probability of going from state i to state j in n transitions. States i and j communicate if i is reachable from j and j is reachable from i. A state j is recurrent under policy a if f~. = 1 where fa. is the probability of eventually making a transition to state j under policy a given that state j is currently occupied. There must exist at least one non-empty communicating recurrent class of states in any finite Markov chain. In the work which follows we consider MRDP's in which the Markov chain determined by any stationary policy has only one communicating recurrent class of states. That is, the Markov chain is completely ergodic f or any policy. A MRDP which satisfies this condition will be called a single chain MRDP. We now state a definition and a lemma. Definition In a single chain MRDP a set of states, R is called recurrent

39 core if this set of states is recurrent under every stationary policy. That is, fkk = 1 for all k e R and for all policies a. Note that the states in R all communicate with one another. Lemma 2. 5 A single chain MRDP has a non-empty recurrent core. Proof Call the set of states comprising the recurrent core, R. Then we wish to prove R # ~. Suppose R = ~. Then there exists a policy Pf3with a non-empty set of recurrent states R1 and a policy B2 with a non-empty set of recurrent states rP2 such that R1 n R2 =. This is shown graphically in Figure 2. 1 where we see the transitions between classes of states possible under policies /1 and 32. In the figure T, is the set of states transient under both policies 31 and,2. Now because alternatives may be chosen independently in each state, there exists a policy 03 with alternatives from 31 chosen in R1 and T and alternatives from 2 chosen in R2. But under this policy, both R1 and R2 are recurrent classes and this contradicts the hypothesis that there is only one recurrent class per policy. The transitions possible under policy 13 are shown in Figure 2.2 The following theorem states that only in a single-chain MRDP does there exist a state m reachable from any arbitrary state regardless of the policy sequence chosen. (Actually a somewhat

40 POLICY P1 POLICY P2 T T Figure 2. 1. Disjoint Recurrent Classes of States Under Two Distinct Policies POLICY [3 Figure 2. 2 Two Recurrent Clas Under Policy f3

stronger result is proved.) Thus for the hypothesis of Theorem 2.4 to hold, it is necessary that we have a single chain MRDP. Theorem 2.6 In a MRDP, any state mE R is reachable from an arbitrary state i regardless of the sequence of policies chosen if and only if the MRDP is single-chain. Furthermore, m is reachable in N-1 or less transitions. Proof "Only if" part is trivial. Si mply choose a policy for which there is more than one Markov chain and then note that there is not state m reachable from every other state of the MRDP. To prove any state m e R is reachable when the MRDP is single chain, choose a state m e R. Suppose the system is initally in state i and some sequence of policies is used as transitions are made. We know that if the policy is stationary then all states in the recurrent core are reachable. We wish to show that this is still true when the policy changes on successive transitions. Assume we start with transition 0 and form sets of states Sn made up of all states reachable with probability greater than zero at transition n but not reachable at transitions 0,1,...,n-l under the sequence of policies used. Thus set S% contains the single state i.

42 Then for some r we have S = r r-l f1 sO f Such an r must exist and furthermore O<r< N. For convenience, define the set S to be the union of the sets above., S = o U S1U... USr-1 It is clear that the proof will be complete if it can be shown that mES. To show this, determine a stationary policy from the above dynamic policy by choosing the alternatives chosen in the state set Sn at transition n; n=O, 1,..., r-1; and arbitrary alternatives in states outside S. For this policy, some subset of the set of states S forms a closed, communicating class of states and so RC S. This is sufficient to prove meSsince by hypothesis, meR; and since r<N, state m is reachable in N-1 or less transitions. The next theorem gives a sufficient condition for Theorem 2.4 to hold. Theorem 2.7 In a single-chain MRDP if a state meR exists such that

43 Pkm> 0 for allk, then max[gi(n)]- min[gi(n)] - 0 as n -oo. i i Proof From Theorem 2.6, m is reachable in N-1 or less transitions under any policy. Since pk m>, state m may be occupied with probability >O after N-1 transitions regardless of the initial state and policy sequence. Therefore the hypothesis of Theorem 2.4 is satisfied. Thus for convergence to occur it is only necessary to exhibit a state which is recurrent under any policy and which allows transitions to itself under any alternative. Before turning to the time-optimal problem we look at one case in which the process may be altered to assure convergence of the bounds on the gain. Both the gain and the optimal policy of the orginal process may be determined from those of the derived process. Theorem 2.8 k I If the one step rewards r.. = r-. = r for all i,j,k, Q in a single chain MRDP, then the bounds on the gain converge in the process defined by setting Ak k Ap-k k (1-e)p+e6 c for all i,j,k (2.43) 0< e < 1 ij = ( i- j

44 Futhermore the gain of the original process for any policy 3 may be determined from the equation g - e r, (2.44) g 1-6 and both processes have the same optimal policies. The new process,k defined by the pij will be called the derived process. Proof For an arbitrary policy (, define the N dimensional row vectors nr and g to be the stationary state probabilities in the original process and derived process, respectively. Similarly, define Pp and P to be the transition probability matrices for these two processes. By definition of the stationary probabilities, ~7 ='/ f (2.45) Equation (2.43) may be used to replace the pk in (2.45) to get T= (1 - E) T Pp +E 7I (2.46) where I is the N x Nidentity matrix. Thus it is seen that 7T =7T By definition also iT =I p and since the stationary probabilities are unique, (3 =( forall i and.

45 For the derived process it is easily shown that i (l-E) qi + e r (2.47) ii and from Theorem 2. 1 g: q There fore p N. Aqi 1=i = EZ i [(1-e)qi +E rii] i-_i = (-e) g +e r (2.48) where r =rit and is constant for all i, 1. It is clear from the above equation that the same policies will be optimal in the derived process as are optimal in the original process since e and r do not depend on 1. Furthermore the gain of the original process is easily determined from that of the derived process by means of Equation (2.48). The bounds on the gain muA converge in the derived k process because Pii > 0 for all i, k, and therefore the hypothesis of Theorem 2. 7 is satisfied.

46 2.3 Tim e Optimal Problem In the previous section it was shown how the recurrence relation in Equation (2.3) can be used to determine bounds on the gain of policies which maximize the return per transition in infinite time MRDP?s. It was shown that these bounds are guaranteed to converge in certain cases and that they also bound the gain of the policy currently in use in the recurrence relation. Two objectives for MRDP's were given in the introductory section of this chapter: maximization of gain per transition and maximization of gain per unit time. Gain per unit time is called the gain rate and in this section bounds on the gain rate are given which are analogous to the bounds on the gain determined in the previous section. In addition conditions are given which guarantee convergence of these bounds. In this way the recurrence relation in E quation (2. 4) i s made useful for the infinite time problem when the goal is to maximize expected return per unit time. The recurrence relation for the time-optimal problem was given in Equation (2.4) and is N k k wi(t) max pkj dF (T) [R (t ) +S. (tT) i[ ij ij 1 k j=1 t 1J 1J + dFk (T) RkT) + (t-)] } (2.4) 1] (~) [ ij(T) + wj wi(t) is the expected return given that we start in state i and the process terminates after t time units. It is clear that it is neccessary to place restrictions on the distribution functions, Fk (t), in order

47 to be able to evaluate the Equations (2.4). In the work which follows Fk (t) are restricted to lattice distributions with distribution span A k and for some integer L <oo, Fi (L A) = 1 for all i,j,k. Also instantaneous transitions are not allowed and so Fjk(0) = O0 for all i, j,k. Define i(t) to be the probability density function for the distribution function F.. (t). The times between transitions are restricted to discrete values and have discrete distributions so that the density functions may be defined by (n) =F (n ) - Fk (nA -A);. j ij ij n =, 2,..., L (2.49) ij (nA) = 0 elsewhere. It follows immediately that for n> L, the recurrence relation may be written N L w.(nA) m ax k PA) RZk (.() + A)(nA- A) 1 k j=1 Jj = 1 iij n>L (2.50) N L By definition, q k = Pj Z 0j (IA) j (IA) and furthermore j=1 l =1 the distribution span, A, can be set equal to one without loss of k k generality. Also define d..kj () =pij 0.j (1?). Then N L w.(n) = max {qk + dk(Q w(n-Q)}; n >L (2.51) k.j=l =1 1] w

48 Since the process of interest is to run for infinite time, the total expected return will be infinite, and so the goal is to maximize expected return per unit time. For this situation, any finite boundary k k reward, S.k (t, T), will have no effect on the gain rate and so S.. (t, ) ij is set equal to zero for convenience. Furthermore let R.k (t T) =Rk (T) which means that the entire reward for making a transition from i to j under alternative k is collected at the beginning of the transition interval It is necessary to set wi(O) in order to evaluate the recurrence relations and therefore let wi(O) =0 for all i. None of the above assumptions are necessary but only serve to make the form of the recurrence relation simpler for values of n<L. Thus with these assumptions wi(O) =0, for all i N min[ n,L] I j1 Ed..j (d ) w (n-Q)]; n=, 2,... (2. 5a It is clear that this expression may be easily evaluated for any integer n>O. In the particular case where L=1, the time-optimal problem and the transition-optimal problem are identical because all transitions take equal time. For this case j (1) = 1 for all i,j, k so that k N wi(n) = max [ q + 3 Pij wj(n-1) ] k j=1 This is, of course, the recurrence relation for the transition-optimal problem.

49 Before proceeding to a derivation of bounds on the gain rate it is desirable to define two new variables. Let hi(z) = wi(z) -wi(z-L); z > L (2. 53) A column vector of these hi(z) of dimension N is defined as h(z) H(z) = I; z>L (2. 54) hN(Z)/ Next f or a fixed constant n >L define a L, N dimensional column vector with the H-vectors defined above as components. H (n0+nL) /fl(n) H(n0+nL+1) f (n) F (n) = H(n0+nL+L- 1) f LN(n) n =0, 1, 2,...; n;>L (2.55) It will be obvious in what follows why the variables defined above are desirable. Next a definition is given which allows a simple explicit statement of the choice of alternatives at successive stages in the recurrence relation. Recall that a policy, a, was defined as a particular choice of alternative in each of the N states. An extension of this over a number of stages follows.

50 Definition An L-stage policy sequence, A, is defined as a choice of policies aO,a1,..., 9aL-1 in the L successive stages of the recurrence relation (2. 52). A stationary L stage policy sequence, A, is a repetitive choice of the above policies at successive stages so that the policy sequence is a0,al1,, aL_-1 aO,al,..., aL1) a0,.... This stationary sequence may begin at any desired stage. Evaluation of the recurrence relation for wi(n) up to some n determines the optimal sequence of policies to be used for the first n stages of the process. Instead of choosing the alternatives at each stage which maximize expected return, it is possible to choose other alternatives in which case the recurrence relation can be used to find expected return for the alternatives chosen. This can be formalized by defining a new variable w A(n). As in the definition of wi(n), the i refers to the initial state while the n refers to the number of stages remaining before termination of the process. For wn), however, the optimal policy sequence as determined from Equation (2. 52) is used before stage nO where nO is some arbitrary constant such that no> L. Beginning at stage no, the stationary L stage policy sequence A is used. As stated above, nO is an arbitrary constant such that n0>L and so wi (n) is actually a function of nO as well, but this isnot shown explicitly. The recurrence relation for wi (n) is written in terms of the alternatives which make up the policy sequence A.

These policies are a0,al... aL_1 and for policy ax the alternative in state i will be called ax(i). Whlere no confusion canu result, the functional dependence on i will be omitted. Up to stage no, the optimal policy sequence is followed and therefore A k N min[, L] k A wi (n) = max [qi + i () (n-)] j=1 2=1 n<n0 (2. 56) From stage no on, the L stage stationary policy sequence A is used and so a N L a n A w 0+L+n) qin + E dij () w (n0+xL+n-2); x=O, 1, 2,3,...; n=O, 1, 2,..., L (2. 57) In the obvious way, hi (n) is defined by hA ~(n) =wn) w iA(n-L); n>L (2. 58) and HA(n), FA(n), and fiA(n) are defined analogously to H(n), F(n), and fi(n) in Equations (2. 54) and (2. 55). The reason for an interest in a stationary L stage policy sequence is that when such a policy sequence is used a simple recurrence r elation

52 for the hi(n) can be obtained, This in turn leads to a coefficient matrix A A for the h i(n) and ultimately for the fA(n). This coefficient matrix is stochastic and is used in the proofs which exhibit bounds on the gain rate and show that these bounds converge. The fi(n) are shown to be closely related to the gain rate and the bounds on it. As a first step in obtaining the desired recurrence relation on A the h (n), we have A A A hi (n +L+n) = w (n0+L+n) - w. (n0+n) N L a N a A j=1 jQ-1 0 ) N L a /jl? ~ d.n (Q) h.(n0+L+n-fl); n =0,1,...,L-1 (2.59) Again no is a constant such that no >L. The goal is to obtain each of hi(n0+x L+n) for any integer x>0. in terms of hi(n0+(x-l)L+n) for i=1,..., N and n=0, 1,...,L-1. For n =0, our desired relation is N L a A hA (n0+xL) = 0d (EA (n0+x L-l) (2.60) Z d. (2)h (n 01 j=1 f=1 For nr:1, the relation hA(n+X L+1) =dij (P) hA (n0+xL+l-) (2. 61) j=1 2=1

53 may be obtained from E quation (2. 57). In this case it is seen that the right hand side contains h (n0+xL); j=1, 2,..., N; whereas an equation is desired which contains hj z) with argumerts no larger t han z=n +xL-1. To obtain this, substitute the right side of Equation (2.60) into Equation (2. 61) to get A N La1 A hi (n0+xL+1) = dij () h (n0+xL+l-) j=l L =21 a N L a0A +d. t (1) (n dLk() (2.62) 1 djk The same procedure may be followed to obtain h A(n0+xL+2) in terms of hiA(n0+(x-1)L+n); i=1,...,N; n=0,1,...,L-1. In this case the first two terms in the summation over 2 must be replaced by the expressions found for hA (nO+xL) and for h A (n +xL+1) in Equations (2.60) and (2.62). This procedure is repeated f or hi (z) up to z = n0+x L+L- 1. In o rder to simplify notation the relationships above will be given a x in m atrix notation. Define the matrix of d (2) for policy ax to be a A Dx(2) = (dij (2)). Then the vectors H (n0+xL+n) may be written as follows A L A H (n0 +xL) = D0(q)H (n0+x L-l) (2.63) HA (n+xL+1) = 3 D1()H (n+x L+1-T)+D(1) HA (n0+xL) (2. 64) 0 2=2 09

54 A AL A A HA(n0+xL+2) = (, D2(l)H (n0+xL+2-1) + D2(2)H (n +xL)+D2(1)HA(n0+xL+1) (2.65) H (n0+XL+L- 1) = DL 1(L)H (n0+x L-1)+DL_ (L- 1)H (n+x L) + 0 +DL 1(l)H (n0+xL+L-2) (2.66) In each of these equations, the terms which must be written in terms of preceding equations have been taken out of the summation over L. The general equation may be written H (n0+xL+n) = n(Z)H (n0+x L+n- Z) + Dn(I)HA(no+xL+n- ) n =0, 1,..., L-1 (2.67) A( The H (n +x L+n- 2) in the second summation must all be replaced by expressions for these given in the equations for smaller values of n.

55 Next, recall the definition for F (x): HA(n0+xI) fA (X) FA(x) = = A A H (n0+xL+L- 1) L N(X); x= 0,1,2,... (2.68) In terms of this definition, Equations (2.67) give FA(x) in terms of FA(x-1) for x=l, 2,.... The LNxLN matrix of coefficients for FA(x-1) will be called UA and so FA(x) = U AFA(x-1); x=1, 2,.... (2.69) This matrix UA may be partitioned into L2 submatrices each of dimension NxN. Thus A A A Ull U12. UL 11U1 A~ UA A A ULl ULL

56 Row i (1<i < N) of this matrix, UA, may be obtained from the equation N L a0 hi+xL) di (2)h (n0+xL- Q) j=1 a=1 lJ j The elements of this row, of UA sum to one: N L a E Z d.0 () =1 (2.70) j=1 Q=1 1J Similarly, row i+N (l<i <N) may be obtained from Equation (2. 62) and the coefficients again sum to one. N L a al N L a - |Cdij (f) +dij (1) E d 1 j=1 =2 k =1 j The matrix U is given explicitly in Figure 2.3 in terms of the submatrices UIJ where each row of submatrices except the first contains submatric es defined in previous rows. It is now shown that each row of matrix UA has row sum equal to one and so the matrix UA is a stochastic matrix.

57 4 4 PI'! 1-;a i*~*. +,+,.a +.. a~-11 P- 1 + * + _C - I - 1c ID ~-4 _______ __ __ _

58 Theorem 2.9 Let UA be the LNxLN matrix of coefficients of F A(x-1) in the equations A AFA F (x) =U FA(x-1); x=1,2,.... (2.69) where A is used to specify an arbitrary stationary L stage policy sequence as discussed earlier. Then UA is a stochastic matrix, and all its row sums are one. Proof It has already been shown that fcr the first 2N rows of matrix UA the row sums are one. These 2N rows correspond to the first two rows of the NxN submatrices which comprise matrix U A. Thus, the row sums in submatrix row 1 are the same as the row sums for the ma trix L P0 C= DO (f) where a0 P = (Pi.) is the NxN transition probability m atrix for policy a0. Next it will be shown that if the row sums in the submatrix rows 1,...,I are one then the row sums in submatrix row I+1 must be one, and thus that UA is stochastic. It is easily verified that if an arbitrary NxN matrix B with row sum in row i equal to b. is post-multiplied by an 1

59 matrix BS will have sum bi. In submatrix row I+1 of UA, DI (I+1),..., DI(L) each appear once and are not multiplied by any other matrix while DI(1),...,DI(I) each appear L times and are each post-multiplied by matrices whose sum 1forms a stochastic matrix. The contribution to the row sums in submatrix row I+1 of DI(J); for some JI; is that of the matrix L D (J) Z U K=I I-J+1, K. L But since K UI-J+1,K is a stochastic matrix, the row sums are the same as those of DI(J) and since the row sums of E DI(J) are 1, then J=1 the row sums in submatrix row I+1 must be 1. Thus UA is a stochastic matrix with row sums one. In order to be useful in the derivation of bounds on the gain rate A and convergence of these bounds, the rratrix UA must have certain properties which hold regardless of the L stage policy sequence A used to determine the matrix. More specifically, there is a LN state homogeneous Markov chain induced by the matrix UA and more generally a LN state non-homogeneous Markov chain induced by using matrices A A U,U,... as transition probability matrices for successive state transitions in a LN state process where A1,A2,... is a sequence of L stage policy sequences. It is these Markov chains which are required to possess certain properties, one of which is that for arbitrary L stage policy sequence A, the Markov chain induced by UA must possess a stationary distribution which will be denoted by the LN dimensional A row vector, p.

60 The other property needed is that there must exist some state, b, in the A A LN state processinduced by U, U,... which is reachable from any state after some number M of transitions regardless of the A1,A2,... chosen. This second property implies the first because the reachable state, b, exists for A —A 2 =... and this state may be occupied with probability greater than zero for all transitions after the Mth. Therefore the process induced by UA is acyclic and contains a single closed communicating class of states which means the process has a long-run distribution and therefore a stationary distribution [ 38] A Verification directly from the UA matrix that the properties given above hold may be inconvenient and so in this paragraph restrictions on the density functions for the time between transitions, 0ik (f), and on the transition probabilities in the underlying Markov chain of the MRDP, pij, are given which ensure that UA has the needed characteristics. First of all, the restriction is placed on the underlying Markov chain of the MRDP that it be single chain as defined in section 2. 2 and that for some state meR, the recurrent core, pmm >0 for all k. This condition is identical to the one used in Iheorem 2. 7. If now the 0kj (Q) are restricted sothat iij(1)>0 for all i,j,k; then state b=m+(L-1)N is reachable after N-I or less transitions regardless of the policy sequences A1,A2,... used to induce the Markov chain. This may be stated formally as a theorem. Theorem 2. 10 Given a single c hain MRDP with recurrent co re R and with a

k k state mrER such that pkm >0 for all k. If ij (1)>0 for all i,j,k; then state b=m+(L-1)N is reachable in N-1 or less transitions in any A A 1 2 Markov chain induced by using matrices U,U,... as transition probability matrices for successive transitions where A1,A2,... are arbitrary L stage policy sequences. Proof Define Px as the transition probability m atrix of the underlying Markov chain of the MRDP when policy a x is in use. In theorem 2. 6 it was shown that f or the given conditions on the MRDP, state m is occupied with probability greater than zero after N-1 or less transitions regardless of the initial state and regardless of the policies used on successive transitions. A necessary and sufficient condition for state m to be reachable in this fashion is that all elements in the mth column of the product matrix, r'1 Px, be greater than zero for any arbitrary set of 1- N- 1 Next inspect the rmtrix UA and note that the theorem is proved if it can N-1 Ai be shown that the product matrix, i_l U, has all elements in column b=m+(L-1)N greater than zero regardless of the policy sequences, A1,.. AN_1, N-1 Ai chosen. If the product matrix, i7T U, is written in terms of submatrices as UA is in Figure 2.3, then it is seen that all elements in column b are greater than zero if and only if all elements in the mth column of each submatrix in the right most column of subntrices is greater than zero. Therefore attention may be restricted to this column

62 of submatrices in the following. k k From the hypothesis and the fact that dij(l) = 0(1) Pij, it is clear that dk.(1) >0 if pkj>0. Therefore DI(1); O<I<L-1; in matrix UA has non-zero elements in the same positions within the matrix as PI, the transition probability matrix in the MRDP for policy aI. Since a N-1 order product of P-matrices has all elements in column m greater than zero, then a N-1 order product of D(1) matrices must have all elements in column m greater than zero. For submatrix UIA; 1<I<L; in UA it is s een that one term consists of the I order product DI_ 1(1).. D0(1) and in particular submatrix UtL contains the term DL 1(1)... D0(1). Therefore inspection of UA shows that the product of two matrices of this form has a L+I order product of D(1) matrices in submatrix row I and column L. The product of N-1 matrices of the form of UA has a L(N-2)+I order product of D(1) matrices in the submatrix in row I and column L. Since I> 1 and L> 1 the order of this product is N-1 or greater and so all elements in column m,of this submatrix are greater than zero. This holds for all I; 1< I<L; and therefore the product of N-1 matrices of form UA has all elements in column b greater than zero which was to be proved. The restriction on the ij (1) can be relaxed still further by requiring only that km (1) >0 for all k. With this condition and the condition Pmm >0 it can still be shown that state b =m+(L-i)N can be occupied after N or less transitions regardless of the initial state.

63 The argument needed to shown this is quite complex and is therefore relegated to Appendix E. The preceding discussion shows that under reasonable conditions on the variables pjk and i (2) in the MRDP, it can be guaranteed that some state b in a process induced by matrix UA for any L stage policy sequence A is occupied with probability greater than zero after N-I or less transitions of this process. Suppose now that a MRDP is given and so under some L stage policy sequence, A, a matrix UA is determined. Assume there exists a state b which is reachable from all states of the Markov chain induced by UA; then this Markov chain has only one communicating class of states. Therefore the Markov chain has a stationary distribution and the row vector of state probabilities of dimension LN making up this distribution will be denoted by p A. In this UA- induced process the equation Fn)A AA (2.71) FA(n)= UF (n-1); n > 1 holds by definition of the matrix UA. Also, of course, pA p by definition of the Stationary distribution. In Theorem 2. 1 it was shown that lim f. (n) exists and is independent of i. Define hA as this limit: n-.oo 1 A A A h lim f (n). In what follows h will be r elated to the gain rate n-boo i but first the following lemma is shown to be true.

64 Lemma 2. 11 pAFA(n) =hA; n=0,,... (2.72) Proof The proof follows immediately from the relations among pA,FA(n), and UA given above. Thus pAFA(n) = pAUAFA(n-1) pAFA(n- 1) n = 1, 2,.... (2. 73) Therefore pAFA(n) is-a constant for all n and since lim fA(n) is n-.oo independent of i then n-o [pAFA(n)]= hA (2.74) and the lemma follows. For the time-optimal problem the quantity to be maximized is the gain per unit time called the gain rate. In this paragraph the variable hA as determined for L s tage policy sequence A is related t o the gain rate in the MRDP when L stage stationary policy sequence A is used. The gain rate for this policy sequence will be denoted by 4. Recall that by definition (see Equations (2. 53) - (2. 58)) A A A f (n); l<i <N; n>O; can be written as w. (z)- w (z-L) for some j and z. In the lemma just proved, it was shown that lim A A lim w (z) - w (z-L) h forallj. (2.75) zoo0

65 Equation (2. 75) states that for the infinite time process under stationary L stage policy sequence A the expected return in L time units is hA Therefore the gain per unit time is A A, h (2. 76) The next theorem exhibits bounds on the gain rate of the current L stage policy sequence and on the optimal policy for the MRDP. This theorem.is analogous to Theorem 2.3 for the gain. These bounds are given in terms of elements of vectors H(z), and since these elements are of the form wi(z) - wi(z-L), they are easy to determine from the recurrence relation for the MRDP. Before stating Theorem 2. 12 formally, some explanatory material is presented which should make the theorem easier to understand. Suppose the recurrence relation i(n) = max[ qki+: d (f) w.(n-Q) (2. 52) k 1 is used up to some stage n0+L-1; n >L; in a MRDP. The recurrence equation specifies a particular L stage policy sequence for the last L stages (stage nO to stage n0+L-1), and this policy sequence may be used as a stationary L stage policy sequence by using it repetitively beginning at stage n0. Use of Equation (2. 52) in this way consitutes a particular' way of choosing a stationary L stage policy sequence, A, to be used beginning at stage nO; and this policy sequence in turn defines a matrix U. It was stated earlier that it has been shown [ 16] that an optimal

66 stationary policy exists for the infinite time problem, and therefore an optimal stationary L stage policy sequence exists in which the policies are identical at each step in the sequence. Call this optimal stationary policy sequence *; by use of this policy sequence a matrix U is defined in the usual way. With these definitions and concepts in mind, Theorem 2.12 may be stated as follows. Theorem 2.12 Let the recurrence relation (2. 52) be used up to sone stage ng+L-; nO >_L; in a MRDP in which some L stage policy sequence which we will call A, maximized expected return for the last L stages. A*A If a stationary distribution with probabilities p exists for the Markov chain induced by the matrix UA, and a stationary distribution p exists for the Markov chain induced by the matrix U where * is some optimum stationary policy sequence, then max [hi(no+n)] > h >hA (2.77) <i <N O<n<L-1 min [hi(n0+n) ] h h (2.78) 1<i<N O<n<L-1

67 and thus, the gain per unit time for the current policy sequence and for the optimal policy are bounded by 1<i< N [hi(L +n) >,*>,,A (2.79) O<n< L- 1 min IA * (2.80) l<i<N L A < (2.80) O<n<L-1 Proof In the proof which follows, it is shown that min [hi(no +n)] < hA < max [h.(n+n)] 1<i< N 1<i<N O<n< L-1 O<n< L- 1 and that min [hi(n0+n) < h < max [hi(n0+n)] 1<i<N 1<i<N O<n< L-1 O<n< L- 1 These inequalities are sufficient to prove the theorem since by definition an optimal policy is one which maximizes the gain rate, and therefore hA < h

68 Because policy sequence A was used for the last L stages, the vector of h (no+n) over which the maximum and minimum are to be obtained defines FA(0): H (n) FA(0) = (2. 81) H(n0+L- 1) A Therefore we can work with F (0) rather than H(n0+n); 0<n<L-1. It A was shown in Lemma 2. 11 that for stationary probability distribution p pAFA(0) = hA (2.82) and therefore the inequalities in the theorem pertaining to the current L stage policy sequence must hold. Of course, if the current L stage policy sequence is an optimal stationary policy sequence for the infinite time process, then A is such that hA is maximum so that hA = h and the proof is complete. Otherwise hA<h aid it is necessary to prove that the inequalities hold which contain h. This is now done. The proof of the inequalities containing h is by contradiction. Let f* Let fi (0) > h for all i. Then hA = AFA(0) > h which is a contradiction because the gain rate of the policy * must be at least as great as the gain rate of the policy A since *

69 was assumed to be optimal. Therefore, for some i, fA(0) <h. It remains to show that fA(0) ~h fcr some i. 1 Let fA(0) < h for all i. This implies that p FA(o)<h. By definition, each fA(O) is equal to wj(z) - wj(z-L) for some j; l<j<N; and for some z; n <z <n +L-1; and the recurrence relation which determines wj(z) gives A kN L k fA(0) = max i q + E djr() Wr(Z- - (z-L) k r=l =l1 (2.83) The alternative, k, chosen in state j at step z makes up one part of the current policy sequence, A, and it is seen that this alternative is chosen to maximize f (0). Instead of choosing alternatives over each of the last L stages which m aximize the f (0), it would have been possible to choose alternatives in each state which make up an optimal stationary policy for the infinite time process and thereby define a vector with * A * elements which may be called fi (0). Obviously fA (0) >fi (0) for all i. (2. 84) But this inequality contradicts the assumption that p F (0)<h because it means that p F (0) > p F (0) = h (2. 85) This completes the proof of the theorem. II The next theorem shows that the bounds on the gain rate determined above converge to a common value as the number of steps taken in the

70 recurrence relation increases pro vided certain conditions on the possible forms of the matrices UA are met. These conditions are sufficient to insure convergence of the bounds; convergence may occur, however, even if the conditions are not met. Therefore the usefulness of the recurrence relation (2. 52) as a method of finding the gain rate and optimal policy for the infinite time process is not limited only to situations where the bounds can be shown to converge by the following theorem. Theorem 2.13 Given a MRDP and an arbitrary sequence of L stage policy sequences A A A1, A2,.... If the Markov chain induced by using U,.. as transition probability matrices for successive transitions is such that in this L N state process there exists a state b which may be occupied with probability > a > 0 after B transitions regardless of the policy sequences A1, A2,... used and the initial state in the U-induced process, then max [hi(n+x)] - min [hi(n + x)]-0 as n- oo (2.86) l<i<N l<i<N 1x<L 1<x<L and thus the bounds on the gain rate determined in Theorem 2. 12 are guaranteed to converge.

71 Proof The proof of this theorem is similar to the proof of Theorem 2.4. Before proceeding with the proof, some new notation is introduced. For policy sequence AI, define aIo..., aI, L - 1 to be the L policies used in this policy sequence. Then define aIJ(i) as the alternative chosen in state i for policy aIJ. This defines ad.. (i) for policy aJ and for all i, j, and I. For any 2, the NxN matrix of the a1J(i) d.. (M) will be written aIJ(i) DIj() =(d1ij (2)) If it is desirable to indicate some general policy K we write DK(f). Other definitions will be introduced when needed. As usual, nO is restricted to a value equal to or greater than L. From the definition of hi (z);z >L; in terms of w (z) and w. (z - L); 1 -1 1

72 h(n)k N L hi (n O xL ) nkax [ q + (d ) wj (+xL+n3-) k N L k -mkax [q + d ij() wj (n+(X-1)L + n- ) ]; j=l I=1 x= 1, 2,...; n=O, 1,..., L - 1. (2.87) The maximum over all possible alternatives may be found for all terms together on the right side of Equation (2. 87) above, and this gives the following inequality which is analogous to Equation (2. 32). N L h (no +xL+n) _ max [ 3 ) d.(e)h. (n0 +xL+n- )]; i 0 k 12130 x=1, 2,...; n= 0, 1,..., L- 1; i=1, 2,..., N. (2.88) The above inequality as a vector relation may be written as L H (n +xL+n) _ max[ DK () H (n + xL + n - )] (2. 89) K h 1 K where the maximum is over ail policies K or in other words over all

73 alternatives in each state such that each element of the vector on the right is maximized. Thus the inequality holds for all N elements of the vectors. Using the inequality relationships above, it is now possible to obtain a L'N dimensional vector inequality in which H(n0 + xL),..o H (nO + xL + L-1) appear on the left and H(n + xL - L),..., H (nO + xL - 1) appear on the right. To simplify notation, assume that in the inequality (2. 89) for H(n0 + xL +n); the policy which maximizes the right side is a xn In the relations which follow; vectors H0(n0 + xL + n) are defined by the quantities they are set equal to. These definitions serve to simplify the notation. Thus L H (n +xL) - 1 DxO () H(nO +xL - ) = H0 (nO +xL) L H (n + xL + 1) _ Dxl () H (no + xL + 1 - ) L _-< ~ Dxi () H (n0 + xL + 1 - l) + Dxi (1) H (n +xL) ~= 2 - H (n0 + xL + 1) H0 (nO + xL) is used simply to avoid having to write out the summation,

74 L zl 1Dxo (1) H (n0 + xL - 1), while both Ho(n0 + xL) and HO(n0 + xL + 1) are used similarly in the inequality inwhich H (nO + xL + 2) appears on the left. Thus, for example, Ho (no + xL) may be replaced to obtain L H(no +xL+ 1) < Dxl () H(n +xL+1- ) Q- 2 xl 0 =2 L +D (1) Dx (2) H (n + xL- ). =1 xO0 In this form it is clear that H (n0 + xL + 1) is in terms of H (nO +xL- L),..., H (nO +xL- 1). H0 (no +xL+n) for n = 0, 1,..., L - 1 are defined in a fashion analogous to that above so that the general inequality is L H (no +xL+n) < Dn () H (n0 +xL+n-) L n D () H (n+ xL + n- 2) + D (2) H 0(n+xL+n-f) 2=n+ xn 0 = xn' = H0 (nO +xL+n); n= 0, 1,..., L-1. (2.90) The L inequalities shown here are determined by a policy sequence,

75 Ax, consisting of policies a0,'., ex, L-I' A L.N x L.N A stochastic matrix, U, is defined by the coefficients of the Hvectors and so an L' N dimensional vector inequality may be given as A F (x) < U x F (x- 1); x= 1, 2,... (2.91) by definition of F (x) in terms of H (n + xL + n); n = 0, 1,..., L-1. Next another L'N x L'N matrix, U (B), is defined: U(B)U B 1A (2.92) u (B) = U U Thus F (B) _- U (B) F (0) (2.93) and by the hypothesis that a state b in the Lo N state process may be occupied with probability > a >0 after B transitions, we have L N fi (B) - 1 Uij (B) fj (0) ( +Ei) fb (0) + Uij (B) fj(O) jib where uij (B) is an element of the matrix U (B) and where a +I e=> a >0 is the probability of transition from i to b in B A1 AB as transition probability matrices transitions using U..., U

76 for these transitions. It follows that fi(B)< orfb(O) +(1 - a) max f. (0); i= 1, 2,..., L N; j b and so max fi(B) f< fb(0) +(1- c) max fj(0) (2.94) i j b By going back to (2. 88) and replacing max by min, the inequality is reversed. Arguments identical to those used above in whi ch all inequalities are reversed and max is replaced by min may be used to obtain fi (B) > fb(O) + (1 - a) min f. (0); 1 < i < LN; and so min f. (B) > fb (0) + (1- o) min f. (). (2.95) i j Inequalities (2.94) and (2. 95) may be subtracted to yield max f. (B) - min f (B) (1 - ) [ max f () - min f (0)] i1 1 j. 9 j 3 (2.96)

77 It is clear that the argument used to obtain this inequality in which x = I, 2,..., B was used, holds also for x = y B + 1,..., y B +B for any integer y = 0 and therefore max f. (y B+B) - min f. (y B+B) 1 1 1 < (1 - oa) [ max f. (y B) - in f. (y B)] so that max f. (y B+B) - min f. (y B+B) i~1.i ~1 (1- )y+l[ max f. (0) - min f. (0)]. j 3 J nO was any number such that nO > L and so this is sufficient to prove that max [hi (n+x)] - min [hi (n+x) ]-O as n-oo (2.86) l_i__<N l_i_N 1<x< L 1<x< L Bounds on the gain rate of the current L-stage policy sequence and on the gain rate of the optimal policy have been obtained. It has been shown that these bounds converge. The next theorem shows that the recurrence relation converges to a stationary optimal policy.

78 Theorem 2.14 If bounds on the gain rate converge, then the recurrence relation for the time-optimal Markov-renewal decision process converges to a stationary optimal policy provided ties for choice of alternative are broken by using the same algorithm at each iteration. Proof It has been shown (Theorems 2. 12 and 2. 13) that under certain conditions lim h.(n) = h* i.(297) n-oo (297) The recurrence relation is N L wi(n) = max[qi + ij ) wn k j=1 /=1 It is clear that for Equation (2. 97) to hold Wi(n) - h* Ln + wi V i as n - oo for some constant w. Therefore, N L wi(n) mka[q. m+ Z d.. (l) (h* Ln-h* L + wj)] as n -oo ~k 1 j=1 f=13 The summation over terms not dependent on j or Q may be given explicitly so that N L k wi(n) - h* Ln + max[qk +k d. () (wj.h* L)] as n -oo. choose k on each iteration. II

79 In summary, the algorithm for the time-optimal problem consists of iterating using the recurrence equation (2. 52). At every stage n after the first 2L stages we compute wi (x) - wi(x- L) max [ ] 1(i_c N n-L<x n L wi (x) - w (x- L) ii1 min [ ] 15i<N L n-L< x_n These are bounds on the gain rate of the current and optimal L-stage policy sequences. The bounds converge and also convergence occurs to a stationary policy providing certain conditions on the form of the MRDP hold. 2.4 Computational Considerations In this section we look briefly at the computation and storage required to obtain solutions to MRDP's. In typical MRDP's which are models of physical systems (including those in Chapter 3), transitions may be made from the current state to only a few (say m) of the N states so that m<<N. With this situation much less computer storage is needed if only non-zero transition probabilities are stored rather than all probabilities. For example,

80 solution of the transition optimal problem requires only storage of k the non-zero pij and of three N-dimensional vectors composed of the vi (n), vi (n - 1), and qk. Each iteration requires one k multiplication for each non-zero pij It is interesting to compare the computation required when using Equation (2. 3) and the computation when using the algorithm devised by Howard [23] called the policy iteration method. Figure 2.4 shows this algorithm. Howard proves that it does converge to an optimal policy and that each successive policy chosen has a gain at least as great as that of the preceding policy. The computation required in the Policy-Improvement Routine is comparable to that required for an iteration of Equation (2. 3). The Value Determination Operation, however, requires the solution of N simultaneous linear equations in N unknowns. Using Gauss elimination to solve these requires about N /3 multiplications ( [53], p. 241). Except in special cases the storage required would be that for a full N x N matrix and so no advantage is gained by the fact that the matrix is likely to be sparse. No comparison of the number of iterations required for satisfactory convergence using the two methods has been made. This can vary over a wide range depending on the parameters chosen. From a theoretical point of view, the advantage of the Howard algorithm is that after some finite number of iterations one can state with certainty that the optimal policy has been found while

81 Choose an arbitrary initial policy Value- Determination Operation Use Pij and qi for a given policy to solve N g +v. qi + Pijj i=1, 2,...,N j= 1 for all relative values v. and g by setting vN to zero. Policy-Improvement Routine For each state i, find the alternative k' that maximizes k N k qi + Pij v j=1 using the relative values vi of the previous policy. Then k' becomes the new decision in the i-th state, qi becomes qi, and Pij becomes p... Nere Polic ie No on last two iterations identical? Yes r Policy chosen is optimal Figure 2.4. The Howard Algorithm

82 use of the recurrence relation only tells how close the gain of the current policy is to that of the optimal policy but does not guarantee that the current policy is the optimal policy. From a practical point of view, however, the recurrence relation has the advantage that the iterations may be stopped at any point and in particular when the bounds on the gain have been computed with as much precision as that for other parameters of the problem. At this point we turn to a complete mathematical description of a model which provides an application for the optimization method presented in this chapter.

Chapter 3 MODELS FOR MULTIPROGRAMMING This chapter contains a detailed description of mathematical models for multiprogrammed computer systems. The models are useful for analysis and optimization of task scheduling policies where an optimum task scheduling policy is defined to be one which maximizes the system throughput. Many of the computing systems being marketed today have features which facilitate a multiprogrammed mode of operation. This is desirable because effective use of multiprogramming allows more efficient use of the system resources than would otherwise be possible. Multiprogramming makes it possible to increase the productivity of valuable system resources such as CPU(s) and I/O devices (drums, disks, printers, etc. ) by increasing the fraction of time tasks are available for these resources to work on. The effectiveness of multiprogramming to a given system's efficiency of operation depends on the task scheduling rules and procedures used in that system. The model described in this chapter measures the efficiency of a multiprogrammed computer system (in terms of task completions possible per unit time interval or "throughput') as a function of the task scheduling rules used and other parameters. Two salient features of this model are that the model may be used to measure

system throughput when reentrant code or other sharable information is used by tasks: and the model is suitable for application of an optimization procedure so that maximum throughput scheduling rules may be found. The scheduling model may be described in a rough way with the aid of Figure 3. 1. Tasks in main memory alternate among periods of waiting for a CPU, using a CPU, and experiencing a delay for an I/O operation. The CPU scheduler determines which of these tasks waiting for a CPU receive the use of one. New tasks arriving at the system are placed in a queue outside the main memory, and the memory scheduler decides which tasks to move into main memory. It is clear that decisions made by these schedulers are interdependent and so they cannot be treated separately. For example, the task configuration in main memory is affected by both the memory scheduler and by priorities assigned to tasks in main memory by the CPU scheduler. The memory scheduler is constrained by the sizes of tasks and the number of pages of main memory available where the word pages here may refer to any convenient sized unit of memory if no page unit is defined for the system being modeled. And of course, the CPU scheduler is constrained by the number of CPU's available in the system~

85 - 0 LJ. 0 E CoLLJ 0LJ Z L). 0,

86 Figure 3. 2 presents the model as a service system and shows more clearly the task flow through the system. New tasks arriving at the system are placed in the memory queue and the memory scheduler controls the movement of tasks to the CPU queue. The CPU scheduler schedules tasks in the CPU queue on the available CPU's. The CPU's are periodically interrupted and at these points may be assigned to other tasks even though tasks currently using them have not finished. An executing task may request an I/O operation (including a page request) and at this point it becomes ineligible to use a CPU until the I/O operation is complete. After completion of the I/O operation the task may either terminate and leave the system,or it may require another CPU interval in which case it reenters the CPU queue. Ref erence will be made to this figure in the following sections where specific parameters and assumptions are discussed. We now turn to the specific assumptions made in the model. 3.1 Assumptions In this section, the general assumptions made in the development of the computer system model are given, and some of the parameters of the model are defined. Other specific assumptions are given in relevant sections. Listed with the assumptions are some of the input parameters required for the model and comments on the validity of the assumptions. The assumptions are numbered to make them easier to pick out from the text.

87 co CaQ) cmI V,, XI~~~~ C~~I - i I 0 0 0,:~~~~~~~~a,I a V-T cI o c~ i C C_Y) I C Y4I - 0 ~ I -Q I I ~C 5E Q) cd),..n.h.

88 1) There are M distinct kinds of tasks; and thus at each point in the system shown in Figure 3. 2, M task types must be distinguished. The reason for this distinction is to allow specification of sets of tasks which may share information and specification of sets of tasks with similar execution characteristics. Thus, tasks of a given type may be allowed to share information: for example, the procedure of tasks of the same type may be sharable among these tasks. Furthermore, tasks of a given type are not distinguished from one another in a queue and in the sense that their execution characteristics are all drawn from the same probability distributions. 2) The probability that a new arrival at the memory queue in Figure 3. 2 is a task of type i; i=1, 2,..., M; is independent of the status of the system at the time of arrival. The probability that a newly arriving task is of type i is an input parameter to the model and is denoted by bi, and of course, M bi=l. i=l The assumption that the types of newly arriving tasks are independent of the status of the system and in particular of the number of tasks of each type already in the system is justified if users are independent of one another. 3) When a task completes and leaves the system, a new task

89 immediately enters the mlemory queue. As stated above, the new entry in the memory queue is not necessarily a task of the same type as the task which terminated. The assumption implies that there are always a fixed number of tasks in the model. This number is an input parameter and is denoted by N. This restricts attention to a system under heavy load, and this is the condition where choice of scheduling rule is especially important to performance of the system. With this assumption we assure that there are always tasks awaiting loading and thus assure a heavily loaded (perhaps overloaded would be a better term) computer system. A situation similar to this actually occurs in a system with a limited number of users (perhaps limited by available terminals), each making a new request shortly after receiving a response to the previous request. 4) The time required to move a task from the memory queue to the CPU queue in Figure 3. 2 is a variable which is dependent only on the type of task being loaded and on whether or not other tasks of the same type are in main memory. Thus, given the type of task to be loaded and knowing whether other tasks of the same type are in main memory, the time required to load the task is a known constant and is another of the parameters required to specify the model. During the course of this study data were collected which included the loading times for many tasks. When these tasks are sorted by type, it is found that loading times for each type do not vary greatly from one load to another. Some of these data are presented in Appendix

90 D and provide justification for the foregoing assumption. 5) The length of time a task uses a CPU before requesting an I/O operation is exponentially or hyperexponentially distributed with parameters of the distribution dependent on the type of task using the CPU. Relating this to Figure 3. 2, the boxes labelled Central Processors may be considered exponential or hyperexponential servers with the parameters of the service distribution dependent on the type of task in service. These parameters must, of course, be specified and are among the input parameters of the model. The small amount of data previously available [ 41] on lengths of CPU intervals shows a good fit to the exponential. These data, however, lump all tasks in the computer system together. Data for individual tasks presented in Appendix D fit hyperexponential distributions very well. 6) Input/output delays are exponentially or hyperexponentially distributed with parameters of the distribution dependent on the type of task. This may be related to the boxes labelled I/O, Paging Delays in Figure 3. 2. Each such box holds a task entering it an exponentially or hyperexponentially distributed amount of time, and the parameters of the delay distribution depend on the task type. An I/O delay is the time from request for an I/O operation until that operation is complete and the task either terminates or goes back to the CPU queue. This means that we do not model queuing explicitly at the I/O devices, and that there are

enough I/O delay boxes in Figure 3. 2 to handle the maximum number of tasks which may require them at any one time. The I/O delay is dependent on the type of task and on the number of other tasks competing for the available system I/O devices. That is, the effects of queuing on I/O delays are handled indirectly by including both queuing time at I/O devices and the time to perform the I/O operation in the I/O delay. In view of the multiplicity of such devices (e. g. drums, disks, printers, etc.) and the multiplicity of queues at some individual I/O devices (e.g. drum), this is felt to be a reasonable approximation. The data in Appendix D fit hyperexponential distributions quite well and data in [ 41] fit exponential distributions fairly well. 7) At completion of an I/O operation, a task may terminate and leave the system or may return to the CPU queue for another CPU interval. The probability of termination is independent of the number of execution intervals the task has already received. This probability is, however, dependent on the type of task and is a parameter of the model which must be specified. The probability that a task of type i terminates after an I/O delay is denoted by Pi (1 < i < M). The assumption that the termination probability is independent of the number of execution intervals already taken means that the total number of times the task goes through the execution-input/output cycle is a geometrically distributed random variable. This distribution was hypothesized first on the basis of data in [ 41] which show it to be possible. Data were then obtained (presented

92 in Chapter 4) which show this assumption to be valid. 8) All tasks of a given type require the same amount of main memory for execution. The amount of sharable and non-sharable memory required by each type of task must be specified. If the memory requirement for a task is broken into a part that can be shared with other tasks of the same type and a non-sharable part, then we assume each task of the same type requires the same amount of non-sharable memory. (The sharable memory requirements are also identical.) This assumption is made so it is always possible to determine whether there is room in the core to load a particular type of task without having to distinguish the memory requirements for each task of the type. The data in Appendix D indicate that this is not an unreasonable assumption. Furthermore, as shown in Appendix C, the variation in memory requirement from one task to another becomes less important in this regard as the number of programs being multiprogrammed increaseso In summary, in.the queuing model which we are developing in this chapter we distinguish tasks by type which is another way of saying they are distinguished, for example, by the procedure or code that they use. We would, for example, distinguish an assembler from a PL/1 compiler. The tasks of one particular type, however, are indistinguishable in the sense that no special inforlnation (such as their elapsed CPU time) is maintained about each one. The only information available which allows tasks of a given type to be distinguished is the tasks' status in the system. By this is meant an indication of the task's activity:

whether awaiting loading, queued at or using a CPU, or carrying out an input or output operation. Loading times, lengths of CPU intervals between I/O operations, times required to satisfy I/O requests, and the number of I/O operations before termiLations have distributions which are the same for all tasks of a single type. We now turn to a detailed description of the mathematical model. 3. 2 Mathematical Models In Chapters 1 and 2 we discussed the use of Markov models for modeling stochastic service systems. Discussed also were Markov renewal decision processes and techniques for finding optimal policies in a process of this type. We now turn to description of a specific Markov model for a multiprogrammed computer system. This model is suitable for analysis of the computer system throughput resulting from various task scheduling policies and is also suitable for application of the previously discussed optimization techniques in order to find scheduling rules which maximize throughput. To increase the generality of the results and to allow more comparisons of results, we will describe two closely related models: one to be used for obtaining opti mal scheduling policies and the other to model a scheduling policy similar to that in use on a typical large time - shared multiprogrammed computer system. This last will be called the heuristic scheduling policy. In what follows much of the material will be common to both systems, but where a distinction must be made reference will be m ade to the appropriate system by referring to either the optimization model o r to the single queue model. The term

"single queue" arises in the following way. In the optimization model, it is convenient to think of a separate memory queue and a separate CPU queue for each of the M types of tasks in the system. Then at a decision point, the optimum scheduler decides on the best task type to load and/or assign to a CPU and goes to the appropriate memory queue or CPU queue to get a task of that type. On the other hand, the heuristic scheduling policy makes no attempt to distinguish the M types of tasks, and so it is natural to think of all types of tasks occupying a single memory queue and a single CPU queue. The emphasis in the optimization of the task scheduling rules is on maximization of task completions per unit time in a heavily loaded (or overloaded) system. No consideration is given to response times of individual tasks. Scheduling policies are not influenced by such factors as elapsed waiting times in queues or the length of time a particular task has held the C PU. Thus there is no time slice in the optimization model. On the other hand, the scheduling rules in the single queue model are an approximation to first-come-first-serve (FCFS) for the loading of tasks from the memory queue and last-comefirst-serve (LCFS) for tasks arriving at the CPU. In the single queue model, one of the input parameters is the length of the CPU time slice. Results from the optimization and single queue models may be used to compare throughput for the two policies. It should be noted that since optimal policies maximize throughput, the average response to tasks is minimized for these policies. The variance of this response may be

95 large, but this price may be worth paying in order to maximize throughput during periods of system overload. It was originally proposed to model demand paging in a system ofs this type in some detail, but this was dropped after data were obtained which showed that a suitable characterization of the system may be obtained without this detail. In the remaining sections of this chapter, the goal is to define the model in detail so it is useful for determination of scheduling rules which maximize throughput and for determination of the throughput realized by both optimal scheduling rules and the heuristic scheduling rule which is to be considered. In order that the optimization method described in Chapter 2 be applicable it is necessary to define the states of the model and possible alternatives in each state so that transitions among states form a Markov chain. For each state and alternative the transition probabilities to all other states must be determined. It is also necessary to define a one transition return function such that the expectation of the return per unit time for a given scheduling policy corresponds to the expected system throughput. Then the optimization method may be used to determine a scheduling policy which maximizes this expectation. 3.3 Regeneration and Decision Points The models of multiprogrammed computer systems we are discussing in this chapter are Markov renewal decision processes (optimiz

96 ation) or simply Markov renewal processes if the decision variables are fixed (single queue). In a Markov renewal process the successive states of the model form a Markov chain while the time interval between successive state transitions is described by a distribution function which may be dependent on both the current and the next states. In a Markov renewal decision process this distribution function may depend on the decision variables as well as the state variables. In a Markov renewal process the time instants at which a transition is made are called regeneration points. It is at the instants of transition in a Markov renewal decision process that decision variables are chosen, and so we will call these time points the decision points of the Markov renewal decision process. Usually at a decision point a decision is made by the memory scheduler to move a task into main memory. The next decision point occurs at the completion of this transfer. The scheduler may also choose to take no action, and in this case the next decision point occurs after a time interval equal to the shortest possible loading time interval. For the single queue model we approximate the case where all tasks go into a single queue when they arrive at main memory and are loaded on a FCFS basis as space becomes available in main memory. This is discussed in detail in section 3. 7. When no load is possible because of inadequate space in core we assume a regeneration interval equal to that of the shortest possible loading time.

97 The task loading decisions made in the optimization model determine the time interval until the next decision point. Other events and decisions also occur at decision points. The CPU scheduler interrupts and reassigns (possibly to the same tasks) all CPU's. A CPU scheduting policy is chosen at the decision point and is used until the next one. This policy is a rule for assignment of tasks to CPU's when one becomes available. The assignment choice may depend on the status of other tasks in the main memory and in the memory queue but cannot depend on the time remaining till the next regeneration point. That is, a stationary, state-dependent CPU scheduling policy is used between decision points, and at each decision point a new policy may be chosen. A CPU becomes available for assignment by the CPU scheduler when a task using it requests an I/O operation (including a page demand) or is interrupted for some other reason. The CPU scheduler may also preempt a task using a CPU in order to re-assign the CPU to a task of higher priority which has just completed an I/O operation. An example of a CPU scheduling policy is a simple relative priority assigned to each type of task. Then whenever a CPU becomes available, that task in the CPU queue with the highest priority is executed. For the single queue model we approximate a situation in which tasks are assigned CPU's on a LCFS basis. This is discussed in section 3. 6 although it may be stated here that the approximation is exact when a task arrives in the CPU queue after completion of an aI/O operation. Again there is only a single queue for the CPU's. When a task completes

an I/O operation and requires more CPU time it is assigned a CPU immediately. If no CPU's are idle at the time of the request, the task preempts a user of one of the CPU's. All tasks using a CPU are equally likely to be preempted in this fashiono In the models the time between regeneration or decision points is known exactly. At one of these points we may choose either to load a task (if there is room in memory) or not load a task. We set the time between regeneration points when there is no task being loaded to unity and set times required to load tasks to integer multiples of this. Other times in the model are scaled accordingly. The time required to load a task is deterministic and depends on the type of task and whether or not there are other tasks of the same type in execution store at the time of the load. If some information is shared among tasks of the same type, then the loading time for tasks of a type already in memory may be reduced by the fact that some of the information required by the task is already loaded. The loading times (integer) and space requirements (total memory size = P pages) for a task of type k (k = 1,..., M) are Ck total number of pages of sharable information dk: number of pages of non-sharable information Ick loading time when no other task of same type is in memory Idk loading time when another task of the same type is in memory. At a decision point we make a decision, denoted by D, which is a

99 specification among other things of the type of task to be loaded, if any. The current state is denoted by i1 and specifies what tasks are in memory. The decision, D, and current state, il, determine the task to be loaded and the time required to load the task which is the time between decision points. For our model, then, we have a specialization of the most general MRDP because the distribution function for the time between transitions depends only on the initial state, il, and not on the final state, i2 Furthermore it is an especially simple lattice distribution because it is a delayed unit step function. That is, if ID is the time between 11 transitions FD (T) =F () = U (T-ID ili2 1 1 where U(x){ 7, x<O 1, x>O When D specifies no load, I = 1. When D specifies that a type k 11 task is to be loaded and i1 indicates there are other tasks of type k in memory then I= Idk Complete specification of the decision vector, D, will be given later. For the single queue model the same loading times are required for tasks, but tasks are loaded into memory on a FCFS basis as space in memory becomes available. We now give a description and definition for an arbitrary state of the model by means of a set of state variables.

100 3. 4 State Variables The state of the Markov chain defined at successive decision points is given by specifying the status of the system at these time instants. This status information includes, for each type of task, the number in the memory queue, in the CPU queue and in input/ output. The state may thus be specified by the three - tuple, (a,f3, Y) where each of these variables represents a vector: a (fgl,.. gM) = (hl,.., hM) fk = number of type k tasks queued outside main memory gk = number of type k tasks queued at or using a CPU hk - number of type k tasks in I/O (inculuding pagidg) We also define zk = gk + hk: the number of type k tasks in main memory. For convenience we define a function T(a, _, y) which maps each state into a unique integer state designator i. For the particular state (al,1,y ) we write iI =T(a1,3Vy) An assumption was made that whenever a task terminates and leaves the system a new task immediately arrives at the system. This

101 leads to the following condition on the state variables: M (fk + gk+ hk) =N where N is the constant number of tasks queued at or in memory. It should also be noted that in specifying the state, no indication is given of the status of tasks individually: but rather the status of each type of task is given. Thus the aggregate number of memory pages allotted to data for all type k tasks is assumed to be divided equally among these tasks as mentioned earlier. This brings us to another restriction on the state variables; namely,that the total number of pages used by the tasks in main memory must be less than or equal to the total pages in memory available for these tasks, P. This restriction is given explicitly following a discussion of the memory space required by tasks. If we are modeling a system where an entire task is moved into main memory before execution begins, then we may use ck as the number of pages of sharable information required for type k tasks and this number is independent of the number of tasks of type k in core. On the other hand we may be modeling a system operating in a page-on-demand mode. In this situation we may assume that a single type k task has clk pages of sharable information in core. With two type k tasks in main memory we have a total of C2k pages of sharable information in core because the second task may be using some pages which are different than those in use by the first task.

102 With n type k tasks in core we have cn k and of course cnk < ck If tasks are independent of one another and each page of the total ck pages is equally likely to be in use by each task, we may compute cn k based on a knowledge of Clk. The table derived in Appendix A may be used for this purpose. clk may be estimated from system data and so this is a useful approximation. The parameter dk is defined as the number of non-sharable pages a type k task has in core. This may be the task's entire complement of non-sharable pages or perhaps some fraction of them. We may now write out explicitly the restriction on the state variables which states that the tasks in memory must not require more than the P available memory pages. M k= (zk + Z kdk) < P where Cok = 0. In systems where all sharable pages are loaded into memory we have czk k Z > k k =0 zk 0 3. 5 Decision Variables At each regeneration point in the model a memory scheduling and CPU scheduling alternative must be chosen. These alternatives together form the decision made at the regeneration point~ In general, decisions at successive regeneration points may be made randomly,

103 may depend on values of some or all of the state variables, on the time remaining till the system shuts down, or on some combination of these factors. We will always assume that the time until the system shuts down is long enough so that no error will arise by considering it to be infinite. This is perfectly reasonable when one considers that the time between transitions may be measured in milli-seconds while the total continuous running time of the system between shutdowns may normally be measured in hours. If we specify a decision for each state of the model where this decision is dependent only on the system statse then this decision specifies a stationary policy. An optimal decision vector has been found if no other decision vector exists which results in greater computer system throughput. It can be shown [ 16] that optimal policies for the model being developed here exist which are both stationary and deterministic. For such a policy, the scheduling decision is completely determined when the state of the system is known. Since policies of this type are also easiest to implement, we will not consider random or time-varying scheduling policies. Decisions which may be made at a regeneration point may be specified by a vector, (a1, a4), in the optimization model. This will be made more clear after we define the components of this vector. a1: a1 = 0 means no task is to be loaded in the next interval. a1 = k means load a type k task in the next interval.

104 a4: a4 = (kl,...,kM) specifies the relative priority at the CPU's for each task type. The variable ki specifies the type of task which has priority i at the CPU; thus k1 specifies the task type with highest priority and kM the task type with lowest priority. For convenience we define a function D which maps each decision vector into a unique linear decision designator. When we desire to indicate that a variable depends on the decision made, we superscript that variable with a D rather than the entire decision vector. Let us now define the function D. To do this we need to know the values which the decision variables may assume and the range of these values. The decision variables may assume only integer values. al may assume values 0,.l.,, M corresponding to the possible decisions to load any type of task and to the decision to load no task. Thus al may take on M+1 values. The decision variable a4 was defined as a vector (kl,.., kM) where the values of the k. range from 1 to M and give the priority of each task type at the CPUO There are actually M! different CPU scheduling policies possible which means that the interval (1, M!) is sufficient for all CPU scheduling policies. For convenience, we may map each CPU scheduling vector into a unique integer by forming the integer a4 =kl k2'.~ k from the vector (kl,..,kM ). For M < 10 this may be a radix 10 number. For M > 10 choose the radix M. In any event, the range of values which this integer may take on is now

105 (12... M, M...1) and this is greater than M!. Only M, however, of the integers in this range are legal scheduling policies for the central processor. We may now give D as a function of a1 and a4. D = (M + ) a4 + a1 Many of the values of D which would be generated by allowing al and a4 to take on all values in their interval of definition do not correspond to any physical alternatives in the model. Many other alternatives (values of D) may be chosen only in subsets of the total states of the model. For example, a decision to load a task may not be made unless the state of the model is such that there is room in main memory for the task. Neither of these facts presents any additional complexity from a computational point of view. In a given state, the components of the decision function (the decision vectors) are constrained as follows. 1) A decision to load a task of type i (a1 = i) may be made only if the memory space required by the task does not exceed the available memory space (space not in use by other tasks). 2) A decision to load a type i task may not be made unless there is a type i task in the memory queue. 3) The CPU priority vector, a4, is restricted so that priorities of task types which are not in the main memory all have lower priorities than any priority of a task type which is in main

106 memory. 4) The CPU priorities for task types not in main memory are assigned so that these task types appear in ascending order in the CPU priority vector. The first two restrictions assure that only legal decisions are made in the states of the model. The last two restrictions assure that there is a one-one mapping between possible values of D and physical scheduling choices at the CPU. This is done by assigning CPU priorities to tasks which are unable to make use of the CPU in a unique way. 3. 6 Submodels One of the main goals in this chapter is to determine the probabilities of transition between all pairs of states under all possible alternatives (D) in the Markov model of the computer system. In section 3.3 it was explained that these transitions occur at particular instants of time which are called regeneration points or decision points. Before giving a derivation of these transition probabilities in the model, it is necessary to discuss the events which occur between two such regeneration or decision points and to describe these events mathematically. Recall that this time interval is dependent on the time required to load a task into main memory; the time is unity if no task is being loaded. In terms of Figure 3. 2, concern is with the events which occur inside the dashed line (including the possibility of task terminations) during the time between two regeneration or decision points. In this interval tasks may queue at the CPU, or they may use the CPU for a

107 period of time and then either request an I/O operation or return to the CPU queue because of preemption by another task or time-slice runout. Tasks which request an I/O operation or which are in I/O at the beginning of the interval may stay in I/O, terminate, or request another CPU interval. In section 3. 1 we stated assumptions about the lengths of CPU and I/O intervals and about the number of CPU-I/O cycles before termination. These assumptions are that CPU and I/O intervals are exponentially or hyperexponentially distributed and that the number of CPU - I/O cycles is a geometrically distributed random variable. These assumptions allow events between regeneration or decision points to be described by a continuous time, finite state Markov process. By modeling the events which occur between regeneration points by means of such processes we obtain results which are needed in the determination of transition probabilities for the model. The parameters of these processes will depend on the state at the regeneration or decision point and on the CPU priority vector, a4. We will refer to these Markov processes as submodels to distinguish them from the MRP or MRDP of the single queue model and optimization model, respectively. Thus for each decision in each state of the model, a submodel is defined and this submodel is used in the determination of the transition probabilities from the given state under t he given decision to all oth er states of t he mode l.

108 It may be recalled from Chapter 1 that a continuous time Markov process can be defined by means of an initial vector of state probabilities and by a transition intensity matrix which will be denoted by A. It is the purpose of the remainder of this section to define suitable states for the submodels and to determine transition intensities between all pairs of states in these submodels. An initial vector of state probabilities for each submodel is defined in terms of the state of the model at the regeneration or decision point. It may appear that the number of such submodels and therefore the computation required for them would be excessive since one or more submodels is defined for each state of the model. It is shown, however, that by suitable choice of computational method, solution can essentially be carried out for large numbers of submodels simultaneously. Then the vector of state probabilities for the submodel at the end of the regeneration interval is used as part of the function which specifies the transition probabilities from the initial state to every other state of the model. Most of these probabilities are seen to be zero.

109 A submodel of the optimization model has states which may be described as a pair of vectors ( C,,) where 7= (uV.'., uM) Uk = number of type k tasks queued at or using a CPU Vk number of type k tasks in I/O. In the optimization model, the actual assignment of CPU's to tasks is determined by decision variable a4 for each state. That is, when a CPU becomes free due to termination of an execution interval, the scheduling policy determines which of the available tasks will be allowed to use the CPU. Suppose the CPU scheduling policy is a4 = (kl,.., kM) which is an ordering of task types from highest to lowest priority. Define sI as the number of type Q tasks using a CPTJ. Obviously 1i < u,. Then if we have L CPU's (we will restrict L to one or two in the model), we get kl = min (k, L) k 1 sk2 = min (uk L-s k) 2 2 M-1 Sk min (u, L-k ) skM k For the single queue model the CPU assignment is not a deterministic

function of C and a4. Therefore we must add another state vector to the submodels here, = (Sl,..., sM) sk = number of type k tasks using CPU's. For each type of task we must specify the mean CPU interval, the mean I/O delay, the total mean CPU time required before completion, and the probalility that a task using the CPU is interrupted for other than an I/O delay. Define the following parameters: il/uk: mean CPU interval between I/O requests for type k tasks l/vk: mean time required to satisfy an I/O request (including page request) for type k tasks. Pk: probability that a type k task terminates after completion of an I/O operation. 1-Pk: probability that a task requires another CPU interval after an I/O operation is complete. 1/p: the mean time slice for all types of tasks in the single queue model. In most systems the time slice is a known fixed interval, but in the model the time slice has an exponential distribution. The use of a time slice may affect the results in the single queue model but has no effect in the optimization model. For an optimal scheduling policy we assign the CPU based on the number of tasks of each type in the memory queues and CPU queues. These numbers do not change when a time

slice runs out and therefore the optimal scheduler will re-assign the CPU to the same type of task. We now have defined all parameters necessary for a complete specification of the submodels for both the optimization and single queue models. As stated earlier, these submodels are continuous time, finite state, Markov processes. It is necessary to obtain transient solutions to these models for the time between two regeneration points. Let us now take a closer look at these submodels. First expressions are obtained which may be used to get the transition intensities between all pairs of states in any submodel and thus to define a transition intensity matrix, A. Then the initial state probability vector for an arbitrary submodel is obtained as a function of the state of the model at the regeneration or decision point. By means of vectors ~, rl, and 4' we have defined the states of a submodel. Transition from one state to another may be defined in terms of a transition intensity which is a function of the elements of these vectors and of /uk' Vk, and Pk; k = 1,..,M. By determining all possible transitions and their intensities for all the states of a submodel, a transition intensity matrix, A, may be formed. Most entries in this matrix will be zero. Next the transitions which may occur in a submodel are given along with the associated transition intensities. It may be helpful to refer to Figure 3. 2 in order to put these transitions in the context of the model.

1) A type i task which is currently using a central processor may request an I/O operation. Given a state in which one or more type 1 tasks are using central processors, it is possible for one of these tasks to request an I/O operation at some point in time. The state transition here includes the movement of a type i task from a CPU to I/O. This frees a CPU Which must now be assigned to one of the tasks in the CPU queue, if any. In the optimization model the assignment of a queued task to the available CPU is deterministic and depends only on the CPU priority vector, a4, for the submodel. Therefore the change in state for this transition may be written Ui - u.-1 v. - v.+1 1 1 If si type i tasks are using central processors, then the transition intensity for the optimization model in this case is siLi. Note, however, that for the optimization model, Vp = (sl,.. SM) is not actually part of the state specification but rather is determined from the vectors and a4. In the single queue model, on the other hand, there is no CPU priority vector and so if is needed to specify the state. Also the state variables do not contain a record of the order of the CPU queue but only the number of tasks of each type in the queue. Therefore the CPU's must be assigned probabilistically as they become arvailable. The probability that a task of type j is at the head of the CPU queue is assumed to be proportional to the number of type j tasks in the queue

113 relative to the total number enqueued. Therefore the probability that the CPU released by the type i task is assigned to a type j task is U. -S. M (uk-sk) k=l1 The change in state for this transition is written.-i - i 1 v. -S. + 1 and the transition intensity is s i(uj - sj) M Z (Uk Sk) k=1 It is possible, of course, that no tasks are queued at the CPU when the type i task completes its CPU interval, and then the transition is u.-U. - 1 1 1 v.-v. +1 s.-s.- 1 and the intensity in this case is si,i. 2) A task of type i currently in I/O may require another CPU interval. There may be several type i tasks in I/O, and one of these may complete its I/O operation and request another CPU interval at some instant of

time. At completion of an I/O operation, a task may terminate or request another CPU interval; and a CPU interval is requested with probability 1 - Pi for a type i task. In the optimization model, the change in state for the transition is Ui - U. + 1 Vi - Vi - 1 and the transition intensity is vivi(1-Pi). If the type i task going from I/O to the central processors is of higher priority than one or more of the tasks using CPU's at the time of the transition, then the type i task is assigned the CPU in use by the lowest priority task and this task goes into the CPU queue. For the single queue model, CPU's are assigned to tasks coming from I/O on a LCFS basis and so the type i task preempts a task using a CPU if there are no idle CPU's. Each such task is preempted with equal probability and thus a type j task loses the CPU to the type i task with probability sj/L. This transition is UiUi+ 1 v. -v. - 1 1 1 s. -.s. + 1 s.-s.-1 J J and the intensity for the transition is vi vi(1-pi)sj/L. Of course, if the type i task arrived to find an idle CPU, the transition would be Ui -Ui. + 1 1 1 v. -v. - 1 1 1 s -s. +1 1 1

and the intensity in this case is viv.i(1-Pi). 3) A task of type i currently in input/output may terminate and leave the system. At completion of an I/O operation a task of type i terminates with probability Pi. With vi type i tasks in I/O, the intensity of I/O completions for tasks of this type is vivi. Thus for both the optimization and single queue models the state change for this transition may be written vi Vi - 1 and the transition intensity for the two models is vivipi. 4) In the single queue model a task of type i currently using a central processor may exhaust its time slice. For the optimization model the CPU is assigned on the basis of the priorities of the M types of tasks and so a time slice runout in this model would result in the same task type being re-assigned the CPU. Thus the same state would be occupied after time slice runout as before and so a time slice in this model has no effect on the transition intensity matrix for the submodels. For the single queue model, the CPU queue may be empty and in this case also time slice runout for a task is ineffective. Next suppose the CPU queue is not empty in the single queue model, and the time slice for a type i task runs out. As in 1) above the CPU released by the type i task is assigned probabilistically to tasks in the CPU queue. As stated above this is an approximation to the deterministic CPU assignment which would be made in a system where an ordered CPU queue is maintained. As in 1) above, the available

CPU is assigned to a type j task with probability U. - S. J J M U (u -Sk) The intensity with which a type i task gives up a CPU due to time slice runout is sip, and so the transition intensity here is siP(Uj- sj) M Z (uk- Sk) k —l The state change for this transition is expressed as i 1 S. - S. + 1 3 3 We now have an expression for the transition intensity from any submodel state to any other submodel state. The states which must occur in the state space include all states to which transition may be made from every possible initial state during the regeneration interval. In this interval many transitions may occur. Thus the state space must include at least all possible CPU-I/O configurations of tasks for the initial number of tasks in core and for all lesser numbers of tasks in core.

117 Our ultimate use for the submodels is to aid in determination of transition probabilities in the model by providing a probability for each task configuration in core at the end of a regeneration interval, given the task configuration at the beginning of the interval. Define a vector of state probabilities, p(t) = (Pl(t),.. pz (t)), for a submodel with z states. Pi(t) is the probability that we are in state i of the submodel at time t. Define p(O) to be the vector of state probabilities at the regeneration point. Then with regeneration interval ID, or simply Ii for the single queue model,we are interested in determining p(ID) or p(I. ). p(t) must satisfy a system of linear differential equations with 11 constant coefficients, p (t) = p(t) A (3. 1) Initial conditions necessary to solve this system of equations are provided by the known state of the model (il) at the regeneration point and the relationship between this state in the model and states in the submodel. The model state is i, = T (aX, yb = T (fl"'fM' gl'gM' hl'''' hM) In the optimization model, the initial submodel state can be found very simply from this. There is a one - one correspondence between vectors B, y in the model and states in a submodel. Suppose we denote the submodel state at the regeneration point by 1, U ) where

118 1U1 =(Vl,..., UM) 7) - (v1v*..,vM) Then knowing i1, we have 1 1 u. = gi 1 1 v. =h. 1 1 Note that the memory queue configuration does not matter here. Suppose we denote the initial submodel state by jl = V ( a, 71 ) where V is a function which maps the state vector into a linear index. Then for our initial conditions on the state probability vectors we have p (o) = 1 Pij(O) = j J l With these initial conditions we may now solve the system of differential equations (3. 1) and determine p(I. ). For the single queue model the relation between states in the model and those in the submodel is not quite so simple. In this case we have an additional state vector, 4, representing the assignment of central processors to tasks. We have the same relationships as before between the vectors,B, y in the model and, 77 in the submodel. Now, however, there may be more than one possible CPU assignment, V/, for given r, 77 and so corresponding to vectors i, y of the state i, there may be multiple corresponding states; j; in the submodel

119 corresponding to the possible initial CPU assignments in the submodel. The probability of occurrence for each initial CPU assignment is determined using the same approximation used earlier to assign a task to a CPU when one becomes available. Let us consider the initial conditions for one and two central processors. Suppose jl corresponds to assignment of a type f task to the single CPU. Then pj (O)= u1 M Z Uk k=l As the other case suppose there are two CPU's. Suppose jl corresponds to a state in which both CPU's are assigned to type I tasks and j2 to a state in which one CPU is assigned to a type f task and the other to a type j task. Then our initial probabilities for these two states in the submodel are up (U- 1) n_ (0) = u $ J M M E uk E (u k1) k=1 k=1 2u u. p. (0) = u -- u 2 M M (Uk) (Uk- l) k=l k=l As in the optimization model, these initial conditions can be used to obtain solutions to the system of differential equations.

120 The solution to Equations (3. 1) is well-known [ 19 ]. We have p(O) and the transition intensity matrix, A, and so the solution is p(t) = p()eAt where e I + At + + + At 2! 3! Recall that the time between regeneration or decision points is restricted to integer values up to some maximum, say Tmax. Therefore we need A 2A TmaxA A only compute e, e..., e Computation of e is discussed in Appendix Bo We have enough information now to obtain solutions to all needed submodels, The question is, how many such submodels must be solved? Actually a more pertinent question is: for how many transition intensity matrices, A, must we compute e; since this is the difficult part from a computational viewpoint. We may determine all state probability vectors from a single transition intensity matrix for each CPU scheduling policy if desired. Simply set up a state space which includes the maximum number of every type of task in core with every possible configuration in core. Then in the state space for the matrix, A, we have all possible configurations of tasks in core for the model. Now we may compute eA, (eA) O., (eA) maxand by setting appropriate initial conditions p(O) for various states, i, of the model, may easily compute p(l), p(2), o.I, p(Tmax ) It may, however, be more efficient to obtain solutions to a number of smaller submodels.

Let us take a simple example in which M=2 (two task types). The notation (x,y) will be used where x refers to the number of type 1 tasks in core and y refers to the number of type 2 tasks in core. Suppose there are enough pages of core ( P) for 3 type 1 tasks (3,0) or for 2 type 2 tasks (0, 2). It is also possible for 1 type 1 and 1 type 2 task (1, 1) to share core simultaneously. In this case we consider a submodel which includes all possible states in which there are three type 1 tasks and two type 2 tasks in core (submodel (3, 2)). For the optimization model we must consider all possible locations for all tasks: CPU or I/O. For type 1 tasks, there may be 0, 1, 2, or 3 tasks at the CPU at the same time there are 3, 2, 1, or 0 tasks in I/O. Similar configurations are possible for type 2 tasks. Since any number of tasks may terminate in the interval we must include in our state space all configurations with lesser numbers of tasks in core including the state in which all tasks have terminated and there are no tasks remaining in core. The number of states in this submodel is easily found to be 60, On the other hand we could have chosen to solve three smaller submodels, Note that the submodel in the previous paragraph contains several states which are unusable since they correspond to no state in the model. We could have chosen to salve submodels (3, 0), (0, 2) and (1, 1) and would have covered all model states this way. Note that the aggregate number of states for all three of these submodels is only 11 and that now we are working with 4x4, 3x3, and 4x4 A matrices for

122 a total of only 41 elements rather than a single 60x60 matrix or 3600 elements. It is clear that solution of the three smaller submodels is the preferable method. 3. 7 Transition Probabilities In this section we determine expressions for the transition probabilities for both the optimization model and single queue modeL We are interested in determining the probability of transition from arbitrary state iI to arbitrary state i2. The transition probability is denoted by PilP2 for the optimization model and Pi i for the single queue model. 12 1112 The transition probabilities in the optimization model depend on the decision, D,chosen where D = D (a1, a4 )o Recall that 1,1 i =T (a, 1 1 i2= T(a, 2) That is iI and i2 are determined by the state vectors a, I, and y where a specifies the tasks in the memory queue, 1 specifies tasks at CPUts, and y specifies tasks in I/O. In the optimization model there is a one - to - one correspondence between states and decisions of the model defined at regeneration points and states of the submodels. That is, for initial state iI and decision D there exists a corresponding state jl in a submodeL These states are related through the decision D and vectors p3 and y in the

123 model and vectors and /71 in the submodel. The specific functional relationships are given in Section 3. 6. Using the initial state i1 we determine an initial state for the submodeilj 1. This gives us our submodel initial conditions p. (0) = 1 31 Knowing these allows solution of the submodel which gives us a probability vector p(Ii). This solution is discussed fully in section 3.6 where the submodels are described. In particular, one element of this solution vector corresponds to state i2 in the model. Call this element Pj (i ). This gives the probability that j, = v(, v )7 occurs at the end of the regeneration interval where 2 2 2 Fo (vl1,., v,y For state i2 we have i2 = T(a2,,' ) where 2 2 2 = (hl,...,hM)

124 Then the relationship between 2, 71 and 2,y is (in terms of the elements of these vectors) 2 2 gk = Uk + 1 k = a1 (loading decision) 2 uk; k a1 2 2 hk v; allk Thus i2 and y2 may be determined from 2, 2 so that the probability 2 2 of occurrence of 23, r may be found at the end of the regeneration interval given B, y at the beginning of the interval. This specifies the configuration of tasks in memory and so what remains is to determine the probability of occurrence of the new memory queue configuration, 2 (o f2)O We may note here that the states to which transition may be made from i1 are restricted by the possible values of a in the following wayso M 2 2 2 (fQ + g2 + h ) = N (3.0 2) 2 1 a ff2 fI + 6 >a > ~0 Y (3. 3) 6 is the Kronecker delta and thus is zero unless a type Q task was loaded in the regeneration interval, in which case it is one. A2 is the number of new tasks of type X that arrive at the memory queue during the interval I. D 11 Recall that b is an input parameter which is the probability that a

125 newly arriving task at the memory queue is of type 2 independent of any previous arrivals or the status of the model. Therefore we may compute 2 2 2 the probability that vector a =(fl,..,f) occurs conditional on the vector a and the loading decision al. The multinomial coefficient, (ZA )! Q=1, determines the number of ways in which Ai type i tasks arrive at the memory queue; i=1, 2,...,M. Each order of arrival occurs with probability lb and so M Pr a2 a, al} = =1 (3.4) 2(A,!)... (AM!) 2=1 where the f2 (f = 1,...,M ) are constrained by Equations (3. 2) and (3. 3). The probability of any vector a occuring which does not meet these constraints is zero. We now give the transition probability which is Pi i2 p (IM [(A1!).. (AM!) 2n b' (3.5) (Jl!)(.. (Am!) =1 To summarize briefly, it will generally be true that for most states, i2, the transition probability p.i2 = 0. The only transitions I12 of interest are those which can occur with non-zero probability, and these transition probabilities are generated by first using the given relations between model and sub.model states to find the initial submodel state. Then numerical methods are used to find the state p robability

126 vector for the submodel, p(. D) For each submodel state occurring with probability greater than zero we again use these relations to determine the corresponding state variables in the decision point model. At this point the only state variables remaining to be determined are a2 = (f 1"'' fM ); these are constrained by Equations (3. 2) and (3. 3), and the probability of occurrence of any vector a meeting the constraints is given by Equation (3. 4). We now have probabilities of occurrence associated with all the state variables which make up state i2. These probabilities are multiplied in Equation (3. 5) to yield the transition probability Pill D 112 So far we have discussed only the optimization model. Determination of pii2 for the single queue model is somewhat more difficult for 1 2 two reasons. First, in the optimization model the decision variable al determines what task type is to be loaded into core from the memory queue while in the single queue model the task type to be loaded is determined probabilistically as outlined in the following paragraph. Second, in the optimization model the CPU assignments are deterministic and can be derived from the decision variable a4 (CPU priority vector) and the tasks at the CPUis while in the single queue model the CPU is assigned in a more random fashion. This means that submodels re - quire the vector 4s= (s,... SM) as part of their state specification and so there is now a one-to-many correspondence between states in the model and states in the submodels.

127 In the single queue model we want tasks entering the memory queue to be serviced on a FCFS basis. Modeling this exactly would require maintaining a record of the order of the memory queue and this would increase the number of states in the cirodel to an unmanageable number. Therefore we approximate FCFS behavior by maintaining only a record of the number of tasks of each type in the memory queua, With fk (k=1,.., M) tasks of type k in the memory queue we assume the probability that a type i task is at the head of the queue i s fi/Zfko If there is room in memory for the type i task we load it; if not there is no load. Thus fi/Yfk is the probability of loading a task of type i providing there is room for it in memory. Assuming there is not room in memory for tasks of type il,.., i (n < M) the probability that no task is loaded is n pr { no task loaded} -= -1 Q M fk k=l Since we do not actually know what task type is being loaded, if any, we do not know the length of the regeneration interval. The above probabilities permit computation of the expected regeneration interval, however, and we use this expectation rounded to the nearest integer as the value for I. Two problems arise because the tasks are not assigned to CPU's in a deterministic fashion. Our goal is to determine P. i and to do! 1

128 this we must relate inital submodel states to i and final submodel states to i2. We have a one- one correspondence between ( and y in the model and C, r in the submodel as stated earlier. Now, however, there may be more than one possible CPU assignment ( 4q). Suppose the initial submodel states corresponding to i1 are jl,..' m and those corresponding to i2 are kl,...,kn. Our initial conditions in the submodel are the possible initial assignment of CPU's to tasks. Proabilities for these assignrre nts were given in Section 3. 6 and are used to obtain solutions to the submodels. This may be sumna rized by saying that the initial state i1 corresponds to more than one state in the submodel. Therefore we must assign initial probabilities to these states. In the optimization model the probability was simply one for the single corresponding state. The rationale for these particular probabilities was given earlier where we discussed assignment of CPU's to tasks in the CPU queue. At the end of the regeneration interval we want to know the probability we are in i2. Submodel states corresponding to i2 are kl,..., kn Therefore we compute n Z Pkl (I.) Q=1kf 11 We are now ready to determine Pi i. De f ine ~m ~2 2 Q = f P P P~~ + 5 Pm

129 8 = 1; Q = m and room in memory for type Q task = 0 otherwise Then an argument similar to that used to derive Equation (3. 5) yields M f l 2 1 M1 (m m L Pr {a a'} = m k-,; In this equation the constraints given in Equations (3. 2) an<! (3. 3) hold by replacing he by l. Any term where the constraints do not hold m= ~=1 b=1 is set to zero. Finally we get n _i2 i =1Pk (Ii) Pr {a a1 } 1 2 Q=1 Qk 3. 8 Reward Matrix The reward for making a transition from state i! to state i2 is the number of task completions during the interval between the regeneration points. The goal of the optimization model is to determine a task scheduling rule which will maximize the number of completions per unit time. For the single queue model we wish to determine the number of completions per unit time for the scheduling rule used in this model. In either case, the one step reward is needed to determine this throughput. For the optimization model we apply the optimization method in Chapter 2 (time - optimal problem). For the single queue model the

130 problem is simply the trivial optimization problem where there is one alternative in each state and the same solution method applies~ The reward or number of completions in an interval for the optimization problem is R D D 2 1 i (Ii ) (= (f f_ + 6 1R2 1 =1 1 In the single queue model we may have loaded any one of several types of tasks so we have M f M1 R 11 (i ) + 6 I m=l k(_lf l=1 k=l k At this point the model has been completely specified, and the optimization methods derived in Chapter 2 may be applied to it. It may be recalled that for certain conditions on the transition probabilities under the possible alternatuves it was shown that the bounds on the gain and the gain rate (which correspond to throughput here) could be guaranteed to converge. Applicability of these conditions to the current model is discussed in Appendix F. 3o 9 Overhead In the preceding sections of this chaper we have discussed models of multiprogrammed computer systems which utilize reentrant, shared procedure. The savings to be realized by sharing procedure were discussed (memory space savings, reduction of I/D traffic) but no additional costs associated with sharing information among users have been given.

There may be costs associated with sharing, however. Depending on the hardware configuration and how this is used by the operating system, it may be necessary for the supervisor to maintain and update information about pages available to be shared and what tasks are currently using these pageso The addition of these tables to main memory, and maintenance and use of these tables introduce an additional supervisory overhead over that for a system which does not share code. This overhead appears in the form of reduced main memory space available for tasks because of the additional system tables and in the form of increased CPU time necessary for execution of the additional bookkeeping tasks brought on by the use of sharing. If we wish to compare the operation of a system under conditions where both sharing of information is and is not allowed, then for systems where there is additional overhead required to share information we must account for this in the model in order to obtain a valid comparison. A straightforward way to do this is to assume that CPU intervals are shorter for given tasks when information is not shared and to assume that the total memory requirements for a task's potentially sharable information is greater when the information is actually shared than when it is not. Suppose we are sharing information and our parameters for a type k task are c k' dk, and gk for the number of pages of sharable information, non-sharable information, and the central processor service rate'for

13.2 this task, Then for the model where no sharing can occur we have Ck = 0 k d = Ck + dk - Xk = 1/ak Here Xk is the number of pages of tables needed to allow sharing and k Ok is the mean processor time needed in each CPU interval to carry out the supervisor tasks which handle sharing. Quantization of these variables may be difficult since there will usually be no way to observe a system running in both a sharing and non-sharing mode, On the other hand some hardware configurations allow information to be shared with essentially no additional overhead and in this case the relations above are not needed. 3. 10 Summary This chapter contains a detailed description of a mathematical model of multiprogrammed computer systems. The model was developed to allow comparison of task scheduling policies and the use or non-use of shared information and the effects of these on system throughput in a heavily loaded computer system. Tasks which have been loaded into the execution store of the commputer are characterized as alternating between requests for the CPU and requests for input or output operations. A queue is maintained at the CPU (or possibly two CPU's) and variation of task priorities in this queue may be investigated for effects on throughput,

133 A second queue is maintained for requests for execution of tasks. These requests are not eligible to execute until they are loaded into the execution store. This is again a scheduling decision and effects on throughput when the policy here is changed may also be investigated. Parameters of the model which may be varied include the size of the execution store, and the use or non-use of shared information (e. g. reentrant procedure) by tasks. In the next chapter we compare system throughput under optimal and heuristic scheduling policies, and as a function of these parameters.

Chapter 4 EFFECTS OF SCHEDULING AND SHARED INFORMATION In this chapter we present results of application of the models described in Chapter 3. The data collected and analyzed from the MTS system were used to obtain parameters for the mathematical models and results of using these parameters are shown. Miuch of these data is presented in Appendix D. Parameterization of the model to represent MTS and results of that representation are given in the first ten sections of this chapter. In the last section we hypothesize other systems suitable for use with optimal scheduling rules and shared information and present results for these. 4. 1 Scheduled Tasks Only a subset of all ta sk:s run on MTS were deemed suitable for consideration in the scheduling model, and reasons for this are discussed below. The models described in Chapter 3 are useful for determining the increase in task completions per unit time (throughput) possible by sharing information among tasks and/or scheduling the memory and the central processors optimally for these tasks. The models are aimed at using system resources most efficiently without regard to the response given individual users. Maximizing throughput assures minimum average response to users, but individual response times may be unacceptably large for some of the tasks in a time-shared system 134

135; such as MTS. In a system of this type users who make trivial requests expect and should receive short response times, and so for this reason trivial'tasks are not suitable for the scheduling model. In addition, since the demand on system resources made by these tasks is minirnal, the advantage gained by scheduling them to make best use of reentrant code would be small. A good example of a task of this type is the line file editor (*ED) in the MTS system. This is a highly interactive program run by terminal users who wish to make alterations, additions, or deletions to line files stored on disks. The user issues a command to make a particular change from the terminal and a response is made to the terminal when the change is complete. A typical command requires a very small amount of CPU time to complete and the editor has small memory requirements as well, Delaying response to a command in order to use system resources more efficiently would result in little savings while the delay to the user who normally must wait for a response before giving a new command might- well be intolerable. For the scheduling model data it was decided to consider only reasonably large (15 or more virtual pages) tasks. Furthermore, attention was restricted to public tasks since these are the only tasks

136 for which a priori information may reasonably be obtained about their behavior during execution, and knowledge of this behavior is needed in order to make intelligent scheduling decisions. In addition, known interactive tasks were excluded from the model. These were PIL (Pittsburgh Interpretive Language) and DCALC, a program which allows the terminal to be used much like a sophisticated desk calculator. Thus the tasks considered in the scheduling model were those tasks which have a known behavior and which make non-trivial demands on the system. In the remainder of this chapter, these tasks will be referred to as scheduled tasks while other tasks using the system will be referred to as non-scheduled tasks. 4.2 Use of Reentrant Code All the MTS data analyzed in this report were collected over a period of about 22 minutes at a time when the system was under heavy load. By far the most heavily used program during the data collection period was the Fortran compiler (41 requests). Next among the tasks considered in the scheduling model (scheduled tasks) was the smaller of the two University of Waterloo Fortrancompilers (*SWAT) with 13 requests. The assembler was run eight times and the Snobol 4 compiler twice. Since data were collected for aplproximately twenty

137 two minutes we see that requests for Fortran arrive at a rate of about two per minute so there woald appear to be some advantage in the use of a reentrant compiler. On the other hand, the rate of arrival of the other types of tasks was felt to be so low that they would not warrant the use of reentrant code. This is especially true because the Waterloo Fortran compiler executes the programs it compiles, and of course little sharing would be possible during this phase of execution anyway. Thus the only program assumed reentrant in the model was the IBM Fortran IV compiler. It has been estimated that if the IBM Fortran IV (G) compiler were made reentrant there would be approximately nine pages of procedure which could be shared. The remainder of the required storage would be used for tables unique to each compilation. The data show that tasks used an average 30 virtual pages during Fortran compilations and an average 25 real pages. For completeness it should be mentioned that three pages in virtual memory consist of tables used by system routines to monitor the status of the user and are thus not part of the compiler itself. They still must be treated as part of a user's virtual (and possibly real) memory, of course. If we assume that the ratio of real pages to virtual pages in the Fortran compiler is the same for both procedure and data, we arrive at 7.5 procedure pages in core and 17.5 data pages in core. Seven

138 procedure pages and eighteen data pages were chosen for the model. If two or more tasks are using the compiler simultaneously they may not be referring to the same procedure pages. Table A. 1 in Appendix A may be used to estimate the number of procedure pages in core when more than one compilation is proceeding. In particular we may look at the table for c equal to 9 and interpolate w and q. Rounding, we find that with two compilations in memory we would expect eght procedure pages and with three or more compilations all nine procedure pages. The remainder of the scheduled tasks are assumed non-reentrant. From the data they were found to have an average of twenty-two pages in core. 4.3 CPU and I/O Interval Distributions As part of their input data, the models developed in Chapter 3 require for each task the mean CPU interval between I/C) requests and the mean interval between request for an I/O operation and completion of that operation. In addition, the empirical probability distribution functions for these intervals are of interest because these distributions may be used to check the assumption that the intervals are exponentially or hyperexponentially distributed. Figures D. 2 and D. 3 in Appendix D show the cumulative distributions of CPU intervals and I/O intervals for the Fortran compiler. Exponential and hyperexponential distributions with the same mean

139 are shown also. It is clear that the hyperexponential curve fits the data much better than the exponential curve in each case. The same' quantities are plotted in Figures4. 1 and 4. 2 for the other scheduled tasks. Again the hyperexponential fit is seen to be significantly better than the exponential fit. The disadvantage of using hypero pontential rather than exponential distributions in the model is that this significantly increases the number of states in the model. This in turn limits the range of other parameters which may be chosen because of computational costs. Results were obtained using both exponential and hyperexponential distributions and compared. The throughput was found to differ by less than one percent in the cases compared. On this basis it was decided to assume exponential distributions for the remainder of the models. 4.4 Paging The MTS data indicate that the number of pages a task has in core does not vary widely during that task's execution, and in fact that the number of virtual and real pages a particular task type is assigned does not vary widely from se execution to the next. For example, Table D. 2 in Appendix D shows that over all the Fortran executions during the data collection period, the virtual pages

140 a) CDQ,~~~~~~~~~~~~~~~~C) ~I O Io I C co'0 \, _ ~ Ct t-'\: -E..z R V) ) \ w'' _ o c OZ c~~-~ ~~ I 00 1I- I0 LA v mICS r I o D Cl 0r ~C: ~ ~ ~r: a) CDJ C 0 00 C0D

141 cr*-~~~~~~c V. 0' \gg~. CYN ~~~ ~ ~0 C:: C:~~~~~~~~~~~~~~C ~~~~~~BO~~~~~~~~~~~~O1 CLJ Cl. 0 a.)~~~c / a) cr 0 -~~~~~~~~~~~~~~~ cnOO~~~~~~~~~~~~~~~~~~ S L.~~~~~~~~I I 1 IC,/i... -Vt ~~~~~C) r CD ~00 i 0 Lr\ % CY C'41 r — CD 15o $4ll ISV908d 1.-I ~ ~ ~ ~ ~ ~ r L ~IQ m t cl~~~~~~~~~~~~~~~~~~~~~~~~~94I

142 averaged around 30 with a standard deviation of only 9 while the real pages averaged around 25 with a standard deviation of only 8. This observation makes it reasonable to assume that a task executes with a constant number of pages in main memory. Furthermore it lends credence to the assumption that all tasks of the same type have the same number of pages (further justified in Appendix C). In the model, page waits were lumped together with other kinds of I/O requests. It is interesting to note that the total time spent in page wait is generally low compared to that spent doing other types of input-output and further there are usually significantly fewer page waits than other I/O operations. Again as an example, Table D. 2 shows 8.13 seconds spent in I/O (excluding paging) and only.434 seconds in page wait for the average Fortran execution. In the same table it is seen that on the average there were 63. 1 I/O waits per execution but only 14.4 page waits per execution. Physically, these facts indicate that the results would not change greatly if paging were ignored completely in the model. Inclusion of paging in the model amounts to adding a relatively small number of short I/O requests to the other I/O requests made by the task. 4.5 Number of CPU - I/OI ntervals In the model it is assumed that a task of a particular type alternates between use of the CPU and I/O devices until it terminates. The number of suchC PU - I/O cycles is assumed geometrically

143 distributed. Figures 4 3 and 4.4 sh3ow the empirical distributions for both Fortran and the other scheduled tasks plotted along with geometric distributions of the same mean. The geometric assumption appears reasonable in both cases. In these curves we have included page waits as well as other I/Q Similar graphs were plotted which exclude page waits and it was found that the fit to a geometric distribution is still good. These latter curves are not shown here because they are very similar to Figures 4. 3 and 4.4. 4. 6 Central Processors The Michigan Terminal System has two central processors which have equal status in the system. Therefore two central processors were used in the model of MTS. A difficulty arises with the model of the central processors because the tasks under consideration in the scheduling model are not all the tasks making use of MTS. The scheduled tasks used about 17 % of the total available processor time during the data collection period with the remainder of the processor time being used by other MTS tasks and by the supervisor. The problem then is to account for the interference with the scheduled tasks by other tasks in the system, and this may reasonably be done by assuming the C PU runs at some fraction of its true rate. This assumption becomes more attractive when it is realized that a task in MTS is unlikely to finish a CPU interval without interruption anyway.

144 _., 00 0 0 o H _ U "" C),~: \ L) e - w c\ o -' a) O0 a v M O - % N., U 111 1Sr.OU C ) C E0 N50 UA1I1I98OOd.~-,4,,,~~C L

145 0 0 0.). o-~ c cL so o, X LL\.C~~~~u - ~C....L~... L N Su A1I111V!Otld

146 The CPU switched from one task to another an average of once every 5. 7 milliseconds during the data collection period. Thus in MTS a task is very likely to have a CPU interval between I/O requests broken into two or more shorter intervals with periods of being queued at the CPU in between. This happens because tasks which complete an I/O or paging operation receive the CPU immediately (LCFS) rather than going to the end of the CPU queue and thus cause a service interruption for the task using the CPU at the time of the I/O completion. The difficulty with assuming a CPU running at a fraction of its true rate lies in determining just what that rate should be in orderto account properly for interference by other, non-scheduled tasks in the system. Since it was not possible to determine what the effective CPU rate should be, this problem was handled by obtaining results for two CPU rates: one known to be higher and the other lower than the true effective rate. These results are open to other interesting interpretations which are discussed in Section 4. 8 where the results are presented. The CPU rates chosen were a rate 170 that of the true CPU rate and a rate equal to the full CPU rate for the following reasons. The effective CPU rate is determined by the fraction of the available CPU time used by scheduled tasks when one or more are queued at the central processors. Since the data show the scheduled tasks use 17%o of the total available CPU time, these tasks must use more than 17% of the available CPU time when one or more are queued

147 at the CPU; and so a 17% rate is lower than the effective rate. On the other hand, when scheduled tasks are queued at the CPU, they undoubtedly do not monopolize the CPU and so a 100%0 rate is higher than the effective rate. Thus, assuming a CPU running at 17% its full rate overstates the amount of interference expected from non-scheduled tasks while a CPU running at 10 0% its full rate no doubt understates this interference. 4.7 Loading Scheduled Tasks The time requiredto load a task is assumed fixed for each task in the model. For the Fortran compiler this is quite a good assumption because the mean loading time is 5. 1 seconds with a standard deviation of 1. 8. For the other scheduled tasks the variation in loading time is substantially greater, but the assumption of a constant loading time has little effect on the results because load times are short compared to execution times. Under these circumstances it is the time spent in execution which is the major factor in determining thraxghput and no! the time required to load the task. The elapsed time required to load Fortran and the other scheduled tasks averaged 5. 1 and 9. 1 seconds, respectively. Loading times in the model are restricted to integer multiples of the shortest loading time up to a maximum multiple of three. The loading time for Fortran was chosen to be 5. 6 seconds and 8.4 seconds for the other scheduled tasks. If procedure is sharable and a user requests the Fortran com

148 piler when it is already in use, the procedure need not be loaded. The time required to set up the non-sharable storage for the new request is assumed to be 2. 8 seconds. One other point should be mentioned regarding the loading of scheduled tasks. No direct consideration is given to the CPU time used by the loader. This time is lumped with the CPU time used by tasks other than the scheduled tasks in the model. From the data it was found that 1. 67 seconds average CPU time were required to load the Fortran compiler. 4. 8 MTS Results Results are presented in this section which show throughput of scheduled tasks when system parameters are similar to those in MTS. Throughput is plotted for both reentrant and non-reentrant Fortran compilers and for optimal scheduling and scheduling similar to that in MTS. The model for MTS scheduling is presented in Chapter 3 and consists of an approximation to FCFS in the memory queue and LCFS in the CPU queue for jobs arriving in this queue after completion of an I/O operation. MTS is also assumed to give tasks a 0. 1 second time slice at the CPU. The results for MTS scheduling are labelled "Single Queue" on the graphs to distinguish them from results obtained when optimal scheduling is used. The results obtained from the model with values of parameters derived from data obtained from MTS are given in terms of task completions per second in Figures 4. 5 and 4.6. With these results it is

149 cu e0 4-' C' QC —._._ C V C) Qa) ) a) C.'. a) r CT - U E u =, bD E V3).cn~ rQ O OO o S a cU0 C E e v ~ cs N 0 aN033S?13d SNOllIldWO9 )IS V

150.06 P=9 0.05 C) ~.04 o.03 o.02 C_).01 1 2 3 4 5 6 7 8 FULL CPU RATE X X X X INFORMAT ION SHARING X X X OPTIMAL SCHEDULING X X X H IGHER MULTI PROGRAMM I NG X Figure 4.6. Throughput Using Parameters Derived From MTS Data

possible to compare system throughput of scheduled tasks when such things as memory size, scheduling policy, and use of reentrant code are varied. Values for the parameters of these figures are given in Table 4. 1, and the results given in the figures are explained and interpreted in the following paragraphs. The parameters in Table 4. 1 are those described in Chapter 3 where the scheduling models are developed. Tables in Appendix G give the policies which were foand to be optimal and which produced the results shown in the figures. Parameters for the low degree of multiprogramming (columns marked L in Table 4. 1) come directly from the data while those marked H are derived in section 4. 10. For the low degree of multiprogramming, the termination probabilities are the reciprocals of the mean numbers of CPU - I/O cycles shown in Figures 4.3 and 4.4. The mean CPU interval (full rate) for Fortran is obtained from Table D. 2 by dividing the CPU time per run by the sum of the I/O requests and page waits per run. The mean I/O interval for Fortran is also obtained from Table 1 2 by dividing the sum of the I/O time and page wait time per run by the sum of the number of I/O requests and page waits per run. The means of tIe procbability distributions shown in Figures D. 2 and D. 3 were not used for the mean CPU and I/O intervals because these figures do not include page waits. Mean CPU and I/O intervals for the other scheduled tasks were obtained in an analogous fashion although no table such as Table D. 2 is included for these tasks.

152 Table 4. 1 Parameter Values Derived From MTS Data Task types (M) 2 Tasks (N) 6 Pages available (P) 70, 90 Central processors 2 Time slice (sec) 0.1 ITEM FORTRAN OTHER Arrival probability (b). 5.5 Loading time (sec) First task 5.6 8.4 Additional tasks 2. 8 8.4 DEGREE OF MULTIPROGRAMMING L H L Termination probability (p).0129.0119...0 031.00403 Mean CPU interval (sec) 17o CPU rate.363.166 Full CPU rate. 0632.0583. 0288 0 270 Mean I/O interval (sec).110.104.418.393 Non-sharable pages in core 18 16 22 20 Sharable pages in core One task in core 7 6 0 0 Two tasks in core 8 8 0 0 Three or more tasks 9 9 0 0

153 In section 4. 6 it was pointed out that non-scheduled tasks may interfere with scheduled tasks at the central processors, and therefore there is a need to modify the CPUrate to account for this interference. In the model two CPU rates were used: one which was 17% of the true rate and another which was the full CPU rate. This appears in the model as a variation in the mean CPU intervals used between I/O operations by tasks. At the full CPU rate we use the mean CPU interval as determined from the data while at a 17% CPU rate we use that interval divided by. 17. With the CPU running at a 17% rate we are in effect representing a system more heavily loaded with non-scheduled tasks than the actual system was at the time of the data collection. Another interpretation for this amount of interference with scheduled tasks might be a system in which non- scheduled tasks are given priority at the central processors over scheduled tasks. Whereas a CPU running at 17% its true rate represents a situation in which more interference with scheduled tasks occurs than is actually the case in MTS, a CPU running at its full rate represents a situation with less CPU interference than is actually the case. This is also open to interesting interpretations. This situation would occur where scheduled tasks are given priority over non-scheduled tasks. By far the most interesting and useful interpretation, however, is that of assuming a system with three central processors where the

154 interference of scheduled tasks which would occur in a two processor system is taken care of by the third processor. This is an especially interesting interpretation because the natural next step in expansion of the MTS system is to add a third processor, since there is in fact no hope of raising throughput any great amount in the system as presently constituted no matter what kind of sharing of information Co scheduling is done. A look at the data reveals that during the data collection period the CPU was idle only five percent of the time and so this is the maximum increase in throughput attainable during this period. Adding a third CPU with no increase in main memory might well make the use of optimal scheduling and sharing of information more attractive as a means of increasing CPU utilization and thereby throughput by more effi cient use of real memory which would be relatively less abundant in this situation. As a final word on interpretation of the CPU rates, the true effective rate lies somewhere between the two rates given and so the true throughput should lie somewhere between the extremes given in the results, and more importantly the relative advantage of changing operating policies should lie between these results as given at the two CPU rates. The quantity of real mnemory allotted scheduled tasks was chosen to be 70 or 90 pages for all the results presented. The results in Figure 4.5 show the variation in throughput as available memory goes from 70 to 90 pages. The CPU rate for this figure

155 is 17%o the true rate and the number of pages allotted each task was the same as the number allotted by MTS during the data collection period. This corresponds to the column marked L in Table 4. 1 and represents the lower of the two degrees of multiprogramming considered. Results with a higher degree of multiprogramming will be discussed in section4. lOin detail. The mean number of pages actually allotted scheduled tasks by MTS during the time data were collected is close to 90 pages. All results in Figure 4. 6 are for this number of available real core pages. The relation between available memory for scheduled tasks and the number of pages of memory allotted each such task determines the number of tasks it is possible to multiprogram. Because of the assumption in the model of fixed memory requirements for each task, throughput as a function of available memory is not continuous but has jumps at points where it is possible to multiprogram some new combination of tasks. The results in Figure 4.6 show a maximum increase in throughput of scheduled tasks of 16% by going from non-reentrant code and MTS scheduling to reentrant code and optimal scheduling and using a 17% CPU rate. For 17% CPU rate or full CPU rate, the increase in throughput in going from non-reentrant code to reentrant code is around 12% while going from MTS scheduling to optimal scheduling results in a throughput increase of around 5 to 7%. The important thing to note here is that these increases are only for scheduled

156 tasks, and that throughput of non-scheduled tasks probably would not change significantly. Therefore total system throughput would change significantly less than the amounts given above: for example, a throughput increase of 16% for tasks using 17% of the total CPU time results in an increase in CPU utilization of only around 3%. 4.9 Implementation In the previous section, discussion centered on the increase in throughput attainable in MTS by use of optimal scheduling rules and by use of a reentrant Fortran compiler. In this section, consideration is given to the ways in which such sharing of information among tasks and such scheduling at the CPU's and main memory might be implemented in MTS. If the Fortran compiler were reentrant (it currently is not) then there would remain the problem of sharing this among users. There are two ways this may be done. A request for the compiler may result in a search of system tables to determine if the compiler is currently in use by another user, and if not, the compiler may be loaded. If it is in use then a segment table entry is set up to point to the appropriate page table for the sharable pages. (See Arden, et. al. [2] for a discussion of the memory organization assumed here. ) This method of operation has been found to require excessive overhead. To get around this the compiler may be made a permanent part of every user's virtual memory. Here the compiler occupies the same segment of

157 everyone's virtual store. Because virtual storage is so large, the loss in storage for those who do not use the compiler but still have it in their address space is insignificant. Thus it is reasonable to assume that the Fortran compiler may be shared with no significant increase in system overhead. This mode of operation has the further advantage that thie sharable procedure need never be loaded for any user and thus would result in less elapsed time per compilation for users and in a saving of CPU time for the system. (2. 6% of the total available CPU time was used in loading the Fortran compiler during the data collection period. ) Implementation of an optimal scheduling algorithm for some MTS tasks while scheduling others with the same algorithm currently in use requires an understanding of how tasks in MTS are currently scheduled. In the following paragraphs a brief explanation of MTS scheduling at memory and the CPU's is given in which we refer to scheduled tasks and the scheduler. As stated earlier, scheduled tasks are those tasks which were considered suitable for scheduling in a way to maximize the throughput without regard to individual response times; and the scheduler refers to an extension to the MTS supervisor which would implement the scheduling policy determined to be optimal for these tasks. In a virtual memory computer the degree of multiprogramming (number of programs being simultaneously multiprogrammed) is not

158 limited by the core memory available since the pages of a task do not have to be in core. It would be possible in most cases to operate such a system by loading every new task on demand, thereby eliminating any queuing at the memory. In such a situation the throughput is likely to increase up to a point as the degree of multiprogramming increases from zero. When the degree of multiprogramming inc-eases beyond this point, throughput decreases because of excessive paging. The degree of multiprogramming is such that each task has too few pages in core to allow it to execute for more than a very short time between page faults, and so a situation arises in which CPU utilization is low because much of the time all tasks in the system are waiting for requested pages to be brought from secondary storage. This situation has been called thrashing and is obviously undesirable. MTS avoids thrashing by controlling the number of users who have access to the memory in several distinct ways. Arriving batch tasks are queued outside main memory and are executed at a controlled rate which decreases as the number of currently active terminal tasks increase while at the same time the number of terminal users is limited by the total number of telephone lines connected to the system (around 80). In addition, if a task attempts to obtain a large number of real pages at a time when other tasks are using a large number of real pages, this task may be prevented from further execution until a time when demand for real core by other tasks is

159 not so great. This last restriction is the most direct method of preventing thrashing, but the other restrictions are important also. Thrashing of scheduled tasks under a policy determined to be optimal in the scheduling model is prevented simply by setting an upper limit on the number of tasks which may share core at any one time. This means that direct control of the degree of multiprogramming for scheduled tasks is used in place of controlling the rate of execution of batch tasks as described above. In the model this control is exercised by assuming each scheduled task requires a known amount of storage in order to execute without excessive paging, and this amount of storage must be free before the task is loaded. There is a fixed total quantity of storage available to the aggregate of scheduled tasks so this quantity minus the amount already in use gives the storage available to any task in the memory queue. Implementation of a scheduling policy similar to that found to be optimal for scheduled tasks in the model would require establishment of two memory queues: one for each type of scheduled task. Requests by batch or terminal users for execution of tasks identified by the supervisor as scheduled tasks would cause an entry in the appropriate memory queue. The scheduler would be table driven and would decide what type of task, if any, to load based on other scheduled tasks already loaded and in the memory queues. Loading of scheduled tasks would be done in this way rather than by loading of terminal tasks on demand and loading of batch tasks at a rate determined by

160 the terminal user load on the system. The order of service for each of these queues would, however, be immaterial and so terminal tasks in each queue could be serviced ahead of batch tasks if desired. CPU queuing must also be handled specially for scheduled tasks. Entries would be made into separate CPU queues for each type of scheduled task, but an entry would also be made in the CPU queue currently maintained by MTS for all tasks. The entry in this latter queue would simply indicate that a scheduled task occupies the queue position so that the scheduler can determine which type of scheduled task should actually receive the CPU when one of these entries arrives at the head of the queue. In this way the scheduler is able to assign the CPU to either type of scheduled task without interfering with the normal use of the CPU by other tasks in the system. The scheduling model is cyclic with a constant total number of tasks while the number of scheduled tasks in MTS may vary. Therefore the status of scheduled tasks in MTS may not correspond to any state in the scheduling model, but the policy determined to be optimal in the model with parameter values derived from MTS data may be used as a guide in setting up a table to drive the scheduler. If desired, optimal policies could be determined for several values of N(total number of tasks in system) and in this way as many entries as desired in the scheduling table can be directly determined. Thus the model does not provide an optimal scheduling policy directly but provides

161 a guide for the scheduling decisions which should be made and also provides a good estimate of the gain in throughput attainable with such a policy. Although sharing code may result in little additional system overhead, implementation of an optimal scheduling policy is another matter. This would require maintaining special queues for scheduled tasks and observing the status of these queues each time a CPU assignment decision or loading decision is to be made for a scheduled task. The overhead required to do this in MTS might well outweigh any advantage which might be gained. A computing system with a much more restricted class of users would be much more suitable for implementation of a policy like this. Here the optimal scheduler could be used for all tasks in the system and a greater throughput gain could be achieved for the same cost. 4. 10 Increased Multiprogramming We turn now to a discussion of the one case in Figure 4.6 where the number of real pages allotted each task was decreased in order to increase the degree of multiErogramming possible. A simple increase in the degree of multiprogramming would normally tend to increase system throughput, but in this case there is increased multiprogramming with fixed total memory allocation so that the number of page faults during task execution will increase which will tend to decrease throughput. Therefore it is of interest to look at the net effect of this change in core allocation. The

162 number of pages of core allocated tasks is given in the columns labelled H in Table 4. 1 along with other parameter values for this situation: these represent a decrease of about 10% in the number of pages allocated each task. The major difficulty in obtaining results for reduced core allocation lies in determining the expected number of page faults during execution of a task for this situation. Figures 4. 7 and 4. 8 are approximate curves showing the CPU time between page faults as a function of the number pf pages in core for the two task classifications used in the model. Figure 4. 7 was determined in the obvious way from the data given in Table D. 3 while Figure 4. 8 was found in a similar fashion for scheduled tasks other than Fortran. These curves are only approximate because the number of pages in core between page faults is not necessarily fixed so that only an average number in core can be obtained, and also because the data shown in Table D. 3 give mean time between page faults for a range of pages in core and Figures 4. 7 and 4. 8 simply plot the mean of that range. Nevertheless it is felt that these curves represent a useful approximation to the paging behavior of the tasks under consideration in the scheduling model, and so these figures will be used to determine the number of page faults during task execution when core allocation is reduced. The new number of page faults may then be used to get a new expectation for the number of CPU - I/O cycles before

163 700 600 s' 500 -,.c. 400 L.I ul B 300, 200 -0 100 *FORTRAN 0 10 20 30 40 PAGES IN CORE Figure 4. 7. CPU Interval Between Page Faults As a Function of Mean Number Pages In Core During Interval

164 700 600 (A 500 I),0 400 n 300 100 OTHER SCHEDULED TASKS 0 10 20 30 40 PAGES IN CORE Figure 4. 8. CPU Interval Between Page Faults As a Function of Mean Number Pages In Core During Interval

termination, and to get expectations for lengths of CPU intervals and I/O intervals. These are then used as new input parameters to the scheduling model (columns marked H in Table 4. 1). Suppose data for the core allocation for tasks as determined fromn the MTS data show an average x1page faults per execution. By definition of page fault there must have been a CPU interval before the first page fault and after the last one. These intervals will be ignored and we will concentrate on determination of the reduction of the length of the CPU intervals between the first and last page faults when the number of pages in core is reduced. Knowing the original core allocation per task, the CPU time, tl, between page faults may be determined from Figure 4. 7 or 4. 8. The CPU time, t2, between page faults when the core allocation per task is reduced may be determined similarly. The quantity to be determined is x2, the number of page faults when the core allocation is reduced for each task. This new number of page faults is used to determine a new number of CPU - I/O cycles before task termination and also to change the length of the average I/O interval since page faults in general require less time than other types of input or output. The average CPU time used between the first and last page fault is (x1 - l)t1 milliseconds as there is one less CPU interval between page faults than there are page faults. Over this period of CPU time there will be a page fault every t2 milliseconds on average when the core allocation for each task is reduced. Therefore

166 (x1 - 1)t1 x2= 1+ t t2 where a one is added to account for the fact that a page fault occurs at both ends of the C PU intervals between page faults. This expression should be a reasonable approximation for the mean number of page faults per task execution under conditions of reduced core allocation providing we do not change the core allocation by too large an extent. As an example, consider Fortran when the core allocation is reduced. From Figure 4. 7 it is seen that with the original core allocation of 25 pages, t1 = 215 milliseconds elapse between page faults on the average. The mean number of page faults per execution is x1 = 14.4 (see Table D. 2). With 22 pages in core, t2 = 145 milliseconds of CPU time are used between page faults. Thus 215 (14.4 - 1) x 2= 1+ = 20.9 145 is the average number of page faults per run when Fortran tasks have 22 pages in core. This leads to a new mean number of CPU - I/O cycles which is the sum of the number of I/O requests per run (63. 1 in Table D. 2) and the number of page faults per run (2 0.9). The reciprocal of this sum is the termination Wrobability in Table 4. 1. One other problem remains in determining parameter values for the case of reduced core allocation, and this is the problem of estimating the time required for a page fault. The increased rate at which page faults occur for each task as well as increased multiprogramming

167 could cause mean paging delays to increase because of increased congestion at the paging drum. For MTS, however, congestion at the drum channel was very low and remained low even with the increased paging so no appreciable error is introduced by assuming the mean paging delays remain constant. More specifically, the maximum drum busy fraction was determined to be less than.2 during the data collection period, and this goes up to a maximum of.27 when core allocation for all tasks is reduced by the amount given in Table 4. 1. The change in drum busy fraction was derived by assuming that the pages of core allocated tasks not included in the scheduling model were also reduced, and that this reduction causes an increase in paging activity for these tasks which is the same proportionately as the increase in paging activity for scheduled tasks. Another factor which influences mean paging delay is the fact that there are 18 queues for the two drums and this further tends to mitigate the effect of increased activity on mean delay. A comparison of bars 5 and 8 in Figure 4.6 shows that with MTS scheduling and no information sharing, throughput is increased about 20% simply by decreasing the number of pages allocated each task in order to increase the degree of multiprogramming. These results were obtained by assuming central processors which run at full rate and since all tasks and not just scheduled tasks, may be run with reduced core allocation, the results may be considered indicative of

168 the increase in throughput for MTS as a whole if there were three central processors, no increase in total main memory, and the increase in degree of multiprogramming made possible by the given decrease in core allocation for each task. It is clear that if more CPU power were added to the system, the degree of multiprogramming and thereby throughput could be raised with the real memory currently available and without danger of thrashing, although just how much the increase in degree of multiprogramming should be to maximize throughput is not given by these results. 4. 11 Further Results The results presented up to this point were obtained from the scheduling model by use of input parameters which were extracted from data obtained from a multiprogrammed computer system. Results are presented in this section for several sets of hypothetical data. These data were chosen to illustrate how throughput may be expected to vary over a range of values of certain parameters. Presented first is throughput in a system where parameters were chosen for which it was felt optimal scheduling would result in an especially large improvement in throughput. Next results are presented in which memory size is varied over a wide range, and finally results in which a relatively large fraction of the pages are sharable. For all these results it is assumed that each arriving task is placed in one of two possible classifications.

169 The first system to be discussed is one in which arriving tasks may be classified either as compute-bound or as I/O bound. Some of the arriving tasks use, on the average, ten times as much CPU time as I/O time, while the others require ten times as much I/O time as CPU time. There is a single CPU in the system, and core memory is of such a size relative to the arriving tasks that it is always possible to multiprogram two tasks. That is, the maximum degree of multiprogramming is always two. Figure 4.9 shows the effect on throughput as the fraction of arriving tasks that are I/O bound is varied, both for optimal scheduling and single queue scheduling. Table 4.2 gives parameter values in the model for the results shown. The figure shows a maximum gain in throughput of about 8% when optimal scheduling is used over single queue scheduling. It should be borne in mind that the single queue policy is itself a good heuristic scheduling algorithm since it gives tasks arriving at the CPU from I/O priority over any task using the CPU. This tends to keep I/O bound tasks from getting locked up in the CPU queue. Thus it is expected that the increase in throughput under optimal scheduling would be even greater in systems using other simple scheduling algorithms such as FCFS at all queues. The figure also shows the increase in throughput with optimal scheduling going to zero when only one type of task is arriving at the system, because in these cases there are no scheduling decisions to be made other than the trivial one of loading a task whenever there is room in core.

170 1. 2.0 L OPTIMAL SCHEDULING, EL 0.8- " SINGLE QUEUE (/) 0.6 mA 0.4 0. 2 0 _ I I 0 0.2 0.4 0.6 0.8 1.0 FRACTION OF ARRIVING TASKS THAT ARE I I O BOUND Figure 4.9. Variation of Throughput With Scheduling Policy and Relative Task Arrival Rates

171 Table 4. 2 Parameters For Results in Figure 4.9 Task types 2 Tasks 4 Page s available 5 0 CPU's 1 Task Completion Rate Limited By I/O CPU Arrival probability Variable Termination probability. 01. 0 1 Mean CPU interval (sec) 0.1 1. 0 Mean I/O interval 1. 0 0.1 Non- sharable pages 25 25 Sharable pages 0 0 Loading time 1 1 Another parameter varied when the arrival probability for each task type was 0.5 was the time-slice. The plotted values are for a time slice of 100 seconds which is effectively no interruptions due to time slice runout since the average CPU interval is no longer than one second. A time slice of. 0 1 second was' also tried and the throughput increased by around 1%. Actual increase would be even less than this since the model does not account for the overhead involved in switching tasks at the CPU. The optimal scheduling policy may be given as a table of schedul ing decisions. This table shows the decision to be made in each

172 possible state of the system. For the results shown in Figure 4.9, an optimal policy may be stated in simpler terms. The optimal scheduling policy given below was abstracted from the decision table produced by the computer program which determined the optimal policy. This policy is 1) If core is empty, load a CPU bound task if any are in the memory queue. Otherwise load an I/O bound task. 2) Always give an I/O bound task preemptive priority at the CPU. 3) If there is one task in core and it is I/O bound, load a CPU bound task if possible. If there are no CPU bound tasks in the memory queue, load an I/O bound task. 4) If there is one task in core and it is CPU bound, load an I/O bound task if possible. If there are no I/O bound tasks in the memory queue, load another CPU bound task. This is a good place to point out that sharing and optimal scheduling may operate at cross purposes to one another in the sense that the optimal scheduling policy with no sharing is to mix the task types in core while with sharing the degree of multiprogramming and thereby throughput may be increased by scheduling tasks of the same type together. We now present results for a system inwhich the memory size was varied over a range wide enough to exhibit the maximum range in system throughput.

173 The values of the parameters for Figure 4. 10 are given in Table 4. 3, and the policies found to be optimal are presented in Appendix G. Here is a situation where all tasks being run on the system are CPU bound, and so throughput is limited by saturation of the CPU when the possible degree of multiprogramming as determined by the size of memory is still fairly low. The maximum throughput is shown and occurs at 100% CPU utilization. When the memory is so small that no multiprogramming is possible, throughput is the same for all cases. When memory is very large, throughput is limited by available Table 4. 3 Parameters For Results Of Figure 4. 10 Task types (M) 2 Tasks (N) 5 CPUs ITEM TYPE 1 TYPE 2 Arrival probability.5. 5 Termination probability.01.0 2 Mean CPU Interval (sec) 1. 0 2. 0 Mean I/O Interval (sec).111.143 Non- sharable pages 20 15 Sharable pages 10 10 Loading time (sec) 1 1

174 00 0 0 0..-00 CC CLE fizz I Co 4 -. e — Lo0 o _'g8 CD V) I,, r4 E C', Ck'"' 1...0... QN033S Cd SNO illdW03 S~ 1 E -n. 0,~I r -n evJ r'I' -r CV ~~~~~~~~~~~~ ~~~~d~~b

175 CPU time. It is only in the middle range where use of reentrant code and scheduling affect system throughput. Of course we are assuming here as elsewhere that the additional I/O delay experienced by tasks as the degree of multiprogramming increases is insignificant over the range of interest and thus throughput is ultimately limited by the CPU and not by bottlenecks at I/O devices. Since the CPU is generally the most expensive single system resource this assumption is reasonable for most properly designed general purpose computing systems. The behavior shown in Figure 4. 10 would appear in Figures 4. 5 and 4. 11 if throughput had been computed for a wider range of memory sizes. In Figure 4. 11 throughput is shown for a system dedicated to running two types of tasks. Table 4.4 gives values of the parameters for these results and shows that the sharable fraction of the total information used by each type of task is substantial. The optimal scheduling policies are given in Appendix G. At 35 pages of core no multiprogramming is possible and so scheduling decisions and reentrant code do not affect throughput. At 60 pages the capability of sharing information is seen to have substantially more impact on throughput than optimal scheduling. This is due to the large fraction of sharable pages in the two types of tasks using the system. This means the degree of multiprogramming possible with sharing is substantially higher than that without sharing.

176 00 (1)ci* - Ci) * r ~ ~0- O * --. — t, O0 0 O0 0 0 0 0.C Q.) O~ 0 0 0 0N09S d oII1 *- aN033S N3d SNO13'ldWOD ISVl

177 Table 4. 4 Parameters For Results Of Figure 4. 11 Task types (M) 2 Tasks (N) 5 Pages available (P) 35, 60 CPUs 1 ITEM TYPE 1 TYPE 2 Arrival probability (b).5'5 Termination probability (p).0 1.01 Mean CPU Interval (sec). 1. 08 Mean I/O Interval (sec). 1.2 Non- sharable pages 10 15 Sharable pages 25 15 Loading time (sec) 1 1 Parameters such as those given in Table 4. 4 might arise in a small to medium scale multiprogrammed computer system which is dedicated to querying sharable data bases and perhaps updating the data and carrying out some computation with the data. Users give commands which initiate execution of one of several possible programs which use one or the other of the two sharable data bases.

Chapter 5 CONCLUSION The major efforts in this work have been directed toward derivation of a useful optimization method for Markov renewal decision processes (MRDP's), and toward development and application of a queuing model useful for determination of the effects of queue control rules on computer system efficiency. The queuing model is a Markov renewal process under any specific queue control rule and further may be formulated as a MRDP to find optimal control rules. Thus the MRDP optimization method derived in Chapter 2 is applicable to the computer system queueing model developed in Chapter 3, and results of this application are presented in Chapter 4. Ancillary to getting these results was collection and analysis of computer system data which provided concrete input parameters to the model and therefore results which have applicability to current multiprogrammed computer systems. Results of this data analysis are presented in both Chapter 4 and Appendix D. The major theoretical development in this thesis is the optimization method for infinite time Markov renewal decision processes in Chapter 2. Both optimization per unit time and per stage are treated; and the method provides a practical computational technique for models with large numbers of states, especially when transition matrices are 178

179 sparse. The adv<ant,re of having to store and use only non-zero elements of these matrices can be very great. Furthermore, models of most physical systems do have sparse transition matrices, and so this method should have wide applicability both for mnodels of computer systems and for models of other stochastic service systems which may be treated as MRDP's. There are two endeavors which might provide interesting and useful extensions to the work presented in Chapter 2. The first has to do with the rate of convergence of the optimization algorithm. This could be an attempt to find out what factors determine or affect the rate of convergence and an attempt to influence these factors in order to speed convergence. No formal attempt was made to study this problem although experience with optimization of scheduling rules showed that seemingly small changes in some parameters affected the rate of convergence quite substantially in some cases. The second has to do with determination of conditions which assure convergence of the algorithm that are more general than those given. The conditions given are sufficient for convergence and probably hold for almost all models of physical systems, but these conditions are certainly not necessary. Of course, even if the conditions given are not met, the algorithm is still useful as long as convergence does in fact occur. The model developed in Chapter 3 has rather general applicability to the problem of scheduling the two major resources of most computer

180 systems; main memory and the central processors. The goal is to schedule these resources in a way that maximizes system efficency. The complexity of this problem arises from having to schedule two separate resources which nonetheless are interdependent. Besides allowing comparison of scheduling rules for their effects on system efficiency, the model also allows investigation of the improvement in efficiency when information is sharable among tasks. In particular, in the development of this model, effort was concentrated on a formulation suitable for determining optimal scheduling policies and on formulation for a particular simple heuristic policy: FCFS at the memory and LCFS at the CPU's. It should be pointed out that in addition to the effort required to develop and describe this scheduling model, a very substantial programming effort was required to obtain useful results. The programming required probably matches that in many simulation models of computer systems. The advantage of the model here over a simulation model is that optimization is possible and results are not dependent on the particular sequence of random numbers generated during the simulation. Of course, a disadvantage is the necessity of assuming certain "nice" probability distributions such as the exponential. The results obtained from this mathematical model, in terms of system throughput, are presented as a function of memory size, scheduling rule, and whether or not sharing of information among

181 tasks is possible. Values for other parameters of the model were determined in some cases by analysis of data collected from a timeshared, multiprogrammed computer system. Effects of increasing the load on this system are shown as well as variation in throughput when the parameters given above are varied. Another result shows that scheduling and sharing of information are only important in an environment where there is enough memory to support some multiprogramming but not so much memory that full CPU utilization occurs simply due to the high degree of multiprogramming possible and independently of the scheduling policy used or sharing of information. One conclusion to be drawn from the results shown and from experience with the model is that the gain to be derived from optimal scheduling and sharing information depends strongly on the computer system and on the tasks which use it. Potentially, this gain will be greatest in systems where the users are constrained to run a small number of programs which contain a large percentage of sharable procedure or data. An example might be a computer used to update and query some form of intelligence data. Users may be constrained to interrogate the data through a given set of programs, and the same data may be required by more than one user.

182 At this point it would be well to reiterate some assumptions made in the model which would not strictly hold in the system being modelled. Any additional supervisory overhead brought about by implementat ion of an optimal scheduling policy was ignored. It was not feasible to estimate this for purposes of the model, but should certainly be a factor in any decision to use such a scheduling policy. In anenvironment where information is shared, an additional benefit of sharing may be the reduction in CPU time used by the loader due to the fact that only one copy of a task need be loaded for several users. On the other hand, this may be somewhat offset if there is additional supervisory overhead associated with the sharing of information. In the model CPU time used by the loader in moving a program into main memory in a form suitable for execution was ignored so that no cognizance was taken of the problem of scheduling the loader at the CPU or of savings in loader CPUtime when information is shared. This assumption was considered reasonable in view of the fact that the loader is usually a program characterized by large amounts of input/output relative to the amount of CPU time required. The results obtained by applying the optimization method developed in this work to an important computer system control problem should be useful to designers of such systems, while at the same time these results show that this optimization technique can profitably be used in the design of stochastic service systems.

183 Finally, a brief comment may be made on the data analysis carried out during this study. Computer system data are scarce and difficult to obtain, and so it is hoped that the data presented in this thesis will find applicablilty to computer system analysis efforts of others. For that reason, a substantial amount of data are presented which were not used directly in the analysis and optimization work in this thesis, but which it was felt would be of fairly general interest to other workers in the field.

Appendix A EXTENT OF PAGE SHARING IN MAIN MEMORY In this appendix we are concerned with a set of tasks in main memory which shares pages. For these tasks we assume a set of sharable pages common to all the tasks, but allow for the possibility that not all these pages are in main memory and further, that each of the pages which is in main memory is not in use by the entire set of tasks. Using simple assumptions, a functional relationship is obtained among the total number of sharable pages for a task, the number of those pages in core, and the number of those pages being used by each of the set of tasks in core. Stated in another way, the goal is to obtain a reasonable approximation to the number of sharable pages each task in main memory is making use of where more than one task may be using the same page because of the possibility of tasks sharing pages. In the derivation of this approximation all tasks make potential use of the same set of sharable pages, some of which may not be in core. Define w: the approximation to the number of sharable pages in use by each task. q: the total number of sharable pages in memory for the.tasks. z: the number of tasks in memory which may share these pages. c: the total number of sharable pages for these tasks. 184

185 Wm: the set of sharable pages in use by the mth task of the set of z tasks in memory. (n,. 1,..., z) Wm!: the cardinality of Wm We see that since sharing of pages among tasks is possible q < zw Also, of course, q < c The assumptions we make in this derivation are that all tasks of the same type are statistically independent of one another and that all possible page sets of a given size have equal probability of being in use by a given task. These assumptions represent a worst case as far as the extent of page sharing among tasks is concerned. We also assume that IWm - IWnI vm,n and of course it is just the cardinality of these sets for which we want an approximation. That is, our goal is a function w(q, z) to be used as an approximation to IWmI for all m. The function will be determined separately for each value of z. To determine the function we begin by assuming a value for w. Under our assumptions we are then able to compute the probability that any given number of pages is used by m tasks (m= 1,..., z). Our approximation consists of determining the expectation of the amount of page sharing which occurs and using this expectation as the amount of actual

186 page sharing. This expectation gives the amount of overlap of the sets Wm and gives the desired relation between the total number of sharable pages in memory (q) and the number of pages each task is using (w). The case z = 1 is trivial. Here w(q, 1) = q; z= 1. Next suppose z = 2. Again we assume a value for w, the cardinality of Wand W2. Choose any page, p, in W1. Then Prp E W21P e W1} = Pr{p E W2} = c Let S2 be the number of pages shared by both tasks. S2 is a random variable which may take on values from 0 to w. The probability that the page p, chosen above is not shared is w Pr{p/W2 pe WI } = 1- - From this and our prior assumptions: Pr{S = O} = (1 - — )I 2 c pr{S2 1} = w -C (1 -.) pr ( w )k (1- w-k pr{S2.=k} (-k H(c c The random variable S2 thus has a binomial distribution and 2. E(S2) = c c Now q = 2w - S2 C

187 Then w(q,2) = c - -;z = 2 Next let z =3. Again we assume the cardinality of sets W1, W2, and W3 is w. Again define S2 as the number of pages shared by Wm and W (m / n ). Then as before we have n E(S2) = It is also possible that all three tasks may share some pages. The number of pages so shared will be denoted by the random variable S3. Then the relation q =3w - 3S2 +S3 (A. 1) must hold. To get the approximation w in terms of q we replace S2 and S3 by their expected values in the same manner as before. To get E(S3) we proceed as follows. Analogous to the case where z = 2 we pick a page p E Wi and determine the probability that this page is also in W2 and W3. Pr{p E W2 nW3 I pe W1} = Pr{pE W P2, p W3! pW1} = Pr{p e W3 I p W1, p E W2} Pr{W2 IPEW1} _w w w c c 2 2 Pr{p W2 p W1} 1 - W I'~~~ - -~t

188 From this we get 2 w Pr(S3o) =o (1- w 2 Pr {S3 =k}= (w) w k 2 (132 (1 E(S3) = w 2 2 C C Replacing S2 and S3 by their expectations in Equation A. 1 we get W 3 q = 3w- 3 + 2 3 cw c w - 2 3cw2 22 + 3c w-qc =0

189 This cubic equation in w may be s:olved to yield w(q, 3) for positive integer values of q. Because analytic solution for z > 3 is difficult, values of w as a function of q, z, and c are tabulated at the end of this appendix (Table A. I). We may derive expressions for w for z = 4, 5,... individually for each z,but it seems more reasonable to try to get a general expression which holds ior ad z. To this end let us define a random variable Sn as the number of pages shared by all n of n tasks when each task is using w pages. We have already found S2 and S3 and of course S1 = w. Pick a page p W 1. Then P {p E (w2 n..."Wn ) p E Wl} = Pr{p E Wn Ip E Wln.. t Wn 1))} Pr{P E Wnl I PE(W 1n.e. nwn -}w Pr{PEW2Ip EW1} n-i w n-I c n-1 Pr{p ~ WnV2-,*- nWn) Ip e w,} = 1 - In-I n-i Pr{S k} = (w) ( W )k (1- w w-k c c n E(S) - n cnIn what follows we replace Sn by its expectation so that each of two different groups of n tasks may be assumed to share E(Sn) pages among all n of the tasks. We now obtain a relation among w, q, and z.

190 This will be a polynomial of degree z in w. The polynomial may be solved for w and is tabulated in Table A. I as mentioned earlier. We build up f(w, z) iteratively. First let q = zw + f 2(w, z) Here we have added the w pages of each of the z tasks. f2 accounts for the possible intersections. Next take all possible groups of two tasks and note that for each of these we have added in a number of pages equal to E(S2) twice. Thus q = zw - ( ) E(S2) + f3(w, z) Now take all possible groups of three tasks and we see that in each case we have added the pages shared by all three tasks three times and then subtracted these pages three times. Therefore = zw - (l2) E(S2) + (3 ) E(S3) + f4(w' z) Next take all possible groups of four and note that for each we have added the pages shared by all four, four times by adding the pages of each task individually. We then subtracted these same pages six, or(2 ) times when subtracting all possible pairs; and finally added the pages again four times, or(4) times when adding the pages shared by three tasks. Then in order to add these pages in exactly once, we must subtract them from each group of four tasks. So q =zw - (2) E(S2) + (3) E(S3) - (4) E(S4) +f5 (w). (2 2) 3 (S3) 4 (S4) + f, (w, z)~~~~~~

191 We continue forming larger groups until we have included all z tasks in a single group. Thus q = zw+. -(-1)(Z)E(n) + (ZE(S _n z) 2 n z z w n z w zw zw (2) c n n c c As stated above, this is a polynomial equation Of degree z in w and may oe solved numerically. Solutions are taoulated Ior 1 ~ z a 10 and tor 1 < c < 10 below.

192 O, t-e -0 _ t.0; f C c O - C ~ O e- ~N e. ~ fV N!'t h C._ )v C C ~ I.- C JN'C IO C- C CC! CCi C' O I C a I I j I II I I C,,I CIr,',,,,.'Og r'0,,., c, I _41 c.' r,., )" _ rc, 0 1e ~~ t ~ -~ 9J i ~., I,I c n, I c I 0 0 c'.C I.2 C' 0,..-:;I,. I I I.. II, It I - I 0 N * I * r * 1 9 I * 9~ * * * I * *. * * I I; 1,joI, IC h ~ t rdlC~ nj''Ce I "'' 1 Ci' * 1 I L I,1 cc rcr I 0 1 1, I 00 ~ COI 1!, " I ", I; I! IJ, II I I i Io C I,,o I ro e _,c. I - -,',,ci o,- 1' I *, * *. *ij C,* N.' *: *T t *.* * * IY - I | _ |! SONI C S)C) rVI C C)4! I 0 0 t o Io) _ P+'4 1' " i i I! 9\ 11 l -4 I, n tJII c 4'' > SCr tI Cm rC'-f m.c _zul >IrCI,0 NO,C I.- I. |',.'" 1.14I -- Ctr, C: It O -,' I.,-'i,, Ic-, Ir o I rC'o~I r~X~*C- ~II (,r C' I-IQ0NI00)'.tI0'cj a IC) C;~.-~ Ni~i~ I C 0' rHC)'I i I C, I C IC C EHl C3Q I C5 (3, IH 31 1;t' I CN! OX! t,', c: C.4 fjct: C I r~ lp Ct,C'I I' I I I I I I I.., ~~ 9 1 * 0 * 9 9 * ^*!.1,p 9 * 9 *. * 9. 1 i 1 tI I I l O I C C,I s c, 1 i CjlCD | 1r rei1 t; C-: t 9l1 CI 1 1 S P ~;4~ ~ ~ ~~ ~~C. I ~ 3 I I:.,t. i!,i, _'' i i | J I i I G ~; t _ I1 I i r I t,, M.r ~,Sj M _, ~ IJ-+ + is ~ + — i~! + ~1, 0 I -; 0!, a: I' I f } I I I Ii i! I:I t

193 _,'.' ": _'.- ~ L"'"'- C: L,"..L;.,~:% ~ l" " - (b.' t'N, t' 5;;' *~~r N c *r * rL t4 * * 7 O O - * t *'.. <. C.. (~ 1C' C 0 C'C C _,_i,'"i Q C.:C C) C..- _C I * * * | < w v, i j o t I e ~! * * ~ * 4. 4 o:( I i ~ CO~~~~~ | ~~r, < C, _: < o r? h Q(.) tbsO a < Cs ss e I. v, ~.. C'.'... -- I' I,. ".. cs < _, P t f; r_ r ) ": N 4 r"'z O Cl -C 6 t~~~ cP 4I.r tE i~ ct -..........'|;P t-C' * C` ~ O 4' 4 0 0 9 0 9 9 0 4 9. 9 9 9 0 0 0c * 5 * * * & *. * o o eS 1 C? C2 -- cF IC 1 i..., -. c., C-.4..<,, —, - C 4I I4 I C C0'-..'.' C: t I ~, _ t j e: ~ ~ C ~ ~f o ~ ~ e t j ~ ~ ~ _, ~r <^vn fr.v.x C,m q7,3 S z;.xs rCI " fl er Nu- x; _e cr; C~ 4 4J 4' " O 4 4 0 ", t C'. ~' L C I. — - 4,'C " O... P,.t CC) I N -2,; 4s cr;- cf 4, iN~ i r-: 1~~.4 * 1t 1 9 * * * 4 0 * * * 0 * I 0s 0 1 *' 0 * 9 0 * 4 C{- N I IC.-~-.-'c * I t~~~~ 4 -'C>C-C r'',,i b t ".\ t.'' "~ ~ ts t., t'.' ~,........ U'", Lf". "" LP,'.l ~ ~ C 2~0~~~~~~~~~~~~~,'t,tC''~ I -~ s3 e- e S C~ I ~- ~CI ~l ~ C~ ~ ~~l: ~rla I o * * * * 0 0! * * * - * * - *,*: * * o * * * 9 I ( - 43' -f Ad -4 I C: rC W x 6 X 1 X I'C', 6-N N e 4 C 4 ~ 1 ~~~~~~~~~~~~I I ('. r. C,' r,,. l _ - (..t r.-. I^ ~-N OC "- "" U",.~' C." t"-' 0'"T C2,C r.D t. I' t,:,e ~ ~ ~ _ 1- c a ~ ~ ~ ~:. ~ e. ~0 ~ ~ ~ ~ I'4 " I ""-'.(2- C2.' S, 4h 4 -',N:. it r.' -. -"_'. ~,. 4.,,... I f1I J - -.D,' I-.' cr I ~.e ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~..~0.O,-, c-.t o:'.. OC C. I,~,C.,.?'.!"- -,t,,t' ~IC -,:Z.b ~D L.r.- ~"'C',- r.O O,.i,C C) ~ ~ J ~ ~,, ~ ~ ~ ~ ~! ~, ~ ~ ~9 ~ ~ ~ ~ ""r'f C' -- L~ ~,, 1~,- I -.'~.:%:~'" gQ,-.q,:"~4 r~'.I:;.! I, -e-, t~.. - ~.,.~)r,'- 1'-. -. ~ c,, C,T C-' C'. I \ t-c I' —,~,~4, — p J u".'3(. I 1~~~~~~~~~~~~~~ I.'", / "',"..(- I~~~~~~~~~~~~~e,,,- g:..

194'C t, N;: 0 rI-. C, iC..C C' -.4 cN,' L"', 4''-4..'4; - j.., ~! t t t rj~ ~, ~ ~ ~ ~ 9 9. 9 9 9,, 9. 9, 9.",3 C C 0) CJ C - N i 1N 4'- W ~- r- &c toFc 9 - n' tC t- 0; N tC N C I, -, _ lT: F~ ~ i ~ N X~ Ill t -~ n 1 1 e ~Oro s, 9:' * * * * 9 9 * 9 *9 I 9 C C C;, --, -i ). _ _, C'. I.,,!) ) C. -,,- (N, C - 0: C:...i-'~,x. — 4 C.je. C) I -' _ ~ ~ ~' ~.P. tC. C, C) C. C) ~.'".N N'" -L..~ I' I.,.,:; )' N N.s L X': u i, <' ~. ~ ~..~ e C~.e ~ ~- ~ I i ~ 9 C' C. - 0 ~'-_._ "'- )..0 t I",P:. (~ CX. t,,. ~,'~,-..-4 I:'-. 0,' c"". -!". C2. 0) 9 C) C' C C)' C N'- r o r I; ~ ~* 9 * 9. 9 * I C C 0'- -4 fX N N3 -c I'-".-. ~ -'.')...~ c.. H''9 -'-i <' LI". t, C N,.4 C I',-'' r, - -,:' N Nc C.. I - c, ~ ~,, ~r ~L ~ I * C~ C\ * _' - (.);D h'.~ C' ~f e X' I. ~ ~* ~ ~~ +: L.-. t- fr b- -"2 W Cf 9-. N * *.4' L - L I"- r.; C" *'CL. _,, cl

Appendix B COMPUTATION OF eA We consider here the problem of computing the matrix eA in an efficient manner when the N x N matrix A is given. Much of what follows holds for any matrix A although the particular problem of interest is for A a transition intensity matrix. An efficient method of computation of eA is very useful because this matrix provides a solution to the general system of homogeneous linear differential equations of first order with constant coefficients. These equations are z(t) = z(t)C where z(t) is an N-vector and C an N x N matrix. Then the solution to these equations may be shown to be z(ty = z(O) eCt In what follows, Ct may be substituted for matrix A without difficulty. We may write S = e M+R K Ak where M = k! k=0 oo A R k!' k=K+1 195

196 A We use M as the approximating matrix for e and therefore are interested in determining how large K must be to give us an acceptably small error. Liou [33] proves Theorem BR. 1 If IIAIl < K + 2, then for all elements rij of R, JriJ <E = IIKl'1 1 (B. 1) N where IIAHI lail i, j-1 - This theorem gives an easily computed upper bound on all elements of the remainder matrix. Proof It can be shown that IlAkll < IIAIk, k=- 1,2,... Hence each element of the matrix A is less than or equal to I A | k. It follows that oo Jr.. < I fAilkP "A 13-" k=K+l' I r I < (K+1 +.lA. + 2 (K.i1) -(K+ 2)

197 If we choose. Kso that llAll < K + 2, then 1r K+)! AK+j Ail A K+2 We may now choose a maximum acceptable error, E, and use this in Equation (B. 1) to determine the number of terms, K, needed in an approximating series for eA This in itself may be satisfactory, but an N x N matrix multiplication is required for every additional term in the series and so for large K the computation required may be excessive. Figure B. i shows the variation in E with K for several values of II A. When A is a transition intensity matrix, the matrix S is a stochastic matrix with all row sums equal to one and so we certainly want e < 1. It is clear from this figure that the number of matrix multiplications necessary to achieve a given e is strongly dependent on Ail. The strong dependence of the number of required terms on I A j suggests we try to use a related matrix with smaller norm. In particular, define the matrix A B =- for some b = 1,2,.. We have |IBiI =. - -|AIl and define Q = eB = X + Y

198 _ i 09 U ~~~~~m 0 4j — 1 Q ~~~ 010 E= 0 R 1Xm r eZ o 0 CD Ln l_- oY X Ir - sE V) CV L~~C 1N,~~~~~~~~~~~~~~~~~~~~~~~~ V) o,.oo o oo,oo W S0 lN3WM3 Nl (3) 80883 WllWIXV L~ 1' I r — - r4 -q- r4 - r_._..._ — 4 - ~ o0~~~~~~~~V k It~ ~ ~ ~ ~ ~~~~~~~~~~~~~a,,~~~~~~~~~~~~~LJ p ~,~..~.-.~~~~~~~~~~~~~~~~~~~~~r I~ Ir c ~:)IC I~ I' I I I I ~~~~~~~~~~~~~~~~II I I W.1JN~~] I:) Oi3n wI xv

199 where X is the approximating series and Y is the remainder series as defined earlier for A using M and R. With matrix B we may compute X and then with b additional matrix multiplications recover an approximation to S. That is, 2b S X2b Suppose e is the maximum acceptable error in each element of the approximation to the matrix S. If Q were computed exactly then S could be determined with no error (except round-off error). But we use the approximation X for Q and so there is an error which we may call eb associated with this computation. This error eb may be propagated and grow as we take successive powers of X. Therefore Eb must be chosen to insure that this accumulated error is less than c0 when X is raised to the 2b power. In order to find an eb (in terms of eo) which assures that the allowable error e is not exceeded, assume that the maximum possible error occurs with the same sign in all elements of X. That is, Q = X + [l ]eb where [1] is an NxN matrix of ones. Then Q=2 (X + [l]eb) N (2) I ~ (X + E + E':i j (ij b (xjk +b) N 2 xxjk +(x..+ +Xjk) Eb+Eb ij=l j' x)E

200 N Now x..= 1 N _Xk < N Therefore the maximum error in Q2 is Eb - 1 (N+ 1) Eb where we have assumed Eb << N + 1. This error may actually be shown to be smaller by noting that the row sums of the actual error terms are equal to zero because row sums of any power of a transition intensity matrix are zero. Note also that this means the row sums of X are always equal to one. We may now square the approximation to Q and again assume the maximum error, Eb_l' occurs in every element of the approximating matrix. We get eb-2 =(N+ 1) Eb-l =(N+ 1)2 b Continuing this process we get b eo = (N + 1) Eb Therefore if we choose Eb I' (B.2) (N + 1) we are assured that no element of S - X2b will exceed Eo in absolute value.

201 Using Equations (B. 1) and (B. 2) it is possible to choose a value of b which results in the minimum number of matrix multiplications to obtain an approximation to S with maximum error.. In actual practice however, a rough estimate is sufficient. As an example suppose AII11 = 128 Eo: 10 N = 99 The number of matrix multiplications required as a function of |{ B1 is shown in Figure 13. 2. This number includes the b multiplications needed to get eA from eB. An actual minimum does not appear in Figure B. 2 although it is clear that we are very close to the minimum and that little additional computational savings can be realized by increasing the value of b further. A very pertinent fact about this figure is that it is not very sensitive to changes in N or E. This suggests using a rule of thumb where we choose b to get a matrix B with norm somewhere around 1. One final note may be made about the computational cost as we increase the number of states in the transition matrix. Usually as the number of states increases, 1A|il increases also since there are more terms in the sum which determine this quantity. And of course, the number of actual multiplications for a matrix multiplication goes up as N.

202 400 350. IIAII = 128 MAX ERROR, E = 10-6 N = 99 300 (T) 250 > 200 150 LU, 100 50 O, I 128 64 32 16 8 4 2 1 IIBII Figure B. 2 Matrix Multiplications to Compute eA Using \' Bk/k!

Appendix C DISPERSION OF MEMORY REQUIREMENTS WITH DEGREE OF MULTIPROGRAMMING This appendix contains a brief. discussion of the advantage which may accrue in terms ot more etficient use ot memory as the memory size is increased to allow more programs to share core simultaneously. No consideration is given to changes in other facets of the system needed to maintain balance as the memory size is increased (such as increased CPU power). Changes in other system tunctions are assumed to keep step with changes in the memory size. In a monoprogrammed computer system we may want assurance that some traction x(x > 2) of all the jobs which use the system will fit entirely within core memory. This requirement implies that we must supply some excess memory, zl, over the average memory requirement, ml, for a job. If we assume that system cost and capacity are proportional to the memory size then the tractional increase in cost over the average memory needed due to provision ot memory zl is f.z1 fl-,Z ml1 If we increase the memory size in order to be able to multiprogram two programs we must provide excess memory z2 in order to be assured that the same fraction x ot the sets of programs we wish to multiprogram 203

204 will fit. Our fractional cost increase tor memory in excess of our mean memory requirement is now z2 z2 2 m 2 2ml We wish to show that f2 < fl and in general that f < f which says n+1 n that as memory size is increased to allow a greater degree of multiprogramming, the excess memory which must be provided per task to assure that an acceptable traction of the sets of programs we wish to multiprogram will fit decreases and thus we use memory more etficiently. One way to see this is to look at the coefficient ot variation of memory requirements as we increase the degree ot multiprogramming. If tasks have mean size m1 and standard deviation sl, then the coefficient ot variation ot memory requirements in a monoprogrammed system is s1 1 m- m This is really an expression of dispersion of memory required as a fraction ot mean memory requirements of tasks. Assuming that tasks are statistically independent the mean (mn) and standard deviation (s n) of memory required when n tasks are multiprogrammed is just m =nm In 1 s = In s n 1 s s Thus c = n = 1 n m / n m n 1

205 and we see that the coefficient ot variation decreases as the degree of multiprogramming increases. Let us take a concrete example. Suppose memory size for tasks is normally distributed such that c _1 1 Ml 1 m1 3 We wish to determine the fraction of memory in excess of the mean re - quirement as we vary the degree of multiprogramming. Figure C. 1 shows this tor the cases where we want assurance that 7b%and 90%of the sets of tasks we multiprogram will fit in core. As another example, suppose the mean task size is 20 pages and task sizes are uniformly distributed trom 16 to 24 pages. We decide to provide memory 10%in excess ot our mean requirements in order to handle some ot the programs entirely within core which are larger than the mean program size. Then if we desire to multiprogram 1, 2, 3, or 4 tasks; we provide 22, 44, 66 and 88 pages respectively. Figure C. 2 gives the probability that a set of tasks will not fit in core as a tunction of the degree of multiprogramming. It is seen that the probability that tasks will not fit is substantially smaller with four tasks multiprogrammed than in a monoprogrammed configuration. Looked at in another way, this is a strong argument for having flexible partitions in a multiprogrammed computer system rather than partitioning core into tixed, equal size blocks.

206 o E ~ ~ *13 U) Bet - 8) 00 ~W.,.,) a. P,- - LL. U, a3a33N ASOW3W SS33X3 I VNOI I VNJ v, E=~~~~ Lr~~~~~~~~~~ -~~~~v 0~~~v 0

207 CDI t0 Cd C) 1 I I. I, I... CO Lt%\ C) O. 3Z A OW3W 033X3 S IHI* * 3ZIS ASOW3W c3f3lX311IM S)SVI IVHI A1ll8V8O d

Appendix D DATA COLLECTION AND ANALYSIS This appendix gives the background for the data collection and analysis carried out on the multiprogrammed, time-shared system at The University of Michigan and results from that effort. D. 1- System Description The computing system consists of an IBM System/360 Model 67 with two central processing units and 384 pages of core storage (1024 words per page). This is a virtual memory machine operated in a page-on-demand mode with paging to two drums (and possibly disks). The system runs under UMMPS (University of Michigan Multi-Programming System) which is described in more detail by Alexander [ 1 ] and Pinkerton [ 41 ]. In addition to the supervisor there exists a reentrant program, MTS (Michigan Terminal System) [ 54 ], which controls remote terminal users and the batch streams. Code has been added to the system which allows data collection to be initiated at the operator's console. The specific items which may be collected are described by Pinkerton [39,41]. Events which occur along with the time they occur are placed in buffers which are written onto tape when they are full. For example, each time the CPU changes hands, the time is recorded along with the identification 208

209 of the job relinquishing the CPU and the job receiving the CPU. Pinkerton has shown that the process of collecting data disturbs the system operation a negligible amount so no cognizance need be taken of this when interpreting results. D. 2 General Data The data presented here were collected October 10, 1970 about 3:00 p. m. This time was chosen in order to observe the system with as heavy a load as possible. During the data collection period (approximately 22 minutes) there were, on the average, about 50 terminal users and two batch streams active. The CPU time used may be placed in four broad categories. MTS batch and MTS terminal CPU time consists of time used by jobs in the batch stream and terminal users, respectively. Non-MTS CPU time is time used by system routines which cannot reasonably be charged to a particular job. Finally a CPU may be idle. The number of seconds spent by the central processors in each of these four categories is shown in Table D. 1. Table D. 1 CPU Use During Data Collection (seconds) Non-MTS 601 MTS batch 341 MTS Terminal 1571 Idle 129

210 During the data collection period the two CPU's were switched from one job to another a total of 470321 times. Thus the average length of time a job held a CPU was 5.7 ms. D. 3 Analysis for Specific Types of Tasks In this and following sections results of analysis of the collected data are presented. The data collection facility records a large amount of detailed information on the status of each job in the system, but a substantial amount of effort is required for analysis of these data in order to obtain results which are useful and interesting. The main results presented here consist of presentation of the running characteristics of each of several types of tasks in the system (e.g. an assembler). Figure D. 1 shows the cumulative distribution for the elapsed time between occurrence of a page fault and satisfaction of the page request. The particular curve shown here is for page faults during runs of a Fortran compiler, but the distribution is independent of the type of task. In the following sections we present results for each of several types of tasks using the system. By task we mean a program which is loaded and run from a terminal or batch stream. We give the elapsed time required to load the task. The remainder of the data presented give characteristics of the tasks from the

211 cs4 FV)CV ~F z ~ c- r. 0E O c0 LL O 00. -4 -rC~ s 0 0.,-( cv. \ S Q U~~~~~~ \.> p~~~~~~~~~~~~~~~~~~~~~a < Cx C~~~~~~~~~~~~~~e V Q~~,,~ ooD ~c 0 00 ~ v CM O'VEOtl

212 time loading is completed until execution of the task terminates. For each type of task a table presents means and standard deviations for elapsed execution time, CPU time, I/O time, and page wait time. The time the tasks are eligible to use the CPU (ready) may be obtained by subtracting CPU time, I/O time and page wait time from the elapsed running time. The mean number of I/O operations and the mean number of page waits per run are also given in this table. In addition the table shows virtual memory and real memory assigned to tasks during execution. The virtual memory consists of the memory assigned the executing task plus three pages of tables used by the system to keep track of the job status. Cumulative distributions are given for the length of time the task type uses the CPU between I/O requests and for the length of time the task type uses the CPU between page faults. Also distributions are given for the time required to carry out requested I/O operations (time from I/O request until request satisfied and task again eligible to use a CPU). In MTS, programs intended for public use (such as compilers and assemblers) are placed in files and given names preceded by an asterisk. Data analysis was carried out for each such identifiable public task run during the data collection period. In addition all non-public tasks were grouped together for analysis purposes and

213 are called user generated tasks. Many tasks other than the ones presented in this appendix were run during the data collection period. The ones chosen for presentation were picked because it was felt there would be general interest in the results and because of the high number of requests for these tasks. D. 4 Fortran Compiler (IBM Lelvel G) This compiler is by far the most heavily used program run by users of MTS. It is the IBM Fortran IV (G) compiler with a modified interface to allow it to run with the operating system (UMMPS) used at The University of Michigan. There were 41 requests (loads) for this compiler during the 22 minute data collection period. The mean elapsed loading time for those 41 samples was 5. 06 seconds with a standard deviation of 1. 75. Data obtained during completed executions of this compiler are presented in Table D. 2. In Figure D. 2 we show the distribution of lengths of CPU intervals between input-output requests for the compiler. In addition two theoretical distributions with the same mean as the empirical distribution are shown. It is clear that the hyperexponential distribution fits the data far better than the exponential distribution. Figure D. 3 gives the distribution of lengths of I/O operations during Fortran compilations and again we see that a hyperexponential distribution fits the data far better than an exponential distribution.

214 00 V) __,n C\J E 0* V) C C — C\j CD) 0 a I II a LU l 00 Cf) ct 00 *cJ oo -- O0 Q.) ~ ~ ~ ~ ~ ~ ~ ~ V (NJ Eco~~~~a LcU 00 O S S S 050 ~l li ~z ~

215 O%LC\ P\ 2 aI \ j x C\r vL > oo v C\l O a o o0 a > O0 COQ l CuX C:~~~~C ~~~E~~~~~~~~~ /o00- q3 "~ ~.,.o~~u Z 1 C~~~~~~3d~~ t ~~~~ k~~~

216 Table D. 2 Fortran Execution Data Item Samples Mean S. D. Elapsed Time Per Run (sec) 40 19. 1 27. 0 CPU Time Per Run 40 4.90 5. 37 I/O Time Per Run 40 8.13 16.3 Page Wait Time Per Run 40.434.758 Number I/O Requests Per Run 40 63.1 71.9 Number Page Waits Per Run 40 14.4 24. 1 Virtual Pages Per CPU Interval 2504 29 7 Real Pages Per CPU Interval 2504 24 7 Virtual Pages Per I/O Interval 2539 30 9 Real Pages Per I/O Interval 2539 25 8 Figures D. 4 and D. 5 give distributions on the CPU time used between page faults. Figure D. 5 is a breakdown of the data in Figure D. 4 by mean number of pages in core during the period of CPU use between page faults. Pertinent data for this figure are given in Table D. 3. Table D. 3 Data for Figure D. 5 Pages in Core Samples Mean S. D. 0- 9 29 7.54 13.6 10- 19 127 43.6 136 20 - 29 325 205 775 30 - 39 57 620 1179 40 -49 6 415 492

217 O * AS 00C Cf.m-4 II.-4 0 C m Icu,~~cd 1O Pb o~~~~~~~~~~~~~~~~~~~I~~ 1>}~~~ ~~~ AllllV O8

218 C'N C>% Z? ~ ( ~ ~ CE a) A~) C O OO E ~ o 154 A11I9 9VO0 d

219 D. 5 Fortran compiler (University of Waterloo) This is the so-called Watfor compiler developed at The University of Waterloo. Invoking this compiler causes the user's source program to be both compiled and executed. There are two versions available on MTS; the version reported here has the smaller storage requirements of the two and is most often used by students. There were 13 requests for this compiler during the data collection period. Mean elapsed loading time was 8. 17 seconds with a standard deviation of 3. 01. Execution time data are given in Table D.4 for this compiler and include both compile time and execution of the compiler output. Table D.4 Watfor Execution Data Item Samples Mean S. D. Elapsed Time Per Run (sec) 12 41.0 68.8 CPU Time Per Run 12 4.85 1.45 I/O Time Per Run 12 31.0 66.4 Page Wait Time Per Run 12.900 1.33 Number I/O Requests Per Run 12 92.3 36. 8 Number Page Waits Per Run 12 31. 6 44.7 Virtual Pages Per CPU Interval 1185 133 34 Real Pages Per CPU Interval 1185 26 13 Virtual Pages Per I/O Interval 1186 135 22 Real Pages Per I/O Interval 1186 26 10

220 Figures D. 6- D. 9 present empirical cumulative distributions for lengths of CPU intervals between I/O operations and between page faults and for lengths of I/O operations similar to Figures D. 2 - D. 5. D. 6 Assembler The assembler used by MTS is The University of Waterloo G-Assembler. The entire assembler is not loaded when initially called. Rather, modules are loaded selectively depending on options specified by the user. For example the user may specify the model 67 instruction set (default) or the instruction set for some other model of the 360. Default options were used for all 8 of the runs during the data collection period. Mean elapsed loading time for all the modules for each run was 9. 63 seconds. Table D. 5 gives pertinent execution time data for the assembler. Table D. 5 Assembler Execution Data Item Samples Mean S. D. Elapsed Time Per Run (sec) 8 47.4 46.9 CPU Time Per Run 8 7. 58 5. 50 I/O Time Per Run 8 34.9 50. 9 Page Wait Time Per Run 8.561.495 Number I/O Requests Per Run 8 103 64. 5 Number Page Waits Per Run 8 19.7 17.7 Virtual Pages Per CPU Interval 791 78 34 Real Pages Per CPU Interval 791 31 13 Virtual Pages Per I/O Interval 822 81 37 Real Pages Per I/O Interval 822 33 13

221.V) ~ 0~~0 q,z~.. 00 ~.o OQU 00 X O 1 A1I8V8OQ J ~> ~ (lIl l0EV8OUd

222 c/ CM C\: E c-,.. C,) C) co~ cn 0 Cc 0. O 4-4 1'} A1I1I8V8OId F- o,.P, 4l ~ ), A11118V808

223 -'00 C\z _.2. E~= a E E C: L X m s:: 00 C i 0..0 D 15} All] I 8V8OUid

224 c7~~c — ) 0 ~.,.00 r"~ ~'0 N ~~ V, Q)~~~~~~~~~~~~. ~)~ Ce')e) Ull OCi 00~~~~~~~~0 (\J 00 r.C15CVQ)c t= o in I —r -q -- * w ~~~~~~~~~~) ~ ~ ~ ~ ~ ~ ~ 0~.Q aV~~~~~) (NJOI~~~~~~~~~~~~~~~~ (: -0000 fz.. YB (NJ ~~~~~~~~~~~=-~ (I) I fl' _ L_~~~~~~~~~~~~~~L O ~D,O~CDC C~ ~ ~G ~~~~~ (j I -J k f~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Q 1~,kll18 V808d r 1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~1 c~~~~~~~~~~~~~~~~~~ o~~~~~~~~~ ~~~~~~~~*~~F'-4 Ir ~~ hll~~ 18 VgOtld~

225 Figures D. 10 - D. 13 show cumulative distributions for the same quantities shown in Figures D. 2 - D. 5. Table D. 6 gives pertinent data for Figure D. 13. Table D. 6 Data for Figure D. 13 Pages in Core Samples Mean S. D. 0- 9 27 5.38 6.88 10 - 19 21 11.4 14.3 20 - 29 20 209 565 30- 39 39 253 479 0 - 49 10 222 364 50 or more 18 201 276 D. 7 Line File Editor The editor is an interactive program which provides terminal users with a powerful facility for making desired changes in their line files. There were 10 requests for the editor during the data collection period and 7 complete executions. Because the editor is likely to be used for relatively long periods of time, three of the ten users who began execution during the data collection period were still in execution when the period ended. Mean elapsed loading time for the editor was 4.41 seconds with a standard deviation of 1. 32. Table D. 7 gives execution data for the editor. Note that the

226 00 C\C * - r-6 0 -,o oo — C a) 000;04 5.O 1Q, AlSl I BVOS 1 A1I1I9V8O~~~~~~~~~~~~~~~~~~~~~~Id~~l

227 Q)'o0 O0 P0 LI)Cd ~. 1 a) Q) o ~>. o a) 00,,,,,,. - 19~~~C 00 o v': O\JQ o..~~~~~~~~~~~~~~~~~~~~~~~~~r, _ %... _. t, \. |~~~~~~~~~~~~~~~Cl

228.fr oo E0 ~~~E CQ) Q-32O a) CDC~f a) CDo n a, -J.100 rv 5 15 I Ahi1I8V8O~Jd

229 0 L__~~~~~~~~~~~~~~~~~~~~~~~~~~~Cu J V)~~V 0' 0~~ 0 _.,.4 ~~~~~~~~~~~~~~~~~~~LU u.i-I~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~0 I~~~~~~~~~~~~ LP% u Q CD~ 1 All iVO~ Q$ 4.p-4 4-.0 I h S ~ ~ ~ ~ ~ n Q 0~ ~ ~ ~~~~~~~~~~~~~~~~~~C 151 AII 8Sa

230 items given "per run" may be somewhat biased toward shorter runs since data do not appear for the runs begun but not completed during the time data were being collected. Table D. 7 Editor Execution Data Item Samples Mean S. D. Elapsed Time Per Run (sec) 7 219 365 CPU Time Per Run 7 2. 07 2.75 I/O Time Per Run 7 215 357 Page Wait Time Per Run 7 2. 16 3. 22 Number I/O Requests Per Run 7 141 210 Number Page Waits Per Run 7 67.4 115 Virtual Pages Per CPU Interval 1214 13 6 Real Pages Per CPU Interval 1214 8 5 Virtual Pages Per I/O Interval 1219 14 4 Real Pages Per I/O Interval 1219 9 3 Figures D. 14 - D. 17 show cumulative distributions for the same quantities plotted in Figures D. 2 - D. 5. D. 8 User-generated Tasks The data in this section were obtained from all tasks run from files with names not preceded by an asterisk. These are in general object modules of programs written by users. There were 83 loads and 61 executions during the data collection period. In this case, in contrast to the line file editor, the disparity between

231 CM aT) 0 S) o E r._ i X1J LLJ a) 0 0,O ~ a) (r cl. 0:'', _,,:CI-I1880!

232 co CDi 0 CM 0 ~ 1C',,1 >C / d C ) 0~ c.4 0 rA0 C)'-4l

233 a) CD. i' o D0 0OQ s*Ev _ U S. S' 0 0 ~151 ~ A11I~V9~Ou~d~ 1~ 1 AlI'I I~i V lO1

234 ~*~~ ~ s X i U)0 | U o _ X )). r- CI.- rV)\ ~~~~~~~~~~~a) dS 00. 07 0t) 0 Z ct 4-4~C

235 the number of loads and number of executions is probably due in part to a number of unsuccessful loading attempts. The mean elapsed load time was 13.4 seconds with a standard deviation of 15. 1. Some of the long load times may have occurred because conversational users initially provided the loader with insufficient data and were thus prompted at the terminal to provide more. Execution data are given in Table D. 8 and distributions in Figures D.18 - D.21. Table D.9 gives parameters for Figures D. 21. The long I/O times shown in Table D. 8 and Figure D. 19 may be due to terminal interactions built in by the user but in many cases are probably caused by undebugged programs being interrupted during execution. If the user is at a terminal the program remains loaded after an interruption and he may display or alter the contents of chosen memory locations and restart the program. These operations appear in the execution data.

236 Table D. 8 User Program Execution Data Item Samples Mean S.D. Elapsed Time Per Run (sec) 61 102 138 CPU Time Per Run 61 6. 24 22. 1 I/O Time Per Run 61 88.6 114 Page Wait Time Per Run 61. 853 1. 09 Number I/O Requests Per Run 61 93. 0 136 Number Page Waits Per Run 61 29. 1 37. 5 Virtual Pages Per CPU Interval 9296 23 16 Real Pages Per CPU Interval 9296 12 9 Virtual Pages Per I/O Interval 9303 24 16 Real Pages Per I/O Interval 9303 13 9 Table D. 9 Parameters for Figure D. 21 Pages in Core Samples Mean (MS) S. D. i0 - 9 1952 132 2097 10- 19 1068 52.3 224 20- 29 186 297 773 30 - 39 143 253 656 j40 - 49 8 76.9 65.1 50 or More 1 3.70 0

237 CV r0 Q)1Q)' 0. c) ~I S I k ~ ~ ii q i J m, i A A, I I

238 C\ Co 0 ~E:~~~o - c ) 0. S - H 4-4 00 ~ b V) \> d _t *C)'Ip;C b 1>1 AI1I18V8VO?d

239 o CL c E o (I( 00 Co C Ln 4>~~~~~~~~~~~L ZE ~,r. S Q) tn z C O.V. -,Cd1 cr ~,-J,4 o.,? _ v v E: a 0 o0,,0 ~1' ~,1 1> -;,Alil!SV~!O~ld

240 000 Ca i\i C~~~~~~~~~~~~~~~~~~~J ~~ ~ ~ ~ ~ ~ C a) LL Z V) 0 4-z - oo., —( a) 00 t)a) i —4 A1 ~ ~ All-I~~~~~~lS V'20~lc I ~ ~~~ ~ ~~~~~~ I I 00~ ~ ~~~~~~~~~~~~~~I C~J U-.4~~~~ ~ ~ ~ 0 0 0 151 A1I1I8V8O~~~~~~~~~~d

Appendix E REACHABILITY OF STATE m+(L-1)N This appendix is devoted to showing that state m+(L-1)N is occulied with probability greater than zero after N or less transitions of the Uprocess regardless of the initial state when dk (1)>O for all k. The U-process is the Markov chain induced by using stochastic matrices A1 A U, U,... as transition probability matrices for successive state transitions where Al, A2,... are arbitrary L-stage policy sequences. These matrices are defined in section 2. 3 and one is shown in Figure 2.3. Reference to this figure will make the arguments in this appendix easier to follow. The underlying Markov chain of the MRDP is called the P-process in this appendix and is restricted to be such that no matter what the sequence of policies used to determine the probabilities of successive transitions, state m may be occupied after N-1 or less transitions regardless of the initial state. For some particular policy, a, a P-matrix, 1 =(Pij() is defined, and similarly for any L-stage policy sequence, A, a U-matrix U is defined. Transitions in the N state process defined by a sequence of P-matrices will be called P-transitions while those in the LN state process defined by a sequence of U-matrices will be called U-transitions. The remainder of this appendix is given in the form of a theorem and its proof. 241

242 Theorem E. 1 Hypothesize a MRDP with a state m which may be occupied with probability greater than zero after N-1 or less transitions regardless of the sequence of policies used. Hypothesize also that dkmm(l)>O for all k, and let arbitrary L-stage policy sequences; A1,A2,...; be used A1 A2 to define stochastic matrices U, U,.. in the manner discussed in Chapter 2. Then regardless of the A1, A2,... chosen and regardless of the initial state occupied, state m+ (L- 1)N is occupied with probability greater than zero after N or less transitions in the Markov process induced by using UA1'U 2... as transition probability matrices for successive transitions. Proof First it is argued that translition is possible from any one of states m, m+N,..., m+(L-1)N in the U-process to state m+(L-1)N. Inspection of the last column of submatrices; U1L,..., ULL; shows that element (m, m) is greater than zero in each. This is easily seen by noting that it is true in the first submatrix row and that in submatrix row I+1 we have a term DI(1) UIL where by hypothesis [ DI(1)] mm>. Thus if (U) mm>O, then (UI+1 mm>0 and since (U1L)mm 0 this part of the proof is complete. Therefore, if transition to any of states m, m+N,..., m+(L-1)N can be shown to be possible in N-1 or less transitions, we are done. At this point it is useful to define a generic state, i, called generic i in the U-process where i is an integer such that 1< i< N. This term will be used to refer to any one or more than one of the states i, i+N,o. o,

243 i+(L-1)N in the U-process. Thus if transition is possible (occurs with probability >0) to generic i in the U-process; then transition is possible to at least one of states i, i+N,..., i+(L-1)N. In view of what was proved in the preceding paragraph, it remains to show that transition occurs with probability greater than zero to generic m in N-1 or less transitions. Another useful notion in what follows is that of a transition tree. A transition tree is a tree structure which shows all transitions possible out of some initial state in a Markov chain, then all transitions possible out of some or all of those states and so on up to some maximum number of transitions. Thus at any possible node in the tree, the structure may terminate or all possible transitions out of this node may be shown. An example of such a tree is shown in Figure E. 1 in which the state represented by each node is given. The minimum path length in this tree is one because no transitions occur out of state two at level one. It is clear that if these are transitions in a P-process where the possible transitions at each level in the tree are determined by the policy chosen at that level; then if the minimum path length in the tree is at least N-1, state m must appear in at least one terminal node of the tree. The tree shown in Figure E. 2 has a more complex structure. Here it is assumed that the possible transitions out of any state at any level are all those which could occur under one or more of the possible alternatives in that state. Recall that transitions from state i under alternative k are possible to those states j for which Pik > 0. In Figure E. 2, transition from a given

244 r~ ~uI!~~~~~~~~~~~~~~~~ /~~ ~ ~ ~~~ ~! a),-( 0 H C\J~ ~~~~~~C

245 cu ) (~~~Lr\ U (C)tS V)t,.r,,I' ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~J ~C\J~0 L O *14 Cu~~~~~~ PcI Ln ~~~~~r cD~~~~~~~~~~~~~~~~~~~~~b

246 state at any level of the tree may be possible to all states reachable under more than a single alternative, k, and thus for the transitions and alternatives possible in the P-matrices it is obviously still true that if the minimum path length in this tree is N-1 or more, state m will appear in a terminal node. It will be shown in what follows that given a transition out of state i+xN in the U-process for some O<x< L-1 and for any 1< i <N, there is a corresponding tree cf the above form with root node i, with possible transitions determined by the possible P-transitions under one or more alternativesq and with minimum path length one which determines which generic states may be reached as a result of the U-transition. Thus if the tree shows j reachable from i then in the U-process one or m ore of states j, j+N,..., j+(L-1)N are reachable from i+xN. Then for the next U-transition, the possible initial states include one or more of j, j+N,..., j+(L-l)N, and since i and x were arbitrary in the discussion above there is a corresponding tree for each of these initial states. Therefore, the transition tree corresponding to two successive U-transitions consists of the transition tree for the first transition extended by other trees of the same form with root nodes which are the terminal nodes of the first tree. Thus in N-1 U-transitions, there is a corresponding transition tree with minimum path length N-I and with possible transitions to generic states determined by possible P-transitions under one or more alternatives which means that generic m is reachable in

247 N-1 transitions of the U-process regardless of the intitial state. As stated above this is sufficient to show that m+(L-1)N may be occupied after N transitions because it has already been shown that a direct transition from generic m to m+(L-1)N is possible. It remains to show that there exists a transition tree for any U-transition which shows possible transitions to generic U-states which correspond to states to which transitions can be made under specific alternatives in the P —matricesm. The transition tree is exhibited by using an inductive proof on the U-matrix. Such a transition tree is shown to exist for transitions determined by submatrix row one; i. e. transitions out of states i,... N; and then it is shown that if such a tree exists for submatrix rows 1,..., I, it must exist for submatrix row I+1. In submatrix row 1 we have submatrices Do(l),.I,Do (L), where a0(i) a0(i) a0(i) an element of one of these matrices is d.. () =ij 0 ()i a (i) a(i) ii Thus if p. > O, then d.. (Q) > O for at least one Q; 1 <f <L so ij 1J that if transition is possible from i to j under alternative ao(i), transition is possible from i to generic j when this U-matrix is the transition probability matrix. Note that tIe minimum and maximum path lengths in this transition tree are one and that the transitions possible out of state i are those determined by alternative a0(i). Now suppose that a transition tree of the required form exists for U-transitions determined by submatrix rows 1,..., I, i.e., out of stats 1,...,IN. It is now shown that such a tree exists for transitions out of

24 8 any state i+IN; i=1,..,,N. First the general submatrix in row I+1 may be written as Di(I) U1j+DI (I-1)U 2j+ +DI(1)UIJ J<I UI+1J = DI(L-J+I+l)+DI(I)U1J+DI(I- 1)U2J +... +DI(1)UI; J>I. Note that DI(K); 1<K<L; appears either as a term by itself in some submatrix of the I+ 1 st row, or it appears in each submatrix of the row post-multiplied by a submatrix In the same column and in some specific a1(i) aI(i) previous row. Thus if ij > 0 and ij (1)> 0 for some!>I, then it is clear that transition is possible from i +IN to generic j. Otherwise a1(i)'j (C) >0 for some f<I and so there is a transition at levelzero in the tree to j and then additional transitions from j determined by the subna trices which multipy DI(): U+l, 1,.., U l,L This row of submatrices specifies a transition tree for the initial state j and so this tree extends the branch which already goes from i to j. Thus for any initial state i+IN, there is a corresponding transition tree of minimum length one, and so in N-1 or less U-transitions, generic m may be occupied which shows that m+(L-1)N may be occupied after N transitions.

Appendix F CONVERGENCE OF GAIN RATE BOUNDS IN SCHEDULING MODEL In Chapter 2 conditions were given which are sufficient to insure that the upper and lower bounds on the gain or gain rate converge. These bounds provide an upper limit to the gain or gain rate of the optimal policy and a lower limit to the gain or gain rate of the current policy in the MRDP. Recall that it was pointed out that the conditions given for convergence were sufficient but not necessary, and thus that the optimization method may be useful even when these conditions are not met. As a matter of fact, the conditions given in Chapter 2 which assure convergence of the bounds do not hold in general for the model developed in Chapter 3. This offers no difficulty, however, since the bounds did in fact converge in all cases. It is nonetheless of interest to show one set of restrictions on the model which assure convergence, and this is now done. The first restriction is to remove from the model all alternatives which would allow no task to be loaded when in fact there is room in main memory for a task which is in the memory queue. Such alternatives may be removed from consideration without loss of generality because in the model the loading of the additional task must increase throughput and so the choice not to load is sub-optimal. Next restrict the number of task types to two and the size of tasks relative to the memory size to be such that at least one half of the fixed 249

250 number of tasks in the model may occupy main memory simultaneously. Also restrict the normalized load times for all tasks to be one. With this last restriction, all transitions require the same amount of time, and so the problem of maximizing the gain rate is the same as the problem of maximizing gain. Therefore it is only necessary to exhibit a state reachable from all other states in some fixed number of transitions regardless of the sequence of policies chosen. Call this state m. Furthermore define No as the maximum number of tasks which may occupy memory. The restriction above states that N _ N/2. Then the state m will be shown to be that state in which there are No type 1 tasks in 0 the memory queue and N-No type 2 tasks in the memory queue. Recall that between regeneration points any number (including zero) of the tasks in core may terminate and that this same number of tasks enter the memory queue. The type of task which enters the memory queue may, however, differ from the type of task which terminates. Then it is obvious that with N tasks in core, state m is reachable in 0 any finite number of transitions. That is, with probability greater than zero, no tasks terminate for n-1 transitions and then all No tasks terminate at transition n for n=1, 2,... (n<oo). Furthermore with N tasks in core, the number of type one tasks in the memory queue is less than or equal to N. Then after termination of all N tasks in core, 0 0 there will be No type one tasks in the memory queue with probability greater than zero.

251 Next it is noted that after No or less transitions there may be No tasks in main memory because a task is always loaded when there is room in main memory for one. At worst there may be no tasks in memory in the initial state and then No transitions fill the memory with probability greater than zero because it is possible for no tasks to terminate between regeneration points. From the preceding discussion it should now be clear that state m may be occupied after No+ 1 transitions regardless of the initial state and regardless of the sequence of policies used. This is sufficient to assure convergence of the bounds on the gain rate.

Appendix G SCHEDULING POLICIES In this appendix, scheduling policies are given which maximized throughput for the scheduling model parameters of Chapter 4. Each table in this appendix contains one scheduling policy and refers back to the result in Chapter 4 obtained by using this policy. Each table presents all states of the model and the memory scheduling and CPU scheduling decision to be used in each state. The state is specified by giving the number of type one and type two tasks in the memory queue, at the CPU, and in I/O. The scheduling decision is denoted by Al and A4 where Al denotes the memory scheduling decision. 0 means no load A1 = ( 1 means load a type 1 task 2 means load a type Z task A4 denotes the CPU scheduling decision as follows. 12 means type 1 tasks have preemptive priority at the CPU A4 = 21 means type 2 tasks have preemptive priority at the CPU Note that in some states there actually is no choice to be made; for example, only one decision is possible when memory is filled with a single type of task. 252

253 Table G. 1 Scheduling Policy For Figure 4. 5 (70 Pages, No Sharing) STATE DECISION MEM CPU I/O 12 1 2 1 2 AI A4 60 00 00 1 12 5 1 00 0 0 1 12 42 0 0 00 1 12 33 0 0 0 0 12 2 4 00 0 0 1 12 1 5 00 00 1 12 06 00 0 0 2 12 50 0 0 0 I 1 21 4 1 00 1 1 21 32 0 01 O 1 21 23 00 01 1 21 1 4 00 01 1 21 0 5 00 01 2 21 40 n C0 02 1 21 31 I 0 0 2 1 21 22 00 02 1 21 13 00 02 1 21 0) O 0o 02 2 21 30 00 0 3 0 21 2 1 0 0 0 3 0 21 1 2 0 0 0 3 0 21 0 3 00 0 3 0 21 50 0 0 10 1 12 41 00 10 1 12 ) 2 00 10 1 12 2 3 0 I10 2 12 1 4 00 I 0 2 12 05 00 10 2 12 4 0 00 I 1 0 12 31 00 I 1 2 12 22 0 0 1 2 12 13 C00 11 2 12 0 4 00 11 2 12 30 00 12 0 12 21 00 12 0 12 12 00 12 0 21 0 3 00 12 0 21 40 00 20 0 12 3 1 0 ( 2 0 O 12 22 00 20 0 12

254 Table G. 1 (continued) 1 3 0 0 20 0 12 04 0 0 20 0 12 50 I 0 0 1 21 41 0 I 0 0 1 21 3 2 01 0 0 1 21 23 0 1 00 21 1 4 0 1 0 0 1 21 0.5 0 1 0 0 2 21 40 0 I 0 I 1 21 3 1 C I 0 I I 21 22 0 1 0 I 1 21 13 0 1 01 1 21 04 0 1 0 1 2 21 30 0 1 02 0 21 2 1 0 1 02 0 21 1 2 0 1 02 0 21 0 3 0 1 0 2 0 21 4 0 01 1 0 0 12 31 0 1 1 0 2 12 22 01 1 0 2 12 13 0 1 1 0 2 12 04 01 I 2 12 30 01 11 0 12 21 01 11 0C 12 12 0 1 I 1 0 21 0 3 0 1 1 1 0 21 4 0 2 0 0 1 21 31 02 00 1 21 22 02 00 1 21 1 3 0 2 0 0 1 21 04 02 0 0 2 21 3 (J 2 0 I1 0 21 2 1 0 2 0 1 0 21 I 2 C 2 0 I 0 21 03 02 01 0 21 30 02 1 0 0 12 2 1 0 2 1 ( 0 12 I 2 02 1 0 0 21 03 02 10 0 21 30 03 0 0 0 21 2 1 03 00 0 21 1 2 0 3 0 0 0 21 03 0 3 00 0 21 5 ( 1 I 1 1 4 1 1 0 0 0~ I 12 32 1 0 00 1 12

255 Table G. 1 (continued) 2 3 I 0 00 2 12 14 1 0 0 0 2 12 O5 1 0 0 0 2 12 40 10 01 0 12 31 10 0 1 2 12 22 10 0 1 2 12 z3 I O 0 1 2 12 0 4 10 01 2 12.0 10 02 0 12 2 I I 0 02 0 12 1 2 1 0 O2 0 21 0 3 1 0 02 0 21 40 1 I0 I 0 0 12 2G I I 0 0 12 1 3. 1 0 I 0 0 12 3 1 0 1 0 0 12 04 1 1 0 0 12 i 0 1 0 0 0 12 31 I I (0 O 2 12 2 2 11 00 2 13 11 CO 2 12 0 4 1 1 0 0 2 12 3 0 I I 0 1 (C 12 21 1 01 0 12 12 1 01 O 21 0 3 151 0 1 0 21 3,0 n I O00 0 12 2 1 1 2 0 0 0 12 2 1 2 00 0 21 O 3 120 00 0 21 41 0 20 00 0 12 3 1 2 ( O O 0 12 ~2 2 2 00 O 0 12 1 3 2 O 00 0 12 04 2 0 00 0 12

256 Table G. 2 Scheduling Policy For Figure 4. 5 (70 Pages, Sharing) STATE DECISI ON MEM CPU I/O 1 2 1 2 1 2 AI A4 60 0 0 0 1 12 51 0 0 0 0 1 12 42 00 0 0 1 12 33 0 0 0 0 1 12 24 0 0 0 0 1 12 1 5 00 0 0 1 12 0 6 0 0 0 0 2 12 50 00 0 1 1 21 41 0 0 01 1 21 3 2 0 0 01 1 21 23 00 0 I 1 21 1 4 00 0C 1 21 0 5 00 0 0 1 2 21 4 0 0 0 0 2 1 21 3 1 0 0 02 1 21 22 00 02 1 21 13 00 02 2 21 0 4 00 02 2 21 3 0 0 0 0 3 0 21. 21 o0 03 0 21 1 2 00 0 3 0 21 03 0 0 0 3 0 21 5 0 0 1 0 1 12 41 00 1 0 1 12 3 2 0 0 1 0 1 12 23 0 0 1 0 1 12 14 0 0 1 0 1 12 0 5 ( 0 I 0 2 12 40 00 11 1 12 31 0 0 I 1 1 12 2 2 0 0 1 1 1 12 13 0 0 11 1 12 04 00 I 2 12 3 0 0 0 1 2 0 21 21 0 0 12 0 21 1 2 00 12 0 21 0 3 0 0 12 0 21 4 0 0 O- 20 1 12 31 00 20 2 12

257 Table G. 2 (continued) 2 2 0 0 2 0 2 12 13 0 0 20 2 12 0 4 O ( 2 0 2 12 30 0 0 21 0 21 2 1 0 0 21 0 21 12 0 0 2 1 0 21 0 3 0 0 21 0 21 30 0 0 3 0 0 12 2 1 00 3 0 0 12 1 2 0 0 30 0 12 0 3 0 3 0 0 1 2 50 0 1 0 0 1 21 41 0 1 0 0 1 21 3 2 0 000 1 21 2 3 01 00 1 21 1 4 0 1 00 1 21 05 01 00 2 21 40 01 01 1 21 31 01 01 1 21 2 2 0 1 01 1 21 13 0 1 01 2 21 04 01 01 2 21 3 0 01 0 2 0 21 21 01 02 0 21 1 2 0 1 02 0 21 03 0 1 02 0 21 4 0 01 1 0 1 12 31 01 1 0 1 12 22 01 1 0 1 12 1 3 01 10 1 12 0 4 0 1 10 2 12 30 0 1 1 0 21 21 0 1 11 0 21 12 0 1 11 0 21 03 0 1 11 0 21 30 01 20 0 21 2 1 0 1 2 0 0 21 12 20 0 21 0 3 0 1 20 0 21 4 0 02 00 1 21 31 02 00 1 21 2 2 02 00 1 21 1 3 02 00 2 21 0a 02 00 2 21 3O 02 01 0 21

258 Table G. 2 (continued) 21 02 0 1 0 21 12 02 01 0 21 03 02 01 0 21 30 02 10 0 21 21 02 10 0 21 12 02 10 0 21 0 3 02 1 0 0 21 3 0 03 00 0 21 2 1 03 00 0 21 12 03 00 0 21 03 03 00 0 21 5 0 1 0 00 1 12 4 1 1 0 00 1 12 32 1 0 00 1 12 2 3 1 0 00 1 12 14 1 0 00 1 12 0 5 1 0 00 2 12 4 0 I O 0 I 1 12. 3 1 1 0 0 1 1 12 22 1 0 01 1 12 13 1 0 01 1 12 04 1 0 0 1 2 12 30 10 02 0 21 2 1 1 0 02 0 21 12 1 0 02 0 21 0 3 I 0 02 21 40 1 0 1 0 1 12 3 1 0 1 0 2 12 22 10 1 0 2 12 13 1 0 1 0 2 12 0 4 1 0 1 C 2 12 3 0 1 0 11 0 21 21 I 0 1 1 0 21 12 1 0 11 0 21 03 1 0 1 1 0 21 3 0 1 0 20 0 12 2 1 1 0 20 0 12 12 1 0 20 0 12 0 3 1 0 20 0 12 40 1 0 0 1 12 31 1 1 0 0 1 12 22 1 1 0 0 1 12 13 11 0 0 1 12 04 11 00 2 12 30 11 01 0 21

259 Table G. 2 (continued) 2 1 1 1 0 1 0 21 12 11 01 0 21 0 3 11 0 01 21 30 11 1 0 0 21 21 11 1 0 0 21 12 11 1 0 0 21 0 3 11 1 0 0 21 3 0 12 0 0 0 21 2 1 1 2 0 0 0 21 12 1 2 00 0 21 0 3 1 2 0 0 0 21 4 0 20 0 0 1 12 31 20 0 0 2 12 2 2 20 00 2 12 1 3 20 00 2 12 04 2 0 00 2 12 30 20 01 0 21 2 1 20 0 1 0 21 1 2 20 0 1 0 21 03 20 01 0 21 3 0 2 0 10 0 12 21 20 10 0 12 1 2 20 1 0 0 12 0 3 2 0 1 O 12 3 2 1 00 0 21 21 21 00 0 21 12 21 00 0 21 0 3 2 1 00 0 21 3 0 3 0 00 0 12 21 3 0 0 0 0 12 1 2 3 0 00 0 12 0 3 3 0 00 0 12

260 Table G. 3 Scheduling Policy For Figure 4. 5 (90 Pages, No Sharing) and Figure 4. 6 (2) STATE DECISION MEM CPU I/O 1 2 1 2 1 2 Al A4 60 00 00 1 12 51 00 00 1 12 4 2 0 0 00 1 12 33 00 0 0 1 12 24 0 0 0 0 1 12 1 5 00 00 1 12 0 6 00 0 0 2 12 5 o ()0 0 I 1 21 41 00 0 I 1 21 32 0 0 0 1 1 21 23 0 0 1 1 21 14 00 0 I 1 21 0 5 0 0 0 1 2 21 4 0 0 0 02 1 21 31 0 0 02 I 2i 22 00 02 1 21 1 3 00 02 1 21 04 00 02 2 21 30 00 0 0 21 21 00 05 221 12 00 03 2 21 03 00 03 2 21 20 00 0 4 0 21 11 00 0 4 C 21 02 00 0 4 0 21 5 0 0 1I 1 12 4 1 0 10 0 1 12 32 00 1 0 1 12 23 0 0 1 0 1 12 1 4 0 0 1 0 1 12 0 5 0 0 I 0 2 12 4 0 0 0 11 1 12 3 1 0 0 11 1 12 22 0 0 11 1 12 13 0 0 11 1 12 04 00 1 2 12 30 0 0O 12 0 21 21 00 12 0 21 12 00 12 0 21

261 Table G. 3 (continued) 0 3 O 0 1 2 0 12 40 0 0 20 1 12 3 1 0 0 20 1 12 22 0 0 20 1 12 13 0 0 20 2 12 0 4 0 ( 20 2 12 30 0 0 21 0 21 21 0 0 21 0 21 1 2 00 2 1 0 21 03 0 0 21 0 21 30 00 30 0 12 21 0 0 3 0 0 12 1 2 0 ( 3 0 0 12 0 3 00 30 0 12 5 0 01 0 0 1 21 41 0 1 0 0 1 21 32 0 1 0 0 1 21 2 3 01 0 0 1 21 I 4 0 I 0 0 1 21 0 5 01 0 0 2 21 4 0 0 I 0 I 1 21 31 01 0 I 1 21 2 0 1 01 1 21 13 01 01 1 21 04 01 0 1 2 21 30 01 02 0 21 21 0 1 02 2 21 12 0 1 02 2 21 0 3 0 1 02 2 21 20 0 1 0 3 0 21 1 1 0 I 0 3 0 21 02 0 1 0 3 0 21 40 01 I 1 12 31 01 10 1 12 22 01 1 0 1 12 1 3 01 1 0 1 12 0 4 01 1 0 2 12 3C 0 I I I 0 21 2 1 0 1 11 0 21 12 0 1 1 0 21 0 3 0 1 1 0 12 3 0 O 1 20 0 21 2 1 0 1 20 0 21 12 01 20 0 21 03 0 20 0 21 40 02 00 1 21

262 Table G. 3 (continued) 31 02 0 0 1 21 22 02 0 0 1 21 13 02 0 0 1 21 04 02 0 0 2 21 3 0 02 0 1 0 21 2 1 02 0 1 2 21 12 02 0 1 2 21 03 02 0 1 2 21 20 02 02 0 21 1 1 02 02 0 21 02 02 02 0 21 3 0 0' 2 1 0 0 21 21 02 10 0 21 1 2 02 10 0 21 03 02 10 0 12 30 0 3 00 0 21 21 03 0 0 2 21 1 2 03 0 0 2 21 03 03 0 0 2 21 20 3 0 1 0 21 I 1 03 0 1 0 21 02 03 0 1 0 21 2 0 04 00 0 21 11 I 04 00 0 21 02 04 00 0 21 50 1 0 00 1 12 A 10 00 1 12 32 1 0 00 1 12 23 10 00 1 12 14 1 0 00 1 12 05 1 0 00 2 12 40 1 0 0 I 1 12 3 1 1 0 0 1 1 12 22 1 0 01 1 12 1 3 10 01 1 12 04 1 0 0 1 2 12 3 0 1 0 02 0 21 21 1 0 02 0 21 1 2 1 0 2 0 21 03 1 0 02 0 12 4 I 0 I I1 12 3 1 1 0 I 0 1 12 22 10 1 0 1 12 I13 10 1 0 2 12 04 10 10 2 12 30 I I I 0 21

263 Table G. 3 (continued) 21 1 0 1 1 0 21 12 I 0 I t C 21 0 3 1 ) 1 1 0 21 3 0 1 0 20 0 12 21 1 0 20 0 12 1 2 1 C 20 0 12 0 3 1 20 0 12 40 11 00 1 12 3 1 1 01 0 1 12 22 11 0 0 1 12 1 3 11 00 1 12 0 4 1 I 0 0 2 12 30 11 0 I 0 21 21 11 0 1 0 21 1 2 11 0 1 0 21 03 11 0 I 0 12 30 1 1 1 0 0 21 2 1 11 1 0 0 21 12 11 1 0 0 21 03 1 1 1 0 0 21 30 12 00 0 21 2 1 1 2 00 0 21 12 12 00 0 21 0 3 12 00 0 12 40 20 00 1 12 3 1 2 0 00 12 22 2C 00 1 12 13 20 00 2 12 04 20 00 2 12 3 0 2 0 01 0 21 21 20 01 0 21 1 2 2 0 0 1 0 21 03 20 01 0 21 30 20 1 0 0 12 2 1 20 1 0 0 12 12 20 1 0 0 12 03 20 10 0 12 3 0 21 00 0 21 21 21 00 0 21 12 21 00 0 21 03 21 00 0 21 30 3 0 0 0 12 21 30 00 0 12 12 30 00 0 12 O03 30 00 0 12

264 Table G. 4 Scheduling Policy For Figure 4. 5 (90 Pages, Sharing) and Figure 4. 6 (4) STATE DECISION MEM CPU I/O 1 2 1 2 1 2 Al A4 60 0)0 00 1 12 51 00 00 1 12 42 00 00 1 12 33 00 0 0 1 12 2 4 00 0 O0 1 12 1 5 00 0 0 2 12 0 6 00 0 2 12 50 00 01 1 21 41 0 0 01 1 21 3 2 0 0 0 1 1. 21 2 3 00 01 1 21 14 00 0 1 2 21 0 5 00 01 2 21 4 0 0- 0 0 2 1 21 31 00 0 2 1 2 22 00 02 1 21 1 3 00 02 2 21 04 00 02 2 21 3 0 0 0 03 0 21 2 1 00 0 22 21 1 2 0 0 ( 3 2 21 03 00 053 2 21 20 00 04 0 21 1 1. 0 0' O0 21 C) 2 00 0 4 0 21 50, 00 I 1 12 4 1 C 0 I1 ( 1 12 32 00 I10 1 12 2 3 0 1 0 1 12 14 0 10 1 12 05 00 1 I0 2 12 4 00 o 11 1 12 3 1 00 I I 112 22 00 I 1 1 12 13 00 1 1 1 12 04 00 11 2 12 30 00 12 1 21 2 I 12 1 21 12 00 12 1 21

265 Table G. 4 (continued) 0 3 00 1 2 0 12 40 0 0 20 1 12 3 I -O 0 2 C 1 12 22 0 0 20 2 12 13 0 0 20 2 12 0 4 0 0 2 0 2 12 30 0 0 21 1 21 2 1 0 0 2 1 2 21 12 0 0 21 2 21 03 00 21 2 21 20 0 0 22 0 21 I 1 0 0 22 0 21 02 0 0 22 0 21 30 0 30 1 12 21 0 30 2 13 12 00 3 0 2 12 0 3 0 ( 3 0 2 12 20 00 31 0 21 1 I 0 0 3 1 0 21 0 2 0 ( 3 1 0 21 2 C 00 40 0 12 11 00 40 0 12 02 0 0! 4 0 12 50 01 0 0 1 21 a 01 00 1 21 3 2 01 00 1 21 2 3 0 1 0 1 21 14 0 1 0 0 2 21 5 I 01 2 2 1 4 0 0 1 01 1 21 31 0 1 01 1 21 22 0 1 01 1 21 1 3 0 1 0 1 2 21 04 01 0 1 2 21 3 0 0 1 02 0 21 21 01 0 2 2 21 1 2 0 1 02 2 21 3 0 1 02 2 21 20 0 1 03 0 21 I I 0 I 03 21 02 0 1 03 0 21 4 0 0 1 10 1 12 31 01 10 1 12 22 01 10 1 12 1 3 O I O 1 12

266 Table G. 4 (continued) 04 0 1 1 0 2 12 3 0 0 1 11 1 21 21 01 1 1 1 21 12 01 11 1 21 03 0 I I 1 0 12 3 0 01 20 1 21 21 0 1 20 2 21 1 2 0 1 20 2 21 03 0 1 20 2 21 20 0 1 21 0 21 1 I 0 1 2 1 0 21 02 C 1 2 1 0 21 20 0 1 3 0 0 21 1. 0 1 3 0 0 21 0 2 0 1 3. 0 21 40 02 00 1 21 31 02 00 1 21 2 2 02 00 1 21 1 3 0 2 00 2 21 04 02 00 2 21 30 02 01 0 21 21 0 2 0 1 2 21 1 2- 0 2 0 1 2 21 0 3 02 0 1 2 21 20 02 02 0 21 1 1 02 02 0 21 02 02 02 0 21 3 0 02 1 0 1 21 21 02 10 1 21 1 2 02 1 0 1 21 03 02 1 0 0 12 20 02 2 0 0 21 I 1 02 20 0 21 0 2 0 2 2 0 0 21 3 0 0 3 0 0 0 21 2 1 03 0 0 2 21 12 0 3 0 0 2 21 03 0 3 0 0C) 2 21 20 03 0 1 0 21 1 1 0 3 0 1 0 21 02 03 0 1 0 21 20 04 0 0 0 21 I 1 0 4 0 0 0 21 02 04 00 0 21 50 1 0 0 0 1 12

267 Table G. 4 (continued) 4 I 1 0 00 1 12 32 10 00 I 12 2 3 1 0 0 0 I 12 1 4 1 0 0 0 1 12 05 1 0 0 0 2 12 40 1 0 0 1 I 12 3 1 1 0 01 I 12 22 1 0 0 1 1 12 1 3 1 0 0 1 1 12 0 4 10 O 2 12 3 0 I 0 0 2 1 21 2 1 1 0 2 1 21 12 10 0 2 1 21 03 1 0 2 0 12 4 0 1 0 1 0 1 12 31 10 10 1 12 2 2 1 0 10 2 12 1 3 1 0 1 0 2 12 0 4 1 0 1 0 2 12 3 0 1 0 11 1 21 2 1 1 0 1 1 2 21 1 2 1 0 I 1 2 21 0 3 1 0 1 2 21 20 1 0 12 0 21 1 1 10 12 0 21 02 1 0 12 0 21 3 0 1 0 20 I 12 21 1 0 20 2 12 12 1 0 20 2 12 0 3 1 0 20 2 12 2 0 10 21 0 21 I I 1 0 21 0 21 02 10 21 0 2i 2 0 10 30 0 12 I I I 0 3 0 0 12 02 10 3 0 0 12 4 0 1 1 0 0 1 12 31 11 00 1 12 22 11 1 0 I 112 13 11 0 0 1 12 04 1 I 0 0 2 12 3O I1 0 1 I 21 21 11 01 1 21 12 11 0 1 1 21 Q I I 01 1.2

268 Table G. 4 (continued) 30 11 1 0 1 21 21 11 1 0 2 21 12 11 1 0 2 21 03 11 10 2 21 20 11 11 0 21 I I I1 I I I 0 21 02 11 11 0 21 2 11 20 0 21 1 1 11 20 0 21 02 11 2 0 0 21 3 0 12 00 1 21 2 1 1 2 00 1 21 1 2 12 0 0 1 21 0 3 1 2 0 0 0 12 2 0 12 1 0 0 21 11 12 1 0 0 21 02 12 1 0 0 21 4 0 20 0 0 1 12 3 1 20 0 O 1 12 22 20 00 2 12 13 20 00 2 12 0 4 20 00 2 12 3 0 2 0 0 I 1 21 21 20 0 1 2 21 1 2 2 0 0 1 2 21 0 3 20 0 1 2 21 20 20 02 0 21 I 1 20 02 0 21 02 20 02 0 21 3 0 20 1 0 1 12 2 1 20 1 0 2 12 1 2 20 1 0 2 12 0 3 20 1 0 2 12 20 20 1 1 0 21 1 1 20 11 0 21 02 20 11 0 21 20 20 2 0 0 12 1 1 20 2 0 0 12 02 20 20 0 12 3 0 21 0 0 1 21 21 21 0 0 2 21 1 2 2 1 0 0 2 21 03 21 00 2 21 2 O 2 1 0 I 0 21 1 2 1 0 1 0 21

269 Table G. 4 (continued) 0 2 2 1 0 1 0 21 2 0 2 1 1 0 0 21 1 1 2 1 1I0 0 21 02 21 1 0 0 21 20 22 0 0 0 21 11 22 0 0 0 21 02 22 0 0 0 21 3 30 0 0 1 12' 2 1 30 0 0 2 12 1 2 3 0 0 0 2 12 03 3 0 0 0 2 12 20 3 0 01 0 21 11 30 0 I 0 21 02 3 0 0 I 0 21 2 0 30 1 0 0 12 1 1 3 0 1 0 0 12 02 30 1I 0 12 20 3 1 00 0 21 11 3 1 0 0 0 21 02 3 1 00 0 21 20 4 0 00 0 12 11 40 00 0 12 02 40( 00 0 12

270 Table G. 5 Scheduling Policy For Figure 4. 6 (6) STATE DECISION MEM CPIU I/O 12 1 2 1 2 Al A4 60 0 0 0 0 1 12 51 0 0 0 0 1 12 42 0 0 0 0 1 12 33 00 0 0 1 12 2 4 0 0 0 0 1 12 15 0 0 0 0 1 12 06 0 0 0 0 2 12 50 00 0 1 1 21 4 0 0 01 1 21 32 0 0 01 1 21 23 00 0 I 1 21 14 0 0 01 1 21 05 0 -0 0 1 2 21 40 0 0 0 2 1 21 31 0 0 02 1 21 22 0 0 02 1 21 13 00 0 2 1 21 04 00 02 2 21 3 0 0 0 0 3 0 21 21 00 03 2 21 12 0 0 03 2 21 03 0 0 0 3 2 21 2 0 0 0 0 4 0 21 I I 0 0 0 4 0 21 02 0 0 04 0 21 50 0 0 1 0 1 12 4 1 0 0 I0 1 12 32 0 0 1 0 1 12 23 0 0 1 0 1 12 14 0 0 1 0 1 12 05 0 0 1 0 2 12 4 0 0 0 1 1 1 12 3 1 00 I 1 1 12 22 0 0 11 1 12 13 00 I 1 1 12 04 0 0 11 2 12 30 0 0O 12 0 12 21 00 12 0 12 12 00 12 0 12 03 00 12 0 12

271 Table G. 5 (continued) 40 0 0 20 1 12 3 1 0 0 20 1 12 22 0 0 20 1 12 13 0 0 20 1 12 04 0 0 2 0 2 12 3 0 0 0 21 0 21 21 0 0 21 0 21 1 2 0 0 2 1 0 12 03 0 0 21 0 12 3 0 0 0 30 0 12 2 1 00 30 0 0 12 12 0 0 30 0 12 03 0 0 3 0 O 12 5 0 01 00 1 21 4 1 0 1 0 0 1 21 3 2 0 1 0 0 1 21 23 0 1 0 0 1 21 1 4 0 1 0 0 1 21 0 5 0 1 0 0 2 21 4 0 0 1 0 1 1 21 3 1 0 1 01 1 21 22 0 1 0 1 1 21 1 3 0 1 01 1 21 04 0 1 0 1 2 21 3 00 1 02 0 21 2 1 0 1 02 2 21 12 0 1 02 2 21 03 0 1 0 2 2 21 20 0 1 03 0 21 I 1 0 I 03 0 21 02 0 1 0 3 0 2'1 40 0 1 1 0 1 12 3 1 0 1 1 0 1 12 22 01 1 0 1 12 13 0 1 1 0 1 12 04 0 1 1 0 2 12 3 0 0 1 1 1 0 12 2 1 01 11 0 12 1 2 01 11 0 12 0 3 01 11 0 12'3 0 0 1 2 0 0 21 21 0 1 20 0 21 1 2 0 1 20 0 12 03 0 1 20 0 12 40 02 00 1 21 31 n 0 0 21

272 Table G. 5 (continued) 22 02 0 0 1 21 1 3 02 0 0 1 21 0 4 0 2 0 0 2 21 3 0 02 0 1 0 21 21 02 0 1 2 21 12 02 0 1 2 21 03 02 0 1 2 21 20 02 02 0 21 1 1 02 02 0 21 02 02 02 0 21 30 02 1 0 0 12 2 1 0 2 1 0 0 12 12 02 1 0 0 12 0 3 02 1 0 0 12 30 03 0 0 0 21 21 03 0 0 2 21 12 0 3 0 0 2 21 0 3 0 3 0 0 2 21 20 03 0 1 0 21 11 0 3 0 1 0 21 02 03 0 1 0 21 2 0 04 0 0 0 21 1I 0 4 00 0 21 02 04 0 0 0 21 50 1 0 00 1 12 4 1 1 0 0 0 1 12 32 1 0 0 0 1 12 2 3 10 00 1 12 1 4 1 0 0 1 12 05 10 00 2 12 4 0 10 01 1 12 31 1 0 01 1 12 2.2 1 0 01 1 12 1 3 10 0 1 12 0 4 1 O O 1 2 12 3 0 1 0 02 0 12 21 1 0 0 2 0 12 12 1 0 02 0 12 03 1 0 2 0 12 4 10 1 0 1 12 3 I I I O 1 12 22 10 1 0 1 12:1 I 0 I O 1 12 04 10 1 0 2 12 30 10 11 0 21 21 10 11 0 21

273 Table G. 5 (continued) 12 1 0 1 1 0 12 03 I 0 1 1 0 12 30 1 0 20 0 12 2 1 1 0 20 0 12 12 1 0 2 0 0 12 03 1 0 20 0 12 4 0 11 0 0 1 12 3 1 1 1 0 0 1 12 22 1 1 0 0 1 12 1 3 11 0 0 1 12 04 11 0 0 2 12 3 0 11 0 1 0 12 2 1 1 1 0 1 0 12 12 1 0 1 0 12 03 1 1 0 1 0 12 3 0 11 1 0 0 21 21 11 1 0 0 21 1 2 11 1 0 0 12 03 1 1 1 0 0 12 3 0 1 2 00 0 12 2 12 00 0 12 12 1 2 00 0 12 03 1 2 00 0 12 40 20 00 1 12 31 20 00 1 12 22 20 00 1 12 13 20 00 1 12 04 20 00 2 12 3 0 20 01 0 21 2 1 20 0 1 0 21 1 2 20 0 1 0 12 0 3 20 01 0 12 3 0 20 1 0 0 12 21 20 10 0 12 12 20 1 0 0 12 0 3 2 0 10 0 12 3 0 2 1 00 0 21 21 2 1 00 0 21 1 2 2 1 00 0 21 0 3 2 1 00 0 12 3 O 30 0 0 0 12 2 1 30 00 0 12 12 3 0 00 0 12 0 3 30 00 0 12

274 Table G. 6 Scheduling Policy For Figure 4. 10 (1, 40 Pages) STATE DECISION MEM CPU I/O 1 2 1 2 1 2 Al A4 50 0 0 0 1 12 4 1 0 O O 0 1 12 32 00 0 0 1 12 23 0 0 0) 1 12 1 4 0 0 0 C 1 12 0 5 00 0O 0 2 12 4 O O O 01 o o 21 31 00 0 I 0 21 2 2 0 0 Cn 0 21 13 O n 0 1 2 21 C0 0 0 0 I 2 21 3O 0o 0 0 2 0 21 2 1 00 0 2 0 21 12 00 0 2 0 21 03 00 02 0 21 40 00 1 0 0 12 31 O 0 I C1 0 12 22 00 1 0 0 12 13 00 1 0 0 12 0 4 00 1 0 0 12 4 0 () - 0 0 0 21 3 1 O 0 0 2 21 22 0 1 0 2 21 1 3 0 I 0 0 2 21 0 4 0 1 0 O 2 21 30 0 1 0 I 0 21 21 01 0 1 0 21 1 2 0 1 0 1 0 21 03 0 1 0 I 0 21 30 02 00 0 21 2 I 0 2 0 O 0 21 12 02 0 0 0 21 03 02 00 0 21 4 0 1 0 0 0 12 31 10 0 0 0 12 22 I 0 0 0 0 12 1 3 I 0 O0 0 12 0 4 1 O 00 0 12

275 Table G. 7 Scheduling Policy For Figure 4. 10 (1, 50 Pages) STATE DECISI ONMEM CPU I/O 1 2 1 2 1 2 Al A4 50 00 00 1 12 41 00 00 1 12 32 00 00 2 12 2 3 0 0 O0 2 12 1 4 00 0 0 2 12 0 5 0 0 0 0 2 12 40 00 01 0 21'3 1 0 0 I 2 21 22 0 0 O 1 2 21 1 3 00 0 1 2 21 C0 0 0 0 1 2 21 3 0 0 0 o2 0 21 21 00 0 C2 0 21 1 2 C0 0 2 0 21 0 3 0 0 0 2 0 21 4 0( C 0 10 1 12 3 1 00 10 1 12 22 00 I 0 1 12 1 3 0 1 0 0 12 04 00 1 0 0 12 3 0 0 0 2 0 0 12 21 C 0 20 0 12 12 00 20 0 12 c 3 C 0 2 0 0 12 4 0 1 0 0 0 21 31 01 01O 0 221 22 0 1 0 0 2 21 1 3 0 1 0 0 2 21 0 4 0 1 0 0 2 21 3 0 0 1 0 1 0 21 1 0 1 O 0I 0 21 12 01 0 1 0 21 03 01 01 0 21 3 0 02 00 0 21 2 1 0 2 O t0 21 1 2 0 2 00 0 21 03 02 00 0 21

276 Table G. 7 (continued) 4 0 10 0 0 I 1 12 31 10 0 1 10 22 I 0 00 1 12 13 10 0C 1 12 0 4 10 0 o 0 12 30 1 ()0 0 12 21 10 10 0 12 12 I1 1I 0 12 03 1 0 10 0 12 30 20 00 0 12 2 1 20 00 0 12 12 20 00 0 12 03 20 00 0 12

277 Table G. 8 Scheduling Policy For Figure 4. 10 (3, 50 Pages) STATE DECISION MEM CPU I/O 1 2 1 2 1 2 A1 A4 50 0 0 00 1 12 5~ I 0 C O. 0 I 12 4 00 00c 1 12 2 3 O C00 C) 1 12 fC 7 C0 1 12 I z C 0 C1' 0 12 05 C0 0 0 o 2 12 4', (C 0 0 1 C) 21 1 00 0 I 021,() 0 () 0 1 2 21. I 0 C 0 2 C e21 t (' C; C) 1 0( 1,3 I 0 0 1 0 0, 12 02' C 0 1 0 C 12 i ('. C0 1 0 0 1 2 C I2 C0 1 I 0 2 12 1 3 C I CO O 21 0 1I 0 C) 2 1 (1 O 1 C. 0 2 ~1 3, 0 ( 1 1 0 21 2 1 0 0 1 0 1 0 21 1;, I ( I C 1 C0 21 1, C- 21 4. v (., 1 0 I ( 2%1., "C) OC':' (2 CC C; 21 1 (2' 2 00 O 21 C 3 C' 2 () o C) 21 a CI 1 C C 0 (l0 12 3 I 1 C C 12 1 0 O 12 1 3 1 Cr 0 0 C. 12 C 4 1 CO 00 C 1"2

278 Table G. 9 Scheduling Policy For Figure 4. 10 (3, 55 Pages) STATE DECISI ON MEM CPU I/O 1 2 1 2 1 2 AI A4 5 0 C00 00 1 12 4 1 0 0 () 0 1 12 3 2 O O O2 12 2 3 o CO, 2 12 14 C00 0 2 12 0 5 0 0 0. 2 12 40 C O 01 1 21 3 1 00 0 1 1 21 22 00 01 1 21 1 3 0 0 O 1 2 21 0( 4 C0 0 1 2 21 3 0 0 0 0 2 0 21 21 00 02 0 21 1 2 O 0, 02 0 21 3 0 () 02 0 21 4 C) C 0 1 0 0 12 3 I 0O C I 1 0 2 1 t2 2 0 0 IC0 2 12 I 3 0C) I - 2 12 C 4 C 0 I 0 2 12 30 0 O, 0 I I 0 12 2 1 0 0 1 1 I 0 12 12 00 1 1 0 12 0 3 0 n I I C0 12 0 0 1 0 0 1 21 22 0 1 00 1 21 1 3 0 1 C) ( 2 21 0 4 00 1 22 1 30 0 1 01 0 21 21 0 1 01 0 21 1 2 O-I I 0 21 3 0 I 0 I 0 21 3 0 O I 1 (0 0 12 21 01 1 0 12 12 0 1 0 0 12

279 Table G. 9 (continued) 0 3 0 I I 0 C) 12 0 ( 0 2 0 0 0 21 2 1 0 2 0 ) 0 21 i t O C C O C- 2 1: 3 0 2 0 0 0 21 4 (' 1 0 0 (1 0 12 "2 1 1 (1 () () 2 12,. - ( C) 0Cl 2 12 1 3 1 (' O (0 2 12 0, z' I C O 0 1 31 (C J 1 C 12 21 1I 0 0 I 0 12 I 2; 1 C; 0 10 12 (C 3 1 C0 0 1 0 12 7. (0 1 1 0 0 0 12':2 1 1 1 0 0 C 12 1 2 1 1I 0G 0 12 3 1I I 0 0 0 12

280 Table G. 10 Scheduling Policy For Figure 4. 11 (60 Pages, No Sharing) STATE DECISI ON MEM CPU I/0 1 2 1 2 1 2 Al A4 50 0 0 0 I 112 41 00 00 1 12 32 00 00 1 12 23 C00 O 0 1 12 4I h 0 0 0 0 1 12 05 0 0 0 0 2 12 40 0 0 01 0 21 3I 0 0 0 1 2 21 22 00 0 1 2 21 13 0 0 0 I 2 21 04 00 01 21 3 00 0 2 0 21 2 1 0 0 0 C 21 12 0 0 02 0 21 03 00 0n 0 2 1 40 00 I 0 0 12 3 I 0 0 0I O 12 22 00 1 0 0 12 3 00 10 0 12 40 O I 00 0 21 ~. 0 0 I 0 0 2 21 31 0 1 0 0 2 21 22 C) 1 0 0 2 21 13 01 00 2 1 I 4 0 I O C 2 21 04. 0 1 2 21 3 0 0 1 O I 0 21 2 1 0 1 0 I 0 21 l 2 l0 1 0 l 0 21 0 3 ) 0 I 0 21 3 O2 0 0 0 21 2 1 0 2 0 0 0 21 12 02 O0 C0 21 0 3 0 2 0 ( 0 21 40 C I 00 0 12 3 1 10 0 0 0 12 22 10 00 0 12 13 I0 0 0 0 12 4 10 0 0 0 12

281 Table G. 11 Scheduling Policy For Figure 4. 11 (60 Pages, Sharing) STATE DECT SI ON MEM CPU I/O 1 2 1 2 1 2 Al A4 5 0 0 () O O I 12 32 0 0 00 1 12 25 C D0 O 0 2 12 1 0 (0 n 0 0 2 12 0 5 0 0 0 0 2 12 14 0 0 0 0 1 0 21 3 I 00 0n 1 2 21 2. 00 0 I 1 2 2.1 13 C0 0 01 221 ) I 0/i CC00 01 2 21 30 0 0 02 021 21 00 02 221 12 0 0 02 2 21 03 00 2 21 2 0! r () O 3 0 21 1 0 0 0 3 0 21 C 2 0 0 3 0 21 L 0 0 0 ( 0 1 12 31 0 0 10 1 1I 1 3 0 (') I 0 1 1 2 0 4 OC 1 0 12 3 C0 C0' 2 C) I 12 S2 () 2 0 1 12 1 2 0O (0 2 0 1 12 0 3 0 C 2 O O 12 2 0 CO 0 3 0 0 12 I I 0 0 0 0 I 12 )0 2 0 0 3 0 0 12 3l O 1 00 0 21 1 01 00 221 2 2 0 I 0 2 21 1 3 0! 1 0 0 21 C1 4 C 1 0 0'2 21 3 0 0 1 0 1 0 21 C: I 0 I 1 C 2 21 12 2. I O 1 2 21 C 0 3 I 01 2 21

282 Table G. 11 (continued) 2 O C, 1 C, L. () 2 1 S C C O C! ei el c 2 0 0 1 0 2 0 21 I I 0 2 0 1 0 21 0'2 0 2 0 1 21 2 1 -: 3 n c c,00 c021 02 02 00 2 21 2 0 0 3 0 0 0 1 1 0 2 0 1 1 1 0 |0 0|1 C 2| 1 1 1 I 3/. C 0 21 02 03 00 0 I 1 40 1 O 00 0 1 1 2 0 ) 00 1 2 2 1 1 ( (1 1- 1 a0 I C 0 1 0 12 2C) 1 0 2 0 0 12 0 2 1 0 20 0 1 2 3 C) 0 00 1 12 2 1 2 0 C) 0 1 12 12 2 0 0 1 12 0 3 C0 00 0 12 2 0 n I0 0 12 11 I 00 12 0? 20 10 0 12 20 30 C0O 0 12 11 30 o 012 20 00 0 n 12

BIBLIOGRAPHY [1] M. T. Alexander, "Time Sharing Supervisor Programs", Computing Center, The University of Michigan, May 1969. [2] B. Arden, B. Galler, T. O'Brien, F. Westervelt, "Program and Addressing Structure in a Time -Sharing Environment", Journal of the ACM, 13, 1, January 1966, [3] B. Arden, "Time-Sharing Systems: A Review", Proc. of IEEE International Convy, lb, Part 10, March 1967, pp. 23-35. [4] L. A. Belady, "A Study of Replacement Algorithms for a Virtual-Storage Computer", IBM Systems Journal, 5,2, 1966, pp. 78-101. [5] R. Bellman, Dynamic Programming, Princeton University Press, Princeton, N. J., 19o7. [61 R. Bellman, "A Markovian Decision Process", Je of Mathematics andMechanics, 6, 5, (1957) pp. 679-684. [71 R. S. Burington and C. C. Torrance, Higher Mathematics With Application to Science and Engineering McGraw-Hill, New York, 1939. [8] W. Chang, "A Queuing Model for a Simple Case of Time-Sharing", IBM Systems Journal, b, 2, 1966, pp. 115-125. [9] E. G. Coffman, "Analysis of Two Time-Sharing Algorithms Designed for Limited Swapping", Journal of the ACM 15, 3, July 1968, pp. 341-3 3. [101 E. G. Coffman and L. C. Varian, "Further Experimental Data on the Behavior of Programs in a Paging Environment", CACM, 11, 7, July 1968, pp. 471-474. [111 D. R. Cox and W. L. Smith, Queues, Wiley, New York, 1961. [ 12] P. J. Denning, "Resource Allocation in Multiprocess Computer Systems", Project MAC Tech. Rept. MAC-TR-50, 1968 (Thesis). 283

284 [131 P. J. Denning, "The Working Set Model for Program Behavior", Communications of the ACM4 11, 5, May 1968, pp. 323-333. [14] J. B. Dennis, "Segmentation and the Design of Multiprogrammed Computer Systems", Journal of the ACM, 12, 4, Oct. 1965, pp. b89-602. [15] M. Eisenberg, "Multi-Queues with Changeover Times", Tech. Rept. No. 35, Operations Research Center, M. I. T., April 1968 (Thesis). [16] D. W. Fife, "The Optimal Control of Queues, with Applications to Computer Systems", Tech. Rept. No. 170, Cooley Electronics Laboratory, University of Michigan, October 1965. [171 D. W. Fife, "An Optimization Model for Time-Sharing", Proc. AFIPS 1966 SJCC, 28, pp. 97-104. [ 181 G. H. Fine, C. W Jackson and P. V. McIsaac, "Dynamic Program Behavior Under Paging", Proc. 21th National Conf. of ACM, Thompson Book Co., Washington, D. C., 1966. [19] F. R. Gantmacher, The Theory of Matrices, Chelsea, New York, 1960. [201 D. P. Gaver, Jr., "Probability Models for Multiprogramming Computer Systems", Journal of the ACM, 14, 3, July 1967, pp. 423-438. [21] C. T. Gibson, "Time-Sharing with the IBM System 360 Model 67", AFIPS Conference Proceedings 28, (SJCC 1966), pp. 61-78. [221 M. Greenberger, "The Priority Problem", MIT Project MAC, November 1965, MAC-TR-22. [231 R. A. Howard, Dynamic Programming and Markov Processes, MIT Press, 1960. [241 W. S. Jewell, "Markov Renewal Programming", Parts I and II, Operations Research, 11, pp. 938-971, (1963). [251 L. Kleinrock, "Certain Analytic Results for Time-Shared Processors", IFIP Congress 68 Proceedings, August 1968, D119-D125.

285 [261 L. Kleinrock, Communication Nets Stochastic Message Flow and Delay McGraw-Hill, 1964. [27! L. Kleinrock, "Time-Shared Systems A Theoretical Treatment", JACM 14, 2, April 1967. [281 B. Krishnamoorthi and R. C. Wood, "Time Shared Computer Operations with Both Interarrival and Service Exponential", Journal of the ACM, 13, 3, July 1966, pp. 317-338. [291 B. W. Lampson, "A Scheduling Philosophy for Multiprocessing Systems", Communications of the ACM, 11, 5, May 1968, pp. 347-360.. [30] D. J. Lasser, "Productivity of Multiprogrammed ComputersProgress in Developing an Analytic Prediction Method", CACDM 12, 12, December 1969, 678-684. [311 M. A. Leibowitz, "An Approximate Method for Treating a Class of Multiqueue Problems", IBM Journal, 5, 3, July 1961. [32] M. A. Leibowitz, "A Note on Some Fundamental Parameters of Multiqueue Systems", IBM Journal, 6,4, pp. 470-471, October 1962. [331 M. L. Liou, "A Novel Method of Evaluating Transient Response", Proc. of IEEE, 54, 1, January 1966, pp. 20-23. [341 P. M. Morse, Queues, Inventories and Maintenance, Wiley, 1958. [35] J. M. McKinney, "A Survey of Analytical Time-Sharing Models", Computing Surveys, 1, 2, June 1969, pp. 105-116. [361 N. R Nielsen, "An Analysis of Some Time-Sharing Techniques", Communications of the ACM, 14, 2, February 1971, pp. 79-90. [371 A. Papoulis, Probability, Random Variables, and Stochastic Processes, McGraw-Hill, 1965. -- [38] E. Parzen, Stochastic Processes, Holden-Day, 1962. [39] T. B. Pinkerton, "The MTS Data Collection Facility", Memorandum 18, CONCOMP, The University of Michigan, June 1968.

286 [401 T. B. Pinkerton, "Performance Monitoring in a Time-Sharing System", CACM, 12, 11, Novwmber 1969, pp. 608-610. [41] T. B. Pinkerton, "Program Behavior and Control in Virtual Storage Computer Systems", Tech. Rept. 4, CONCOMP, University of Michigan, April 1968. [421 R. Pyke, "Markov Renewal Processes: Definitions and Preliminary Properties", and "Markov Renewal Processes with Finitely Many States", Ann. Math. Stat., 33, pp. 1231-1259 (1961). [431 B. Randell and C. Kuehner, "Dynamic Storage Allocation Systems", Communications of the ACM, 11, 5, May 1968, pp. 297-306. [44] P. J. Rasch, "A Queueing Theory Study of Round-Robin Scheduling of Time -Shared Computer Systems", Journal of the ACM, 17, 1,'January 1970, pp. 131-145. [451 J. Riordan, Stochastic Service Systems, Wiley, 1962. [46] T. L. Saaty, Elements of Queueing Theory, McGraw-Hill, 1961. [47] J. H. Saltzer and J. W. Gintell, "The Instrumentation of Multics", CACM, 13, 8, August 1970, pp. 495-500. [481 A. L. Scherr, "An Analysis of Time-Shared Computer Systems", MAC-TR-18, Cambridge, M. I.T. Project MAC, 1965. [49] J. E. Shemer and G. A. Shippey, "Statistical Analysis of Paged and Segmented Computer Systems", IEEE Trans. on Electronic Computers, EC-15, 6, December 19-6', pp. 855-863. [50] J. L. Smith, "Markov Decisions on a Partitioned State Space, and the Control of Multiprogramming", 07742-4-T, Systems Engineering Laboratory, University of Michigan, April 1967. [51] J. L. Smith, "Multiprogramming Under a Page on Demand Strategy", Communications of the ACM 10, 10, October 1967, pp. 636-646. [52] Lajos Takacs, Introduction to the Theory of Queues, Oxford University Press, New York, 1962.

287 [53] J. Todd, Survey of Numerical Analysis, McGraw-Hill, 1962. [54] University of Michigan, "MTS: Michigan Terminal System", University of Michigan Publication Distribution Services, Volumes I, II, III, February 1971. [55] V. L. Wallace and D. L. Mason, "Degree of Multiprogramming in Page-on-Demand Systems", CACM, 12, 6, pp. 305-308, June 1969. [56] V. L. Wallace and R. S. Rosenberg, "RQA- 1, The Recursive Queue Analyzer", 07742-1-T, Systems Engineering Laboratory, University of Michigan, February 1966. [57] E. So Walter and V. L. Wallace, "Further Analysis of a Computing Center Environment", CACM, 10, 5, May 1967. [581 D. J. White, "Dynamic Programming, Markov Chains, and the Method of Successive Approximations", Journal of Mathematical Analysis and Applications, 6, pp. 373-376 (1963).

UNIVERSITY OF MICHIGAN 3901111111115 02523 1 005111111 3 9015 02523 1005