Operating Systems Lecture 3b
Dr Ronald Grau School of Engineering and Informatics Spring term 2020
Previously 1 On programming with threads
Parallel vs concurrent execution
Data vs. Task vs. Pipeline parallelism Thread Safety
Limits of parallelisation
Hyperthreading
Java thread library
Today 2 Scheduling
Long/mid/short-term scheduling
CPU vs I/O-bound processes
Scheduling criteria
Scheduling policies: FCFS, SJF, SRT, RR
Recap: Multithreading / Parallelisation 3
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 4 What type of parallelism is this?
Recap: Multithreading / Parallelisation 5 What type of parallelism is this?
Recap: Multithreading / Parallelisation 6 What type of parallelism is this?
Scheduling 7 Determines the execution order of processes
CPU vs I/O-Bound Processes 8 a) CPU-bound process b) I/O-bound process
CPU Bursts 9 What kind of process is this?
Short-term Scheduling 10
Scheduler: selects process from Ready queue Dispatcher: performs the context switch
Short-term Scheduling 11 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 12 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
13
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 14
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 15
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) 16 + Simple implementation
(FIFO queue)
– Long average waiting times
Process
Burst time
P1
24
P2
3
P3
3
Shortest Job First (SJF) 17 „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 18
Prediction by Exponential Averaging 19
Tn+1 = * tn + (1 – ) * Tn-1
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) 20 Preemptive version of SJF
Process
Arrival time
Burst time
P1
0
8
P2
1
4
P3
2
9
P4
3
5
Priority Scheduling
21
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
22
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? 23
Summary 24 Scheduling
Long/mid/short-term scheduling Scheduler and dispatcher
CPU vs I/O-bound processes
Scheduling criteria
Scheduling policies: FCFS, SJF, SRT, RR
Read 25 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
26
Introduction
Operating System Architectures Processes
Threads – Programming
Process Scheduling (continued) Process Synchronisation
Deadlocks
Memory Management File Systems
Input / Output
Security