Operating Systems Lecture 4a
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously 1 Scheduling
Time scales: Long-, medium-, and short-term scheduling Scheduling criteria
Scheduling algorithms: FCFS, SJF, SRT, RR
Today 2 Scheduling
Performance overview of last week’s scheduling policies: FCFS, SJF, SRT, RR Another look at Round Robin
Multi-level queue scheduling
Feedback scheduling
Parametrised Scheduling Algorithms Real-time scheduling
Java thread scheduling
Recap: Scheduling basics 3 Questions:
What are CPU-bound and I/O-bound processes? What is starvation?
What is throughput?
What is turnaround time?
What is waiting time?
Why is it important for a scheduling algorithm to be fair?
Recap: Scheduling basics 4 Throughput and Turnaround Time
https://www.neweurope.eu/wp-content/uploads/2011/12/auto-assembly-line-1.jpg
Performance of scheduling policies 5
First-Come First- Served
Shortest Job First
Shortest Remaining Time
Round Robin
Selection function
max waiting time
min execution time
min remaining execution time
max waiting time
Performance of scheduling policies 6
First-Come First- Served
Shortest Job First
Shortest Remaining Time
Round Robin
Selection function
max waiting time
min execution time
min remaining execution time
max waiting time
Decision mode
non-preemptive
non-preemptive
preemptive
Preemptive (at time quantum)
Performance of scheduling policies 7
First-Come First- Served
Shortest Job First
Shortest Remaining Time
Round Robin
Selection function
max waiting time
min execution time
min remaining execution time
max waiting time
Decision mode
non-preemptive
non-preemptive
preemptive
Preemptive (at time quantum)
Overhead
very small
can be high
can be high
very small
Performance of scheduling policies 8
First-Come First- Served
Shortest Job First
Shortest Remaining Time
Round Robin
Selection function
max waiting time
min execution time
min remaining execution time
max waiting time
Decision mode
non-preemptive
non-preemptive
preemptive
Preemptive (at time quantum)
Overhead
very small
can be high
can be high
very small
Fairness
penalises short processes
penalises long processes
penalises long processes
fair
Performance of scheduling policies 9
First-Come First- Served
Shortest Job First
Shortest Remaining Time
Round Robin
Selection function
max waiting time
min execution time
min remaining execution time
max waiting time
Decision mode
non-preemptive
non-preemptive
preemptive
Preemptive (at time quantum)
Overhead
very small
can be high
can be high
very small
Fairness
penalises short processes
penalises long processes
penalises long processes
fair
Starvation
no
possible
possible
no
Performance of scheduling policies 10
First-Come First- Served
Shortest Job First
Shortest Remaining Time
Round Robin
Selection function
max waiting time
min execution time
min remaining execution time
max waiting time
Decision mode
non-preemptive
non-preemptive
preemptive
Preemptive (at time quantum)
Overhead
very small
can be high
can be high
very small
Fairness
penalises short processes
penalises long processes
penalises long processes
fair
Starvation
no
possible
possible
no
Throughput
variable
high
high
depends on time quantum
Performance of scheduling policies 11
First-Come First- Served
Shortest Job First
Shortest Remaining Time
Round Robin
Selection function
max waiting time
min execution time
min remaining execution time
max waiting time
Decision mode
non-preemptive
non-preemptive
preemptive
Preemptive (at time quantum)
Overhead
very small
can be high
can be high
very small
Fairness
penalises short processes
penalises long processes
penalises long processes
fair
Starvation
no
possible
possible
no
Throughput
variable
high
high
depends on time quantum
Waiting time
can be high
good for short proc.
better than SJF
depends on time quantum
Scheduling Algorithms 12
Another look at Round Robin 13 Recap:
FCFS + preemption at the end of a time slice (time quantum)
Implementation: FIFO queue + Timer interrupt
Process
Burst time
P1
24
P2
3
P3
3
Time quantum: 4ms
How to choose the time quantum? 14
Quantum too large: Scheduling degenerates and works like FCFS Quantum too short: Too many context switches
Rule of thumb: 80% of CPU bursts <= time quantum
Virtual Round Robin 15 Problem of RR
I/O-bound processes use only a small fraction of their time slice spend a long time in the Ready queue
VRR
Auxiliary queue higher priority
Multi-level Queue Scheduling 16 Separate processes according to their expected behaviour
Multi-level Feedback Queue Scheduling 17 Dynamically adapt to process behaviour
move processes between queues as they change Example:
I/O-bound processes get served quickly CPU-bound processes get demoted
RR
RR
Parameterised Scheduling Algorithms 18 Scheduling policies can be flexibly designed and highly configurable
E.g. Multi-level Feedback Queues
Number of levels in the scheduling system
Methods for determining at which level a process is admitted
Methods for upgrading and demoting processes between queues
Choice of scheduling algorithm at every level e.g. Round Robin
time quantum parameter
Real-time Scheduling 19
Processes with periodic arrival times
Deadlines
Hard real-time: Guarantee that there are no deadline misses Soft real-time: Minimise number of deadline misses
Preemptive scheduling with static or dynamic priorities
Example: Earliest Deadline First 20
Image: Earliest Deadline First. P. Puscher, TU Wien.
Real-time Scheduling
21
A set of tasks is schedulable if and only if
𝑖
where
Worst-Case Execution time: Ci Task deadline = period Ti
𝑇 𝑖
𝐶 𝑖≤1
𝐶 25
1= =0.5
𝑇 50 1
𝐶 35
2 = =0.4375
𝑇 80 2
0.5 + 0.4375 < 1 all good!
Java Thread Scheduling 22
Java Thread Scheduling 23 Scheduling policy
Early Java versions: user threads map to one kernel thread
FCFS + priorities, preemptive
Today:
Depends on operating system,
user threads map 1:1 to kernel-threads
Java Thread Scheduling 24 Scheduler is run when
A thread terminates
A higher priority thread becomes runnable (ready) A thread calls yield()
Summary 25 Scheduling algorithms
Performance measures
Round-Robin scheduling
Multi-level queue scheduling Feedback scheduling
Real-time scheduling
Java thread scheduling
Read 26 Tanenbaum & Bos., Modern Operating Systems
Chapter 2.4
Silberschatz et al., Operating System Concepts
Chapter 5
Further reading: Love. Linux Kernel Development: Chapter 4
Next Lecture
27
Introduction
Operating System Architectures Processes
Threads - Programming
Process Scheduling - Evaluation Process Synchronisation
Deadlocks
Memory Management
File Systems
Input / Output
Security and Virtualisation