CPU Scheduling Algorithms

CPU scheduling is how the operating system decides which ready process or thread runs next on each CPU core, and for how long. Because a machine usually has far more runnable threads than cores, this decision is made thousands of times a second, and the policy behind it shapes how responsive your laptop feels, how much work a server completes, and whether a real-time controller meets its deadlines.

In interviews and exams, this is the most numerical OS topic. You will be handed a table of processes with arrival times and burst times and asked to draw a Gantt chart and compute average waiting and turnaround time for FCFS, SJF, SRTF, Priority or Round Robin. Interviewers then probe the ideas: the convoy effect, starvation and aging, how to choose a time quantum, why multilevel feedback queues exist and how Linux actually schedules. This lesson covers each algorithm with fully worked examples. Every number below was checked with a small simulator.

Background: bursts and the ready queue

Most processes alternate between two kinds of activity: computing on the CPU (a CPU burst) and waiting for I/O (an I/O burst). A text editor has tiny CPU bursts between long waits for keystrokes; a video encoder has very long CPU bursts.

 I/O-bound:  CPU|--io wait--|CPU|--io wait--|CPU|--io wait--
 CPU-bound:  CPU CPU CPU CPU CPU CPU|io|CPU CPU CPU CPU CPU

• An I/O-bound process has many short CPU bursts.
• A CPU-bound process has few, long CPU bursts.

When a process is ready to run, its PCB sits in the ready queue. The short-term scheduler (CPU scheduler) picks one from that queue, and the dispatcher performs the context switch and jumps to the process's code. The time the dispatcher takes is the dispatch latency.

A scheduling decision can happen at four moments:

1. A process switches from running to waiting (it starts I/O or calls wait).
2. A process switches from running to ready (a timer interrupt ends its time slice).
3. A process switches from waiting to ready (its I/O completes).
4. A process terminates.

Preemptive versus non-preemptive scheduling

• Non-preemptive (cooperative) scheduling makes decisions only at moments 1 and 4: once a process has the CPU, it keeps it until it blocks or finishes. Simple, with fewer context switches, but one long job can hold up everyone.
• Preemptive scheduling can also take the CPU away at moments 2 and 3, for example when the time slice expires or a more important process becomes ready. All modern general-purpose operating systems (Linux, Windows, macOS) are preemptive, which needs a timer interrupt and careful protection of shared kernel data.

Scheduling criteria and formulas

To compare algorithms you need precise measures. For each process, you are usually given:

• Arrival time (AT): when it enters the ready queue.
• Burst time (BT): how much CPU time it needs.

From a schedule you compute:

• Completion time (CT): when it finishes.
• Turnaround time (TAT): total time from arrival to completion. TAT = CT - AT
• Waiting time (WT): total time spent waiting in the ready queue. WT = TAT - BT (assuming no I/O inside the burst).
• Response time (RT): time from arrival until it first gets the CPU. RT = first start - AT. This is what an interactive user notices.

And for the whole system:

• CPU utilization: the fraction of time the CPU is busy. utilization = busy time / total time. Real systems aim for roughly 40% to 90% depending on load.
• Throughput: completed processes per unit time. throughput = number of processes / total time.

No algorithm optimizes all of these at once. Reducing average waiting time can starve long jobs; reducing response time with tiny time slices hurts throughput through context-switch overhead.

How to solve a scheduling problem

Use the same procedure every time:

1. Sort processes by arrival time.
2. Walk through time. At each decision point, list who is in the ready queue and apply the algorithm's rule.
3. Draw the Gantt chart: a timeline showing which process runs in each interval. Include idle gaps if no process is ready.
4. Read off each process's completion time and first start time.
5. Compute TAT, WT and RT per process in a table, then average.
6. Sanity check: the last completion time should equal total burst time plus any idle time; and the sum of waiting times must be the same whichever formula you use.

State tie-breaking rules explicitly, since different textbooks choose differently. In this lesson, ties are broken by earlier arrival, then by lower process number.

First-Come, First-Served (FCFS)

