代写 algorithm Java math operating system statistic network security Operating Systems Lecture 4b

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