§ 18.1-18.28 Processes, pthreads, Sync, and Advanced Concurrency

1. Overview

Linux exposes processes, threads, and coroutines as different points on the same sharing spectrum: a process is isolated by page tables, a thread is a kernel-scheduled task sharing the process resources, and a coroutine is a user-space control-flow object inside one thread. The kernel center of gravity is copy_process(), which creates a task_struct and decides what to share based on clone flags.

Process vs Thread vs Coroutine

A process buys fault isolation and independent VM; a pthread buys cheap sharing and kernel preemption; a coroutine buys extremely cheap cooperative switching but depends on the current thread to yield. The model below shows what is actually separate.

2. Key Data Structures

The main structures are not just C structs: they are ownership boundaries. task_struct is the schedulable entity, mm_struct owns the address space, files_struct owns descriptor slots, and ucontext_t is a user-space snapshot for coroutine switching.

3. Core Mechanism

fork and Copy-On-Write

Background: A shell often forks only to immediately exec a new program. Copying every page of a large parent would be wasteful, so Linux copies metadata and shares physical pages until one side writes.

The COW state is visible in the page tables: both parent and child map the same physical page with write permission removed, even though the VMA still says the mapping is logically writable.

Plan: create a child task, duplicate resource tables, mark writable PTEs read-only, and let the page-fault handler allocate a private page only if a write occurs.

The fork-plus-threads trap

In a multi-threaded process, only the calling thread exists in the child after fork(). Any lock held by a vanished sibling may remain permanently locked in the child process copied memory.

fork, vfork, clone, and exec

fork(), vfork(), and clone() differ mostly in sharing policy. execve() is different: it keeps the task identity but replaces the user-space image.

A typical shell path is fork, adjust descriptors in the child, then exec. The close-on-exec bit is what prevents helper pipes, secrets, and listening sockets from leaking into the new image.

The descriptor table itself survives fork, but execve() consults the close_on_exec bitmap and closes marked descriptors before the new program starts.

4. Minimal C Demo

5. Kernel Source Pointers

• kernel/fork.c: kernel_clone, copy_process, copy_mm, copy_files.
• mm/memory.c: do_cow_fault, wp_page_copy.
• fs/exec.c: do_execveat_common, begin_new_exec.
• fs/file.c: descriptor table growth, close_on_exec bitmap handling.
• arch/x86/entry/syscalls/syscall_64.tbl: syscall numbers for clone, fork, vfork, execve.

6. Interview Prep

7. §18.5-18.9 Process Lifecycle, Daemons, Job Control, Limits, and Privilege

After creation and exec, the operating-system story becomes lifecycle management: tasks move between runnable, sleeping, stopped, and zombie states; parents reap children; sessions and process groups control terminal signals; limits constrain damage; and UID/capability state decides which privileged operations are allowed.

8. Key Data Structures

Process state is a compact kernel-visible state machine. A zombie is not a running program; most resources are already gone, but the kernel keeps enough status for the parent to collect a reliable result.

Terminal job control is a hierarchy: a session owns the controlling terminal, the terminal designates one foreground process group, and terminal-generated signals are delivered to that foreground group.

Resource limits are inherited defaults with two ceilings. The soft limit is enforced now; the hard limit bounds how far an unprivileged process can raise the soft limit later.

9. Core Mechanism

Background

A parent starts a worker, the worker exits with status 42, and the parent is busy doing other work. The kernel cannot throw the status away because the parent may later call waitpid(), so the child becomes a zombie until reaped.

Plan

1. On exit, release expensive resources such as VM mappings, open files, and userspace memory.
2. Retain a small process record containing PID, parent link, signal state, and exit status.
3. Notify the parent with SIGCHLD unless the disposition says otherwise.
4. When the parent calls waitpid or waitid, copy the status out and free the final task record.

Walkthrough

Initial state: parent PID 900 forks child PID 901. PID 901 exits with _exit(42); ps shows state Z because PID 900 has not reaped it. When PID 900 runs waitpid(901, &status, 0), the kernel returns 901, WEXITSTATUS(status) is 42, and PID 901 disappears from the process table.

