COMP9334
Capacity Planning for Computer Systems and Networks
Week 7A_1: Queueing disciplines
COMP9334
1
Queuing disciplines
Arrivals
Departures
• We have focused on first-come first-serve (FCFS) queues so far
• However, sometimes you may want to give some jobs a higher priority than others
• Priority queues can be classified as • Non-preemptive
• Preemptiveresume
T1,2021 COMP9334 2
What is priority queueing?
High priority jobs
Arrivals
Departures
Low priority jobs
• Ajobwithlowprioritywillonlygetservedifthehighpriorityqueueis empty
• EachpriorityqueueisaFCFSqueue
• Exercise:Iftheserverhasfinishedajobandfinds1jobinthehigh priority queue and 3 jobs in the low priority queue, which job will the server start to work on?
• Repeat the exercise when the high priority queue is empty and there are 3 jobs in the low priority queue.
T1,2021 COMP9334 3
Preemptive and non-preemptive priority (1)
• Example:
High priority job queue
Low priority job queue
10
Job in server
Time t = 9
9
time
Time t = 10 : A high priority job requiring 1s
of processing arrives
• Thehighpriorityjobqueueis empty
• Theserverstartsservingalow priority job which requires 2s of processing
T1,2021 COMP9334
4
Preemptive and non-preemptive priority (2)
• Non-preemptive:
• Ajobbeingservedwillnotbeinterrupted(evenifahigher
priority job arrives in the mean time)
• Example: High priority job (red), low priority job (green)
Job in server
9 10 11
time
T1,2021 COMP9334
5
Time t = 11 : Server finishes processing the low priority job. It takes the high priority job in from the queue
Time t = 10 : A high priority job requiring 1s of
processing arrives.
The job joins the high priority queue
Preemptive and non-preemptive priority (3)
• Preemptive resume:
• Higherpriorityjobwillinterruptalowerpriorityjobunderservice.Once
all higher priorities served, an interrupted lower priority job is resumed. • Example: High priority job (red), low priority job (green)
Job in server
9 10 11
time
T1,2021 COMP9334
6
Time t = 11 : Server finishes processing the high priority job. Since no high priority job arrives in (10,11], the high priority job queue is empty, it resumes processing the low priority job that is pre-empted at time t = 10
Time t = 10 : A high priority job requiring 1s of processing
arrives.
The server starts processing the high priority job immediately
Example of non-preemptive priority queueing
High priority packets
Arrivals
Departures
•
Example: In the output port of a router, you want to give some packets a higher priority
• In Differentiated Service
• Real-time voice and video packets are given higher priority because they need
a lower end-to-end delay
• Other packets are given lower priority
You cannot preempt a packet transmission and resume its transmission later
• A truncated packet will have a wrong checksum and packet length etc.
•
Low priority packets
T1,2021 COMP9334 7
Example of preemptive resume priority queueing
• E.g. Modelling multi-tasking of processors
• Can interrupt a job but you need to do context switching (i.e. save the registers for the current job so that it can be resumed later)
T1,2021 COMP9334 8
M/G/1 with priorities
• Separatequeueforeachpriority(seepicturenextpage) • ClassifiedintoPprioritiesbeforeenteringaqueue
• Prioritiesnumbered1toP,Queue1beingthehighestpriority
• Arrivalrateofpriorityclasspis
λp wherep = 1,!P
• Average service time and second moment of class p requests is given by
ES andES2 [p] [p]
T1,2021 COMP9334 9
€
Priority queue
Highest priority
Arrival rate for each priority class
Departures
Lowest priority
Let us derive the waiting time for P = 2
T1,2021
COMP9334
10
Lecture 4A: Deriving the P-K formula
Substitution
T1,2021 COMP9334
11
Arrival rate l
• Applying Little’s Law to the queue
• N=lW
• Let
• W=Meanwaitingtime
• N=Meannumberof customers in the queue
• 1/μ=Meanservicetime
• R=Meanresidual
service time
• We can prove that
• W=N*(1/μ)+R
Mean residual time R
Deriving the non-preemptive queue result (1)
High priority Low priority
Departures
• S1 – service time for Class 1 with mean E[S1]
• W1 = mean waiting time for Class 1 customers
• N1 = number of Class 1 customers in the queue
• R = mean residual service time when a customer arrives • WehaveforClass1:W1 =N1 E[S1]+R
• Little’s Law: N1 = l1 W1
where
T1,2021 COMP9334
12
Deriving the non-preemptive queue result (2)
High priority Low priority
Departures
• To find the residual service time R, note that the customer in the server can be a high or low priority customer, we have
• The waiting time is therefore
where
T1,2021 COMP9334 13
Deriving the non-preemptive queue result (3)
High priority Low priority
Departures
• S2 – service time for Class 2 with mean E[S2]
• W2 = mean waiting time for Class 2 customers
• N2 = number of Class 2 customers in the queue
• R = mean residual service time when a customer arrives
T1,2021 COMP9334 14
Deriving the non-preemptive queue result (4)
High priority Low priority
• For Class 2 customers:
Departures
Question:
Consider a customer arriving at the low priority queue, when can this customer receive service? This customer has to wait for
Average number of
• The customer at the server to finish customers that arrive in
Average number of customers already in
• The customers who are already in the low priority queue
Queues 1 and 2 when a
Queue 1 after a low priority customer arrives
when this customer arrives
Class 2 customer arrives
• ?????
• ?????
T1,2021 COMP9334 15
Deriving the non-preemptive queue result (5)
• Little’s Law to Queue 1: • Little’s Law to Queue 2:
• Combining all of the above
Where
T1,2021 COMP9334
16
Deriving the non-preemptive queue result (6)
High priority Low priority
Departures
where
T1,2021 COMP9334
17
Non-preemptive Priority with P classes Waiting time of priority class k
where
T1,2021 COMP9334 18
Example
• Router receives packet at 1.2 packets/ms (Poisson), only one outgoing link
• Assume 50% packet of priority1, 30% of priority 2 and 20% of priority 3. Mean and second moment given in the table below.
• What is the average waiting time per class?
• Solution to be discussed in class.
Priority
Mean (ms)
2nd Moment (ms2)
1
0.5
0.375
2
0.4
0.400
3
0.3
0.180
T1,2021 COMP9334 19
Pre-emptive resume priority (1)
• Can be derived using a similar method to that used for non- preemptive priority
• The key issue to note is that a job with priority k can be interrupted by a job of higher priority even when it is in the server
• For k = 1 (highest priority), the response time T1 is: where
T1,2021 COMP9334
20
A highest priority job only has to wait for the highest priority jobs in front of it.
Preemptive resume priority (2)
• Fork32,wehaveresponsetimeforajobinClassk:
Question:
Consider a customer arriving in priority class k (3 2), what are the
components of the waiting time for this customer?
An arriving job in Priority Class k needs to wait for all the jobs in Priority Classes 1 to k, that are already in the system when it
arrives, to complete.
An arriving job of priority k has to wait for all the jobs of higher priorities that arrive during the time that this job is waiting in the queue and in the server.
Note that Rk contains only terms of priority k or higher since a job with priority k cannot be interrupted by jobs with a lower
priority. In other words, a job with priority k does not see the residual service time of lower priority classes.
T1,2021 COMP9334 21
Preemptive resume priority (3)
• Solvingtheseequations,wehavethe response time of Class k jobs is:
where
T1,2021 COMP9334 22
Other queuing disciplines
• There are many other queueing disciplines, examples include
• Shortestprocessingtimefirst
• Shortestremainingprocessingtimefirst • Shortestexpectedprocessingtimefirst
• Optional: For an advanced exposition on queueing disciplines, see Kleinrock, “Queueing Systems Volume 2”, Chapter 3.
T1,2021 COMP9334 23
References
• Recommended reading
• BertsekasandGallager,“DataNetworks”
• Section 3.5.3 for priority queuing • Optional reading
• Harchol-Balter,Chapter22
T1,2021 COMP9334 24