Chapter 3

Process Scheduling

1
 Objectives
• To introduce CPU scheduling
• To describe various scheduling algorithms

2
 Introduction
• Scheduling refers to a set of policies and mechanisms to
control the order of work to be performed by a computer
system.
• Of all the resources of a computer system that are
scheduled before use, the CPU/processor is the far most
important.
• Process / Processor scheduling is the means by which
operating systems allocate processor time for processes.
• It can be implemented on uniprocessor systems
(uniprocessor Scheduling) or multiprocessor
systems (multiprocessor scheduling)
• The part of the operating system module that performs the
various process scheduling tasks is called a scheduler.

3
 Process Scheduling
• Maximize CPU use, quickly switch processes onto
CPU for time sharing.
• Process scheduler selects among available
processes for next execution on CPU.
• Maintains scheduling queues of processes
– Job queue – set of all processes in the system
– Ready queue – set of all processes residing in main
memory, ready and waiting to execute
– Device queues – set of processes waiting for an I/O
device
– Processes migrate among the various queues

4
 Types of Schedulers
• Short-term scheduler (or CPU scheduler) – selects which process
should be executed next and allocates CPU
– Sometimes the only scheduler in a system
– Short-term scheduler is invoked frequently (milliseconds)  (must
be fast)
• Long-term scheduler (or job scheduler) – selects which processes
should be brought into the ready queue
– Long-term scheduler is invoked infrequently (seconds, minutes) 
(may be slow)
– The long-term scheduler controls the degree of multiprogramming
• Processes can be described as either:
– I/O-bound process – spends more time doing I/O than
computations, many short CPU bursts
– CPU-bound process – spends more time doing computations; few
very long CPU bursts

5
 Types of Schedulers
 Medium-term scheduler can be added if degree of multiple
programming needs to decrease
 Remove process from memory, store on disk, bring back in
from disk to continue execution: swapping

6
• Two schemes of CPU scheduling:
– Non-preemptive – once CPU is given to a process it cannot be
preempted until completes its execution, CPU burst time or
request I/O.
– Non-preemptive algorithms are designed so that once a process
enters the running state, it cannot be preempted until it
completes its allotted time.
– allows a process finishes with its current CPU burst
– Preemptive –Preemptive allows a process to be interrupted in
the middle of its CPU execution, taking the CPU away to
another process.
– allows a process to be interrupted
– 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).
– the preemptive scheduling is based on priority where a
scheduler may preempt a low priority running process anytime
when a high priority process enters into a ready state. 7
 Process Scheduling Algorithms
CPU uses some kind of process scheduling algorithms
to select one process for its execution among so many
processes in ready queue.
 The process scheduling algorithms are used to
maximize CPU utilization by increasing throughput.
CPU scheduling algorithms:
Firs come First Serve(FCFS) scheduling
Shortest Job First (SJF) scheduling
Priority scheduling
Round Robin scheduling
The objective of scheduling is to maximize CPU
utilization and fair allocation of CPU.
8
 Scheduling terminology
• Arrival Time: Time at which the process arrives in the ready
queue.
• Completion Time: Time at which process completes its
execution.
• Burst Time: Time required by a process for CPU execution. It is
the amount of time to execute a particular process.
• Turn Around Time: total time (burst and waiting time).Time
difference between completion time and arrival time.
• Turn Around Time = Completion Time – Arrival Time
• Waiting Time: amount of time a process has been waiting in the
ready queue after arrival . Time difference between turn around
time and burst time.
– Waiting Time = Turn Around Time – Burst Time
• Response time – amount of time it takes from when a request
was submitted until the first response is produced. 9
 Optimization
• Is increasing the efficiency of a system by:
– Max CPU utilization
– Max throughput
– Minimum turnaround time
– Minimum waiting time
– Minimum response time

10
 First Come First Serve(FCFS)
