Gyanrush
Start freeOpen Gyanrush
Start freeOpen Gyanrush
  1. LPU MCA Semester 1
  2. CAP366
  3. Unit 4

CAP366 · Unit 4: CPU scheduling

FCFS, SJF and SRTF scheduling

14 practice questions · in the MTE and ETE syllabus

Practise this topicPractise this topic

Key points

  • FCFS: non-preemptive, convoy effect
  • SJF minimises average waiting time
  • SRTF compares remaining time on every arrival
  • Predict bursts by exponential averaging

FCFS is non-preemptive and simple but suffers the convoy effect. SJF picks the shortest next burst and gives the minimum average waiting time; it needs burst estimates, usually by exponential averaging: tau(n+1) = alpha t(n) + (1 - alpha) tau(n). SRTF is preemptive SJF.

Example: P1(0,7), P2(2,4), P3(4,1), P4(5,4).

AlgorithmGantt orderAvg waiting
SJFP1, P3, P2, P44 ms
SRTFP1, P2, P3, P2, P4, P13 ms

Method: draw the Gantt chart, read completion times, then WT = CT - AT - BT.

Exam pitfall: in SRTF compare a newcomer's burst with the running process's remaining time, not its original burst; and long jobs can starve under SJF/SRTF.

Try two questions

Question 1 · Tier 5, Exam level

Processes P1(arrival 0, burst 7), P2(2, 4), P3(4, 1), P4(5, 4). Which pair of average waiting times is correct?

  1. SRTF = 3 ms and non-preemptive SJF = 4 ms
  2. SRTF = 3.5 ms and non-preemptive SJF = 4.5 ms
  3. Both algorithms give 4 ms
  4. SRTF = 4 ms and non-preemptive SJF = 3 ms
Show the answer

A. SJF: P1 0-7, P3 7-8, P2 8-12, P4 12-16 with waits 0, 6, 3, 7 giving 4. SRTF: P1 0-2, P2 2-4, P3 4-5, P2 5-7, P4 7-11, P1 11-16 with waits 9, 1, 0, 2 giving 3. Preemption helps here, so equal values are wrong.

Question 2 · Tier 3, Apply

Non-preemptive SJF on the same four processes gives an average waiting time of:

  1. 8.5 ms
  2. 6.5 ms
  3. 7.75 ms
  4. 9.25 ms
Show the answer

C. Gantt: P1(0-8) P2(8-12) P4(12-17) P3(17-26). Waits: 0, 7, 15, 9; average = 31/4 = 7.75.