FCFS runs processes in order of arrival, each to completion. It is non-preemptive and implemented with a simple FIFO queue.

Worked example 1: the convoy effect

Three processes arrive at time 0 in the order P1, P2, P3.

Gantt chart for order P1, P2, P3:

|            P1            | P2 | P3 |
0                         24   27   30

Now suppose the same jobs had arrived in the order P2, P3, P1:

| P2 | P3 |            P1            |
0    3    6                         30

Waiting times become P2 = 0, P3 = 3, P1 = 6, so the average waiting time is 9 / 3 = 3, and the average turnaround is (3 + 6 + 30) / 3 = 13.

The same work, but average waiting time drops from 17 to 3 just by running short jobs first. This is the convoy effect: short processes stuck behind one long process, like cars behind a slow truck on a single-lane road. In a real system it also hurts devices: while a CPU-bound process holds the CPU, all the I/O-bound processes finish their I/O and wait, leaving the disks idle, and then they all rush through the CPU and the CPU sits idle.

Worked example 2: FCFS with arrival times

We will reuse this process set for several algorithms so you can compare them directly.

Total burst time is 8 + 4 + 9 + 5 = 26.

|    P1    |  P2  |     P3     |   P4   |
0          8      12           21       26

Averages: TAT = (8 + 11 + 19 + 23) / 4 = 61 / 4 = 15.25; WT = (0 + 7 + 10 + 18) / 4 = 35 / 4 = 8.75. In a non-preemptive algorithm, response time equals waiting time, because each process waits once and then runs to completion. Throughput is 4 processes in 26 time units, about 0.154 per unit, and CPU utilization is 100% because the CPU is never idle.

Pros: simple, fair in the "first in line" sense, no starvation. Cons: convoy effect, poor average waiting time, bad for interactive use.

Shortest Job First (SJF)

SJF picks the ready process with the smallest next CPU burst. The non-preemptive version runs that process to completion.

SJF is provably optimal for average waiting time among non-preemptive schedules when all jobs are available together: moving a short job ahead of a long one reduces the short job's wait by more than it increases the long job's wait.

Worked example 3: SJF (non-preemptive)

Same process set as example 2.

1. Time 0: only P1 has arrived, so P1 runs. Being non-preemptive, it runs until 8.
2. Time 8: P2 (4), P3 (9) and P4 (5) are all waiting. Shortest is P2, which runs 8 to 12.
3. Time 12: P3 (9) and P4 (5). P4 runs 12 to 17.
4. Time 17: P3 runs 17 to 26.

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

TAT = 57 / 4 = 14.25; WT = 31 / 4 = 7.75. Better than FCFS's 8.75, even though P1 still had to run first because it was alone at time 0.

The catch: you do not know the next burst

The scheduler cannot see the future. Real systems predict the next burst from past bursts using an exponential average:

τ(n+1) = α · t(n) + (1 - α) · τ(n)

where t(n) is the actual length of the most recent burst, τ(n) was the previous prediction, and α (between 0 and 1) controls how much weight recent history gets. With α = 0.5, recent and past history count equally.

Worked numbers: let α = 0.5 and the initial guess τ(0) = 10. The process then has actual bursts 6, 4, 6, 4.

Setting α = 0 ignores recent behavior entirely; α = 1 uses only the last burst.

Starvation

SJF's weakness is starvation: if short jobs keep arriving, a long job may wait indefinitely. It is also unfair to long jobs by design.

Shortest Remaining Time First (SRTF)

SRTF is preemptive SJF. Whenever a new process arrives, the scheduler compares its burst with the remaining time of the running process and switches if the newcomer is shorter.

Worked example 4: SRTF

Same process set.

1. Time 0: only P1. P1 starts (remaining 8).
2. Time 1: P2 arrives with 4. P1 has 7 left. 4 < 7, so P2 preempts P1.
3. Time 2: P3 arrives with 9. P2 has 3 left. P2 continues.
4. Time 3: P4 arrives with 5. P2 has 2 left. P2 continues and finishes at 5.
5. Time 5: remaining times are P1 = 7, P3 = 9, P4 = 5. P4 runs and, with no new arrivals, finishes at 10.
6. Time 10: P1 (7) beats P3 (9). P1 runs 10 to 17.
7. Time 17: P3 runs 17 to 26.

