Performance Modeling Flashcards
Computing systems are central in today’s business and we need a deeper understanding on how they behave also from extra functional perspectives
True or false
True
There are a lot of information related to quality available early in the system life cycle
True or false
False
Little information related to quality is usually available early in the system life cycle
Why do we need to evaluate the system early in the life cycle?
Because it is of great importance from the cost and performance point of view. During design and system sizing, but also during system evolution.
How can we evaluate system quality?
Use of intuition and trend extrapolation, which is rapid and flexible but little accurate
Experimental evaluation of alternatives Which is more accurate, but laborious and inflexible
What are the techniques used to model systems
Measurement based and model-based
What are the model based techniques?
Analytical and numerical techniques are based on the application of mathematics
Simulation techniques are based on the reproduction of traces of the model
Hybrid techniques combine analytical/numerical methods with simulation
What is the queuing network modeling?
It easy particular approach to computer system modeling in which the computer system is represented as a network of queues
What is a network of queues
It is a collection of service centers, which represent system resources, and customers, which represent users or transactions
How is a graphical representation of a service center as a queue
See picture 7S in the Comp Infra album
What are the different aspects characterizing queueing models
Arrival
Service
Queue
Population
Define arrival
Arrivals represent jobs entering the system: they specify how fast, how often and which types of jobs does the station service.
Arrival can come from an external source
Arrival can come from another queue or even from the same queue, through a loop-back arc
Define service
represents the time a job spends being served.
Define the single-servers
• capability to serve one customer at a time;
• waiting customers remains in the buffer until chosen for service;
• the next customer is chosen depending on the service discipline
Define the infinite server
• there are always at least as many servers as there are customers,
• each customer can have a dedicated server
• There is no queueing, (and no buffer) in such facilities
Define multiple servers
• Fixed number of c servers, each of which can service a
customer at any time
• If the number of customers in the facility is less than or
equal to c there will no queueing
• If there are more than c customers, the additional customers will have to wait in the buffer
Define the queue in a server
If jobs exceed the capacity of parallel processing of the
system, they are forced to wait queueing in a buffer
How do we determine which of the job in the queue will be selected to start service?
Service discipline/queueing policy determines which of the job in the queue will be selected to start service
What is the population in the network queue model?
Members of the population are indistinguishable from each other, ideally. Otherwise, we divine the population into classes, whose members all exhibit the same behavior.
What are the types of queuing networks?
Open, closed, and mixed
What is the definition of open queue networks?
Customers may arrive from, or depart two, some external environment
What is the definition of closed queueing networks?
A fixed population of customers remain within the system
What is the definition of mixed queue networks?
There are classes of customers within the system, exhibiting open and close patterns of behavior, respectively
What is the definition of routing in the queue network models?
Whenever a job, after finishing service at a station has several possible alternative routes, an appropriate selection policy must be defined
What are some of the algorithms designed for routing?
Probabilistic, round robin, and join the shortest queue
Define the probability routing algorithm
Each path has assigned a probability of being chosen by the job that left the considered station
Defined the round robin routing algorithm
Destination chosen by the job rotates among all the possible exits
Define the joining the shortest queue routing algorithm
Job can query the length of the queue of the possible destinations, and choose to move to the one with the smallest number of jobs waiting to be served
What are performance bounds evaluation?
They determine asymptotic bounds on a systems performance índice
Provide valuable insight into the primary factors affecting the performance of computing systems
Highlight and quantify the critical influence of the system bottleneck
What are the operational laws in the network queueing models?
They are simple equations which may be used as an abstract representation or model of the average behavior of almost any system
What are the general assumptions taken by the operational laws?
We assume that the system receives requests from its environment, each request generates a job or customer within the system. When a job has been processed the system response to the environment with the completion of the corresponding request.
What are the observations and measurements made by the operational laws
The length of time we observe the system
The total number of requests arrivals, we observe
The number of requests completions we observe
The total amount of time during which the system is busy
The average number of jobs in the system
What are the derived measurements obtained using the operational laws
The arrival rate. Which corresponds to the number of arrivals observed in the period divide by the time in which system has been observed.
The boots or completion rate. Which corresponds to the completed request divided by the time we observed the system.
The utilization rate. Which corresponds to the relation between the totalization of the server and the total time we observed the system.
And the main service time per completed job. Which corresponds to the amount of time the server has been working divided by the amount of completed requests
Calculate the arrival rate, the throughput rate, the utilization rate and the mean service time in the picture 7 of the Comp Infra album
Arrival rate: lk = Ak/T = 7/26 req/s
Throughput: Xk = Ck/T = 7/26 req/s
Utilization: Uk = Bk/T = 20/26 = 0.77 = 77%
Avg. service time: Sk = Bk/Ck= 20/7 s
What is the utilization law?
The utilization law uses the throughput, the mean service time, and the utilization rate in order to derive the utilization of the resource without an active monitor on it. (E. I. Without knowing it busy time)
U=X . S
What is the little law?
It is a law that relates the throughout and the average time a request remain the system (response time, takes into consideration the queue time) to tell how many requests are in the system
Then, for each unity of time, we can observe in average off through times (average remain request time in the system) requests inside the system
N = X . R
Consider a disk that serves 40 requests/seconds (X = 40 req/s) and suppose that on average there are 4 requests (N = 4) present in the disk system (waiting to be served or in service)
What is the average time spent by a request at the disk?
If we know S, what is the average waiting time:
• (e.g.)Each request requires 0.0225 seconds of disk service
Little’s law tells us that R=N/X
• the average time spent at the disk by a request must be 4/40
= 0.1 seconds
We can then deduce that the average waiting time (time in the queue) is 0.0775 seconds (average time spent in the disk - time of process)
What is the residence time?
Correspondence to our conventional notion of response time, the period of time from where a user submits a request until that users responses returned, considering that the request is going to be processed by a complex system
What is the relationship in a closed system between the thing time, the throughout, and the residence time
The residence time of the total system is equal to the summation of the think time and the response time
This way we can arrive the overall number of request leave inside the system by multiplying the throughput by the residence time
This way we can calculate for example the user think time, knowing the system throughput, the system response time, and the amount of requests
Suppose that the library catalogue system has 64 interactive users connected via Browsers, the average think time is 30 seconds, and that system throughput is 2 interactions/second. What is the response time?
Theinteractiveresponsetimelawtellsusthattheresponse time must be 64/2 − 30 = 2 seconds
What does the interactive response time law states
The response time in the interactive system is the residence time minus the think time
What is the visit count?
It is the ratio of the number of completions at the k-th resource to the number of the system completions
if, during an observation interval, we measure 10 system completions and 150 completions at a specific disk, then what is the visit count for each resource
on average each system-level request requires 15 disk operations.
What is the relationship between the visit count of a given resource and the overall system visit count?
If the visit count of a given resource is greater than the visit count of the system, the resource is visited several times during each system level request
If the visit count of the resource is lower than the visit count of the system, the resource may not be visited during each system level request
What is the forced flow law
It captures the relationship between the different components within a system. It states that the throughput or flow, in all parts of a system must be proportional to one another.
The throughput at the k-th resource is equal to the product of the throughput of the system and the visit count at the resource
What is the total amount of service that a system job generates at the k-th source?
It is the service demand. And is equal to the multiplication of the meantime to service and visit count of the given resource.
What is the relationship between the utilization law and the demand of a given resource?
Uk =XkSk =(XVk)Sk=DkX
The utilisation of a resource is equal to the product of:
1. the throughput of that resource and the average service time at that resource,
2. the throughput at system level and the average service demand at that resource
When considering nodes characterized by visits different from one, we can define two permanence times
The Response Time Rk accounts for the average time spent in station k, when the job enters the corresponding node (i.e., time for the single interaction, e.g. disk request)
The Residence Time Rk accounts instead for the average time spent by a job at station k during the staying in the system: it can be greater or smaller than the response time depending on the number of visits.
What is the relationship between residency time and response time and how does it interact with the demand and mean service time?
Note that there is the same relation between Residence Time and Response Time as the one between Demand and Service Time
D = V . S
Residency = V . Response
When doing the bound analysis what are the cases we analyze?
We analyze optimistic and pessimistic cases
For throughput the optimistic case is the upper bound, but for the response time it is the lower bound
The pessimistic case for throughput is lower bound, and for response time is upper bound
In the case of open models what bound can’t we calculate?
The lower bound of throughput, because the bound of my system is determined by my arrival rate, therefore, if no request center into the system, no request is served
And the higther bound of the response time, because an infinite batch of requests arrives to my system at the same time so they wait for an infinite time (upper bound = infinity = no bound)
How do we calculate the upper bound of a open model for the throughput
The upper bound of a system happens when one resource saturates. This means that the utilization of that given resources one.
Utilization law: Uk = X . Dk
In our upper bound Uk = 1
And, therefore, the maximum throughput of the the system is 1/Dmax.
I cannot have a throughput that is higher than one over D max, otherwise the utilization of that resources higher than one which is not feasible
How do we calculate the lower bound of a open model for the response time
Lower bound of no model though is when you have only one request to your system. This way this request do not have to wait in any queue.
And the response time is equal to the summation of all the demand time of all the resources in my system
In a graph given by response time vs throughput, what is the feasible area
See picture 8S in the Comp Infra album
How do we calculate the lower bound for the throughput in closed models?
We start by using the interactive response time law, to calculate our through for one client (N=1)
N=X(R+Z)
Once there is only one client there is no queue time and therefore R=D
1=X(D+Z)
X=1/(D+Z)
Since X and R in the formula are inversely proportional, the lowest X happens with the highest R. This occurs when all jobs find the other N-1 customers in front of it (the response time of each resquest corresponds to waiting N requests in front of it to complete all the demands on the resources (R=ND)
X=N/(ND+Z)
And when our clients N go to infinity
Lim N/(ND+Z) = 1/D, which corresponds to the maximum of the lowest bound of the throughput
How do we calculate the upper bound for the throughput in closed models?
In the case of the upper bounds for the throughput, we have the opposite that we observed in the lower bound for the throughput, so we expect to attain the maximum throughput by the lowest response time
Primarily, we have the optimistic version of the case where we found all the clients in front of us at each resource (R=ND), now we find no one (R=D)
This is given by: X=N/(D+Z), a line that increases until X=1/Dmax, after which throughput can not increase anymore
How do we calculate the bounds for the response time
See picture 9S in the Comp Infra album
