Dr. Soumadip Biswas
Computer Science & Engineering | Student | Researcher | Educator

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?

💡 View Solution

  • Throughput: The number of processes completed per unit time, where high throughput signifies more work done.

  • Turnaround Time (TAT): The total time from process arrival to completion, calculated as Waiting Time plus Execution Time.

  • Response Time (RT): The time from when a request is submitted until the first response is produced.

It is often impossible to optimize all criteria simultaneously because prioritizing one metric frequently degrades another; for example, optimizing average turnaround time might lead to poor response times for some processes. Operating system designers must choose which criteria to prioritize based on their specific system goals.

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.

💡 View Solution
The Convoy Effect occurs when a short process gets stuck waiting behind a long process. This scenario is most commonly triggered when a long, CPU-bound process is executed first, followed by multiple I/O-bound processes in the Ready Queue. Because FCFS is non-preemptive, the long process runs to completion without interruption, causing the shorter processes to wait unnecessarily. This leads to low CPU utilization and extremely poor performance (high waiting times) for the short processes.

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

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

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?

💡 View Solution

Under FCFS, processes are scheduled in the exact order they arrive. Since FCFS is non-preemptive, once a process starts executing, it runs to completion.

  • Execution Order: P1 (0 to 8), P2 (8 to 12), P3 (12 to 21), P4 (21 to 26).
  • P1: Completion = 8. TAT = $8 - 0 = 8$. WT = $8 - 8 = 0$.
  • P2: Completion = 12. TAT = $12 - 1 = 11$. WT = $11 - 4 = 7$.
  • P3: Completion = 21. TAT = $21 - 2 = 19$. WT = $19 - 9 = 10$.
  • P4: Completion = 26. TAT = $26 - 3 = 23$. WT = $23 - 5 = 18$.
  • Average TAT: $(8 + 11 + 19 + 23) / 4 = 15.25$ units.
  • Average WT: $(0 + 7 + 10 + 18) / 4 = 8.75$ units.

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.

💡 View Solution

Under SRTF, if a new process arrives with a CPU burst time less than the remaining time of the currently executing process, the CPU is preempted.

  • Time 0: P1 arrives (burst 8) and runs.
  • Time 1: P2 arrives (burst 4). P1 has 7 remaining. Since $4 < 7$, P2 preempts P1.
  • Time 2: P3 arrives (burst 9). P2 has 3 remaining. P2 continues.
  • Time 3: P4 arrives (burst 5). P2 has 2 remaining. P2 continues until Time 5.
  • Time 5: P2 completes. Remaining: P1(7), P3(9), P4(5). P4 is shortest. P4 runs until Time 10.
  • Time 10: P4 completes. Remaining: P1(7), P3(9). P1 is shortest. P1 runs until Time 17.
  • Time 17: P1 completes. P3 runs until Time 26.
  • P1: Completion = 17. TAT = $17 - 0 = 17$. WT = $17 - 8 = 9$.
  • P2: Completion = 5. TAT = $5 - 1 = 4$. WT = $4 - 4 = 0$.
  • P3: Completion = 26. TAT = $26 - 2 = 24$. WT = $24 - 9 = 15$.
  • P4: Completion = 10. TAT = $10 - 3 = 7$. WT = $7 - 5 = 2$.
  • Average TAT: $(17 + 4 + 24 + 7) / 4 = 13$ units.
  • Average WT: $(9 + 0 + 15 + 2) / 4 = 6.5$ units.

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.

💡 View Solution

In Round Robin scheduling, each process gets a small unit of CPU time called a time quantum or time slice. When a process’s quantum expires, it is preempted and added to the end of the Ready Queue.

  • Advantage: It is highly fair and ensures that no process waits indefinitely, completely eliminating starvation and providing good response times for time-sharing systems.

  • Disadvantage: Frequent context switches increase overhead, as the CPU performs no useful work during the switch.

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).

💡 View Solution

  • Extremely Large Quantum: The scheduling behavior simply approaches First-Come, First-Served (FCFS), which leads to poor response times for short jobs that get stuck waiting behind longer ones.

  • Extremely Small Quantum: The system will suffer from massive context switch overhead, which reduces overall system throughput because the CPU spends too much time switching contexts rather than executing processes.

  • An optimal time quantum is typically calibrated to fall between 80% of CPU bursts to balance these extremes.

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?

