Preemptive Weighted Fair-queueing Algorithm

From this argument, we can see that an alternative is for the scheduler to give each server a finish number each time it replenishes the server budget. It then schedules eligible servers according to their finish numbers; the smaller the finish number, the higher the priority. If the scheduler were to use this alternative in our example, the finish numbers of the servers FQi , for i = 1, 2, 3, would be the numbers under the time lines of TBi , respectively, in Figure 7–14(a). At time 18, the system is in round 28.8, and it takes 8 rounds to complete each job in A4. Hence, at time 18, the scheduler sets the finish number of FQ4 to 36.8. At this time, the finish numbers of FQ1, FQ2 and FQ3 are 36, 40, 36, respectively. If we were construct a schedule according to these finish numbers, we would get the schedule in Figure 7–14(d).

Rules of Preemptive Weighted Fair-Queueing Algorithm. We are now ready to state the rules that define the WFQ algorithm. The scheduling and budget consumption rules of a WFQ server are esentially the same as those of a total bandwidth server.
Scheduling Rule: A WFQ server is ready for execution when it has budget and a finish time. The scheduler assigns priorities to readyWFQ servers based their finish numbers: the smaller the finish number, the higher the priority.
Consumption Rule: A WFQ server consumes its budget only when it executes. In addition to these rules, the weighted fair-queueing algorithm is defined by rules governing the update of the total size of backlogged servers and the finish number of the system and the replenishment of server budget. In the statement of these rules, we use the following notations:

• t denotes the current time, except now we measure this time from the start of the current system busy interval. (In other words, t is the length of time interval from the beginning of the current system busy interval to the current time.)
• f ni denotes the finish number of the server FQi , ei its budget, and ˜ ui its size. e denotes the execution time of the job at the head of the server queue.
• Ub denotes the total size of all backlogged servers at t, and F N denotes the finish number of system at time t . t−1 denotes the previous time when F N and Ub were updated.

Finally, the system contains n servers whose total size is no greater than one.

Initialization Rules
I1 For as long as all servers (and hence the system) are idle, F N = 0, Ub = 0, and t−1 = 0. The budget and finish numbers of every server are 0.
I2 When the first job with execution time e arrives at the queue of some server FQk and starts a busy interval of the system,
(a) t−1 = t , and increment Ub by ˜ uk, and
(b) set the budget ek of FQk to e and its finish number f nk to e/ ˜ uk .

Rules for Updating F N and Replenishing Budget of FQi during a System Busy Interval
R1 When a job arrives at the queue of FQi , if FQi was idle immediately prior to this arrival,
(a) increment system finish number F N by (t − t−1)/Ub,

(b) t−1 = t , and increment Ub by ˜ ui, and
(c) set budget ei of FQi to e and its finish number f ni to F N e/ ˜ ui and place the server in the ready server queue in order of nonincreasing finish numbers.

R2 Whenever FQi completes a job, remove the job from the queue of FQi ,
(a) if the server remains backlogged, set server budget ei to e and increment its finish number by e/ ˜ ui .
(b) if the server becomes idle, update Ub and F N as follows:

i. Increment the system finish number F N by (t − t−1)/Ub,

ii. t−1 = t and decrement Ub by ˜ ui .