代写 algorithm Java assembly operating system security Operating Systems Lecture 4a

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