Short Notes: T6-Process Management - CPU Scheduling | Short Notes for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

 Page 1


All of the processes which are ready to execute and are placed in main memory 
then selection of one of those processes is known as scheduling, and after 
selection that process gets the control of CPU.
Scheduling Criteria: The criteria for comparing CPU scheduling algorithms include 
the following •
• CPU Utilization: Means keeping the CPU as busy as possible.
• Throughput: It is nothing but the measure of work i.e., the number of 
processes that are completed per time unit.
• Turnaround Time: The interval from the time of submission of a process to 
the time of completion. It is the sum of the periods spent waiting to get into 
memory, waiting in the ready queue, executing on the CPU and doing I/O.
• Waiting Time: The sum of the periods spent waiting in the ready queue.
• Response Time: The time from the submission of a request until the first 
response is produced.
First Come First Served (FCFS) Scheduling:
• With this scheme, the process that requests the CPU first is allocated the CPU 
first.
• The implementation of the FCFS policy is easily managed with FIFO queue.
• When a process enters the ready queue, its PCB (Process Control Block) is 
linked onto the tail of the queue.
• When the CPU is free, it is allocated to the process at the head of the queue. 
The running process is then removed from the queue.
Page 2


All of the processes which are ready to execute and are placed in main memory 
then selection of one of those processes is known as scheduling, and after 
selection that process gets the control of CPU.
Scheduling Criteria: The criteria for comparing CPU scheduling algorithms include 
the following •
• CPU Utilization: Means keeping the CPU as busy as possible.
• Throughput: It is nothing but the measure of work i.e., the number of 
processes that are completed per time unit.
• Turnaround Time: The interval from the time of submission of a process to 
the time of completion. It is the sum of the periods spent waiting to get into 
memory, waiting in the ready queue, executing on the CPU and doing I/O.
• Waiting Time: The sum of the periods spent waiting in the ready queue.
• Response Time: The time from the submission of a request until the first 
response is produced.
First Come First Served (FCFS) Scheduling:
• With this scheme, the process that requests the CPU first is allocated the CPU 
first.
• The implementation of the FCFS policy is easily managed with FIFO queue.
• When a process enters the ready queue, its PCB (Process Control Block) is 
linked onto the tail of the queue.
• When the CPU is free, it is allocated to the process at the head of the queue. 
The running process is then removed from the queue.
Gantt chart
~ f z Tp7 Pi
0 24 27 30
Waiting time for Pi = 0 ms 
Waiting time for Pz = 24 ms
Waiting time for Pa = 27 ms
Process Table
Process Burst Time
(in m illiseconds)
Pi 24
Pz 3
Pa 3
Turn around time for Pi = 24 - 0 = 24 ms 
Turn around time for Pa = 27 - 24 = 3 ms
• FCFS scheduling is non-preemptive, very simple, can be implemented with a 
FIFO queue, Not a good choice when there are variable burst times (CPU 
bound and I/O bound), drawback: causes short processes to wait for longer 
ones.
Shortest Job First (SJF) Scheduling
• When the CPU is available, it is assigned to the process that has the smallest 
next CPU burst.
• If the two processes have the same length or amount of next CPU burst, FCFS 
scheduling is used to break the tie.
Process Table
Process
Burst Time
(in milliseconds)
Pi 6
P2 8
P s 7
P 4 3
Waiting time for Pi = 3 
Waiting time for P2 = 16 
Waiting time for P3 = 9 
Waiting time for Pi = 0
Gantt chart
P 4 Pi P3 P2
0 3 9 16 24
Average waiting time
3+16+9+0
= -------------- = 7 ms
4
• A more appropriate term for this scheduling method would be the shortest 
next CPU burst algorithm because scheduling depends on the length of the 
next CPU burst of a process rather than its total length.
• SJF works based on burst times (not total job time), difficult to get this 
information, must approximate it for short term scheduling, used frequently 
for long term scheduling, preemptive (SJF) or non-preemptive (SRTF), Special 
case of priority scheduling.
Page 3


