# 同步，第 3 部分：使用互斥锁和信号量
> 原文：<https://github.com/angrave/SystemProgramming/wiki/Synchronization%2C-Part-3%3A-Working-with-Mutexes-And-Semaphores>
## 线程安全栈
## 什么是原子操作？
用维基百科来解释
> 如果系统的其余部分看起来是即时发生的，则操作（或一组操作）是原子的或不可中断的。没有锁，只有简单的 CPU 指令（“从内存中读取这个字节”）是原子的（不可分割的）。在单 CPU 系统上，可以暂时禁用中断（因此不会中断一系列操作）但实际上通过使用同步原语（通常是互斥锁）来实现原子性。
增加变量（`i++`）是 _ 而不是 _ 原子，因为它需要三个不同的步骤：将位模式从存储器复制到 CPU 中;使用 CPU 的寄存器执行计算;将位模式复制回内存。在此递增序列期间，另一个线程或进程仍然可以读取旧值，并且当递增序列完成时，对同一存储器的其他写入也将被覆盖。
## 如何使用互斥锁使我的数据结构线程安全？
注意，这只是一个介绍 - 编写高性能的线程安全数据结构需要它自己的书！这是一个非线程安全的简单数据结构（栈）：
```c
// A simple fixed-sized stack (version 1)
#define STACK_SIZE 20
int count;
double values[STACK_SIZE];
void push(double v) {
values[count++] = v;
}
double pop() {
return values[--count];
}
int is_empty() {
return count == 0;
}
```
栈的版本 1 不是线程安全的，因为如果两个线程同时调用 push 或 pop，则结果或栈可能不一致。例如，假设两个线程同时调用 pop，则两个线程可以读取相同的值，两者都可以读取原始计数值。
为了将其转换为线程安全的数据结构，我们需要识别代码的 _ 关键部分 _，即代码的哪个部分一次只能有一个线程。在上面的例子中，`push`，`pop`和`is_empty`函数访问相同的变量（即存储器）和栈的所有关键部分。
当`push`（和`pop`）正在执行时，数据结构是不一致的状态（例如，计数可能尚未写入，因此可能仍包含原始值）。通过使用互斥锁包装这些方法，我们可以确保一次只有一个线程可以更新（或读取）栈。
候选“解决方案”如下所示。这是对的吗？如果没有，它将如何失败？
```c
// An attempt at a thread-safe stack (version 2)
#define STACK_SIZE 20
int count;
double values[STACK_SIZE];
pthread_mutex_t m1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t m2 = PTHREAD_MUTEX_INITIALIZER;
void push(double v) {
pthread_mutex_lock(&m1);
values[count++] = v;
pthread_mutex_unlock(&m1);
}
double pop() {
pthread_mutex_lock(&m2);
double v = values[--count];
pthread_mutex_unlock(&m2);
return v;
}
int is_empty() {
pthread_mutex_lock(&m1);
return count == 0;
pthread_mutex_unlock(&m1);
}
```
上面的代码（'版本 2'）包含至少一个错误。花点时间看看你是否可以得到错误并找出后果。
如果三个同时调用`push()`，则`m1`确保只有一个线程处理栈（两个线程需要等到第一个线程完成（调用解锁）），然后第二个线程将被允许继续进入临界区，最后第二个线程完成后，第三个线程将被允许继续。
类似的参数适用于`pop`的并发调用（同时调用）。但是，版本 2 不会阻止 push 和 pop 同时运行，因为`push`和`pop`使用两个不同的互斥锁。
在这种情况下，修复很简单 - 对推送和弹出功能使用相同的互斥锁。
代码有第二个错误;比较后`is_empty`返回，不会解锁互斥锁。但是，错误不会立即被发现。例如，假设一个线程调用`is_empty`，第二个线程稍后调用`push`。这个线程会神秘地停止。使用调试器可以发现线程卡在`push`方法内的 lock（）方法中，因为锁定从未被先前的`is_empty`调用解锁。因此，在一个线程中的疏忽导致在任意其他线程中很晚的问题。
更好的版本如下所示 -
```c
// An attempt at a thread-safe stack (version 3)
int count;
double values[count];
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
void push(double v) {
pthread_mutex_lock(&m);
values[count++] = v;
pthread_mutex_unlock(&m);
}
double pop() {
pthread_mutex_lock(&m);
double v = values[--count];
pthread_mutex_unlock(&m);
return v;
}
int is_empty() {
pthread_mutex_lock(&m);
int result= count == 0;
pthread_mutex_unlock(&m);
return result;
}
```
版本 3 是线程安全的（我们已确保所有关键部分的互斥）但是有两点需要注意：
* `is_empty`是线程安全的，但其结果可能已经过时，即在线程获得结果时栈可能不再为空！
* 没有防止下溢（在空栈上弹出）或溢出（推入已经满的栈）的保护
后一点可以使用计数信号量来修复。
该实现假设一个栈。更通用的版本可能包含互斥锁作为内存结构的一部分，并使用 pthread_mutex_init 初始化互斥锁。例如，
```c
// Support for multiple stacks (each one has a mutex)
typedef struct stack {
int count;
pthread_mutex_t m;
double *values;
} stack_t;
stack_t* stack_create(int capacity) {
stack_t *result = malloc(sizeof(stack_t));
result->count = 0;
result->values = malloc(sizeof(double) * capacity);
pthread_mutex_init(&result->m, NULL);
return result;
}
void stack_destroy(stack_t *s) {
free(s->values);
pthread_mutex_destroy(&s->m);
free(s);
}
// Warning no underflow or overflow checks!
void push(stack_t *s, double v) {
pthread_mutex_lock(&s->m);
s->values[(s->count)++] = v;
pthread_mutex_unlock(&s->m); }
double pop(stack_t *s) {
pthread_mutex_lock(&s->m);
double v = s->values[--(s->count)];
pthread_mutex_unlock(&s->m);
return v;
}
int is_empty(stack_t *s) {
pthread_mutex_lock(&s->m);
int result = s->count == 0;
pthread_mutex_unlock(&s->m);
return result;
}
```
使用示例：
```c
int main() {
stack_t *s1 = stack_create(10 /* Max capacity*/);
stack_t *s2 = stack_create(10);
push(s1, 3.141);
push(s2, pop(s1));
stack_destroy(s2);
stack_destroy(s1);
}
```
## 栈信号量
## 如果栈为空或已满，我如何强制我的线程等待？
使用计数信号量！使用计数信号量来跟踪剩余的空格数和另一个信号量来跟踪栈中的项目数。我们将这两个信号量称为“sremain”和“sitems”。记住，如果信号量的计数已减少到零（由另一个调用 sem_post 的线程），`sem_wait`将等待。
```c
// Sketch #1
sem_t sitems;
sem_t sremain;
void stack_init(){
sem_init(&sitems, 0, 0);
sem_init(&sremain, 0, 10);
}
double pop() {
// Wait until there's at least one item
sem_wait(&sitems);
...
void push(double v) {
// Wait until there's at least one space
sem_wait(&sremain);
...
```
草图＃2 过早地实现了`post`。另一个在推送中等待的线程可能会错误地尝试写入完整栈（类似地，在 pop（）中等待的线程被允许过早地继续）。
```c
// Sketch #2 (Error!)
double pop() {
// Wait until there's at least one item
sem_wait(&sitems);
sem_post(&sremain); // error! wakes up pushing() thread too early
return values[--count];
}
void push(double v) {
// Wait until there's at least one space
sem_wait(&sremain);
sem_post(&sitems); // error! wakes up a popping() thread too early
values[count++] = v;
}
```
Sketch 3 实现了正确的信号量逻辑，但是你能发现错误吗？
```c
// Sketch #3 (Error!)
double pop() {
// Wait until there's at least one item
sem_wait(&sitems);
double v= values[--count];
sem_post(&sremain);
return v;
}
void push(double v) {
// Wait until there's at least one space
sem_wait(&sremain);
values[count++] = v;
sem_post(&sitems);
}
```
Sketch 3 使用信号量正确执行缓冲区已满和缓冲区空条件。然而，没有 _ 互斥 _：两个线程可能同时位于 _ 临界区 _ 中，这会破坏数据结构（或最不会导致数据丢失）。解决方法是在临界区周围包含一个互斥锁：
```c
// Simple single stack - see above example on how to convert this into a multiple stacks.
// Also a robust POSIX implementation would check for EINTR and error codes of sem_wait.
// PTHREAD_MUTEX_INITIALIZER for statics (use pthread_mutex_init() for stack/heap memory)
pthread_mutex_t m= PTHREAD_MUTEX_INITIALIZER;
int count = 0;
double values[10];
sem_t sitems, sremain;
void init() {
sem_init(&sitems, 0, 0);
sem_init(&sremains, 0, 10); // 10 spaces
}
double pop() {
// Wait until there's at least one item
sem_wait(&sitems);
pthread_mutex_lock(&m); // CRITICAL SECTION
double v= values[--count];
pthread_mutex_unlock(&m);
sem_post(&sremain); // Hey world, there's at least one space
return v;
}
void push(double v) {
// Wait until there's at least one space
sem_wait(&sremain);
pthread_mutex_lock(&m); // CRITICAL SECTION
values[count++] = v;
pthread_mutex_unlock(&m);
sem_post(&sitems); // Hey world, there's at least one item
}
// Note a robust solution will need to check sem_wait's result for EINTR (more about this later)
```
## 常见的 Mutex 陷阱是什么？
* 锁定/解锁错误的互斥锁（由于愚蠢的错字）
* 没有解锁互斥锁（因为在错误情况下提前返回）
* 资源泄漏（不调用`pthread_mutex_destroy`）
* 使用未初始化的互斥锁（或使用已经被破坏的互斥锁）
* 在线程上锁定互斥锁两次（不先解锁）
* 死锁和优先级倒置（稍后我们将讨论这些）
- UIUC CS241 系统编程中文讲义
- 0. 简介
- #Informal 词汇表
- #Piazza：何时以及如何寻求帮助
- 编程技巧，第 1 部分
- 系统编程短篇小说和歌曲
- 1.学习 C
- C 编程，第 1 部分：简介
- C 编程，第 2 部分：文本输入和输出
- C 编程，第 3 部分：常见问题
- C 编程，第 4 部分：字符串和结构
- C 编程，第 5 部分：调试
- C 编程，复习题
- 2.进程
- 进程，第 1 部分：简介
- 分叉，第 1 部分：简介
- 分叉，第 2 部分：Fork，Exec，等等
- 进程控制，第 1 部分：使用信号等待宏
- 进程复习题
- 3.内存和分配器
- 内存，第 1 部分：堆内存简介
- 内存，第 2 部分：实现内存分配器
- 内存，第 3 部分：粉碎堆栈示例
- 内存复习题
- 4.介绍 Pthreads
- Pthreads，第 1 部分：简介
- Pthreads，第 2 部分：实践中的用法
- Pthreads，第 3 部分：并行问题（奖金）
- Pthread 复习题
- 5.同步
- 同步，第 1 部分：互斥锁
- 同步，第 2 部分：计算信号量
- 同步，第 3 部分：使用互斥锁和信号量
- 同步，第 4 部分：临界区问题
- 同步，第 5 部分：条件变量
- 同步，第 6 部分：实现障碍
- 同步，第 7 部分：读者编写器问题
- 同步，第 8 部分：环形缓冲区示例
- 同步复习题
- 6.死锁
- 死锁，第 1 部分：资源分配图
- 死锁，第 2 部分：死锁条件
- 死锁，第 3 部分：餐饮哲学家
- 死锁复习题
- 7.进程间通信＆amp;调度
- 虚拟内存，第 1 部分：虚拟内存简介
- 管道，第 1 部分：管道介绍
- 管道，第 2 部分：管道编程秘密
- 文件，第 1 部分：使用文件
- 调度，第 1 部分：调度过程
- 调度，第 2 部分：调度过程：算法
- IPC 复习题
- 8.网络
- POSIX，第 1 部分：错误处理
- 网络，第 1 部分：简介
- 网络，第 2 部分：使用 getaddrinfo
- 网络，第 3 部分：构建一个简单的 TCP 客户端
- 网络，第 4 部分：构建一个简单的 TCP 服务器
- 网络，第 5 部分：关闭端口，重用端口和其他技巧
- 网络，第 6 部分：创建 UDP 服务器
- 网络，第 7 部分：非阻塞 I O，select（）和 epoll
- RPC，第 1 部分：远程过程调用简介
- 网络复习题
- 9.文件系统
- 文件系统，第 1 部分：简介
- 文件系统，第 2 部分：文件是 inode（其他一切只是数据...）
- 文件系统，第 3 部分：权限
- 文件系统，第 4 部分：使用目录
- 文件系统，第 5 部分：虚拟文件系统
- 文件系统，第 6 部分：内存映射文件和共享内存
- 文件系统，第 7 部分：可扩展且可靠的文件系统
- 文件系统，第 8 部分：从 Android 设备中删除预装的恶意软件
- 文件系统，第 9 部分：磁盘块示例
- 文件系统复习题
- 10.信号
- 过程控制，第 1 部分：使用信号等待宏
- 信号，第 2 部分：待处理的信号和信号掩码
- 信号，第 3 部分：提高信号
- 信号，第 4 部分：信号
- 信号复习题
- 考试练习题
- 考试主题
- C 编程：复习题
- 多线程编程：复习题
- 同步概念：复习题
- 记忆：复习题
- 管道：复习题
- 文件系统：复习题
- 网络：复习题
- 信号：复习题
- 系统编程笑话