Process Management and Scheduling

Learning Objectives

By the end of this page, you should be able to:

• Describe the five-state process lifecycle (New, Ready, Running, Waiting, Terminated) and draw its transition diagram.
• Explain the purpose of the Process Control Block (PCB) and what a context switch actually saves and restores.
• Differentiate user-level, kernel-level, and system processes.
• Compute waiting time, turnaround time, and average waiting time for FCFS, SJF, Round Robin, and Priority scheduling given arrival/burst times.
• Compare preemptive vs. non-preemptive scheduling and identify which algorithms risk starvation.
• Relate textbook scheduling concepts to a real scheduler (Linux Completely Fair Scheduler) and explain what "nice values" do.

Quick Answer

Process management is the part of the OS that creates, schedules, and terminates processes, tracking each one's state (New, Ready, Running, Waiting, Terminated) in a Process Control Block (PCB). The CPU scheduler decides which Ready process gets the CPU next, using algorithms such as FCFS, SJF, Priority, and Round Robin, each trading off simplicity, fairness, and average waiting time differently. This matters because scheduling policy directly determines system responsiveness, throughput, and whether any process starves. Every multitasking OS — Linux, Windows, Android — runs some variant of these algorithms (Linux uses the Completely Fair Scheduler) under the hood, so understanding them explains real, observable behavior like why a nice-ed background job slows down and why interactive apps feel snappy even under load.

Process States and the Process Lifecycle

A process moves through a well-defined set of states from creation to termination. Most operating systems textbooks use this five-state model:

1. New — the process is being created (program image loaded, PCB allocated) but has not yet been admitted to the Ready queue.
2. Ready — the process has everything it needs to run and is waiting only for CPU time. It sits in the ready queue.
3. Running — the process is currently executing instructions on the CPU (one process per core at a time).
4. Waiting (Blocked) — the process cannot proceed until some event occurs, typically I/O completion, a signal, or a resource becoming available.
5. Terminated — the process has finished execution (or was killed) and its resources are being reclaimed; on Unix this is briefly the "zombie" state until the parent reaps the exit status with wait().

Note the two arrows leaving Running: a process can be preempted back to Ready (it still wants to run, but its turn is over) or it can block itself by requesting I/O, moving to Waiting. A process can never go directly from Waiting to Running — it must re-enter Ready and be re-scheduled.

The Process Control Block (PCB)

The OS represents every process with a Process Control Block, a kernel data structure that stores everything needed to suspend and later resume the process exactly where it left off:

• Process ID (PID) and parent PID
• Process state (one of the five above)
• Program counter — address of the next instruction to execute
• CPU registers — general-purpose registers, stack pointer, status flags
• CPU scheduling info — priority, scheduling queue pointers, nice value
• Memory management info — page tables, base/limit registers, segment tables
• Accounting info — CPU time used, time limits, process number
• I/O status info — list of open file descriptors, allocated devices

On Linux, the analogous structure is struct task_struct, and it's larger and more detailed than the classic textbook PCB (it also describes threads, since Linux treats threads as processes that share resources).

Context Switching

A context switch is the act of saving the PCB of the currently running process and loading the PCB of the next process to run. It happens whenever the scheduler decides to give the CPU to a different process — because of a timer interrupt, an I/O request, a higher-priority process becoming ready, or the running process exiting.

Context switching is pure overhead — no useful work is done for the application during the switch itself. The cost comes from:

• Saving/restoring CPU registers (fast, done in hardware/microcode on many architectures)
• Switching memory address space (updating page tables, flushing/reloading the TLB) — this is the expensive part
• Scheduler bookkeeping (updating queues, statistics)

This is why threads (which share an address space) are "lighter" to switch between than full processes, and why scheduling algorithms try to avoid switching more often than necessary.

Types of Processes

• User-level processes — ordinary application programs run in user mode with restricted privileges (a browser, a text editor).
• Kernel-level processes — code that executes in kernel/privileged mode, such as kernel threads that handle deferred work (e.g., kswapd on Linux for page reclaiming).
• System processes — background processes that keep the OS itself running (init/systemd, daemons, service managers).

