Unit 3: CPU Scheduling

Opening Hook — The 60-Second Window That Breaks India's Internet

Learning Outcomes — Bloom's Taxonomy Mapped

Concept Explanation — CPU Scheduling Algorithms with Full Numericals

1. Scheduling Criteria & Key Formulas

The CPU scheduler decides which process in the ready queue gets the CPU next. But how do we measure if a scheduling algorithm is "good"? We use these five criteria:

TAT = Completion Time (CT) − Arrival Time (AT)

WT = TAT − Burst Time (BT)
   = CT − AT − BT

RT = First CPU Time − Arrival Time (AT)

2. Preemptive vs Non-Preemptive Scheduling

3. The Dispatcher

The dispatcher is the module that gives control of the CPU to the process selected by the scheduler. It performs:

• Context switching — saving the state of the old process and loading the state of the new process
• Switching to user mode from kernel mode
• Jumping to the proper location in the user program to resume execution

Dispatch Latency = time the dispatcher takes to stop one process and start another. This should be as small as possible (typically microseconds). Every context switch incurs dispatch latency — this is why too many context switches (e.g., tiny RR quantum) hurt performance.

4. Algorithm 1: FCFS (First Come First Served)

Concept: The simplest scheduling algorithm. Processes are executed in the order they arrive. It is non-preemptive — once a process gets the CPU, it runs to completion.

Implementation: FIFO queue. New processes go to the back. The process at the front gets the CPU.

✏️ Worked Example: FCFS

5. Algorithm 2: SJF (Shortest Job First — Non-Preemptive)

Concept: Among all processes in the ready queue, select the one with the smallest burst time. It is provably optimal for minimizing average waiting time among non-preemptive algorithms.

Problem: We can't always know the burst time in advance (prediction needed). Also causes starvation — long processes may never get CPU if short processes keep arriving.

✏️ Worked Example: SJF (Non-Preemptive)

6. Algorithm 3: SRTF (Shortest Remaining Time First — Preemptive SJF)

Concept: The preemptive version of SJF. Whenever a new process arrives, compare its burst time with the remaining time of the currently running process. If the new process has a shorter remaining time, preempt the current process.

SRTF is provably optimal — it gives the minimum possible average waiting time among all scheduling algorithms.

✏️ Worked Example: SRTF (Same processes as SJF for comparison)

7. Algorithm 4: Priority Scheduling

Concept: Each process is assigned a priority number. The CPU is allocated to the process with the highest priority. Convention: lower number = higher priority (in most textbooks and this chapter).

Can be preemptive (new high-priority process preempts current) or non-preemptive (current process finishes first).

✏️ Worked Example: Priority Scheduling (Non-Preemptive)

✏️ Worked Example: Priority Scheduling (Preemptive)

Starvation & Aging

Starvation: Low-priority processes may wait indefinitely if high-priority processes keep arriving. In the example above, P5 (pri=5) waits until t=13!

Aging: The solution — gradually increase the priority of waiting processes. For example, increase priority by 1 every 15 minutes. Eventually, even the lowest-priority process becomes the highest.

8. Algorithm 5: Round Robin (RR)

Concept: Each process gets a fixed time quantum (time slice). After the quantum expires, the process is preempted and placed at the back of the ready queue. The next process in the queue gets the CPU. This is the most widely used algorithm for time-sharing systems.

Key Design Decision: Quantum size matters enormously:

• Too small (e.g., 1ms) → too many context switches → overhead dominates
• Too large (e.g., 100ms) → degenerates into FCFS
• Rule of thumb: 80% of CPU bursts should be shorter than the quantum

✏️ Worked Example: Round Robin with Quantum = 2

✏️ Worked Example: Round Robin with Quantum = 4 (Same Processes)

Impact of Quantum Size — Comparison

In this example, q=4 happens to give slightly better Avg WT, but with fewer context switches. However, for interactive systems, smaller quantum gives better response time for newly arriving processes.

9. Algorithm 6: Multilevel Queue Scheduling

Concept: The ready queue is divided into multiple separate queues, each with its own scheduling algorithm. Processes are permanently assigned to a queue based on their type.

10. Algorithm 7: Multilevel Feedback Queue Scheduling (MLFQ)

Key difference from Multilevel Queue: Processes can move between queues! This is the most sophisticated and flexible scheduling algorithm.

11. Multiprocessor Scheduling

When there are multiple CPUs, scheduling becomes more complex:

12. Real-Time Scheduling

Hard Real-Time: Deadlines MUST be met (pacemakers, ABS brakes). Missing a deadline = system failure.

Soft Real-Time: Deadlines are preferred but not absolute (video streaming, gaming).