|P1|  P2  |   P4   |    P1     |     P3     |
0  1      5        10          17           26

TAT = 52 / 4 = 13.0; WT = 26 / 4 = 6.5; RT = 17 / 4 = 4.25.

Check P1's waiting time by hand: it waited from 1 to 10, which is 9 units, matching WT = 17 - 8 = 9. Its response time is 0 because it started immediately. This is why you should use WT = TAT - BT for preemptive algorithms: P1 waited once it was preempted, not before it first ran.

SRTF gives the minimum average waiting time of all the algorithms here, at the cost of more context switches, the same prediction problem as SJF, and the same starvation risk for long jobs.

Priority scheduling

Each process gets a priority number, and the CPU goes to the highest-priority ready process. Conventions differ; in this lesson (as in Linux nice values and many textbooks), a lower number means higher priority. Priority scheduling can be non-preemptive or preemptive. SJF is a special case where priority is the predicted burst length.

Worked example 5: Priority, non-preemptive and preemptive

Non-preemptive.

1. Time 0: only P1. It runs to 10.
2. Time 10: all others have arrived. Highest priority is P2 (1), runs 10 to 11.
3. Time 11: P5 (2) runs 11 to 16.
4. Time 16: P3 (4) runs 16 to 18.
5. Time 18: P4 (5) runs 18 to 19.

|      P1      |P2|   P5   | P3 |P4|
0              10 11       16   18 19

TAT = 64 / 5 = 12.8; WT = 45 / 5 = 9.0.

Preemptive.

1. Time 0: P1 starts.
2. Time 1: P2 (priority 1) arrives and preempts P1 (3). P2 finishes at 2.
3. Time 2: P1 (3) and P3 (4) are ready. P1 resumes.
4. Time 3: P4 (5) arrives; lower priority than P1, no change.
5. Time 4: P5 (2) arrives and preempts P1. P5 runs 4 to 9. P1 has 10 - 1 - 2 = 7 left.
6. Time 9: P1 (3) runs 9 to 16.
7. Time 16: P3 runs 16 to 18; then P4 runs 18 to 19.

|P1|P2| P1 |   P5   |     P1      | P3 |P4|
0  1  2    4        9             16   18 19

TAT = 54 / 5 = 10.8; WT = 35 / 5 = 7.0; RT = 29 / 5 = 5.8. The high-priority processes P2 and P5 never wait.

Starvation and aging

In a busy system, a steady stream of high-priority processes can keep a low-priority one waiting forever. This is starvation (or indefinite blocking).

The standard fix is aging: gradually raise the priority of a process the longer it waits. For example, improve a waiting process's priority by one level every 15 minutes, so even the lowest-priority process eventually becomes the highest and runs. The same idea appears in many forms, including the periodic priority boost in MLFQ below.

Round Robin (RR)

Round Robin is FCFS with preemption by time. Each process gets a fixed time quantum (time slice), typically 10 to 100 milliseconds in textbook descriptions. If it has not finished when the quantum expires, the timer interrupt preempts it and it goes to the back of the ready queue. RR is designed for time-sharing: every process gets a turn quickly.

One detail changes answers, so state it: when a new process arrives at the same moment a quantum expires, does the newcomer join the queue before or after the preempted process? The common convention, used here, is new arrivals first, then the preempted process.

Worked example 6: Round Robin with quantum 2

Same process set as examples 2 to 4 (P1 0/8, P2 1/4, P3 2/9, P4 3/5).

Trace the ready queue (front on the left):

Note the last step: P3 runs 23 to 25 for one quantum, finds the queue empty and simply continues 25 to 26, so it is shown as one block.

|P1|P2|P3|P1|P4|P2|P3|P1|P4|P3|P1|P4| P3 |
0  2  4  6  8  10 12 14 16 18 20 22 23   26

