Self-checkedTier 1 13 min reados.scheduling-priority-rr

Priority and round robin scheduling

Priority scheduling (preemptive and non-preemptive, starvation and aging) and round robin (the time quantum, the circular ready queue, bounds on waiting and response time, the effect of the quantum and of the context-switch cost), with Gantt charts and the conventions that change the answer.

Why it exists

FCFS and SJF do not suit an interactive system: FCFS can leave short requests waiting behind a long job, and SJF needs burst lengths nobody knows. Two ideas dominate real schedulers. Priority scheduling lets the system say that some processes matter more than others. Round robin gives every process a short turn on the CPU in rotation, so that nobody waits long for a first response. They are the building blocks of the multilevel schedulers used in practice. GATE asks you to draw their schedules, to compute waiting and turnaround times, and to reason about the time quantum and starvation.

Prerequisites

CPU scheduling: criteria, FCFS, SJF and SRTF

You need the scheduling criteria and the Gantt chart method from CPU scheduling, and the cost of a switch from the context switch.

Precise definitions

Priority scheduling. Each process has a priority (an integer); the CPU is allocated to the ready process of highest priority. Equal priorities are served FCFS. A smaller number means a higher priority in most textbooks and in the examples here; some books and questions use the opposite, so read the question. SJF is priority scheduling with the priority equal to the predicted burst time.

Non-preemptive priority: the CPU is given to the highest-priority ready process when it becomes free, and the process keeps it until it ends or blocks. A newly arrived higher-priority process waits.
Preemptive priority: when a process arrives with a higher priority than the running one, the running process is preempted at once.
Priorities can be internal (computed from time limits, memory needs, the ratio of I/O to CPU burst) or external (set by the user or the importance of the work).

Starvation and aging. A low-priority process can wait indefinitely if higher-priority processes keep arriving: indefinite blocking (starvation). Aging is the remedy: the priority of a process is raised gradually the longer it waits, so that eventually it runs.

Round robin (RR). Designed for time-sharing systems. The ready queue is a FIFO (circular) queue and each process gets the CPU for at most one time quantum (time slice) $q$ .

The scheduler takes the process at the front of the queue and gives it the CPU.
If its remaining burst is at most $q$ , it runs to completion and leaves.
Otherwise the timer interrupts after $q$ and the process goes to the back of the queue.

RR is preemptive. A process that arrives while another is running joins the back of the queue. Convention in the examples: when a new process arrives at the same instant a quantum expires, the new process is queued before the preempted one.

Properties of round robin.

With $n$ processes in the ready queue and quantum $q$ , no process waits more than $(n - 1)\,q$ before getting the CPU again, so the response time of a process is at most $(n - 1)\,q$ (counted from its position in the queue).
If $q$ is large (at least the longest burst), RR is the same as FCFS.
If $q$ is very small, the CPU appears to give each of the $n$ processes a processor of $1/n$ the speed (processor sharing), but most of the time goes to context switches. With switch time $s$ the useful fraction is $q/(q + s)$ (context switch).
RR has a larger average turnaround time than SJF but better response time. The average turnaround time does not always improve when $q$ increases; it improves if most processes finish in a single quantum. A rule of thumb: choose $q$ so that about 80% of CPU bursts are shorter than $q$ .
RR does not starve any process (every process gets the CPU within $(n - 1)\,q$ ).

Multilevel queue and feedback queues combine these ideas (separate queues with different policies, and processes moving between queues). They come later with the real-time schedulers.

How it works

The animations use five processes with arrival, burst and priority P1 (0, 5, 3), P2 (1, 3, 1), P3 (2, 4, 4), P4 (3, 2, 2), P5 (4, 6, 5), where 1 is the highest priority.

Non-preemptive priority. P1 starts at 0 (nothing else is there) and keeps the CPU to 5 even though P2, which has a higher priority, arrived at 1. At 5 the highest-priority ready process, P2, goes first, then P4, P3 and P5. Average waiting time 5.4.

Priority scheduling (non-preemptive): start

Schedule simulated, not typed

Priority, non-preemptive (a smaller number is a higher priority). Context-switch time is ignored.

running

ready queue (front first)

empty

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

average turnaround

average waiting

average response

Step 0

Five processes with priorities (smaller number = higher priority). Non-preemptive: when the CPU is free the highest-priority READY process runs, to completion.

0 / 10

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

