CPU Scheduling: Algorithms, Metrics & Real-World Impact

Key Concepts & How They Work

1. What is CPU Scheduling?

CPU scheduling is the mechanism by which the OS decides which process gets the CPU at any given time. It ensures fairness, efficiency, and optimal resource utilization.

stateDiagram-v2
    [*] --> Ready: Processes wait in ready queue
    Ready --> Running: Scheduler selects a process
    Running --> Blocked: Process I/O or waits
    Running --> Exit: Process completes
    Blocked --> Ready: Process resumes
    Ready --> [*]: Process preempted

Real-world analogy:

• Think of a restaurant waiter deciding which customer to serve next (FCFS), or a traffic cop managing lanes (Round Robin).

2. Scheduling Criteria (Metrics)

The OS evaluates algorithms using these metrics:

Example: For a process arriving at time 0 with burst time 8ms:

• If it runs immediately: $TAT=8$, $WT=0$.
• If it waits 3ms: $TAT=11$, $WT=3$.

3. Scheduling Algorithms

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

• How it works: Processes are executed in the order they arrive (non-preemptive).
• Gantt Chart Example:

gantt
    title FCFS Example (Arrival: P1=0, P2=2, P3=4)
    dateFormat  YYYY-MM-DD
    section CPU
    P1 :a1, 2023-01-01, 6
    P2 :a2, 2023-01-07, 3
    P3 :a3, 2023-01-10, 1
    note right of P1: "Arrival Time"
    note right of P2: "Arrival Time"
    note right of P3: "Arrival Time"

Pros/Cons:

Real-world use:

• eSewa payment queue: Transactions are processed in the order they are received (FCFS-like), but this can cause delays for urgent payments.

B. Shortest Job First (SJF)

• How it works: The process with the shortest burst time is executed next (preemptive or non-preemptive).
• Gantt Chart (Non-Preemptive):

gantt
    title SJF (Non-Preemptive) Example
    dateFormat  YYYY-MM-DD
    section CPU
    P3 :a1, 2023-01-01, 1
    P2 :a2, 2023-01-02, 3
    P1 :a3, 2023-01-05, 6
    note right of P3: "Shortest burst time"
    note right of P2: "Next shortest"
    note right of P1: "Longest"

Pros/Cons:

Real-world use:

• Pathao driver dispatch: The app assigns the nearest available driver (shortest "burst" = shortest travel time) to minimize wait time for riders.

C. Priority Scheduling

• How it works: Processes are assigned priorities (higher priority = runs first). Can be preemptive (higher priority interrupts) or non-preemptive.
• Example:

  Process	Burst Time	Priority
  P1	10	3
  P2	1	1
  P3	2	2

Gantt Chart (Preemptive):

gantt
    title Priority Scheduling (Preemptive)
    dateFormat  YYYY-MM-DD
    section CPU
    P2 :a1, 2023-01-01, 1
    P3 :a2, 2023-01-02, 2
    P1 :a3, 2023-01-04, 10
    note right of P2: "Priority 1 (highest)"
    note right of P1: "Priority 10 (lowest)"
    note right of P3: "Priority 2"

Pros/Cons:

Real-world use:

• NTC network traffic: High-priority data packets (e.g., emergency calls) are processed before lower-priority ones (e.g., streaming).

D. Round Robin (RR)

• How it works: Each process gets a time quantum (q) in a cyclic order. Preemptive.
• Gantt Chart (q=4):

  gantt
    title Round Robin (q=4)
    dateFormat  YYYY-MM-DD
    section CPU
    P1 :a1, 2023-01-01, 4d
    P2 :a2, 2023-01-05, 4d
    P3 :a3, 2023-01-09, 4d
    P1 :a4, 2023-01-13, 2d
    P2 :a5, 2023-01-15, 3d

Pros/Cons:

Real-world use:

• Google Cloud VMs: Virtual machines share CPU time in RR fashion to ensure no single VM monopolizes resources.

E. Multilevel Queue Scheduling

• How it works: Processes are divided into queues (e.g., foreground/background). Each queue has its own scheduling algorithm.
• Example:
  • Foreground (Interactive): RR (q=2)
  • Background (Batch): FCFS

