Lesson 5.4: Priority Scheduling

01 Introduction

In Lessons 5.2 and 5.3 we saw two rules for choosing among ready processes: arrival order (FCFS) and predicted burst length (SJF and SRTF). Both rules are special cases of a more general idea. The scheduler can assign each process a priority and always run the ready process with the highest priority. Arrival order is priority equal to the negative of the arrival time; burst length is priority inversely proportional to the predicted burst. But priority can also encode things that neither rule captures: the importance of a task, its deadline, the user or class it belongs to, or the policy the system administrator has chosen.

Priority scheduling is the most general of the classical CPU scheduling algorithms, and it is the one most used in practice. Real-time operating systems use it for their hard-deadline tasks; general-purpose systems use it as one component of a hybrid scheduler; and cluster and batch schedulers use it to give certain jobs precedence over others. The idea is simple — highest priority runs first — but the design questions are subtle: where do priorities come from? Are they static or dynamic? Is the policy preemptive or not? How is starvation prevented?

This lesson covers the definition of priority, the sources of priority values, the preemptive and non-preemptive forms of the algorithm, the relationship between priority scheduling and SJF, the starvation problem and the aging technique that mitigates it, the priority-inversion problem that arises when tasks of different priorities share resources, and the way Linux exposes priority to user space. The lesson closes with a worked example that compares priority scheduling to the algorithms from the previous two lessons on the same workload.

Prerequisites

This lesson builds on Lessons 5.2 and 5.3. The concepts of non-preemptive and preemptive scheduling, the metrics from Lesson 5.1, and the starvation discussion from Lesson 5.3 are all used here. The priority-inversion section assumes no prior knowledge of real-time systems or synchronization, but the details of the latter are deferred to Unit 6.

02 Learning objectives

By the end of this lesson you will be able to

Describe priority scheduling and distinguish preemptive from non-preemptive forms.
Identify the sources of priority values and explain static versus dynamic assignment.
Explain the relationship between priority scheduling and SJF.
Analyse starvation in priority scheduling and describe aging as a solution.
Explain priority inversion and the priority-inheritance protocol.

This lesson contributes to U5.2, U5.4, and U5.5, and to course learning outcomes CLO1, CLO3, and CLO8.

03 Required reading

Operating System Concepts — Chapter 5, Section 5.3.4, Priority Scheduling. The standard treatment, including the discussion of starvation, aging, and the relationship to SJF.
OSTEP — Chapter 7, Scheduling: Introduction, and Chapter 8, Scheduling: The Multi-Level Feedback Queue. OSTEP does not treat priority scheduling as a separate algorithm, but its discussion of MLFQ shows how priority scheduling is used in real systems to approximate SJF.
Tanenbaum & Bos — Modern Operating Systems, Chapter 2, Section 2.4.4, Priority Scheduling, and Chapter 2, Section 2.5, Real-Time Scheduling.
Silberschatz et al. — Chapter 5, Section 5.6, Real-Time CPU Scheduling. The sections on priority inversion and priority inheritance.
Linux man pages: man 7 sched, man 2 sched_setscheduler, man 2 sched_get_priority_min, man 1 chrt, man 1 nice, man 2 setpriority, man 3 pthread_setschedparam, man 3 pthread_mutexattr_setprotocol.

Reading strategy

Read the Silberschatz section on priority scheduling first; it establishes the standard terminology and the relationship to SJF. Then read the real-time scheduling section for the priority-inversion discussion — this is the most practically important part of the lesson, and the one most often omitted from introductory treatments. Keep man 7 sched open as a reference for how Linux names and exposes priorities; you will use it in the interactive activity.

04 Core content

4.1 The algorithm

Priority scheduling assigns each process a priority, conventionally an integer, and always selects the ready process with the highest priority. The algorithm is defined by two rules:

Each process has a priority p, assigned at creation or updated dynamically.
When the CPU becomes free, the scheduler selects the ready process with the highest priority. If two processes have the same priority, the tie-break is by arrival time (FCFS within a priority level).

The convention for the numeric value of the priority varies. Some systems use small numbers for high priorities — Linux's nice values, for example, where −20 is the highest priority and +19 is the lowest. Other systems use large numbers for high priorities — Windows uses 0 to 31, with larger numbers meaning higher priority. Throughout this lesson we will use "higher priority" in the abstract sense and note the numeric convention when it matters.

4.2 Preemptive and non-preemptive forms

Priority scheduling comes in two forms, just as SJF does.