CPU Scheduling Algorithms

The CPU scheduler picks the next process from the Ready queue to run whenever the CPU becomes idle or a scheduling event occurs. The two central goals in tension are fairness/responsiveness and throughput/efficiency.

First-Come-First-Served (FCFS)

Processes are run strictly in arrival order, non-preemptively, using a FIFO queue. Simple but can cause the convoy effect: a long process at the front makes every process behind it wait, tanking average waiting time.

Shortest Job First (SJF) / Shortest Remaining Time First (SRTF)

SJF always picks the Ready process with the smallest burst time. Non-preemptive SJF waits for the current process to finish before choosing; the preemptive version, SRTF, will interrupt a running process if a newly arrived process has a shorter remaining time. SJF is provably optimal for minimizing average waiting time, but requires predicting burst time in advance (usually via exponential averaging of past bursts) and can starve long processes.

Priority Scheduling

Each process is assigned a priority number; the CPU goes to the highest-priority Ready process. Can be preemptive or non-preemptive. Risk: starvation of low-priority processes under heavy load. The standard fix is aging — gradually increasing the priority of processes that wait too long.

Round Robin (RR)

Each process gets a fixed time quantum; if it doesn't finish, it's preempted and placed at the back of the Ready queue. Designed for time-sharing systems — it guarantees no process waits more than (n-1) × quantum for its next turn, at the cost of higher average turnaround than SJF for CPU-bound jobs. Quantum size is a key tuning knob: too large and RR degenerates into FCFS; too small and context-switch overhead dominates.

Multilevel Queue and Multilevel Feedback Queue

Multilevel queue scheduling splits the Ready queue into separate queues by process type (e.g., interactive vs. batch), each with its own algorithm, and schedules between queues (often with fixed priority or time-slicing across queues). Processes are permanently assigned to a queue.

Multilevel feedback queue (MLFQ) improves on this by letting processes move between queues based on observed behavior: a process that uses its full time quantum (CPU-bound) gets demoted to a lower-priority, longer-quantum queue, while a process that blocks for I/O quickly (interactive) stays at high priority. This is the general family of design that Linux's scheduler and Windows' scheduler both draw on conceptually.

Worked Example: FCFS vs. SJF vs. Round Robin

Consider four processes:

Process	Arrival Time	Burst Time
P1	0	8
P2	1	4
P3	2	9
P4	3	5

FCFS (run in arrival order: P1, P2, P3, P4):

Process	Start	Finish	Turnaround (Finish − Arrival)	Waiting (Turnaround − Burst)
P1	0	8	8	0
P2	8	12	11	7
P3	12	21	19	10
P4	21	26	23	18

Average waiting time = (0 + 7 + 10 + 18) / 4 = 8.75

Non-preemptive SJF (once a process starts, run to completion; pick shortest burst among arrived processes at each decision point): at t=0 only P1 has arrived, so P1 runs (0–8). At t=8, P2(4), P3(9), P4(5) have all arrived → pick P2 (8–12). Next shortest is P4(5) → (12–17). Then P3 (17–26).

Process	Start	Finish	Turnaround	Waiting
P1	0	8	8	0
P2	8	12	11	7
P4	12	17	14	9
P3	17	26	24	15

Average waiting time = (0 + 7 + 9 + 15) / 4 = 7.75 — better than FCFS.

Round Robin, quantum = 4 (Ready queue managed FIFO, new arrivals join at the back after any process running at that instant):

Timeline: P1(0–4, remaining 4) → P2 arrives during this; queue after P1's slice: [P2, P3(arr@2), P4(arr@3), P1]. Run P2(4–8, remaining 0, done) → P3(8–12, remaining 5) → P4(12–16, remaining 1) → P1(16–20, remaining 0, done) → P3(20–25, remaining 0, done) → P4(25–26, done).

Process	Finish	Turnaround	Waiting
P1	20	20	12
P2	8	7	3
P3	25	23	14
P4	26	23	18

