Operating System · Chapter 15

CPU Scheduling Algorithms in OS: FCFS, SJF, SRTF, Priority & Round Robin

When many processes are waiting in the ready queue, the operating system must decide which process should get the CPU next. Different rules can be used to make this decision. These rules are called CPU Scheduling Algorithms in OS.

Students usually know the names FCFS, SJF, SRTF, Priority Scheduling and Round Robin, but numerical questions become confusing when arrival time, burst time, preemption, priority, time quantum and Gantt charts appear together. In this chapter, we will solve every major CPU scheduling algorithm step by step.

Quick Answer: CPU scheduling algorithms decide the order in which ready processes receive CPU time. FCFS uses arrival order, SJF selects the shortest available CPU burst, SRTF selects the shortest remaining burst, Priority Scheduling selects according to process priority, and Round Robin gives every process a fixed time quantum in turns.

FIVE MAJOR CPU SCHEDULING ALGORITHMS

FCFS Arrival Order

SJF Shortest Burst

SRTF Shortest Remaining

Priority Priority Value

Round Robin Time Quantum

What Are CPU Scheduling Algorithms in Operating System?

CPU Scheduling Algorithms in OS: FCFS, SJF, SRTF, Priority & Round Robin

A CPU scheduling algorithm is a rule used by the operating system to choose one process from the ready queue for CPU execution.

Different algorithms use different information. One algorithm may look at arrival time. Another may look at CPU burst time. Another may use priority. Round Robin gives processes repeated turns.

Simple Definition:
CPU Scheduling Algorithms in OS are methods used to decide which ready process should execute next and for how long.

Why Do We Need Different CPU Scheduling Algorithms?

Waiting We want processes to avoid unnecessary waiting.

Response Interactive processes should receive CPU service quickly.

Efficiency CPU time should be used productively.

Throughput A system should complete useful work efficiently.

Fairness Processes should not wait forever without CPU service.

Workload Different systems have different scheduling needs.

Preemptive vs Non-Preemptive CPU Scheduling

Before learning the algorithms, understand one very important difference.

Non-Preemptive

Once a process gets CPU, it normally continues until its current CPU burst finishes or it blocks.

Preemptive

The operating system can interrupt a running process and give the CPU to another ready process.

Examples:
FCFS → Non-preemptive
SJF → Usually taught as non-preemptive
SRTF → Preemptive
Priority → Can be preemptive or non-preemptive
Round Robin → Preemptive

Terms You Must Know Before Solving CPU Scheduling Numericals

Arrival Time – AT Time when a process becomes ready for CPU scheduling.

Burst Time – BT CPU execution time required by the process in the scheduling problem.

Completion Time – CT Time when the process completes.

Turnaround Time – TAT TAT = CT − AT

Waiting Time – WT WT = TAT − BT

Response Time – RT RT = First CPU Start − AT

Important: These formulas are used in the standard CPU scheduling numerical model where each process is represented by its required CPU burst.

What Is a Gantt Chart in CPU Scheduling?

A Gantt chart in CPU scheduling is a timeline showing which process uses the CPU during each time interval.

Example Gantt Chart CPU execution timeline

0 3 5 6

Once the Gantt chart is correct, completion time, turnaround time, waiting time and response time become much easier to calculate.

Process Set Used in Our Solved Examples

To make comparison easy, we will use the same four processes for all major CPU Scheduling Algorithms in OS.

Scheduling Dataset Lower priority number = higher priority

P1 Arrival Time = 0 Burst Time = 7 Priority = 3

P2 Arrival Time = 2 Burst Time = 4 Priority = 1

P3 Arrival Time = 4 Burst Time = 1 Priority = 4

P4 Arrival Time = 5 Burst Time = 4 Priority = 2

FCFS Scheduling Algorithm in OS

First Come First Served

FCFS Scheduling is the simplest CPU scheduling algorithm. The process that arrives first gets the CPU first.

FCFS Full Form: First Come First Served.

It follows the same basic idea as a normal queue: first arrival → first service.

Is FCFS Preemptive or Non-Preemptive?

FCFS is a non-preemptive CPU scheduling algorithm.

Once a process starts its CPU burst, another newly arriving process does not normally remove it from the CPU.

How FCFS Scheduling Works

