Self-checkedTier 1 14 min reados.cpu-scheduling

CPU scheduling: criteria, FCFS, SJF and SRTF

How the OS chooses which ready process runs: the scheduling criteria and their formulas, preemptive and non-preemptive scheduling, the dispatcher, and first come first served, shortest job first, shortest remaining time first and highest response ratio next, with Gantt charts and the average waiting time.

Why it exists

When several processes are ready and there is one CPU, the operating system must decide who runs next. The rule it uses is the scheduling algorithm, and it determines how fast processes finish, how long they wait and how responsive the system feels. GATE asks you to draw the schedule (a Gantt chart) for a given set of processes and algorithm and compute the average turnaround, waiting or response time; and to compare algorithms: which is optimal, which starves, which preempts. This page covers the basic algorithms; priority and round robin are on the next one.

Prerequisites

Process states, fork and exec

You need the ready queue and the process states from process states, and the cost of switching from the context switch.

Precise definitions

CPU burst and I/O burst. A process alternates between a CPU burst (computing) and an I/O burst (waiting for I/O). The scheduler is concerned with the CPU bursts: burst time in the exercises is the length of the (next) CPU burst. I/O-bound processes have many short CPU bursts; CPU-bound ones have few long bursts.

CPU (short-term) scheduler and dispatcher. The scheduler selects a process from the ready queue; the dispatcher gives it the CPU (context switch, switch to user mode, jump to the saved PC). The dispatch latency is the time the dispatcher takes.

When a decision is made. CPU scheduling decisions can take place when a process (1) goes from running to waiting (an I/O request), (2) goes from running to ready (an interrupt, such as the timer), (3) goes from waiting to ready (an I/O completion), (4) terminates. If scheduling happens only in cases 1 and 4 the scheduling is non-preemptive (cooperative): once the CPU is given to a process, it keeps it until it terminates or waits. If cases 2 and 3 can also trigger a decision the scheduling is preemptive: the OS can take the CPU away from a running process. Preemption needs care with data shared between processes (a process may be preempted in the middle of updating it).

Scheduling criteria. For $n$ processes with arrival time $AT$ , burst time $BT$ , completion time $CT$ and the time $FT$ it first receives the CPU:

Criterion	Definition	Aim
CPU utilization	fraction of time the CPU is busy	maximize
Throughput	processes completed per unit time	maximize
Turnaround time	$TAT = CT - AT$	minimize
Waiting time	$WT = TAT - BT$ (total time spent in the ready queue)	minimize
Response time	$RT = FT - AT$ (time from arrival until the first response, the first time on the CPU)	minimize

Averages over all processes are what questions usually ask. Also $\overline{TAT} = \overline{WT} + \overline{BT}$ . For a process that does I/O, the waiting time counts only time in the ready queue, not time blocked for I/O.

Gantt chart. A bar showing which process runs in each time interval; the completion times are read off it. Gaps are idle times.

First come, first served (FCFS). The CPU goes to the process that arrived first; non-preemptive; the ready queue is a FIFO queue. Simple, but the average waiting time can be long, and a long process delays the short ones behind it: the convoy effect.

Shortest job first (SJF). The CPU goes to the ready process with the smallest next CPU burst; ties broken by FCFS. The non-preemptive version lets the chosen process run to the end of its burst. SJF is optimal: it gives the minimum average waiting time among non-preemptive schedules of a given set of processes (all ready at once). Problems: the next burst length is not known in advance (it is predicted), and long processes can starve if short ones keep arriving.

Predicting the next burst. By exponential averaging of the measured bursts: $\tau_{n+1} = \alpha\,t_n + (1 - \alpha)\,\tau_n$ , where $t_n$ is the length of the $n$ -th burst, $\tau_n$ the prediction for it and $0 \le \alpha \le 1$ . With $\alpha = 0$ the history is ignored (recent bursts do not count) and with $\alpha = 1$ only the last burst counts.

Shortest remaining time first (SRTF). The preemptive form of SJF: whenever a new process arrives, compare the new process's burst with the remaining time of the running process and preempt if the newcomer is shorter. SRTF gives the minimum average waiting time among all schedules (preemption allowed) when switching costs nothing. It needs more context switches and can also starve long processes.