Non-preemptive priority scheduling: Once a process has been given the CPU, it runs until it blocks or terminates. A higher-priority process that arrives while a lower-priority process is running must wait for the running process to finish its burst.
Preemptive priority scheduling: If a higher-priority process becomes ready while a lower-priority process is running, the scheduler preempts the running process immediately and switches to the higher-priority one. This is the more common form in systems that support priorities, because it is the whole point of having priorities: a high-priority task should be able to run promptly.

The choice between the two is often dictated by the semantics of the priority. If the priority represents an importance ranking, preemptive scheduling is usually wanted: an important task should preempt an unimportant one as soon as it becomes ready. If the priority represents a batch-level classification with no urgency component, non-preemptive scheduling may be adequate and cheaper.

4.3 Where priorities come from

Priorities can be assigned by the system or by the user, and they can be fixed or variable. The distinction is important because it determines what the scheduler is actually optimizing.

Internal priorities. Assigned by the kernel based on measurable properties of the process: its resource usage, its burst pattern, the amount of memory it holds, the ratio of CPU time to I/O time, or the time it has been waiting. SJF is priority scheduling with an internal priority derived from the predicted burst length. The multilevel-feedback queues of Lesson 5.6 use internal priorities based on observed behaviour.
External priorities. Assigned from outside the kernel, based on criteria that are not measurable from the process itself: the importance of the user, the funding source of the computation, the department that submitted the job, or the service level agreement. External priorities require a policy decision that the kernel cannot make on its own.
Static priorities. Fixed at process creation and never changed. Simple to implement and easy to reason about, but inflexible: a process that becomes more important (or less) over its lifetime cannot be reclassified.
Dynamic priorities. Adjusted during the process's lifetime based on its behaviour or on the state of the system. Dynamic priorities allow the scheduler to respond to changing conditions — for example, by raising the priority of a process that has been waiting a long time (aging), or by lowering the priority of a process that has consumed a lot of CPU recently. The O(1) scheduler that preceded CFS in Linux used dynamic priorities for exactly this reason.

4.4 Priority scheduling generalizes SJF

SJF is priority scheduling with a specific internal priority: priority inversely proportional to the predicted next CPU burst. A process with a short predicted burst gets a high priority; a process with a long predicted burst gets a low priority. If priorities are integers and we set priority = −burst (higher number = shorter burst in a system where larger priorities run first), the priority scheduler produces exactly the SJF schedule.

This relationship is useful for two reasons. First, it means that everything we learned about SJF in Lesson 5.3 applies to priority scheduling in the special case where priority encodes burst length: the same optimality result for average waiting time, the same starvation problem, the same need for a burst-length estimate. Second, it means that priority scheduling is a framework rather than a single algorithm. By choosing different priority functions, we obtain different scheduling policies — some of which optimize one metric, some another.

Priority as a general mechanism

Thinking of priority scheduling as a framework rather than a single algorithm is the key to understanding modern schedulers. Linux's CFS, Windows's thread scheduler, and the multilevel-feedback queues of the classic UNIX schedulers are all built on the idea of assigning a priority (possibly a dynamic, multi-dimensional one) and always running the highest-priority ready task. The interesting design work is in how the priority is computed.

4.5 Starvation

The central problem with priority scheduling is starvation: a low-priority process can be indefinitely postponed if higher-priority processes keep arriving. Unlike SJF, where starvation requires a steady stream of short jobs, priority starvation can occur with only a few high-priority processes — as long as they remain ready or keep returning to the ready queue. A low-priority process on a busy system might never run.

The famous illustration is the MIT IBM 7094 shutdown in 1973. A low-priority job had been submitted to the system and had been waiting since 1967. When the machine was finally shut down, the job was still in the queue; it had never been scheduled. Six years of waiting, on a machine that ran twenty-four hours a day.

Figure 5.4 — Starvation under priority scheduling. Without aging, a low-priority process waits indefinitely while high-priority processes keep arriving. With aging, the low-priority process's priority rises the longer it waits, and it is eventually scheduled. The cost is a slightly higher average waiting time for the high-priority processes.

4.6 Aging

Aging is the standard solution to priority starvation. The scheduler gradually increases the priority of a process the longer it waits. Eventually, a long-waiting low-priority process's priority exceeds that of newly arriving high-priority processes, and it is scheduled. Aging bounds the maximum waiting time; a process that receives no CPU for long enough will eventually become the highest-priority ready process.

The aging policy has several parameters:

The aging rate. How much the priority increases per unit time, or per scheduling event. A fast rate bounds starvation tightly but degrades the average waiting time; a slow rate preserves most of the priority policy's benefit but allows long waits.
The priority ceiling. The maximum priority a process can reach through aging. If the ceiling is below the highest-priority tasks, high-priority processes are still protected from being overtaken; if it is above, they are not.
The reset policy. When a process is finally scheduled, its priority is typically reset to its base value. If it is not reset, the aging effect accumulates and eventually every process reaches the ceiling.

The trade-off is the same as the one we saw in Lesson 5.3 for SJF starvation: aging bounds the worst-case waiting time at the cost of the average-case performance that the priority policy was designed to achieve. The choice of aging rate is a policy decision that depends on the system's requirements.

Starvation and priority inversion are different problems

Starvation is a scheduling problem: a ready process is never selected. Priority inversion, discussed next, is a synchronization problem: a high-priority process is blocked waiting for a resource held by a low-priority process, and a medium-priority process runs in the meantime. The two are often confused because both involve priorities and both involve waiting. Aging solves starvation; priority inheritance (or a related protocol) solves priority inversion.

4.7 Priority inversion

Priority inversion is a phenomenon that arises when processes of different priorities share a resource protected by a lock. Consider three processes:

L, a low-priority process.
M, a medium-priority process.
H, a high-priority process.

Suppose L acquires a lock on a shared resource. H becomes ready and preempts L, then tries to acquire the same lock. Because the lock is held by L, H blocks. The scheduler resumes L — but M becomes ready and, because M has higher priority than L, preempts L. Now M runs, L is not running, and the lock is still held by L. H is blocked waiting for L, and L cannot run because M is running. H — the highest-priority process in the system — is effectively blocked by M, a medium-priority process that does not even use the shared resource.

This is priority inversion: the priority of H has been inverted to that of L, because H is waiting for a resource that L holds. In the meantime, M — which should have the lowest effective priority — runs.

Figure 5.4b — Priority inversion without and with priority inheritance. Without inheritance, a medium-priority process runs while a high-priority process waits for a lock held by a low-priority process. With inheritance, the low-priority process temporarily runs at the high priority, finishes its critical section quickly, and releases the lock.

4.8 Priority inheritance

Priority inheritance is the standard solution to priority inversion. When a high-priority process H blocks on a lock held by a low-priority process L, L temporarily inherits H's priority. L then runs at H's priority — which is higher than M's — so M cannot preempt it. L finishes its critical section, releases the lock, and reverts to its original priority. H then acquires the lock and runs.

The effect is that the duration of the inversion is bounded by the duration of L's critical section, rather than by the (potentially unbounded) time M chooses to run. In a real-time system, where the bound on the inversion directly affects the worst-case response time of H, this is essential.

Priority inheritance is a protocol, not a scheduler. It is implemented in the synchronization primitives — the locks and semaphores — rather than in the scheduling code. In POSIX, it is requested through the PTHREAD_PRIO_INHERIT protocol on a mutex; Linux implements it for the real-time mutex types. Unit 6 discusses the details of the synchronization primitives; here we note only that the protocol exists and why it is needed.

Priority inversion in the real world: Mars Pathfinder

The most famous priority-inversion incident occurred on the Mars Pathfinder mission in 1997. A low-priority meteorological task held a mutex on the spacecraft's information bus. A high-priority task — the one responsible for communicating with Earth — tried to acquire the same mutex and blocked. A medium-priority task then preempted the low-priority one and ran for an extended period, causing the high-priority task to miss its deadlines. The spacecraft began to reset itself repeatedly. The fix was to enable the priority-inheritance protocol on the mutex, which had been disabled by default in the shipped software. The engineers were able to upload the fix and the mission continued successfully.

4.9 Priority scheduling and the standard criteria

Applying the criteria from Lesson 5.1 to priority scheduling gives the following assessment. The values depend on the priority assignment, so the table reports the general tendencies.

Priority scheduling against the standard criteria
Criterion	Assessment	Notes
Average waiting time	Depends on priority function	If priority encodes burst length (SJF), optimal. Otherwise, variable.
Turnaround time	Depends on priority function	High-priority processes finish quickly; low-priority processes may wait a long time.
Response time	Excellent for high-priority processes	This is the point of priorities: important tasks respond promptly.
CPU utilization	Good	Preemptive form keeps the CPU busy; non-preemptive form may leave it idle on long bursts.
Throughput	Moderate	Preemption overhead; low-priority processes may block useful work.
Fairness	Poor without aging	Starvation is possible; aging bounds the maximum wait.
Predictability	High for high-priority processes	Low-priority processes are less predictable.

