CPU Scheduling

A CPU scheduler chooses the ready process or thread that runs next on a CPU. The rule it follows is its policy. The dispatcher carries out the choice by switching execution to the selected job. A different policy can use the same switching mechanism.

Follow the state changes

A running job owns a CPU. A ready job could run but is waiting for a turn. A blocked job is waiting for an event, such as the completion of a disk read. Only ready jobs are candidates for selection.

Suppose an editor starts a disk read while a compiler is ready. The editor moves from running to blocked, so the compiler can run. When the read finishes, an interrupt makes the editor ready again. It does not necessarily run immediately: the policy must choose between it and other ready work.

Scheduling decisions occur when a job blocks, finishes, becomes ready, or is interrupted and returned to ready. Voluntary yielding also releases the CPU. Preemption means taking the CPU from a job that could have continued running; the job keeps its saved state and can resume later.

A timer interrupt lets the kernel enforce a time slice, even if a program loops without yielding. A completed I/O can also trigger preemption by making a more favored task ready. Linux, Windows, and macOS use preemptive scheduling.

Work comes in bursts

Programs alternate between CPU bursts, when they compute, and periods spent waiting for I/O. A CPU-bound program such as an encoder has long CPU bursts. An I/O-bound program such as an editor often computes briefly and then waits. Giving an editor prompt service after a keypress can help responsiveness without giving it much total CPU time.

The dispatcher saves the old task's state, restores the chosen task's registers, and resumes its instruction stream in user mode. Dispatch latency is the time taken to hand over execution. Switching also disturbs caches and the translation lookaside buffer, or TLB, which caches address translations. The next task may need to refill them, so register-saving time is only part of the cost.

Three scheduling timescales

The long-term scheduler admits submitted jobs and controls how many are in the system. The medium-term scheduler can suspend whole processes by swapping them out of memory and later restoring them. The short-term scheduler selects the next ready task and acts frequently. General-purpose systems rely mainly on this last role; batch systems and clusters may also control admission explicitly.

Start a policy comparison with simple CPU-only jobs and known lengths. Then vary one feature: unequal lengths expose FIFO's delays, later arrivals expose the limits of non-preemption, I/O creates opportunities to overlap work, and unknown lengths require prediction or feedback.

A schedule tells you when jobs run. A metric tells you which part of that schedule matters. Record each job's arrival, first run, and completion before calculating any averages.

Separate the three times

Turnaround time measures the whole interval from arrival to completion. Response time measures the delay until the first run. Waiting time adds every interval spent ready but not running.

For a CPU-only job, turnaround equals waiting plus CPU run time. With I/O, blocked time is also part of turnaround, so subtracting CPU time alone would overcount waiting. Response uses the first-run definition here; a user-facing service may separately measure time to its first output.

Work through a FIFO timeline

A arrives at 0 ms and needs 8 ms of CPU time. B arrives at 1 ms and needs 4 ms. C arrives at 2 ms and needs 2 ms. With no switching cost, FIFO gives:

• A: 0–8 ms.
• B: 8–12 ms.
• C: 12–14 ms.

The average turnaround is $\frac{8+11+12}{3}=\frac{31}{3}\approx 10.33$ ms. Average response and waiting are both $\frac{0+7+10}{3}=\frac{17}{3}\approx 5.67$ ms. They coincide because each job runs once without interruption. Under preemption, a job may wait again after its first turn, so waiting can exceed response.

Measure the whole workload

Throughput counts completed jobs per unit of elapsed time. The schedule completes three jobs in 14 ms, about 214.29 jobs/s. CPU utilization is busy CPU time divided by elapsed time; it is 100% here because the CPU never idles. Specify the measurement interval: adding an idle period after completion would change both figures.

High utilization can still accompany long waits. It also need not mean all busy time is useful application work: real measurements may count switching and other kernel work as busy time. State whether an overhead calculation measures busy time or useful work.

Choose what to optimize

Batch work often values average turnaround. Interactive work values a quick response. Shared services need fair access as well as throughput. Starvation means an eligible job waits indefinitely, so a good average alone cannot establish fair treatment.

Inspect individual delays and the tail of the distribution. A 99th-percentile response time describes the delay at or below which roughly 99% of observations fall; a few severe delays can disappear inside a low average. Always subtract the job's own arrival time, and count its running intervals as service, never as waiting.

FIFO, also called first come, first served or FCFS, runs ready jobs in arrival order. It is non-preemptive: a later arrival cannot interrupt a running CPU burst. For CPU-only examples, each selected job runs to completion.

See the convoy effect

