并发中的同步互斥

软硬件解决互斥、信号量解决、经典问题、管程

2024/04/26

并发带来的进程同步问题

操作系统为了让 CPU 充分忙碌，并充分利用各种资源，就需要使得多个应用程序分时执行，并由操作系统来完成任务切换，也就是进程的并发。并发性能有效改善系统资源利用率，也带来了对共享资源的争夺问题，也就是同步互斥问题。操作系统中的进程同步是指在多进程环境下，为了防止多个进程在执行共享资源时产生冲突，按照某种顺序执行进程的一系列机制和方法。进程同步主要是解决数据的一致性和进程的协调问题。

并发与并行

并行 (Parallel) 是指两个或者多个事件在同一时刻发生；
并发 (Concurrent) 是指两个或多个事件在同一时间间隔内发生。

对于基于单 CPU 的计算机而言，各个“同时”运行的程序其实是串行分时复用一个 CPU ，任一个时刻点上只有一个程序在 CPU 上运行。这些虚拟性的特征给应用程序的开发和执行提供了非常方便的执行环境，但也给操作系统的设计与实现提出了很多挑战。--- rCore-tutorial 并发性

临界区（Critical Section）

临界区是指那段访问共享资源的代码区域。

临界资源

临界资源是那些一次只能被一个线程或进程安全访问的资源。这些资源可能是物理的，如打印机，也可能是逻辑的，如共享变量或数据结构。为了管理对临界资源的访问，通常需要使用互斥锁或其他同步机制。

数据一致性

在单处理器（即只有一个核的CPU）下，如果某线程更新了一个可被其他线程读到的共享数据，那么后续其他线程都能读到这个最新被更新的共享数据。

竞态条件（race condition）

竞态条件（race condition）指的是两个或者以上进程或者线程并发执行时，其最终的结果依赖于进程或者线程执行的精确时序。

当某些线程在修改变量，而其他线程在读取这个变量时，由于线程之间的执行顺序不能提前预知（取决于操作系统的调度），导致各个线程对同一变量的读写操作序列不确定，这就会导致不同线程可能会看到与预期结果不一样的值，这就出现了数据不一致性的问题，而且每次执行的结果不确定。我们把这种两个或多个线程在竞争访问同一资源时，执行结果取决于它们的不可预知的执行顺序的情况称为线程的竞态条件（race condition）。

出现线程的数据不一致问题和竞态条件问题的根本原因是调度的不可控性：即读写共享变量的代码片段会随时可能被操作系统调度和切换。先看看如下的伪代码例子：

[rust]//全局共享变量 NUM初始化为 0
static mut NUM : usize = 0;
...
//主进程中的所有线程都会执行如下的核心代码
unsafe { NUM = NUM + 1; }
...
//所有线程执行完毕后，主进程显示num的值
unsafe {
    println!("NUM = {:?}", NUM);
}

如果线程的个数为 n ，那么最后主进程会显示的数应该是多少呢？也许同学觉得应该也是 n ，但现实并不是这样。为了了解事实真相，我们首先必须了解Rust编译器对 num = num + 1; 这一行源代码生成的汇编代码序列。

[asm]# 假设NUM的地址为 0x1000
# unsafe { NUM = NUM + 1; } 对应的汇编代码如下
addi x6, x0, 0x1000        # addr 100: 计算NUM的地址
                           # 由于时钟中断可能会发生线程切换
ld   x5, 0(x6)             # addr 104: 把NUM的值加载到x5寄存器中
                           # 由于时钟中断可能会发生线程切换
addi x5, x5, 1             # addr 108: x5 <- x5 + 1
                           # 由于时钟中断可能会发生线程切换
sd   x5, 0(x6)             # addr 112: 把NUM+1的值写回到NUM地址中

可以看到这里生成了四行 RISC-V 汇编代码，如果多个线程在操作系统的管理和调度下都执行这段代码，那么在上面四行汇编代码之间（4、6、8）可能产生时钟中断，并导致线程调度和切换。

假设 NUM=0，有两个线程 A 和 B，A 到了第 8 行（NUM）被中断，此时寄存器 x5 = 1，而 B 线程则拿到时间片执行，此时 NUM 为 0（汇编第 9 行还未执行）， B 线程执行完全程：

NUM = 0 > x5 = 0 > x5 = 1 > NUM = 1

最后时间片还给 A，A 把 x5 的值写入 NUM，NUM = 1。而我们的期望的”正确“结果是 NUM = 2，这就是竞态条件问题。

条件变量：通常与互斥锁配合使用，允许进程在某些条件不满足时阻塞，直到其他进程改变条件并通知它。

屏障：用于同步一组进程，要求所有进程都到达屏障点后才能继续执行。

相传在杭电和理工之间有一条狭窄的东西通道。该通道通行需要遵循以下原则：当对向无学生过通道时，此向的学生可以过通道，且后续同向的学生可跟随通过；否则，此向学生需要等待。用信号量解决上述问题。

通道互斥信号量 mutex_tunnel = 1
status = 0 # 0 没人 1 hdu 2 zstu
count = 0 # 桥上人数
请求互斥访问 status 和 count信号量 mutex = 1

HDU stu

[rust]fn hdu_student() {
  wait(mutex)
  if status == 0 || status == 1 {
    if status == 0 {
      wait(mutex_tunnel); // 通道空闲，拿下
    }
    status = 1; // 状态为杭电使用
    count += 1; // 增加通道上学生数量
  } else {
    // 理工正在用呢
    signal(mutex); // 让出互斥信号量，让别的学生能检查状态
    wait(mutex_tunnel); // 等待别的学校让出通道
    wait(mutex); // 请求互斥访问
    status = 1; // 状态置为杭电使用
    count += 1;
  }
  signal(mutex); // 释放互斥信号量

  杭电通行🚀；

  wait(mutex); // 准备离开通道
  count -= 1;
  if count == 0 {
    status = 0; // 通道空闲
    signal(mutex_tunnel); // 释放通道，允许别的学校学生进入
  }
  signal(mutex);
}

ZSTU stu

[rust]fn hdu_student() {
  wait(mutex)
  if status == 0 || status == 2 {
    if status == 0 {
      wait(mutex_tunnel); // 通道空闲，拿下
    }
    status = 2; // 状态为理工使用
    count += 1; // 增加通道上学生数量
  } else {
    // 杭电正在用呢
    signal(mutex); // 让出互斥信号量，让别的学生能检查状态
    wait(mutex_tunnel); // 等待别的学校让出通道
    wait(mutex); // 请求互斥访问
    status = 2; // 状态置为理工使用
    count += 1;
  }
  signal(mutex); // 释放互斥信号量

  理工通行🚗；

  wait(mutex); // 准备离开通道
  count -= 1;
  if count == 0 {
    status = 0; // 通道空闲
    signal(mutex_tunnel); // 释放通道，允许别的学校学生进入
  }
  signal(mutex);
}

并发带来的进程同步问题

并发与并行

临界区（Critical Section）

临界资源

数据一致性

竞态条件（race condition）

解决方案

互斥（Mutual Exclusion）

同步原语（Synchronization Primitives）

死锁（Deadlock）和饥饿（Starvation）

进程同步案例

杭电理工单边桥