What are common examiner traps in CPU and I/O Scheduling?

Ready Queue order on concurrent events: When a process quantum expires at the exact instant a new process arrives, failing to put the newly arrived process ahead of or behind the preempted process according to specified rules. Subtracting Arrival Time: Forgetting to subtract Arrival Time when computing Turnaround Time (confusing Completion Time with TAT when AT > 0). Waiting Time in Preemption: Calculating waiting time merely as first start time minus arrival time, which fails when a process is preempted multiple times. Disk boundary traversal: Confusing SCAN (which travels all the way to track 0 or track Max) with LOOK (which stops at the extreme request), or C-SCAN vs C-LOOK. SSTF tie-breaking: Moving in the wrong direction when two track requests are equidistant from the current head position. Multi-core contention: Assigning a newly freed processor without checking if a higher-priority process is already running on another core or queued with specific processor affinity.

CPU and I/O Scheduling

25 Qs · since 2011 · 42 marks · 1.7 marks/paperMedium yield

Take topic test

CPU and I/O scheduling in GATE CS is predominantly an algorithmic and numerical topic focusing on precise Gantt chart simulation, turnaround/waiting time computation, and comparati… Guide

Type

GATE CSE 2026 Set 1Q64NAT2 marksMediumConsider a CPU that has to execute two types of processes. The first type, Actuators (A), requires a CPU burst of 6 seconds. The second type, Controllers (C), requires a CPU burst of 8 seconds. A new process of type A arrives at time $t = 10, 20, 30, 40,$ and $50$ (in seconds). Similarly, a new process of type C…
GATE CSE 2026 Set 2Q23MCQ1 markEasyWhich one of the following CPU scheduling algorithms cannot be preemptive?
GATE CSE 2025 Set 1Q38MCQ2 marksMediumA computer has two processors, $M_1$ and $M_2$ . Four processes $P_1, P_2, P_3, P_4$ with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows:…
GATE CSE 2025 Set 2Q26MCQ1 markMediumProcesses $P1$ , $P2$ , $P3$ , $P4$ arrive in that order at times $0$ , $1$ , $2$ , and $8$ milliseconds respectively, and have execution times of $10$ , $13$ , $6$ , and $9$ milliseconds respectively. Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context…
GATE CSE 2024 Set 2Q37MCQ2 marksMediumConsider 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…
GATE CSE 2023Q27MSQ1 markEasyWhich one or more of the following CPU scheduling algorithms can potentially cause starvation?
GATE CSE 2022Q42MCQ2 marksHardConsider four processes P, Q, R, and S scheduled on a CPU as per round robin algorithm with a time quantum of 4 units. The processes arrive in the order P, Q, R, S, all at time t = 0. There is exactly one context switch from S to Q, exactly one context switch from R to Q, and exactly two context switches from Q to R.…
GATE CSE 2021 Set 1Q25NAT1 markEasyThree processes arrive at time zero with CPU bursts of 16, 20 and 10 milliseconds. If the scheduler has prior knowledge about the length of the CPU bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is ___________ milliseconds.
GATE CSE 2021 Set 2Q14MSQ1 markMediumWhich of the following statement(s) is/are correct in the context of CPU scheduling?
GATE CSE 2020Q35MCQ2 marksMediumConsider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time. (P, 155), (Q, 85), (R, 110), (S, 30), (T, 115) Assume the head is positioned at cylinder 100. The scheduler follows Shortest Seek Time First scheduling to service…
GATE CSE 2020Q50NAT2 marksMediumDiagramConsider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order $P_1, P_2, P_3, P_4$ . If the time quantum for RR is 4 ms, then the absolute value of the…
GATE CSE 2017 Set 1Q24NAT1 markMediumDiagramConsider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below : If the pre-emptive shortest remaining time first scheduling algorithm is used to schedule the processes, then the average waiting time across all processes is ________ milliseconds.
GATE CSE 2017 Set 2Q51NAT2 marksMediumDiagramConsider the set of processes with arrival time (in milliseconds), CPU burst time (in milliseconds), and priority (0 is the highest priority) shown below. None of the processes have I/O burst time. The average waiting time (in milliseconds) of all the processes using preemptive priority scheduling algorithm is…
GATE CSE 2016 Set 1Q20MCQ1 markEasyConsider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?
GATE CSE 2016 Set 1Q48NAT2 marksMediumConsider a disk queue with requests for I/O to blocks on cylinders 47, 38, 121, 191, 87, 11, 92, 10. The C-LOOK scheduling algorithm is used. The head is initially at cylinder number 63, moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered from 0 to 199. The total head movement (in…
GATE CSE 2016 Set 2Q47NAT2 marksMediumDiagramConsider the following processes, with the arrival time and the length of the CPU burst given in milliseconds. The scheduling algorithm used is preemptive shortest remaining-time first. The average turn around time of these processes is ________ milliseconds.
GATE CSE 2015 Set 1Q30NAT2 marksMediumSuppose the following disk request sequence (track numbers) for a disk with 100 tracks is given: 45, 20, 90, 10, 50, 60, 80, 25, 70. Assume that the initial position of the R/W head is on track 50. The additional distance that will be traversed by the R/W head when the Shortest Seek Time First (SSTF) algorithm is used…
GATE CSE 2015 Set 1Q46NAT2 marksMediumConsider a uniprocessor system executing three tasks $T_1$ , $T_2$ and $T_3$ , each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of 3, 7 and 20 milliseconds, respectively. The priority of each task is the inverse of its period, and the available tasks…
GATE CSE 2015 Set 3Q34MCQ2 marksMediumDiagramFor the processes listed in the following table, which of the following scheduling schemes will give the lowest average turnaround time?
GATE CSE 2014 Set 1Q32NAT2 marksMediumDiagramConsider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds. Using the *shortest remaining time first* scheduling algorithm, the average process turnaround time (in msec) is _________.
GATE CSE 2014 Set 2Q32NAT2 marksMediumDiagramThree 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…
GATE CSE 2014 Set 3Q32NAT2 marksMediumDiagramAn operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds): The average waiting time (in milliseconds) of the processes is ________.
GATE CSE 2013Q10MCQ1 markMediumA scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (the lowest priority). The scheduler re-evaluates the process priorities every $T$ time units and decides the next process to schedule. Which one of the following is TRUE if the processes…
GATE CSE 2012Q31MCQ2 marksMediumDiagramConsider the 3 processes, P1, P2 and P3 shown in the table. The completion order of the 3 processes under the policies FCFS and RR2 (round robin scheduling with CPU quantum of 2 time units) are
GATE CSE 2011Q35MCQ2 marksMediumDiagramConsider the following table of arrival time and burst time for three processes P0, P1 and P2. The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at arrival or completion of processes. What is the average waiting time for the three processes?

