CPU Scheduling

CSE 2431: Introduction to Operating Systems

Instructor: Adam C. Champion, Ph.D.
Reading: Chapter 5, [OSC] (except Sections
5.7.2, 5.8)

1
Contents
• Why Scheduling?
• Basic Concepts of Scheduling
• Scheduling Criteria
• A Basic Scheduling Algorithm (FCFS)
• Scheduling Algorithms (SJF, RR, etc.)
• Thread Scheduling

2
Why Scheduling?
• Deciding which process/thread should
occupy the resource (CPU, disk, etc.)
(CPU (horsepower))

I want to
ride it Whose turn is it?

Process 1 Process 2 Process 3

3
Contents
• Why Scheduling?
• Basic Concepts of Scheduling
• Scheduling Criteria
• A Basic Scheduling Algorithm (FCFS)
• Scheduling Algorithms (SJF, RR, etc.)
• Thread Scheduling

4
When to Schedule?

5
Contents
• Why Scheduling?
• Basic Concepts of Scheduling
• Scheduling Criteria
• Basic Scheduling Algorithm (FCFS)
• Scheduling Algorithms (SJF, RR, etc.)
• Thread Scheduling

6
Scheduling Objectives
• Fairness (nobody cries)
• Priority (ladies first)
• Efficiency (make best use of equipment)
• Encourage good behavior (good boy/girl)
• Support heavy loads (degrade gracefully)
• Adapt to different environments (interactive,
real-time, multimedia)

7
 Performance Criteria
• Fairness: No starvation
• Efficiency: keep resources as busy as possible
• Throughput: # of processes completed in unit time
• Turnaround time (also called elapsed time): Amount of time to
complete a certainprocess from its beginning
• Waiting Time: Amount of time process has been waiting in
ready queue
• Response Time: Amount of time from when a request was first
submitted until first response is produced.
• Policy Enforcement: Enforcing that stated policy is carried out
• Proportionality: Meet users' expectations
8
• Meeting Deadlines: Avoid losing data
Different Systems, Different Foci

• For all
– Fairness, policy enforcement, resource balance
• Batch Systems
– Max throughput, min turnaround time, max
CPU utilization
• Interactive Systems
– Min Response time, best proportionality
• Real-Time Systems
– predictability, meeting deadlines
9
Preemptive vs. Non-preemptive
• Non-preemptive scheduling:
– The running process keeps the CPU until it
voluntarily gives up the CPU 4
Running Terminated
• Process exits 1
3
• Switches to waiting state
Ready Waiting
• 1 and 4 only (no 3)

• Preemptive scheduling:
– The running process can be interrupted and
must release the CPU (be forced to give up CPU)
10
Process Behavior
• I/O-Bound
– Does too much I/O to keep CPU busy
• CPU-Bound
– Does too much computation to keep I/O busy
• Process Mix
– Scheduling should load-balance between I/O
bound and CPU-bound processes
– Ideal would be to run all equipment at 100%
utilization, but that would not necessarily be
good for response time
11
 Program Characteristics
Considered in Scheduling
• Is it I/O bound? I/O I/O

• Is it CPU bound? compute I/O compute

• Batch or interactive environment?

• Urgency
• Priority
• Frequency of page faults
• Frequency of preemption
• How much execution time has it already received?
• How much execution time needed to finish?
12
CPU Scheduler
• Proc 1: 14 time units
CPU
• Proc 2: 8 time units
• Proc 3: 8 time units
Dispatcher
Proc 1 Proc 10
• Dispatcher Proc 2 Proc 11

• Preemptive vs. Proc 3 Proc 12

non-preemptive
Ready queue Waiting queue

13
Dispatcher
• Gives the control of the CPU to the process,
scheduled by the short-term scheduler.
• Functions:
– Switching context
– Switching to user mode
– Jumping to the proper location in the user program.
• Dispatch Latency: time to stop a process and
start another one.
– Pure overhead
– Needs to be fast

