CPU Scheduling Simulation

Author: Seeyeon (Stephanie) Oh Course: CS 520 Operating Systems

Project Overview

This project implements a comprehensive discrete event simulation of a CPU scheduling system with Ready Queue, I/O Queue, CPU, and I/O Channel components. The simulation supports multiple scheduling algorithms and provides detailed performance analysis.

System Architecture

The simulation models the system shown in Figure 1 where:

• Processes arrive and enter the Ready Queue
• The CPU executes one process at a time
• Processes request I/O and enter the I/O Queue
• The I/O Channel handles one request at a time (65ms service time)
• Processes alternate between CPU bursts and I/O operations until completion

Core Implementation

• Process.java - Process Control Block implementation with exponential burst generation
• Event.java - Discrete event system with priority queue (heap) support
• CPUSchedulingSimulator.java - Main simulation engine supporting FCFS, SJF, and Round Robin
• SchedulingExperiments.java - Experiment runner with automated data collection

Documentation

• Report.pdf - Project report with analysis
• README.md - This file

Demo and Testing

• SimpleDemo.java - Basic demonstration of simulation concepts

Compilation and Execution

Prerequisites

• JDK 8 or higher
• Standard Java libraries

Compilation

javac *.java

Running the Simulation

# Run basic demonstration
java SimpleDemo

# Run complete experiments (generates log files)
java SchedulingExperiments

Scheduling Algorithms

1. First Come First Served (FCFS)

• Non preemptive scheduling
• Processes executed in arrival order
• Simple but may suffer from convoy effect

2. Shortest Job First (SJF)

• Non preemptive scheduling
• Selects process with shortest CPU burst
• Optimal for minimizing average waiting time
• Uses actual burst times (not predictions)

3. Round Robin (RR)

• Preemptive scheduling with time quantum
• Provides fairness and good response time
• Context switching overhead considered

Round Robin Analysis

Theory: Quantum Size Effects

Waiting time INCREASES with decreasing quantum when:

• High variability in CPU burst times (factor ≥2 difference)
• Mix of very short and very long processes
• Context switching overhead dominates fairness benefits

Waiting time DECREASES with decreasing quantum when:

• Similar CPU burst times across processes
• Better fairness outweighs context switching costs
• Interactive/time sensitive workloads

Experimental Design

Experiment 1: High Burst Variability

• Purpose: Demonstrate increasing wait time with decreasing quantum
• Configuration: 18 processes, inter I/O intervals 10ms-260ms (26x factor)
• Quantum values: 100ms, 50ms, 25ms, 10ms, 5ms
• Expected result: Wait time increases as quantum decreases

Experiment 2: Similar Burst Times

• Purpose: Demonstrate decreasing wait time with decreasing quantum
• Configuration: 16 processes, inter I/O intervals 45ms-75ms (1.67x factor)
• Quantum values: 80ms, 40ms, 20ms, 10ms, 5ms
• Expected result: Wait time decreases as quantum decreases

Output Files

When you run SchedulingExperiments, the following files are generated:

Basic Algorithm Comparison

• fcfs_vs_sjf_results.log - Detailed analysis and comparison
• fcfs_vs_sjf_results.csv - Raw data in CSV format

Round Robin Experiments

• rr_experiment1_high_variability.log - High variability experiment log
• rr_experiment1_results.csv - High variability data
• rr_experiment2_similar_bursts.log - Similar bursts experiment log
• rr_experiment2_results.csv - Similar bursts data

Performance Metrics

The simulation collects the following statistics:

• CPU Utilization: Percentage of time CPU is busy
• I/O Utilization: Percentage of time I/O channel is busy
• Throughput: Processes completed per second
• Average Turnaround Time: Mean time from arrival to completion
• Average Waiting Time: Mean time spent in ready queue

Key Implementation Features

Event Driven Simulation

• Priority queue (min heap) for event scheduling
• Event types: arrival, CPU completion, I/O request/completion, time slice expiry
• Precise timing with discrete event processing

Statistical Accuracy

• Exponential random number generation for CPU bursts
• Precise waiting time tracking with timestamp management
• Multiple trial runs for statistical significance

Modular Design

• Separate classes for processes, events, and scheduling algorithms
• Easy extension for additional scheduling policies
• Clean separation of simulation logic and experiment management

Expected Results

Based on theoretical analysis:

1. SJF vs FCFS: SJF should show significantly lower average waiting time
2. Round Robin Quantum Effects:
   • Experiment 1: Wait time increases with smaller quantum (overhead dominates)
   • Experiment 2: Wait time decreases with smaller quantum (fairness dominates)
3. CPU Utilization: Should remain relatively consistent across algorithms