Chapter 13 of 38

Priority Scheduling

In a hospital emergency room, patients are not treated in the order they walk in. A heart-attack patient is seen before someone with a sprained ankle, even if the ankle patient arrived an hour earlier. Each patient gets a priority, and the most urgent case goes first.

Operating systems need the same idea. A keyboard handler, an audio player or a control loop in a car must react quickly, while a backup job can wait. This is Priority Scheduling.

In Priority Scheduling, every process has a priority, and the CPU is given to the ready process with the highest priority. Processes with equal priority are usually served in FCFS order.

Priority scheduling is a general framework. In fact, SJF from the previous chapter is just priority scheduling where the priority is the (predicted) burst length: the shorter the burst, the higher the priority. In this chapter we will solve both the non-preemptive and preemptive versions, see why low-priority processes can starve, fix it with aging, and look at how Linux handles priorities in practice.


How Priority Numbers Work

A priority is usually a small integer, for example 0 to 7 or 0 to 139. The tricky part is that there is no universal rule about whether a small number means high or low priority.

Convention

Example

Lower number = higher priority

Most OS textbooks, Linux nice values (-20 is most favoured), Linux internal kernel priority

Higher number = higher priority

Windows thread priorities (0 to 31), Linux real-time priorities (1 to 99), Java thread priorities (1 to 10)

In this chapter, a lower number means a higher priority (priority 1 beats priority 3). In an exam, always check which convention the question uses before you start.

Where Do Priorities Come From?

  • Internal priorities are computed by the OS from measurable things: memory needs, number of open files, the ratio of I/O time to CPU time, predicted burst length.

  • External priorities are set from outside: the importance of the process, the user's account type, money paid for computing time, an administrator's decision, or a command like nice.

Priorities can also be:

  • Static: fixed when the process is created and never changed.

  • Dynamic: adjusted by the OS while the process runs (for example, aging, or boosting a process that just woke up from I/O).


Non-Preemptive vs Preemptive Priority

Just like SJF and SRTF, priority scheduling comes in two forms.

Non-preemptive Priority

Preemptive Priority

When a higher-priority process arrives

It goes to the front of the ready queue, but waits for the running process to finish its burst

It immediately takes the CPU from the running process

Decision points

Only when the CPU becomes free

CPU becomes free, or a new process arrives

Response for urgent work

Can be delayed by a long low-priority burst

Fast

Context switches

Fewer

More

Preemption happens only on strictly higher priority. A newcomer with the same priority as the running process does not preempt it.


Example 1: All Processes Arrive at Time 0

Process

Burst Time

Priority

P1

4

3

P2

2

1

P3

6

4

P4

3

2

P5

1

5

With everyone present at time 0, simply sort by priority: P2 (1), P4 (2), P1 (3), P3 (4), P5 (5). Preemptive and non-preemptive give the same result here, because nobody arrives later.

|  P2  |  P4  |  P1  |  P3  |  P5  |
0      2      5      9      15     16

Process

BT

Priority

CT

TAT

WT

P1

4

3

9

9

5

P2

2

1

2

2

0

P3

6

4

15

15

9

P4

3

2

5

5

2

P5

1

5

16

16

15

Average TAT = 47 / 5 = 9.4
Average WT  = 31 / 5 = 6.2

Look at P5. It needs only 1 unit of CPU but waits 15, because it has the lowest priority. Priority scheduling does not care about burst length unless the priority itself is based on it. The goal is not the lowest average waiting time; the goal is to serve important work first.


Example 2: Non-Preemptive Priority With Arrivals

We will use this data for both versions.

Process

Arrival Time

Burst Time

Priority

P1

0

5

3

P2

1

3

1

P3

2

6

4

P4

3

2

2

P5

5

4

5

P6

6

2

1

Step-by-step trace

t = 0  : ready = {P1(pr 3)}                       → P1 runs 0-5 (cannot be interrupted)
t = 5  : ready = {P2(1), P3(4), P4(2), P5(5)}     → P2 runs 5-8
t = 8  : ready = {P3(4), P4(2), P5(5), P6(1)}     → P6 runs 8-10
t = 10 : ready = {P3(4), P4(2), P5(5)}            → P4 runs 10-12
t = 12 : ready = {P3(4), P5(5)}                   → P3 runs 12-18
t = 18 : ready = {P5(5)}                          → P5 runs 18-22
|  P1  |  P2  |  P6  |  P4  |  P3  |  P5  |
0      5      8      10     12     18     22

