CPU Scheduling

Before we start

Why this matters

Chapter 5 · Lectures 15–18

Outline

Select a topic to jump to the slide that explains it.

1. Basic concepts
2. Scheduling criteria
3. Scheduling algorithms
4. Algorithm evaluation

Basic concepts

Basic concepts

• Maximum CPU utilization obtained with multiprogramming
• CPU–I/O burst cycle – process execution consists of a cycle of CPU execution and I/O wait
• CPU burst followed by I/O burst
• CPU burst distribution is of main concern

Basic concepts

Basic concepts (cont.)

Basic concepts

Histogram of CPU-burst times

• Large number of short bursts
• Small number of longer bursts

Basic concepts

Histogram of CPU-burst times (cont.)

Basic concepts

CPU scheduler

• The CPU scheduler selects from among the processes in ready queue, and allocates a CPU core to one of them
  • Queue may be ordered in various ways
• CPU scheduling decisions may take place when a process:
  • 1. Switches from running to waiting state
  • 2. Switches from running to ready state
  • 3. Switches from waiting to ready
  • 4. Terminates
• For situations 1 and 4, there is no choice in terms of scheduling. A new process (if one exists in the ready queue) must be selected for execution.
• For situations 2 and 3, however, there is a choice.

Basic concepts

Preemptive and nonpreemptive scheduling

• When scheduling takes place only under circumstances 1 and 4, the scheduling scheme is nonpreemptive.
• Otherwise, it is preemptive.
• Under nonpreemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it releases it either by terminating or by switching to the waiting state.
• Virtually all modern operating systems including Windows, MacOS, Linux, and UNIX use preemptive scheduling algorithms.

Basic concepts

Preemptive scheduling and race conditions

• Preemptive scheduling can result in race conditions when data are shared among several processes.
• Consider the case of two processes that share data. While one process is updating the data, it is preempted so that the second process can run. The second process then tries to read the data, which are in an inconsistent state.
• This issue will be explored in detail in Chapter 6.

Scheduling criteria

Scheduling criteria

FCFS

First-come, first-served (FCFS) scheduling

FCFS

FCFS scheduling (cont.)

Code and output

FCFS in C

#include <stdio.h>

int main(void)
{
    char *name[] = {"P1", "P2", "P3"};
    int burst[]  = {24, 3, 3};          /* all arrive at time 0, in this order */
    int n = 3, t = 0, total = 0;

    printf("Process  Burst  Waiting  Turnaround\n");
    for (int i = 0; i < n; i++) {
        int wait = t;                   /* FCFS: waits for everyone before it */
        t += burst[i];

Code and output

FCFS in C (cont.)

        total += wait;
        printf("%-7s  %5d  %7d  %10d\n", name[i], burst[i], wait, t);
    }
    printf("Average waiting time = %.2f\n", (double)total / n);
    return 0;
}

$ gcc fcfs.c -o fcfs -pthread && ./fcfs
Process  Burst  Waiting  Turnaround
P1          24        0          24
P2           3       24          27
P3           3       27          30
Average waiting time = 17.00

Each process waits for the bursts of everyone before it: the same 0, 24, 27 and average 17 as the Gantt chart.

SJF

Shortest-job-first (SJF) scheduling

• Associate with each process the length of its next CPU burst
  • Use these lengths to schedule the process with the shortest time
• SJF is optimal – gives minimum average waiting time for a given set of processes
• Preemptive version called shortest-remaining-time-first
• How do we determine the length of the next CPU burst?
  • Could ask the user
  • Estimate

SJF

Example of SJF

SJF

Example of SJF (cont.)

SRTF

Example of shortest-remaining-time-first

Round robin

Round robin (RR)

• Each process gets a small unit of CPU time (time quantum q), usually 10–100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.
• If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n − 1)q time units.
• Timer interrupts every quantum to schedule next process
• Performance
  • q large → FIFO
  • q small → q must be large with respect to context switch, otherwise overhead is too high

Round robin

Example of RR with time quantum = 4

Round robin

Example of RR with time quantum = 4 (cont.)

The Gantt chart is:

Round robin

Time quantum and context switch time

Priority

Priority scheduling

• A priority number (integer) is associated with each process
• The CPU is allocated to the process with the highest priority (smallest integer → highest priority)
  • Preemptive
  • Nonpreemptive
• SJF is priority scheduling where priority is the inverse of predicted next CPU burst time
• Problem → starvation – low priority processes may never execute
• Solution → aging – as time progresses increase the priority of the process

