Assignment 04: CPU Scheduling Algorithms

Self-Assessment

Topic 1: Scheduling Criteria & Bottlenecks

Exercise 1.1: Core Performance Metrics Define the following scheduling criteria: Throughput, Turnaround Time (TAT), and Response Time (RT). Why is it often impossible for an operating system designer to optimize all of these criteria simultaneously?

Exercise 1.2 (Advanced): Analyzing the Convoy Effect First-Come, First-Served (FCFS) is the simplest scheduling algorithm but suffers from a specific performance degradation known as the Convoy Effect. Describe the sequence of events that triggers this effect and explain exactly how it impacts both CPU utilization and the performance of short processes.

Topic 2: FCFS and SJF (Gantt Charts & Metrics)

Base Scenario for Topic 2: Assume the following processes arrive in the Ready Queue:

• P1: Arrival = 0, Burst Time = 8
• P2: Arrival = 1, Burst Time = 4
• P3: Arrival = 2, Burst Time = 9
• P4: Arrival = 3, Burst Time = 5

Exercise 2.1: FCFS Execution Calculate the Turnaround Time (TAT) and Waiting Time (WT) for all four processes using First-Come, First-Served (FCFS) scheduling. What are the average TAT and average WT?

Exercise 2.2 (Advanced): Preemptive SJF (SRTF) Execution Calculate the Turnaround Time (TAT) and Waiting Time (WT) for the same four processes using Preemptive Shortest Job First (also known as Shortest-Remaining-Time-First, or SRTF). Hint: Track the remaining burst times carefully upon each new arrival.

Topic 3: Round Robin & Quantum Dynamics

Exercise 3.1: The Mechanism of Time-Sharing Explain how Round Robin (RR) scheduling works. Identify one major performance advantage and one major operational disadvantage of this algorithm.

Exercise 3.2 (Advanced): Tuning the Quantum Size The performance of Round Robin depends heavily on the chosen time quantum size. Describe the system behaviors that emerge if an operating system designer sets the time quantum to an extremely large value (e.g., 1000 seconds) versus an extremely small value (e.g., 1 microsecond).

Topic 4: Real-World Application & Algorithm Selection

Exercise 4.1: Batch vs. Interactive Optimization Classify SJF and Round Robin based on their primary optimization goals. Which real-world environment is best suited for each algorithm?

Exercise 4.2 (Advanced): The Optimality vs. Practicality Dilemma Shortest Job First (SJF) is theoretically optimal for average waiting time. However, it is rarely implemented in its pure form in modern interactive operating systems. Explain the two primary reasons why SJF is impractical, and describe the mathematical technique real-world operating systems use to try and mimic its behavior.

Topic 5: Complex Numerical Analysis (Gantt Charts & Metrics)

Base Scenario for Topic 5: Assume the following processes arrive in the Ready Queue. Ensure you track the specific arrival times carefully during your calculations.

• P1: Arrival = 0, Burst Time = 8
• P2: Arrival = 1, Burst Time = 4
• P3: Arrival = 2, Burst Time = 9
• P4: Arrival = 3, Burst Time = 5

Exercise 5.1: Non-Preemptive SJF Evaluation Using the Non-Preemptive Shortest Job First (SJF) algorithm, determine the execution order. Draw the conceptual Gantt chart, and calculate the Turnaround Time (TAT) and Waiting Time (WT) for all four processes. What are the average TAT and average WT?

Exercise 5.2 (Hard): Round Robin (Quantum = 4) Evaluation Evaluate the same four processes using Round Robin scheduling with a time quantum of 4. Track the Ready Queue accurately as processes arrive and are preempted. Calculate the average Turnaround Time, average Waiting Time, and average Response Time.

Topic 6: Comparative Analysis and Strategy

Exercise 6.1: Preemptive vs. Non-Preemptive Categorization Categorize FCFS, SJF, SRTF, and Round Robin based on their preemption type. Explain the fundamental architectural difference between preemptive and non-preemptive scheduling.

Exercise 6.2 (Advanced): Algorithm Selection by Optimization Goal You have been hired to architect the schedulers for two entirely different systems:

1. An automated batch processing mainframe focused purely on maximizing system throughput.
2. A consumer interactive desktop operating system where UI fairness and response times are critical.

Select the most appropriate scheduling algorithm from this week’s lesson for each system and justify your choice. Identify whether your chosen algorithm for either system suffers from the risk of starvation.

Topic 7: Large-Scale System Simulations & Algorithm Comparison

Base Scenario 1: The High-Volume Batch Workload A batch processing system receives a sudden influx of 7 processes. Note the arrival of a massive CPU-bound process right at system initialization.

• P1: Arrival = 0, Burst Time = 12
• P2: Arrival = 2, Burst Time = 4
• P3: Arrival = 3, Burst Time = 6
• P4: Arrival = 5, Burst Time = 5
• P5: Arrival = 7, Burst Time = 2
• P6: Arrival = 9, Burst Time = 7
• P7: Arrival = 10, Burst Time = 3

Exercise 7.1: Demonstrating the Convoy Effect Mathematically Calculate the average Waiting Time (WT) for all 7 processes using First-Come, First-Served (FCFS) scheduling. Then, recalculate the average WT using Non-Preemptive Shortest Job First (SJF). Compare the two averages to mathematically prove the performance degradation caused by the Convoy Effect under FCFS.

Base Scenario 2: High-Contention Preemptive Scheduling An interactive time-sharing system experiences heavy contention. Six processes arrive in rapid succession, resulting in continuous queue reorganization.

• P1: Arrival = 0, Burst Time = 10
• P2: Arrival = 1, Burst Time = 4
• P3: Arrival = 2, Burst Time = 2
• P4: Arrival = 4, Burst Time = 7
• P5: Arrival = 6, Burst Time = 3
• P6: Arrival = 7, Burst Time = 1

Exercise 7.2 (Hard): SRTF vs. Round Robin Dynamics Evaluate this high-contention workload using two different preemptive algorithms:

1. Shortest-Remaining-Time-First (SRTF): Calculate the Turnaround Time (TAT) and Waiting Time (WT) for all processes.
2. Round Robin (Time Quantum = 3): Calculate the TAT and WT for all processes. (Assume new arrivals are placed at the back of the Ready Queue BEFORE a preempted process is re-added).

Compare the execution lifecycle of the shortest process (P6) under both algorithms.