Process

AT

BT

Pr

CT

TAT

WT

P1

0

5

3

5

5

0

P2

1

3

1

8

7

4

P3

2

6

4

18

16

10

P4

3

2

2

12

9

7

P5

5

4

5

22

17

13

P6

6

2

1

10

4

2

Average TAT = 58 / 6 ≈ 9.67
Average WT  = 36 / 6 = 6.0

The problem is visible at the start: P2 has the top priority and arrives at time 1, but it must wait 4 units for the lower-priority P1 to finish. For truly urgent work, that delay may be unacceptable.


Example 3: Preemptive Priority With Arrivals

Same data. Now a newly arrived process with a strictly higher priority takes the CPU at once.

Step-by-step trace

Time  Event            Running vs newcomer                Action
----  ---------------  ---------------------------------  -------------------------
 0    P1 arrives       -                                  P1 runs
 1    P2 arrives       P1(pr 3) vs P2(pr 1)               preempt P1 (rem 4), P2 runs
 2    P3 arrives       P2(1) vs P3(4)                     P2 continues
 3    P4 arrives       P2(1) vs P4(2)                     P2 continues
 4    P2 done          ready: P1(3), P3(4), P4(2)         P4 runs
 5    P5 arrives       P4(2) vs P5(5)                     P4 continues
 6    P4 done, P6 arr. ready: P1(3), P3(4), P5(5), P6(1)  P6 runs
 8    P6 done          ready: P1(3), P3(4), P5(5)         P1 resumes (4 left)
12    P1 done          ready: P3(4), P5(5)                P3 runs
18    P3 done          ready: P5(5)                       P5 runs
22    P5 done
|  P1  |  P2  |  P4  |  P6  |  P1  |  P3  |  P5  |
0      1      4      6      8      12     18     22

Process

AT

BT

Pr

CT

TAT

WT

RT

P1

0

5

3

12

12

7

0

P2

1

3

1

4

3

0

0

P3

2

6

4

18

16

10

10

P4

3

2

2

6

3

1

1

P5

5

4

5

22

17

13

13

P6

6

2

1

8

2

0

0

Average TAT = 53 / 6 ≈ 8.83
Average WT  = 31 / 6 ≈ 5.17
Average RT  = 24 / 6 = 4.0

Now the two highest-priority processes, P2 and P6, never wait at all (WT = 0). That is exactly what preemptive priority promises. The price is paid by P1, which got interrupted after 1 unit and had to wait 7 units in total.

Notice that P3 and P5, the two lowest-priority processes, have the same waiting times in both versions. Low-priority work always ends up at the back.


Equal Priorities: FCFS or Round Robin

What happens when several ready processes share the highest priority?

  • The simple rule is FCFS among them: the one that arrived first goes first.

  • Many real systems instead use Round Robin among equal-priority processes, so they share the CPU in time slices. Linux SCHED_RR works this way.

Keeping a separate queue for each priority level and running the highest non-empty queue is the basic idea of Multilevel Queue Scheduling, which you will meet two chapters from now. Round Robin itself is the topic of the next chapter.


The Big Problem: Starvation

If high-priority processes keep arriving, a low-priority process may never run. This is called starvation or indefinite blocking.

Ready queue over time (lower number = higher priority)

t = 0   : Low(9)  High(1)          → High runs
t = 3   : Low(9)  High(2)          → High runs
t = 6   : Low(9)  High(1)          → High runs
t = 9   : Low(9)  High(3)          → High runs
 ...
Low has been ready the whole time and has never run.

A famous story, often repeated in OS textbooks, says that when an old IBM 7094 at MIT was shut down in 1973, administrators found a low-priority job that had been submitted in 1967 and had still not run. Whether or not every detail is exact, the lesson is real: on a busy system, pure priority scheduling can leave a process waiting forever.

The Fix: Aging

Aging gradually increases the priority of a process the longer it waits, so every process eventually reaches the top priority and gets the CPU.