Daemonization

A classic daemon detaches from the launching terminal by forking, creating a new session, forking again, resetting process environment details, and redirecting standard descriptors. The second fork matters because a session leader can acquire a controlling terminal; the grandchild is not a session leader.

Privilege Transition

Privilege is not just UID 0. Linux combines real/effective/saved UIDs, file ownership transitions, and capability sets. Modern services should acquire the one privileged resource they need, drop IDs and capabilities, and often set PR_SET_NO_NEW_PRIVS before processing untrusted input.

10. Minimal C Demo

These demos keep the mechanisms observable: a zombie appears before waitpid, a reusable daemon function performs the double fork, process group/session IDs change after setsid, descriptor limits produce EMFILE, and a privileged process permanently drops to nobody.

11. Kernel Source Pointers

12. Interview Prep

13. §18.10-18.11 pthread Lifecycle and Mutexes

POSIX threads are user-space API objects backed by Linux kernel tasks in the NPTL 1:1 model. Creating a thread is mostly libc preparing a stack, TLS, and a start trampoline, then asking the kernel to create a schedulable task that shares the process address space and file table.

14. Key Data Structures

A pthread is a small set of coordinated objects: a join handle, a user stack with a guard page, a TCB/TLS area, kernel task state, and optional synchronization words that stay in user memory until contention forces a futex syscall.

The mutex word has a deliberately small state machine. The common case is a compare-exchange from unlocked to locked; the kernel only sees the operation when a thread has to sleep or wake a waiter.

15. Core Mechanism

Background

A server creates eight worker threads to share an in-memory cache. Thread creation needs independent stacks and TLS, while the cache update path needs mutual exclusion without paying a syscall on every uncontended lock.

Plan

1. Initialize attributes, optionally reducing stack size or choosing detached state.
2. Call pthread_create; libc allocates stack/TCB/TLS and uses clone sharing flags.
3. Keep joinable threads until pthread_join collects the return value and releases resources, or detach them when no result is needed.
4. Protect shared state with a mutex; the uncontended path is atomic user-space code, while contended waiters sleep through futex.

Walkthrough

Initial state: counter=0, four threads each run 100,000 increments. Without a mutex, two threads can read 17, both compute 18, and both store 18, losing one increment. With pthread_mutex_lock, one thread changes the mutex word from 0 to 1, updates the counter, unlocks, and only then can another thread enter; the final protected counter is exactly 400,000.

Robust Owner Death

Robust mutexes are for recoverable shared state, especially across processes. If an owner dies in the critical section, the next locker is told that protected data may be inconsistent rather than silently continuing.

16. Minimal C Demo

The first demo shows pthread creation attributes, kernel TIDs, return values, and joins. The second demo contrasts a racing increment with the same increment protected by a normal mutex.

17. Kernel Source Pointers

18. Interview Prep

19. §18.12-18.17 Sync Primitives Beyond Mutexes

Mutexes protect exclusive critical sections, but real pthread programs also need to wait for predicates, admit many readers, synchronize phases, survive cancellation, initialize shared state once, store per-thread data, and handle process-directed signals without running unsafe code in an async handler.

20. Key Data Structures

A condition variable is not the condition itself. The condition is the protected predicate such as count > 0; the condition variable is only the wait queue used when the predicate is false.

A reader-writer lock is useful when protected data is read often and mutated rarely. The state must distinguish active readers, an active writer, and waiters whose preference policy decides who enters next.

Spinlocks and barriers solve opposite timing problems: a spinlock avoids sleeping because the hold time should be tiny, while a barrier deliberately waits until every participant has reached the same phase boundary.

Thread-specific data is a two-level lookup. The key is process-wide, but each thread has its own slot value, and a destructor receives that thread's non-null value when the thread exits.

21. Core Mechanism

Background

A bounded queue starts empty. A consumer must sleep until a producer inserts an item, but the sleep must not miss the producer's wakeup and must not consume from an empty buffer after a spurious wake.

Plan