A, B, and C arrive together. A needs 60 ms; B and C need 6 ms each. With A first, FIFO runs A 0–60, B 60–66, and C 66–72. Turnaround times are 60, 66, and 72 ms, averaging 66 ms. The small jobs spend most of their lives waiting behind A. This is the convoy effect.

Shortest job first (SJF) selects the shortest next CPU burst among ready jobs and does not preempt it. With the same arrivals, it runs B 0–6, C 6–12, then A 12–72. Average turnaround becomes $\frac{6+12+72}{3}=30$ ms. Total CPU work is still 72 ms; the improvement comes from finishing short jobs sooner.

Why does this help? If a long burst runs immediately before a short burst, both jobs wait for all earlier work. Swapping just these two cuts the short job's delay by the long burst's length while increasing the long job's delay only by the short burst's length. Repeating such swaps puts the bursts in ascending order. With all jobs arriving together and known lengths, SJF minimizes average turnaround and waiting; first-run response also equals waiting in this non-preemptive CPU-only case.

Restrict the choice to ready jobs

Now A arrives at 0 ms, while B and C arrive at 10 ms. At 0 ms, A is the only choice. Non-preemptive SJF runs A 0–60, B 60–66, C 66–72. Turnaround times are 60, 56, and 62 ms, averaging about 59.33 ms. SJF cannot act on a future job or interrupt a burst it already started.

FIFO avoids starvation when jobs ahead eventually release the CPU. SJF can starve a long waiting job if short work keeps arriving.

Predict a burst

The next CPU burst is usually unknown. An exponential average combines the latest measured burst with the previous prediction:

Here, $t_n$ is the measured burst, ${\tau }_n$ the previous prediction, and $\alpha$ a weight between 0 and 1. Starting with 10 ms and using $\alpha =0.5$, a measured 6 ms gives a prediction of 8 ms. A subsequent 4 ms gives 6 ms; another 6 ms leaves it at 6 ms. At zero weight, measurements have no effect; at weight one, only the newest measurement matters. The predicted quantity is CPU burst length, not program file size or line count.

Shortest time-to-completion first (STCF), also called shortest remaining time first or SRTF, is preemptive SJF. At an arrival or completion, compare the CPU time each ready job still needs. A newcomer interrupts the current job when it needs less time than the current job has left.

Compare remaining time

A needs 60 ms and arrives at 0 ms. B and C each need 6 ms and arrive at 10 ms. A runs for 10 ms, leaving 50 ms. At 10 ms, B wins because 6 ms is less than 50 ms; C has the same length, so arrival order and then the name break the tie.

The timeline is A 0–10, B 10–16, C 16–22, A 22–72. Turnaround times are A 72 ms, B 6 ms, and C 12 ms, averaging 30 ms. Response times are 0, 0, and 6 ms, averaging 2 ms. Non-preemptive SJF on these arrivals averages about 59.33 ms turnaround and 35.33 ms response.

Always subtract service already received. Comparing a new 12 ms burst with A's original 60 ms would be wrong if A had only 5 ms left. STCF would finish A first. With known CPU-only lengths and zero switching cost, STCF minimizes average turnaround across arbitrary arrivals. Long jobs can still starve under a continuing stream of shorter work.

When all CPU-only jobs arrive together, SJF and STCF give the same ordering. The running shortest job only gets shorter, so no waiting job becomes a reason to preempt it.

Use another job's blocked time

A blocked job cannot use the CPU. Its I/O wait is an opportunity to run other ready work, even under a non-preemptive policy. Preemption matters again when completed I/O makes a short burst ready while another job is running.

Consider A with five 10 ms CPU bursts and a 10 ms disk read after each of its first four bursts. B needs one 50 ms CPU burst. Both arrive at 0 ms. If the CPU idles during A's reads and delays B until A finishes, A completes at 90 ms and B at 140 ms.

Treat each returning burst of A as short ready work:

• A runs 0–10; its read occupies 10–20 while B runs.
• A returns for 20–30; B has 40 ms left, so A's 10 ms wins.
• B runs 30–40 during the next read. The alternation repeats.
• A's last burst runs 80–90; B finishes its last 10 ms during 90–100.

A still finishes at 90 ms, but B finishes at 100 ms. The CPU performs 100 ms of work in 100 ms of elapsed time. Disk activity and CPU activity overlap; the CPU does not execute A while A is blocked. A device interrupt marks A ready when each read ends, after which STCF compares its new burst with B's remaining work.

Round robin (RR) keeps a FIFO ready queue and gives its front job at most one quantum, or time slice. A job that finishes or blocks leaves the CPU early. A job still ready when its slice expires moves to the back.

