Transcript Module 6: CPU Scheduling

Chapter 5: CPU Scheduling
Operating System Concepts with Java – 8th Edition
5.1
Silberschatz, Galvin and Gagne ©2009
Announcements
 Mid-term exam – Next Tuesday (10/08)
 In-class, closed book, one cheat sheet
allowed
 What topics are included – everything that
we cover until tomorrows class
 Thursday – brief review session
Operating System Concepts with Java – 8th Edition
5.2
Silberschatz, Galvin and Gagne ©2009
Scheduling Criteria
 CPU utilization – %age of time CPU is busy
 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)
Operating System Concepts with Java – 8th Edition
5.3
Silberschatz, Galvin and Gagne ©2009
Scheduling Algorithm Optimization Criteria
 Max CPU utilization
 Max throughput
 Min turnaround time
 Min waiting time
 Min response time
Operating System Concepts with Java – 8th Edition
5.4
Silberschatz, Galvin and Gagne ©2009
First-Come, First-Served (FCFS) Scheduling
 Schedule according to processes arrival time
Process
Burst Time
P1
P2
P3
24
3
3
 Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:
P1
P2
0
24
P3
27
30
 Waiting time for P1 = 0; P2 = 24; P3 = 27
 Average waiting time: (0 + 24 + 27)/3 = 17
Operating System Concepts with Java – 8th Edition
5.5
Silberschatz, Galvin and Gagne ©2009
FCFS Scheduling (Cont.)
Suppose that the processes arrive in the order:
P2 , P3 , P1
 The Gantt chart for the schedule is:
P2
0
P3
3
P1
6
30
 Waiting time for P1 = 6; P2 = 0; P3 = 3
 Average waiting time: (6 + 0 + 3)/3 = 3
 Drawback-1: Drastic variations in wait times
 Drawback-2: Convoy effect
 FCFS is non-preemptive
Operating System Concepts with Java – 8th Edition
5.6
Silberschatz, Galvin and Gagne ©2009
Shortest-Job-First (SJF) Scheduling
 Associates each process with the length of its next CPU burst

Use these lengths to schedule the process with the shortest
CPU burst time
 Shortest-next-CPU-Burst algorithm
 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

Long-term job schedulers utilize user-specified process time
limit

Users are motivated to accurately estimate job durations
 Cannot be implemented in a short-term scheduler

Estimation-based strategy
Operating System Concepts with Java – 8th Edition
5.7
Silberschatz, Galvin and Gagne ©2009
Example of SJF
Process
Arrival Time
Burst Time
P1
0.0
6
P2
2.0
8
P3
4.0
7
P4
5.0
3
 SJF scheduling chart
P1
P4
0
3
P3
9
P2
16
24
 Average waiting time = (3 + 16 + 9 + 0) / 4 = 7
Operating System Concepts with Java – 8th Edition
5.8
Silberschatz, Galvin and Gagne ©2009
Estimating Length of Next CPU Burst
 Use previous data from previous CPU bursts to estimate the
next burst
 Can be done by using the length of previous CPU bursts, using
exponential averaging
1. t n  actual length of n th CPU burst
2.  n 1  predicted value for the next CPU burst
3.  , 0    1
 n 1   t n  1    n .
4. Define :
Operating System Concepts with Java – 8th Edition
5.9
Silberschatz, Galvin and Gagne ©2009
Exponential Averaging
  =0

n+1 = n

Recent history does not count
  =1


n+1 =  tn
Only the actual last CPU burst counts
 If we expand the formula, we get:
n+1 =  tn+(1 - ) tn -1 + …
+(1 -  )j  tn -j + …
+(1 -  )n +1 0
 Since both  and (1 - ) are less than or equal to 1, each
successive term has less weight than its predecessor
Operating System Concepts with Java – 8th Edition
5.10
Silberschatz, Galvin and Gagne ©2009
Prediction of the Length of the Next CPU Burst
Operating System Concepts with Java – 8th Edition
5.11
Silberschatz, Galvin and Gagne ©2009
Pre-emptive and Non-Preemptive SJF
 What happens if a process with shorter CPU burst arrives at the
ready queue when previous process still running?
 Non-preemptive lets the current job complete before scheduling
the shortest one next
 Pre-emptive may interrupt the current job
 Shortest-remaining-time-first scheduling
 Current job will be interrupted only if the remaining time of at
least one process on ready queue is less than the remaining
time of the current process
Process
AT
BT
P1
0
8
P2
1
4
P3
2
9
P4
3
5
Operating System Concepts with Java – 8th Edition
5.12
Silberschatz, Galvin and Gagne ©2009
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 in this text
book)
 SJF is a priority scheduling where priority is the
predicted next CPU burst time
 Preemptive
 Non-preemptive
 Problem  Starvation – low priority processes may never execute
 Solution  Aging – as time progresses increase the priority of the
process
Operating System Concepts with Java – 8th Edition
5.13
Silberschatz, Galvin and Gagne ©2009
Priority Scheduling (Contd.)
 Example
Process
BT
Priority
P1
10
3
P2
1
1
P3
2
4
P4
1
5
5
2
P5
 Priority may be internally or externally specified
 Problem  Starvation – low priority processes may
never execute
 Solution  Aging – as time progresses increase the
priority of the process
Operating System Concepts with Java – 8th Edition
5.14
Silberschatz, Galvin and Gagne ©2009
Round Robin (RR)
 Designed for time-sharing systems
 FCFS with pre-emption
 Each process gets a small unit of CPU time called
time quantum
 Processes pre-empted at the end of time quantum
 New processes added to tail of ready queue
 CPU executes process at the head of the queue
 On preemption, process added to the tail