1. Protect queue state with one mutex: head, tail, and count.
2. Consumers use while (count == 0) pthread_cond_wait(&not_empty, &mutex).
3. Producers use while (count == CAP) pthread_cond_wait(&not_full, &mutex).
4. After changing the predicate, signal the opposite side before unlocking or while still holding enough ordering through the mutex.

Walkthrough

Initial state: count=0, consumer C holds the mutex and checks the predicate. C calls pthread_cond_wait, which atomically places C on the wait queue and unlocks the mutex. Producer P locks, writes item 7, changes count to 1, signals not_empty, and unlocks. C wakes, reacquires the mutex before returning, checks count > 0 again, removes item 7, signals not_full, and unlocks. The mutex creates the happens-before edge; the loop creates correctness under spurious or competing wakes.

Cancellation and Cleanup

Cancellation is only sane when resources are paired with cleanup handlers. The common pattern is lock, push an unlock handler, call cancellation points, then pop the handler when the protected region is finished.

Multi-Threaded Signals

Signal handlers are process-wide, but each thread has its own signal mask. Production pthread programs usually block signals in all workers and dedicate one thread to sigwait(), so shutdown code can use normal mutexes and condition variables instead of async-signal-safe handler rules.

22. Minimal C Demo

These demos focus on the failure-resistant patterns: predicate loops with two condition variables, phase synchronization with a barrier, cleanup handlers around cancellation points, exactly-once initialization with TSD destructors, and synchronous signal handling through sigwait.

23. Kernel Source Pointers

24. Interview Prep

25. Overview

Concurrency patterns are reusable shapes for moving work through shared state without letting memory, latency, or failure domains grow without control. The practical Linux building blocks are bounded queues, pthread synchronization, process workers, event loops, and a clear choice of where isolation should live.

26. Key Data Structures

A bounded producer-consumer queue is a ring plus two predicates. not_full is true when producers may insert, and not_empty is true when consumers may remove; both predicates are guarded by the same mutex.

The single-producer single-consumer ring removes the mutex by giving each side exclusive ownership of one index. Release/acquire ordering publishes the slot contents before the consumer observes the advanced tail.

Reader-writer patterns choose different costs for the same read-mostly problem: rwlock blocks writers until readers drain, seqlock makes readers retry, and RCU lets old readers finish before freeing replaced data.

Userspace RCU separates pointer publication from reclamation. Readers mark a read-side region, writers publish a replacement, and the old object is freed only after every pre-existing reader has passed through a quiescent state.

A fixed thread pool is a bounded queue plus sleeping workers. Shutdown is just another state transition: set the quit flag, broadcast the waiters, and join every worker.

27. Core Mechanism

Background

A service receives bursts of requests, but only has enough CPU and memory for a fixed number of workers and queued jobs. The concurrency design must absorb small bursts, apply backpressure during overload, and shut down without losing ownership of queued work.

Plan

1. Use a bounded queue so submitters block or fail fast when the system is overloaded.
2. Protect queue state with one mutex and use not_empty and not_full predicates.
3. Workers sleep while the queue is empty and the shutdown flag is false.
4. Shutdown sets the flag, broadcasts workers, drains or rejects new submissions, then joins every thread.

Walkthrough

Initial state: queue capacity is 8, count=0, and three workers are sleeping on not_empty. A producer submits jobs 1 through 8, advancing tail and signaling workers. Job 9 blocks because count == CAP. Worker 0 pops job 1, decrements count, signals not_full, and executes outside the mutex, so job 9 can be queued while CPU work continues. During shutdown, the main thread sets quit=1 and broadcasts; a worker exits only when the queue is empty and quit is set, so already accepted work is not abandoned.

Work Stealing

Work stealing reduces contention by giving each worker a private deque. The owner pushes and pops recent tasks from the head for cache locality, while idle workers steal older tasks from the tail to rebalance load.

Server Models

Apache prefork spends memory to isolate each request handler in a process. Nginx spends engineering complexity on event-driven workers that epoll shared listening sockets and keep many idle connections without one stack per connection.

In the Nginx-style model, the master supervises workers while the kernel owns readiness notification and accept-queue behavior. SO_REUSEPORT can shard incoming connections across worker sockets.