14
Single Processor Scheduling
Algorithms
• Batch systems
– First Come First Serve (FCFS)
– Shortest Job First
• Interactive systems
– Round Robin
– Priority Scheduling
– Multi-Queue and Multi-Level Feedback
– Shortest process time
– Guaranteed Scheduling
– Lottery Scheduling
– Fair Sharing Scheduling 15
First Come First Serve (FCFS)
• Process that requests the CPU FIRST is allocated the CPU FIRST.
• Also called FIFO
• Preemptive or non-preemptive?
• Used in batch systems
• Real life analogy?
– Buying tickets?
• Implementation
– FIFO queues
– A new process enters the tail of the queue
– The schedule selects from the head of the queue.
• Performance Metric: Average Waiting Time.
• Given Parameters:
– Burst Time (in msec), Arrival Time and Order

16
FCFS Example
Process Duration Order Arrival Time
P1 24 1 0
P2 3 2 0
P3 4 3 0
The final schedule (Gantt chart):
P1 (24) P2 (3) P3 (4)
0 24 27 31

P1 waiting time: 0 Average waiting time:

P2 waiting time: 24 (0+24+27)/3 = 17
P3 waiting time: 27
What if P1 arrives at time 2?
17
Problems with FCFS
• Non-preemptive
• Suboptimal AWT
• Cannot utilize resources in parallel:
– Assume: 1 CPU-bound process, many I/O-
bound processes
– Result: Convoy effect, low CPU and I/O
device utilization
– Why?

18
 Why Convoy Effects?
• Consider 100 I/O-bound processes, 1 CPU-bound job in system.
• I/O-bound processes pass quickly through the ready queue and
suspend themselves waiting for I/O.
• CPU-bound process arrives at head of queue, executes until
completion.
• I/O bound processes rejoin ready queue, wait for the CPU-
bound process to release CPU.
• I/O devices idle until the CPU-bound process completes.
• In general, a convoy effect happens when a set of processes
need to use a resource for a short time, and one process holds
the resource for a long time, blocking all of the other processes.
19
This causes poor utilization of system resources.
Shortest Job First (SJF)
• Schedule the job with the shortest duration time first
• Used in batch systems
• Two types:
– Non-preemptive
– Preemptive
• Requirement: duration time must be known in
advance
• Optimal if all jobs available simultaneously
(provable)
– Gives the best possible AWT (average waiting time)
20
Non-preemptive SJF: Example
Process Duration Order Arrival Time
P1 6 1 0
P2 8 2 0
P3 7 3 0
P4 3 4 0
Do it yourself

21
Comparing to FCFS
Process Duration Order Arrival Time
P1 6 1 0
P2 8 2 0
P3 7 3 0
P4 3 4 0

Do it yourself

22
SJF Is Not Always Optimal
• Is SJF optimal if all jobs are not available
simultaneously?
Process Duration Order Arrival Time
P1 10 1 0
P2 2 2 2
Do it yourself

23
Preemptive SJF
• Also called Shortest Remaining Time
First
– Schedule the job with the shortest remaining
time required to complete
• Requirement: duration time must be
known in advance

24
 Preemptive SJF: Same Example
Process Duration Order Arrival Time

P1 10 1 0
P2 2 2 2

P1 (2) P2 (2) P1 (8)

0 2 4 12

P1 waiting time: 4 – 2 = 2 Average waiting time (AWT):

P2 waiting time: 0 (0+2)/2 = 1

25
A Problem with SJF
• Starvation
– In some scenarios, a job may wait forever
– Example: SJF
• Process A with duration time of 1 hour arrives at
time 0
• But every 1 minute, a shorter process with
duration time of 2 minutes arrive
• Result of SJF: process A never gets to run
• What’s the difference between starvation
and a deadlock?

