Computer Systems Process Scheduling
Dr. Mian M. Hamayun
m.m.hamayun@bham.ac.uk
Credits to:
Dr. Phillip Smith
Lecture Outline
Basic Concepts of CPU Scheduling
Scheduling Criteria
Scheduling Algorithms
FCFS – First Come First Serve
SJF – Shortest Job First
SRTF – Shortest Remaining Time First Priority and Round-Robin Scheduling
Slide #2 of 39
Basic Concepts
Single processor system = single process can run at a time
Others must wait until the CPU is free and can be rescheduled
Objective of multi-programming is to have some process running at all times
Maximize CPU utilization
This is a fundamental OS function
Slide #3 of 39
Scheduling
CPU Scheduling
Decides which process to execute next – is the activity of selecting the next process in the Ready queue for execution on a processor
Slide #4 of 39
When does Scheduling happen?
A scheduling decision takes place when an event occurs that interrupts the execution of a process
Possible events
Clock Interrupts (i.e. process running → ready state)
I/O Interrupts (i.e. process waiting → ready state)
Operating System Calls (read, write, process ready → waiting) Signals (e.g. Semaphores)
Slide #5 of 39
Characteristics of Process Execution
Batch Processing: CPU Bound Interactive Systems: I/O Bound
Slide #6 of 39
CPU-I/O Burst Cycle
Process execution consists of a cycle of CPU execution and I/O wait
Processes alternate between these two states
Process execution begins with a CPU burst, this is followed by an I/O burst. This pattern repeats!
Scheduler can schedule another process during I/O burst.
Eventually final CPU burst ends with a system request to terminate execution
Slide #7 of 39
Histogram of CPU Bursts
This histogram shows that most of the processes have many very short CPU bursts e.g. Interactive systems
Slide #8 of 39
CPU Scheduler
Recall: whenever the CPU becomes idle, the OS must select one of the processes in the ready queue to be executed next
This is carried out by the short-term scheduler from the processes in the ready queue
The queue is not necessarily first-in, first-out (FIFO) It may be a priority queue, tree or an unordered linked list
Conceptually, all processes are waiting for a chance to run on the CPU
Slide #9 of 39
Dispatcher
The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. This involves:
Switching context
Switching to user mode
Jumping to the proper location in the user program to restart that program
Dispatcher should be as fast as possible
It is invoked during every process switch
Time taken by dispatcher to stop one process and start another one is known as dispatch latency.
Slide #10 of 39
Levels of Scheduling
Slide #11 of 39
Non-preemptive Scheduling
Once a process is scheduled, it continues to execute on the CPU, until:
it is finished (terminates)
it releases the CPU voluntarily (cooperative scheduling)
It blocks due to an event such as I/O interrupts, waits for another process etc.
Slide #12 of 39
Preemptive Scheduling
The operating system interrupts (intervenes) processes
A scheduled process executes, until its time slice is used up
Clock interrupt returns control of CPU to scheduler (time slice expired)
► Current process is suspended and placed in the Ready queue
► New process is selected from Ready queue and executed on CPU When a process with higher priority becomes ready
Slide #13 of 39
Scheduling Criteria
Different CPU-scheduling algorithms have different properties. One may favour one class of processes over another.
Many criteria suggested, including
CPU Utilization – keep that CPU as busy as possible. 0-100%, but realistically,
40-90%
Throughput – Number of processes that complete their execution per time unit
Turnaround time – Total amount of time to execute one process to its completion.
Waiting time – Total amount of time a process has been waiting in the Ready queue
Response time – The time it takes from when a request was submitted until the first response is produced by the operating system (latency).
Others include meeting deadlines, predictability, fairness, balance and enforcing priorities.
Slide #14 of 39
Optimization Criteria
Maximize (operating system concerns) CPU Utilization
Throughput
Minimize (user concerns) Turnaround time
Waiting time
Response time
Slide #15 of 39
First Come, First Served Scheduling (FCFS)
Simplest CPU-scheduling algorithm
The process that requests the CPU first is allocated the
CPU first
Managed with a FIFO queue, process enters the ready queue
PCB linked onto tail of queue
When CPU free, it is allocated to the process at the
head of the queue
Running process then removed from queue
Slide #16 of 39
Process
Burst Time
P1
24
P2
3
P3
3
FCFS Example
Suppose the processes arrive in the order: P1 , P2 , P3. Gantt Chart as follows:
Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17ms
Slide #17 of 39
Process
Burst Time
P1
24
P2
3
P3
3
FCFS Example – 2
Suppose now that the processes arrive in the order: P2, P3, P1. Gantt Chart for
schedule:
Waiting time for P1 = 6; P2 = 0; P3 = 3
Average waiting time: (6 + 0 + 3)/3 = 3ms
Better, but shows that waiting time under an FCFS policy may vary substantially
Slide #18 of 39
Shortest-Job First (SJF) Scheduling
Associate with each process the length of the process’s next CPU burst
When the CPU is available it is assigned to the process that has the smallest next CPU burst
If next CPU bursts of two processes are the same, FCFS is used to break the tie
Better name shortest-next-CPU-burst algorithm – scheduling depends on the length of the next CPU burst of a process, rather than total length
Slide #19 of 39
SJF Example
Process
Burst Time
P1
6
P2
8
P3
7
P4
3
SJF scheduling chart
Average waiting time: (3 + 16 + 9 + 0)/4 = 7ms In comparison, FCFS would be 10.25ms
Slide #20 of 39
Optimality of SJF
Provably optimal – it gives the minimum average waiting time for a given set of processes
Moving a short process before a long one decreases the waiting time of the short process more than it increases the waiting time of the long process – hence average time decreases
Slide #21 of 39
Difficulty of SJF
Determining the length of the next CPU request is difficult!
Could ask the user (if they know)?
For this reason, SJF is difficult to implement at the level
of short-term CPU scheduling
There is no way to know the length of the next CPU burst
Approximation is a possible solution
Slide #22 of 39
Determining the Length of the next CPU burst
Exponential averaging of the measured lengths of previous CPU bursts:
Commonly, 𝝰 set to 0.5
Slide #23 of 39
Prediction of the Length of the next CPU Burst
Slide #24 of 39
Shortest Remaining Time First Scheduling
SJF is either preemptive or nonpreemptive
Choice arises when a new process arrives at the ready
queue while a previous process still executing
Next CPU burst of the newly arrived process may be shorter
than what is left of the currently executing process
Preemptive SJF will preempt the currently executing process
Nonpreemptive will allow the currently running process to finish its CPU burst
Preemptive SJF scheduling called Shortest-Remaining- Time-First (SRTF) scheduling
Slide #25 of 39
SRTF Scheduling – Example
Process
Arrival Time
Burst Time
P1
0
8
P2
1
4
P3
2
9
P4
3
5
Preemptive SJF Gantt Chart:
Average waiting time = ((10-1)+(1-1)+(17-2)+(5-3))/4 = 26/4 = 6.5ms
Slide #26 of 39
Priority Scheduling
SJF special case of general priority-scheduling algorithm
Priority associated with each process
CPU allocated to process with highest priority
Equal priority scheduled using FCFS
Slide #27 of 39
Priority Scheduling
Process
Burst Time
Priority
P1
10
3
P2
1
1
P3
2
4
P4
1
5
P5
5
2
Low vs. high priority
Priorities indicated by fixed range of numbers Low numbers = high priority
Slide #28 of 39
Priority Scheduling
Priorities can be defined internally or externally
Internal criteria = measurable quantity such as time
limits, memory requirements, number of open files
External criteria = Outside OS such as process importance, type and amount of funds paid for computation, department sponsoring the work, political factors
Slide #29 of 39
Priority Scheduling – Preemption
Preemptive vs. Non-preemptive
Preemptive will preempt the CPU if the priority of the newly arrived process in the ready queue is higher than the priority of the currently running process
Non-preemptive priority scheduling algorithm will put the new process at the head of the ready queue
Slide #30 of 39
Priority Scheduling – Problems
Indefinite blocking or starvation
A process ready to run but waiting for CPU is blocked
Low priority processes can be blocked indefinitely
A heavily loaded computer system with a steady stream of high priority processes can prevent a low-priority process from ever getting the CPU
Two things will probably happen:
Process will eventually run (at 2 A.M Sunday)
Computer will eventually crash and lose these unfinished, low priority processes
Solution: importance increases with age (aging) Increase importance by a point every 15 minutes
Slide #31 of 39
Round-Robin (RR) Scheduling
Specially designed for time-sharing systems
Similar to FCFS, but with preemption to enable the
switching of processes
Small unit of time used: time quantum or time slice
10 to 100 milliseconds in length
Ready queue is circular
CPU goes around the ready queue, allocating CPU time to each process for a time interval or up to 1 time quantum
Slide #32 of 39
Round-Robin (RR) Scheduling
Implementation treats ready queue as a FIFO queue of processes
CPU scheduler picks first process from ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process
Two things could happen:
Process may have CPU burst of less than 1 quantum, so process
will release CPU voluntarily
If process CPU burst greater than 1 time quantum, timer goes off and causes an interrupt to the OS, resulting in a context switch and process goes to the tail of ready queue
Slide #33 of 39
Round-Robin (RR) Scheduling – Example
Time quantum = 4 milliseconds Resulting RR schedule as follows:
Process
Burst Time
P1
24
P2
3
P3
3
Average waiting time = ((10 – 4) + 4 + 7)/3 = 17/3 = 5.66ms
Slide #34 of 39
Round-Robin (RR) Scheduling
If there are n processes in the ready queue and the time quantum is q, each process gets 1/n of the CPU time in chunks of at most q time units
Each process must wait no longer than (n – 1) x q time units until its next time quantum
Example:
5 processes
q = 20 milliseconds
Each process gets up to 20 milliseconds every 100 milliseconds
Slide #35 of 39
RR Scheduling Performance
Depends heavily on size of time quantum
If extremely large, RR is same as FCFS policy
If extremely small, RR can result in a large number of context switches
Slide #36 of 39
RR – Time Quantum vs. Context Switch Time
Ideally, time quantum should be large with respect to the context-switch time
If context-switch is approximately 10% of time quantum, then ~10% of CPU time will be spent context-switching
In reality, most modern systems have time quanta ranging from 10 – 100 milliseconds
In comparison, context-switch is typically less than 10 microseconds
Slide #37 of 39
Summary
Basics of CPU Scheduling CPU-I/O Burst Cycle
Preemption
Dispatcher
Scheduling Criteria
Scheduling Algorithms
FCFS, SJF, SRTF, Priority, Round-Robin
Slide #38 of 39
References / Links
Chapter # 6: CPU Scheduling, Operating System
Concepts (9th edition) by Silberschatz, Galvin & Gagne
Slide #39 of 39