These are the notes for CS Fundamentals for Placements, episode 17. In episode 16 the kernel booted and started PID 1. Today you find out what a process really is, one problem at a time: program vs process, the process memory layout (text, data, BSS, heap, stack), the PCB and the PID, the process states (new, ready, running, waiting/blocked, terminated, suspended-ready, suspended-blocked) and the state transition diagram, the job queue, ready queue and device queues, the long-term, short-term and medium-term schedulers, swapping, the degree of multiprogramming, the dispatcher and dispatch latency, the context switch and its overhead, CPU-bound vs I/O-bound processes, and CPU bursts and I/O bursts. Every term is explained in plain words the first time it appears, and there is a full glossary at the end. All outputs below are real: the C programs were compiled with gcc -O2 (gcc 13.3) and run on Linux x86-64 on 30 October 2026. Process ids, addresses and switch counts change on every run.
A quick refresher: the CPU runs instructions; registers are tiny storage slots inside it; the program counter (PC) is the register holding the address of the next instruction (episode 6). RAM is main memory. A system call asks the kernel to do something for a program (episode 15). An address is the number of a byte in memory, usually printed in hexadecimal (episode 2), like 0x7ffc41aaf144.
The six problems
| Problem | What it teaches |
|---|---|
| Same program, run twice | Program vs process |
| Where does everything live? | Text, data, BSS, heap, stack; ASLR |
| The kernel must remember | PCB, PID, what a PCB contains |
| It can't always run | New, ready, running, waiting, terminated, suspended states; transition diagram |
| Hundreds of processes | Job, ready and device queues; long-, short-, medium-term schedulers; swapping; degree of multiprogramming |
| Switching costs time | Context, context switch, dispatcher, dispatch latency, overhead; CPU-bound vs I/O-bound; CPU and I/O bursts |
Problem 1: same program, run twice (program vs process)
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int marks = 90; // initialised global → data
int total; // uninitialised global → BSS
int main() {
int local = 5; // → stack
int *box = malloc(sizeof(int)); // → heap
printf("process id %d\n", getpid());
printf("text (main) %p\n", (void *) main);
printf("data (marks) %p\n", (void *) &marks);
printf("bss (total) %p\n", (void *) &total);
printf("heap (box) %p\n", (void *) box);
printf("stack (local) %p\n", (void *) &local);
return 0;
}
Run 1:
process id 1991
text (main) 0x56397a9620c0
data (marks) 0x56397a965010
bss (total) 0x56397a965018
heap (box) 0x56399f5e12a0
stack (local) 0x7fff3aa333f4
Run 2, the same code:
process id 2005
text (main) 0x557a5d05b0c0
data (marks) 0x557a5d05e010
bss (total) 0x557a5d05e018
heap (box) 0x557a6037b2a0
stack (local) 0x7ffc41aaf144
Same program, but each run is a different live thing with its own id and its own memory.
Real-life example: recipe vs cooking. A recipe in a cookbook is just words; it does nothing. Someone cooking it right now has the gas on, a hot pan, half-cut onions, and is at step 4. Two cooks can follow the same recipe at the same time, each with their own pan.
| Program | Process | |
|---|---|---|
| What it is | a file of instructions on disk | a program in execution |
| Nature | passive | active |
| Has | code (and initial data) | code + program counter + registers + its own memory (stack, heap) + open files + a PID |
| Lifetime | stays until deleted | from creation until it ends |
| How many | one file | many processes can run the same program at once |
%p prints a pointer (an address) in hexadecimal; (void *) converts the pointer to the generic type %p expects; malloc(sizeof(int)) asks for 4 bytes of memory while the program runs.
Problem 2: where does everything live? (memory layout)
Every process gets the same layout of its (virtual) memory, from low addresses to high:
| Part | Holds | Example | Notes |
|---|---|---|---|
| Text (code) | the compiled machine instructions | main and every function |
read-only, so a bug can't overwrite the program; can be shared by processes running the same program |
| Data | global and static variables that have a starting value | int marks = 90; |
its starting values are stored in the program file |
| BSS | global and static variables without a starting value | int total; |
zero-filled at start; the file only records its size. BSS = "block started by symbol", an old assembler name |
| Heap | memory requested while running | malloc, new |
grows upward; freed with free / delete / garbage collection |
| (gap) | unused space | heap and stack grow toward each other | |
| Stack | local variables, function arguments, return addresses | int local = 5; |
one stack frame per active function call; pushed on call, popped on return; grows downward |
Reading our real addresses from small to big confirms it: text (0x5639...20c0) < data (...5010) < BSS (...5018) < heap (0x56399f...) ≪ stack (0x7fff...).
The addresses differ between runs because Linux uses ASLR, address space layout randomisation: each part is placed at a random offset every time a program starts, so an attacker can't guess where code or data lives.
Problem 3: the kernel must remember (PCB and PID)
The kernel runs hundreds of processes and keeps pausing and resuming them, so it must remember everything about each one.
Real-life example: the hospital patient file.
| Hospital | Kernel |
|---|---|
| Patient number, unique while admitted | PID (process id), unique while the process exists |
| Patient file: bed, reports, medicines, next dose | PCB (process control block), one per process |
| A doctor called away mid-check-up writes down where she stopped | the PCB stores the saved registers and program counter so the process resumes exactly |
A process control block (PCB) (also called a task control block) is the kernel's record for one process. In Linux it is a C structure named task_struct.
| PCB field | Meaning |
|---|---|
| Process id (PID) and parent's PID | who it is, who created it |
| Process state | new, ready, running, waiting, terminated, ... |
| Program counter | address of the next instruction to run |
| CPU registers | saved values while it is not running |
| CPU scheduling information | priority, pointers to its place in scheduling queues |
| Memory-management information | where its memory is: base/limit registers or page tables (episodes 30-32) |
| Accounting information | CPU time used, time limits, start time |
| I/O status information | open files, devices allocated to it |
Problem 4: it can't always run (process states)
One CPU core runs one process at a time, so most processes are usually not running.
Real-life example: a cricket team. Picked in the squad, not at the ground yet = new. Padded up in the dugout, waiting for a turn = ready. Batting at the crease (only two at a time) = running. Bat broke, waiting for a new one; can't bat even if it's his turn = waiting. Out = terminated.
| State | Meaning |
|---|---|
| New | being created: PCB and memory being set up |
| Ready | has everything it needs except the CPU; waiting in the ready queue |
| Running | its instructions are executing on a CPU core |
| Waiting (blocked) | waiting for an event: I/O completion, a key press, a timer, a signal; giving it the CPU would be pointless |
| Terminated (exit) | finished; the kernel is cleaning up |
| Suspended ready | ready, but swapped out to disk |
| Suspended blocked (suspended waiting) | waiting, and swapped out to disk |
The state transition diagram
| From → To | When | Name |
|---|---|---|
| new → ready | the OS admits the process into memory | admitted |
| ready → running | the short-term scheduler picks it | dispatch |
| running → ready | its time slice ends (timer interrupt) or a higher-priority process arrives | interrupt / preemption |
| running → waiting | it asks for I/O or waits for an event (read, sleep) |
I/O or event wait |
| waiting → ready | the I/O or event completes | I/O or event completion |
| running → terminated | it calls exit or is killed |
exit |
| ready → suspended ready | swapped out to make room in RAM | suspend |
| waiting → suspended blocked | swapped out while waiting | suspend |
| suspended blocked → suspended ready | its event completes while it is on disk | event completion |
| suspended ready → ready | swapped back into RAM | activate / resume |
| suspended blocked → waiting | swapped back in, still waiting (some books) | activate |
Key rule: waiting → ready, never waiting → running. After its event, a process must wait for its turn again.
Catch a process moving between states
/proc/self/status shows the kernel's facts about the calling process, read from its PCB:
#include <stdio.h>
#include <string.h>
#include <unistd.h>
void show(const char *when) { // read my own PCB facts from the kernel
char line[128];
FILE *f = fopen("/proc/self/status", "r");
while (fgets(line, sizeof line, f))
if (!strncmp(line, "State", 5) || strstr(line, "ctxt"))
printf("%s %s", when, line);
fclose(f);
}
int main() {
show("start:");
for (int i = 0; i < 20; i++)
usleep(1000); // wait for a timer: blocked
show("after 20 waits:");
return 0;
}
Output:
start: State: R (running)
start: voluntary_ctxt_switches: 0
start: nonvoluntary_ctxt_switches: 0
after 20 waits: State: R (running)
after 20 waits: voluntary_ctxt_switches: 20
after 20 waits: nonvoluntary_ctxt_switches: 0
State: R (running): it is running whenever it reads the file. Other Linux letters:S(sleeping = waiting, can be woken),D(waiting for disk, can't be interrupted),T(stopped),Z(zombie, episode 18).- Voluntary context switches: times the process gave up the CPU itself by blocking. Each
usleep(1000)(sleep 1000 microseconds = 1 ms) moved it running → waiting; when the timer fired it went waiting → ready, and later ready → running. 20 sleeps = 20 voluntary switches. - Nonvoluntary context switches: times the scheduler took the CPU away (time slice over, or a more important process).
strncmp(line, "State", 5)checks the first 5 characters;strstr(line, "ctxt")checks whether "ctxt" appears anywhere in the line.
Suspended states and swapping
When RAM fills up, the OS can move a whole process out to disk. Moving processes between RAM and disk is swapping; the disk area used is the swap space. A ready process moved out becomes suspended ready; a waiting one becomes suspended blocked. That makes seven states in the full diagram. (Modern systems mostly move individual pages instead of whole processes, episode 33, but the states are still asked in interviews.)
Problem 5: hundreds of processes (queues and schedulers)
Real-life example: a busy hospital.
| Hospital | OS |
|---|---|
| People line up at the admission desk | job queue: all submitted jobs waiting to be admitted (batch systems, on disk) |
| The admission desk decides who is admitted | long-term scheduler (job scheduler) |
| Admitted patients wait in the waiting room; a nurse calls the next one every few minutes | ready queue + short-term scheduler (CPU scheduler) |
| A separate line at each X-ray machine | device queues (one per device) |
| Ward full: shift some patients to a hall, bring them back later | medium-term scheduler (swapping) |
- Job queue: the set of all processes/jobs waiting to enter the system.
- Ready queue: processes in memory, ready to run. In Linux, often implemented as a linked list or a tree of PCBs.
- Device queue (I/O queue / wait queue): processes waiting for one particular device or event, e.g. the disk queue.
| Scheduler | Also called | Moves processes | Runs | Controls |
|---|---|---|---|---|
| Long-term | job scheduler | job queue → memory (new → ready) | rarely (seconds-minutes) | the degree of multiprogramming and the mix of CPU-bound and I/O-bound jobs |
| Short-term | CPU scheduler | ready queue → CPU (ready → running) | very often (every few milliseconds) | who runs next; must be very fast |
| Medium-term | swapper | memory ↔ disk (suspend / resume) | when memory is tight | lowers the degree of multiprogramming temporarily |
The degree of multiprogramming is the number of processes in memory at the same time (episode 15). On desktops and phones every program you open is admitted at once, so a long-term scheduler barely exists; it mattered most on batch systems.
Problem 6: switching costs time (context switch)
The context of a process is everything about where it is: the CPU registers, the program counter, its state and memory information. A context switch is switching the CPU from one process to another:
- an interrupt or system call enters the kernel;
- save the old process's context into its PCB;
- the scheduler picks the next process;
- load the new process's context from its PCB (including its memory map);
- return to user mode at the new process's saved program counter.
The dispatcher is the kernel module that hands the CPU to the process the short-term scheduler chose: it switches context, switches to user mode, and jumps to the right place in the new program. The time it takes to stop one process and start another is the dispatch latency.
Overhead: during a switch no user process makes progress, so the time is pure waste. On top of that, the new process's data is not yet in the CPU caches (episode 9-10), so it starts slowly. Switch too often and the CPU spends its time switching instead of working (this matters for Round Robin, episode 23).
CPU-bound vs I/O-bound
#include <stdio.h>
#include <string.h>
#include <unistd.h>
void show(const char *who) { // read my PCB facts from the kernel
char line[128];
FILE *f = fopen("/proc/self/status", "r");
while (fgets(line, sizeof line, f))
if (strstr(line, "ctxt_switches"))
printf("%s %s", who, line);
fclose(f);
}
int main() {
for (int i = 0; i < 20; i++)
usleep(1000); // I/O-bound: wait 20 times
show("after waiting:");
volatile long sum = 0;
for (long i = 0; i < 400000000; i++)
sum += i; // CPU-bound: just compute
show("after computing:");
return 0;
}
Output (the last number depends on how busy the machine is; it is often 0 to a few):
after waiting: voluntary_ctxt_switches: 20
after waiting: nonvoluntary_ctxt_switches: 0
after computing: voluntary_ctxt_switches: 20
after computing: nonvoluntary_ctxt_switches: 3
While waiting, the process gave the CPU away 20 times itself. While computing, it never blocked, so no new voluntary switches; any nonvoluntary ones were forced by the scheduler's timer. (volatile stops the compiler from deleting the loop as useless.)
Every process alternates CPU bursts (periods of computing) and I/O bursts (periods of waiting for input/output): compute, wait, compute, wait, ..., end.
| CPU-bound process | I/O-bound process | |
|---|---|---|
| CPU bursts | few, long | many, short |
| Spends most time | computing | waiting for I/O |
| Examples | video encoding, compiling, our sum loop | text editor, web server, file copy |
| Context switches | mostly nonvoluntary | mostly voluntary |
A good long-term scheduler admits a mix: only CPU-bound jobs leave devices idle; only I/O-bound jobs leave the CPU idle. Which process gets the CPU next is the scheduling problem of episodes 21-23.
Common mistakes (and the real output)
| Mistake | Real output | Why | Fix |
|---|---|---|---|
| Expecting the same addresses every run | different addresses each run | ASLR randomises the layout | compare the order, not the values |
| Expecting the same PID every run | different PID each run | each run is a new process | print getpid() |
"int total; lives in data" |
its address sits just after data, in BSS | no initial value → BSS, zero-filled | initialised → data, uninitialised → BSS |
| "Waiting goes straight to running" | (interview: wrong) | after its event it must queue again | waiting → ready → running |
| "A program and a process are the same" | (interview: wrong) | a program is a passive file | process = program in execution + its state |
| Counting a context switch as useful work | (interview: wrong) | no user process runs meanwhile | it's overhead; too many switches waste the CPU |
| Mixing up long-term and short-term schedulers | (interview: wrong) | they move processes between different places | long: job queue → memory; short: ready queue → CPU |
Mini project: watch states change with ps
On a Linux machine, open two terminals. In the first, run sleep 100. In the second, run ps -o pid,stat,comm -C sleep: the STAT column shows S (sleeping = waiting). Press Ctrl+Z in the first terminal and look again: T (stopped). Type fg to resume it. Then run yes > /dev/null and check it with ps -o pid,stat,comm -C yes: R (running or ready). Finally look at /proc/<pid>/status for its context-switch counters and watch the nonvoluntary count climb for yes (CPU-bound) while sleep stays still. Press Ctrl+C to stop yes.
Practice
1. Add a static local variable with a value, and one without. Where does each go?
Solution
#include <stdio.h>
int marks = 90; // data
int total; // BSS
int main() {
static int visits = 1; // static local WITH a value
static int count; // static local WITHOUT a value
int local = 5; // stack
printf("data (marks) %p\n", (void *) &marks);
printf("data? (visits) %p\n", (void *) &visits);
printf("bss (total) %p\n", (void *) &total);
printf("bss? (count) %p\n", (void *) &count);
printf("stack (local) %p\n", (void *) &local);
return 0;
}
Output:
data (marks) 0x562a8900f014
data? (visits) 0x562a8900f010
bss (total) 0x562a8900f01c
bss? (count) 0x562a8900f020
stack (local) 0x7ffca44a7724
visits sits next to marks (data) and count next to total (BSS). nm on the compiled file confirms it: d visits.1 (data) and b count.0 (BSS). A static local lives as long as the program, like a global, but is visible only inside its function.
2. Draw the 7-state diagram from memory.
Solution
New → Ready (admit) → Running (dispatch) → Terminated (exit). Running → Ready (time slice over). Running → Waiting (I/O request). Waiting → Ready (I/O done). Ready → Suspended ready (swap out); Waiting → Suspended blocked (swap out); Suspended blocked → Suspended ready (event done); Suspended ready → Ready (swap in).
3. Change the sleep loop to 50 waits. Predict the voluntary switch count.
Solution
- Real output:
voluntary_ctxt_switches: 50(eachusleepblocks once).
4. CPU-bound or I/O-bound? (a) a video encoder, (b) a chat app, (c) a compiler, (d) a file download.
Solution
(a) CPU-bound, (b) I/O-bound (waits for messages and keys), (c) mostly CPU-bound, (d) I/O-bound (waits for the network and disk).
5. A process is in the ready queue and its memory is swapped to disk. Then the medium-term scheduler brings it back. Name the two states it passes through.
Solution
Ready → suspended ready (swapped out) → ready (swapped back in). It can only run after the short-term scheduler dispatches it.
6. Which scheduler controls the degree of multiprogramming, and which one runs most often?
Solution
The long-term scheduler controls the degree of multiprogramming (the medium-term scheduler can lower it temporarily). The short-term (CPU) scheduler runs most often, every few milliseconds.
Quick quiz
A running process calls read() on the keyboard and you haven't typed anything yet. Which state does it move to?
A. Ready B. Waiting (blocked) C. Terminated D. Suspended ready
Answer
B. It needs an event (a key press) before it can continue, so it moves from running to waiting. After you type, it goes to ready, and later back to running.
Interview questions
- Program vs process? A program is a passive file of instructions; a process is a program in execution with a PC, registers, its own memory, open files and a PID. One program can be many processes.
- Describe the memory layout of a process. Text (code, read-only), data (initialised globals/statics), BSS (uninitialised, zero-filled), heap (dynamic, grows up), stack (locals and call frames, grows down).
- Why does BSS exist? Zero-initialised variables needn't be stored in the executable; only their total size is recorded, which keeps the file small.
- What is a PCB? What does it contain? The kernel's record per process: PID, state, PC, registers, scheduling info, memory info, accounting, I/O status.
- Draw the process state diagram. New, ready, running, waiting, terminated (+ suspended ready, suspended blocked) with admit, dispatch, interrupt, I/O wait, I/O done, exit, suspend, resume.
- Can a process go from waiting to running directly? No, it goes to ready first and waits to be dispatched.
- Long-term vs short-term vs medium-term scheduler? Long: admits jobs to memory, controls degree of multiprogramming, runs rarely. Short: picks the next process from the ready queue, runs every few ms. Medium: swaps processes out/in to manage memory.
- What is a context switch, and why is it overhead? Saving one process's context into its PCB and loading another's. No useful user work is done, and caches/TLB are cold afterwards.
- What is the dispatcher? Dispatch latency? The module that gives the CPU to the chosen process (switch context, switch to user mode, jump). Dispatch latency is the time it takes.
- CPU-bound vs I/O-bound? CPU-bound: long CPU bursts (computation). I/O-bound: short CPU bursts, lots of waiting. A good mix keeps CPU and devices busy.
- What is swapping? Moving a whole process between RAM and disk (swap space) to free memory.
- What is the degree of multiprogramming? The number of processes in memory at once.
Glossary
| Term | Meaning in plain words | Example |
|---|---|---|
| Program | A passive file of instructions on disk | main compiled to ./main |
| Process | A program in execution, with its own state and memory | each run of ./main |
| Program counter (PC) | Register holding the address of the next instruction | saved in the PCB |
| Address | The number of a byte in memory | 0x7ffc41aaf144 |
| Memory layout | How a process's memory is divided | text, data, BSS, heap, stack |
| Text segment | The process's machine code, read-only | main |
| Data segment | Globals and statics with a starting value | int marks = 90; |
| BSS | Globals and statics without a starting value, zero-filled | int total; |
| Heap | Memory requested while running; grows upward | malloc(sizeof(int)) |
| Stack | Locals, arguments and return addresses of active calls; grows downward | int local = 5; |
| Stack frame | The stack space for one function call | main's frame |
static local |
A local variable that lives for the whole program (in data/BSS) | static int visits = 1; |
| ASLR | Address space layout randomisation: random addresses each run | addresses change between runs |
| PID | Process id, unique number of a process | getpid() |
| PCB | Process control block: the kernel's record for one process | Linux task_struct |
| Process state | Where a process is in its life | ready, running |
| New | Being created | PCB being built |
| Ready | Could run; waiting only for the CPU | in the ready queue |
| Running | Executing on a CPU core | State: R |
| Waiting / blocked | Waiting for an event; can't use the CPU | during usleep |
| Terminated | Finished, being cleaned up | after exit |
| Suspended ready | Ready but swapped out to disk | swapped by the medium-term scheduler |
| Suspended blocked | Waiting and swapped out to disk | waiting for disk while swapped |
| State transition diagram | The states and the arrows (events) between them | waiting → ready |
| Dispatch | Moving a process from ready to running | the scheduler picks it |
| Preemption | Taking the CPU away from a running process | time slice over |
| Job queue | All jobs waiting to enter the system | batch jobs on disk |
| Ready queue | Processes in memory ready to run | list of PCBs |
| Device queue | Processes waiting for one device | disk queue |
| Long-term scheduler | Admits jobs into memory | job scheduler |
| Short-term scheduler | Picks the next process to run | CPU scheduler |
| Medium-term scheduler | Swaps processes out of and into memory | swapper |
| Swapping | Moving whole processes between RAM and disk | RAM full |
| Swap space | Disk area used for swapped-out memory | swap partition |
| Degree of multiprogramming | Number of processes in memory at once | 5 processes loaded |
| Context | A process's registers, PC, state and memory info | saved in the PCB |
| Context switch | Saving one context and loading another | timer interrupt → new process |
| Voluntary context switch | The process gave up the CPU by blocking | each usleep |
| Nonvoluntary context switch | The scheduler took the CPU away | time slice ended |
| Dispatcher | Kernel module that gives the CPU to the chosen process | switch context, user mode, jump |
| Dispatch latency | Time to stop one process and start another | microseconds |
| Overhead | Time spent on bookkeeping instead of useful work | context switches |
| CPU burst | A stretch of computing | the sum loop |
| I/O burst | A stretch of waiting for input/output | waiting for a key |
| CPU-bound | Spends most time computing | video encoder |
| I/O-bound | Spends most time waiting for I/O | text editor |
/proc/self/status |
Kernel-generated file describing the calling process | State, ctxt_switches |
Summary
- A program is a passive file; a process is that program in execution. Running it twice gives two processes with different PIDs and addresses.
- A process's memory: text, data, BSS, heap (grows up), stack (grows down). ASLR randomises where each part starts.
- The kernel keeps a PCB per process: PID, state, PC, registers, scheduling, memory, accounting and I/O info.
- States: new, ready, running, waiting, terminated, plus suspended ready and suspended blocked. Waiting goes to ready, never straight to running. Our
usleeploop made 20 voluntary switches. - Queues: job, ready, device. Schedulers: long-term (admits, controls the degree of multiprogramming), short-term (picks who runs), medium-term (swaps).
- A context switch saves one context and loads another; the dispatcher does it, taking the dispatch latency. It is pure overhead.
- Processes alternate CPU bursts and I/O bursts: CPU-bound vs I/O-bound.
Next episode: process creation in code: fork, exec and wait, zombie and orphan processes, and fork counting.