3

Process
Scheduling

Dr. Reshma Kadam

PhD, CISA (Pass), MCA, BCA
Assistant Professor
AKI‟s Poona College of Arts, Commerce and Science,
Camp, Pune
 Chapter 3
3 Process Scheduling

Basic Concept –
CPU-I/O burst cycle,
Scheduling Criteria ,
CPU scheduler,
Preemptive scheduling,
Dispatcher
Scheduling Algorithms –
FCFS,
SJF,
Priority scheduling,
Round-robin scheduling,
Multiple queue scheduling,
Multilevel feedback queue scheduling
 Process Scheduling

• Basic Concept
• Process scheduling is a crucial component of
operating systems that manages the execution
of processes.

• It determines which process runs at any given

time and how system resources are allocated
among processes.

Dr. Reshma Kadam

 Process Scheduling
• Basic Concept
• Process: A program in execution, including its
code, data, and state.

• Scheduler: The part of the operating system that

decides which process runs at a given time.

• CPU Scheduling: Allocates CPU time to various

processes.

Dr. Reshma Kadam

 Process Scheduling

• Basic Concept
• Scheduling is the fundamental function of
O.S., almost all the computer resources are
scheduled before use.

• The CPU is also one of the primary resource.

So CPU is also scheduled before use.

Dr. Reshma Kadam

 Process Scheduling
• Basic Concept
Three Types of Scheduling
• Short Term Scheduling
– It is the actual decision of which ready process to
execute next.
• Medium Term Scheduling
– It is a part of the swapping function
• Long Term Scheduling
– It performs when a new process is created

Dr. Reshma Kadam

 Process Scheduling
• CPU-I/O burst cycle
• Cycle contains
– CPU Burst
• A period of uninterrupted
CPU activity.

– I/O Burst
• A period of uninterrupted
I/O activity.

Dr. Reshma Kadam

 Process Scheduling
• CPU-I/O burst cycle
• Process execution consists of a cycle of CPU
execution and I/O wait.

• Processes alternate back and forth between

these two states.

• Process starts with CPU burst followed by I/O

burst and so on.

Dr. Reshma Kadam

 Process Scheduling

• Scheduling Criteria
• CPU utilization
– Keep the CPU as busy as possible

• Throughput
– No. of processes completed per time unit

• Turnaround time
– How long it takes to complete a process.

Dr. Reshma Kadam

 Process Scheduling

• Scheduling Criteria
• Waiting time
– The total time a process is in the ready queue

• Response time
– Time a process takes to start responding.

Dr. Reshma Kadam

 Process Scheduling

• CPU Scheduler
• O.S. must select one of the processes in the
ready queue to be executed. This is carried out
by Short Term Scheduler.

• A ready queue may be FIFO, priority queue,

tree, linked list.

Dr. Reshma Kadam

 Process Scheduling

• CPU Scheduling

• Preemptive & Non-Preemptive Scheduling

Dr. Reshma Kadam

 Process Scheduling

• Preemptive scheduling
• The operating system can interrupt and
suspend a currently running process to switch
to another process.

• Example algorithms: Round Robin, Shortest

Time First (SJF), Priority Scheduling
(preemptive).

Dr. Reshma Kadam

 Process Scheduling

• Preemptive scheduling
• Once a process starts execution, it runs to
completion or until it voluntarily releases the
CPU.

• Example algorithms: First-Come, First-Served

(FCFS), Priority Scheduling (non-preemptive).

Dr. Reshma Kadam

 Process Scheduling
• Dispatcher
• It is a module, it connects the CPU to the process selected
by the short-term scheduler.

• Main function is Switching, means switching CPU from one

process to another.

• Other function – jumping to the proper location in the user

program and ready to start execution.

• It should be fast, because it invokes during each and every

switch.

• Time to stop one process and start another process is called

as „dispatch latency‟
Dr. Reshma Kadam
 Process Scheduling
• Scheduling Algorithms
1. First-Come, First-Served (FCFS)

2. Shortest Job First (SJF)

3. Priority Scheduling

4. Round Robin (RR)

5. Multilevel Queue Scheduling

6. Multilevel Feedback Queue Scheduling

Dr. Reshma Kadam
 Process Scheduling
• Scheduling Algorithms
1. First-Come, First-Served (FCFS)
• Processes are scheduled in the order they arrive in
the ready queue.

• When the CPU is available, assign it to the

process at the start of the ready queue.

• Simple to implement
• use a FIFO queue

• Non-preemptive Dr. Reshma Kadam

 Process Scheduling
• Scheduling Algorithms
1. First-Come, First-Served (FCFS)
• Processes are scheduled in the order they arrive in
the ready queue.

• When the CPU is available, assign it to the

process at the start of the ready queue.

• Simple to implement
• use a FIFO queue

• Non-preemptive Dr. Reshma Kadam

 Process Scheduling

1. First-Come, First-Served (FCFS)

• All processes arrive at time 0.

• Process Burst Time
P1 24
P2 3
P3 3
P1 P2 P3
• Gantt Chart:
0 24 27 30

• Average waiting time:

(0 + 24 + 27)/3 = 17 ms
 Process Scheduling
1. First-Come, First-Served (FCFS)

• Process Burst Time

P2 3
P3 3
P1 24

• Gantt Chart: P2 P3 P1

0 3 6 30

• Average waiting time:

(6 + 0 + 3)/3 = 3 ms
 Process Scheduling
• Scheduling Algorithms
1. First-Come, First-Served (FCFS)
• May not give the best average waiting time.

• Average times can vary a lot depending on the

order of the processes.