13. Thread Scheduling

Modern systems (Linux, Windows) use SCS — every thread is a kernel thread, scheduled by the OS.

Learn by Doing — 3-Tier Lab Structure

Python
def fcfs(processes):
    """First Come First Served Scheduling"""
    # Sort by arrival time, then by process id
    procs = sorted(processes, key=lambda x: (x['at'], x['pid']))
    time = 0
    gantt = []
    results = []
    
    for p in procs:
        if time < p['at']:
            time = p['at']  # CPU idle until process arrives
        start = time
        time += p['bt']
        ct = time
        tat = ct - p['at']
        wt = tat - p['bt']
        gantt.append((p['pid'], start, ct))
        results.append({'pid': p['pid'], 'at': p['at'], 'bt': p['bt'],
                        'ct': ct, 'tat': tat, 'wt': wt})
    return gantt, results


def sjf_non_preemptive(processes):
    """Shortest Job First (Non-Preemptive)"""
    procs = [p.copy() for p in processes]
    n = len(procs)
    done = [False] * n
    time = 0
    gantt = []
    results = []
    completed = 0
    
    while completed < n:
        # Find available processes (arrived and not done)
        available = [(i, p) for i, p in enumerate(procs)
                     if not done[i] and p['at'] <= time]
        if not available:
            time += 1
            continue
        # Pick shortest burst time (tie-break by arrival)
        idx, p = min(available, key=lambda x: (x[1]['bt'], x[1]['at']))
        start = time
        time += p['bt']
        ct = time
        tat = ct - p['at']
        wt = tat - p['bt']
        gantt.append((p['pid'], start, ct))
        results.append({'pid': p['pid'], 'at': p['at'], 'bt': p['bt'],
                        'ct': ct, 'tat': tat, 'wt': wt})
        done[idx] = True
        completed += 1
    return gantt, results


def round_robin(processes, quantum):
    """Round Robin Scheduling"""
    from collections import deque
    procs = sorted([p.copy() for p in processes], key=lambda x: x['at'])
    n = len(procs)
    remaining = {p['pid']: p['bt'] for p in procs}
    ct_map = {}
    time = 0
    gantt = []
    queue = deque()
    idx = 0  # next process to arrive
    
    # Add first process
    if procs:
        time = procs[0]['at']
        queue.append(procs[0]['pid'])
        idx = 1
    
    while queue:
        pid = queue.popleft()
        exec_time = min(quantum, remaining[pid])
        start = time
        time += exec_time
        remaining[pid] -= exec_time
        gantt.append((pid, start, time))
        
        # Add newly arrived processes
        while idx < n and procs[idx]['at'] <= time:
            queue.append(procs[idx]['pid'])
            idx += 1
        
        if remaining[pid] > 0:
            queue.append(pid)  # Not finished, back to queue
        else:
            ct_map[pid] = time  # Finished!
        
        # If queue empty but processes remain
        if not queue and idx < n:
            time = procs[idx]['at']
            queue.append(procs[idx]['pid'])
            idx += 1
    
    results = []
    for p in procs:
        ct = ct_map[p['pid']]
        tat = ct - p['at']
        wt = tat - p['bt']
        results.append({'pid': p['pid'], 'at': p['at'], 'bt': p['bt'],
                        'ct': ct, 'tat': tat, 'wt': wt})
    return gantt, results


def print_results(algo_name, gantt, results):
    print(f"\n{'='*50}")
    print(f"  {algo_name}")
    print(f"{'='*50}")
    
    # Gantt Chart
    print("\nGantt Chart:")
    chart = "| "
    times = ""
    for pid, start, end in gantt:
        width = max(4, (end - start) * 2)
        chart += f"{pid}".center(width) + "| "
    print(chart)
    
    # Timeline
    time_line = ""
    for pid, start, end in gantt:
        width = max(4, (end - start) * 2) + 2
        time_line += str(start).ljust(width)
    time_line += str(gantt[-1][2])
    print(time_line)
    
    # Results Table
    print(f"\n{'Process':<10}{'AT':<6}{'BT':<6}{'CT':<6}{'TAT':<6}{'WT':<6}")
    print("-" * 40)
    total_wt, total_tat = 0, 0
    for r in results:
        print(f"{r['pid']:<10}{r['at']:<6}{r['bt']:<6}{r['ct']:<6}{r['tat']:<6}{r['wt']:<6}")
        total_wt += r['wt']
        total_tat += r['tat']
    n = len(results)
    print(f"\nAvg WT  = {total_wt}/{n} = {total_wt/n:.2f}")
    print(f"Avg TAT = {total_tat}/{n} = {total_tat/n:.2f}")


