10. 并发控制：同步 (2) (jyywiki.cn)

信号量

信号量（semaphore）：一种条件变量的特例
void P(sem_t *sem) { // wait
wait_until(sem->count > 0) {
sem->count--;
}
}

void V(sem_t *sem) { // post (signal) atomic { sem->count++; } }

> 初始时count=1的特殊情况：互斥锁是信号量的特例
> ```c
> #define YES 1
> #define NO 0
> 
> void lock() {
>   wait_until(count == YES) {
>     count = NO;
>   }
> }
> 
> void unlock() {
>   count = YES;
> }
> ```
>
>扩展的互斥锁：一个手环->n个手环
>让更多同学可以进入更衣室：管理员可以持有任意数量的手环 (count, 更衣室容量上限)。先进入更衣室的同学先进入游泳池。手环用完后需要等同学出来。
>信号量对应了 “资源数量”

- P - prolaag (try + decrease/down/wait/acquire)
    试着从袋子里取一个球。如果拿到了，离开。如果袋子空了，排队等待
- V - verhoog (increase/up/post/signal/release)
    往袋子里放一个球。如果有人在等球，他就可以拿走刚放进去的球了
    放球-拿球的过程实现了同步

优雅地实现生产者-消费者
```c
void Tproduce() {
  P(&empty);
  printf("("); // 注意共享数据结构访问需互斥
  V(&fill);
}
void Tconsume() {
  P(&fill);
  printf(")");
  V(&empty);
}

理解：生产者有一个口袋，放n个球。消费者有一个口袋，初始没有球。打印一个左括号，把一个球从生产者的口袋转移到消费者的口袋；打印一个右括号，把一个球从消费者的口袋转移到生产者的口袋。

信号量：应用

实现一次临时的 happens-before

初始：s=0
A; V(s);
P(s); B; 假设s只被使用一次，保证A happens-before B

此场景比条件变量简易。用条件变量，A做完后broadcast，如果此时B对应的线程还没有，则broadcast就丢了，还需要做额外的什么什么条件来告诉B。

实现计数类型的同步

初始：done=0
Tworker：V(done)
Tmain：P(done) * T

上边两种应用对应两种线程join的方法 T1->T2->... VS 完成就行不管顺序

实现计算图

a ---> c ---> d ---> e
|             ↑
|             |
⨽----> b ----⨼

为每个节点分配一个线程，每条边是一个信号量
对每条入边执行P（wait）操作
完成计算任务
对每条出边执行V（post/signal）操作
```
void Tworker_d() {
P(bd);P(cd);
// 完成节点d上的信号任务
V(de);
}
```
乍一看完美解决了并行问题，但是... 创建太多线程和信号量=Time Limit Exceeded 解决线程太多的问题：一个线程负责多个节点的计算
- 静态划分 -> 覆盖问题
- 动态调度 -> 又变回了生产者-消费者解决信号量太多的问题：计算节点共享信号量
- 可能出现假唤醒 -> 又回到了条件变量

哲学家吃饭问题

经典同步问题：5个哲学家在圆桌围成一桌，（线程）有时思考，有时吃饭。吃饭需要同时得到左手和右手的叉子。当叉子被其他人占有时，必须等待，如何完成同步？

失败的尝试：把信号量当互斥锁，先拿一把叉子，再拿另一把叉子。

void Tphilosopher() {
  while (1) {
    P(lhs);
    P(rhs);
    eat();
    V(lhs);
    V(rhs);
  }
}

成功的尝试（万能方法，条件变量）

#define CAN_EAT (avail[lhs] && avail[rhs])
mutex_lock(&mutex);
while (!CAN_EAT)
  cond_wait(&cv, &mutex);
avail[lhs] = avail[rhs] = false;
mutex_unlock(&mutex);

mutex_lock(&mutex);
avail[lhs] = avail[rhs] = true;
cond_broadcast(&cv);
mutex_unlock(&mutex);

成功的尝试：信号量。死锁会在5个哲学家“同时吃饭”时发生。破坏这个条件即可，保证任何时候至多只有4个人可以吃饭。

void Tphilosopher() {
  while (1) {
    P(table);

    P(lhs);
    P(rhs);
    eat();
    V(lhs);
    V(rhs);

    V(table);
  }
}

int main() {
  SEM_INIT(table, 4);
  // ......
}

反思：分布与集中 “Leader/follower (master/slave)” - 有一个集中的“总控”，而非“各自协调”。哲学家自己不决定什么时候吃饭。由服务员进行调度。联想：分布式存储 master 的角色。

gem-universe / blog

[操作系统]10. 并发控制-同步（信号量与哲学家吃饭问题） #10

信号量

信号量：应用

哲学家吃饭问题