The pattern is that priority scheduling is a tool rather than a single policy. Its quality on each criterion depends on how the priorities are chosen. This is why priority scheduling appears as a component of nearly every real scheduler: it is general enough to encode a wide variety of policies, and the design work is in choosing the priority function.

4.10 Priority in Linux

Linux exposes priorities to user space through several interfaces, and it uses priorities internally for its scheduling classes. The relevant concepts are:

Nice values. The traditional UNIX interface. Nice values range from −20 (highest priority) to +19 (lowest priority). Only a privileged process can set a negative nice value; any process can increase its own nice value (lower its priority). The command nice runs a program with a specified nice value; renice changes the nice value of a running process.
Real-time priorities. The scheduling policies SCHED_FIFO and SCHED_RR use real-time priorities in the range 1 to 99, where a larger number means higher priority. Real-time tasks always have higher priority than ordinary tasks, regardless of nice value. Only privileged processes can set real-time priorities; the command chrt sets them.
Scheduling classes. Linux's scheduler is built from scheduling classes, each with its own priority domain. In descending order of priority: SCHED_DEADLINE, SCHED_FIFO and SCHED_RR (real-time), the CFS class for ordinary tasks, and SCHED_IDLE. A task in a higher class always runs before a task in a lower class, regardless of the priorities within the classes.
Priority inheritance. Linux implements priority inheritance for real-time mutexes, requested through the PTHREAD_PRIO_INHERIT protocol. The protocol is opt-in: the mutex must be created with the appropriate attribute set.

These interfaces are examined in more detail in Lesson 5.6 and in the interactive activity for this lesson. The essential point is that Linux uses priority scheduling at multiple levels — for real-time tasks, for the CFS class's internal ordering, and for the scheduling classes themselves — and that the design is more complex than any of the classical algorithms, but recognizably built on the same idea.

4.11 Common misconceptions

"Priority scheduling is just SJF with a different name."

SJF is one instance of priority scheduling, in which the priority encodes burst length. Priority scheduling is more general: the priority can encode importance, deadlines, user class, or any other criterion.

"Higher priority means a bigger number."

The convention varies. Linux's nice values use smaller numbers for higher priority; Linux's real-time priorities use larger numbers. Windows uses larger numbers for higher priority. Always check the convention.

"Priority scheduling is always preemptive."

Both preemptive and non-preemptive forms exist. The choice depends on the semantics of the priority and on the system's requirements.

"Aging eliminates starvation."

Aging bounds the maximum waiting time, but it does not eliminate the possibility of a long wait if the aging rate is slow. It converts an unbounded wait into a bounded but potentially large one.

"Priority inversion is a scheduling bug."

It is a property of the interaction between priority scheduling and mutual exclusion. It is not a bug in either mechanism; it is a design issue that requires a protocol — priority inheritance or priority ceiling — to solve.

"Priority inversion means low-priority tasks run before high-priority ones."

No. Priority inversion means a high-priority task is delayed by a low-priority task holding a resource, and a medium-priority task runs in the meantime. The low-priority task does not "run before" the high-priority one in a scheduling sense; it holds a resource the high-priority task needs.

05 Worked example

The following example compares FCFS, non-preemptive SJF, SRTF, and priority scheduling on the same workload. The priority values are chosen to illustrate the range of behaviours the priority function can produce.

Priority scheduling on a mixed workload

Four processes arrive at different times. Each has a burst length and a priority; a larger number means a higher priority.

Process	Arrival	Burst	Priority
P₁	0	8	3
P₂	1	4	1
P₃	2	9	4
P₄	3	5	2

Non-preemptive priority scheduling

At time 0, only P₁ is available; it runs to completion at time 8. At time 8, P₂ (priority 1), P₃ (priority 4), and P₄ (priority 2) are all available. The highest priority is P₃ (4), so P₃ runs from 8 to 17. Then P₄ (2) runs from 17 to 22, and finally P₂ (1) runs from 22 to 26.

| P1      | P3      | P4  | P2  |
0         8         17   22   26

Process	Arrival	Burst	Priority	Start	Completion	Turnaround	Waiting	Response
P₁	0	8	3	0	8	8	0	0
P₃	2	9	4	8	17	15	6	6
P₄	3	5	2	17	22	19	14	14
P₂	1	4	1	22	26	25	21	21
Average							16.75	10.25