Highest response ratio next (HRRN). Non-preemptive: when the CPU is free choose the ready process with the largest response ratio $R = \frac{W + BT}{BT},$ where $W$ is the time waited so far. Short jobs have a high ratio, but a long job's ratio grows as it waits, so it is not starved.

Conventions to state in an answer. Context-switch time is zero; if two processes tie, the earlier arrival (or the lower process number) goes first; a running process is not preempted by an equal one.

How it works

All the animations use the same five processes, so the schedules can be compared: P1 arrives at 0 with burst 6, P2 at 1 with 3, P3 at 2 with 8, P4 at 3 with 2, P5 at 4 with 4. Step through each: the Gantt chart is built up, the ready queue shows who is waiting, and the table fills in turnaround, waiting and response times as processes finish. The same set gives average waiting 8.2 under FCFS, 6.0 under SJF and 5.0 under SRTF.

FCFS runs the processes in the order of arrival; the short P4 waits 14 time units behind the long P3.

FCFS: start

Schedule simulated, not typed

First come, first served (non-preemptive). Context-switch time is ignored.

running

ready queue (front first)

empty

process	arrival	burst	left	status
P1	0	6	6	running
P2	1	3	3	not arrived
P3	2	8	8	not arrived
P4	3	2	2	not arrived
P5	4	4	4	not arrived

average turnaround

average waiting

average response

Step 0

Five processes arrive at times 0, 1, 2, 3 and 4 with bursts 6, 3, 8, 2 and 4. FCFS runs them in arrival order and never preempts: the short processes P2 and P4 wait behind the long P3 (the CONVOY effect).

0 / 10

computed by script: tick-by-tick simulation of the algorithm. python3 scripts/gen-os-sched-traces.py

Non-preemptive SJF: when P1 finishes at 6, the shortest ready burst (P4, 2) goes first, then P2, then P5, and P3 (the longest) runs last.

SJF (non-preemptive): start

Schedule simulated, not typed

Shortest job first (non-preemptive). Context-switch time is ignored.

running

ready queue (front first)

empty

process	arrival	burst	left	status
P1	0	6	6	running
P2	1	3	3	not arrived
P3	2	8	8	not arrived
P4	3	2	2	not arrived
P5	4	4	4	not arrived

average turnaround

average waiting

average response

Step 0

The same five processes. Whenever the CPU becomes free, shortest job first picks the READY process with the smallest burst. Once started a process runs to completion, even if a shorter one arrives.

0 / 10

computed by script: tick-by-tick simulation of the algorithm. python3 scripts/gen-os-sched-traces.py

SRTF preempts: P2 arrives at 1 needing 3 against P1's 5 remaining, so P1 is preempted and resumes only at 10. Look at the first response column: P1's response time is 0 even though it waited 9 in all.

SRTF (preemptive SJF): start

Schedule simulated, not typed

Shortest remaining time first (preemptive). Context-switch time is ignored.

running

ready queue (front first)

empty

process	arrival	burst	left	status
P1	0	6	6	running
P2	1	3	3	not arrived
P3	2	8	8	not arrived
P4	3	2	2	not arrived
P5	4	4	4	not arrived

average turnaround

average waiting

average response

Step 0

The same five processes. SRTF is the preemptive form of SJF: at every arrival it compares the new process's burst with the REMAINING time of the running one and preempts if the newcomer is shorter.

0 / 9

computed by script: tick-by-tick simulation of the algorithm. python3 scripts/gen-os-sched-traces.py

Worked examples

EX 1FCFS by hand

Easy

For FCFS the order is P1, P2, P3, P4, P5 with bursts 6, 3, 8, 2, 4. The Gantt chart is P1 (0 to 6), P2 (6 to 9), P3 (9 to 17), P4 (17 to 19), P5 (19 to 23). Completion times: 6, 9, 17, 19, 23. Turnaround = completion − arrival: 6, 8, 15, 16, 19, average $64/5 = 12.8$ . Waiting = turnaround − burst: 0, 5, 7, 14, 15, average $41/5 = 8.2$ . For FCFS the response time equals the waiting time (the process runs without interruption once it starts).