Trace turns before calculating times

A, B, and C arrive at 0 ms and each need 9 ms. With a 3 ms quantum, RR runs:

• First round: A 0–3, B 3–6, C 6–9.
• Second round: A 9–12, B 12–15, C 15–18.
• Final round: A 18–21, B 21–24, C 24–27.

First runs are at 0, 3, and 6 ms, so average response is 3 ms. Completions are at 21, 24, and 27 ms, so average turnaround is 24 ms. FIFO gives average response 9 ms and average turnaround 18 ms. Here RR starts everyone promptly but postpones the first completed job until 21 ms.

RR divides CPU access while jobs compete; it does not equalize completion times. A short job can finish on its first turn. With a fixed population of $n$ ready jobs and quantum $q$, the wait between turns is at most $(n-1)q$ without switching costs. Ongoing arrivals, other priority classes, and restricted CPU eligibility change the setting of that bound.

Handle arrivals at a slice boundary

Use arrival order, then alphabetical order for ties. A job arriving exactly when a slice expires joins before the preempted job. With A arriving at 0 ms needing 8 ms, B at 1 ms needing 4 ms, and C at 2 ms needing 2 ms, a 2 ms quantum gives A 0–2, B 2–4, C 4–6, A 6–8, B 8–10, A 10–14.

The final A interval contains two consecutive turns with no competitor. Response times are 0, 1, and 2 ms; turnaround times are 14, 9, and 4 ms. Their averages are 1 ms and 9 ms. When a blocked job returns in basic RR, it joins for a fresh turn; it does not reserve unused CPU time while blocked.

Make the quantum worth its cost

A very large quantum makes RR behave like FIFO for bursts shorter than that quantum. A tiny quantum creates many dispatches and repeated cache disruption. In a simple timer-based implementation the quantum is a whole number of timer periods.

For switching cost $s$ after each useful slice of length $q$, the approximate overhead fraction is $\frac{s}{q+s}$. A 0.1 ms switch costs about 9.1% with a 1 ms slice, but about 0.99% with a 10 ms slice. Longer slices amortize switching cost by spreading it over more useful work.

A common sizing heuristic is to let most bursts, for example about 80%, end within one slice. The right choice depends on measured burst lengths and the response delays the workload can tolerate. Count switches between tasks separately from timer events that simply let the same sole ready task continue.

A priority scheduler runs the highest-priority ready job. Equal-priority jobs can follow FIFO or round robin. In a preemptive version, a newly ready higher-priority job takes the CPU immediately; in a non-preemptive version it waits until the current job releases it.

Read the direction of the scale

Priority numbers have no universal direction. Use smaller numbers for higher priority in the textbook examples here. Linux nice values follow that direction, but Windows priority levels and Linux real-time priorities use larger numbers for higher priority.

A, B, and C arrive at 0 ms with bursts of 4, 3, and 5 ms and priorities 2, 1, and 3. Non-preemptive priority scheduling runs B 0–3, A 3–7, and C 7–12. Their waiting times are 0, 3, and 7 ms, averaging about 3.33 ms; turnarounds are 3, 7, and 12 ms, averaging about 7.33 ms.

An internal priority comes from measured behavior, such as CPU usage or I/O waits. SJF derives rank from predicted burst length. An external priority comes from a person, such as an administrator who marks a backup as less urgent. Neither choice ensures that low-priority work receives time under a continuous supply of higher-priority work.

Raise priority with waiting

Aging gradually raises the priority of a waiting job. If the rank improves by one every 100 ms, a job starting at priority 20 reaches the top priority 0 after 2 s of ready waiting. Higher rank brings it into competition with favored work; tie rules determine turns among jobs at the same rank.

Starvation is a lack of progress caused by repeated selection of other work. Aging tackles it by changing rank over time. It serves a different purpose from predicting burst length: an old long job may deserve a turn even though its burst remains long.

Follow the dependency in priority inversion

A high-priority job H may be blocked on a lock held by low-priority job L. A medium-priority job M can preempt L. Now H cannot proceed, even though M has lower priority than H: L must run to release the lock first. This is priority inversion.

With priority inheritance, L temporarily inherits H's priority while it holds the lock H needs. M can no longer keep L off the CPU. L runs, releases the lock, and loses the inherited priority; H becomes ready and can run.

Raising H's own priority does not release its lock: H remains blocked. The key is to let the thread that can satisfy the dependency execute. In 1997, Mars Pathfinder encountered a priority-inversion problem that was addressed by enabling priority inheritance.

