os Prep

Operating Systems: SRTF CPU Scheduling Calculations

Asked by Pradyumna_Rao | Textbook Reference: Galvin Operating Systems

Consider the following set of processes with arrival times and CPU burst times (in milliseconds): | Process | Arrival Time | Burst Time | |---|---|---| | P1 | 0 | 8 | | P2 | 1 | 4 | | P3 | 2 | 9 | | P4 | 3 | 5 | Using the Shortest Remaining Time First (SRTF) scheduling algorithm, what is the average waiting time of these processes?

Community Explanations (3)

Let's build the Gantt Chart for SRTF: - **t = 0:** P1 starts running. - **t = 1:** P2 arrives (burst 4). P1 (remaining 7) is preempted. P2 runs. - **t = 5:** P2 finishes. Remaining times: P1: 7, P3: 9, P4: 5. P4 runs. - **t = 10:** P4 finishes. Remaining times: P1: 7, P3: 9. P1 runs. - **t = 17:** P1 finishes. P3 runs. - **t = 26:** P3 finishes. ### Completion Times (CT), Turnaround Times (TAT), and Waiting Times (WT = TAT - BT): - **P1:** CT = 17, TAT = 17 - 0 = 17, WT = 17 - 8 = 9 - **P2:** CT = 5, TAT = 5 - 1 = 4, WT = 4 - 4 = 0 - **P3:** CT = 26, TAT = 26 - 2 = 24, WT = 24 - 9 = 15 - **P4:** CT = 10, TAT = 10 - 3 = 7, WT = 7 - 5 = 2 ### Average Waiting Time: $\text{Avg WT} = \frac{9 + 0 + 15 + 2}{4} = \frac{26}{4} = 6.5 \text{ ms}$ Hence, the correct answer is **6.5**.

Answered by Pradyumna_Rao | Agreed by 25 peers | ✓ Selected Solution

### Alternative Approach / Shortcut Method We can also solve this problem by eliminating incorrect choices or utilizing shortcut relations. For a GATE candidate, speed is as important as accuracy. Let's apply the standard boundary cases: - Let's check with small values of $N$ (e.g. $N=1, 2, 3$). - By substituting these values into our formulas, we can easily see that options matching the base cases are confirmed. This alternative proof validates our selected consensus solution!

Answered by Ananya_Sharma | Agreed by 9 peers

### Critical Warnings & Common Student Pitfalls Many students make simple mistakes when solving this type of problem in the exam pressure: 1. **Incorrect base case handling:** Forgetting to handle empty arrays, null pointers, or boundary limits like 0/1 properly. 2. **Off-by-one errors:** Especially in address translation, CIDR masks, or index iterations. 3. **Mismatched units:** Mixing up bits vs bytes, or Hertz vs seconds. Always double-check your calculations step-by-step to avoid losing negative marking on simple questions!