Topic guide

What does GATE test in CPU and I/O Scheduling?

CPU and I/O scheduling in GATE CS is predominantly an algorithmic and numerical topic focusing on precise Gantt chart simulation, turnaround/waiting time computation, and comparative metric evaluation. While Preemptive Shortest Remaining Time First (SRTF) and Round Robin (RR) form the core of numerical problems, questions also assess real-time scheduling (Rate Monotonic), multi-processor scheduling, disk I/O head movement algorithms (SCAN, SSTF, C-LOOK), and theoretical properties like starvation and preemption hardware requirements.

Core concepts

Preemptive vs Non-Preemptive scheduling mechanics (SRTF vs SJF, Priority)
Round Robin queue management (tie-breaking at arrival vs quantum expiry)
Gantt chart construction with variable arrival times
Real-time Rate Monotonic Scheduling (RMS) with periodic tasks
Multi-processor / Dual-core task allocation under asymmetric priorities
Interleaved CPU burst and I/O burst execution pipelines
Disk seek scheduling policies (SSTF, SCAN, LOOK, C-SCAN, C-LOOK)
Starvation conditions, aging techniques, and convoy effect
Hardware prerequisites for preemption (programmable interval timer interrupts)

Recurring question patterns

Preemptive SRTF / Priority Metric Calculation
common · NAT · 2 marks · 2025, 2024, 2017, 2016
A table of 3 to 5 processes with arrival times, burst times (and optional priorities) is given. Candidates must construct a precise Gantt chart tracking preemptions at arrival instants and compute average turnaround time or average waiting time.
Round Robin Execution & State/Switch Tracking
common · mixed · 2 marks · 2022, 2020, 2014, 2012
Simulating Round Robin with a given time quantum $q$ , either determining completion orders, evaluating interleaved CPU-I/O bursts, tracing context switch pairs between specific processes, or comparing TAT/WT against SJF.
Comparative Algorithm Evaluation & Optimization
common · mixed · 2 marks · 2024, 2021, 2020, 2016
Comparing metrics (average TAT, average WT, or head movement) across two or more algorithms (e.g., SRTF vs NP-SJF, SSTF vs SCAN, SJF vs RR) or identifying optimal scheduling properties.
Disk I/O Head Scheduling
occasional · NAT · 2 marks · 2016, 2015
Given a sequence of cylinder/track requests, initial head position, and direction, calculate total seek distance or seek distance differences using SSTF, SCAN, LOOK, C-SCAN, or C-LOOK.
Advanced / Non-Standard Scheduling Models
occasional · mixed · 2 marks · 2026, 2025, 2015, 2013
Novel variations such as Rate Monotonic periodic task deadlines, dynamic priority re-evaluation over time, interleaved arrivals of multiple process streams, or multi-processor scheduling with asymmetric priority lists.
Conceptual & MSQ Theoretical Properties
occasional · MSQ · 1 marks · 2026, 2023, 2021, 2013
Testing theoretical definitions and boundary cases: starvation vulnerability, preemption hardware dependencies (timer interrupt), metric definitions (TAT = WT + BT), or algorithm equivalence.