💡 View Solution

  • SJF (Shortest Job First): This is a batch-oriented scheduling algorithm. Its primary focus is maximizing throughput and minimizing average turnaround time. It is best suited for batch systems where burst times are known in advance or specialized tasks.

  • Round Robin (RR): This is an interactive / time-sharing scheduling algorithm. Its primary focus is providing good response times and fairness among users. It is best suited for interactive systems, desktops, and servers.

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.

💡 View Solution

SJF is considered impractical for two primary reasons:

  1. Prediction Impossibility: It requires knowing the exact future CPU burst time in advance to schedule the shortest job, which is generally not possible.

  2. Starvation Risks: Long processes might never get to execute if the system receives a continuous, unbroken stream of short processes.

To mimic SJF’s optimal waiting times, practical operating systems attempt to predict the next CPU burst using exponential averaging of past bursts.

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.

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?

💡 View Solution

Under Non-Preemptive SJF, once the CPU is allocated to a process, it cannot be preempted until its CPU burst is completed. The scheduler selects the process in the Ready Queue with the shortest burst time.

  • Time 0: P1 is the only process available. It runs to completion.
  • Time 8: P1 completes. P2, P3, and P4 are all in the Ready Queue. The shortest is P2 (burst 4).
  • Time 12: P2 completes. P3 and P4 are in the queue. The shortest is P4 (burst 5).
  • Time 17: P4 completes. P3 (burst 9) runs to completion.
  • Execution Order (Gantt Chart): P1 (0 to 8) $\rightarrow$ P2 (8 to 12) $\rightarrow$ P4 (12 to 17) $\rightarrow$ P3 (17 to 26).

Performance Metrics:

  • P1: Completion = 8. TAT = $8 - 0 = 8$. WT = $8 - 8 = 0$.

  • P2: Completion = 12. TAT = $12 - 1 = 11$. WT = $11 - 4 = 7$.

  • P3: Completion = 26. TAT = $26 - 2 = 24$. WT = $24 - 9 = 15$.

  • P4: Completion = 17. TAT = $17 - 3 = 14$. WT = $14 - 5 = 9$.

  • Average TAT: $(8 + 11 + 24 + 14) / 4 = 14.25$ units.

  • Average WT: $(0 + 7 + 15 + 9) / 4 = 7.75$ units.

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.

💡 View Solution

Under Round Robin, each process gets a time quantum of 4 units. If it does not complete, it is preempted and added to the end of the Ready Queue.

  • Time 0: P1 arrives and runs.
  • During Time 0-4, P2, P3, and P4 arrive and enter the queue in that order.
  • Time 4: P1 completes its quantum (4 remaining) and goes to the back of the queue. The queue is now [P2, P3, P4, P1]. P2 runs.
  • Time 8: P2 completes its entire burst and terminates. The queue is [P3, P4, P1]. P3 runs.
  • Time 12: P3 completes its quantum (5 remaining) and goes to the back. The queue is [P4, P1, P3]. P4 runs.
  • Time 16: P4 completes its quantum (1 remaining) and goes to the back. The queue is [P1, P3, P4]. P1 runs.
  • Time 20: P1 completes its remaining burst (0 remaining) and terminates. The queue is [P3, P4]. P3 runs.
  • Time 24: P3 completes its quantum (1 remaining) and goes to the back. The queue is [P4, P3]. P4 runs.
  • Time 25: P4 completes its remaining burst and terminates. The queue is [P3]. P3 runs.
  • Time 26: P3 completes its remaining burst and terminates.
  • Execution Order (Gantt Chart): P1 (0-4) $\rightarrow$ P2 (4-8) $\rightarrow$ P3 (8-12) $\rightarrow$ P4 (12-16) $\rightarrow$ P1 (16-20) $\rightarrow$ P3 (20-24) $\rightarrow$ P4 (24-25) $\rightarrow$ P3 (25-26).