Example rule: priorities range from 0 (highest) to 99 (lowest). For every 5 seconds a process waits in the ready queue, its priority number decreases by 1.

A process starting at priority 99 needs 99 steps to reach 0.

Worst-case time = 99 × 5 s = 495 s = 8 minutes 15 seconds

So instead of waiting forever, the lowest-priority process is guaranteed to reach the highest priority in a bounded time (here, about 8 minutes). Once it runs, its priority is usually reset to its original value.

Aging turns a static priority into a dynamic one. You already saw a special case of it: HRRN in SJF & SRTF Scheduling raises a job's "priority" (its response ratio) as its waiting time grows.


Priority Inversion

Priorities create another, more surprising problem when processes share resources such as locks.

Suppose there are three processes: H (high), M (medium) and L (low).

1. L runs and acquires a lock R.
2. H arrives, preempts L, and tries to acquire R → H blocks (L holds R).
3. M arrives. It does not need R. M has higher priority than L, so M runs.
4. M runs for a long time. L cannot run, so it cannot release R.
5. H, the highest-priority process, is effectively waiting for M.

Priority order says:   H > M > L
What actually happens: M runs while H waits

This is priority inversion: a high-priority process is indirectly blocked by a lower-priority one. The usual solution is the priority-inheritance protocol: while L holds a lock that H is waiting for, L temporarily inherits H's priority, so M cannot preempt it. When L releases the lock, its priority drops back.

A well-known real case happened on NASA's Mars Pathfinder lander in 1997. A low-priority task held a shared resource needed by a high-priority task, medium-priority tasks kept running, and a watchdog timer kept resetting the system. Engineers fixed it from Earth by enabling priority inheritance in the real-time OS. We will look at the locks involved in Mutex Locks & Semaphores.


Priorities in Linux

Linux has two groups of scheduling policies:

Policy

Type

Priority range

SCHED_FIFO

Real-time, FCFS within a priority level

1 to 99 (higher number = higher priority)

SCHED_RR

Real-time, Round Robin within a priority level

1 to 99

SCHED_OTHER (also called SCHED_NORMAL)

Normal time-sharing (the default)

Static priority 0; controlled by the nice value

SCHED_BATCH, SCHED_IDLE

Background work

Static priority 0

Any runnable real-time thread runs before any normal thread (the kernel only keeps a small safety reserve, by default about 5% of each second, for normal threads so that a runaway real-time thread cannot lock up the machine). Among real-time threads, the scheduler uses preemptive priority scheduling. You can see the ranges with the chrt tool. This is real output from an Ubuntu system running kernel 6.18 under WSL2:

$ chrt -m
SCHED_OTHER min/max priority	: 0/0
SCHED_FIFO min/max priority	: 1/99
SCHED_RR min/max priority	: 1/99
SCHED_BATCH min/max priority	: 0/0
SCHED_IDLE min/max priority	: 0/0
SCHED_DEADLINE min/max priority	: 0/0

Nice Values

For normal processes, priority is expressed as a nice value from -20 (most favoured) to 19 (least favoured). The default is 0. The name comes from the idea that a process with a high nice value is being "nice" to others by asking for less CPU.

Linux's fair scheduler does not use nice values as strict priorities. A process with nice 10 is not starved by a process with nice 0; it simply gets a smaller share of the CPU. Internally each nice level maps to a weight (nice 0 = 1024), and neighbouring levels differ by a factor of about 1.25, which works out to roughly 10% more or less CPU per step. This weight-based sharing is one built-in reason normal Linux processes do not starve.

$ nice                     # print current nice value
0
$ nice -n 10 nice          # run 'nice' with nice value +10
10

Changing Priority From C

A program can read and change its own nice value with getpriority() and nice():

#define _DEFAULT_SOURCE              /* for nice() with -std=c17 */
#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <unistd.h>
#include <sys/resource.h>

static void show(const char *label) {
    errno = 0;                       /* getpriority can legally return -1 */
    int p = getpriority(PRIO_PROCESS, 0);
    printf("%-28s nice = %d\n", label, p);
}

int main(void) {
    show("At start:");

    /* Any process may LOWER its own priority (raise nice). */
    if (nice(5) == -1 && errno != 0)
        perror("nice(5)");
    show("After nice(5):");

    /* Raising priority (lowering nice) needs privilege. */
    errno = 0;
    if (nice(-3) == -1 && errno != 0)
        printf("nice(-3) failed: %s\n", strerror(errno));
    show("After trying nice(-3):");

    return 0;
}

