First Come First Serve (FCFS) Scheduling

• It's the simplest CPU scheduling algorithm.

• It works like a queue: the first software to request the CPU gets it first.

• It is non-preemptive, so once a software starts running, it keeps the CPU until it finishes.

Each process has:

• Arrival Time (AT) – when it enters the queue.

• Burst Time (BT) – how long it needs the CPU.

The CPU runs the software in the order of arrival

Process Arrival Time Burst Time

P1 0 5

P2 1 3

P3 2 8

• Execution Order: P1 → P2 → P3

Calculated Times:

Process Completion Time (CT) Turnaround Time (TAT) Waiting Time (WT)

P1 5 5 0

P2 8 7 4

P3 16 14 6

• TAT = CT - AT

• WT = TAT - BT
Shortest Job First (SJF) Scheduling
SJF (Shortest Job First) is a non-preemptive scheduling algorithm that selects the process with the
smallest CPU burst time (the shortest execution time) to execute next.

It means:

“The process that requires the least amount of CPU time is executed first.”

Characteristics:

• Type: Non-preemptive

• Selection Criterion: CPU burst time (shortest next job first)

• Goal: Minimize average waiting and turnaround time

• Disadvantage: Can cause starvation (long jobs may never get CPU)

Example:

Process Burst Time (ms)

P1 6

P2 8

P3 7

P4 3

Execution Order:

The shortest burst time is P4 (3) → then P1 (6) → then P3 (7) → then P2 (8).

Order: P4 → P1 → P3 → P2

Advantages:

Minimum average waiting time

Simple and efficient when burst times are known

Disadvantages:
 Not suitable for real-time systems
Requires knowledge of CPU burst time in advance
Causes starvation for longer processes

Shortest Remaining Job First (SRJF)

Definition:

SRJF (Shortest Remaining Job First) is the preemptive version of SJF.

In this algorithm, if a new process arrives with a shorter remaining burst time than the current running
process, the CPU is preempted and given to the new process.

It means:

“At any moment, the process with the smallest remaining time gets the CPU.”

Characteristics:

• Type: Preemptive

• Selection Criterion: Remaining burst time

• Goal: Reduce average waiting time

• Can preempt: Yes, when a shorter job arrives

Example:

Process Arrival Time Burst Time

P1 0 7

P2 2 4

P3 4 1

P4 5 4

Execution (Step-by-step):

• At time 0 → P1 starts (7 ms).

 • At time 2 → P2 arrives (burst 4 < remaining 5 of P1), so P1 is preempted.

• At time 4 → P3 arrives (burst 1 < remaining 2 of P2), so P2 is preempted.

• P3 runs and finishes quickly.

• CPU returns to P2, then later resumes P1 and P4.

Advantages:

Better average waiting time than SJF

Suitable when process times vary dynamically

Disadvantages:

More complex to implement

May cause starvation for long processes
Requires knowledge of remaining burst times

Priority Scheduling
Priority Scheduling is a CPU scheduling algorithm in which each process is assigned a priority number,
and the CPU is allocated to the process with the highest priority.

Rule:
The process with the highest priority runs first.
If two processes have the same priority, they are scheduled using FCFS (First Come, First Served).

Types of Priority Scheduling

Type Description

Non-
Once a process starts execution, it cannot be stopped until it finishes.
preemptive

If a new process arrives with a higher priority, it preempts (interrupts) the current
Preemptive
running process.

Example 1: Non-preemptive Priority Scheduling

Process Burst Time (ms) Priority (1 = highest)

P1 10 3

P2 1 1

P3 2 4

P4 1 2

Step 1: Arrange according to priority

The smaller the number → higher the priority.

Order of execution: P2 → P4 → P1 → P3

Step 2: Gantt Chart

| P2 | P4 | P1 | P3 |

0 1 2 12 14

Step 3: Calculate Waiting & Turnaround Times

Process Burst Time Priority Waiting Time Turnaround Time

P2 1 1 0 1

P4 1 2 1 2

P1 10 3 2 12

