CPU Scheduling: Algorithms, Metrics & Real-World Impact

What is CPU Scheduling?

CPU scheduling is the mechanism by which the operating system decides which process gets the CPU at any given time. It ensures fairness, efficiency, and optimal resource utilization. Without scheduling, only one process would run at a time, leading to poor performance.

Why is CPU Scheduling Needed?

• Multiprogramming: Multiple processes share the CPU.
• Multiprocessing: Multiple CPUs require coordination.
• Interactive Systems: Users expect quick responses (e.g., typing in a terminal).
• Batch Systems: Jobs must complete efficiently (e.g., NTC billing systems).

Key Concepts

1. Process States and Scheduling Queues

A process moves through different states:

stateDiagram-v2
    [*] --> New: "Process created"
    New --> Ready: "Admitted to ready queue"
    Ready --> Running: "CPU allocated"
    Running --> Waiting: "I/O or event"
    Waiting --> Ready: "I/O completes"
    Running --> Terminated: "Process ends"
    Terminated --> [*]

• Ready Queue: Processes ready to execute.
• Device Queues: Processes waiting for I/O.
• Job Queue: All processes in the system.

2. Scheduling Criteria

The OS evaluates algorithms based on:

CPU Scheduling Algorithms

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

• How it works: Processes are executed in the order they arrive.
• Example:
  • Process A arrives at time 0, needs 5 units.
  • Process B arrives at time 1, needs 3 units.
  • Process C arrives at time 2, needs 1 unit.
  • Execution order: A → B → C.
  • Turnaround times: A = 5, B = 8, C = 9.

• Advantages: Simple, fair (no starvation).
• Disadvantages: Convoy effect (short processes wait for long ones).
• Real-world use: Batch processing (e.g., NTC’s nightly billing jobs).

2. Shortest Job First (SJF)

• How it works: The shortest job runs first (non-preemptive or preemptive).
• Example:
  • Same processes as above, but SJF picks the shortest remaining time.
  • Execution order: C → B → A.
  • Turnaround times: C = 1, B = 4, A = 9.
  • Average waiting time: (0 + 1 + 3)/3 = 1.33 (better than FCFS’s 5.33).

• Advantages: Minimizes average waiting time.
• Disadvantages:
  • Starvation: Long processes may never run.
  • Hard to predict job lengths.
• Real-world use: Cloud computing (e.g., Google Cloud’s short-lived tasks).

3. Priority Scheduling

• How it works: Processes are assigned priorities (higher priority runs first).
• Preemptive vs. Non-preemptive:
  • Non-preemptive: Lower-priority processes finish first.
  • Preemptive: Higher-priority processes interrupt lower ones.
• Example:
  • Process A (Priority 1, 6 units), B (Priority 2, 1 unit), C (Priority 3, 8 units).
  • Preemptive order: B → A → C.
  • Non-preemptive order: A → B → C.

• Advantages: Critical tasks run first (e.g., system processes).
• Disadvantages: Starvation if low-priority processes never run.
• Solution: Aging (increase priority over time).
• Real-world use: Operating system kernels (e.g., Linux’s nice and renice commands).

4. Round Robin (RR)

• How it works: Each process gets a time quantum (e.g., 2–10 ms). If a process doesn’t finish, it goes to the end of the queue.
• Example:
  • Time quantum = 2 units.
  • Processes: A (5), B (3), C (1).
  • Execution order: A → B → C → A → A.
  • Turnaround times: A = 7, B = 5, C = 3.

• Advantages:
  • Fair (no starvation).
  • Good for interactive systems (e.g., WhatsApp’s message processing).
• Disadvantages: High overhead due to frequent context switches.
• Real-world use: Time-sharing systems (e.g., Pathao’s driver assignment).

5. Multilevel Queue Scheduling

• How it works: Processes are divided into fixed-priority queues (e.g., foreground vs. background).
• Example:
  • Queue 1 (High Priority): Interactive processes (time quantum = 2).
  • Queue 2 (Low Priority): Batch jobs (FCFS).
  • If Queue 1 is empty, Queue 2 gets CPU time.

