CPU Scheduling Algorithms - Comprehensive Analysis Problem
Problem Statement
You are a system administrator analyzing the performance of different CPU scheduling
algorithms for a multi-user system. A set of processes has arrived at the system, and you need to
analyze how different scheduling algorithms would handle these processes.
Given Process Information
Process ID Arrival Time Burst Time Priority I/O Burst Time I/O Start Time
P1 0 8 3 2 4
P2 1 4 1 1 2
P3 2 9 4 3 5
P4 3 5 2 1 3
P5 4 3 5 - -
Additional Information:
Time Quantum = 3 units (for Round Robin)
Context Switch Time = 1 unit (consider this in your calculations)
Priority: Lower number = Higher priority
I/O operations are performed after the specified time from process start
After I/O completion, process returns to ready queue
Your Tasks
Part A: Non-Preemptive Scheduling Algorithms
1. First-Come, First-Served (FCFS)
Create a Gantt chart showing process execution timeline
Calculate completion time, turnaround time, and waiting time for each process
Calculate average turnaround time and average waiting time
Identify any convoy effect issues
2. Shortest Job First (SJF) - Non-Preemptive
Create a Gantt chart
Calculate completion time, turnaround time, and waiting time for each process
Calculate average turnaround time and average waiting time
Compare efficiency with FCFS
3. Priority Scheduling - Non-Preemptive
Create a Gantt chart (remember: lower number = higher priority)
Handle priority ties using FCFS order
Calculate all timing metrics
Identify potential starvation issues
Part B: Preemptive Scheduling Algorithms
4. Shortest Remaining Time First (SRTF)
Create a detailed Gantt chart showing preemptions
Track when processes are preempted and resumed
Calculate all timing metrics including context switch overhead
Compare with non-preemptive SJF
5. Round Robin (RR) with Time Quantum = 3
Create a Gantt chart showing time slices
Handle context switches between processes
Calculate all timing metrics
Analyze the effect of the chosen time quantum
6. Priority Scheduling - Preemptive
Create a Gantt chart showing preemptions
Handle priority-based preemption
Calculate all timing metrics
Discuss aging solutions for starvation
Part C: Advanced Analysis
7. Multilevel Queue Scheduling
Design a multilevel queue system with:
Queue 1 (Highest Priority): System processes - Round Robin (Q=2)
Queue 2 (Medium Priority): Interactive processes - Round Robin (Q=4)
Queue 3 (Lowest Priority): Batch processes - FCFS
Classify the given processes and show execution:
P1, P3: Batch processes
P2, P4: Interactive processes
P5: System process
8. I/O Consideration
For processes with I/O operations:
Show how I/O affects the scheduling
Calculate CPU utilization
Demonstrate process state transitions (Ready → Running → Waiting → Ready)
Create a timeline showing both CPU and I/O device usage
Calculation Requirements
For each algorithm, calculate:
1. Timing Metrics
Completion Time (CT): Time when process finishes execution
Turnaround Time (TAT): CT - Arrival Time
Waiting Time (WT): TAT - Burst Time
Response Time (RT): Time from arrival to first CPU allocation
2. Performance Metrics
Average Turnaround Time: Σ(TAT) / n
Average Waiting Time: Σ(WT) / n
Average Response Time: Σ(RT) / n
CPU Utilization: (Total CPU busy time / Total time) × 100%
Throughput: Number of processes completed per unit time
3. Additional Analysis
Variance in turnaround times: Measure fairness
Number of context switches: Overhead analysis
Convoy effect occurrence: In FCFS
Starvation potential: In priority-based algorithms
4. Discussion Questions
Answer the following:
1. Which algorithm provides the best average turnaround time? Why?
2. Which algorithm is most fair to all processes? Justify your answer.
3. How does the time quantum in Round Robin affect performance?
4. What are the trade-offs between preemptive and non-preemptive scheduling?
5. How do I/O operations impact different scheduling algorithms?
6. Which algorithm would you recommend for:
o A batch processing system?
o An interactive system?
o A real-time system?