A multi-level feedback queue (MLFQ) combines priorities with round robin. Its goal is to approximate short-job service and keep interactive work responsive without being told each job's future run time. Recent CPU use supplies the feedback.

Apply the queue rules

Each ready job belongs to one priority queue. The basic accounting version follows four rules:

1. Choose the highest-priority queue containing ready work.
2. Within that queue, rotate equal-priority jobs with round robin.
3. Put a new job in the top queue.
4. Demote a job when it consumes its CPU allotment at its current level, counting usage across all turns and I/O interruptions.

A quantum limits one turn. An allotment limits total service at a priority level. A level may allow several quanta before demotion. At the bottom level a demotion leaves the job in the bottom queue.

This gives a new job a chance to finish quickly. A job that repeatedly consumes CPU time reveals a longer demand and moves down. A short burst that blocks consumes little allotment, so interactive jobs tend to stay high for longer.

Trace a long job and a newcomer

Use queues Q2, Q1, and Q0, with Q2 highest, 10 ms quanta and 10 ms allotments at each level, and no boost during this trace. A needs 200 ms and arrives at 0 ms. It runs in Q2 from 0–10, in Q1 from 10–20, and in Q0 afterward.

At 100 ms, A has received 100 ms of CPU time. B arrives needing 20 ms. B enters Q2 and preempts A, then runs 100–110 in Q2. It has consumed that level's allotment and drops to Q1. Q1 outranks A's Q0, so B runs 110–120 and finishes. A resumes at 120 and completes its remaining 100 ms at 220 ms. B's turnaround is 20 ms despite arriving after a much longer job.

Track A's remaining work while B runs: it stays at 100 ms. Elapsed time advances during B's service, but A receives no CPU service then.

Separate waiting from CPU consumption

An editor that runs for 1 ms and waits for input uses a 10 ms allotment over ten such bursts. Blocked time does not count against the CPU allotment. Under strict accounting, those short bursts still add up, so the editor eventually moves down unless a priority boost resets it first.

An early MLFQ rule demoted only jobs that used a whole uninterrupted quantum. A job that yielded just before expiry kept its priority. That rule made interactive work responsive but also allowed deliberate gaming. Counting cumulative CPU use closes that loophole.

Lower queues run whenever all higher queues have no ready work. A higher-priority job that is blocked does not prevent lower-priority jobs from using the CPU. Under sustained high-priority demand, lower work needs an additional anti-starvation mechanism, supplied by periodic boosts.

Feedback creates useful separation, but a job's past behavior can stop representing its current needs. A long computation may later become interactive. Meanwhile, a bottom-queue job can wait indefinitely if higher queues stay busy.

Reconsider every job periodically

A priority boost moves all jobs back to the top queue after a period $S$. It lets waiting jobs share the top queue and lets the scheduler learn changed behavior afresh. A boosted CPU-bound job later consumes its allotment and moves down again.

Consider the early MLFQ rules: two interactive jobs always yield before a full 10 ms slice and together keep Q2 busy. A CPU-bound job waits in Q0. Without boosts it gets no service. In a repeating schedule where a boost every 100 ms gives it one 10 ms top-level turn before it is demoted and higher work fills the rest, it receives 10% of the CPU. That percentage comes from this trace; a boost does not assign a general fixed share.

A long boost period leaves long waits between opportunities. A very short period repeatedly resets CPU-bound work and weakens the advantage of interactive work. Designs have used periods around one second, but the period is a tuning choice based on workload behavior and response goals.

Account across yields

A separate problem is gaming. Under the early full-slice rule, a program can run for 9 ms, request a 1 ms I/O, and repeat. It never uses a whole 10 ms slice at once, so it retains top priority while consuming nearly all available CPU time.

With a cumulative 10 ms allotment, the first burst consumes 9 ms and leaves 1 ms. After the I/O, one further millisecond exhausts the allotment, and the job is demoted during its second burst. An I/O request changes state; it does not erase service already received. The accounting rule prevents this tactic even without a boost.

Tune the levels

Choose the number of queues, each queue's quantum, each level's allotment, and the boost period. Top queues usually use short quanta, for example 10 ms, to alternate quickly among interactive jobs. Lower queues can use much longer quanta, sometimes hundreds of milliseconds, to reduce switching during sustained computation.

Allotment can grow independently of quantum. A level with a 5 ms quantum and 15 ms allotment can allow three full turns before demotion. Increasing allotment delays classification as long-running; increasing quantum lengthens an individual turn.

