COMP9334 Project Term 1 2023 Priority queueing for multi-phase jobs
Version 1.02 (11 April 2023) The changes are in magenta color and can be found on Pages 9, 21 and 23.
Version 1.01 (25 March 2023) The changes are:
Copyright By PowCoder代写 加微信 powcoder
– There were errors in Section 4.2 and this section has been reduced to remove the errors.
– Sections 4.3 and 4.4 have been added.
– Some parameters for the design problem in Section 5.2 have changed, see the text typeset in blue.
– There are also changes in Section 6.1.4 and 6.4, see the text in blue and the yellow highlight.
– You should download sample project files 25Mar.zip and discard the earlier ver- sion.
Version 1.00. Issued on 20 March 2023.
Introduction and learning objectives
COMP9334 Project, Term 1, 2023: Priority queueing for multi-phase jobs
Due Date: 5:00pm Friday 21 April 2023 Version 1.02
When you were learning about operational analysis earlier in the term, we talked about jobs that require multiple visits to the CPU (or servers) to receive their service. In this project, you will use simulation to study how priority queueing can be used to improve the performance of a multi- server system that works on jobs that require multiple visits to the servers.
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
Dispatcher
Jobs requiring further processing are sent back to the dispatcher
Jobs that do not require further processing depart the system permanently
Jobs requiring further processing are sent back to the dispatcher
Jobs that do not require further processing depart the system permanently
Jobs arriving externally
Jobs requiring further processing,
i.e., recirculated jobs
High priority queue ↓
Low priority queue ↑
Figure 1: The system for this project.
2 Support provided and computing resources
If you have problems doing this project, 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! Please note that if your forum post shows part of your solution or code, you must mark that forum post private.
Another way to get help is to attend a consultation (see the Timetable section of the course website for dates and times).
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 Multi-server system configuration and job characteristics for this project
The configuration of the system that you will use in this project is shown in Figure 1. The sys- tem consists of a dispatcher and n servers where n > 1. The dispatcher has two queues: a high priority queue and a low priority queue. You can assume that both queues have infinite queueing slots. You have not learnt about priority queues yet but the following description will explain how priority queues are used.
We will use the word job to refer to a request that requires service from this system. A job 2
may require one or more visits to the servers in order to get all its work completed. These visits of a job take place one after another with a possible time gap between two consecutive visits. Jobs in this system do not use parallel processing so each job does not use more than one server at a time.
We will now explain how this system handles a new job. When a new job (i.e., an external arrival) arrives at the system, the dispatcher will send the job to any one of the idle servers if there is at least one idle server. If all the servers are busy, the dispatcher will place this job at the end of the high priority queue.
After a job has completed a visit to the server, the job either requires or does not require further visits to the servers. If the job does not require further visits to the servers, then the job will depart from the system permanently. If the job requires further visits to the servers, then the job will be sent back to the dispatcher. We will use the term re-circulated jobs to refer to those jobs that are sent back to the dispatcher from the servers because these jobs require further visits to the servers.
A job that arrives at the dispatcher can either be a new job or a re-circulated job, see Figure 1. We have already explained how the dispatcher handles new jobs. We will start to describe how the dispatcher handles the re-circulated jobs. Since the dispatcher handles all re-circulated jobs in the same way, the procedure therefore applies to a generic re-circulated job. We first need to define some notation. First, when a re-circulated job arrives at the dispatcher, the job can have completed 1, 2, 3 or more visits to the servers. We will use c to denote the number of completed server visits when a re-circulated job arrives at the dispatcher. Second, the dispatcher uses a threshold h, which is an integer bigger than or equal to 1, to decide on whether an arriving re- circulated job should be considered a high or low priority job. Now we have defined the notation, we can state the rule that the dispatcher uses: When a re-circulated job arrives at the dispatcher, the dispatcher will classify this job as low priority if its value of c is greater than or equal to h; otherwise the job is a high priority job. Let us consider an example.
Example 1 In this example, we assume the threshold h has a value of 2. Let us consider a job which requires altogether 3 server visits before it will permanently depart from the system. So, this job will re-circulate to the dispatcher two times: once with a value of c = 1 and the other with c = 2.
• When this job re-circulates to the dispatcher the first time, its value of c will be 1. Since c ≥ h does not hold, the dispatcher will consider this job as a high priority job on this occasion.
• The second time that this job re-circulates to the dispatcher, its value of c will be 2. Since c ≥ h holds, the dispatcher will consider this job as a low priority job on this occasion.
We have now explained how the dispatcher classifies an arriving re-circulated job into either a high or low priority job. We have yet to explain the detailed working of the dispatcher. We will do that together with the description of how departures are handled. This is because the arrival of a re-circulated job at a dispatcher follows the job’s earlier departure from a server, see Figure 1. The following steps describe how a job, which has completed a server visit, will be handled. For ease of referral, we will use the term tagged job to refer to this job that has just completed its server visit.
• The tagged job is considered to be a permanent departure if the number of complete visits that it has already made is equal to the total number of visits that this job requires. If the tagged job is not a permanent departure, then it will be re-circulated to the dispatcher. The server that was working on the tagged job would send a message to the dispatcher to inform it that it is available to serve another job.
• If the tagged job is a re-circulated job, then it will be sent to the dispatcher which will classify it into either a high or low priority job using the values of c and h as described earlier. The dispatcher will then place the tagged job at the end of the appropriate queue.
• The dispatcher is aware that a server has just completed a visit of a job and is available to process another job. The dispatcher executes the following:
– If the high priority queue is non-empty, then the job at the head of the high priority queue will be sent to the available server for processing.
– If the high priority queue is empty and the low priority queue is non-empty, then the job at the head of the low priority queue will be sent to the available server for processing.
– If both high and low priority queues are empty, then the dispatcher does not need to do anything. The server that has just been made available will go idle.
We remark that the above description means that the dispatcher uses the non-preemptive queue- ing discipline. We will be discussing queueing disciplines in Week 7 and you can read about it on p. 500 of [1]. However, the above description should be enough for you to get your project going now even before we discuss priority queues in Week 7.
We make the following assumptions on the system in Figure 1. First, it takes the dispatcher negligible time to process a job, to classify a job and to send a job to an available server. Second, it takes a negligible time for a server to send a re-circulated job to the dispatcher and to inform the dispatcher on its availability. As a consequence of these assumptions, it means that: (1) If a job arriving at the dispatcher is to be sent to an available server right away, then its arrival time at the dispatcher is the same as its arrival time at the chosen server; (2) The departure time of a job from the dispatcher is the same as its arrival time at the chosen server; and (3) The departure time of a re-circulated job from a server is the same as its arrival time at the dispatcher. Ultimately, these assumptions imply that the response time of the system depends only on the queues and the servers.
We have now completed our description of the operation of the system in Figure 1. We will provide a number of numerical examples to further explain its operation in Section 4.
You will see from the numerical examples in Section 4 that the threshold h can be used to influence the system’s mean response time. 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 system. You can read in [1] how priority queueing can be used to reduce the mean response time of computer systems.
Remark 1 This project is inspired by a recent work [2] which studies how priority queueing can be used to improve the performance of a multi-server system that provide service to multi-phase jobs. A multi-phase job also requires multiple visit to the servers in order to get its work done. However, the multi-phase job in [2] will sometimes require only the service of a server but sometimes it may require a number of servers in parallel. In order to make this project more do-able, we have simplified many of the settings in [2]. For example, we do not use preemptive queueing, processor sharing and parallel servers.
4 Examples
We will now present two examples to illustrate the operation of the system 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 = 2 and threshold h = 1
In this example, we assume the there are n = 2 servers in the system and the threshold h for
determining whether a re-circulated job is of low or high priority is 1.
In this example, each job requires one or two visits to the servers before it permanently departs from the system. Table 1 shows, for each job, its arrival time and the service times for its visits. If there is only one service time in the third column in Table 1, then it means the job only requires one server visit. If there are two service times, then the job requires two server visits. For example, Job 1 in Table 1 requires two visits where the first and second visits require, respectively, 3 and 10 time units of service times. As another example, Job 3 requires only one visit and the service time required for that visit is 6 time units.
1 0.9 2 1.5 3 2.2 4 3.3 5 8.0
Service times of the job’s server visits 3, 10
Table 1: Data for Example 1.
Arrival time
In this example, a job will be identified with using the tuple (i, c/r) where i is the job’s index (see the first column of Table 1), c is the number of complete servers visits made by the job and r is the total number of server visits required by the job. For example,
• The job (1, 0/2) refers to the job with index 1. We know from Table 1 that Job 1 requires 2 visits to the servers and this is indicated by “/2”. The notation “0/2” says that this job has done zero complete visits to the servers. When Job 1 re-circulates to the dispatcher for the first time, its tuple becomes (1, 1/2).
• The job (5, 1/2) refers to Job 5 which requires altogether 2 visits to the servers. The notation “1/2” says that this job has done one complete visit to the servers out of the two required visits.
Remark 2 We remark that the job indices are not necessary for carrying out the discrete event simulation. We have included the job index to make it easier to refer to a job in our description below.
The events in the system in Figure 1 are the arrival of a new job to the dispatcher and the completion of a visit at a server. Note that we have not included the arrival of a re-circulated job to the dispatcher as an event. This is because the arrival of a re-circulated job at the dispatcher is immediately after the completion of a server visit. So the simulation will handle the arrival of re-circulated job at the dispatcher and its associated server completion together.
We will illustrate how the simulation of the system works using “on-paper simulation”. The quantities that you need to keep track of are:
• Next arrival time is the time that the next new job will arrive
• For each server, we keep track its server status, which can be busy or idle.
• We also keep track of the following information on the job that is being processed in the server:
– Next completion time is the time at which the job will complete its current server visit. If the server is idle, the next completion time is set to ∞. Note that there is a next completion time for each server.
– The time that this job arrived at the system. This is needed for calculating the response time of the job when it permanently departs from the system.
– A list of the service times for the future server visits of this job. Note that we enclose the list of service times within a pair of square brackets [ ].
– The job’s tuple.
For example, the job information “3.5, 1.5, [1], (2,0/2)” indicates that current visit will be completed at time 3.5 and this job arrived at the system at time 1.5. The “0/2” indicates that the job has not completed any server visits so the current visit is the job’s first visit to the server. The “[1]” indicates that the job needs one more visit in the future and this visit will require a service time of 1. Note that if the job has no more future visits to make, then we will use [ ] to indicate that.
• The contents of the high and low priority queues. Each job in the queue is identified by 3 fields: the job’s tuple, the job’s arrival time to the system, a list of the job’s service times for its future server visits. For example, we write a job in a queue as
[(1,1/2), 0.9, [10] ]
which means the job (1,1/2) arrived at the system at time 0.9, has 1 visit completed and its future visit to the server will require a service time of 10.
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. Recall that the two event types in this simulation are the arrival of a new job to the dispatcher and the completion of a visit at a server, we will simply refer to these two events as Arrival and Completion in the “Event type” column (i.e., second column) in Table 2.
Master Event clock type
Next Server arrival 1
Server High priority Low priority queue 2 queue
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.
This event is the arrival of Job 1 as a new job. Since all the servers were idle before this arrival, the job can be sent to any one of the idle servers. We have chosen to send this job to Server 1. At the time this job enters the server, the job has zero completed visits so it is identified by (1, 0/2). The job requires a service time of 3 for this visit and it starts to receive service at time 0.9, so its completion time is 3.9. Note that the record of the job in the server also includes the list of service times [10] that the job requires in its future visit; you will see how this information will be used later on. From Table 1, you can see that Job 1 requires two visits with service times 3 and 10, and we want to point out we no longer need to remember the first service time 3 as it is for this visit and will not be needed again in the future; the service time 3 has been used to compute the completion time of this visit and this is all we need this service time for. Lastly, we need to update the arrival time of the next new job, which is 1.5.
0.9 Arrival
Idle, –– 3.9, ∞
1.5 Arrival
This event is the arrival of Job 2 as a new job. Since there was an idle server before this arrival, the job can be sent to the idle server. The job (2, 0/2) requires a service time of 2 for this visit and it starts to receive service at time 1.5, so the completion time of this visit is 3.5. Lastly, we need to update the arrival time of the next new job, which is 2.2.
0.9, [10], (1,0/2)
0.9, 1.5, [10] [1], (1,0/2) (2,0/2)
2.2 Arrival
Busy, Busy, 3.9, 3.5, 0.9, 1.5, [10], [1] (1,0/2) (2,0/2)
[(3,0/1), 2.2, [6] ]
This event is the arrival of Job 3 as a new job. Since both servers were busy before this arrival, the job is placed at the end of the high priority queue. The record of the job in the queue has 3 components: (i) Its tuple identifier (3, 0/1) indicating that it has not received any service; (ii) Its arrival time at 2.2; (iii) A list of its service times for its future visits and for this job, this is [6] as it requires 6 time units for a future server visit. The number 6 will be used to determine the completion time when this job enters into a server. Lastly, we need to update the arrival time of the next new job, which is 3.3.
3.3 Arrival
Busy, Busy, 3.9, 3.5, 0.9, 1.5, [10], [1] (1,0/2) (2,0/2) Busy, Busy, 3.9, 9.5, 0.9, 2.2, [10], [], (1,0/2) (3,0/1)
[(3,0/1), 2.2, [6] ], [(4,0/1), 3.3, [2] ]
This event is the arrival of Job 4 as a new job. Since both servers were busy before this arrival, the job is placed at the end of the high priority queue. Lastly, we need to update the arrival time of the next new job, which is 8.
3.5 Completion 8.0
[(4,0/1), 3.3, [2] ]
[(2,1/2), 1.5, [1]]
This event is the completion of a visit of the Job (2,0/2). Upon this completed visit, this job will now be identified by (2,1/2). The iden- tifier indicates that this job will require future visits to the server so this job will be re-circulated to the dispatcher. The dispatcher seesthatthisjobhasc=1andfindsthatc≥hholds,sothisjob should join the low priority queue. Since the high priority queue is non-empty, the job at the top of the priority queue will move to the server. This job requires 6 units of service so its completion time should be 3.5 + 6 = 9.5. Note that the list of future service times in the server for this job is now empty (i.e, [ ]) rather than [6] because we have already used the number 6 to calculate the job’s completion time for this visit, so this number will no longer be needed in the future.
3.9 Completion 8.0
Busy, 5.9, 3.3,
[], (4,0/1)
Busy, – 9.5,
[], (3,0/1)
[(2,1/2),1.5,[1]], [(1,1/2),0.9, [10]]
This event is the completion of a visit of Job (1,0/2). Upon this completed visit, this job will now be identified by (1,1/2). This job will be re-circulated to the dispatcher. Since c = 1, the dispatcher will place thi
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com