COMP9334 Capacity Planning of Computer Systems and Networks - Assignment: CPU Throughput, Markov Chain, Database
COMP9334 Capacity Planning of Computer Systems and Networks
Assignment (Version 1.01), Term 1, 2023
Question 1 (5 marks)
Assuming that you are the administrator of an interactive computer system. The computer system consists of a multi-core CPU and a disk. During an observation time of 1800 seconds, you obtained the following measurements from the system:
|Average busy time per core | 1575 s| |Disk busy time | 1124 s| |Number of requests completed by the computer system | 57|
This computer system is used by 16 interactive users and the thinking time per interactive user is 45 seconds.
You consider the current throughput of the system is too low. You are considering a proposal to upgrade the current CPU, which has 4 cores, to a new CPU with 6 cores and the same processing speed per core as that of the current CPU.
For this question, you can assume that the total workload remains the same before and after the upgrade. You can also assume that the workload is requests (note the plural) are almost evenly distributed among the cores at the moment and the workload requests can still be evenly distributed among the cores after the upgrade. As the system administrator, you know that when the workload each request (note the singular) uses the CPU, it uses only one core at a time, i.e., the workload a request does not use multiple cores concurrently.
Answer the following questions. (a) Determine the current average service demand of a core. (b) What will the average service demand per core be if the proposed CPU upgrade is carried out?
Hint: The service demand of a core depends on two factors: the number of visits to the core and the service time needed per visit to the core. For the set up of this question, one of these two factors remains the same after the upgrade, while the other factor will change. (c) What will the throughput bound of the computer system be if the proposed CPU upgrade is carried out?
Reminder: If you use a computer program to derive your numerical answers, you must include your computer program in your submission. Do not forget to show us your steps to obtain your answer.
Question 2 (7 marks)
Assuming that you are the owner of a CPU and you are happy for outsiders to use your CPU as long as these outsiders’ work does not interrupt yours and your work takes precedence over theirs. This question is inspired by people who donate their spare CPU time for scientific research.
In this question, we will use the term primary user to refer to the CPU owner (which is you) and the term external users to refer to the outsiders. We make the following assumptions:
• The CPU is configured as a single processing unit without any queueing spaces. • If a request (which can be from the primary user or an external user) arrives when the CPU is idle, the request will be admitted to the CPU. • If a request (which can be from the primary user or an external user) arrives when the CPU is working on a primary user’s request, the arriving request will be rejected. This is because there are no queueing spaces in the CPU. • If a request from the primary user arrives when the CPU is working on an external user’s request, the external user’s work will be terminated immediately and the primary user’s request will be admitted to the CPU immediately. In this case, the external user loses their work and its remaining work will not be resumed. Therefore, you can consider that the external user has left permanently. • If a request from an external user arrives when the CPU is working on another external user’s request, the newly arriving request will be rejected. • The inter-arrival times for the primary user’s requests are exponentially distributed with mean arrival rate λp ; those for the external users’ requests are exponentially distributed with mean arrival rate λe . • The service times of the primary user’s requests are exponentially distributed with a mean service time of µ1p ; those for the external users’ requests are exponentially distributed with mean µ1e . • The four probability distributions mentioned in the last two dot points are independent of each other.
Answer the following questions. You are expected to express your answers in terms of these rate parameters: λp , λe , µp and µe . (a) Let us assume that at time t, you observe that the request at the CPU belongs to an external user. What is the probability that this observed request will still be in the CPU at time (t + ∆t) where ∆t is an infinitesimal time change? You should express this probability in terms of ∆t and any of the appropriate rate parameters. (b) Formulate a continuous-time Markov chain for the CPU. Your formulation should include the definition of the states and the transition rates between states. (c) Write down the balance equations for the continuous-time Markov chain that you have formulated. (d) Derive the expressions for the steady state probabilities of the continuous-time Markov chain that you have formulated. You should be able to solve for the steady state probabilities analytical and provide answers in terms of λp , λe , µp and µe . (e) What is the probability that a request from the primary user will be admitted? Why is this probability independent of the rate parameters of the external users? (f) What is the probability that a request from an external user will be admitted?
Question 3 (8 marks)
This question is based on the system illustrated in Figure 1. The system consists of a database server and an external queue. The database server consists of a front-end server and a backend server; each server has its own queue. Each of the three queues in this system (i.e., external, front-end, back-end) has the capacity to hold only one request.
Database server Incoming requests
External queue
Front-end
Back-end
Departing requests
Figure 1 The mode of operation for the system in Figure 1 is as follows: • The total number of requests in the database server (i.e., the two servers and two queues) must be two or less. • If an incoming request arrives when there are a total of 2 requests in the database server, then the incoming request will join the external queue if it is empty; otherwise it will be rejected if the external queue is already occupied. • If an incoming request arrives when there are no requests in the database server, then the incoming request will be sent to the front-end server. • If there is one request in the database server, then an incoming request will be sent to the front-end server if it is idle or it will be placed in the front-end queue if the front-end server is busy. • After the front-end server has finished processing a request, there is a probability of p that the front-end server will send the request to the back-end server for further processing, and a probability of (1 − p) that the request will leave the database server (hence the system) permanently. • After a request has been processed by the back-end server, the request will always be sent back to the front-end for further processing; this request will need to join the queue if the front-end server is busy. • If there is a request waiting in the external queue at the time a request is leaving the database server permanently, then the request in the external queue will be admitted to the database server. There are two scenarios depending on whether the front-end queue is occupied at the time when the permanent departure takes place. If the front-end queue is occupied, then upon the permanent departure, the request in the front-end queue will move to the server and the request in the external queue will move to the front-end queue. If the front-end queue is unoccupied, then the request in the external queue will go to the front-end server.
You can assume the following for the workload: • The incoming requests are Poisson distributed with a mean arrival rate of λ requests per unit time. • The service time (i.e., per visit) to the front-end is exponentially distributed with a mean of µ1f . • The service time (i.e., per visit) to the back-end is exponentially distributed with a mean of µ1b . • All the service times and inter-arrival times are independent of each other. (a) Formulate a continuous-time Markov chain for the system. Your formulation should include the definition of the states and the transition rates between states. The transition rates should be expressed in terms λ, µf , µb and p. (b) Assuming that λ = 1.4, µf = 2.1, µb = 1.8 and p = 0.3. (i) Determine the steady state probabilities of the state of the continuous-time Markov chain that you have specified in Part (a). (ii) Determine the throughput of the database server. (iii) Determine the mean response time of the database server. Reminder: If you use a computer program to derive your numerical answers, you must include your computer program in your submission. Do not forget to show us your steps to obtain your answer.