TAT = 77 / 4 = 19.25; WT = 51 / 4 = 12.75; RT = 8 / 4 = 2.0.

With quantum 4, the Gantt chart becomes:

|  P1  |  P2  |  P3  |  P4  |  P1  |  P3  |P4|P3|
0      4      8      12     16     20     24 25 26

Averages: TAT = 18.25, WT = 11.75, RT = 4.5.

Compare all the algorithms on this one set:

The lesson in this table: Round Robin has the worst turnaround and waiting time but the best response time. That is exactly its purpose. An interactive user cares that the system reacts quickly, not when a batch job finishes.

Choosing the quantum

• Quantum too large: RR degenerates into FCFS, with poor response time.
• Quantum too small: the CPU spends a big share of its time on context switches. If a switch costs s and the quantum is q, the fraction of time lost is s / (q + s). With s = 0.1 ms, a 4 ms quantum loses 0.1 / 4.1, about 2.4%, while a 1 ms quantum loses 0.1 / 1.1, about 9.1%.
• Rule of thumb: make the quantum longer than most CPU bursts (a common textbook guideline is about 80% of bursts), so interactive processes finish their burst within one slice and block for I/O on their own, and much larger than the context-switch time.

Multilevel Queue scheduling

Different processes have different needs. A multilevel queue scheduler splits the ready queue into several separate queues, each with its own algorithm, and assigns each process permanently to one queue based on its type.

 highest priority
 +-------------------------------------+
 | real-time processes      (priority) |
 +-------------------------------------+
 | system processes         (priority) |
 +-------------------------------------+
 | interactive processes    (RR)       |
 +-------------------------------------+
 | batch processes          (FCFS)     |
 +-------------------------------------+
 lowest priority

Between queues, the scheduler uses either:

• Fixed priority: never run a lower queue while a higher one has work. Simple, but lower queues can starve.
• Time slicing between queues: for example, 80% of CPU time to the interactive queue (shared by RR) and 20% to batch (FCFS).

The weakness is rigidity: a process that is placed in the wrong queue, or whose behavior changes, stays there.

Multilevel Feedback Queue (MLFQ)

MLFQ fixes that rigidity by letting processes move between queues based on observed behavior. It approximates SJF without needing to know burst lengths in advance: it learns which processes are short or interactive.

Typical rules:

1. There are several queues with decreasing priority. Higher queues have shorter quanta.
2. The scheduler always runs a process from the highest non-empty queue (RR within a queue).
3. A new process enters the top queue.
4. If a process uses its entire quantum, it is CPU-hungry: it is demoted one level.
5. If it gives up the CPU before its quantum expires (it blocks for I/O), it stays at its level. Interactive processes therefore stay near the top and get fast response.
6. Priority boost: periodically, move every process back to the top queue. This prevents starvation and lets a process whose behavior changed (a CPU-heavy phase ending) be treated as interactive again.

Rule 4 has a loophole a clever program can exploit: run for 99% of its quantum, then do a tiny I/O to avoid demotion. Many implementations close this by tracking total CPU time used at a level, regardless of how it was split, and demoting once that allowance is spent.

Worked example 7: an MLFQ trace

Three queues: Q0 with quantum 4, Q1 with quantum 8, Q2 with FCFS. A process arriving in a higher queue preempts a lower-queue process; a preempted process goes to the back of its own queue and gets a fresh quantum next time.

1. 0 to 4: A runs in Q0, uses its whole quantum, is demoted to Q1 (16 left).
2. 4 to 8: B runs in Q0, uses its whole quantum, is demoted to Q1 (2 left). Q1 is now [A, B].
3. 8 to 10: A runs in Q1. At 10, C arrives in Q0 and preempts A, which has 14 left and goes to the back of Q1: [B, A].
4. 10 to 13: C runs in Q0 and finishes (completion 13).
5. 13 to 15: B runs in Q1 and finishes (completion 15).
6. 15 to 23: A runs a full Q1 quantum of 8 and is demoted to Q2 (6 left).
7. 23 to 29: A runs in Q2 and finishes (completion 29).

