CPU Scheduling Algorithms – OS | GATE 2026 CSE

Concept Notes – CPU Scheduling

🔹 CPU Scheduling Basics

• CPU scheduling decides which process executes next from the ready queue.
• Goal: maximize CPU utilization, throughput, and minimize waiting & turnaround time.

Key Metrics:

• Arrival Time (AT): Time when process enters ready queue.
• Burst Time (BT): CPU execution time required.
• Completion Time (CT): Time when process finishes.
• Turnaround Time (TAT) = CT – AT
• Waiting Time (WT) = TAT – BT
• Response Time (RT) = First CPU allocation time – AT

---

🔹 1. First Come First Serve (FCFS)

• Non-preemptive.
• Processes scheduled in the order they arrive (like a queue).
• Easy to implement with FIFO queue.
• Problem: Convoy effect (short jobs wait for long jobs).

---

🔹 2. Shortest Job First (SJF)

• Non-preemptive or Preemptive (SRTF).
• Process with least burst time executes first.
• Advantage: Minimum average waiting time.
• Problem: Requires prior knowledge of burst times.

---

🔹 3. Round Robin (RR)

• Preemptive scheduling.
• Each process gets a time quantum (q).
• After q expires, process goes to back of queue.
• Fair for time-sharing systems.
• Performance depends on size of q.

---

🔹 4. Priority Scheduling

• Each process has a priority value.
• Higher priority process executes first.
• Can be preemptive or non-preemptive.
• Problem: Starvation (low priority never executes).
• Solution: Aging (gradually increase waiting process priority).

---

⚙️ Formulas

Turnaround Time (TAT):

Waiting Time (WT):

Response Time (RT):

(Where FT = first CPU allocation time)

Average Turnaround Time:

Average Waiting Time:

Average Response Time:

---

🔟 10 Most Expected MCQs – GATE 2026 OS (CPU Scheduling)

Q1. FCFS scheduling is equivalent to:
A) Stack
B) Queue
C) Tree
D) Heap

Q2. Which scheduling algorithm may lead to convoy effect?
A) FCFS
B) SJF
C) RR
D) Priority

Q3. Which algorithm gives minimum average waiting time (if burst times are known)?
A) FCFS
B) SJF
C) RR
D) Priority

Q4. In Round Robin with quantum = 2, 4 processes of equal burst time 4 arrive at t=0. How many context switches occur?
A) 4
B) 6
C) 8
D) 10

Q5. In SJF, if two processes have same burst time, tie is broken by:
A) Priority
B) Arrival time
C) Round robin
D) Random selection

Q6. Which scheduling algorithm is most suitable for real-time systems?
A) FCFS
B) SJF
C) Priority
D) Round Robin

Q7. A process with high burst time in RR will:
A) Starve
B) Wait until CPU is free
C) Get multiple small CPU slices
D) Never complete

Q8. Which problem occurs in Priority Scheduling?
A) Convoy effect
B) Starvation
C) Deadlock
D) Thrashing

Q9. Average waiting time is minimum in:
A) FCFS
B) SJF
C) RR
D) Priority

Q10. Aging is a technique used in:
A) FCFS
B) SJF
C) RR
D) Priority Scheduling

---

✅ Answer Key

Q.No	Answer
1	B
2	A
3	B
4	C
5	B
6	C
7	C
8	B
9	B
10	D

---

🧠 Explanations

1. FCFS uses queue (FIFO).
2. FCFS → long process delays others → convoy effect.
3. SJF minimizes average waiting time.
4. Each of 4 processes gets CPU in cycles → total 8 switches.
5. Tie-breaker in SJF = arrival time.
6. Real-time → priority scheduling is preferred.
7. In RR, high burst → process gets many time slices.
8. Priority scheduling suffers from starvation.
9. SJF → provably minimum waiting time.
10. Aging prevents starvation in priority scheduling.

---

🎯 Why This Practice Matters

• CPU scheduling is core OS concept → always asked in GATE (2–4 marks).
• Mastery helps in OS interview rounds (Infosys, TCS, Qualcomm, etc.).
• Real-world: OS kernels, cloud resource management, distributed systems.
• Practicing problems ensures clarity in Gantt chart calculations & time metrics.

---

📲 CTA

Join our GATE 2026 CSE OS Prep Community: @LearnNewThinsHub