OPERATING SYSTEMS

PROCESS SCHEDULING
ALGORITHMS
By
Dr.N.Shirisha, Assoc.Prof.
DEPARTMENT OF CSE

Dr.N.Shirisha, Associate Professor

 PROCESS SCHEDULING ALGORITHMS

What is mean by process

scheduling?
• Definition: Manages process execution by allocating CPU time efficiently.
• Goal: Ensures optimal system performance and responsiveness.
• Types: Long-term, Short-term, and Medium-term scheduling.
• Queues: Job Queue, Ready Queue, and Waiting Queue manage processes.
• Context Switching: Saves and loads process states for multitasking.
• Algorithms: FCFS, SJF, Round Robin, and Priority Scheduling.
• Impact: Improves CPU utilization, process execution speed, and system efficiency.

Dr.N.Shirisha, Associate Professor

 PROCESS SCHEDULING ALGORITHMS

TERMS TO REMEMBER:

 Burst Time (BT):The total time a process needs for execution on the CPU.
 Arrival Time (AT):The time when a process enters the ready queue.
 Completion Time (CT):The time when a process completes execution.
 Turnaround Time (TAT):The total time a process takes from arrival to completion.
Formula: TAT = CT - AT
 Waiting Time (WT):The total time a process spends in the ready queue waiting for execution.
Formula: WT = TAT - BT
 Response Time (RT):The time from process arrival to its first execution.
Formula: RT = First Execution Time - AT
 Throughput:The number of processes completed per unit time.
 Context Switching:The process of switching from one process to another, saving and restoring state.
 Preemptive vs. Non-Preemptive Scheduling
 Preemptive: The CPU can be taken away from a process (e.g., Round Robin, Preemptive SJF).
 Non-Preemptive: A process runs until completion or waiting (e.g., FCFS, Non-Preemptive SJF).

Dr.N.Shirisha, Associate Professor

 PROCESS SCHEDULING ALGORITHMS

TYPES OF PROCESS SCHEDULING ALGORITHMS:

1.First Come First Served(FCFS):
 FCFS is the simplest scheduling algorithm. Processes execute in the order they arrive in the
ready queue.
 The process that arrives first gets executed first.
 It’s always Non-Preemptive.
 Uses a FIFO (First-In-First-Out) Queue to schedule processes.
 The serious demerit of this FCFS is the convoy effect(i.e all the other processes waiting for one busy
process to get off the CPU).
 Convoy Effect:A long-running process at the front of the queue can cause other processes to wait,
even if they have shorter burst times.
 FCFS Pros and Cons:
• Simple (+)
• Short jobs get stuck behind long ones (-)
• If all you’re buying is milk, doesn’t it always seem like you are stuck behind a cart full of
many items
• Performance is highly dependent on the order in which jobs arrive (-)

Dr.N.Shirisha, Associate Professor

 PROCESS SCHEDULING ALGORITHMS

EXAMPLE OF FCFS:
 Let’s consider three process arrive in order P1,P2,P3
• P1 burst time:24;
• P2 burst time:3;
• P3 burst time:3; Gantt Chart:
 Waiting Time
• P1: 0;P2: 24;P3: 27 P1 P2 P3
 Completion Time:
• P1: 24;P2: 27;P3: 30 0 24 27 30
 Average Waiting Time: (0+24+27)/3 = 17
 Average Completion Time: (24+27+30)/3 = 27

Dr.N.Shirisha, Associate Professor

 PROCESS SCHEDULING ALGORITHMS

2.Round Robin (RR) Scheduling:

 Works in a cyclic order (FIFO queue)
 Preemptive CPU scheduling algorithm
 Works in a cyclic order (FIFO queue)
 Each process gets a small unit of CPU time (time quantum)
• Usually 10-100 ms
• After quantum expires, the process is preempted and added to the end of the ready
queue
 Suppose N processes in ready queue and time quantum is Q ms:
• Each process gets 1/N of the CPU time
• In chunks of at most Q ms
• What is the maximum wait time for each process?
 No Depends
 Performance process waits more
on Size of Qthan (n-1)q time units
• Small Q => interleaved
• Large Q is like FCFS
• Q must be large with respect to context switch time, otherwise overhead is too high
(spending most of your time context switching!)
Dr.N.Shirisha, Associate Professor
 PROCESS SCHEDULING ALGORITHMS

Example of RR with Time Quantum = 20:

Process BurstTime
P1 53
P2 8
P3 68
P4 24
Waiting Time:P1: (68-20)+(112-88) = 72
P2: (20-0) = 20
P3: (28-0)+(88-48)+(125-108) = 85 Average Waiting Time: (72+20+85+88)/4 = 66.25
P4: (48-0)+(108-68) = 88 Average Completion Time: (125+28+153+112)/4 = 104.5
Completion Time:P1: 125
P2: 28
P3: 153
P4: 112 Dr.N.Shirisha, Associate Professor
 PROCESS SCHEDULING ALGORITHMS
