Processor Scheduling

Learning outcomes:

  • Describe the goals and levels of processor scheduling, and compare preemptive and nonpreemptive scheduling
  • Apply scheduling algorithms such as FIFO, shortest job first, and round-robin to a set of processes, and compare their waiting times
  • Explain how priorities, aging, and multilevel feedback queues keep systems responsive and prevent starvation
  • Describe how real-time scheduling works, and how Linux, Windows, and macOS schedule processes today

Would you like to download my PowerPoint to follow along?

  • Scheduling Goals
    • Processor scheduling decides which ready process gets the CPU next, and for how long
    • Common goals:
      • Throughput: finish as much work as possible
      • Low waiting and response times, especially for interactive apps
      • Fairness, and no process waits forever (no starvation)
      • Meet deadlines, for real-time work
      • Keep the CPU busy, with low overhead
      • Predictability: similar jobs take a similar amount of time
    • Different systems weigh these differently. A phone cares about responsiveness and battery, and a supercomputer cares about throughput
  • Types of Schedulers
    • Long-term: decides which jobs get loaded into memory, which controls the degree of multiprogramming
      • On a laptop it barely exists, since every app you open just runs. It lives on in job queues for supercomputers and the cloud, such as Slurm (Slurm Workload Manager: Overview)
    • Medium-term: moves processes out of memory and back again (swapping), covered in Week 11
    • Short-term: picks which ready process runs next on the CPU. This is what most of this week is about
  • Scheduling Levels
    • Diagram: jobs move from waiting for entry, to waiting for initiation (high-level scheduling), to suspended and active (intermediate-level scheduling), to running (low-level scheduling), and then complete
  • Process Activities
    • Every process repeats a cycle:
      • Wait in the ready queue for the CPU
      • Run for its CPU burst, or until its time slice runs out
      • Wait for I/O, or go back to the ready queue
    • When it has no more work to do, it ends
    • CPU-bound processes mostly compute, like a video export. I/O-bound processes mostly wait, like a text editor waiting for you to type
  • Priorities
    • Some kinds of processes get priority over others, such as system processes over background tasks
    • Static priorities never change: simple and low overhead, but they can't react to what's happening
    • Dynamic priorities change as the system runs: more responsive and smoother, for a little more overhead
  • Implementing Dynamic Priority
    • The OS guesses from recent behavior: a process will probably keep doing what it just did
    • Give the CPU to the highest priority process, with a time slice
      • If it stops early to wait for I/O, raise its priority. It's probably interactive
      • If it uses its whole time slice, lower its priority. It's probably CPU-bound
    • This keeps the apps you're using quick, while long jobs still make progress
  • Starvation and Aging
    • Giving some processes priority isn't fair, by design
    • Starvation: a low-priority process waits forever, because higher-priority work keeps arriving
    • Aging: slowly raise a process's priority the longer it waits, until it finally runs
      • Selfish round-robin is one example: waiting processes gain priority until they join the active queue
  • Preemptive vs. Nonpreemptive Scheduling
    • Preemptive: the OS can take the CPU away from a running process
      • Better response times, and needed for interactive systems
    • Nonpreemptive: a process runs until it finishes or gives up the CPU
      • A long or stuck process can block everything else
    • Every modern desktop and phone OS is preemptive
    • Historical note: Windows 3.1 and classic Mac OS used cooperative multitasking, where each app had to give up the CPU on its own, so one frozen app could freeze the whole computer. Still worth knowing because it shows exactly why preemption matters
  • First-In-First-Out (FIFO) Scheduling
    • Processes run in the order they arrive
    • Nonpreemptive, and simple to understand
    • Fair in one sense, since everyone waits their turn, but short jobs get stuck behind long ones
    • Rarely used on its own, but it's part of other schedulers
  • Shortest Job First (SJF)
    • Also called shortest process first (SPF), or shortest process next
    • Runs the process with the shortest next CPU burst first
    • Gives the lowest average waiting time of any nonpreemptive method
    • But it has to guess run times, and those guesses can be wrong, or even faked
    • Long processes can wait a very long time, so it's a poor fit for interactive systems
  • Priority Scheduling
    • Each process gets a priority, and the highest priority ready process runs next
    • Nonpreemptive: a new high-priority process waits for the current one to finish
    • Preemptive: a new high-priority process takes the CPU right away
    • Needs aging, or low-priority processes can starve
  • Highest-Response-Ratio-Next (HRRN)
    • An improvement on shortest job first
    • Looks at both how long a process has waited and how long it needs to run
    • The longer a process waits, the higher its priority, so nothing waits forever
    • Still nonpreemptive
  • Round-Robin (RR) Scheduling
    • Like FIFO, but each process only runs for a short time slice (quantum), usually a few milliseconds
    • When its slice runs out, it goes to the back of the line. The ready queue works like a circle
    • Preemptive, and built for time-sharing systems
    • Picking the time slice:
      • Too long, and it acts just like FIFO
      • Too short, and the system spends more time context switching (Week 2) than running processes
      • Just right: long enough for interactive processes to start their next I/O
  • Shortest-Remaining-Time (SRT) Scheduling
    • The preemptive version of shortest job first
    • A new process with a shorter run time takes the CPU from the running one
    • Long processes wait even longer than with shortest job first
    • Lots of switching adds overhead, and a nearly finished process can get bumped
  • Scheduling Example: The Setup
    • Four processes arrive at time 0, in this order: P1 needs 8 units of CPU time, P2 needs 4, P3 needs 2, and P4 needs 1
    • Waiting time is how long a process sits in the ready queue before it finishes
  • Scheduling Example: Three Schedulers
    • FIFO: P1 runs from 0 to 8, P2 from 8 to 12, P3 from 12 to 14, and P4 from 14 to 15. Waiting times are 0, 8, 12, and 14, so the average wait is 8.5
    • Shortest job first: P4 runs from 0 to 1, P3 from 1 to 3, P2 from 3 to 7, and P1 from 7 to 15. Waiting times are 7, 3, 1, and 0, so the average wait is 2.75
    • Round-robin with a time slice of 2: P1 0 to 2, P2 2 to 4, P3 4 to 6, P4 6 to 7, P1 7 to 9, P2 9 to 11, then P1 11 to 15. Waiting times are P1 7, P2 7, P3 4, and P4 6, so the average wait is 6
  • What the Example Shows
    • FIFO: average wait 8.5. Simple, but the short jobs get stuck behind the long one
    • Shortest job first: average wait 2.75, the best average. But it needs to know run times ahead of time, and long jobs can starve
    • Round-robin: average wait 6. Everyone gets a turn quickly, and every process starts within 6 time units
    • Real schedulers mix these ideas, to be both fast and fair
  • Multilevel Feedback Queues
    • Quick interactive apps should usually run before long background jobs
    • New processes start in the top queue, with the highest priority
    • Processes that use their whole time slice move down a level
    • So short and I/O-bound processes stay near the top, and long jobs sink to the bottom
    • Each level uses round-robin, and the lower levels run when the levels above are empty
    • The scheduler learns about each process from how it behaves, without being told
  • Multilevel Feedback Queue Diagram
    • Diagram: several first-in, first-out queues stacked by priority, with round-robin at the bottom level. A process that is preempted drops to the next queue down
  • Multi-Queue Scheduling
    • The ready queue is split into separate queues by type of process, each with its own scheduling method
    • For example: system processes, interactive apps, and background batch jobs
    • Unlike multilevel feedback queues, processes usually stay in their own queue
  • Fair Share Scheduling
    • Divides the CPU between groups of users or apps, not just individual processes
    • Stops one group from hogging the system, and passes unused time to the others
    • Today on Linux, cgroups do this. They're how containers and cloud servers limit each customer's share of the CPU (Linux kernel documentation: Control Group v2)
  • How Linux Schedules Today
  • How Windows and macOS Schedule
  • Priorities You Can See
    • Linux: nice starts a program with a different priority, and renice changes a running one (Week 2) (Linux manual page: nice)
      • Example: nice -n 10 starts a big job at a lower priority, so it doesn't slow down your desktop
    • top shows each process's priority (PR) and nice value (NI)
    • Windows: Task Manager, Details tab, right-click a process, then Set priority
    • Setting priorities too high can make the rest of the system sluggish, so most of the time, let the OS decide
  • Real-Time Systems
    • A real-time system has to respond within strict time limits
    • It relies on priorities and preemption
    • Examples: a car's airbags and anti-lock brakes, pacemakers, and factory robots
  • Real-Time Scheduling
    • Processes have deadlines, and many run on a regular schedule (periodically)
    • Soft real-time: deadlines are usually met. Missing one is annoying, like a stuttering video call
    • Hard real-time: deadlines must always be met. Missing one can be catastrophic, like in air traffic control or airbags
  • Static Real-Time Scheduling
    • Priorities don't change. Low overhead, and good when conditions rarely change
      • Rate-monotonic: tasks that run more often get higher priority
      • Deadline rate-monotonic: for tasks whose deadline isn't the same as how often they run
  • Dynamic Real-Time Scheduling
    • Priorities change based on deadlines
      • Earliest deadline first (EDF): always run the task whose deadline is soonest
      • Minimum laxity first: run the task with the least spare time, based on its deadline and how much work it has left
    • The extra overhead must never cause a missed deadline
  • Real-Time on Linux

Suggested Activities and Discussion Topics:

  • Activity: pick 4 processes with different run times, and work out the order they would run under FIFO, round-robin, and shortest job first. Which is fairest? Which is fastest?
  • Activity: redo the worked example with round-robin and a time slice of 4. How does the average waiting time change? What about a time slice of 1?
  • Activity: on a Linux system or virtual machine, run a CPU-heavy command twice at the same time, one normally and one with nice -n 19 in front of it. Watch them in top. Which one gets more CPU time?
  • Activity: on Windows 11, open Task Manager, right-click a background app, and turn on Efficiency mode. What changes in its status? Why might Microsoft have added this?
  • Discussion: Windows 3.1 and classic Mac OS used cooperative multitasking. What would it be like to use a computer today where one frozen app could freeze everything?

Would you like to see some more classes? Click here