常见并发问题

违反原子性缺陷

• 违反原子性缺陷(atomicity violation)：违反了多次内存访问中预期的可串行性（即代码本意是原子的，但在实际执行中并没有强制执行原子性）
• 通过给共享资源加锁，我们就可以强制让内存访问变得具有原子性

违反顺序缺陷

• 违反顺序缺陷(order violation)：两个内存访问的顺序异于预期
• 通过使用条件变量，我们可以让两个内存访问操作拥有逻辑性的先后顺序

为什么发生死锁

• 在大型的代码库中，各个组件之间有非常复杂的依赖，很容易出现依赖导致的死锁
• 模块化的开发中惯用封装来隐藏细节，而封装隐藏的细节可能会导致两个看起来毫不相关的模块发生死锁

产生死锁的四个必要条件

• 互斥：线程对于需要的资源进行互斥的访问
• 持有并等待：线程持有了资源，同时又在等待其他资源
• 非抢占：线程获得的资源不能被抢占
• 循环等待：线程之间存在一个环路，环路上的每个线程都额外持有一个资源，而这个资源又是下一个线程要申请的

死锁预防

• 循环等待

  • 让代码不会产生循环等待是一个预防死锁的常用方法
  • 最直接的办法就是获取锁时提供一个全序(total ordering)，让两个锁之间的申请顺序被严格规定下来（必须锁1被占有了，锁2才能被占有）
  • 对于有多个锁的系统，可以使用偏序(partial ordering)

• 持有并等待

  • 通过原子地抢锁，可以避免死锁的持有并等待条件
  • 原子地抢锁意为一个线程原子地占有多个锁，要么全部都拿到，要么一个锁也拿不到
  • 可以通过一个预防(prevention)锁来办到

    mutex_t L1, L2; // 系统中的锁
    
    /*
    	thread_function()函数 可能存在“持有并等待”问题的线程函数
    */
    void* thread_function() {
    	// 获取所有需要的锁
    	lock(L1);
    	lock(L2);
    
    	// 接下来的代码...
    }
    
    mutex_t prevention; // 定义预防锁prevention
    
    /*
    	thread_function_updated()函数 解决了“持有并等待”问题的线程函数
    */
    void* thread_function_updated() {
    	// 首先给预防锁上锁
    	lock(prevention);
    	// 然后获取所有需要的锁
    	lock(L1);
    	lock(L2);
    	// 然后释放预防锁
    	unlock(prevention);
    
    	// 接下来的代码...
    }
    

  • 出于某些原因，这个方案也不适用于封装：因为这个解决方案需要我们精确地知道要占有哪些锁，并原子地抢到所有的锁，而封装让我们难以知道这些信息

• 非抢占

  • 对于一个被占有的锁，在调用unlock()之前，没有其他线程可以lock()获得这个锁。而很多线程库会提供更加灵活的接口trylock()，trylock()会尝试获得锁，或者返回-1表示锁被占有了
  • 使用trylock()可以实现无死锁的加锁方法：
    1. 持有锁L1
    2. 调用trylock(L2)，尝试获得L2
    3. 如果获得L2失败，那么释放锁L1，并返回第一步重新开始
  • 这种方法虽然避免了死锁问题，但是会产生活锁(livelock) 问题，即两个线程一直在重复这些步骤，同时都抢锁失败，程序虽然在运行，但是没有任何进展

• 互斥

  • 对于一块共享资源，我们很难做到避免互斥，不过通过一些无等待(wait-free)数据结构的思想和强大的硬件指令，可以构造出不需要锁的共享资源
    • 例如通过比较并等待这一由硬件提供的原子指令，可以实现原子地给某个值增加/减少特定的数量

死锁避免

• 死锁避免(avoidance) 需要我们了解全局的信息，包括不同线程在运行中对锁的需求情况

• 银行家算法

  • 银行家算法是一种避免死锁的经典算法，其内容为：把操作系统比作银行家，把系统资源比作资金。银行家（操作系统）在批准贷款（分配资源）前，会判断这次分配后系统是否处于安全状态——如果存在一种顺序能让所有客户（进程）最终都获得所需资源并顺利完成，则批准分配；否则就让他们等待，避免系统进入不安全状态、导致死锁
  • 算法会维护4个数据结构：假设系统中有n个进程，m类资源
    • Available：长度为m的向量，表示每类资源当前可用的数量
    • Max：n×m矩阵，表示每个进程对每类资源最大的需求量
    • Allocation：n×m矩阵，表示每个进程当前已分配的资源数
    • Need：n×m矩阵，表示每个进程还需要的资源数。
      • Need[i][j] = Max[i][j] - Allocation[i][j]
  • 算法流程：

    • 资源请求分配

      1. 进程p[i]请求资源Request[i]
      2. 如果 Request[i] ≤ Need[i]，进入下一步；否则出错（请求超过最大需求）
      3. 如果 Request[i] ≤ Available，进入下一步；否则进程等待（资源不足）
      4. 试探分配，临时修改数据结构：
         • Available -= Request[i]
         • Allocation[i] += Request[i]
         • Need[i] -= Request[i]
      5. 调用安全性检查算法：
         • 如果新状态是安全的 → 正式分配
         • 否则 → 撤销试探分配，进程等待

    • 安全性检查算法

      1. 初始化两个向量：
         • Work = Available（可用资源副本）
         • Finish = [false] * n（进程完成标志）
      2. 找到一个 Finish[i] == false 且 Need[i] ≤ Work 的进程 P[i]
      3. 假设该进程执行完，释放资源：
         • Work += Allocation[i]，Finish[i] = true
      4. 重复步骤2-3，直到
         • 所有 Finish[i] == true -> 系统处于安全状态
         • 找不到满足条件的进程 -> 系统处于不安全状态（可能死锁）

检查并恢复

• 如果死锁发生的不是很频繁，那么可以在死锁发生的时候终止某个进程/线程、手动抢占资源、回滚事务、或者直接把电脑重启
• 《新机器的灵魂》一书中提到一句话：“不是所有值得做的事情都值得做好”。如果一个坏事的发生频率很小，影响很小，那么就不应该总是花费大量的时间和精力来预防它