Lecture 7: Process Scheduling (Part 2)

Introduction

• Continuation of process scheduling discussion.
• Previous focus: First-Come, First-Serve (FCFS) scheduling.
  • Simple to implement, relies on queue and process arrival time.
  • Disadvantages: Depends on arrival order, can lead to high waiting time (Convoy Effect).
• Today's focus: Shortest Job First (SJF) scheduling.

Shortest Job First (SJF) Scheduling

• Concept: Prioritizes processes with the shortest burst time rather than arrival time.
• Variants:
  • Non-Preemptive SJF: Once a process starts, it runs to completion.
  • Preemptive SJF (Shortest Remaining Time First - SRTF): Can interrupt a running process if a new process arrives with a shorter burst time.

Non-Preemptive SJF Example

• Process: P1, P2, P3, P4 with arrival times and burst times.
• Scheduling involves calculating completion time, turnaround time, and waiting time.
• Average Waiting Time: Calculated based on process order.

Preemptive SJF (SRTF) Example

• Involves frequent checking and switching between processes based on burst time.
• Results in generally lower average waiting time compared to non-preemptive.
• Key Insight: Preemptive scheduling can reduce waiting time but may increase context switching.

Burst Time Prediction

• Challenge: Burst time is often predicted rather than known.
• Static vs. Dynamic Prediction: Static based on process size/type, Dynamic uses historical data (simple or exponential averaging).

Round Robin Scheduling

• Concept: Allocates fixed time slices to each process.
• Advantages: Fairness, prevents starvation.
• Example: Processes executed in cycles with a fixed time slice.
  • Time slice affects context switching and response time.
  • Smaller time slices increase context switches, reduce response time.

Priority Scheduling

• Concept: Assigns priorities to processes to determine execution order.
• Types: Preemptive and non-preemptive priority scheduling.
  • Higher priority processes interrupt lower priority ones in preemptive scheduling.

Starvation in Priority Scheduling

• Low-priority processes may suffer starvation if constantly preempted by higher priority processes.
• Solution: Dynamic priority adjustment or priority aging to ensure execution.

Multi-Level Scheduling

• Concept: Organizes processes into different priority classes with their ready queues.
• Prioritizes execution based on process class.
• Each class can use different scheduling algorithms (e.g., round robin, FCFS).

Conclusion

• Reviewed various scheduling techniques including FCFS, SJF, Round Robin, Priority Scheduling.
• Discussed multi-level scheduling approach for organizing processes into priority classes.
• Emphasized the trade-offs involved in different scheduling algorithms.