Topic 4.1 · CPU Scheduling Algorithms

CPU Scheduling Criteria & Core Performance Metrics

3 min read1 question to test yourself

1Definition

CPU Scheduling is the process by which the short-term operating system scheduler dispatches CPU execution time among processes residing in the ready queue. Scheduling performance is evaluated using metrics including CPU Utilization, Throughput, Turnaround Time (TAT), Waiting Time (WT), Response Time (RT), and Completion Time (CT).

2Simple Explanation

The CPU is the most expensive engine in a computer. The goal of CPU scheduling is to keep that engine operating at 100% capacity without letting any job starve. When multiple processes arrive in memory, the scheduler uses specific rules to decide who gets the CPU next. To measure which rule works best, engineers track how long processes spend waiting in line, how fast they get their first response, and how many jobs finish per minute.

3Real-Life Example / Analogy

A Bank Teller Queue:

  • Arrival Time (AT): The time you walk into the bank lobby.
  • Burst Time (BT): The time it takes the teller to process your cash deposit.
  • Completion Time (CT): The timestamp when you walk out of the bank with your receipt.
  • Turnaround Time (TAT): The total time you spent inside the bank (CT−ATCT - AT).
  • Waiting Time (WT): The time you spent standing in line before reaching the teller (TAT−BTTAT - BT).
  • Throughput: The number of customers the bank teller serves per hour.

4Diagram / Visual Representation

Arrival
AT

Waiting in ready queue
WT

First CPU access
Response time

CPU execution
Burst time (BT)

Completion
CT

Turnaround time = CT − AT

5Working / How It Works

  1. Job Arrival: Process enters Ready Queue at timestamp Arrival Time (AT).
  2. Scheduler Dispatch: Short-term scheduler selects process; CPU touches it for the first time (Response Time reference).
  3. Execution: Process executes for its Burst Time (BT) (may be interrupted).
  4. Termination: Process completes execution at Completion Time (CT).
  5. Metric Calculations:
    • Turnaround Time (TAT)=Completion Time (CT)−Arrival Time (AT)\text{Turnaround Time (TAT)} = \text{Completion Time (CT)} - \text{Arrival Time (AT)}
    • Waiting Time (WT)=Turnaround Time (TAT)−Burst Time (BT)\text{Waiting Time (WT)} = \text{Turnaround Time (TAT)} - \text{Burst Time (BT)}
    • Response Time (RT)=Time of First CPU Access−Arrival Time (AT)\text{Response Time (RT)} = \text{Time of First CPU Access} - \text{Arrival Time (AT)}
    • Throughput=Total Processes CompletedTotal Elapsed Unit Time\text{Throughput} = \frac{\text{Total Processes Completed}}{\text{Total Elapsed Unit Time}}

6Types / Components / Characteristics

  • Primary Optimization Goals:
    • Maximize: CPU Utilization (Keep CPU as busy as possible, ideally 100%) and Throughput.
    • Minimize: Turnaround Time, Waiting Time, and Response Time.
  • Scheduling Modes:
    • Non-Preemptive Scheduling: Once a process gets the CPU, it holds it until termination or manual I/O wait.
    • Preemptive Scheduling: Operating system can forcibly suspend a running process when its time quantum expires or a higher-priority job arrives.

7Solved Examples / Problems

Problem: Given Process P1 with Arrival Time AT = 0 ms, Burst Time BT = 8 ms, and Completion Time CT = 8 ms, calculate its Turnaround Time and Waiting Time. Solution: Turnaround Time (TAT)=CT−AT=8−0=8 ms\text{Turnaround Time (TAT)} = \text{CT} - \text{AT} = 8 - 0 = \mathbf{8 \text{ ms}} Waiting Time (WT)=TAT−BT=8−8=0 ms\text{Waiting Time (WT)} = \text{TAT} - \text{BT} = 8 - 8 = \mathbf{0 \text{ ms}}

8Advantages, Disadvantages & Applications

  • Preemptive Advantages: High system responsiveness, low process starvation.
  • Preemptive Disadvantages: Context-switching overhead; requires hardware timer interrupts.
  • Non-Preemptive Advantages: Simple design, zero context-switch overhead.
  • Non-Preemptive Disadvantages: Convoy effect; long jobs block short jobs.

9Important Points to Remember

  • TAT=CT−AT\text{TAT} = \text{CT} - \text{AT}
  • WT=TAT−BT\text{WT} = \text{TAT} - \text{BT}
  • Non-preemptive algorithms cannot be interrupted once executed.

10Test Your Understanding

  1. MCQ: What is the correct formula to calculate the Waiting Time (WT) of a process?
    • A) WT=Arrival Time−Completion Time\text{WT} = \text{Arrival Time} - \text{Completion Time}
    • B) WT=Turnaround Time−Burst Time\text{WT} = \text{Turnaround Time} - \text{Burst Time}
    • C) WT=Burst Time+Completion Time\text{WT} = \text{Burst Time} + \text{Completion Time}
    • D) WT=Turnaround Time+Arrival Time\text{WT} = \text{Turnaround Time} + \text{Arrival Time}
    Show answer
    B.
  2. Conceptual Question: Define Throughput and explain how it relates to CPU Utilization.
  3. Application Question: Differentiate between Response Time and Waiting Time in interactive multi-user operating systems.

Finished this topic?

0 of 27 topics read in Operating Systems

Handwritten notes for the exam

Unit-wise SPPU notes and PYQs for this subject.

Helpful? Share it with your class

Free for everyone, no login needed.

Share topic