同步工具

同步工具概述

定义

同步工具是操作系统提供的机制，用于协调并发进程/线程对共享资源的访问，确保数据一致性和程序正确性

核心目标

互斥：确保临界区间同时只有一个进程访问
同步：控制进程间的执行顺序
痛惜：进程间安全地交换信息

作用

保证数据一致性
- 避免线程并发运行导致的数据错误。
- 可以想象成银行。假设A和B同时登录一个有1000元存款的银行账户，A取出500元，B取出400元。但由于并发执行，B查看账户时的余额仍然是1000元，并且取钱后会将600元写入余额，导致错误。
- 所以需要通过并发锁等方式，在A访问账户时阻塞B对账户的访问
控制访问顺序
- 确保每个环节在正确的时机开始
- 可以想象成厨房。假设没有控制访问，会出现在菜还没做完时，服务员就上菜的现象。需要控制在炒菜完成后，才开始上菜线程。
协调资源分配
- 确保正确分配资源
- 可以想象成停车场，如果没有调度，会发生有车试图停在已经被占用的车位，而空车位没有车去停泊

主要同步工具类型

互斥锁(Mutex)

基本概念

1
2
3
4


// 基本操作
mutex_lock(&mutex);    // 获取锁（原子操作）
// 临界区代码
mutex_unlock(&mutex);  // 释放锁（原子操作）

工作机制
- 加锁：如果锁可用则获取，否则阻塞等待
- 解锁：释放锁并唤醒等待的进程
- 原子性：加锁和解锁操作不可被中断
使用场景：上面提及的银行账户问题
高级特性：
- 递归锁：同一线程可多次获取
- 优先级继承：防止优先级反转
- 超时机制：避免无限期等待

信号量(Semaphore)

一种用于进程/线程同步的抽象数据结构
核心思想：由一个整数来表示可用资源的数量，通过原子操作来控制对这些资源的访问
就像一个“资源计数器”
- 记录还有多少资源可以使用
- 当有人要用资源时，计数器+1
- 当有人释放资源时，计数器-1
- 当计数器为0时，后来的人必须等待

基本概念

1
2
3


sem_wait(&semaphore);   // P操作：信号量-1，如果<0则阻塞
  // 临界区或资源使用
sem_post(&semaphore);   // V操作：信号量+1，唤醒等待进程

类型分类
- 计数信号量（用于泊车问题）
- 二进制信号量（类似互斥锁）
经典问题：生产者-消费者问题

条件变量(Condition Variable)

基本概念：条件变量用于在某个条件满足之前让线程等待，通常与互斥锁配合使用。

读写锁(Read-Writer Lock)

基本概念：允许多个读者同时访问，但写者需要独占访问。
使用场景
- 数据库系统
- 缓存系统
- 文件系统
- 读多写少的场景

屏障(Barrier)

基本概念：让多个线程在某个点等待，直到所有线程都到达该点才继续执行。、

自旋锁(Spin Lock)

基本概念：不会让线程睡眠，而是持续检查锁状态
使用场景：
- 临界区很短
- 多处理器系统
- 内核级同步

注：生产者-消费者问题

问题定义：生产者-消费者问题描述了两类线程之间的协作关系
- 生产者：生成数据并放入缓冲区
- 消费者：从缓冲区取出数据并处理
- 缓冲区：存储数据的共享区域，容量有限
核心约束条件
- 缓冲区满时：生产者必须等待，不能再生产
- 缓冲区空时：消费者必须等待，不能再消费
- 互斥访问：生产者和消费者不能同时访问缓冲区
- 同步关系：生产者生产的数据要能被消费者及时消费

竞态条件

定义

当多个进程（或进程）并发地访问和操作同一数据，且执行结果依赖于访问发生地特定顺序时，这种情况被成为竞态条件。

核心特征

多个执行流：至少有两个线程/进程
共享数据：共享数据
并发访问：并发访问
结果不确定：最终结果取决于执行顺序

经典案例

银行账户问题

临界区

定义

考虑一个由n个进程组成的系统{p0, p1, … p~~n-1~~}，每个进程都有一个临界区代码段，例如改变公共变量、更新表格、写文件等。同时只能有一个进程位于临界区中。当一个进程在临界区中时，其他进程都不能进入它们的临界区。每个进程必须在进去区请求进入临界区的许可。许可应该在退出区被释放。
即临界区为程序中访问共享资源的代码段。在多进程或多线程环境中，这段代码同一时刻只能被一个执行单元执行，以避免数据竞争和不一致

组成

完整的进程结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


do
{
    request_permission(); //进入区，请求进入临界区的许可

    access_shared_resource(); //临界区，访问和修改共享资源的核心代码

    release_permission(); //退出区，释放临界区，允许其他进程进入

    do_other_work(); //剩余区，执行不涉及共享资源的其他操作
}

基本要求