Maximum waiting time: 21 (P₂). P₂ has the lowest priority and the shortest burst, but it waits the longest — the opposite of what SJF would do. This illustrates that priority scheduling is not automatically better than SJF; it produces whatever schedule the priorities dictate.

Preemptive priority scheduling

The scheduler re-evaluates at every arrival. P₁ runs from 0 to 1. At time 1, P₂ arrives with priority 1, which is lower than P₁'s priority 3, so P₁ continues. At time 2, P₃ arrives with priority 4, which is higher than P₁'s priority 3, so P₃ preempts P₁. P₃ runs from 2 to 11. At time 3, P₄ arrives with priority 2, which is lower than P₃'s priority 4, so P₃ continues. After P₃ completes at time 11, the highest-priority ready process is P₁ (priority 3, remaining 7), which runs from 11 to 18. Then P₄ (priority 2) runs from 18 to 23, and finally P₂ (priority 1) runs from 23 to 27.

|P1|  P3      |    P1     | P4  | P2  |
0  1  2        11         18   23   27

Process	Arrival	Burst	Priority	Start	Completion	Turnaround	Waiting	Response
P₁	0	8	3	0	18	18	10	0
P₃	2	9	4	2	11	9	0	0
P₄	3	5	2	18	23	20	15	15
P₂	1	4	1	23	27	26	22	22
Average							18.25	11.75

Maximum waiting time: 22 (P₂). The average waiting time is slightly worse than the non-preemptive case, because preempting P₁ to run P₃ delays P₁'s completion without helping the low-priority processes. The preemptive form is better on response time for the high-priority processes — P₃ starts immediately at time 2 — but worse on average waiting time for this particular workload.

Comparison

Metric	FCFS	SJF	SRTF	Priority (NP)	Priority (P)
Average turnaround	15.25	14.25	13.0	16.75	18.25
Average waiting	8.75	7.75	6.5	10.25	11.75
Average response	8.75	7.75	4.25	10.25	9.25
Maximum waiting	18	15	15	21	22

The comparison makes an important point: priority scheduling is not automatically better than the algorithms from the previous lessons. It produces whatever schedule the priorities dictate, and if the priorities do not encode the right criterion, the result can be worse than FCFS on the average metrics. In this example, the priorities favour P₃ (long burst) and P₄ (medium burst) over P₂ (short burst), which is the opposite of what SJF would choose.

The value of priority scheduling is not in its average metrics but in its expressiveness. It can encode any policy the system designer chooses: run real-time tasks first, run interactive tasks before batch tasks, run short jobs before long ones, or any combination. The design question is not "is priority scheduling good?" but "what priorities should we assign?"

Adding aging

Suppose the scheduler ages P₂ — the lowest-priority process — by 1 priority unit for every 5 time units it waits. P₂ arrives at time 1 with priority 1. At time 6, its priority rises to 2; at time 11, to 3; at time 16, to 4; at time 21, to 5. At time 21, P₂'s priority (5) exceeds P₄'s (2), so P₂ is scheduled before P₄ in the non-preemptive variant. Its waiting time drops from 21 to about 10, and P₄'s waiting time rises correspondingly. The average waiting time is roughly unchanged, but the maximum waiting time is reduced — the point of aging.

06 Interactive activity

Activity · implement priority scheduling and observe Linux priorities

This activity extends the simulator from Lesson 5.3 to priority scheduling, then explores how Linux exposes priorities to user space. Work through the steps in your course VM.

