CPU Scheduling: Algorithms, Metrics & Real-World Impact

Core Concepts: What is CPU Scheduling?

CPU scheduling is the core mechanism of an OS that decides which process gets the CPU at any given time. It ensures fairness, efficiency, and responsiveness in multi-programming environments.

Why is CPU Scheduling Needed?

Without scheduling, processes would run sequentially, leading to:

• CPU idle time (wasted cycles).
• Poor response time (e.g., a bank app freezing while processing transactions).
• Starvation (some processes never get CPU time).

stateDiagram-v2
    [*] --> Ready: Processes wait in ready queue
    Ready --> Running: Scheduler selects a process
    Running --> Blocked: I/O or waiting for event
    Running --> Exit: Process terminates
    Blocked --> Ready: Process resumes

Key Scheduling Metrics (How to Measure Performance)

Scheduling algorithms are evaluated using these four critical metrics:

Worked Example: Bank Loan Processing A bank processes 3 loan requests with the following burst times (in seconds):

• Loan A: 5s
• Loan B: 3s
• Loan C: 8s

Question: Calculate turnaround time and waiting time for each under FCFS (First-Come-First-Served).

Solution:

1. Order: A → B → C
2. Turnaround Time = Completion Time - Arrival Time (assuming all arrive at t=0).
   • A: 5s (5-0)
   • B: 8s (5+3-0)
   • C: 16s (8+8-0)
3. Waiting Time = Turnaround Time - Burst Time.
   • A: 0s (5-5)
   • B: 3s (8-5)
   • C: 8s (16-8)

Visual Comparison:

gantt
    title FCFS Scheduling for Bank Loans
    dateFormat  YYYY-MM-DD
    section CPU
    Loan A :a1, 2023-01-01, 5s
    Loan B :a2, 2023-01-01, 3s
    Loan C :a3, 2023-01-01, 8s

Scheduling Algorithms: How They Work

1. First-Come-First-Served (FCFS)

• Type: Non-preemptive (once started, a process runs to completion).
• How it works: Processes are executed in the order they arrive.
• Pros: Simple to implement, fair for short processes.
• Cons: Convoy effect (short processes wait behind long ones). Example: In Kathmandu traffic, a slow truck blocks fast cars behind it.

2. Shortest Job First (SJF)

• Type: Non-preemptive (basic) or Shortest Remaining Time First (SRTF) (preemptive).
• How it works: Selects the process with the shortest burst time next.
• Pros: Minimizes average waiting time.
• Cons: Starvation (long processes may never run); hard to predict burst times.

Worked Example: Daraz Order Processing Daraz’s backend processes orders with burst times:

• Order X: 4s (electronics)
• Order Y: 6s (groceries)
• Order Z: 2s (books)

SJF Schedule:

1. Order Z (2s) → Order X (4s) → Order Y (6s)
2. Total Waiting Time: 0 (Z) + 2 (X) + 6 (Y) = 8s (vs. 12s in FCFS).

3. Priority Scheduling

• Type: Preemptive or non-preemptive.
• How it works: Processes are assigned priority numbers (lower = higher priority).
• Problem: Starvation (low-priority processes never run).
• Solution: Aging (gradually increase priority of waiting processes).

Example: Ncell Call Routing

• Priority 1: Emergency calls (911).
• Priority 2: Premium customers.
• Priority 3: Regular users.
• Risk: If too many Priority 1 calls arrive, Priority 3 users face delays.

4. Round Robin (RR)

• Type: Preemptive (time-slicing).
• How it works: Each process gets a fixed time quantum (e.g., 2s). If not finished, it goes to the end of the queue.
• Pros: Fair, responsive (good for interactive systems like WhatsApp).
• Cons: High overhead if quantum is too small.

Worked Example: WhatsApp Message Processing

• Quantum = 1s.
• Processes: Message A (3s), Message B (5s), Message C (2s).
• Schedule:
  1. A (1s) → B (1s) → C (1s) → A (1s) → B (1s) → C (1s) → A (1s) → B (2s).
  2. Total Waiting Time: 2 (A) + 3 (B) + 1 (C) = 6s.

