1 信号量

1.1 用互斥锁实现同步

一个奇妙的想法

  • 创建锁时，立即 “获得” 它 (总是成功)
  • 其他人想要获得时就会等待
    • 此时 release 就实现了同步
  • 一个线程上锁，在另一个线程解锁

让我们来试一试吧 (demo)

  • 先把厕所门都锁上
  • 线程到达以后等待
  • 管理员把所有门都打开

Acquire-Release 实现计算图

  • 为每一条边 𝑒=(𝑢, 𝑣) 分配一个互斥锁
  • 初始时，全部处于锁定状态
  • 对于一个节点，它需要获得所有入边的锁才能继续
  • 可以直接计算的节点立即开始计算
  • 计算完成后，释放所有出边对应的锁

挺好用 (demo)

  • 甚至比条件变量还好用！

1.2 本质：Release as Synchronization

Release-Acquire 实现了 happens-before

  • Acquire = 等待 token
  • Release = 发出 token

Token 可以理解为现实生活中的“资源”

  • 停车场：停车位
  • 游泳馆：获得手环 (token) 的人可以进入更衣室
    • mutex 实现 token 似乎有什么问题？
      缺点：token=1

1.3 信号量

如果我是游泳馆的老板……

  • 一个能 “计数” 的 mutex: 发 𝑛 个手环！
    • 手环 = synchronization token
  • mutex 是 𝑛=1 的特殊情况

Acquire

  • 获得手环的同学进入游泳池 (手环不够，等待)

Release

  • 归还一个手环 (一个等待的同学就能得到手环了)

1.4 把任何东西理解为Token

停车场有 𝑛 个车位

  • Acquire: 在有车位时进入停车场
  • Release: 出停车场；车位 + 1

袋子里有 𝑛 个球

  • Acquire: 从袋子里取一个球
    • 如果没有球，需要等待
  • Release: 向袋子里放一个球
    • 如果有人在等待，直接把球交给他

注意我们可以有多个口袋！

1.5 API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void P(sem_t *sem) {
    // P - prolaag
    //     try + decrease/down/wait/acquire
    atomic {
        wait_until(sem->count > 0) {
            sem->count--;
        }
    }
}

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

2 使用信号量实现同步

  1. 实现一次临时的 happens-before: 𝐴→𝐵
  • 𝐴→𝑉(𝑠)→𝑃(𝑠)→𝐵这就是刚才的 “互斥锁实现同步”
  1. 管理计数型资源
  • 游泳池里的人不能超过 𝑛 个
  • 停车场里的车不能超过 𝑛 个
  • 但可以有多个 “停车场”、“游泳池”
  • 我们也可以创造出车位

2.1 线程join()

  1. 形成 happens-before
  • worker: $ V(done_t) $
  • main: $ P(done_1 )→P(done_2​)…→P(done_T) $描述了一个 “计算图”
  1. 使用计数型资源
  • worker: V(done)V(done)
  • main: P(done)×TP(done)×T

2.2 实现生产者-消费者

信号量设计思路

  • 考虑 “球”/“手环” (每一单位的 “资源”) 是什么
  • 生产者/消费者 = 把球从一个袋子里放到另一个袋子里
1
2
3
4
5
6
7
8
9
10
11
void produce() {
    P(&empty);
    printf("(");
    V(&fill);
}

void consume() {
    P(&fill);
    printf(")");
    V(&empty);
}

3 信号量、条件变量与同步

3.1 信号量 v.s. 条件变量

信号量

  • 互斥锁的自然推广
  • 干净、优雅：没有条件变量的 “自旋”

条件变量

  • 万能：适用于任何同步条件
  • 不太好用：代码总感觉不太干净
1
2
3
4
5
6
synchronized (obj) {  // reads better in Java
    while (!cond) {
        obj.wait();
    }
    ...
}

哲学家吃饭问题 (E. W. Dijkstra, 1960)

  • 哲学家 (线程) 有时思考，有时吃饭
  • 吃饭需要同时得到左手和右手的叉子

条件变量

  • 同步条件：avail[lhs] && avail[rhs]

信号量

  • P(&sem[lhs]) && P(&sem[rhs])
  • 看起来没什么问题？
    • 当互斥锁用就行了

如果 5 个哲学家同时举起左手的叉子……

  • 我们需要禁止这件事发生

Workaround 1: 从桌子上赶走一个人

  • 直观理解：大家先从桌上退出
    • 袋子里有 4 张卡
    • 拿到卡的可以上桌吃饭 (拿叉子)
    • 吃完以后把卡归还到袋子

Workaround 2: Lock Ordering

  • 给叉子编号，总是先拿编号小的

3.2 用条件变量实现信号量

P 操作的同步条件

  • sem->count > 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void P(sem_t *sem) {
    hold(&sem->mutex) {
        while (!COND)
            cond_wait(&sem->cv, &sem->mutex);
        sem->count--;
    }
}

void V(sem_t *sem) {
    hold(&sem->mutex) {
        sem->count++;
        cond_broadcast(&sem->cv);
    }
}

3.3 用信号量实现条件变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void wait(struct condvar *cv, mutex_t *mutex) {
    mutex_lock(&cv->lock);
    cv->nwait++;
    mutex_unlock(&cv->lock);

    mutex_unlock(mutex);
    P(&cv->sleep);

    mutex_lock(mutex);
}

void broadcast(struct condvar *cv) {
    mutex_lock(&cv->lock);

    for (int i = 0; i < cv->nwait; i++) {
        V(&cv->sleep);
    }
    cv->nwait = 0;

    mutex_unlock(&cv->lock);
}

3.4 实现困难的本质原因

先释放锁，再执行 P

  • 释放锁的一瞬间可能与 broadcast 并发

先执行 P，再释放锁

  • P(&cv->sleep) 会 “永久睡眠”

那怎么办

  • release-wait 必须实现成 “原子操作”
  • 信号量：在合适的时候好用；但不总是好用

信号量可以看做是互斥锁的一个 “推广”，可以理解成游泳馆的手环、袋子里的球，通过计数的方式实现同步——在符合这个抽象时，使用信号量能够带来优雅的代码。但信号量不是万能的——理解线程同步的条件才是真正至关重要的。