Processes and Threads

1. Processes

1.1 Definition

A process is a running instance of a program and is the basic unit of resource allocation by the operating system.

Each process has its own independent:

Virtual address space (code, data, heap, stack segments)
File descriptor table
Signal handler table
Process ID (PID)

1.2 Process Control Block (PCB)

The OS uses a PCB (Process Control Block) to maintain metadata for each process:

Field	Content
PID	Process identifier
Process state	Running / Ready / Waiting / ...
PC (Program Counter)	Address of the next instruction to execute
CPU registers	Snapshot of general-purpose registers, stack pointer, etc.
Scheduling info	Priority, scheduling queue pointers
Memory management info	Page table base address, segment table
I/O status	List of open files, I/O requests

1.3 Process State Transitions

stateDiagram-v2
    [*] --> New: Created
    New --> Ready: Admitted to ready queue
    Ready --> Running: Scheduler selects
    Running --> Ready: Time slice expired / Preempted
    Running --> Waiting: Waiting for I/O or event
    Waiting --> Ready: I/O complete / Event occurred
    Running --> Terminated: Execution finished / Abnormal exit
    Terminated --> [*]

1.4 Process Creation and Termination

UNIX/Linux model:

fork(): Create a child process (copies parent's address space, COW optimization)
exec(): Replace process image with a new program
wait() / waitpid(): Parent waits for child termination
exit(): Process termination

Process tree: All processes form a tree rooted at init/systemd (PID 1).

2. Threads

2.1 Definition

A thread is the basic unit of CPU scheduling. Threads within the same process share the address space and resources.

Attribute	Process	Thread
Address space	Independent	Shared (within same process)
Creation overhead	Large (requires copying address space)	Small (only stack and registers needed)
Context switch	Slow (requires page table switch, TLB flush)	Fast (shared address space)
Communication	IPC (pipes, messages, shared memory)	Direct read/write of shared variables
Isolation	Strong	Weak (one thread crash affects entire process)

2.2 Thread Implementation

Type	Implementation Location	Advantages	Disadvantages
User-level threads	User-space thread library	Fast switching, no kernel involvement	One thread blocking -> entire process blocks
Kernel-level threads	OS kernel	True parallelism, can utilize multiple cores	Switching requires kernel trap, higher overhead
Hybrid model	M:N mapping	Combines advantages of both	Complex implementation

Modern practice:

Linux: 1:1 model (NPTL), each user thread maps to one kernel thread
Go: M:N model (goroutine -> OS thread), runtime scheduler manages scheduling

2.3 Context Switching

Overhead of context switching:

Operation	Source of Overhead
Save/restore registers	Direct CPU time
TLB flush (process switch)	Increased TLB misses after switch
Cache pollution	New process/thread data evicts old data
Pipeline flush	Branch predictor state invalidated

Typical overhead: Process switch ~1-10 us, thread switch ~0.1-1 us.

3. CPU Scheduling

3.1 Scheduling Criteria

Metric	Meaning	Optimization Goal
CPU utilization	Fraction of time CPU is busy	Maximize
Throughput	Processes completed per unit time	Maximize
Turnaround time	Total time from submission to completion	Minimize
Waiting time	Total time spent in ready queue	Minimize
Response time	Time from submission to first response	Minimize (interactive systems)

3.2 Scheduling Algorithms

FCFS (First Come First Served)

First come, first served; non-preemptive
Convoy effect: Long processes block short processes behind them

SJF / SRTF

SJF (Shortest Job First): Select the process with shortest estimated run time (non-preemptive)
SRTF (Shortest Remaining Time First): Preemptive version of SJF
Theoretically optimal (minimizes average waiting time), but requires advance knowledge of run time

\[ \text{Average wait time}_{\text{SJF}} \leq \text{Average wait time}_{\text{any other algorithm}} \]

In practice, exponential weighted moving average is used to predict the next CPU burst:

\[ \tau_{n+1} = \alpha \cdot t_n + (1 - \alpha) \cdot \tau_n \]

Round Robin

Each process receives a fixed time quantum \(q\)
When the quantum expires -> back to the end of the ready queue
\(q\) too large -> degenerates to FCFS; \(q\) too small -> excessive context switch overhead
Typical values: 10-100 ms

MLFQ (Multi-Level Feedback Queue)

The foundational scheduling framework for modern operating systems:

Rules:

Processes in higher-priority queues execute first
Within the same priority queue, use Round Robin
New processes enter the highest-priority queue
Time quantum exhausted -> demoted to the next queue
Periodically boost all processes to the highest priority (Boost, prevents starvation)

Priority High  [Q0] -- RR, quantum = 8ms
               [Q1] -- RR, quantum = 16ms
               [Q2] -- RR, quantum = 32ms
Priority Low   [Q3] -- FCFS

I/O-intensive processes: Frequently yield CPU -> stay at high priority -> fast response
CPU-intensive processes: Exhaust time quantum -> gradually demoted -> don't affect interactivity

CFS (Completely Fair Scheduler)

Default Linux scheduler (since 2.6.23):

Goal: Each process receives a fair share of CPU time
Uses virtual runtime (vruntime) to track CPU time each process has received
Maintains the ready queue in a red-black tree; the process with the smallest vruntime runs next
nice value affects the rate at which vruntime increases

4. Process Synchronization

4.1 Race Conditions

Multiple threads concurrently access shared data, and the outcome depends on execution order.

Critical Section: The code segment that accesses shared resources and requires mutual exclusion protection.

A critical section solution must satisfy:

Mutual Exclusion: Only one thread in the critical section at a time
Progress: Threads not in the critical section cannot block others from entering
Bounded Waiting: There is an upper bound on waiting time to enter the critical section

4.2 Synchronization Primitives

Mutex

pthread_mutex_lock(&mutex);    // Acquire lock (blocking)
// Critical section
pthread_mutex_unlock(&mutex);  // Release lock

Implementation basis: Atomic instructions (CAS, test-and-set, LL/SC)

Spinlock

while (test_and_set(&lock) == 1)
    ; // Busy-wait (spin)
// Critical section
lock = 0;

Efficient when wait time is short (no context switch)
Wastes CPU when wait time is long
Suitable for short critical sections in multi-core environments

Semaphore

Proposed by Dijkstra; a more general synchronization mechanism:

P (wait/down): \(S \leftarrow S - 1\); if \(S < 0\), block
V (signal/up): \(S \leftarrow S + 1\); if there are waiters, wake one

Type	Initial Value	Use
Binary semaphore	1	Equivalent to a mutex
Counting semaphore	\(N\)	Control concurrent access to resources

Condition Variable

Used with a mutex; allows threads to wait when a condition is not met:

pthread_mutex_lock(&mutex);
while (!condition)
    pthread_cond_wait(&cond, &mutex);  // Atomically release lock + sleep
// Condition is met, proceed
pthread_mutex_unlock(&mutex);

Must Use while, Not if

After cond_wait returns, the condition may have been changed by another thread (spurious wakeup); the condition must be rechecked.

4.3 Classic Synchronization Problems

Producer-Consumer (Bounded Buffer)

Semaphores:
  mutex = 1          // Mutual exclusion for buffer access
  empty = N          // Number of empty slots
  full = 0           // Number of filled slots

Producer:                       Consumer:
  P(empty)                       P(full)
  P(mutex)                       P(mutex)
  Insert data                    Remove data
  V(mutex)                       V(mutex)
  V(full)                        V(empty)

Readers-Writers Problem

Readers-priority: Multiple readers can read simultaneously; writers wait for all readers to finish
Writers-priority: When a writer arrives, new readers wait
Fair version: Process in arrival order

Dining Philosophers Problem

5 philosophers sit around a round table with one chopstick between each pair; both chopsticks are needed to eat.

Solutions:

Allow at most 4 philosophers to attempt picking up chopsticks simultaneously
Odd-numbered philosophers pick left first then right; even-numbered do the opposite (break circular wait)
Use a single global lock (reduces concurrency)

5. Deadlock

5.1 Necessary Conditions (Coffman Conditions)

Deadlock can occur only when all four conditions hold simultaneously:

Mutual Exclusion: Resources cannot be shared
Hold and Wait: Processes holding resources can request new ones
No Preemption: Resources cannot be forcibly reclaimed
Circular Wait: A circular chain of processes exists, each waiting for a resource held by the next

5.2 Handling Strategies

Strategy	Method	Practical Application
Prevention	Break one of the four conditions	Resource ordering (breaks circular wait)
Avoidance	Dynamically check safety	Banker's algorithm
Detection + Recovery	Allow occurrence, detect and handle	Databases (timeout + rollback)
Ostrich strategy	Ignore the problem	Most general-purpose OSes

5.3 Banker's Algorithm

A deadlock avoidance algorithm proposed by Dijkstra. Before allocating resources, the system checks whether a safe sequence exists.

Data structures (\(n\) processes, \(m\) resource types):

\(\text{Available}[m]\): Currently available resource vector
\(\text{Max}[n][m]\): Maximum demand of each process
\(\text{Allocation}[n][m]\): Currently allocated
\(\text{Need}[n][m] = \text{Max} - \text{Allocation}\)

Safety check:

Initialize \(\text{Work} = \text{Available}\), \(\text{Finish}[i] = \text{false}\)
Find process \(i\) such that \(\text{Finish}[i] = \text{false}\) and \(\text{Need}[i] \leq \text{Work}\)
\(\text{Work} = \text{Work} + \text{Allocation}[i]\), \(\text{Finish}[i] = \text{true}\)
Repeat until all processes are finished or no executable process is found
If all \(\text{Finish}[i] = \text{true}\), the system is in a safe state

\[ \text{Time complexity} = O(n^2 \times m) \]

6. Inter-Process Communication (IPC)

Mechanism	Characteristics	Use Case
Pipe	Unidirectional, byte stream, parent-child processes	Shell pipes `\\|`
Named Pipe (FIFO)	Has a filename, no kinship required	Simple IPC
Message Queue	Structured messages	Asynchronous communication
Shared Memory	Fastest (no copying)	Large data transfer
Signal	Asynchronous notification	Process control (SIGKILL, etc.)
Socket	Cross-network	Network communication

Navigation

Next: Memory Management
Related: Memory Hierarchy Design