Priority Scheduling

 CPU is assigned to the process

with the highest priority – A
framework for various scheduling
algorithms:
 FCFS: Equal-Priority with Tie-
Breaking by FCFS
 SFJ: Priority = 1 / next CPU burst
length

Priority Scheduling
Process CPU Burst Time Priority
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2
Average waiting time
Gantt Graph = (6+0+16+18+1)/5 = 8.2

P2 P5 P1 P3 P4
0 1 6 16 18 19
Priority Scheduling
 Priority Assignment
 Internally defined – use some
measurable quantity, such as the #
of open files, Average CPU Burst
Average I/O Burst

 Externally defined – set by criteria

external to the OS, such as the
criticality levels of jobs.

Priority Scheduling
 Preemptive or Non-Preemptive?
 Preemptive scheduling – CPU
scheduling is invoked whenever a
process arrives at the ready queue,
or the running process relinquishes
the CPU.
 Non-preemptive scheduling – CPU
scheduling is invoked only when the
running process relinquishes the
CPU.
 Priority Scheduling
 Major Problem
 Indefinite Blocking (/Starvation)
 Low-priority processes could starve
to death!
 A Solution: Aging
 A technique that increases the
priority of processes waiting in the
system for a long time.

Round-Robin Scheduling (RR)

 RR is similar to FCFS except that
preemption is added to switch between
processes.

ready running
Interrupt at every time quantum (time slice)

 Goal: Fairness – Time Sharing

CPU FIFO… New process

The quantum is used up!

Round-Robin Scheduling (RR)
Process CPU Burst Time
P1 24
P2 3 Time slice = 4
P3 3

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

AWT = ((10-4) + (4-0) + (7-0))/3

= 17/3 = 5.66

Round-Robin Scheduling (RR)

 Service Size and Interval
 Time quantum = q  Service interval <= (n-
1)*q if n processes are ready.
 IF q = ∞, then RR  FCFS.
 IF q = , then RR  processor sharing. The
# of context switchings increases!
process quantum context switch #
0 10 12 0
0 6 10 6 1
0 10
1 9
If context switch cost
= 10% => 1/11 of CPU is wasted!
time quantum
Round-Robin Scheduling (RR)
 Turnaround Time
process (10ms) quantum = 10 quantum = 1

P1 0 10 20 30
0 10
P2
10 20 0 10 20 30
P3
20 30 0 10 20 30
Average Turnaround Time ATT = (28+29+30)/3 = 29
= (10+20+30)/3 = 20
=> 80% CPU Burst < time slice

Multilevel Queue Scheduling

 Partition the ready queue into
several separate queues =>
Processes can be classified into
different groups and permanently
assigned to one queue.

System Processes

Interactive Processes
…

Batch Processes
 Multilevel Queue Scheduling
 Intra-queue scheduling
 Independent choice of scheduling
algorithms.
 Inter-queue scheduling
a. Fixed-priority preemptive scheduling
a. e.g., foreground queues always have absolute
priority over the background queues.
b. Time slice between queues
a. e.g., 80% CPU is given to foreground processes,
and 20% CPU to background processes.
c. More??

Multilevel Feedback
Queue Scheduling
 Different from Multilevel Queue
Scheduling by Allowing Processes to
Migrate Among Queues.
 Configurable Parameters:
a. # of queues
b. The scheduling algorithm for each queue
c. The method to determine when to upgrade a
process to a higher priority queue.
d. The method to determine when to demote a
process to a lower priority queue.
e. The method to determine which queue a newly
ready process will enter.
*Inter-queue scheduling: Fixed-priority preemptive?!
Multilevel Feedback
Queue Scheduling
 Example

quantum = 8

quantum = 16

FCFS
*Idea: Separate processes with different CPU-burst
characteristics!

Multiple-Processor Scheduling
 CPU scheduling in a system with
multiple CPUs
 A Homogeneous System
 Processes are identical in terms of their
functionality.
 Can processes run on any processor?
 A Heterogeneous System
 Programs must be compiled for
instructions on proper processors.
Multiple-Processor Scheduling
 Load Sharing – Load Balancing!!
 A queue for each processor
 Self-Scheduling – Symmetric
Multiprocessing
 A common ready queue for all processors.
 Self-Scheduling
 Need synchronization to access common
data structure, e.g., queues.
 Master-Slave – Asymmetric Multiprocessing
 One processor accesses the system
structures  no need for data sharing.

Multiple-Processor Scheduling
 Load Balancing
 Push migration: A specific task periodically
checks for imbalance and migrate tasks
 Pull migration: An idle processor pulls a
waiting task from a busy processor
 Linux and FreeBSD do both!
 Processor Affinity
 The system might avoid process migration
because of the cost in invalidating or re-
populating caches
 Soft or hard affinity
 Multiple-Processor Scheduling

 Symmetric Multithreading (SMT), i.e.,

Hyperthreading
 A feature provided by the hardware
 Several logical processors per
physical processor
 Each has its own architecture state,
including registers.
 Issues: Process Synchronization

Multiple-Processor Scheduling –
SMT Superscalar SMT

U t ilizat io n++
time T hr o ghput ++
u
Pe rf ormance++

occupied issue slot

unused issue slot
: 13 : 10 : 11