程序代写代做代考 file system kernel Java algorithm concurrency Operating Systems Lecture 3b

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

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

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

Recap: Multithreading / Parallelisation 3
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 4 What type of parallelism is this?

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

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

Scheduling 7 Determines the execution order of processes

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

CPU Bursts 9 What kind of process is this?

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

Short-term Scheduling 11  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 12  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
13
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 14
 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 15
 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) 16 + Simple implementation
(FIFO queue)
– Long average waiting times
Process
Burst time
P1
24
P2
3
P3
3

Shortest Job First (SJF) 17 „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 18

Prediction by Exponential Averaging 19
Tn+1 =  * tn + (1 – ) * Tn-1
 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) 20 Preemptive version of SJF
Process
Arrival time
Burst time
P1
0
8
P2
1
4
P3
2
9
P4
3
5

Priority Scheduling
21
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
22
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? 23

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

Read 25  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
26
 Introduction
 Operating System Architectures  Processes
 Threads – Programming
 Process Scheduling (continued)  Process Synchronisation
 Deadlocks
 Memory Management  File Systems
 Input / Output
 Security