gantt
    title Round Robin (Quantum=1s)
    dateFormat  YYYY-MM-DD
    section CPU
    A :a1, 2023-01-01, 1s
    B :a2, 2023-01-01, 1s
    C :a3, 2023-01-01, 1s
    A :a4, 2023-01-01, 1s
    B :a5, 2023-01-01, 1s
    C :a6, 2023-01-01, 1s
    A :a7, 2023-01-01, 1s
    B :a8, 2023-01-01, 2s

5. Multilevel Queue Scheduling

• How it works: Processes are divided into fixed priority queues (e.g., foreground vs. background).
• Example: Linux uses:
  • Real-time processes (highest priority, e.g., audio playback).
  • Interactive processes (medium, e.g., terminal commands).
  • Batch processes (lowest, e.g., data backups).

In the Real World

1. Khalti Payments

   • Uses priority scheduling to process high-value transactions (e.g., bill payments) faster than low-value ones (e.g., peer-to-peer transfers).
   • Why? Reduces waiting time for critical payments (e.g., electricity bills).

2. Daraz Order Fulfillment

   • Employs Round Robin for backend processing to ensure no single order monopolizes CPU time.
   • Example: During Diwali sales, Daraz’s servers use RR to handle 10,000+ orders simultaneously without freezing.

3. Ncell Network Calls

   • Uses Multilevel Queue Scheduling:
     • Priority 1: Emergency calls (routed instantly).
     • Priority 2: VoLTE calls (higher bandwidth).
     • Priority 3: SMS/data (lower priority).
   • Result: 95% call success rate even during network congestion.

Comparison Table: Scheduling Algorithms

Advanced Topics

1. Multiprogramming vs. Multiprocessing

• Multiprogramming: Multiple processes in memory; CPU switches between them (scheduling focus).
• Multiprocessing: Multiple CPUs/core; processes run simultaneously (parallelism).

2. Scheduling in Real-Time Systems

• Hard Real-Time: Missed deadline = system failure (e.g., pacemaker software).
• Soft Real-Time: Missed deadline = degraded performance (e.g., video streaming).
• Algorithm: Rate-Monotonic Scheduling (RMS) assigns priorities based on task period (shorter period = higher priority).

3. Linux Scheduling (CFQ - Completely Fair Queuing)

• How it works: Divides CPU time into time slices and allocates them fairly.
• Goal: Ensure no process gets more than its "fair share."
• Example: In a Linux server, a web app (Apache) and a database (MySQL) share CPU time equally.

Exam Tip

What to Expect in TU/PU Exams:

1. Definitions & Short Answers (3-5 marks):

   • Define turnaround time, preemptive scheduling, and convoy effect.
   • Example Question: "What is the difference between SJF and SRTF?" Answer: SJF is non-preemptive; SRTF preempts if a shorter job arrives.

2. Worked Examples (5-10 marks):

   • Given burst times, calculate metrics for FCFS, SJF, or RR.
   • Tip: Always draw a Gantt chart to visualize schedules.

3. Algorithm Comparison (5-8 marks):

   • Compare Round Robin vs. Priority Scheduling in terms of fairness and overhead.
   • Use the comparison table above as a reference.

4. Real-World Applications (3-5 marks):

   • Relate scheduling to Nepali apps (e.g., Khalti, Daraz, Ncell).
   • Example: "How would you schedule transactions in Khalti to minimize waiting time?" Answer: Use SJF for small transactions and priority scheduling for large payments.

5. Shortcomings & Solutions (3-5 marks):

   • "What is starvation? How does aging solve it?" Answer: Starvation occurs when low-priority processes wait indefinitely. Aging gradually increases their priority.

Common Mistakes to Avoid:

• Ignoring preemption: Always check if an algorithm is preemptive/non-preemptive.
• Forgetting to draw diagrams: Gantt charts and state diagrams are mandatory for full marks.
• Mixing metrics: Turnaround time ≠ waiting time. Always calculate both separately.