Performance Metrics:

  • Completion Times: P1=20, P2=8, P3=26, P4=25.

  • Turnaround Time (Completion - Arrival): P1=20, P2=7, P3=24, P4=22. Average TAT: $73 / 4 = 18.25$ units.

  • Waiting Time (TAT - Burst Time): P1=12, P2=3, P3=15, P4=17. Average WT: $47 / 4 = 11.75$ units.

  • Response Time (First Start - Arrival): P1=0, P2=3, P3=6, P4=9. Average RT: $18 / 4 = 4.5$ units.

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.

💡 View Solution

  • Non-Preemptive Algorithms: FCFS and SJF.

  • Preemptive Algorithms: SRTF (Preemptive SJF) and Round Robin.

The fundamental difference lies in how the CPU is released. In non-preemptive scheduling, once the CPU is granted to a process, it is held continuously until the process either completes its burst or voluntarily yields. In preemptive scheduling, the operating system can forcibly take the CPU away from a running process, typically triggered by an interrupt (such as a time quantum expiring) or the arrival of a higher-priority process.

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.

💡 View Solution

  1. Batch Processing Mainframe: The optimal choice is Shortest Job First (SJF) or FCFS. SJF is a batch-oriented strategy focused on maximizing throughput and minimizing average turnaround time, which is ideal if CPU bursts can be estimated. However, SJF suffers from a high risk of starvation; long jobs may never execute if there is a continuous stream of short processes.

  2. Interactive Desktop OS: The optimal choice is Round Robin (RR). Round Robin is an interactive, time-sharing scheduler that ensures fairness and provides good response times by guaranteeing every process gets a time slice. Round Robin completely eliminates the risk of starvation, ensuring no process waits indefinitely.

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.

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.

💡 View Solution

1. FCFS Evaluation: Under FCFS, processes execute strictly in arrival order.

  • Execution Order: P1 (0-12) $\rightarrow$ P2 (12-16) $\rightarrow$ P3 (16-22) $\rightarrow$ P4 (22-27) $\rightarrow$ P5 (27-29) $\rightarrow$ P6 (29-36) $\rightarrow$ P7 (36-39).

  • Waiting Times (Start Time - Arrival Time):

  • P1: $0 - 0 = 0$

  • P2: $12 - 2 = 10$

  • P3: $16 - 3 = 13$

  • P4: $22 - 5 = 17$

  • P5: $27 - 7 = 20$

  • P6: $29 - 9 = 20$

  • P7: $36 - 10 = 26$

  • FCFS Average WT: $106 / 7 = 15.14$ units.

2. Non-Preemptive SJF Evaluation: Under Non-Preemptive SJF, P1 must finish entirely before a decision is made. At time 12, P2, P3, P4, P5, P6, and P7 are all waiting. The scheduler clears them in order of shortest burst to longest burst.

  • Execution Order: P1 (0-12) $\rightarrow$ P5 (12-14) $\rightarrow$ P7 (14-17) $\rightarrow$ P2 (17-21) $\rightarrow$ P4 (21-26) $\rightarrow$ P3 (26-32) $\rightarrow$ P6 (32-39).

  • Waiting Times (Start Time - Arrival Time):

  • P1: $0 - 0 = 0$

  • P5: $12 - 7 = 5$

  • P7: $14 - 10 = 4$

  • P2: $17 - 2 = 15$

  • P4: $21 - 5 = 16$

  • P3: $26 - 3 = 23$

  • P6: $32 - 9 = 23$

  • SJF Average WT: $86 / 7 = 12.29$ units.

Comparison: The Convoy Effect is mathematically proven here. Under FCFS, the massive P1 process forces six smaller processes to idle, driving the average waiting time up to 15.14 units. By simply reordering the queue after P1 finishes to clear the shortest jobs first, SJF drops the average waiting time by nearly 20%, bringing it down to 12.29 units.

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.

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.

💡 View Solution

