Operating Systems Laboratory
Operating Systems Laboratory COP 4610L
University of Central Florida
Popular in Course
Popular in Computer Programming
This 12 page Class Notes was uploaded by Luisa Beer on Thursday October 22, 2015. The Class Notes belongs to COP 4610L at University of Central Florida taught by Staff in Fall. Since its upload, it has received 32 views. For similar materials see /class/227464/cop-4610l-university-of-central-florida in Computer Programming at University of Central Florida.
Reviews for Operating Systems Laboratory
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/22/15
Chapter 3 Fundamental Laws 31 Introduction This chapter provides the technical foundation for much of the remainder of the book It has three objectives The rst is to de ne a number of quantities of interest and to introduce the notation that we will use in referring to these quantities The second is to derive various alge braic39relationships among these quantities some of which because of their importance will be identi ed as fundamental laws The third is to explore thoroughly the most important of these fundamental laws Little s law named for JDC Little which states that the average number of requests in a system must equal the product of the throughput of that system and the average time spent in that system by a request Because of the volume of notation introduced this chapter may appear formidable It is not The material is summarized in three small tables in Section 36 which we suggest you copy for convenient reference 32 Basic Quantities If we were to observe the abstract system shown in Figure 31 we might imagine measuring the following quantities T the length of time we observed the system A the number of request arrivals we observed C the number of request completions we observed From these measurements we can de ne the following additional quanti ties 40 32 Basic Quantities 41 Arrivals Completions gt Figure 31 An Abstract System Nile A the arrival rate A E If we observe 8 arrivals during an observation interval of 4 minutes then the arrival rate is 84 2 requestsminute X the throughput X E g If we observe 8 completions during an observation interval of 4 minutes then the throughput is 84 2 requestsminute If the system consists of a single resource we also can measure B the length of time that the resource was observed to be busy Two more de ned quantities now are meaningful U the utilization U E A r If the resource is busy for 2 minutes during a 4 minute observation interval then the utilization of the resource is 24 or 50 S the average service requirement per request S E g If we observe 8 completions during an observation interval and the resource is busy for 2 minutes during that interval then on the average each request requires 2 8 minutes of service We now can derive the rst of our fundamental laws Algebraically From the three preceding de nitions 7 E U T E X 42 Preliminaries Fundamental Laws The Utilization Law U XS That is the utilization of a resource is equal to the product of the throughput of that resource and the average service requirement at that resource As an example consider a disk that is serving 40 requestssecond each of which requires 0225 seconds of disk service The utilization law tells us that the utilization of this disk must be 40X 0225 90 33 Little s Law The utilization law in fact is a special case of Little s law which we now will derive in a more general setting Figure 32 is a graph of the total number of arrivals and completions occurring at a system over time Each step in the higher step function signi es the occurrence of an arrival at that instant each step in the lower signi es a completion At any instant the vertical distance between the arrival and completion functions represents the number of requests present in the system Over any time interval the area between the arrival and completion functions represents the accumulated time in system during that interval measured in requestseconds or requestminutes etc For example if there are three requests in the system during a two second period then six requestseconds are accumulated This area is shaded in Figure 32 for an observation interval of length T 4 minutes We temporarily denote accumulated time in system by W We de ne N the average number of requests in the system N E g If a total of 2 requestminutes of residence time are accumulated during a 4 minute observation interval then the average number of requests in the system is 24 05 R the average system residence time per request R E If a total of 2 requestminutes of residence time are accumulated during an observation interval in which 8 requests complete then the average contribution of each completing request informally the average system residence time per request is 28 025 minutes W CW1 T C Algebraically 1 T But E N E X and E R 33 Little39s Law 43 Hence Little s Law N XR That is the average number of requests in a system is equal to the pro duct of the throughput of that system and the average time spent in that system by a request Arrivals Jobs ox to Time Figure 32 System Arrivals and Completions A subtle but important point in our derivation of Little s law is that the quantity R does not necessarily correspond to our intuitive notion of average residence time or response time the expected time from arrival to departure This discrepancy is due to end effects it is hard to know how to account for requests that are present just prior to the start or just after the end of an observation interval For the time being suf ce it to say that if the number of requests passing through the system during the observation interval is signi cantly greater than the number present at the beginning or end then R corresponds closely to our intui tion and if the observation interval begins and ends at instants when sys tem is empty then this correspondence is exact End effects arise 44 Preliminaries Fundamental Laws elsewhere for example considerations similar to those affecting R also affect our earlier de nition of S the average service requirement per request Little s law is important for three reasons First because it is so widely applicable it requires only very weak assumptions it will be valuable to us in checking the consistency of measurement data Second in studying computer systems we frequently will nd that we know two of the quantities related by Little s law say the average number of requests in a system and the throughput of that system and desire to know the third the average system residence time in this case Third Little s law is central to the algorithms for evaluating queueing network models which we will introduce in Part 11 Given a computer system Little s law can be applied at many different levels to a single resource to a subsystem or to the system as a whole The key to success is Consistency the de nitions of population throughput and residence time must be compatible with one another In Figure 33 we illustrate this by applying Little s law to a hypothetical timesharing system at four different levels as indicated by the four boxes in the gure quotl Figure 33 Little s Law Applied at Four Levels 33 Little39s Law 45 Box 1 is perhaps the most subtle it illustrates the application of Little s law to a single resource not including its queue In this example population corresponds to the utilization of the resource there are either zero or one requests present at any instant in time the resource is util ized whenever there is one request present thus resource utilization is equal to the proportion of time there is one request present which is also equal to the average number of requests present throughput corresponds to the rate at which the resource is satisfying requests and residence time corresponds to the average service requirement per request at the resource remember queueing delay is not included in this application of Little s law once a request acquires the resource it remains at that resource for its service time This application of Little s law constitutes an alternative derivation of the utilization law To repeat the example used previously suppose that the resource is a disk that the disk is serving 40 requestssecond X 40 and that the average request requires 0225 seconds of disk service S 0225 Then Little s law U XS tells us that the utilization of the disk must be 40X 0225 90 Box 2 illustrates the application of Little s law to the same resource this time including its queue Now population corresponds to the total number of requests either in queue or in service throughput remains the rate at which the resource is satisfying requests and residence time corresponds to the average time that a request spends at the resource per visit both queueing time and service time Suppose that the average number of requests present is 4 N 4 and that the disk is serving 40 requestssecond X 40 Then Little s law N XR tells us that the average time spent at the disk by a request must be 440 01 seconds Note that we can now compute the average queueing time of a request a total of 01 seconds are spent both queueing and receiving service of which 0225 seconds are devoted to receiving service so the average queueing time must be 0775 seconds and also the average number of requests in the queue an average total of 4 requests are either queueing or receiving service and on the average there are 09 requests receiving service so the average number awaiting service in the queue must be 1 Box 3 illustrates the application of Little s law to the central subsystem the system without its terminals Our de nition of request changes at this level we are no longer interested in visits to a particular resource but rather in systemlevel interactions Population corresponds to the number of customers in the central subsystem ie those users not think ing Throughput corresponds to the rate at which interactions ow between the terminals and the central subsystem Residence time corresponds to our conventional notion of response time the period of time from when a user submits a request until that user s response is 46 Preliminaries Fundamental Laws returned Suppose that system throughput is 12 interaction per second X 05 and that on the average there are 75 ready users N 75 Then Little s law N XR tells us that average response time must be 7505 15 seconds Finally box 4 illustrates the application of Little s law to the entire system including its terminals Here population corresponds to the total number of interactive users throughput corresponds to the rate at which interactions ow between the terminals and the system and residence time corresponds to the sum of system response time and user think time Suppose that there are 10 users average think time is 5 seconds and average response time is 15 seconds Then Little s law tells us that the system throughput must be 05 interactionssecond If we 155 denote think time by Z then we can write this incarnation of Little s law as N XRZ As with the utilization law this application is so ubi quitous that we give it its own name and notation expressing R in terms of the other quantities The Response Time Law R Z As an example application of the response time law suppose that a sys tem has 64 interactive users that the average think time is 30 seconds and that system throughput is 2 interactionssecond Then the response time law tells us that response time must be ii 30 2 seconds In earlier chapters we have noted that throughputs and utilizations typically are projected with greater accuracy than residence times We now are in a position to understand why this must be Suppose we were to construct a queueing network model of the system in the previous example The number of users 64 and the average think time 30 seconds would be parameters of the model along with the service demands at the various resources in the system Throughput and response time would be outputs of the model Suppose that the model projected a throughput of 19 interactionssecond an error of just 5 Since the response time law must be satis ed by the queueing network model a compensating error in projected response time must result 64 RT 19 30 Thus the model must project a response time of 37 seconds an error of 85 34 The Forced Flow Law 47 34 The Forced Flow Law In discussing Little s law we allowed our eld of View to range from an individual resource to an entire system At different levels of detail different de nitions of request are appropriate For example when considering a disk it is natural to de ne a request to be a disk access and to measure throughput and residence time on this basis When consider ing an entire system on the other hand it is natural to de ne a request to be a userlevel interaction and to measure throughput and residence time on this basis The relationship between these two views of a system is expressed by the forced ow law which states that the ows throughputs in all parts of a system must be proportional to one another Suppose that during an observation interval we count not only system completions but also the number of completions at each resource We de ne the visit count of a resource to be the ratio of the number of completions at that resource to the number of system completions or more intuitively to be the aver age number of visits that a systemlevel request makes to that resource If we let a variable with the subscript k refer to the kth resource a vari able with no subscript continues to refer to the system as a whole then we can write this de nition as Ck C If during an observation interval we measure 10 system comple tions and 150 completions at a speci c disk then on the average each systemlevel request requires 15010 15 disk operations If we rewrite this de nition as Ck Vk C and recall that the completion count divided by the length of the observation interval is de ned to be the throughput then the throughput of resource k is given by Vk the visit count of resource k Vk The Forced Flow Law Xk VkX An informal statement of the forced ow law is that the various com ponents of a system must do comparable amounts of work measured in transaction s worth in a given time interval As an example suppose we are told that each job in a batch processing system requires an average of 6 accesses to a speci c disk and that the disk is servicing 12 requests from batch jobs per second Then we know that the system throughput of batch jobs must be 126 2 jobssecond If in addition we are told that another disk is servicing 18 batch job requests per second then we know that each batch job requires on average 182 9 accesses to this second disk 48 Preliminaries Fundamental Laws Little s law becomes especially powerful when combined with the forced ow law As an example suppose that we are asked to determine average system response time for an interactive system with the following known characteristics 25 terminals N 25 18 seconds average think time Z 18 20 visits to a speci c disk per interaction VW 20 30 utilization of that disk Udisk 30 25 millisecond average service requirement per visit to that disk Sm5k 025 secs N We would like to apply the response time law R Y Z We know the number of terminals and the average think time but are missing the throughput We do however know the visit count at one speci c disk that is the average number of visits made to that disk by an interactive request so if we knew the throughput at that disk we would be able to apply the forced ow law to obtain systemlevel throughput To obtain disk throughput we can use the utilization law since we know both utili zation and service requirement at this device We calculate the following quantities U disk throughput Xdkk A if 3912 requestssec Sdbk 025 X v system throughput X Vd Sk 06 interactionssec disk N 25 R 39 response time X Z 06 18 23 7 secs Note that we can describe an interaction s disk service requirement in either of two ways by saying that an interaction makes a certain number of visits to the disk and requires a certain amount of service on each visit or by specifying the total amount of disk service required by an interac tion These two points of view are equivalent and whichever is more convenient should be chosen We de ne Dk the service demand at resource k Dk E Vk Sk If a job makes an average of 20 visits to a disk and requires an average of 25 milliseconds of service per visit then that job re quires a total of 20gtlt25 500 milliseconds of disk service so its service demand is 500 milliseconds at that disk From now on we will use SA to refer to the service requirement per visit at resource k and Dk to refer to the total service requirement at that resource We de ne D with no subscript to be the sum of the Dk the total service demanded by a job at all resources 34 The Forced Flow Law 49 Again consistency is crucial to success Consider using the utilization law to calculate the utilization of a resource We can express throughput in terms of visits to that resource Xk in which case service requirement must be expressed as service requirement per visit 31 Using the forced ow law we can also express throughput in terms of systemlevel interactions X in which case service requirement must be expressed on a perinteraction basis Dk In other words Uk XkSk XDk In Chapter 1 we observed that service demands are one of the parame ters required by queueing network models If we observe a system for an interval of length T we can easily obtain the utilizations of the various resources Uk and the systemlevel completion count C The service demands at the various resources then can be calculated as Dk 7 Uk be parameterized in terms of the Dk rather than the corresponding Vk and Sk since the former typically are much more easily obtained from measurement data than the latter As a nal illustration of the versatility of Little s law in conjunction with the forced ow law consider Figure 34 which represents a timesharing system with a memory constraint swapping may occur between interactions so a request may be forced to queue for a memory partition prior to competing for the resources of the central subsystem As indicated by the boxes we once again are going to apply Little s law at several diiferent levels The following actual measurement data was obtained by observing the timesharing workload on a system with several distinct workloads It is fortunate that queueing network models can average number of timesharing users 23 N 23 average response time perceived by a user 30 seconds R 30 timesharing throughput 045 interactionssecond X 45 average number of timesharing requests occupying memory 19 Mn mem average CPU service requirement per interaction 063 seconds DCPU Now consider the following questions 0 What was the average think time of a timesharing user Applying the response time law at the level of box 4 in the gure R Y Z so Z 30 or 21 seconds 0 On the average how many users were attempting to obtain service ie how many users were not thinking at their terminals Apply ing Little s law at the level of box 3 Nwam mm XR 45gtlt30 or 135 users Of the 23 users on this system an average of 135 were Preliminaries Fundamental Laws I I Terminals I I I I I I C I I l l quot a a M I I r n I I I Disks I I I I 39 I I I 39 I l I I I I I 39 I i I 39 39 I l I 39 I I l I I I I I 77 I I I i I I I I I I I l l I 39 I i 2 39 l I L l I I I3 I I4 Figure 34 Little s Law Applied to a Memory Constrained System attempting to obtain service at any one time We know from meas urement data that only 19 were occupying memory on the average so the remaining 116 must have been queued awaiting access to memory On the average how much time elapses between the acquisition of memory and the completion of an interaction Applying Little s law at the level of box 2 N mquot XRIII mm so RI me 19045 or 42 seconds In other words of the 30 second response time per ceived by a user nearly 26 seconds are spent queued awaiting access to memory What is the contribution to CPU utilization of the timesharing work load Applying the utilization law to the CPU box 1 UCPU XDCPU 45gtlt63 or 28 of the capacity of the CPU Notice that in this application of the utilization law throughput was de ned in terms of systemlevel interactions and service requirement was de ned on a perinteraction basis