Object-Oriented Programming
Operating Systems
Lecture 4a
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously
Scheduling
Time scales: Long-, medium-, and short-term scheduling
Scheduling criteria
Scheduling algorithms: FCFS, SJF, SRT, RR
1
Today
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
2
Recap: Scheduling basics
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?
3
Recap: Scheduling basics
Throughput and Turnaround Time
4
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
Recap:
FCFS + preemption at the end of a time slice
(time quantum)
Implementation: FIFO queue + Timer interrupt
13
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
Rule of thumb: 80% of CPU bursts <= time quantum Quantum too short: Too many context switches Virtual Round Robin 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 15 Multi-level Queue Scheduling Separate processes according to their expected behaviour 16 Multi-level Feedback Queue Scheduling Dynamically adapt to process behaviour move processes between queues as they change Example: 17 I/O-bound processes get served quickly CPU-bound processes get demoted RR RR Parameterised Scheduling Algorithms 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 18 Real-time Scheduling 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 19 Example: Earliest Deadline First 20 Image: Earliest Deadline First. P. Puscher, TU Wien. Real-time Scheduling A set of tasks is schedulable if and only if where Worst-Case Execution time: Ci Task deadline = period Ti 21 𝑖 𝐶𝑖 𝑇𝑖 ≤ 1 𝐶1 𝑇1 = 25 50 = 0.5 𝐶2 𝑇2 = 35 80 = 0.4375 0.5 + 0.4375 < 1 all good! Java Thread Scheduling 22 Java Thread Scheduling 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 23 Java Thread Scheduling Scheduler is run when A thread terminates A higher priority thread becomes runnable (ready) A thread calls yield() 24 Summary Scheduling algorithms Performance measures Round-Robin scheduling Multi-level queue scheduling Feedback scheduling Real-time scheduling Java thread scheduling 25 Read Tanenbaum & Bos., Modern Operating Systems Chapter 2.4 Silberschatz et al., Operating System Concepts Chapter 5 Further reading: Love. Linux Kernel Development: Chapter 4 26 Next Lecture Introduction Operating System Architectures Processes Threads - Programming Process Scheduling - Evaluation Process Synchronisation 27 Deadlocks Memory Management File Systems Input / Output Security and Virtualisation