互斥性：同时只能由一个进程在临界区内
进展性：如果临界区空闲且有进程想要进入，那应该能进入
有界等待：进程等待时间应该是有限的

解决方案

互斥锁
信号量
自旋锁

时机应用场景

操作系统
数据库管理系统
Web服务器

经典的软件同步算法————Peterson算法

核心设计思想————谦让机制

每个进程都表达自己想要进入临界区的意愿
同时主动谦让把优先权交给对方

实现代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


// 进程Pi (i = 0 或 1)
// j是另一个进程的编号 (j = 1-i)
  do {
    // === 进入区 ===
    flag[i] = true;              // 第1步：举手表示"我想进入临界区"
    turn = j;                    // 第2步：谦让，"你先请"

    // 第3步：等待检查
    while (flag[j] == true && turn == j) {
        // 如果对方也想进入(flag[j]==true) 
        // 且确实轮到对方(turn==j)
        // 那么我就等待
        // 这里是忙等待
    }

    // === 临界区 ===
    critical_section();

    // === 退出区 ===
    flag[i] = false;             // 第4步：表示"我不再需要临界区了"

    // === 剩余区 ===
    remainder_section();

} while (true);

处理两个进程时的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


// ====== 进程P0 ======
do {
    flag[0] = true;    // P0想要进入
    turn = 1;          // P0谦让，优先权给P1

    while (flag[1] == true && turn == 1) {
        // 等待：如果P1也想进入且轮到P1
    }

    // P0的临界区
    printf("P0 in critical section\n");
  // 访问共享资源...

  flag[0] = false;   // P0完成，退出

  // P0的其他工作

}while (true);

// ====== 进程P1 ======
do {
    flag[1] = true;    // P1想要进入
    turn = 0;          // P1谦让，优先权给P0

    while (flag[0] == true && turn == 0) {
        // 等待：如果P0也想进入且轮到P0
    }

    // P1的临界区
    printf("P1 in critical section\n");
    // 访问共享资源...

    flag[1] = false;   // P1完成，退出

    // P1的其他工作

} while (true);

顺序一致性

基本概念

定义

一个多处理器是顺序一致的，当且仅当任何一次的执行的结果都和某个顺序执行的结果相同，切每个处理器的操作在这个顺序中都按照程序指定的顺序出现

两个核心要求

程序顺序：每个处理器内的操作必须按程序指定的顺序执行
全局顺序：所有处理器必须对所有内存操作有统一的观察顺序

直观理解

可以类比为图书馆的借书系统
想象一个图书馆的借书系统，顺序一致性即所有人能看到相同的结束记录顺序
- 张三借《操作系统》
- 李四借《数据结构》
- 王五还《算法导论》
- 无论在哪个分馆查询，大家看到的记录顺序完全一致

存储缓冲区(Store Buffer)

基本概念

定义：存储缓冲区是位于CPU和缓存之间的硬件组件，用于临时存储CPU发出的写操作，以提高系统性能
- CPU -> Store Buffer -> Chache -> Memory
目的：
- 避免CPU再写操作时等待
- 提高流水线指令地效率
- 允许写操作地批量处理和优化

为什么需要Store Buffer

无Store Buffer时：
- CPU执行：x = 1;
- 步骤：
  - CPU发送写请求到缓存
  - 如果缓存缺失，需要等待从内存加载
  - 更新缓存
  - CPU才能继续执行下一条指令
- 延迟可能高达几百个CPU周期
有Store Buffer时：
- CPU执行：x = 1;
- 步骤：
  - CPU将写操作放入Store Buffer
  - CPU立即继续执行下一条指令
  - Store Buffer在后台异步完成实际写入
可以类比为邮箱，如果没有邮箱，那么用户每一封信都要等待邮递员到来，才能写信交给邮递员；有邮箱后之后写完放入邮箱就能写下一封

存储缓冲区的详细结构

硬件组织

1
2
3
4
5
6
7
8
9


          CPU Core
             |
    [Store Buffer]  ←── 队列结构，FIFO
       |  |  |  |
    Entry Entry Entry Entry
       |  |  |  |
         Cache
         |
       Memory

每个Entry包含：
- 地址 (Address)
- 数据 (Data)
- 大小 (Size)
- 有效位 (Valid)
- 其他控制信息

典型的Store Buffer参数

现代CPU的Store Buffer特征：
- 容量：16-64个条目
- 宽度：支持不同大小的写操作（1,2,4,8字节）
- 合并：相邻写操作可能被合并
- 顺序：通常按FIFO顺序排出到缓存

工作机制：FIFO队列

存在的问题

违反程序顺序

1
2
3
4
5
6
7
8
9


  //程序意图：先设置数据，再设置标志
  data = 42;    //写操作1：进入Store Buffer
  flag = true;  //写操作2：也进入Store Buffer

  //其他CPU可能观察到的顺序：
  //flag=true先生效（如果flag在缓存中）
  //data=42后生效（如果data需要从呢村加载到缓存）

  //这违反了程序顺序

