Project 5: Process Scheduler Simulator

Simulate multiple scheduling policies and measure fairness, response time, and throughput.

Quick Reference

Attribute Value
Difficulty Intermediate
Time Estimate 10-16 hours
Main Programming Language C or Python
Alternative Programming Languages Rust, Go
Coolness Level High
Business Potential Medium (perf modeling)
Prerequisites Data structures, basic OS process model
Key Topics preemption, time slices, fairness metrics

1. Learning Objectives

By completing this project, you will:

  1. Implement FIFO, SJF, RR, and MLFQ/CFS scheduling.
  2. Compute response time, turnaround time, and wait time.
  3. Simulate I/O bursts and blocking behavior.
  4. Explain trade-offs between fairness and throughput.

2. All Theory Needed (Per-Concept Breakdown)

Scheduling Policies and Fairness Metrics

Fundamentals

A scheduler decides which runnable process gets the CPU next. Different policies optimize different goals: FIFO maximizes simplicity, SJF minimizes average turnaround time, Round Robin improves responsiveness, and MLFQ approximates fairness by moving interactive jobs to higher priorities. Metrics like response time, wait time, and turnaround time quantify these trade-offs. Preemptive scheduling uses timer interrupts to force context switches, while non-preemptive scheduling runs a task until it blocks or completes. Real systems combine multiple techniques to balance responsiveness and throughput.

Deep Dive into the concept

Schedulers operate on a timeline with events: arrivals, CPU bursts, I/O blocking, and completions. The system maintains a ready queue of runnable tasks. In FIFO, tasks run in arrival order and are never preempted. This is easy to implement but can be unfair: a long-running process can delay short tasks. SJF improves average turnaround by selecting the shortest remaining CPU burst, but it requires prediction and can starve long tasks. Round Robin assigns a time quantum to each task and cycles through the queue, improving responsiveness for interactive tasks.

MLFQ uses multiple queues with different priority levels and time quanta. New or interactive tasks start in high-priority queues with short quanta, while CPU-bound tasks are demoted to lower queues with longer quanta. Periodic priority boosts prevent starvation. This design approximates the behavior of many real OS schedulers. CFS (Completely Fair Scheduler) goes further by tracking virtual runtime and scheduling the task with the smallest runtime, approximating fair sharing of CPU time.

Metrics reveal trade-offs. Response time is the time from arrival to first execution, critical for interactive workloads. Turnaround time is the total time from arrival to completion, important for batch jobs. Wait time measures time spent in the ready queue. Throughput measures jobs completed per unit time. A scheduler that optimizes one metric often degrades another. Your simulator should compute all metrics and present them clearly.

Simulating I/O is essential. When a process performs I/O, it leaves the ready queue and enters a blocked state. After a fixed I/O time, it returns to the ready queue. This introduces realistic behavior: CPU-bound tasks will run longer, while I/O-bound tasks will return frequently. The scheduler must handle events that occur at the same time (e.g., quantum expiration and I/O completion) in a deterministic order to maintain repeatability.

How this fit on projects

This concept informs Section 3.2 (requirements), Section 4.4 (algorithms), and Section 6 (testing). It connects to Project 4 (VM) and Project 6 (process creation).

Definitions & key terms

  • Response time: time from arrival to first CPU run.
  • Turnaround time: time from arrival to completion.
  • Wait time: time spent in the ready queue.
  • Preemption: forced context switch after a time slice.
  • MLFQ: multi-level feedback queue scheduler.

Mental model diagram (ASCII)

Arrive -> Ready Queue -> CPU -> (I/O -> Blocked -> Ready)

How it works (step-by-step)

  1. Load processes with arrival and burst times.
  2. Add newly arrived processes to ready queue.
  3. Select next process based on policy.
  4. Run for quantum or until I/O/finish.
  5. Update metrics and advance time.

Minimal concrete example