Average waiting time = (12 + 3 + 14 + 18) / 4 = 11.75 — worse average than SJF here, but no single process waits an unbounded amount, and P2 (a short job) finishes fast — the tradeoff RR is designed to make for responsiveness.

Takeaway: SJF/SRTF minimizes average waiting time but needs burst-time knowledge and can starve long jobs; RR bounds worst-case response time at the cost of average waiting time; FCFS is simplest but suffers the convoy effect.

Real-World Note: Linux CFS and Windows Priority Classes

Real operating systems rarely implement the textbook algorithms directly. Linux's default scheduler, the Completely Fair Scheduler (CFS), doesn't use fixed time quanta at all — it models an idealized "perfectly fair" CPU that gives every runnable process an equal share of CPU time, tracked via a per-process vruntime (virtual runtime), and always picks the process with the smallest vruntime from a red-black tree. A process's nice value (-20 to +19) scales how fast its vruntime accumulates, so a "niced" (lower priority) process accumulates virtual runtime faster and gets scheduled less often — this is a weighted, dynamic descendant of priority scheduling, not literal Round Robin. Windows uses priority classes (Idle, Below Normal, Normal, Above Normal, High, Realtime) combined with a base priority per thread and a multilevel feedback-like dynamic boosting scheme (e.g., threads get a temporary priority boost after waking from I/O) — conceptually an MLFQ variant.

Thread-Level and Real-Time Scheduling

