GATE CSE CPU and I/O Scheduling PYQs
CPU and I/O scheduling in GATE CS is predominantly an algorithmic and numerical topic focusing on precise Gantt chart simulation, turnaround/waiting time comput… Read the guide
- Questions
- 25
- Asked
- since 2011
- Total marks
- 42
- Marks / paper
- 1.7
25 GATE CSE CPU and I/O Scheduling PYQs with solutions, from Operating Systems. Browse all GATE CSE PYQs.
Questions
Every official paper that asked this topic, newest first.
- GATE CSE 2026 Set 1 · Q64Consider 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 and (in seconds). Similarly, a new process of type C…NAT2 marksMediumSolve
- GATE CSE 2026 Set 2 · Q23Which one of the following CPU scheduling algorithms cannot be preemptive?MCQ1 markEasySolve
- GATE CSE 2025 Set 1 · Q38A computer has two processors, and . Four processes 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:…MCQ2 marksMediumSolve
- GATE CSE 2025 Set 2 · Q26Processes , , , arrive in that order at times , , , and milliseconds respectively, and have execution times of , , , and milliseconds respectively. Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context…MCQ1 markMediumSolve
- GATE CSE 2024 Set 2 · Q37Consider 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…MCQ2 marksMediumSolve
- GATE CSE 2023 · Q27Which one or more of the following CPU scheduling algorithms can potentially cause starvation?MSQ1 markEasySolve
- GATE CSE 2022 · Q42Consider 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.…MCQ2 marksHardSolve
- GATE CSE 2021 Set 1 · Q25Three 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.NAT1 markEasySolve
- GATE CSE 2021 Set 2 · Q14Which of the following statement(s) is/are correct in the context of CPU scheduling?MSQ1 markMediumSolve
- GATE CSE 2020 · Q35Consider 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…MCQ2 marksMediumSolve
- GATE CSE 2020 · Q50Consider 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 . If the time quantum for RR is 4 ms, then the absolute value of the…NAT2 marksMediumDiagramSolve
- GATE CSE 2017 Set 1 · Q24Consider 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.NAT1 markMediumDiagramSolve
- GATE CSE 2017 Set 2 · Q51Consider 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…NAT2 marksMediumDiagramSolve
- GATE CSE 2016 Set 1 · Q20Consider 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?MCQ1 markEasySolve
- GATE CSE 2016 Set 1 · Q48Consider 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…NAT2 marksMediumSolve
- GATE CSE 2016 Set 2 · Q47Consider 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.NAT2 marksMediumDiagramSolve
- GATE CSE 2015 Set 1 · Q30Suppose 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…NAT2 marksMediumSolve
- GATE CSE 2015 Set 1 · Q46Consider a uniprocessor system executing three tasks , and , 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…NAT2 marksMediumSolve
- GATE CSE 2015 Set 3 · Q34For the processes listed in the following table, which of the following scheduling schemes will give the lowest average turnaround time?MCQ2 marksMediumDiagramSolve
- GATE CSE 2014 Set 1 · Q32Consider 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 _________.NAT2 marksMediumDiagramSolve
- GATE CSE 2014 Set 2 · Q32Three 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 CPU milliseconds and then initiates a single I/O operation that lasts for milliseconds. It is assumed that the computer where the processes execute…NAT2 marksMediumDiagramSolve
- GATE CSE 2014 Set 3 · Q32An 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 ________.NAT2 marksMediumDiagramSolve
- GATE CSE 2013 · Q10A 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 time units and decides the next process to schedule. Which one of the following is TRUE if the processes…MCQ1 markMediumSolve
- GATE CSE 2012 · Q31Consider 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) areMCQ2 marksMediumDiagramSolve
- GATE CSE 2011 · Q35Consider 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?MCQ2 marksMediumDiagramSolve
What GATE tests in CPU and I/O Scheduling
Concepts, patterns, formulas and traps distilled from past papers.
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
CommonNAT2 marks2025, 2024, 2017, 2016A 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
Commonmixed2 marks2022, 2020, 2014, 2012Simulating Round Robin with a given time quantum , 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
Commonmixed2 marks2024, 2021, 2020, 2016Comparing 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
OccasionalNAT2 marks2016, 2015Given 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
Occasionalmixed2 marks2026, 2025, 2015, 2013Novel 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
OccasionalMSQ1 marks2026, 2023, 2021, 2013Testing 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)
Used in virtually all CPU scheduling Gantt chart calculations to find process turnaround duration.
Waiting Time (WT)
Used to find total wait time in ready queue for CPU-bound processes.
Average Metric Calculation
Used to compute average waiting time or average turnaround time across all processes.
Rate Monotonic Priority Rule
Used when periodic real-time tasks are scheduled with priority inversely proportional to task period .
C-LOOK Total Head Movement
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 () 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.