并发控制：信号量

我们分析了同步的本质需求：两个并发的线程等待某个同步条件达成，完成时间线的 “交汇”。相应地，我们有了条件变量实现同步，并且解决了生产者-消费者问题 (括号打印问题)。

本讲内容：另一种共享内存系统中常用的同步方法：信号量 (E. W. Dijkstra)

• 什么是信号量

• 信号量适合解决什么问题

• 哲学家吃饭问题

上次的内容，生产者-消费者问题，一种万能的同步机制：条件变量。我们先需要一把锁，在持有锁的情况下检查条件是否成立，以此实现同步。

什么是信号量

信号量是条件变量的特例。

//消费
void P(sem_t *sem) { // wait
  wait_until(sem->count > 0) {
    sem->count--;
  }
}

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

有点生产者、消费者的味道。区别

• P 失败时立即睡眠等待

• 执行 V 时，唤醒任意等待的线程

理解1

初始时 count = 1 的特殊情况，信号量就变成了互斥锁。

#define YES 1
#define NO 0

void lock() {
  wait_until(count == YES) {
    count = NO;
  }
}

void unlock() {
  count = YES;
}

隐含假设：我们 unlock 的时候 count 一定是0。

互斥锁每次只能让一个人进入。

完全没有必要，因为可以让更多的人一起进来。

理解2

• P - prolaag (try + decrease/down/wait/acquire)

  • 试着从袋子里取一个球

  • 如果拿到了，离开

  • 如果袋子空了，排队等待

• V - verhoog (increase/up/post/signal/release)

• 往袋子里放一个球

  • 如果有人在等球，他就可以拿走刚放进去的球了

  • 放球-拿球的过程实现了同步

PV 是荷兰语。

信号量即资源的数量。

信号量实现生产者-消费者

#include "thread.h"
#include "thread-sync.h"

sem_t fill, empty;

void Tproduce() {
  while (1) {
    P(&empty);
    printf("(");
    V(&fill);
  }
}

void Tconsume() {
  while (1) {
    P(&fill);
    printf(")");
    V(&empty);
  }
}

int main(int argc, char *argv[]) {
  assert(argc == 2);
  SEM_INIT(&fill, 0);
  SEM_INIT(&empty, atoi(argv[1]));
  for (int i = 0; i < 8; i++) {
    create(Tproduce);
    create(Tconsume);
  }
}

我们需要两个信号量，有两类线程，生产者每打一个 ( 就意味着有一个线程可以打印 ) ，即创造了一个资源。同样的，右括号同理。

因此一开始需要给这两个信号量初值。

empty->val = 3;
fill-val = 0;

有两个信号量。这个代码很漂亮。很干净。

整个这代码密度就要比前面的简单。在“一单位资源”很明确的情况下，确实很好用，也应该用。

信号量的应用

信号量适合干什么，不适合干什么。

典型应用 1 ：先 A 后 B 的同步操作。(初始是锁定状态的互斥锁。)

• 实现一次临时的 happens-before

  • 初始：s = 0

  • A; V(s)

  • P(s); B

典型应用 2 ：带计数型的同步

• 初始：done = 0

• Tworker: V(done)

• Tmain: P(done)

这两种方式都可以实现线程的 join()

哲学家吃饭问题

遇到的问题：死锁。并发编程一定会遇到这个问题，幸运的是，这个 bug 是比较容易解决的。