Compiled with gcc -std=c17 -Wall -Wextra and run as a normal user on Linux:

At start:                    nice = 0
After nice(5):               nice = 5
nice(-3) failed: Operation not permitted
After trying nice(-3):       nice = 5

Started with nice -n 2 ./nicedemo, it begins at 2 and moves to 7, and the nice(-3) call fails the same way.

This shows an important protection rule: a normal user can lower the priority of their own processes, but not raise it. Raising priority requires the CAP_SYS_NICE capability (typically root) or a raised RLIMIT_NICE resource limit. Otherwise, every user would simply set their programs to the highest priority and the whole idea would collapse.

Note the errno = 0 trick: getpriority() and nice() can legitimately return -1 as a valid nice value, so checking errno is the only reliable way to detect an error.


Advantages and Disadvantages

Advantages

Disadvantages

Important and time-critical work runs first

Low-priority processes can starve (needs aging)

Flexible: priority can encode anything (deadlines, payment, burst length, user type)

Choosing good priorities is hard

Preemptive form gives very fast response to urgent processes

Priority inversion when sharing locks

Basis of real-time scheduling

Average waiting time is not minimised (unless priority = shortest burst)


Common Mistakes

  • Assuming the priority convention. Check whether the question says "lower number = higher priority" or the opposite. Getting this wrong reverses the whole Gantt chart.

  • Preempting in the non-preemptive version. In Example 2, P2 arrives at 1 with top priority, but P1 still runs until 5.

  • Preempting on equal priority. A newcomer must have strictly higher priority to preempt.

  • Using the original burst after a preemption. In Example 3, P1 resumes at 8 with 4 units left, not 5.

  • Confusing starvation with deadlock. A starving process is ready and could run; it just keeps losing. In a deadlock, processes are blocked waiting for each other and none can proceed.

  • Thinking aging removes priorities. It only bounds the waiting time; high-priority work is still favoured.


Interview Questions

What is priority scheduling?

An algorithm that gives the CPU to the ready process with the highest priority, using FCFS (or Round Robin) to break ties.

How is SJF a special case of priority scheduling?

SJF uses the predicted next CPU burst as the priority: the shorter the burst, the higher the priority.

What is starvation, and how does aging solve it?

Starvation is when a ready process never gets the CPU because higher-priority processes keep arriving. Aging gradually raises the priority of waiting processes, so every process eventually becomes the highest priority and runs.

What is priority inversion?

A high-priority process waits for a lock held by a low-priority process, while a medium-priority process preempts the low-priority one. The high-priority process is effectively delayed by the medium one. Priority inheritance fixes it.

What is the range of nice values in Linux?

-20 (highest priority, most CPU share) to 19 (lowest). The default is 0. Only privileged processes can lower their nice value.

Does a nice 19 process starve under Linux's normal scheduler?

No. The fair scheduler gives it a small share of the CPU based on its weight, rather than running it only when nothing else wants the CPU.

Internal vs external priority?

Internal priorities are computed by the OS from measurable properties such as I/O-to-CPU ratio or memory use. External priorities are set by policy or users, such as importance, payment or the nice command.


The Main Idea

Priority Scheduling runs the most important ready process first. Equal priorities are handled by FCFS or Round Robin.

Pick the highest-priority ready process
      ↓
Non-preemptive: run until the burst ends
Preemptive:     run until done or a higher-priority process arrives
      ↓
Waiting too long? Aging raises priority

Key facts:

Forms        → Non-preemptive and preemptive
Ties         → FCFS (or Round Robin)
Problem      → Starvation of low-priority processes
Fix          → Aging
Lock problem → Priority inversion → priority inheritance
Linux        → RT priorities 1-99, nice -20..19 for normal tasks

Priorities let the OS serve what matters most, but without aging the least important work may never be served at all.

So far, every algorithm either never preempts or preempts only when something "better" arrives. In the next chapter, Round Robin Scheduling, we preempt on a timer instead, giving every process a fair, fixed slice of CPU time. That is the foundation of every time-sharing system.