EX 2SJF and SRTF against FCFS, computed by a program

Medium

A different implementation (a C program) computes the three schedules for the same processes.

#include <stdio.h>
 
#define N 5
 
/* processes: arrival and burst */
static const int arrival[N] = {0, 1, 2, 3, 4};
static const int burst[N] = {6, 3, 8, 2, 4};
 
enum algo { FCFS, SJF, SRTF };
 
static void run(enum algo a, const char *name) {
    int rem[N], finish[N] = {0}, first[N], started[N] = {0};
    for (int i = 0; i < N; i++) rem[i] = burst[i];
    int done = 0, cur = -1;
    for (int t = 0; done < N; t++) {
        /* a non-preemptive algorithm only chooses when the CPU is free; SRTF chooses at every time unit */
        if (cur < 0 || a == SRTF) {
            int best = cur;
            for (int i = 0; i < N; i++) {
                if (arrival[i] > t || rem[i] == 0 || i == cur) continue;
                int better = best < 0;
                if (!better) {
                    int ki, kb;
                    if (a == FCFS) { ki = arrival[i]; kb = arrival[best]; }
                    else if (a == SJF) { ki = burst[i]; kb = burst[best]; }
                    else { ki = rem[i]; kb = rem[best]; }
                    better = ki < kb || (ki == kb && arrival[i] < arrival[best] && best != cur);
                }
                if (better) best = i;
            }
            cur = best;
        }
        if (cur < 0) continue;                       /* idle */
        if (!started[cur]) { started[cur] = 1; first[cur] = t; }
        if (--rem[cur] == 0) { finish[cur] = t + 1; done++; cur = -1; }
    }
    double ta = 0, w = 0, r = 0;
    for (int i = 0; i < N; i++) {
        ta += finish[i] - arrival[i];
        w += finish[i] - arrival[i] - burst[i];
        r += first[i] - arrival[i];
    }
    printf("%-5s average turnaround %5.2f, waiting %5.2f, response %5.2f\n", name, ta / N, w / N, r / N);
}
 
int main(void) {
    run(FCFS, "FCFS");
    run(SJF, "SJF");
    run(SRTF, "SRTF");
    return 0;
}

FCFS  average turnaround 12.80, waiting  8.20, response  8.20
SJF   average turnaround 10.60, waiting  6.00, response  6.00
SRTF  average turnaround  9.60, waiting  5.00, response  3.20

Reading it. SJF cuts the average waiting time from 8.2 to 6.0 by letting the short processes go first, and SRTF to 5.0 by also preempting. SRTF's average response time (3.2) is the best of the three because short processes start the moment they arrive. The price: the longest process, P3, waits 7 under FCFS but 13 under SJF and SRTF, and would wait still longer if more short processes arrived. Check by hand that turnaround $=$ waiting $+$ average burst (4.6): $8.2 + 4.6 = 12.8$ .

EX 3The convoy effect

Medium

Three processes arrive together with bursts 20, 2 and 3. In the order P1, P2, P3 (FCFS) the waits are 0, 20, 22: average $42/3 = 14$ . If the short processes go first (P2, P3, P1) the waits are 0, 2, 5: average $7/3 \approx 2.33$ . The same work, six times the waiting, only because the long process went first and the short ones queued behind it. This is why SJF minimizes the average: putting short jobs first lets the fewest others wait for the longest time. For $n$ processes arriving together the average waiting time of an order is $\frac{1}{n}\sum_k (\text{sum of the bursts before the } k\text{-th})$ , smallest when the bursts are in increasing order.

EX 4Predicting the next CPU burst

Medium

With $\alpha = 1/2$ and the first prediction $\tau_0 = 10$ , the measured bursts are 6, 4, 6, 4.

#include <stdio.h>
 
int main(void) {
    /* next CPU burst predicted as tau(n+1) = alpha * t(n) + (1 - alpha) * tau(n) */
    double alpha = 0.5, tau = 10;
    int bursts[4] = {6, 4, 6, 4};
    printf("prediction before burst 1: %.1f\n", tau);
    for (int n = 0; n < 4; n++) {
        tau = alpha * bursts[n] + (1 - alpha) * tau;
        printf("after a burst of %d: next prediction %.1f\n", bursts[n], tau);
    }
    return 0;
}

