Object-Oriented Programming
Operating Systems
Lecture 4b
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously
Scheduling
Scheduling policies & performance
Multi-level queue scheduling
Feedback scheduling
Real-time scheduling
Java thread scheduling
1
Today
Evaluating Scheduling Algorithms
Deterministic Evaluation
Probabilistic Evaluation
Stochastic Evaluation
Simulation
Implementation & Testing
Coursework 1 introduction
2
Recap: Scheduling
Questions:
What happens if the chosen time quantum for RR is too large?
What is the purpose of multi-level queue scheduling?
What is the effect of using feedback in multi-level queue scheduling?
In what kind of system would we commonly find periodic processes?
Under which conditions can a set of periodic processes be scheduled to not miss
their deadlines?
Can a Java thread be preempted by the OS?
3
How to select a CPU scheduling algorithm?
Performance Evaluation
Factors to consider:
Type of system
Expected process characteristics
Expected workload
Scheduling criteria/goals ! metrics
4
Evaluation methods:
Deterministic
Probabilistic
Stochastic
Testing the implementation (ultimately)
Deterministic Evaluation
Given a predefined work load
First-come first-served (FCFS)
Shortest Job First (SJF)
5
Process Burst time
P1 10
P2 29
P3 3
P4 7
P5 12
Average waiting time: 28ms
Average waiting time: 13ms
Deterministic Evaluation
Given a predefined work load
Round Robin (RR) : 10ms time quantum
6
Process Burst time
P1 10
P2 29
P3 3
P4 7
P5 12
Average waiting time: 23ms
Probabilistic Evaluation
Analytical models
Mathematical representations of computer systems
E.g. Markov chains
7
State
Probability of
state change
Probabilistic Evaluation
Analytical models
8
Created
Terminated
Running
Blocked
Ready
???
???
???
???
???
???
Suspended,
Ready
Suspended,
Blocked
???
???
???
???
???
???
???
??? ???
1.0
???
???
Probabilistic Evaluation
Analytical models
Pros
Large body of existing work
Can be applied to new problems
Relatively fast and accurate
Cons
Probabilities are only approximations of real behaviour
Systems can be too complex to model everything
Must use other techniques to validate results
9
Inputs
System Model
Measured output Predicted output
Comparison
Queueing Models
Computer system:
A network of servers, each with a queue of waiting processes
Knowing arrival rates and service rates
Computes throughput, average queue
length, average wait time, etc
Arrival of processes & CPU and I/O bursts
can be determined probabilistically
Typically, these are exponentially
distributed and described by their
mean value
10
Exponential Distribution
Rate λ > 0
E.g. arrival times
Probability density:
𝑓 𝑥 = 𝜆 ∗ 𝑒−𝜆∗𝑥 (for x ≥ 0)
Mean: Τ1 𝜆
Probability of arrival interval for one process: 𝑃 𝑙 < 𝑥 < 𝑢 = 𝑒−𝜆∗𝑙 − 𝑒−𝜆∗𝑢 11 t t+1 Weibull Distribution Rate: λ Shape: 𝑘 (β) 𝑘 = 1 (exponential) 𝑘 < 1 𝑘 > 1
E.g. decreasing/increasing failure rates
Other distributions:
Uniform, Gaussian, Rayleigh, Fisher, etc.
12
Little’s Law
Assuming a system in steady state, processes that are leaving the queue must equal
processes arriving at the queue
L = 𝜆 ∗ 𝑊
where
L : average queue length
W : average waiting time in queue
𝜆 : average arrival rate into queue
Valid for any scheduling algorithm and arrival distribution
Given two parameters we can determine the third:
For example, if 7 processes arrive per second on average,
and there are 14 processes in queue on average, then the
average wait time per process = 2 seconds.
13
Little’s Law – Conservation of Flow 14
Stochastic Evaluation
Simulation
Programmed model of computer system
Gather statistics indicating algorithm performance
Data to drive simulation gathered via
Random generation informed by probability distributions (mathematical/empirical)
Data recorded from real systems (trace tape of sequences of events)
Pros & Cons
More accurate
Bugs in the simulation
Imprecise modelling, deliberate omissions (due to complexity)
Results of a simulation must be validated
15
Simulation 16
Implementation and Testing
The real thing
Even the best simulations have limited accuracy
We could also implement our own scheduler and
Test it with hand-crafted / random-generated data
Test it in real systems
Parameterisation of scheduler important for compatibility & fine-tuning
High cost, high risk
17
Summary
Evaluation of scheduling algorithms
Deterministic evaluation
Probabilistic evaluation
Queueing models
Little’s Law
Stochastic evaluation
Simulation models
18
Read
Silberschatz et al., Operating System Concepts
Chapter 5.8
19
Coursework 1
Basics
Demonstrate that you understand how CPU Scheduling works
Write simple classes to simulate scheduling algorithms
Create, run and save experimental data from simulations
Write a report to present your results
Create hypotheses about expected behaviour and discuss your evidence / results
Basic statistics (mean, variance, etc.)
Visualise data (tables, charts, etc.)
20
Coursework 1
Which scheduling algorithm is most suitable for different kinds of workloads?
21
Input
Generator
SimulatorInput data Output data
Coursework 1
public abstract class AbstractScheduler {
// Initializes with given parameters
public void initialize(Properties parameters) {
}
// Adds a process to the ready queue.
public abstract void ready(Process process);
// Returns the next process to be run
// and removes it from the ready queue
public abstract Process schedule();
}
22
Coursework 1
Find the assignment description and detailed guidelines on
Study Direct (Module Assessment)
Read the guidelines carefully!
E-submission via Study Direct
Deadline 22 March 2018 , 4PM
23
Next Lecture
Introduction
Operating System Architectures
Processes
Threads – Programming
Process Scheduling – Evaluation
Process Synchronisation
24
Deadlocks
Memory Management
File Systems
Input / Output
Security and Virtualisation