What Are Process Scheduling Algorithms?
Process Scheduling Algorithms are strategies used by an operating system (OS) to
determine the order in which processes are executed by the CPU. They are a
crucial component of multitasking and multiprogramming systems, enabling
efficient use of CPU resources while ensuring fairness among processes.
Types of Process Scheduling Algorithms
Process scheduling algorithms can be categorized into preemptive (where a
running process can be interrupted) and non-preemptive (where a process runs to
completion once started).
Round Robin Time: (Preemptive Scheduling Algorithm)
Each process gets a fixed time slice (quantum) before being moved to the back of
the queue. Balances responsiveness and fairness, especially in time-sharing
systems.
Time slice 2. Criteria = TQ, Mode = Preemption
Process Arrival Burst Completion Turn Waiting
Time Time Time around time
time
P1 0 5-2=3- 12 12 7
2=1
P2 1 4-2=2 11 10 6
P3 2 2-2=0 6 4 2
P4 4 1 9 5 4
AVG TAT: 7.75s
AVG WT: 4.75s
Priority Proces Arrival Burst Completitio TAT(CT- WT
s No. Time Time n Time AT) (TAT-BT)
10 P1 0 5-1=4-4=0 12 12 7
20 P2 1 4-1=3-3=0 8 7 3
30 P3 2 2-1=1-1=0 4 2 0
40 P4 4 1-1=0 5 1 0
Priority Scheduling (Preemptive):
Higher-priority processes can preempt lower-priority ones.
Criteria: Priority
Mode: Preemptive
Condition: Higher the number higher the priority
AVG TAT: 6.5 unit
AVG WT: 2.5 unit
FCFS (First Come First Serve) {Criteria: Arrival Time,
Mode: Non-Preemptive}
Proces Arrival Burst Completio Turn WT (TAT-
s Time Time n Time TAT(CT- BT)
AT)
P1 0 5 5 5 0
P2 1 4 9 8 4
P3 2 2 11 9 7
P4 4 1 12 8 7
Proces Arrival Burst Completion Turn Waiting
s Time Time Time around time
time
P1 1 3 6 5 2
P2 2 4 10 8 4
P3 1 2 3 2 0
P4 4 4 14 10 6
Shortest Job First (SJF):
Criteria: Burst Time
Mode: Non Premmptive
AVG TAT : 6.25
AVG WT : 3
Process Arrival Burst Completion Turn Waiting
Time Time Time around time
time
P1 3 1 7 4 3
P2 1 4 16 15 11
P3 4 2 9 5 3
P4 0 6 6 6 0
P5 2 3 12 10 7
Criteria: Burst Time
Mode: Non-Preemptive
AVG TAT: 8 unit
AVG WT: 4.8 unit
Shortest Remaining Time First (SRTF):
Criteria: Burst Time
Proces Arrival Burst Completio Turn Waiting
s Time Time n Time around time
time
P1 0 5-1=4- 9 9 4
1=3-3=0
P2 1 3-1=2- 4 3 0
1=1-1=0
P3 2 4 13 11 7
P4 4 1-1=0 5 1 0
Mode: Preemptive
AVG TAT: 6.0 unit
AVG WT: 2.75 unit
Banker’s Algorithm
The Banker’s Algorithm is a deadlock avoidance algorithm used in operating
systems to allocate resources to processes in a safe and controlled manner. It
ensures that the system remains in a safe state by carefully allocating resources
and avoiding any allocation that could lead to deadlock.
Key Concepts
1. Safe State:
A system is in a safe state if there exists at least one sequence of processes (safe
sequence) such that each process can finish executing with the available resources, and
all processes can eventually complete.
2. Unsafe State:
A state where no safe sequence exists. This does not mean a deadlock has occurred yet,
but it indicates that one could happen.
Total Resources: A = 10 – 7 = 3, B = 5 – 2 = 3, C = 7 – 5 = 2
3. Deadlock:
A situation where processes are stuck waiting for resources indefinitely because no
process can proceed.
P2 P4 P5 ->
Total Resources:
A=10-7=3, B=5-2=3, C=7-5=2
Current available >= Remaining Need
P2->P4->P5->P1->P3
Class Task:
Process Allocation Max Need Current Remaining Need
Available (Max - Allocation)
A B C A B C A B C A B C
P1 0 1 0 7 5 3 3 3 2 7 4 3
2 0 0
P2 2 0 0 3 2 2 5 3 2 1 2 2
2 1 1
P3 3 0 2 9 0 2 7 4 3 6 0 0
0 0 2
P4 2 1 1 4 2 2 7 4 5 2 1 1
0 0 2
P5 0 0 2 5 3 3 7 4 7 5 3 1
---------------- 7 4 3
7 2 5 14 8 10
Tasks:
a) Calculate the Remaining Need.
Question: You have 4 processes (P0, P1, P2, P3) and resource types (A, B, C). The following
information is given:
Available Vector = [2, 1, 1]
Tasks:
o Compute the Need Matrix.
o Determine if the system is in a safe state.
o If not in a safe state, explain why and identify the processes
causing potential deadlock.
FCFS:
1. Consider the set of 5 processes whose arrival time and burst time are given below
If the CPU scheduling policy is FCFS, calculate the average waiting time and average turn
around time.
Mode: Non-preemptive
Criteria : Arrival Time
Process ID Arrival Time Burst Time Completion TAT (CT- WT (TAT -
Time AT) BT)
P1 3 4 7 4 0
P2 5 3 13 8 5
P3 0 2 2 2 0
P4 5 1 14 9 8
P5 4 3 10 6 3
ATAT = 5.8 unit
AWT = 3.2 unit
2. Consider the set of 3 processes whose arrival time and burst time are given below
If the CPU scheduling policy is FCFS, calculate the average waiting time and average turn
around time.
Process ID Arrival Time Burst Time Completion TAT WT
Time
P1 0 2 2 2 0
P2 3 1 4 1 0
P3 5 6 11 6 0
Round Robin:
1. Consider the set of 5 processes whose arrival time and burst time are given below
If the CPU scheduling policy is Round Robin with time quantum = 2 unit, calculate the
average waiting time and average turn around time.
Running Queue:
P1 P2 P3 P1 P4 P5 P2 P1 P5
0 2 4 5 7 9 11 12 13 14
Priority Scheduling Algorithm
1. Consider the set of 5 processes whose arrival time and burst time
are given below
If the CPU scheduling policy is priority non-preemptive, calculate
the average waiting time and average turn around time. (Higher
number represents higher priority)
2. Consider the set of 5 processes whose arrival time and burst time
are given below
If the CPU scheduling policy is priority preemptive, calculate the
average waiting time and average turn around time. (Higher
number represents higher priority)
Bankers Algorithm:
1. A single-processor system has three resource types X, Y, and Z,
which are shared by three processes. There are 5 units of each
resource type. Consider the following scenario, where the
column alloc denotes the number of units of each resource type
allocated to each process, and the column request denotes the
number of units of each resource type requested by a process in
order to complete execution. Which of these processes will
finish LAST?
1. P0
2. P1
3. P2
4. None of the above, since the system is in a deadlock
Total = [X Y Z] = [5 5 5]