26
Interactive Scheduling Algorithms
• Usually preemptive
– Time sliced into quantum (time intervals)
– Scheduling decision made at beginning of each quantum
• Performance Criteria
– Min Response time
– best proportionality
• Representative algorithms:
– Priority-based
– Round-robin
– Multi-Queue and Multi-Level Feedback
– Shortest process time
– Guaranteed Scheduling
– Lottery Scheduling
27
– Fair Sharing Scheduling
Priority Scheduling
• Each job is assigned a priority.
• FCFS within each priority level.
• Select highest priority job over lower ones.
• Rationale: higher priority jobs are more
mission-critical
– Example: DVD movie player vs. send email
• Problems:
– May not give the best AWT
– Starvation

28
Set Priority
• Two approaches
– Static (for system with well known and
regular application behaviors)
– Dynamic (otherwise)
• Priority may be based on:
– Cost to user.
– Importance of user.
– Aging
– Percentage of CPU time used in last X hours.

29
Priority Scheduling: Example
Process Duration Priority Arrival Time
P1 6 4 0
P2 8 1 0
P3 7 3 0
P4 3 2 0
Do it yourself

30
Round-Robin (RR)
• One of the oldest, simple, commonly used
scheduling algorithms
• Select process/thread from ready queue in
a round-robin fashion (take turns)

• Problems:
– Does not consider priority
– More context switch overhead

31
Round-Robin: Example
Process Duration Order Arrival Time
P1 3 1 0
P2 4 2 0
P3 3 3 0
Suppose time quantum is 1 unit; P1, P2, and P3 never block
Do it yourself

32
Time Quantum
• Time slice too large
– FIFO behavior
– Poor response time
• Time slice too small
– Too many context switches (overheads)
– Inefficient CPU utilization
• Heuristic: (Eliminating preemption)
– 70–80% of processes block within time-slice
• Typical time slice: 10 to 100 ms
• Time spent in system depends on size of job
33
Multi-Queue Scheduling
• Hybrid between priority and round-robin
• Processes assigned to one queue
• Scheduling between queues
– Fixed Priorities
– Dynamic priorities based on CPU % spent on queue
• Example
– System processes
– Interactive programs
– Background processes
• Address the starvation problem

34
Multi-Queue Scheduling:
Example

35
Multi-Processor Scheduling: Load Sharing

• Decides:
– Which process to run?
– How long does it run?
– Where to run it?

(CPU (horsepower))

I want to
ride it

…
Process 1 Process 2 Process n 36
Multi-Processor Scheduling Choices
• Self-Scheduled
– Each CPU dispatches a job from the ready queue
• Master-Slave
– One CPU schedules the other CPUs
• Asymmetric
– One CPU runs the kernel and the others run the
user applications.
– One CPU handles network and the others handle
applications

37
Gang Scheduling for
Multi-Processors
• A collection of processes belong to one job
• All the processes run at the same time
– If one process is preempted, all the processes
of the gang are preempted. Why?
• Helps to eliminate the time a process
spends on waiting for other processes in
its parallel computation.

38
 Priority Inversion and Inheritance
• Priority inversion problem:
– When a higher priority process needs to read/modify
kernel data currently locked by a lower priority process
– The higher priority process must wait!
– But the lower priority cannot proceed due to scheduling.
• Solution: Priority inheritance
– When a lower-priority process accesses a resource, it
inherits high priority until it is done with the resource in
question. Then its priority reverts to its natural value.

39
User-Level Thread Scheduling

Possible Scheduling
• 50-msec process
quantum
• Threads run 5 msec per
CPU burst

40
 Kernel-Level Thread Scheduling

Possible Scheduling
• 50-msec process
quantum
• Threads run 5 msec per
CPU burst

41
Summary (1)
• Why Scheduling?
• Basic Concepts of Scheduling
• Scheduling Criteria
• Basic Scheduling Algorithm (FCFS)
• Convoy Effects

42
Summary (2)
• Scheduling algorithms
– Shortest job first (SJF)
– Round-robin (RR)
– Priority scheduling
– Multi Queue
– Multi-Processor Scheduling
• Priority Inversion
• Thread Scheduling

43