P3 2 4 12 14

Step 4: Average Times

• Average Waiting Time: (0 + 1 + 2 + 12) / 4 = 3.75 ms

• Average Turnaround Time: (1 + 2 + 12 + 14) / 4 = 7.25 ms

 Example 2: Preemptive Priority Scheduling

Process Arrival Time Burst Time Priority

P1 0 5 2

P2 1 3 1

P3 2 8 4

P4 3 6 3

Execution Explanation:

1. At time 0 → P1 starts (priority 2).

2. At time 1 → P2 arrives (priority 1, higher) → P1 is preempted.

3. P2 runs from 1–4 and finishes.

4. P1 resumes (priority 2) from 4–9.

5. P4 arrives at time 3 (priority 3) but must wait (lower priority than P1).

6. After P1, P4 runs (9–15).

7. Then P3 (priority 4) runs last (15–23).

Order: P1 → P2 → P1 → P4 → P3

Advantages of Priority Scheduling

• Efficient for time-critical processes (real-time systems).

• Flexible — priorities can be assigned based on importance or resource needs.

Disadvantages

• Starvation (Indefinite blocking):

A low-priority process may never get CPU if high-priority processes keep arriving.

• Complexity: Needs proper handling of priority assignments.

🩵 Solution: Use Aging — gradually increase the priority of waiting processes to avoid starvation.
Round Robin (RR) Scheduling
Round Robin Scheduling is a preemptive scheduling algorithm that assigns a fixed time slice (called
time quantum) to each process in the ready queue.

The CPU executes each process for a small unit of time (quantum).
If a process doesn’t finish in that time, it is moved to the back of the queue, and the CPU is given to
the next process.

Key Features:

Feature Description

Type Preemptive

Basis Time-sharing

Time Quantum Fixed small amount of CPU time (e.g., 2–5 ms)

Goal Ensure fairness — every process gets equal CPU time in turns

Used In Time-sharing and interactive systems (like Windows, Linux)

Example: Round Robin Scheduling

Process Burst Time (ms)

P1 5

P2 4

P3 2

P4 1

Let’s assume Time Quantum = 2 ms.

Step 1: Execution Order (Gantt Chart)

Each process gets 2 ms, then the CPU moves to the next process in the queue.

Time Process Executed

0–2 P1 (Remaining = 3)

2–4 P2 (Remaining = 2)

4–6 P3 (Remaining = 0 Finished)

6–8 P4 (Remaining = 0 Finished)

8–10 P1 (Remaining = 1)

10–12 P2 (Remaining = 0 Finished)

12–13 P1 (Remaining = 0 Finished)

Gantt Chart

| P1 | P2 | P3 | P4 | P1 | P2 | P1 |

0 2 4 6 8 10 12 13

Step 2: Calculate Waiting and Turnaround Times

Process Burst Time Completion Time Turnaround Time (CT – AT) Waiting Time (TAT – BT)

P1 5 13 13 8

P2 4 12 12 8

P3 2 6 6 4

P4 1 8 8 7

Step 3: Average Times

• Average Waiting Time = (8 + 8 + 4 + 7) / 4 = 6.75 ms

• Average Turnaround Time = (13 + 12 + 6 + 8) / 4 = 9.75 ms

 Advantages of Round Robin

• Fair: Every process gets equal CPU time.

• Simple and easy to implement.

• Ideal for time-sharing systems and interactive processes.

• Reduces starvation (no process waits forever).

Disadvantages of Round Robin

• Performance depends heavily on the time quantum chosen:

o Too small → too many context switches (overhead increases).

o Too large → behaves like FCFS (not fair).

• Doesn’t prioritize urgent or short tasks.

Choosing the Right Time Quantum

• Time quantum should be slightly greater than the average CPU burst time.

• Common values: 10–100 milliseconds in real systems.

Summary

Feature Description

Type Preemptive

Basis Time-sharing

Key Parameter Time Quantum

Goal Fairness among processes

Common Problem Too small or large quantum affects performance