Events and queue order

What this concept is

A deterministic scheduler model needs rules for simultaneous events. A policy name alone leaves unanswered whether a new arrival joins before an expired slice is requeued. This lab orders arrivals by timestamp and input position, admits all arrivals through a slice endpoint, then requeues the unfinished job.

Why it matters here

Two plausible simulators can disagree while both conserve CPU service. The disagreement may be a different contract rather than arithmetic failure. State the contract first, then test it with a workload that distinguishes alternatives.

Concrete example

A arrives at 0 needing 4; B arrives at 2 needing 1; quantum is 2. A runs [0,2). B is admitted before A is requeued, so the queue is B,A. B runs [2,3), then A runs [3,5). Requeue-first semantics would delay B to time 4.

Common confusion / misconception

An arrival during a slice does not interrupt RR in this model. Preemption happens at the quantum boundary, unlike shortest-remaining-time scheduling. Simultaneous arrival order is input order, not alphabetical name order.

How to use it

Maintain an ordered pending list, a ready deque and remaining service per job. Record the ready queue just before dispatch. When it is empty, advance to the next arrival and emit an idle interval. An unfinished running job belongs outside the ready deque until its slice ends.

Check yourself

What happens if B arrives at 1 instead of 2? It still runs at 2 with quantum 2. What if B arrives at 3? A starts its second slice at 2, so B waits until 4. Name the event rule causing the difference.

Mini drill or application

Add C at the same arrival time as B and reverse their input order. Predict which response changes. Construct a test that fails a front-requeue mutant while still satisfying service conservation.

Read this only if stuck

Return to process states in OSTEP chapter 4, then label pending, ready and running separately in your own trace.