• Convoy effect
• Small processes can get stuck behind a big
process
Dr. Reshma Kadam
 Process Scheduling
• Scheduling Algorithms
2.2. Shortest Job First Scheduling
• When the CPU is available, assign it to the
process with the smallest next CPU burst
duration better name is “shortest next CPU
burst”

• Can be preemptive or non-preemptive

Dr. Reshma Kadam

 Process Scheduling
Non-preemptive Example
2.2. Shortest Job First Scheduling
• Process Burst Time
P1 6
P2 8
P3 7
P4 3
• Gantt Chart:?
• Average waiting time:?
• Average Turn Around Time:?
 Process Scheduling
Non-preemptive Example
2.2. Shortest Job First Scheduling
• Process Burst Time
P1 6
P2 8
P3 7
P4 3
• Gantt Chart: P4 P1 P3 P2

0 3 9 16 24

• Average waiting time:

(3 + 16 + 9 + 0)/4 = 7 ms
– FCFS gives 10.25 ms
 Process Scheduling
• Scheduling Algorithms
2.2. Shortest Job First Scheduling
• Provably optimal
– Gives the minimum average waiting time

• Problem: it is usually impossible to know the

next CPU burst duration for a process
• Solution: guess (predict)

Dr. Reshma Kadam

 Process Scheduling

Preemptive SJF
• When a new process arrives, if it has a
shorter next CPU burst duration than what
is left of the currently executing process
then preempt the current process.
 Process Scheduling
Preemptive SJF Example
• Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5

• Gantt Chart: ?

continued
 Process Scheduling
Preemptive SJF Example
• Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5

• Gantt Chart:

P1 P2 P4 P1 P3

0 1 5 10 17 26

continued
 Process Scheduling
Preemptive SJF Example
• Average waiting time:
( (10-1) + (1-1) + (17-2) + (5-3) )/4
= 6.5 ms

start time arrival time

• Non-preemptive SJF gives 7.75 ms

 Process Scheduling

Priority Scheduling
• Associate a priority with each process and the CPU
is allocated to the process with the highest priority.

• FCFS, SJF are special cases.

• Low numbers = high priority.

 Example p.134

• Process Burst Time Priority

P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2
• Gantt Chart:

• Average waiting time:

 Example
• Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2
• Gantt Chart:

P2 P5 P1 P3 P4

0 1 6 16 18 19
• Average waiting time: 8.2 ms
 Process Scheduling

Priority Scheduling
• Preemptive or non-preemptive.

• How to avoid starvation?

– aging
 Process Scheduling

Round Robin Scheduling (RR)

• A small unit of time (a time quantum, a time
slice) is defined
• typically 10 - 100 ms

• The ready queue is treated as a circular queue.

• The CPU scheduler goes around the queue

giving each process one time quantum
• preemptive
 Process Scheduling

Round Robin Scheduling (RR)

• A small unit of time (a time quantum, a time slice) is
defined
• typically 10 - 100 ms

• The ready queue is treated as a circular queue.

• The CPU scheduler goes around the queue giving

each process one time quantum

• Preemptive

• Average waiting time can be quite long.

Example
• Time quantum = 4 ms. At time 0.
• Process Burst Time
P1 24
P2 3
P3 3
• Gantt Chart:

• Average waiting time:

Example
• Time quantum = 4 ms. At time 0.
• Process Burst Time
P1 24
P2 3
P3 3
• Gantt Chart:
P1 P2 P3 P1 P1 P1 P1 P1

0 4 7 10 14 18 22 26 30

• Average waiting time: 17/3 = 5.67 ms

 Multilevel Queue Scheduling
• This scheduling algorithm is created for areas in
which we classify process into different groups
such as foreground processes and background
processes.

• Priority of foreground processes are higher than

background processes.

• The multilevel queue- scheduling algorithm

partitions the ready queue into several separate
queues, each with its own scheduling algorithm.
 Multilevel Queue Scheduling
• This method is used when processes can be
easily classified into different groups based on
their characteristics.
highest priority

system processes

interactive processes

interactive editing processes

batch processes

student processes
lowest priority
continued
• Processes is assigned to the queue depending on
some properties of the process.

• Property may be memory size, process priority or

process type.

• Each queue is associated with its own scheduling

algorithm.

• E.g. foreground processes might be scheduled by

RR algorithm and the background queue is
scheduled by FCFS algorithm.
 Multilevel Feedback Queue
Scheduling
• It is an advanced CPU scheduling algorithm. It allows
processes to move between different queues.

• Separate processes with different CPU-Burst

characteristics.

• If process uses too much CPU time, it will be moved to

a lower priority queue.

• If a process waits for long time in a lower priority

queue, then it is moved to a higher priority queue.

• This form of aging prevents starvation.

 Multilevel Feedback Queue
Scheduling
• The CPU scheduler selects processes from the
highest-priority queue first. If that queue is
empty, it moves to the next-priority queue, and
so on.
 Multilevel Feedback Queue
Scheduling

• Allow a process to
move between queues
Q=8
– priority sinks when
quantum exceeded Q=16
– greater discrimination
against longer jobs FCFS

– better response for

shorter jobs
 Multilevel Feedback Queue
Scheduling
• A process entering the ready queue is put in queue 0.

• Process in queue 0 has given time quantum 8 ms.

• If it does not finish within this time, it is moved to the tail of

queue 1.

• If queue 0 is empty, the process at the head of the queue 1 is

given a quantum of 16ms.

• If it does not complete, it is preempted and is put into queue

2.
 Multilevel Feedback Queue
Scheduling
• Process in queue 2 are run on an FCFS basis
only when queue 0 and 1 are empty.
THANK YOU