CPU Scheduling Simulation

01 Lab overview

This lab contributes to U5.1 through U5.5, and to course learning outcomes CLO3, CLO5, and CLO8.

02 Learning objectives

03 Background

3.1 The scheduler's model

The simulator models the classical CPU scheduling problem. A process is a tuple (pid, arrival, burst, priority). The scheduler selects one process at a time to run on a single CPU. The scheduler's decisions are captured by the process's timeline: the intervals during which the process runs.

3.2 Metrics

Waiting time

The total time a process spends in the ready queue (i.e., ready but not running). Computed as turnaround − burst.

Turnaround time

The total time from a process's arrival to its completion. Computed as completion − arrival.

Response time

The time from a process's arrival to its first scheduling. For interactive workloads, this is more informative than the turnaround time.

Throughput

The number of processes completed per unit time.

CPU utilisation

The fraction of time the CPU is busy, total_burst / wall_clock_interval.

Fairness

Informally, the extent to which processes of the same priority receive comparable service. Quantified by the variance of the waiting times and by the maximum waiting time.

3.3 The algorithms

FCFS

First Come, First Served — non-preemptive; the process that arrived first runs to completion.

SJF

Shortest Job First — non-preemptive; the process with the shortest burst is selected next.

SRTF

Shortest Remaining Time First — preemptive SJF; the process with the shortest remaining burst is selected at every scheduling point.

Priority

Non-preemptive; the process with the highest priority runs to completion. In the simulation, lower numbers mean higher priority.

Round Robin

Preemptive; processes run in arrival order, each for at most one time quantum, then go to the back of the ready queue.

3.4 The workload file format

The simulator reads workloads from plain text files, one process per line:

# pid  arrival  burst  priority
1      0        7      3
2      2        4      1
3      4        1      2
4      5        4      4
          

Lines beginning with # are comments; blank lines are ignored.

04 Guided activities

Activity 4.1 — The skeleton and the FCFS scheduler

1. Create the lab directory and download the starter skeleton (or build it yourself following the specification below):

   mkdir -p ~/comp3150/lab4 && cd ~/comp3150/lab4

2. Implement the process structure and the workload reader. The structure should be:

   typedef struct {
       int   pid;
       int   arrival;
       int   burst;
       int   priority;
       int   remaining;      /* for preemptive algorithms */
       int   start;          /* first dispatch, -1 if not dispatched */
       int   completion;     /* -1 if not completed */
       int   waiting;        /* accumulated waiting time */
   } process_t;

3. Implement the FCFS scheduler. It selects, at each scheduling point, the arrived process with the smallest arrival time; ties are broken by PID.
4. Write the metric computation: for each process, compute the waiting time, the turnaround time, and the response time; then compute the averages and the CPU utilisation.
5. Test FCFS on the workload from § 3.4. Your output should include, for each process, the start time, the completion time, and the three metrics.

Activity 4.2 — SJF and SRTF

1. Implement SJF: at each scheduling point, select the arrived process with the smallest burst. Ties are broken by arrival, then by PID.
2. Implement SRTF: at every unit of time, check whether a newly arrived process has a smaller remaining burst than the running process; if so, preempt. Ties are broken by arrival, then by PID.
3. Run both on the workload from § 3.4. Compare the average waiting times. Which algorithm performs better on this workload, and why?

Activity 4.3 — Priority scheduling

1. Implement non-preemptive priority: at each scheduling point, select the arrived process with the smallest priority number. Ties are broken by arrival, then by PID.
2. Run it on the workload. What is the average waiting time?
3. Construct a workload in which a long, low-priority process arrives first and a stream of short, high-priority processes arrives after it. Observe the low-priority process's waiting time and discuss starvation.

Activity 4.4 — Round Robin and the time quantum

1. Implement Round Robin with a parameter q for the time quantum. At each quantum's expiry, the running process goes to the back of the ready queue; the next process in arrival order is dispatched.
2. Run it on the workload with q = 1, q = 2, q = 4, and q = 8. Record the average waiting time, the average turnaround time, and the average response time for each.
3. Plot the four metrics as functions of q. What happens as q grows? What happens as q approaches the largest burst? Explain the two limits.

Activity 4.5 — Comparing all algorithms on multiple workloads

1. Create four workload files:
   • workload-cpu-bound.txt — 10 processes, all with long bursts (50–200 ms).
   • workload-io-bound.txt — 10 processes, all with short bursts (1–10 ms).
   • workload-mixed.txt — 5 long bursts and 5 short bursts interleaved.
   • workload-interactive.txt — 10 processes, each with several short bursts and one long burst, mimicking an interactive session.
2. Run all five algorithms on all four workloads. Record the average metrics in a table.
3. For each workload, identify the algorithm that minimises the average waiting time and the algorithm that minimises the average response time. Are they the same? Explain.
4. Repeat with SRTF and Round Robin (with a small quantum such as 2) and confirm that SRTF is optimal for average waiting time (given the actual burst times) while Round Robin is comparable but not optimal.

05 Exercises

06 Deliverables

Submit a single archive named lab4-<lastname>-<studentnumber>.tar.gz containing:

• The simulator's C source (sched.c or a small set of files), with your name and student number at the top.
• The Makefile with a default target building the simulator and a clean target.
• The four workload files from Activity 4.5.
• metrics.txt — the complete metrics' table for all algorithms on all workloads, with the commands that produced it.
• plots/ — the plots from Activity 4.4 (Round Robin's metrics as functions of the quantum) and any additional plots you generate.
• report.md (or report.pdf) — the lab report described below.

Lab report

The report should be 4–6 pages (excluding code) and contain:

07 Grading rubric

Late submission penalty: 10% per day, up to a maximum of three days, after which the lab is accepted only with documented extenuating circumstances.

08 Knowledge check

09 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 5.
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 7–10.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2.
• Linux kernel documentation: CFS Scheduler (Documentation/scheduler/sched-design-CFS.rst).
• Linux man-pages: man 7 sched, man 2 sched_setscheduler, man 1 taskset, man 1 nice, man 1 chrt.