A master can also accept centrally and pass connected sockets to workers over a Unix socket with SCM_RIGHTS. The receiving worker gets a valid duplicate FD in its own descriptor table.

Multi-threaded servers choose between one thread per connection, a bounded worker pool around epoll, M:N runtimes, and io_uring variants. The common rule is to keep blocking work away from the event loop.

An epoll worker repeatedly sleeps for readiness, accepts or reads nonblocking FDs, writes responses, and re-arms interest when edge-triggered or one-shot modes are used.

Model Comparison

Concurrency models are trade-offs between fault isolation, switch cost, memory footprint, and reasoning cost. Processes isolate failures; threads share memory cheaply but make data races possible; coroutines and event loops are fast but require cooperative nonblocking discipline.

28. Minimal C Demo

These runnable demos show the core interview patterns: a many-producer many-consumer bounded queue, a minimal thread pool with graceful shutdown, and the shape of a prefork worker pool using a pipe as the stand-in for accepted connections.

29. Kernel Source Pointers

30. Interview Prep

31. §18.24-18.28 Deadlocks, PI Futexes, IPC Sync, and Coroutines

Advanced user-space concurrency is about the failure modes that appear after the basic mutex and queue code works: lock cycles, realtime priority inversion, cross-process ownership, file-lock semantics, and runtimes that multiplex logical tasks without creating one kernel thread per task.

32. Key Data Structures

A deadlock is a cycle in a wait-for graph. In the classic two-lock bug, each thread owns one lock and waits for the other, so neither edge can be removed by normal execution.

Cross-process synchronization works only when the synchronization word and protected data live in shared memory. A process-shared pthread mutex on a private heap is just two unrelated copies after fork.

Linux exposes several cross-process coordination tools. The crucial difference is ownership scope: whole file, byte range, process, open file description, named kernel semaphore, or futex word in a shared page.

A stackful coroutine is just another saved CPU context and stack inside one OS thread. Switching saves the current instruction and stack pointers, then restores another coroutine's saved state.

33. Core Mechanism

Background

A service has two shared indexes guarded by two locks. One path updates cache then index; another updates index then cache. Under load, thread A owns the cache lock and waits for the index lock while thread B owns the index lock and waits for the cache lock.

Plan

1. Assign every lock a canonical rank: static enum, object address, or lock class.
2. Acquire multiple locks in increasing rank and release them in reverse rank.
3. For optional locks, use pthread_mutex_trylock with release-and-backoff instead of waiting while holding lower-priority resources.
4. In complex systems, log wait-for edges and fail fast when adding an edge would create a cycle.

Walkthrough

Initial state: lock A has rank 10 and lock B has rank 20. Thread 1 asks for A then B; thread 2 asks for B then A. The ordered helper sorts both requests into A then B. Thread 1 may run first and hold both; thread 2 waits at A without owning B, so there is no cycle. When thread 1 releases B then A, thread 2 proceeds and the circular-wait Coffman condition is removed.

Priority Inversion

Priority inversion appears when a low-priority lock owner is preempted by medium-priority work while a high-priority thread waits behind it. The high-priority thread is indirectly blocked by a thread that does not even need the lock.

A priority-inheritance mutex lets the kernel see the dependency. When the high-priority waiter blocks, the kernel temporarily boosts the low-priority owner so it can finish and release the mutex.

Coroutine Runtimes

Modern coroutine systems all split logical waiting from OS-thread blocking. Go schedules goroutines onto worker threads, while C++20 and Rust represent suspended work as state machines that an executor resumes when I/O or timers complete.

A stackless coroutine moves through explicit compiler-generated states at each suspension point. Local variables that must survive a suspension live in the coroutine frame rather than on an ordinary caller stack.

34. Minimal C Demo

These demos show the practical core without requiring realtime privileges: ordered two-lock acquisition prevents a deadlock, a process-shared mutex coordinates two forked children through anonymous shared memory, stackful coroutines ping-pong with swapcontext, and the model comparison prints equivalent coroutine shapes.

35. Kernel Source Pointers

36. Interview Prep