P1: arrival 0, CPU 5
P2: arrival 0, CPU 2
FIFO: P1 runs 0-5, P2 runs 5-7

Common misconceptions

  • “SJF is always best”: it can starve long tasks.
  • “RR is unfair”: fairness depends on quantum choice.
  • “Metrics are interchangeable”: they measure different goals.

Check-your-understanding questions

  1. Why can SJF starve long-running jobs?
  2. How does MLFQ prevent starvation?
  3. What happens if the RR quantum is too large?

Check-your-understanding answers

  1. Short jobs keep arriving and are always chosen first.
  2. Periodic priority boosts move jobs back up.
  3. It degenerates toward FIFO behavior.

Real-world applications

  • OS scheduling in Linux, Windows, and mobile OSes.
  • Task scheduling in server runtimes.

Where you’ll apply it

References

  • “OSTEP” Ch. 7-9
  • “Linux Kernel Development” (scheduler overview)

Key insights

Schedulers are policy engines that trade fairness, responsiveness, and throughput.

Summary

By simulating multiple policies, you see why real kernels combine techniques to satisfy conflicting goals.

Homework/Exercises to practice the concept

  1. Implement SJF with estimated burst times.
  2. Add a priority boost every 100 ms.
  3. Compare RR with quantum 2 vs 20.

Solutions to the homework/exercises

  1. Use exponential averaging of previous bursts.
  2. Periodically move all tasks to top queue.
  3. Measure response time and fairness metrics.

3. Project Specification

3.1 What You Will Build

A scheduler simulator that accepts a workload file, runs FIFO/SJF/RR/MLFQ (or CFS), and outputs timelines and metrics.

3.2 Functional Requirements

  1. Parse workload with arrivals, CPU bursts, and I/O bursts.
  2. Implement FIFO, SJF, and RR.
  3. Implement MLFQ or CFS.
  4. Output metrics and timeline.

3.3 Non-Functional Requirements

  • Performance: handle 10k events quickly.
  • Reliability: deterministic output for same input.
  • Usability: clear CLI interface.

3.4 Example Usage / Output

$ ./schedsim workload.txt --algo=mlfq --quantum=10 --seed 42
Average response: 20ms
Average turnaround: 160ms

3.5 Data Formats / Schemas / Protocols

  • Workload file: CSV or simple text with arrival, CPU, I/O.

3.6 Edge Cases

  • Multiple arrivals at same timestamp.
  • Zero-length CPU burst.
  • I/O completion at same time as quantum end.

3.7 Real World Outcome

3.7.1 How to Run (Copy/Paste)

./schedsim workload.txt --algo=mlfq --seed 42

3.7.2 Golden Path Demo (Deterministic)

  • Use --seed 42 for any randomized tie-breaks.

3.7.3 If CLI: exact terminal transcript

$ ./schedsim workload.txt --algo=rr --quantum=2 --seed 42
Timeline:
0-2: P1
2-4: P2
4-6: P1
Results:
P1 turnaround=6 response=0 wait=1
P2 turnaround=4 response=2 wait=2

Failure demo (deterministic):

$ ./schedsim workload.txt --algo=rr --quantum=0
error: quantum must be > 0

Exit codes:

  • 0 success
  • 2 invalid arguments
  • 3 workload parse error

4. Solution Architecture

4.1 High-Level Design

Workload -> Event Queue -> Ready Queue -> Scheduler -> Metrics

4.2 Key Components

| Component | Responsibility | Key Decisions | |———–|—————-|—————| | Event queue | track arrivals and IO completions | priority queue | | Ready queue | runnable tasks | FIFO or multiple queues | | Scheduler | policy choice | RR/MLFQ/CFS | | Metrics | compute response/wait/turnaround | per-process tracking |

4.3 Data Structures (No Full Code)

struct proc {
    int pid;
    int arrival;
    int remaining_cpu;
    int response_time;
};

4.4 Algorithm Overview

