Systems, Networks & Concurrency 2019
Scheduling 6 Uwe R. Zimmer – The Australian National University
[Ben2006]
[Stallings2001]
Ben-Ari, M
Stallings, William
Principles of Concurrent and Dis- tributed Programming
second edition, Prentice-Hall 2006
Operating Systems
[AdaRM2012]
Ada Reference Manual – Lan- guage and Standard Libraries; ISO/IEC 8652:201x (E)
© 2019 Uwe R. Zimmer, The Australian National University
page 428 of 757 (chapter 6: “Scheduling” up to page 458)
Scheduling
References for this chapter
Prentice Hall, 2001
Scheduling
Motivation and definition of terms
Purpose of scheduling
© 2019 Uwe R. Zimmer, The Australian National University page 429 of 757 (chapter 6: “Scheduling” up to page 458)
live, on-line application of scheduling algorithms.
2. Predicting system behaviours under anticipated loads.
simulated, off-line application of scheduling algorithms. Predictions are used:
Scheduling
Motivation and definition of terms
Purpose of scheduling
Two scenarios for scheduling algorithms:
1. Ordering resource assignments (CPU time, network access, …).
• at compile time: to confirm the feasibility of the system, or to predict resource needs, …
• at run time: to permit admittance of new requests or for load-balancing, …
© 2019 Uwe R. Zimmer, The Australian National University page 430 of 757 (chapter 6: “Scheduling” up to page 458)
Performance criteria: Process / user perspective:
Predictability criteria:
Waiting time Response time Turnaround time
minimize the …
minima / maxima / average / variance minima / maxima / average / variance minima / maxima / average / variance
minimize deviation from given … value / minima / maxima
System perspective:
Throughput
maximize the …
minima / maxima / average
Utilization
CPU busy time
© 2019 Uwe R. Zimmer, The Australian National University
page 431 of 757 (chapter 6: “Scheduling” up to page 458)
Scheduling
Motivation and definition of terms
Criteria
value / minima / maxima / deadlines value / minima / maxima / deadlines
© 2019 Uwe R. Zimmer, The Australian National University
page 432 of 757 (chapter 6: “Scheduling” up to page 458)
Scheduling
Definition of terms
Time scales of scheduling
ready
Short-term
executing
blocked
block or synchronize
pre-emption or cycle done
dispatch
CPU
© 2019 Uwe R. Zimmer, The Australian National University
page 433 of 757 (chapter 6: “Scheduling” up to page 458)
swap-in
swap-out
Medium-term
Scheduling
Definition of terms
Time scales of scheduling
ready
Short-term
executing
ready, suspended
suspend (swap-out) suspend (swap-out)
blocked, suspended
unblock
blocked
block or synchronize
pre-emption or cycle done
dispatch
CPU
creation
terminate.
Long-term
pre-emption or cycle done
© 2019 Uwe R. Zimmer, The Australian National University
page 434 of 757 (chapter 6: “Scheduling” up to page 458)
batch
admit
ready
Short-term executing dispatch CPU
swap-in
swap-out
Medium-term
Scheduling
Definition of terms
Time scales of scheduling
ready, suspended
suspend (swap-out) suspend (swap-out)
blocked, suspended
unblock
blocked
block or synchronize
(16, 8)
(12, 3)
(4, 1) (Ti,Ci)0
5 10 15 20 25 30 35 40
45 time
Scheduling
Performance scheduling
Requested resource times
Tasks have an average time between instantiations of Ti and a constant computation time of Ci
© 2019 Uwe R. Zimmer, The Australian National University page 435 of 757 (chapter 6: “Scheduling” up to page 458)
(16, 8)
(12, 3)
(4, 1) (Ti,Ci)0
5 10 15 20 25 30 35 40 Waiting time: 0..11, average: 5.9 – Turnaround time: 3..12, average: 8.4
45 time
Scheduling
Performance scheduling
First come, first served (FCFS)
As tasks apply concurrently for resources, the actual sequence of arrival is non-deterministic. hence even a deterministic scheduling schema like FCFS can lead to different outcomes.
© 2019 Uwe R. Zimmer, The Australian National University page 436 of 757 (chapter 6: “Scheduling” up to page 458)
(16, 8)
(12, 3)
(4, 1) (Ti,Ci)0
5 10 15 20 25 30 35 40 Waiting time: 0..11, average: 5.4 – Turnaround time: 3..12, average: 8.0
45 time
In this example:
the average waiting times vary between 5.4 and 5.9
the average turnaround times vary between 8.0 and 8.4
Scheduling
Performance scheduling
First come, first served (FCFS)
Shortest possible maximal turnaround time!
© 2019 Uwe R. Zimmer, The Australian National University page 437 of 757 (chapter 6: “Scheduling” up to page 458)
(16, 8)
(12, 3)
(4, 1) (Ti,Ci)0
15 20 25 30 35 40 45 time Waiting time: 0..5, average: 1.2 – Turnaround time: 1..20, average: 5.8
5 10
Optimized for swift initial responses. “Stretches out” long tasks.
Scheduling
Performance scheduling
Round Robin (RR)
Bound maximal waiting time! (depended only on the number of tasks)
© 2019 Uwe R. Zimmer, The Australian National University page 438 of 757 (chapter 6: “Scheduling” up to page 458)
CPU
• Implementmultiple hierarchical ready-queues.
• Fetch processes from the highest filled ready queue.
priority 1
dispatch 21 dispatch 2i
• Dispatch more CPU time for lower priorities (2i units).
priority i
Processes on lower ranks may suffer starvation.
New and short tasks will be preferred. © 2019 Uwe R. Zimmer, The Australian National University
page 439 of 757 (chapter 6: “Scheduling” up to page 458)
Scheduling
Performance scheduling
Feedback with 2i pre-emption intervals
admit
priority 0
dispatch 20
executing
(16, 8) (12, 3) (4, 1)
Scheduling
Performance scheduling
Feedback with 2i pre-emption intervals – sequential
(Ti,Ci)0 5 10 15 20 25 30 35 40 45 time Waiting time: 0..5, average: 1.5 – Turnaround time: 1..21, average: 5.7
Optimized for swift initial responses.
Prefers short tasks and long tasks can suffer starvation.
Very short initial response times! and good average turnaround times.
© 2019 Uwe R. Zimmer, The Australian National University page 440 of 757 (chapter 6: “Scheduling” up to page 458)
(16, 8) (12, 3) (4, 1)
Scheduling
Performance scheduling
Feedback with 2i pre-emption intervals – overlapping
(Ti,Ci)0 5 10 15 20 25 30 35 40 45 time Waiting time: 0..3, average: 0.9 – Turnaround time: 1..45, average: 7.7
Optimized for swift initial responses.
Prefers short tasks and long tasks can suffer starvation.
Long tasks are delayed until all queues run empty!
© 2019 Uwe R. Zimmer, The Australian National University page 441 of 757 (chapter 6: “Scheduling” up to page 458)
(16, 8)
(12, 3)
(4, 1) (Ti,Ci)0
15 20 25 30 35 40 45 time Waiting time: 0..11, average: 3.7 – Turnaround time: 1..14, average: 6.3
5 10
Optimized for good average performance with minimal task-switches. Prefers short tasks but all tasks will be handled.
Scheduling
Performance scheduling
Shortest job first
Good choice if computation times are known and task switches are expensive!
© 2019 Uwe R. Zimmer, The Australian National University page 442 of 757 (chapter 6: “Scheduling” up to page 458)
(16, 8)
(12, 3)
(4, 1) (Ti,Ci)0
15 20 25 30 35 40 45 time Waiting time: 0..10, average: 3.4 – Turnaround time: 1..14, average: 6.0
5 10
Can be sensitive to non-deterministic arrival sequences.
Scheduling
Performance scheduling
Shortest job first
© 2019 Uwe R. Zimmer, The Australian National University page 443 of 757 (chapter 6: “Scheduling” up to page 458)
(16, 8)
(12, 3)
(4, 1) (Ti,Ci)0
5 10 15 20 25 30 35 40 45 time Waiting time: 0..9, average: 4.1 – Turnaround time: 2..13, average: 6.6
Blend between Shortest-Job-First and First-Come-First-Served. Prefers short tasks but long tasks gain preference over time.
Scheduling
Performance scheduling
Highest Response Ration Wi +Ci First (HRRF) Ci
More task switches and worse averages than SJF but better upper bounds!
© 2019 Uwe R. Zimmer, The Australian National University page 444 of 757 (chapter 6: “Scheduling” up to page 458)
(16, 8)
(12, 3)
(4, 1) (Ti,Ci)0
5 10 15 20 25 30 35 40 45 time Waiting time: 0..6, average: 0.7 – Turnaround time: 1..21, average: 4.4
Optimized for good averages.
Prefers short tasks and long tasks can suffer starvation..
Scheduling
Performance scheduling
Shortest Remaining Time First (SRTF)
Better averages than Feedback scheduling but with longer absolute waiting times!
© 2019 Uwe R. Zimmer, The Australian National University page 445 of 757 (chapter 6: “Scheduling” up to page 458)
FCFS
FCFS
Waiting times
RR
FB- seq.
FB- ovlp
SJF SJF
HRRF SRTF
Scheduling
Performance scheduling
Comparison (in order of appearance)
0 5 10 15 20 25 30 35 40 45 time
© 2019 Uwe R. Zimmer, The Australian National University page 446 of 757 (chapter 6: “Scheduling” up to page 458)
Averages Turnaround times
FB- seq.
FB- ovlp
RR
SRTF
HRRF SJF
Averages Turnaround times
SJF FCFS FCFS
Scheduling
Performance scheduling
Comparison by shortest maximal waiting
0 5 10 15 20 25 30 35 40 45 time Providing upper bounds to waiting times Swift response systems
© 2019 Uwe R. Zimmer, The Australian National University page 447 of 757 (chapter 6: “Scheduling” up to page 458)
Waiting times
SRTF
FB- ovlp
RR
FB- seq.
SJF
SJF HRRF FCFS FCFS
Averages Turnaround times
Scheduling
Performance scheduling
Comparison by shortest average waiting
0 5 10 15 20 25 30 35 40 45 time Providing short average waiting times Very swift response in most cases
© 2019 Uwe R. Zimmer, The Australian National University page 448 of 757 (chapter 6: “Scheduling” up to page 458)
Waiting times
FCFS
FCFS
Waiting times
HRRF SJF
SJF RR
SRTF
FB- seq.
FB- ovlp
Scheduling
Performance scheduling
Comparison by shortest maximal turnaround
0 5 10 15 20 25 30 35 40 45 time Providing upper bounds to turnaround times No tasks are left behind
© 2019 Uwe R. Zimmer, The Australian National University page 449 of 757 (chapter 6: “Scheduling” up to page 458)
Averages Turnaround times
SRTF
FB- seq.
Averages Turnaround times
RR SJF
SJF
HRRF
FB- ovlp
FCFS FCFS
Scheduling
Performance scheduling
Comparison by shortest average turnaround
0 5 10 15 20 25 30 35 40 45 time Providing good average performance High throughput systems
© 2019 Uwe R. Zimmer, The Australian National University page 450 of 757 (chapter 6: “Scheduling” up to page 458)
Waiting times
SJF
min (C i) max ( W i + C i )
no
medium
medium
short yes controllable no
HRRF
C i
no yes
controllable compromise
controllable compromise
SRTF
very short
wide variance
short yes
Selection Pre- Waiting Turnaround emption
Preferred jobs
Starvation possible?
Methods without any knowledge about the processes
FCFS RR FB
max (W i) equal share
no long yes bound yes very short
long average & short maximum
equal no short no short no
priority queues
short average & long maximum
Methods employing computation time Ci and elapsed time Ei
min(Ci -Ei)
© 2019 Uwe R. Zimmer, The Australian National University
page 451 of 757 (chapter 6: “Scheduling” up to page 458)
Scheduling
Performance scheduling
Comparison overview
good average & large maximum
Guarantee data flow levels
Guarantee reaction times
Guarantee deadlines
Guarantee delivery times
Provide bounds for the variations in results
Examples:
• Streaming media broadcasts, playing HD videos, live mixing audio/video, …
• Reacting to users, Reacting to alarm situations, …
• Delivering a signal to the physical world at the required time, …
Scheduling
Predictable scheduling
Towards predictable scheduling …
Task requirements (Quality of service):
© 2019 Uwe R. Zimmer, The Australian National University page 452 of 757 (chapter 6: “Scheduling” up to page 458)
Common attributes:
• Minimal & maximal delay after creation
max. exec. time
• Maximal elapsed time
• Maximal execution time
• Absolutedeadline
max. elapse time
© 2019 Uwe R. Zimmer, The Australian National University
page 453 of 757 (chapter 6: “Scheduling” up to page 458)
Task i
created
20 25 30t
Scheduling
Predictable scheduling
Temporal scopes
max. delay min. delay
1 5 10
deadline
Common attributes:
• Minimal & maximal delay after creation
max. exec. time
• Maximal elapsed time
• Maximal execution time
• Absolutedeadline
max. elapse time
© 2019 Uwe R. Zimmer, The Australian National University
page 454 of 757 (chapter 6: “Scheduling” up to page 458)
Scheduling
Predictable scheduling
Temporal scopes
max. delay min. delay
Task i
created activated
20 25 30t
1 5 10
deadline
Common attributes:
• Minimal & maximal delay after creation
elapse time
• Maximal elapsed time
• Maximal execution time
• Absolutedeadline
max. elapse time
© 2019 Uwe R. Zimmer, The Australian National University
page 455 of 757 (chapter 6: “Scheduling” up to page 458)
Task i
Scheduling
Predictable scheduling
Temporal scopes
max. delay min. delay
1 5 10
20 25 30t re-activated
max. exec. time
created activated
suspended terminated
deadline
Common attributes:
execution time
• Minimal & maximal delay after creation
elapse time
• Maximal elapsed time
• Maximal execution time
• Absolutedeadline
max. elapse time
© 2019 Uwe R. Zimmer, The Australian National University
page 456 of 757 (chapter 6: “Scheduling” up to page 458)
Task i
Scheduling
Predictable scheduling
Temporal scopes
max. delay min. delay
1 5 10
20 25 30t re-activated
max. exec. time
created activated
suspended terminated
deadline
Semantics defined by application
Temporal scopes can be:
Periodic Aperiodic Sporadic / Transient
controllers, routers, schedulers, streaming processes, …
periodic ‘on average’ tasks, i.e. regular but not rigidly timed, … user requests, alarms, I/O interaction, …
Deadlines can be: “Hard”
single failure leads to severe malfunction and/or disaster results are meaningless after the deadline
only multiple or permanent failures lead to malfunction results are still useful after the deadline
“Firm” “Soft”
Scheduling
Predictable scheduling
Common temporal scope attributes
© 2019 Uwe R. Zimmer, The Australian National University page 457 of 757 (chapter 6: “Scheduling” up to page 458)
• Basic performance scheduling
• Motivation & Terms
• Levels of knowledge / assumptions about the task set
• Evaluation of performance and selection of appropriate methods
• Towards predictable scheduling • Motivation & Terms
• Categories & Examples
Scheduling
Summary
Scheduling
© 2019 Uwe R. Zimmer, The Australian National University page 458 of 757 (chapter 6: “Scheduling” up to page 458)