In a shared print spooler, what does round-robin across per-user queues change versus one first-in-first-out queue?
answer
- Fair to jobs is not fair to people
- Who sets the wait for a small job
- One hundred documents ahead of one page
- Rotation trades ordering for bounded waiting
- Turn size decides whether one job still hogs
basics
~20 sA single first-in-first-out queue is fair to jobs, not to people: one user's five-hundred-page batch delays everyone behind it. Round-robin over per-user queues makes a job's wait depend on how many users are active, not on one user's backlog.
solid answer
~50 sOne shared queue guarantees arrival order and starves nobody — every job eventually reaches the front — but the wait for any job is the total work queued ahead of it, so a single user who submits a hundred documents at nine o'clock owns the printer until noon. Round-robin keeps a queue per user and serves one job from each in rotation, so a job's wait scales with the number of *active users* rather than with the largest backlog. The price is that global arrival order is gone: a job submitted later can print earlier because its owner's queue was idle. That is not a defect, it is the trade — you give up the ordering guarantee to bound each user's wait. Whether that is right depends on whether the guarantee people care about is 'in the order sent' or 'my small job soon'.
go deeper
Recall that a single shared queue serves strictly in arrival order, so a small job submitted just behind a huge batch waits for the whole batch. That is the concrete complaint any rotation policy exists to answer.
Explain what each policy makes a job's wait depend on: total queued work under one shared queue, versus the number of active participants under rotation. Name the price — global arrival order across users is gone.
Distinguish starvation from unbounded waiting rather than blurring them, and raise turn granularity: rotating per job still lets one enormous job hold the device, and shrinking the turn requires interrupting and resuming work.
Own the question of which guarantee the organisation is actually promising — 'in the order sent' or 'a small request is served promptly' — and whether the per-participant bookkeeping and the loss of a global order are worth what the complaint costs today.
## Two different things called fairness The misconception this question aims at is *"first-in-first-out is the fair policy"*. It is fair — to **jobs**. Every job is served in arrival order, and nothing is ever passed over, so no job starves. What it does not do is treat *users* equally, and in a shared office spooler users, not jobs, are the parties who feel the wait. Make the asymmetry concrete. Eight people share a printer. At nine o'clock one of them sends a hundred documents; at one minute past, six others each send a single page. Under one shared queue, those six single-page jobs sit behind a hundred documents and wait for the entire batch. Each of the six submitted a trivial amount of work and waits an amount of time set entirely by somebody else's submission. Arrival order was honoured perfectly, and the outcome is still one everybody in the room recognises as unfair. ## What rotation changes Round-robin keeps a separate queue per user and cycles: one job from the first user's queue, one from the second's, and so on, skipping users with nothing pending. In the scenario above, the batch submitter's first document prints, then each of the six single-pagers prints, and only then does the batch's second document begin. The six waited behind seven jobs instead of a hundred. The shift is in what a job's wait depends on: | Policy | A job's wait is set by | Order guarantee | | --- | --- | --- | | Single shared queue | Total work already queued, whoever queued it | Global arrival order | | Round-robin per user | Number of currently active users, times the per-turn work | Order within a user only | Round-robin's guarantee is per-user and *local*: your job's wait grows with how many colleagues are printing, not with how much any one of them printed. Ten light users are now a worse neighbour than one heavy user — which is exactly the intended inversion. ## What you give up, precisely **Global ordering disappears.** A job submitted at 9:05 can print before one submitted at 9:00, because its owner's queue was empty when the rotation came round. Anything that assumed sequence — a numbered report split across submissions, a cover page sent separately — breaks. Order *within* one user is untouched, which is usually the guarantee that actually mattered, but it must be stated rather than assumed. **Total time for a large batch gets worse.** The heavy user's hundred documents now finish later than under a shared queue, because every rotation hands turns to others. Round-robin does not create throughput; it redistributes waiting, and the heavy user pays for the light users' improvement. **Granularity is a real parameter.** Rotating per *job* still lets one enormous document hold the device for its whole duration; a five-hundred-page job is one turn. If that matters, the turn must be a page or a time slice rather than a job — which requires the ability to interrupt and resume, and that is a much larger commitment than maintaining several queues. ## The claim to correct carefully Saying *"round-robin prevents the starvation that a shared queue causes"* is wrong on both halves. A single first-in-first-out queue does not starve anyone: every job advances one position for each job served, so with finitely many arrivals ahead of it, every job is eventually served. And round-robin's benefit is not the removal of starvation but the **bounding of wait as a function of the right variable**. Keep those separate — an interviewer listening for the distinction hears immediately whether you have thought about it or memorised a slogan. ## When each is right A single shared queue is correct whenever arrival order is itself the promised guarantee — a chronological log, a sequence of operations whose result depends on their order, anything where reordering changes meaning. It is also simply cheaper: one structure, no per-user bookkeeping, no decision about what to do with a user who has been idle for an hour. Rotation is correct when the parties are independent, when their submissions vary wildly in size, and when the perceived quality of the service is a small job's wait rather than the sequence of jobs overall. A shared office printer is nearly the canonical case: submissions are unrelated to each other, sizes differ by two orders of magnitude, and the complaint you are trying to prevent is always *"I waited forty minutes for one page."* ## The sentence to land First-in-first-out is an *ordering* guarantee, and people mistake it for a *fairness* guarantee. Rotation is the opposite trade: it abandons global order to make each participant's wait depend on how many participants there are rather than on how much the loudest one asked for.
- Does a single shared queue ever starve a job?No. Every job served moves each waiting job one place closer to the front, so with a finite number of jobs ahead, every job is eventually served. Its weakness is that the waiting time is unbounded in the size of what was submitted before it, which people experience as unfairness — but starvation and unbounded waiting are different claims, and conflating them is a common slip.
- Under round-robin, can one enormous single job still monopolise the printer?Yes, if the rotation's turn is one whole job. A five-hundred-page document is a single turn and holds the device until it finishes. Bounding that needs a smaller turn — a page or a fixed time slice — which in turn requires the ability to pause a job and resume it later, a much bigger commitment than keeping one queue per user.
- What guarantee does round-robin still provide about a single user's own jobs?Their relative order. Each user's own queue is still first-in-first-out, so that user's jobs print in the order they were submitted, however the rotation interleaves other users between them. Only the global ordering across users is given up, which is usually the acceptable half of the trade.
A single queue is one supermarket till taking customers in order; round-robin is a server visiting each table in turn, so a party ordering the whole menu no longer blocks the table that wants coffee.
saying these in an interview costs you the question
- Calls first-in-first-out fair without asking fair to whom
- Claims a single shared queue starves small jobs
- Thinks rotation increases total throughput
- Misses that global arrival order is abandoned
- Assumes per-job turns bound one huge job's hold