程序代写代做代考 Java algorithm file system chain Object-Oriented Programming

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