Chapter: CPU/ Process Scheduling
(Unit-2)
Basic Concept
CPU Scheduling is basis of Multi-programmed OS
Objective of Multi-programming is to have some processes
running all the time to maximize CPU Utilization.
Sequence of CPU and I/O Bursts
CPU Burst- when process is executed in CPU
CPU Burst Time: The amount of time the process uses
the processor
Types of CPU bursts:
Long bursts -- process is CPU bound (spend max. time with
CPU
Short bursts -- process is I/O bound (spend max. time with I/O)
I/O Burst- when CPU is waiting for I/O completion for
further execution.
Sequence of CPU and I/O Bursts
CPU Scheduling Decisions
1. When process switches from 1. Non-preemptive
Running State to Waiting State
(i/o request or wait)
2. When process switches from 2. Pre-emptive
Running to Ready State
(interrupt)
3. When process switches from 3. Pre-emptive
Waiting State to Ready State
(at completion of i/o)
4. Non-Preemptive
4. When a process terminates (allow)
Process States
Scheduling
Non-Preemptive
Preemptive
Non-Preemptive
Once the CPU is allocated to a process, process keeps
the CPU until:
it releases when it completes
by switching to waiting state
E.g : 1. Windows 3.x and Apple Macintosh operating
systems uses non-preemptive scheduling
2. Windows (also 10) uses a round-robin technique with
a multi-level feedback queue for priority scheduling
Process is executed till completion. It cannot be
interrupted.
Eg First In First Out
Preemptive Scheduling
The running process is interrupted for some
time and resumed later on, when the priority
task has finished its execution.
CPU /resources is/are taken away from the
process when some high priority process
needs execution.
Dispatcher
A module that gives control of CPU to the process
selected by short-term scheduler.
Functions:
Switching Context
Switching to User mode
Jumping to proper location to restart the program.
The dispatcher should be as fast as possible, given that
it is invoked during every process switch
Dispatch Latency:
Time taken for the dispatcher to stop one process and start
another running.
Scheduling Criteria
Which algorithm to use in a particular situation
1. CPU Utilization: CPU should be busy to the fullest
2. Throughput: No. of processes completed per unit of
time.
3. Turnaround Time: The time interval from submitting a
process to the time of completion.
Turnaround Time= Time spent to get into memory + waiting
in ready queue + doing I/O + executing on CPU
(It is the amount of time taken to execute a particular process)
Scheduling Criteria
4. Waiting Time: Time a process spends in a ready queue.
Amount of time a process has been waiting in the ready
queue to acquire control on the CPU.
5. Response Time: Time from the submission of a request
to the first response, Not Output
6. Load Average: It is the average number of processes
residing in the ready queue waiting for their turn to get
into the CPU.
Scheduling Algorithm Optimization Criteria
Max CPU utilization
Max throughput
Min turnaround time
Min waiting time
Min response time
Formula
Turn around time= Completion Time- Arrival Time
Waiting Time= Turn around Time-Burst Time
OR
Turnaround time = Burst time + Waiting time
First-Come, First-Served (FCFS)
Processes that request CPU first, are allocated the CPU
first
It is non-preemptive scheduling algorithm
FCFS is implemented with FIFO queue.
A process is allocated the CPU according to their arrival
times.
When process enters the ready queue, its PCB is attached
to the Tail of queue, When CPU is free, it is allocated to the
process selected from Head/Front of queue.
First-Come, First-Served (FCFS)
“Run until Completed:” FIFO algorithm
Example: Consider three processes arrive in order
P1, P2, and P3.
P1 burst time: 24
P2 burst time: 3
P3 burst time: 3
Draw the Gantt Chart and compute Average Waiting
Time and Average Turn Around Time.
Sol: As arrival time is not given assume order of arrival
as: P1,P2,P3
17
First-Come, First-Served (FCFS)
Example: Three processes arrive in order P1, P2, P3.
P1 burst time: 24
P2 burst time: 3
P3 burst time: 3
Waiting Time
P1: 0 P1 P2 P3
P2: 24
0 24 27 30
P3: 27
Turnaround Time/Completion Time:
P1: 24
P2: 27
P3: 30
Average Waiting Time: in milliseconds
Average Completion Time: in milliseconds
Example: First-Come, First-Served (FCFS)
Example: First-Come, First-Served (FCFS)
First Come First Serve
Process AT BT CT TAT WT
P1 0 2
P2 3 1
P3 5 6
First Come First Serve (Convoy Effect
H.W
Process AT BT CT TAT WT
P1 0 4
Calculate avg. P2 1 3
CT, TAT,WT P3 2 1
P4 3 2
P5 4 5
First Come First Serve (Convoy Effect
Solve: FCFS Arrival Time
Process AT BT CT TAT WT
P1 0 4 4
P2 1 3 7
P3 2 1 8
P4 3 2 10
P5 4 5 15
Turn around time= Completion Time- Arrival Time
Waiting Time= Turn around Time-Burst Time
(2) Shortest Job First
Processes with least execution time are selected first.
CPU is assigned to process with less CPU burst time.
SJF:
Non-Preemption: CPU is always allocated to the process with least
burst time and Process Keeps CPU with it until it is completed.
Pre-Emption: When a new process enters the queue, scheduler
checks its execution time and compare with the already running
process.
If Execution time of running process is more, CPU is taken from it
and given to new process.
Shortest Job First(Preemptive)
Q1. Consider foll. Processes with A.T and B.T
Process A.T B.T
P1 0 9
P2 1 4
P3 2 9
Cal. Completion time, turn around time and avg. waiting time.
SJF(Pre-emptive)-> SRTF
Shortest Job First(Preemptive)
Shortest Job First(Preemptive)
Q1. Consider foll. Processes with A.T and B.T
Process A.T B.T
P1 0 5
P2 1 3
P3 2 3
P4 3 1
Cal. Completion time, turn around time and avg. waiting time.
Shortest Job First (Non Preemption)
P1 burst time: 15
P2 burst time: 8
P3 burst time: 10
P4 burst time: 3
Arrival time of all processes is 0.
30
H.W. Practice: Shortest Job First (Non
Preemption)
Q1. Consider foll. Processes with A.T and B.T
Process A.T B.T
P1 1 7
P2 2 5
P3 3 1
P4 4 2
P5 5 8
Cal. Completion time, turn around time and avg. waiting time.
H.W. Practice: Shortest Job First
(Preemption)
Process Arrival Burst CT Turn Waiting
Time Time around Time
time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
P1 P2 P4 P1 P1 P3
0 1 5 10 17 26
PRE-EMPTIVE SJF IS SHORTEST REMAINING TIME
FIRST
H.W. Practice: Shortest Job First
(Preemption)
Process Arrival Burst CT Turn Waiting
Time Time around Time
time
P1 0 7
P2 2 4
P3 4 1
P4 5 4
Priority Scheduling
Priority is associated with each process.
CPU is allocated to the process with highest
priority.
If 2 processes have same priority FCFS
Disadvantage: Starvation (Low priority Processes
wait for long)
Solution of Starvation: Aging
Aging: Priority of process is increased gradually (e.g
after every 5 min priority is incremented by 1)
Priority Scheduling (Preemptive)
Process Arrival Priority Burst Completion Consider 4 as
Time Time Time
Highest and 7 as
P1 1 5 4
Lowest Priority
P2 2 7 2
P3 3 4 3
Priority Scheduling (Preemptive)
Process Arrival Priority Burst Completion
Time Time Time
P1 0 2 10
P2 2 1 5 Consider 3 as
P3 3 0 2 Lowest and 0
P4 5 3 20 as Highest
Priority
Priority Scheduling (Preemptive)
Process Arrival Priority Burst Completion
Time Time Time
P1 1 4 4
P2 2 5 2 Consider 4 as
P3 2 7 3 Lowest and 8
P4 3 8 5 as Highest
P5 3 5 1 Priority
P6 4 6 2
Priority Scheduling (Preemptive)
Process Arrival Priority Burst Completion
Time Time Time
P1 1 2 4
P2 1 2 2 Consider 2 as
P3 2 10 5 Lowest and 10
P4 3 6 3 as Highest
Priority
Priority Scheduling (Preemptive)
Process Arrival Priority Burst Completion
Time Time Time
P1 0 2 4
P2 1 4 2 Consider 2 as
P3 2 6 3 Lowest and 12
P4 3 10 5 as Highest
P5 4 8 1 Priority
P6 5 12 4
P7 6 9 6
Priority Scheduling (Non-Preemptive)
Process Arrival Priority Burst Completion
Time Time Time
P1 0 4 4
P2 1 5 5 Consider 7 as
P3 2 7 1 Lowest and 1
P4 3 2 2 as Highest
P5 4 1 3 Priority
P6 5 6 6
Round Robin Scheduling
A Time Quantum is associated to all processes
Time Quantum: Maximum amount of time for which
process can run once it is scheduled.
RR scheduling is always Pre-emptive.
Round Robin
Process Arrival Burst Completion
TQ: 2 Time Time Time
P1 0 5
P2 1 7
P3 2 1
Process Arrival Burst Completion
Time Time Time
P1 0 3
P2 3 4
P3 4 6
Round Robin
Process Arrival Burst Completion
TQ: 2 Time Time Time
P1 0 4
P2 1 5
P3 2 2
P4 3 1
P5 4 6
P6 6 3
Round Robin
Process Arrival Burst Completion
TQ: 2 Time Time Time
P1 0 4
P2 1 5
P3 2 2
P4 3 1
P5 4 6
P6 6 3
Multilevel Queue
A multilevel queue scheduling algorithm partitions
the ready queue into several separate queues.
For Example: a multilevel queue scheduling algorithm
with five queues, listed below in order of priority:
1. System processes
2. Interactive processes
3. Interactive editing processes
4. Batch processes
5. Student/ user processes
