Chapter Three

Process Scheduling
After completing this chapter, the students will be able to:
 Understand the basic concept of process
scheduling
 Explain the types of scheduler
 Detail understand on scheduling criteria: CPU

utilization, Throughput, Turnaround Time,

Waiting Time, Response Time
 Differentiate the following scheduling algorithm

such as Pre-emptive and Non pre-emptive,

FCFS, SJF, RR; Multiprocessor scheduling

05/08/2025
 Contents
Process scheduling
CPU scheduling policies
 CPU Scheduling Criteria
Scheduler
Scheduling algorithms

05/08/2025
 Brainstorming
What is process scheduling ?
What is scheduler?
What is dispatcher ?

05/08/2025
 Introduction
 CPU scheduling is the basis of multi programmed operating
systems.
 By switching the CPU among processes, the operating
system can make the computer more productive

 When a computer is multi-programmed, it frequently has

multiple processes computing for the CPU at the same time.
 This situation occurs whenever two or more processes are
simultaneously in the ready state.
 If only one CPU is available, a choice has to be made which
process to run next.
05/08/2025
 Cont..
 In multiprogramming systems, the Operating system
schedules the processes on the CPU to have the maximum
utilization of it and this procedure is called CPU scheduling.
 The Operating System uses various scheduling algorithm to
schedule the processes.
 CPU scheduling focuses on selecting the next process from the
ready queue and allocating the CPU to that process for the
duration of its current CPU burst.

05/08/2025
 Cont..
Every process that requests CPU service
carries out the following sequence of actions:
 Join the ready queue and wait for CPU processing.
 Execute (receive CPU service) for the duration of
the current CPU burst or for the duration of the
time slice (timeout).
 Join the I/O queue to wait for I/O service or return
to the ready queue to wait for more CPU service.
 Terminate and exit if service is completed-e., if
there are no more CPU or I/O bursts. If more
service is required, return to the ready queue to
wait for more CPU service.

05/08/2025
 CPU scheduler
The CPU scheduler is the part of the operating system that

selects the next process to which the CPU will be allocated,

deallocates the CPU from the process currently executing, and
allocates the CPU to the newly selected process.
The part of the operating system that makes the

choice is called the scheduler and the algorithm

it uses is called the scheduling algorithm.

05/08/2025
 Cont..
Selects among processes in memory that are
ready to be executed, and allocates CPU to
one of them.
CPU scheduling decisions may take place
when a process:
1. Switches from running to waiting state.
2. Switches from running to ready state.
3. Switches from waiting to ready.
4. Terminates.
Scheduling under 1 and 4 is non preemptive.
All other scheduling is preemptive.

05/08/2025
 Dispatcher
Dispatcher is a special program which comes into play after the
scheduler.
When the scheduler completes its job of selecting a process, it
is the dispatcher which takes that process to the desired
state/queue.
The dispatcher is the module that gives a process control over
the CPU after it has been selected by the short-term scheduler.
Short-term scheduler selects from among the
processes in ready queue, and allocates the CPU
to one of them
Dispatch latency – time it takes for the
dispatcher to stop one process and start another
running.
05/08/2025
 Cont.….
 Dispatcher different from scheduler by the
following concept
 All the processes are in a ready state with no
schedule.
 At that time the scheduler used some algorithm.
 Scheduling is done for all the processes in the ready
queue.
 After completing scheduling, the dispatcher enters.
 The dispatcher moves the selected process from the
ready queue into the running state.
 The same process continues simultaneously.
 Scheduler scheduling the process, at the same time
dispatcher dispatches selected processes to the
running state.
05/08/2025
 CPU scheduling policies
In non-preemptive scheduling, a process that is executing will
continue until completion of its CPU burst. The process will
then change to its wait state for I/O service, or terminate
(change to the terminate state) and exit the system.
In preemptive scheduling, the process that is executing may be
interrupted before completion of its current CPU burst and
moved back to the ready queue.
A process can be interrupted for one of the
following reasons:
1. The allocated service interval (time slice)
expires.
2. Another process with a higher priority has
arrived into the ready queue.
05/08/2025
 CPU Scheduling Criteria
 CPU utilization: The proportion of time that the
