Operating Systems Lecture 4b
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously 1 Scheduling
Scheduling policies & performance Multi-level queue scheduling
Feedback scheduling
Real-time scheduling
Java thread scheduling
Today 2 Evaluating Scheduling Algorithms
Deterministic Evaluation Probabilistic Evaluation Stochastic Evaluation
Simulation
Implementation & Testing Coursework 1 introduction
Recap: Scheduling 3 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?
How to select a CPU scheduling algorithm? 4 Performance Evaluation
Factors to consider:
Type of system
Expected process characteristics Expected workload
Scheduling criteria/goals ! metrics
Evaluation methods: Deterministic
Probabilistic
Stochastic
Testing the implementation (ultimately)
Deterministic Evaluation 5 Given a predefined work load
First-come first-served (FCFS)
Average waiting time: 28ms
Shortest Job First (SJF)
Process
Burst time
P1
10
P2
29
P3
3
P4
7
P5
12
Average waiting time: 13ms
Deterministic Evaluation 6 Given a predefined work load
Round Robin (RR) : 10ms time quantum
Average waiting time: 23ms
Process
Burst time
P1
10
P2
29
P3
3
P4
7
P5
12
Probabilistic Evaluation
7
Analytical models
Mathematical representations of computer systems E.g. Markov chains
State
Probability of state change
Probabilistic Evaluation
8
Analytical models
???
???
Created
??? ??? ???
Ready
???
??? ???
Suspended, Ready
???
Suspended, Blocked
???
???
???
???
Running
???
???
Blocked
1.0
???
???
Terminated
Probabilistic Evaluation
9
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
Inputs
System
Measured output Comparison
Model
Predicted output
Queueing Models 10 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
Exponential Distribution 11 Rate λ > 0
E.g. arrival times
t t+1
Probability density:
𝑓 𝑥 =𝜆 ∗𝑒−𝜆∗𝑥 (forx≥0)
1 Mean: Τ
𝜆
Probability of arrival interval for one process: 𝑃 𝑙 < 𝑥 < 𝑢 = 𝑒−𝜆∗𝑙 − 𝑒−𝜆∗𝑢
Weibull Distribution 12 Rate: λ
Shape: 𝑘 (β)
𝑘 = 1 (exponential) 𝑘<1
𝑘>1
E.g. decreasing/increasing failure rates
Other distributions:
Uniform, Gaussian, Rayleigh, Fisher, etc.
Little’s Law 13 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.
Little’s Law – Conservation of Flow 14
Stochastic Evaluation 15
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
Simulation 16
Implementation and Testing 17 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
Summary 18 Evaluation of scheduling algorithms
Deterministic evaluation
Probabilistic evaluation Queueing models
Little’s Law
Stochastic evaluation Simulation models
Read 19
Silberschatz et al., Operating System Concepts Chapter 5.8
Coursework 1 20 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.)
Coursework 1 21
Input Generator
Simulator
Input data Output data
Which scheduling algorithm is most suitable for different kinds of workloads?
Coursework 1 22 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();
}
Coursework 1 23 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
Next Lecture
24
Introduction
Operating System Architectures Processes
Threads – Programming
Process Scheduling – Evaluation Process Synchronisation
Deadlocks
Memory Management
File Systems
Input / Output
Security and Virtualisation