Build a Round-Robin Task Scheduler

Topic Overview

Kernel Preemption Loop

The mini-kernel scheduler ties PIT ticks to a ready queue of tasks. On each tick, decrement quantum, preempt if zero, and call your assembly context switch.

Scheduler Invariants

Maintain:

• Current task pointer
• Ready ring of runnable tasks
• Idle task when queue empty

For example, three kernel tasks with quantum 5 ticks rotate in ABCABC order if all remain runnable.

Why This Matters in Production

Round-robin is exactly how early Unix and the original Linux scheduler shared the CPU before the O(1) scheduler and later Completely Fair Scheduler (CFS) replaced it with more sophisticated fairness models. Forgetting to reset a task's time slice before re-enqueuing it is a bug that lets one task monopolize the CPU forever while every other READY task starves in the queue.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will integrate timer IRQ, scheduling decisions, and switch_to. The task asks you to print each dispatch with task id and remaining quantum for debugging.

Your Task

Simulate a kernel's round-robin scheduler. Tasks arrive over time and wait in a FIFO ready queue. Each dispatch runs a task for at most one time quantum. A preempted task goes to the back of the queue, and a task that starts I/O blocks until the I/O completes. Print the timeline, the per-task metrics, and the averages.

Input

cCopy
Loading…

Rules

• At each scheduling point, first queue the tasks that have arrived (in input order), then the tasks whose I/O has finished (in input order), then the task that was just preempted. So newcomers go ahead of the preempted task.
• A slice runs for the smallest of: Q, the task's remaining burst, and the CPU time left until its I/O point. Time jumps by the slice length, and nothing is charged for switching.
• If the queue is empty and tasks are still pending, the CPU idles until the next arrival or I/O completion.
• Turnaround is finish minus arrival. Waiting is turnaround minus burst minus the I/O duration. Response is the first dispatch minus arrival.
• Averages are rounded half up to two decimals.
• A context switch is a dispatch of a different task than the last one that ran. Idle time in between does not reset this.
• Invalid input is rejected with a message and ignored:
  • quantum Q: must be at least 1
  • task NAME: rejected (negative arrival, burst below 1, or more than 16 tasks)
  • io NAME: rejected (unknown task, AFTER not in 1..burst-1, or DURATION below 1)
  • run: no tasks

Output

cCopy
Loading…

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Use a real FIFO ready queue of task indices. Do not scan the task list for "the next one".
2. Keep the per-task counters (remaining time, CPU used, first dispatch, finish), so that every metric comes from the simulation itself.

Hidden tests cover staggered arrivals that join ahead of a preempted task, I/O blocking and wake-ups, idle gaps before the first arrival, a quantum of 1, and rejected input.