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