Check the arrival time of all processes.

Put processes in arrival order.

Give CPU to the process that arrived first.

Let it complete its CPU burst.

Move to the next process in the queue.

FCFS Solved Example

Arrival order is: P1 → P2 → P3 → P4.

FCFS Gantt Chart Arrival order

0 7 11 12 16

Process	AT	BT	CT	TAT	WT	RT
P1	0	7	7	7	0	0
P2	2	4	11	9	5	5
P3	4	1	12	8	7	7
P4	5	4	16	11	7	7

Average TAT 8.75

Average WT 4.75

Average RT 4.75

Convoy Effect in FCFS Scheduling

FCFS can suffer from the convoy effect.

This happens when a long CPU-bound process reaches the front of the queue and several short processes are forced to wait behind it.

Long Job
P1

→

Short P2

→

Short P3

→

Short P4

Advantages of FCFS

very simple to understand
easy to implement using a queue
processes are served in arrival order
does not normally starve an arrived process

Disadvantages of FCFS

short processes may wait behind long processes
can produce high average waiting time
can suffer from convoy effect
not ideal when fast interactive response is important

SJF Scheduling Algorithm in OS

Shortest Job First

SJF Scheduling selects the ready process with the shortest CPU burst time.

SJF Full Form: Shortest Job First.

At every scheduling decision, choose the available process with the smallest CPU burst.

Is SJF Preemptive or Non-Preemptive?

The standard SJF algorithm is usually taught as non-preemptive.

Once a selected process starts running, a newly arriving shorter process does not interrupt it.

How SJF Scheduling Works

Look only at processes that have already arrived.

Compare their CPU burst times.

Select the process with the shortest burst.

Let that process finish its CPU burst.

Repeat the comparison among processes currently ready.

SJF Solved Example

At time 0, only P1 has arrived, so P1 must run first.

P1 completes at time 7. By then P2, P3 and P4 are ready.

P2 Burst = 4

P3 Burst = 1
✓ shortest

P4 Burst = 4

So P3 runs next. After P3, P2 and P4 both have burst time 4. Using arrival time as the tie breaker, P2 goes before P4.

SJF Gantt Chart Shortest available burst

0 7 8 12 16

Process	AT	BT	CT	TAT	WT	RT
P1	0	7	7	7	0	0
P2	2	4	12	10	6	6
P3	4	1	8	4	3	3
P4	5	4	16	11	7	7

Average TAT 8.00

Average WT 4.00

Average RT 4.00

Why Is SJF Important?

When the next CPU burst lengths are known accurately, choosing shorter work first can reduce average waiting time.

The practical problem is that the operating system normally does not know the exact future CPU burst of a process.

CPU Burst Prediction in SJF

In theory and textbooks, previous CPU bursts can be used to estimate a future burst. One common prediction formula is:

Exponential Averaging:

τ_n+1 = αt_n + (1 − α)τ_n

where:
t_n = actual previous burst
τ_n = previous prediction
α = weight between 0 and 1

Advantages of SJF

can reduce average waiting time
short jobs finish quickly
useful concept for understanding burst-based scheduling

Disadvantages of SJF

future CPU burst is not normally known exactly
long processes may wait for a long time
can suffer from starvation

SRTF Scheduling Algorithm in OS

Shortest Remaining Time First

SRTF Scheduling is the preemptive version of Shortest Job First.

SRTF Full Form: Shortest Remaining Time First.

The CPU is given to the ready process having the smallest remaining execution time.

Difference Between SJF and SRTF

SJF

Looks at shortest burst when CPU becomes free.

Normally non-preemptive.

SRTF

Continuously considers remaining time as processes arrive.

Preemptive.

SRTF Solved Example Step by Step

At time 0, only P1 is available. P1 starts running.

At time 2, P2 arrives. P1 has 5 units remaining. P2 needs 4 units. So P2 preempts P1.

At time 4, P3 arrives with burst time 1. P2 has 2 units remaining. P3 is shorter, so P3 gets CPU.

P3 finishes. P4 arrives with burst 4. P2 has only 2 remaining, so P2 resumes.

P2 finishes. P4 has 4 while P1 has 5 remaining. P4 runs.

P4 finishes. P1 completes its remaining 5 units.