• A process arrives first in a ready state will be executed first by the
CPU irrespective of the burst time or the priority.
• This is implemented by using the First In First Out (FIFO) queue.
• when a process enters into the ready state, it will be linked to the
tail of the queue and the CPU starts executing the processes by
taking the process from the head of the queue.
• If a CPU is allocated to a process then it can't be taken back until
it finishes the execution of that process.
• Jobs are executed on first come, first serve basis.
• It is a non-preemptive.

11
12
Process Burst time Wait Comp. Turn Res. time
time time round
time

p1 24 0 24 24 0

p2 3 24 27 27 24

p3 3 27 30 30 27

TRT=BT+WT ( or TRT=CT-AT)

13
 Given
Process Arrival Time Burst time

p1 0 24

p2 5 3

p3 10 3

14
Process Arrival Burst time Wait Comp. Turn Res.
time time time round time
time

p1 0 24 0 24 24 0

p2 5 3 19 27 22 19

p3 10 3 17 30 20 17

TRT=BT+WT ( or TRT=CT-AT)

15
16
 Exercise: Fill free space using slide 15.
Process Burst time Wait Comp. Turn Res.
time time round time
time

p2 3

p3 3

p1 24

TRT=BT+WT ( or TRT=CT-AT)

17
 Example of FCFS

• So, based on the arrival time, the process P1 will be executed for the
first 18ms. After that, the process P2 will be executed for 7ms and finally,
the process P3 will be executed for 10ms.
18
19
 Exercise on FCFS

Process Arrival Burst time Wait Comp. Turn Res.

time time time round time
time
p0 0 5

p1 1 3

P2 2 8

p3 3 6

20
 Exercise

• Find:
– waiting time of each process and average waiting time
– Turn round of each process and average turn round time
– Completing and response time of each process.

21
• Advantages of FCFS:
– It is the most simple scheduling algorithm and is
easy to implement.
• Disadvantages of FCFS:
– This algorithm is non-preemptive so you have to
execute the process fully and after that other
processes will be allowed to execute.
– FCFS can cause long waiting times, especially when
the first job takes too much CPU time.

22
 Shortest-Job-First(SJF) Scheduling
• In the FCFS, we saw if a process is having a very high burst time and it
comes first then the other process with a very low burst time have to
wait for its turn. So, this problem can be solved by SJF.
• In SJF algorithm, a process having a minimum burst time at a particular
instant of time will be executed first.
• When the CPU is available, it is assigned to the process that has the
smallest next CPU burst.
• If the next CPU bursts of two processes are the same, FCFS scheduling
is used to break the tie.
• scheduling depends on the length of the next CPU burst of a process,
rather than its total length.
• When several jobs are sitting in the input queues waiting to be started
the scheduler picks the shortest job first.
• This algorithm will be optimal when all the jobs arrive simultaneously.

23
 Shortest Job First(SJF)
• Types of SJF:
– Non-preemptive : if the process starts its execution then it will
be fully executed and then some other process will come.
– once CPU given to the process it cannot be preempted until
completes its CPU burst time.
– preemptive: if new process with less burst time than the
remaining time of currently executed process come, CPU will
be allocated to the newly arrived process forcefully.
– 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).

24
 Example
• Consider the following set of processes, with the length of the CPU
burst given in milliseconds.

• using SJF scheduling, we would schedule the above processes

according to the following Gantt chart.

• Waiting time: p1=3, p2=16,p3=9,p4=0

• Average=(3+16+9+0)/4=7 25
26
 Shortest Job First (SJF) scheduling
•

Process Arrival Burst Waiting Completio Turn round Respons

time time time n time time e time

p1 0 7 0 7 7 0

p2 2 4 6 12 10 6

P3 4 1 3 8 4 3

p4 5 4 7 16 11 7

TRT=BT+WT
TRT=CT-AT
WT=RT-AT
27
Non-preempt SJF

28
 Preemptive SJF algorithm
• This is the preemptive approach of the Shortest
Job First algorithm. Here, at every instant of time,
the CPU will check for some shortest job. For
example, at time 0ms, we have P1 as the shortest
process. So, P1 will execute for 1ms and then the
CPU will check if some other process is shorter
than P1 or not. If there is no such process, then
P1 will keep on executing for the next 1ms and if
there is some process shorter than P1 then that
process will be executed. This will continue until
the process gets executed.

