PadhaikoAll subjects

Threads and Concurrent Programming

Network and Systems Programming (ENCT 386)

Open in the Padhaiko app

3.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 vs. Private Resources in a Multi-Threaded ProcessText
+-------------------------------------------------------------------+
|  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:

Comparison of Thread Mapping Models
ModelMappingConcurrency on Multi-Core?Blocking Syscall ImpactExamples
Many-to-OneMany user threads -> 1 kernel threadNo (only 1 thread runs at a time)Blocks all user threads in the processLegacy green-thread libraries
One-to-One1 user thread -> 1 kernel thread (clone())Yes (true parallel multi-core)Blocks only the calling threadLinux 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 threadsGo goroutines (M:N runtime scheduler)

Thread Lifecycle

  1. New / Created: Thread structure and private stack are allocated via pthread_create().
  2. Ready / Runnable: Thread is eligible for CPU scheduling in the kernel run queue.
  3. Running: Actively executing instructions on a CPU core.
  4. Blocked / Waiting: Suspended waiting for a mutex, condition variable (pthread_cond_wait), I/O, or pthread_join().
  5. Terminated: Returns from its start routine or calls pthread_exit(). If joinable, its return value and kernel metadata remain until another thread calls pthread_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.

Core Pthreads API Functions
FunctionPurpose
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.
Spawning and Joining Worker Threads Safely in PthreadsC
#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)

Definition

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.

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:


3.4 Deadlocks, race conditions, and avoidance

Race Conditions

Definition

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:

  1. Load count from RAM into a register (MOV).
  2. Increment the register (ADD 1).
  3. 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:

Coffman's Four Deadlock Conditions and Breaking Strategies
ConditionMeaningPrevention / Avoidance Strategy
1. Mutual ExclusionResource/mutex can be held by only one thread at a timeUse lock-free atomics or read-only sharing where possible
2. Hold and WaitA thread holds at least one lock while waiting for anotherAcquire all needed locks together atomically (or release held locks on trylock failure)
3. No PreemptionLocks cannot be forcibly taken from a holding threadUse pthread_mutex_trylock() / timed locks and back off if unavailable
4. Circular WaitClosed cycle of threads each waiting on a lock held by the nextImpose a strict global lock ordering (always acquire lower-ID/address mutex before higher-ID mutex)

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.

AspectMultithreadingMultiprocessing
Creation OverheadLow (creates stack + kernel task_struct; shares VM)Higher (clones page tables, FD table, CoW setup)
Context Switch CostFaster (no page-table / CR3 switch, no TLB flush)Slower (switches virtual address space; TLB pressure)
Communication SpeedFastest (direct shared memory + mutexes/atomics)Slower (requires pipes, sockets, or explicit shm_open)
Fault IsolationLow (a segfault or abort() in 1 thread kills all threads)High (crash in 1 worker process does not kill siblings)
Synchronization ComplexityHigh (must guard every shared object against race conditions)Lower (isolated state; only explicit IPC channels shared)
Memory FootprintSmaller (shared code, heap, and static data)Larger (separate heap/runtime per worker, mitigated by CoW)

Performance Considerations and Amdahl's Law


Worked Examples

Example

Calculating Thread Stack Footprint and Amdahl's Speedup Limit

  1. 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().
  2. 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 GiB of 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 at 10x).
Answer:
  1. Default 8 MiB stacks reserve 4,000 MiB; 512 KiB stacks reserve 250 MiB.
  2. Speedup on 8 cores = 4.71x; theoretical upper bound = 10.0x.
Example

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:

Thread-Safe Bounded Socket Queue (Pthreads)C
#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;
}
Answer:

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.

Example

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)):

C
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:

  1. Thread 1 acquires accA.lock (from) and is preempted before locking accB.lock.
  2. Thread 2 acquires accB.lock (from) and tries to lock accA.lock (to) -> Thread 2 blocks waiting for Thread 1.
  3. 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:

Deadlock-Free transfer() Using Canonical Lock OrderingC
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);
}
Answer:

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

Question 1

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() or PTHREAD_CREATE_DETACHED): Kernel reclaims all resources automatically when the thread exits; calling pthread_join() on it is invalid.
Answer:

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.

Question 2
  1. Two threads each execute for (int i = 0; i < 100000; i++) counter++; on an unprotected shared int counter = 0;. What is the exact maximum possible final value of counter, and why can the actual observed value be much smaller (for example, 112,450)?
  2. 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 value k, compute k + 1, and overwrite each other, yielding a final count strictly below 200,000 (the theoretical minimum with pathological interleaving can be as low as 2 if 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.
Answer:
  1. Maximum final value = 200,000; observed value is lower due to lost updates from non-atomic load-increment-store interleavings (race condition).
  2. 4-core speedup = 2.50x; maximum theoretical speedup = 5.00x.
Question 3

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):

  1. Precondition: caller must hold mutex.
  2. Atomically places the thread onto cond's wait queue and unlocks mutex (atomic so no wakeup signal between unlock and sleep can be lost — avoiding the lost-wakeup race).
  3. Thread sleeps with zero CPU usage until another thread calls pthread_cond_signal(&cond) or pthread_cond_broadcast(&cond).
  4. Upon waking, pthread_cond_wait() re-acquires mutex before returning to the caller.

Why while Is Mandatory & Missing Mutex Risk:

  • while vs. if: Handles spurious wakeups (permitted by POSIX without a signal) and stolen wakeups (another thread acquires mutex first and consumes the resource before the woken thread re-enters).
  • Forgetting to lock mutex: Causes undefined behavior—typically corrupting mutex ownership or missing the condition check-to-sleep transition (lost wakeup), leaving the thread permanently sleeping.
Answer:

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.

Question 4

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:

  1. Mutual Exclusion: Only one thread may hold a resource/mutex at a time.
  2. Hold and Wait: A thread holds at least one resource while waiting for others.
  3. No Preemption: Held resources cannot be forcibly reclaimed.
  4. 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 returns EBUSY, 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.
Answer:

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.

Question 5

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.
Answer:

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.

← Process Management and IPCSocket Programming and Network APIs (part 1: 4.1–4.3) →