SRTF Gantt Chart Shortest remaining time

0 2 4 5 7 11 16

Process	AT	BT	CT	TAT	WT	RT
P1	0	7	16	16	9	0
P2	2	4	7	5	1	0
P3	4	1	5	1	0	0
P4	5	4	11	6	2	2

Average TAT 7.00

Average WT 3.00

Average RT 0.50

In this particular example, SRTF produces the lowest average waiting time among the algorithms calculated here. That does not mean SRTF is automatically the best scheduling policy for every real system.

Advantages of SRTF

short processes can receive CPU quickly
can reduce average waiting time
responds to newly arriving short jobs

Disadvantages of SRTF

requires burst-time estimation
long processes may starve
preemption causes extra context-switch overhead
more complex than FCFS

Priority Scheduling Algorithm in OS

CPU selection based on process priority

In Priority Scheduling, every process is assigned a priority. The process with the highest scheduling priority is selected first.

Very important exam rule: A smaller number does not always mean higher priority in every system. The question must define the convention.

In our example: smaller priority number = higher priority.

P1 Priority 3

P2 Priority 1

P3 Priority 4

P4 Priority 2

Types of Priority Scheduling

Priority Scheduling can be:

Non-Preemptive Priority

Once a process starts, it continues its current CPU burst.

Preemptive Priority

A newly arrived higher-priority process may interrupt the running process.

Non-Preemptive Priority Solved Example

At time 0 only P1 exists, so P1 starts. At time 7, all remaining processes are available.

Their priorities are: P2 = 1, P4 = 2, P3 = 4. Therefore the order becomes: P2 → P4 → P3.

Non-Preemptive Priority Gantt Chart Lower number = higher priority

0 7 11 15 16

Process	Priority	CT	TAT	WT	RT
P1	3	7	7	0	0
P2	1	11	9	5	5
P3	4	16	12	11	11
P4	2	15	10	6	6

Average TAT 9.50

Average WT 5.50

Average RT 5.50

Preemptive Priority Example

Now suppose the same priority values are used with preemptive Priority Scheduling.

P1 starts at time 0. At time 2, P2 arrives with priority 1, which is higher than P1's priority 3. P2 therefore preempts P1.

Preemptive Priority Gantt Chart Higher priority can preempt

0 2 6 10 15 16

Average TAT 9.00

Average WT 5.00

Average RT 3.00

Starvation in Priority Scheduling

A low-priority process may keep waiting if higher-priority processes continue to enter the ready queue.

This problem is called starvation.

Problem: Starvation

A low-priority process may wait for a very long time.

Solution: Aging

Gradually improve the priority of a process that has waited for a long time.

Advantages of Priority Scheduling

important processes can receive preference
flexible scheduling policy
can be implemented as preemptive or non-preemptive

Disadvantages of Priority Scheduling

low-priority processes may starve
priority assignment can be difficult
aging may be required to maintain fairness

Round Robin Scheduling Algorithm in OS

Time-sharing CPU scheduling

Round Robin Scheduling is a preemptive CPU scheduling algorithm commonly associated with time-sharing systems.

Every ready process receives a small fixed amount of CPU time called a time quantum or time slice.

2 time units

Time Quantum = 2

Each process can use the CPU for at most 2 time units during one turn.

If the process still has remaining burst time, it goes back to the ready queue.

How Round Robin Scheduling Works

Put ready processes into a FIFO ready queue.

Give the first process one time quantum.

If the process finishes, remove it.

If it still needs CPU time, place it at the back of the ready queue.

Give the next ready process its turn.

Round Robin Solved Example

We will use: Time Quantum = 2 units.

Round Robin Gantt Chart Time Quantum = 2

0 2 4 6 7 9 11 13 15 16

Process	AT	BT	CT	TAT	WT	RT
P1	0	7	16	16	9	0
P2	2	4	9	7	3	0
P3	4	1	7	3	2	2
P4	5	4	15	10	6	4

Average TAT 9.00

Average WT 5.00

Average RT 1.50

Why Response Time Is Important in Round Robin

Round Robin gives processes repeated chances to use the CPU.

Because a process does not need to wait for every earlier process to fully finish, it can often receive its first CPU service sooner than in a simple FCFS queue.