Pros/Cons:

Real-world use:

• WhatsApp messages: High-priority (foreground) messages are processed faster than background sync tasks.

4. Comparison of Algorithms

5. Worked Example: Calculating Metrics

Given:

Algorithm: SJF (Non-Preemptive) Gantt Chart:

gantt
    title SJF Example (Non-Preemptive)
    dateFormat  YYYY-MM-DD
    section CPU
    P2 :a1, 2023-01-01, 3
    P3 :a2, 2023-01-04, 8
    P1 :a3, 2023-01-12, 5
    note right of P2: "Burst=3"
    note right of P3: "Burst=8"
    note right of P1: "Burst=5"

Calculations:

Averages:

• Average Waiting Time = $(0+4+6)/3=3.33$ ms
• Average Turnaround Time = $(5+7+14)/3=8.67$ ms

Real-world tie-in: This is similar to how Daraz order processing might prioritize shorter delivery times (SJF-like) to minimize customer wait times for small orders.

6. Context Switching Overhead

When the CPU switches from one process to another, it incurs overhead:

1. Save state of the current process (registers, program counter).
2. Load state of the next process.
3. Update PCB (Process Control Block).

Example Overhead:

• Time: ~100–10,000 CPU cycles (depends on OS).
• Impact: Too frequent switching (e.g., small quantum in RR) reduces throughput.

7. Real-World Applications

A. Nepali Context

1. eSewa Payments:

   • Uses priority scheduling to process emergency payments (e.g., hospital bills) faster than routine transactions.
   • How: High-priority queue for urgent requests, background queue for scheduled payments.

2. NTC Internet Service:

   • Implements Round Robin for fair bandwidth allocation among users.
   • How: Each user gets a time slice to transmit data, preventing one user from hogging bandwidth.

3. Khalti Transactions:

   • Employs SJF-like logic for microtransactions (e.g., bus tickets) to minimize processing delays.
   • How: Shorter transactions are processed before longer ones (e.g., bulk transfers).

B. Global Context

1. Google Cloud Scheduling:

   • Uses multilevel feedback queues to balance interactive (RR) and batch (FCFS) workloads.
   • How: VMs with high I/O get shorter time quanta; compute-heavy VMs get longer bursts.

2. WhatsApp Message Delivery:

   • Prioritizes real-time messages (priority scheduling) over media uploads (background).
   • How: High-priority queue for chats, low-priority for syncing photos/videos.

3. Air Traffic Control Systems:

   • Uses priority scheduling for emergency landings (highest priority) over routine flights.
   • How: Real-time OS ensures critical tasks preempt others.

8. Exam Tip

What Examiners Look For

1. Gantt Charts:

   • Draw correctly labeled charts for each algorithm (FCFS, SJF, RR, Priority).
   • Common mistake: Forgetting to account for arrival times in SJF.

2. Metric Calculations:

   • Always show step-by-step calculations for turnaround/waiting time.
   • Formula shortcut: $WT=TAT-Burst$.

3. Algorithm Comparison:

   • Use the table format above to compare pros/cons.
   • Key points to mention:
     • FCFS: Simple but convoy effect.
     • SJF: Optimal but starvation.
     • RR: Fair but high overhead.
     • Priority: Flexible but needs careful design.

4. Real-World Scenarios:

   • eSewa/Khalti: Priority scheduling for urgency.
   • Pathao/Daraz: SJF or RR for efficiency.
   • NTC/Google Cloud: Multilevel queues for mixed workloads.

5. Diagrams:

   • Mandatory for full marks:
     • Gantt charts for scheduling traces.
     • State diagrams for process transitions (e.g., ready → running).
     • Avoid: Hand-drawn ASCII tables (use Mermaid).

Common Pitfalls

• Ignoring arrival times: SJF must consider when processes arrive, not just burst times.
• Assuming preemptive = always better: Non-preemptive SJF can be optimal if burst times are known.
• Overcomplicating: Stick to the 4–5 key algorithms (FCFS, SJF, Priority, RR, Multilevel).