Skip to content
Tutorials Center
My learning

Topics

Lesson 61 of 66 ยท Projects and Practice

Project: Build a CPU Scheduler Simulator

Build a tick-based CPU scheduling simulator in Python that runs FCFS, SJF, SRTF, round robin and priority scheduling, draws Gantt charts and compares waiting, turnaround and response time.

Reading about scheduling algorithms is one thing. Being able to predict, within a minute, how each of them treats a set of processes is another. In this project you build a small CPU scheduler simulator that you can reuse for homework and exam practice, and that shows exactly why no policy wins on every metric.

You will end up with one function, simulate(processes, policy), that returns a Gantt chart (who ran in each time unit) and the three standard metrics for each policy:

  • Turnaround time = finish time - arrival time.
  • Waiting time = turnaround time - burst time (time spent in the ready queue).
  • Response time = first time on the CPU - arrival time.

The theory is in the CPU scheduling chapter. Here we turn it into code.

Step 1: model and a first policy

A process has a name, an arrival time, a CPU burst and (later) a priority. Start with the simplest policy, FCFS, written directly, with a Gantt printer.

Python Step 1: processes, FCFS and a Gantt chart

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

FCFS is easy but the short job B waits behind the long job A. That is the convoy effect.

Step 2: one engine for every policy

Instead of one function per algorithm, write a tick-based engine that advances time one unit at a time and, whenever the CPU needs a decision, calls the policy to pick from the ready queue. Policies differ in two things only:

  1. Which ready process to pick (first arrived, shortest, highest priority).
  2. When to reconsider (never = non-preemptive; every tick = preemptive; after a quantum = round robin).
flowchart TD
    T["Tick t"] --> A["Move arrivals into the ready queue"]
    A --> P{"Need a decision?<br/>(CPU idle, preempt, quantum over)"}
    P -->|"yes"| S["Policy picks next process"]
    P -->|"no"| R["Keep running current"]
    S --> R
    R --> E["Run 1 tick, record in Gantt"]
    E --> F{"Finished?"}
    F -->|"yes"| X["Record finish time"]
    F -->|"no"| T
    X --> T

The same loop serves all policies; only the pick rule and the reconsideration rule change.

Python Step 2: the engine and five policies

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Study the table you just produced:

  • SRTF (shortest remaining time first) gives the lowest average waiting time, which is provably optimal for that metric, but it needs to know burst lengths in advance and can starve long jobs.
  • SJF is close behind and never preempts.
  • RR has the best (lowest) response time, because everyone gets the CPU within a few ticks, but a higher waiting time because jobs are interleaved.
  • PRIORITY is only as good as the priorities you choose: here the long job C has top priority and delays the others.

Step 3: how big should the quantum be?

Round robin hides a tuning problem. A tiny quantum means fast response but many context switches (each costs real time). A huge quantum turns RR into FCFS. The experiment below counts context switches and prints metrics for several quantum values.

Python Step 3: choosing the round-robin quantum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

As the quantum grows, switches and overhead shrink but the response time worsens; with q = 20 RR behaves exactly like FCFS. A common rule of thumb is to choose a quantum that is longer than most CPU bursts (so about 80% of bursts finish within one quantum), typically 10-100 ms in real systems.

Extensions to try

  1. Aging. Add priority -= 1 for every 5 ticks a process spends waiting, and show that starvation disappears.
  2. Multilevel feedback queue. Three queues with quanta 2, 4 and FCFS; a process that uses its whole quantum drops a level.
  3. Context-switch cost. Insert idle ticks whenever the running process changes.
  4. Random workloads. Generate 50 processes with a seeded RNG and compare the policies' averages, as a real study would.
  5. Multiple CPUs. Keep a list of running processes, one per core, and add an affinity rule.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How is waiting time computed from the finish time?

    Turnaround is finish - arrival, and the part of it not spent on the CPU is waiting, so waiting = finish - arrival - burst.
  2. 2. Which policy gives the minimum average waiting time for a known set of jobs?

    Running the job with the least remaining work first minimizes average waiting time, but it requires knowing burst lengths and can starve long jobs.
  3. 3. What happens to round robin as the quantum becomes very large?

    If no process ever uses up its quantum, nobody is preempted, so processes run in arrival order.
  4. 4. Why does a very small quantum hurt throughput?

    Each switch costs time spent saving and restoring state, so frequent switching wastes CPU cycles.

Summary

  • A tick-based engine with a pluggable pick rule and a preemption rule simulates every classic CPU scheduling policy.
  • Turnaround, waiting and response time give different rankings: SRTF wins waiting, RR wins response, and FCFS suffers the convoy effect.
  • Round-robin quantum trades response time against context-switch overhead.
  • Extend the simulator with aging, multilevel feedback queues and switching costs to explore further.

Next: Project: Page Replacement Lab