prediction before burst 1: 10.0
after a burst of 6: next prediction 8.0
after a burst of 4: next prediction 6.0
after a burst of 6: next prediction 6.0
after a burst of 4: next prediction 5.0

Reading it. $\tau_1 = 0.5 \times 6 + 0.5 \times 10 = 8$ , $\tau_2 = 0.5 \times 4 + 0.5 \times 8 = 6$ , and so on. The prediction moves towards the actual bursts; expanding the formula, every older burst is weighted by a power of $(1 - \alpha)$ , which is why it is called an exponential average. A larger $\alpha$ makes the prediction follow recent behaviour faster.

EX 5HRRN, and counting preemptions

GATE level

HRRN on the same processes. At time 6, after P1: P2 has waited 5 (ratio $(5 + 3)/3 = 2.67$ ), P3 waited 4 ( $(4 + 8)/8 = 1.5$ ), P4 waited 3 ( $(3 + 2)/2 = 2.5$ ), P5 waited 2 ( $(2 + 4)/4 = 1.5$ ): P2 runs (6 to 9). At 9: P3 $(7 + 8)/8 = 1.88$ , P4 $(6 + 2)/2 = 4$ , P5 $(5 + 4)/4 = 2.25$ : P4 runs (9 to 11). At 11: P3 $(9 + 8)/8 = 2.13$ , P5 $(7 + 4)/4 = 2.75$ : P5 (11 to 15), then P3 (15 to 23). Waiting times 0, 5, 13, 6, 7: average $31/5 = 6.2$ , between SJF (6.0) and FCFS (8.2). Counting preemptions in the SRTF chart: the running process changes five times (P1 to P2, P2 to P4, P4 to P5, P5 to P1, P1 to P3). Only the first, at time 1, is a preemption (P2 arrives with a shorter burst than P1's remaining time); in the other four the running process had just finished. A question that asks for context switches must say whether the start and the end of the schedule count.

Cheat box

$TAT = CT - AT$ . $WT = TAT - BT$ . $RT = \text{first run} - AT$ . $\overline{TAT} = \overline{WT} + \overline{BT}$ .
Non-preemptive: runs until it ends or blocks. Preemptive: the OS can take the CPU away.
FCFS: non-preemptive, convoy effect, response $=$ waiting.
SJF (non-preemptive): minimum average waiting among non-preemptive schedules; needs burst prediction; starves long jobs.
SRTF (preemptive SJF): minimum average waiting among all schedules; more switches.
HRRN: $R = (W + BT)/BT$ ; non-preemptive; no starvation.
Prediction: $\tau_{n+1} = \alpha\,t_n + (1 - \alpha)\,\tau_n$ .
Draw the Gantt chart; read completion times; compute. State your tie-break and the zero-cost switch assumptions.

Traps and GATE patterns

Connections

Builds on

Process states, fork and exec

Unlocks

Process states, fork and execuses Priority and round robin schedulingPrerequisite of Priority and round robin schedulinguses Disk schedulinganalogous to Producer-consumer, readers-writers, dining philosophersuses Memory management: partitioning and fragmentationuses Thrashing and the working setuses Multilevel queues and real-time schedulinguses Queue (abstract data type)uses

Across subjects

Performance: CPI, MIPS and Amdahl's lawanalogous-to

Within this subject

Process states, fork and execuses Context switchinguses Priority and round robin schedulinguses

Journeys that pass through here

A C program, from source to exit · Interrupts and scheduling

The scheduler chooses among the ready processes of process states, and each preemption costs a context switch. The time-slicing and priority policies are on priority and round robin. The idea of "serve the common case better" has the same flavour as Amdahl's law: the total gain depends on what share of the time is affected.

PYQs

26 previous year questions from your book. I re-solved each one myself (19 by running or simulating, 7 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2026 · MCQQ1 · page 295 of the book

Which one of the following CPU scheduling
algorithms cannot be preemptive?

(a)Shortest Remaining Time First (SRTF) Scheduling
(b)First Come First Serve (FCFS) Scheduling
(c)Round Robin Scheduling
(d)Priority Scheduling

GATE 2026 · NATQ2 · page 295 of the book

Consider 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 seconds. Similarly, a new process of
type C arrives at time t = 11, 22, 33, 44, and 55 seconds.

The CPU scheduling policy is First Come First
Serve (FCFS). The first process of type A starts
running at t = 10 seconds.

The average waiting time (in seconds) for the 10
processes is ______. (rounded off to one decimal place).

GATE 2025 · MCQQ3 · page 295 of the book

Processes 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 switching times.
Which ONE of the following correctly gives the
average turnaround time of the four processes in
milliseconds?

(a)22
(b)15
(c)37
(d)

GATE 2025 · MCQQ4 · page 295 of the book

A computer has two processors, M1 and M2. Four
processes P1, P2, P3, P4 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:
• M1 uses priority of execution for the processes
as, P1 > P3 > P2 > P4, i.e., P1 and P4 have
highest and lowest priorities, respectively.
• M2 uses priority of execution for the processes
as, P2 > P3 > P4 > P1, i.e., P2 and P1 have
highest and lowest priorities, respectively.

A process Pi is scheduled to a processor Mk, if the
processor is free and no other process Pj is waiting
with higher priority. At any given point of time, a
process can be allocated to any one of the free
processors without violating the execution priority
rules. Ignore the context switch time. What will be the
average
waiting
time
of
the
processes
in
milliseconds?

(a)9.00
(b)8.75
(c)6.50
(d)7.50

GATE 2024 · MCQQ9 · page 296 of the book

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

GATE 2023 · MSQQ13 · page 297 of the book

Which one or more of the following CPU
scheduling algorithms can potentially cause
starvation?

(a)First-in First-Out
(b)Round Robin
(c)Priority Scheduling
(d)Shortest Job First.

GATE 2021 · NATQ16 · page 297 of the book

There are 6 jobs with distinct difficulty levels, and 3
computers with distinct processing speeds. Each job
is assigned to a computer such that:

- The fastest computer gets the toughest job and the
slowest computer gets the easiest job.

- Every computer gets at least one job

The number of ways in which this can be done is
_________

GATE 2021 · MSQQ17 · page 297 of the book

Which of the following statement(s) is/are correct in
the context of CPU scheduling?

(a)Turnaround time includes waiting time.
(b)Round-robin policy can be used even when the CPU time required by each of the processes is not known apriori.
(c)Implementing pre-emptive scheduling needs hardware support.
(d)The goal is to only maximize CPU utilization and minimize throughput. OPERATING SYSTEMS

GATE 2021 · NATQ19 · page 298 of the book

Three 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 processes in a non-preemptive
scheduler
(rounded
to
nearest
integer)
is
_________milliseconds.

GATE 2020 · NAT · 2 marksQ20 · page 298 of the book

Consider 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 P1, P2, P3, P4.

Processes
P1
P2
P3
P4
Burst time (in ms)
8
7
2
4

If the time quantum for RR is 4 ms, then the

absolute value of the difference between the

average turnaround times (in ms) of SJF and RR

(round off to 2 decimal places) is ______

GATE 2019 · NAT · 2 marksQ22 · page 298 of the book

Consider the following four processes with arrival
times (in milliseconds) and their length of CPU bursts
(in milliseconds) as shown below:

Process
P1 P2 P3 P4
Arrival time
0
1
3
4
CPU burst time
3
1
3
Z

OPERATING SYSTEMS
These processes are run on a single processor
using preemptive Shortest Remaining Time First
scheduling algorithm. If the average waiting time
of the processes is 1 millisecond, then the value of
Z is ______

GATE 2017 · Set 1 · NAT · 1 markQ24 · page 299 of the book

Consider the following CPU processes with arrival
times (in milliseconds) and length of CPU bursts
(in milliseconds) as given below:

Process: P1, P2, P3, P4

Arrival Time: 0, 3, 5, 6

Burst Time: 7, 3, 5, 2
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 2016 · MCQQ28 · page 299 of the book

Consider 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?

(a)Shortest remaining time first
(b)Round-robin with time quantum less than the shortest CPU burst
(c)Uniform random
(d)Highest priority first with priority proportional to CPU burst length OPERATING SYSTEMS

GATE 2016 · NATQ29 · page 300 of the book

Consider the following processes, with the arrival
time and the length of the CPU burst given in
milliseconds. The scheduling algorithm used is the
pre-emptive shortest remaining-time first.

Process
Arrival Time
Burst Time
P1
0
10
P2
3
6
P3
7
1
P4
8
3

The average turn-around time of these processes is
_________ milliseconds

GATE 2015 · MCQQ30 · page 300 of the book

The maximum number of processes that can be in
Ready state for a computer system with n CPUs is

(a)n
(b)n2
(c)2N
(d)Independent of n

GATE 2015 · MCQQ31 · page 300 of the book

Which of the following is FALSE about SJF
(Shortest Job First Scheduling)?
S1: It causes minimum average waiting time

S2: It can cause starvation

(a)Only S1
(b)Only S2
(c)Both S1 and S2
(d)Neither S1 or S2

year not read yetQ32 · page 300 of the book

For the processes listed in the following table, which
of the following scheduling schemes will give the
lowest average turnaround time?

Proces
Arrival Time
Processing
Time
A
0
3
B
1
6
C
4
4
D
6
2

(a)First Come First Serve
(b)Non-pre-emptive Shortest Job First
(c)Shortest Remaining Time First
(d)Round Robin with Quantum value two

GATE 2014 · NATQ36 · page 301 of the book

An operating system uses the 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):
Process
Arrival Time
Burst Time
P1
0
12
P2
2
4
P3
3
6
P4
8
5

The average waiting time (in milliseconds) of the
processes is ______.

GATE 2014 · NATQ37 · page 301 of the book

Consider the following set of processes that need to
be scheduled on a single CPU. All the times are given
in milliseconds.

Process
Name
Arrival Time
Execution
Time
A
0
6
B
3
2
C
5
4
D
7
6
E
10
3

Using the shortest remaining time first scheduling
algorithm, the average process turnaround time (in
msec) is

year not read yetQ40 · page 302 of the book

Consider the 3 processes, P1, P2 and P3 shown in
the table.
Process
Arrival Time  Time Units
Required
Time
P1
0
5
P2
1
7
P3
3
4

The completion order of the 3 processes under the
policies FCFS and RR2 (round robin scheduling
with CPU quantum of 2 time units) are

(a)FCFS: P1, P2, P3 RR2: P1, P2, P3
(b)FCFS: P1, P3, P2 RR2: P1, P3, P2
(c)FCFS: P1, P2, P3 RR2: P1, P3, P2
(d)FCFS: P1, P3, P2 RR2: P1, P2, P3

GATE 2011 · MCQQ43 · page 302 of the book

Consider the following table of arrival time and burst
time for three processes P0, P1 and P2.
Process
Arrival Time
Burst Time
P0
0 ms
9 ms
P1
1 ms
4 ms
P2
2 ms
9 ms

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?

(a)5
(b)4.33
(c)6.33
(d)7.33

GATE 2010 · MCQ · 1 markQ44 · page 302 of the book

Which of the following statements is/are true?

I. Shortest remaining time first scheduling may cause
starvation

II. Preemptive scheduling may cause starvation

III. Round robin is better than FCFS in terms of
response time

(a)I only
(b)I and II only
(c)II and III only
(d)I, II and III OPERATING SYSTEMS

GATE 2007 · MCQ · 2 marksQ47 · page 303 of the book

An operating system uses the Shortest Remaining
Time First (SRT) process scheduling algorithm.
Consider the arrival times and execution times for the
following processes:

Process Execution Time Arrival Time
P1
20
0
P2
25
15
P3
10
30
P4
15
45

What is the total waiting time for process P2?

(a)5
(b)15
(c)40
(d)55

GATE 2006 · MCQ · 1 markQ50 · page 304 of the book

Consider three CPU-intensive processes, which
require 10, 20 and 30 time units and arrive at times
0, 2 and 6, respectively. How many context
switches are needed if the operating system
implements a Shortest Remaining Time First
(SRTF) scheduling algorithm?

Do not count the context switches at time zero and
at the end.

(a)1
(b)2
(c)3
(d)4

GATE 2006 · MCQ · 2 marksQ51 · page 304 of the book

Consider three processes (process id 0, 1, 2,
respectively) with compute time bursts 2, 4, and 8
time units. All processes arrive at time zero.
Consider the Longest Remaining Time First
(LRTF) scheduling algorithm. In LRTF ties are
broken by giving priority to the process with the
lowest process id. The average turnaround time is

(a)13 units
(b)14 units
(c)15 units
(d)16 units

GATE 2006 · MCQ · 2 marksQ52 · page 304 of the book

Consider three processes, all arriving at time zero,
with total execution time of 10, 20, and 30 units,
respectively. Each process spends the first 20% of
execution time doing I/O, the next 70% of time doing
computation, and the last 10% of time doing I/O
again.

The operating system uses a shortest remaining
compute time first scheduling algorithm and
schedules a new process either when the running
process gets blocked on I/O or when the running
process finishes its compute burst. Assume that all
I/O operations can be overlapped as much as possible.

For what percentage of time does the CPU remain
idle?

(a)0%
(b)10.6%
(c)30.0%
(d)89.4%

Self-check

Question 1

Processes P1 (arrival 0, burst 4), P2 (1, 3), P3 (2, 1). Average waiting time under FCFS and under SJF (non-preemptive)?

Show answer

FCFS: P1 0 to 4, P2 4 to 7, P3 7 to 8; waits 0, 3, 5: average $8/3 = 2.67$ . SJF: P1 runs first (only one at 0), then P3 (burst 1) before P2 (3): P3 4 to 5, P2 5 to 8; waits 0, 4, 2: average $6/3 = 2$ .

Question 2

Under SRTF, P1 (arrival 0, burst 8) runs. At time 2 P2 arrives with burst 5. Does it preempt?

Show answer

P1 has 6 remaining, P2's burst is 5: yes, P2 preempts. (If P2's burst were 6 it would not, since a tie does not preempt.)

