CS代写 COMP30023 – Computer Systems

COMP30023 – Computer Systems

© University of Melbourne

Copyright By PowCoder代写 加微信 powcoder

Process Scheduling

Which process to schedule next after [which events] ?

• Multiprogramming recap
• Scheduling objectives
• Scheduling algorithms

© University of Melbourne

Multiprogramming increases system efficiency. When one
process needs to wait for e.g. data from disk or keyboard input,
another process can make use of the CPU.

Multiprogramming recap

© University of Melbourne

4 processes running in “parallel”:

Scheduler picks which process to run and for how long
How: based on a scheduling algorithm

• Process creation
• Process exit
• Process blocks
• Interrupt

Scheduler input: processes in ready state (kept in run queue)

© University of Melbourne

Process Scheduler

Scheduler picks which process to run and for how long
How: based on a scheduling algorithm

• Process creation
• Process exit
• Process blocks
• Interrupt

Scheduler input: processes in ready state (kept in run queue)

© University of Melbourne

Process Scheduler

Scheduler picks which process to run and for how long
How: based on a scheduling algorithm

• Process creation
• Process exit
• Process blocks
• Interrupt

Scheduler input: processes in ready state (kept in run queue)

© University of Melbourne

Process Scheduler

Scheduler picks which process to run and for how long
How: based on a scheduling algorithm

• Process creation
• Process exit
• Process blocks
• Interrupt

Scheduler input: processes in ready state (kept in run queue)

© University of Melbourne

Process Scheduler

– Different workloads
– Different environments
– The scheduler has only a limited information about

the processes

© University of Melbourne

Scheduling is not easy

Bursts of CPU usage alternate with periods of waiting for I/O. (a) A CPU-
bound process. (b) An I/O-bound process.

© University of Melbourne

Process Behavior

1. Batch (e.g., periodic analytic tasks)
2. Interactive (e.g., user facing)
3. Real time (e.g., need to meet deadlines)

© University of Melbourne

Environments

• Fairness
– all processes get fair share of the CPU

• Throughput
– number of processes that complete per unit time

• Turnaround Time
– time from process start to its completion

• Response Time
– time from when a request was first submitted until first

response is produced

© University of Melbourne

Scheduler objectives

© University of Melbourne

Scheduling Algorithm Goals

What objectives should a scheduler try to
meet in all systems?
What about for each of the following
1. Batch (e.g., periodic analytic tasks)
2. Interactive (e.g., user facing)
3. Real time (e.g., need to meet deadlines)

© University of Melbourne

Scheduling Algorithm Goals

• Non-preemptive
– Process runs until it finishes or blocks

• Preemptive
– Process can be suspended after some time interval

(indicated by a clock interrupt)

© University of Melbourne

Algorithm Categories

Context switching takes time

Involves saving and reloading process states:
– saving and loading registers and memory maps

(program counter, stack pointer etc)
– updating various memory tables and lists

© University of Melbourne

Process/Context switch

• First-Come First-Served
• Shortest Process First
• Shortest Remaining Time Next
• Priority Scheduling
• Multiple Queues
• Guaranteed Scheduling
• Lottery Scheduling
• Fair-Share Scheduling

© University of Melbourne

Algorithms

Batch systems

Interactive systems

© University of Melbourne

First-come first-served

© University of Melbourne

First-come first-served

© University of Melbourne

First-come first-served

Blocked Unblocked

© University of Melbourne

First-come first-served

Blocked Unblocked

Pros? Simple and fair

Cons? What if B is CPU-bound
and F is IO-bound?

© University of Melbourne

Shortest Job First

What is the average turnaround time of (a)? (b)?
(a) (8 + 12 + 16 + 20)/4 = 14
(b) (4 + 8 + 12 + 20)/4 = 11

What if jobs did not arrive at the same time?

Running shortest job first orderRunning in the original order

© University of Melbourne

Shortest Job First

What is the average turnaround time of (a)? (b)?
(a) (8 + 12 + 16 + 20)/4 = 14
(b) (4 + 8 + 12 + 20)/4 = 11

What if jobs did not arrive at the same time?

Running shortest job first orderRunning in the original order

© University of Melbourne

Shortest Remaining Time Next

Preemptive Version of Shortest Job First

Blocked Unblocked3 4 6 7 8

© University of Melbourne

Shortest Remaining Time Next

Preemptive Version of Shortest Job First

Blocked Unblocked3 4 6 7 8

© University of Melbourne

Runnable processes after B uses up
its quantum.

The list of runnable processes.

– The scheduler sets a timer to generate an interrupt after a particular
amount of time, quantum
– The amount of time that a process can run without interruption*
– How to set quantum?

• Important jobs always run before less important jobs.
• For example: system processes are more important

than user processes in some cases.
• Static vs. dynamic prioritisation
• Potential problem: starvation; possible that low priority

jobs will never execute, if more important jobs
continually arrive.

© University of Melbourne

Priority Scheduling

© University of Melbourne

Priority Scheduling

• First-Come First-Served
• Shortest Process First
• Shortest Remaining Time Next
• Priority Scheduling
• Multiple Queues
• Guaranteed Scheduling
• Lottery Scheduling
• Fair-Share Scheduling

© University of Melbourne

Algorithms

Batch systems

Interactive systems

Building a general scheduler that works well for all is

Real scheduling is more complex. Linux uses hierarchical
scheduling.

Multiprocessors:
– per CPU or shared queue of processes
– load balancing

© University of Melbourne

Summary: Process Scheduling

• Memory management
• Virtual memory
• Page tables

© University of Melbourne

Next lecture

• The slides were prepared by .
• Some of the images included in the notes were supplied as

part of the teaching resources accompanying the text books
listed in lecture 1.

• Reference: TB 2.4

Acknowledgement

© University of Melbourne 34

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com