All of the processes which are ready to execute and are placed in main memory 
then selection of one of those processes is known as scheduling, and after 
selection that process gets the control of CPU.
Scheduling Criteria: The criteria for comparing CPU scheduling algorithms include 
the following •
• CPU Utilization: Means keeping the CPU as busy as possible.
• Throughput: It is nothing but the measure of work i.e., the number of 
processes that are completed per time unit.
• Turnaround Time: The interval from the time of submission of a process to 
the time of completion. It is the sum of the periods spent waiting to get into 
memory, waiting in the ready queue, executing on the CPU and doing I/O.
• Waiting Time: The sum of the periods spent waiting in the ready queue.
• Response Time: The time from the submission of a request until the first 
response is produced.
First Come First Served (FCFS) Scheduling:
• With this scheme, the process that requests the CPU first is allocated the CPU 
first.
• The implementation of the FCFS policy is easily managed with FIFO queue.
• When a process enters the ready queue, its PCB (Process Control Block) is 
linked onto the tail of the queue.
• When the CPU is free, it is allocated to the process at the head of the queue. 
The running process is then removed from the queue.
Gantt chart
~ f z Tp7 Pi
0 24 27 30
Waiting time for Pi = 0 ms 
Waiting time for Pz = 24 ms
Waiting time for Pa = 27 ms
Process Table
Process Burst Time
(in m illiseconds)
Pi 24
Pz 3
Pa 3
Turn around time for Pi = 24 - 0 = 24 ms 
Turn around time for Pa = 27 - 24 = 3 ms
• FCFS scheduling is non-preemptive, very simple, can be implemented with a 
FIFO queue, Not a good choice when there are variable burst times (CPU 
bound and I/O bound), drawback: causes short processes to wait for longer 
ones.
Shortest Job First (SJF) Scheduling
• When the CPU is available, it is assigned to the process that has the smallest 
next CPU burst.
• If the two processes have the same length or amount of next CPU burst, FCFS 
scheduling is used to break the tie.
Process Table
Process
Burst Time
(in milliseconds)
Pi 6
P2 8
P s 7
P 4 3
Waiting time for Pi = 3 
Waiting time for P2 = 16 
Waiting time for P3 = 9 
Waiting time for Pi = 0
Gantt chart
P 4 Pi P3 P2
0 3 9 16 24
Average waiting time
3+16+9+0
= -------------- = 7 ms
4
• A more appropriate term for this scheduling method would be the shortest 
next CPU burst algorithm because scheduling depends on the length of the 
next CPU burst of a process rather than its total length.
• SJF works based on burst times (not total job time), difficult to get this 
information, must approximate it for short term scheduling, used frequently 
for long term scheduling, preemptive (SJF) or non-preemptive (SRTF), Special 
case of priority scheduling.
Preemptive and Non-preemptive Algorithm
• The SJF algorithm can either be preemptive or non-preemptive.
• The choice arises when a new process arrives at the ready queue while a 
previous process is still executing.
• The next CPU burst of the newly arrived process may be shorter than what is 
left of the currently executing process.
• A preemptive SJF algorithm will preempt the currently executing process, 
whereas a, non-preemptive algorithm will allow the currently running process 
to finish its CPU burst.
• Preemptive SJF scheduling, is sometimes called shortest-remaining-time-first- 
scheduling,
Process Table
Process Arrival Time Burst Time
Pi 0 8
P 2 1 4
Ps 2 9
P 4 3 5
Waiting time for Pi = 10 - 1 = 9 
Waiting time for P2 = 1 - 1 = 0 
Waiting time for P3 = 17 - 2 = 15 
Waiting time for P4 = 5 - 3
Gantt chart
P, P- P,
10
17
26
Average waiting time
9 + 0 + 15 + 2 * •
4
= 6.5 ms
Priority Scheduling
• A priority is associated with each process and the CPU is allocated to the 
process with the highest priority, Equal priority processes are scheduled in 
FCFS order.
• We can be provided that low numbers represent high priority or low numbers 
represent low priority, According to the question, we need to assume anyone 
of the above.
• Priority scheduling can be either preemptive or non-preemptive.
• A preemptive priority scheduling algorithm will preempt the CPU, if the priority 
of the newly arrived process is higher than the priority of the currently running 
process.
• A non-preemptive priority scheduling algorithm will simply put the new 
process at the head of the ready queue.
A major problem with priority scheduling algorithm is indefinite blocking or 
starvation.
Process Table
Page 4


