Processes and CPU Scheduling
From process states and the PCB to FCFS, SJF, round robin, and CFS: the rules an operating system uses to hand out the CPU.
Contents
A CPU core runs exactly one task at any instant, yet process states and the scheduler make hundreds of them look like they are running at once.
Processes and the PCB
A process is a program in execution. Launching the same executable twice creates two separate processes, each with its own memory space and execution flow. The operating system tracks each one through a data structure called the PCB (process control block).
The PCB holds everything needed to pause a process and later resume it at exactly the same point. The main fields look like this.
| Field | What it holds |
|---|---|
| Process ID (PID) | Unique identifier for the process |
| Process State | Current state (Ready, Running, and so on) |
| Program Counter | Address of the next instruction to execute |
| CPU Registers | Register values (saved on pause, restored on resume) |
| Memory Info | Page tables, segment information |
| I/O Status | Open files, allocated I/O devices |
| Scheduling Info | Priority, scheduling queue pointers |
The two fields that matter most here are the program counter and the CPU registers. Saving just those two is enough to restart a paused process at the same point, and that is the basis of the context switching discussed below.
The five process states
A process moves through five states from creation to termination. Transitions happen only on specific events.
The diagram shows process state transitions as arrows. The label on each arrow is the event that causes the transition.
| State | Description | Backend example |
|---|---|---|
| New | Process being created | Right after the fork() system call |
| Ready | Waiting for the CPU | Ready to handle a request, waiting in the run queue |
| Running | Executing on the CPU | Running HTTP request handling logic |
| Waiting | Waiting for I/O to finish | Waiting on a database query response or a file read |
| Terminated | Execution finished | Process exits after sending the response |
The transition to watch is the path from Running back to Ready. It happens not because the work finished but because a timer interrupt takes the CPU away, and that forced reclaim is what prevents one process from monopolizing the core. Waiting on I/O is different: the process drops into Waiting and gives up the CPU voluntarily.
Context switching
Context switching saves the state of the running process into its PCB and restores the next process's state from its PCB. Context here means the information needed to resume execution, such as register values and the program counter.
A switch happens at four moments.
- Time slice expiry: the process used up its allotted time under preemptive scheduling
- I/O request: the process requested I/O and moved into Waiting
- Interrupt: a hardware or software interrupt fired
- System call: the process invoked work that requires switching to kernel mode
The problem is that the switch itself accomplishes no work; it is pure overhead. The cost comes from the following.
| Cost component | Details |
|---|---|
| Saving and restoring registers | Dozens of CPU registers written to memory and loaded back |
| TLB flush | Each process has a different virtual address space, so the address translation cache is invalidated |
| Cache pollution | The new process's data enters L1, L2, and L3 and evicts the previous data |
| Pipeline flush | Instructions in flight in the CPU pipeline are discarded |
TLB stands for translation lookaside buffer, hardware that caches the result of translating a virtual address into a physical one and thereby cuts translation cost. When the process changes, the address space changes and the cache has to be emptied, which accounts for a large share of the switching cost. A single context switch is generally estimated at 1 to 10 microseconds. At tens of thousands of switches per second, a non-trivial share of total CPU time leaks away as overhead.
Processes and threads
A thread is a unit that carries only an execution flow inside a process. Threads in the same process share memory, so a thread switch does not change the address space and is cheaper than a process switch.
| Property | Process | Thread |
|---|---|---|
| Memory space | Independent (its own address space) | Shared (the same process heap and data) |
| Stack | Independent | Independent per thread |
| Creation cost | High (memory duplication) | Low (only a new stack) |
| Context switching | High (needs a TLB flush) | Low (same address space) |
| Communication | Requires IPC (pipes, shared memory) | Direct memory access |
| Robustness | One dying does not affect other processes | One dying can terminate the whole process |
The last two rows are the decision criteria. Fast communication and low switching cost favor threads; fault isolation favors processes. Thread pools are common for the same reason: reusing pre-created threads instead of spawning one per request cuts both creation and switching cost.
The question CPU scheduling answers
The scheduler picks which of the processes queued in Ready runs next. What counts as a good choice depends on the metric.
| Metric | Meaning | Direction |
|---|---|---|
| CPU utilization | Fraction of time the CPU does real work | Maximize |
| Throughput | Processes completed per unit of time | Maximize |
| Waiting time | Total time spent in the Ready queue | Minimize |
| Response time | Time from submission to first response | Minimize |
| Turnaround time | Total time from submission to completion | Minimize |
These metrics cannot all be satisfied at once. Interactive services care more about response time, while batch jobs care about throughput and turnaround time, so the policy follows the goal.
Scheduling splits into two broad families. Non-preemptive scheduling waits for the running process to yield the CPU on its own; preemptive scheduling can stop a running process with a timer. Preemptive scheduling responds better at the cost of more frequent context switches.
Scheduling algorithms
Each of the classic policies reduces to a single selection rule. What matters for comparison is the problem each rule creates.
- FCFS (first come, first served): gives the CPU in arrival order. A long job at the front makes shorter jobs behind it wait, which is the convoy effect.
- SJF (shortest job first): runs the process with the shortest remaining execution time first. It gives the theoretically shortest average waiting time, but execution time is hard to know in advance and long jobs can be pushed back indefinitely, which is starvation.
- Round robin: gives every process the same time quantum and cycles through them. Too small a quantum inflates switching overhead; too large a quantum degenerates into FCFS. Common values fall in the 10 to 100 millisecond range.
- Priority scheduling: runs higher-priority processes first. Low-priority processes may never run, which is starvation again, mitigated by aging, where priority rises gradually as waiting time grows.
Starvation is the shared weakness of SJF and priority scheduling, and aging is the correction that patches it.
Modern operating system schedulers are built on the MLFQ (multilevel feedback queue). It maintains several Ready queues at different priorities and moves processes between them based on their behavior.
As the diagram shows, jobs that hold the CPU for a long time sink to lower queues, while interactive jobs that yield frequently on I/O stay in the upper queue. The strength of MLFQ is that it classifies work by observed behavior, with no need to declare the job type in advance.
The same workload under three policies
The differences show up clearly in a three-process calculation. A arrives at 0 and needs 5 units of execution, B arrives at 1 and needs 3, C arrives at 2 and needs 1. The round robin quantum is 2.
| Policy | Execution intervals |
|---|---|
| FCFS | A(0-5), B(5-8), C(8-9) |
| SJF (non-preemptive) | A(0-5), C(5-6), B(6-9) |
| Round robin (q=2) | A(0-2), B(2-4), C(4-5), A(5-7), B(7-8), A(8-9) |
Turnaround time is completion minus arrival, and response time is first execution minus arrival. Computing from the intervals above gives the following.
| Policy | Turnaround (A/B/C) | Avg turnaround | Response (A/B/C) | Avg response |
|---|---|---|---|---|
| FCFS | 5 / 7 / 7 | 6.33 | 0 / 4 / 6 | 3.33 |
| SJF | 5 / 8 / 4 | 5.67 | 0 / 5 / 3 | 2.67 |
| Round robin | 9 / 7 / 3 | 6.33 | 0 / 1 / 2 | 1.00 |
Identical input, divergent results. SJF has the shortest average turnaround time and therefore wins on throughput. Round robin has the shortest average response time and gets every process to its first execution quickly. In exchange, A's turnaround time under round robin stretches to 9, the price of repeatedly yielding to shorter jobs. Which policy is right comes down to whether responsiveness or throughput takes priority.
Linux CFS
Linux ran CFS (completely fair scheduler) as its default for many years. CFS uses virtual runtime (vruntime) to give the next turn to whichever process has used the least CPU. Instead of a fixed queue order, it measures who has received less and balances on that basis.
Priority is adjusted through the nice value. A lower nice value means a higher weight, so vruntime rises more slowly for the same amount of execution and the process gets picked more often. The values below come from the weight table in the Linux kernel.
| nice value | Weight | Relative CPU share |
|---|---|---|
| -20 (highest) | 88761 | Maximum |
| 0 (default) | 1024 | Baseline |
| +19 (lowest) | 15 | Minimum |
In practice, something like nice -n -5 node server.js gives a server process a low nice value and thus a higher CPU priority. From Linux 6.6 the default scheduler changed to EEVDF (earliest eligible virtual deadline first). The idea of using virtual runtime as the yardstick of fairness carries over unchanged.
Summary
Processes are tracked through the PCB and move among five states, with transitions occurring only on defined events such as timer interrupts and I/O. Context switching performs no work of its own and is pure overhead, which is why designs that reduce switch counts, such as thread pools, matter. Scheduling policy is a compromise among metrics like response time and turnaround time, and the same input produces different results under FCFS, SJF, and round robin. Linux CFS and its successor EEVDF resolve that compromise toward fairness using virtual runtime. Which policy fits depends on whether the system prioritizes responsiveness or throughput.