Preemptive priority. P2 arrives at 1 with a higher priority than P1 and takes the CPU at once; P1 resumes only at 6 and is finished at 10. Average waiting 4.8: with priorities that match urgency the important process (P2) never waits.

Priority scheduling (preemptive): start

Schedule simulated, not typed

Priority, preemptive (a smaller number is a higher priority). Context-switch time is ignored.

running

ready queue (front first)

empty

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

average turnaround

average waiting

average response

Step 0

The same five processes. Preemptive priority: a newly arrived process with a higher priority than the running one takes the CPU at once.

0 / 9

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

Round robin, quantum 3 (priorities ignored). Look at time 3: P4 arrives at the instant P1's quantum expires, so P4 joins the queue before P1, which goes to the back. Every process gets the CPU within a few time units, but the average waiting time (7.4) is larger than the best priority schedule.

Round robin, quantum 3: start

Schedule simulated, not typed

Round robin, quantum 3. Context-switch time is ignored.

running

ready queue (front first)

empty

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

average turnaround

average waiting

average response

Step 0

The same bursts (priorities ignored). Round robin keeps a FIFO ready queue and gives each process at most one quantum (3 time units) before sending it to the back. A process arriving at the instant a quantum expires is queued before the preempted one.

0 / 12

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

Worked examples

EX 1Preemptive and non-preemptive priority, computed by a program

Easy

The same five processes. A program computes the average waiting time under both.

#include <stdio.h>
 
#define N 5
/* arrival, burst, priority (a smaller number is a higher priority) */
static const int arrival[N] = {0, 1, 2, 3, 4};
static const int burst[N] = {5, 3, 4, 2, 6};
static const int prio[N] = {3, 1, 4, 2, 5};
 
static double run(int preemptive) {
    int rem[N], finish[N] = {0}, done = 0, cur = -1;
    for (int i = 0; i < N; i++) rem[i] = burst[i];
    for (int t = 0; done < N; t++) {
        if (cur < 0 || preemptive) {
            int best = cur;
            for (int i = 0; i < N; i++) {
                if (arrival[i] > t || rem[i] == 0 || i == cur) continue;
                if (best < 0 || prio[i] < prio[best]) best = i;
            }
            cur = best;
        }
        if (cur < 0) continue;
        if (--rem[cur] == 0) { finish[cur] = t + 1; done++; cur = -1; }
    }
    double w = 0;
    for (int i = 0; i < N; i++) w += finish[i] - arrival[i] - burst[i];
    return w / N;
}
 
int main(void) {
    printf("non-preemptive priority: average waiting %.2f\n", run(0));
    printf("preemptive priority:     average waiting %.2f\n", run(1));
    return 0;
}

non-preemptive priority: average waiting 5.40
preemptive priority:     average waiting 4.80

