代写 algorithm Java scala parallel concurrency operating system security Operating Systems Lecture 3b

Operating Systems Lecture 3b
Dr Ronald Grau School of Engineering and Informatics Spring term 2018

The elephant on campus 1 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
Image source: The Guardian

Previously 2 On programming with threads
 Parallel vs concurrent execution
 Data vs. Task vs. Pipeline parallelism  Thread Safety
 Limits of parallelisation
 Hyperthreading
 Java thread library

Today 3 Scheduling
 Long/mid/short-term scheduling
 CPU vs I/O-bound processes
 Scheduling criteria
 Scheduling policies: FCFS, SJF, SRT, RR

Recap: Multithreading / Parallelisation 4
Benefits of multithreading
 Responsiveness
 Resource sharing (communication)
 Economy (creation, context switching, . . . )  Scalability (parallel architectures)
Parallelism vs Concurrency
Patterns for parallelisation: pipelines, tasks, data splitting

Recap: Multithreading / Parallelisation 5 What type of parallelism is this?

Recap: Multithreading / Parallelisation 6 What type of parallelism is this?

Recap: Multithreading / Parallelisation 7 What type of parallelism is this?

Scheduling 8 Determines the execution order of processes

CPU vs I/O-Bound Processes 9 a) CPU-bound process b) I/O-bound process

CPU Bursts 10 What kind of process is this?

Short-term Scheduling 11
 Scheduler: selects process from Ready queue  Dispatcher: performs the context switch

Short-term Scheduling 12  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)

Short-term Scheduling 13  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

Short-term Scheduling
14
utilisation = 1 – pn
 p is the fraction of time processes spend waiting for I/O  n is the number of processes
 This model assumes independent processes.

Scheduling Criteria 15
 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)
Which criteria are most important depends on the kind of system used

Scheduling Algorithms 16
 Batch Systems
 First-Come First-Served
 Shortest Job First
 Shortest Remaining Time Next
 Interactive Systems  Round Robin
 Priority Scheduling
 Feedback Scheduling
 Real-Time Systems
 Earliest Deadline First
 Rate Monotonic Scheduling
… and many more!

First-Come First-Served (FCFS) 17 + Simple implementation
(FIFO queue)
– Long average waiting times
Process
Burst time
P1
24
P2
3
P3
3

Shortest Job First (SJF) 18 „Shortest CPU burst first”
+ Is optimal: minimal average waiting time
Process
Burst time
P1
6
P2
8
P3
7
P4
3
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 20
Tn+1 =  * tn + (1 – ) * Tn
 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

Shortest Remaining Time First (SRT) 21 Preemptive version of SJF
Process
Arrival time
Burst time
P1
0
8
P2
1
4
P3
2
9
P4
3
5

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
Process
Burst time
P1
24
P2
3
P3
3
FCFS + preemption at end of time slice (time quantum)
Implementation: FIFO queue + Timer interrupt
Time quantum: 4ms

How to choose the time quantum? 24

Summary 25 Scheduling
 Long/mid/short-term scheduling  Scheduler and dispatcher
 CPU vs I/O-bound processes
 Scheduling criteria
 Scheduling policies: FCFS, SJF, SRT, RR

Read 26  Tanenbaum & Bos., Modern Operating Systems
 Chapter 2.4
 Silberschatz et al., Operating System Concepts
 Chapter 5
 Further reading: Love. Linux Kernel Development:  Chapter 4

Next Lecture
27
 Introduction
 Operating System Architectures  Processes
 Threads – Programming
 Process Scheduling (continued)  Process Synchronisation
 Deadlocks
 Memory Management
 File Systems
 Input / Output
 Security and Virtualisation