Effect of Time Quantum in Round Robin

Very Large Time Quantum

If the quantum becomes very large, Round Robin begins to behave more like FCFS because processes may finish before their time slice expires.

Very Small Time Quantum

Processes get frequent turns, but the number of context switches can increase, creating more scheduling overhead.

Advantages of Round Robin

gives ready processes repeated CPU opportunities
useful for interactive and time-sharing ideas
can provide good response time
simple queue-based operation

Disadvantages of Round Robin

performance depends strongly on time quantum
small quantum creates more context switches
average waiting time may not be minimum

FCFS vs SJF vs SRTF vs Priority vs Round Robin

Algorithm	Main Selection Rule	Preemptive?	Main Strength	Main Problem
FCFS	Earliest arrival	No	Very simple	Convoy effect
SJF	Shortest CPU burst	No	Low average waiting can be achieved with accurate burst knowledge	Need burst prediction; starvation possible
SRTF	Shortest remaining time	Yes	Quick service for short remaining work	Starvation and preemption overhead
Priority	Highest scheduling priority	Both possible	Important jobs can get preference	Starvation
Round Robin	Fixed time quantum in turns	Yes	Responsive and fair-turn behaviour	Quantum and context-switch overhead

Performance Comparison Using Our Same Process Set

Because every algorithm above used the same processes, we can directly compare the calculated averages.

Algorithm	Average Turnaround	Average Waiting	Average Response
FCFS	8.75	4.75	4.75
SJF	8.00	4.00	4.00
SRTF	7.00	3.00	0.50
Priority – Non-Preemptive	9.50	5.50	5.50
Priority – Preemptive	9.00	5.00	3.00
Round Robin – q = 2	9.00	5.00	1.50

Do not memorize these numbers. They belong only to this process set.

Change the arrival times, burst times, priorities or Round Robin time quantum, and the result can change completely.

How Different CPU Scheduling Algorithms Think

FCFS asks: Who came first?

SJF asks: Who has the shortest CPU burst among ready processes?

SRTF asks: Who has the shortest remaining CPU time right now?

Priority Scheduling asks: Who has the highest scheduling priority?

Round Robin asks: Whose turn is next for one time quantum?

Operating System asks: Which policy fits the workload and performance goals?

Which CPU Scheduling Algorithm Is Best?

There is no single CPU scheduling algorithm that is best for every workload.

The answer depends on what the system is trying to improve.

Simple Queue FCFS is easy to understand and implement.

Short Jobs SJF and SRTF give preference to shorter CPU work.

Importance Priority Scheduling uses process priority.

Fast First Response Round Robin can be useful for time-sharing and interactive workloads.

Fairness Concern Policies must avoid processes waiting indefinitely.

Real Systems Modern operating systems can use more advanced scheduling designs.

What Happens When Two Processes Have the Same Burst Time or Priority?

CPU scheduling questions often contain ties.

For example, two SJF processes may have the same burst time, or two Priority Scheduling processes may have the same priority.

Unless the question gives another rule, arrival order is commonly used as a tie breaker in classroom numericals.

If arrival time is also equal, the question may use process order or another defined rule.

Always write the tie-breaking assumption before solving an ambiguous question.

What If No Process Has Arrived?

Sometimes the CPU becomes free but no process has arrived yet.

In that case, the CPU remains idle until the next process becomes ready.

Example with CPU Idle Time No ready process available

IDLE

0 3 5 8

Do not skip idle time in the Gantt chart. It affects completion and turnaround calculations.

Waiting Time vs Response Time

This is one of the most common mistakes in CPU scheduling numericals.

Response Time

Measures only the wait before the process gets CPU for the first time.

Waiting Time

Measures all time spent waiting in the ready queue during the process's life.

In a non-preemptive one-burst numerical, response time and waiting time are often equal.

In algorithms such as SRTF and Round Robin, a process can run, get preempted and wait again. Therefore its total waiting time can be much larger than its response time.

Context Switching in CPU Scheduling Algorithms

In preemptive algorithms, the CPU may move from one process to another many times.

During a context switch, the operating system saves the state of the old process and restores the state of the new process.

Context switching allows multitasking, but it also creates overhead.

This is why an extremely small Round Robin time quantum is not automatically better. More frequent switching can increase overhead.

