Lecture 10: Concurrency 3
回顾：
互斥方法
- 软件方法：Peterson的解决方案
- 硬件方法：test_and_set() ；compare_and_swap（）
- 互斥锁作为提供二进制锁的抽象
并发原语
- 互斥锁是一种提供互斥的锁抽象。
- 通常由操作系统通过API（如pthreads）提供。
- 它们是二进制的——线程当前要么已经获得互斥锁，要么还没有！
pthread_mutex_t lock; // declarationpthread_mutex_lock(&lock); // acquire
counter++;
pthread_mutex_unlock(&lock); // release
信号量(Semaphores)
操作系统的方法
信号量是互斥和进程同步的另一种抽象，通常由操作系统提供
- 它们有一个容量，要么是正数，要么是无穷大。
- 我们区分二进制（2 valued）和计数信号量（N-valued或无界）。
2-valued（二进制）信号量
只能取 0 或 1 两个值，用来实现 互斥锁（mutex）。
典型用法：
初始值 = 1，表示资源可用。
wait()获取资源 → 值变为 0。
signal()释放资源 → 值回到 1。N-valued（计数）信号量
可以取 0, 1, 2, …, N（甚至无上限），用来管理 N 个同类资源。
典型用法：
初始值 = N，表示有 N 个资源可用。
每次
wait()成功就减 1；减到 0 时，后续线程阻塞等待。
signal()把值加 1，唤醒一个等待线程。一句话总结：
2-valued = 互斥（锁一个资源）。
N-valued = 计数（锁多个相同资源）。
有两个函数用于操作信号量（想想counter++的例子）
- 当获取资源时调用wait()，容量减少
- 当资源释放时调用signal（）或/post()，容量增加。
该信号量只能在其当前容量严格的情况下获取
调用post的线程不必具有先前调用的wait。
信号量的概念定义：
typedef struct {int value;struct process * list;
} semaphore;
wait（）的概念实现：
void wait(semaphore* S) {S->count--;if(S->count < 0) {//add process to S->listblock(); // system call}
}post（）的概念实现：
void post(semaphore* S) {S->count++;if(S->count <= 0) {// remove process P from S->listwakeup(P);}
}
实施
当内部计数器不为正时，调用wait（）将阻塞进程
- 进程加入阻塞在信号量上的队列
- 进程状态由running变为blocked
- 控制权移交给进程调度程序
调用post（）从阻塞队列中移除可用的进程：
- 进程状态由blocked变为ready
- 可以使用不同的排队策略来删除进程-因此避免在代码中进行不合理的假设。
队列长度是等待该信号量的进程数。
block（）和wakeup（）是操作系统提供的系统调用。
post（）和wait（）必须是原子的。
void post(semaphore* S) {lock(&mutex);S->count++;if(S->count <= 0) {// remove process P from queuewakeup(P);}unlock(&mutex);
}
Posix信号量
Counter++
同一进程中的信号量可以声明为sem_t类型的变量：
- sem_init（）初始化信号量的值
- sem_wait（）减少信号量的值
- sem_post（）增加信号量的值
这些函数的解释可以在手册页（man pages）中找到，例如，在Linux命令行中输入man sem_init
sem_t s;
int sum = 0;
void* calc(void* arg) {int const iterations = 50000000;for(int i = 0; i < iterations;i++) {sem_wait(&s);sum++;sem_post(&s);}return 0;
}
int main() {pthread_t tid1,tid2;sem_init(&s,0,1);pthread_create(&tid1, NULL, calc, 0);pthread_create(&tid2, NULL, calc, 0);pthread_join(tid1,NULL);pthread_join(tid2,NULL);printf("The value of sum is: %d\n", sum);
}这段代码在Mac上给出正确的答案吗？
答：不幸的是，在Mac上运行代码得到的答案略低于上面的100000000
- 编译时带有sem_init已弃用的编译器警告。
- sem_init总是失败，返回−1！
- 使用命名信号量也可以——参见实验。
- 即便如此，使用命名信号量的代码必须在Mac上以root身份运行才能成功调用sem_unlink。
因此：
- 永远不要忽视编译器警告。
- 总是检查返回值——幻灯片示例由于空间原因没有这样做。
- 彻底测试代码-隐含的假设Mac会像Linux一样工作是错误的！
- 注意特定于平台的问题，例如sem_unlink在Mac的行为。
- 使用适当的并发原语——示例确实需要一个互斥锁。
效率：如何/何时同步
快速同步求和：
void* calc(void* increments) {int number_of_iterations = 50000000;int total = 0;for(int i = 0; i < number_of_iterations; i++) {total++; // Pretend this is non-trivial to work out}sem_wait(&s);sum+=total;sem_post(&s);return 0;
}
潜在问题
饥饿：设计不良的排队方法（例如后进先出）可能导致违反公平性
死锁：两个或多个进程正在无限期地等待一个事件，而该事件只能由其中一个等待进程引起
- 即，一个集合中的每个进程都在等待一个事件，该事件只能由同一集合中的另一个进程引起
- 例如，考虑以下关于信号量的指令序列
生产者/消费者问题
问题描述
生产者和消费者共享一个值的缓冲区-例如，这可能是一个打印机队列。
- 缓冲区可以是有界的（最大大小为N），也可以是无界的。
- 可以有任意数量的生产者或消费者。
如果缓冲区已满，生产者将尝试添加项和块。
如果缓冲区为空，消费者将尝试删除项和块。
一个消费者，一个生产者，无限缓冲区
这个问题最简单的版本有一个生产者、一个消费者和一个无限大小的缓冲区
计数器（索引）变量跟踪缓冲区中的项数
它使用两个二进制信号量：
- sync同步对缓冲区（计数器）的访问，初始化为1。
- delay_consumer确保消费者在没有项目可用时阻塞，初始化为0
显然，对items的任何操作都必须是同步的
竞态条件仍然存在：当消费者耗尽缓冲区时，应该阻塞，但生产者在消费者检查之前增加items
理解
二进制信号量（binary semaphore）和互斥锁（mutex）是同一件事吗？
不是。
• 二进制信号量只有 0/1 两种状态，可以用来做互斥，但 没有“所有权”概念：任何线程都可以signal()，即便它之前没有wait()。
• 互斥锁额外规定了 “谁加锁，谁解锁” 的所有权语义，并且通常支持可重入（递归锁）、优先级继承等特性。
→ 二进制信号量是“更弱”的同步原语，mutex 是专门针对互斥场景设计的。什么时候应优先选 mutex 而不是二进制信号量？
• 需要 严格的加锁/解锁配对（防止别的线程误释放）。
• 需要 可重入（同一线程可多次获取）。
• 需要 优先级继承、错误检测（如PTHREAD_MUTEX_ERRORCHECK）。
→ 如果目的就是 保护临界区，用 mutex；若只想做“可用/不可用”的通用同步（不限于互斥），可用二进制信号量。有没有“简单直接”的方法验证并发代码的正确性？
没有。
• 形式化验证（TLA⁺、Coq、模型检测）理论上可证，但成本高、门槛高。
• 静态分析工具（Coverity、Clang ThreadSanitizer、go vet、Rust borrow checker）能发现部分竞态，但不能保证“绝对正确”。
• 动态检测/压力测试（ThreadSanitizer、Helgrind、反复跑单元测试）可以发现很多 bug，但无法穷尽所有线程交错。
→ 实际工程中通常组合使用：编码规范 + 静态分析 + 动态检测 + 代码审查 + 压力测试。