程序代写代做代考 assembly Java flex algorithm file system Object-Oriented Programming

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