Build Round-Robin Scheduler: Time-Slice Between N Processes

Topic Overview

Time Slicing as Fairness

Round-robin scheduling gives every ready process a fixed quantum before moving it to the back of the queue. No process monopolizes the CPU while others sit in the ready state. The policy is predictable: throughput is fine for interactive workloads, and starvation is impossible as long as the queue drains.

Mechanics You Will Code

Key pieces of a RR scheduler:

• Ready queue: FIFO of runnable PCBs
• Timer tick: decrement quantum; on zero, preempt and rotate
• Context switch: save/restore registers when swapping processes

For example, with quantum 10 ms and three processes A, B, C each needing 30 ms of CPU, the run order is A(10), B(10), C(10), A(10), B(10), C(10), A(10), B(10), C(10). Total completion is 90 ms of CPU time spread across nine slices.

Why This Matters in Production

Round-robin is the ancestor of every time-sharing scheduler still in production, from early Unix to Windows' quantum-based dispatcher, and picking the quantum wrong is a real tuning problem: too short and context-switch overhead dominates (as seen in early VAX/VMS tuning guides), too long and interactive shells feel laggy. This task's turnaround/waiting/response metrics are exactly what tools like perf sched report when engineers diagnose scheduler fairness.

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 build the ready queue, timer interrupt handler, and preemption path that rotates processes. Understanding slice boundaries matters because every real OS scheduler (Linux CFS still uses the same preemption idea) depends on correct quantum accounting.

Your Task

Round robin has one knob: the time quantum. A small quantum gives fast response but many context switches, and a large one degenerates into first-come-first-served. Build a round-robin simulator, then run the same workload under several quanta, with and without a context-switch cost, so you can see the trade-off in numbers.

Input

cCopy
Loading…

Rules

• Take the task at the head of the FIFO queue and run it for min(Q, remaining). If it has not finished, append it to the back of the queue.
• A context switch happens when the dispatched task is different from the one that ran last. The very first dispatch is not a switch. Each switch costs C time units in which no task runs, and this time counts in everything (waiting, turnaround, makespan).
• Turnaround is the finish time, waiting is finish minus burst, and response is the time of the first dispatch (all tasks arrive at 0).
• Averages are rounded half up to 2 decimals. Overhead is switches * C / makespan as a percentage, rounded half up to 1 decimal.
• Errors: task NAME: rejected (burst below 1, or more than 16 tasks), quantum Q: rejected (negative, skipped while the others still run), and compare: no tasks / trace: no tasks.

Output

cCopy
Loading…

Traces print one line per dispatch, plus a switch line for each context switch when C > 0.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Write one simulation function that takes the quantum, and call it for every value on the line. Reset all per-task state on each call.
2. Use integer arithmetic for the rounding, so the results match on every platform.

Hidden tests cover a nonzero switch cost across several quanta, a quantum of 1, a quantum larger than every burst (identical to FCFS), traces with and without switch cost, a single task (no switches at all), and rejected input.