• Advantages: Balances responsiveness and throughput.
• Disadvantages: Complexity in queue management.
• Real-world use: Android’s app scheduling (foreground apps get priority).

6. Multilevel Feedback Queue

• How it works: Processes can move between queues based on behavior.
• Example:
  • Queue 1: Short processes (RR, quantum=2).
  • Queue 2: Medium processes (RR, quantum=4).
  • Queue 3: Long processes (FCFS).
  • If a process uses its full quantum, it moves to the next queue.

• Advantages: Adaptive to process needs.
• Disadvantages: Complex implementation.
• Real-world use: Linux’s Completely Fair Scheduler (CFS).

Comparison of Scheduling Algorithms

Real-World Applications

1. eSewa and Khalti (Mobile Payments)

• Idea Used: Round Robin + Priority Scheduling
  • High-priority queue: Payment processing (low time quantum for fast responses).
  • Low-priority queue: Background transactions (e.g., statement generation).
  • Why? Ensures users don’t face delays during peak hours (e.g., Dashain/Tihar).

2. Daraz Order Fulfillment

• Idea Used: Shortest Job First (SJF)
  • How? Orders with the fewest items (shortest "processing time") are picked first.
  • Result: Faster delivery for small orders, reducing customer waiting time.

3. Ncell Network Traffic

• Idea Used: Multilevel Feedback Queue
  • Queue 1: Real-time calls (high priority, small quantum).
  • Queue 2: Data downloads (medium priority).
  • Queue 3: Background syncs (low priority).
  • Why? Prevents call drops during data-heavy usage.

4. Bank Loan Processing (NMB, Global IME)

• Idea Used: Priority Scheduling with Aging
  • High-priority loans: Government-backed or emergency loans (fast approval).
  • Low-priority loans: Standard personal loans (processed in batches).
  • Aging: Loans waiting too long get priority boosts to avoid customer complaints.

Worked Example: Kathmandu Traffic Routes

Scenario: Imagine traffic lights at a busy intersection (e.g., Thapathali) as a CPU scheduler.

• FCFS: Cars arrive in order; long buses block short cars → jams.
• Round Robin: Each car gets 10 seconds of green light → fair but slow.
• Priority Scheduling:
  • High priority: Ambulances, emergency vehicles (preemptive).
  • Low priority: Private cars (non-preemptive).
• Optimal Solution: Multilevel Feedback Queue
  • Queue 1: Emergency vehicles (RR, quantum=5s).
  • Queue 2: Public transport (RR, quantum=15s).
  • Queue 3: Private cars (FCFS).

Exam Tip

What Examiners Look For:

1. Definitions: Clearly define terms like turnaround time, preemption, and time quantum.
2. Examples: Always provide a numerical example (like the FCFS/SJF above) to illustrate algorithms.
3. Pros/Cons: Compare algorithms in a table (as shown above) to highlight trade-offs.
4. Real-World Links: Relate scheduling to Nepali apps/companies (e.g., Daraz, Khalti) or everyday scenarios (e.g., traffic lights).
5. Diagrams: Draw Gantt charts for scheduling sequences and state diagrams for process flows.
6. Shortcomings: Know starvation, convoy effect, and how aging solves starvation.

Common Pitfalls:

• Assuming SJF is always best: It’s optimal only if you know job lengths (hard in real systems).
• Ignoring preemption: Many modern schedulers (e.g., Linux CFS) are preemptive.
• Forgetting metrics: Always calculate turnaround time and waiting time in examples.

Summary Checklist

Before the exam, ensure you can: ✅ Explain the 5 process states and their transitions. ✅ Draw a Gantt chart for any scheduling algorithm. ✅ Compare FCFS vs. SJF vs. Round Robin using metrics. ✅ Describe how priority scheduling avoids starvation (aging). ✅ Relate Round Robin to WhatsApp or SJF to Daraz. ✅ Sketch a multilevel feedback queue and explain its queues.