Capacity Planning for Computer Systems and Networks
Week 2A: Operational Analysis (2). Workload Characterisation
Last lecture
Copyright By PowCoder代写 加微信 powcoder
• Modellingacomputersystemasaqueueingnetwork • Operationalanalysisonqueueingnetworks
• Wehavederivedtheseoperationallaws • UtilisationlawU(j)=X(j)S(j)
• ForcedflowlawX(j)=V(j)X(0)
• ServicedemandlawD(j)=V(j)S(j)=U(j)/X(0) • Little’slawN=XR
T1,2022 COMP9334 2
This lecture
• Operational analysis (Continued)
• Usingoperationallawfor
• Performance analysis
• Bottleneck analysis
• Workload characterisation
• Poissonprocessanditsproperties
T1,2022 COMP9334 3
Interactive systems
• An interactive system is used to model the interaction between humans (users) and computers
• The system consists of • A number of users
• A computer system
Interactive systems (Cont’d)
• Interactions
• Users send requests to
the computer system
• After finish processing a request, the computer system returns the result to the user
• A user, after inspecting the results from the computer system, will send another request to the system
Interactive systems: Modelling assumptions
• Analyze interactive systems with specific assumptions
• Fixed number of users denoted by M
• Each user can have at most 1 request at the computer system
• Each user goes through a cycle consisting of
• Thinkingtime
• Waitingforresulttime
Interactive cycle
• The time the request from User 1 spends in the computer system
• User 1 waiting for the results
User 1 has no requests at the system before this time. They send a request to the computer system at this time.
T1,2022 COMP9334
Results are returned to the user
User 1 sends a new request to the computer system
Thinking time
Interactive cycle
• User 1’s perspective: waiting for the result of their job
• Computer system’s perspective: Response time of the request from User 1
User 1 has no request at the system before this time. They send a request to the computer system at this time.
Results are returned to the user
User 1 sends a request to the computer system
T1,2022 COMP9334
Thinking time
= Processing time of the user. That’s why a user is depicted as a circle
• Question: At any time, what is the sum of the number of busy users and the number of requests at the computer system? M
Request at computer system
Busy user (= thinking)
User 1 User 2
T1,2022 COMP9334
Interactive system: Parameters
• M interactive users
• Z = mean thinking time
• R = mean response time of the computer system
• X0 = throughput
T1,2022 COMP9334
Analyzing interactive system: Quiz 1
• Mavg = mean # busy users
• Z = mean thinking time
• X0 = throughput
• Apply Little’s Law to the red box. What do you get?
• Mavg=Z*X0
T1,2022 COMP9334
Analyzing interactive system: Quiz 2
• Navg=average# requests in the computer system
• R=meanresponsetime at the computer system
• X0=throughput
• ApplyLittle’sLawtothe computer system (i.e. the blue box), what do you get?
• Navg=R*X0
T1,2022 COMP9334
Analyzing interactive system: Quiz 3
• Quiz1: • Quiz2:
• WhatisMavg+Navg? • M=Mavg+Navg
• Interactiveresponsetime law
• M=X0*(Z+R)
T1,2022 COMP9334
Mavg = X0 * Z
Navg = X0 * R
The operational laws
• Thesearetheoperationallaws
• UtilisationlawU(j)=X(j)S(j)
• ForcedflowlawX(j)=V(j)X(0)
• ServicedemandlawD(j)=V(j)S(j)=U(j)/X(0) • Little’slawN=XR
• InteractiveresponsetimeM=X(0)(R+Z)
• Applications
• Meanvalueanalysis(laterinthecourse) • Bottleneckanalysis
• Modificationanalysis
T1,2022 COMP9334 14
Bottleneck analysis – motivation
Utilisation
Service demand law: D(j) = U(j) / X(0) ==> U(j) = D(j) X(0)
Utilisation increases with increasing throughput and service demand
T1,2022 COMP9334 15
Utilisation vs. throughput plot U(j) = D(j) X(0)
What determines this order?
Observation: For all system throughput:
Utilisation of Disk 3 > Utilisation of Disk 2 >
Utilisation of CPU > Utilisation of Disk 1
T1,2022 COMP9334 16
Bottleneck analysis
• Recall that utilisation is the busy time of a device divided by measurement time
• Whatisthemaximumvalueofutilisation?
• Based on the example on the previous slide, which device
will reach the maximum utilisation first?
T1,2022 COMP9334 17
Bottleneck (1)
• Disk3hasthehighestservicedemand • Itisthebottleneckofthewholesystem
Operational law: } Utilisation limit:
T1,2022 COMP9334
Bottleneck (2)
Should hold for all K devices in the system
Bottleneck throughput is limited by the maximum service demand
T1,2022 COMP9334
Bottleneck exercise
The system throughput is upper bounded by ! = 7.04 jobs/s “.!$%
If we upgrade Disk 3 by a new disk which is 2 times faster, which device will be the bottleneck after the upgrade? You can assume that service time is inversely proportional to disk
T1,2022 COMP9334 20
Utilisation
Another throughput bound
• Little’s law
Previously, we have
Therefore:
T1,2022 COMP9334 21
Throughput bounds
Throughput
Bound 2. Slope =
Actual throughput
T1,2022 COMP9334
Bottleneck analysis
• Simple to use
• Needsonlyutilisationofvariouscomponents
• Assumes service demand is load independent
T1,2022 COMP9334 23
Modification analysis (1)
(Reference:LazowskaSection5.3.1)
Acompanycurrentlyhasasystem(3790)andisconsideringswitching to a new system (8130). The service demands for these two systems are given below:
Service demand (seconds) Disk
8130 5.1 1.9
Thecompanyusesthesystemforinteractiveapplicationwithathink time of 60s.
Giventhesameworkload,shouldthecompanyswitchtothenew system?
Exercise:Answerthisquestionbyusingbottleneckanalysis.Foreach system, plot the upper bound of throughput as a function of the number of interactive users.
T1,2022 COMP9334 24
Modification analysis (2)
Slope = 1/68.6
Slope = 1/67
T1,2022 COMP9334 25
Operational analysis
• Operational analysis allows you to bound the system performance but it does NOT allow you to find the throughput and response time of a system
• To order to find the throughput and response time, we need to use queueing analysis
• To order to use queueing analysis, we need to specify the workload
T1,2022 COMP9334 26
Workload analysis
• Performancedependsonworkload
• Whenwelookattheperformanceboundearlier,thebounds
depend on number of users and service demand
• Queueresponsetimedependsonthejobarrivalprobability distribution and job service time distribution
• Recall from Lecture 1A:
• Uniform arrival times and uniform processing times result in zero waiting
• But non-uniform distributions give non-zero waiting time
• Needtospecifyworkloadbyusingprobabilitydistribution. • Wewilllookatawell-knownarrivalprocesscalledPoisson
process today.
T1,2022 COMP9334 27
Arrival process
• Each vertical arrow in the time line below depicts the arrival
of a customer
Inter-arrival time
• Anarrivalcanmean
• A telephone call arriving at a call centre
• A transaction arriving at a computer system
• A customer arriving at a checkout counter
• An HTTP request arriving at a web server
• Theinter-arrivaltimedistributionwillimpactontheresponsetime.
• Wewillstudyaninter-arrivaltimedistributionthatresultsfromalarge
number of independent customers.
T1,2022 COMP9334 28
Describing arrivals probabilistically
• Assumeacustomerarrivesattime0
At least one arrival in (0,t]
No arrivals in (0,t]
• Quiz:Whatistherelationbetweenthefollowingtwoprobabilities?
• Prob[at least one arrival in (0,t] ]
• Prob[no arrivals in (0,t] ]
• Answer:Theyaddupto1
• Moral:”Noarrivals”isnotboring,ittellsyousomething
T1,2022 COMP9334 29
Inter-arrival time probability
• Assumeacustomerarrivesattime0
Inter-arrival time
Next arrival is after time t
No arrivals in (0,t]
• Quiz:Whatistherelationbetweenthefollowingtwoprobabilities?
• Prob[Inter-arrival time is >= t]
• Prob[no arrivals in (0,t] ] • Answer:Equal
• Nextstep:FindProb[noarrivalsin(0,t]]forindependentcustomers
T1,2022 COMP9334 30
Many independent arrivals (1)
• Problemsetup:
• An arrival at time 0
• A large pool of N independent customers
• Behaviour of each customer: Within a small time interval of d, a customer sends a request (or arrives) with a probability of pd
• p is a constant
• Quiz:Ifthereare2(=N)customers,whatistheprobabilitythatboth of them do not send any request in the time interval d
• Answer: (1 – p d)2
Customer 1
Customer 2
Prob[Send] = pd Prob[Not send] = 1 – pd
Prob[Send] = pd Prob[Not send] = 1 – pd
Picture credit: openclipart.org 31
Many independent arrivals (2)
• Aim: Want to find the probability of no arrivals in (0,t] • Divide the time t into intervals of width d
• No arrivals in (0,t] = no arrivals in each interval d from N users • Probability of no arrivals in d =
• There are t / d intervals
• Probability of no arrivals in (0,t] is
(1 – p d)N
T1,2022 COMP9334 32
Exponential inter-arrival time
• We have showed
Probability(no arrivals in (0,t]) =
• Probability(inter-arrival time > t) =
• This means
Probability(inter-arrival time £ t) =
• What this shows is the inter-arrival time distribution for
independent arrival is exponentially distributed
• Define: l = Np
• l is the mean arrival rate of customers
T1,2022 COMP9334 33
Exponential distribution – cumulative distribution
• Cumulative distribution of inter-arrival time with customer arrival rate l
• Prob(inter-arrivaltime£t)=1-exp(-lt)
Prob that at least a customer will arrive before t = 1 for l = 1
Prob that at least a customer will arrive before t = 1 for l = 3
T1,2022 COMP9334
Exponential distribution
• A continuous random variable is exponentially distributed with rate l if it has probability density function
Probability density function
integration Cumulative differentiation probability
T1,2022 COMP9334 35
Probability density function (PDF)
Reminder: PDF f(t) Probability(t £ T £ t + dt) = f(t) dt
Red area = probability that inter-arrival time is in the interval [0,0.2]
Blue area = probability that the inter-arrival time is in the interval [1,1.2]
Two different methods to describe arrivals
Method 1: Continuous probability distribution of inter-arrival time
Inter-arrival time
T1,2022 COMP9334
Two different methods to describe arrivals
Method 2: Use a fixed time interval (say t), and count the number of arrivals within t.
5 arrivals in t 8 arrivals in t
6 arrivals in t
• The number of arrivals in t is random
• The number of arrivals must be a non-negative integer
• We need a discrete probability distribution:
• Prob[#arrivals in t = 0]
• Prob[#arrivals in t = 1] • etc.
T1,2022 COMP9334 38
Poisson process (1)
• Definition: An arrival process is Poisson with parameter l if the probability that n customers arrive in any time interval t is
l= 5 and t = 1
Note: Poisson is a discrete probability distribution.
T1,2022 COMP9334
Poisson process (2)
• Theorem: An exponential inter-arrival time distribution with parameter l gives rise to a Poisson arrival process with parameter l
• How can you prove this theorem?
• Apossiblemethodistodivideanintervaltintosmalltimeintervals of width d. A finite d will give a binomial distribution and with d ! 0, we get a Poisson distribution.
T1,2022 COMP9334 40
Customer arriving rate
• Given a Poisson process with parameter l, we know that the probability of n customers arriving in a time interval of t is given by:
• What is the mean number of customers arriving in a time interval of t?
• That’s why l is called the arrival rate.
T1,2022 COMP9334 41
Customer inter-arrival time
• You can also show that if the inter-arrival time distribution is exponential with parameter l, then the mean inter-arrival time is 1/l
• Quite nicely, we have
Mean arrival rate = 1 / mean inter-arrival time
T1,2022 COMP9334 42
Application of Poisson process
• Poisson process has been used to model the arrival of telephone calls to a telephone exchange successfully
• Queueing networks with Poisson arrival is tractable • Wewillseethatinthenextfewweeks.
• Beware that not all arrival processes are Poisson! Many arrival processes we see in the Internet today are not Poisson. We will see that later.
T1,2022 COMP9334 43
References
• Operationalanalysis
• Lazowska et al, Quantitative System Performance, , 1984. (Classic text on performance analysis. Now out of print but can be download from http://www.cs.washington.edu/homes/lazowska/qsp/
• Chapters 3 and 5 (For Chapter 5, up to Section 5.3 only)
• Alternative 1: You can read Menasce et al, “Performance by design”, Chapter 3. Note that Menasce doesn’t cover certain aspects of performance bounds. So, you will also need to read Sections 5.1-5.3 of Lazowska.
• Alternative 2: You can read Harcol-Balter, Chapters 6 and 7. The treatment is more rigorous. You can gross over the discussion mentioning ergodicity.
• Poisson process: Harcol-Balter Chapter 11
T1,2022 COMP9334 44
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com