Reading it. Non-preemptive: P1 keeps the CPU to time 5; P2 (finish 8, wait 4), P4 (10, wait 5), P3 (14, wait 8), P5 (20, wait 10): $(0 + 4 + 8 + 5 + 10)/5 = 5.4$ . Preemptive: P1 runs 0 to 1; P2 arrives with a higher priority and runs 1 to 4 (P4 arrives at 3 with priority 2, which is not higher than P2's 1, so it waits); then P4 runs 4 to 6, P1 6 to 10, P3 10 to 14 and P5 14 to 20. The waits are P1 5, P2 0, P3 8, P4 1, P5 10: average $24/5 = 4.8$ .

EX 2How the quantum changes the result

Medium

Five processes arrive together with bursts 6, 3, 8, 2, 4. The program runs round robin for several quanta and prints the average waiting time, the average response time and the number of times the running process changes.

#include <stdio.h>
 
#define N 5
static const int burst[N] = {6, 3, 8, 2, 4};          /* all five processes are in the ready queue at time 0 */
 
static void rr(int q) {
    int rem[N], finish[N] = {0}, first[N];
    int queue[256], head = 0, tail = 0;
    for (int i = 0; i < N; i++) { rem[i] = burst[i]; first[i] = -1; queue[tail++] = i; }
    int t = 0, last = -1, switches = 0;
    while (head < tail) {
        int p = queue[head++];
        int span = rem[p] < q ? rem[p] : q;
        if (first[p] < 0) first[p] = t;
        if (last >= 0 && last != p) switches++;
        t += span;
        rem[p] -= span;
        last = p;
        if (rem[p] > 0) queue[tail++] = p; else finish[p] = t;
    }
    double w = 0, r = 0;
    for (int i = 0; i < N; i++) { w += finish[i] - burst[i]; r += first[i]; }
    printf("q = %3d: average waiting %5.2f, average response %5.2f, %2d changes of running process\n", q, w / N, r / N, switches);
}
 
int main(void) {
    int qs[6] = {1, 2, 3, 4, 8, 100};
    for (int i = 0; i < 6; i++) rr(qs[i]);
    return 0;
}

q =   1: average waiting 11.60, average response  2.00, 20 changes of running process
q =   2: average waiting 11.40, average response  4.00, 10 changes of running process
q =   3: average waiting 11.00, average response  5.80,  8 changes of running process
q =   4: average waiting 11.20, average response  7.00,  6 changes of running process
q =   8: average waiting 10.20, average response 10.20,  4 changes of running process
q = 100: average waiting 10.20, average response 10.20,  4 changes of running process

Reading it. The response time grows steadily with $q$ : with $q = 1$ every process starts within the first 5 time units (average 2.0). The average waiting time is not monotonic ( $11.0$ at $q = 3$ , $11.2$ at $q = 4$ ) and is smallest when $q$ is at least the longest burst, where RR becomes FCFS (10.2: the same as FCFS on this order: waits 0, 6, 9, 17, 19, average 10.2). The number of switches falls as $q$ grows, which with a switch cost $s$ means less overhead.

EX 3Round robin by hand

Medium

Bursts 10, 5, 8 for P1, P2, P3, all arriving at 0, $q = 4$ . The queue gives the order P1 (0 to 4), P2 (4 to 8), P3 (8 to 12), P1 (12 to 16), P2 (16 to 17, finishes), P3 (17 to 21, finishes), P1 (21 to 23, finishes). Completion times: P1 23, P2 17, P3 21; waiting $= CT - BT$ since all arrive at 0: 13, 12, 13, average $38/3 = 12.67$ . The number of times the CPU is given out is 7 (the number of slices), so there are 6 context switches between slices.

EX 4Aging arithmetic

Medium

Priorities run from 0 (highest) to 127 (lowest). A system lowers the priority number of every waiting process by 1 every 10 minutes. A process that starts at priority 127 reaches priority 0 after $127 \times 10 = 1270$ minutes, about 21 hours, so even the lowest-priority process is guaranteed to run eventually, whatever the arrivals. Without aging a stream of higher-priority processes could keep it waiting for ever (starvation).

EX 5Which algorithm gives what?

GATE level

Best response for interactive users: round robin (bounded wait of $(n - 1)q$ ). No starvation: FCFS, round robin, HRRN. May starve: SJF, SRTF, priority without aging. Same as FCFS: round robin with $q$ at least the longest burst; priority scheduling when all priorities are equal. Lowest average waiting time: SJF (non-preemptive), SRTF (overall), not priority or round robin. Most context switches: round robin with a small $q$ . Requires burst-length estimates: SJF and SRTF. Convoy effect: FCFS. For a given problem, compute both the algorithm's schedule and the condition (number of switches, waiting times); the properties above let you eliminate options quickly.

Cheat box

Priority: highest priority runs; smaller number $=$ higher priority (check the question). Preemptive: a newcomer with higher priority takes the CPU. Equal priority: FCFS.
Starvation of low priorities; cure: aging (raise priority with waiting time).
Round robin: FIFO queue, quantum $q$ , preempted process goes to the back. A new arrival at the instant of expiry is queued before the preempted process (state the convention).
RR: wait for the next turn at most $(n - 1)\,q$ . $q \to \infty$ : FCFS. $q \to 0$ : processor sharing, overhead $s/(q + s)$ .
RR has better response and worse average turnaround than SJF; average waiting is not monotonic in $q$ .
Completion times from the Gantt chart; $WT = CT - AT - BT$ .

Traps and GATE patterns

Connections

Builds on

CPU scheduling: criteria, FCFS, SJF and SRTF

Unlocks

Context switchinguses CPU scheduling: criteria, FCFS, SJF and SRTFuses Multilevel queues and real-time schedulingPrerequisite of Multilevel queues and real-time schedulinguses

Across subjects

No cross-subject links yet.

Within this subject

CPU scheduling: criteria, FCFS, SJF and SRTFuses Context switchinguses Process states, fork and execuses Multilevel queues and real-time schedulinguses Critical section and race conditionsuses

Both algorithms extend CPU scheduling: SJF is priority with burst as priority, and round robin with an unbounded quantum is FCFS. The cost of each preemption is the context switch. Real systems combine them in multilevel queues and real-time scheduling. A low-priority process holding a resource that a high-priority process needs causes priority inversion, which is met with critical sections.

PYQs

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

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 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 2022 · MCQ · 2 marksQ14 · page 297 of the book

Consider 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. There is no context switch
from S to P. Switching to a ready process after the
termination of another process is also considered a
context switch. Which one of the following is NOT
possible as CPU  burst time (in time units) of these
processes?

(a)P = 4, Q = 10, R = 6, S = 2
(b)P = 2, Q = 9, R = 5, S = 1
(c)P = 4, Q = 12, R = 5, S = 4
(d)P = 3, Q = 7, R = 7, S = 3

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 2017 · NATQ27 · page 299 of the book

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

Proces
Arrival
Time
Burst
Time
Priority
P1
0
11
2
P2
5
28
0
P3
12
2
3
P4
2
10
1
P5
9
16
4

The average waiting time (in milliseconds) of all the
processes using the pre-emptive priority scheduling
algorithm is __________.

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 · NATQ35 · page 301 of the book

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
tc CPU milliseconds and then initiates a single I/O
operation that lasts for tio 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
TC
Tio
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
___________.

GATE 2013 · MCQQ38 · page 301 of the book

A 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 unit
and decides the next process to schedule. Which one
of the following is TRUE if the processes have no I/O
operations and all arrive at time zero?

(a)This algorithm is equivalent to the first-come- first-serve algorithm.
(b)This scheduling algorithm behaves like Round-Robin scheduling.
(c)This algorithm is equivalent to the shortest-job- first algorithm.
(d)This algorithm is equivalent to the shortest- remaining-time-first algorithm.

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

Self-check

Question 1

P1 (arrival 0, burst 4, priority 2), P2 (1, 2, 1). Non-preemptive priority, 1 is highest. Waiting time of each?

Show answer

P1 runs 0 to 4 (it is alone at 0). P2 runs 4 to 6. Waiting: P1 0, P2 $4 - 1 = 3$ .

Question 2

The same two processes with preemptive priority. Completion times?

Show answer

P2 arrives at 1 with a higher priority and preempts P1: P1 runs 0 to 1, P2 1 to 3, P1 3 to 6. Completion: P2 3, P1 6.

Question 3

Round robin with 6 processes in the ready queue and $q = 5$ ms. What is the longest a process waits before its next turn?

Show answer

$(n - 1)q = 5 \times 5 = 25$ ms.

Question 4

What does round robin become when $q$ is larger than every burst?

Show answer

FCFS (each process runs to completion in its first turn).

Revision card

One-screen revision

Priority: smaller number $=$ higher (check). Preemptive or not. Starvation $\to$ aging.
RR: quantum $q$ , circular FIFO, back of the queue when preempted; waits at most $(n - 1)q$ .
$q$ large: FCFS. $q$ small: overhead $s/(q + s)$ .
RR: good response, higher average turnaround than SJF; average waiting not monotonic in $q$ .
State conventions: priority direction, simultaneous arrival at expiry, zero-cost switches.

References

·Silberschatz, Galvin, Gagne, Operating System Concepts, Chapter 5 CPU Scheduling (priority scheduling, round-robin scheduling)
·Tanenbaum and Bos, Modern Operating Systems, Chapter 2 Processes and Threads (scheduling in interactive systems)
·Stallings, Operating Systems: Internals and Design Principles, Chapter 9 Uniprocessor Scheduling (round robin, priority)

Verification

The schedules come from the tick-by-tick simulator in scripts/gen-os-sched-traces.py, compared in scripts/enum-checks/os_sched.py with an independent event-driven implementation on 24000 random cases, re-derived by a third implementation in tests/os-sched-traces.test.ts, and the two tables on this page (average waiting for priority scheduling; waiting, response and switches against the quantum) are produced by C programs (npm run verify:c). Conventions that change answers, stated on the page: a SMALLER priority number is a HIGHER priority; a process arriving at the same instant a quantum expires is queued BEFORE the preempted process; context switches take no time; a running process is not preempted by an equal priority. 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 overstated claim (round-robin turnaround 'is smallest when...') softened. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

CPU scheduling: criteria, FCFS, SJF and SRTF

Disk scheduling