|  A   |  B   | A  |  C  | B  |     A (Q1)    |  A (Q2)  |
0      4      8    10    13   15              23         29

The short, late-arriving C finished with zero waiting, just as SJF would have done, without the scheduler ever being told C was short.

MLFQ is the classic basis for interactive schedulers: classic BSD Unix, Solaris's time-sharing class and Windows' dynamic priority boosts use variations of the idea. Its parameters (number of queues, quanta, boost interval) are hard to tune, which is a fair point to raise in an interview.

Linux: the Completely Fair Scheduler

For normal (non-real-time) tasks, Linux used the Completely Fair Scheduler (CFS) from kernel 2.6.23 (2007) until kernel 6.6 (2023), when it was replaced by the EEVDF (Earliest Eligible Virtual Deadline First) scheduler, which keeps CFS's core ideas of weighted fairness and virtual runtime. CFS remains the version most interview questions mean.

The idea: ideal fair sharing

Imagine a perfect CPU that could run all n runnable tasks simultaneously, each at 1/n speed. CFS tries to approximate that. It tracks for each task how much CPU time it has received, and always runs the task that has received the least.

vruntime

Each task has a virtual runtime (vruntime): the CPU time it has used, scaled by its priority weight.

vruntime += actual runtime × (weight of nice 0 / weight of this task)

A nice-0 task has weight 1024. Each nice step changes the weight by roughly a factor of 1.25, which works out to about a 10% change in CPU share relative to a competing task. A higher-priority (lower nice) task has a larger weight, so its vruntime grows more slowly, so it is picked more often.

