COMP30023 – Computer Systems
Process Scheduling
© University of Melbourne
Copyright By PowCoder代写 加微信 powcoder
Which process to schedule next after [which events] ?
• Multiprogrammingrecap • Schedulingobjectives
• Schedulingalgorithms
© University of Melbourne
Multiprogramming recap
4 processes running in “parallel”:
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.
© 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
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
Scheduling is not easy
– Different workloads
– Different environments
– The scheduler has only a limited information about the processes
© University of Melbourne
Process Behavior
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
Environments
1. Batch(e.g.,periodicanalytictasks)
2. Interactive(e.g.,userfacing)
3. Realtime(e.g.,needtomeetdeadlines)
© University of Melbourne
Scheduler objectives
• 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
Scheduling Algorithm Goals
What objectives should a scheduler try to meet in all systems?
What about for each of the following systems:
1. Batch(e.g.,periodicanalytictasks)
2. Interactive(e.g.,userfacing)
3. Realtime(e.g.,needtomeetdeadlines)
© University of Melbourne
Scheduling Algorithm Goals
© University of Melbourne
Algorithm Categories
• 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
Process/Context switch
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
Algorithms
• First-Come First-Served
• Shortest Process First
• Shortest Remaining Time Next
• Priority Scheduling
• Multiple Queues
• Guaranteed Scheduling
• Lottery Scheduling
• Fair-Share Scheduling
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
Running in the original order Running shortest job first order
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?
© University of Melbourne
Shortest Job First
Running in the original order Running shortest job first order
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?
© University of Melbourne
Shortest Remaining Time Next
Preemptive Version of Shortest Job First
Blocked 4 6 7 8 Unblocked
© University of Melbourne
Shortest Remaining Time Next
Preemptive Version of Shortest Job First
Blocked 4 6 7 8 Unblocked
© University of Melbourne
The list of runnable processes.
Runnable processes after B uses up its quantum.
– 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?
© University of Melbourne
Priority Scheduling
• 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
Algorithms
• First-Come First-Served
• Shortest Process First
• Shortest Remaining Time Next
• Priority Scheduling
• Multiple Queues
• Guaranteed Scheduling
• Lottery Scheduling
• Fair-Share Scheduling
Batch systems
Interactive systems
© University of Melbourne
Summary: Process Scheduling
Building a general scheduler that works well for all is difficult
Real scheduling is more complex. Linux uses hierarchical scheduling.
Multiprocessors:
– per CPU or shared queue of processes – load balancing
© University of Melbourne
Next lecture
• Memory management • Virtual memory
• Page tables
© University of Melbourne
Acknowledgement
• 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
© University of Melbourne
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com