GATE CS 2014 Set 2 Q.42 (CS Q.32): CPU Scheduling

Three processes A, B and C each execute a loop of 100 iterations. In each iteration of the loop, a process performs a single computation that requires $t_c$ CPU milliseconds and then initiates a single I/O operation that lasts for $t_{io}$ milliseconds. It is assumed that the computer where the processes execute has sufficient number of I/O devices and the OS of the computer assigns different I/O devices to each process. Also, the scheduling overhead of the OS is negligible. The processes have the following characteristics:

Process id	$t_c$	$t_{io}$
A	100 ms	500 ms
B	350 ms	500 ms
C	200 ms	500 ms

The processes A, B, and C are started at times 0, 5 and 10 milliseconds respectively, in a pure time sharing system (round robin scheduling) that uses a time slice of 50 milliseconds. The time in milliseconds at which process C would complete its first I/O operation is _____.

Your answer

Official answer and solution

Official answer: 1000
From: Official GATE 2014 answer key

Solution

Simulate Round Robin scheduling with 50 ms time slice to find the exact CPU completion time of process C before its first I/O.

Process Attributes:
- A: arrives at $t = 0$ , CPU burst $t_c = 100$ ms, I/O burst $t_{io} = 500$ ms.
- B: arrives at $t = 5$ , CPU burst $t_c = 350$ ms, I/O burst $t_{io} = 500$ ms.
- C: arrives at $t = 10$ , CPU burst $t_c = 200$ ms, I/O burst $t_{io} = 500$ ms.
- Quantum $q = 50$ ms.
Ready Queue Simulation (First CPU Burst):
- $t = 0$ to $50$ : A executes 50 ms (50 ms remaining). At $t = 5$ , B arrives; at $t = 10$ , C arrives. At $t = 50$ , A is preempted and enqueued. Queue: [B, C, A].
- $t = 50$ to $100$ : B executes 50 ms (300 ms remaining), enqueued. Queue: [C, A, B].
- $t = 100$ to $150$ : C executes 50 ms (150 ms remaining), enqueued. Queue: [A, B, C].
- $t = 150$ to $200$ : A executes its remaining 50 ms. A completes its first CPU burst at $t = 200$ ms and starts its I/O. Queue: [B, C].
- $t = 200$ to $250$ : B executes 50 ms (250 ms remaining), enqueued. Queue: [C, B].
- $t = 250$ to $300$ : C executes 50 ms (100 ms remaining), enqueued. Queue: [B, C].
- $t = 300$ to $350$ : B executes 50 ms (200 ms remaining), enqueued. Queue: [C, B].
- $t = 350$ to $400$ : C executes 50 ms (50 ms remaining), enqueued. Queue: [B, C].
- $t = 400$ to $450$ : B executes 50 ms (150 ms remaining), enqueued. Queue: [C, B].
- $t = 450$ to $500$ : C executes its final 50 ms (0 ms remaining). C finishes its first CPU burst at $t = 500$ ms!
I/O Completion of C:
- C immediately starts its first I/O operation of duration $t_{io} = 500$ ms at $t = 500$ ms.
- Dedicated I/O devices are available without interference.
- Time of I/O completion for C: $t_{\text{complete}} = 500 + 500 = 1000 \text{ ms}.$

Thus, process C completes its first I/O operation at $1000$ ms.

Final answer

1000

Common trap

Omitting the 500 ms I/O duration and reporting 500 ms (when CPU burst finishes) instead of when I/O completes.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 2
Question: 42 of 65, printed as CS Q.32
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source