CPU spends executing processes.
 Throughput – # of processes that complete their
execution per unit time •
 Turnaround time(TAT) – total time required to
execute a particular process •
 Waiting time(WT) – amount of time a process
waits in the ready queue •
 Response time(RT) – amount of time it takes
from when a request was submitted until the first
response is produced.
 Ensure fairness for all jobs - give everyone an
equal amount of CPU and I/O time.
05/08/2025
 CPU scheduling criteria cont..
Maximize throughput - run as many jobs as possible in a
given amount of time. – This could be accomplished
easily by running only short jobs or by running jobs
without interruptions.
Minimize response time - quickly turn around interactive
requests. – This could be done by running only interactive
jobs and letting the batch jobs wait until the interactive
load ceases.
Minimize turnaround time - move entire jobs in and out
of the system quickly. – This could be done by running all
batch jobs first (because batch jobs can be grouped to run
more efficiently than interactive jobs).

05/08/2025
 CPU scheduling criteria cont..
Minimize waiting time - move jobs out of the READY
queue as quickly as possible. – This could only be done by
reducing the number of users allowed on the system so the
CPU would be available immediately whenever a job
entered the READY queue.
Maximize CPU efficiency - keep the CPU busy 100
percent of the time. – This could be done by running only
CPU-bound jobs (and not I/O- bound jobs).

05/08/2025
Process Scheduling Algorithms
Part of the operating system that makes scheduling
decision is called scheduler and the algorithm it uses is
called scheduling algorithm.
1. First-come-first-served (FCFS)
2. Shortest job first (SJF)
3. Shortest Remaining Time (SRTF)
4. Priority scheduling(PS)
5. Round robin (RR)

05/08/2025
First-Come, First-Served (FCFS) Scheduling
Is a non preemptive scheduling algorithm
that handles jobs according to their arrival
time:
 The earlier they arrive, the sooner they're
served. •
 It's a very simple algorithm to implement
because it uses a FIFO queue. •
Poor in performance, as average wait time is
high.

05/08/2025
 Example

Process BT WT=TAT-BT TAT=CT- CT RT

AT
p1 24 0 24 24 0
p2 3 24 27 27 24
p3 3 27 30 30 27
P1 P2 P3
0 0 24 27 30

 Waiting time for P1 = 0; P2 = 24; P3 = 27

 Average waiting time: (0 + 24 + 27)/3 = 17
 Turnaround time for P1=24, P2=27, P3=30
 Avg turnaround time: (24+27+30)/3= 27

05/08/2025
 Shortest Job First(STF)
Shortest process next (SPN), also known as shortest job
first (SJF), is a scheduling policy in which the scheduler
selects from the ready queue the process with the shortest
CPU service time interval (burst).

05/08/2025
 Cont..
Since, No Process arrives at time 0 hence;
there will be an empty slot in the Gantt
chart from time 0 to 1 (the time at which the
first process arrives).
According to the algorithm, the OS schedules
the process which is having the lowest burst
time among the available processes in the
ready queue.
Till now, we have only one process in the
ready queue hence the scheduler will
schedule this to the processor no matter what
is its burst time.
05/08/2025
 Example
Process AT BT TAT=CT-AT WT=TAT- CT
BT
P1 0 7 7 0
P2 2 4 10 6
p3 4 1 4 3
p4P1 5 P3 4 11
P2 P4 7
0 7 8 12 16

 Waiting time P1=0-0=0, P2=8-2=6, P3=7-4=3, P4=12-

5=7
 Average waiting time = (0 + 6 + 3 + 7)/4 = 4
 Turnaround time: P1= 7-0=7, P2=12-2=10, P3=8-4=4,
P4=16-5=11
 Avg. turnaround time: (7+10+4+11)/4= 8

05/08/2025
 Round Robing Scheduling
Round robin (RR) scheduling is used in time-
sharing systems. It is the most common of the
preemptive scheduling policies.
Every process is allocated the CPU for a
short-fixed interval called the time quantum,
or time slice.
After this short interval expires, the process
that is executing (receiving CPU service) is
interrupted by the operating system.
The time slice is usually much shorter than
the average CPU burst of the processes.
When the time slice expires, the scheduler
carries out a context switch to the next
process selected from the ready queue.
05/08/2025
 Cont..