Pros and Cons of RR Algorithm:
 pros:
1. Fairness: RR ensures that each process gets a fair share of CPU time, preventing any single process
from monopolizing the CPU.
2. Good Response Time: RR provides good response time for interactive processes, as each process gets a
chance to execute for a short period (time quantum).
3. Prevents Starvation: RR prevents starvation, as each process will eventually get a chance to execute.
 Cons:
1. Can Lead to Process Switching Overhead: If the time quantum is too small, RR can lead to high process
switching overhead, which can impact system performance.
2. Time Quantum Selection: The choice of time quantum (time slice) can significantly impact the
performance of RR. If the time quantum is too small, context switching overhead can be high. If it's too
large, response time can suffer.
3. Not Suitable for Real-Time Systems: RR is not suitable for real-time systems, as it does not provide any
guarantees about the maximum response time or deadline meeting.
Dr.N.Shirisha, Associate Professor
 PROCESS SCHEDULING ALGORITHMS

3.SHORTEST JOB FIRST:

 Definition: A CPU scheduling algorithm that selects the process with the shortest
burst time for execution first.
 Types: Can be preemptive (Shortest Remaining Time First - SRTF) or non-preemptive.
 Efficiency: Minimizes average waiting time and turnaround time compared to other
algorithms.
 Starvation Issue: Long processes may suffer indefinite delays if many short processes
keep arriving.
 Best for Batch Systems: Works well where process execution times are known in
advance.
 It may cause starvation if shorter processes keep coming. This problem can be solved
using the concept of ageing.
 AGING:Aging is a technique that gradually increases the priority of waiting processes
to prevent starvation.

Dr.N.Shirisha, Associate Professor

 PROCESS SCHEDULING ALGORITHMS

EXAMPLE OF SJF(NON-PREEMPTIVE):

Average waiting time=(0+20+27)/3=15.66

Average turn aroundtime=(20+27+31)/3=26
NOTE:If all procces arrives at time t=0, then it’s consider as Non-
preemptive SJF
Dr.N.Shirisha, Associate Professor
 PROCESS SCHEDULING ALGORITHMS

Pros and Cons of SJF:

 Pros of SJF:
1. SJF is better than the First come first serve(FCFS) algorithm as it reduces the average waiting time.
2. SJF is generally used for long term scheduling
3. It is suitable for the jobs running in batches, where run times are already known.
4. SJF is probably optimal in terms of average turnaround time.

 Cons of SJF:
SJF may cause very long turn-around times or starvation.
1. In SJF job completion time must be known earlier, but sometimes it is hard to predict.
2. Sometimes, it is complicated to predict the length of the upcoming CPU request.
3. It leads to the starvation that does not reduce average turnaround time.

Dr.N.Shirisha, Associate Professor

 PROCESS SCHEDULING ALGORITHMS

4.PRIORITY SCHEDULING:
 A CPU scheduling algorithm that assigns a priority to each process.
 The CPU executes the process with the highest priority first.
 If two processes have the same priority, they follow First-Come, First-Served (FCFS).
 TYPES OF PRIORITY SCHEDULING:
1.Preemitive priority scheduling :
A higher-priority process can interrupt a running lower-priority process.
Example: If a doctor is treating a regular patient and an emergency patient arrives, the emergency
case is treated immediately.
2. Non-Preemptive Priority Scheduling:
The currently running process cannot be interrupted.
The CPU assigns the next highest-priority process only when the running process finishes.
Example: In a queue at a bank, a priority customer is served first, but once a teller starts serving a
customer, they don’t stop midway.

Dr.N.Shirisha, Associate Professor

 PROCESS SCHEDULING ALGORITHMS

EXAMPLE OF PRIOITY SCHEDULING:

Let’s take an example with 5 processes:
process burst time priority
p1 3 1
p2 4 3
p3 2 2
p4 1 1
P5 3 4

Average waiting time=(0+3+4+6+10)/5=4.6

Average Turnaround time=(3+4+6+10+13)/5=7.2

Dr.N.Shirisha, Associate Professor

 PROCESS SCHEDULING ALGORITHMS

Pros and Cons of Priority Scheduling:

 Pros:
1. Gives priority to important processes.
2. Suitable for real-time systems (e.g., medical, banking, and military applications).
3. Helps manage multiple processes efficiently.

 Cons:
1. Starvation: Low-priority processes may never execute if high-priority tasks keep arriving.
2. Complexity: Requires an efficient way to manage priorities.

Dr.N.Shirisha, Associate Professor

Dr.N.Shirisha, Associate Professor