Formulas GATE uses

Turnaround Time (TAT)

\text{TAT} = \text{Completion Time (CT)} - \text{Arrival Time (AT)}

Used in virtually all CPU scheduling Gantt chart calculations to find process turnaround duration.

Waiting Time (WT)

\text{WT} = \text{TAT} - \text{Burst Time (BT)}

Used to find total wait time in ready queue for CPU-bound processes.

Average Metric Calculation

\text{Avg } X = \frac{\sum_{i=1}^{n} X_i}{n}

Used to compute average waiting time or average turnaround time across all $n$ processes.

Rate Monotonic Priority Rule

\text{Priority} \propto \frac{1}{P_i}

Used when periodic real-time tasks are scheduled with priority inversely proportional to task period $P_i$ .

C-LOOK Total Head Movement

\text{Total Seek} = (\text{MaxReq} - \text{StartPos}) + (\text{MaxReq} - \text{MinReq}) + (\text{LastReq} - \text{MinReq})

Used for C-LOOK disk scheduling moving upwards to the maximum request then wrapping to the minimum request.

Examiner traps in CPU and I/O Scheduling

Ready Queue order on concurrent events: When a process quantum expires at the exact instant a new process arrives, failing to put the newly arrived process ahead of or behind the preempted process according to specified rules.
Subtracting Arrival Time: Forgetting to subtract Arrival Time when computing Turnaround Time (confusing Completion Time with TAT when AT > 0).
Waiting Time in Preemption: Calculating waiting time merely as first start time minus arrival time, which fails when a process is preempted multiple times.
Disk boundary traversal: Confusing SCAN (which travels all the way to track 0 or track Max) with LOOK (which stops at the extreme request), or C-SCAN vs C-LOOK.
SSTF tie-breaking: Moving in the wrong direction when two track requests are equidistant from the current head position.
Multi-core contention: Assigning a newly freed processor without checking if a higher-priority process is already running on another core or queued with specific processor affinity.

How questions are asked

Compute average waiting time or turnaround time from a process table (NAT/MCQ)
Identify execution/completion order of processes across two algorithms (MCQ)
Compute total disk head movements or delta between two disk algorithms (NAT)
Trace context switch transitions or determine valid/invalid burst time configurations (MCQ)
Multi-statement correctness on scheduling properties and starvation (MSQ)
Multi-processor / real-time multi-task periodic completion time calculation (NAT/MCQ)

Paper trends

Shift from simple single-algorithm MCQ questions to multi-algorithm comparison questions and precise NAT numerical outputs.
2024, 2020, 2016, 2014, 2011
Introduction of multi-processor asymmetric scheduling rules and complex multi-stream interleaved arrival workloads.
2026, 2025
Use of MSQs to test nuanced conceptual foundations such as starvation edge cases and hardware support requirements for preemption.
2023, 2021

Difficulty notes

Easy: Single-algorithm standard metrics with identical arrival times ( $t=0$ ) or pure definitional MSQ/MCQ questions. Medium: SRTF/RR with 4-5 processes, staggered arrival times, context-switch tracking, or disk head calculations. Hard: Multi-core scheduling with asymmetric priority constraints, multi-loop CPU-I/O pipelines, or inverse reasoning to deduce impossible burst configurations from switch sequences.