Each process gets a small unit of CPU time
(time quantum q), usually 10-100
milliseconds. After this time has elapsed, the
process is preempted and added to the end of
the ready queue.
If there are n processes in the ready queue
and the time quantum is q, then each process
gets 1/n of the CPU time in chunks of at most
q time units at once. No process waits more
than (n-1)q time units.

05/08/2025
 Example
Process BT WT=TAT-BT TAT=CT- CT
AT
p1 24 6 30 30
p2 3 4 7 7
p3 3 7 10 10

Consider the above three Round-robin

scheduling processes. With (T=4).
P1 P2 P3 P1 P1 P1 P1 P1

0 4 7 10 14 18 22 26
30
Average waiting time = [(30-24) +4+7]/3 =
17/3 =5.66
05/08/2025
 Shortest Remaining Time
Two schemes: –
 Nonpreemptive – once CPU given to the process it
cannot be preempted until completes its CPU burst.
 preemptive – if a new process arrives with CPU burst
length less than remaining time of current executing
process, preempt. This scheme is know as the
Shortest-Remaining- Time-First (SRTF).
 With this scheduling policy, a new process that arrives
will cause the scheduler to interrupt the currently
executing process if the CPU service time interval of
the newly arrived process is less than the remaining
service time interval of the process currently
executing (receiving CPU service).
 A context switch occurs and the new process is started
immediately.
05/08/2025
 Example
Proces AT BT TAT=CT- WT=TAT-BT CT RT
s AT
p1 0 7 16 9 16 0
p2 2 4 5 1 7 2
p3 4 1 1 0 5 4
p4 5 4 6 2 11 7
P1 P2 P3 P2 P4 P1
0 2 4 5 7 11 16

Average waiting time = (9 + 1 + 0 +2)/4 = 3

Turnaround time:P1=16-0=16, P2=7-2=5,
P3=5-4=1, P4=11-5=6
Avg. turnaround time= (16+5+1+6)/4=7

05/08/2025
 Priority Scheduling
 A priority number (integer) is associated with each
process .
 The CPU is allocated to the process with the highest
priority (smallest integer =highest priority).
1. Allocate the CPU to the highest priority process.
2. When a process is selected for execution, assign it a time slice.
3. If the process requests an I/ 0 operation before the time slice expires, raise its\
priority (i.e., assume it will carry out another I/O request soon).
4. If the time slice expires, lower its priority (i.e., assume it is now in a CPU
burst) and allocate the CPU to the highest priority ready process.
 Problem  Starvation – low priority processes may never execute

 Solution  Aging – as time progresses increase the priority of the

process

05/08/2025
 Example
Proces BT Priorit TAT=CT- WT=TAT-BT CT RT
s y AT
P1 10 3 16 6 16 6
P2 1 1 1 0 1 0
P3 2 4 18 16 18 16
P4 1 5 19 18 19 18
p5 5 2 6 1 6 1

P2 P5 P1 P3 P4

0 1 6 16 18 19

Average waiting time = 8.2 msec

05/08/2025
 Summary
 FCFS simple but causes short jobs to wait for long
jobs.

 SJF is optimal giving shortest waiting time but need

to know length of next burst.

 SJF is a type of priority scheduling - may suffer

from starvation - prevent using aging

 RR is gives good response time, it is preemptive.
 Problem selecting the quantum.
05/08/2025
 Project
 Program and simulate scheduling algorithms
discussed before:
1. FCFS •
2. Shortest-Job-First (SJR) Scheduling •
3. Preemptive SJF •
4. Priority Scheduling •
5. Round Robin (RR)
 All scheduling algorithm shall be programmed in one
file (all in one) so that once you submit no. of process,
process's name , Arrival time and burst time, it should
display options to the user to choose from the menu,
then calculate waiting time, turnaround time, avg.
waiting and avg. turnaround time, Completion time,
for scheduling alg. Presented above.

05/08/2025
 End of Chapter Three!

Query?

05/08/2025