# ── Main Program ──
if __name__ == "__main__":
    processes = [
        {'pid': 'P1', 'at': 0, 'bt': 5},
        {'pid': 'P2', 'at': 1, 'bt': 3},
        {'pid': 'P3', 'at': 2, 'bt': 1},
        {'pid': 'P4', 'at': 3, 'bt': 2},
        {'pid': 'P5', 'at': 4, 'bt': 3},
    ]
    
    g, r = fcfs(processes)
    print_results("FCFS (First Come First Served)", g, r)
    
    g, r = sjf_non_preemptive(processes)
    print_results("SJF (Shortest Job First - Non-Preemptive)", g, r)
    
    g, r = round_robin(processes, quantum=2)
    print_results("Round Robin (Quantum = 2)", g, r)

Industry Spotlight — A Day in the Life

Earn With It — Freelance & Income Roadmap

⏱️ Time to First Earning: 3–4 weeks (complete Tier 1 + Tier 3 labs, build GitHub portfolio, apply on Internshala)

MCQ Assessment Bank — 30 Questions (Bloom's Mapped)

Remember / Identify (Q1–Q5)

Understand / Explain (Q6–Q10)

Apply — Numerical Problems (Q11–Q20)

Analyze / Compare (Q21–Q25)

Evaluate / Create (Q26–Q30)

Short Answer Questions

Q1. Compare FCFS and SJF scheduling algorithms with an example. Which gives better average waiting time?

Answer: FCFS (First Come First Served) executes processes in arrival order — simple but suffers from the convoy effect. SJF (Shortest Job First) selects the process with the smallest burst time — optimal for non-preemptive scheduling.

Example: Processes: P1(AT=0, BT=6), P2(AT=0, BT=2), P3(AT=0, BT=8).

FCFS: Order P1→P2→P3. WT: P1=0, P2=6, P3=8. Avg WT = 14/3 = 4.67.

SJF: Order P2→P1→P3. WT: P2=0, P1=2, P3=8. Avg WT = 10/3 = 3.33.

SJF always gives ≤ FCFS average waiting time. However, SJF requires knowing burst times in advance and may cause starvation for long processes.

Q2. What is the convoy effect? Illustrate with an example.

Answer: The convoy effect occurs in FCFS scheduling when a long CPU-bound process arrives before several short processes. All short processes must wait for the long process to complete, creating a "convoy" of waiting processes — similar to slow trucks blocking fast cars on a highway.

Example: P1(AT=0, BT=100), P2(AT=1, BT=2), P3(AT=2, BT=1). With FCFS: P2 waits 99ms and P3 waits 100ms for their 2ms and 1ms jobs! Avg WT = (0+99+100)/3 = 66.33ms. If we used SJF after P1 finishes (since P1 arrived first and started first), we'd still have the convoy. The fundamental issue: FCFS doesn't consider burst time.

Q3. Explain starvation and aging in the context of priority scheduling.

Answer: Starvation occurs when a low-priority process waits indefinitely because higher-priority processes keep arriving and getting the CPU. In priority scheduling, if a process with priority=10 (low) is waiting while processes with priority=1 (high) keep entering the system, the low-priority process may never execute.

Aging is the solution: the OS gradually increases the priority of waiting processes over time. For example, every 15 minutes, increase priority by 1. A process with initial priority=10 will become priority=9 after 15 minutes, priority=8 after 30 minutes, and so on. Eventually, it reaches priority=1 and gets scheduled. This guarantees every process will eventually execute, preventing starvation while still respecting priorities.

Q4. How does the choice of time quantum affect Round Robin performance?

Answer:

Too Small Quantum (e.g., 1ms): Frequent context switches → high overhead (dispatch latency accumulates). Most CPU time is spent switching rather than executing useful work. Throughput drops.

Too Large Quantum (e.g., 1000ms): Degenerates into FCFS — each process finishes within one quantum. Loses the advantage of time-sharing. Response time increases for interactive users.

Optimal Quantum: Rule of thumb — 80% of CPU bursts should be shorter than the quantum. Typical values: 10–100ms. Linux CFS uses dynamic quanta based on system load. A well-tuned quantum balances response time (good for interactive users) with throughput (minimal context switch overhead).

Q5. Compare Multilevel Queue and Multilevel Feedback Queue scheduling.

Answer:

MLFQ is preferred for general-purpose OS because it automatically classifies processes based on behavior without requiring prior knowledge of process types.

Case Studies

Chapter Summary

Earning Checkpoint — What Can You Do Now?

✅ Unit 3 complete. Numerical problems included: 10+. MCQs: 30. Ready for Unit 4!

[QR: Link to EduArtha video tutorial — CPU Scheduling Algorithms]