Which CPU Scheduling Algorithms Can Cause Starvation?

Starvation means a process remains ready but waits for an excessively long time because other processes keep receiving CPU preference.

SJF / SRTF Long jobs can be delayed if shorter jobs continue arriving.

Priority Scheduling Low-priority processes may be delayed by repeated higher-priority arrivals.

Aging Can help reduce priority-based starvation by improving waiting-process priority.

Round Robin Ready processes rotate through the queue, so classic priority-style starvation is less natural under a basic fair Round Robin model.

How to Solve Any CPU Scheduling Numerical Step by Step

Write the process table.
Note PID, Arrival Time, Burst Time, Priority and Time Quantum if required.

Identify the algorithm.
FCFS, SJF, SRTF, Priority or Round Robin.

Check whether the algorithm is preemptive.
This changes whether a running process can be interrupted.

Build the Gantt chart.
Never calculate final averages before the timeline is correct.

Find Completion Time.
Record when every process finishes.

Calculate Turnaround Time.
TAT = CT − AT.

Calculate Waiting Time.
WT = TAT − BT.

Calculate Response Time.
RT = first CPU start − arrival time.

Calculate averages.
Add individual values and divide by the number of processes.

Common Mistakes in CPU Scheduling Algorithms

Using processes that have not arrived yet.
SJF, SRTF and Priority Scheduling can only choose among processes currently ready.

Using original burst time instead of remaining time in SRTF.
SRTF compares remaining CPU time.

Assuming lower priority number always means higher priority.
Follow the convention given in the question.

Forgetting to requeue an unfinished Round Robin process.
After its quantum ends, it goes back to the ready queue if CPU work remains.

Confusing waiting time with response time.
Response time only measures time until first CPU service.

Ignoring CPU idle time.
If no process is ready, show IDLE in the Gantt chart.

Changing tie-breaking rules halfway through the numerical.
Decide the tie rule once and use it consistently.

Calling SRTF the same as SJF.
SRTF is the preemptive version and can interrupt a running process.

Easy Memory Trick for CPU Scheduling Algorithms

FCFS Queue at a ticket counter: whoever comes first gets served first.

SJF Finish the shortest available task first.

SRTF Keep checking which task has the least work remaining.

Priority Important task gets preference.

Round Robin Everyone gets a limited turn and then moves to the back.

Gantt Chart The timeline that proves who actually used the CPU and when.

CPU Scheduling Algorithms Exam Preparation

OPERATING SYSTEM · CHAPTER 15 · EXAM MODE

For a 2-Mark Question

Answer: CPU Scheduling Algorithms in OS are methods used by the operating system to select which ready process gets the CPU. Common algorithms include FCFS, SJF, SRTF, Priority Scheduling and Round Robin.

For a 5-Mark Question

Explain:

meaning of CPU scheduling algorithm
FCFS
SJF or SRTF
Priority Scheduling
Round Robin
one major advantage or limitation of each

For a 10-Mark Question

Write in this order:

CPU scheduling definition
preemptive vs non-preemptive scheduling
AT, BT, CT, TAT, WT and RT
Gantt chart concept
FCFS with example
SJF with example
SRTF with example
Priority Scheduling with starvation and aging
Round Robin with time quantum
comparison of algorithms

For a Numerical Question

Golden rule: First make the correct Gantt chart. Then calculate CT → TAT → WT → RT → averages.

CPU Scheduling Algorithms Practice Questions

Q1. What are CPU Scheduling Algorithms in OS?

Q2. Explain FCFS Scheduling with an example.

Q3. What is convoy effect in FCFS?

Q4. What is SJF Scheduling?

Q5. Why is exact SJF difficult to implement using future CPU burst lengths?

Q6. What is SRTF Scheduling?

Q7. Differentiate SJF and SRTF.

Q8. What is Priority Scheduling?

Q9. What is starvation?

Q10. How does aging help in Priority Scheduling?

Q11. What is Round Robin Scheduling?

Q12. What is time quantum?

Q13. What happens if the Round Robin quantum is very large?

Q14. What happens if the quantum is too small?

Q15. Write formulas for TAT, WT and RT.

Q16. Why is a Gantt chart important?

Q17. Which scheduling algorithms are preemptive?

