Object-Oriented Programming
Operating Systems
Lecture 3b
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
The elephant on campus
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
1
Image source: The Guardian
mailto:vc@sussex.ac.uk
Previously
On programming with threads
Parallel vs concurrent execution
Data vs. Task vs. Pipeline parallelism
Thread Safety
Limits of parallelisation
Hyperthreading
Java thread library
2
Today
Scheduling
Long/mid/short-term scheduling
CPU vs I/O-bound processes
Scheduling criteria
Scheduling policies: FCFS, SJF, SRT, RR
3
Recap: Multithreading / Parallelisation
Benefits of multithreading
Responsiveness
Resource sharing (communication)
Economy (creation, context switching, . . . )
Scalability (parallel architectures)
Parallelism vs Concurrency
Patterns for parallelisation: pipelines, tasks, data splitting
4
Recap: Multithreading / Parallelisation
What type of parallelism is this?
5
Recap: Multithreading / Parallelisation
What type of parallelism is this?
6
Recap: Multithreading / Parallelisation
What type of parallelism is this?
7
Scheduling
Determines the execution order of processes
8
CPU vs I/O-Bound Processes
a) CPU-bound process b) I/O-bound process
9
CPU Bursts
What kind of process is this?
10
Short-term Scheduling
Scheduler: selects process from Ready queue
Dispatcher: performs the context switch
11
Short-term Scheduling
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)
12
Short-term Scheduling
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
13
Short-term Scheduling
p is the fraction of time processes spend waiting for I/O
n is the number of processes
This model assumes independent processes.
14
utilisation = 1 – p
n
Scheduling Criteria
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)
15
Which criteria are most important depends on the kind of system used
Scheduling Algorithms
Batch Systems
First-Come First-Served
Shortest Job First
Shortest Remaining Time Next
Interactive Systems
Round Robin
Priority Scheduling
Feedback Scheduling
16
Real-Time Systems
Earliest Deadline First
Rate Monotonic Scheduling
… and many more!
First-Come First-Served (FCFS)
Process Burst time
P1 24
P2 3
P3 3
17
+ Simple implementation
(FIFO queue)
– Long average waiting times
Shortest Job First (SJF)
Process Burst time
P1 6
P2 8
P3 7
P4 3
18
„Shortest CPU burst first”
+ Is optimal: minimal average waiting time
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
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
20
Tn+1 = * tn + (1 – ) * Tn
Shortest Remaining Time First (SRT) 21
Process Arrival time Burst time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Preemptive version of SJF
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
FCFS + preemption at end of 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? 24
Summary
Scheduling
Long/mid/short-term scheduling
Scheduler and dispatcher
CPU vs I/O-bound processes
Scheduling criteria
Scheduling policies: FCFS, SJF, SRT, RR
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 (continued)
Process Synchronisation
27
Deadlocks
Memory Management
File Systems
Input / Output
Security and Virtualisation