Solaris's time-sharing design illustrates table-based feedback: its classic configurable table has 60 priority levels, with quanta ranging from about 20 ms at high priority to a few hundred milliseconds at low priority. Classic BSD designs instead computed priority from recent CPU usage that decays over time. Both let old CPU use lose influence, so a thread's distant history does not permanently determine its treatment.

Proportional-share scheduling aims to divide CPU service according to assigned shares. In lottery scheduling, each runnable job owns tickets. A random winning ticket chooses the job for the next equal-length slice. A job's chance of winning is its tickets divided by all runnable tickets.

Locate a winning ticket

A holds 100 tickets, B 50, and C 250. Number the 400 tickets from 0 through 399. A owns 0–99, B owns 100–149, and C owns 150–399. A draw of 300 selects C.

A list-based implementation draws a number and accumulates ticket counts. The running totals are 100 after A, 150 after B, and 400 after C. Stop at the first total strictly greater than the draw. Using “greater than or equal” would assign boundary tickets incorrectly: draw 100 belongs to B. Putting larger ticket holders first reduces the average length of this list search.

Distinguish expectation from a guarantee

With A holding 75 tickets and B 25, A's expected share is 75%. In 100 independent equal-slice draws with both runnable, A expects 75 wins. The standard deviation is:

$\sqrt{100\times 0.75\times 0.25}\approx 4.33$ slices.

A result around 71–79 wins is within roughly one standard deviation of the mean; it is not a guaranteed range. Short runs can depart markedly from the intended 3:1 ratio. As the observation window grows, the relative random variation becomes smaller. Lottery provides probabilistic fairness, not an exact finite-window split or a bounded wait for the next turn.

For two equal-ticket jobs with equal CPU demands, the unfairness metric U divides the earlier completion time by the later one. The ratio reaches 1 when they complete together and is smaller when one completes much earlier. This completion ratio is especially variable for short lottery-scheduled jobs.

Allocate tickets across users and dependencies

Ticket currency lets a user divide an assigned global entitlement locally. User X has 200 global tickets and assigns 300 local tickets to X1 and 100 to X2. Of 400 local tickets, X1 has three quarters, giving 150 global tickets; X2 gets 50. User Y has 100 global tickets for Y1. The total is 300, so X1 receives an expected 50%, X2 about 16.67%, and Y1 about 33.33% of the contested CPU.

Ticket transfer temporarily lends a client's tickets to a server doing work for it, then returns them when the request completes. This follows the work dependency. Ticket inflation lets cooperating jobs increase their own ticket counts to request more service. It requires trust or limits: unrestricted inflation lets a greedy job dilute everyone else's shares.

Lottery needs ticket totals but no record of how far each job is ahead in service. A new job simply contributes its tickets to the runnable pool. Assigning the tickets remains a policy choice; the random draw enforces that choice in expectation. A blocked job's tickets do not compete for a slice it cannot use.

Stride scheduling turns ticket shares into a deterministic sequence. Each runnable job has a stride, calculated as a large constant divided by its tickets, and a pass value that records its weighted progress. Choose the lowest pass, run that job for one equal-length slice, then add its stride to its pass.

Calculate the strides

A has 50 tickets, B 25, and C 100. With constant 1,000, their strides are 20, 40, and 10. More tickets produce a smaller stride. A favored job's pass rises slowly, so it becomes the minimum more frequently.

Start all passes at zero and break ties alphabetically. Keep the tuple in the fixed order A, B, C:

Only the selected job's pass changes. In seven slices, A receives two turns, B one, and C four: the exact ratio 50:25:100. At the shared pass value of 40, each has advanced through the same amount of weighted service. Between such alignments, short-window shares need not be exact.

Keep real service and virtual progress separate

The pass is an ordering value, not elapsed time or a count of tickets. B's large stride makes it wait while A and C catch up in pass. It still receives its intended one-seventh share over this repeating cycle. Adding the ticket count to the pass would reverse the design: the highest-ticket job would make the biggest jump and be selected less often.

The constant controls the scale of strides, not the intended ticket ratios. Integer implementations need enough precision to avoid distorting those ratios through rounding. Comparisons and updates must use a consistent scale.

Place a newcomer sensibly

Suppose established jobs have passes around 4,000. A new job starting at zero would win repeatedly while catching up, even if it had few tickets. Initialize its pass relative to current system progress, such as the minimum current pass, so it does not collect service for time before it arrived.

Linux virtual runtime uses the related idea of charging weighted progress for actual CPU service. In both designs, a higher entitlement makes that progress grow more slowly, keeping the task competitive for later service.