Q18. Can Priority Scheduling be preemptive and non-preemptive?

Q19. What happens when two processes have equal burst time?

Q20. Why is there no universal best CPU scheduling algorithm?

CPU Scheduling Algorithms Quick Revision

FCFS: first arrival runs first.

FCFS Type: non-preemptive.

Convoy Effect: short jobs wait behind a long job.

SJF: shortest available CPU burst first.

SJF Type: normally non-preemptive.

SRTF: shortest remaining CPU time first.

SRTF Type: preemptive.

Priority: process selected according to priority.

Priority Type: can be preemptive or non-preemptive.

Starvation: process waits excessively long.

Aging: gradually improves waiting-process priority.

Round Robin: every ready process receives a time slice.

Time Quantum: maximum CPU time per RR turn.

TAT: CT − AT.

WT: TAT − BT.

RT: First Start − AT.

Gantt Chart: shows CPU execution order.

Preemption: running process can be interrupted.

Frequently Asked Questions About CPU Scheduling Algorithms in OS

What are CPU Scheduling Algorithms in OS?

CPU Scheduling Algorithms in OS are methods used by the operating system to select which ready process should receive the CPU.

What are the main CPU scheduling algorithms?

Common CPU scheduling algorithms include FCFS, SJF, SRTF, Priority Scheduling and Round Robin.

What is FCFS Scheduling?

FCFS or First Come First Served executes processes according to their arrival order and is normally non-preemptive.

What is convoy effect in FCFS?

Convoy effect occurs when short processes wait behind a long process that is already ahead of them in the FCFS queue.

What is SJF Scheduling?

Shortest Job First selects the ready process with the smallest CPU burst. The standard form is non-preemptive.

What is SRTF Scheduling?

Shortest Remaining Time First is the preemptive version of SJF. It selects the ready process with the smallest remaining CPU execution time.

What is the difference between SJF and SRTF?

SJF normally allows the selected process to complete its current CPU burst, while SRTF may preempt it if a process with a shorter remaining time becomes ready.

What is Priority Scheduling?

Priority Scheduling selects processes according to scheduling priority. It can be implemented in preemptive or non-preemptive form.

What is starvation in CPU scheduling?

Starvation occurs when a process waits for an excessively long time because other processes repeatedly receive scheduling preference.

What is aging in CPU scheduling?

Aging gradually improves the priority of a process that has been waiting for a long time and can help reduce starvation.

What is Round Robin Scheduling?

Round Robin is a preemptive scheduling algorithm in which ready processes receive CPU time in repeated turns using a fixed time quantum.

What is time quantum in Round Robin?

Time quantum is the maximum CPU time normally given to a process during one Round Robin turn before it may be preempted and returned to the ready queue.

What happens if Round Robin time quantum is too large?

If the time quantum becomes very large compared with process burst times, Round Robin begins to behave more like FCFS.

What happens if Round Robin time quantum is too small?

A very small time quantum may increase the number of context switches and therefore increase scheduling overhead.

How is turnaround time calculated?

Turnaround Time is calculated as Completion Time minus Arrival Time.

How is waiting time calculated?

In standard CPU scheduling numericals, Waiting Time is calculated as Turnaround Time minus Burst Time.

How is response time calculated?

Response Time is calculated as the time of first CPU allocation minus the process Arrival Time.

Which CPU scheduling algorithm is best?

No single scheduling algorithm is best for every workload. The suitable policy depends on goals such as waiting time, response, fairness, throughput and scheduling overhead.

Conclusion

CPU Scheduling Algorithms in OS become much easier when you stop memorising names and instead understand the question each algorithm asks.

FCFS Scheduling asks who arrived first. SJF Scheduling looks for the shortest available CPU burst. SRTF Scheduling keeps checking the shortest remaining execution time. Priority Scheduling uses process priority, while Round Robin Scheduling gives ready processes repeated turns using a fixed time quantum.

For numerical questions, always build the Gantt chart first. Then calculate Completion Time, Turnaround Time, Waiting Time and Response Time.

Once FCFS, SJF, SRTF, Priority and Round Robin are clear, advanced scheduling topics such as Multilevel Queue and Multilevel Feedback Queue become much easier to understand.

Sahil Dubey