第7章 同步实例
7.1 同步的经典问题
7.1.1 有限缓冲问题（the Bounded-Buffer Problem）
n个缓冲，每个可以放一项
信号量mutex初始化为1，信号量full初始化为0，信号量empty初始化为n
生产者进程：
// Producer
while(true) {
...
/* produce an item in next_produced */
...
wait(empty);
wait(mutex);
...
/* add next produced to the buffer */
...
signal(mutex);
signal(full);
}
消费者进程：
// Consumer
while(true) {
wait(full);
wait(mutex);
...
/* remove an item from buffer to next_consumed */
...
signal(mutex);
signal(empty);
...
/* consume the item in next consumed */
...
}
7.1.2 读写问题（the Readers-Writers Problem）
一些并发进程共享一个数据集
- 读者：只读数据集，不做任何更新
- 写者：既可读也可写
问题：允许多个读者同时读，但在某时刻只有一个写者可以访问共享数据
共享数据：
- 数据集
- 信号量rw_mutex初始化为1
- 信号量mutex初始化为1
- int read_count初始化为0
写者：
// writer
while (true){
wait(rw_mutex);
...
/* writing is performed */
...
signal(rw_mutex);
}
读者
// reader
while (true){
wait(mutex);
read_count++;
if(read_count == 1)
wait(rw_mutex);
signal(mutex);
...
/* reading is performed */
...
wait(mutex);
read_count--;
if(read_count == 0)
signal(rw_mutex);
signal(mutex);
}
变体：
- 第一变体：直到写者允许使用共享对象之后，读者才能读
- 第二变体：只要写者就绪，它就尽快写
两种变体都可能遇到饥饿情况，引发更多变体
在某些系统上，内核提供读写锁来解决问题
7.1.3 哲学家就餐问题（the Dining-Philosophers Problem）
哲学家一辈子就坐在桌边，要么吃要么思考
他们不和邻居交流，偶尔会拿筷子起来吃饭（一次拿一根）
- 拿两根才能吃饭，放下的时候两根一起放
共享数据：
- 一碗饭（数据集）
- 信号量chopstick[n] 初始化为1
7.1.3.1 信号量解法
哲学家i：
// Philpsopher i
while(true){
wait(chopstick[i]);
wait(chopstic[(i+1)%5]);
...
/* eat for a while */
...
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);
...
/* think for a while */
...
}
❌❌❌：可能引发死锁
7.1.3.2 管程解法
7.2 在内核中的同步
7.2.1 在Windows中的同步
在单处理器系统中，用中断屏蔽（interrupt mask）来保护对全局资源的访问
在多处理器系统上，用自旋锁
- 自旋锁的线程永远不会被抢占
还提供了可以充当互斥锁，信号量，事件和计时器的调度程序对象用户权限
7.2.2 在Linux中的同步
7.3 POSIX同步
7.3.1 POSIX互斥锁
7.3.2 POSIX信号量
7.3.3 POSIX条件变量
7.4 Java中的同步
7.5 替代方法
- 事务内存（Transactional Memory）
- 内存事务是原子执行的一系列对内存的读写操作。 可以通过添加atomic {S}完成事务，以确保原子地执行S中的语句
- OpenMP
- OpenMP是一组支持并行编程的编译器指令和API
- #pragma omp critical指令中包含的代码被视为关键部分，并自动执行。
- 函数式编程（Functional Programming Languages）
- 函数式编程语言提供了与过程语言不同的范例，因为它们不维护状态
- 变量被视为不可变的，一旦为其分配了值，便无法更改状态
- 函数式语言（例如Erlang和Scala）对处理数据竞争的方法越来越感兴趣。