Extend the simulator to priority scheduling. Modify the SJF simulator so that each process has a priority instead of a burst used for selection. The simulator should select the ready process with the highest priority, with FCFS as the tie-break.
```
struct proc {
    int pid;
    int arrival;
    int burst;
    int priority;   /* larger = higher priority */
    int start;
    int completion;
    int remaining;  /* for preemptive variant */
};
```
Run the simulator on the worked-example workload and verify the numbers match the non-preemptive priority table.
Add the preemptive variant. Modify the simulator to preempt the running process whenever a higher-priority process arrives. Re-run the worked-example workload and verify the preemptive priority table.
Implement aging. Add an aging parameter to the simulator: every age_interval time units a process waits, its priority increases by 1, up to a ceiling. Run the workload with aging enabled and observe how the waiting times change. Experiment with different aging rates and ceilings.
Show that SJF is priority scheduling. Modify the simulator to set priority = −burst for each process before scheduling. Run the workload and verify that the schedule is identical to the non-preemptive SJF schedule from Lesson 5.3. This demonstrates that SJF is a special case of priority scheduling.
Observe nice values. Run two CPU-bound processes with different nice values and observe how the scheduler divides the CPU between them.
```
nice -n 0  yes > /dev/null &
nice -n 19 yes > /dev/null &
sleep 10
ps -o pid,ni,pcpu,comm -C yes
kill %1 %2
```
The process with nice 0 should receive roughly 99 percent of the CPU, and the process with nice 19 roughly 1 percent. The ratio depends on the mapping from nice value to scheduler weight, described in man 7 sched.
Observe real-time priorities. Use chrt to run a process with a real-time policy and observe its behaviour.
```
sudo chrt -f 50 sleep 5 &
chrt -p $(pgrep sleep)
sudo chrt -r 50 sleep 5 &
chrt -p $(pgrep sleep)
```
The real-time process runs at a priority that is higher than any ordinary process. Confirm that it cannot be preempted by ordinary tasks. Be careful: a runaway real-time process can lock the system. Use short-lived processes and have a root shell available to kill them if necessary.
Observe priority inheritance. Write a small program that creates a real-time mutex with the PTHREAD_PRIO_INHERIT protocol, then creates three threads of different priorities that contend for the mutex. Use strace or perf to observe the temporary priority elevation of the low-priority thread while it holds the lock. Compare to a mutex created without the protocol; the low-priority thread should not be elevated.
```
pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
pthread_mutex_init(&mutex, &attr);
pthread_mutexattr_destroy(&attr);
```
This program requires privileges to create real-time threads; run it under sudo.
Read man 7 sched carefully. Read the section on the scheduling policies, the description of the nice value, and the discussion of real-time priorities. List the policies that Linux provides, and for each one write a one-sentence description of the workload it is intended for. Then answer: which policies implement priority scheduling in the classical sense, and which implement other ideas?

Reflect: priority scheduling is the most general of the classical algorithms, but its quality depends entirely on how priorities are chosen. If you were designing a general-purpose scheduler, what priority function would you use, and why? How would you balance the competing objectives of responsiveness, fairness, and throughput? If you were designing a real-time system, how would your answer change?

07 Knowledge check

Check your understanding

Question 1

Describe priority scheduling. What are the two forms of the algorithm, and how do they differ? In what sense is SJF a special case of priority scheduling?

Show answer

Priority scheduling assigns each process a priority and always selects the ready process with the highest priority (with FCFS as the tie-break). In the non-preemptive form, a running process keeps the CPU until it blocks or terminates, even if a higher-priority process becomes ready. In the preemptive form, a newly ready higher-priority process immediately preempts the running one. The two forms differ in whether the priority is enforced at arrival or only at scheduling points. SJF is a special case of priority scheduling in which the priority is inversely proportional to the predicted next CPU burst: a short predicted burst gives a high priority, and a long predicted burst gives a low priority. If the priority is defined as priority = −burst (in a system where larger priorities run first), the priority scheduler produces exactly the SJF schedule. This relationship means that the optimality result for SJF carries over to priority scheduling when the priority function encodes burst length, and that the starvation problem of SJF is a special case of the general starvation problem of priority scheduling.

Question 2

What are internal and external priorities? Give an example of each, and explain why the distinction matters.

Show answer

Internal priorities are assigned by the kernel based on measurable properties of the process: its burst pattern, its resource usage, the ratio of CPU time to I/O time, or the time it has been waiting. For example, the multilevel-feedback queue scheduler assigns a process a higher priority if it has used less CPU time recently, which is an internal priority derived from observed behaviour. External priorities are assigned from outside the kernel, based on criteria the kernel cannot measure: the importance of the user, the funding source of the computation, or a service-level agreement. For example, a university's batch system might give faculty research jobs a higher priority than student coursework jobs, regardless of the processes' resource usage. The distinction matters because it determines what the scheduler is optimizing. Internal priorities can be updated by the kernel in response to the process's behaviour; external priorities require a policy input from outside the kernel and cannot be inferred from measurements.

Question 3

What is starvation in priority scheduling? Describe the MIT IBM 7094 incident. How does aging prevent starvation, and what trade-off does it introduce?

Show answer

Starvation is the indefinite postponement of a ready process: it never gets the CPU because higher-priority processes are always available. In priority scheduling, a low-priority process can starve if high-priority processes keep arriving or keep returning to the ready queue. The MIT IBM 7094 incident is the canonical illustration: a low-priority job was submitted in 1967 and was still in the queue when the machine was shut down in 1973, having never been scheduled in six years of round-the-clock operation. Aging prevents starvation by gradually increasing the priority of a process the longer it waits. Eventually the waiting process's priority exceeds that of newly arriving processes, and it is scheduled. Aging bounds the maximum waiting time. The trade-off is that it raises the average waiting time relative to unmodified priority scheduling: the priority policy is designed to favour some processes over others, and aging partially defeats that design by giving long-waiting low-priority processes a boost. The choice of aging rate is a policy decision that balances the worst-case bound against the average-case performance.

