Reasoning About Parallel Execution Safely 安全地推理并行执行

pthreads, mutexes, condition variables, and atomics with exam-grade race analysis 覆盖 pthreads、互斥量、条件变量与原子操作，面向考试级竞态分析

🎯 Learning Objectives学习目标

Differentiate concurrency vs parallelism and articulate when each model appears in COMP1521 practicals.区分并发与并行，并举例说明在 COMP1521 实践中分别出现的场景。
Create portable pthread programs that manage thread life-cycle with pthread_create/pthread_join.编写可移植的 pthread 程序，使用 pthread_create/pthread_join 管理线程生命周期。
Protect shared state with mutexes and condition variables while avoiding deadlock and starvation.利用互斥量与条件变量保护共享状态，并避免死锁及饥饿。
Employ atomic operations for lock-free counters and reason about memory ordering simplifications.使用原子操作实现无锁计数器，并分析简化的内存序模型。
Explain real exam outputs that involve race conditions, scheduling delays, and inconsistent logs.解释包含竞态、调度延迟与日志不一致的真实考试输出。

🧭 Exam Alignment考试对齐

Race diagnostics — 22T3 Q8 & 20T3 Q6 require step-by-step explanation of interleavings.竞态诊断 — 22T3 Q8 与 20T3 Q6 要求逐步分析交错执行。
Mutex ordering — Lab07 «bank_account_mutex» directly maps to exam deadlock avoidance discussion.互斥顺序 — Lab07 “bank_account_mutex” 与考试中的死锁规避问答一一对应。
Atomic reasoning — Tutorial07 questions compare fetch_add vs mutex-protected increments.原子推理 — Tutorial07 习题比较 fetch_add 与互斥保护的增量实现。
Worker pools — 22T2 Q9 describes thread pool design; this week’s practice log mirrors solution outline.线程池 — 22T2 Q9 讨论线程池，本周实践记录与标准解法相呼应。
Barrier semantics — Lab07 challenge uses pthread barriers, same focus as 20T2 Q8 extension.屏障语义 — Lab07 挑战题采用 pthread 屏障，与 20T2 Q8 扩展题一致。

Coverage goals: document ≥4 mutex ordering templates, ≥3 condition-variable wakeup patterns, and ≥2 atomic counter variants, marking any uncertain cases for rework. 覆盖目标：记录 ≥4 种互斥锁顺序模板、≥3 种条件变量唤醒模式、≥2 种原子计数实现，并标注需复习的不确定案例。

📚 Core Concepts核心概念

Concurrency vs Parallelism并发 vs 并行

Concurrency interleaves tasks in time, while parallelism executes simultaneously on separate cores. COMP1521 labs mix both, e.g. independent threads vs multi-process pipelines.并发表示任务在时间上交错执行，并行则在多核上同时执行。COMP1521 实验同时涉及二者，例如独立线程与多进程管道。

Flynn’s taxonomy (SISD, SIMD, MISD, MIMD) classifies hardware support — exam short answers expect definitions.Flynn 分类（SISD、SIMD、MISD、MIMD）描述硬件支持，考试会要求简述这些概念。

Thread Lifecycle API线程生命周期 API

pthread_create spawns threads with function pointer + argument; pthread_join waits for completion and collects return values.pthread_create 通过函数指针和参数创建线程；pthread_join 等待线程结束并获取返回值。

Detaching threads relinquishes join-ability but risks losing error codes. Exams often ask whether join is necessary to prevent resource leaks.分离线程会放弃 join 机会，也可能丢失错误码。考试常问是否必须 join 以避免资源泄漏。

Mutexes & Deadlock Avoidance互斥锁与死锁规避

Mutual exclusion ensures only one thread enters critical section. Deadlocks appear when cyclic wait exists; fix by ordering locks globally or using trylock fallbacks.互斥锁保证临界区同一时间只有一个线程进入。当出现环状等待时会死锁，可通过全局锁顺序或 trylock 回退避免。

