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
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
High 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.)
浙大学霸代写 加微信 cstutorcs
(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
程序代写 CS代考 加QQ: 749389476
[ (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 ]
Code Help
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, 12.9, 8, 9, (2,1) (7,1)
Busy, 12.0, 6, (4,2)
Busy, – 15,
[ (6,2), 8, 4.1 ]
The event is a departure from Server 4. Sub-job (5,1) has now been completed with an arrival time of 7 and a departure time of 10.0. 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.
11 Departure ∞ Server 1
Busy, Busy, 15.1, 12.9, 8, 9, (6,2) (7,1)
Busy, 12.0, 6, (4,2)
Busy, – 15,
The event is a departure from Server 1. Sub-job (2,1) has now been completed with an arrival time of 3 and a departure time of 11.0. 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.
12 Departure ∞ Server 3
Busy, Busy, 15.1, 12.9, 8, 9, (6,2) (7,1)
Busy, – 15,
The event is a departure from Server 3. Sub- job (4,2) has now been completed with an arrival time of 6 and a departure time of 12.0. Since both queues are empty, Server 3 becomes idle. The server status has been updated accordingly. The event is a departure from Server 2. Sub- job (7,1) has now been completed with an arrival time of 9 and a departure time of 12.9. Since both queues are empty, Server 2 becomes idle. The server status has been updated accordingly.
12.9 Departure ∞ Server 2
Busy, Idle, 15.1, ∞ 8,
Busy, – 15,
15.0 Departure ∞ Server 4
Busy, Idle, Idle, Idle, 15.1, ∞ ∞ ∞ 8,
The event is a departure from Server 4. Sub- job (6,1) has now been completed with an arrival time of 8 and a departure time of 15.0. Since both queues are empty, Server 4 becomes idle. The server status has been updated accordingly. The event is a departure from Server 1. Sub- job (6,2) has now been completed with an arrival time of 8 and a departure time of 15.1. Since both queues are empty, Server 1 becomes idle. The server status has been updated accordingly.
15.1 Departure ∞ Server 1
Idle, Idle,
Table 2: Table illustrating the updates in the server farm.
The above description has not explained what happens if an arrival and a departure are at the same time. We will leave it unspecified. If we ask you to simulate in trace driven mode, we will ensure that such situation will not occur. If the inter-arrival time and service time are generated randomly, the chance of this situation occurring is practically zero so you do not have to worry about it.
Table 3 summarises the arrival and departure times of all the sub-jobs. The two sub-jobs of Job
2 complete at times 9.1 and 11.0. Hence, the departure time of Job 2 from the server farm is 11.0,
which is the later time of the two departure times. Since Job 2 arrives at time 3, the response time
of Job 2 is 11–3 = 8. The departure and response times of other jobs can be similarly computed.
The arrival and departure times of all the jobs for Example 1 are given in Table 4. The mean
response time of the 7 jobs in this example is 33.7 = 4.8143. 7
Sub-jobs (1,1) (4,1) (3,1) (2,2) (5,1) (2,1) (4,2) (7,1) (6,1) (6,2)
Arrival time 1.0 6.0 5.0 3.0 7.0 3.0 6.0 9.0 8.0 8.0
Departure time 2.8 8.1 8.9 9.1 10.0 11.0 12.0 12.9 15.0 15.1
Table 3: The arrival and departure
times of the sub-jobs for Example 1.
Job Arrival time
Departure time 2.8 11.0 8.9 12.0 10.0 15.1 12.9
Table 4: The arrival and departure times of the jobs for Example 1.
Note that in this example, we have chosen to obtain the departure times of the sub-jobs and perform post-processing to obtain the departure times of the jobs. Alternatively, the computation of the departure times of the jobs can be incorporated into the simulation exemplified in Table 2. You can use either of the methods.
4.2 Example 2: number of servers n = 4, threshold h = 2
This example is identical to Example 1 except that the threshold h = 2. In other words, for this example, the server farm uses n = 4 and h = 2, and the arrivals to the server farm are given in Table 1. Note that the setting h = 2 essentially means all sub-jobs go into the high priority queue and the low priority queue is not used at all.
Table 5 summarises the arrival and departure times of all the sub-jobs while Table 6 summarises
the arrival and departure times of all the jobs. The mean response time of the 7 jobs in this example
is 35.4 = 5.0571, which is higher than that of Example 1. This demonstrates that priority queueing 7
can be used to influence the mean response time of
the server.
Departure time 2.8 8.1 8.9 9.1 10.8 11.0 11.2 14.1 14.8 14.9
Sub-jobs (1,1) (4,1) (3,1) (2,2) (5,1) (2,1) (4,2) (6,1) (7,1) (6,2)
Arrival time 1.0 6.0 5.0 3.0 7.0 3.0 6.0 8.0 9.0 8.0
Table 5: The arrival and departure
times of the sub-jobs for Example 2.
Job Arrival time
Departure time 2.8 11.0 8.9 11.2 10.8 14.9 14.8
Table 6: The arrival and departure times of the jobs for Example 2.
5 Project description
This project consists of two main parts. The first part is to develop a simulation program for the server farm in Fig. 1. The system has already been described in Section 3 and illustrated in Section 4. In the second part, you will use the simulation program that you have developed to solve a design problem.
5.1 Simulation program
You must write your simulation program in one (or a combination) of the following languages: Python (either version 2 or 3), C, C++, or Java. All these languages are available on the CSE system.
We will test your program on the CSE system so your submitted program must be able to run on a CSE computer. Note that it is possible that due to version and/or operating system differences, code that runs on your own computer may not work on the CSE system. It is your responsibility to ensure that your code works on the CSE system.
Note that our description uses the following variable names:
1. A variable mode of string type. This variable is to control whether your program will run simulation using randomly generated arrival times and service times; or in trace driven mode. The value that the parameter mode can take is either random or trace.
2. A variable time_end which stops the simulation if the master clock exceeds this value. This variable is only relevant when mode is random. This variable is a positive floating point number.
Note that your simulation program must be a general program which allows different param- eter values to be used. When we test your program, we will vary the parameter values. You can assume that we will only use valid inputs for testing.
For the simulation, you can always assume that the system is empty initially.
5.1.1 The random mode
When your simulation is working in the random mode, it will generate the inter-arrival times
and the workload of a job in the following manner.
1. We use {a1,a2,…,ak,…,…} to denote the inter-arrival times of the jobs arriving at the dispatcher. These inter-arrival times have the following properties:
(a) Each ak is the product of two random numbers a1k and a2k , i.e ak = a1k a2k ∀k = 1, 2, … (b) The sequence a1k is exponentially distributed with a mean arrival rate λ requests/s.
(c) The sequence a2k is uniformly distributed in the interval [a2l,a2u].
Note: The easiest way to generate the inter-arrival times is to multiply an exponentially distributed random number with the given rate and a uniformly distributed random number in the given range. It would be more difficult to use the inverse transform method in this case, though it is doable.
2. The workload of a job is characterised by the number of sub-jobs and the service times of the sub-jobs. The first step to generate the workload of a job is to generate a random positive integer which is the number of sub-jobs for that job. You will be given a sequence of J non-negative real numbers p1, p2, …, pk, … , pJ with the property Jk=1 pk = 1. Given these numbers, we want the probability that a job consists of k sub-jobs to be equal to pk,
for k = 1,…,J.
For example, if you are given the sequence 0.5, 0.2, 0.3. This means for the jobs in this
workload, you have
(a) Prob[a job consists of exactly 1 sub-job] = 0.5 (b) Prob[a job consists of exactly 2 sub-jobs] = 0.2 (c) Prob[a job consists of exactly 3 sub-jobs] = 0.3
Note that you may interpret J is the maximum number of servers that a job can request.
If a job consists of k sub-jobs, then you will need to generate k random service times for the k sub-jobs. These k service times are independent and they all come from the same probability distribution. The cumulative distribution function (CDF) S(t) of the service time t for a sub-job is:
S(t) = 1 − exp(−(μ t)α) (1) where the parameters μ and α are positive real numbers.
As an example, if a job consists of 3 sub-jobs, then you will need to generate 3 random numbers which come from a probability distribution whose CDF is given by S(t).
The trace mode
When your simulation is working in the trace mode, it will read the list of inter-arrival times and the list of service times of the sub-jobs from two separate ASCII files. We will explain the format of these files in Sections 6.1.3 and 6.1.4 .
An important requirement for the trace mode is that your program is required to simulate until all jobs have departed. You can refer to Table 2 for an illustration.
Hint: Do not write two separate programs for the random and trace modes because they share a lot in common. A few if–else statements at the right places are what you need to have both modes in one program.
5.2 Determining the threshold h that minimises t