1. SRTF (Preemptive SJF) Evaluation: Under SRTF, the CPU is preempted whenever a new process arrives with a shorter remaining burst than the current process.

  • Time 0: P1(10) starts.

  • Time 1: P2(4) arrives. P2(4) < P1(9). P2 preempts P1.

  • Time 2: P3(2) arrives. P3(2) < P2(3). P3 preempts P2.

  • Time 4: P3 completes. Ready: P1(9), P2(3). P4(7) arrives. P2 is shortest and resumes.

  • Time 6: P5(3) arrives. P2(1) < P5(3). P2 continues.

  • Time 7: P2 completes. Ready: P1(9), P4(7), P5(3). P6(1) arrives. P6 is shortest and runs.

  • Time 8: P6 completes. Ready: P1(9), P4(7), P5(3). P5 is shortest and runs.

  • Time 11: P5 completes. Ready: P1(9), P4(7). P4 is shortest and runs.

  • Time 18: P4 completes. P1 resumes and finishes at 27.

  • SRTF Metrics:

  • P1: End=27. TAT = $27 - 0 = 27$. WT = $27 - 10 = 17$.

  • P2: End=7. TAT = $7 - 1 = 6$. WT = $6 - 4 = 2$.

  • P3: End=4. TAT = $4 - 2 = 2$. WT = $2 - 2 = 0$.

  • P4: End=18. TAT = $18 - 4 = 14$. WT = $14 - 7 = 7$.

  • P5: End=11. TAT = $11 - 6 = 5$. WT = $5 - 3 = 2$.

  • P6: End=8. TAT = $8 - 7 = 1$. WT = $1 - 1 = 0$.

  • Average TAT: $55 / 6 = 9.17$ units.

  • Average WT: $28 / 6 = 4.67$ units.

2. Round Robin (Quantum = 3) Evaluation:

  • Time 0-3: P1 runs. P2 and P3 arrive. Q: [P2, P3, P1].

  • Time 3-6: P2 runs. P4 arrives (t=4). P5 arrives (t=6). Q: [P3, P1, P4, P5, P2]. (P2 preempted).

  • Time 6-8: P3 runs and completes (only needed 2). P6 arrives (t=7). Q: [P1, P4, P5, P2, P6].

  • Time 8-11: P1 runs. Q: [P4, P5, P2, P6, P1]. (P1 preempted).

  • Time 11-14: P4 runs. Q: [P5, P2, P6, P1, P4]. (P4 preempted).

  • Time 14-17: P5 runs and completes. Q: [P2, P6, P1, P4].

  • Time 17-18: P2 resumes and completes (needed 1). Q: [P6, P1, P4].

  • Time 18-19: P6 runs and completes (needed 1). Q: [P1, P4].

  • Time 19-22: P1 runs. Q: [P4, P1]. (P1 preempted).

  • Time 22-25: P4 runs. Q: [P1, P4]. (P4 preempted).

  • Time 25-26: P1 resumes and completes (needed 1). Q: [P4].

  • Time 26-27: P4 resumes and completes (needed 1).

  • Round Robin Metrics:

  • P1: End=26. TAT = $26 - 0 = 26$. WT = $26 - 10 = 16$.

  • P2: End=18. TAT = $18 - 1 = 17$. WT = $17 - 4 = 13$.

  • P3: End=8. TAT = $8 - 2 = 6$. WT = $6 - 2 = 4$.

  • P4: End=27. TAT = $27 - 4 = 23$. WT = $23 - 7 = 16$.

  • P5: End=17. TAT = $17 - 6 = 11$. WT = $11 - 3 = 8$.

  • P6: End=19. TAT = $19 - 7 = 12$. WT = $12 - 1 = 11$.

  • Average TAT: $95 / 6 = 15.83$ units.

  • Average WT: $68 / 6 = 11.33$ units.

Comparison of P6: Under SRTF, P6 arrives at time 7, immediately preempts the system because its burst (1) is the absolute shortest possible, and finishes at time 8. Its waiting time is exactly 0. Under Round Robin, P6 arrives at time 7 but is forced to wait at the back of a massive queue while P1, P4, P5, and P2 all take their 3-unit time slices. P6 does not even start executing until time 18, suffering a waiting time of 11 units for a 1-unit job. This mathematically demonstrates how Round Robin sacrifices throughput and average wait time across the board in order to guarantee absolute fairness (no starvation).

SDB Watermark