Lab07 emphasises acquiring locks in consistent order (e.g. account ID ascending) — same pattern tested in finals.Lab07 强调按照固定顺序加锁（如账户 ID 升序），考试也会考查这一策略。

Condition Variables条件变量

Wait functions atomically release mutex + block until signaled. Always loop around pthread_cond_wait to re-check predicates.等待函数会原子地释放互斥锁并阻塞，直到被唤醒。必须在循环中调用 pthread_cond_wait 并重新检查条件。

Broadcast vs signal: choose broadcast when multiple consumers should wake (e.g. barrier release).选择 broadcast 可唤醒多个等待线程，例如屏障释放。

Atomics & Lock-free Counters原子操作与无锁计数器

C11 atomics (atomic_int, atomic_fetch_add) guarantee indivisible updates. Use in high-frequency counters to avoid mutex contention.C11 原子类型（如 atomic_int、atomic_fetch_add）保证更新不可分割。高频计数可替代互斥锁以避免锁争用。

Still follow memory-order defaults (memory_order_seq_cst) unless explicitly optimising; finals rarely require weaker orders.除非有性能优化需求，否则保持默认的 memory_order_seq_cst，考试一般不会要求更弱的序。

🧪 Worked Examples示例串讲

Example 1 — Bank Account with Mutex Ordering示例 1 — 银行账户互斥顺序

Two threads transfer funds between account A and B. Acquire locks in fixed ascending account ID order to avoid deadlock.两个线程在账户 A/B 间转账。按账户 ID 升序获取锁，可避免死锁。

                        int acquire_pair(pthread_mutex_t *lhs, pthread_mutex_t *rhs) {
                            if (lhs == rhs) return pthread_mutex_lock(lhs);
                            pthread_mutex_t *first = lhs < rhs ? lhs : rhs;
                            pthread_mutex_t *second = lhs < rhs ? rhs : lhs;
                            pthread_mutex_lock(first);
                            pthread_mutex_lock(second);
                            return 0;
                        }
                    

Exam markers expect commentary on ordering strategy; refer to ./week7-threads-concurrency.html#mutexes. 考试阅卷会重点关注锁顺序策略说明，详见 ./week7-threads-concurrency.html#mutexes。

Example 2 — Producer/Consumer with Condition Variable示例 2 — 条件变量实现生产者/消费者

A bounded queue guards access with mutex and two condvars (not_empty, not_full). Always wait inside while loop to handle spurious wakeups.有界队列使用互斥锁与两个条件变量（not_empty、not_full）保护访问，必须在 while 循环中等待以处理虚假唤醒。

Map this design to Lab07 «bounded_buffer» challenge and 22T2 Q9 thread pool question.该设计对应 Lab07 “bounded_buffer” 挑战与 22T2 Q9 线程池题目。

⚠️ Common Pitfalls易错点

Forgetting to join threads leads to resource leaks and lost error codes.忘记 join 线程会导致资源泄漏并丢失错误码。
Using if instead of while around pthread_cond_wait fails under spurious wakeups.在 pthread_cond_wait 外使用 if 而非 while 会在虚假唤醒时出错。
Holding multiple mutexes without ordering leads to deadlock; exam penalties escalate with each stuck thread.对多个互斥锁缺乏顺序管理会导致死锁，考试会按被卡住线程数量扣分。
Mixing atomics and regular loads without understanding semantics may reintroduce races; stick to one approach per counter.在不了解语义的情况下混用原子操作与普通读取可能再次引入竞态，计数器应坚持一种实现方式。

🛠️ Practice Task实践任务

Build thread_pool.c: a fixed-size worker pool executing queued jobs. The dispatcher pushes tasks, workers pop and execute, using condition variables to sleep when idle.实现 thread_pool.c：固定大小的线程池执行排队任务。调度线程推入任务，工作线程弹出执行，并在空闲时通过条件变量休眠。