Operating System Concepts with Java – 8th Edition
5.15
Silberschatz, Galvin and Gagne ©2009
Example of RR with Time Quantum = 4
Process
P1
Burst Time
24
P2
P3
3
3
 The Gantt chart is:
P1
0
P2
4
P3
7
P1
10
P1
14
P1
18 22
P1
26
P1
30
 Average wait time is 17/3 milliseconds
 Typically, higher average turnaround than SJF, but better response
Operating System Concepts with Java – 8th Edition
5.16
Silberschatz, Galvin and Gagne ©2009
Round Robin (Contd.)
 If there are n processes and the time quantum is q, 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 depends heavily on time quantum duration

q large  FIFO

q small  Processor sharing appearance of each
process having its own processor (was used in CDC
hardware)

In general, having too small quantum duration is bad –
why?

Context-switch time should be small fraction of quantum
duration
 Turn-around time also depends upon time-quantum duration

Does not monotonically improve as quantum increases
Operating System Concepts with Java – 8th Edition
5.17
Silberschatz, Galvin and Gagne ©2009
Time Quantum and Context Switch Time
Operating System Concepts with Java – 8th Edition
5.18
Silberschatz, Galvin and Gagne ©2009
Turnaround Time Varies With
The Time Quantum
Operating System Concepts with Java – 8th Edition
5.19
Silberschatz, Galvin and Gagne ©2009
Multilevel Queue
 Crafted for situations with multiple job categories
(e.g., interactive and batch processes running on the
same machine
 Ready queue is partitioned into separate queues:

Foreground (interactive)

Background (batch)
 Jobs permanently assigned to one of the queues
 Each queue has its own scheduling algorithm

foreground – RR

background – FCFS
Operating System Concepts with Java – 8th Edition
5.20
Silberschatz, Galvin and Gagne ©2009
Multilevel Queue Scheduling
Operating System Concepts with Java – 8th Edition
5.21
Silberschatz, Galvin and Gagne ©2009
Multilevel Queue (Contd.)
 Scheduling must be also done between the queues
 Fixed priority scheduling

No process from lower priority queue is executed unless all
higher priority queues are empty

Possibility of Starvation
 Time slice – each queue gets a certain amount of
CPU time which it can schedule amongst its
processes

80% to foreground in RR

20% to background in FCFS
Operating System Concepts with Java – 8th Edition
5.22
Silberschatz, Galvin and Gagne ©2009
Multilevel Feedback Queue
 In multi-level queues jobs are permanently assigned
to queues

Simple but inflexible
 MFQ allows processes to move between queues
 Process using too much CPU time will move to a
lower priority queue
 Process waiting for too long in a lower priority queue
can be promoted

Aging to prevent starvation
Operating System Concepts with Java – 8th Edition
5.23
Silberschatz, Galvin and Gagne ©2009
Multilevel Feedback Queues
Operating System Concepts with Java – 8th Edition
5.24
Silberschatz, Galvin and Gagne ©2009
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 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.
Operating System Concepts with Java – 8th Edition
5.25
Silberschatz, Galvin and Gagne ©2009
Multilevel Feedback Queue (Contd.)
 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
Operating System Concepts with Java – 8th Edition
5.26
Silberschatz, Galvin and Gagne ©2009
Multiple-Processor Scheduling
 CPU scheduling more complex when multiple CPUs
are available
 Homogeneous processors within a multiprocessor
 Asymmetric multiprocessing

Scheduling decisions and I/O processing handled by a
single processor

Simple because it alleviates the need for data sharing
 Symmetric multiprocessing

each processor is self-scheduling

all processes can be in common ready queue, or each can
have its own private queue of ready processes

Need for synchronization
Operating System Concepts with Java – 8th Edition
5.27
Silberschatz, Galvin and Gagne ©2009
Multiple-Processor Scheduling Issues
 Processor Affinity
 Load Balancing
 Scheduling on Multi-Cores
Operating System Concepts with Java – 8th Edition
5.28
Silberschatz, Galvin and Gagne ©2009
Processor Affinity
 Migrating processes from one processor to another is
expensive

Data caching at processors

Needs invalidation and repopulation
 Processor affinity – process has affinity for processor on
which it is currently running
 Soft affinity

Attempt to keep process on same machine – no guarantees
 Hard affinity

Processes can specify that they should not be migrated

Most Oses provide this option
Operating System Concepts with Java – 8th Edition
5.29
Silberschatz, Galvin and Gagne ©2009
NUMA and CPU Scheduling
 CPUs have faster access to certain parts of memory
 Memory allocation on the same board where a process has affinity
 Requires memory allocation and scheduler to work in tandem
Operating System Concepts with Java – 8th Edition
5.30
Silberschatz, Galvin and Gagne ©2009
Load Balancing
 Important to keep the workload balanced
 Load imbalances can reduce throughput of the system

Some processors might be overloaded whereas others may sit idle
 Load balancing typically needed on machines with private run
queues
 Push Migration

Dedicated task checks for loads and re-distributes
 Pull Migration

Idle processors “pull” tasks from overloaded processors
 Tension between processor affinity and load balancing
Operating System Concepts with Java – 8th Edition
5.31
Silberschatz, Galvin and Gagne ©2009
Virtualization and Scheduling
 Host OS and Guest OSes
 Virtualization software presents virtual CPUs to guest OSes
 Physical CPU is multiplexed among guest Oses
 Scheduling algorithms that assume certain amount of
progress in certain amount of time will be affected by
virtualization
 A process of guest OS might not get 100ms of CPU time
although the guest OS allocated 100ms of CPU time
 Virtualization may counteract scheduling algorithm benefits
Operating System Concepts with Java – 8th Edition
5.32
Silberschatz, Galvin and Gagne ©2009