Key Algorithm: MLFQ

  1. New tasks start at highest priority queue.
  2. Run for queue quantum.
  3. Demote if still runnable.
  4. Periodically boost priorities.

Complexity Analysis:

  • Time: O(log n) per event with heap
  • Space: O(n)

5. Implementation Guide

5.1 Development Environment Setup

sudo apt-get install build-essential

5.2 Project Structure

project-root/
|-- schedsim.c
|-- workload.txt
|-- Makefile
`-- README.md

5.3 The Core Question You’re Answering

“How should an OS choose who runs next so that the system is fair and responsive?”

5.4 Concepts You Must Understand First

  1. Preemption and time quanta.
  2. Scheduling metrics.
  3. I/O blocking and wakeups.

5.5 Questions to Guide Your Design

  1. How will you break ties deterministically?
  2. How will you model context switch overhead?
  3. What is your fairness definition?

5.6 Thinking Exercise

Compute metrics for P1(5), P2(2), P3(8) under FIFO, SJF, RR(q=2).

5.7 The Interview Questions They’ll Ask

  1. Why does MLFQ use multiple queues?
  2. What is the trade-off between responsiveness and throughput?

5.8 Hints in Layers

Hint 1: Start with FIFO and timeline output.

Hint 2: Add RR with a fixed quantum.

Hint 3: Add MLFQ priority queues.

5.9 Books That Will Help

| Topic | Book | Chapter | |——-|——|———| | Scheduling | OSTEP | 7-9 | | Linux scheduler | Linux Kernel Development | 4 |

5.10 Implementation Phases

Phase 1: FIFO and metrics (3-4 hours)

Goals: basic timeline and metrics.

Phase 2: RR and SJF (4-5 hours)

Goals: add preemption and SJF.

Phase 3: MLFQ/CFS (4-6 hours)

Goals: advanced policy and fairness analysis.

5.11 Key Implementation Decisions

| Decision | Options | Recommendation | Rationale | |———-|———|—————-|———–| | Event ordering | IO before quantum vs after | document and fix | determinism | | Quantum size | 2-10 ms | configurable | compare policies |

6. Testing Strategy

6.1 Test Categories

| Category | Purpose | Examples | |———-|———|———-| | Unit | metric calculations | small known workload | | Integration | full run | compare with manual results | | Stress | many events | 10k processes |

6.2 Critical Test Cases

  1. Two jobs arriving at same time.
  2. I/O completion coincides with quantum end.
  3. Burst length smaller than quantum.

6.3 Test Data

P1 0 5
P2 0 2
P3 3 4

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

| Pitfall | Symptom | Solution | |——–|———|———-| | Response time negative | wrong initialization | record first run only once | | Stuck in blocked state | IO completion not handled | requeue correctly | | Non-determinism | unordered events | stable sorting |

7.2 Debugging Strategies

  • Print timeline step-by-step for tiny workloads.
  • Add assertions for monotonic time.

7.3 Performance Traps

  • O(n) scans of queues at each event.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add Gantt-chart ASCII output.

8.2 Intermediate Extensions

  • Implement CFS with red-black tree.

8.3 Advanced Extensions

  • Simulate multi-core scheduling.

9. Real-World Connections

9.1 Industry Applications

  • OS scheduling and JVM runtime scheduling.
  • Linux CFS source for reference.

9.3 Interview Relevance

  • Scheduling fairness and starvation discussions.

10. Resources

10.1 Essential Reading

  • OSTEP Ch. 7-9

10.2 Video Resources

  • OS scheduling lectures

10.3 Tools & Documentation

  • none

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain response vs turnaround time.
  • I can describe fairness trade-offs.

11.2 Implementation

  • Simulator outputs correct metrics.

11.3 Growth

  • I can discuss scheduler trade-offs in interviews.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • FIFO, RR implemented with metrics.

Full Completion:

  • MLFQ/CFS added and compared.

Excellence (Going Above & Beyond):

  • Multi-core simulation.