CPU Scheduling Algorithms & Performance Metrics

TAKEAWAYS:

• CPU scheduling determines process execution order, balancing fairness and efficiency.
• FCFS is simple but can starve long processes; SJF minimizes wait time but requires burst-time prediction.
• Round Robin (RR) uses a time quantum to ensure fairness, but high overhead for small quantum.
• Priority scheduling can lead to starvation; aging mitigates this by gradually increasing priority.
• Disk scheduling (e.g., SSTF, SCAN) optimizes I/O performance, reducing seek time.
• Real-world systems (e.g., Ncell call queues, Daraz order processing) use hybrid scheduling.

1. Introduction to CPU Scheduling

CPU scheduling is the mechanism by which the OS selects a process from the ready queue to allocate the CPU. It ensures:

• Fairness: All processes get CPU time.
• Efficiency: Maximizes CPU utilization.
• Responsiveness: Short jobs complete quickly.

Key Terms:

• Ready Queue: Processes waiting for CPU time.
• Turnaround Time (TAT): Time from submission to completion.
• Waiting Time: Time a process spends in the ready queue.
• Response Time: Time until the first I/O or output.

2. CPU Scheduling Algorithms

2.1 First-Come First-Served (FCFS)

How it works:

• Processes execute in arrival order.
• No preemption; once a process starts, it runs to completion.

Example:

sequenceDiagram
    participant P1 as P1 (arrives at 0, BT=6)
    participant P2 as P2 (arrives at 1, BT=4)
    participant P3 as P3 (arrives at 2, BT=5)
    P1->>P1: Runs 6ms (0-6)
    P2->>P2: Runs 4ms (6-10)
    P3->>P3: Runs 5ms (10-15)

Performance:

Advantages:

• Simple to implement.
• No overhead for context switching.

Disadvantages:

• Convoy Effect: Short processes wait behind long ones.
• Unfair to short jobs.

Real-world use:

• Ncell call queues: Calls are handled in arrival order (FCFS-like).

2.2 Shortest Job First (SJF)

How it works:

• Selects the process with the shortest burst time next.
• Non-preemptive (SJF): Once started, runs to completion.
• Preemptive (SRTF): Switches to shorter jobs if one arrives.

Example (Non-preemptive SJF):

sequenceDiagram
    participant P1 as P1 (arrives at 0, BT=6)
    participant P2 as P2 (arrives at 1, BT=4)
    participant P3 as P3 (arrives at 2, BT=5)
    note right of P2: Shortest job at arrival
    P2->>P2: Runs 4ms (1-5)
    P1->>P1: Runs 6ms (5-11)
    P3->>P3: Runs 5ms (11-16)

Performance:

Advantages:

• Minimizes average waiting time.
• Optimal for offline scheduling (if burst times are known).

Disadvantages:

• Starvation: Long jobs may never run.
• Requires burst-time prediction (hard in real-time systems).

Real-world use:

• Pathao driver dispatch: Shortest ride requests are prioritized.

2.3 Round Robin (RR)

How it works:

• Each process gets a time quantum (q).
• If not completed, moves to the end of the queue.
• Preemptive: CPU is stolen from processes.

Example (q=2ms):

sequenceDiagram
    participant P1 as P1 (arrives at 0, BT=6)
    participant P2 as P2 (arrives at 1, BT=4)
    participant P3 as P3 (arrives at 2, BT=5)
    P1->>P1: Runs 2ms (0-2)
    P2->>P2: Runs 2ms (2-4)
    P1->>P1: Runs 2ms (4-6)
    P3->>P3: Runs 2ms (6-8)
    P2->>P2: Runs 2ms (8-10)
    P1->>P1: Runs 2ms (10-12)
    P3->>P3: Runs 2ms (12-14)
    P3->>P3: Runs 1ms (14-15)

Performance:

Advantages:

• Fairness: All processes get CPU time.
• Responsive to interactive jobs (e.g., terminals).

Disadvantages:

• Overhead: Frequent context switches for small q.
• Starvation: Long jobs may take too long to complete.

Choosing q:

• Too small → high overhead.
• Too large → loses fairness (like FCFS).

Real-world use:

• WhatsApp message delivery: Messages are processed in small batches (RR-like).

2.4 Priority Scheduling

How it works:

• Processes assigned priorities (higher number = higher priority).
• Preemptive: Higher-priority processes preempt lower ones.
• Non-preemptive: Runs to completion.

Example (Preemptive):

sequenceDiagram
    participant P1 as P1 (arrives at 0, BT=8, Priority=3)
    participant P2 as P2 (arrives at 1, BT=4, Priority=1)
    participant P3 as P3 (arrives at 2, BT=5, Priority=2)
    P1->>P1: Runs 1ms (0-1)
    P3->>P3: Runs 2ms (1-3) [higher priority]
    P3->>P3: Runs 3ms (3-6)
    P2->>P2: Runs 4ms (6-10)
    P1->>P1: Runs 7ms (10-17)

Performance:

Advantages:

• Critical processes (e.g., real-time systems) get priority.

Disadvantages:

• Starvation: Low-priority processes may never run.
• Solution: Aging – Gradually increase priority of waiting processes.