Worked example: two CPU-bound tasks, one at nice 0 (weight 1024) and one at nice 5 (weight 335 in the kernel's table). Their CPU shares are 1024 / (1024 + 335) ≈ 75.3% and about 24.7%. Over time their vruntime values stay close together, even though the nice-0 task gets three times the real CPU time.

The red-black tree

CFS keeps runnable tasks in a red-black tree (a self-balancing binary search tree) ordered by vruntime:

                    [ v=120 ]
                   /         \
            [ v=95 ]          [ v=160 ]
            /      \               \
     [ v=80 ]    [ v=101 ]       [ v=200 ]
        ^
   leftmost = smallest vruntime = runs next (cached pointer)

• Pick next: the leftmost node, whose pointer is cached, so selection is O(1).
• Insert / remove a task: O(log n).

There is no fixed time quantum. CFS computes each task's slice from a target latency (a period, a few milliseconds by default, in which every runnable task should run once), divided in proportion to weights, with a minimum granularity so slices never become too tiny when there are many tasks.

Why it favors interactive tasks naturally

A task that sleeps waiting for input does not accumulate vruntime. When it wakes, it has a small vruntime compared with CPU hogs, so it is placed near the left of the tree and runs almost immediately. (CFS clamps a waking task's vruntime to near the current minimum so a long sleeper cannot then monopolize the CPU.) No special "interactive" detection is needed.

Linux scheduling classes

CFS is only one class. Linux checks classes in strict priority order:

On multi-core machines, each CPU has its own run queue, and the kernel periodically load balances tasks between them, trying to respect cache affinity (keeping a task on the core whose cache already holds its data).

Real-time scheduling

In a real-time system, each task has a deadline, and correctness means meeting it. Typical tasks are periodic: a task with period P and computation time C must run for C units once in every period, finishing before the next period starts. A task's utilization is C / P.

Rate Monotonic (RM)

Rate Monotonic scheduling assigns static priorities: the shorter the period, the higher the priority. It is preemptive. RM is optimal among fixed-priority algorithms.

A sufficient (not necessary) test: n tasks are guaranteed schedulable under RM if total utilization U ≤ n(2^(1/n) - 1). That bound is 1.0 for one task, about 0.828 for two, about 0.780 for three, and approaches ln 2, about 0.693, as n grows.

Earliest Deadline First (EDF)

EDF assigns dynamic priorities: at every moment, run the task whose current deadline is nearest. On a single CPU, EDF can schedule any periodic task set with U ≤ 1 (deadlines equal to periods), so it can use the processor fully.

Worked example 8: RM misses, EDF succeeds

Total U = 2/5 + 4/7 ≈ 0.971. That is above the RM bound for two tasks (0.828), so RM is not guaranteed, and below 1, so EDF is.

Rate Monotonic (T1 has the shorter period, so higher priority):

time:  0    2         5    7  8
       | T1 |   T2    | T1 |T2|
                           ^ T2's deadline at 7: 1 unit still left -> MISS

T1 runs 0 to 2. T2 runs 2 to 5 (3 of its 4 units). At 5, T1's second job arrives and preempts T2, running 5 to 7. T2's deadline at 7 passes with 1 unit unfinished.

EDF:

time:  0    2           6    8          12   14
       | T1 |    T2     | T1 |    T2    | T1 | ...

T1 (deadline 5) runs 0 to 2. T2 (deadline 7) runs 2 to 6; at 5, T1's new job has deadline 10, later than T2's 7, so T2 is not preempted and finishes at 6. T1 runs 6 to 8. T2's second job (arrived 7, deadline 14) runs 8 to 12, not preempted by T1's job arriving at 10 with deadline 15. T1 runs 12 to 14. Simulating the full hyperperiod of 35 (the least common multiple of 5 and 7) shows no missed deadline.

Trade-offs: RM is simpler, uses fixed priorities that hardware and RTOSes support directly, and degrades predictably under overload (the lowest-priority tasks miss first). EDF achieves higher utilization but needs dynamic priorities, and under overload it can miss deadlines in a cascading, hard-to-predict way.

Multiprocessor scheduling, briefly

With several cores, new questions appear:

• Shared queue versus per-CPU queues: one global queue is simple but becomes a lock bottleneck; Linux and Windows use per-CPU queues with load balancing.
• Processor affinity: moving a task to another core loses its warm cache, so schedulers prefer to keep it where it was (soft affinity). Programs can request hard affinity with sched_setaffinity or taskset on Linux.
• Load balancing: push migration moves tasks off overloaded cores; pull migration lets an idle core steal work.
• NUMA (non-uniform memory access): on multi-socket servers, memory attached to a task's own socket is faster, so the scheduler also tries to keep tasks near their memory.

Algorithm summary

Interview questions

Q1. What is the difference between preemptive and non-preemptive scheduling?

In non-preemptive scheduling, a running process keeps the CPU until it blocks or terminates. In preemptive scheduling, the OS can take the CPU away, typically when a timer interrupt ends the time slice or a higher-priority process becomes ready. Preemption gives better response time and protects against runaway processes, at the cost of more context switches and the need to synchronize shared data.

Q2. Define turnaround time, waiting time and response time.

Turnaround time is completion time minus arrival time: the total time the process spent in the system. Waiting time is turnaround time minus burst time: the time spent in the ready queue. Response time is the time from arrival until the process first gets the CPU, which matters most to interactive users.

Q3. What is the convoy effect?

It happens under FCFS when one long CPU-bound process holds the CPU and many short processes queue behind it, greatly increasing average waiting time. It also hurts utilization, since I/O-bound processes finish their I/O and wait while devices sit idle. Running short jobs first, as in SJF, or preempting with Round Robin avoids it.

Q4. Why is SJF optimal, and why is it hard to implement?

For non-preemptive scheduling of jobs available together, running the shortest first minimizes average waiting time, because each swap of a short job ahead of a long one reduces total waiting. The problem is that the OS does not know the length of the next CPU burst. It must predict it, typically with an exponential average of previous bursts.

Q5. How does SRTF differ from SJF?

SRTF is the preemptive version of SJF. When a new process arrives with a burst shorter than the remaining time of the running process, it preempts it. This gives the lowest average waiting time but causes more context switches and can starve long processes.

Q6. What is starvation and how does aging fix it?

Starvation is when a ready process waits indefinitely because others are always chosen first, as can happen to low-priority processes in priority scheduling or long jobs in SJF. Aging gradually increases the priority of a process the longer it waits, so eventually it becomes the highest priority and runs.

Q7. How do you choose the time quantum in Round Robin?

It should be large compared with the context-switch time, so overhead stays small, and large enough that most CPU bursts complete within one quantum. If it is too large, Round Robin behaves like FCFS with poor response time; if too small, context switching dominates. A common guideline is that about 80% of CPU bursts should be shorter than the quantum.

Q8. Does a smaller quantum always improve response time?

It reduces the time before each process first runs, but it adds context-switch overhead, which slows everything, and it generally increases turnaround time because every process is chopped into more pieces. Past a point, the overhead dominates and the system does less useful work.

Q9. What is MLFQ and how does it approximate SJF?

A multilevel feedback queue has several priority levels with increasing quanta. New processes start at the top; a process that uses its full quantum is demoted, while one that blocks early stays high. Short and interactive processes therefore finish or stay in high-priority queues, while CPU-bound ones sink, approximating shortest-job-first without knowing burst lengths. A periodic priority boost prevents starvation.

Q10. How does the Linux CFS work?

CFS gives each task a virtual runtime that increases with the CPU time it uses, scaled by its weight from its nice value. Runnable tasks sit in a red-black tree ordered by virtual runtime, and the scheduler always runs the leftmost task, the one that has had the least weighted CPU time. Time slices come from a target latency divided by weight rather than a fixed quantum. Since kernel 6.6, Linux uses EEVDF, which builds on the same virtual-runtime idea.

Q11. Why does CFS use a red-black tree?

It needs to repeatedly find the task with the smallest virtual runtime and to insert and remove tasks efficiently as they block and wake. A red-black tree keeps operations at O(log n) and stays balanced, and caching the leftmost node makes picking the next task O(1).

Q12. Compare Rate Monotonic and EDF scheduling.

Rate Monotonic gives fixed priorities by period, shorter period meaning higher priority, and guarantees schedulability only if utilization is below n(2^(1/n) - 1), about 69% to 83%. EDF gives dynamic priorities by nearest deadline and can schedule any set with utilization up to 100% on one CPU. RM is simpler and more predictable under overload; EDF uses the CPU better.

Q13. Which algorithm gives the best response time and which gives the best average waiting time?

Round Robin generally gives the best response time, since every process gets the CPU within one cycle of the queue. SRTF gives the minimum average waiting time, with non-preemptive SJF optimal among non-preemptive algorithms. Interactive systems favor response time, so they use Round Robin variants or fair schedulers.

Q14. What is processor affinity?

Processor affinity is the tendency, or a requirement, to keep a process on the same core. Moving it to another core loses the cached data in the old core's caches, so schedulers prefer soft affinity, and programs can set hard affinity with calls such as sched_setaffinity on Linux. It trades load balance against cache performance.

Key takeaways

• Memorize TAT = CT - AT, WT = TAT - BT, RT = first run - AT; use WT = TAT - BT for preemptive algorithms.
• FCFS is simple but suffers the convoy effect; SJF minimizes average waiting time but needs burst prediction and can starve long jobs.
• SRTF is preemptive SJF; it gives the lowest average waiting time at the cost of more switches.
• Priority scheduling risks starvation; aging is the standard fix. Always state whether a lower number means higher priority.
• Round Robin trades turnaround time for response time; the quantum must be much larger than context-switch time but not so large that RR becomes FCFS.
• MLFQ learns which processes are interactive by demoting those that use full quanta, and boosts priorities periodically to prevent starvation.
• Linux CFS runs the task with the smallest weighted virtual runtime from a red-black tree; EEVDF replaced it in kernel 6.6.
• Real-time scheduling targets deadlines: Rate Monotonic (static, bound about 69% to 83%) and EDF (dynamic, up to 100%).

Next lesson

Continue with Synchronization.