ANALYSIS AND OPTIMIZATION OF MULTIPROGRAMMED COMPUTER SYSTEMS USING STORAGE HIERARCHIES Ashby Woolf University of Michigan Approved for public release; distribution unlimited

FOREWORD The research described in this technical report was accomplished under Contract F30602-69-C-0214, Job Order Number 55810000 at the University of Michigan, Ann Arbor, MI. Mr. Rocco F. Iuorno (ISIS) was the Rome Air Development Center project engineer. This report has been reviewed by the Office of Information (0I) and is releasable to the National Technical Information Service (NTIS). This technical report has been reviewed and is approved. Approved: ROCCO F. IUORNO Project Engineer Software Sciences Section Approved: / tKfN Cx K THMA INI Ch, Infb Processing Branch Info Sdiences Division ii

ABSTRACT The research described in this report centers around the development and application of a general and comprehensive mathematical model of computer systems which use storage hierarchies consisting of 2, 3 or more levels and in which the storage management is carried out automatically (i.e. transparent to the user.) This model has been implemented in the form of a highly interactive computer program which provides the user with an animated view of the system performance as model parameters are varied. There are roughly 50 independent variables in the model. (The number of independent variables is dependent on the hardware configuration.) These variables describe the system architecture, data paths and routing, storage device characteristics, CPU performance, and user program behavior. The overall model can best be described in terms of several component models. The storage device models take into account the effects of queueing for the device itself (such as a disk drive), queueing for channel service, seek time, latency time, and transfer time. The specific parameters may vary according to the specific device being modeled. Models for a core or random access device, drum, disk and data cell are described and implemented. The model which describes user program behavior is dependent on the storage allocated at each level in the hierarchy, the logical record or page size at each level, the size of the user program, and five other system independent variables. The user program model and the storage device models are linked together by a final model which relates user program behavior and the storage device performance. The macroscopic model includes effects of system architecture, data paths, queueing for the CPU, CPU lookahead and system software overhead. The solution of the combined system model involves numerical techniques. A complete solution requires approximately 1 sec., based on IBM 360/67. When the model is used in the context of optimization, an evaluation can be obtained in approximately 50 ms. In practical terms this means that in the case of analysis the printing of results is more expensive than the analysis itself. In the case of optimization over 1000 systems can be examined in 1 minute or over 60,000 per hour. iii

TABLE OF CONTENTS Page Chapter I INTRODUCTION1 1.1 A General Discussion 1 1.2 The Nature of the Problem 4 1.3 Objectives 5 1.4 A Preview 6 II A MODEL OF PROGRAM BEHAVIOR 16 2.1 A General Description of Program Behavior 16 2. 2 Basic Model Description 20 2.3 Effects of Program Loop Lengths on Page Faults 23 2. 4 Effects of Allocation During Initial Paging 29 2. 5 Consideration of a Distribution of Loop Lengths 37 2.6 Final Model Development 42 2. 7 Examples of Model Behavior With Varying Allocation 55 2. 8 Example of Model Behavior With Varying Page Size 68 II MACROSCOPIC MODEL 82 3.1 The N Level Hierarchy 82 3.2 Storage Allocation 83 3.3 Multiprogramming 91 3. 5 Interlevel Data Traffic 94 3. 6 Primary and Secondary Levels of Storage 101 3. 7 Dedicated and Shared Levels of Storage 108 3. 8 Traffic Description At Individual Levels 117 3.9 Storage Hardware Performance 125 3.10 Primary and Secondary Access Time 128 3.11 Interaction Between CPU and Primary Storage 143 3.12 System Performance 148 3.13 Solution 155 v

TABLE OF CONTENTS (Continued) Chapter Page IV HARDWARE MODEL FOR INDIVIDUAL LEVELS OF STORAGE 162 4.1 Basic Model 163 4. 2 Solution of Basic Model 172 4.3 Solution Algorithm 176 4.4 Disk Model 179 4. 5 Data Cell Model 189 4. 6 Core Model 191 4.7 Drum Model 192 4. 8 Effect of Specific Record Sizes 195 V A CASE STUDY IN ANALYSIS 198 5.1 Program Description 198 5.2 System Description 201 5.3 A Hardware Modification 242 5.4 A Change in User Program Characteristics 246 5. 5 Changing the Number of User Programs 253 5.6 Summary 259 VI SYSTEM OPTIMIZATION 261 6.1 Objective Function and Method 261 6. 2 A Simple Example 266 6.3 Changing the User Program Size 278 6. 4 Changing the Number of Core Units 281 VII CONCLUSIONS 286 Appendices A SOLUTION FOR INTEGRALS OF EQUATION 2.54 289 B REQUEST DISTRIBUTION 299 C COMPUTATIONAL DIFFICULTIES IN COMPUTING ( 311 BIBLIOGRAPHY 316 vi

LIST OF FIGURES Figure Page 1.1 System Analysis Model 1.2 System Model 1.3 Detailed System Model, Part 1 1.4 Detailed System Model, Part 2 2.1 Definition of W(t, r) 2. 2 The Lifetime Function for Random Accesses 2.3 General Lifetime Function 2. 4 The Virtual Address Space 2.5 Access Loop 2.6 Loop Position 2.7 The A Distribution 2. 8 gia as a Function of A 2.9 The Components of H (A) 2o 10 The Generation of HiCA) 2.11 The Lifecycle Function Versus Allocation for "Standard" Case 2.12 The Lifecycle Function Versus Allocation Wi Variations in p 2. 13 The Lifecycle Function Versus Allocation Wi Variations in e 2.14 The Lifecycle Function Versus Allocation Wi 7 7 10 11 17 19 19 23 24 25 39 45 46 48 the th th 57 59 60 th Variations in H 2.15 The Lifecycle Function 2.16 The Lifecycle Function Variations in a 2.17 The Lifecycle Function Variations in q' 2.18 The Lifecycle Function Variations in q 2 19 The Lifecycle Function "Standard" Case 2o 20 The Lifecycle Function Variations in H 2. 21 The Lifecycle Function 2. 22 The Lifecycle Function Variations in s 2o 23 The Lifecycle Function Variations in p 2. 24 The Lifecycle Function Variations in e 2o 25 The Lifecycle Function Variations in a 62 63 Versus Versus Allocation for H = oo Allocation With 64 Versus Allocation With Versus Allocation With Versus Page Size for the Versus Page Size With 66 67 69 72 73 Versus Versus Page Page Sice for H = oo Size With 75 Versus Page Size With Versus Page Size With Versus Page Size With 77 78 80 vii

LIST OF FIGURES (Continued) Figure Page 2. 26 The Lifecycle Function Versus Page Size With Variations in q' 301 A Four Level Hierarchy 3, 2 Access Distribution 3 03 Multilevel Paging 3. 4 Traffic - Primary Read to Level 4 3.5 T Array for Example 1 3.6 Transfer Pattern 4-Level Hierarchy for User Induced Level 4 Read 3.7 Traffic Diagrams 3. 8 T Array for Example 2 3.9 3.10 3.11 3.12 3,13 3.14 3.15 3.16 3.17 3.18 3.19 3.20 3. 21 3.22 3.23 3.24 3.25 3.26 3.27 3.28 4. 1 4.2 403 4 4 4.5 4. 6 4.7 4.8 5.1 5.2 5.3 Example 3 Read to Level 1 Example 3 Read to Level 2 Example 3 Read or Write to Level 3 Example 3 Read or Write to Level 4 T Array for Example 3 Example 4 Read to Level 1 Example 4 Write to Level 1 Example 4 Read to Level 2 Example 4 Write to Level 2 Example 4 Read or Write to Level 3 Example 4 Read or Write to Level 4 T Array for Example 4 Regions of Storage Periods of User Program Execution G Array 3-Level Hierarchy Tc Versus Tp Primary Bound Operation Secondary Bound Operation Solution for r and r' State Diagram for Basic Model State Diagram for Basic Model State Diagram for General Model Service Rate Versus Arrival Rate Disk Service Timing Diagram Channel Queueing Model State Diagram for Channel Queueing Model Drum Sectors and Fields System Diagram System Variables Level 1 Hardware Description 81 83 86 88 95 97 99 102 103 105 105 106 106 107 109 109 110 110 112 112 113 115 118 132 138 144 150 152 158 164 165 171 174 181 185 187 193 200 203 205 viii

