1. 线程同步

Synchronization

  • 控制并发，使得 “两个或两个以上随时间变化的量在变化过程中保持一定的相对关系”
  • 有点抽象，让我们来看例子

理解并发的方法

  • 线程 = 我们自己
  • 共享内存 = 物理空间

1.1 现实世界中的同步

演奏音乐中的同步

  • 每个乐手都是一个 “线程”
  • 节拍 𝑖 到达 → 演奏 𝑛𝑖𝑛_𝑖
    ​
1
2
3
4
5
6
void T_player() {
    while (!end) {
        wait_next_beat();
        play_next_note();
    }
}

在某个瞬间达到 “互相已知” 的状态

  • NPY: 等我洗个头就出门
  • NPY: 等我打完这局游戏就来
  • 舍友：等我修好这个 bug 就吃饭
  • 导师：等我出差回来就讨论这个课题
  • join(): 等所有线程结束就继续

“先到先等”，在条件达成的瞬间再次恢复并行

  • 同时开始出去玩/吃饭/讨论

1.2 状态机视角

系统到达某个 “同步” (互相已知) 的状态

1
2
3
4
5
6
7
8
9
10
11
12
13
void T_player() {
    while (!end) {
        wait_next_beat();
        play_next_note();
    }
}

void T_conductor() {
    while (!end) {
        wait_next_beat();
        release();
    }
}
  • release() 之后，player 都会演奏下一拍

自旋等待同步条件达成

  • 线程有先后，先来先等待
1
2
3
4
5
6
void wait_next_beat() {
retry:
    if (!next_beat_has_come) {
        goto retry;
    }
}

2. 生产者-消费者问题与条件变量

  • 99% 的实际并发问题都可以用生产者-消费者解决

Producer 和 Consumer 共享一个缓冲区

  • Producer (生产数据)：如果缓冲区有空位，放入；否则等待
  • Consumer (消费数据)：如果缓冲区有数据，取走；否则等待
1
2
void produce(Object obj); 
Object consume();

2.1 生产者-消费者问题的简化

缓冲区太麻烦，我们有一个简化版问题

1
2
void produce() { printf("("); }
void consume() { printf(")"); }
  • 生产 = 打印左括号 (push into buffer)
  • 消费 = 打印右括号 (pop from buffer)
  • 在 printf 前后增加代码，使得打印的括号序列满足
    • 一定是某个合法括号序列的前缀
    • 括号嵌套的深度不超过 𝑛
      • 𝑛 = 3, ((())())((( 合法
      • 𝑛 = 3, (((()))), (())) 不合法

2.2 同步：先来先等待

1
2
3
4
5
6
7
8
9
10
11
void produce() {
    wait_until(括号深度 < n) {
        printf("(");
    }
}

void consume() {
    wait_until(括号深度 > 0) {
        printf(")");
    }
}

我们发明了条件变量！

  • 把条件用一个变量来替代
  • 条件不满足时等待，条件满足时唤醒
1
2
3
4
5
6
7
8
mutex_lock(&lk);
if (!condition) {
    cond_wait(&cv, &lk);
}
// Wait for someone for wake-up.
assert(condition);

mutex_unlock(&lk);
1
2
cond_signal(&cv);  // Wake up a (random) thread
cond_broadcast(&cv);  // Wake up all threads

条件变量的正确打开方式

  • 使用 while 循环和 broadcast
    • 总是在唤醒后再次检查同步条件
    • 总是唤醒所有潜在可能被唤醒的人
1
2
3
4
5
6
7
8
9
mutex_lock(&mutex);
while (!COND) {
  wait(&cv, &mutex);
}
assert(cond);

...

mutex_unlock(&mutex);

3. 同步机制的应用

3.1 实现任意计算图

计算任务构成有向无环图

  • (𝑢, 𝑣)∈𝐸表示 𝑣 要用到前 𝑢 的值
  • 只要调度器 (生产者) 分配任务效率够高，算法就能并行
1
2
3
4
5
6
7
8
9
10
11
12
void T_worker() {
    while (1) {
        consume().run();
    }
}
void T_scheduler() {
    while (!jobs.empty()) {
        for (auto j : jobs.find_ready()) {
            produce(j);
        }
    }
}

为每个节点设置一个条件变量

  • 𝑣 能执行的同步条件：𝑢 → 𝑣 都已完成
  • 𝑢 完成后，signal 每个 𝑢 →
    𝑣

例子

c9-3.1-1.webp

3.2 条件变量

有三种线程

  • TaT_a 若干: 死循环打印 <
  • TbT_b 若干: 死循环打印 >
  • TcT_c 若干: 死循环打印 _

任务：

  • 对线程同步，使得屏幕打印出 <><_ 和 ><>_ 的组合

使用条件变量，只要回答三个问题：

  • 打印 “<” 的条件？打印 “>” 的条件？打印 “_” 的条件？

同步的本质是线程需要等待某件它所预期的事件发生，而事件的发生总是可以用条件 (例如 depth 满足某个条件，或是程序处于某个特定的状态) 来表达。因此计算机系统的设计者实现了条件变量，将条件检查和临界区 “放在一起”，以实现线程间的同步。