All of the processes which are ready to execute and are placed in main memory 
then selection of one of those processes is known as scheduling, and after 
selection that process gets the control of CPU.
Scheduling Criteria: The criteria for comparing CPU scheduling algorithms include 
the following •
• CPU Utilization: Means keeping the CPU as busy as possible.
• Throughput: It is nothing but the measure of work i.e., the number of 
processes that are completed per time unit.
• Turnaround Time: The interval from the time of submission of a process to 
the time of completion. It is the sum of the periods spent waiting to get into 
memory, waiting in the ready queue, executing on the CPU and doing I/O.
• Waiting Time: The sum of the periods spent waiting in the ready queue.
• Response Time: The time from the submission of a request until the first 
response is produced.
First Come First Served (FCFS) Scheduling:
• With this scheme, the process that requests the CPU first is allocated the CPU 
first.
• The implementation of the FCFS policy is easily managed with FIFO queue.
• When a process enters the ready queue, its PCB (Process Control Block) is 
linked onto the tail of the queue.
• When the CPU is free, it is allocated to the process at the head of the queue. 
The running process is then removed from the queue.
Gantt chart
~ f z Tp7 Pi
0 24 27 30
Waiting time for Pi = 0 ms 
Waiting time for Pz = 24 ms
Waiting time for Pa = 27 ms
Process Table
Process Burst Time
(in m illiseconds)
Pi 24
Pz 3
Pa 3
Turn around time for Pi = 24 - 0 = 24 ms 
Turn around time for Pa = 27 - 24 = 3 ms
• FCFS scheduling is non-preemptive, very simple, can be implemented with a 
FIFO queue, Not a good choice when there are variable burst times (CPU 
bound and I/O bound), drawback: causes short processes to wait for longer 
ones.
Shortest Job First (SJF) Scheduling
• When the CPU is available, it is assigned to the process that has the smallest 
next CPU burst.
• If the two processes have the same length or amount of next CPU burst, FCFS 
scheduling is used to break the tie.
Process Table
Process
Burst Time
(in milliseconds)
Pi 6
P2 8
P s 7
P 4 3
Waiting time for Pi = 3 
Waiting time for P2 = 16 
Waiting time for P3 = 9 
Waiting time for Pi = 0
Gantt chart
P 4 Pi P3 P2
0 3 9 16 24
Average waiting time
3+16+9+0
= -------------- = 7 ms
4
• A more appropriate term for this scheduling method would be the shortest 
next CPU burst algorithm because scheduling depends on the length of the 
next CPU burst of a process rather than its total length.
• SJF works based on burst times (not total job time), difficult to get this 
information, must approximate it for short term scheduling, used frequently 
for long term scheduling, preemptive (SJF) or non-preemptive (SRTF), Special 
case of priority scheduling.
Preemptive and Non-preemptive Algorithm
• The SJF algorithm can either be preemptive or non-preemptive.
• The choice arises when a new process arrives at the ready queue while a 
previous process is still executing.
• The next CPU burst of the newly arrived process may be shorter than what is 
left of the currently executing process.
• A preemptive SJF algorithm will preempt the currently executing process, 
whereas a, non-preemptive algorithm will allow the currently running process 
to finish its CPU burst.
• Preemptive SJF scheduling, is sometimes called shortest-remaining-time-first- 
scheduling,
Process Table
Process Arrival Time Burst Time
Pi 0 8
P 2 1 4
Ps 2 9
P 4 3 5
Waiting time for Pi = 10 - 1 = 9 
Waiting time for P2 = 1 - 1 = 0 
Waiting time for P3 = 17 - 2 = 15 
Waiting time for P4 = 5 - 3
Gantt chart
P, P- P,
10
17
26
Average waiting time
9 + 0 + 15 + 2 * •
4
= 6.5 ms
Priority Scheduling
• A priority is associated with each process and the CPU is allocated to the 
process with the highest priority, Equal priority processes are scheduled in 
FCFS order.
• We can be provided that low numbers represent high priority or low numbers 
represent low priority, According to the question, we need to assume anyone 
of the above.
• Priority scheduling can be either preemptive or non-preemptive.
• A preemptive priority scheduling algorithm will preempt the CPU, if the priority 
of the newly arrived process is higher than the priority of the currently running 
process.
• A non-preemptive priority scheduling algorithm will simply put the new 
process at the head of the ready queue.
A major problem with priority scheduling algorithm is indefinite blocking or 
starvation.
Process Table
Process Burst Time Priority
Pi 10 3
P2 1 1
Ps 2 4
P4 1 5
Ps 5 2
Waiting time for Pi = 6 
Waiting time for P2 = 0 
Waiting time for P3 = 16 
Waiting time for P4 = 18 
Waiting time for P5 = 1 
Average waiting time
Round Robin (RR) Scheduling
• The R R scheduling algorithm is designed especially for time-sharing systems.
• It is similar to FCFS scheduling but preemption is added to switch between 
processes.
• A small unit of time called a time quantum or time slice is defined.
• If time quantum is too large, this just becomes FCFS, Since context-switching 
costs time, the rule of thumb is 80% of CPU bursts should be shorter than the 
time quantum.
Process Table
Process
Burst Time
(in milliseconds]
Pi
24
P2
3
P3
3
Let's take time quantum = 4 ms. Then the resulting R R schedule is as Follows
Pi P i2
P3
Pi Pi
P3
Pi Pi
4 7
10
14
18 22 26
3 0
Pi waits for the 6 ms (10 - 4), P2 waits for 4 ms and P3 waits for 7 ms. 
Thus,
Average waiting time 
6 + 4+ 7
= ---------------= 5.66 ms
Multilevel Queue Scheduling:
Page 5