Modern kernels schedule threads, not just whole processes — Linux schedules task_struct entities uniformly whether they represent a process or a thread. This introduces context-switch cost even between threads of the same process (cheaper, since the address space doesn't change) and requires synchronization primitives (semaphores, mutexes, monitors) to avoid race conditions when threads share data.

Real-time scheduling targets systems with deadlines rather than just fairness:

• Rate Monotonic Scheduling (RMS) — static priorities assigned inversely to task period (shorter period = higher priority); optimal among static-priority algorithms for periodic tasks.
• Earliest Deadline First (EDF) — dynamic priority given to whichever ready task has the nearest deadline; can achieve full CPU utilization but requires more overhead to track deadlines.

Key Terms

Term	Definition	Context/Related
Process	An instance of a program in execution, with its own address space and resources	Distinct from a program (static) and a thread (lighter execution unit)
Process Control Block (PCB)	Kernel data structure holding all state needed to save/restore a process	Contains PID, state, program counter, registers, memory info
Context Switch	Saving one process's PCB and restoring another's so the CPU can run it	Triggered by timer interrupt, I/O block, or higher-priority arrival
Burst Time	The amount of CPU time a process needs before it next blocks or finishes	Central input to SJF/SRTF
Turnaround Time	Finish time minus arrival time	Total time a process spends in the system
Waiting Time	Turnaround time minus burst time	Time spent in the Ready queue, not running
Convoy Effect	Short processes stuck waiting behind one long process (typical of FCFS)	Motivates preemptive algorithms
Starvation	A process indefinitely denied CPU time because others are always prioritized	Risk in Priority and SJF scheduling; fixed by aging
Aging	Gradually raising the priority of a waiting process over time	Prevents starvation in priority-based schedulers
Time Quantum	The fixed slice of CPU time given to a process in Round Robin	Too large → behaves like FCFS; too small → context-switch overhead
Completely Fair Scheduler (CFS)	Linux's default scheduler, based on tracking virtual runtime per process	Uses nice values, a red-black tree keyed on vruntime
Nice Value	A Linux priority hint (-20 to +19) influencing how fast vruntime accrues	Lower nice = higher priority = more CPU share

Common Mistakes

1. Misconception: "SJF is always the best scheduling algorithm because it minimizes average waiting time." Why it's wrong: SJF requires knowing (or accurately predicting) burst times in advance, which is generally impossible in a general-purpose OS, and it can starve long-running processes indefinitely if short jobs keep arriving. Correct explanation: SJF/SRTF is optimal for average waiting time under the assumption burst times are known, which makes it a useful theoretical benchmark and practical for batch systems with predictable jobs, but real interactive OS schedulers (like CFS) use fairness- and priority-based approaches instead precisely because burst time isn't known ahead of time.

2. Misconception: "A process moves from Waiting directly to Running once its I/O completes." Why it's wrong: This skips the Ready state and ignores that the CPU may currently be running another process. Correct explanation: When a blocking event completes, the process moves from Waiting to Ready, joining the ready queue; the scheduler then decides when (and whether) to dispatch it to Running based on its priority and current system load.

3. Misconception: "Round Robin is always fairer and better for average waiting time than FCFS or SJF." Why it's wrong: RR bounds the worst-case wait for CPU time and improves responsiveness, but it usually produces a higher average waiting time than SJF and even than FCFS in some arrival patterns, because of the extra context switches and because long jobs get chopped into many rounds. Correct explanation: "Fair" in RR means bounded turnaround for response time — every process gets the CPU regularly — not minimal average waiting time. The right algorithm depends on whether you're optimizing for throughput/average wait (batch systems, favors SJF) or responsiveness (interactive systems, favors RR/MLFQ/CFS).

Comparison and Connections

Algorithm	Preemptive?	Starvation Risk	Avg. Waiting Time	Best Use Case
FCFS	No	Low (but convoy effect hurts short jobs)	Often high	Simple batch systems, non-interactive queues
SJF (non-preemptive)	No	High (long jobs)	Optimal (given known bursts)	Batch systems with predictable job lengths
SRTF (preemptive SJF)	Yes	High (long jobs)	Lower than SJF, still optimal-ish	Systems that can estimate remaining burst dynamically
Priority Scheduling	Either	High (low-priority procs), fixed via aging	Depends on priority distribution	Systems needing explicit importance ranking (real-time-ish tasks)
Round Robin	Yes	None (every process gets a turn)	Higher than SJF, bounded worst case	Interactive/time-sharing systems
Multilevel Feedback Queue	Yes	Low (adaptive)	Good in practice	General-purpose OS (approximates Linux/Windows behavior)

Practice Questions

Recall

1. List the five standard process states and one event that triggers each transition. Answer guidance: New→Ready (admitted), Ready→Running (dispatched), Running→Waiting (I/O request), Waiting→Ready (I/O completion), Running→Terminated (exit/kill); also Running→Ready (preemption).

2. What information does a Process Control Block store? Answer guidance: PID/parent PID, process state, program counter, CPU registers, scheduling info (priority), memory management info, accounting info, I/O status — see Key Terms/PCB section.

Understanding

3. Why can Round Robin never cause starvation, while Priority Scheduling can? Answer guidance: RR cycles through every Ready process in FIFO order regardless of priority, guaranteeing each gets the CPU within (n-1) × quantum; Priority Scheduling always favors higher-priority processes, so a continuous stream of higher-priority arrivals can indefinitely delay a low-priority process unless aging is applied.

4. Explain why context switching between two threads of the same process is generally cheaper than between two different processes. Answer guidance: Threads of the same process share the same address space (page tables), so switching threads doesn't require reloading page tables or flushing the TLB the way switching processes does — only registers/stack and scheduler bookkeeping change.

Application

5. Two processes arrive: P1 (arrival 0, burst 6), P2 (arrival 0, burst 3). Compute the average waiting time under non-preemptive SJF. Answer guidance: SJF picks the shorter job first: P2 runs 0–3 (wait 0), P1 runs 3–9 (wait 3). Average waiting time = (0+3)/2 = 1.5.

6. Using the worked example table (P1 arr 0/burst 8, P2 arr 1/burst 4, P3 arr 2/burst 9, P4 arr 3/burst 5), what is P2's waiting time under FCFS vs. Round Robin (quantum 4), and why does it differ so much? Answer guidance: Under FCFS, P2 waits 7 (runs 8–12, arrived at 1). Under RR, P2 waits only 3 (runs 4–8, since it gets a slice as soon as its turn in the queue arrives). RR gives short/recently-arrived jobs a chance quickly instead of making them wait behind a long earlier job (P1's full 8-unit burst under FCFS).

Analysis

