34-1©2011 Raj JainCSE567MWashington University in St. LouisMean Value Analysis Mean Value Analysis and Related Techniquesand Related TechniquesRaj Jain Washington University in Saint LouisSaint Louis, MO [email protected]/Video recordings of this lecture are available at:http://www.cse.wustl.edu/~jain/cse567-11/34-2©2011 Raj JainCSE567MWashington University in St. LouisOverviewOverview1. Analysis of Open Queueing Networks2. Mean-Value Analysis3. Approximate MVA4. Balanced Job Bounds34-3©2011 Raj JainCSE567MWashington University in St. LouisAnalysis of Open Queueing NetworksAnalysis of Open Queueing Networks Used to represent transaction processing systems, such as airline reservation systems, or banking systems. Transaction arrival rate is not dependent on the load on the computer system. Arrivals are modeled as a Poisson process with a mean arrival rate . Exact analysis of such systems Assumption: All devices in the system can be modeled as either fixed-capacity service centers (single server with exponentially distributed service time) or delay centers(infinite servers with exponentially distributed service time).34-4©2011 Raj JainCSE567MWashington University in St. LouisAnalysis of Open Queueing NetworksAnalysis of Open Queueing Networks For all fixed capacity service centers in an open queueing network, the response time is:Ri= Si(1+Qi) On arrival at the ithdevice, the job sees Qijobs ahead (including the one in service) and expects to wait QiSiseconds. Including the service to itself, the job should expect a total response time of Si(1+Qi) . Assumption: Service is memory-less (not operationally testable) Not an operational law Without the memory-less assumption, we would also need to know the time that the job currently in service has already consumed.34-5©2011 Raj JainCSE567MWashington University in St. LouisMean PerformanceMean Performance Assuming job flow balance, the throughput of the system is equal to the arrival rate:X = The throughput of ithdevice, using the forced flow law is:Xi= X Vi The utilization of the ithdevice, using the utilization law is:Ui= XiSi= X ViSi= Di The queue length of ithdevice, using Little's law is:Qi= XiRi= XiSi(1+Qi) =Ui(1+Qi)Or Qi= Ui/(1-Ui) Notice that the above equation for Qiis identical to the equation for M/M/1 queues.34-6©2011 Raj JainCSE567MWashington University in St. LouisMean PerformanceMean Performance The device response times are: In delay centers, there are infinite servers and, therefore: Notice that the utilization of the delay center represents the mean number of jobs receiving service and does not need to be less than one.34-7©2011 Raj JainCSE567MWashington University in St. LouisExample 34.1Example 34.1 File server consisting of a CPU and two disks, A and B. With 6 clients systems:34-8©2011 Raj JainCSE567MWashington University in St. LouisExample 34.1 (Cont)Example 34.1 (Cont)34-9©2011 Raj JainCSE567MWashington University in St. LouisExample 34.1 (Cont)Example 34.1 (Cont) Device utilizations using the utilization law are:34-10©2011 Raj JainCSE567MWashington University in St. LouisExample 34.1 (Cont)Example 34.1 (Cont) The device response times using Equation 34.2 are: Server response time: We can quantify the impact of the following changes:34-11©2011 Raj JainCSE567MWashington University in St. LouisExample 34.1 (Cont)Example 34.1 (Cont) Q: What if we increase the number of clients to 8? Request arrival rate will go up by a factor of 8/6. Conclusion: Server response time will degrade by a factor of 6.76/1.406= 4.834-12©2011 Raj JainCSE567MWashington University in St. LouisExample 34.1 (Cont)Example 34.1 (Cont) Q: What if we use a cache for disk B with a hit rate of 50%, although it increases the CPU overhead by 30% and the disk B service time (per I/O) by 10%. A:34-13©2011 Raj JainCSE567MWashington University in St. LouisExample 34.1 (Cont)Example 34.1 (Cont) The analysis of the changed systems is as follows: Thus, if we use a cache for Disk B, the server response time will improve by (1.406-1.013)/1.406 = 28%.34-14©2011 Raj JainCSE567MWashington University in St. LouisExample 34.1 (Cont)Example 34.1 (Cont) Q: What if we have a lower cost server with only one disk (disk A) and direct all I/O requests to it? A: the server response time will degrade by a factor of 3.31/1.406 = 2.3534-15©2011 Raj JainCSE567MWashington University in St. LouisMeanMean--Value Analysis (MVA)Value Analysis (MVA) Mean-value analysis (MVA) allows solving closed queueing networks in a manner similar to that used for open queueing networks It gives the mean performance. The variance computation is not possible using this technique. Initially limit to fixed-capacity service centers. Delay centers are considered later. Load-dependent service centers are also considered later. Given a closed queueing network with N jobs:Ri(N) = Si(1+Qi(N-1)) Here, Qi(N-1) is the mean queue length at ithdevice with N-1 jobs in the network. It assumes that the service is memoryless34-16©2011 Raj JainCSE567MWashington University in St. LouisMeanMean--Value Analysis (MVA)Value Analysis (MVA) Since the performance with no users ( N=0 ) can be easily computed, performance for any number of users can be computed iteratively. Given the response times at individual devices, the system response time using the general response time law is: The system throughput using the interactive response time law is:34-17©2011 Raj JainCSE567MWashington University in St. LouisMeanMean--Value Analysis (MVA)Value Analysis (MVA) The device throughputs measured in terms of jobs per second are:Xi(N)= X(N) Vi The device queue lengths with N jobs in the network using Little's law are:Qi(N)= Xi(N) Ri(N)= X(N) ViRi(N) Response time equation for delay centers is simply:Ri(N) = Si Earlier equations for device throughputs and queue lengths apply to delay centers as well.Qi(0)=034-18©2011 Raj JainCSE567MWashington University in St. LouisExample 34.2Example 34.2 Consider a timesharing system Each user request makes ten I/O requests to disk A, and five I/O requests to disk B. The service times per visit to disk A and disk B are 300 and 200 milliseconds, respectively. Each request takes two seconds of CPU time and the user think time is four seconds.34-19©2011 Raj JainCSE567MWashington
View Full Document
Unlocking...