Priority

Example of priority scheduling

Priority

Priority scheduling with round-robin

Animated

Watch the scheduler run

Multilevel queue

Multilevel queue

• With priority scheduling, have separate queues for each priority.
• Schedule the process in the highest-priority queue!

Multilevel queue

Multilevel queue (cont.)

Multilevel queue

Multilevel queue (cont.)

Prioritization based upon process type:

Multilevel queue

Multilevel queue (cont.)

Multilevel feedback queue

Multilevel feedback queue

• A process can move between the various queues.
• Multilevel-feedback-queue scheduler defined by the following parameters:
  • Number of queues
  • Scheduling algorithms for each queue
  • Method used to determine when to upgrade a process
  • Method used to determine when to demote a process
  • Method used to determine which queue a process will enter when that process needs service
• Aging can be implemented using multilevel feedback queue

Multilevel feedback queue

Example of multilevel feedback queue

• Three queues:
  • Q0 – RR with time quantum 8 milliseconds
  • Q1 – RR time quantum 16 milliseconds
  • Q2 – FCFS
• Scheduling
  • A new process enters queue Q0 which is served in RR
    • When it gains CPU, the process receives 8 milliseconds
    • If it does not finish in 8 milliseconds, the process is moved to queue Q1
  • At Q1 job is again served in RR and receives 16 additional milliseconds
    • If it still does not complete, it is preempted and moved to queue Q2

Multilevel feedback queue

Example of multilevel feedback queue (cont.)

Interactive

Run the multilevel feedback queue

Algorithm evaluation

Algorithm evaluation

Algorithm evaluation

Deterministic evaluation

• For each algorithm, calculate minimum average waiting time
• Simple and fast, but requires exact numbers for input, applies only to those inputs
• FCFS is 28 ms, non-preemptive SJF is 13 ms, RR (q = 10) is 23 ms:

Algorithm evaluation

Deterministic evaluation (cont.)

Algorithm evaluation

Queueing models and Little’s formula

• Describes the arrival of processes, and CPU and I/O bursts probabilistically
  • Commonly exponential, and described by mean
  • Computes average throughput, utilization, waiting time, etc.
• Computer system described as network of servers, each with queue of waiting processes
  • Knowing arrival rates and service rates
  • Computes utilization, average queue length, average wait time, etc.
• n = average queue length; W = average waiting time in queue; λ = average arrival rate into queue
• Little’s law – in steady state, processes leaving queue must equal processes arriving, thus: n = λ × W
  • Valid for any scheduling algorithm and arrival distribution

Algorithm evaluation

Queueing models and Little’s formula (cont.)

• For example, if on average 7 processes arrive per second, and normally 14 processes in queue, then average wait time per process = 2 seconds

Algorithm evaluation

Simulations

• Queueing models limited
• Simulations more accurate
  • Programmed model of computer system
  • Clock is a variable
  • Gather statistics indicating algorithm performance
  • Data to drive simulation gathered via
    • Random number generator according to probabilities
    • Distributions defined mathematically or empirically
    • Trace tapes record sequences of real events in real systems

Algorithm evaluation

Simulations (cont.)

Algorithm evaluation

Implementation

• Even simulations have limited accuracy
• Just implement new scheduler and test in real systems
  • High cost, high risk
  • Environments vary
• Most flexible schedulers can be modified per-site or per-system
• Or APIs to modify priorities
• But again environments vary

Interactive · every algorithm

CPU-scheduling simulator

Worked example 1 of 2

Worked example 1

Worked example 2 of 2

Worked example 2

Practice

Practice (1 of 2)

Try each one on paper first, then check your answer.

Practice

Practice (2 of 2)

Try each one on paper first, then check your answer.

Check yourself

Quiz

Resources

Further learning

Free material to go deeper. Links open in a new tab.

Summary · End of Chapter 5

Summary

• Processes alternate CPU and I/O bursts; most bursts are short.
• The scheduler picks from the ready queue; it is preemptive if it can take the CPU away, which can cause race conditions.
• Criteria: maximize CPU utilization and throughput; minimize turnaround, waiting and response time.
• FCFS is simple but suffers the convoy effect; SJF is optimal for waiting time; SRTF is its preemptive form.
• RR shares the CPU in quanta (q large → FCFS, q small → many context switches); priority scheduling risks starvation, cured by aging.
• Multilevel (feedback) queues combine algorithms; algorithms are evaluated by deterministic modelling, queueing models (n = λW), simulation and implementation.