Card 04/ 09
Queue Example: Serving Print Jobs in Arrival Order
Jobs that arrive first are printed first, whatever their size.
A queue fits any problem in which items should be handled in the order they arrived, and a shared printer is the most familiar such problem. This card covers four print jobs served from a queue, and the same four served from a stack, to show what the wrong order does.
A printer prints one page a minute. Job A, four pages long, arrives at minute 0 and starts at once. While it prints, B (one page) arrives at minute 1, C (two pages) at minute 2 and D (one page) at minute 3, and each waits. When A finishes at minute 4, the printer takes the next waiting job: from the front of a queue, or from the top of a stack.
Before the table: if the waiting jobs sit on a stack, which one waits longest?
B, the first of the three to arrive. It is printed last, at minute 8, seven minutes after it arrived.
A run of both orders recorded when each job was printed and its turnaround, the minutes from arriving to finishing:
| Job | Arrives at minute | Pages | Printed by a queue | Printed by a stack |
|---|---|---|---|---|
| A | 0 | 4 | 1st, done at 4, turnaround 4 | 1st, done at 4, turnaround 4 |
| B | 1 | 1 | 2nd, done at 5, turnaround 4 | 4th, done at 8, turnaround 7 |
| C | 2 | 2 | 3rd, done at 7, turnaround 5 | 3rd, done at 7, turnaround 5 |
| D | 3 | 1 | 4th, done at 8, turnaround 5 | 2nd, done at 5, turnaround 2 |
Both orders finish at minute 8 and average a turnaround of 4.5 minutes, because the total work is the same, but they differ in who waits. The queue keeps every turnaround at 4 or 5 minutes, while the stack lets D jump ahead and leaves B, which arrived first, waiting seven. With jobs arriving all day, a stack could hold an early job back for as long as newer ones keep coming, which is called starvation. The size of a job never decides its place in a queue: C's two pages print before D's one, because C arrived first.
The cue is "first come, first served". Requests reaching a web server, keystrokes waiting for a program to read them and messages passed between programs all share it, and each is a queue.
← → move through sections and cards