Linux's fair schedulers track weighted CPU service. The Completely Fair Scheduler (CFS), introduced in Linux 2.6.23 in 2007, chose the runnable task with the smallest virtual runtime. Linux began replacing that selection rule with EEVDF in 6.6 in 2023.

Divide service by weight

A nice value ranges from −20, most favored, to +19, least favored. Nice 0 has weight 1024. Each step toward a larger nice value reduces weight by a factor of about 1.25. Example weights are 3121 at nice −5, 820 at nice 1, 335 at nice 5, 110 at nice 10, and 15 at nice 19.

Nice 0 against nice 1 gives $\frac{1024}{1024+820}\approx 0.555$, about 55.5% against 44.5%. Shares depend approximately on the difference in nice values: $3121\mathrm{/}1024$ and $335\mathrm{/}110$ are both about 3.05. Nice +19 competing with nice 0 still receives about 1.4% in this simple two-task model.

Classic CFS distributes a target scheduling latency by weight:

For weights 1024, 1024, and 335, the total is 2383. A 48 ms target period gives about 20.63 ms to each heavier task and 6.75 ms to the lighter one. These are illustrative parameters, not universal kernel defaults. With four equal tasks, 48 ms gives 12 ms each. With ten, 4.8 ms each would fall below an illustrative 6 ms minimum granularity, so the period must grow.

Charge virtual progress

CFS increases a running task's virtual runtime by:

A weight-1024 task gains one virtual millisecond per real millisecond. A weight-335 task gains about 3.06. Charging lighter tasks faster makes them wait sooner while heavier tasks receive more real service.

Classic CFS orders queued runnable tasks in a red-black tree by virtual runtime. Insertion and removal cost logarithmic time; a cached pointer to the leftmost node makes finding the minimum constant time. Blocked tasks leave this runnable tree. Wake-up placement limits old sleep from becoming an unlimited claim on catch-up service.

Choose among eligible tasks with EEVDF

Earliest Eligible Virtual Deadline First keeps weights and virtual service accounting. A task has positive lag when it is owed service and negative lag when it has received more than its entitlement. Tasks with nonnegative lag are eligible. EEVDF selects the eligible task with the earliest virtual deadline.

The deadline combines a request's virtual start with its requested service length scaled into virtual time. It is a service-ordering value, not a promised wall-clock completion time. A shorter requested slice can give an eligible task an earlier deadline and improve latency without increasing its long-run weight share. Current Linux supports slice requests through sched_setattr().

Several CPUs help only when there is parallel work. A single thread runs on one logical CPU at a time; several threads or independent programs can use several CPUs together. A scheduler must choose both which job runs and where it runs.

Share scheduling responsibility

In symmetric multiprocessing (SMP), CPUs run kernel code and make scheduling decisions for themselves. In asymmetric multiprocessing, one main processor coordinates scheduling while others run assigned work. Central control is simpler, but the main processor can become a bottleneck. General-purpose systems use SMP.

Simultaneous decisions require coordination. If two CPUs remove tasks from a shared ready queue, its updates must be synchronized so neither loses an entry nor selects the same queued task twice. More CPUs can increase contention for that shared structure.

Preserve useful cache contents

Cores have small fast caches, typically private L1 and L2 caches and a larger L3 shared by several cores. Temporal locality means reusing recently accessed data. Spatial locality means accessing nearby data, such as consecutive array elements.

A sorting thread on core 0 fills its caches and TLB. If it resumes there after a brief preemption, many needed entries may still be present. On core 3, it may need to fetch the same data again from a shared cache or memory. Cache affinity is the scheduler's tendency to keep a thread near the CPU it recently used. The exact benefit depends on what remains cached and on the cache-sharing topology.

Separate coherence from synchronization

Cache coherence prevents cores from indefinitely using conflicting cached copies of a single memory location. Bus snooping is one implementation idea: caches observe traffic and invalidate or update copies when another core writes. Larger systems can use other coherence mechanisms.

Coherence does not turn several instructions into one atomic operation. If two CPUs both read a queue length, alter entries, and write the length back, coherent individual reads and writes still allow harmful interleavings. The scheduler needs locks or another synchronization method for the whole update. A lock's shared cache line can itself move between cores as they compete for it.

Read the hardware layout

Intel calls its SMT implementation Hyper-Threading. Two busy threads on sibling logical CPUs contend for one core's resources; two logical CPUs are not equivalent to two independent physical cores. A NUMA migration may also move computation away from the memory it uses, even when cache warm-up is brief.

Moving a thread to an idle CPU can eliminate a long queue delay. Keeping it in place can preserve locality. Compare those costs using the actual workload: affinity is a performance preference, while an explicit affinity mask restricts which CPUs are allowed at all.