Question 4

Explain the priority-inversion problem using the three processes L, M, and H. Why is it a problem, and how does priority inheritance solve it?

Show answer

Priority inversion occurs when a low-priority process L holds a resource (such as a lock) that a high-priority process H needs. H blocks waiting for the resource. A medium-priority process M then becomes ready and, because M has higher priority than L, preempts L. Now M runs, L does not run, and the lock remains held by L. H — the highest-priority process in the system — is effectively blocked by M, a medium-priority process that does not even use the shared resource. The priority of H has been inverted to that of L. It is a problem because in a real-time system the delay to H is unbounded: M can run for as long as it likes, and H cannot make progress until M finishes and L resumes. Priority inheritance solves the problem by having L temporarily inherit H's priority when H blocks on the lock. L then runs at H's priority, which is higher than M's, so M cannot preempt it. L finishes its critical section, releases the lock, and reverts to its original priority. H acquires the lock and runs. The duration of the inversion is bounded by the duration of L's critical section, rather than by the unbounded time M might choose to run.

Question 5

In the worked example, priority scheduling produced a higher average waiting time than SJF. Does this mean priority scheduling is worse than SJF? Explain your answer, and describe a situation in which priority scheduling would be the right choice even though it has a higher average waiting time.

Show answer

No. The comparison in the worked example reflects the particular priority assignment used, not a general property of priority scheduling. SJF is priority scheduling with priority inversely proportional to burst length; if the priority assignment does not encode burst length, the schedule will not be optimized for average waiting time, and the metrics may be worse than FCFS or SJF. Priority scheduling is a framework, not a single algorithm, and its performance depends on the priority function chosen. A situation in which priority scheduling is the right choice despite a higher average waiting time: a real-time system with a hard-deadline task and a best-effort background task. The real-time task must run promptly when it becomes ready; the background task has no deadline and can tolerate long waits. A priority scheduler that gives the real-time task a high priority ensures that it meets its deadline, at the cost of delaying the background task. The average waiting time across the two tasks might be higher than under FCFS, but FCFS would miss the real-time deadline, which is unacceptable. The right scheduler is the one that satisfies the system's requirements, not the one that optimizes an arbitrary metric.

08 Unit discussion

Discussion prompt

Priority scheduling allows a system administrator or application developer to give some processes precedence over others. In a university's shared computing cluster, this might mean giving faculty research jobs higher priority than student coursework jobs. In a cloud platform, it might mean giving paying customers higher priority than free-tier users. In a hospital's patient records system, it might mean giving emergency-room requests higher priority than administrative queries.

Is it always legitimate to prioritize some processes over others? What are the ethical and policy considerations? Consider:

The system's purpose: a shared cluster serves many users, and prioritization is a policy decision about how to allocate a common resource.
Transparency: should users be told what priority their jobs will receive, and why?
The risk of abuse: what prevents a privileged user from monopolizing the system by setting an artificially high priority?
Starvation: even with aging, a sufficiently low-priority process can wait a very long time. Is there a priority below which a process should simply not be admitted?

Post your response to the Unit 5 discussion forum and reply to at least two classmates. Supports CLO1, CLO3, and CLO7.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for Lesson 5.5 and Lab 4. Aim to spend 60–90 minutes on it.

Trace priority scheduling by hand. For the workload below, construct the Gantt charts for non-preemptive and preemptive priority scheduling, compute the completion, turnaround, waiting, and response times for each process, and report the averages and the maximum waiting time for each algorithm.

Process	Arrival	Burst	Priority
P₁	0	6	2
P₂	1	4	4
P₃	2	8	1
P₄	3	3	3
P₅	4	5	2

Then verify your answers using the simulator from the interactive activity.

