Job Scheduling With a Queue

Measured, by running the same four jobs in a different order:

from collections import deque


def fcfs_average_wait(jobs):
    ready = deque(sorted(jobs, key=lambda j: j[1]))
    clock, waits = 0, []
    while ready:
        name, arrival, burst = ready.popleft()
        start = max(clock, arrival)
        waits.append(start - arrival)
        clock = start + burst
    return sum(waits) / len(waits)


long_first = [("P1", 0, 8), ("P2", 1, 2), ("P3", 2, 3), ("P4", 3, 1)]
short_first = [("P1", 0, 1), ("P2", 1, 2), ("P3", 2, 3), ("P4", 3, 8)]

print("the SAME four burst times, arriving in two different orders")
print()
print("longest first : average waiting time %.2f" % fcfs_average_wait(long_first))
print("shortest first: average waiting time %.2f" % fcfs_average_wait(short_first))
print()
print("identical work, identical policy, and the average wait differs")
print("entirely because of the order the jobs happened to arrive in.")

the SAME four burst times, arriving in two different orders

longest first : average waiting time 6.25
shortest first: average waiting time 1.00

identical work, identical policy, and the average wait differs
entirely because of the order the jobs happened to arrive in.

The same four jobs, the same total work, the same policy. The average wait is more than six times worse in one case, decided by nothing but arrival order.

What the queue cannot do about it

The obvious improvement is to serve the shortest job first. That would give the best possible average waiting time, and it is a standard result.

A queue cannot do it. Chapter 46 gave the reason: a queue knows only the order in which items arrived. To serve the shortest job first, the structure would have to be able to find the smallest burst time among everything waiting, and a queue has no way to look at anything but its front.

So the structure has to change, and what is needed is:

• add a job with a priority, in this case its burst time
• remove the job with the best priority, not the oldest

That is the priority queue, its ADT is chapter 79, and the structure that makes both operations cheap is the heap of chapter 81.

Where Module 1 ends

Module 1 has built five structures and each one answered a limitation of the one before it.

And Module 1 ends with a limitation of its own that none of them can answer: none of these structures can find anything. Not the most urgent job, not a particular value, not the largest item, without looking at everything.

That is what Module 2 is about, from its first chapter to its last.

Quick revision

• Jobs waiting for the processor sit in a queue; serving them in arrival order is first come first

served.

• Turnaround time is completion minus arrival; waiting time is turnaround minus burst.
• A scheduler is judged on the average waiting time.
• The convoy effect: one long job at the front delays every short job behind it. Measured here, the same

four jobs gave average waits of 6.25 and 1.00 depending only on arrival order.

• Serving the shortest job first would be better, and a queue cannot do it, because it knows only

arrival order.

• That needs a structure that removes by priority rather than by age: the priority queue of chapter 78,

built on the heap of chapter 81.

Test yourself

1. Define turnaround time and waiting time. Turnaround is completion time minus arrival time, the total time in the system. Waiting is turnaround minus burst time, the time spent not running.

2. For a job arriving at 3 with a burst of 2 that starts at 16, give all three figures. Completion 18, turnaround 15, waiting 13.

3. What is the convoy effect? One long job at the front of the queue delaying every short job behind it, however small those jobs are.

4. The same four jobs were run in two arrival orders. What were the average waits, and what does that show? 6.25 with the longest first and 1.00 with the shortest first. The policy and the total work were identical, so the difference came entirely from arrival order, which is what first come first served is at the mercy of.

5. Why can a queue not serve the shortest job first? Because a queue knows only the order of arrival and can see only its front. Finding the smallest burst time requires looking at everything waiting, which is not a queue operation.

6. What limitation does Module 1 end on, and where is it answered? None of its structures can find anything without looking at everything: not the most urgent item, not a particular value, not the largest. Module 2 answers it, beginning with the tree.