Success TrackerSuccess Tracker
Log inSign up

GATE CS 2024 Set 2 — Question 37

MCQ+2 / -0.67MediumFCFS & SJFProcess SchedulingOperating SystemSRTF (Preemptive SJF)Scheduling Numericals

Operating System → Process Scheduling → FCFS & SJF

Last updated

Question

Consider a single processor system with four processes A, B, C, and D, represented as given below, where for each process the first value is its arrival time, and the second value is its CPU burst time.
A (0, 10), B (2, 6), C (4, 3), and D (6, 7).
Which one of the following options gives the average waiting times when preemptive Shortest Remaining Time First (SRTF) and Non-Preemptive Shortest Job First (NP-SJF) CPU scheduling algorithms are applied to the processes?
A.
SRTF = 6, NP-SJF = 7
B.
SRTF = 6, NP-SJF = 7.5
C.
SRTF = 7, NP-SJF = 7.5
D.
SRTF = 7, NP-SJF = 8.5

Correct answer

(B) SRTF = 6, NP-SJF = 7.5

Solution

We calculate the average waiting time for both algorithms.
1. Preemptive Shortest Remaining Time First (SRTF):
Processes: A(0, 10), B(2, 6), C(4, 3), D(6, 7)
  • t=0: A arrives (burst 10). A starts.
  • t=2: B arrives (burst 6). A has run for 2 units, remaining 8. B(6) < A(8), so preempt A. B starts.
  • t=4: C arrives (burst 3). B has run for 2 units, remaining 4. C(3) < B(4), so preempt B. C starts.
  • t=6: D arrives (burst 7). C has run for 2 units, remaining 1. C(1) < D(7), so continue C.
  • t=7: C finishes. Remaining: A(8), B(4), D(7). Shortest is B(4). B resumes.
  • t=11: B finishes. Remaining: A(8), D(7). Shortest is D(7). D starts.
  • t=18: D finishes. Remaining: A(8). A resumes.
  • t=26: A finishes.
Completion Times (CT):
  • C: 7
  • B: 11
  • D: 18
  • A: 26
Turnaround Time (TAT = CT - Arrival):
  • A: 26−0=2626 - 0 = 26
  • B: 11−2=911 - 2 = 9
  • C: 7−4=37 - 4 = 3
  • D: 18−6=1218 - 6 = 12
Waiting Time (WT = TAT - Burst):
  • A: 26−10=1626 - 10 = 16
  • B: 9−6=39 - 6 = 3
  • C: 3−3=03 - 3 = 0
  • D: 12−7=512 - 7 = 5
Average WT (SRTF): (16+3+0+5)/4=24/4=6(16 + 3 + 0 + 5) / 4 = 24 / 4 = 62. Non-Preemptive Shortest Job First (NP-SJF):
  • t=0: A arrives. Only A is available. A starts.
  • t=10: A finishes. Available processes: B(2, 6), C(4, 3), D(6, 7). Shortest is C(3). C starts.
  • t=13: C finishes. Available: B(2, 6), D(6, 7). Shortest is B(6). B starts.
  • t=19: B finishes. Available: D(6, 7). D starts.
  • t=26: D finishes.
Completion Times (CT):
  • A: 10
  • C: 13
  • B: 19
  • D: 26
Turnaround Time (TAT = CT - Arrival):
  • A: 10−0=1010 - 0 = 10
  • B: 19−2=1719 - 2 = 17
  • C: 13−4=913 - 4 = 9
  • D: 26−6=2026 - 6 = 20
Waiting Time (WT = TAT - Burst):
  • A: 10−10=010 - 10 = 0
  • B: 17−6=1117 - 6 = 11
  • C: 9−3=69 - 3 = 6
  • D: 20−7=1320 - 7 = 13
Average WT (NP-SJF): (0+11+6+13)/4=30/4=7.5(0 + 11 + 6 + 13) / 4 = 30 / 4 = 7.5Result: SRTF = 6, NP-SJF = 7.5.

More questions on Process Scheduling

2024 Set 1 Q24Which of the following statements about threads is/are TRUE?2024 Set 2 Q24Which of the following tasks is/are the responsibility/responsibilities of the memory management…2024 Set 2 Q25Consider a process P running on a CPU. Which one or more of the following events will always…2024 Set 1 Q25Which of the following process state transitions is/are NOT possible?2024 Set 1 Q40Consider the following two threads T1 and T2 that update two shared variables a and b. Assume that…

Practice GATE CS PYQs with adaptive difficulty

Timed practice, skill tracking, and AI explanations — free to start.

Start practicing free