CS330 · Chapter 5 · Annotated SlidesCPU Scheduling
Original
Overview

CPU Scheduling

CPU–I/O burst cycle, preemptive vs. nonpreemptive scheduling, the dispatcher, scheduling criteria, FCFS, SJF and SRTF (with exponential averaging), Round Robin, priority, multilevel and multilevel feedback queues, thread and real-time scheduling, and algorithm evaluation.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 45 slides
  1. 1 Slide 1
  2. 2 Outline
  3. 3 Objectives
  4. 4 Basic Concepts
  5. 5 Histogram of CPU-burst Times
  6. 6 CPU Scheduler
  7. 7 Preemptive and Nonpreemptive Scheduling
  8. 8 Preemptive Scheduling and Race Conditions
  9. 9 Dispatcher
  10. 10 Scheduling Criteria
  11. 11 Scheduling Algorithm Optimization Criteria
  12. 12 First- Come, First-Served (FCFS) Scheduling
  13. 13 FCFS Scheduling (Cont.)
  14. 14 Shortest-Job-First (SJF) Scheduling
  15. 15 Example of SJF
  16. 16 Determining Length of Next CPU Burst
  17. 17 Prediction of the Length of the Next CPU Burst
  18. 18 Examples of Exponential Averaging
  19. 19 Shortest Remaining Time First Scheduling
  20. 20 Example of Shortest-remaining-time-first
  21. 21 Round Robin (RR)
  22. 22 Example of RR with Time Quantum = 4
  23. 23 Time Quantum and Context Switch Time
  24. 24 Turnaround Time Varies With The Time Quantum
  25. 25 Priority Scheduling
  26. 26 Example of Priority Scheduling
  27. 27 Priority Scheduling w/ Round-Robin
  28. 28 Multilevel Queue
  29. 29 Multilevel Queue
  30. 30 Multilevel Queue
  31. 31 Multilevel Feedback Queue
  32. 32 Example of Multilevel Feedback Queue
  33. 33 Thread Scheduling
  34. 34 Dispatch Latency
  35. 35 Priority-based Scheduling
  36. 36 Rate Monotonic Scheduling
  37. 37 Operating System Examples
  38. 38 Windows Priorities
  39. 39 Solaris
  40. 40 Solaris Scheduling
  41. 41 Solaris Scheduling (Cont.)
  42. 42 Algorithm Evaluation
  43. 43 Deterministic Evaluation
  44. 44 Queueing Models
  45. 45 Slide 45
Slide 1 / 45

Slide 1

Slide 1: Slide 1
Slide 2 / 45

Outline

Slide 2: Outline
Slide 3 / 45

Objectives

Slide 3: Objectives
Slide 4 / 45

Basic Concepts

Slide 4: Basic Concepts
Slide 5 / 45

Histogram of CPU-burst Times

Slide 5: Histogram of CPU-burst Times
Slide 6 / 45

CPU Scheduler

Slide 6: CPU Scheduler
Slide 7 / 45

Preemptive and Nonpreemptive Scheduling

Slide 7: Preemptive and Nonpreemptive Scheduling

Notes

  1. Scheduling decisions when a process: 1) running → waiting, 2) running → ready, 3) waiting → ready, 4) terminates. Only 1 and 4 → nonpreemptive; otherwise preemptive.

Exam angle

PredictionQ1

Under nonpreemptive scheduling, the CPU is taken from a process only when it:

Slide 8 / 45

Preemptive Scheduling and Race Conditions

Slide 8: Preemptive Scheduling and Race Conditions
Slide 9 / 45

Dispatcher

Slide 9: Dispatcher

Notes

  1. Dispatcher gives the CPU to the chosen process: context switch, switch to user mode, jump to the right instruction. Dispatch latency = time to do this.

Slide 10 / 45

Scheduling Criteria

Slide 10: Scheduling Criteria

Notes

  1. Tip Waiting time = turnaround − burst. Turnaround = completion − arrival. Response = first run − arrival. Draw the Gantt chart first.

Exam angle

PredictionQ1

Which criterion should be MINIMIZED?

Slide 11 / 45

Scheduling Algorithm Optimization Criteria

Slide 11: Scheduling Algorithm Optimization Criteria
Slide 12 / 45

First- Come, First-Served (FCFS) Scheduling

Slide 12: First- Come, First-Served (FCFS) Scheduling

Notes

  1. FCFS: run in arrival order; nonpreemptive. Convoy effect: short processes wait behind a long one.

Exam angle

PredictionQ1

P1 = 24, P2 = 3, P3 = 3 arrive in that order at time 0. FCFS average waiting time:

Slide 13 / 45

FCFS Scheduling (Cont.)

Slide 13: FCFS Scheduling (Cont.)

Notes

  1. Order P2, P3, P1 gives average wait (6 + 0 + 3) / 3 = 3: order matters a lot.

