Operating Systems Lecture 3b
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
The elephant on campus 1 What is going to happen with operating systems during the strike?
Lectures and Labs will keep running as usual
Lectures will be recorded as usual, too – those who want to support their lecturers during the industrial action can do so without disadvantage
If you want to help getting the current problems resolved as soon as possible, consider sending your suggestions to the University’s Vice-Chancellor:
Professor Adam Tickell: vc@sussex.ac.uk
Image source: The Guardian
Previously 2 On programming with threads
Parallel vs concurrent execution
Data vs. Task vs. Pipeline parallelism Thread Safety
Limits of parallelisation
Hyperthreading
Java thread library
Today 3 Scheduling
Long/mid/short-term scheduling
CPU vs I/O-bound processes
Scheduling criteria
Scheduling policies: FCFS, SJF, SRT, RR
Recap: Multithreading / Parallelisation 4
Benefits of multithreading
Responsiveness
Resource sharing (communication)
Economy (creation, context switching, . . . ) Scalability (parallel architectures)
Parallelism vs Concurrency
Patterns for parallelisation: pipelines, tasks, data splitting
Recap: Multithreading / Parallelisation 5 What type of parallelism is this?
Recap: Multithreading / Parallelisation 6 What type of parallelism is this?
Recap: Multithreading / Parallelisation 7 What type of parallelism is this?
Scheduling 8 Determines the execution order of processes
CPU vs I/O-Bound Processes 9 a) CPU-bound process b) I/O-bound process
CPU Bursts 10 What kind of process is this?
Short-term Scheduling 11
Scheduler: selects process from Ready queue Dispatcher: performs the context switch
Short-term Scheduling 12 Scheduler: selects process from Ready queue
Dispatcher: performs the context switch
When is scheduling happening?
After process creation
After ISR completion
A process blocks (I/O request, synchronisation, . . . ) At end of time slice
After process termination
On a yield system call (voluntary release of CPU)
Short-term Scheduling 13 Non-preemptive
The current process retains a hold over the CPU until returning control
Preemptive
Scheduler takes control of the CPU even though the current process could continue executing
Short-term Scheduling
14
utilisation = 1 – pn
p is the fraction of time processes spend waiting for I/O n is the number of processes
This model assumes independent processes.
Scheduling Criteria 15
CPU utilisation (“Load”): Percentage of time the CPU is busy
Throughput: Processes per second handled
Turnaround time: Time from submission to completion
Waiting time: Time processes spend in the Ready queue
Response time: Time from submission to the first response (Interactive systems)
Meeting deadlines: Operating within required time constraints (real-time systems)
Predictability: Avoiding erratic behaviour that needs frequent correction
Fairness: Every process gets a turn.
Balance: All system components well-used, not just the CPU.
Policy enforcement: Some things are more important than others (e.g. make sure critical processes can run when needed)
Which criteria are most important depends on the kind of system used
Scheduling Algorithms 16
Batch Systems
First-Come First-Served
Shortest Job First
Shortest Remaining Time Next
Interactive Systems Round Robin
Priority Scheduling
Feedback Scheduling
Real-Time Systems
Earliest Deadline First
Rate Monotonic Scheduling
… and many more!
First-Come First-Served (FCFS) 17 + Simple implementation
(FIFO queue)
– Long average waiting times
Process
Burst time
P1
24
P2
3
P3
3
Shortest Job First (SJF) 18 „Shortest CPU burst first”
+ Is optimal: minimal average waiting time
Process
Burst time
P1
6
P2
8
P3
7
P4
3
How do we know the length of the next CPU burst of a process?
Requires good predictability!
Prediction by Exponential Averaging 19
Prediction by Exponential Averaging 20
Tn+1 = * tn + (1 – ) * Tn
tn is the (known) length of the most recent burst
Tn+1 is the prediction of the next burst
T0 is initialised e.g. to average expected burst length
[0, 1] gives weight to the history, e.g. 1/2
Shortest Remaining Time First (SRT) 21 Preemptive version of SJF
Process
Arrival time
Burst time
P1
0
8
P2
1
4
P3
2
9
P4
3
5
Priority Scheduling
22
Process
Priority
Burst time
P1
3
10
P2
1
1
P3
4
2
P4
5
1
P5
2
5
Lowest number is highest priority
Processes with same priority scheduled FCFS
Implementation: Priority queue
Starvation possible, i.e. indefinite waiting Aging: gradually increase priority
Round Robin
23
Process
Burst time
P1
24
P2
3
P3
3
FCFS + preemption at end of time slice (time quantum)
Implementation: FIFO queue + Timer interrupt
Time quantum: 4ms
How to choose the time quantum? 24
Summary 25 Scheduling
Long/mid/short-term scheduling Scheduler and dispatcher
CPU vs I/O-bound processes
Scheduling criteria
Scheduling policies: FCFS, SJF, SRT, RR
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 (continued) Process Synchronisation
Deadlocks
Memory Management
File Systems
Input / Output
Security and Virtualisation