Question 3

$\tau_0 = 8$ , $\alpha = 0.25$ , the first burst is 4. What is $\tau_1$ ?

Show answer

$0.25 \times 4 + 0.75 \times 8 = 7$ .

Question 4

Why can SJF cause starvation but FCFS cannot?

Show answer

In SJF a long process can be passed over forever if shorter ones keep arriving. In FCFS every process eventually reaches the front of the queue.

Revision card

One-screen revision

$TAT = CT - AT$ , $WT = TAT - BT$ , $RT =$ first run $- AT$ .
FCFS: convoy effect. SJF: optimal among non-preemptive. SRTF: optimal overall, preempts on shorter remaining time. HRRN: $(W + BT)/BT$ .
Predict bursts by exponential averaging.
Preemptive vs non-preemptive: decision points 1 and 4 only, or also 2 and 3.
Draw the Gantt chart; mind idle time and ties.

References

·Silberschatz, Galvin, Gagne, Operating System Concepts, Chapter 5 CPU Scheduling (basic concepts, scheduling criteria, scheduling algorithms)
·Tanenbaum and Bos, Modern Operating Systems, Chapter 2 Processes and Threads (scheduling)
·Stallings, Operating Systems: Internals and Design Principles, Chapter 9 Uniprocessor Scheduling

Verification

Every schedule on this page is produced by a tick-by-tick simulator (scripts/gen-os-sched-traces.py). scripts/enum-checks/os_sched.py compares it with a second, event-driven implementation on 24000 random cases (all six algorithms), brute-forces that SJF is optimal among run-to-completion orders when everything arrives together, checks that SRTF has the smallest average waiting time on 1500 random sets, and checks the figures quoted here (including HRRN and the convoy example); tests/os-sched-traces.test.ts re-derives every schedule with a third implementation in TypeScript and the C program on this page (npm run verify:c) is a fourth. Conventions that change answers: context switches take no time; ties go to the earlier arrival and then the input order; a running process keeps the CPU on a tie. Textbook chapter titles are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand. One misleading callout title fixed. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Threads and multithreading models

Priority and round robin scheduling