A2. Scheduler simulator

basicbuilds on module 7

Goal

Module 7 walks through FCFS, SJF, Round Robin, and MLFQ on a single example of three jobs. The simulator turns them into numbers for any set of jobs: SJF really does give the lowest average waiting time, the long job that waits until last pays for it, and no algorithm wins on every metric.

After this lab you will be able to:

compute, for any set of jobs, the average waiting time, turnaround time, and response time, and explain how they differ;
show the convoy effect in FCFS and starvation in SJF with your own numbers;
explain how the time quantum size in Round Robin affects response time and the number of switches, and why a large quantum degenerates it into FCFS;
explain why MLFQ needs aging and what happens without it.

You’ll run into these metrics every time you need to explain why an interactive program lags under background load, whether in Linux or in a thread pool.

Task

Write a program sched that reads a job description from a file and prints average metrics for each scheduling algorithm.

./sched workload.txt

The input is a text file with one line per job: name, arrival time, burst length, priority. Lines starting with # are skipped.

# name arrival burst priority
A 0 24 2
B 0 3 1
C 0 3 1

The output has one line per algorithm: the first word is the algorithm name, followed by three metrics with two decimal places, all averaged over jobs:

algorithm         waiting  turnaround  response
FCFS                 17.00   27.00   17.00
SJF                   3.00   13.00    3.00
RR(q=4)               5.67   15.67    3.67
MLFQ                  ...

What it must do:

FCFS and SJF, both non-preemptive.
SRTF, the preemptive variant of SJF.
Round Robin with a time quantum passed as an argument. Without the argument the quantum is 4: the automated check runs the program without it.
MLFQ with several queues and a periodic boost of all jobs to the top. For it, the job format is extended with a description like “runs X, then waits Y”.
CPU idle time: if no job has arrived yet, time keeps moving.
The degenerate case with a single job.

What you don’t need to do. The required algorithms don’t use the priority from the fourth column: you only need to read it. The cost of a context switch is not modeled: in module 7 and in the check it takes no time.

Constraints. Any language: the script runs ./sched and reads only the output.

What to write in the report:

the metrics for the example from module 7 and whether they match 17.00, 3.00, and 5.67;
a “quantum → average response time, number of switches” table for RR;
the metrics of all algorithms on the three sets from the “Comparison” stage;
a conclusion: which algorithm won on which set and by which metric.

Done when:

./check.sh ./sched passes all thirteen checks on four sets;
SRTF and MLFQ, which the check doesn’t touch, print lines in the same table; on the example from the module, SRTF matches SJF, because all jobs arrive at time zero;
the report has the comparison table and the conclusion.

Before you start

Read the sections “What we optimize”, “Classic algorithms”, and “Multilevel feedback queues” in module 7.
Unpack the course archive: the check is in labs/a2-scheduler/check.sh, and it creates the job sets itself.
Any Linux will do, including a container and WSL2. All you need from the system is a compiler or interpreter for your language.

Stages

Reading the description and checking against the module example.

The set A 0 24, B 0 3, C 0 3 is worked through in module 7: FCFS gives 17.00, SJF gives 3.00, RR with a quantum of 4 gives 5.67. If your numbers match, your parsing and metrics are correct.
FCFS and SJF.

Both are non-preemptive: the chosen process runs to completion. The only difference is the rule for choosing among those that have already arrived.
SRTF, the preemptive variant of SJF.

Now the arrival of a new short job must preempt the current one. This is the first algorithm where you have to process events in time rather than just sort a list.
Round Robin with a quantum parameter.

The quantum is passed as an argument. Be sure to plot “quantum → average response time” and “quantum → number of switches”: they show the tradeoff the module talks about.
MLFQ.

Several queues: a new process goes into the highest one, one that used up its quantum moves down, one that blocked earlier stays where it is. Plus a periodic boost of everyone to the top, so long jobs don’t starve.

For MLFQ to make sense, jobs need I/O behavior: add a “runs X, then waits Y” description to the format.
Comparison.

Run all algorithms on three different sets: compute-bound jobs only, interactive only, and a mix. Write down your conclusion.

Automated check

The check is in the archive with the course files, and the commands below are run from the unpacked directory.

cd labs/a2-scheduler
./check.sh ./sched

The check runs four sets with precomputed answers, thirteen checks in total, including the example from module 7 and a case where FCFS shows the convoy effect.

Common mistakes

Idle time isn’t accounted for. If at some point no job has arrived yet, the CPU sits idle, but time still passes. Simulators that just take the next job from the list get the turnaround wrong here.

RR puts the preempted job at the wrong end of the queue. The preempted job goes to the end, and if a new one arrived at the same instant, you have to fix the order between them and document it. Different textbooks settle this differently, so what matters is that your choice is consistent.

Response time gets confused with waiting time. For non-preemptive algorithms they coincide, for RR they don’t. If yours are equal everywhere, there’s a bug somewhere.

MLFQ without aging. Without the periodic boost, long jobs never get the CPU, and that’s starvation.

Further, if you’re curious

Add SCHED_FIFO and SCHED_RR as separate classes with absolute priority over everything else, and see how a real-time job stalls all the others.