Real-world use:

• NEPSE stock trading: High-priority orders (e.g., market makers) execute first.

3. Multilevel Queue Scheduling

How it works:

• Processes are divided into queues (e.g., foreground/background).
• Each queue uses a different scheduling algorithm (e.g., RR for interactive, FCFS for batch).
• Fixed priority: Foreground always higher than background.

Example:

• Foreground Queue (RR, q=1ms): Interactive jobs (e.g., terminals).
• Background Queue (FCFS): Batch jobs (e.g., compilers).

Advantages:

• Balances responsiveness and throughput.

Disadvantages:

• Starvation: Background jobs may wait indefinitely.

4. Multilevel Feedback Queue (MFQ)

How it works:

• Processes move between queues based on CPU usage.
• New processes start in the highest-priority queue (RR).
• If a process uses too much CPU, it moves to a lower-priority queue (FCFS).

Example:

1. Process starts in Queue 0 (RR, q=8ms).
2. If it uses >8ms, moves to Queue 1 (RR, q=16ms).
3. If it uses >16ms, moves to Queue 2 (FCFS).

Advantages:

• Adaptive: Short jobs stay in high-priority queues.
• Fair: Long jobs eventually get CPU time.

Disadvantages:

• Complex to implement.

Real-world use:

• Google’s search indexing: Short tasks (e.g., caching) get priority; long tasks (e.g., indexing) run in background.

5. Disk Scheduling Algorithms

Disk scheduling optimizes seek time (time to move the read/write head).

5.1 Shortest Seek Time First (SSTF)

• Selects the request closest to the current head position.
• Example:
  • Current head: 143
  • Queue: [25, 17, 119, 197, 194, 15, 182, 115, 183]
  • Order: 119 → 115 → 182 → 183 → 194 → 197 → 25 → 17 → 15
  • Total Seek Time: 34 + 67 + 3 + 1 + 13 + 23 + 168 + 8 + 2 = 317

Disadvantages:

• Starvation: Requests far from the head may never be served.

5.2 SCAN (Elevator Algorithm)

• Head moves in one direction, servicing requests until the end, then reverses.
• Example:
  • Current head: 45
  • Queue: [88, 72, 13, 74, 48, 9, 22, 50, 35]
  • Order: 48 → 50 → 72 → 74 → 88 → 35 → 22 → 13 → 9
  • Total Seek Time: 3 + 2 + 22 + 2 + 16 + 43 + 37 + 9 + 13 = 145

Advantages:

• Balanced seek time; no starvation.

5.3 C-SCAN (Circular SCAN)

• Head moves in one direction, then jumps to the other end and repeats.
• Example:
  • Current head: 45
  • Queue: [88, 72, 13, 74, 48, 9, 22, 50, 35]
  • Order: 48 → 50 → 72 → 74 → 88 → 0 → 9 → 13 → 22 → 35
  • Total Seek Time: 3 + 2 + 22 + 2 + 14 + 88 + 9 + 4 + 9 + 13 = 162

Advantages:

• Fairer than SCAN; no long waits at the end.

Real-world use:

• NTC’s fiber-optic routing: SCAN-like scheduling to minimize signal delays.

6. Performance Metrics Comparison

7. Exam Tip

• Focus on:
  1. Calculating TAT/waiting time for FCFS, SJF, RR (practice past papers).
  2. Comparing algorithms (trade-offs: fairness vs. efficiency).
  3. Disk scheduling (SSTF vs. SCAN vs. C-SCAN; calculate seek time).
  4. Real-world examples (e.g., "How does Pathao use SJF?").
• Common mistakes:
  • Forgetting to update remaining burst time in SRTF.
  • Misapplying time quantum in RR (e.g., counting partial quantum).
  • Ignoring arrival times in priority scheduling.
• Formula reminder:
  • TAT = Waiting Time + Burst Time
  • Avg. Waiting Time = Σ(Waiting Time) / Number of Processes

In the Real World

1. Ncell Call Queues:

   • Uses FCFS for incoming calls (first come, first served).
   • Problem: Long calls block shorter ones (convoy effect).

2. Daraz Order Processing:

   • Priority scheduling: Urgent orders (e.g., same-day delivery) get higher priority.
   • Aging: Orders waiting too long get priority boosts.

3. Google’s Borg System:

   • Uses multilevel feedback queues to balance short-lived tasks (e.g., caching) and long-running jobs (e.g., machine learning).

Worked Example: Hybrid Scheduling (Bank Loan Approvals)

Scenario: A bank uses a hybrid scheduler for loan approvals:

• Foreground Queue (RR, q=1 hour): Urgent loans (e.g., home loans).
• Background Queue (FCFS): Standard loans (e.g., personal loans).

Processes:

Trace:

1. 0-1: L1 runs (urgent).
2. 1-2: L2 runs (standard, RR quantum=1hr).
3. 2-4: L3 runs (urgent).
4. 4-8: L4 runs (standard, FCFS).

Performance:

Key Takeaway:

• Urgent loans get priority but don’t starve standard loans.
• Aging: If a standard loan waits >4hrs, it gets priority.