All of the processes which are ready to execute and are placed in main memory 
then selection of one of those processes is known as scheduling, and after 
selection that process gets the control of CPU.
Scheduling Criteria: The criteria for comparing CPU scheduling algorithms include 
the following •
• CPU Utilization: Means keeping the CPU as busy as possible.
• Throughput: It is nothing but the measure of work i.e., the number of 
processes that are completed per time unit.
• Turnaround Time: The interval from the time of submission of a process to 
the time of completion. It is the sum of the periods spent waiting to get into 
memory, waiting in the ready queue, executing on the CPU and doing I/O.
• Waiting Time: The sum of the periods spent waiting in the ready queue.
• Response Time: The time from the submission of a request until the first 
response is produced.
First Come First Served (FCFS) Scheduling:
• With this scheme, the process that requests the CPU first is allocated the CPU 
first.
• The implementation of the FCFS policy is easily managed with FIFO queue.
• When a process enters the ready queue, its PCB (Process Control Block) is 
linked onto the tail of the queue.
• When the CPU is free, it is allocated to the process at the head of the queue. 
The running process is then removed from the queue.
Gantt chart
~ f z Tp7 Pi
0 24 27 30
Waiting time for Pi = 0 ms 
Waiting time for Pz = 24 ms
Waiting time for Pa = 27 ms
Process Table
Process Burst Time
(in m illiseconds)
Pi 24
Pz 3
Pa 3
Turn around time for Pi = 24 - 0 = 24 ms 
Turn around time for Pa = 27 - 24 = 3 ms
• FCFS scheduling is non-preemptive, very simple, can be implemented with a 
FIFO queue, Not a good choice when there are variable burst times (CPU 
bound and I/O bound), drawback: causes short processes to wait for longer 
ones.
Shortest Job First (SJF) Scheduling
• When the CPU is available, it is assigned to the process that has the smallest 
next CPU burst.
• If the two processes have the same length or amount of next CPU burst, FCFS 
scheduling is used to break the tie.
Process Table
Process
Burst Time
(in milliseconds)
Pi 6
P2 8
P s 7
P 4 3
Waiting time for Pi = 3 
Waiting time for P2 = 16 
Waiting time for P3 = 9 
Waiting time for Pi = 0
Gantt chart
P 4 Pi P3 P2
0 3 9 16 24
Average waiting time
3+16+9+0
= -------------- = 7 ms
4
• A more appropriate term for this scheduling method would be the shortest 
next CPU burst algorithm because scheduling depends on the length of the 
next CPU burst of a process rather than its total length.
• SJF works based on burst times (not total job time), difficult to get this 
information, must approximate it for short term scheduling, used frequently 
for long term scheduling, preemptive (SJF) or non-preemptive (SRTF), Special 
case of priority scheduling.
Preemptive and Non-preemptive Algorithm
• The SJF algorithm can either be preemptive or non-preemptive.
• The choice arises when a new process arrives at the ready queue while a 
previous process is still executing.
• The next CPU burst of the newly arrived process may be shorter than what is 
left of the currently executing process.
• A preemptive SJF algorithm will preempt the currently executing process, 
whereas a, non-preemptive algorithm will allow the currently running process 
to finish its CPU burst.
• Preemptive SJF scheduling, is sometimes called shortest-remaining-time-first- 
scheduling,
Process Table
Process Arrival Time Burst Time
Pi 0 8
P 2 1 4
Ps 2 9
P 4 3 5
Waiting time for Pi = 10 - 1 = 9 
Waiting time for P2 = 1 - 1 = 0 
Waiting time for P3 = 17 - 2 = 15 
Waiting time for P4 = 5 - 3
Gantt chart
P, P- P,
10
17
26
Average waiting time
9 + 0 + 15 + 2 * •
4
= 6.5 ms
Priority Scheduling
• A priority is associated with each process and the CPU is allocated to the 
process with the highest priority, Equal priority processes are scheduled in 
FCFS order.
• We can be provided that low numbers represent high priority or low numbers 
represent low priority, According to the question, we need to assume anyone 
of the above.
• Priority scheduling can be either preemptive or non-preemptive.
• A preemptive priority scheduling algorithm will preempt the CPU, if the priority 
of the newly arrived process is higher than the priority of the currently running 
process.
• A non-preemptive priority scheduling algorithm will simply put the new 
process at the head of the ready queue.
A major problem with priority scheduling algorithm is indefinite blocking or 
starvation.
Process Table
Process Burst Time Priority
Pi 10 3
P2 1 1
Ps 2 4
P4 1 5
Ps 5 2
Waiting time for Pi = 6 
Waiting time for P2 = 0 
Waiting time for P3 = 16 
Waiting time for P4 = 18 
Waiting time for P5 = 1 
Average waiting time
Round Robin (RR) Scheduling
• The R R scheduling algorithm is designed especially for time-sharing systems.
• It is similar to FCFS scheduling but preemption is added to switch between 
processes.
• A small unit of time called a time quantum or time slice is defined.
• If time quantum is too large, this just becomes FCFS, Since context-switching 
costs time, the rule of thumb is 80% of CPU bursts should be shorter than the 
time quantum.
Process Table
Process
Burst Time
(in milliseconds]
Pi
24
P2
3
P3
3
Let's take time quantum = 4 ms. Then the resulting R R schedule is as Follows
Pi P i2
P3
Pi Pi
P3
Pi Pi
4 7
10
14
18 22 26
3 0
Pi waits for the 6 ms (10 - 4), P2 waits for 4 ms and P3 waits for 7 ms. 
Thus,
Average waiting time 
6 + 4+ 7
= ---------------= 5.66 ms
Multilevel Queue Scheduling:
Highest
p ro n ty_____________
« ;>] System processes
i = q |~ Interactive processes
Interactive editing processes j= Q >
Batcfi processes
= ^ _
Student processes
Lower
priority
J = >
Multilevel queue
• This scheduling algorithm has been created for saturation in which processes 
are easily classified into different groups
• A multilevel queue scheduling algorithm partitions the ready queue into 
several separate queues.
• The processes are permanently assigned to one queue, generally based on 
some property of the process, such as memory size, process priority or 
process type.
Multilevel Feedback Queue Scheduling
• This scheduling algorithm allows a process to move between queues.
• The idea is to separate processes according to the characteristics of their 
CPU bursts.
• If a process uses too much CPU time, it will be moved to a lower priority 
queue.
• Similarly, a process that waits too long in a lower priority queue may be 
moved to a higher priority queue. This form of aging prevents starvation.
CPU Overhead:
• First In First Out: Low
• Shortest job first: Medium
• Priority based Scheduling: Medium
• Multilevel Queue Scheduling: High
Throughput:
• First In First Out: Low
• Shortest job first: High
• Priority based Scheduling: Low
• Multilevel Queue Scheduling: Medium
Turn Around Time:
• First In First Out: High
• Shortest job first: Medium
• Priority based Scheduling: Medium
• Multilevel Queue Scheduling: Medium
Response Time:
• First In First Out: Low
• Shortest job first: Medium
• Priority based Scheduling: High