Slide 14 / 45

Shortest-Job-First (SJF) Scheduling

Slide 14: Shortest-Job-First (SJF) Scheduling

Notes

  1. SJF: run the shortest next CPU burst. Optimal: minimum average waiting time for a given set. Problem: you can’t know the next burst length.

Exam angle

PredictionQ1

SJF gives the minimum average waiting time for a given set of processes.

Slide 15 / 45

Example of SJF

Slide 15: Example of SJF
Slide 16 / 45

Determining Length of Next CPU Burst

Slide 16: Determining Length of Next CPU Burst

Exam angle

PredictionQ1

τ₀ = 10, α = 0.5, the actual burst t₀ = 6. τ₁ =

Slide 17 / 45

Prediction of the Length of the Next CPU Burst

Slide 17: Prediction of the Length of the Next CPU Burst
Slide 18 / 45

Examples of Exponential Averaging

Slide 18: Examples of Exponential Averaging
Slide 19 / 45

Shortest Remaining Time First Scheduling

Slide 19: Shortest Remaining Time First Scheduling

Notes

  1. SRTF = preemptive SJF: a new arrival with a shorter burst than the remaining time preempts the running process.

  2. Trap In SRTF compare the newcomer with the REMAINING time of the running process, not its original burst.

Slide 20 / 45

Example of Shortest-remaining-time-first

Slide 20: Example of Shortest-remaining-time-first
Slide 21 / 45

Round Robin (RR)

Slide 21: Round Robin (RR)

Exam angle

PredictionQ1

P1 = 24, P2 = 3, P3 = 3, RR with q = 4. P1 completes at time:

Slide 22 / 45

Example of RR with Time Quantum = 4

Slide 22: Example of RR with Time Quantum = 4
Slide 23 / 45

Time Quantum and Context Switch Time

Slide 23: Time Quantum and Context Switch Time

Notes

  1. Large q → behaves like FCFS. Small q → too many context switches. q should be large compared with the context-switch time (80% of bursts < q).

Exam angle

PredictionQ1

If the RR time quantum is very large, RR behaves like:

Slide 24 / 45

Turnaround Time Varies With The Time Quantum

Slide 24: Turnaround Time Varies With The Time Quantum
Slide 25 / 45

Priority Scheduling

Slide 25: Priority Scheduling

Notes

  1. Priority scheduling (smaller number = higher priority here). Problem: starvation. Solution: aging (raise priority over time).

Exam angle

PredictionQ1

The solution to starvation in priority scheduling is:

Slide 26 / 45

Example of Priority Scheduling

Slide 26: Example of Priority Scheduling
Slide 27 / 45

Priority Scheduling w/ Round-Robin

Slide 27: Priority Scheduling w/ Round-Robin
Slide 28 / 45

Multilevel Queue

Slide 28: Multilevel Queue

Notes

  1. Multilevel queue: separate queues (e.g. foreground RR, background FCFS), each with its own algorithm; scheduling between queues by fixed priority or time slices.

Slide 29 / 45

Multilevel Queue

Slide 29: Multilevel Queue
Slide 30 / 45

Multilevel Queue

Slide 30: Multilevel Queue
Slide 31 / 45

Multilevel Feedback Queue

Slide 31: Multilevel Feedback Queue

Notes

  1. Multilevel feedback queue: processes MOVE between queues (demote CPU-hogs, age old ones up).

Exam angle

PredictionQ1

What distinguishes a multilevel FEEDBACK queue from a multilevel queue?

Slide 32 / 45

Example of Multilevel Feedback Queue

Slide 32: Example of Multilevel Feedback Queue
Slide 33 / 45

Thread Scheduling

Slide 33: Thread Scheduling
Slide 34 / 45

Dispatch Latency

Slide 34: Dispatch Latency
Slide 35 / 45

Priority-based Scheduling

Slide 35: Priority-based Scheduling
Slide 36 / 45

Rate Monotonic Scheduling

Slide 36: Rate Monotonic Scheduling
Slide 37 / 45

Operating System Examples

Slide 37: Operating System Examples
Slide 38 / 45

Windows Priorities

Slide 38: Windows Priorities
Slide 39 / 45

Solaris

Slide 39: Solaris
Slide 40 / 45

Solaris Scheduling

Slide 40: Solaris Scheduling
Slide 41 / 45

Solaris Scheduling (Cont.)

Slide 41: Solaris Scheduling (Cont.)
Slide 42 / 45

Algorithm Evaluation

Slide 42: Algorithm Evaluation
Slide 43 / 45

Deterministic Evaluation

Slide 43: Deterministic Evaluation

Notes

  1. Deterministic modelling: compute each algorithm’s numbers for a given workload.

Slide 44 / 45

Queueing Models

Slide 44: Queueing Models
Slide 45 / 45

Slide 45

Slide 45: Slide 45