7. A system exclusively uses non-preemptive priority scheduling with no aging. Under what workload conditions would a low-priority process starve, and how would adding aging change the outcome? Answer guidance: Starvation occurs whenever higher-priority processes keep arriving faster than the low-priority process can be scheduled, so its turn never comes. Aging periodically increases the waiting process's effective priority the longer it waits, so eventually it will out-rank even continuously-arriving higher-priority processes and get scheduled — bounding worst-case wait time.

8. Compare how Linux's CFS and classic Round Robin both try to be "fair," and explain one concrete way their notions of fairness differ. Answer guidance: Both aim to give every runnable process a share of the CPU. RR achieves this with fixed-size time slices dispatched in strict FIFO order, so fairness is about turn-taking. CFS achieves it by tracking accumulated virtual runtime (vruntime) per process and always running whichever process has received the least CPU time so far relative to its weight (nice value) — fairness is proportional-share and continuous rather than round-based, so quantum size isn't a fixed global constant and nice values let some processes get more/less than an equal share by design.

FAQ

Q: What's the actual difference between a process and a thread? A: A process has its own independent address space, PCB, and resources; a thread is a unit of execution within a process that shares that process's address space and most resources with sibling threads, only having its own stack, registers, and program counter. This is why context-switching threads is cheaper than switching processes.

Q: Why does the "zombie" state exist instead of processes disappearing immediately on exit? A: On Unix systems, when a process terminates, its exit status must remain available for the parent to retrieve via wait()/waitpid(). Until the parent reaps it, the process stays in the process table as a zombie — using no CPU or memory beyond the PCB entry, but consuming a process table slot.

Q: Is Round Robin used in real operating systems, or only priority/fairness-based schedulers like CFS? A: Pure Round Robin is rare in modern general-purpose OS kernels, but its core idea (bounded time slices, cyclic fairness) survives inside multilevel feedback queues and influences how CFS caps how long a process can run before being reconsidered (sched_latency/minimum granularity settings). RR is still used directly in simpler embedded/RTOS contexts.

Q: How do you choose the "right" time quantum for Round Robin? A: Rule of thumb: 80% of CPU bursts should be shorter than the time quantum. Too small a quantum causes excessive context-switch overhead (system spends more time switching than computing); too large a quantum makes RR behave like FCFS, reintroducing the convoy effect and hurting responsiveness.

Q: Why is SJF called "optimal" if it can starve processes? A: It's optimal in a narrow, specific sense: among all algorithms that don't preempt (or, for SRTF, among all algorithms), it minimizes the average waiting time across the batch of processes given, assuming burst times are known upfront. Optimality here is a statement about a single metric (mean waiting time), not about fairness or worst-case behavior — which is exactly why starvation is possible despite it being "optimal."

Quick Revision

• Process lifecycle: New → Ready → Running → Waiting → Terminated (Running can also return to Ready via preemption).
• PCB stores: PID, state, program counter, registers, scheduling info, memory info, I/O status.
• Context switch = save current PCB + load next PCB; expensive part is switching address space (TLB/page tables), not registers.
• FCFS: simple, non-preemptive, suffers convoy effect (short jobs stuck behind long ones).
• SJF/SRTF: minimizes average waiting time but needs burst-time prediction; can starve long jobs.
• Priority Scheduling: risk of starvation for low priority; fixed with aging.
• Round Robin: fixed time quantum, no starvation, but higher average wait than SJF; quantum sizing is critical.
• Multilevel Feedback Queue: processes move between priority queues based on observed CPU vs. I/O behavior.
• Linux uses CFS: tracks vruntime per process, nice values (-20 to 19) weight CPU share — not literal Round Robin.
• Windows uses priority classes + dynamic priority boosting, an MLFQ-like design.
• Waiting time = Turnaround time − Burst time; Turnaround time = Finish time − Arrival time.
• Real-time scheduling (RMS, EDF) prioritizes by deadline/period rather than fairness alone.

Related Topics

Prerequisites: Introduction to Operating Systems

Related Topics: Threads and Concurrency, Inter-Process Communication and Synchronization, Deadlocks

Next Topics: Memory Management