Skip to main content

Events and queue order

This generated surface maps a learner-facing curriculum unit to its canonical source routes.

Curriculum surface​

  • Open learner-facing unit
  • Curriculum path: content/curriculum/systems/semester-05-os-networking/module-01-processes-scheduling/concepts/cluster-06-executable-scheduling-contracts/16-event-order.md
  • App: systems
  • Semester: semester-05-os-networking
  • Module: module-01-processes-scheduling
  • Unit kind: concept
  • Curation level: module_curated

Learning objectives​

  • Trace Events and queue order using the language of processes, scheduling policy, and kernel-visible state.
  • Compare the abstraction in the learner page against concrete scheduler behavior you can observe or reason about on a real system.
  • Use ostep to connect the learner explanation to metrics, tradeoffs, and debugging evidence.

Prerequisites​

  • Comfort reasoning about CPU, memory, and the kernel/user boundary from earlier systems work.

Source books​

  • ostep

Source routes​

Ostep​

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, 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`

Supporting curriculum routes​

No supporting curriculum routes linked yet.

External enrichment​

  • man 7 sched (official_docs_companion) - Anchors scheduler concepts in the actual Linux process scheduling interface and policy vocabulary.
  • Linux Kernel Documentation: Scheduler (optional_deep_dive) - Useful after the learner has the concept page, when they want to see how theory lands in kernel design.

AI companion modes​

  • Explain simply
  • Socratic tutor
  • Quiz me
  • Diagnose my confusion
  • Generate extra practice

Source-of-truth note​

This teaching unit is learner-facing guidance. Its canonical source backbone is the referenced book ostep, and outside material should only clarify or strengthen that backbone.