Process Concepts
Process Concepts¶
Overview¶
A process is a program in execution. This lesson covers process memory structure, Process Control Block (PCB), process state transitions, and context switching.
Table of Contents¶
- What is a Process?
- Process Memory Structure
- Process Control Block (PCB)
- Process State Transitions
- Context Switch
- Process Creation and Termination
- Practice Problems
1. What is a Process?¶
Program vs Process¶
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Program vs Process β
ββββββββββββββββββββββ¬ββββββββββββββββββββββββββββββββββββ€
β Program β Process β
ββββββββββββββββββββββΌββββββββββββββββββββββββββββββββββββ€
β Static entity β Dynamic entity β
β Stored on disk β Loaded in memory β
β Executable file β Executing file β
β Passive β Active β
β Doesn't change β State constantly changes β
ββββββββββββββββββββββ΄ββββββββββββββββββββββββββββββββββββ
Program ββ(load)βββΆ Process
Load into
memory
Components of a Process¶
Process = Code + Data + Stack + Heap + PCB
βββββββββββββββββββββββββββββββββββββββ
β Process β
βββββββββββββββββββββββββββββββββββββββ€
β βββββββββββββββββββββββββββββββββ β
β β Text (Code) Section β β Instructions to execute
β βββββββββββββββββββββββββββββββββ€ β
β β Data Section β β Global/static variables
β βββββββββββββββββββββββββββββββββ€ β
β β Heap β β Dynamic allocation
β βββββββββββββββββββββββββββββββββ€ β
β β Stack β β Local vars, function calls
β βββββββββββββββββββββββββββββββββ β
β β
β βββββββββββββββββββββββββββββββββ β
β β PCB (stored in kernel) β β Process metadata
β βββββββββββββββββββββββββββββββββ β
βββββββββββββββββββββββββββββββββββββββ
2. Process Memory Structure¶
Memory Layout¶
High address (0xFFFFFFFF)
βββββββββββββββββββββββββββββββββββββββ
β Kernel Space β OS only (no user access)
βββββββββββββββββββββββββββββββββββββββ€ β 0xC0000000 (Linux 32-bit)
β β
β Stack β Local variables, parameters
β β Grows downward β Return addresses
β β
β β β β β β β β β β β β β β β β β β β€
β β
β β Grows upward β
β Heap β malloc, new
β β
βββββββββββββββββββββββββββββββββββββββ€
β BSS β Uninitialized global/static
βββββββββββββββββββββββββββββββββββββββ€
β Data β Initialized global/static
βββββββββββββββββββββββββββββββββββββββ€
β Text (Code) β Program code (read-only)
βββββββββββββββββββββββββββββββββββββββ
Low address (0x00000000)
Section Details¶
#include <stdio.h>
#include <stdlib.h>
// BSS section: uninitialized global
int uninit_global;
// Data section: initialized global
int init_global = 42;
// Data section: static variable
static int static_var = 100;
void example_function(int param) { // param: stack
int local_var = 10; // stack
static int func_static = 0; // Data section
int *heap_ptr;
heap_ptr = malloc(sizeof(int)); // Allocate on heap
*heap_ptr = 20;
printf("local: %d, heap: %d\n", local_var, *heap_ptr);
free(heap_ptr); // Free heap memory
}
// Text section: this code itself
int main() {
example_function(5);
return 0;
}
Memory Region Characteristics¶
ββββββββββββ¬βββββββββββ¬βββββββββββ¬βββββββββββββββββββββββββ
β Section β Read β Write β Purpose β
ββββββββββββΌβββββββββββΌβββββββββββΌβββββββββββββββββββββββββ€
β Text β O β X β Program code β
β Data β O β O β Initialized global/staticβ
β BSS β O β O β Uninitialized global/staticβ
β Heap β O β O β Dynamic allocation β
β Stack β O β O β Local vars, function callsβ
ββββββββββββ΄βββββββββββ΄βββββββββββ΄βββββββββββββββββββββββββ
Stack Frame¶
Function call stack structure:
int add(int a, int b) {
int result = a + b;
return result;
}
int main() {
int x = add(3, 5);
return 0;
}
βββββββββββββββββββββββββββββββ β High address
β ... β
βββββββββββββββββββββββββββββββ€
β main() stack frame β
β βββββββββββββββββββββββββ β
β β x (local variable) β β
β β Previous frame pointerβ β
β β Return address β β
β βββββββββββββββββββββββββ β
βββββββββββββββββββββββββββββββ€
β add() stack frame β
β βββββββββββββββββββββββββ β
β β result (local var) β β
β β Previous frame pointerβ β
β β Return address β β
β β b = 5 (parameter) β β
β β a = 3 (parameter) β β
β βββββββββββββββββββββββββ β
βββββββββββββββββββββββββββββββ€ β Stack Pointer (SP)
β ... β
βββββββββββββββββββββββββββββββ β Low address
3. Process Control Block (PCB)¶
What is PCB?¶
PCB (Process Control Block) = Data structure containing all info to manage a process
= Maintained by kernel
= Stored in process table
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β PCB Structure β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Process Identifier (PID) β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ€ β
β β Process State (Ready, Running, Waiting...) β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ€ β
β β Program Counter (PC) - next instruction address β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ€ β
β β CPU Registers (general purpose, SP, flags...) β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ€ β
β β CPU Scheduling Info (priority, scheduling queue) β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ€ β
β β Memory Management Info (page table, segment table)β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ€ β
β β Accounting Info (CPU time used, start time...) β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ€ β
β β I/O Status Info (open files, I/O devices...) β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Linux task_struct (Simplified)¶
// Linux kernel process structure (simplified)
struct task_struct {
// Process identification
pid_t pid; // Process ID
pid_t tgid; // Thread group ID
// Process state
volatile long state; // TASK_RUNNING, TASK_INTERRUPTIBLE...
// Scheduling info
int prio; // Dynamic priority
int static_prio; // Static priority
struct sched_entity se; // Scheduling entity
// CPU context
struct thread_struct thread; // CPU register state
// Memory management
struct mm_struct *mm; // Memory descriptor
// File system
struct files_struct *files; // Open file table
struct fs_struct *fs; // File system info
// Process relationships
struct task_struct *parent; // Parent process
struct list_head children; // Children processes list
struct list_head sibling; // Sibling processes list
// Signals
struct signal_struct *signal;
// Timing info
u64 utime, stime; // User/system CPU time
u64 start_time; // Start time
};
Process Table¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Process Table β
βββββββ¬βββββββββββββββββββββββββββββββββββββββββββββββββββ€
β PID β PCB β
βββββββΌβββββββββββββββββββββββββββββββββββββββββββββββββββ€
β 1 β init: state=Running, priority=20, mem=4MB... β
βββββββΌβββββββββββββββββββββββββββββββββββββββββββββββββββ€
β 2 β kthreadd: state=Sleeping, priority=10... β
βββββββΌβββββββββββββββββββββββββββββββββββββββββββββββββββ€
β 100 β bash: state=Ready, priority=20, mem=8MB... β
βββββββΌβββββββββββββββββββββββββββββββββββββββββββββββββββ€
β 101 β vim: state=Waiting, priority=20, mem=12MB... β
βββββββΌβββββββββββββββββββββββββββββββββββββββββββββββββββ€
β ... β ... β
βββββββ΄βββββββββββββββββββββββββββββββββββββββββββββββββββ
4. Process State Transitions¶
5-State Model¶
New
β
β Admitted
βΌ
ββββββββββββββββ Dispatch ββββββββββββββββ
β βββββββββββΆβ β
β Ready β β Running ββββββββ Exit
β ββββββββββββ β β
β β Interrupt β β β
ββββββββββββββββ(Timeout) ββββββββββββββββ β
β² β βΌ
β β ββββββββββββ
β I/O or β βTerminatedβ
β Event Complete β β β
β β ββββββββββββ
β β I/O or
β β Event Wait
β βΌ
β ββββββββββββββββ
ββββββββββββββββ Waiting β
β β
ββββββββββββββββ
State Descriptions¶
ββββββββββββββββββ¬βββββββββββββββββββββββββββββββββββββββββ
β State β Description β
ββββββββββββββββββΌβββββββββββββββββββββββββββββββββββββββββ€
β New β Process being created β
ββββββββββββββββββΌβββββββββββββββββββββββββββββββββββββββββ€
β Ready β Waiting for CPU assignment β
β β Ready to execute β
ββββββββββββββββββΌβββββββββββββββββββββββββββββββββββββββββ€
β Running β Executing instructions on CPU β
β β Only one process at a time (single CPU)β
ββββββββββββββββββΌβββββββββββββββββββββββββββββββββββββββββ€
β Waiting β Waiting for I/O or event completion β
β β Transitions to Ready when I/O completesβ
ββββββββββββββββββΌβββββββββββββββββββββββββββββββββββββββββ€
β Terminated β Execution completed, releasing resourcesβ
β β β
ββββββββββββββββββ΄βββββββββββββββββββββββββββββββββββββββββ
State Transition Conditions¶
βββββββββββββββββββ¬ββββββββββββββββββββββββββββββββββββββββββ
β Transition β Condition β
βββββββββββββββββββΌββββββββββββββββββββββββββββββββββββββββββ€
β New β Ready β OS admits process β
βββββββββββββββββββΌββββββββββββββββββββββββββββββββββββββββββ€
β Ready β Running β Scheduler assigns CPU (dispatch) β
βββββββββββββββββββΌββββββββββββββββββββββββββββββββββββββββββ€
β Running β Ready β Time slice expired (timeout) β
β β Higher priority process arrives (preempt)β
βββββββββββββββββββΌββββββββββββββββββββββββββββββββββββββββββ€
β Running β Wait β I/O request, event wait β
βββββββββββββββββββΌββββββββββββββββββββββββββββββββββββββββββ€
β Wait β Ready β I/O complete, event occurs β
βββββββββββββββββββΌββββββββββββββββββββββββββββββββββββββββββ€
β Running β Term β exit() call, normal/abnormal terminationβ
βββββββββββββββββββ΄ββββββββββββββββββββββββββββββββββββββββββ
7-State Model (Including Swapping)¶
ββββββββββββββββββββββββββββββββββββ
β β
β Swap out β
βΌ β β
βββββββββββ βββββββββββ βββββ΄ββββββ β
β New ββββββββββββΆβ Ready βββββββββββΆβ Ready β β
β β β β Swap in β Suspend β β
βββββββββββ βββββββββββ βββββββββββ β
β β
Dispatch β
β β
βΌ β
βββββββββββ βββββββββββ β
β Term βββββββββββββ Running β β
β β β β β
βββββββββββ βββββββββββ β
β β
I/O Request β
β β
βΌ Swap out β
βββββββββββ βββββββββββ β
β Waiting βββββββββββΆβ Waiting ββββββββββ
β β Swap in β Suspend β
βββββββββββ βββββββββββ
Suspend state: Process swapped out from memory to disk
5. Context Switch¶
What is a Context Switch?¶
Context Switch = Process of switching CPU to another process
= Save current process state, restore new process state
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Context Switch Process β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Process P0 Operating System Process P1
β β β
β Executing β β Waiting
β β β
βββInterrupt/SyscallβββΆβ β
β β β
β Save state to PCB0 β
β β β
β Restore state from PCB1 β
β β β
β ββββββββββββββββββββββββΆβ
β Waiting β β Executing
β β β
β ββββInterrupt/Syscallβββ
β β β
β Save state to PCB1 β
β β β
β Restore state from PCB0 β
β β β
ββββββββββββββββββββββββ β
β Executing β β Waiting
Information Saved/Restored in Context Switch¶
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Context β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β CPU Registers: β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β’ Program Counter (PC) β β
β β β’ Stack Pointer (SP) β β
β β β’ Base Pointer (BP) β β
β β β’ General Purpose Registers (RAX, RBX, RCX, RDX...)β β
β β β’ Status Register (FLAGS) β β
β β β’ Floating Point Registers β β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Memory Management Info: β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β β’ Page Table Base Register β β
β β β’ Segment Registers β β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Context Switch Cost¶
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Context Switch Cost β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Direct cost: β
β β’ Register save/restore: ~hundreds of nanoseconds β
β β’ Kernel mode transition: ~hundreds of nanoseconds β
β β
β Indirect cost (larger): β
β β’ TLB flush: hundreds~thousands of cycles β
β β’ Cache miss increase (cache pollution) β
β β’ Pipeline flush β
β β
β Typical total cost: 1~10 microseconds β
β β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Timeline view of context switch:
P0 exec β Context Switch β P1 exec β Context Switch β P0 exec
βββββββββ Overhead ββββββββββ Overhead ββββββββ
ββ ~1-10 ΞΌs ββ ββ ~1-10 ΞΌs ββ
β No useful work during this time
6. Process Creation and Termination¶
Process Creation with fork()¶
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
int main() {
pid_t pid;
int x = 10;
printf("Parent process starting, PID: %d\n", getpid());
pid = fork(); // Fork point
if (pid < 0) {
// fork failed
perror("fork failed");
return 1;
}
else if (pid == 0) {
// Child process
printf("Child: PID=%d, Parent PID=%d\n", getpid(), getppid());
x = x + 10;
printf("Child: x = %d\n", x);
}
else {
// Parent process
printf("Parent: PID=%d, Child PID=%d\n", getpid(), pid);
wait(NULL); // Wait for child termination
printf("Parent: x = %d\n", x); // Still 10
}
return 0;
}
/*
Output:
Parent process starting, PID: 1234
Parent: PID=1234, Child PID=1235
Child: PID=1235, Parent PID=1234
Child: x = 20
Parent: x = 10
*/
How fork() Works¶
Before fork():
βββββββββββββββββββββββββββββββββββ
β Parent Process (PID: 100) β
β βββββββββββββββββββββββββββ β
β β x = 10 β β
β β Code/Data/Stack/Heap β β
β βββββββββββββββββββββββββββ β
βββββββββββββββββββββββββββββββββββ
After fork():
βββββββββββββββββββββββββββββββββββ βββββββββββββββββββββββββββββββββββ
β Parent Process (PID: 100) β β Child Process (PID: 101) β
β βββββββββββββββββββββββββββ β β βββββββββββββββββββββββββββ β
β β x = 10 β β β β x = 10 (copied) β β
β β Code/Data/Stack/Heap β β β β Code/Data/Stack/Heap β β
β β fork() returns: 101 β β β β fork() returns: 0 β β
β βββββββββββββββββββββββββββ β β βββββββββββββββββββββββββββ β
βββββββββββββββββββββββββββββββββββ βββββββββββββββββββββββββββββββββββ
β β
β Two processes are independent β
β (separate memory spaces) β
βΌ βΌ
Program Execution with exec()¶
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
int main() {
pid_t pid = fork();
if (pid == 0) {
// Child process: execute ls command
printf("Child: executing ls\n");
// execl: exec with list of arguments
execl("/bin/ls", "ls", "-l", NULL);
// If exec succeeds, this code won't execute
perror("exec failed");
return 1;
}
else {
// Parent process
wait(NULL);
printf("Parent: child terminated\n");
}
return 0;
}
How exec() Works¶
Before exec():
βββββββββββββββββββββββββββββββββββ
β Child Process β
β βββββββββββββββββββββββββββ β
β β Original program code β β
β β Original data β β
β β Original stack/heap β β
β βββββββββββββββββββββββββββ β
βββββββββββββββββββββββββββββββββββ
After exec("/bin/ls"):
βββββββββββββββββββββββββββββββββββ
β Child Process β
β βββββββββββββββββββββββββββ β
β β ls program code β β β Completely replaced
β β ls data β β with new program
β β New stack/heap β β
β βββββββββββββββββββββββββββ β
β β
β PID remains the same β
βββββββββββββββββββββββββββββββββββ
Process Termination¶
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
int main() {
pid_t pid = fork();
if (pid == 0) {
printf("Child process terminating\n");
exit(42); // Exit with status code 42
}
else {
int status;
wait(&status); // Collect child's exit status
if (WIFEXITED(status)) {
printf("Child exit code: %d\n", WEXITSTATUS(status));
}
}
return 0;
}
/*
Output:
Child process terminating
Child exit code: 42
*/
Zombie and Orphan Processes¶
Zombie Process:
- Child has terminated but parent hasn't called wait()
- PCB remains (stores exit status)
- Resources released but process table entry maintained
ββββββββββββββββββββββββββββββββββββββββββββββββ
β Parent Process (PID: 100) β
β - Hasn't called wait() β
ββββββββββββββββββββββββββββββββββββββββββββββββ
β
β (Relationship maintained)
βΌ
ββββββββββββββββββββββββββββββββββββββββββββββββ
β Zombie Process (PID: 101) β
β - State: Z (Zombie) β
β - Code/Data/Stack released β
β - Only PCB remains β
ββββββββββββββββββββββββββββββββββββββββββββββββ
Orphan Process:
- Parent terminated before child
- init (PID 1) or systemd becomes new parent
ββββββββββββββββββββββββββββββββββββββββββββββββ
β init (PID: 1) β
β - New parent of orphan processes β
β - Periodically calls wait() β
ββββββββββββββββββββββββββββββββββββββββββββββββ
β
β (Adoption)
βΌ
ββββββββββββββββββββββββββββββββββββββββββββββββ
β Orphan Process (PID: 102) β
β - Original parent (PID: 100) terminated β
β - PPID changed to 1 β
ββββββββββββββββββββββββββββββββββββββββββββββββ
7. Practice Problems¶
Problem 1: Memory Region Identification¶
Identify the memory region where each variable is stored.
int global_var = 100; // ( )
int uninitialized; // ( )
const char* str = "hello"; // ( )
void func() {
int local = 10; // ( )
static int stat = 20; // ( )
int* ptr = malloc(4); // ptr: ( ), *ptr: ( )
}
Options: Text, Data, BSS, Stack, Heap
Show Answer
int global_var = 100; // (Data)
int uninitialized; // (BSS)
const char* str = "hello"; // str: Data, "hello": Text (read-only)
void func() {
int local = 10; // (Stack)
static int stat = 20; // (Data)
int* ptr = malloc(4); // ptr: (Stack), *ptr: (Heap)
}
Problem 2: Process State Transitions¶
Explain the process state transitions in the following situations.
- Process A is using CPU, time slice expires
- Process B requests file read
- Process C's file read completes
- Scheduler selects process D
Show Answer
1. A: Running β Ready (timeout/interrupt) 2. B: Running β Waiting (I/O request) 3. C: Waiting β Ready (I/O complete) 4. D: Ready β Running (dispatch)Problem 3: fork() Output Prediction¶
Predict the output of the following code.
#include <stdio.h>
#include <unistd.h>
int main() {
printf("A\n");
fork();
printf("B\n");
fork();
printf("C\n");
return 0;
}
Show Answer
A (1 output - original process)
B (2 outputs - 2 processes after first fork)
B
C (4 outputs - 4 processes after second fork)
C
C
C
Total: A 1 time, B 2 times, C 4 times
Process branching:
main
β
βββββββ΄ββββββ
β fork() β
β β
main child1
β β
ββββ΄βββ ββββ΄βββ
βfork()β βfork()β
β β β β
main c2 c1 c3
4 processes each print "C"
Problem 4: PCB Information¶
Explain the changes to PCB information in the following situations.
- When a process transitions from Running to Waiting
- When a context switch occurs
Show Answer
1. Running β Waiting transition: - PCB's state field changes from Running to Waiting - I/O status info records the waiting I/O operation - Process moves to waiting queue 2. Context switch: - Save current process's PC, registers, stack pointer to PCB - Restore PC, registers, stack pointer from new process's PCB - Update memory management info (page table) - Change new process's state to RunningProblem 5: Context Switch Cost¶
Describe two direct costs and two indirect costs of context switching.
Show Answer
**Direct costs:** 1. Register save/restore: Time to save current process's registers to PCB and restore new process's registers 2. Kernel mode transition: Overhead of transitioning from user mode to kernel mode and back **Indirect costs:** 1. Cache pollution: New process's data not in cache, increasing cache misses 2. TLB flush: New process uses different virtual address space, invalidating TLB entriesNext Steps¶
- 03_Threads_and_Multithreading.md - Thread concepts and multithreading models