Different Scheduling Algorithm, Which one to Used Where?

Scheduling algorithms determine which process or task gets the CPU next. The scheduler's goal is to optimize one or more of the following:

• CPU utilization
• Throughput
• Response time
• Waiting time
• Turnaround time
• Fairness
• Meeting real-time deadlines

---

Comparison Overview

Algorithm	Preemptive	Main Idea	Used In
FCFS	No	First process to arrive runs first	Simple batch systems
SJF	No (or Yes as SRTF)	Shortest job runs first	Batch processing
Round Robin	Yes	Equal CPU time for all	Time-sharing OS
Priority Scheduling	Yes/No	Highest-priority process first	RTOS, Embedded
Multilevel Queue	Yes	Separate queues for different classes	General-purpose OS
Multilevel Feedback Queue	Yes	Processes move between queues	Modern desktop OS
EDF	Yes	Earliest deadline first	Hard real-time systems

---

1. FCFS (First Come First Serve)

Definition

The process that arrives first gets the CPU first.

It is the simplest scheduling algorithm.

---

Logic

Ready Queue

P1 → P2 → P3 → P4

Execution

CPU

P1

↓

P2

↓

P3

↓

P4

---

Example

Process	Arrival	Burst
P1	0	5
P2	1	3
P3	2	2

Execution

0-----5-----8----10

P1    P2    P3

---

Advantages

• Very simple
• No starvation
• Easy implementation

Disadvantages

• Convoy Effect
• Long waiting time
• Poor response time

---

Used In

• Batch systems
• Printer queues

---

2. SJF (Shortest Job First)

Definition

The process with the smallest CPU burst time executes first.

---

Example

Process	Burst
P1	8
P2	4
P3	2
P4	1

Execution

P4

↓

P3

↓

P2

↓

P1

---

Advantages

• Minimum average waiting time
• Efficient for batch jobs

---

Disadvantages

• Need to know burst time beforehand
• Starvation of long jobs

---

Variant

Preemptive version:

Shortest Remaining Time First (SRTF)

---

3. Round Robin (RR)

Definition

Each process gets a fixed amount of CPU time called the Time Quantum.

If it doesn't finish, it goes to the end of the queue.

---

Example

Time Quantum = 2 ms

Queue

P1 P2 P3

Execution

P1

↓

P2

↓

P3

↓

P1

↓

P2

---

Advantages

• Fair
• Good response time
• No starvation

---

Disadvantages

If quantum is too small:

• Too many context switches

If quantum is too large:

• Behaves like FCFS

---

Used In

• Linux (historically for some scheduling classes)
• Windows
• Interactive systems

---

4. Priority Scheduling

Definition

The process with the highest priority executes first.

---

Example

Process	Priority
Brake	5
Engine	4
Display	2

Execution

Brake

↓

Engine

↓

Display

---

Types

Non-preemptive

Current process finishes first.

Preemptive

Higher-priority process immediately interrupts.

---

Advantages

• Critical tasks run first
• Excellent for RTOS

---

Disadvantages

Starvation of low-priority tasks.

---

Solution

Aging

Increase waiting process priority over time.

---

Used In

• OSEK
• AUTOSAR
• FreeRTOS
• VxWorks

---

5. Multilevel Queue Scheduling

Processes are permanently divided into different queues.

Example

System Queue

Interactive Queue

Batch Queue

Each queue has its own scheduling policy.

Example

System

↓

Round Robin

Interactive

↓

Priority

Batch

↓

FCFS

---

Example

Highest

System Queue

↓

Interactive Queue

↓

Batch Queue

Lowest

The scheduler first checks the highest-priority queue.

---

Advantages

• Good separation
• Efficient

---

Disadvantages

A process cannot move between queues.

---

Used In

Desktop operating systems.

---

6. Multilevel Feedback Queue (MLFQ)

Improvement over Multilevel Queue.

Processes can move between queues.

---

Example

Queue 1

High Priority
Quantum = 5

↓

Queue 2

Quantum = 10

↓

Queue 3

FCFS

---

Logic

Short jobs

Stay at top.

Long jobs

Move downward.

---

Example

P1

Queue 1

↓

Uses entire quantum

↓

Queue 2

↓

Uses entire quantum

↓

Queue 3

---

Advantages

• Adapts automatically
• Good response
• Prevents starvation

---

Disadvantages

• Complex implementation
• Difficult tuning

---

Used In

Modern Linux (conceptually)
Windows
macOS

---

7. EDF (Earliest Deadline First)

Used in Real-Time Systems.

Definition

The task with the nearest deadline executes first.

---

Example

Task	Deadline
T1	10 ms
T2	6 ms
T3	15 ms

Execution

T2

↓

T1

↓

T3

---

Dynamic Priority

Priority changes continuously.

Closer deadline

↓

Higher priority

---

Advantages

• Very efficient
• Maximum CPU utilization
• Optimal scheduling for many preemptive uniprocessor real-time workloads

---

Disadvantages

• More complex
• Requires accurate deadline information
• Less predictable than fixed-priority scheduling for certification in some safety-critical domains

---

Used In

• Aerospace
• Robotics
• Medical devices
• Telecom
• Some real-time Linux configurations

Note: OSEK/AUTOSAR OS does not use EDF. It uses fixed-priority preemptive scheduling because static priorities are simpler to analyze and certify for automotive safety.

---

Scheduling Algorithm Comparison

Algorithm	Preemptive	Starvation	Response Time	Real-Time Suitable	Complexity
FCFS	❌	No	Poor	No	Very Low
SJF	❌ (SRTF: Yes)	Yes	Good	No	Medium
Round Robin	✅	No	Very Good	Limited	Low
Priority	✅ / ❌	Yes	Excellent	Yes	Low
Multilevel Queue	✅	Possible	Good	Limited	Medium
Multilevel Feedback Queue	✅	Rare	Excellent	No	High
EDF	✅	No (under schedulable conditions)	Excellent	Yes	High

---

Which Scheduling Algorithm is Used Where?

Operating System / Platform	Scheduling Algorithm
OSEK OS	Fixed Priority Preemptive
AUTOSAR OS	Fixed Priority Preemptive
FreeRTOS	Fixed Priority Preemptive (optional cooperative mode)
Linux (normal tasks)	Completely Fair Scheduler (CFS)
Linux Real-Time (SCHED_FIFO, SCHED_RR)	Fixed Priority
Windows	Priority-based with dynamic adjustments
Aerospace RTOS	EDF or Fixed Priority
Medical RTOS	EDF or Fixed Priority

---

Interview Tips

A common interview question is:

"Why does AUTOSAR use Fixed Priority Scheduling instead of EDF?"

A strong answer is:

• Fixed priorities provide deterministic behavior.
• Worst-case response time analysis is simpler.
• Easier to certify for standards such as ISO 26262.
• Lower runtime overhead than dynamic-priority algorithms like EDF.
• Most automotive workloads have well-defined periodic tasks that map well to fixed priorities.

This demonstrates not only that you know the algorithms, but also why specific industries choose one over another.