A multiprocessor scheduler needs somewhere to hold ready work. A single shared queue makes work easy to find. Separate per-CPU queues reduce shared contention and preserve placement, but can leave one CPU overloaded while another is idle.

Compare queue designs

In single-queue multiprocessor scheduling, all CPUs draw from one shared queue. If jobs can run on every CPU, waiting work naturally fills an idle CPU. A shared lock protects the queue, so increasing CPU count can turn that lock into a bottleneck.

With five round-robin jobs A–E on four CPUs, one sequence assigns A, B, C, D in the first round; E, A, B, C in the second; and D, E, A, B in the third. A runs on CPU 0, then 1, then 2. The machine stays busy, but A repeatedly changes private caches. Affinity rules can retain most placements while moving selected jobs to balance work.

Notice unequal shares

In multi-queue multiprocessor scheduling, each CPU schedules its own queue. Suppose CPU 0 has A and C and CPU 1 has B and D, all CPU-bound and sharing locally in round robin. Initially each job gets half a CPU. When C finishes, A receives all of CPU 0 while B and D still receive half of CPU 1 each.

The machine remains fully utilized, but the jobs no longer get equal shares. If A also finishes, CPU 0 becomes idle even though B and D are ready. Moving one of them to CPU 0 gives both a full CPU and uses previously idle capacity.

With three equal CPU-bound jobs and two CPUs, equal long-run service is two-thirds of a CPU per job. A fixed placement leaves one job alone and two sharing. Periodically rotating which job is alone can approach the equal split. No one thread executes on both CPUs at once.

Decide when to migrate

Migration moves a task to another CPU's queue. Work stealing is a pull strategy: a CPU with little work examines a busier CPU's queue and takes work. Frequent checks create synchronization traffic; rare checks leave imbalance unresolved. Stealing also has to respect CPU eligibility and memory locality.

Compare expected saved waiting time with migration cost. A long queue on one CPU and an idle compatible CPU create a strong reason to move. A tiny temporary queue difference may disappear before cold-cache costs are recovered.

Linux's O(1) and CFS designs used per-CPU run queues; Linux balances across hardware scheduling domains, accounting for shared cores and sockets. The alternative BF Scheduler used a single queue. Users can constrain placement with taskset or sched_setaffinity() on Linux and SetThreadAffinityMask() on Windows. A restricted affinity mask can explain why a ready task does not use a CPU that appears idle.

Linux schedules threads, called tasks in the kernel. A task's scheduling policy, nice value, group controls, and CPU affinity answer different questions about when and where it runs.

Read the policy first

The normal policies have static priority 0. Real-time FIFO and RR use 1–99, where 99 is highest. A FIFO task continues until it blocks, yields, or is preempted by higher-priority work. RR adds turns among equal-priority tasks; sched_rr_get_interval() reports its quantum. These names describe Linux policies: normal fair scheduling is not the textbook equal-slice RR algorithm.

Change shares and placement

Nice runs from −20 to +19, with default 0. Larger values reduce fair-class weight, by roughly a factor of 1.25 per step. On a typical launch at nice 0, nice -n 10 make starts a build at nice 10; -n is an adjustment to inherited niceness. renice -n 5 -p 4321 sets the target process to nice 5. A user can make their own work less favored; increasing priority requires suitable privilege or an allowed resource limit.

taskset -c 0,1 ./app permits a program to run on CPUs 0 and 1. It does not create a second thread or promise either CPU exclusively. ps -o pid,cls,ni,rtprio,comm shows policy-related fields, while top helps observe priority, nice, and CPU consumption.

chrt -f 50 ./app selects FIFO real-time priority 50. Use real-time settings only in a controlled environment: a busy high-priority thread can delay the shell and essential system work. Default real-time bandwidth limits reserve some time for normal work, but do not make every such workload responsive. Precedence changes access to CPU service, not the speed of an instruction.

Distinguish group weight from quota

In cgroup v2, cpu.weight ranges from 1 to 10000, default 100, and divides contested fair-class CPU capacity among active sibling groups. Weights 200 and 100 give about two-thirds and one-third of one CPU when both groups are busy. If the second becomes idle, the first can use all available capacity.

cpu.max sets a bandwidth cap. The value "50000 100000" permits 50 ms of aggregate CPU time per 100 ms period, equivalent to half a CPU on average. Several threads can consume that budget in parallel and exhaust it sooner in elapsed time. A capped group can be throttled even when spare CPU capacity exists.

Place the names in history

