Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 66 ยท CPU Scheduling

CPU Scheduling Basics

Learn what CPU scheduling is, the CPU-I/O burst cycle, preemptive vs non-preemptive scheduling and the criteria (throughput, turnaround, waiting, response), with a metrics calculator.

When several processes are ready to run and there is only one CPU, someone has to choose which one goes next. That choice is CPU scheduling, and the OS component that makes it is the CPU scheduler. A good scheduling policy keeps the CPU busy, finishes jobs quickly, and keeps interactive programs responsive. A bad one makes the system feel sluggish or lets some programs wait forever.

This lesson sets up the vocabulary for the whole chapter: the CPU-I/O burst cycle, the different schedulers, preemptive and non-preemptive scheduling, and the performance criteria with their formulas. You will build a small calculator for those formulas that every later lesson (FCFS and SJF, priority, round robin) uses.

Scheduling in one picture

Ready queue Processes waiting for the CPU.
Scheduler Picks one using a policy.
CPU Runs the chosen process.

The policy is the scheduling algorithm.

1 / 2

The CPU-I/O burst cycle

Processes alternate between using the CPU and waiting for I/O. A CPU burst is a stretch of computation; an I/O burst is a stretch of waiting. Execution starts with a CPU burst, then an I/O burst, then another CPU burst, and so on until the process ends.

Measurements of real programs show a typical pattern: many short CPU bursts and a few long ones. I/O-bound programs (editors, browsers) have lots of short bursts; CPU-bound programs (video encoding) have a few long ones. A scheduler should favor short bursts, so that interactive programs respond quickly while CPU-bound ones fill the gaps.

Three levels of scheduling

Scheduler Also called Decides Runs
Long-term Job scheduler Which new jobs are admitted into memory Rarely (seconds to minutes)
Medium-term Swapper Which processes to swap out and back in Occasionally
Short-term CPU scheduler Which ready process gets the CPU next Very often (milliseconds)

When people say "the scheduler" they almost always mean the short-term one, which must be fast because it runs on every scheduling decision. The long-term scheduler controls the degree of multiprogramming and balances CPU-bound and I/O-bound jobs. The medium-term scheduler is used where memory is tight, swapping processes to disk (suspended states).

When does the scheduler run?

A scheduling decision may be needed when a process:

  1. goes from running to waiting (I/O request),
  2. goes from running to ready (timer interrupt),
  3. goes from waiting to ready (I/O completes),
  4. terminates.

If scheduling happens only in cases 1 and 4, the scheduling is non-preemptive (cooperative): once a process has the CPU, it keeps it until it blocks or finishes. If it can also happen in 2 and 3, it is preemptive: the OS can take the CPU away.

Non-preemptive Preemptive
CPU taken away? Never, until the process yields or ends Yes, on timer or arrival of a better process
Overhead Low Higher (more context switches)
Response time Can be poor Better
Risk One long job blocks everyone Shared-data races if preempted mid-update
Examples FCFS, SJF Round robin, SRTF, preemptive priority

Modern general-purpose OSes are preemptive. Non-preemptive scheduling still appears in simple embedded systems and in the theory of algorithms.

The dispatcher

The dispatcher is the module that actually gives the CPU to the process the scheduler chose: it performs the context switch, switches to user mode and jumps to the right instruction. The time it takes is the dispatch latency. More about the dispatcher in Starvation, Aging and Schedulers.

Scheduling criteria

For a process with arrival time AT, burst time BT (total CPU time needed), first start time and completion time CT:

  • CPU utilization: percentage of time the CPU is busy. Aim: 40% (light) to 90% (heavy load).
  • Throughput: number of processes completed per time unit.
  • Turnaround time (TAT) = CT - AT. Everything from submission to completion.
  • Waiting time (WT) = TAT - BT. Total time in the ready queue.
  • Response time (RT) = first start - AT. Time until the first response; it matters most for interactive work.

The goal is usually to maximize utilization and throughput and minimize turnaround, waiting and response times. These goals conflict (optimizing average waiting time may hurt fairness), so each algorithm makes a different choice. In practice we look at the average, and sometimes the maximum or variance, because users prefer predictable response.

A reusable metrics calculator

A schedule can be described as a Gantt chart: a timeline of which process ran when. The helper below takes the list of processes and a Gantt list of (name, start, end) segments, prints the table of metrics and the averages. The later lessons build their algorithms on the same idea.

Python Scheduling metrics calculator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check one row by hand: process C arrives at 2, needs 2 units, and finishes at 16. Turnaround is 16 - 2 = 14, waiting time 14 - 2 = 12, and it first ran at 14, so response time is 12. The tiny job C waited behind a long one, which is exactly the problem the next lessons try to solve.

Visualizing the ready queue

The simulation below shows the ready queue at each moment of a non-preemptive run, so you can see which processes are waiting while another one runs.

Python Watching the ready queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which criteria matter when?

System Priority goal
Desktop / phone Low response time and consistency
Server Throughput, fairness between clients
Batch / HPC Throughput and utilization
Real-time Meeting deadlines (real-time scheduling)

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A process arrives at time 3, needs 5 units of CPU, and finishes at time 20. What is its waiting time?

    Turnaround = 20 - 3 = 17. Waiting = turnaround - burst = 17 - 5 = 12.
  2. 2. Which scheduler is invoked most frequently?

    The short-term scheduler picks the next process every few milliseconds, so it must be very fast.
  3. 3. What distinguishes preemptive from non-preemptive scheduling?

    In preemptive scheduling the OS may interrupt the running process; in non-preemptive scheduling it keeps the CPU until it blocks or ends.
  4. 4. Which criterion is most important for an interactive program?

    Users notice how quickly the system reacts, which is response time.
  5. 5. Response time is defined as

    It measures the delay until the process first gets the CPU.

Summary

  • CPU scheduling picks which ready process runs next; processes alternate between CPU bursts and I/O bursts.
  • Long-term, medium-term and short-term schedulers work at different time scales.
  • Preemptive scheduling can reclaim the CPU; non-preemptive scheduling cannot.
  • Key formulas: TAT = CT - AT, WT = TAT - BT, RT = first run - AT.
  • A Gantt chart records a schedule and is the input to all metrics.

Next: FCFS and SJF Scheduling