Protect queue with single mutex; use pthread_cond_wait for not_empty and not_full.用单个互斥锁保护队列；分别为 not_empty 与 not_full 使用 pthread_cond_wait。
Record per-task start/end timestamps to illustrate scheduling fairness.记录每个任务的开始/结束时间，以展示调度公平性。
Optional Optional: integrate atomic counters for completed jobs and expose --metrics flag.可选 Optional：加入原子计数器统计完成任务量，并提供 --metrics 参数。

🧪 Tutorial & Lab Mapping教程与实验映射

Tutorial 07 HighlightsTutorial 07 重点

Race-condition detective stories — reorder operations to expose/patch races.竞态侦探题：重排操作以定位并修补竞态。
Mutex vs atomic debate for counters, culminating in design trade-offs.互斥与原子计数的取舍讨论，分析不同实现的权衡。
Barrier puzzle: explain why all threads must reach barrier to avoid deadlock.屏障谜题：说明为何所有线程必须抵达屏障，否则会死锁。

Lab 07 Programming TasksLab 07 编程任务

bank_account_mutex.c — protect transfers with ordered locking.bank_account_mutex.c — 通过有序加锁保护转账。
counter_race.c — demonstrate race vs fix with mutex or atomic increments.counter_race.c — 对比竞态增量与互斥/原子修复。
bounded_buffer.c — implement producer/consumer with condvars.bounded_buffer.c — 条件变量实现生产者/消费者。
thread_barrier.c (challenge) — write reusable barrier for repeated synchronisation rounds.thread_barrier.c（挑战） — 编写可重复使用的线程屏障。

📝 Study Log学习记录

Inputs shared: threads.pdf, Lab07 spec, Tutorial07 handout, exam 22T3 Q8 + 22T2 Q9.提供资料：threads.pdf、Lab07 说明、Tutorial07 讲义、22T3 Q8 与 22T2 Q9。
Prompt: “Design mutex/condvar templates that map to lab tasks and justify race fixes in exams.”提示词：“构建与实验匹配的互斥/条件变量模板，并为考试中的竞态修复提供论证。”
Breakthrough: Logging thread IDs alongside queue lengths quickly pinpointed starvation when prioritising heavy tasks.收获：记录线程 ID 和队列长度，快速定位偏向重型任务导致的饥饿。
Misconception fixed: Previously used if around cond wait; switched to while loops after debugging lost wakeups.修正误区：过去在 cond wait 外用 if，修复丢唤醒案例后改用 while。
Action items: Benchmark atomic vs mutex counters; rehearse short-answer narratives explaining atomic semantics.后续行动：基准对比原子与互斥计数器，并练习原子语义的简答叙述。

Premium Quiz — 40 Questions on Threads & SynchronisationPremium 测验 — 40 道线程与同步题

28 basic (APIs, race ID) · 8 intermediate (mutex/cond orchestration) · 4 advanced (atomics & design trade-offs)基础 28 题（API 与竞态识别）· 中级 8 题（互斥/条件协作）· 高级 4 题（原子与设计取舍）

🔒 Open Week 7 Quiz (Premium) 打开第 7 周测验（会员）

🔭 Next Week Preview下周预告

Week 8 shifts to virtual memory and caching — page tables, TLBs, replacement policies. Skim virtual_memory.pdf and prepare to simulate page faults.第 8 周将转向虚拟内存与缓存：页表、TLB 与置换策略。请预习 virtual_memory.pdf 并准备模拟缺页。

📎 Resources & Checklist资源与检查表

PPT: threads.pdf p1–38 (mutexes, atomics, barriers).PPT：threads.pdf 第 1–38 页（互斥、原子、屏障）。
Autotest: 1521 autotest lab07_bank_account, lab07_counter_race, lab07_bounded_buffer, lab07_thread_barrier.自动测试：1521 autotest lab07_bank_account、lab07_counter_race、lab07_bounded_buffer、lab07_thread_barrier。
Self-check: Can you describe a deadlock scenario and fix it with ordering or trylock? Can you justify using atomics instead of mutexes?自检：能否描述死锁场景并用锁顺序或 trylock 解决？能否说明使用原子的理由？