Threads and Concurrent Programming
Open in the Padhaiko app3.1 Thread models and lifecycle
A thread (lightweight process) is the smallest schedulable unit of CPU execution inside a process. All threads belonging to the same process share a single virtual address space—meaning they share global variables, heap memory (malloc), executable code, and open file descriptors—while each thread maintains its own private Thread ID (TID), CPU registers, Program Counter (PC), errno, and private call stack.
+-------------------------------------------------------------------+
| SHARED ACROSS ALL THREADS IN PROCESS |
| [ Text (Code) ] [ Data / BSS ] [ Heap ] [ Open FD Table ] |
+-------------------------------------------------------------------+
| Thread 1 Private | Thread 2 Private | Thread 3 Priv. |
| - TID, Registers, PC | - TID, Registers, PC | - TID, Regs |
| - Private Stack | - Private Stack | - Private Stack|
| - Thread-local errno | - Thread-local errno | - Thread errno |
+-------------------------------------------------------------------+Thread Mapping Models
Operating systems map user-created threads onto kernel-scheduled threads using three architectural models:
| Model | Mapping | Concurrency on Multi-Core? | Blocking Syscall Impact | Examples |
|---|---|---|---|---|
| Many-to-One | Many user threads -> 1 kernel thread | No (only 1 thread runs at a time) | Blocks all user threads in the process | Legacy green-thread libraries |
| One-to-One | 1 user thread -> 1 kernel thread (clone()) | Yes (true parallel multi-core) | Blocks only the calling thread | Linux NPTL (pthreads), Windows threads |
| Many-to-Many (M:N) | M user threads -> N kernel threads (N <= M) | Yes (up to N cores) | Other user threads continue on remaining kernel threads | Go goroutines (M:N runtime scheduler) |
Thread Lifecycle
- New / Created: Thread structure and private stack are allocated via
pthread_create(). - Ready / Runnable: Thread is eligible for CPU scheduling in the kernel run queue.
- Running: Actively executing instructions on a CPU core.
- Blocked / Waiting: Suspended waiting for a mutex, condition variable (
pthread_cond_wait), I/O, orpthread_join(). - Terminated: Returns from its start routine or calls
pthread_exit(). If joinable, its return value and kernel metadata remain until another thread callspthread_join(); if detached, resources are reclaimed immediately upon exit.
3.2 POSIX threads (Pthreads)
The POSIX Threads (Pthreads) API (<pthread.h>, linked with -pthread) is the standard C/C++ threading interface on Linux and Unix systems.
| Function | Purpose |
|---|---|
int pthread_create(pthread_t *tid, const pthread_attr_t *attr, void *(*fn)(void *), void *arg); | Spawns a new thread executing fn(arg). Returns 0 on success or positive error number on failure (does not use errno). |
int pthread_join(pthread_t tid, void **retval); | Blocks the calling thread until tid finishes and retrieves its return pointer; frees tid's resources. |
int pthread_detach(pthread_t tid); | Marks tid as detached so its resources are reclaimed automatically on exit (cannot be joined afterward). |
void pthread_exit(void *retval); | Terminates only the calling thread (unlike exit(), which kills the entire process and all threads). |
pthread_t pthread_self(void); | Returns the pthread_t identifier of the calling thread. |
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int worker_id;
int port;
} worker_arg_t;
void *worker_fn(void *arg) {
worker_arg_t *cfg = (worker_arg_t *)arg;
printf("Worker %d handling port %d\n", cfg->worker_id, cfg->port);
int *result = malloc(sizeof(int));
*result = cfg->worker_id * 10;
return result; /* retrieved via pthread_join */
}
int main(void) {
pthread_t tids[2];
worker_arg_t args[2] = {{1, 8080}, {2, 8081}};
for (int i = 0; i < 2; i++) {
pthread_create(&tids[i], NULL, worker_fn, &args[i]);
}
for (int i = 0; i < 2; i++) {
void *ret = NULL;
pthread_join(tids[i], &ret);
printf("Joined worker %d -> result=%d\n", i + 1, *(int *)ret);
free(ret);
}
return 0;
}3.3 Thread synchronization: Mutexes, condition variables
Because threads share global and heap memory, concurrent unsynchronized reads and writes corrupt shared data structures. Pthreads provides mutexes for mutual exclusion and condition variables for efficient event signaling.
Mutexes (pthread_mutex_t)
Mutual Exclusion Lock (Mutex)
A mutex is a locking primitive that ensures at most one thread executes a critical section of code at any instant. Unlike a binary semaphore, a mutex has ownership: only the thread that locked the mutex is permitted to unlock it.
pthread_mutex_lock(&m): Acquires the lock, or puts the thread to sleep if another thread holds it.pthread_mutex_trylock(&m): Attempts to acquire the lock without blocking; returnsEBUSYimmediately if already held.pthread_mutex_unlock(&m): Releases ownership and wakes a waiting thread.
Condition Variables (pthread_cond_t)
Busy-waiting in a while loop (while (queue_empty) {}) wastes 100% of a CPU core. Condition variables allow a thread to sleep with zero CPU usage until another thread modifies shared state and notifies it:
pthread_cond_wait(&cond, &mutex): Must be called while holdingmutex. It atomically unlocksmutexand puts the thread to sleep oncond. When signaled, it wakes up and re-acquiresmutexbefore returning.pthread_cond_signal(&cond): Wakes at least one thread waiting oncond.pthread_cond_broadcast(&cond): Wakes all threads waiting oncond(used when multiple consumers or different predicates may become satisfied).
3.4 Deadlocks, race conditions, and avoidance
Race Conditions
Race Condition
A race condition occurs when two or more threads access shared mutable data concurrently—with at least one write—and the final outcome depends on the unpredictable order in which the OS schedules the threads.
Even a single C statement like count++ compiles into three non-atomic CPU instructions:
- Load
countfrom RAM into a register (MOV). - Increment the register (
ADD 1). - Store the register back to RAM (
MOV).
If Thread A and Thread B interleave between load and store when count == 10, both read 10, both increment to 11, and both write 11—losing one update! Protecting count++ with a mutex (or using C11 _Atomic instructions) eliminates the race.
Deadlocks and Coffman's Four Necessary Conditions
A deadlock occurs when a set of threads is permanently blocked because every thread holds a lock needed by another thread in the cycle. Deadlock can occur if and only if all four Coffman conditions hold simultaneously:
| Condition | Meaning | Prevention / Avoidance Strategy |
|---|---|---|
| 1. Mutual Exclusion | Resource/mutex can be held by only one thread at a time | Use lock-free atomics or read-only sharing where possible |
| 2. Hold and Wait | A thread holds at least one lock while waiting for another | Acquire all needed locks together atomically (or release held locks on trylock failure) |
| 3. No Preemption | Locks cannot be forcibly taken from a holding thread | Use pthread_mutex_trylock() / timed locks and back off if unavailable |
| 4. Circular Wait | Closed cycle of threads each waiting on a lock held by the next | Impose a strict global lock ordering (always acquire lower-ID/address mutex before higher-ID mutex) |
- Livelock vs. Deadlock: In a deadlock, threads are blocked sleeping; in a livelock, threads keep actively retrying and backing off in lockstep without making forward progress (fixed via randomized exponential backoff).
- Starvation: A thread waits indefinitely because higher-priority or faster threads repeatedly grab the lock ahead of it.
3.5 Multithreading versus multiprocessing (Performance considerations)
When designing a concurrent network server, engineers choose between multiple processes (fork()), multiple threads (pthread_create()), or a hybrid of both.
| Aspect | Multithreading | Multiprocessing |
|---|---|---|
| Creation Overhead | Low (creates stack + kernel task_struct; shares VM) | Higher (clones page tables, FD table, CoW setup) |
| Context Switch Cost | Faster (no page-table / CR3 switch, no TLB flush) | Slower (switches virtual address space; TLB pressure) |
| Communication Speed | Fastest (direct shared memory + mutexes/atomics) | Slower (requires pipes, sockets, or explicit shm_open) |
| Fault Isolation | Low (a segfault or abort() in 1 thread kills all threads) | High (crash in 1 worker process does not kill siblings) |
| Synchronization Complexity | High (must guard every shared object against race conditions) | Lower (isolated state; only explicit IPC channels shared) |
| Memory Footprint | Smaller (shared code, heap, and static data) | Larger (separate heap/runtime per worker, mitigated by CoW) |
Performance Considerations and Amdahl's Law
- Lock Contention: Adding more threads on a multi-core CPU stops scaling—and can even slow down performance—if threads spend most of their time contending on a single coarse-grained mutex (lock contention) or bouncing cache lines across CPU cores (false sharing).
- Amdahl's Law: If fraction
sof a workload is strictly serial (such as a global mutex critical section), the maximum theoretical speedup acrossNCPU cores is bounded by1 / (s + (1 - s)/N), which never exceeds1 / seven asNgrows arbitrarily large. - Hybrid Server Model: Many production servers (such as Nginx or Gunicorn workers) run one worker process per CPU core (for fault isolation and cache affinity) and use non-blocking I/O or a bounded thread pool inside each worker.
Worked Examples
Calculating Thread Stack Footprint and Amdahl's Speedup Limit
- A Linux x86-64 network server spawns 500 worker threads. The default thread stack reservation on Linux is 8 MiB. Calculate the total virtual memory reserved purely for stacks with default settings, and compare it against setting a custom 512 KiB stack via
pthread_attr_setstacksize(). - Profiling shows that 10% (
s = 0.10) of each request executes inside a global mutex critical section while 90% runs fully in parallel. Using Amdahl's Law, calculate the speedup on an 8-core CPU and the theoretical maximum speedup as cores approach infinity.
Part 1 — Virtual Stack Memory Reservation:
- With default 8 MiB stack per thread:
500 * 8 MiB = 4,000 MiB(~3.91 GiBof virtual address space reserved). - With
pthread_attr_setstacksize(&attr, 512 * 1024):500 * 512 KiB = 256,000 KiB = 250 MiB.
Reducing stack size saves 4,000 - 250 = 3,750 MiB of virtual address reservation.
Part 2 — Amdahl's Law Speedup on 8 Cores (s = 0.10):
- For
N = 8:Speedup(8) = 1 / (0.10 + 0.90 / 8) = 1 / (0.10 + 0.1125) = 1 / 0.2125 = 4.71x. - As
N -> infinity,(1 - s)/N -> 0:Max Speedup = 1 / s = 1 / 0.10 = 10.0x(even with 1,000 cores, a 10% mutex bottleneck caps speedup at10x).
- Default 8 MiB stacks reserve 4,000 MiB; 512 KiB stacks reserve 250 MiB.
- Speedup on 8 cores = 4.71x; theoretical upper bound = 10.0x.
Thread-Safe Bounded Producer-Consumer Queue with Mutex and Condition Variables
Write a C implementation of a thread-safe bounded circular queue (CAP = 8) for passing client socket descriptors from an acceptor thread to worker threads, using pthread_mutex_t and two pthread_cond_t condition variables (not_full, not_empty).
Define the Queue Structure and Synchronization Primitives: Keep head, tail, and count protected by mtx, with not_full signaled when an item is removed and not_empty signaled when an item is inserted.
Implement enqueue() and dequeue() Using while Guards:
#include <pthread.h>
#define CAP 8
typedef struct {
int fds[CAP];
int head, tail, count;
pthread_mutex_t mtx;
pthread_cond_t not_full;
pthread_cond_t not_empty;
} sock_queue_t;
void queue_init(sock_queue_t *q) {
q->head = q->tail = q->count = 0;
pthread_mutex_init(&q->mtx, NULL);
pthread_cond_init(&q->not_full, NULL);
pthread_cond_init(&q->not_empty, NULL);
}
void queue_push(sock_queue_t *q, int client_fd) {
pthread_mutex_lock(&q->mtx);
while (q->count == CAP) { /* while prevents spurious/stolen wakeup bugs */
pthread_cond_wait(&q->not_full, &q->mtx);
}
q->fds[q->tail] = client_fd;
q->tail = (q->tail + 1) % CAP;
q->count++;
pthread_cond_signal(&q->not_empty);
pthread_mutex_unlock(&q->mtx);
}
int queue_pop(sock_queue_t *q) {
pthread_mutex_lock(&q->mtx);
while (q->count == 0) {
pthread_cond_wait(&q->not_empty, &q->mtx);
}
int fd = q->fds[q->head];
q->head = (q->head + 1) % CAP;
q->count--;
pthread_cond_signal(&q->not_full);
pthread_mutex_unlock(&q->mtx);
return fd;
}The circular buffer guards head, tail, and count with mtx, sleeps cleanly inside while loops via pthread_cond_wait(), and signals the complementary condition variable (not_empty or not_full) before releasing the mutex.
Diagnosing and Fixing an AB-BA Deadlock via Lock Ordering
Examine the following transfer() function called concurrently by Thread 1 (transfer(&accA, &accB, 100)) and Thread 2 (transfer(&accB, &accA, 50)):
void transfer(account_t *from, account_t *to, int amt) {
pthread_mutex_lock(&from->lock);
pthread_mutex_lock(&to->lock);
from->balance -= amt;
to->balance += amt;
pthread_mutex_unlock(&to->lock);
pthread_mutex_unlock(&from->lock);
}Explain how deadlock arises and rewrite transfer() using canonical lock ordering to break Circular Wait.
How the AB-BA Deadlock Occurs:
- Thread 1 acquires
accA.lock(from) and is preempted before lockingaccB.lock. - Thread 2 acquires
accB.lock(from) and tries to lockaccA.lock(to) -> Thread 2 blocks waiting for Thread 1. - Thread 1 resumes and tries to lock
accB.lock(to) -> Thread 1 blocks waiting for Thread 2.
All four Coffman conditions hold, creating a permanent Circular Wait (T1 -> accB.lock -> T2 -> accA.lock -> T1).
Fixing via Global Lock Ordering:
void transfer_safe(account_t *from, account_t *to, int amt) {
if (from == to) return; /* guard self-transfer deadlock */
account_t *first = (from->id < to->id) ? from : to;
account_t *second = (from->id < to->id) ? to : from;
pthread_mutex_lock(&first->lock);
pthread_mutex_lock(&second->lock);
from->balance -= amt;
to->balance += amt;
pthread_mutex_unlock(&second->lock);
pthread_mutex_unlock(&first->lock);
}Thread 1 (accA -> accB) and Thread 2 (accB -> accA) acquire locks in opposite orders, forming a Circular Wait deadlock. Ordering acquisition consistently by id (first before second) and guarding from == to eliminates Circular Wait completely.
Exercises
Practice Exercises — Threads and Concurrent Programming
Compare Many-to-One, One-to-One (Linux NPTL), and Many-to-Many thread models with respect to multi-core parallelism and blocking system calls. Also explain the difference between a joinable thread and a detached thread.
Comparing Thread Models:
- Many-to-One: Multiple user threads multiplex onto one kernel thread; zero multi-core parallelism, and a single blocking syscall (
read()) blocks the entire process. - One-to-One (Linux NPTL): Each
pthread_create()maps 1:1 to a kernel-scheduled thread (clone()); delivers true multi-core execution, and one thread blocking in I/O does not stall sibling threads, at slightly higher per-thread kernel overhead. - Many-to-Many: Multiplexes M user threads onto N kernel threads (
N <= M), combining low user-space switching cost with parallel execution across N kernel workers.
Joinable vs. Detached Threads:
- Joinable (default): Keeps its exit status and kernel resources after termination until another thread calls
pthread_join(). Failing to join causes memory/thread leaks. - Detached (
pthread_detach()orPTHREAD_CREATE_DETACHED): Kernel reclaims all resources automatically when the thread exits; callingpthread_join()on it is invalid.
Many-to-One lacks multi-core parallelism and stalls on any blocking syscall; One-to-One (Linux NPTL) runs threads in parallel across cores with isolated blocking; Many-to-Many maps M user threads onto N kernel threads. Joinable threads retain exit state until pthread_join(), whereas detached threads auto-reclaim resources on exit.
- Two threads each execute
for (int i = 0; i < 100000; i++) counter++;on an unprotected sharedint counter = 0;. What is the exact maximum possible final value ofcounter, and why can the actual observed value be much smaller (for example,112,450)? - A multithreaded packet analyzer spends 20% of its execution time inside serialized mutex-protected logging (
s = 0.20) and 80% processing packets independently. Calculate its Amdahl's Law speedup on a 4-core processor and its maximum speedup with unlimited cores.
Part 1 — Race Condition Bounds:
- Maximum possible final value (if no increments are overwritten) =
2 * 100,000 = 200,000. - Because
counter++is three separate machine operations (Load, Increment, Store), interleaved execution causes lost updates: both threads read the same old valuek, computek + 1, and overwrite each other, yielding a final count strictly below200,000(the theoretical minimum with pathological interleaving can be as low as2if one thread overwrites 99,999 increments, or typically ~105k–140k in practice).
Part 2 — Amdahl's Law (s = 0.20, N = 4):
Speedup(4) = 1 / (0.20 + (1 - 0.20) / 4) = 1 / (0.20 + 0.20) = 1 / 0.40 = 2.50x.- Unlimited cores (
N -> infinity):Max Speedup = 1 / 0.20 = 5.00x.
- Maximum final value = 200,000; observed value is lower due to lost updates from non-atomic load-increment-store interleavings (race condition).
- 4-core speedup = 2.50x; maximum theoretical speedup = 5.00x.
Explain the exact internal sequence executed by pthread_cond_wait(&cond, &mutex). Why must it always be called inside a while (!condition) loop instead of an if (!condition) check, and what happens if the caller forgets to lock mutex before calling pthread_cond_wait()?
Internal Execution of pthread_cond_wait(&cond, &mutex):
- Precondition: caller must hold
mutex. - Atomically places the thread onto
cond's wait queue and unlocksmutex(atomic so no wakeup signal between unlock and sleep can be lost — avoiding the lost-wakeup race). - Thread sleeps with zero CPU usage until another thread calls
pthread_cond_signal(&cond)orpthread_cond_broadcast(&cond). - Upon waking,
pthread_cond_wait()re-acquiresmutexbefore returning to the caller.
Why while Is Mandatory & Missing Mutex Risk:
whilevs.if: Handles spurious wakeups (permitted by POSIX without a signal) and stolen wakeups (another thread acquiresmutexfirst and consumes the resource before the woken thread re-enters).- Forgetting to lock
mutex: Causes undefined behavior—typically corruptingmutexownership or missing the condition check-to-sleep transition (lost wakeup), leaving the thread permanently sleeping.
pthread_cond_wait() atomically unlocks mutex and sleeps on cond, then re-acquires mutex on wakeup. A while loop is mandatory to re-check the predicate after spurious or stolen wakeups; calling without holding mutex triggers undefined behavior and lost-wakeup hangs.
List Coffman's four necessary conditions for a deadlock. Explain how Lock Ordering, Try-Lock with Backoff (pthread_mutex_trylock), and Mutex Timeouts each break specific Coffman conditions.
Coffman's Four Conditions:
- Mutual Exclusion: Only one thread may hold a resource/mutex at a time.
- Hold and Wait: A thread holds at least one resource while waiting for others.
- No Preemption: Held resources cannot be forcibly reclaimed.
- Circular Wait: A closed ring of threads each waiting for a lock held by the next.
How Each Avoidance Strategy Breaks a Condition:
- Global Lock Ordering: Always acquiring locks in ascending global rank makes any wait-for cycle impossible, breaking Circular Wait.
pthread_mutex_trylock()with Backoff: If the second lock returnsEBUSY, the thread voluntarily releases its first lock (pthread_mutex_unlock) and retries later—breaking Hold and Wait (and effectively simulating voluntary preemption).- Timed Locks (
pthread_mutex_timedlock): Bounds how long a thread holds-and-waits before aborting and releasing held resources, breaking Hold and Wait / preventing permanent indefinite blocking.
Coffman's four conditions are Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait. Global lock ordering breaks Circular Wait; trylock with unlock-and-retry (or timed locks) breaks Hold and Wait.
Compare multithreading and multiprocessing for building a network server. Suppose a thread-per-connection server uses 2 MiB of stack/metadata per thread while a process-per-connection server uses 12 MiB of private pages per worker process. Calculate the total memory required to serve 2,000 concurrent clients under both designs, and name one non-memory advantage of each design.
Memory Calculation for 2,000 Concurrent Clients:
- Thread-per-connection:
2,000 * 2 MiB = 4,000 MiB(~3.91 GiB). - Process-per-connection:
2,000 * 12 MiB = 24,000 MiB(~23.44 GiB).
(Threads use 6x less memory here because code, heap, and shared tables are not duplicated per client.)
Key Non-Memory Advantages:
- Multithreading advantage: Faster creation and context switches (shared page tables/TLB) and instant in-memory data sharing (such as a shared session cache) via mutexes without IPC copying.
- Multiprocessing advantage: Fault isolation—if a buggy request crashes one worker process (
SIGSEGV), the master server and the other 1,999 client connections continue running unaffected.
For 2,000 concurrent clients, thread-per-connection requires 4,000 MiB versus 24,000 MiB for process-per-connection. Multithreading offers faster context switches and zero-copy shared state; multiprocessing offers strong fault isolation between clients.