How Does Thread Scheduling Work?
Learn how thread scheduling works, CFS virtual runtime, priority inversion and inheritance, with a pthread scheduling code example.
Expected Interview Answer
Thread scheduling is the mechanism by which the OS (or a user-space runtime) decides which of the runnable threads gets CPU time next, typically driven by priorities, time quanta, and readiness state stored per thread rather than per process.
At the kernel level, each schedulable thread has its own entry in the scheduler’s ready queue with a priority and state (ready, running, blocked); on a timer interrupt or when a thread blocks or yields, the scheduler picks the next thread according to its policy — for example Linux’s Completely Fair Scheduler tracks virtual runtime per thread and always picks the thread that has received the least CPU time proportionally, while real-time policies use strict priority. Because threads within the same process share an address space, the scheduler can dispatch different threads of the same process onto different CPU cores concurrently, unlike the older model of a single schedulable process. Thread scheduling also interacts with priority inversion, where a low-priority thread holding a lock blocks a high-priority thread waiting on it while a medium-priority thread runs freely, which is commonly solved with priority inheritance. In systems using user-level threads (N:1 or M:N models), a second layer of scheduling happens in user space, where the runtime chooses which user thread runs atop the kernel thread(s) it owns.
- Explains why threads, not just processes, are the true unit of CPU scheduling on modern OSes
- Connects to real algorithms like CFS virtual runtime
- Surfaces priority inversion, a classic real-time systems interview topic
- Distinguishes kernel-level scheduling from user-level (library) scheduling
AI Mentor Explanation
Thread scheduling is like a franchise’s rotation policy for who bowls next, tracked per individual bowler rather than per team: the captain keeps a running tally of overs bowled by each bowler and always calls up whoever has bowled the least relative to their quota, similar to tracking virtual runtime. If a fast bowler holding the only spare ball is delayed by a slow over from a lower-ranked bowler, a star bowler waiting for that ball is stuck behind them — a rotation-priority inversion the captain fixes by temporarily bumping the slow bowler’s priority.
Step-by-Step Explanation
Step 1
Ready queue entry
Each schedulable thread has its own ready-queue entry, priority, and state, independent of its sibling threads.
Step 2
Scheduling event
A timer interrupt, a thread blocking, or a thread yielding triggers the scheduler to re-evaluate.
Step 3
Selection policy
The scheduler picks the next thread using its policy, e.g. least accumulated virtual runtime under CFS, or strict priority for real-time threads.
Step 4
Dispatch to core
The chosen thread is dispatched, potentially to a different CPU core than its sibling threads of the same process, enabling true parallelism.
What Interviewer Expects
- Understanding that threads, not just processes, have independent scheduler entries
- Ability to name a real scheduling policy (e.g. CFS virtual runtime, priority-based)
- Explanation of priority inversion and priority inheritance as its fix
- Awareness that user-level thread models add a second, invisible scheduling layer
Common Mistakes
- Thinking only processes are scheduled and threads passively ride along
- Not knowing what priority inversion is or how to fix it
- Assuming a single global run queue is used on all modern multi-core OSes
- Confusing thread scheduling with process scheduling as identical concepts
Best Answer (HR Friendly)
“Thread scheduling is how the operating system decides, moment to moment, which individual thread — not just which program — gets to run on the CPU next. Modern schedulers try to keep things fair over time and can even run different threads of the same program on different CPU cores at once, though care has to be taken so a high-priority thread never gets stuck waiting behind a lower-priority one that is hogging a shared resource.”
Code Example
#include <pthread.h>
#include <sched.h>
#include <stdio.h>
void *worker(void *arg) {
int policy;
struct sched_param param;
pthread_getschedparam(pthread_self(), &policy, ¶m);
printf("thread %ld running with priority %d\n",
(long) arg, param.sched_priority);
return NULL;
}
int main(void) {
pthread_t t;
pthread_attr_t attr;
struct sched_param param;
pthread_attr_init(&attr);
pthread_attr_setschedpolicy(&attr, SCHED_FIFO); /* real-time, priority-based */
param.sched_priority = 10;
pthread_attr_setschedparam(&attr, ¶m);
pthread_attr_setinheritsched(&attr, PTHREAD_EXPLICIT_SCHED);
pthread_create(&t, &attr, worker, (void *) 1);
pthread_join(t, NULL);
return 0;
}Follow-up Questions
- What is priority inversion and how does priority inheritance solve it?
- How does the Completely Fair Scheduler decide which thread runs next?
- How does thread scheduling differ between SCHED_OTHER and SCHED_FIFO on Linux?
- How does user-level thread scheduling interact with kernel-level scheduling under an M:N model?
MCQ Practice
1. On a modern multi-core OS, what is the actual unit the scheduler dispatches to a CPU core?
The scheduler operates on individual threads, each with its own ready-queue entry, letting different threads of one process run on different cores.
2. What is priority inversion?
Priority inversion happens when a low-priority thread holds a resource a high-priority thread needs, and a medium-priority thread preempts the low-priority one, effectively blocking the high-priority thread indefinitely.
3. What is a common fix for priority inversion?
Priority inheritance temporarily boosts the priority of the thread holding the needed resource to that of the highest-priority waiter, preventing indefinite blocking.
Flash Cards
What is thread scheduling? — The mechanism by which the OS decides which runnable thread gets CPU time next, per-thread rather than per-process.
What does Linux’s CFS track per thread? — Virtual runtime — accumulated CPU time weighted by priority, used to pick the least-served thread next.
What is priority inversion? — A high-priority thread blocked by a low-priority thread holding a resource, while a medium-priority thread runs freely.
What fixes priority inversion? — Priority inheritance — temporarily raising the resource holder’s priority to that of the waiting high-priority thread.