29
• Example of Preemptive SJF
• Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
• SJF (preemptive)
P1 P2 P3 P2 P4 P1

0 2 4 5 7 11 16

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

 Exercise
• Find :
– Competition, response and turn round time of each
process.
– Average response time, turn round time
• Based on slide number 30

31
Given

32
Complete scheduling information for slide 31

33
• The SJF scheduling algorithm is provably optimal, in that it gives
the minimum average waiting time for a given set of processes.
• SJF is optimal – gives 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. Consequently, the average waiting time
decreases.

34
 Exercise
• Process Arrival Time Burst Time
• P1 0.0 3
• P2 2.0 5
• P3 4.0 10
• P4 5.0 2
• Draw Gantt chart using SJF (preemptive and
non-preemptive) .

35
Exercise

36
• Advantage of SJF:
– optimal – gives minimum average waiting time for a
given set of processes.
• Short processes will be executed first.
• Disadvantage SJF:
– SJF may cause starvation. Consider a situation when
a long process is there in the ready queue and
shorter processes keep coming.

37
 Round Robin(RR) Scheduling Algorithm
• Each process is provided a fixed time to execute, it is called
a quantum/Time Slice in cyclic way.
• Once a process is executed for a given time period, it is
preempted and other process executes for a given time period.
• Context switching is used to save states of preempted processes.
• If the time quantum for round robin scheduling is very large,
then it behaves same as FCFS scheduling.
• Round Robin is the preemptive process scheduling algorithm.

38
 RR cont’d
• each user or process get a share of the CPU at regular
intervals.
• The ready queue is treated as a circular queue.
• Each process gets a small unit of CPU time (time
quantum), 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.

39
40
Proc AT Brust
P0 0 5
P1 1 3
P2 2 8
P3 3 6

41
 Round robin with quantum =3

pr AT BT CT TT W RT
oc T
ess
p1 0 8 22 22 14 0
P2 5 2 11 6 4 4
P3` 1 7 23 22 15 2
``
P4 6 3 14 8 5 5
p5 8 5 25 17 12 9

p1 p3 p1 p2 p4 p3 p5 p1 p3 p5

0 3 6 9 11 14 17 20 22 23 25
42
 Exercise
• Consider a system having 5 processes with the
following CPU burst time and with the RR
Time Quantum = 15.
• Process Burst Time
• P1 25
• P2 35
• P3 18
• P4 24
• P5 5
• Show the Gant chart based on RR algorithm. 43
 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).
• Problem ≡StarvaIon –low priority processes may never
execute.
• Solution ≡ Aging – as time progresses increase the
priority of the process.

44
 Example
• consider the following set of processes, assumed to have arrived at
time 0 in the order P1, P2, ・ ・ ・, P5, with the length of the CPU
burst given in milliseconds:

• Using priority scheduling, we would schedule these processes

according to the following Gantt chart:

• The average waiting time is 8.2 milliseconds 45

• When a process arrives at the ready queue, its priority is compared
with the priority of the currently running process.
• A major problem with priority scheduling algorithms is indefinite
blocking, or starvation.
• Exercise
• Consider 5 processes with the following CPU burst time and priority
number.
• Process burst time priority
• P1 3 4
• P2 7 2
• P3 13 1
• P4 27 3
• P5 1 5
• Question : draw Gant chart and compute average waiting time.
46
Priority Algorithm (non-preemptive)

process Burst time priority

P1 5 1
P2 3 2
P3 8 1
p4 6 3

47
 Priority Algorithm (preemptive)
process arrival time Burst time priority
2
P1 0 1
6
P2 1 7
3
P3 2 3
5
p4 3 6
4
P5 4 5
10
P6 5 15
9
p7 15 8

48
 complete scheduling information of priority(preemptive) algorithm

process
•
P1
P2
P3
p4
P5
P6
p7

49
• Advantage priority algorithm:
– It is possible to execute urgent process first
• Disadvantage priority algorithm :
– starvation of process is possible.

50