Updates to the project, including any corrections and clarifications, will be posted on the course website. Make sure that you check the course website regularly for updates.
Change log
COMP9334 Project, Term 1, 2022: Priority queueing for server farms
Due Date: 5:00pm Friday 22 April 2022 Version 1.00, 18 March 2022
Copyright By PowCoder代写 加微信 powcoder
Version 1.00. Issued on 18 March 2022.
1 Introduction and learning objectives
Server farms form the backbone of a lot of corporate information technology infrastructures. You can find them in data centres and cloud platforms. In this project, you will use simulation to study how priority queueing can be used to improve the performance of a server farm.
In this project, you will learn:
1. To use discrete event simulation to simulate a computer system 2. To use simulation to solve a design problem
3. To use statistically sound methods to analyse simulation outputs
2 Support provided and computing resources
If you have problems doing this assignment, you can post your question on the course forum. We strongly encourage you to do this as asking questions and trying to answer them is a great way to learn. Do not be afraid that your question may appear to be silly, the other students may very well have the same question!
If you need computing resources to run your simulation program, you can do it on the VLAB remote computing facility provided by the School. Information on VLAB is available here: https: //taggi.cse.unsw.edu.au/Vlab/
3 Server farm configuration for this project
Let us start with a short background. A server farm [1] consists of hundreds (or even thousands) of servers. These server farms are used to process information in data centres [2]. They can also form part of public cloud infrastructure where users can purchase computing time from cloud service providers such as Amazon, Google and Microsoft [2]. When you purchase computing time,
Dispatcher
Completed sub-jobs
Completed sub-jobs
priority queue ↓
Low priority queue ↑
Arriving jobs
Completed jobs
Figure 1: The server farm for this project.
Status of the 4 servers and queues
High pri. queue Low pri. queue
Number of servers requested
(1,1) (1,2)
Sub-job (1,1) Sub-job (1,2)
(1,1) (1,2)
(2,1) (2,2)
Sub-job (2,1) Sub-job (2,2) Sub-job (2,3)
(1,1) (1,2)
(2,1) (2,2)
(2,1) (2,2)
Sub-job (3,1)
Sub-job (1,2) completes at t4
0 t1 t2 t3 t4 Job 1 Job 2 Job 3
Figure 2: An illustration of the work load and the operation of the server farm. Each job consists of one or more sub-jobs where each sub-job is to be processed by a server.
you may have to specify the type of servers that you want, how many of them and for how long.
The configuration of the server farm that you will use in this project is shown in Fig. 1. The farm consists of a dispatcher, n servers (where n > 1) and a joiner. The dispatcher has two queues: a high priority queue and a low priority queue. You can assume that both queues have infinite queueing slots. There are no queues at the server nor joiner.
We will use the word job to refer to a request arriving at the server form. Each job will ask to use the service of one or more servers. As an illustration, in Fig. 2, Job 1 asks for 2 servers, Job 2 asks for 3 servers and Job 3 asks for 1 server. If a job asks for k servers for service, then we say that the job consists of k sub-jobs where each sub-job is to be processed by a server. For example, in Fig. 2, Job 1 asks for 2 servers, so it consists of 2 sub-jobs which are referred to as using the tuples (1,1) and (1,2). You can interpret the first coordinate of the tuple as the index to a job and the second coordinate of the tuple as the index to a sub-job. You can see other examples in Fig. 2.
We will now use Fig. 2 to illustrate the operation of the server farm assuming there are 4 (= n) servers. We assume that the server farm is empty at time 0, i.e. all servers are idle and the queues are empty. Job 1 arrives at time t1 and asks for 2 servers. Since there are sufficient number of idle servers available, all the sub-jobs will head to the servers to receive their service. Fig. 2 shows the status of the servers and queues just after time t1. We assume that it takes negligible time for the dispatcher to do its processing and to communicate with the server. This means we can assume that Sub-jobs (1,1) and (1,2) arrive at the servers at time t1.
In Fig. 2, Job 2 arrives at time t2 and asks for 3 servers. However, only two servers are idle. So, Sub-jobs (2,1) and (2,2) will head to the two idle servers, while sub-job (2,3) will join the queue. This illustrates that the sub-jobs are ordered and they are processed in an order according to their indices.
We will now explain the operation of the queues. The server farm uses a threshold h to decide whether a sub-job will join the high or low priority queue. If a sub-job comes from a job that asks for h or less servers, then that sub-job will join the high priority queue; otherwise, it will join the low priority queue. For the example in Fig. 2, we assume h = 2. Since Sub-job (2,3) comes from Job 2 and Job 2 asks for 3 servers, so the number of servers that Job 2 asks for is higher than the threshold h = 2 and this means Sub-job (2,3) will head to the low priority queue. Fig. 2 shows the status of the servers and queues just after time t2, where you can see that Sub-jobs (2,1) and (2,2) are in the servers but Sub-job (2,3) is in the low priority queue.
Before moving on, we need to further explain how the queues operate at the dispatcher. The queueing discipline in the dispatcher is non-preemptive and we will explain that in Week 7. You can also read about it on p. 500 of [1]. Since we hope that you can get your project started early, we will explain here the rules for the queues at the dispatcher:
1. If a sub-job arrives when all the servers are busy, you will need to determine whether the sub-job is of a high or low priority. After that, a high priority sub-job will go to the back of the high priority queue, and similarly a low priority sub-job will go to the back of the low priority queue.
2. When a server finishes the processing of a sub-job, it will ask the dispatcher for the next sub-job. One of the following three possibilities will happen:
(a) If the high priority queue is non-empty, the dispatcher will send the first sub-job in the high priority queue to the available server. (Note that if the high priority queue is non-empty, you do not need to check the status of the low priority queue.)
(b) If the high priority queue is empty and the low priority queue is non-empty, the dis- patcher will send the first sub-job in the low priority queue to the available server.
(c) If both queues are empty, the server will become idle.
We now continue on the example in Fig. 2 where Job 3 arrives at time t3 and asks for a server. Since all the servers are busy at the time that Job 3 arrives and Job 3 has a high priority, the only sub-job of Job 3 will join the high priority queue. Fig. 2 shows the status of the server and queues just after the arrival of Job 3.
Next, we assume that Sub-job (1,2) is completed at time t4, see Fig. 2. A completed sub-job will depart the server and head to the joiner. The available server will contact the dispatcher for a possible next sub-job. Since the high priority queue is non-empty, the sub-job at the head of the queue — which is Sub-job (3,1) — will head to the available server. Fig. 2 shows the status of the server and queues just after Sub-job (3,1) has gone to the server.
We have now explained how the dispatcher and the servers operate, we will now explain the operation of the joiner. The joiner has memory to store the results of the sub-jobs. Once all the results of all the sub-jobs of a job have arrived at the joiner, the jointer will combine all the results and send them to the user who submitted the job. We say that the departure time of a job from the server farm is the time at which the joiner sends all the results of a job to an user. We assume that it takes negligible time for a server to send results to the joiner, it takes negligible time for a joiner to combine all the results from the sub-jobs, and there is sufficient memory at the joiner to store the results from the sub-jobs. Let us consider the example in Fig. 2. Since the server completes the processing of Sub-job (1,2) at time t4, the result of Sub-job (1,2) will be at the joiner at time t4. Let us assume that Sub-job (1,1) will be done at the server at time t5 (and we assume t5 > t4), so this is also the time that the result of Sub-job (1,1) arrives at the joiner. This means that, at time t5, all the sub-jobs of Job 1 have been processed. The joiner will combine these results and send them to the user who submitted Job 1. Since it takes negligible time for the joiner to combine the results, we therefore consider that the server farm completes Job 1 at time t5. In general, consider a job that has k sub-jobs and the times at which these k sub-jobs are completed at the servers are c1, c2, …, and ck. Let cmax be the maximum of c1, c2, …, and ck. This means that all the sub-jobs of this job will have been completed at the time cmax. This means that cmax is the time that the joiner sends the results of this job to the user and the time cmax is the departure time of this job from the server farm. Consequently, the response time of a job is its departure time minus its arrival time.
We want to make a few remarks concerning this server farm. First, there are no rejections or losses in this server farm since we assume the dispatcher has infinite number of queueing slots and the joiner has sufficient memory. Second, the response time of the server farms depends only on the queues and the servers. This is because it takes negligible processing time at the dispatcher and at the joiner.
We have now completed our description of the operation of the server farm. We will provide a number of numerical examples to further explain their operation in Section 4. Note that in the illustration in this section, we have assumed particular values for the number of servers n and the threshold h for deciding whether a sub-job is considered high or low priority. However, note that n and h are parameters, and we will vary them in the simulation.
You will see that for a given number of servers n, we can use the value of threshold h to influence the mean response time of the server farm. So, a design problem that you will consider in this project is to determine the value of the threshold h to minimise the mean response time of the server farm. You can read in [1] how priority queueing can be used to reduce the mean response time of computer systems.
4 Examples
We will now present two examples to illustrate the operation of the server farm that you will simulate in this project. In all these examples, we assume that the system is initially empty.
4.1 Example 1: number of servers n = 4 and threshold h = 1
In this example, we assume the there are n = 4 servers in the server farm and the threshold h for
determining whether a sub-job is of low or high priority is 1.
In this example, each job may ask for the service of either 1 server or 2 servers. Table 1 shows, for each job, its arrival time and the service times of its sub-jobs. If there is only one service time, then it means the job is only asking for one server. If there are two service times, then the job is asking for two servers.
Job index 1
Arrival time 1
Service times of the sub-jobs 1.8
2.1, 3.1 1.9
5.0, 4.1 3.8
Table 1: Data for Example 1.
In Table 1, Job 1 has one sub-job, which can be represented as the tuple (1,1), and this sub-job requires a service time of 1.8. Job 2 has two sub-jobs and its two sub-jobs are represented by the tuples (2,1) and (2,2). The service times required by Sub-jobs (2,1) and (2,2) are, respectively, 8.0 and 6.1.
The events in the server farm are the arrival of a job to the dispatcher and the departure of a completed sub-job from a server. We will illustrate how the simulation of the server farm works using “on-paper simulation”. The quantities that you need to keep track of are:
• Next arrival time is the time of the next job arrival
• For each server, we keep track of the following information:
– Server status, which can be either busy or idle.
– Next departure time is the time at which the sub-job that is being processed will depart from the server. If the server is idle, the next departure time is ∞. Note that there is a next departure time for each server.
– For a sub-job in the server, the time that this sub-job arrives at the server farm
– The tuple to identify the sub-job in the server
For example, if the server status is “Busy, 7.5, 3.4, (1,2)”, this means the server is busy serving the sub-job identified by the tuple (1,2), and this sub-job is scheduled to depart at time 7.5 and has arrived at the server farm at time 3.4. If the server is idle, we will write the status as “Idle, ∞” where the departure time is ∞.
• The contents of the high and low priority queues. Each sub-job in the queue is identified by 3 fields: the tuple identifying the sub-job, the sub-job’s arrival time to the server farm, the sub-job’s service time. For example, we write a sub-job in a queue as
[ (4,2), 6, 3.1 ]
which means Sub-job (4,2) arrives at the server farm at time 6 and requires a service time of 3.1.
The “on-paper simulation” is shown in Table 2. The notes in the last column explain what updates you need to do for each event.
Master Event Next clock type arrival
Server Server 1 2
High Low priority priority queue queue – –
time 0 – 1
Idle, Idle,
We assume the servers are idle and queues are empty at the start of the simulation. The next departure times for all servers are ∞. The “–” indicates that the queues are empty.
1 Arrival 3
Busy, Idle, 2.8, ∞ 1,
The event is the arrival of Job 1 with one sub- job (1,1). Since all the servers are idle before this arrival, the sub-job can be sent to any one of the idle servers. We have chosen to send this sub-job to Server 1. Sub-job (1,1) requires a service time of 1.8 and it starts to receive service at time 1, so its departure time is 2.8. Lastly, we need to update the next arrival time, which is 3.
2.8 Departure 3 Server 1
Idle, Idle,
The event is a departure from Server 1. Sub- job (1,1) has now been completed with an arrival time of 1 and a departure time of 2.8. Since both queues are empty, Server 1 becomes idle. The server status has been updated accordingly.
3 Arrival 5
Busy, Busy, 11.0, 9.1, 3, 3, (2,1) (2,2)
The event is the arrival of Job 2 which consists of two sub-jobs (2,1) and (2,2). Since there are 4 idle servers before the arrival of these two sub- jobs, they can be sent to any two idle servers. We have chosen to send the two sub-jobs to Servers 1 and 2. Sub-job (2,1) requires a service time of 8.0 and it starts to receive service at time 3, so its departure time is 11.0. Similarly, Sub-job (2,2) will depart at time is 9.1. Lastly, we need to update the next arrival time, which is 5.
5 Arrival 6
Busy, Busy, Busy, 11.0, 9.1, 8.9, 3, 3, 5, (2,1) (2,2) (3,1)
The event is the arrival of Job 3 which consists of one sub-job (3,1). Since there are 2 idle servers before the arrival of this sub-job, it can be sent to any of the idle servers. We have chosen to send this sub-job to Server 3. Sub-job (3,1) requires a service time of 3.9 and it starts to receive service at time 5, so its departure time is 8.9. Lastly, we need to update the next arrival time, which is 6. The event is the arrival of Job 4 which consists of two sub-jobs (4,1) and (4,2). Since there is only one idle server before the arrival of these two sub-jobs, the first sub-job (i.e., Sub-job (4,1)) will go to the idle server (i.e., Server 4). The status of Server 4 has been updated accordingly. The second sub-job (i.e., Sub-job (4,2)) will join the queue. Since Job 4 has two sub-jobs and the threshold h = 1, therefore Sub-job (4,2) will enter the low priority queue. We enclose the details of each sub-job in the queue within a pair of square brackets. In this case, the sub-job details are [ (4,2), 6, 3.1 ] which refers to Sub-job (4,1) with an arrival time of 6 and a service time of 3.1. Lastly, we need to update the next arrival time, which is 7.
6 Arrival 7
7 Arrival 8
Busy, Busy, Busy, Busy, 11.0, 9.1, 8.9, 8.1, 3, 3, 5, 6, (2,1) (2,2) (3,1) (4,1)
[ (5,1), 7, 1.9 ]
[ (4,2), 6, 3.1 ]
The event is the arrival of Job 5 which consists of one sub-job (5,1). Since all servers are busy, Sub-job (5,1) will be sent to the queue. Since Job 5 has one sub-job and the threshold h = 1, therefore Sub-job (5,1) will enter the high priority queue. The sub-job details [ (5,1), 7, 1.9 ] are added to the high priority queue. Lastly, we need to update the next arrival time, which is 8.
Busy, Busy, Busy,
11.0, 9.1, 8.9, 8.1, 3, 3, 5, 6, (2,1) (2,2) (3,1) (4,1)
[ (4,2), 6, 3.1 ]
8 Arrival 9
Busy, Busy, Busy, Busy, 11.0, 9.1, 8.9, 8.1, 3, 3, 5, 6, (2,1) (2,2) (3,1) (4,1)
[ (5,1), 7, 1.9 ]
[ (4,2), 6, 3.1 ]
[ (6,1), 8, 5.0 ]
The event is the arrival of Job 6 which consists of two sub-jobs (6,1) and (6,2). Since all servers are busy, both sub-jobs will be sent to the low priority queue. The sub-job details [ (6,1), 8, 5.0 ] and [ (6,2), 8, 4.1 ] have been added to the low-priority queue. Lastly, we need to update the next arrival time, which is 9.
8.1 Departure 9 Server 4
Busy, Busy, Busy, Busy, 11.0, 9.1, 8.9, 10.0, 3, 3, 5, 7, (2,1) (2,2) (3,1) (5,1)
[ (4,2), 6, 3.1 ]
[ (6,1), 8, 5.0 ]
The event is a departure from Server 4. Sub- job (4,1) has now been completed with an arrival time of 6 and a departure time of 8.1. Since the high priority queue is non-empty, the first sub-job in the queue will advance to the available server. The sub-job heading to the queue has a service time of 1.9 and the current time (= master clock) is at 8.1, so the departure time of the sub-job will be 8.1 + 1.9 = 10.0. The server status has been updated accordingly.
8.9 Departure 9 Server 3
Busy, Busy, Busy, Busy, 11.0, 9.1, 12.0, 10.0, 3, 3, 6, 7, (2,1) (2,2) (4,2) (5,1)
[ (6,1), 8, 5.0 ]
[ (6,2), 8, 4.1 ]
The event is a departure from Server 3. Sub-job (3,1) has now been completed with an arrival time of 5 and a departure time of 8.9. Since the high priority queue is empty and the low priority queue is non-empty, the first sub-job in the low priority queue will advance to the available server. The server status and queue status have been updated accordingly.
9 Arrival ∞
Busy, Busy, Busy, Busy, 11.0, 9.1, 12.0, 10.0, 3, 3, 6, 7, (2,1) (2,2) (4,2) (5,1)
[ (7,1), 9, 3.8 ]
[ (6,1), 8, 5.0 ]
[ (6,2), 8, 4.1 ]
The event is the arrival of Job 7 which consists of one sub-job (7,1). Since all servers are busy, Sub- job (7,1) will be sent to the high-priority queue and the queue status has been updated. Lastly, we need to update the next arrival time to ∞ because there are no more arrivals.
[ (6,2), 8, 4.1 ]
[ (6,2), 8, 4.1 ]
9.1 Departure ∞ Server 2
Busy, Busy, 11.0, 12.9, 3, 9, (2,1) (7,1)
Busy, 12.0, 6, (4,2)
Busy, – 10.0,
[ (6,1), 8, 5.0 ]
[ (6,2), 8, 4.1 ]
The event is a departure from Server 2. Sub-job (2,2) has now been completed with an arrival time of 3 and a departure time of 9.1. Since the high priority queue is non-empty, the first sub-job in the high priority queue will advance to the avail- able server. The server status and queue status have been updated accordingly.
10 Departure ∞ Server 4
Busy, Busy, 11.0
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com