Demonstrate that SJF is a special case. For the workload in question 1, set priority = −burst for each process. Run non-preemptive priority scheduling with these priorities and verify that the result matches non-preemptive SJF. Repeat for the preemptive variant and SRTF.
Design an aging policy. For the workload in question 1, the lowest-priority process (P₃, priority 1) waits the longest. Design an aging policy that bounds its waiting time to 10 units without increasing the average waiting time by more than 20 percent. Specify the aging rate, the ceiling, and the reset policy. Run the simulator to verify your design.
Investigate nice values in Linux. Run a set of CPU-bound processes with nice values 0, 5, 10, 15, and 19 simultaneously, and measure the CPU share each one receives over a 30-second period. Plot or tabulate the relationship between nice difference and CPU share. How close is the observed ratio to the weight mapping described in man 7 sched?
```
for n in 0 5 10 15 19; do nice -n $n yes > /dev/null &; done
sleep 30
ps -o pid,ni,pcpu,comm -C yes
kill %1 %2 %3 %4 %5
```
Reproduce priority inversion. Write a small program with three threads L, M, and H of increasing priority. L acquires a mutex; H tries to acquire it and blocks; M runs for a fixed period without touching the mutex. Measure the time from H's lock attempt to H's acquisition. Then change the mutex to use PTHREAD_PRIO_INHERIT and measure again. How much is H's delay reduced?
```
pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
pthread_mutex_init(&m, &attr);
```
Run under sudo to permit real-time priorities.
Compare priority scheduling to FCFS and SJF. For the workload in question 1, compute the average waiting time under FCFS, SJF, SRTF, non-preemptive priority, and preemptive priority. Which algorithm gives the best average? Which gives the best maximum? Which gives the best response time for the highest-priority process? Comment on which algorithm you would choose for a system where all five processes have equal importance, and which for a system where P₂ is a real-time task with a hard deadline.
Read the real-time scheduling section of Silberschatz. Read section 5.6 and the discussion of priority inversion. Write a short paragraph explaining why priority inheritance is necessary for real-time systems but less important for general-purpose systems.

10 Summary

Priority scheduling assigns each process a priority and always runs the ready process with the highest priority, with FCFS as the tie-break.
The non-preemptive form runs a process to completion; the preemptive form interrupts a running process when a higher-priority process becomes ready. Preemptive priority scheduling is the more common form in systems that use priorities.
Priorities can be internal (assigned by the kernel from measurable properties) or external (assigned from outside the kernel). They can be static (fixed at creation) or dynamic (updated during the process's lifetime).
SJF is a special case of priority scheduling in which the priority is inversely proportional to the predicted burst length. The optimality of SJF and its starvation problem carry over to this special case.
Starvation is the indefinite postponement of a low-priority process. The MIT IBM 7094 incident — a job that waited six years and never ran — is the canonical illustration.
Aging mitigates starvation by gradually increasing the priority of a long-waiting process. It bounds the maximum waiting time at the cost of a slightly higher average.
Priority inversion occurs when a high-priority process H blocks on a resource held by a low-priority process L, and a medium-priority process M runs in the meantime, delaying H. The duration of the inversion is unbounded in the absence of a protocol.
Priority inheritance solves priority inversion: L temporarily inherits H's priority while holding the lock, so M cannot preempt it. The duration of the inversion is bounded by the critical section.
Linux exposes priorities through nice values (for ordinary tasks), real-time priorities (for SCHED_FIFO and SCHED_RR), and scheduling classes (which have their own priority domains). Priority inheritance is available for real-time mutexes via PTHREAD_PRIO_INHERIT.
Priority scheduling is a framework, not a single algorithm. Its quality on any metric depends on the priority function chosen, and the design work is in choosing that function.

Looking ahead

Priority scheduling and SJF both share a common weakness from the perspective of interactive systems: they are not designed to give every process a regular turn. Round robin scheduling, the subject of Lesson 5.5, addresses this directly. It gives each process a fixed time quantum and rotates through the ready queue, which guarantees that every process receives the CPU regularly. The cost is more context switches and a higher average waiting time than SJF. Lesson 5.5 examines the trade-off and the choice of quantum size.

11 References

Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 5, Sections 5.3.4 and 5.6.
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 7 and 8. Available online at ostep.org.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2, Sections 2.4.4 and 2.5.
Love, R. Linux System Programming, 2nd ed., Chapter 3.
Linux man-pages: man 7 sched, man 2 sched_setscheduler, man 1 chrt, man 1 nice, man 2 setpriority, man 3 pthread_setschedparam, man 3 pthread_mutexattr_setprotocol.
Jones, M. B. What Really Happened on Mars? The authoritative account of the Mars Pathfinder priority-inversion incident.
Sha, L., Rajkumar, R., & Lehoczky, J. P. Priority Inheritance Protocols: An Approach to Real-Time Synchronization. IEEE Transactions on Computers, 1990. The original paper on priority inheritance.