Linux 2.6.0's O(1) scheduler used priority arrays and interactivity feedback. CFS arrived in 2.6.23 in 2007. Linux 6.6 in 2023 began the transition to EEVDF selection in the fair class. Since Linux 6.12 in 2024, sched_ext supports dynamically loaded BPF scheduling policies on configured kernels. If such a scheduler fails or stalls runnable work, the kernel restores built-in scheduling.

Windows schedules ready threads by priority from 0 through 31, with larger numbers higher. Equal-priority ready threads rotate in round robin. A newly ready higher-priority thread preempts a lower one without waiting for its quantum to end. Priority 0 belongs to the zero-page thread, which clears free pages.

Find base priority from two settings

A thread's base priority depends on its process's priority class and its own relative thread level. Process classes are Idle, Below normal, Normal, Above normal, High, and Realtime. Thread levels include Idle, Lowest, Below normal, Normal, Above normal, Highest, and Time critical.

Time critical gives 15 outside Realtime class and 31 within it. Idle thread level gives 1 outside Realtime and 16 within it. These boundary levels are special table entries, so adding a fixed offset to every class would give wrong results.

Follow a temporary boost

Priorities 1–15 are the variable range; 16–31 are the real-time range. A thread starts with dynamic priority equal to base priority. For variable-range threads, events such as input or completion of a wait can temporarily raise dynamic priority. Threads with real-time base priorities receive no such boosts.

Suppose a thread with base priority 8 is boosted to 14. If it keeps computing, its dynamic priority falls one level after each complete quantum: 13 after the first, 12 after the second, and 8 after the sixth. The boost does not permanently change base priority and does not decay below that base.

This is feedback: recently unblocked work gets prompt service, while sustained CPU use loses the temporary advantage. Windows also uses temporary boosts for long-waiting ready threads to address starvation. Such a boost can help a low-ranked lock holder make progress, but it is a different mechanism from lock-specific priority inheritance.

Recognize related designs

Solaris's time-sharing class is a table-driven MLFQ design. FreeBSD's ULE uses per-CPU run queues and compares sleep with running behavior to identify interactive threads. These systems share the idea of adapting service to observed behavior without using identical queue rules.

macOS provides quality-of-service (QoS) classes, including user-interactive, user-initiated, default, utility, and background. They describe the urgency of work. On Apple silicon, QoS helps the system place work across performance and efficiency cores. Programs communicate the work's importance; the operating system chooses placement according to policy and available hardware.

Real schedulers combine feedback, priorities, fairness, and affinity. A Windows Realtime class has stronger precedence, not a guaranteed faster computation or a complete real-time correctness guarantee.

Choose the workload's objective before choosing a scheduler. A batch queue may value quick completion of many small jobs. An editor needs prompt service after input. A shared server needs a defensible allocation among users or groups.

Match the mechanism to the objective

Compare policies on identical inputs

A arrives at 0 ms needing 8 ms, B at 1 ms needing 4 ms, and C at 2 ms needing 2 ms. Ignore switching cost. FIFO runs A, B, C. SJF also starts A, but then runs C before B. STCF runs A 0–1, B 1–2, C 2–4, B 4–7, A 7–14. RR uses a 2 ms quantum with boundary arrivals queued before the expired task.

STCF wins both metrics on this workload because each newly arriving shorter job immediately runs. RR gives a quick start without knowing burst lengths. With equal-length simultaneous arrivals, FIFO can have lower average turnaround than RR. A ranking on one workload is evidence about that workload.

Choose an evaluation method

Deterministic modeling calculates a fixed trace by hand. It gives exact results for its inputs and makes decisions easy to inspect, but often leaves out dispatch and cache costs. Queueing models describe arrival and service patterns using distributions and predict average behavior.

For a stable system in steady state, Little's law links average population $n$, arrival rate $\lambda$, and average residence time $W$:

At 14 jobs/s and 0.5 s average time in the system, the average population is 7 jobs. Keep the boundary consistent: a ready-queue population needs time waiting in that queue, while a whole-system population needs time in the whole system. Convert units before multiplying.

Simulation executes a scheduler model, often against a recorded workload trace. It can test complicated arrival and blocking patterns, but its conclusions depend on the model and the chosen traces. Implementation measures the scheduler in a real operating system and includes actual overhead; it takes more effort and still needs representative workloads and repeatable measurements.

Inspect throughput, utilization, individual and tail delays, fairness, and energy use alongside means. On a multiprocessor, a busy machine can still divide service unevenly or waste time refilling caches. Compare policies using the same observation window and workload, then vary the workload features that matter to the intended users.