Operating System Concepts
Chapter 6 { CPU Scheduling
Based on the 9th Edition of:
Abraham Silberschatz, Peter B. Galvin and Jreg Gagne:. Operating System
Concepts
Department of Information Technology, College of Business, Law & Governance
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Learning Objectives
To introduce CPU scheduling, which is the basis for
multiprogrammed operating systems
To describe various CPU-scheduling algorithms
To discuss evaluation criteria for selecting a CPU-scheduling
algorithm for a particular system
To examine the scheduling algorithms of several operating
systems
Chapter 6 { CPU Scheduling Operating System Concepts 2
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Outline
1 Basic Concepts
2 Scheduling Criteria
3 Scheduling Algorithms
4 Thread Scheduling
5 Real-Time CPU Scheduling
6 Operating-System Examples
7 Algorithm Evaluation
Chapter 6 { CPU Scheduling Operating System Concepts 3
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Basic Concepts

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
CPU burst
load store
add store
read from file
store increment
index
write to file
load store
add store
read from file
wait for I/O
wait for I/O
wait for I/O
I/O burst
I/O burst
I/O burst
CPU burst
CPU burst
••• •••
Chapter 6 { CPU Scheduling Operating System Concepts 4
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Basic Concepts
Histogram of CPU-burst Times
frequency
160
140
120
100
80
60
40
20
0 8 16 24 32 40
burst duration (milliseconds)
Chapter 6 { CPU Scheduling Operating System Concepts 5
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Basic Concepts
CPU Scheduler
Short-term scheduler selects from among the processes in
ready queue, and allocates the CPU to one of them.
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
Scheduling under 1 and 4 is nonpreemptive. All other
scheduling is preemptive
Chapter 6 { CPU Scheduling Operating System Concepts 6
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Basic Concepts
Dispatcher
Dispatcher module gives control of the CPU to the process
selected by the short-term scheduler; this involves:
switching context
switching to user mode
jumping to the proper location in the user program to restart
that program
Dispatch latency { time it takes for the dispatcher to stop one
process and start another running
Chapter 6 { CPU Scheduling Operating System Concepts 7
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Criteria
CPU utilization { keep the CPU as busy as possible
Throughput # of processes that complete their execution per
time unit
Turnaround time { amount of time to execute a particular
process
Waiting time { amount of time a process has been waiting in
the ready queue
Response time { amount of time it takes from when a request
was submitted until the first response is produced, not output
(for time-sharing environment)
Chapter 6 { CPU Scheduling Operating System Concepts 8
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Criteria
Scheduling Algorithm Optimization Criteria
Max CPU utilization
Max throughput
Min turnaround time
Min waiting time
Min response time
Chapter 6 { CPU Scheduling Operating System Concepts 9
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Algorithms
First-Come, First-Served (FCFS) Scheduling

Suppose that the processes arrive in the order: P1; P2; P3. The
Gantt Chart for the schedule is:
P1 P2 P3
0 24 27 30
Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27)=3 = 17
Chapter 6 { CPU Scheduling Operating System Concepts 10
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Algorithms
First-Come, First-Served (FCFS) Scheduling (Cont.)
Suppose that the processes arrive in the order: P2; P3; P1
The Gantt chart for the schedule is:
P2 P3 P1
0 3 6 30
Waiting time for P1 = 6; P2 = 0; P3 = 3
Average waiting time: (6 + 0 + 3)=3 = 3
Much better than previous case
Convoy effect { short process behind long process |consider
one CPU-bound and many I/O-bound processes
Chapter 6 { CPU Scheduling Operating System Concepts 11
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Algorithms
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
The difficulty is knowing the length of the next CPU request
Could ask the user
Chapter 6 { CPU Scheduling Operating System Concepts 12
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Algorithms
Shortest-Job-First (SJF) Scheduling | Example

SJF scheduling chart
P4 P1 P3 P2
0 3 9 16 24
Average waiting time: (3 + 16 + 9 + 0)=4 = 7
Chapter 6 { CPU Scheduling Operating System Concepts 13
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Algorithms
Preemptive Shortest-Job-First (SJF) Scheduling | Example
Now we add the concepts of varying arrival times and preemption
to the analysis
Process Arrival Time Burst Time
P1 0 8

P
P1 P2 P4 1 P3
0 1 5 10 17 26
Average waiting time:
[(10 – 1) + (1 – 1) + (17 – 2) + 5 – 3)]=4 = 26=4 = 6:5
Chapter 6 { CPU Scheduling Operating System Concepts 14
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Algorithms
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
Chapter 6 { CPU Scheduling Operating System Concepts 15
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Algorithms
Priority Scheduling | example

Priority scheduling Gantt Chart
P
P2 P5 1 P3 P4
0 1 6 16 18 19
Average waiting time: 8:2
Chapter 6 { CPU Scheduling Operating System Concepts 16
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Algorithms
Round Robin (RR) Scheduling
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.
Performance
q large ) FIFO
q must be large with respect to context switch, otherwise
overhead is too high
Chapter 6 { CPU Scheduling Operating System Concepts 17
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Algorithms
Round Robin (RR) Scheduling | Example with q = 4

The Gantt chart is:
P
P1 P2 P1 1 P1 P1 P1
0 4 7 10 14 26 18 22 30
P
3
Typically, higher average turnaround than SJF, but better
response
q should be large compared to context switch time
q usually 10ms to 100ms, where context switch < 10 usec
Chapter 6 { CPU Scheduling Operating System Concepts 18
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Algorithms
Time Quantum and Context Switch Time
process time 10 quantum context
switches
12 0
6 1
1 9
0 10
0 10
0 1 2 3 4 5 6 7 8 9 10
6
Chapter 6 { CPU Scheduling Operating System Concepts 19
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Algorithms
Turnaround Time varies With the Time Quantum
average turnaround time
1
12.5
12.0
11.5
11.0
10.5
10.0
9.5
9.0
2 3 4
time quantum
5 6 7
P1
P2
P3
P4
6
3
1
7
process time
80% of CPU bursts
should be
shorter than q
Chapter 6 { CPU Scheduling Operating System Concepts 20
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Algorithms
Multilevel Queue
Ready queue is partitioned into separate queues, eg:
foreground (interactive), and background (batch)
Process permanently in a given queue
Each queue has its own scheduling algorithm: foreground !
RR, and background ! FCFS
Scheduling must be done between the queues:
Fixed priority scheduling { serve all from foreground then from
background. Possibility of starvation.
Time slice { each queue gets a certain amount of CPU time
which it can schedule amongst its processes; i.e., 80% to
foreground in RR, and 20% to background in FCFS
Chapter 6 { CPU Scheduling Operating System Concepts 21
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Algorithms
Multilevel Queue Scheduling
system processes
highest priority
lowest priority
interactive processes
interactive editing processes
batch processes
student processes
Chapter 6 { CPU Scheduling Operating System Concepts 22
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Algorithms
Multilevel Feedback Queue
A process can move between the various queues; aging can be
implemented this way
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
Chapter 6 { CPU Scheduling Operating System Concepts 23
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Scheduling Algorithms
Multilevel Feedback Queue | Example

2 Q1 – RR time quantum 16 ms
3 Q2 – FCFS
quantum 8
quantum 16
FCFS
Scheduling:
A new job enters queue Q0 which is served FCFS. When it
gains CPU, job receives 8 milliseconds. If it does not finish in
8 milliseconds, job is moved to queue Q1
At Q1 job is again served FCFS and receives 16 additional
milliseconds. If it still does not complete, it is preempted and
moved to queue Q2.
Chapter 6 { CPU Scheduling Operating System Concepts 24
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 is the number of processes that are completed per time
unit.
A. CPU utilization
B. Response time
C. Turnaround time
D. Throughput
Answer:
Chapter 6 { CPU Scheduling Operating System Concepts 25
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 is the number of processes that are completed per time
unit.
A. CPU utilization
B. Response time
C. Turnaround time
D. Throughput
Answer: D
Chapter 6 { CPU Scheduling Operating System Concepts 25
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 is the number of processes that are completed per time
unit.
A. CPU utilization
B. Response time
C. Turnaround time
D. Throughput
Answer: D
2 True or False { In RR scheduling, the time quantum should
be small with respect to the context-switch time.
Answer:
Chapter 6 { CPU Scheduling Operating System Concepts 25
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 is the number of processes that are completed per time
unit.
A. CPU utilization
B. Response time
C. Turnaround time
D. Throughput
Answer: D
2 True or False { In RR scheduling, the time quantum should
be small with respect to the context-switch time.
Answer: False
Chapter 6 { CPU Scheduling Operating System Concepts 25
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 is the number of processes that are completed per time
unit.
A. CPU utilization
B. Response time
C. Turnaround time
D. Throughput
Answer: D
2 True or False { In RR scheduling, the time quantum should
be small with respect to the context-switch time.
Answer: False
3 True or False { The most complex scheduling algorithm is
the multilevel feedback-queue algorithm.
Answer:
Chapter 6 { CPU Scheduling Operating System Concepts 25
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 is the number of processes that are completed per time
unit.
A. CPU utilization
B. Response time
C. Turnaround time
D. Throughput
Answer: D
2 True or False { In RR scheduling, the time quantum should
be small with respect to the context-switch time.
Answer: False
3 True or False { The most complex scheduling algorithm is
the multilevel feedback-queue algorithm.
Answer: True
Chapter 6 { CPU Scheduling Operating System Concepts 25
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 The scheduling algorithm is designed especially for
time-sharing systems.
A. SJF
B. FCFS
C. RR
D. Multilevel queue
Answer:
Chapter 6 { CPU Scheduling Operating System Concepts 26
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 The scheduling algorithm is designed especially for
time-sharing systems.
A. SJF
B. FCFS
C. RR
D. Multilevel queue
Answer: C
Chapter 6 { CPU Scheduling Operating System Concepts 26
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 The scheduling algorithm is designed especially for
time-sharing systems.
A. SJF
B. FCFS
C. RR
D. Multilevel queue
Answer: C
2 Which of the following scheduling algorithms must be
nonpreemptive?
A. SJF
B. RR
C. FCFS
D. priority algorithms
answer:
Chapter 6 { CPU Scheduling Operating System Concepts 26
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 The scheduling algorithm is designed especially for
time-sharing systems.
A. SJF
B. FCFS
C. RR
D. Multilevel queue
Answer: C
2 Which of the following scheduling algorithms must be
nonpreemptive?
A. SJF
B. RR
C. FCFS
D. priority algorithms
answer: C
Chapter 6 { CPU Scheduling Operating System Concepts 26
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Thread Scheduling
Distinction between user-level and kernel-level threads
When threads supported, threads scheduled, not processes
Many-to-one and many-to-many models, thread library
schedules user-level threads to run on LWP {known as
process-contention scope (PCS) since scheduling competition
is within the process
Kernel thread scheduled onto available CPU is
system-contention scope (SCS) {competition among all
threads in system
Chapter 6 { CPU Scheduling Operating System Concepts 27
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Multiple-Processor Scheduling
CPU scheduling more complex when multiple CPUs are
available
Homogeneous processors within a multiprocessor
Asymmetric multiprocessing { only one processor accesses the
system data structures, alleviating the need for data sharing
Symmetric multiprocessing (SMP) { each processor is
self-scheduling, all processes in common ready queue, or each
has its own private queue of ready processes
Processor affinity { process has affinity for processor on which
it is currently running
soft affinity
hard affinity
Chapter 6 { CPU Scheduling Operating System Concepts 28
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Multiple-Processor Scheduling
Load Balancing
If SMP (Symmetric Multiprocessing), need to keep all CPUs
loaded for efficiency
Load balancing attempts to keep workload evenly distributed
Push migration { periodic task checks load on each processor,
and if found pushes task from overloaded CPU to other CPUs
Pull migration { idle processors pulls waiting task from busy
processor
Chapter 6 { CPU Scheduling Operating System Concepts 29
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Multiple-Processor Scheduling
Multicore Processors
Recent trend to place multiple processor cores on same
physical chip
Faster and consumes less power
Multiple threads per core also growing
Takes advantage of memory stall to make progress on another
thread while memory retrieve happens
Chapter 6 { CPU Scheduling Operating System Concepts 30
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Multiple-Processor Scheduling
Multithreaded Multicore system
time
compute cycle memory stall cycle
thread
C
C
M C M C M
M
C M
time
thread0
thread1
C M C M C M C
C M C M C M C
Chapter 6 { CPU Scheduling Operating System Concepts 31
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 Which of the following is true of multilevel queue scheduling?
A. Processes can move between queues.
B. Each queue has its own scheduling algorithm.
C. A queue cannot have absolute priority over lower-priority
queues.
D. It is the most general CPU-scheduling algorithm.
Answer:
Chapter 6 { CPU Scheduling Operating System Concepts 32
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 Which of the following is true of multilevel queue scheduling?
A. Processes can move between queues.
B. Each queue has its own scheduling algorithm.
C. A queue cannot have absolute priority over lower-priority
queues.
D. It is the most general CPU-scheduling algorithm.
Answer: B
Chapter 6 { CPU Scheduling Operating System Concepts 32
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 Which of the following is true of multilevel queue scheduling?
A. Processes can move between queues.
B. Each queue has its own scheduling algorithm.
C. A queue cannot have absolute priority over lower-priority
queues.
D. It is the most general CPU-scheduling algorithm.
Answer: B
2 True or False { Load balancing is typically only necessary on
systems with a common run queue.
Answer:
Chapter 6 { CPU Scheduling Operating System Concepts 32
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 Which of the following is true of multilevel queue scheduling?
A. Processes can move between queues.
B. Each queue has its own scheduling algorithm.
C. A queue cannot have absolute priority over lower-priority
queues.
D. It is the most general CPU-scheduling algorithm.
Answer: B
2 True or False { Load balancing is typically only necessary on
systems with a common run queue.
Answer: False
Chapter 6 { CPU Scheduling Operating System Concepts 32
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 Which of the following is true of multilevel queue scheduling?
A. Processes can move between queues.
B. Each queue has its own scheduling algorithm.
C. A queue cannot have absolute priority over lower-priority
queues.
D. It is the most general CPU-scheduling algorithm.
Answer: B
2 True or False { Load balancing is typically only necessary on
systems with a common run queue.
Answer: False
3 True or False { SMP systems that use multicore processors
typically run faster than SMP systems that place each
processor on separate cores.
Answer:
Chapter 6 { CPU Scheduling Operating System Concepts 32
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 Which of the following is true of multilevel queue scheduling?
A. Processes can move between queues.
B. Each queue has its own scheduling algorithm.
C. A queue cannot have absolute priority over lower-priority
queues.
D. It is the most general CPU-scheduling algorithm.
Answer: B
2 True or False { Load balancing is typically only necessary on
systems with a common run queue.
Answer: False
3 True or False { SMP systems that use multicore processors
typically run faster than SMP systems that place each
processor on separate cores.
Answer: True
Chapter 6 { CPU Scheduling Operating System Concepts 32
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Real-Time CPU Scheduling
Soft real-time systems { no guarantee as to when critical
real-time process will be scheduled
Hard real-time systems { task must be serviced by its deadline
Two types of latencies affect
performance
1 Interrupt latency time
from arrival of interrupt
to start of routine that
services interrupt
2 Dispatch latency time for
schedule to take current
process off CPU and
switch to another
task T running
ISR
determine
interrupt
type
interrupt
interrupt
latency
context
switch
time
Chapter 6 { CPU Scheduling Operating System Concepts 33
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Real-Time CPU Scheduling
Conflict phase of dispatch latency:
Preemption of
any process
running in
kernel mode
Release by
low-priority
process of
resources
needed by
high-priority
processes
response to event
real-time
process
execution
event
conflicts
time
dispatch
response interval
dispatch latency
process made
interrupt available
processing
Chapter 6 { CPU Scheduling Operating System Concepts 34
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Real-Time CPU Scheduling
Priority-Based Scheduling
For real-time scheduling, scheduler must support preemptive,
priority-based scheduling |only guarantees soft real-time
For hard real-time must also provide ability to meet deadlines
Processes have new characteristics: periodic ones require CPU
at constant intervals
Has processing time t, deadline d, period p
0 ≤ t ≤ d ≤ p
Rate of periodic task is 1=p
Chapter 6 { CPU Scheduling Operating System Concepts 35
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Real-Time CPU Scheduling
Priority-Based Scheduling (Cont.)
period1 period2 period3
Time
p p p
d d d
t t t
Chapter 6 { CPU Scheduling Operating System Concepts 36
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 A significant problem with priority scheduling algorithms is
.
A. complexity
B. starvation
C. determining the length of the next CPU burst
D. determining the length of the time quantum
Answer:
Chapter 6 { CPU Scheduling Operating System Concepts 37
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 A significant problem with priority scheduling algorithms is
.
A. complexity
B. starvation
C. determining the length of the next CPU burst
D. determining the length of the time quantum
Answer: B
Chapter 6 { CPU Scheduling Operating System Concepts 37
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 A significant problem with priority scheduling algorithms is
.
A. complexity
B. starvation
C. determining the length of the next CPU burst
D. determining the length of the time quantum
Answer: B
2 involves the decision of which kernel thread to schedule
onto which CPU.
A. Process-contention scope
B. System-contention scope
C. Dispatcher
D. Round-robin scheduling
Answer:
Chapter 6 { CPU Scheduling Operating System Concepts 37
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 A significant problem with priority scheduling algorithms is
.
A. complexity
B. starvation
C. determining the length of the next CPU burst
D. determining the length of the time quantum
Answer: B
2 involves the decision of which kernel thread to schedule
onto which CPU.
A. Process-contention scope
B. System-contention scope
C. Dispatcher
D. Round-robin scheduling
Answer: B
Chapter 6 { CPU Scheduling Operating System Concepts 37
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Operating-System Examples | Linux
Prior to kernel version 2.5, ran variation of standard UNIX
scheduling algorithm
Version 2.5 moved to constant order O(1) scheduling time
Version 2.6.23 + are based on Completely Fair Scheduler
(CFS)
CFS scheduler maintains per task virtual run time in variable
vruntime
To decide next task to run, scheduler picks task with lowest
virtual run time
Chapter 6 { CPU Scheduling Operating System Concepts 38
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Operating-System Examples | Linux
T0
T2
T3 T5 T6
T1
T4
T7 T8 T9
smaller larger
Task with the smallest
value of vruntime
Value of vruntime
Chapter 6 { CPU Scheduling Operating System Concepts 39
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Operating-System Examples | Windows
Windows uses priority-based preemptive scheduling
{Highest-priority thread runs next
Dispatcher is scheduler |Thread runs until (i) blocks, (ii)
uses time slice, (iii) preempted by higher-priority thread
Real-time threads can preempt non-real-time
32-level priority scheme
Variable class is 1-15, real-time class is 16-31 |Priority 0 is
memory-management thread
If no run-able thread, runs idle thread
Chapter 6 { CPU Scheduling Operating System Concepts 40
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Operating-System Examples | Windows
Win32 API identifies several priority classes to which a process
can belong {all are variable except REALTIME
A thread within a given priority class has a relative priority.
Base priority is NORMAL within the class
If wait occurs, priority boosted depending on what was waited
for |foreground window given 3x priority boost
Windows 7 added user-mode scheduling (UMS)
Applications create and manage threads independent of kernel
UMS schedulers come from programming language libraries
like C++ Concurrent Runtime (ConcRT) framework
Chapter 6 { CPU Scheduling Operating System Concepts 41
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Operating-System Examples | Windows
Windows Priorities
high above normal normal below normal idle priority
time-critical
realtime
31
26
25
24
23
22
16
15
15
14
13
12
11
1
15
12
11
10
9 8 1
15
10
9 8 7 6 1
15
8 7 6 5 4 1
15
6 5 4 3 2 1
highest
above normal
normal
lowest
idle
below normal
Chapter 6 { CPU Scheduling Operating System Concepts 42
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Operating-System Examples | Solaris
Priority-based scheduling. Six classes available
1 Time sharing (default) (TS)
2 Interactive (IA)
3 Real time (RT)
4 System (SYS)
5 Fair Share (FSS)
6 Fixed priority (FP)
Given thread can be in one class at a time
Each class has its own scheduling algorithm
Time sharing is multi-level feedback queue
Chapter 6 { CPU Scheduling Operating System Concepts 43
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Operating-System Examples | Solaris
Scheduler converts
class-specific priorities into a
per-thread global priority
Thread with highest
priority runs next
Runs until (i) blocks, (ii)
uses time slice, (iii)
preempted by
higher-priority thread
Multiple threads at same
priority selected via RR
interrupt threads
169
highest
lowest
rst
scheduling
order
global
priority
last
160
159
100
60
59
0
99
realtime (RT) threads
system (SYS) threads
fair share (FSS) threads
xed priority (FX) threads
timeshare (TS) threads
interactive (IA) threads
Chapter 6 { CPU Scheduling Operating System Concepts 44
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 The default scheduling class for a process in Solaris is .
A. time sharing
B. system
C. interactive
D. real-time
Answer:
Chapter 6 { CPU Scheduling Operating System Concepts 45
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 The default scheduling class for a process in Solaris is .
A. time sharing
B. system
C. interactive
D. real-time
Answer: A
Chapter 6 { CPU Scheduling Operating System Concepts 45
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 The default scheduling class for a process in Solaris is .
A. time sharing
B. system
C. interactive
D. real-time
Answer: A
2 Which of the following statements are false with regards to
the Linux CFS (Completely Fair Scheduler)?
A. Each task is assigned a proportion of CPU processing time.
B. Lower numeric values indicate higher relative priorities.
C. There is a single, system-wide value of vruntime.
D. The scheduler doesn’t directly assign priorities.
Answer:
Chapter 6 { CPU Scheduling Operating System Concepts 45
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 The default scheduling class for a process in Solaris is .
A. time sharing
B. system
C. interactive
D. real-time
Answer: A
2 Which of the following statements are false with regards to
the Linux CFS (Completely Fair Scheduler)?
A. Each task is assigned a proportion of CPU processing time.
B. Lower numeric values indicate higher relative priorities.
C. There is a single, system-wide value of vruntime.
D. The scheduler doesn’t directly assign priorities.
Answer: C
Chapter 6 { CPU Scheduling Operating System Concepts 45
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Algorithm Evaluation
How to select CPU-scheduling algorithm for an OS?
Determine criteria, then evaluate algorithms
Deterministic modeling
Type of analytic evaluation
Takes a particular predetermined workload and defines the
performance of each algorithm for that workload
Consider 5 processes arriving at time 0:
Process Burst Time
P1 10
P2 29
P3 3
P4 7
P5 12
Chapter 6 { CPU Scheduling Operating System Concepts 46
Concept Criteria Scheduling Algorithms Thread Real-Time Examples 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 |average waiting time: 28 ms
P
P1 2 P3 P4 P5
0 10 39 49 42 61
SJF (non-preemptive) |average waiting time: 13 ms
P
P3 P4 5 P2
0 3 10 20 32 61
P
1
RR |average waiting time: 23 ms
P
P2 P3 P4 5 P2 P5 P2
0 10 20 23 30 40 50 52 61
P
1
Chapter 6 { CPU Scheduling Operating System Concepts 47
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Algorithm Evaluation | Queueing Models
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
Chapter 6 { CPU Scheduling Operating System Concepts 48
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
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
Chapter 6 { CPU Scheduling Operating System Concepts 49
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Algorithm Evaluation | Simulations
Evaluation of CPU Schedulers by Simulation
actual
process
execution
performance
statistics
for FCFS
simulation
FCFS
performance
statistics
for SJF
performance
statistics
for RR (q 14)
trace tape
simulation
SJF
simulation
RR (q 14)
• • •
CPU 10
I/O 213
CPU 12
I/O 112
CPU 2
I/O 147
CPU 173
• • •
Chapter 6 { CPU Scheduling Operating System Concepts 50
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 True or False { The Completely Fair Scheduler (CFS) is the
default scheduler for Linux systems.
Answer:
Chapter 6 { CPU Scheduling Operating System Concepts 51
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 True or False { The Completely Fair Scheduler (CFS) is the
default scheduler for Linux systems.
Answer: True
Chapter 6 { CPU Scheduling Operating System Concepts 51
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 True or False { The Completely Fair Scheduler (CFS) is the
default scheduler for Linux systems.
Answer: True
2 True or False { Windows 7 User-mode scheduling (UMS)
allows applications to create and manage thread
independently of the kernel.
Answer:
Chapter 6 { CPU Scheduling Operating System Concepts 51
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 True or False { The Completely Fair Scheduler (CFS) is the
default scheduler for Linux systems.
Answer: True
2 True or False { Windows 7 User-mode scheduling (UMS)
allows applications to create and manage thread
independently of the kernel.
Answer: True
Chapter 6 { CPU Scheduling Operating System Concepts 51
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 True or False { The Completely Fair Scheduler (CFS) is the
default scheduler for Linux systems.
Answer: True
2 True or False { Windows 7 User-mode scheduling (UMS)
allows applications to create and manage thread
independently of the kernel.
Answer: True
3 True or False { In the Linux CFS (Completely Fair
Scheduler), the task with smallest value of vruntime is
considered to have the highest priority.
Answer:
Chapter 6 { CPU Scheduling Operating System Concepts 51
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
Quick Quiz
1 True or False { The Completely Fair Scheduler (CFS) is the
default scheduler for Linux systems.
Answer: True
2 True or False { Windows 7 User-mode scheduling (UMS)
allows applications to create and manage thread
independently of the kernel.
Answer: True
3 True or False { In the Linux CFS (Completely Fair
Scheduler), the task with smallest value of vruntime is
considered to have the highest priority.
Answer: True
Chapter 6 { CPU Scheduling Operating System Concepts 51
Concept Criteria Scheduling Algorithms Thread Real-Time Examples Evaluation
End of Chapter 6
Chapter 6 { CPU Scheduling Operating System Concepts 52