LIST OF FIGURES (Continued) Figure Page 5 4 5.5 5. 6 5.7 5.8 5.9 5.10 5.11 5.12 5.13 5.14 5.15 5.16 5.17 5.18 5.19 Lev( Levi Levi Levi Lev( Lev( Lev( Levi Tral Trai The The The The el 1 Performance el 1 Queueing el 2 Hardware Description el 2 Performance el 2 Queueing el 3 Hardware Description el 3 Performance el 3 Queueing ffic Patterns Resulting From User Program R, ffic Patterns Resulting From User Program W Traffic Array for User Program Reads Traffic Array for User Program Writes Critical Read/Write Array for User Program Critical Read/Write Array for User Program eads rites Reads Writes User Program Specifications User Program Behavior 5. 20 Dependent Variables, Part 1, 5. 21 Dependent Variables, Part 2, 5. 22 Dependent Variables, Part 3, 5. 23 Dependent Variables, Part 1, 5. 24 Dependent Variables, Part 2, 5. 25 Dependent Variables, Part 3, 5. 26 Dependent Variables, Part 1, 5. 27 Dependent Variables, Part 2, 5. 28 Dependent Variables, Part 3, 5. 29 Dependent Variables, Part 1, 5.30 Dependent Variables, Part 2, 5.31 Dependent Variables, Part 3, 5. 32 Performance Versus Number "Standard't Case "Standard" Case "Standard" Case for Drum RPM= 3600 for Drum RPM= 3600 for Drum RPM= 3600 for p=,3 for p=.3 for p=.3 for p=.7 for p=.7 for p=.7 of Programs 206 207 210 211 212 215 216 217 219 220 222 223 225 226 228 229 232 233 234 243 244 245 247 248 249 250 251 252 254 254 255 255 257 257 258 258 268 269 270 271 5. 33 CPU Utilization Versus Number of Programs 5. 34 Relative Effect Versus Number of Programs 5.35 Allocation Versus Number of Programs 5. 36 % of Level 3 Accesses Versus Number of Programs 5.37 Queue Length Versus Number of Programs 5.38 Access Time Versus Number of Programs 5. 39 Secondary Access Time Versus Number of Programs 6. 1 Decision Variables for "Standard" Case 6. 2 Decision Variables for Optimal $250, 000 System 6. 3 Dependent Variables, Part 1, for Optimal $250, 000 System 6.4 Dependent Variables, Part 2, for Optimal $250, 000 System ix

LIST OF FIGURES (Continued) Figure Page 6. 5 Decision Variables, Part 3, for Optimal $250, 000 System 272 6.6 Decision Variables for Optimal $300, 000 System 274 6.7 Decision Variables, Part 1, for Optimal $300, 000 System 275 6.8 Dependent Variables, Part 2, for Optimal $300,000 System 276 6.9 Dependent Variables, Part 3, for Optimal $300,000 System 277 6.10 Performance Versus User Program Size 279 6.11 Optimal Number of Programs Versus Program Size 279 6.12 Allocation Versus User Program Size 280 6.13 Relative Effect Versus User Program Size 280 6.14 Optimal Performance Versus Number of Core Units 282 6.15 CPU Utilization Versus Number of Core Units 282 6.16 Optimal Number of Programs Versus Number of Core Units 283 6.17 Allocation Versus Number of Core Units 283 6.18 Relative Effect Versus Number of Core Units 284 B1 Circulating Queue 300 B2 Open Queueing Model 305 x

Chapter 1 Introduction The design and application of large computing systems involves considerable risk. One can draw a parallel between those who have designed and applied today's computing systems and those who, in the early days of flight, strapped wings to their backs and jumped from the roofs of barns. Neither had adequate methods of predicting system performance. The work reported here attempts to contribute to computer system technology through the development of improved methods of predicting system performance. 1.1 A General Discussion Throughout the development of computing systems there has been an effort to make a given hardware technology perform better as a system. The primary emphasis in the early days of development was on hardware technology. However, as computing systems have progressed, there has been a continued and growing interest in the design of systems which make the best and most efficient use of a given hardware technology. One important method of achieving efficient use of a given hardware technology has been the use of storage hierarchies. Storage hierarchies are not unique to computer systems. Your pocket, your desk or dresser drawer and your basement represent a storage hierarchy. The basic idea is simply to store those items used most frequently in 1

an easily accessible location. Those items seldom used may be stored in less accessible and correspondingly less costly locations. The storage hierarchy was first implemented in a computing system developed at the University of Manchester in England in 1949. As computer system designed have progressed, two things have happened. First the complexity of the hierarchy itself has increased. We commonly see systems with 5, 6, or more different kinds of storage hardware capability, for instance registers, cores, drums, disks, data cells, magnetic tapes, punched cards, and punched paper tape. A second and very important change has occurred in the management responsibility of the hierarchy. The gains achieved by the storage hierarchy have imposed considerable burden upon the programmer. At the outset the programmer was responsible for deciding what information should be stored on what device at each instant of time. In addition the programmer was responsible for carrying out the necessary operations required to move the information about as required. Lastly and very importantly, the programmer was responsible for keeping track of how and where everything was stored as it was moved about in the system. As we have progressed and hierarchies have become more complex the operating systems and hardware have assumed these responsibilities in varying degrees. In some cases all responsibilities for management of a hierarchy have been assumed by the operating system and/or hardware and the hierarchy is invisible to the programmer. 2

Another area of computer systems development has been in the use of multiprogramming. A computer is often limited by its slowest (or most overworked) component, often an I0 device. One of the methods used to alleviate this problem has been multiprogramming or the practice of working with more than one user program at a time. One of the effects of multiprogramming is to provide the system with a more balanced workload. If a system processes one program at a time, it will find some programs using a great deal of CPU resource and leaving the 10 devices idle, while others leave the CPU idle and do voluminous I0. On the other hand, if a system is processing 10 or 20 programs at once, it is unlikely that the system will see this group of programs exhibit the wide variations in resource demand exhibited by the individual programs in the group. In other words system loading is more consistent and predictable when the sample space grows larger. The second effect of multiprogramming is to introduce parallel paths in the workload as seen by the computing system. If a computing system must follow a single thread of execution, a delay in any part of the system holds up the entire system. Multiprogramming is one way of providing the necessary parallel paths of execution which, if properly used, can increase resource utilization. The difficulty with multiprogramming is complexity. The problems of resource scheduling are difficult. The problems of protecting one user from another, protecting the operating system itself, and 3

charging for resource use become most complex. However, the rewards for efficient resource utilization can be great. There has been considerable motivation for complexity in the effort to better utilize computing system resources. This has been added to by the response requirements of time-sharing and real time systemso This need for complexity has placed the modern computing system outside the capability of man's unaided intuition. 1. 2 The Nature of the Problem In very few words the problem is that of predicting and controlling the behavior of complex computing systems using storage hierarchies and multiprogramming. A computing system using a storage hierarchy generally involves 2 or more different types of storage devices. Different device types have widely varying performance characteristics. Drums, cores and disks all behave differently under load. A system's performance may be determined by a complex balance of workload throughout the system of devices or may be determined by the performance characteristics of a single overworked device. User programs can be big or small. They can access data in a serial or random manner. They can do large quantities of 10 or almost none at all. The data paths and routing of information influence the load seen by storage devices. The logical record sizes throughout the 4

system also influence the load seen by storage devices and in turn their response times. The number of programs running in a multiprogrammed system affects the storage allocations of user programs. This in turn influences the demands placed on the system by user programs. All of these factors and many others combine to create an enormously complex and remarkably difficult analysis problem. It is difficult to merely determine what a given system will and will not do in a given circumstance. It is even more difficult to design such systems especially if some kind of optimal or near optimal design is required. 1.3 Objectives The specific objective of this research is to develop and demonstrate a mathematical model of a computing system. The computing systems in question here fall into the class of those systems using storage hierarchies of 2, 3 or more levels and multiprogramming. The model will exhibit the following characteristics: 1. The model will include the effects of user program behavior, operating system characteristics and hardware performance. 2o The model will be versatile and easily applied to a wide range of system configurations. The model should be useful as a tool for the investigation of computing systems in general as well as applicable to the detailed investigation of a particular system. 5

3. The model will be useful as a tool for both analysis and optimization. 4. The results obtained from the model will approach the accuracy and realism of those obtained from simulation models. 1.4 A Preview At this point we will attempt a broad preview of the coming chapters. It is hoped that this section will serve to place the contents of the chapters to follow in proper perspective and serve as a reader's guide. The overall model for computer system analysis is shown in Figure 1.1. On the left we see 3 categories of independent variables. First we have the user program description. This includes independent variables such as the size of the user programs and other characteristics of user program behavior. Next is the storage device descriptions. This includes such items as drum RPM, disk seek time and variables relevant to storage device performance. Last we have data traffic dependencies and architecture. This includes CPU performance characteristics, logical record sizes, data transfer timing dependencies and other global system characteristics. As an output for the model we show performance. In the narrow sense, performance is defined as the mean rate at which the collection of user programs running on the system make reference or access to data and instructionso In the broad sense the performance also includes many 6

User Program Description Storage Device __ Descriptions " ys - KArn mputer;tem del lVlUI -- Performance Data Traffic Dependencies and Architecture System Analysis Model Figure 1.1 Assumed Performance User Program ------ Description Storage Device Descriptions Data Traffic Dependencies and Architecture Assumed Performance High or Low System Model Figure 1.2 7

details such as mean queue lengths at various devices in the storage system and CPU utilization. Figure 1.1 shows the model as seen by the designer when being used for analysis. Figure 1. 2 shows the model in slightly greater detail and from a different point of view. It is this model that we will deal with in the next 3 chapters. We see that the independent variables on the left have not changed. However, the model shown here does not give us performance (mean user program access rate) directly but rather tells us if an assumed performance is greater than or less than a given system's capability. For analysis we will carry out a simple search to find the performance of a given system. The primary advantage of this particular approach to the problem occurs in optimization where systems are compared in a search for a system configuration with the greatest performance or mean user program access rate. Figure 1.3 and 1.4 show a detailed breakdown of the model of Figure 1. 2. Beginning at the left of Figure 1.3 we see the User Program Model. The independent variables supplied to this model fall into two classes, the user program description and the storage system characteristics. The user program description consists of 5 independent variables which describe the characteristics of the user program. The variables are shown in brackets here for reference in later chapters. The storage system characteristics consist of the 8

storage allocation at each level in the hierarchy and the logical record size at each level. The user program model, given this information, determines what fraction of a user program's accesses will be directed to each level in the hierarchy of storage. This is referred to and shown in the figure as user program demand. For example, in a two level system with a core and a drum, this would be the fraction of user program references or accesses to storage which are satisfied at the core and the fraction which require drum activity. The user program model is discussed at length in chapter 2. The model is an outgrowth of the "lifetime function" concept proposed by Belady and Kuehner [6]. The model is also indebted to the "working set" concept introduced by Denning [21]. The next block in Figure 1.3 shows the System Traffic Model. This model has as its independent variables the assumed mean user program access rate (assumed performance), the user program demand and the data transfer specifications. The data transfer specifications describe what happens when a user program accesses a given level in the hierarchy. We are treating the user program access to a given level as a cause and the activity generated in the system as a result of that access as the effect. The effect takes the form of data transfers in the system. The data transfer specifications describe the data transfers which occur as a result of user program accesses to 9

User Program Description [Q,cr,p,e,H] i Assumed Mean User_ Program Access Rate \ [r] _..... User Storage User Program 1/frll 1.QxTr Q+A (Chap. 2) Storage System - Characteristics [Si qi] Program Traffi Traffic__ TrafficDemand Environment [ui] Model [.. [ui] [A',C^, (Chap. 3 C'. Bj] Data Transfer / Storage Device Specifications Specifications [T,w] [variables depen Storage Device Model Response Time [Bj( )] de/ ident O-I on device type] Detailed System Model, Part 1 Figure 1.3

Storage Device Response Time [Bj(.)] i Assumed Mean User Program Access Rate [r] v I~~~~~~~~~~~~~~ User Program Demand [Ui] Major Function Timing Model Ma or Function Timing Information [Tp T, Tel Assumed Mean User Program _ Access Rate High or Low Data Transfer (Cha Timing Dependencies [G] ---— / p. 3) CPU and Architecture_ Description [N,L,K,M,r,y, h] Detailed System Model, Part 2 Figure 1.4

some level in the hierarchy. Using this information along with the mean user program access rate and the fraction of user program accesses to each level (user program demand) the System Traffic Model generates a description of the traffic environment at each level in the hierarchy. The traffic environment is given in terms of the mean rate at which records are being read and written at each level, the mean record size being read and written at each level, and the maximum number of requests for service that can be generated by the system for each level, This System Traffic Model is discussed in detail in Chapter 3. We arrive now at the Storage Device Model at the right hand side of Figure 1.3. The storage device model is actually a collection of models, any one of which can be used to represent the hardware at any level in the storage hierarchy. The device models give us the mean time required to read or write a record of a given size at a given level in the hierarchy. The model independent variables are the traffic environment seen by the level in question and device specification relevant to the device type at that level. The storage device models are discussed at length in Chapter 4. Models for core or random access devices, drums, disks, and data cells have been developed. The models are not particularly unique or special in any real sense. They are based on finite Markov chains 12

and require a numerical solution. The models were designed to provide generality of application, realistic results and rapid solution. Backing away from the details of Figure 1.3, we can review what goes in and what comes out of this portion of the system model. We provide as independent variables a description of user program behavior and some storage system characteristics. From this we learn how the user program behaves in the system. Next, assuming a mean user program access rate and given the data trasfers which occur as a result of user program behavior,we compute the traffic flows at each level in the system. Given this and a description of the hardware at each level we compute the mean time required to read or write records of various sizes at each level. The principal result of the portion of the model shown in Figure 1.3 is simply the mean response time for each of the levels in the hierarchy. We will now turn to Figure 1.4 where the second portion of the system model is shown. On the left we have the Major Function Timing Model which is discussed in detail in chapter 3. This model is responsible for timing information such as the mean time that a user program remains ineligible for execution following an access to some lower level of storage. The independent variables of this model are the storage device response times,the user program demand,and the data transfer timing dependencies. The data transfer timing dependencies require some explanation. 13

Imagine a system having a core and a drum. If a user program references some piece of data that happens to be on the drum a record or page will be read from the drum and written in core. There may also be a transfer from the core to the drum in order to make room for the new information coming into core. Here we see the possibility for 4 reads or writes. There is the operation of reading a record from the drum and writing that record in core and reading a record from core and writing it on the drum. However, in a typical system the only delay experienced by the executing program is that of reading the record from the drum. The other reads and writes do occur and do contribute to the congestion in the system but are generally carried out in such a way as to avoid a direct delay in execution. The data transfer timing dependencies specify precisely which reads and writes contribute directly to delays in program execution. Finally on the right of Figure 1.4 we have the system performance model again covered in Chapter 3. This model has as its independent variables the assumed mean user program access rate, the major function timing information and certain items of a CPU and architecture description. This submodel determines if in fact the assumed mean user program access rate is too high or too low. This completes the model giving us the final result as shown in Figure 1. 20 This description of the model has been necessarily incomplete and simplified somewhat to aid in explanation. The detailed description 14

of the various model components are found in Chapters 2, 3, and 4 as indicated. Chapter 5 is concerned with examples involving analysis and Chapter 6 with examples of optimization. Chapters 2, 3, and 4 are long and concentrate on the detailed development of the various parts of the model described. The difficulties of placing the numerous but necessary details in proper perspective may be greatly reduced by becoming familiar with the examples of Chapters 5 and 6. Section 5. 2 of Chapter 5 is of particular interest in this regard. A complete example is covered in Section 5. 2 including some mention of all of the independent and dependent variables. 15

Chapter 2 A Model of Program Behavior In an effort to identify and describe the characteristics of a computer program or process L. A. Belady and C. J. Kuehner [6] proposed the lifetime function. The lifetime function expresses a program's mean execution interval between references to secondary storage, as a function of the storage allocation in core or primary storage. Belady and Kuehner are not alone in attempting to model this aspect of a process. Very similar constructs have been considered by Peter J. Denning [21]. These efforts are at least in part attempting to determine what part of a program or process must be located in core to avoid an excessive number of transfers between core and drum. 2. 1 A General Description of Program Behavior It is generally agreed that most processes have a non-uniform storage access behavior and that it is meaningful to discuss the currently active part of a process. The concept of the currently active part of a process has been expressed in several different and useful ways. This idea is basic to the question of what part of a process should be in core. P. J. Denning [21] refers to this currently active part as the working set. In Denning's words, "We define the working set of information W(t, T) of a process at time t to be the collection of 16

information referenced by the process during the process time interval (t-, t) ". t-T t -!x —2/ZZ..x7-7777'7?F7?-/-7_ //_ - process time (l [ pages referenced in this interval constitute W(t, T) Figure 2. 1 Definition of W(t, T) There are many other ways to define a set of currently active pages. For instance we may modify the working set by considering t and Tof W(t, 7) to be real time instead of process time. We might consider a different parameterization such as the set W'(t, n) defined as the n most recently used pages as a function of process time t. This is very similar in concept to the work by L. A. Belady and C. J. Kuehner [6]. Belady and Kuehner define the locality of storage references as a basic program property. "Locality is defined as the total range of storage references during a given execution interval. " The remainder of the paper [6] if not the definition of locality would indicate that Beladyts notion of locality is very similar to if not W'(t, n). The Two Level Hierarchy The concept of a lifetime function was developed by Belady and Kuehner [6] in the context of a paging system consisting of a 17

core and a drum. Here we will extend this concept in several ways but first we will consider it in a form close to Belady's original form as developed for two levels of storage. When a program begins execution following a page fault (a reference requiring a page transfer from the drum) some of its pages will be in core and others generally will not. The precise information contained in core will determine the number of execution cycles required to generate another page fault. Since we are considering a paged system the information contained in core is determined by three factors: 1. The method of selecting pages to be paged in and out. 2. The number of pages remaining in core. 3. The page size. If we consider 1 and 3 to be fixed we may express the average number of execution cycles required to produce a page fault as a function of 2. Belady defines his lifetime function as a relation between the size of the core allocation and the average length of an execution interval. In order to get a feel for the general shape of this function let us consider the simple case of completely random accesses. In this case the lifetime function is given in [6] as f(s) r = /r + (s/r) 2 + (s/r) +... (2.1) where r is the size of the program in bits and s is the core allocation in bits. 18

f(s) f(s) = s/r 1 - s/r O s r The lifetime function for Random Accesses Figure 2. 2 s ask f(s) as I / // f(s) s General lifetime function Figure 2.3 19

This function is clearly convex and a curve of this form is shown in Figure 2. 2. The general shape of a more realistic lifetime function is shown in Figure 2.3 with a solid line as well as an approximation proposed by Belady. Belady's approximating function is of the following form where a and k are constants to be adjusted to fit specific program behavior f(s) = a sk (2. 2) 2. 2 Basic Model Description Belady's functional model for approximating program behavior has several deficiencies. 1. The model parameters a and k are not clearly related to properties of the program being modeled. 2. The model is valid only over part of the range of s for realistic programs. 3. The value of the lifetime function is expressed in units of execution time which limits its use in certain contexts. In addition to removing the above deficiencies we would like to develop a model which considers the lifetime function as a function of both allocation, s, and page size, q. We will refer to the model of program behavior developed here as the lifecycle function. This name reflects a change in units from execution time to the number of user program storage references required to produce a page fault. 20

conclusion by noting that with independent and equally probable random accessing, the specifics of what information is in core are irrelevant. Thus the lifecycle function is only a function of s and is independent of q. As an aside we might consider what the optimal page size would be if programs did in fact behave in this manner. Since the lifecycle function is independent of q we have no motivation to make q larger than 1 word. A larger q and its associated information movement would be without effect on the lifecycle function and serve only to clutter channels and devices. This is of course an extreme case and has few representatives in the real world. Now we will consider a second extreme case one which is the antithesis of the above. Consider a process which accesses storage sequentially from its first location to its last and then continues by repeating these accesses forming a large loop. Here accesses will be made proceeding sequentially through a page and into the next, producing a page fault. If the entire process is not in core (i. e. s < qrQ/ql where rxl is the smallest integer > x and Q is the actual program size) the page needed will have always been paged out. This of course assumes a first in first out, least recently used or similar page out selection algorithm. Since we will produce a page fault at the end of each page we can write f(s, q) = q for s < qrQ/ql. (2.3) 21

Where Q is the actual program size rQ/ql is the smallest integer > Q/q and qrQ/ql is the apparent program size as seen by a system with a page size q. When s > qfQ/ql we may write f(s, q) = aq for s > q[Q/ql (2.4) where a is the number of times the loop is executed. Again we may stop to consider an optimal page size for processing such a process. It is clear that q should be large, in fact on the order of s,thereby refreshing the entire allocated storage with each page fault. Having considered these two extremes we will now turn to a more realistic model. A Process Model We will consider here a stochastic model of a process which is in some sense a combination of the two extremes just discussed. We may describe the access behavior as follows: 1. Randomly select a location a in the virtual address space of the process. 2. Randomly select a loop length A. 3. Access the A locations in the loop of 2 above sequentially a times. 4. Repeat the above steps. Where a loop which extends beyond the last virtual address of the process is continued at the beginning of the virtual address space. 22

Our pattern of access is then one of a series of loops where both the position and size of the loops change in a random fashion. Our immediate concern will be to develop the lifecycle function f(s, q) for such an access behavior. 2.3 Effects of Program Loop Lengths on Page Faults The first step in developing this lifecycle function is to determine the number of distinct pages accessed when accessing the loop. This is a function of two things, the loop length and the position of the loop in virtual address space. The virtual address space can be represented as shown in Figure 2.4. This boundary is part of this page IV A B A —.- | -| —| B The page size is q bits The Virtual Address Space Figure 2.4 The line A-B in Figure 2.4 depicts a segment of virtual address space. The division lines represent page boundaries and the boundary is assumed to be part of the page to the right. The page size is q and is in bits. 23

We will now consider a loop of length A which begins on a page boundary at the beginning of a page. A- q A -i ItoB --- —.-~-t. --- —— ~ -- B ---- A. —.. a Access Loop Figure 2. 5 Here we may write the number of unique pages accessed in the loop as [A/q], where [xl is defined as the smallest integer >x. Examining Figure 2. 5 we can see that if we move the position of the loop a to the right the number of unique pages accessed will remain [A/q] until the right end of the loop crosses a page boundary. At this point the number of pages accessed will increase by 1 to [A/ql + 1 and remain so until the left end of the loop crosses a page boundary. Thus the number of unique pages accessed by a loop of length A will be either [A/ql or [A/q] + 1 depending upon the position of the loop in the virtual address space. We will now consider what positions of the loop will involve [A/q] unique pages and what positions of the loop will involve [A/ql + 1 unique pages. We will consider the position of the loop in virtual address space to be indicated by the starting address of the loop or the left end when diagrammed. We will first point out that if it is positioned or begins on any one of the first [A/q]q - A bit positions a page [A/ql unique pages will be accessed by the loop. 24

— [A/qlq - ^_ -^- I^S - f —, I[A/qlq- A A/qq -- [A/qlq - A Figure 2.6 Loop Position As shown in Figure 2.6 there are [A/qlq bits in the unique pages accessed by a loop of length A when the loop is positioned on a page boundary. Thus it is clear that in this case there are [A/q]q - A bit positions not used by the loop. Thus one may position the loop on any one of the first r[A/qlq - A bit positions of any page and access only [A/q] unique pages. Correspondingly if the loop is positioned on any one of the q - ([A/qlq - A) or q - [A/ql + A bit positions of any page the loop will access [A/ql + 1 unique pages. We will consider a the position of each loop, to be a uniformly distributed random variable whose range is the entire virtual address space of the process. Thus we may write the probability of accessing any given number of unique pages in a loop as: 25

P(accessing N unique pages) = [A/ql - A/q for N = [,&/ql (2. 5) = 1 - [A/ql + A/q for N = [A/q1 + 1 = 0 otherwise Page Faults Up to this point we have considered the number of unique pages accessed by a loop of length A in a system with a page size q. Here we will consider the number of page faults generated while accessing such a loop. There are two important factors that must be taken into consideration here. We must determine if the number of unique pages accessed by the loop is greater than the space allocated s/q. If this is the case we will exhibit almost continuous paging. This is the simple result of the fact that as we access sequentially around the loop pages will be paged out before we complete the loop and access them again. Here one might say that the working set is larger than the allocated space. A second condition occurs if the allocated space, s/q, is larger than or equal to the number of unique pages accessed in the loop. Here we will experience an initial burst of page faults as the pages associated with the loop are paged in and then a period of execution uninterrupted by additional page faults. 26

A second factor to be considered is that of finding needed pages in core (or some equivalent high level in the hierarchy) as a result of paging which occurred earlier. This means that as we begin each new loop of accesses we may find some of (and possibly all of) the needed pages resident in core. Our immediate interest will be to find the ratio between the number of accesses made and the number of page faults which occur while accessing a loop A bits in length a times. At least initially we will be interested in this ratio as a function of A the loop length. Thus we will define g(A) = # of accesses g(lA) # of page faults. (2.6) In order to express g(A) it will be necessary to consider several special cases. We will begin by considering the two special cases g(A) = gl(A) when a falls in the first [A/q]q - A bits of a page = g2(A) when a falls in the last q-[A/q]q + A bits of a page (2. 7) where a is the virtual address position of the beginning of a loop. The need for these two cases is generated by the different number of unique pages accessed in each case. In Case 1, for gl(A), [A/q] and in Case 2, for g2(A), [A/ql + 1 unique pages are accessed. The development of gl(A) and g2(A) are quite 27

similar with this difference of a single page being the only distinction. Thus we will develop gl(A) in some detail and write g2(A) by extending the same arguments. An Expression for gl(A) As we vary A we find that gl(A) itself falls into two rather special cases. We will consider these two cases as Case la and Case lb and write them as gl(A) = ga(A) for [A/ql < s/q glb(A) for [r/ql > s/q (2.8) To begin, notice that s/q is the number of pages allocated in core. In Case la the number of unique pages accessed is less than or equal to this allocation. Thus after the initial accessing of all the pages in the loop no further paging will be required. It should be clear that at most there will be rA/ql page faults during the accessing of this loop for after the loop has been accessed once all the required pages will be in core and repeated accesses in this loop will produce no further page faults. Let us now consider Case lb. Here [A/ql > s/q, or more unique pages are accessed in the loop than the allocated space in core. This means that as we reach the end of the loop more pages will have been accessed than space has been allocated for. Assuming a least recently used, first in first out or similar page out selection 28

scheme we may be sure that after accessing the first s/q unique pages in the loop a page fault will occur each time the sequence of accesses crosses a page boundary. This will continue as long as the loop is accessed. Since the loop will be accessed a times a maximum of [A/qla page faults will occur. 2.4 Effects of Allocation During Initial Paging Another factor to be considered is that of finding one or more of the [A/ql unique pages needed, in core. When the loop now being considered is begun there will be s/q pages in core as a result of one or more previous access loops. These pages may very well be some of those needed in the new loop and may remain in core (i. e. not be paged out) at the time of its first access in the new loop. It is clear at the outset that the number of page faults avoided in this manner is a random variable. It is also apparent that this random variable's mean and density function may be a function of all previous A's and a's. We will avoid these complications by making certain assumptions and replacing this random variable with its mean. Before we proceed with this, let us recall that our ultimate objective is not to accurately model the described process but to develop a function which may be used to approximate the lifetime functions of real programs. Thus we have a great deal of flexibility in the assumptions we may make as we proceed as long as the final result is suitable and useful for our purposes. 29

As we begin a new loop we will assume that the s/q pages remaining in core from previous accesses are scattered about randomly in the virtual address space of the process. Thus as we begin the new loop the probability of finding the first page in core =s/q [Q/ql probability of finding the second page in core s/q - Q/ql -1 or in general probability of finding the ith page in core = s/q +1 (2.9) Q/ql - i+1 This only holds true for the first s/q pages or the number of pages accessed in the loop whichever is smaller. In the case of the first page accessed there are s/q pages in core and the process uses rQ/ql pages. On each successive access the number of these left over pages is reduced by one either by the paging out process caused by a page fault or by its use and lack of availability. This of course assumes that s < qrQ/ql for if s > qfQ/ql no such paging out will occur and the probability of finding the i-th page in core will always be 1. Thus we may write th s/q __ i+1 Prob(i page in core) = s/q i+1 for s < qrQ/ql [Q/ql - i+1 =1 for s> q[Q/ql (2.10) 30

Unfortunately this expression of probability leads to excessive complications later when we consider a distribution of loop lengths, A, and integrate with respect to A. However we can successfully approximate using Prob(i page in core) = s/q - i+1 for s < q[Q/ql rQ/ql =1 for s > q[Q/ql (2.11) There are several reasons why this approximation serves us well. First it is reasonably accurate for small i and small i's predominate. The value of i cannot exceed s/q or [A/q] + 1. This means that in order to be involved with large i's, we must have both a large allocation s and a long loop length A. Second we will be using a summation of these probabilities for i = 1 to [A/ql or in some cases [A/ql + 1. The values of the terms in both Equation 2. 10 and 2.11 decrease with increasing i. Thus the dominant terms in the series are those with small i for which the approximation is most accurate. We may write the expected value of the number of such "free" pages which will occur with each new loop as 31

K K K(s/q+ 1) - i z s/q - i=+l i=1 [Q/ql [Q/ql K s/q + K - K(K+1)/2 (2.12) [Q/ql for s <q[Q/ql and K Z 1= K for s >qQ/q] i=l where K = [A/ql in case la and K = s/q in case lb We will digress for a moment to insure that the source of the two values of K above is clear. In case la the number of pages referenced is less than or equal to the number allocated. In this case we must terminate the sum at the number of unique pages accessed which is rf/q1. In case lb the number of unique pages referenced is greater than the number allocated. The number allocated is s/q and we can only expect to find "free" pages during the first s/q unique page accessed. Making these substitutions for case la and lb: Case la substituting K = rA/qg when s < q[Q/ql 32

[A l s/q - i+l i=1 [r/ql 1 2 1 s/q [A/ql + rA/ql - -- [r/ql 2 - - A/ql 2. rQ/ql (2 [A/ql (s/q - [A r/ql) + rQ/ql:. 13) when s > qrQ/ql [Aq1 i 1 = rA/ql i=l (2.14) Case lb substituting K = s/q when s < qrQ/ql s/q - i+l i=1 [Q/ql s/q (s/q + 1) - s/q (s/q + 1)/2 [Q/ql (2.15) 1 22 (s2/q2 +s/q) 2[Q/q] Recalling that case lb occurs when rA/ql > s[Q/ql, Equation (2. 8), and that [A/ql < [Q/q1 we see that in case lb s < q[A/ql < q[Q/q1 (2.16) Thus in case lb it is always the case that s < q[Q/ql Here we will substitute the expected number of "free" pages for the actual number of the pages which is a random variable 33

(except when s >q[Q/ql). By subtracting the number of "free" pages from the number of possible page faults we will obtain the number of actual page faults. There are several cases: Case la: [r/ql( s/q - 2 rA/ql) + 2-rA/q # of page faults (la) = [A/ql - 2 [Q/ql -ra/q][1 1 1 = [A/ql[l - 1s I + I A- r/ql ] qrQ/ql 2[Q/ql 2[Q/q1 for s < qrQ/ql = A/ql - [A/q] = 0 for s > q[Q/ql Case lb: (2.17) #of page faults (lb) = rA/ql C - (s2/q + s/q) (2. 18) 2rQ/ql for s < qrQ/ql (Note s never equals q[Q/q] in case lb) In all cases the number of accesses made is the same. # of accesses = A a/q' (2.19) where q' = # of bits in a word. Thus we may write: 34

gla(A) =A — / — (2.20) [A/ql[(1 s 1 1 q[Q/ql 2[Q/q] 2[Q/q1 for [A/ql < s/q and s < q[Q/q] A a /q' = 0- = a (2.21) for [A/ql < s/q and s > qFQ/ql and glb() -= -- -- (2. 22) A/q~ 2/1 ( 2 2 [A/q]a- 1- (s/q+ s/q) 2[Q/q] for [A/q] > s/q The expressions for g2a(A) and g2b(A) may be obtained directly from gla(A) and glb(A) by substituting [A/q] + 1 for FA/ql. This does not fall into the category of those things which are intuitively clear even to the most casual observer. However we will not go into a lengthy justification here because the development of case 2 is identical to case 1 which we have just considered. Any 35

questions concerning case 2 may be resolved by referring to the discussion of case 1 and substituting 2a, 2b and [A/q] + 1 in the appropriate places. We may write g2a(A) and g2b(A) as follows. g2a(A) = _A o/q (A/ql + 1)[(1 - 1 ) + ([A/ql + 1)] q[Q/ql 2rQ/ql 2rQ/ql (2. 23) for rA/ql + 1 < s/q and s < qrQ/ql for [A/ql + 1 < s/q = 00 (2. 24) and s > q[Q/ql and g2b(A) = A a/q' ([r/ql + 1) a - -- (s2/q2 +s/q) 2rQ/ql (2.25) for [A/ql + 1 > s/q Note: We will make a small alteration to the expressions for gla(A), glb(A), g2a(A) and g2b(A) at a later point in the text. 36

2. 5 Consideration of a Distribution of Loop Lengths In order to compute E[g(A) ] we must have a density function for A. The question arises as to what should such a density function look like. One would imagine that a real program would be best modeled by a number of fixed length loops in addition to several variable length loops. The fixed length loops are generated by such things as actual DO loops. Variable length loops are generated by such activities as searching a list for some value. This would produce a density function containing a number of "spikes". However, the level of this model does not lend itself to such a detailed description of a program. We can however consider a density function with a single dominant peak with appropriate variables which allow control over the sharpness and the position of the peak. A function of the form 1 a + (b - A)2 provides us with the needed peak and control over the sharpness of the peak. Here the peak will occur at A = b and will have a maximum value of 1/a. For our purposes we will choose the constants in the equation to more closely suit our problem. Thus choosing 1 1 A 2 (2.26) + (P- [Q/ e 37

as our basic function we may position the peak at any point in the virtual address space by choosing a p in the range 0 < p < 1. Thus if we wish to locate the peak of the distribution of A's at.2 of the length of the program then we choose p =. 2. Notice that as we change the size of the program the peak will remain in the same relative position. We will consider this aspect in more detail later. In order to make this function into a density function we must normalize it. Taking the integral [Q/qq dA = q[Q/qetan - ep)][qlq e2 ( Q/qp e [Q/qlq = q[Q/qle[tane( tan e(p)tanep] (2. 27) and normalizing we have a density function for A 1 fA(A) = q[Q/q]e[- + (p - ) ][tan le(l-p)+ tan ep] e [Q/q]q (2. 28) for 0 < A < [Q/qlq for 0 >A > [Q/clq = 0 Although this appears to be rather complex it is simply of the form 1 2 aA + bA + c where the constants a, b and c are rather cumbersome. 38

This density function was purposely constructed so that changes in the program size Q produce reasonable changes in the density function fA(A). The assumption has been made that as the size of a program increases the size of the access loops increase proportionally. The inclusion of [Q/qlq, the number of bits associated with the process, in this function performs exactly that function. We may draw a graph to illustrate this. Figure 2. 7 shows what happened to the density function when the number of pages used by the program is doubled. Curve A depicts the density function for a program using [Q/ql pages. Here p =. 25 making the most frequent loop length 1/4 the size of the program. A program using twice as many pages 2[Q/ql but with the same p and e parameters would appear as curve C. Curve C may be obtained by B 0 q[Q/1q 2qFQ/q] A — The A Distribution Figure 2. 7 39

first making a simple linear scale change to obtain curve B and then normalizing to obtain curve C. There is another aspect of normalizing with respect to q[Q/ql which must be considered. The term q[Q/ql represents the apparent size of the program when the actual size is Q and the page size is q. Thus we see that the probability of a given loop length is affected by the page size. For instance if a program's actual size Q is "poorly" matched to the page size q the program will appear larger due to wasted space. We will assume that this wasted space is scattered at random throughout the programs virtual address space and thereby expands the length of loops being executed. This has one effect which must be corrected for. Earlier we said that the number of accesses made by a loop of length A traversed a times would be Aa/q' where q' is the word size. However the process of normalizing the distribution of A to the apparent size of the program means that loops contain wasted space which does not contribute to actual program accesses. In order to account for this wasted space contained in loops we will express the number of program accesses in a given loop as: Aur Q # of accesses = A (2.29) q' q[Q/ql The term Q can be recognized as the ratio between the actual q[Q/ql size of the program and the apparent size of the program. Including 40

this change the expressions for gl(A), gb(A), g2a( ) and 2b) become: (A a/q') (Q/qrQ/ql) gla(A) = (2.30) [A/ql[(1 - s qfQ/ql 1 1 + -- A/ql] 2[Q/ql 2rQ/ql for [A/ql < s/q for s < q[Q/ql a/q' = - -- O - = x0 = (2.31) for [r/ql < s/q and s > q[Q/q] (A a/q') (Q/qQ/ql) g lb(A) = (2.32) [A/qla - 1 — 2FQ/q1 (s2/q2 + s/q) for [A/ql > s/q (A a/q') (Q/q[Q/ql) g2a(A) = ([A/ql + ) [(1 - s qrQ/q] 1 1 - ) + - (rA/ql+ 1) ] 2[Q/ql 2[Q/ql (2.33) for [A/ql + 1 < s/q and s < qrQ/ql 41

= 00 (2.34) for [A/ql + 1 < s/q and s > qrQ/ql and (A a/q') (Q/qQ/ql) ' g2b(A) = (2.35) ([A/q] + 1) a- 1 (sq2 + s/q) 2rQ/ql for [A/ql + 1 > s/q 2. 6 Final Model Development We may express the expected value of g(A) as q[Q/ql E[g(A) =fq[Q/q o [g1(A)P(Case 1|A) fA(A) (2.36) + g2(A) P(Case 2 A) fA(A)]dA This integral must be divided into three separate integrals in order to accommodate the changes in functional representation which occur at A = qs[Q/q]- 1 and A = qs[Q/ql. Thus it will take the form (s-q) E[g(A)] = S [gla(A) P(Case IA) fA(A) + g2(A) P(Case 2 AfA(A) dA o s + S [gla(A) P(Case l|)fA(A) +g2b(A) P(Case 2|A)f(A) ]dA s-q q[Q/ql + [glb(A) P(Case 11A) fA(A) +g2(A) P(Case 21A) f(A)]dA ~~~s~~~~~~~~(2.37) (2.37) 42

The probabilities P(Case l|A) and P(Case 2jA) may be taken from Equation (2. 5). They are: P(Case 1 A) = [A/ql - A/q (2.38) P(Case 2 A) = 1 - [A/ql + A/q (2.39) We can at this point simplify our equations considerably. We will proceed by examining the terms in the above integrals in some detail. Beginning with the term in the first integral we will factor out fA(A) giving us [gla(A)P(Case 11A) + g2a(A) P(Case 21A)] fA(A) (2.40) Let us now consider the function g la(A) in some detail. Rewriting it (A a/q') (Q/qfQ/ql) gla(A) = (2.41) [A/ql[(l - s - - + [ A/q] 2[Q/ql 2[Q/q] for [A/ql < s[Q/q] and s # 1 Notice that between values where [A/ql changes abruptly gla(A) increases linearly with A. This is simply because only the numerator contains a A that is not in the form rA/ql and this is in effect multiplied times a constant except in the neighborhood of points where A/q is an integer. Thus we would expect a graph of gla(A) to be a series of straight lines connected by discontinuities. 43

The form of g2a(A) is the same as gla(A) except that rA/ql is replaced by rA/ql + 1. It should be clear that our comments about g1(A) also apply to g(A). Another most important characteristic of these two functions is that g2a(A) = lim gla(A + c) for A/q = integer (2.42) In Figure 2. 8 we show a graph of gla(A) and g2a(A) showing the characteristics we have just discussed. Next we would like to turn to a detailed examination of the term [gla(A) P(Case llA) +g2a(A) P(Case 2 1A)] (2.43) over a range of delta from nq to (n+l) q. Figure 2.9 shows three graphs one displayed a detailed graph of ga (A) and g 2(A) and two others showing P(Case I A) and P(Case 2jA) over the same range. If we examine these graphs and the term in question we can see that at a point just to the right of A = nq (or A = nq + c where e is arbitrarily small) the Expression 2.43 is equal to gl (A). Correspondingly at the other end of the range where A = (n+l)q the expression is equal to g2a(A). The value of the expression clearly begins on the left equal to gla(A) and progresses between the two function gla(A) and g2a(A) equaling g2a(A) at the page boundary. The expression is clearly never greater than g l(A) nor less than g2(A). 44

# of accesses # of page faults / 1 /, I. / / P i /,/ / I I/ I /, /,, / /, / 2a( 'g2a (z~) I V.. - -- nq (n+l)q (n+2)q (n+3)q as a function of A Figure 2. 8 45

# of accesses # of pagq faults r glR(A) I 1-11, I I W-.I -.-I -' I I I I J I I (n,+ll ga (h) and g2a(A) versus A 1 P(casel 0 P(case 1 A)|versus A 1 P(case 2.L[) 0 (n+l)q A' -r4 P(case 2 A) versus A The Components of H (A) Figure 2. 9 46

We will replace Expression 2.43 with the function (A a/q') (Q/q[Q/ql) Hi(A) = 1 (A/q + 1)[(1 -s 1 1 (A/q+ 1) qfQ/ql 2[Q/ql 2fQ/q] = 2qQ x (2.44) q? ( + q)(2(q[Q/ql- s) + A) We can recognize H (A) as g2a(A) where rf/ql has been replaced by A/q. Hi(A) is clearly an exact replacement for Expression 2.43 at page boundaries and is a smooth function which conforms to 2a() < H1(A) < ga(A). (2.45) Keeping in mind that we will be integrating the product H1(A) fA(A) it is clear that any errors introduced by the use of H1(A) are trivial when compared to the rather arbitrary choice of fA(A). If we examine the other two integrals of Equation 2. 37 we see that the situation in each is approximately the same. In each we have two functions which are straight lines between page boundaries and have discontinuities at the page boundaries. Figure 2. 10 shows the general form of the functions gla(A), g2a(A), glb(A) and g2b(A). In this plot we have plotted these functions over the ranges where they appear in the integrals of Equation 2. 37 in the case of s = 5q. Turning to the third integral of Equation 2. 37 we will replace the term 47

# of accesses # of page faults Hi(A) I H3(A) iIlb(a) / / ' / - ^ ^;/k' g.^ I 0 q 2q 3q 4q 5q 6q 7q 8q 9q lOq A --- — The Generation of Hi(A) Figure 2. 10 48

[glb(A) P(Case I|A) +g2b(A) P(Case 21A)] (2.46) with (A a/q')(Q/qQ/ql) H3(A) = (2.47) 1 2 2 (A/q+ - 1) (s/q +s/q) 2rQ/ql =- x Q A__ ql[Q/ql (A +(q - q (s2/q + s/q))) 2 arQ/ql The function H3(A) can be recognized as g2b(A) where [A/q] has been replaced by A/q. Again H3(A) is equal to the expression in question at page boundaries and satisfies g2b(A ) h(A) b() (2. 48) In the case of the second integral of Equation 2. 37 we will factor out the term [gla(A) P(Case 1IA) + g2b(A) P(Case 2 A)]. (2.49) This term combines both cases a and b and is illustrated in Figure 2. 10 in the range of A from 5q to 6q. We will replace this term with a straight line which connects the values of the term at the page boundaries. The general form of this approximation will be simply H2(A) = (slope) A + (constant). (2. 50) Since the value of H1(A) and H2(A) is exact at the page boundaries we may compute the slope as 49

H3(s) - Hl(s- q) slope = s - (s - q) H3(s) -H1(s- q) =(2.51) q and slope for the constant constant = H3(s) - (slope) s Expanding these terms we see that s(Q/qrQ/ql) 2 a Q (s - q) H2(A) = [( _ 2Q A q'(s + q -- q (s2/q2+ s/q)) q's(2(qrQ/q]- s) + s - q) L 2raQ/ql ((q - s) s) (Q/qrQ/ql) 2aQ(s - q) q'(s+ qq --- - s / q'(2(q /q q'(s + q - (sq2+s/q)) qt(2(q[Q/ql- s) + s - q) _ 2aQ/ql (2.52) We can now write E[g(A) ] using the approximating functions. E[g(A)] = 1 (2. 53) for 0 < s < q s-q s = f Hl(A)fA(A) dA+ s-qH2(A) fA() dA q+ Q/ H( (2.54) + H3(A)fA(A)dCA (2. 54) 50

for q < s < q[Q/ql = 00 (2.55) for s > q[Q/q] This integral is evaluated in Appendix A and the results follow: E[g(A)]= 1 (2. 56) for 0 < s < q E[g(A) ] = A1[K1 a- + s - q in (- -- )+ K2 n(al a2+ s - q a2 1 a3+ a (s-q) + K32 n (a 5 --- 3 2"5 -3 + a5(s-q)2 ) K3 a4 )qQ/qle[tan 1 e(s-q) + (K -3 2 a ) q[Q/q]e[tan (e(s-q) 5 q[Q/ql -ep)+ tan- (ep) ]] 2 1 a3+ a s + a5 s + A2[K5 -2 a n( 3 4 2) — 5 a3+ a4(s-q) + a(s-q) a(s-q) + 6(K6- K 2a4 )q[Q/qle[tan -l e ep) - tan1 (e(s-q) en]] ^5 q[Q/ql q[Q/q] a6 + q[Q/ql + A3[K7n( +s ) 1 a3+ + 8 2a5 in 5 4 q[Q/ql + a5 q2[Q/q2 a 4 s + a5 a3+ a4 s + a5 s a4 )- -1 es + (K - K 2 a5 )q[Q/qt e(-p)- tan- 9 ^5 slq[Q/q] - ep)]] (2. 57) 51

for q < s < q[Q/ql E[g(A)] = oo (2. 58) for s > q[Q/q] Where A i 2o(Q/[Q/q1 q' e[tan~ e(1-p) + tan (ep) ] e[tan e(Q-p)tanep) qrQ/qle[tan I e(1-p) + tan l(ep) ] (2. 59) (2.60) Q/q A =q 3 q'/qle[tan1 e(1-p) + tan -(ep)] a1= q a2 = 2(qQ/q] - s) 1 2 a3= 2 + P e 2p a =- 2 q[Q/ql 1 a5= 2 2 q 2[/ql2 (2.61) (2.62) (2.63) (2.64) (2.65) (2.66) a6 = q - q (s2/q2 2a[Q/ql + s/q) (2.67) 52

-a K = 1 2 (2.68) (a2- al)(a3- a4 al+ a5 al ) -a2 K2 = (2.69) (al- a2)(a3- a4 2+ a5 a2 ) K3 = -(K1+ K2) a (2.70) a3 a3 K =-K -K (2.71) 4 1 a1 2 a2 2aq[Q~/ql(s-q) K = - (2.72) q'(s + a6) sq'(a2+ s - q) (q - s) s 2aq[Q/ql(s-q) K = + (2.73) q'(s + a6) q'(a2+ s - q) -a6 K7 = (2.74) a3- a4 a6+ a5 a6 K8 = (2.75) a6 a3 K K = -K7 (2.76) K 7 a6 6 To begin, E[g(A) ] is the expected ratio between the number of accesses and the number of page faults or in other words the average number of accesses required to produce a page fault. Thus we may express the lifecycle function as a seven variable function 53

f(s,q',q,Q, a,p,e) = E[g(A)] (2. 77) Before continuing we would like to add one additional consideration. We will define H = the number of storage accesses between I0 interrupts. (2.78) Here 10 involves interaction outside of the storage system, possibly with a terminal user. The rate of 10 interrupts per access is then 1/H and the rate of storage interrupts will be. We E[g(A) ] may express the combined rate as Interrupt rate = + E[g(A) ] H (2.79) We may now write an expression for an eight variable function which includes I0 interrupts as life cycle 1 f(s,q', q,Q,,p,e,H) = (2.80) 1 1 E[g(A)] H where s = absolute allocation in bits < s q' = word length in bits 0 <q' < q q = page size in bits q'< q 54

Q = program size in bits 0 < Q = cycle repetition number (dimensionless) 1 < ar p = the normalized mode of the cycle length O< p< 1 e = a control of the A distribution 0 < e H = # of storage accesses between I0 interrupts 0 < H 2. 7 Examples of Model Behavior With Varying Allocation Here we want to study the lifecycle function and its behavior. We will consider a number of graphs of the function. To begin we will consider a specific case where: q' = 32 bits (a 32 bit word) q = 16384 bits (a 2048 byte or 512 word page) Q= 163840 bits (a 10 page program) 55

a= 20 (loops are accessed 20 times before a random jump) p=.5 (the most frequent loop length is 1/2 the length of the program size) e = 20 (the distribution of loop lengths has a moderately sharp peak) H = 4000 (Iom interrupts occur at a rate of 1 out of every 4000 accesses) These parameters were selected with two goals in mind. First reality and second a demonstration of functional behavior as we varied the parameters away from this "standard" case. Examining Figure 2. 11 we see a graph of this "standard" lifecycle function plotted as a function of the absolute allocation s. We may describe this graph in terms of three regions; the under allocated on the left, the fully allocated on the right, and the transition region in the center where we see that the lifecycle function grows rapidly with respect to allocation. 56

f(s,q',q,Q, a,p,e,H) 4000 -r 3200 2400 1600 800 0 0 40, 000 80, 000 120, 000 160, 000 allocation (s in bits) The Lifecycle Function Versus Allocation for the "Standard" Case Figure 2.11 57

In the under allocated region the mean number of accesses required to produce a page fault is most strongly affected by the page size q and the word size q'. In fully allocated region the number of times a loop is accessed before beginning a new loop, a, and the number of accesses per 10 interrupt, H, have the greatest consequence. The location and sharpness of the transition region is affected most strongly by the variables that control the loop length distribution p and e. In Figure 2.12 a graph is displayed showing the lifecycle function for three different values of p (normalized mode of the loop length). All the other variables are the same as our "standard" case just considered and the plot for p =. 5 is the "standard " case. Here we see that as we increase p and thus increase the length of the loops the transition region moves to the right or to a higher allocation. Likewise reducing the value of p reduces the allocation required to reach the transition region. In terms of the working set we could say that increasing p increases the size of the working set and decreasing p decreases the size of the working set. Turning to Figure 2.13 we also see a graph containing three plots of the lifecycle function. Here we have varied e which controls the sharpness of the distribution of loop lengths. Small values of e produce a broad distribution of loop lengths and large values produce a sharply peaked distribution with low variance. 58

f(s,q' q,Q,, p,e,H) 4000 T 3200 2400 1600 800 0 II a, ) 0 40, 000 80, 000 120, 000 160, 000 allocation (s in bits) The Lifecycle Function Versus Allocation With Variations in p Figure 2. 12 59

f(s, q', q, Q, u, p, e, H) 4000 - 3200 - 2400 1600 - 800 / I I I,, 0 40, 000 80, 000 120, 000 160, 000 allocation (s in bits) The Lifecycle Function Versus Allocation With Variations in e Figure 2. 13 60

Again we display the "standard" curve and two variations from it. The standard curve is in the center where e = 20. Here we see that the broad distribution of loop lengths in the case of e = 4 produce a wide transition region. In the case of e = 100 we have a sharper distribution of loop lengths and corresponding a sharper transition region. In terms of the working set, if the size of the working set is sharply defined we can expect a sharp rise in the lifecycle function when the allocation exceeds the size of the working set. Correspondingly if the size of the working set varies as the program is executed and has a broad distribution we can expect a broad to non-existent transition region. In the fully allocated region the two variables H and or have a large effect. In Figure 2. 14 a graph is shown with three plots of the lifecycle function. Here we have varied H, the number of accesses between I0 interrupts. The "standard" curve is as usual in the middle where H = 4000. The effect of varying H can be dramatic but is generally predictable. Notice that in the case of H = 8000 the curvature in the fully allocated region is different from the other two cases. In Figure 2. 15 we show a case which is "standard" except that H = co. Notice here both the scale of the graph and the distinct change in curvature. Figure 2. 16 shows a graph of three cases where c = 20 is the "standard" case. If we disregard the effects of I0 interrupt 61

f(s, q', q, Q,p, e,H) 8000 - 6400 4800 3200 - 1600 - Or 0 40, 000 80, 000 120, 000 160, 000 allocation (s in bits) The Lifecycle Function Versus Allocation With Variations in H Figure 2. 14 62

f(s, q', q, Q, a, p, e, H) 40, 000T 32, 000 24, 000 16, 00 8, 00 0 -- _ I 0 40, 000 The Lifecycle 80, 000 120, 000 160, 000 allocation (s in bits) Function Versus Allocation for H= oo Figure 2. 15 63

f(s,q',q,Q,ca,p, e,H) 4000 T 3200 2400 1600 800 0 0 40, 000 80, 000 120, 000 allocation (s in bits) The Lifecycle Function Versus Allocation With Variations in a Figure 2.16 160, 000 64

we would expect that changes in the lifecycle function in the fully allocated region would be approximately equal to changes in a. However in this case these changes are suppressed by the I0 interrupts. In fact since H = 4000 the lifecycle function cannot exceed 4000. The variables a and H cannot be described in terms of the working set concepts. Both a and H describe what happens when we do allocate sufficient space for the working set. Figures 2. 17 and 2. 18 show the effect of changing the word, q', and page, q, size. In general increased word size means a decrease in the lifecycle function. In the case of page size, an increased page size results in an increased lifecycle function. Great caution must be exercised in the interpretation of either of these results. In the case of page size, q, we are considering here pages which are exact divisors of the program size resulting in no wasted space. Also the three page sizes used here are considerably smaller than the allocation s. The effects of varying page size will be examined in considerable detail in the following pages. In the case of word size, q', the effects on the lifecycle function are representative but changes in word size are accompanied by other important system changes. For example we would expect the useful work per access and the number of accesses between I0 interrupts to change. The important point here is that the lifecycle function is a function of word size. 65

f(s, q', q,Q,, p, e, H) 4000 -- 3200 — 2400 1600 -800 0 0 40, 000 80, 000 120, 000 160, 000 allocation (s in bits) The Lifecycle Function Versus Allocation With Variations in q' Figure 2. 17 66

f(s, q', q, Q, a, p, e,H) 4000 3200 2400 1600 800 0. 0 40, 000 80, 000 120, 000 160, 000 allocation (s in bits) The Lifecycle Function Versus Allocation With Variations in q Figure 2.18 67

2.8 Example of Model Behavior With Varying Page Size We will now consider the effect of varying the page size, q, in detail. The graph of Figure 2. 19 displays the lifecycle function as a function of page size. This represents the "standard" plot from which we will make variations. In our previous "standard" there was obviously no need to specify s as there is no need to specify q here. This "standard" here is identical to the previous standard except that we have chosen s = 122880. This means that the allocation is 3/4 of size of the program. This places us in a rather well allocated region or we might say that this is sufficient allocation to get the working set in core. We will divide the graph of Figure 2.19 into three regions. On the left the life cycle function rises sharply with page size. We will refer to this region as the initial region. In the middle values of page size we see a sawtooth-like variation which increases with page size. We will refer to this region as the sawtooth region. On the right beyond a page size of 122880 bits we see a region where the value of life cycle function is suppressed. We will refer to this region as the suppressed region. Beginning again on the left in the initial region we see a sharp rise in the value of the life cycle function with increasing page size. In this region of very small page sizes the life cycle function is dominated by the necessity to bring in an enormous number of 68

f(s, q', q, Q, T, p, e, H) 4000 T 3200 2400 1600 800 0 0 40, 000 80, 000 120, 000 160, 000 Page Size (q in bits) The Lifecycle Function Versus Page Size for the "Standard" Case Figure 2. 19 69

pages every time any new information is needed. In the case of a 32 bit page (the smallest value calculated here) the page and the word size are equal. Thus every time a new loop is started almost as many page faults will occur as there are words in the loop. In this case we have a 32 bit page, a 32 bit word and we access each loop 20 times, a = 20. Thus we will get somewhat more than 20 accesses per page fault. The "somewhat more" is the result of finding desired pages in core from previous loops. As we increase the page size farther the general shape of the curve begins to flatten out and a sawtooth variation appears. The sawtooth variation is caused by the discrete size of the pages. The peaks of the sawtooth represent page sizes for which some exact multiple of pages is equal to the size of the program. As we increase the page size from one of these peaks we see that the apparent size of the program increases. That is the program is spread out by the inappropriate page size and consumes more space. As we further increase the page size we reach another "perfect" fit and the value of the life cycle function again peaks. If we increase the page size farther we reach a point where the page size exceeds the allocation. In this case this occurs at q = 122880 bits. From this point on the value of the life cycle function is suppressed and the program behaves as though it were severely under allocated. Notice that in these graphs the page 70

size runs from the word size to 10% larger than the actual program. Turning to Figure 2. 20 here we see the effect of varying the I0 interrupt rate. The "standard" curve is shown in the center where the value of H is 4000. In Figure 2. 21 we see the relative value of the life cycle function when H = oo and H = 4000 (the "standard" curve). The curve of Figure 2. 21 with H = oo demonstrates an effect of page size which has been evident but not pronounced in the previous graphs. Let us consider the value of the life cycle function when the program size is multiple of the page size. That is at the peaks of the life cycle function. Notice that in the sawtooth region the value at the peaks first increases and then decreases. The increase can be explained easily as an extension of the behavior in the initial region, however the decrease has yet to be examined. Considering this specific case we see that with a page size of 81920 bits we have a two page program. Likewise with a page size of 54614 bits we have a three page program and with a page size of 40960 bits we have a four page program. Notice that each of these page sizes "fits" the program either exactly or almost exactly. However in the case of the two page program only 1 of the two pages or 1/2 of the program can be allowed in core since the allocation is 3/4 of the total size of the program. Correspondingly, 71

f(s, q', Q,, p, e, H) 8000 T 6400 4800 3200 1600 0 H = 8000 0 40,000 80,000 120,000 Page Size (q in bits) The Lifecycle Function Versus Page Size With Variations in H Figure 2. 20 160, 000 72

f(s, q', q, Q, c, p, e, H) 40, O00 32, 24, 16, 8, 4000 0 0 40,000 80,000 120,000 160,000 Page Size (q in bits) The Lifecycle Function Versus Page Size for H = oo Figure 2.21 73

in the case of the three page program we can keep two pages in core using 8/9 of the allocation and in the four page program we can use all of the allocated space. Thus in addition to the effects of "fitting" the program size we have some effects involving "fitting" the allocation. Before going on to other graphs notice that the 10 interrupts are a major factor in the "standard" lifecycle function we have chosen and this will reduce some of the effects that we will observe as we proceed to examine changes in other variables. In Figure 2. 22 we show the effect of varying the allocation s. Here our "standard" curve is the upper curve where s = 122880. There are several notable effects of changing s. First as we reduce the allocation we see the expected reduction in the value of the life cycle function. We also see that the suppressed region extends further to the left. That is, the page size exceeds the allocated space sooner. Notice that in the case of s = 40960 bits the program is under allocated and appears suppressed over the entire range of page sizes. The effect of not having the working set in core (i. e. most loops bigger than the allocation) is similar to the effect of the page size being larger than the allocation. As we change the allocation we see a marked change in the curvature of the life cycle function between peaks in the sawtooth 74

f(s, q', q, Q,, p, e, H) 4000 T 3200 2400 1600 800 s = 122880 bits 0 0 40, 000 80, 000 120, 000 160, 000 Page Size (q in bits) The Lifecycle Function Versus Page Size With Variations in s Figure 2.22 75

region. When we move from one peak to another increasing page size we are in effect expanding the apparent size of the program, an thus reducing the relative allocation. As we change the value of the absolute allocation s we are in effect picking a different point on the life cycle function versus s curve. We can think the variation which occurs between peaks in the sawtooth region as roughly corresponding to a variation in the allocation in the life cycle function versus s curve where an increased page size corresponds to decreased allocation. Thus when we choose s in a concave region of the life cycle function versus s curve we can expect a tendency for concave behavior between peaks in the sawtooth region and vice versa for s chosen in convex regions of the life cycle function versus s. Turning to Figure 2. 23 we see a graph displaying three plots where we have varied the size of the mode of the loop length or in effect the working set. The "standard" curve is in the center where p =. 5. Notice that the beginning of the suppressed region is the same for all cases. Here we see again large changes in the curvature. Notice also that the largest p, or mode of the loop size, represents a loop size. 7 times the length of the program. In all of these cases we have an allocation of 122880 bits or. 75 times the length of the program. Thus we do not show a sharply under allocated situation. 76

f(s,q',q,Q,, p,e,H) 4000 T 3200 2400 1600 800 0 0 40, 000 80, 000 120, 000 160, 000 Page Size (q in bits) The Lifecycle Function Versus Page Size With Variations in p Figure 2. 23 77

f(s, q', q, Q, a, p, e, H) 4000 T 3200 2400 1600 800 0 0 40, 000 80, 000 120, 000 160, 000 Page Size (q in bits) The Lifecycle Function Versus Page Size With Variations in e Figure 2. 24 78

In Figure 2. 24 we show the effects of changing e. Here the "standard" curve is shown with e = 20. It is interesting to compare these curves of Figure 2. 13. Note that the cross over points between peaks in the sawtooth region of Figure 2. 24 correspond to the cross over point in Figure 2.13. In Figure 2. 25 we show the effect of varying a. The curves are rather simple and show an increase over all regions except the suppressed regions. Figure 2. 26 shows the effect of varying the word size. Changes in word size cause a change in the lifecycle function which is rather uniform over all values of page size. 79

f(s, q', q, Q, o, p, e, H) 4000 T 3200 2400 1600 800 0 0 40, 000 80, 000 120, 000 160, 000 Page Size (q in bits) The Lifecycle Function Versus Page Size With Variations in a Figure 2. 25 80

f(s, q', q, Q,, p, e, H) 4000 T 3200 2400 1600 800 0 0 40, 000 80, 000 120, 000 Page Size (q in bits) The Lifecycle Function Versus Page Size With Variations in q' Figure 2. 26 160, 000 81

Chapter 3 Macroscopic Model The purpose of this chapter is to discuss a macroscopic model which relates the program behavior discussed in the previous chapter to storage delays, page size, data routings, CPU execution rate and the number of programs being multiprogrammed. Taking all of these factors into consideration we will develop a solution for the average system throughput, that is, the average rate at which user induced accesses are processed. 3. 1 The N Level Hierarchy We will now turn to considering the meaning of the lifecycle function in an N level hierarchy. To begin we will consider only variations in the allocation s and thus we will write the lifecycle function as f(s). We will also ignore 10 interrupts for the time being thus we may assume H = o. When treating an N level hierarchy we see that the case of N = 1 is degenerate and the case of N = 2 is the type of system we have assumed up to this point. Thus our focus here will be on N > 2. For examples we will work with N = 4. The choice of N = 4 is attractive in that it is large enough to demonstrate all the complexities. of hierarchies where N > 4 and yet it is small enough to be convenient 82

for discussion. Let us consider the 4-level hierarchy shown in Figure 3. 1. CPU A Possible Implementation thin film (i.e. cache IBM 360/67) L1 I s core(s) s [ ----..-. -- ~ J 12 drum(s) 3 s disk(s) L 4 s4 A Four Level Hierarchy Figure 3. 1 Here we have shown a CPU and 4-levels of storage and on the left a feasible set of devices is given. It should be clear that program information will migrate up and down in these 4 levels in much the same manner as a 2-level system. 3.2 Storage Allocation When considering a system with N > 2 certain new questions arise concerning the allocation of storage space. First we must allocate storage at several levels rather than just core and drum. We must be more precise in stating exactly what is stored where. 83

We may resolve the first question as it relates to the model by simply supplying the variable s with a subscript. Thus we will define Si as the storage allocated to a process at level i. Figure 3. 1 shows this vector as si' s associated with the 4-level hierarchy. The second question is a bit more complex. Exactly what is stored where? We will follow the following convention: If the current copy of some process information is resident at level k then a specific space must be reserved for this information at all lower levels (i. e. levels i where i > k). This space may or may not contain a current copy of the process information. As a direct result of this convention we may state: i < Si+1 (3.1) and n >Q (3.2) where Q = total size of a user program or process. Notice that si represents not only the storage allocation at level i but also the amount of unique current information stored at and above level i. This, of course, is not the complete answer to what is stored where but it will suffice for now. Relative Access Rates In a 2-level hierarchy a single page fault always generates a one page transfer from the lower to the upper level. In a multi-level 84

system a single page fault may cause many transfers to occur. We must then be more precise in defining the relationship between page faults and data transfers. We will introduce the notion of user program accesses. User program accesses are generated by storage accesses in executing user programs. The user program access will always be to the highest level of the hierarchy containing a current copy of the required information. When a user program makes an access the resultant transfer of information may be very complex involving many levels and both upward and downward transfers. A user program access as we will use it here does not imply a specific transfer but rather simply indicates that the user program requires certain information. We will discuss the transfers which result from a user program access in detail later in this chapter. Our immediate concern here will be the fraction of user program accesses made to individual levels of the hierarchy and how this is related to the lifecycle function of the user program. Let us begin by determining what fraction of all accesses made by X process are made to level 1. Recalling that sI is the storage allocation at level 1 from the definition of f(s) (recalling that we are representing the entire lifecycle function as f(s)) it is clear that the average number of accesses required to produce a primary access below level 1 will be f(sl). Thus the fraction of accesses which fall below level 1 will be f and the fraction of access to level 1 is simply 1 -f This general approach tion of access to level 1 is simply 1 -fj-l. This general approach 85

may be taken at all levels. Sg__ --- s1 1. --- -........ s3 CL,.... _.... 1 f(s 0) 1 f(s1) # of primary access below level 1 1 f(s2) 1 f(s3) -f^ 3f 1 f(sA) Access Distribution Figure 3.2 Since si is not only the storage allowed at level i but the total unique storage allocated at level i and above, the fraction of accesses falling below level i will be f(si). This relationship is depicted in Figure 3. 2. The fraction of primary accesses, to any given level i may be expressed simply as 1 1 ui~fsi1-. (3.3) where 1 = f =(s) 1 At this point we have expressed the fraction of primary accesses to each level in the hierarchy as a function of the storage allocation. More precisely the fraction of primary accesses to 86

any specific level is only a function of the allocation at that level and the adjacent higher level. Paging It is our intention to extend the basic concept of paging to an N-level hierarchy. Such an extension is not trivial and requires an explanation. What follows is a description of how paging is carried out in such an extended system and how this system is modeled. Record Size Constraints Up to this point we have ignored the effects of record (or page) size. Here we will consider how record sizes affect data transfers in the system. We will begin by assigning a variable qi to each level of the hierarchy and enforcing the following constraint: qi+l = ni qi where n. = positive non-zero integer. In our model we will treat the qi's as variables and they may in turn control the paging behavior of the system. Information Movement We will begin to examine the paging process by considering an example. Figure 3.3 shows a 4-level hierarchy along with a specific set of qi's and n's. Now suppose an executing process attempts to read a word of information from memory and the most convenient copy is at the bottom of the hierarchy, i. e. level 4. This is simply 87

To CPU P=^ - _.... Level 1 q= 32 n =4 Level 2 q = 128 2 n2 =8 Level 3 q3 = 1024 n = 4 t q1 bits J I\ q bits 00 00 Level 4 q4 = 4096 n4 undefined 4 I I q4 bits - I' tI I Multilevel Paging Figure 3.3

a user program access to level 4 of the hierarchy. It is then necessary to "page this information upward in the hierarchy. "Paging" may be carried out as follows. 1. A copy of the record containing the accessed word at level 4 of size q4 = 4096 bits will be read from level 4 into level 3. At level 3 this will form 4 records (n3) of 1024 bits (q3) each. 2. A copy of the level 3 record (1024 bits) containing the accessed word is read from level 3 to level 2. At level 2 this will form 8 records (n2) of 128 bits (q2) each. 3. A copy of the level 2 record (128 bits) will be read from level 2 to level 1. At level one this will form 4 (n.) records (or words) of 32 bits (q1) each. 4. A copy of the 32 bits (q1) accessed is read from level 1 to the CPU. (Note: the CPU will be referred to where convenient as level 0.) User program accesses to levels above 4 may be paged in much the same manner with the exception that lower levels are not disturbed. There are several aspects to this description of paging one of which will be taken as a fixed part of the model and others which may vary. As to the fixed part of the model we will assume that the final disposition of all the upward paged information will be the same 89

as the final disposition in the example. That is each level i above the level of user program reference will acquire n. new records of size qi. These n. records will contain the information contained in the single 1 record of level i + 1 which includes the primary user program access. Notice that we are not saying anything about how or what path the information follows in order to reach its final goal. We are only fixing the eventual distribution of the information involved in a paging operation and even this remains a function of the qi's. Let us consider a few examples which demonstrate different data paths. We may for instance choose to transfer qi bits directly from the level of user program access to the CPU (level 0) eliminating the transfer from level 1 to CPU leaving other transfers the same. This would be similar to the cache core relationship of the IBM 360/85 F18]. Another possibility would be to transfer a record from the level of primary access to level 1 and then transferring the appropriate parts of that record to the other levels. This in effect uses level 1 as an interlevel buffer. This may or may not be a wise choice but it is interesting to note that the architecture of the IBM 360/67 [30] is limited to this kind of transfer pattern. It is important to note that the question of what data paths and combinations of transfers are best can be explored since this will be a variable in the model. variable portion of the model is discussed later. We will now expand our representation of the lifecycle function from f(si) to f(si,q i+) including the pages or record size as a 90

variable. Applying this new form of the lifecycle function the fraction of primary accesses to any given level i (u.) previously given in Equation 3. 3 we have u.= 1 _ 1 for i=1, 2,..., N (3.4) f(si- 1' qi) f(si'qi+l) where 1 -l f(so, q1) and 1 O - 0 f(SN, qN+1) 3. 3 Multiprogramming Here we will consider the formal representations required to represent a program in a multiprogrammed environment. We will begin by providing the lifecycle function with an index allowing each process a distinct lifecycle function fh(si, h' qi+l) where h is an integer that satisfies 1 < h < M representing M distinct processes and i is an integer that satisfies l<i< N representing N levels of storage and where si h = Total quantity of user program h information at and above level i Notice that in addition to giving each process a distinct lifecycle function fh( ) we now represent the allocation of each process at 91

each level in the hierarchy si h. This allocation can be conveniently expressed as an Nx M matrix S. s1,1 S1 2 - S1,M 2, 1 S2,2 2 — 2,M S = 1 (3. 5) 1 | I _SN, 1 SN 2- SN, M th The elements in the k row of the matrix represent allocations th at the k-level in the hierarchy. Elements in the kth column represent the allocation of the k user program. Thus we may write M Si = Si (3. 6) j=1 I h where s. is the total storage allocation at level i. From Equation 3. 1 we may write S < si+ h (3.7) 1i,h - i+1,h and NY Qh (3.8) SN, h > Qh8) where Qh is the total size of the process h. We may also redefine ui so that individual processes may be identified. Thus: u (3.9) Ui, h= lh (3. 9) f(si-l, h' qi) fh(six h' il) 92

where 1 _ 1 fh(so, h' i and 1 0 fh(SN, h' qN+1) This comes directly from Equation 3.4 and represents the fraction of primary accesses to any given level i by process h. Later in this chapter we will treat the first L levels of storage in a special manner. This will have an effect on the value of ui and u h in the first L+1 levels of storage. We mention this here only i, h to point out that Equations 3.4 and 3.9 will be slightly modified at a later time. 10 Interrupts Thus far we have ignored 10 interrupts in N-level hierarchies. When I0 interrupts are to be considered they will be treated as accesses to the Nth level in the hierarchy where the N level will act as a pseudo storage level. Notice that if we constrain the allocation in the (N-l)th level of storage such that SN-1,h> h (3.10) the fraction of "accesses" to the Nth level (ui h of Equation 3.9 or u.i of Equation 3. 4) will be the fraction of all interrupts (page fault 93

and 10) which are 10 interrupts. We will consider the role of the pseudo Nt level of storage as we proceed. 3. 5 Interlevel Data Traffic We will now consider a mathematical model which relates user accesses and the flow of data between levels. We will begin by defining t., i an element of the 4-dimensional array T. j, k, i,.i tj k, i = the number of records of size qk read or written at level j as a result of a user read (f=0) or write (f=1) to level i. (3.11) where j, k, i, and I are integers satisfying 1< j < N 1<k< N 1<i< N and = O or 1 Let us consider an example. Earlier we considered a specific set of transfers which would achieve the necessary disposition of information in a 4 level hierarchy. This pattern of transfers was shown in Figure 3. 3 and described in detail in the associated text. 94

Notice that all transfers in this scheme are carried out between adjacent levels. Let's begin by considering the traffic caused by a user program access to level 4. Figure 3.4 shows the transfers which occur. To the left, with solid lines, of the hierarchy the "page up" transfers are shown as described earlier. On the right the page down transfers are shown using dashed lines. The page down transfers are dictated by the need to maintain a balance of transfers in or out of any level. q2 q3 q4 Figure 3.4 Traffic - Primary Read to Level 4 Here we are considering a user read to level 4. Thus we have fixed the i and f of t k, i to 4 and 0 respectively. The nonzero 3, k, i, y. 95

value s of t k 4 0 are j, k, 4, 0 Level 1 traffic (j = 1) t 1 1,1,4,0 1,2, 4, 0 indicating 1 record of size ql and 2 records of size q2 Level 2 traffic (j = 2) 2,2,4,0=2 t2,3,4,0 2 Indicating 2 records of size q2 and 2 records of size q3. Level 3 traffic (j = 3) t3 3, 4, 0 2 3,4, 4,0 2 Level 4 traffic (j = 4) ^ ' 2 t44, 4, 0 = 2 Noticing that fixing the values of i, the level of the user access and l, indicating a reador write user access leaves us with an N by N matrix ti, of terms tjk=tj ki, (3.12) There will be 2N such t matrices each of which describes the traffic in the system which results from each of the 2N possible user access types. 96

READ (2 = 0) Records of Si q1 q2 q 1 1 *0 a ize (k) WRITE ( =1) Traffic at Level (J) 2 3 4 1 2 3 4 q q2 q * * 1 2 2 * 2 * * 1 2 3 4 1 2 3 4 L * q1 q2 q * * 1 2 2 * * * * q q2 ( *: 1 2 * ' 2 * * 3 4 User ql q2 q3 q4 - Access. to Level 1 1 13 q4 ql q2 q3 q4 i=2 2 2 3 4 13 q4 q1 q2 q3 q4 *. _ User... Access 1 1 2 to Level 3.. 2 i=3 2 2 2 2 3 2 4 q3 q4 q q2 q3 q4 q3 <l4 1 2 93 4 User Access 11 2 to Level 4 2 i4 2 2 2 2 2 3 2 2 0 02 2 4 2 Figure 3. 5 T Array for Example 1 97

In the case of our example we have 4 levels (N=4) and therefore 2N or 8 t matrices each of which is 4 by 4 or contains 16 t. elei, B jLk ments. These matrices for the example in question are shown in Figure 3. 5. The elements, t, k of these matrices may be determined by simply drawing the transfers which result from a specific user read or write as done in Figure 3.4 and then summing the number of records of a given size qk read or written at a given level j giving us the element tj k. The 8 ti e matrices for this example are shown in Figure 3. 5. It is noteable that in this example and several to follow there is no difference between a user read or write. We will consider an example later where this is not the case. Let us consider a second example. Here we will consider a case where all data transfers must be in or out of level 1. This situation was mentioned earlier. Let us begin by looking at the transfers which result from a primary read to level 4. These transfers are shown in Figure 3. 6 It is important to understand clearly what is meant by page up and page down transfers when examining Figure 3.6 since some of the page up transfers are actually moving down in the hierarchy and some page down transfers are moving up. Page up transfers are those transfers which occur directly as a response to a user access. Page down transfers occur in response to the need to maintain a balance of incoming and outgoing records at each level. In a user read to level 4 the following transfers take place: 98

\ \ i\ \?! I Ax l l \q4 \ \" 'x q / / _.. — Level 3 q3 q4 Page Up Transfers Page Down Transfers ------------- Transfer Pattern 4-Level Hierarchy for User Induced Level 4 Read Figure 3. 6 99

Page up transfers 1. A copy of the record at level-4 containing the desired information is read from level 4 to level 1 a transfer of q4 bits. 2. A copy bf the level 1 record containing the desired information is read from level 1 to level 0 (the CPU) A transfer of q bits. 3. A copy of the level 3 record containing the desired information is read from level 1 to level 2. A transfer of q3 bits. 4. A copy of the level 4 record containing the referenced information is read from level 1 to level 3. A transfer of q4 bits. Note: a. 2, 3, and 4 above may occur in any order or in parallel. b. Only space for a level 2 record is allocated at level 1. That is after serving as a buffer for the above transfers only the level 2 record containing the primary reference is preserved. Page down transfers 5. A level 4 records is read from level 3 to level 4 passing through level 1. a. A q4 bit transfer from level 3 to level 1. b. A q4 bit transfer from level 1 to level 4. 100

6. A level 3 record is read from level 2 to level 3 passing through level 1. a. A q3 bit transfer from level 3 to level 1. b. a q3 bit transfer from level 1 to level 3. 7. A level 2 record is read from level 1 to level 2. Figure 3. 7 shows the transfers for user reads to levels 1 through 3. Here as before page up transfers are indicated by solid lines and page down transfers are shown as dotted lines. The diagrams for user writes would be the same except for a transfer from level 0 to level 1 of size ql rather than the ql transfer shown. The traffic matrices for this example are shown in Figure 3. It is interesting to note that for a hierarchy limited to 2 levels both of the examples that we have discussed are identical. However for the N-level hierarchy where N is large the traffic in and out of level 1 is much greater in the second example. 3. 6 Primary and Secondary Levels of Storage There is a distinction which can be made between the levels of storage which is only meaningful in a multiprogrammed environment. This distinction is based on the question of how far down in the storage hierarchy can a user program make accesses without loss of the CPU. We will refer to the upper levels of the hierarchy as primary levels and the lower levels as secondary. We will define K = Number of primary levels of storage 101

q3 q2 q3 CPUl * Level 0 q1 - Level 1 Level 2 Level 3 Level 4 Primary Read To level 1 Level 4 Primary Read To level 3 Level 3 Level 4 Primary Read To level 2 Page Up Page Down ---- Traffic Diagrams Figure 3. 7 102

READ (I = 0) Records of Size (k) ql q2 q3 q4 1 1 2 3 4 * *0 Is - WRITE (Q = 1) Traffic at Level (j) 1 2 3 4 1 2 3 4 ql q2 1 2 L 2 2 I1 91 1 q3 q4 q3 q4 4 2 2 * User Access to Level 1 i = 1 User Access to Level 2 i=2 User Access to Level 3 i=3 1 2 3 4 1 2 3 4 1 2 3 4 L ql q2 q3 q4 1 2 2 L * _ ql q2 q3 q4 1 1 4 1 2 2 I ql q2 q3 q4 1 a. *.. *.. * _ 1 1 2 3 4 ql q2 1 1 1 q3 q4 q1 q2 q3 q4 3 4 1 1 3 4 User 2 Access 2 1 2 *. to Level 4.. 1 2 4 3 1 2 2 4 2 Figure 3. 8 T Array for Example 2 1C3

where K is an integer satisfying 1 < K < N recalling that N is the total number of levels in the system. We will now be treating a more general case where access to level K and above may cause delay in a user program's execution but will not cause the program to lose the use of the CPU. User accesses below the level K will cause program interruption and will release the use of the CPU to other programs in the system. Let us consider an example where N = 4 and K = 2 as shown in Figures 3.9 through 3. 13. Here we have designated the device type at each level as shown in Figure 3.9. We will transfer data in the primary levels only between adjacent levels as in an earlier example. User accesses to secondary levels will cause transfers as in the previous example but here the core at level 2 will be used as a buffer. Figures 3.9 and 3. 10 show the transfers which result from user reads to the primary levels. User writes would result in a similar pattern differing only between the CPU and level 1 where we would write at level 1 rather than read. Figures 3. 11 and 3. 12 show the transfer patterns for user accesses to secondary levels. Notice here that the upward movement of data stops in this example at level 2. This is because we have assumed in this example that level 1 is completely allocated to the program using the CPU. Thus in this example user programs accessing a secondary will lose all the allocations at level 1. This means that when programs are restarted they begin by accessing level 2 and have 104

thin film r CPU Level 0 I CPU \ Level 1 core drum ql Primary Level 2 Primary 0 Cn rr CI rrr. ~3 -- i J Primary Levels K =2 Level 0 Level 1 q Primary Level 2 Qa r Primary _J I I q aT -. 1 10 disk Level 3 Secondary Leveal r q3 Secondary Secondary Levels Level 4 Secondary Level 4 q4 Secondary Example 3 Read to Level 1 Figure 3.9 Example 3 Read to Level 2 Figure 3.10

CPU Level 0 CPU Level 0 Level 1 ql. Primary Level 1 Primarv Level 2 q2 Primary 0' 0a q33 _ T. q Level 3 q3 Secondary Level 2 Primary \|. Level 3 q4 Secondary Level 4 Secodar Secondary Level 4 q Secon4lary Example 3 Read or Write to Level 3 Figure 3.11 Example 3 Read or Write to Level 4 Figure 3.12

Traffic at Level (j) 1 2 3 4 READ (2 =0) Records of Size (K) ql q2 q3 q4 1 q1 q2 q3 q4 1 2 2 ~ ~ User Access to Level 1 i = 1 User Access to Level 2 i =2 WRITE ( = 1) 1 2 3 4 1 2 3 4 ql q2 q3 q4 ~ ~ 1 ql q2 q3 q4 1 2 2 a * 0 1 2 3 T 4. Primary. *. J Secondary q q q 1 2 3 4 I F / 0 L. * -j q q2 q3 q4 r *. 1 2 3 4 2 2 2 User Access to Level 3 i=3 1 2 3 4 0 a~~ L- * * q q, q2 q3 q4 2 2 * * 1 * 4 q2 q3 q4 ' * 1 ' 4 ' 1 * 2..1 2 r-.- ~ 1 2 3 4 1 4 1 2 2 User Access to Level 4 i=4 1 2 3 4 Figure 3.13 T Array for Example 3 107

an initial transient period of paging in the primary levels. The ti matrices for all possible user accesses are shown in Figure 3. 13. 3. 7 Dedicated and Shared Levels of Storage At this point we would like to formalize this concept of entire levels of storage being dedicated to the program using the CPU by defining L = Number of levels of CPU dedicated storage (3.13) where L is an integer satisfying 0 < L < K recalling that K is the number of primary levels of storage. The restriction that L < K is required to avoid a situation where every user program being restarted would immediately make an access to secondary storage and thus be interrupted. The Model 85 Motivation for considering systems with K > 1 is in part based on the apparent success of the IBM 360/85 which has two levels of primary storage (K=2). The level 1 storage of the Model 85 is thin film and is dedicated to the program using the CPU (L=1). Because of the interest generated by this particular design as well as its relevance to this work we will consider a Model 85 like situation where we have added 2 additional levels of storage, a drum and a disk, and assumed a virtual addressing feature as on the IBM 360/67. Figure 3. 14 shows the transfer path for a read to level 1. Constrasting this to the write to level 1 shown in Figure 3. 15 we can 108

ql CPU Level 0 CPU Level 0 I ___ 1 --— I I I thin film Levei I Primq Primary Level 1 ql Primary.. Jb. ql core Level 2 q2 Primary Level 2 q2 I Primary Co rw __ drum disk Level 3 q3 Secondary Level 3 Secodary Secondary Level 4 q q4 Secondary Level 4 q4 Secondary Example 4 Read to Level 1 Figure 3.14 Example 4 Write to Level 1 Figure 3.15

CPU Level 0 Level 1 q Primary Level 2 q2 Primary,I. 0 Level 3 Secondary Level 3 q3 Secondary Level 4 Secondary Level 4 q Secndary Example 4 Read to Level 2 Figure 3.16 Example 4 Write to Level 2 Figure 3.17

see that there is a considerable difference between reads and writes to level 1. This difference is a result of the fact that a current copy of the contents of level 1 is always maintained at level 2. This means that there will never be an occasion necessitating the actual paging down of records from level I to level 2 in order to make room for records being paged up, When space at level 1 is required it is simply released to the new record since a current copy is always maintained at level 2. Figure 3. 16 and 3. 17 show the transfer patterns of a read and a write to level 2. The read and write differ here also in that a read to level 2 causes information to be moved up to level 1 (64 bytes in the model 85) and a write does not. The transfer patterns resulting from user accesses to the secondary levels are shown in Figure 3. 18 and 3. 19. Here we see patterns similar to these discussed before and more typical of a IBM 360/67. The traffic matrices ti. for all user accesses are shown in Figure 3. 20. Notice here that the user read (Q=0) and use write (f= 1) matrices differ. 111

CPU Level 0 CPU Level 0 I- - -- -- - - I Level 1 ql Primary Level 1 ql Primary,., ND0 q - Level 2 q2 Primary ~I~ rrr - II~ - - \N I Level 3 q3 Secondary Level 4 q4 Secondary Example 4 Read or Write to Level 3 Figure 3.18 Example 4 Read or Write to Level 4 Figure 3.19

READ ( =0) Records of Size (K) ql q2 q3 q4 1 _ * * WRITE ( =1) User Access to Level 1 i= 1 Traffic at Level (j) 1 2 3 4 1 2 ql q2 q3 q4 1 - ~! 1 2 1' 3 Primary 4 Secondary 1~ 1 2 3 4 1 2 3 4 ql q2 q3 q4 ql q2 q3 q4 * * 1 i321 Ii=2 2 1 3 4 q1 q2 q3 q4 q1 q2 q q4 1 2 i=3 2 2 2 3 2 4 ql q2 q3 q4 r 1 4 i=4 1 2 2 gure 3.20 Array for Example 4 Figure 3. 20 T Array for Example 4 1 2 3 4 ql q2 q3 q4 * * 1 4 * * 0 I 1 2 2 * * - 113

Regions of Storage Figure 3. 21 shows a general storage hierarchy relating the variables L, K, N and the terms dedicated, shared, primary, and secondary. Recalling that Dedicated levels are completely allocated to the user program currently executing. Primary levels are those to which an access may be made without causing an interrupt terminating the current users use of the CPU. Secondary levels are those which if accessed cause a user program to lose the use of the CPU. There are three basic regions of interest. They are: 1. Dedicated (levels 0 through L) 2. Shared Primary (levels L + 1 through K) 3. Secondary (levels K + 1 through N) These three regions are of special interest because the data traffic in each is based on different factors. In the dedicated region all traffic is directly the result of the currently executing program. In the secondary levels the traffic is the result of the entire collection of programs being multiprogrammed. In the shared primary region the traffic is affected by both factors and thus is a function of the collection of programs being multiprogrammed as well as the specific program in execution. 114

CPU Level 0 - Level 1 Dedicated Level L Level L + 1 Primary Secondary Shared Level K LE.vel K + 1 Level N Figure 3. 21 Regions of Storage 115

Allocation In the dedicated levels of storage the entire capacity of each level is allocated to the program executing. In the shared levels we will allocate a fixed amount of storage at each level to each user. This fixed amount at a given level being some fraction of the total available at that level. The sum of the individual user allocations at any level will equal the total at that level. Having a fixed allocation the question arises as to what should that allocation be. We will choose a scheme of storage allocation such that the expected execution rate (number of user storage accesses per real time sec) is equal for all of the M jobs being multiprogrammed. Thus we will have the option of running or not running a job (value of M) but if we do run it we will provide it with sufficient storage to so that it may have the same expected rate of execution as the other jobs running at the same time. There are an infinite number of allocation strategies which will provide the desired result of equal expected execution rate. We have made a choice among these which is simple and provides certain important mathematical simplifications. We will allocate the storage at each shared level such that the probability of making an access below that level is equal for all M programs being multiprogrammed. It is clear that this allocation will make all program behave identically in the system when L = 0. When L > 0 the dedicated 116

levels of storage which always provide each program with the same allocation will cause each program to behave differently according to its lifecycle function. To avoid the complications involved in considering each program separately we will consider only cases where L = 0 or all programs have the same lifecycle function. 3. 8 Traffic Description at Individual Levels In writing the equations which describe the performance of the system we will view the system from two points of view. In Figure 3. 22 we show the periods of user program execution interspersed with periods when the CPU is either idle or performing various system housekeeping functions. Notice that in our modeling of the system we have attributed the paging traffic in the system to the user program's behavior. Thus we will assume that the traffic introduced by the system which has not already been accounted for and associated with individual user programs is negligible. We will consider a more detailed model later but for the present we can simply think of the CPU as either executing a user program or idle as shown in Figure 3.22. We will define r = the average rate at which (the collection of M) user programs make access to storage (3.14) and 117

User Program Execution 2 \ i /I I I Ii IY [, I, Real time / - [ 0 - / / \! CPU Idle or System Housekeeping Figure 3. 22 Periods of User Program Execution 118

r' = the average rate at which an executing user program makes access to storage when a user program is in fact executing. (3.15) The variables r and r' are simply related by r = e'r' where e' is the fraction of all time that any user program is in execution. We will now wantto express the average time required to complete a secondary access. The immediate goal is to write expressions for the traffic or rate at which records are read and written at each level. Clearly the traffic in the system is effected by executing user programs. That is the traffic in the system when a user program is executing is not the same as the traffic when the CPU is idle. We will first consider the traffic as seen from the point of view of secondary paging. The actual reads and writes which occur as a result of a secondary access do not occur specifically during a period of user program execution or during a CPU idle period. The transfers which occur can be thought of as occurring over a period of several to many periods of both user program execution and idle CPU time. Thus we will treat the secondary paging transfers as though they occur in a traffic environment described by the average access rate taken over all time, r. 119

We will define d. k = the average over all time of the number of records of size qk read or written at level j per unit real time (3.17) where j and k are integers satisfying 1< j< N 1< k< N We may write an expression for d. as follows ], N d. = L [r(l-w) u it + rw uij t ] (3.18) j,k i= 1,ik, 1,r t 1 In the way of explanation we will disect the terms of the summation beginning with r(1-w)u. t. k, i r1 j= rateki ofu,o r = rate of user program accesses per unit real time. r(1-w) = rate of user program reads per unit real time. r(1-w)ui = rate of user program reads to level i per unit real time. r(1-w) u. tj k. = rate of reads and write at level j j, k, i, involving records of size qk as a result of user program reads to level i per unit real time. The second term in the summation rw i j,k,i,l 120

is the same as the first except here the user program writes are accounted for. Summing these two terms over all possible levels of user program access gives us d. k We will define C. = the average over all time of the number of records of any size read and written at level j per unit real time. (3.19) This may be expressed simply as a sum of dj k over k N c =Z dk (3.20) j k=1l,k We will also define A. = the average over all time of the size of records j being read and written at level j. (3. 21) which may be expressed simply as N Aj C= k jd k. (3. 22) j k=l k Defining N N Z. Z [(l-w)uit. k +wu t (3. 23) J, k-i ii 1 j,k,i,o 1( and N N Y= kl W sqk[(1-w)uitj +wui t ] (3. 24) J k=l k j,k,i,o 0 1 jki, 1 We may write C. = r Z. (3.25) j j 121

and Y. A = Z (3.26) ] where the terms Z. and Y. are expressed completely as functions of: 1. Allocation matrix S 2. Record sizes qk's 3. Lifecycle function f(si,qil) 4. Fraction of read accesses w 5. Traffic matrices ti f 6. Number of programs M 7. Number of levels N 8. Number of primary levels K For our purposes the most important consideration is that Z. and Y. are not functions of r or r'. We would now like to consider the traffic environment in which user program accesses to primary levels are made. Clearly user program accesses to primary levels always occur when a user program is executing. We may also limit our concern to the traffic in the primary levels. This is simply because user program accesses to primary levels never involve data transfers in the secondary levels. We find two sources of traffic in the primary levels. The first component comes directly from the executing user programs accesses to primary levels which occur at a rate r'. The second component 122

is the result of secondary paging transfers which extend into the primary levels. This component is based on the access rate taken over all time r. Consider a simple 2-level system with one primary level, a core, and one secondary level, a drum. We would find two components of traffic at the core when a user program is executing. One generated by the executing program itself and a second generated by the paging activity at the drum. We will define d k = the average over user execution time of the jk number of records of size qk read or written at level j per unit execution time. (3. 27) Where j and k are integers satisfying 1 < j < K 1 < k < N We may write an expression for d! as follows K cik i=l kio't ii kZi, 1k dt k = rI( ui jkY i 0 j, k, i,,l N + X [r(l-w) uit +r k i l] (3.28) i=K+l The expression for d'. is very similar to the expression for 3jk d. k with the exception that the summation is broken into two parts. The first from 1 to k, the primary levels, and the second ki-1 to N, 123

the secondary levels. The first summation gives us the traffic component generated directly by the executing user program. The second summation gives us the traffic component introduced by secondary paging activities. We will define C' = the average over user program execution time j of the number of records of any size read and written at level j per unit execution time. (3. 29) N =E dk (3.30) k=l,k We will also define A' = the average over user program execution time J of the size of records being read and written at level j. (3.31) which may be expressed N A = C1 Z qkd (3.32) j k=l Defining N K Z' = [(1-w)u t +wV 1 (3.33) Z j [(l-w) ui tj k is o+ w ui tj k 1] (3 33) k= 1 i=l J1,k, i, N N Z' = 3 [(1-w)ui t + u t i ] (3. 34) k= i=K+1 Also defining 124

N Y' = 3 k=l N Y,. = k=l K qk(1-w) ui tj, k i, Ui tj,k, i, ] (335) i=F 1 N qk[(l-w)ui t k i + w u t 1(3.36) i=k+l j bkI 1 J) and We may write and C'. = r' Z'. + r Z'. 3 3 J r' Y'. + rY" A'. - = J ] (3.37) (3.38) Notice that here as in the case of Z. and Y. the terms Z J Z". Y' and Y" are independent of r and r'. We may also write: j' j j Z. = Z'. + Z" I J i (3.39) and Y. = Y. + Y". (3.40) We see that if a user program is always executing making r' = r then. = C. 3 3 (3.41) and A. A. J J (3.42) 3.9 Storage Hardware Performance The purpose of the /3 function is to provide a representation for the hardware at a single level which characterizes its performance in 125

the overall system environment. We will define the f function as follows:.(C, A, q) = the average total time required to read or write a record at level j as a function of C, the average number of records read and written per unit time, A, the average record length, and q, the size of the specific record being read. In general the arguments of this function will take the form 3(Cj, Aqk) or j.(C. At, qk) according to whether we are considering secondary or primary level paging. The function j3(C, A, q) will include such delays as waits for disk seek arms to become free, disk arm seek time, wait for channel to become free, latency and read or write time. Thus j3(C, A, q) is itself the result of a rather detailed model of the hardware at the level j. We will devote the entire next chapter to a detailed development of these models. It is interesting to point out that Belady [6] in modeling the 2-level hierarchy considered what we are modeling here with a function to be a constant. It was simply assumed that no queueing occurred. Before continuing we will stop to consider some limitations on j3(C., A,qk) and 0j(Cj, A',qk) as functions of rand r'. In the case of j3(Cj A, qk) we may expand C. and Aj to write 3 3 3 K~~~ 3 3 126

Y. j(Cj, Ajk) = Pj(r Z, (3.44)k Here we will only be concerned with the variable r. Clearly as r increases the average rate at which level j must process reads and writes increases. One would expect that the average time required to perform a single read or write at level j to increase with the increased traffic. We will limit the choice of functions j3(C, A, q) to those which are monotone non-decreasing with increasing C. Thus we can be sure that j3.(C, Aj, qk) is monotone non-decreasing with increasing r. The case for.B(Cj, Ajqk) is a bit more complex. Expanding 3C3 3jk C'. and A. we may write: 3 j r' Y' +r Y 3(C A'q ) = j (r' Z'. + r Z", I I- ' q) (3.45) 3 3 3 j r' Z'. + r Z' (k 3 3 Here we will be concerned with both r and r'. Clearly the average rate at which level j must process reads and writes increases as either r or r' increases. However here we find that the average record length A' is rather unpredictable as a function of r or r' In order to determine what we should expect of 1j(CJ A],q) we must recall the development of C' and A.. C' and A' are the result of two components of traffic one component is proportional to r and a second to r'. Thus increases in r will produce an increase in one component of the traffic and no change in the other and the 127

same can be said for r'. Changes in A. which occur as a result of j increases in either r or r' are clearly the result of an increase in one of the two components of traffic at level j. Thus we would expect that j.(C,A qk) would increase with increases in either r or r' We will limit our choice of functions j(C Aqk) to those which are non-decreasing with increasing r or r'. 3.10 Primary and Secondary Access Time Up to this point we have written expressions which describe the traffic in the system and defined a function 3.(C, A, q) which gives us the expected read or write time for a single record at level j under given traffic conditions. We will continue here by developing expressions for the average time required to complete a paging operation. This will of course in general involve several levels and several reads and writes. We will be discussing two distinct access completion times. The first will be the time between a user program's access to some secondary level, thereby losing the use of the CPU, and the completion of the transfers required to make that user program eligible for execution again. Secondly we will investigate the time required for the executing program to complete accesses in the primary levels and it's effect on the execution rate of the program in question. 128

When describing the T array and its elements tj k i l we were considering the traffic induced in the system as a result of a single user access. It is fairly clear that all the reads or writes indicated in the T array for a single user access need not be accomplished to complete the action required to make a program again eligible for execution or to continue execution if the user access is to a primary level. Let us examine a specific case. Turning to Figure 3. 6 of this chapter we see a most complex series of transfers involved in the paging operations of a user access to level 4 of a 4-level hierarchy. In this particular case f= 0 and k = 1. The only data transfer required to allow execution to continue is the transfer from level 4 to level 1 of a record of size q4. The other indicated transfers may be carried out later or in some cases prior to the actual access to level 4. Now in regard to the specific transfer from level 4 to level 1 the question arises as to the length of time required to complete the transfer. We have both a read at level 4 of a record of size q4 and a write at level 1 of a record of size q4. We will assume for the moment that the level 4 device is a disk, the level 1 device is a core, and the channel connecting the levels contains a buffer of size ql. In this case we find that the read at level 4 and the write at level 1 129

must be carried out simultaneously except for the last word (record of size q) read into core. In common equipment configurations the time required to complete the transfer will depend entirely on the time required to complete the level 4 read. Strictly speaking we could add the time required to write that last word from the disk in core (a level 1 write of size ql). However this would be a rather wasted effort in this case. In this case and similar cases we will treat the time required to complete the transfer simply as the time required to perform the read (or write) at the slower device. Thus in this particular case the time required for the read at level 4 is the time required to return the user program to a condition in which it can be eligible for execution. We will refer to the read at level 4 as a critical read. In another case, shown in Figure 3.4 of this chapter, (which is based on a different system philosophy) an access to level 4 will require a total of three distinct record transfers to complete the necessary paging action. They are: 1. From level 4 to level 3 a record of size q4 2. From level 3 to level 2 a record of size q3 3. From level 2 to level 1 a record of size q2 When these three transfers are complete the program will be eligible for execution. 130

Here we may encounter a situation where the channel buffer is large. For instance if we were to consider a direct transfer between a disk and a drum the size of the channel buffer would almost necessarily be as large as the record being transferred. The time required to complete the transfer would then include both the read (or write) at the disk and the write (or read) at the drum. In general we find that there will be a series of sequential reads and/or writes which must be completed in order to continue or be eligible to continue execution. We will refer to these reads and writes as critical path reads and writes borrowing from the terminology of Critical Path Planning (CPM), PERT and other PERT like planning methods. It should be pointed out that we are making the assumption that there will almost always be space available at each level into which records may be written. Formalizing these ideas we will define gj k, i very similarly to t. k, i f except here we will only include the critical reads and writes. We define: gj, k,. = the number of critical reads and writes at gj, k, i, S level j involving records of size qk in a user program read (- = 0) or write (- = 1) to level i. (3.46) 131

READ> (P -- WRITE (P = 1) Records of Size (k) q1 q2 q3 q4 q.. 0 r 11 1 Traffic 2 at Level 3 ( ) 4 User Access to Level 1 1 i=l 2 3 4 q1 q2 q3 q4 1 ql q2 q3 q4 r * * * - 1 2 3 4 ql q2 q3 q4 1 User Access to Level 2 i=2 1 211 3 4 1 1 2 3 4 q1 q2 q3 q4. 1. User Access to Level 3 i = 3 1 2 3 ql q2 q3 q4 f-..0 0 1 4 1 ql q2 q3 q4 ql q2 q3 q4 1 2 3 4 User Access to Level 4 i = 4 1 2 3 1 4 1 G array Figure 3. 23 132

We will refer to the collection of these elements, gj., ki, as j, k, i, ' the G array. We will also use gi, to indicate the matrix of gi, k, i terms where i and I are fixed. Earlier in this chapter we considered an example much like the IBM 360/85. The T array for this example is shown in Figure 3. 20 and several preceding figures show transfer diagrams. The G array can be obtained from inspection of the transfer diagrams and is shown in Figure 3. 23. In this case each gi l matrix has only one entry; note that this is not always the case. We are now in a position to write an expression for the average time required to complete a user program access. We will begin with user program accesses to secondary levels. In the case of a user program read we may write: N N Average Completion Time = g o(CGj A q (3.47) j=1 k=l ' This is a simple summation of the critical path read and write times involved in a user program read to level i. The write completion time can be expressed as N N Average Completion Time = gj, i, 1 3(C jA k) (3.48) j=l k=l ' 9 ' the only difference being in the last subscript of gj, k i We can now express the average time required to complete an unspecified access to level i. We will define 133

Ti = the average time required to complete a user program access to level i where i is an integer satisfying 1< i< N (3.49) Expressing Ti as N N Ti= Z [(1-w)g oW sk, Ti gj, k, i,(j,k, i, o j' 'qk) j=1 k=1 + gjk, i 1 j(Cj Aj, qk) N N j= k 1 j Aj qk)[(l-w)gjSj +wg(A 11,= 1 1 E j ( j j " * [ ( - ) " -) ^ 0s o + g, k, i, 1 (3. 50) where (1-w) is the probability of a read access and w is the probability of a write access. and i is an integer satisfying K< i< N (i. e. i indicates a secondary level) The time required to complete a user program access to a primary level may be expressed as: N N T =. (C, A,qk) [(l-w)gjk i +wgj ] j=1 k=l (3.51) where i is an integer satisfying 1< i<K 134

The only difference being the traffic at level j. C. replaces C. and A' replaces A.. j J We now have expressions for the average time required to complete an access to any one of the N levels of storage. The next step will be to express the average time required to complete a secondary level access when the specific level is not specified. This is in effect the average time required to complete a secondary page fault. We have already expressed the fraction of accesses to each level i as u.. We will define u' = the probability of accessing level i given that the access is to a secondary level (levels K+1 through N). This may be expressed simply as uti =0 for 0 < i < K U. = N1 for K+ <i <N (3.52) Z u. i=K+l1 where U ( ).... for K+1 < i < N (3. 53) af(sil f(s, ) - and 135

1, o f(sN' qN+1) We will consider an expression for u. where 1 < i < K later. We can see directly from the definition of the lifecycle function or from the expression for ui in Equation 3. 53 that N U.= (3. 54) i=K+l i=K+1 f(sK, qK+1) Thus we may write u =0 for 0 < i < K i - - = f(sK qK+) ui for K+1 < i < N (3. 55) We will define T = the average time required to complete a secondary s page fault. (3. 56) Using u' this may be expressed as N = uT'. (3. 57) i=K+l or N f(sK'qK)1 Ti (3. 58) i=K+l 136

Having an expression for the average time required to make an access to a secondary level we will now turn to the average time required to make a primary access. We will define u' = the probability of accessing level i given that the 1 access is to a primary level (levels 1 through K). (3. 59) The expression for u'. is quite involved and involves considerable digression. When a user program begins execution it experiences an initial period in which the levels of dedicated storage go from a state of containing only the previous CPU user's (system or user programs) information to containing only the current CPU users program. This initial period should be short and in most systems of interest will have negligible or near negligible effect. However we can expect to encounter systems in which the periods of user program execution are so short that the characteristics of this initial period dominate the entire execution period of the user program. The ultimate effect is to modify the probability of accessing a given level, u.. We will now consider the accessing process in some detail focusing on the initial period in particular. Consider a hierarchy in which L = 1, K = 2 and N = 3. This will be a 3-level hierarchy with one level of dedicated storage, one level of shared primary and one level of secondary. 137

Dedicated Level Shared Primaryevel 2 Secondary Level 3 3-Level Hierarchy Figure 3. 24 Let us examine what happens when a user program begins execution and has no information at the dedicated level, level 1. The first access must go below level 1 because there is no information associated with the executing program at level 1. Assuming that the access is to a primary level, i. e. the user program's period of execution is not terminated, we will find q2 bits of the executing program's information at level 1 following the first access. The user program may then continue for an average of f(q2 q2) accesses before making another access below level 1. The second access below level 1 will bring the useful information at level 1 to 2q2 bits and we may expect execution to proceed for an average of f(2q2, q2) accesses before making a third access below level 1. The quantity of useful information at level 1 will grow with each access below level 1 by q2 until level 1 contains only information associated with the currently executing program at which point the quantity of information at level 1 will remain at sl, the 138

allocation at level 1 which in the case of a dedicated level corresponds to the capacity of that level. Correspondingly the average number of accesses which can be carried out with a given number of accesses below level 1 may be written as a finite series of the form: f(q2' q2) + f(2q2 q2) + f(3q2' q2). * +f(sl' q2) + * +f(s1, q2) (3. 60) where the number of accesses below level I corresponds to the number of terms in the series. If we define a function si(x) = x for x < si (3.61) = s. for x > s. 1 - 1 where si is the allocation at level i we may write the above series as R f(s (J q2),q2) (3.62) J=1 where R is the number of accesses below level 1. In order to obtain an effective lifecycle function which includes the initial period of execution we will define: f'(sl, q2) = the average number of accesses required to produce an access below level 1 where it is assumed that initially no information associated with the executing program is stored at level 1. (3. 63) 139

This can be written as # of accesses (3.64) (s' q2) # of accesses below level 1 We will obtain anl approximation for f'(sl, q2) by taking an average over the first R terms of the series of Equation 3. 62 where R is chosen so that the summation of the series (the average number of accesses which can be carried out) corresponds to f(sq, K+) (the average number of accesses made during a single user program execution period). Thus we will write R E f(sl(j q2),q2) f'(sl'q2) = R (3.65) where R is the smallest integer satisfying R f(sKqK+1) < 5 f(sl(j q2) q2) (3.66) j=1 Notice that as f(sK,,qK ) becomes large f'(s,q2) -> f(s, q2). The approach we have taken here to level 1 is completely extendable to all the dedicated levels of storage. In general we may define f'(si, qi+l) = the average number of accesses required to produce an access below level i where it is assumed that initially no information associated with the executing program is stored at level i. (3. 67) 140

And we may write f'(si, qi+) where R. is the smallest f(sK' qK+ 1) < Ri f(si(j qi+l), qi+l) j=l (3.68) R. 1 integer satisfying R. 1 f(si(j qi+l),qi+l) j=1 (3.69) We may now express the overall fraction of accesses to each of the first k levels as u.=.1 - for < i< L 1 f'(si_, qi) f (si, qi+l) (3.70) where f'(So, ql) -- 1 and 1 uL+1 =-f f'(sL, qL+) 1 (3.71) f (s L+I'qL+l) and 1 1 u. = -- for 1 f(si- 1 ) f(iqi+l) L+ < i<K (3.72) Returning now to the probability of an executing program accessing level i, ui, we may write 141

U. Ut. -1 1- K =ui = 1 =0 for 0 < i K for K+l < i < N (3.73) Noting that K i= i= 1 U = 1 1- 1 f(K, qK+i) f(sK qK+l) - 1 f(K' qK+1) (3.74) Thus we may write U?. 1 Ui 1 for 0 < i < K f(sK' qK+l) - 1 = 0 for K+l < i < N (3.75) Defining T = the average page fault. time required to complete a primary (3.76) This may be expressed as K Z p i= 1 ui T. 11 (s K, qK+l) K - il 1 i=1 u. T. 1 1 (3.77) 142

Thus completing the development of an expression for the time required to complete a primary access. 3. 11 Interaction Between CPU and Primary Storage At this point we would like to consider the average time required to complete a CPU access cycle. We will define T = the average time between CPU accesses to storage 1 when a user program is executing or. (3. 78) There are two factors which must be taken into consideration when determining the rate at which a CPU will make accesses. The first is the CPU itself and the second is the storage system to which the CPU makes accesses. The solid line graph of Figure 3. 25 shows the general relationship between T and -. On the left where T is near 0, 7 is determined c p p c by the speed of the CPU and varies little withT p. On the right where T is much greater than the time required to actually execute a single instruction the value of T is determined almost solely by T. c p In a CPU which does not have a look ahead or more precisely can issue only one primary access (fetch) at a time, the slope of Tp as a function of Tp will approach 1 for large Tp. We will define y as y = the slope of T, as a function of Tp, as T becomes large. (379) large. (3.79) 143

a+yT? a / op I, T o A~/ HI I r 0 I1(-,qlqI p -r Versus T c p Figure 3. 25 144 / / slope = y

If a CPU is capable of maintaining on the average several simultaneous primary accesses (look ahead capability) y will have some value less than 1 but always greater than 0. We will assume that for those CPU's which have significant look ahead capability y will be determinable either from hardware specifications or by experiment. Where the look ahead capability is not considered significant we will use y = 1. We are ignoring the possibility that the look ahead capability itself will be directly affected by the storage system. We will approximate Tc with a straight line of slope y which passes through a known point in theTc versus T curve. The approximation may be expressed as Tc =a+yT (3.80) c p where a is a constant and is shown in Figure 3. 25 with a center line. In order to solve for a we consider the special case in which the rate at which the CPU makes accesses to the primary levels (while a program is executing) is highest. This will occur when there is only one activity in the entire system, that being the execution of a program which is contained entirely in the highest level of storage. We will define 145

A r = the average rate at which the CPU makes primary storage accesses when executing a program which is entirely contained in the first level store and there is no other activity in the system. (3. 81) A The variable r will be treated as a hardware specification and is generally equal to the maximum CPU access rate. Since in this -1 special case r7 = -, we may write r a- -yp (3. 82) r Since the accesses are limited to the first level of storage p = T1 (3.83) or a= - -yT r N N = Z 3 Pj(C. j,A A'k)[(1-w)qjk,l,0+wqjk,l,1] r j=l k=l (3.84) where C' and A' may be written j J A N N C - r L [(i-w)tk,l,o+wtk,,] (3.85) A' l qk[(1-w)t,k,l0 + wtj,k 1,1] A - N (3.86) [(1-w)t k,0 + wt k,1,1] k=l J J from Equations 3.37 and 3. 38. This general solution for a appears more complex than it is in most cases. Fcr instance, if an access i46

to level 1 involves only the reading or writing of a record of size q at level 1, as is almost always the case, a becomes simply 1 A a = A- - Yl(r,qlql). r We may now write the average time required to complete a CPU access cycle as: T = a + YT c p f (SK' qK+1) K =a+y ---....... —.Z u.T. (3.88) f(sK, qKgl)-l i=l We will now consider an expression for the average length of time that a user program executes before making a secondary access and thereby losing the use of the CPU we will define: r = the average length of time that a user program executes e bef ore a secondary page fault. (3.89) This may be expressed as: Te f(SK qK+1) (3. 90) where f(sK,qK+1) is the average number of accesses required to produce a secondary page fault. and It is assumed that the time required to complete a CPU access cycle is independent of the number of accesses made. 147

=f7~sq f~f(sK qK+) K =f(s )[a +y uT] e K'K+i e ( KK+1) r + 7 f(sK'qK+1) l i (3.91) Thus far we have developed an expression for the average time required to complete a secondary paging operation, Is' and the average length of time a user program spends in executior Te. There is one other term that will enter into our final equations. We will define h = the average amount of time spent performing the system housekeeping associated with a single user program passing through its cycle execution and secondary paging one time. (3.92) This will be treated as an independent model variable. 3.12 System Performance In analyzing the model for system performance we will assume that the system is either primary storage bound or secondary storage bound. When operating in a primary storage bound condition the CPU is assumed to be always busy and the rate at which work is done (rate of user program access) is based on the primary storage levels and the maximum CPU rate. When operating in a secondary storage bound condition it is assumed that the queue for CPU use is almost always empty and that the rate at which work is done is 148

based primarily on the rate at which page faults to secondary levels are completed. It is fully acknowledged that when the system is operating in a near balanced condition this assumption will produce an optimistic performance figure. Queueing models dealing with the execution queue in a more sophisticated manner have been considered. The increased complexity and additional solution time were weighed against the potential increase in model accuracy and the simpler model was chosen. We will want to consider two performance equations - one based on primary bound operation and a second based on secondary bound operation. In analysis we will simply take the smaller of these two figures. Primary Bound Performance When the system is primary bound the CPU is almost always busy. If we observe the CPU we will find it serving one user program after another along with a certain amount of system activity associated with each user program's execution. We will refer to the period of time that a single user program and its associated system activity occupies the CPU during a single turn at the CPU as a CPU cycle. Figure 3. 26 depicts a series of such CPU cycles. In Figure 3. 26 the r.'s, random variables, represent the time spent servicing each user program 149

System Housekeeping nl n2 / n 7T1 -+- _2-_. _ -F I _ - i - i Real TiProgram Execution User Program Execution Figure 3. 26 Primary Bound Operation The ni's, random variables, represent the number of user program accesses made during a single CPU cycle. We will define r = the average rate at which user program accesses are completed under primary bound conditions. (393) are completed under primary bound conditions. (3.93) We may express this as r f., i i= = lim -- P p i= 1 lim 1 p p-ooP i= 1 lira -1 Z P 1 (3.94) 150

Notice that the 77is are independent identically distributed random variables and the same can be said for the r.s. 1 1? i P We can recognize both the terms P- hi and — P. as sample means, random variables whose variance goes to 0 as p-co and whose value becomes E[7i] and E[Ti] respectively. Thus we may write E[ i] r = [ for any i. (3.95) P E[fi] The E[7i] will be simply f(sK, qK+l) and the E[ri] will be -e + Th thus f(sK' qK+1) r = +(3.96) T + T h e Secondary Bound Performances Our approach to the development of an expression for secondary bound performance will differ slightly from the approach taken with primary bound performance. Here we will examine the behavior of an individual program in the system in contrast to our focus on the CPU in the previous case. In Figure 3. 27 we show what we will call a program cycle. The program cycle consists of a period of system housekeeping, a period of user program execution and a period of secondary paging. Notice that here we are observing sequential cycles in the same user program. It should be understood that the system housekeeping 151

will not all necessarily occur just prior to user program execution but may be spread throughout the program cycle. System Housekeeping /User Program Execution Secondary Paging n' n' T; __t / t2 /" Real Tim{ Figure 3.27 Secondary Bound Operation Here the 7 its, random variables, represent the number of accesses completed in the ith program cycle and the T 's, random variables, represent the time required to complete the ith program cycle. Notice that there is no queueing delay for the CPU in secondary bound operation. We will define rs = the average rate at which user program accesses are completed under secondary bound conditions. (3.97) This may be written as 152

jU'i rs=M lim -ip- (3.98) P = 1 where M is the number of programs being multiprogrammed. Following the same arguments used in the primary bound case we may write E[7ti] r = M for any i (3.99) E[Ti] The E[7?'i] is simply f(sK,qK+1) and E[Ti] = Th + Te + Ts thus M f(sK, qK+1) r= - -= (3.100) Th + T + T h e s We now have an expression for r and r the average rate at p s which user program accesses are completed under primary bound and secondary bound conditions respectively. Both r and r are p s expressed in terms of r, the average rate at which user program accesses are completed, and r', the average rate at which user program accesses are completed during periods of user program execution. The first step in the solution of this system is to determine r' given r. To do this we must express r' as P Z N" i= 1i r' =lim (3.101) 3p T, i=1 i 153

where 7;', a random variable, is the number of user program 1 primary accesses made during the ith period of user program execution and '!, a random variable, is the time th required to complete the i period of user program execution. This becomes as before E[.'i] r' -= (3. 102) E[Ti] and continuing f(SK' qK+1) r' = T e f(sK' qK+1) a+y,, u Ti f(S, qK+ ) - 1 i=1 (3.103) where T. for 1 < i < K is N N Ti S E 3(C'j A q ) [(l-w) g o+wgj ] T Z S?t j, ki, o jy ki,1 j=1 k=1 ' ', and C' r Z. + r Z 3 3 3 and r' Y'. +r Y" A= J J r' Z. + r Z" J 3 154

We will now develop two additional expressions for r', one based on primary bound conditions, and a second on secondary bound conditions. We will begin with the primary bound case. We will solve for r' given r and assuming that the system is primary bound. We will first solve for r directly from Equation 3. 96 e f(s ) - r )__e p (3.104) r p Substituting this into Equation 3.103 and dropping the p subscript for r we have P P rf(sKq - (3.105) rp f(-SK qKl) - rh where r ' is r' assuming primary bound conditions. P Proceeding in the same fashion we may use Equations 3.100 and 3. 103 to write: rf(s KqK+l) r '= (3.106) s Mf(sK,+1) - r(TCh + s) where r ' is r' assuming secondary bound conditions. S 3.13 Solution We have at this point generated a sufficient number of relations and we can now preceed in a reasonably orderly manner with the actual determination of r and r'. The solution for the 2 unknowns r and r' will involve either Equations 3. 103 and 3. 105 or Equations 155

3.103 and 3.106. The equations used depend on whether the system is primary or secondary bound. We will now examine Equations 3. 105 and 3.106 to determine their behavior as a function of r. Since the term 7 in Equation 3. 106 is a function of r we will S begin by considering the behavior of r as a function of r. Repeating s the expression for 7: S N TS =f(SK' qK+ l)1 ii (3.107) i =K+I where T. for K+1< i < N is N N Ti= E Z (j(C Aj,qk) [(l-w)gjk,i,owgj,k,, j =1 k=l J and C =rZ. j 3 and A. = Since the Pj(C, Aj,qk)'s are monotone non-decreasing with increasing r, s is also monotone non-decreasing with increasing ro Returning to Equations 3.105 and 3.106 we see that in both cases the numerator is 0 for r = 0 and becomes larger with increasing r. The denominator has a positive and a negative term. The positive term is constant with respect to r and the negative term is 0 for r = 0 and increases with increasing r. Thus the denominator begins at some positive value for r = 0 and progressively becomes smaller for increas 156

ing r passing through 0 and continuing negatively. Thus both the expressions for rp' and rS' increase with increasing r, growing without bound for some value of r and then go negative. Let us now see what this means in terms of the physical system we are modeling. Under either a primary bound assumption or a secondary bound assumption we see that as we increase the mean user program access rate, r, the rate at which the CPU must carry out these accesses during its busy periods increases. As r is increased we reach some point at which there is simply no time remaining for the CPU to perform user program accesses. As we near this point we see r ' and r ' grow without bound and become undefined. Under p s primary bound conditions this occurs when the CPU is totally consumed with making user program interchanges (i.e. f(sK,qK) - rrh = 0). Further increasing r we obtain negative results for r ' and r ' p s In Figure 3.28 we show typical curves for r ' and r '. We p s display here only the positive behavior of r ' and r ' since these will p s be the only values of interest. The 2 vertical lines shown are assymtotic to r ' and r ' and indicate the point at which they are undefined. p s In order to satisfy Equation 3.103 we will introduce a slight modification of Equation 3.103. We will replace r' on the left with r" and in the right hand member by max {r,r'}. This is written p' S 157

Accesses Per Sec Busy CPU ~ 8)-^ "(Eq. 3.108) p (Eq. 3.105) 1 P // ma/ /(Eq. 3.106)' r (Eq. 3.106) 0 _ — Accesses per Sec. Solution for r and r' Figure 3. 28 158

r = (3. 108) f(s, qK+l) k KI+y K+1 1 a~y + 3 u.T. f(sK, qK+l)-1 i=l where R. for 1 <i <K is N N T Z Z j(c',A ',qk)[ (l-w)gjkio+ gj k,1] j=1 k=l1 C + 1 and Cj' =max {r 'r s} Z' + rZ." ' ' ' ' s I I and max{r 'r s' Yj + rYj. A./ PS 3 3 3 ~max{r ' r '}Z ' =rZ." This equation is plotted in Figure 3. 28 and labled r". The solution we are seeking will be at the intersection of r" and r ' or the p intersection of r" and r, whichever produces a smaller r. In the case shown, the desired solution is the intersection of y" with r ' p' s J and it is marked with a small circle. The solution we are seeking is in fact the intersection of r" and max{rp', r}. Notice first that this solution satisfies either Equation 3. 105 or Equation 3. 106 and Equation 3.103. Second, we can show that there is at most one solution. Since r' and r ' increase with increasing r, max{r ' r '} must increase with increasing r. To show there is at most one solution,we will show with increasing r. To show there is at most one solutionwe will show 159

that r" does not increase with increasing r. Note that the right hand member of Equation 3.103 is of the form: N N - (3.109) a bjk (C ' j k) j=1 k-l,k k where a and b. k are constants which are independent of r',k and j(Cj'Aj',qk) is a monotone non-decreasing function of r and r'. Equation 3. 108 is identical in form except that r' has been replaced by max{rp', rs'} a monotone increasing function of r. Thus the denominator of Equation 3. 108 is a monotone non-decreasing function of r and r" is a monotone non-increasing function of r Last we can see that the solution is based on the proper bounding condition. Recalling that we want to employ the most restrictive bounding condition, and with the described behavior of r", rp' and r, we see that the solution of r" and max{rp r '} results in a minimum r. The actual solution algorithm is based on a binary search over the variable r. The process of determining if a given trial r is too large or too small is carried out as follows: 1. Evaluate r and r ';if either is undefined or negative the p s trial r is too large. 2. Compare r" of Equation 3.108 with max {r 'r '}: pi s if r" > max{r I r '}, the trial r is too small p' s 160

if r" < max{r ',r '} the trial r is too large if r" = max{rp' rs'} the trial r is the correct solution, and r" = max{rp' r } = r We have at this point shown that given the system variables: 1. Number of levels N 2. Number of dedicated levels L 3. Number of primary levels K 4. Traffic matrices t. 's 5. Critical path matrices gi s 6. Record size at each level qk's A 7o Maximum CPU rate r 8. CPU look ahead factor y 9. Mean system overhead time 'h 10. Hardware behavior for each level Pj(C,A,q)'s 11. Storage capacity at each level Qi's 12. Program behavior description f(s,a) 13. Fraction of write accesses w 14. Number of programs being multiprogrammed M we may obtain a solution for the average rate at which user program accesses are processed. 161

Chapter 4 Hardware Model for Individual Levels of Storage Here we will consider the modeling of the performance of the hardware at an individual level. Our primary concern is the average total time required for a read or write request to be processed at a given level. There are many possible models which span a rather wide range between simplicity and reality. At one end of the spectrum we find the simple assumption that the average read/write time is some constant T. This is in fact the assumption made by Belady when applying his lifetime function [3]. In contrast to this simple assumption we find much more complex models at the opposite end of the spectrum. These models may involve a detailed treatment of the read/write request arrival distribution, channel queueing, service storage device queueing and service, and the relationship which exists between these operations. The most realistic of these require simulation or numerical solutions. Here we are developing a storage hardware model to represent a single level of storage in an overall system model. In choosing a psition in the spectrum between simplicity and reality three basic guidelines were specified at the outset: 162

1. We would like to take into consideration the effects of congestion at individual devices (such as core boxes and disk drives) as well as the congestion at the channels serving these devices. 2. The model should have an analytical solution. 3. We would like to be able to model all levels using the same basic model, the model being sufficiently general to adapt to different device types such as core, drum and disk by relatively simple parameter variation. As development proceeded, it was necessary to use some numerical techniques. It was also necessary to compromise 3. above to some degree. 4. 1 Basic Model Here we will consider the form of a basic model which will be used to model each level in the system. We will first describe the model and then discuss the effects of various assumptions in the model. The basic model will consist of a simple queue and server as shown in Figure 4. 1 along with its state transition diagram in Figure 4. 2. The arrivals will be assumed Poisson and the service exponential. The number of requests in the queue will 163

queue server X~B- C x-C Figure 4.1 State Diagram for Basic Model be limited to B- after which additional arrivals are lost. This will limit the total number in the system, queue and server, to B. The service rate jr will be treated as a function of the number of requests in the system at the storage level in question. We will define r = service rate when there are r requests in the system (queue and server). The value of the ir s will be determined by the hardware configuration at a given level. The determination of the value of the Jr's will include such factors as the number of channels, number of devices, seek time, latency time and actual read/write times. The value of B, the maximum number in the system, will be generated from the T array discussed in Chapter 3. This will be 164

done simply by solving for the system conditions which produce the maximum number of read/write requests at the level in question. 1-Att l-(A+,l)At -(XA+u2)At l-(A+UBl)At 1-/lAt lAt XIlAt Ul At Figure 4. 2 State Diagram for Basic Model When solving for the mean total waiting time (queueing and service) we will know the value of C, the mean service rate. Hence it will be necessary to solve for X given C, B and the Lr's. The solution for X will be numeric. Having X the mean total waiting time may be obtained directly. Before considering a solution in detail and developing parameters for specific hardware configurations we will consider the assumptions of the basic model more closely. We will begin by considering the effect of assuming that the server of Figure 4. 1 is exponential. It is clear that the actual storage hardware which we may find at any given level may produce anything from exponential to deterministic service times. We will concern ourselves here with the effects of using an exponential service 165

distribution to model a deterministic server such as a single core box. We must remember that the result which we seek from this model is the mean total waiting time. Thus we must consider how the actual mean total waiting time compares with the mean total waiting time given by the model. First we see that for low utilization or small X, the model is accurate. Second, for high utilization, large X, the results of the model are again accurate and agree with the real system. In this case we will almost always find the queue full (i. e. B requests in the system). Thus the mean total waiting time will be B/LB regardless of the service distribution (/B = service rate with B requests in the system). It is comforting to note that the agreement at both low and high utilizations is essentially independent of the distribution of service times produced by the hardware, and the distribution of interarrival times of service requests. There will be some discrepancy between the model and the actual system in the region of moderate utilization. The model, if in error, vwll tend to produce a pessimistic result, i.e. a larger mean total waiting time. A second source of possible error occurs in the assumption that requests for service have Poisson arrivals. In the case of arrivals we find that the distribution of interarrival times is dependent on essentially everything in the system except the level in question. The arrivals are in general the result of a combination 166

of random events, the basic of driving event being the user program access. Data taken during operation of the Michigan Terminal System (MTS) a multiprogrammed page on demand system with virtual addressing, supports the assumption of Poisson arrivals. Specifically the data (pp. 113-120 of [45]) demonstrates that in this system (MTS) the intervals of CPU execution between interruptions (page faults and I0interrruptions) have a characteristically exponential distribution. This indicates that access to levels below level 1 will tend to be Poisson but says nothing about about level 1 in the hierachy. The distribution of interarrival time at the first level of storage will most likely be dominated by times directly related to the CPU's cycle. It is in the first'level of storage that we will most likely incur the largest error. This is simply because here we are most likely to see deterministic or near deterministic service and the least random of arrivals. In terms of the macroscopic model of the previous chapter this may have the effect of introducing an error in the rate at which instructions are executed when a program is in execution. Consider however the development of the equation for Tc (the average time between CPU accesses to storage when a user program is executing) in Section 3. 11. Here we see that for small 167

values of rc any errors introduced by the first level are completely canceled by the choice of the constant a. This will cause these errors if any to reappear for large values of T where their effect is greatly c reduced. There is one additional restriction which we will want to add to the model of Figure 4. 1. That is we will limit the values of lr to those which satisfy: Ir I fr+1 (4.1) This simply means that an additional request in the system (single level of storage) does not reduce the rate at which the system is servicing requests. In general this will always be the case when modeling realistic hardware configurations. It is difficult to imagine a system in which having an additional request in queue causes a reduction in the rate at which requests are serviced. Consider a level composed of several disk drives. The more requests in the system at any given time the less likely it will be to find idle disk drives. The same is true for any level in which we can carry out service in parallel. In addition to the effects of parallel service, large queues can improve the utilization of a single device in the system. For instance the motion required of a disk arm can be reduced when the queue of requests is large and proper scheduling is used. In the worst case we would expect that Pr = ir+l' 168

An example of this would be a level of storage composed of a single core box. The scheduling of requests here is irrelevant. We will continue at this point with the solution to the basic model and specific determination of the L r's for various device configurations. Our first step in the solution will be to solve for B using the T array discussed in Chapter 3. Recalling that the elements of the T array t, are defined tj., k, = the number of records of size qk read or written at level j as a result of a user read (f=O) or write (i=1) to level i. The number of records read and written at level j as a result of a N user read (f=0) or write (f=1) to level i will be simply E tj. k=l j,k,i, The maximum number of read and writes which a single program can generate at level j will be N max{ Z tj k,i, (4.2) i [1, N] 1 fe[o, 1] where i and I are integers and N, an integer, is the number of levels in the hierarchy. When M programs are being multiprogrammed the maximum number of read and write requests at level j, Bj, may be taken as a) 169

N B. = max { Z tj k i } 3 ie[1, N] k=l ' fE[0, 1] for M = I N max { t. k i {} ie[l,N] k=l J hE[0, 1] N + (M-1) max { t. k i P ie[K+I,N] k=1 J' Qe[0, 1] for M > 1 (4.3) where i and I are integers and N, an integer, is the number of levels in the hierarchy. In the case for M > 0 we see two terms, the first with a range of i from 1 to N and a second with a range of i from K+1 to N. This is necessary because we can have only one user program making a primary access, i. e. an access to the first K levels. As we proceed we will be focusing on the performance of a single level. Thus for convenience of notation we will not use a subscript on the variable B. 170

We will now turn our attention to the determination of the steady state probabilities of the Markov model shown in Figure 4. 2. We will consider a slightly more general model so that the results will be useful for other purposes later in this chapter. General Solution The state diagram for the general model is shown in Figure 4.3. The only difference between this state diagram and the one of Figure 4. 2 is that the arrival rate X is taken to be a function of state and thus is expressed as Xo, X1'''., XN' We have also used the variable N to indicate the maximum number of requests in the system. 1-oAt 1-( A,+,)At 1-(, 2+-p2)At 1-(AN N 'N)At 1- At A At A LAt A At 0 1 N-I pAt 2At At Figure 4. 3 State Diagram for General Model The stationary probabilities are (p. 44 of [17]) 171

1 P o 0o X1 Ao 1 ' " N- 1 1 + + l o..N-. A1 A1 2 A1 -2'" N and 0 1 ' 1-1 A l A - A-AA i 1 P. = (4.4) = o 1 o 1' ' ' AN- 1 + + - +. +.+ J1 ~1 A2 — 1 IJ2.. AN for 1 <i <N 4. 2 Solution of Basic Model Returning to the specific we may rewrite Equation 4.3 and 4.4 substituting B for N and setting Xi = X for 0 < i < B-1. 1 Po -0-__2 B (4.5) X 1+ +- +..+ ---- +-.. - J1 l 2 /L1 /-2 2. *"B and X 11 2' * * 'i Pi = -------- A — - B — 2 (4.6) i X X X 1+ - ---- + + l 2 A1 2 '... AB For the moment at least we will assume that we have the Ai's and concentrate on solving for the mean waiting time as a function of the traffic at the level. In terms of the system external to the specific level being discussed we do not know the arrival rate X but rather the average 172

rate at which request are serviced. We will define C as the average rate at which requests are serviced (meantraffic), ignoring in this context the complexities of specifying the level involved. If we add appropriate subscripts to designate levels, Cj will appear as defined in earlier chapters. In order to relate C and X we may write B C= E iPi (4.7) i=l 2 B- 1 X +.. +- 1+...+ —A - + Al_ /1 1.2 _1/2' "* *B- 1 + + 2 xB - 2B (1+. +.+. ) +'.* Al Al A 2 Ali /J2'".. B- 1 A1 2'" /-B (4.8) defining 2 B-l1 P(X) = 1 + + -- +...+ (4.9) A1 1 A2 1 2... B- 1 we may write C - XP(A) (4. 10) B P(X) + - 11 A2' '.. ' B Before we consider a solution for X we will examine the behavior of C as a function of X. The general relationship between C and X is shown in Figure 4.4 and can be verified either from Equation 4. 10 or from the basic queueing diagram of Figure 4. 1. 173

C=x c /^^ C(X) cT(x) 0 0 X Figure 4.4 Service Rate Versus Arrival Rate Since the mean loss rate is X PB we can see that the C(X) curve falls below the X curve by that amount. As X becomes large PB > 1 and C becomes asymptotic to uB. We will now turn to the problem of finding X given C. We may rewrite Equation 4. 7 in the form of a polynomial in X: C I_^ 1)C 2 1 (C l)2 = C + (^ C 1)A + 1), +...+ (1. 1) + 1 C B...+- 1 ---— i 1)X (4.11) We may show that there is only one solution to this equation using the constraint of Equation 4. 1 and Descartes' rule of signs (p. 28 [10]) which may be stated 174

(p. 28 of [11]) no polynominal can have more real positive zero's tnan its coefficients have changes of sign from + to -, and from - to +. Examining Equation 4. 11 with the constraint of 4. 1 in mind we see that we have at most a single change in sign and thus at most a single real positive root. The solution for X although numerical is straightforward. Having obtained X we may compute the P 's followed immediately B by the mean number in the system i P.. Knowing the mean number i=l 1 in the system and the mean rate at which requests arrive and the mean service rate C we may write [33] B i Pi,= =.Ci1 (4.12) C where j' is the mean time which an individual request spends in the system. Expanded k2 kB X + 2 +...+ B 1 i ~1i 1 2 ~i12" '..B ' 1 - 2 CAl - B2 B- (4.13) 1 X2 X1 + + +-' Al Al42 9- -A 175

4. 3 Solution Algorithm Successive approximations will be obtained using Newton's method. We write f(X) x'= X- f'(x) (4.14) where f() = C - x P(X) B P(X) + -- A1 2... B (4.15) Taking the derivative 2 B xB x B P(X) + P(X) 'B + X P'(X) - P(X) B f(A) 1 02 AB =1 2 "B l lIJB2' B f'(X) = - - J ~ ~~ _B 2 K P(X) + A- \ 2... ABJ (4. 16) Solving for X' using the above equations xB (P () +.. ) [C(p(X) IJ1 gJ2' ' ' gB B + 2"B) - x P(X)] '-1 I-~-'.. -B X' =X + (4.17) B B P(X) [P(X) - x (B-1) + XP( '1 j2'' 2...B + *2. lie ' B recalling that P(X) = 1 + - AI A2 + --- +... + 21 ~2 xB-1 (4.18) A1 2'... B- 1 we may write P'(X) = - + 2 l Al g2 2 + 3 -x +...+B-1 L1 g2 J3 B- 2 (4.19) AL1 '2 ' B-1 and 176

X X2 X3 XB-1 X P'(X) = -- + 2 + 3 A +... +(B-1) A 1 A1 12 A1 2 A3 1 B-1 (4.20) In computing P(X) and X P'(X) we will make use of the common factors xi -1 '2' **Li A FORTRAN program follows which performs the search for X and computes t'. The following program variables correspond to the terms of Equation 4. 15 and other associated variables. P P(X) DP X P'(X) i F -1 j2' A i AB ~R,.x A1 P2... AB XB S (P(X) + A1 ~2' '.'. B FL X FLP X' IB B C C MU(I) i BETA f 177

FUNCTION BETAp (C, IB, MU) REAL MU (10) FL= C K=IB- 1 1 F= 1. DP= 0. P= 1. DO 2 I= 1, K F = F * (FL/MU(I)) P = P + F P=P+F 2 DP= DP + F * I R= F* (FL/MU(IB)) S=R+ P FLP = FL - (S * (C S - FL* P))/(P * (P - R * (IB- 1)) + DP * R) IF (ABS (FLP - FL)/FLP. GT. 0.01) GO TO 1 BETA = (DP + IB * R)/ (C * S) RETURN END This rather short FORTRAN function tends to summarize the results of this section rather well. The function BETA provides the mean total service time for a request given the mean service rate C, the maximum number in the system B and the service rates Ar as a function of the number in the system r. The remaining task is to find the pr's for different device types. 178

4.4 Disk Model We will begin by considering the disk because the results can be simplified to obtain other results and disks are reasonably common and well understood devices. First we must consider how a disk access is carried out. Consider the following steps: 1. Wait for the required arm to become free. As each read or write task enters the system for service it must acquire the service of a particular disk arm for its entire period of service. 2. Wait for free channel. When an arm becomes free we must acquire a channel so that the seek operation can be initiated. 3. Initiate seek operation. As soon as the use of a channel is obtained the seek operation is started. It is important to understand that the use of a channel is required only to initiate the seek operation and that the time involved is negligible. The channel is not held during the actual seek operation. 4. Wait for seek to complete. This involves the mechanical positioning of the disk arm over the desired track. Typical disks (IBM 2314) require a little less than. 1 sec. for this operation. Note again that the channel is not tied up during this operation. 179

5. Wait for channel. At this point the arm is positioned and the task enters into contention for the use of a channel. 6. Latency. As soon as a channel is acquired we begin to wait for the rotation of the disk to bring the first of the desired data under the read/write heads. This is generally about 1/2 a rotation or 8 milliseconds for an IBM 2314. 7. Actual read or write with data transfer. The actual time required for the read or write operation may be only a few milliseconds depending on the length of the record. We will assume at the outset that the time spent performing Steps 2 and 3 is negligible. Step 3 is obviously negligible since it requires only a few micro-seconds to complete in an environment where 10 Is of milliseconds are common. Step 2 is a bit more complex. This wait for a channel is in order to initiate a seek operation. It is only reasonable to place these requests for use of the channel at the head of the channel use queue and complete this operation as soon as possible since it requires a negligible amount of channel time. Assuming that requests for channel service are handled in this way we can consider the effect of this delay. First, when the system is lightly loaded a channel will almost always be free and 180

Wait for arm Wait for seek to complete Wait for channel Latency Re ad/Write Arm busy -ot Arm in competition for channel use, A channel occupied 00 P" i IRead/, Write, -."1' Disk Service Timing Diagram Figure 4. 5

{)o delay is incurred. Second,under heavy load we may find the disk arms almost always busy. Notice that at the end of a complete read or write operation both an arm and a channel become free at the same time. If a task is waiting in queue for that arm it may use the channel freed with the arm to initiate a new seek. Therefore in a heavily loaded system, i.e. busy arms, there will almost never be a wait for a channel to initiate a seek operation. This delay only occurs when a request arrives for an idle arm and all the channels are busy. Lastly there is the case where the delay does occur but is of little consequence. This is again in the heavily loaded system but here we are concerned with heavy channel loading rather than heavy arm loading. When the channels are almost always busy the delay in getting the seek started has only a small effect if any on the total waiting time. Figure 4.5 illustrates the delays which occur along with the periods during which the arm and channel facilities are tied up. The basic goal of this section is to express the mean service completion rate of a system of disk drives when there is some fixed number of requests in the system. We will define r = number of request in the system Thus in the specific case of r requests we are seeking jLr One of the basic factors in solving for ir is the manner in which the requests for disk arm use distribute themselves among the available arms, 182

If we are in state r of the basic model then we know that there are r requests in the system. In the case of disks these requests queue for the use of individual disk arms. We may find that all r requests are in the queue for a single disk arm. In this case we would expect that the bottleneck would be the disk arms and that there would be no congestion at the channel or channels. At the other extreme we may find the r requests spread uniformly over all the arms in the system. Here we would expect to find the bottleneck at the channel(s). This is all dependent on the number of channels, the number of disk arms, r and other hardware specifications. Our basic goal here is to find the mean completion rate pr when there are r requests in the system. To do this we will consider the steady state behavior of the system when m arms are busy. Where m can be any integer value from 0 to NA where NA is the number of disk arms. More specifically we will solve for the mean service completion rate when m arms are busy. Defining t(m) - mean completion rate when m arm busy we may write NA Ar E Pm(r, NA) j(m) (4. 21) m=l 183

where Pm(r, NA) = the probability that m arms are busy when NA arms are servicing r requests. NA r-1 NA- m m-l = — A —/m) —m — - ~ (4. 22) (NA + r-1) r The development of Pm(r, NA) is considered in detail in Appendix B. We will continue here with the development of and expression for B(m). Mean Service Rate when M Arms Busy At this point we are not concerned with queueing for disk arms. We are concerned with the very specific case where m arms are busy. The steps through which a busy arm proceeds in accomplishing a transfer are as follows: 1. Seek 2. Wait for channel 3. Latency + read/write The seek operation is independent of other operations and does not occupy a channel. When the seek operation is complete the request entersa queue for channel service. Upon acquiring a channel the latency and read or write operations proceed. Figure 4.6 shows a 184

queueing model which models these operations. We will use Poisson servers in this model to represent both the seek operation and the latency-read/write operation. We will define -s = mean seek service rate (4. 23) and li = mean (latency + read/write) service rate (4. 24) As a request enters the system (from the left) it enters one of the m servers of service rate.s' Since the system will have SEEK I J I LATENCY- READ/WRITE 1T " 1 7I _ _ _ I 9IN t t I A= Mean Seek Time s AC = Mean Channel Holding Time Figure 4.6 Channel Queueing Model 185

exactly m requests circulating, there will never be any queueing or blocking at the servers representing the seek time. Remember we are considering the case of m busy arms. When the requests complete the seek operation it enters the queue for channel service. Here the request waits for one of the Nc servers representing channel service. Channel service is required for the duration of the latency and read/write operations. After completing channel service the request reenters the system on the left maintaining m arms busy. The use of Poisson servers in this model permits the use a Markov model. We may define the states of a Markov model to correspond to the number of requests in that part of the system of Figure 4.6 that is contained in the dashed box. A state diagram with state transition probabilities is shown in Figure 4.7. Notice that this is analogous to the general model solved earlier in this chapter if we define X = (m-i) ps (4.25) and 1i = i c for i <Nc = Nc for i >Nc (4.26) 186

1-mpu At 1- [uc+ (m-)s At l-[ Nctc+(m-Nc)s ]At 2sAt MiAt A.AcAt NccAt Ncc4At State Diagram for Channel Queueing Model Figure 4. 7

The stationary state probabilities may be obtained directly from Equation 4.4 P 1 x0 X0 x1 xx0 x1' lm-1 1+ + --— +...+..... Al Ao A1 Al A1. Aim 1 o 1 i1 2 *m Al A12'" s Aii 11 j2 **y (4. 27) (4.28) and P = i A 1+ + ol +l + Ao A1 +o Ao Al' 'm-l -L1 M2' * * y We may express the mean completion rate ji(m) when there are m arms busy in terms of us. m,j(m) = i=0 pi(m-i) 11s (4.29) expanding M(m) = Ls A m + (m-1) 1 xmx o X1 + (m-2) +... + 1 2 A A1... m-2 A 2' *m-1 Al 1 x X + +...+ Xo x1 Xm l 2' ' '- m (4.30) where. = (m-i) s = i lc for i < N = NcMC for i >Nc (4.31) (4.32) (4. 33) 188

To obtain,lr we simply write NA r= Pm(r, NA)(m) (4.34) m=I Turning our attention to Jc and As' we will express 1 1 1 (4.35) s mean seek time and c latency + read/write 1 60 60 A 2 RPM + RPM BPT RPM = A-1RPM 1(4.36) 60 ( BPT where RPM = disk speed in revolutions per minute BPT = bits per track A = mean record size. 4. 5 Data Cell Model The data cell is an IBM device in particular the IBM 2321. The data cell records and retrieves information on magnetic strips. The IBM 2321 uses a total of 2000 strips each containing 100 tracks of data. The strips are stored vertically in a circular file which rotates to position the desired strip at the reading station. The desired strip is then separated from neighboring strips using a tab 189

indexing technique. The desired strip is removed from the circular file and wrapped on a drum. The drum is read by a movable head which has five positions and twenty read/write heads providing access to the 100 tracks on the strip. After the above operations are complete a channel is acquired for the latency-readv/rite operation. The data cell is analogous to the disk in that all the operations prior to the latency-read/write operation are carried out without the active use of a channel. Correspondingly the term seek is used for those operations which precede the latency- read/write operation. We can use the same model for the data cell that was developed for disk by simply redefining the following terms: NA = # of access mechanisms = # data cells m = # of busy access mechanisms gs = data cell seek service rate jic = data cell latency + read/write service rate. Other variables are identical. Since at this writing there is only one data cell (IBM 2321) to be considered we will specify,s and A for this device. 1 s mean seek time (4 37) for the IBM 2321 - 1 (438) -s =.550 (4.38) 190

and RPM C 60( A +i+) (BPT 2 for the IBM 2321 c = 6 1A20 1 ) (4.39) 60 (160 - + -) These numbers assume random strip access and include strip replacement time. Additional information on the IBM 2321 data cell may be obtained from IBM [50]. 4.6 Core Model The modeling of the congestion in core is much simpler than either the disk or data cell. First channel congestion is either nonexistent or negligible. This removes the complexities involving channel independent and channel dependent operations. The congestion in a system of cores occurs at the core boxes. In effect the queueing is for core drivers and sense windings. We are seeking the mean service rate for a system of NA core boxes with r requests in the system or. Assuming that core boxes are accessed randomly we may then express the mean service rate r as NA r i pm(r, NA) (m) (4.40) m= 1 191

where u(m) = mean service rate when m core boxes are busy. mo cycle_ time(4.41) core cycle time 4.7 Drum Model Here as before we are seeking ULr but here we are concerned with a drum. The drum poses a rather different problem wuilcv compared to those that we have treated previously. The access time and mean transfer rate for a drum can be improved considerably by ordering the read/write requests in the order which the information passes under the read/write heads. This improvement is sufficient to motivate most users of drums to go to the trouble to implement the ordering of requests in the drum management software. Correspondingly it would be unrealistic to ignore this improved operation when modeling a drum. To begin let us consider what we mean by sectors and fields. The drum may have on the order of 1000 read/write heads (IBM 2301 has 800). These heads are divided into groups (possibly groups of one head) which work together in reading and writing information on the drum. The individual tracks covered by a single group of heads is called a field. The number of sectors is simply the number of records in a single field. Figure 4. 8 shows the fields and sectors of a drum. 192

Drums exhibit certain characteristics which can complicate their modeling. One of these is that the read/write heads cannot be switched from writing to reading mode instantaneously. Generally speaking if a record is currently being written in a given field the *\ 1" | I, I I II I I /.., ',',; t ',,,', \ Sectors,"I, I, I. i i-.,. / _ / / -_, Fields Figure 4. 8 Drum Sectors and Fields record in the same field of the next sector cannot be read. This problem can be circumvented in several ways: 1. Intersector gaps sufficiently wide to provide for head switching. 2. Request ordering to avoid unnecessary head switching. We will ignore the possible delays caused by head switching, assuming either that some measure has been taken to completely avoid the problem or that the delays incurred are negligible. 193

We will make the assumption that the distribution of requests for sectors is the same as used previously for the disk data cell and cores. The difference here is that the service is occurring in a cyclic fashion rather than at random. Thus we may write pm(r, NA) = probability that m sectors have a request in queue when there are r requests and NA sectors. (4.42) We will assume that the mean distance between the active NA sectors (sectors which have request in queue) is m sectors. The mean distance to the starting point of the first of these m 1 NA active sectors is - m sectors. The mean distance between 2 m the starting points of each of the succeeding (m-1) active sectors NA NA N A is m sectors or a total distance of (m-1) - sectors. We must then continue to traverse the last of these sector a distance of one sector. Combining the total distance required to access m active sectors may be written: 1 A N Total distance m active sectors = + (m-1) + 1 2 m m 1 =NA(1 2m) + (4.43) 60 NA x RPM seconds where RPM is the revolutions per minute of the drum. 194

Thus we may write the mean time required to access m active sectors 60 1 1 Time to access m sectors= RPM (1 - + — ) (4.44) A The mean rate of accesses will be m x RPM /A(m) m RPM (4.45) 1 1) 60 (1- 2 + and N pmXr RPMA (4.46) r A) 1 1 60 (1- 2m + 4.8 Effect of Specific Record Sizes Thus far we have developed a model giving us the mean total service time for core, drum, disk and data cell. Each of these models is a function of the specific characteristics of the devices at the level in question as well as the service rate C and the mean record size A. Focusing on the mean total service time as a function of C and A we may write: 3.(C, A) = mean total service time for a read or write request at level j when serving an average of C requests per second which are of an average record length A in bits. (4.47) 195

We would now like to consider the mean total service time when a record of specific size q is read or written at level j. We will define: j.(C, A, q) = mean total service time for a read or write request involving a record of size q at level j when serving an average of C requests per second which are of an average size A. (4.48) We will assume that the requests are generated independently. This means that given the size, q, of a specific record being serviced at a given level gives us no information about the size of the other records being serviced at that level. We may write j(C,A,q) = j(C,A) + Xj(q-A) (4.49) where x =4 01 Xj = Max transfer rate at level j (bits/sec) (40) Notice that in all the models developed the size of a record has no effect on its total service time until the actual read or write operation takes place. The length of time required to complete this read/write operation is simply Xj q where Xj is the transfer rate. The term xj(q-A) gives us the variations about 'j.(C, A) caused by differing record sizes. 196

Notice that if we take the expected value of 3j(C, A, q) for a distribution of record sizes, q, we may write E[3j(C, A, q)]= E[3((C, A) + E[Xj q] - E[Xj A] = j(C,A) +Xj A- X A = (C, A) (4.51) At this point we have completed the development of 0j(C, A, q) the mean total service time at level j as a function of the mean service rate C, mean record size A, and the specific record size q. 197

Chapter 5 A Case btudy in Analysis Up to this point we have been concerned with the development of a general mathematical model of a computing system. In this chapter and the next we will be concerned with implementation and application of this model. In the first section we will discuss briefly the computer program which was designed to implement the mathematical model developed in the preceding chapters. In the sections following (5. 2 through 5. 6) we will discuss a case study in analysis. Here we will describe a single system in some detail, study its performance, and then proceed to examine the changes in performance which occur when various model parameters are changed. 5.1 Program Description The design of the computer program implementing the system model closely follows the development of the system model described in Chapters 2,3, and 4. The lifecycle function of Chapter 2 is implemented in a single 8-variable FORTRAN function. Each of the storage models described in Chapter 4 is implemented in a separate subroutine or group of subroutines. These models are all interfaced through a FORTRAN function BETA which corresponds to the 3 function discussed in Chapters 3 and 4. This FORTRAN functioncalls on the appropriate model based on the level of storage in question and returns the desired 198

mean total service time as a function of the traffic at that level. The storage device model in effect for a given level is controlled by a simple index. The number of different storage device models is not limited and additional models may be added rather simply. The macroscopic model described in Chapter 3 is implemented in several subroutines which compute the values of the u's, C 's, C' 's, A 's, A.'s etc. The method of solution is as described in j j J Chapter 3. In addition to the basic analysis program there are a number of subroutines which perform the functions of input, output,and program control, The program is designed to run in a highly interactive manner allowing the user to modify and display system parameters by using simple commands. There is one important restriction which appears in the computer program and is not necessarily part of the mathematical model itself. The program assumes that all user programs are identical and correspondingly shared levels are allocated equally among the programs being multiprogrammed. We will discuss several other aspects of the program as we consider the examples that follow. The optimization capability of the program will be discussed in the next chapter where we treat the optimization in detail. 199

C P U 10 me Maximum Access Rate L ___________~_ v32 Bit Word CACHE/ LEVEL 1 Dedicated-Primary BUFFER 80 ns Access Time. ----i —. ~~~8192 Bit Capacity (256 Words) tCOREL 2 ORE CORE CORE LEVEL 2 Shared-Primary 1 Lts Access Time 500, 000 Bit Capacity (Per Unit) ( 16k Words) DRUM LEVEL 3 Shared-Secondary 1800 RPM 16.6 ms Latency 10 Million Bit Capacity ( - 300k Words) SYSTEM DIAGRAM Figure 5 1

5. 2 System Description In this section we will describe a multiprogrammed, demand paged computing system using a 3-level storage hierarchy. We will consider the system itself and its performance in considerable detail. The need for careful description here is motivated by the fact that this system will remain at the center of attention throughout our study of analysis and in the next chapter treating optimization. The computing system in question is first shown in Figure 5.1. Here we see a CPU and 3 levels of storage. The CPU is capable of a A maximum access rate of 10 mc. More precisely r as defined in Equation (3. 81) is 10 mc. The CPU word size is 32 bits as noted. The level 1 store is contrived to resemble the cache on the IBM 360/85 or the so-called buffer on the IBM 370 series. This cache or buffer store will be allocated entirely to the executing program and thus will be a dedicated level of storage. This level is also clearly a primary level since access to it will not cause loss of the CPU to another program. The level 1 store here is a random access device with an 80 ns access time and a 8192 bit or 256 word capacity. The level 2 store consists of 3 core boxes. The space at this level will be allocated equally among the programs being multiprogrammed, making this a shared level. This level too is a primary level and access will not cause loss of the CPU. The access time at level 2 is 1 and each core unit has a capacity of 500,000 bits or approximately 16k wordso 201

The level 3 store is shared-secondary and is implemented in the form of a drum. Shared indicates that each multiprogrammed program is allocated equally at this level and secondary indicates that user program access to the drum will cause loss of the CPU to another program. The drum at level 3 rotates at 1800 RPM and has a corresponding latency of 16.6 ms. The drum's capacity is 10 million bits or approximately 300 k words. Figure 5. 2 is the first of a number of figures which show the actual computer output generated by the modeling program. This and future figures containing this style of type were generated by issuing one or more display commands to the program. The first 3 entries of Figure 5. 2 give us the number of levels, the number of dedicated levels and the number of primary levels. These of course correspond to the system of Figure 5. 1. Notice that where possible the variable names used earlier in model development are used here. Continuing, we see the number of programs to be multiprogrammed has been set to 13. The next 2 entries establish limits of the values which M (the number of programs) may take on. The primary function of a minimum and maximum number of programs is in optimization where we are searching over a range of values for an optimum. We will discuss this in more detail in the next chapter, which treats optimization. 202

N 3UMBER OF LEVELS NUMBER OF DEDICATED LEVELS NUMBER OF PRIMARY LEVELS NUMBER OF PROGRAMS MULTIPROGRAMED MIIN # OF PROGRAMS TO BE MULTIPROGRAMED MAX # OF PROGRAMS TO BE MULTIPROGRAMED.MAXIMUM CPU RATE (ACCESS PER SEC.) 0 C.0 CPU OVERLAP FACTOR SYSTEM OVERHEAD TIME N= 3 L- 1 K<= 2 M= 13 MI'NM= 2 'MAXM= 25 RHAT= 0. 130030E 38 GAM=3. 49999982 TAUH= 1499997E-33 TABLE OF RECORD SIZES LEVEL RECORD SIZE 1 32 2 1324 3 16384 SYSTEM VARIABLES Figure 5. 2

Next we see the maximum CPU access rate (r here represented as RHAT). This is followed by the CPU overlap factor. The value of the CPU overlap factor indicates that the CPU is roughly capable of keeping 2 access requests pending at once. This variable (represented here as GAM) corresponds to y defined in Equation (3. 79). The next of these independent variables is the system overhead time 'h (represented here as TAUH). This is the CPU time required for program interchange. 2h is defined in Equation (3.92), Finally at the bottom of Figure 5. 2 we find a table of record sizes. This is the logical record size and corresponds to the qi's where the i corresponds to the level. We will now turn our attention to the individual levels of storage themselves beginning with level 1. In Figure 5. 3 we see a description of the hardware at level 1. Here we see that we are using model type 2 at level 1. This model corresponds to the core model developed in Section 4. 6. The average access time for a single unit is 80 ns as indicated earlier. Note that all times are in seconds unless otherwise noted. The basic device record size is 32 bits. The basic device record size here happens to be the same as the logical record size but this need not be the case. The device record size is the number of bits which are read or written in a single access time. The logical record size specifies the quantity of data "paged up". The unit capacity 204

*** LEVEL I *** OD EL TYPE 2 ^43DEL 2 (RANJ:DOl ACCESS OR CORE J ITS) A V/EAGE ACCESS TI1E FOR A SI MGLE I.JlI T 3ASIC DEVICE RECORD SIZE.J:4 I T CAP AC I TY f.JM3E ER F.J'JI TS vl N O F 'It I TS "' AX D F.J: I rTS COST PER UJ.IT (3).- 7999967E-37 32. 3. 192 I3E 3 4 I I 4 5.,3?J 3.~1 Level 1 Hardware Description Figure 5.3 205

MEAN WAITING TIME 0.236E-06+ I + + + + * I I I 0.221E-06+ I I I I 0.205E-06+ I I I I 0.189E-06+ I I I I 0. 1 74E-06+ I I 0.158E-06+ I I 0.143E-06+ I 0. 143E-06+ I I I I 0. 127E-06+ I I I I 0.11 1E-06+ I I I 0. 956E-07+ I + 4, 4, 4, 4, * * + + 4, * + * 4, 4, 4, * * 4, * 4 -* * + * ** * * * 4, 4.4 4 4, +4 ** 4 ** ** ** * J 4, 4, +4 4+ 3 * ** ** ** ** 4, + +4 + ** ** ** ** ** 4+ ** + ** ** ** + 4, 4.+ + 4, 4, + 4, 4, ** I ** I *** I *** 0. 800E-07** - - - -.- - - - +- - - - - - - + + + 0.10E-02 0.25E 07 0.50E 07 0.75E 07 0.10E 08 0.12E 08 TRAFFIC IN RECORDS/SEC Level 1 Performance Figure 5.4 206

MEAN QUEUE LENGTH 0.295E 01 + ++ +* I I I I * 0*266E 01 + + + I * I I * I * 0.236E 01+ + + + * + I * I * I * I * 0207E 01 + + + + * + I * I * I ** I * 0.177E 01+ + + +* + I ** I ** 1 * I * 0.148E 01+ + + + *4 + I * I * I * I ** 0.118E 01+ + + + * + + I * I ** I * I * 0.886E 00+ + + ** + + + I ** I- ** I ** I ** 0.591E 00+ + * + + + I ** I ** I ** I ** 0.295E 0a+ +** + + + + I *** I *** I ** I *** 0.954E-06** --—.+ -------— + ------— + -------— + ------— + 0.10E-02 0.25E 07 0.50E 07 0.75E 07 0.10E 08 0.12E 08 TRAFFIC IN RECORDS/SEC Level 1 Queuing Figure 5.5 267

is given as 8192 bits. Note that all capacities and record sizes are in bits. We see the number of units, the minimum number of units and the maximum number of units. Clearly the number of units is set to 1 which corresponds to our example. The minimum and maximum are bounds used in optimization when the number of units is a decision variable. Last we find the cost per unit at $50,000. This value is used in optimization and, as you will see,for simplicity we have chosen a cost of $50,000 per unit at each level of storage. This is a bit unrealistic but simplifies our discussion of optimization. Turning to Figure 5.4 we have a plot generated at the terminal which displays the performance characteristics of the level 1 configuration. The plot gives us the mean waiting time for a single service request as a function of the rate at which requests arrive. The request arrival rate or traffic records per second is given on the horizontal axis and runs from near 0 to just less than 12.5 million records/sec. In generating this plot it was assumed that a maximum of 3 requests for service could be in queue and service (i.e. B = 3,see Section 4. 1). It is also assumed that all the records being read or written are 32 bit records. In terms of the f3 function defined in Equation (4.48) we are seeing a plot of /1(C,32,32) versus C,the traffic in records per second. In the lower left-hand corner of the plot we see that under low traffic conditions the access time for level 1 corresponds to access 208

time of the device 80 ns. This is of course a consequence of virtually no queueing. As we move to the right increasing traffic is seen as an increase in the mean waiting time due to congestion. At the far right near 12 5 million record/sec. the mean waiting time increases to 236 ns. It is important to note that 12. 5 million records/sec. is the maximum possible service rate for an 80 ns server under these conditions. Also note that if we always have 3 requests for service in the system the mean waiting time will be 3x 80 ns or 240 nSo The maximum mean waiting time shown here is 236 ns, which is appropriate for a traffic figure slightly under the maximum possible. It is useful to note that in generating these plots the program modeling the j function is called with increasing values of C or traffic, until it responds with a special return which indicates that the device being modeled cannot operate at such a high traffic. Figure 5.5 gives us the mean queue length as a function of the traffic at level 1 under the same circumstances. Here we see the mean queue length (vhich includes the request in service) go from near 0 to 2. 95 or just under 3, as would be anticipated. The values of service rate or traffic using the relation [ 33 ]: Mean number in queue and service=mean service rate x mean waiting time. We will now turn to the next level of storage, level 2. The description of the level 2 configuration is in Figure 5. 6. At level 2 we are using the same model that was used at level 1. Here, however, the 209

*** LEVEL 2 *** MiODEL TYPE 2 'ODEL 2 (RANDOM ACCESS OR CORE UNITS) AVERAGE ACCESS TIME FOR A SINGLE UNIT 3ASIC DEVICE RECORD SIZE UNIT CAPACITY;,J!JMtBER OF J.N I TS VlIN\ # OF UNITS -MAX # OF U.NITS COST PER UNIT (S) 3. 9999967E-36 128. 3.5'.3.3s333E 3 6 3 2 5:,3'3 X 3;3 Level 2 Hardware Description Figure 5.6 210

iEAN WAITING TIME 3.882E-35+ I I I I 0.803E-05+ I I I I I I I I 0.647E-05+ I I I I 3.569E-05+ I I I I 0.491E-35+ I I I I S.413E-05+ I I I I. 334E-045+ I I I I 0.256E-05+ I I I I 0.178E-05+ I I.I, 4 - + + + *.I + + * + + 4, + 4+ * * + * + + + 4+ * * + + +~ + * + * * + * + * + + + + + + * * 4,4, * * ** * 4,4, * 4,4, 4,4, ** + 4, + + + 4, 4+ 4, 4,4, 4,4, 4,4, + 4, + 4, *4,4,4, 4, 4, + I ****** 0.10SE-05***** ---—. —+ --- —+.. - - - + ----- + - -- + 0.13E-32 0.55E 06 0.11E 07 0.17E 07 0.22E 07 a.28E 07 TRAFFIC IN RECORDS/SEC Level 2 Performance Figure 5 7 211

MEAN QUEUE LENGTH 0.244E 02+ + + + + I I I 0. 220E 2+ + + + + * I I I * I 0.195E 02+ + + + + + I * I I * I 0.17I71E 02 + + * + I I I I I 0.147E 02+ + + + + + I * I * I *. 122E 2+ + I * I * I * 3.977~ 31+ + 4 * + I * I * I * I * 0.733E 01+ + 4' **+ 4 I * I * I * I * 3.489E 31+ 4 4 4 *4 4 4 I ** I *4 I I f.244 + 01+ 4' **** + 4 4 I I * -0'0 ***** 4 -— '4' 4' —+ ---- 4' —~+_________.________ S.I1E-02 0.55E 06 0.11E 07 0.17E 37 0.22E 07 1.28E 07 TRAFF'IC IN RECORDS/SEC Level 2 Queuing Figure 5.8 8.73E 1++ ++! I~ ~~T~Ff ***CORS/E I~ ~~~ee * * * * uin ~~~~FIgr **** 212

parameters are different. There is very little new here except possibly the range of allowable number of core units and the basic device record size. Thus we have 3 core units, each with a capacity of 1/2 million bits and each capable of accessing a 128 bit word in 1 Is. The performance of level 2 under load is shown in Figure 5.7. Here as for level 1 we have plotted the mean waiting time as a function of traffic in records per second. The record size used here was the basic device record size of 128 bits and the maximum number in queue and service was set to 26. (The motivation for the choice of the values for the maximum number in queue and service will become obvious later.) The maximum service rate would be 3 million records/sec. if all 3 core units were always busy. Of course we cannot expect all 3 core units to remain busy at every instant. But, with a maximum of 26 requests for service in the system we can expect the maximum feasible traffic to be near 3 million records per second as indicated in Figure 5.7. To get a rough estimate of the maximum mean waiting time we can assume that the requests for service divide evenly among the 3 core units, thus giving us a maximum of 1/3 x 26= 8.666 in each queue. If there were in fact 8. 666 in each queue the mean waiting time would be 8.666 is. Notice that the maximum given in Figure 5. 7 is a little larger than 8.666 ts. This should be expected since an occasionally idle core unit and the resulting long queues at the other units would be expected to increase the mean waiting time. 213

Figure 5.8 shows us the mean queue length as a function of traffic, and this varies as expected from near 0 to just under the maximum of 26. Turning now to level 3 described in Figure 5o 9 we see that the situation has changed somewhat. At level 3 we use model type 3 which is the drum model described in Section 4. 7. The device parameters indicate a 1900 RPM drum with 100 K bits per track and a capacity of 10 million bits. There is currently one drum and we may attach from 1 to 4. Again the cost per unit is $50,000. The performance is shown in Figure 5.10. Here we have assumed a maximum of 26 requests in the system and a record size of 16384. Notice that at the low traffic end we have a mean waiting time of 22. 1 ms. Using a record size of 16384 bits we have 6 sectors on the 100 K bit per track drum. Rotating at 1800 RPM we have 16.6 ms of latency (1/2 a rotation) and 1/3 x 16.6 = 5. 5 ms for data transfer. Thus latency and transfer time is 22.1 and agrees with the low traffic waiting time shown in Figure 5.10. The maximum traffic is 6 records per revolution. Sir e a complete revolution requires 33.3 ms the maximum traffic will be 180 records/sec. Since we have a maximum of 26 requests for service in the system at level 3 and 6 sectors on the drum we see that this is only roughly 4.3 requests per sector. This means that it is quite likely that a sector may pass under the read/write heads with no request in queue 214

*** LEVEL 3 *** MODEL TYPE 3 MODEL 3 (DRUM OR FIXED HEAD DISK) DEVICE RPM BITS PER TRACK UNIT CAPACITY NUMBER OF UNITS MIN # OF UNITS MAX # OF UNITS 0.18 80300E 4 3.100.'00.E 06 0. 1030!33 0E 08 1 4 COST PER UN IT ($) Level 3 Hardware Description Figure 5. 9 215

MEAN WAITING TIME 0.177E 83+ I I I I 0.161E 00+ I I I I 0.146E 30+ I I I I 0.130E 30+ I I I I I I I I I I I I d.995E-01+ 0.843E-01+ I I I I I I I 4~ + + * *i + 4. *4+ * 4+ + + 4. 4. 4. * * 4 * * * * * 4. * * 4* 4 4i 4i 4 4. 4. 4 4 4 4 ** * * 4 4. 4 *-* * + * + * * +4 * * * ** *i 4* 4i 4 4 4. I * 0.53lE-01.+ + 4 ** + + 4 I ** I **.376E-01+.+ 4 ** 4.+ + + + I ****4 I * 4 4 I 3.221E-01***4. --- —— 4 --- —-— 4.-4 —. ---4 --- —— 4 --- —— 4. 0.10E-02 0.28E 02 0.56E 02 0.8SE 02 011IE 03 0.14E 03 TRAFFIC IN RECORDS/SEC Level 3 Performance Figure 5.10 216

MEAN QUEUE LENGTH 03.249E 02+ I I I I 0.224E 02+ I I I I 3.199E 02+ I I I I 0.174E 02+ I I 3.149E 02+ I 3.125E 02+ I I 0.996E 01+ I I I I 0.747E 01+ I I I I 3.498E 01+ I I 4. 4+ + 4, * * 4+ 4+ 4+ 4, * 4. + + + + * * 4. 4, + + * + * * * 4, 4 - 4 - +. * * * $r $r 4, 4, 4+ 4, 4 4, 4, 4, * * * *+ * * * 4, 4, 4, 4, 4 - 4,4, 4, 44 *4, **I **l~ 4, 4, 4+ 4,.I ** I 1** 0.249E 01+ + *** + + + I 44*** I **** I 4***** I 4****** 0. 305E-0 4,****..4 --- —-. + --- ----— 4 ---+ -__ -— 4+......+ 0.10E-02 0.28E 02 0.56E a2 0.85E 02 0.11E 03 0.14E 03 TRAFFIC IN RECORDS/SEC Level 3 Queuing Figure 5.11 217

to be serviced. Thus we see that the maximum indicated here of approximately 140 records per second is expected. A very rough estimate on the maximum mean waiting time can be calculated by simply assuming 4.3 requests in service at each sector and a full rotation or 33.3 ms required for each read. This gives us an average mean waiting time of 143 ms, The maximum shown in Figure 5.10 is 177 ms, clearly larger than our estimate due to the random queueing and idle periods. Figure 5.11 shows the mean queue length, which as expected runs from near 0 to just under 26, the maximum. Traffic We will now examine the traffic patterns in the system and the critical reads and writes. We will begin with the diagrammed transfers in Figure 5.12. In Figure 5.12 the data transfers which result from a user program read to each of the 3 levels of storage are shown. The solid lines indicate the transfers moving data up in the hierarchy. The dashed lines indicate the transfers required to page out or those transfers required to make room for the data being paged up. The qi indicates the size of the transfer in terms of the record sizes at the three levels, in this case q1 = 32 bits, q2 = 1024 bits 218

q 1 CPU LEVEL 1 i LEVEL 1 LEVEL 1 AD )q2 LEVEL 2 q3 )q3 LEVEL 3 LEVEL 3 Read to Level 2 Read to Level 1 Read to Level 3 Traffic Patterns Resulting From User Program Reads Figure 5.12

CPUL LEVEL 1 '~- ~~~~~~~~~~~~ '~~~~ CO LEVEL 2 rite to evel Write to Level 1 N /3 / LEVEL 3 LEVEL 3 Write to Level 2 Write to Level 3 Traffic Patterns Resulting From User Program Writes Figure 5.13

and q3 = 16384 bits as indicated in the table of record sizes given in Figure 5. 2. On the left of Figure 5.12 w see that a user program read to level 1 causes a record of size ql or 32 bits to be read from level 1 into the CPU. In the center we see the effect of level 2 or core access. In this case 1024 bits are brought from core (level 2) into the cache (level 1) followed by a transfer of 32 bits from the cache to the CPU. The downward transfer from the cache to the core of 1024 bits is necessary to maintain space in the cache for the upward paged information. The effect of a user program read to level 3, a secondary access,is shown on the right. Here we see an upward transfer of 1024 from drum (level 3) to core (level 2) and a corresponding downward transfer of the same size. Figure 5. 13 shows the effect of user program writes. The transfers performed here are almost identical to those for reads, differing only in the direction of transfer between core and cache, The transfers shown in Figure 5.12 and 5. 13 are represented in the model in the form of the "T" array shown in Figure 5.14 and 5.15. Let us examine carefully the center matrix in Figure 5. 14. Here we have a description of the traffic which occurs as a result of a user program read to level 2. The elements of this matrix are derived from the traffic pattern shown in the center figure of Figure 5. 12. 221

*** THE "T" ARRAY *** USER PROGRAM READ TO LEVEL 1 TRAFFIC RECORD SIZE AT Q(1) Q(2) 0(3) LEVEL I 1.00 0..0o 80.0 0.0 0.0 3 rt30 3.0 0.0 USER PROGRAM READ TO LEVEL 2 TRAFFIC RECORD SIZE AT 0(1) Q(2) Q(3) LEVEL 1 1.0c 2.00 3.0 2I, 3 2. a' a 3.a 2 13.3 2.303 0.3 3 3.3 3.0,3.3 USER PROGRAM READ TO LEVEL 3 TRAFFIC RECORD SIZE AT( (1) 0(2) 9(3) LEVEL 1 3.3 03.3 3.0 2 3.3 3. 2.,3 3 3.3 3.3 2.33 The Traffic Array for User Program Reads Figure 5.14 222

USER TRAFFIC AT LEVEL 1 2 3 U SER TRAFF IC AT LEVEL 1 2 3 USER 'TRAFFIC AT LEVEL 1 PROGRAM WRITE TO LEVEL 1 RECORD SIZE 9(l) Q(2) 0(3) 1.33 0.0 3. 0.3 0* 3 03. PROGRAM WRITE TO LEVEL 2 RECORD SIZE QI(1) (2) ( 3) 1.33 2.330 3.3 3,.3 2.33 3.3 3.3 3. 3., PROGRAM WRITE TO LEVEL 3 RECORD SIZE Q(1) 0(2) 0(3) 3.3 3.3 f* '3 2 3..3 3,.3. 2.* 33 3 3.3 3. 3 2.3 The Traffic Array for User Program Writes Figure 5.15 223

Notice that 1 record of size ql is read, 1 record of size q2 is read and 1 record of q2 is written at level 1. Summing up, we have 1 record of size ql and 2 records of size q2 read or written at level 1 as a result of a user program read to level 2. In the center matrix of Figure 5. 14 this traffic at level 1 is indicated in row 1 of the matrix. The rows correspond to levels and the columns correspond to record sizes. Following the same lines we see that 2 records of size q2 are read or written at level 2. This results in an entry of 2 at row 2, column 2 of the matrix. There is no traffic generated at level 3 and correspondingly zero entries in row 3 of the matrix. Each of the 6 matrices shown in Figure 5.14 and 5.15 can be derived from its corresponding traffic pattern diagram in a similar manner. This will be left up to the reader's interest and energy. We will now turn to the critical reads and writes shown in the "G" array in Figure 5.16 and 5.17. Here we specify exactly which of the reads and writes generated by a user program access must be completed in order to complete that access. We will again focus on the user program read to level 2, which correspcnds to the center matrix of Figure 5.16. This matrix specifies that the time required to complete a user program access to level 2 is the time required to read a ql or 32 bit record at level 2 plus the time required to read a ql or 32 bit record at level 1. This means that we are assuming that in the transfer from core to cache the write time at the cache is negligible or 224

*** THE "G" ARRAY *** USER PROGRAM READ TO LEVEL 1 TRAFFIC RECORD SIZE AT Q(1) Q(2) 0(3) LEVEL I 1.33 3.0 3.3 2 3.0 3.3,.3 3 3.3 ~.3 3 3 USER PROGRAM READ TO LEVEL 2 TRAFFIC RECORD SIZE AT Q(1) Q(2) 9(3) LEVEL 1 1.3 3.3 3. 2 1.33 3.3 3.1 3 3.0 03. 0. USER PROGRAM REAO TO LEVEL 3 TRAFFIC RECORD SIZE AT ( 1) 0(2) 0(3) LEVEL 1 3.3. 30. ':. 2 '3,3.3 3,3 3 "3.3.3 0 1.3 The Critical Read/Write Array for User Program Reads Figure 5 16 225

USER PROGRAM WRITE TO LEVEL 1 TRAFFIC RECORD SIZE AT Q(1) Q(2) 0(3) LEVEL 1 1.3, 0.3 2 -33* 8.3?.3? 3.3. 30.3 i3 USER PROGRAM WRITE TO LEVEL 2 TRAFF IC RECORD SIZE AT 9(1) 9(2).)(3) LEVEL I I ~ 1.33 3. 3 3. 2 ~1.23 3, 0.3. 3 3.3 3.3 3.3 USER PROGRAM WRITE TO LEVEL 3 TRAFF I C RECORD SIZE AT 9(1 ) (2) 9(3) LEVEL 1 13;.3 1.0 3. 3.3 2 3.3 3 3. 3 3.3 *3 1.33 The Critical Read/Write Array for User Program Writes Figure 5.17 226

concurrent and that we may access the required 32 bit word from the cache as soon as the first 32 bits reaches the cache from core. We have also assumed that the page down operation from the cache is carried out with sufficient anticipation to avoid delays while down transfers are made. The critical reads and writes and their associated assumptions for level 2 are far more complex than either of the remaining 2 levels. In the case of level 1 read, it is simply the time required to read a ql or 32 bit record from level 1. In the case of a level 3 read, it is simply the time required to read a q3 or 16384 bit record from the drum. It is again assumed here that neither writing in core not paging out at the core will cause delay. The User Program Five of the parameters which specify user program behavior are given in Figure 5.18. These parameters are independent variables in the program model developed in Chapter 2. Notice that the values given here are identical to the values used in the "standard" case discussed in Section 2. 7. The CPU word size here, 32 bits, also agrees with the "standard" case in Chapter 2. Continuing, the logical record or page size in the "standard" case is 16384 which is the same as the record size at the drum or level 3 in this example. Thus when we examine the relationship between primary and secondary levels in this system as a function of core allocation, we 227

*** USER PROGRAM SPECIFICATIONS *** PROGRAM SIZE IN BITS CYCLE REPETITION NUMBER MODE OF THE CYCLE LENGTH DELTA DISTRIBUTION PARAMETER ACCESSES BETWEEN NON-STORAGE INTERRUPTS 1 63 43 23.: I 33 3 3 0. 503 n0 23.0,3,03 A 4000"3 User Program Specifications Figure 5.18 228

TOTAL # OF ACCESSES/ ACCESSES BELOW LEVEL 2 0.351E 04+ + I I I I 0.316E 04+ + I I I I 0.281E 04+ + I I I I 0.246E 04+ + I I I I 0.211E 04+ + I I I I 0.176E 04+ + I I I 4 - + + ** + + + + * * * * *+ + + + + + * * 4+ + + + * * * 4 - + + + * * I 0.141E 04+ + + * + + I * I * 0.105E 04+ + + + + I * I * I * ** 74 I 03*** 0.70452E 03 + + + + + I ** I ** 0.352E 03+ * + + + + + I 0.t100E 0f 1+**I ----+ --- —--- -------- - -0.0 0.31E 05 0.62E 05 0.93E 05 0.12E 06 0.16E 06 ALLOCATION AT LEVEL 2 IN BITS User Program Behavior Figure 5.19 229

will get the same results as given in Section 2,7 for the standard case. The plot shown in Figure 5.19 shows the relation between the total number of accesses and the accesses below level 2 as a function of allocation at level 2. This is the same as the curve shown in Figure 2o 11 with obvious differences in scaling and plotting method. There is only 1 remaining independent variable to be discussed. This is the mean time required to complete an interrupt external to the storage system, such as a terminal user. The value used in this case will be 60 ms. Thus on the average a user program will require some kind of interaction with devices outside the CPU and storage system after each 4000 accesses are completed, and that interaction will cause loss of the CPU and an average wait on the external divide of 60 ms. System Performance We have at this point succeeded in wading through the independent variables in the system and we are now in a position to examine the performance of the system. The next 3 figures, 5. 20,5. 21,and 5. 22,contain the dependent variables which are generated by analysis. These 3 figures are ir - portant because we will see them repeated a number of times in the near future. Each repetition will of course contain different numbers resulting from some system modificationbut the format and meaning of the numbers will remain fixed for ease of comparison. Because of the repeated appearance of these dependent variables we will examine 230

them very carefully here to avoid the necessity for repeated explanation. Beginning at the top of Figure 5. 20, Part 1 of the dependent variables we see the mean CPU access rate. This is the rate at which the collection of M user programs makes access or reference to individual words of storage. This is the measure of work done or throughput and corresponds to the variable r defined in Equation 3.14. Next in Figure 5. 20 we find the allocation data. The first line here indicates the number and size of the programs being multipro - grammed (independent variables). This is followed by a table giving the total space and allocation at each level. The total space is the total capacity in bits or simply the product of the number of units at a given level and the unit capacity. The allocation is the space allocated to an executing program. At level 1, a dedicated level, the allocated space is equal to the total space. At levels 2 and 3, shared levels, the allocated space is 1/13 x (Total Space) as the total space is allocated uniformly to the 13 programs being multiprogrammed. The last column on the right headed %OF PROGRAM contains the percentage of the program (163840 bits) which will fit into the allocated space. Thus 5% of the program will fit into the cache, 70% of the program will fit into the core units and the available space at the drum exceeds the space requirements d the running programs by a factor of 4. 69. 231

;E' J Ci'J ACCESS RA'rE =. 649611 53E 36 *** A LL) CATI I O AT A 13?ROGRAMS WITH EACH L 'JEL T'OTAL SPACE 1I 83. 319'23 33a13E,34 2 3 1 533.a.33E.37 3 3.1 1 313.3aE.3 'JS I G 3.16334'.13E ALLOCAT I ) 3. 1 9 1333 E 3 4. 11539456E 36 3. 769a33753E 36 36 3ITS Z.F PRO GRAvI 5. 3 i 33:. 73. 4251 469.5313 C,. J/PRI 4ARY ~FFICI ECY= 23 *545% CP! J Jr I IL I Z TO X n.J.SE R 22. 51 ' AI S 3 73 1 67 'J-A I r 7/44. 373' 2 ~*** '4 E A4J TR.AFFIC *** — ')\VER.ALL r I -- C3.J ACCESS RArE =.3. 64961 1 533E.6 LE iEL U.SER ACCESS READ/WRITE RATE 1 9 6. 9 53l 4.9355:.9 3 6368 1 753E a6;2 3.3.1 77125931 0.3929 6164E;53 3 ~. 36'.3.8 75 1 38 3. 893672.33E 1. — OV)EiR PERIODS OF USE R PROGRA'4 EXECUTION — CPIJ ACCESS RATE = 3.3 2q44643E 37 LEVEL 7 USER ACC.ESS REAO/WRITE RATE ~1 96.9534;89355 3.3357632133E 37 2 3.3 1 7712 59 31;.. 1 741753 7E 36 RECORDO SIZE 3. 4 8843591E 3 2 3. 13 583931 2tE 34 3. 1 6383992?E 35 RECORD SIZE 3..34835 76E 2. 3. 1 3 1 '3'3 9E 34. Dependent Variables, Part 1, "Standard" Case Figure 5. 20 232

*** 'A.XII MU4J POSSI3LE IJtBSER OF JR~E!'JESTS FOR SERV/ICE H i4-, R.J.:'I G 13 iJSER(S). LEVEL MAX RElgJESTS 1 3 2 26 3 26 CO cw *** ACCES S IES*** — S EC 3O DARtY ACCESS E J /I R) 'M\IET — 1EAtNA T rT A L LEVEL SERVICE iRATE SERVICE T'I 1E 2:3.39296E 35 3.92733E-5 3.3 89367E:2. 671 29E-31 EXT.r 16243E 33.3 63J, 3 E3- 31 -- RI.'ARY ACCESS E IRO,:.J T - - MEA '1A tEAM4 TOTAL LEVEL SERVICE RATE SERVIICE TIVME 1 '.3.3576E 37 3.41495E-36 2 3. 17413E 36. 15155E-3 4 lEAJ Q iJ.J LE GTH 3. 3646. 5. 99913 'q ~ 4.,EAl 'qJEQUEJE LE:N GTH 1.26376 2.63963 ME A CRITICAL SE RVICE T I E 3. 3 3.14435E-31 3. 47354E-3 1 WEAN CRITICAL SERVICE TIME 3.2 73 75E-3 6 3. 38642E-36 RELATIVE EFFECT '% 3 5376 '23.5376 76.4624 RELATIVE RFFECT %7 41.4617 53. 5265 Dependent Variables, Part 2, "Standard" Case Figure 5. 21

MVEAN TIME TO COMPLETE A PRI'MARY ACCESS MEAN TIME TO COMPLETE A SECONDARY ACCESS MEAN EXEC'!.JTION TIME BEFORE SECONDARY PAGE FAULT M4EAN TIME BETWSEEN PRIMARY ACCESSES TAIJP= TA!JS= 3. 663241 4E-36 0.61 53823E-01 TAUE= a3. 1337519E-P2 TAJUC= '3. 3466848E-?6 Dependent Variables, Part 3, "Standard" Case Figure 5.22

The cost of storage hardware is simply a summation of the costs associated with each of the storage devices used. In this case we have 1 cache, 3 cores and 1 drum or 5 devices, each assigned a cost of $50,000 or a total of $250,000. Continuing we find several efficiency and utilization figures. First there is the CPU/PRIMARY EFFICIENCY given as 28. 845%. This figure is a measure of CPU efficiency when it is in fact executing a user program. This simply says that when a user program is executing,it is executing at 28. 8% of the rate that it would execute if the user program were located entirely in the cache. In terms of the model variables this figure is simply (r'/r ) x 100 where r' is the CPU access rate during user program execution. (r' defined Equation 3. 15) The CPU utilization is given in the form of 3 percentage figures - user, system and wait. The user figure is the percentage of time that the CPU spends executing a user program, 22.,5%. The system figure is the percentage of time the CPU spends doing the bookkeeping tasks associated with user program interchanges. Finally the percentage of time the CPU spends in an idle or wait state is given. The remaining data at the bottom of Figure 5. 20 gives us the access behavior and traffic environment in the system. We begin with 235

the mean traffic based on an average over all time. We see first the CPU access rate. This is simply a repeat of the mean CPU access rate given at the top of the Figure. Continuing we have a table giving data for levels 1 through 3. On the left we have the %USER ACCESS. This column gives us the percentage of all user program accesses which are made to each of the 3 levels. The second column headed READ/WRITE RATE gives us the rate at which records are being read and written at each level. The final column displays the mean record size for each level. In terms of the model the data shown here comes directly from the ui,Ci, Ai defined in Equations 3. 70-3. 72, 3.19 and 3. 21 respectively. The final and remaining table is the same as the one we have just considered except here we are looking at the system only over periods of user program execution. The CPU access rate given here is r' the rate taken during periods when CPU is busy. The read/write rate and the mean record size are likewise taken over periods when the C PU is busy. The percent of user access given in this table is the same as in the previous table. The read/write rate is simply C'i defined in Equation 3. 29 and the record size is Ai, defined in Equation 3.31. Turning now to Figure 5. 21 we have a group of dependent variables which are closely related to the performance at individual levels. At the top of Figure 5. 21 we have a table expressing the maximum number of requests for service which can occur at each cf 236

the three levels. The values given here are the same as those used earler when examining the performance characteristics of the individual levels. The values in the table are the Bj's expressed in Equation 4.3 where j indicates the level. In the lower part of Figure 5. 21 we see 2 tables, one labled secondary access environment and another labled primary access environment. In the first of these tables (i.e. describing the secondary access environment) we display information about the traffic at the shared levels of storage as seen by a user program making a secondary access. That is, the averages are taken over all time. In addition to the shared levels, levels 2 and 3, data describing the external interrupts are given. Under the heading MEAN SERVICE RATE we have the rate (over all time) at which records are being read or written at each level. In the case of external interrupts this is the rate at which these external transactions are being carried out. Notice that this column is identical to the column headed READ/WRITE RATE in Figure 5. 20 except the dedicated levels are omitted and external behavior is added. In the next column we give the mean TOTAL SERVICE TIME (read/write) for a record of the mean record size under mean traffic conditions. This is an after-the-fact calculation based on mean values and thus may not relate directly to the system performance, but itprovides a measure of the general congestion and delay at a given level. Based 237

on this mean total service time and the mean service rate we compute a queue length which is found in the next column. It should always be kept in mind that the mean total service time given here and the mean queue length are based on the average record size and average service rate. In some cases this presents a problem and in others not. Note that for level 3 in this system all records read or written are of size 16384 bits and thus the values given have a precise meaning. Turning now to the MEAN CRITICAL SERVICE TIME, in this column we see the components of the sum which make up the mean secondary access time r. The critical service time at level 2 is 0 s because delay at level 2 is not considered part of the time required to complete a secondary access. This is of course a function of the "G" array. Notice also that the external interrupts are considered part of the secondary access behavior. The final column simply gives the percentage of each of the components which make up r. In this particular S system on the average programs ineligible for CPU use spend 23. 5% of the time (before becoming eligible for execution) waiting on a drum transfer and 76. 4% of the time waiting on some external action to be completed. The table of data given for the primary access environment is the same with a few exceptions. Here we show only the primary levels and base our calculations on the mean traffic and mean record size taken over user program execution time only. The mean critical 238

service time here consists of the components of the sum which makes up the mean primary access time r. P Arriving now at the final of the 3 displays of dependent variables Figure 5. 22. This is by far the simplest figure and displays p, T, and rc from chapter 4. These are given here in the form TAUP, c TAUS, TAUE and TAUC respectively. Having spent a considerable period of time examining the individual numbers presented we will now discuss for a moment what these numbers are telling us about the system. First of all the CPU is executing near 28. 8% of its specified capability. This low CPU efficiency was a surprise and the cause was not immediately appar.ant. However, on more careful examination the deficiency becomes clear. Notice that the allocated space at the cache is 5% of the program size and that the most likely loop length is half the length of the program (p=.5). Thus the cache is operating in aseverely under-allocated manner. That is, words brought to the cache are rarely used more than once. This means that in accordance with our defined traffic patterns, each word read or written by the CPU must be brought from core to cache, then read or written while in the cache and then later transferred to core. Most important in all this is that each word accessed by the CPU requires 3 accesses at the cache; 1 to bring it into the cache 1 to remove it from the cache 1 CPU read or write to the cache. 239

Since as we discussed earlier the cache has a maximum read/write rate for 32 bit records of 12. 5 million per second the CPU will be limited to 1/3 of that or 4.17 million accesses per second or 41.7% A of the maximum CPU rate r. Thus we clearly have a bandwidth problem at the cache. It is most interesting to note that in the IBM 360/85 which uses a similar cache. structure, the data flow is such as to avoid traffic at the cache. If we were operating a 360/85 under roughly the same conditions, a read would generate 2 cache operations (one on the core to cache transfer and a second on the cache to CPU transfer). We are ignoring here the first word of a block which need not be read from the cache but is transferred directly from core to the CPU. In the IBM 360/85 [16,37] no downward transfer is required when the data is not modified. In the case of writes the cache is avoided entirely and the words are written directly in core -with sufficient buffering to avoid delay. When a write is made to a word already in the cache, that word is modified in the cache but it is also modified directly in core at the same time in order to avoid a later transfer from cache to core adding only one write to the traffic at the cache. Examining the effect of core delays on the CPU rate we see that the core is having considerable effect. (See the relative effect for primary access environment Figure 5. 21o) A Solution here would be to use more core units and a larger record size: more core units to increase the bandwidth at core and a larger record size to incur the 240

delay at core less frequently. Following along the same lines as we did for the cache, one finds that current core bandwidth would limit the CPU access rate to under 6 million per second. It is interesting to note that the traffic patterns in the IBM 360/85 reduces the traffic at both the cache and the coreo Experience with this model indicates that the effort to eliminate unnecessary traffic is important. Thus far we have concentrated on the efficiency of the CPU when it is executing a user program. This, although very interesting, is not the limiting factor in the performance of the system. From the CPU utilization figures we see that even at its reduced execution rate, the CPU is idle 74.3% of the time. This means that the accesses to the drum and/or the interaction with devices external to the storage system are limiting the performance. In Figure 5. 21 the relative effects of these two activities are shown and we can see that neither is negligible. We will consider several changes in the system in the next few sections which will give us some insight into the behavior of the system and expecially the relationship between the primary and secondary levels. As we progress we will want to compare and contrast the performance of other system configurations with the one we have just examined. We will refer to the system studied here as the "standard" system when making comparisons. 241

5.3 A Hardware Modification We are at liberty to modify the system in many ways. We will begin with the simple hardware modification of replacing the current drum at level 3 with a drum indentical to its predecessor in every respect except rotational rate. In the "standard" case just considered, the drum RPM was 1800. We will now double that to 3600 RPM and observe its effect on the system. The results of an analysis for this new system are shown in Figures 5. 23, 5. 24, and 5. 25. The system now being considered is identical in every respect to the "standard" case except for the drum RPM. Comparing the results of this analysis with that of the "standard" case we see an overall increase in mean CPU access rate from 649 thousand accesses per second to 772 thousand. The CPU utilization has increased by several percentage points. Notice that the CPU/PRIMARY EFFICIENCY has dropped slightly. This is due to the increased core congestion resulting from the increased drum bandwidth. In Figure 5, 24 we see a mean queue length at the drum of 2. 2, a drop from 6 in the "standard" case. Notice that the external interrupts now constitute over 90% of the secondary delay. The system could be described as IQ( bound. Notice that access time at level 3 is now less than 1/2 of its previous value. This is a result of both the increase in service rate and the decrease in queuing. 242

MlEAN CPJ ACCESS RATE = 3772937013E 36 *** ALL) CAT I AA: r 13 PROGRAMS WITH EACH LEVEL TOTAL SPACE I 3~.8192-3331E 34 2 3.15 33333E,3 7 3 3. 133,,3333 E 33 USING 0.1 638433E ALLOCAT I ON.3S1923333E 34. 1 1538456E 36,3. 76923 75E 36 36 BITS 7 OF PROGRAM 5.3 333 73. 4251 469 5,31 3 CPJ/PR IARY EFFICIE,'MCY= 2.8 8 19% CPtU tTILIZATION USER 26. 52% SYSTEM 3.696% WAIT 69. 454 *** ME AN TRAFFIC *** — OVER ALL TIME — CP!J ACCESS RATE = 3. 77293733E '36 LEVEL % USER ACCESS READ/WJRITrE RATE 1 96.95 14189355 3.31 934l36`E '36 2 3.~31 77125931 3.46756344E 35 3 3-.336837851 38;3. 1363331 1E '33 — OVER PERIODS,OF USER.ROGRA:', EXECIUTJIIOJ — CPU..J ACCESS RATE = 03.23519233E 37 LE iEL 7. UJSER ACCESS READ/WRITE RATE 1 96.95134839355 3.33354933E,07 2 3..3177125931 3.174:34253E 36 RECORD SIZE 3.8348591E 32 3. 1359312E 34 3.16383992E 35 RECORD SIZE.3,34359 IE 32. 1 333 345E;34 Dependent Variables, Part 1, for Drum RPM= 3600 Figure 5. 23 243

*** MAXIMUJ' IPOSSIBLE 'IU'4L3ER OF R JUESTS FOR SERVICE WHEN R'iJMI\NG 13 USER(S) LEVEL MAX REQUIJESTS 1 3 2 26 3 26 *** ACCESS TIMES *** — SECONDARY ACCESS ENVIRO:34EN ET — MAEAN MEAN TOTAL 1EAq4 OUEUE LEVEL SERVICE RATE SERVICE TIME LENiGTH 2. 46756E 35.94975E-.5 0. 4443 7 3 0.13633E 33.23735E-a31 2.20163 EXT 3.19323E 33 3.630.3E- J1. A. ZGOROi)OD ROBERTS *** PLEASE CALL 763-3197 *** — PRIMARY ACCESS ENVIRONMENT — MEAN MEAN TOTAL MEAN QJEUE LEVEL SERVICE RATE SERVICE TI IE LEANGTH 1.33549E 17 3.41474E-36 1.26731 2 03 17434~E 06 3.1513.6E-04 2.64297 MEAN CRITICAL SERVICE TIME 3.03 3. 44675E-3 2. 473 54E-t31 RELATIVE EFFECT % '.6713 91.3237 RE9LTI VE EFFECT 2 41.3919 53.5964 MEA>N CRITICAL SERVICE TIME 3.27354E-0 6. 33 724E-6 Dependent Variables, Part 2, for Drum RPM= 3600 Figure 5. 24

MEAN TIME TO COMPLETE A PRIMARY ACCESS i'EAN TIME TO COMPLETE A SECONDARY ACCESS MEAN, EXECJT ION T I'ME X~ 9~BEFORRE SECONDARY PAGE FAULT 1 4EAN- T IE 3~'ETWEEr i PRIMARY ACCESSES TA!JP= TA'JS= T A!JE= TAU = 3. 663 3528E- 6. 1 5 1 1 4E-31 13 8 4 7E-O-P * 34699.5E-316 Dependent Variables, Part 3, for Drum RPM= 3600 Figure 5. 25

It is interesting to note carefully the slight changes in the primary levels, At the bottom of Figure 50 24 under primary access environment we see that mean critical service time at the core has increased slightly as a result of the increased traffic from the drum. This in turn has slowed the CPU slightly and reduced the congestion at the cache. This of course in turn reduces the critical service time at the cache. All of this results in a very slight increase in T (TAUP) P given in Figure 5. 22 and a very slight decrease in the mean CPU access rate when a user program is executing, 5.4 A Change in User Program Characteristics We will now observe the effects of making changes in the user program characteristics. The specific variable to be changed here will be p. This variable controls the mode of the distribution of loop lengths. in the user program model. In the "standard" case p =.5 making the most likely loop length 1/2 the length of the program. We will observe the effects of p =.3 and p=o 7 here. The lifecycle function behavior for these values of p is shown in Figure 2.12 and this applies directly to the relationship between primary and secondary storage in this system. Note that the system now being examined is identical to the "Standard" case except for the variable p. In the case of p =. 3, shown in Figures 5. 26, 5. 27, and 5. 28, we have a small performance increase, The CPU is running faster 246

MlEAM CP'J ACCESS RATE = 3.69133353.E 36 *** ALLOCATI3 3 DATA *** 13 PROGRAVIS WITH EACH USI:GG I3.1638430E LEVEL TOTAL SPACE ALLOCATI3N 1 ~3.319239.'E 34 *3.8192-.:3.3E 34 2. IS533.a, E 37 3.11538456t 36 3 3-1. 1 3333333 E 133 3. 769 23 75E 36 36 iITS Z OF PROGRAM 5. 3333 73. 4251 4 69. 53 1 3 CPIJ/PRIMARY E FFICIE ICY= 33. 66 7x CPUJ JTILIZATION. USER 22.1 I 4 SYSTE'v 3.1747_ WA IT 74.642% *4* MEAN\ TRAFFIC *** — OVER ALL TI E — CPUJ ACCESS RATE = 3.63333353E 36 LEVEL.72 USER ACCESS READ/A IRITE RATE 1 97.1763253936 3.71312312E 36 2 2.7928657532 3.3S334635E 35 3 3).3361 1313 942. f3.3315533 32 — OVER PERIODS OF USER PROGRA'1 EXECJTIJO — CP ACCESS RATE = g. 333 6 73.33E?3 7 LEVEL 7. USER ACCESS READ/WRI TE RATE 1 9 7. 1 7632 5 3 9;3 6 3 33 7 3323E ' 7 2 2.7923657532 3. 1 7138269E 36 RECORD SIZE 3.S4494583E 32 3.13574313E 34 3. 1 6334.33E '35 RECORD SIZE 3.84494537E '32 3.13314432E 34 Dependent Variables, Part 1, for p =.3 Figure 5.26 247

**:A-XIUJ' PO~3SSI3.E,LJ3ER )OF rFCJESTS FJR SERVICE H~E: R!Jx',jI:G 1 3 USeR(S) LEV'eL A'AX RE.'JESrS 1 3 2 26 3 26 00 *** ACCESS TIMES *** — SECON4OARY ACCESS E _VIRJ3,M~EIT — v1EAA M1EAAil TOTAL LEVEL SERVICE RATE SERVICE TI IE 2 I.33 33351E 35 3.9229S5E-'5 3 3.3:116E 32 3 3.612:2E9E-:l EKT 3.1733SE 33 3,63..3E- 1 — DRI4ARY ACCESS ENVIlRO'4EIT — '4]EA\ J vi EA:J T OTAL LEVEL ERVICE RATE SERVICE TIEE I,,~3.32371E 37. 393 75E- 6.2...3.1I 7133E 3 36 -3. 14932E-...3 4 VIE A J QUEUE LEl GTH 3., 35153 5. 332835 viEAiJ.J.EUE LE GTN 1. 293.,33 2.55935 MEAi CRITICAL SERVICE TIME ~. -12. 1 E-31 3.4.233E-31 EA:N CRITICAL SERVICE TItlE 3 ~6752E-36 3.35143E-36 RELATIVE EFFECT % 19.9394 33.9616 RELATIVE EFFECT % 43.2156 56. 7735 Dependent Variables, Part 2, for p =.3 Figure 5.27

"EAN TI'4E TO C'OMPLETE A PRI4 ARY ACCESS MEAN TI'E rT CYOMPLETEf A SECOi)ARY ACCESS 1EANJ EXEC!.T I Ol T TIIE BEFOFRE SECO:DA.RY PAGE FAULT EAJ.N TIA E ET EE:J v PRI 'ARY ACCESSES r A IJP = TA!JS= T AU JE = 'a. 619.1J3 3_-'3 6 *.6329433E-31.3 3484573E-32 326'3 793E-3 6 Dependent Variables, Part 3, for p =.3 Figure 5.28

AEAN CPU ACCESS RATE = 3.331 55381E 36 *** ALLOCATION DATA 13 PROGRAMS WITH EACH LEVEL TOTAL SPACE I..819213333E 04 p 3,.153332JE 37 3 3.13'11333E 13 IUS IG 1. I 6343.3E ALLOCATION.8192,3330E 34 3.1 1538456E:36 3. 769.23,3 75E 36 36 BITS 7 OF PROGRAM 73.4251 469 *5.31 3 C'J/P RI 1ARY EFFICI EJCY = 28.445% CPJ UJTILIZATI:O'N U3SER 13.631 SYST E 2., 93 7 WAq I T 37. 33 67o 4** E4 'N~; TRAFFIC *** -.-OVER ALL TIME — C!J ACCESS RATE =.*33155331E 36 LEVEL 7 USER ACCESS READ/WRITE RATE 1 96. 39 996532 1 3 1 98 9361 E 36 2, ~3. 36:8232:4346 3. 1'86":"33.83E 35 3 3.321271513 7 3. 1223996E 33 — O\VE'R PERIO 3 S OF JSER R 3GRA4 EXECuJTIOMiCP A CCESS R-ATE = 3.2 84/44663E 37.LEV~/EL Z JSE R ACCE"SS REA)/WRITE RATE 1 596.*9339965? ~ 3.3317339E 3 7 2 3.3.162'234346 3.17436937E.'36 REC ORD SIZE:3..3933 75E ' 32 3. 11299432E ";4 '3. 1 638 4-333E. 35 RECJORD 3SIZE 3. 9233359E 32 3.1 353313E 34 Dependent Variables, Part 1, for p =. 7 Figure 5.29 250

*** MAAXIMU! JJ POSSIBLE >Nl:.;BER OF ORERQUJESTS FOR SERVICE WHEN RUNNING 13 JUSER(S). LEVEL MAX REJQUESTS 1 3 2 26 3 26 c3n *** ACCESS TIIES *** — SECOND.ARY ACCESS ErJVIR3NMiEJTT — 9, EA'J\ MEAN TOTAL LEVEL SERVICE RATE SERVICE TIME 2 3.1S633.E 5 3.93338E-35 3 3.12?29E 33 3.13317E 33 EXT 3. 75388E 32 3. 6'3330aE-31 — PRIMARY ACCESS EIVIRONIMENT — MEA4 M EAN TOTAL LEVEL SERVICE RATE SERVICE T I ME 1 3.33174E 37 3.41771E-36 2 3.17437E 36 3.15264E-34 IEAN Q IJUEUE LEN GTH 3. 1 7373 16. 69951. MA. M E A:J QIUEUE LEN GTH 1. 26.343 2. 661 62 M;IEAN CRITICAL SERVICE TIME '3 * 3 3. 59941E-31 0.32417E-31 MEAN CRITICAL SERVICE TIME 3.27453E- 6 3.39533E-36 RELATIVE EFFECT X 3.3 64.3623 35.1377 RELATIVE EFFECT % 43.9711 59.3355 Dependent Variables, Part 2, for p=. 7 Figure 5.30

'4FEAN TIE ' TO COMLPLETE A PRIMARY ACCESS 4 EA4> TIME Tr C3OMPLE'TE A SECO)NOARY ACCESS MDEAN EXEC!JTION TIA1E MND B 39EFORE SECO3ND RY PAGE FAULT MEAN TIVME 3ETWE-EM PRIMARY ACCESSES TAUIS= TAJUS= T AU t = TAUC=.669991 4E- 6 3 9225 79E -3 1 3. 7597762E-33.351 559E-3 6 Dependent Variables, Part 3, for p =.7 Figure 5.31

when executing a user program raising the CPU/PRIMARY EFFICIENCY to 30.6%. This increase is influenced by at least 2 factors. First, executing program will require fewer accesses to core. (See %User Access in APrt 1.) Second, the congestion at core is reduced by the reduced drum-to-core activity. This all results in an increase in CPU execution rate,which causes an increase in general performance while increasing the CPU idle time slightly. In this case, both p =.3 and p =. 5 (the "standard") represent cases where the core allocation is adequate and thus the difference in performance shown is small. In the case of p =.7 (shown in Figures 5. 29, 5.30, and 5.31) we no longer have adequate allocation in core and the performance changes are more dramatic. The % of user accesses to level 3 jumps by a factor of 3 and the mean queue length at the drum rises to over 16. Here we see the delays causes by the drum begin to predominate over the I(~ or external interrupts. The overall performance of the system is reduced to a little less than 1/2 of that in the standard case as a fairly direct result of the increased secondary paging activity and associated congestion. 5. 5 Changing the Number of User Programs Here we will observe the changes in performance which occur as a result of varying the number of user programs being multiproing grammed. Our approach will be different in that rather than providing 253

1,000,000 < 0 0 LU 0 oL QoCL = LUA CY 00 = LLJ sE 800, 000 600,0004 400, 000 200, 000 0 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 NUMBER OF PROGRAMS Performance Versus Number of Programs Figure 5.32 100 80 W-' 0 N -= m_ 222 __ 60 40 Wait User System - - - -. - 20t L 'L An _ I I ' 1 Tr I_ _ _ _ _ _ _ _ _ _ _ 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 NUMBER OF PROGRAMS CPU Utilization Versus Number of Programs Figure 5.33 254

C) (/) LJ..) C.) 0 <12 LLJ.) I. >C-) LU L. LL. LLJ LU i.I - Li mo I<1 cO C.. 100 80 Level 3 Acca 60 40 20- External In 0 10 11 12 13 14 15 16 17 18 19 20 21 2 NUMBER OF PROGRAMS Relative Effect Versus Number of Programs Figure 5.34 eSS 2 23 24 80 60 40 20 01 I I I 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 NUMBER OF PROGRAMS Allocation Versus Number of Programs Figure 5.35 255

all the details of 1 or 2 cases, we will plot some of the more interesting dependent variables as a function of the number of programs running. The system performance or mean number of user program accesses per second is shown in Figure 5.32 plotted as a function of the number of programs. We see very quickly that the maximum performance is achieved with 13 user programs, the number chosen for the "standard" example. Figure 5.33 displays the CPU utilization figures. Notice that the peak in system activity occurs to the right of 13 user programs. This is a result of a higher rate of user program interchanges occuring for the larger number of programs. The basis for this will become clearer as we proceed. Figure 5o 34 shows the relative effect of the drum at level 3 and the external or I0 interrupts. When we run fewer programs the external interrupts dominate the secondary delays. As we increase the number of programs the drum at level 3 becomes the dominant factor. We will begin at Figure 5.35 to show the cause of this shift in dominance. Here we have plotted the core allocation as a function of the number of programs. On the left with 10 user programs over 90% of the user programs can be found in core. As we move to the right to 24 user programs the allocation in core is reduced to less than 40% of the user programs. Thus in the range from 10 to 24 programs we move 256

0.10 (I) LUJ C). LUJ 0 LLU LLJ Cn) 0.08 0.06 0.04 0.02 0 I 1 I I I I I I I I I I I I 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 NUMBER OF PROGRAMS %of Level 3 Accesses Versus Number of Programs Figure 5.36 50 C._ -J cL - LU - LU LL Ol 40 30 20 10,e\NPJ Q\Ye 10 11 12 13 14 15 16 17 18 19 20 21 2 NUMBER OF PROGRAMS Queue Length Versus Number of Programs Figure 5.37 257

0.5r A 0.4 0.3 V 0.2 Cz oi' 0.1 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 NUMBER OF PROGRAMS Access Time Versus Number of Programs Figure 5.38 C 0.5 0.4 0.3 C-) 0 0.2 U0 0.1 0 I I I I I I I I 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 NUMBER OF PROGRAMS Secondary Access Time Versus Number of Programs Figure 5.39 258

from a situation of more than sufficient space in core to a condition of severe under-allocation. Figure 5.36 shows the %of user program accesses to the drum as a function of the number of user programs. When compared to the previous figure we can see that the sharp increase in accesses to the drum begins as the allocations drop below 60% of the user program. This should be expected since this is the region of transition or greatest slope in the lifecycle function. The queueing at the drum is shown in Figure 5.37. First we see that the maximum number in queue at level 3 increases linearly as we would expect. Again as we increase the number of programs running, to the point of causing poor allocation at core, the drum queue increases and approaches the maximum. Figure 5.38 shows the mean access time at the drum. This access time follows the queue length and the effect of the maximum queue length can be seen on the right. Lastly, Figure 5, 39 shows the mean secondary access time. For a smaller number of programs the secondary access time is dominated by the external interrupt behavior and thus is roughly 60 ms. For a larger number of user programs, the secondary access time behaves more like the level 3 access time, which becomes dominant as more user programs are introduced. 5.6 Summary We have only been able to scratch the surface of analysis possibilities here and it is a short scratch at that. We have not varied the 259

number of levels, types of devices, data paths, logical record sizes, or the CPU behavior,and this certainly is not a complete list. One of the most interesting cases of analysis was undertaken when attempting to choose a "standard" case to make variations around. Most all of the initial systems worked with had a severe bottleneck. This severe bottleneck dominated the performance of the system to the point of obscuring most of the interesting interrelationships shown in the previous examples. One of the most stifling bottlenecks turns out to be the CPU. The choice of such poor CPU utilization in the "standard" case was most deliberate. 260

Chapter 6 System Optimization In this chapter we will be concerned with optimization. After a statement of the problem we will consider several examples. 6.1 Objective Function and Method The objective of the optimization will be to maximize r, the mean user program access rate, with a dollar constraint placed on the total value of the storage hardware. The choice of r as an objective function means that we are maximizing the system throughput. We are ignoring other system characteristics such as response time. Decision Variables Simply stated the decision variables are: lo The number of user programs being multiprogrammed. 2. The number of storage units at each level. 3. The logical record size at each level except level 1. More carefully: The number of user programs, M, must be an integer satisfying min max M < M< M where min M = Minimum allowable number of user programs and ax imum allowable number of user programs. M = Maximum allowable number of user programs. 261

We define: N. = Number of storage units at level i (Note that N without subscript is the number of levels) The decision variables N. must be an integer satisfying min max Ni < Ni < Ni where min N. = Minimum allowable number of storage units at level i and 1 m ax Ni = Maximum allowable number of storage units at level i The logical record or page size, qi, is considered a decision variable at all levels except level 1, or i =1. The variable qi must satisfy min max qi < qi < qi where q. = Minimum allowable record size at level i. 1 and qi max Maximum allowable record size at level i. In addition qi must satisfy: qi = 2 for some positive integer n Thus far we have considered rather direct constraints imposed on the decision variables. We will now consider several less direct constraints which are applied to eliminate infeasible systems. First we require that the logical record size at level i + 1 be greater than or equal to the logical record size at level i or: qi+l qi 262

If this constraint is not satisfied the paging activity simply does not make sense. Next we will require that the allocated space at each level increase as we move down in the hierarchy. This can be expressed in the form of 2 relations: N S unit > N Sunit i+1 S > N.S. and N. S* unit i+1 1+1- > N S for L > M - LL where S. t= the storage unit capacity at level i 1 The first of these relations simply says that the total capacity at each level i + 1, Nil Si+., must be greater than the total capacity at level i. This is sufficient to guarantee increasing allocation at each lower level except at the interface between dedicated and shared storage. The second relation applies to this dedicated-shared interface if it exists (L > 0). Next we are concerned with a relationship between storage allocation and logical record size. The space allocated to a user program at level i must be equal to or greater than the record size at the next lower level i + 1. If this is not the case there is simply insufficient space at level i to store a record brought up from level i + 1. This again requires 2 relations - one for the dedicated levels and one for the shared levels: 263

unit N.S i t > q for i < L 1 i fqi+r l and and unit N.S. 1I > qi+1 for i > L M Next we will require that there is sufficient capacity at level N to accommodate all of the M user programs: N S unit > MQ NSN > MQ where Q is the size of the user programs. We will also require that an N level system be operated as such. That is we will not allow a level above level N to be sufficiently large to contain all of the M user programs running thus effectively making the lower levels useless. This is simply expressed: unit N.S. < MQ for i < N. 1 1 Last and very important is the dollar cost constraint. Defining unit C. = dollar cost per unit of storage at level i 1 and C = maximum allowable dollar expenditure We will limit the number of devices at each level such that: Cmax> N NiC.unit - i=l 1 and max N uN uunitt unit unit CaC - ni 1 < minmCi c C2,...,Cn ~~~~~~~~~~~~uitI) 264

max The first relation limits the cost of the system to C or less and the second relation requires that difference between the cost of the system and the maximum allowable cost not equal or exceed the cost of any single unit of storage. This last constraint requires some discussion. It is reasonable if we can assume that the addition of a storage unit always improves the system. This may be a reasonable assumption for some systems and not for others. For those systems where we are not willing to make this assumption we must vary max by increments of unit unit unit min {C1,C nit,,Cn } to get a series of optimums for ranges of system cost and select the global optimum from that series. The constraints just discussed leave us with a set of feasible configurations. We will now turn our attention to the process of selecting the optimal configuration from the feasible set. The approach is simply an intelligently ordered exhaustive search of the set of feasible configurations. Generally speaking there are 2 areas where significant economics are introduced in the search. The first of these economics involves the system model itself. As you will recall, the process of analysis involves a search over values of r. At each step in this search we assume an r (mean user program access rate) and the model's response simply tells us if r is too large or too small. In the search for an optimal configuration we will need only to determine if a given configuration will perform better or worse 265

than the highest performance thus far encountered in the search. If a configuration's performance falls below the highest previously encountered performance no further analysis is required and the configuration can be eliminated. If a configuration does in fact have a performance higher than any previously encountered, a complete analysis is performed to determine its precise performance. Since only a small minority of the configurations will require a complete analysis a savings of roughly 20 to 1 is experienced. The second area of economy of effort is found in the ordering of the search. The reduction is achieved by making use of the fact that certain intermediate results can be saved and used repeatedly as the search proceeds. 6. 2 A Simple Example We will now consider an optimization of the "standard" case discussed in the previous chapter. Before becoming involved in the optimization itself we should say a few words about the computer program performing the optimization. First, optimization and analysis are performed by the same program. From the point of view of analysis any of the models' independent variables may be modified. When an optimization is requested, the decision variables in the model are adjusted within bounds to maximize the mean user program access rate. Figure 6.1 shows the decision variables. (Note that the record size at level 1 is not considered a decision variable and is included 266

here only for symmetry.) The center column labled CURRENT shows the values of the decision variables. The columns on the left and right show the imposed bounds on these variables. The current values shown in Figure 6. 1 are simply those of the "standard" case discussed in the previous chapters. Following optimization these values will be adjusted to maximize the meanuser program access rate. Under the given bounds on decision variables we will examine configurations running fromn 2 to 25 user programs, using from 1 to 4 caches, 2 to 4 cores, and 1 to 4 drums. The logical record size at level 2 may range from 128 bits to 4096 bits and at level 3 from 4096 bits to 65536 bits. The'record size at level 1 is not considered a decision variable and thus will be fixed at 32 bits. For a first optimization we set the maximum cost, C ma, at $250,000. This will allow 5 units at $50,000 a piece in the system. Note that this does not change the number in the system but may allow for some rearrangement. The optimization reported a total of 20,124 possible configurations of which 972 were feasible and required a CPU time (IBM 360/67) of 42 sec. The resultsof this optimization are shown in Figures 6. 2 through 6. 5. Figure 6. 2 shows the decision variables. We can see that the optimum system differs from the "standard" case in 3 decision variables. The number of user programs has dropped to 12 from 13. 267

DECISION VARIA9LES iMVl,~ I.'J. CJURREIT MAX I i!J, OF PROGRAMS 2 13 25 * LEVEL 1 * # OF!JiITS 1 1 4 RECORD SIZE 32 32 * LEVEL 2 * I OF J-ITS 2 3 3 RECORD SIZE 123 1324 4396 * LEVEL 3 * ~ OF!J'ITS 1 1 4 RECORD, SIZR 4396 16334 65536 Decision Variables for "Standard" Case Figure 6.1 268

rCISI 3 VA1IA3LES '1q 1 ]. A I ' J: C'J.R R r,,T '1A( I Jjvl # ) F PRO,3GRAAIS I? * LE'JEL I * # )F.J ITS RECOR' SIZE * LFVEL 2 * # -R ~JNI rS REC;),R S1 Z E * LEVEL 3 * # 'F i.J JITS REC:RD) SIZE 1 32 2 1 1 32 3 256 1 32763 4 32 43 9 4^96 4 65536 Decision Variables for Optimal $250,000 System Figure 6.2 269

MA.-N CPU ACCESS RATE = 3.-65334733E '36 *** ALLOCATI ON D'ATA *** 12 PROGRAMS WITH EACH!JSIMG. 3. 1638.433.E LEVEL TOTAL. SPACE ALLO'CATI '3O i1 3.8 19213333E 34 3.01923"'3. E 34 -2 3 1 5.-533a3E' 3 I -.1 25-:3333E: 36. 3 '..I 31.'33IE: - 38:3 333333331E 3-6 36 BI TS: %.. OF PROGR4AM1 5 *I33'33 76. 2939 -5383 62 62.: CP'J/PP I MARY EFFICIENCY= 29. 313% C'U.J T I L I Z AT T I I ] L JSER 22.30 83 SYSTE 4 2 837 7 WAIT 74. 885,**,EA- - TRAFFIC *** — OVER ALL TIMIE — CPU.J- ACCESS RArE = i 6538473 3,4.73'E 3'6 LEVEL 7. USE.R ACCCESS RE-AO/DiWR.ITE RArTE I 33.1717 1 -.3 9'6 7.3 1 3. 3.3 79:,,3 9 4.'E 36 1 -1 2.. 3 76 5 63.15435 3 69 E... 6" 3 3.3 336-1 7676; 3.4 73.3 39E.'3 2, — iOV'ER PERIO)DS: OF" UISER PROGRA; E.XEC:cUrION — CPUJ ACCESS. RATE = 3.- a93396.33E 37 LE. V L 7 i.UJSER~ ACCESS RE-AD/WR I TE. R.ATE 1 S3 t 7 t. 1 9 6933 1 83 3.3 6 -1 85 3E 3-7 a2 I ~ 1.3-33 3. 7 75.63,.691771567 E 365. Dependent Variables, Part 1, for Optimal $250,000 Figure 6.3 RECORD.; SI-Z: 3. 74 73 9.45 E 32 3.26596,411i E 33 3.3 2376799 2. 5 RE.COR.: SI;ZE: 3.74:78 91t4E '3I2 3. 25832-339E. 3.3 System 270

*** MAXI"AT PO4SSIBLE l+JM193ER OF REQ)JESTS FOR SERVICE WHEN' RJr'4iNING 12 JSER(S). LEVEL ilAX REO iJESTS 1 3 2 24 3 24 IN, -^1 h-A I *** ACCESS TI ES *** — SECO.\DARY ACCESS E JVIRO:MIE:Tm.E AM '4 EA'N TOTAL LE VEL SERVICE RATE SERVICE TINME 2 3.15436E 06 3.23266E-'5 3 1.47338E 32 3 *.323 65E - EXTr. 1 6346E 3 3. 6 333E-_3 1 — P'RI MARY ACCESS E'VI RO 'EN 'T — '^A l -AA MEA' TOTAL LEVEL SERVICE RATE SERVICE TI IE 1 3.36219E 37 3.35393E-36 2 3.691 77E 36 3.37721E-35 vM.A N QJUE LE GT H 3.35913 3.38234 A. A. v EAlq O'.JEi.JE LE4 GTH 1.2 71 33 2.63941 MEEA: CRITICAL SERVICE TIME *.3. 13374E-31 3.52415E-"31 MEAN CRITIC'AL SERVICE TIME 3. 2439 7E-36 3.43521E-36 RELATIVE EFFECT Z 16.5222 83.4779 RELAT I VE EFFECT % 37.5785 62.4134 I Dependent Variables, Part 2, for Optimal $250,000 System Figure 6.4

-3 w0 MEATI TIME 1 TO C OY-LETE A P-RI v4IAY ACCESS '^-AM TI.'E TO CO.PLETE A SEC3JODARY ACCESS A4EA4 E EC;JTI TI 'E 3EFOR.E SECODAARY rAGE FAiJLT MEAM\ TT4E a3ETir E-j.RI4ARY ACCESSES TAP J.J= T4AJS=?* 6492432E-36 3.6? 7392 6E -3 1 TA.JE = 3..11921 16E.- 3. TAUC= -. 341 1 3 42E-6 - 6 Decision Variables, Part 3, for Optimal $250,000 System Figure 6. 5

The record size at level 2 has dropped from 1024 bits to 256 bits and the record size at level 3 has risen from 16384 to 32768. It is interesting to note that the change in record sizes has caused a shift in the optimal number of user programs. (Section 5, Chapter 5 shows that the optimal number of user programs is 13 when all else is fixed.) Comparing the dependent variables of this optimal system, shown in Figures 6.3, 6. 4, and 6. 5, with the "standard" case we see that the performance has improved only slightly. In fact the mean user program access rate has increased less than 1%. Thus the "standard" case is very near optimal. We will now see what happens when we increase the maximum expenditure, Cma. Here we will increase Cmax by $50,000 to $300,00 allowing a single additional storage unit in the system. The optimization reported 20,124 possible configurations of which 1362 were feasible. The optimization time was 62 sec. of CPU time. The new optimal system is shown in Figures 6. 6 through 6. 9. We see that an additional core unit was added to the system and the performance has increased considerably. The new performance, r, is 25% greater than that of the previous optimal system. We see also that the number of user programs has increased and the record size at level 2 has decreased again. 273

DECISION VARIABLES M41 i N I IVJ CU RRE;N T MAX I I4 J4 # OF PROGRAMS 2 15 25 * LEVEL 1 * # OF UJITS 1 1 4 RECORD SIZE 32 32.3 * LEVEL 2 * # OF.lIJITS 2 4 3 RECORD SIZE I 2 123 128 4396 * L EVtL 3 * OF 'JJ ITS I 1 4 RECIOR SIZE 47X96 32763 65536 Decision Variables for Optimal $300,000 System Figure 6. 6 274

MEAN CPU ACCESS RATE = 3.1637.33,E 36 *** ALLOCATIO D0ATA 15 PROGRA':S WITH EACH LEVEL TOTAL SPACE 1 3. 1 92I3.32EL 34,.2 3.2.303.3" E 7 3 3.1 013333E 13 USI JG 3. 16334,3E ALL)CAT I ') 3.31923330 E 34 3.13333331E 36 * 66 666662E 36 16 BITS i7 OF PRO3GRAM4 5.33'3'3 431 6* 3.29 43 6.9-39 CPiJ/PRI MARY EFF ICIE CY= 31 364% CP'J JTILI ZATI'IN. UJ SE R 2 6.344 % SYSTEM 3.4487, WAI T 73 5383 ~*** i.EA.4N T RA F IC ** -- VER ALL I T IE CPJ ACCESS RATE = 3. 1 68793"3E,36 LE VEiL % J SER ACCESS READ/ RITE RATE 1 7 6. 519 3 429 6883 3. 1 9 9 79 73E 3 7:2P 23.452 3. 45654 3.3 3 2 3294 E 36 3.313I3 ~33 1 3 851 3.51275 55E S 32 — OVE R 'ERIODS OF J S ER PROGRA EXECiJTIO -- CP!J ACCESS RATE =.3 136443'E ' 7 LEVEL 7 iJSE R ACrCESS READ/W.'RIT. E RATE ~1 76.5193429683 3. 4636725'3E ' 7 i2. 3 2.45'28: 45654.I 4717213,7 RECO RD SIZE.1 62657'791E 2 3. 13236734E 33 3.3 3767992E 15 RECORD SITE;3.62657776E 3 2.3. 12913759E i33 Decision Variables, Part 1, for Optimal $300,000 System Figure 6. 7 275

***:'AXI JMI?^J)SSISLE;U9J413ER OF RE~)'JESrs FO]R SERVICE:dJH E~ R UJ Jl G 1.5 JSER(S) LEVEL A A(X REJ'UESTS 1 3 2 33 3 33 *** ACCESS TIMES *** -SEC.O4nDARY ACCESS E NVIRO iMEIT — MEA AN. EA- r TOrAL LEVEL SERVICE RATE SERVICE TIME 12 3.33321E 36 '.1 1478E-35 3 3 51 2 75 E 32. 3.95'643E- 31,XT 3.2 3422E 033 3. 6., 3.? -3. 1 — P.R I MARY ACC.ESS E N. VI RO M4ENT — ME AN. ' MEAN. TOTAL LEVEL SERVICE RATE SERVICEI TI ME 1 3. 461.67E 37. 3.3 53 6E-3 6 2.3. 1-471 2E 3 7. 16'341E- I35 EA A:J',!JE' E LEN GTH 3. 43936 4. 9041 M.A. MEAi Qa 1 JE JUE LE:J GTH I. 46 6 72 2. 3 63 3 MJEA~4; CRITICAL;,i CR I T I C AL SERVICE TI '4E 3. 53363E-31 543E 33-. 3 ER I T I C AL AEA\I CRITICAL SERVICE TIME 3. 228 72E- 6 3 3 7583 E-3 6 RE LATI VE EFFECT % I *3 1 6.6748 33.3251 RiELAT I VE EF FECT. 37,3335 62.1632 Dependent Variables, Part 2, for Optimal $300,000 System Figue 6 8

MEANJ I'I ET T O C ' PLETE A PRIIMA.RY ACCESS *EAT rI' E T) CO31'LLETE A SECONDOARY ACCESS MEA:l EXEC!JF 'I TIME 3EFR:E SECOTDARY PAGE FAUJLT MEAN 'TI E BETWEEN PRIMdARY ACCESSES TAfJP= 3. 6345366E-3 6 TA'JS= 3. 639 7551E- 1 -.I -~3 TAUE = TAJ C = 3. 1 3333833E-.31,325E —36 Dependent Variables, Part 3, for Optimal $300,000 System Figure 6. 9

6.3 Changing the User Program Size In this section we will study how the behavior and characteristics of an optimal system change when the size of the user programs being run changes. As a simplification we will only optimize the number of user programs being run. To do this we simply set: max min N. = Ni = N. for all i, and max min qi = qi = qi for all i. The performance as a function of user program size is shown in Figure 6. 10. Here we see a variation in program size from 81920 bits to 491520 bits. The upper curve gives the performance d the system when an optimal number of user programs are run as a function of user program size. The lower curve shows how the system performance varies with program size when a fixed number of user programs are running (13),. This lower curve simply shows what happens to the "standard" case when the user program size is changed. In general both the optimal and the fixed configuration decrease in performance with increased program size. The optimal system performance always exceeds the fixed system except for a program size of 163840 bits where the fixed and optimal coincide. The optimal number of user programs is plotted against user program size in Figure 6. 11. The core allocation at level 2 in terms of the % of user program size is shown in Figure 6.12. 278

1,000, 000 im C.)~ <0 rvow (.L Q LJ:DUJ CI) V) =, LA-1 V) V) 800, 000 600, 000 400, 000 200, 000 0 81920 163840 245760 327680 409600 491! USER PROGRAM SIZE IN BITS Performance Versus User Program Size Figure 6.10 CO 0 Q_ C'L 0 ro CL. z 0 eL 0 - 20 0 15 - 0 0 0 10 - 0 0* 0 0* 5 0 I I I I I I 81920 163840 245760 327680 409600 491520 USER PROGRAM SIZE IN BITS Optimal Number of Programs Versus Program Size Figure 6.11 279

_ 100 80 z ~ O * ~ 1 ~60- ~ 0: 40 -| 20 0 _ I I I I 81920 163840 245760 327680 409600 491520 USER PROGRAM SIZE IN BITS Allocation Versus User Program Size Figure 6.12 v) 100 LLJ oU |~~ ~External Interrupt < 80 a80 LU 0 60 O3 40 I-) 40 Lii U- Level 3 Access Li > 20 "' O S~I I I I 0 ~ 81920 163840 245760 327680 409600 491520 USER PROGRAM SIZE IN BITS Relative Effect Versus User Program Size Figure 6.13 280

As one would expect the optimalnumber of user programs decreases as the user program size increases. Notice that the resulting allocation also decreases as user program size increases. This means that the total size of collection of M user programs tends to increase with increased user program size. This suggests that as programs get bigger we are willing to run them with lower allocation in order to reduce the effects of external or I0 interrupts. An interesting result of this experiment in optimization is shown in Figure 6. 13. Here we see the relative effect of the external interrupt and the drum at level 3 on the secondary delay. Notice that for an optimal number of user programs these values remain relatively constant. This suggests that measures of the relative delay in a system might be useful parameters for use in a scheduling algorithm. 6.4 Changing the Number of Core Units In this section we consider an optimization experiment similar to the optimization carried out in the previous section. Here we will study the characteristics of the optimal system as we increase the number of core units. We will again use the "standard" case with the exception of the variation in number of units at level 2 and the number of user programs being run. We will vary the number of core units in the system in each case optimizing the number of user programs running. The optimal system performance versus the number of core units is shown in Figure 6. 14. The performance increases with an 281

2, 000,000 v 1, 50, 000 D V 1, 000, 000 m,' GL~I I,,,00,000 O 2 3 4 5 6 7 8 NUMBER OF CORE UNITS Optimal Performance Versus Number of Core Units Figure 6.14 100 80 s 80 _^^ Wait; 60 40 User 0 0D o 20 System 0 L * I t I 2 3 4 5 6 7 8 NUMBER OF CORE UNITS CPU Utilization Versus Number of Core Units Figure 6.15 282

C.D CO) 0 LLJ 0 -L _J 0 25 0 20 15 10 5 0 0 0 I I I I I I I 2 3 NUMBER 4 5 OF CORE 6 UNITS 7 8 Optimal Number of Programs Versus Number Figure 6.16 of Core Units CMIQ -J LAI 0 i 0 -I < o 0 azsg 100 80 60 0 0 0 40 - 20 - 0 I I I I I I I 2 3 4 NUMBER OF 5 CORE 6 UNITS 7 8 Allocation Versus Number of Figure 6.17 Core Units 283

100 - <{I >- 80 < External Interrupt I'Z o 60 LU L 40,. LU^~ ^ ~~Level 3 Access '> 20 2 3 4 5 6 NUMBER OF CORE UNITS Relative Effect Versus Number of Core Units Figure 6.18 284

increasing number of core units and in a surprisingly linear manner. Figure 6.15 shows the CPU utilization figures and we see that we never approach CPU saturation, Figures 6.16 and 6.17 show the optimal number of programs and the corresponding allocation at level 2. Figure 6. 18 shows the relative effect of the external or 10 interrupts and the drum delayo Here we can again observe relatively constant values over a wide variation in number of core unitso The optimizations in this and the previous section are simple in that there is only one effective decision variable, M. In all cases M was allowed to assume values from 2 to 30 inclusive. The CPU time required to perform an individual optimization is approximately 2 seconds. In both this section and the previous section, 15 distinct optimizations were carried out for a total of 30 optimal solutions. The total CPU time required to find all of these optimal solutions was less than 1 minute. The point to be made is that we can not only analyze and optimize individual computing systems, but we can also study the characteristics of sets of optimal systems. 285

Chapter 7 Conclusions The work described here has been directed toward the analysis, optimization and better understanding of computer systems. The core of the effort has been a mathematical model. The mathematical model is developed in Chapters2, 3 and 4. It involves user program behavior, storage hardware behavior, CPU behavior, and system hardware and system software architecture. After the model was developed and programmed a period of experimentation began in which a variety of system configurations were analyzed and optimized. Some impressions gained concerning both the model itself and the systems being studied are of interest. Many of the results obtained from the model were counterintuitive. This was true for both analysis and optimization. In every case additional experimentation provided a better understanding of the system. The initially counterintuitive results were found to be consistent with an improved understanding of the system. The capability to explore the system, by modifying parameters and observing changes in performance, was extremely useful in identifying the important performance controlling characteristics of the system. This capability to explore a system is the result of 3 factors: Early in the experimentation several cases of true inconsistency Early in the experimentation several cases of true inconsistency were found in the model. These were traced to either program error or an error in the model itself. In each case the error was corrected. 286

1. Low cost of solution 2. Model flexibility 3. An interactive implementation of the model. The CPU time required for analysis and/or optimization was small. In the case of analysis and the simpler optimizations, the cost of solving for the result was less than the cost of printing the result. The interactive nature of the implementing program is such that the user spends much more time deciding what changes to make than he does actually making the changes. The approach taken in the design of the model deserves some discussion. The model was developed specifically for use in the form of a computer program. This has affected a number of important model design decisions. The model is modular. The most important aspect of this modularity is the ease with which diverse mathematical methods can be applied to different portions of the problem. In choosing a method for modeling storage hardware there was no need to use the techniques employed to model the user program behavior. In each case the method used was developed for the specific application with little regard for methods used elsewhere. This modularity of method, which would lead to a uselessly cumbersome model outside the context of computer implementation, was instrumental in providing the realism and speed of solution demonstrated in Chapters 5 and 6. 287

If there is one characteristic of the mathematical model to be identified as contributing most to its worth as a tool for modeling computer systems,it would have to be this modularity of method. 288

Appendix A Solution for Integrals of Equation 2. 54 Here we will evaluate the sum of integrals s-q s foc H(A4)f^(A) A + Js q H2(A)f (A) A /q[Q/q] + Js H3(A)fA(A)dA (A- 1) where H(A), H2(A), H3(A) and fA(A) are defined in Equations 2.44, 2. 52, 2.47 and 2. 28 of Chapter 2. There are three distinct integrals in the above expression. We will treat each separately beginning with s-q Jo t s-q Hl(A)fA(A) dA= A1 o J6 AdA CIA (A +q)(2(q[Q/ql - s) + A)(- (p- 2) e q[Q/q] where (A-2) 2 (Q/rQ/ql) A = - -1 1 q'e [tan e(l - p) + tan ep] We will define a = q a2 = 2(q[Q/ql - s) (A-3) (A-4) 1 2 a3= 2 + p e (A-5) 289

2p a4 = _2 2rQ/ql a-=i 1 a q = Iq rq/ql2 (A-6) (A-7) then we may write S-q I s-q Hl(A)f (A) dA = A1 A dA (al+ A) (a2+A) (a3 + a4A + a5A) (A-8) Expanding using partial fraction A 2A) (a (aI+A) (a2+A) (a3 + a4A + a5A ) K1 K2 2. - K3A + K4 (A-9) al +A a3 + aA + a 5A multiplying by the denominator A = Kl(a2+ A) (a3+ a4A + a5A2) + K2(al+ A) (a3+ a4A + (K3A + K4) (al+ A) (a2 ) Letting A = -aI we see that + a52) (A-10) -a1 K (A-11) (a2- a1)(a3- a4 +a a1 ) and letting A = -a2 290

-a2 K2= (A-12) (a- a2) (a3- a4 a2+ a5 a2 ) We will solve for K3 and K4 by equating powers of A = K1(a2 a3 + (a3+ a2 a4)A + (a4+ a2 a5)A' + K2(a1 a3+(a3 +1 a4)A + (a4+ a1 a)A + K3(a1 a2A + (a1+ a2)A2 3 + K4(a1 a2 + (al+ a2)A + ) Summing the constants 2 a A 3) a5) + a5A (A- 13) 0 = K1 a2 a3 + K2 a1 a3 + K4 a a2 a3 K = -K..a a a3 -K2 a 2 a (A-14) where K1 and K2 are known. Summing the coefficients of A3 0 = K1 a5 + K2 a5 + K3 K3 = -(K1+ K2) a5 (A-15) Thus returning to our original integral we may break it into four separate integrals s-q So HI(A) f(A)dA = A s-q +K3 fo a, K1 s-q s-q dA a++ fo2 a2+ A AdA 2+A + a K4 i+ a4A + a5A s-q so dA (A-16) 291

Working with each integral separately s-q dA K a1 + A s-q = Kl[2n (al+ A)] 0 al+ s - q =K ln( ---- ) 1a (A-17) and s-q K2 2o dA a +A.2 a2+ s- q K2 n( -a-) a2 (A- 18) and s-q 3 So AdA a3+ a4A + 1 a A2=K3[ 2 a. 5 2s-q in (a3+ a4A + a5A )] o a4 2 a5 s-q K3 0 K3 2 a5 2 a5 dA a3+ a4A + a5A a3+ a4(s-q) + a5(s-q) 2 n ( 3.5a3 --— ) a3 a4 2 a5 3 s-q o. dA (A-19) a3+ aA + a5A Substituting what we have done so far back into Equation A-16. s-q HI(A)fA(A) d = al+ s- q a2+ s- q A1[1 n( — ) + K2 n(- a- ) 1 2a + K3 2 - 3 2 a5 a3+ in( — a4(s-q) + a5(s-q) 2 a3 a4 + (K4- K3 2a ) s-q Jo dA I a3+ a4A + a5A2 292 (A-20)

Examining the remaining integral we see that s-q s-q ^ A 2 o o dA (A-21) A 2 a+a a4 +a a5 3 4 — +(p- ) e rQ/qlq which we have previously solved for different limits in Chapter 2. Using the results of Equation 2. 27 in Chapter 2. s-q dA s-q a s- - dA- 2 = q[Q/qle[tan-l( A - ep) ] a3+ a4A + a54 q[Q/ql o = q[Q/qle[tan 1 (e-) _ ep)+ tan (ep)] qrQ/ql (A-22) Substituting into Equation 2. 75, s-q + s q a2 + s - q fo H(A)fA(A)dA = Al[K, tn( -) + K2 n( ) 2 i a3+ a4 (s-q) + a5 (s-q) 3 2 a5 1(a + 4 - 2Q/qle[tan 1 e(s-q) -ep + (K4 - K3 2a ) q[Q/q]e[tan-l(e —L 5 q[Q/q] +tan l(ep)]] (A-23) Thus completing the most complex of the these integrals. The second integral takes the form s H fs-q H2(A) fA(A) dA = A2s-q -q 2. A 2 f-q K 5A + K ------ - dA e.q.Q.2 d (_ + (Pp ) ) e q[Q/ql (A-24) 293

where Q A =_ - Q a -1 — 2 2 2 Q/e[tan1 e(- tanep) q rQ/I e[tan- e(l - p) + tan- (ep) ] (A-25) 2aqfQ/qJ(s - q) K= 5 q'(s + q - s/)) q (s2/q2 + s/q)) 2c[Q/q] (A-26) K =(q-5)s _2aoqrQ/ql(s-q) K6 q 22 + 6 'q(s + q - - -(s /q + s/q)) q'(2(q[Q/q]s) + s - q) 2arQ/ql (A- 27) Using the previously defined terms a3, a4 and a5 we can write s-q H2A)f^) d = fA2[ 5 s-q AA,AdAQ a3+ a4A + asA,dA + K s-q a3+a2 ] (A-28) a3+ a4A + a 5 which is identical in form to the last two integrals of Equation A-16. Using those results we can write s fs-q H2(A)fA(A) dA - 1 2 A2[K5 2 a n (a3+ a4A + a5A ) 25 s-q a4 s + (K6- K5 2 ) q[Q/qle[tan- e ep)] ] 6 "52 a q[Q/q]l s-q 2 AF [K 1 a3+ a s + a5 s 2[ 2 a 25 ~ 5 a3+ a(s-q) + a(sq) a(s-q) + (K6 - K5 2 )q[Q/qle[tan-( es -ep)-tan-l(e(spq)ep)] 5 q[Q/q ] qrQ/ql (A-29) 294

completing the second integral. Continuing we will consider the final integral f HqH3(A)fA(A) dA= A3 J _ (A +(q- q- (s2/q2+ s/q)))( - +(P- ) ) 2arQ/q1 e [Q/qlq (A-30) where A = Q/ 3 q'Q/ql 2e[tan-le(1-p + tan- ep] (A-31) defining a6 = q - q (2/q2 + s/q) (A-32) 2arQ/ql and using the previously defined a3, a4 and a5 we may write q[/l qQ/ql AdA (A-33) Js H3(A)f (A) dA3 S (A-33) H3(A)fA(A)dA 3 (A + a6) (a3+ a4A + a5A) Expanding using partial factions a K7 K A + K A_7 8 (A + a6) (a3+ a4A + a5A ) (A +a ---- (A-34) (A + a6) (a3+ a4A + agA') (A + a6) a3 + a4A + asA Multiplying by the denominator A = K7(a3+ a4A + aA2) + (K8A + Kg) (A + a6) (A-35) Letting A = -a6 and solving for K7 295

-a K = '........ 6 K7 = 6 ---- 2 (A-36) a3- a a6 + a a6 Rewriting Equation 2.95, A = K7(a3+ a4A + a5 ) +K8(0 + a6 +A2) + K9(a6 + + 0) Summing the constant terms 0 = K7 a3 + K9 a6 or a3 K9 =-K7 a6 (A-37) Summing the A terms 0 = K7 a4 + K a6 + Kg - 1 or 1 - [K7 a4 +Kg] K8=- a6" a3 1 - [K7 a4 - K7 - ] 6 a6 1 +K7 (a — a4) ~~6= -- 6 -- (A-S8) a6 296

In its expanded form we may write qQ/l1 qj Q/ql CQA Q/q_ _ ACIA fs H3(A))f(A)h d = A3[K7 s a + /K 8 ds+ a2 6 aa3+ a4 + a 5A +K q[Q/ql dA (A-39) a3+ a4 + a5A These three integrals are identical to the last three of Equation A-16 except for constants and integral limits. Using these previous results we may write qrQ/ql q[Q/ql fs H3(A)f(A) dA = A3[K7 [en(a6 + A)] s 1 2 q[Q/q] + K8[ a rn(a3+ a4A + a5A2) ] 5 s a 14e q[Q/q] +(Kg-K82 q[Q/qle[tan-l( e A - ep)]Q/ 5 q[Q/q] s a6 + q[Q/ql = A3[K7 n( a6 + s ) 6 +s I a3+ a4 qrQ/ql + a5q2Q/q]2 K82a n 234- 5 a3+ a4 s + a5 s _ -1-1 es a4 + (Kg- K8 2 a) q[Q/qle[tan le(1-p) -tan ( — ep) ] (K9-K' 5 qK[Q/q]-l (A-40) 297

Thus completing the last integral. A summary of the results and relevant constants can be found in Equations 2. 56 through 2. 76 of Chapter 2. 298

Appendix B Request Distribution Our concern here will be to consider how the requests for service distribute themselves among the various devices at a given level. In the case of disks we will want to know the probability that m disk arms are busy when there are n disk arms and r requests in the system. In the case of core boxes, drum sectors and data cells we will ask the same basic question. We will assume that an arriving request will require the use of a specific device such as a disk arm or core box and that the probability of any specific device being chosen is simply - where n is the number of devices in the system. Consider the diagram of Figure Bi. Here we have a queueing model with n queues and servers in parallel where the servers are independent and have the same mean service time. When service completes at any one of the n servers the request immediately reenters one of the n queue and server combinations. Thus we see that there will always be a fixed number of requests in the system. This corresponds to a system of n devices where it is assumed that we have r requests in the system and each service completion is accompanied by an arrival. We will want to know the probability of a given distribution of requests in queues and servers after the system has reached a steady 299

1 n Circulating Queue Figure B1 300

state condition. We will describe the state of the system with an n-tuple r1, r2,.. rn (B-1) where ri is the number of requests in the i-th queue and server combination. We will define r = total number of requests (B-2) in the system n r. i= The probability of a transition from any given state r1, r2,..., rn to any other state r'1, r'2,..., r', (where other state implies that 1' 2'"" nn there exists an i such that ri # r'i) is either 0 or -. In order for n a transition to be possible, transition probability / 0, r1, r2,..., r and r', r'2,... r' must differ in 2 positions. 1' 2 n r' = r. - 1 (B-3) J J rk= rk +1 k j (B-4) r'i = ri j i k (B-5) If the transition is possible the probability of the service completion occurring at server j is -and the probability of this circulating requect for service entering server or queue k is -. Since each of these selections is n independent the joint probability is simply --. In terms of the state n transition matrix we are simply stating that the off diagonal forms are either 0 or — 1 n 301

It should be clear that if a transition from state rl, r2,..., rn to r1' r'2 * * *, r' is possible then transition fromr r ', r ' r 1 2 n 1' 2''' n to rl, r2,..., r is possible. Thus a non-zero off diagonal term in the transition matrix implies a symmetrical non-zero term, And since all non-zero off diagonal terms are- the transition r trix n must be symmetric and therefore doubly stochastic. It can be shown (p. 141 of [42] or p. 255 of [43]) that the stationary probabilities resulting from this doubly stochastic state transition are given by 1 T1 = T2 =',, a = a (B-6) where a is the number of states. The number of states is the number of distinguishable distributions of r balls in n urns or the number of different solutions to Eq. (B-2). It can be shown (pp. 36-37 of [37]) that a= (n+r-) (B-7) Thus the probability of being in any given state rl, r2,..., rn may be written 302

=I (n+r-1)-1 (B-8) This may be recognized as the classical Bose-Einstins statistics for which many results are available. (See Chapter 2 of [37]) Specific results which may be of use here are] The number of distinguishable distributions A r, ( ln+r-1 (n+r-i (B-9) Ar, n ( r ) ( n-1 )(B9) The number of distinguishable distributions in which no server remains empty A rn (n-) (B-10) The probability that exactly m servers remain empty n r-I (m )(n-m-1) p m(r, n) m - (B-n1) m (n+r-)1^ (B-li) r and lastly the probability that there are exactly m non-empty servers. n r-1 n-m )(m-) pr(r, n) n+r- - (B-12) r 303

Consider the queueing diagram shown in Figure B2. The 1 arrivals join one of the n queues for service with a probability of The arrival rate is X and the service rate at each of the n servers is /i. The arrivals and service will be taken as Poisson. We will limit the total number of requests in the n servers and n queues to a total of B requests. Arrivals which would cause the total to exceed B are simply lost. This model differs from the previous model in that exponential service is required but here we will not require that each service completion be accompanied by a corresponding arrival. We would now like to show again that the steady state probability of being in any state rl, r2,..., rn is equal to the steady state probabJity of being in any state r' 1, r2,., r'n whenever n n r. = ri. Using the transitions in and out of the state i=l i=1 rl, r2,.., rn we will write an equation for the steady state proban bility of being in iis state given the steady state probability of being in the states which have direct transitions to or from the states r1 r2. rn. We will see that for all states this equation is satisfied by the assumed steady state probability X r 'n I Prob(r r2. r) = X (B-13) I+(Ti-fn +... + 1+ ( + where( ( where 304

ni n t I-, 1 1 n | n ~~~~~~~~~I It~~II Open Queueing Model Figure 2B 305

n r = L r. i=l We will write the probability of being in a state with r requests n ( r. = r) at time t as Pr(t) and at time t + At as Pr(t + At). j=l1 We will first develop an equation for all states in which r < B. We must consider three ways of arriving at state r1, r2,. o., r at time t + At. They are: 1. Being in a state with r+1 requests in the system and having a service completion. 2. Being in a state with r-1 requests and having an arrival. 3. Being in the state r1, r2,.., rn and having neither an arrival or service completion. Beginning with the first of these possibilities we see that there are n states which have r+1 requests from which a service completion can place us in the state r1, r2,..., rn. They are: n ri1, r2+1, *., rn rl, r2,..., rn+1 306

Since the service rate at each server is /i we may write the incomplete equation Pr(t + At) = n iPr+ (t)At + + where we have indicated 2 remaining terms. The second way to arrive at the state r1, r2,..., rn is to be in one of the states: rl-1, r2,..., rn r1, r2-1,.0., rn r1, r2,.., rn-_ which does not have a negative term. We will assume for the moment the state r1, r2,..., rn will produce K such states with r-1 requests. Since the arrival rate is X and there are K states each with a state probability of P (t) we may add the term K P (t) to our equaT (t) n2 r ' tion giving us Pr(t + At) = n IPr+l(t) At+ KXPr_ 1(t) At + The final term in the equation is simply the probability of being in the state r1, r2,..., rn at time t and renaming these during the period ht or [1 - (X + KI)Axt]Pr(t). Here the probability of not leaving states r1, r2,..., rn is expressed as one minus the probability of leaving. The complete equation is Pr(t + At) = n Pr+I(t)At+KPr(t)At+[l- (X + KL)At]Pr(t) rt + t) =n r(B-14) (B-14) 307

Rewriting and equation to 0 for the steady state solution Pr(t + At) - Pr(t) At X = nl Pr+(t) + K Prl(t) -(X + KP (t) = (B-15) Solving for Pr X n P Pr + K P1 r-+l n r1 r<B (B-16) X + K/ In the case of r = B we may write PB(t+ At) = K PB (t)At[l - K luAt]PB(t) (B-17) which becomes K P n B-1.B ~ Kpu x n-i B-1 (B-18) From Equation B-13 we see that Pr1 = - Pr r-1 x Pr (B-19) and pr+ n X p r+1 = n- P r (B-20) substituting in Equation B-16 for r < B we have p _ X+Kl3 p r X + K/gI r 308 = p r (B-21)

and Equation for r = B k nx p PB = -n P B B nA L X B =PB (B-22) Thus we see that Equation B-13 is the steady state solution to the model of Figure B2 and that the probability of being in any state r1, r2,.'. rn is equal to the probability of being in state r'1, r'2,... n n r' given L r. = r'i. Thus again showing that if it is given i=1 1=1 that there are r requests in the system the probability of being in any given state r, r where r = r is (r) i=l 309

A Note on Computation It will be necessary to compute numerous values of P (r, n) for values of r and m. In order to simplify calculation we may express Pm(r, n) as: n! (r-l)Ir! (n-l) I Pm(r,n) (n+r-1)! (n-m)! m! (m-1) (rm) (B-23) By simply substituting m+1 for m we may write P (r n) = n! (r-1)!r! (n-l)! Pm+1 (, n) (n+r-1)!(n-m)! m!(m-1)! (r-m)! x (n-m)(r-m) X (m+1~)m - p r, n) (n-m)(r-m) (B-24) Pm(r' ) (m+l)m (B-24) Similarly we may substitute r+1 for r obtaining P (r+1, n) =P(r, n) r(r+) (B-25) Knowing that P1(l,n) = 1 (B-26) we may compute all the necessary values of P (r, n) rather simply. m 310

Appendix C Computational Difficulties in Computing 3' The use of Equation 4. 17 directly in computation for 0' results in possible exponent overflow and underflow conditions. The basic problem lies in the term of Equations 4.17, 4.18, and 4. 20 of the form Ai Since i can be as high as several bunched these terms tend to become very small or very large. These problems can be overcome by rearranging terms and special care in taking the summations. Repeating 4.17, 4; 18 and 4.20 B B (P(X) + - ) [C(P(X) + ) - xP(x)] AlU 2... jAB AI p-... jB ' = X + l'' ' —B 1'B P(X) [P(X) - (B-l) + XP'(X) x /1/~2"'.B B l2"' B (C- ) + 2 B-1 P(X) = 1 + A + +...+ -- ---- (C-2) /11 A1l2 E1j *2' ' 'B- 1 _3 kB-1 P'(X) = A~ +2 +2 + 3. +... +(B-1)... -- Ai. AIApl/2 l~A123 12..' ^B,(C-3) (C-3) 311

We will now rewrite Equation (C-1) by dividing both numerator and denominator by P2(X). B 1(i + 1c) L 1 +B.2. [X' = A +i.1B} (B I) { P(,) Sl 2 P()) '\ lt2...J.] P(X) P(X) (C We will now consider the behavior of the terms in brackets. Beginning with -4) XP'(X) P(X) - + 2 +3 +...+ (B-1) A A 1 /~1/2 +1"23 1+ __2'". B-1 " Ai, 2 3 i 3 AB-1 1+ I 1. +- +. +.. + A1 1/~2 I 1/2l2A3 11A2' ' AB- 1 (C-5) Mluy2. ~ /XB Multiplying numerator and denominator by: --- B X. XP'(x) _ P(X).2' '. 'B J3... - B --- + 2 2 -2 +. + (B-l) - X X'/*1'**. B 2 '*' *B 3 ' ' B "B B + B- 1 + B-2 + ' X '" (C-6) 312

We will sum the terms of the numerator and denominator from left to right. At each step of the summation we will generate and maintain gji+l' B' B a term of the form B+-i. This term will be generated by X Bi+l multiplying the previous term by the appropriate. Note that since the Oi's are nonincreasing with decreasing index i. The terms Pi+l will decrease as the sum proceeds. Thus if the complete ti+m '" PB A'i+I"..B term, B — in the denominator or i B- i in the numerator begins to grow smaller with decreasing i, it will continue to grow smaller with decreasing i. Thus if the complete term becomes much much less than current sum further terms may be ignored. XP?(X) x The value of P(X) will vary from when X is very small to P(X) ~1 (B-l) when B is large. The summation proposed here will be SIB X successful for values of which are near 1 or large and will fail Al when is small and B is large. This is in effect because we are taxing a number larger than ( l ) and raising it to the power B which can be as large as 300. The important point however is that XP'(k) X X when this occurs. P(X) ~ Turning to the second term in brackets of Equation C-4 we may write: 313

XB -B,1l-,, tZ B- p(X) ~P P ) 1 s1ai 2 f1' P w B- 1 1'.' /B 2' *' * B /3' ' -*B AB B B-1 B-2 ' + (C-7) We see that the denominator here is identical to the previous case and numerator is a constant. Here if we can complete the summation, either by summing all the terms or eliminating them because of their small size, and have a valid result the summations for;v should do likewise (note summation for XP'(X) will be the first to fail). If on the other hand - is small and the summation grows too rapidly A1 it is clear that the term B I Xis very near 0 1** XB as is / Xp'() X Examining Equation C-4 it is clear that these terms may be considered 0 everywhere they occur and Equation C-4 becomes simply 314

'= x + C1X (C-8) or ' = C (C-9) Thus, if we are unable to perform the necessary summations do to excessively large terms, the result being sought is given by Equation C-9. 315

BIBLIOGRAPHY [1] Abd-Alla, A. M., Analysis of the Storage Organization for a Multiprogrammed Computer System, Dept. of Electrical Engr., University of Maryland, College Park, Maryland, (Sept. 1969). [2] Anacker, W. and C. P Wong, "Performance Evaluation of Computing Systems With Memory Hierarchies", IEEE Trans. on Elec. Comp. 16, 6 (Dec. 1967), pp. 765-773. [3] Arden, B.W., "Time Sharing Systems: a review", Michigan Summer Conference on Computer and Program Organization, 1967. [4] Arden, B.W., et. al., "Program and Addressing Structure in a Time-Sharing Environment", Journal of the ACM 13, 1, (Jan. 1966), pp. 1 -16. [5] Belady, L. A., "A Study of Replacement Algorithms for a Virtual-Storage Computer", IBM Systems Journal 5, 2, 1966, pp. 78-101. [6] Belady, L.A., and C.J. Kuehner, "Dynamic Space-Sharing in Computer Systems", Communications of the ACM 12, 5, (May 1969), pp. 282-288. [7] Belady, L.A., et. al., "An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine", Com munications of the ACM 12, 6, (June 1969). [8] Bryan, G.E., "Joss: 20,000Hours at a Console - a Statistical Summary", AFIP Conference Proceedings 31, (Fall 1967). [9] Buchholz, W., "A Selected Bibliography on Computer System Performance Evaluation", Computer Group News, (March 1969), pp. 21-22. [10] Burnside, W. So and A.W. Panton, The Theory of Equations 1, Dover Press, New York, 1960. [11] Calingaert, P., "System Performance Evaluation: Survey and Appraisal", Communications of the ACM 10, 1, 1967, pp. 12-18. 316

[12] Chandy, K.M.,and C.V. Ramamoorthy, "Optimization of Information Storage Systems", Information and Control 13, 6, (Dec. 1968). [13] Coffman, E.G., "Analysis of a Drum Input/Output Queue Under Scheduled Operation in a Paged Computer System", Journal of the Assoc. of Computing Machinery 16,1, (Jan. 1969) pp. 73-90. [14] Coffman, E.G. and L.C. Variam, "Further Experimental Data on the Behavior of Programs in a Paging Environment", Communications of the ACM 11, 7, (July 1968), pp. 471-474. [15] Conti, C.J., "Concepts for Buffer Storage", Computer Group News 12, 8, (March 1969), pp. 9-13. [16] Conti, C.J., et. al., "Structural Aspects of the System 360 Model 85, I General Organization", IBM Systems Journal 7, 1, 1968, pp. 2-14. [17] Cox, D.R. and Walter L. Smith, Queues, John Wiley & Sons, Inc., New York, 1961. [18] Denning, P.J., "Thrashing and Its Cause and Prevention", Proc. AFIPS FJCC 33, 1968, pp. 915-922. [19] Denning, PJ., "Virtual Memory", Computing Surveys 2, 3, (Sept. 1970), pp. 153-189. [20] Denning, P.J., "Effects of Scheduling on File Memory Operations", AFIPS Conference Proceedings 31 (Spring 1967). [21] Denning, P.J., "The Working Set Model for Program Behavior", Communications of the ACM 11, 5, (May 1968), pp. 323-333. [22] Feller, William, An Introduction to Probability Theory and Its Applications I, John Wiley & Sons, Inc., New York, 1950. [23] Fenichel, R.R. and A.J. Grossman, "An Analytic Model of Multiprogrammed Computing", Proc. AFIPS SJCC 34, 1969, 1. 717. [24] Fife, D.W. and J.L. Smith, "Transmission Capacity of Disk Storage Systems with Concurrent Arm Positioning", IEEE Tran on Elec. Comp. 14, 4, (Aug. 1965), pp. 575-582. 317

[25] Fisher, T.O. andC.D. Shepard, "Time Sharing On aComputer With a Small Memory", Communications of the ACM 10, 2, (Feb. 1967), pp. 77-81. [26] Freibergs, I.F., "The Dynamic Behavior of Programs", Proc. AFIPS FJCC 33, 1968, pp. 1163-1138. [27] Hellerman, H,, "On the Average Speed of a Multiple Module Storage System", IEEE Tran. on Elec. Comp. 15, 4, (Aug. 1966), pp. 534-550. [28] Hobbs, L.C., "Present and Future State of the Art in Computer Memories", IEEE Tran. on Elec. Comp. 15, 4, (Aug. 1966), pp. 534-550. [29] International Business Machines Corporation, "IBM System/360 Fortran IV Language", IBM System Reference Library, file no. S360 25, Form C28-6515-4, IBM, White Plains, New York. [30] International Business Machines Corporation, "Functional Characteristics of System/360 Model 67", Form A27-2719, IBM, White Plains, N.Y. [31] International Business Machines, "System/360 Component Descriptions DASD for 2841", Form A26-5988, IBM, White Plains, N.Y. [32] International Business Machines Corporation, "Analysis of Some Queueing Models in Real-Time Systems", IBM Data Processing Techniques, Form F20-0007-1, IBM, White Plains, New York. [33] Jewell, William S., A Simple Proof of: L = XW, University of California, Berkeley, Calif., 1966. [34] Kuck, D.J. and D.H. Lawrie, The Use and Performance of Memory Hierarchies: A Survey, University of Illinois, Urbana, Illinois, (Dec. 1969). [35] Lee, F.F., "Study of 'Look-Aside' Memory", iiEE C-18, 11, (Nov. 1969), pp. 1062-1064. [36] Lehman, M.M. and J.L. Rosenfeld, "Performance of a Simulated Multiprogramming System", Proc. AFIPS FJCC 33, 1968, pp. 1431-1442. 318

[37] Liptag, J.S., "Structural Aspects of the System/360 Model 85, II The Cache", IBM Systems Journal 7, 1, 1968, pp. 15-21. [38] Martin, James, Design of Real-Time Computer Systems, Prentice-Hall, Englewood Cliffs, N.J., 1967, [39] University of Michigan Computing Center, The MTS Manual 2 Volumes, (Dec. 1967). [40] Neilson, N.R., "The Simulation of Time-Sharing Systems", Communications of the ACM 10, 7, 1967, pp. 397-412. [41] Opperheimer, G. and N. Weizer, "Resource Management for a Medium Scale Time Sharing Operating System", Communications of the ACM 11, 5, (May 1968), p. 313. [42] Parzen, Emanuel, Modern Probability Theory and Its Applications, John Wiley e Sons, New York, 1960. [43] Parzen, Emanuel, Stochastic Processes, Holden-Day, San Francisco, 1952. [44] Pinkerton, Tad B., "Performance Monitoring in a Time-Sharing System", Communications of the ACM 12, 11, (Nov. 1969), pp. 608-610. [45] Pinkerton, T., Program Behavior and Control in Virtual Storage Computer Systems, University of Mid igan, CONCOMP Report 4 (April 1968). [4g Pirtle, Mel, "Intercommunication of Processors and Memory", Proc. AFIPS FJCC 31, 1967. [47] Ramamoorthy, C.V. and K.M. Chandy, "Optimization of Memory Hierarchies in Multiprogrammed Systems", Journal of the Assoc. for Computing Machinery 17, 3, (July 1970), pp. 426-445. [48] Randell, B. and C.J. Kuehmer, "Dynamic Storage Allocation Systems", Communications of the ACM 11, 5, (May 1968). 319

[49] Randel, B., "A Note on Storage Fragmentation and Program Segmentation", Communications of the ACM 12, 7, (July 1969), pp. 365-370. [50] Rehmann, S.L. and S.G. Gangwere Jr., "A Simulation Study of Resource Management in a Time-Sharing System", Proc. AFIPS FJCC 33, 1968, pp. 1411-1430. [51] Saltzer, J.H. and J.W. Gintell, "The Instrumentation of Multics", Communications of the ACM 13, 8, (Aug. 1970), pp. 495-500. [5 2 Shemer, J.E. andG.A. Shippey, "Statistical Analysis of Paged and Segmented Computer Systems", IEEE Tran. on Elec. Comp. 15, 6, (Dec. 1966), pp. 855-863. [53] Sisson, S. S. and M. Flynn, "Addressing Patterns and Memory Handling Algorithms", Proc. AFIPS FJCC 33, 2, 1968, pp. 957-967. [54] Smith, J.L., "Multiprogramming Under a Page on Demand Strategy", Communications of the ACM 10, 10 (Oct. 1967), pp. 636-646. [55] Varian, L.C. and E.G. Coffman, "An Empirical Study of the Behavior of Programs in a Paging Environment", Communications of the ACM 11, 7, (July 1968), pp. 471-474. [56] Wallace V.L. and D.L. Mason, "Degree of Multiprogramming in Page on Demand Systems", Communications of the ACM 12, 6, (June 1969), p. 305. [57] Wallace, V.L. and R.S. Rosenberg, RQA-1 The Recursive Queue Analyzer, Systems Engineering Lab, University of Michigan, Ann Arbor, Mich., (Feb. 1966). [58] Weizer, N. and G. Oppenheimer, "Virtual Memory Management in a Paging Environment", Proc. AFIPS FJCC 34, 1969, p. 249. [59] Wilkes, M.V., "Slave Memories and Dynamic Storage Allocation", IEEE Tran. on Elec. Comp. 14, 2, (April 1965), pp. 270-271. [60] Wilkes, M.V., "A Model for Core Allocation in a Time-Sharing System", Proc. AFIPS SJCC 34, 1969, p. 265. 320

UNCLASSIFIED I Security Classification DOCUMENT CONTROL DATA- R & D (Security classification of title, body of abstract and indexing annotation must be entered when the overall report is classified) i. ORIGINATING ACTIVITY (Corporate author) I2a. REPORT SECURITY CLASSIFICATION Dept of Electrical Engineering UNCLASSIFIED Systems Engineering Laboratory 2b. GROUP University of Michigan 3. REPORT TITLE ANALYSIS AND OPTIMIZATION OF MULTIPROGRAMMED COMPUTER SYSTEMS USING STORAGE HIERARCHIES 4. DESCRIPTIVE NOTES (Type of report and inclusive dates) Interim report 5. AU THOR(S) (First name, middle initial, last name) Ashby M. Woolf 6. REPORT DATE 7a. TOTAL NO. OF PAGES 7b. NO. OF REFS August 1971 320 60 88. CONTRACT OR GRANT NO. 9a. ORIGINATOR'S REPORT NUMBER(S) F30602-69-C-0214 SEL Tech. Report No. 53 b. Job Order No. 55010000 c. 9b. OTHER REPORT NO(S) (Any other numbers that may be assigned this reportJ d. RADC-TR-71-165 10. DISTRIBUTION STATEMENT Approved for public release; distribution unlimited. 11. SUPPLEMENTARY NOTES 12. SPONSORING MILITARY ACTIVITY RADC Project Engineer Rocco F. Iuorno Rome Air Development Center (ISIS) AC 315/330-7011 Griffiss Air Force Base, New York 13440 13. ABSTRACT The research described in this report centers around the development and application of a general and comprehensive mathematical model of computer systems which use storage hierarchies consisting of 2, 3 or more levels and in which the storage management is carried out automatically (i.e. transparent to the user.) This model has been implemented in the form of a highly interactive computer program which provides the user with an animated view of the system performance as model parameters are varied. There are approximately 50 independent variables in the model. These variables describe the system architecture, data paths and routing, storage device characteristics, CPU performance, and user program behavior. _ II D D FORM 1 47 DDINOVS 6547 UNCLASSIFIED Security Classification

UNCLASSIFIED Security Classification I 14. LINK A LINK B LINK C KEY WORDS W ROLE I WT ROLE I WT ROLE R WT MULTIPROGRAMMED SYSTEMS STORAGE HIERARCHIES MATHEMATICAL MODELING _1 1I - UNCLASSIFIED Security Classification SAC —Griffiss AFB NY 27 Sep 71-74