Peterson算法失败

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


  // 时间线分析：两个CPU同时执行Peterson算法

  时间0: 初始状态
  flag[0] = false, flag[1] = false, turn = 任意值

  时间1: CPU0和CPU1几乎同时开始执行
  CPU0: flag[0] = true  → 进入CPU0的Store Buffer
  CPU1: flag[1] = true  → 进入CPU1的Store Buffer

  时间2: 继续执行
  CPU0: turn = 1        → 进入CPU0的Store Buffer  
  CPU1: turn = 0        → 进入CPU1的Store Buffer

  时间3: 开始检查条件
  CPU0: 读取flag[1]    → 从内存读到false（CPU1的写入还在Store Buffer中！）
  CPU1: 读取flag[0]    → 从内存读到false（CPU0的写入还在Store Buffer中！）

  时间4: 条件检查结果
  CPU0: flag[1]==false && turn==1 → false，所以不等待
  CPU1: flag[0]==false && turn==0 → false，所以不等待

  时间5: 灾难发生
  CPU0: 进入临界区 
  CPU1: 进入临界区 

  两个进程同时进入临界区！Peterson算法失败！

内存屏障与Store BUffer

定义

内存屏障是一种同步原语，用于控制内存操作的顺序，确保特定的内存操作按照预期的顺序执行
可以类比成红灯，只有当所有应该到达的车到达了才转绿灯

写屏障

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


  // 写屏障的作用：确保屏障前的写操作完成

  void store_barrier() {
      // 等待Store Buffer排空
      while (!store_buffer_empty()) {
          drain_store_buffer();
      }
      // 确保所有写操作都到达缓存/内存
  }

  // Peterson算法的修复：
  flag[0] = true;
  store_barrier();       // 确保flag[0]写入完成
  turn = 1;
  store_barrier();       // 确保turn写入完成
  while (flag[1] && turn == 1);

不同类型的屏障

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


  // x86架构的内存屏障：

  // SFENCE：Store Fence，写屏障
  void sfence() {
      asm volatile("sfence" ::: "memory");
  }

  // MFENCE：Memory Fence，全屏障
  void mfence() {
      asm volatile("mfence" ::: "memory");
  }

  // 编译器屏障：防止编译器重排序
  void compiler_barrier() {
      asm volatile("" ::: "memory");
  }

Store-to-Load Forwarding(存储转发)机制详解

作用演示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


  // 程序代码：
  x = 42;        // 写操作：把42写入变量x
  int a = x;     // 读操作：读取变量x的值

  // 没有转发机制的问题：
  // 1. x = 42进入Store Buffer，还没写到内存
  // 2. int a = x从内存读取，读到的是旧值（比如0）
  // 3. 明明刚写了42，却读到了0！

  // 有转发机制的解决：
  // 1. x = 42进入Store Buffer
  // 2. int a = x时，CPU检查Store Buffer
  // 3. 发现Store Buffer中有x=42，直接返回42
  // 4. 读到了正确的值！

转发机制的实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


  int load_operation(address addr) {
      // 1. 首先检查Store Buffer
      for (int i = store_buffer.newest; i >= store_buffer.oldest; i--) {
          if (store_buffer[i].address == addr && store_buffer[i].valid) {
              // 找到匹配的待写入数据，直接返回
              return store_buffer[i].value;
          }
      }
      
      // 2. Store Buffer中没有，从缓存/内存读取
      return cache_read(addr);
  }

即在Store Buffer中寻找所需数据，如果没有再从缓存/内存读取

Store Buffer的性能优化

写合并

在连续的地址上写入内容时会合并到同一个Entity中

Store Buffer的管理策略

阻塞策略
强制排空策略
优先级策略

原子变量

概念：

通常，像比较交换（compare-and-swap）这样的指令被用作构建其他同步工具的基础构件
其中一个工具是原子变量，它为基本数据类型提供原子的（不可中断的）更新操作
例如，对原子变量sequence的increment()操作确保sequence在没有中断的情况下被递增

过度自旋(Too Much Spinning)

概念

自旋：当线程无法获得锁时，不进入睡眠状态，而是持续循环检查锁状态，直到获得锁为止
过度自旋：在不合适的场景下使用自旋锁，导致大量CPU时间被浪费在无意义的等待上

解决方法

混合锁

核心思想：“先试试，不行就休息”
设计方式：
- 短暂自旋，快速检查锁状态
- 如果自旋失败，进入睡眠等待
- 被唤醒时：重新尝试获取锁

指数退避

核心思想：“越等越慢”
设计方式：
- 每次检查后检查间隔增加

自适应自旋

核心思想：“学习型只能等待”
设计方式：
- 根据历史学习预测检查间隔时间