{T}

并发控制与线程调度

本文整理多线程环境下的并发控制手段（原子操作、锁、信号量、乐观锁、分布式锁）与线程调度算法，并以哲学家就餐问题说明死锁与活锁的成因与解法。

一、原子操作与竞争条件

原子操作指操作不可分，多线程环境下其执行过程无法被中断。例如 i++ 并非原子操作，它由 3 个原子步骤组成：读取 i、计算 i+1、写入新值。在多线程多核环境下，i++ 会造成竞争条件。

竞争条件指多个线程对共享资源（内存地址）的读写存在竞争，资源最终值取决于执行时序，不可预测。访问共享资源、可能引发竞争条件的程序片段称为临界区。

解决竞争条件的思路分两类：

  • 互斥：不让多个线程同时进入临界区。
  • 避免竞争：如 ThreadLocal（每线程独享变量）、CAS 指令、乐观锁。

二、CPU 原子指令

CAS

Compare And Swap 指令要求调用方明确知道内存地址的当前值，仅当期望值与真实值相等时才更新：

code
cas(&oldValue, expectedValue, targetValue)

cas 本身是 CPU 提供的原子操作。使用 cas 实现 i++：

code
while(!cas(&i, i, i+1)) { /* 失败则重试 */ }

cas 失败时返回 false，调用方需重新读取并重试，直到成功。

TAS

Test-And-Set 指令将内存地址置 1，若原值为 0 则置 1 并返回成功，否则失败。可视为特殊的 cas：

code
tas(&lock) { return cas(&lock, 0, 1) }

三、锁

**锁（lock）**的目标是限制进入临界区的线程数量，底层由 cas/tas 实现。以 cas 实现互斥锁：

cpp
int lock = 0;
enter() { while(!cas(&lock, 0, 1)) { /* 自旋 */ } }
leave() { lock = 0; }

lock=0 表示无线程在临界区，lock=1 表示有线程在临界区。

自旋锁

enter 中不断执行 cas 直到获得锁，线程不主动让出 CPU，称为自旋锁。优点是无上下文切换开销；缺点是持续占用 CPU。

休眠与 Monitor

为减少 CPU 消耗，可在 cas 失败后调用 wait 主动触发上下文切换，由其他线程 notify 唤醒。Java 通过 synchronized 关键字封装该逻辑：每个对象关联一个 Monitor，Monitor 封装 enter/leave/wait/notify，既提供互斥又提供线程间通信。

信号量（Semaphore）

信号量是广义的锁，允许 N 个线程同时进入临界区。用 up/down 两个原子操作管理计数器：

cpp
up(&lock)   { while(!cas(&lock, lock, lock+1)) { } }
down(&lock) { while(!cas(&lock, lock, lock-1) || lock == 0) { } }
  • lock=1 时等价于互斥锁（mutex）；
  • lock=N 时允许 N 个线程进入临界区，即信号量。

信号量可用来实现生产者-消费者模型：empty 记录空位、full 记录等待线程数、mutex 保证插入/移除互斥。

四、分布式锁

当服务部署在多个容器/机器上（如 100 个容器各有一个扣减积分的服务，数据在 Redis 中），单机 CPU 指令提供的原子性不再适用，需要分布式锁。分布式环境下由 Redis 的 setnx、ZooKeeper 的节点操作等提供原子操作，实现跨进程的临界区互斥。

五、乐观锁与版本控制

悲观锁对临界区上锁，持保守态度，本质为互斥（如 MySQL 表锁/行锁、Java 锁）。乐观锁允许多方同时编辑，提交时检测版本冲突，类似 Git：

code
cas(&version, 100, 108); // Alice 先提交，成功
cas(&version, 100, 106); // Bob 后提交，失败，需拉取最新后合并

应用场景：购物车可用版本号字段，操作时校验版本是否最新，冲突则提示刷新。

六、去中心化并发：区块链类比

区块链通过历史版本链解决分布式信用与并发：

  • 每个 Block 记录数据，并保存上一节点的摘要签名；
  • 修改任一历史节点会导致其后所有节点签名失效，从而防篡改；
  • 高并发下单时允许多个商家各自维护分支（分区域、分店），定时逐级合并，避免中心化锁瓶颈。

除锁之外，处理并发还可考虑：Lock-Free 数据结构（基于 cas，如 Lock-Free 队列）、ThreadLocal（空间换时间，避免共享）。

七、线程调度算法

所谓调度，即操作系统决定未来执行哪些线程。主线有二：调度场景从何而来、各调度算法如何工作。

先到先服务（FCFS）

作业按到达顺序排队，先入先出（FIFO），作业间不切换。公平性朴素、吞吐量最优（无切换开销），但长作业会阻塞后面的短作业。

短作业优先（SJF）

优先执行预估时间短的作业。以平均等待时间 = 总等待时间 / 任务数 衡量：优先短作业可显著降低平均等待时间，提升用户满意度。

优先级队列（PriorityQueue）

用堆在 (O(1)) 时间内取最高优先级元素。优先级可由 W/P（等待时间/预估执行时间）描述：W 越大、P 越小越靠前。解决紧急任务插队与久等任务插队问题。

抢占（Preemption）

将执行能力分时成时间片段，每个任务执行一个片段后中断、重新排队。结合优先级队列构成基本调度模型：线程按优先级入队，每次取最高优先级执行一个时间片段。

抢占调度示意

多级队列模型

两级队列

  • 上层高优先级队列：非抢占 + 优先级队列，处理紧急任务；
  • 下层低优先级队列：抢占 + 优先级队列，每次执行片段后判断高优队列是否有任务。

多级队列

多级队列可近似实现 SJF：短任务在高优小时间片队列中完成，长任务逐级下沉到大时间片队列，同时保证高优任务最先执行。实际系统通常用 n 层，把长任务沉淀到空闲时段执行。

八、哲学家就餐问题

5 个哲学家围坐圆桌，每人需同时拿到左右两把叉子才能吃面。用以建模并发资源竞争。抽象：forks[i] 记录叉子归属（-1 表示在桌上），LEFT(id) 计算左邻编号。

死锁与活锁

朴素解法中每个哲学家先拿左叉再拿右叉，以下时序会触发死锁：5 人各拿到左叉后互等右叉，形成循环依赖、永久等待。

死锁的 4 个必要条件：

  1. 互斥：资源同时只能被一个线程占用；
  2. 持有等待：线程持资源并等待其他资源；
  3. 不可抢占：拿不到资源时不释放已持资源；
  4. 循环等待：线程间形成环形等待链。

死锁与**活锁（Livelock）**都是饥饿（Starvation，线程长期拿不到资源）的形式。活锁中线程都在工作但无一推进，例如所有哲学家同时拿起左叉、发现右叉不可用又同时放下，周而复始。

解决方案

  • 全局锁排队：所有操作加同一个锁，并发度为 1，正确但性能差。
  • 同时拿/放两叉：仅当两叉皆空闲才拿起，单锁、并发度最高 2，无死锁无饥饿。
  • 转让模型（并发度 5）：每把叉子视为独立锁，若叉子属于他人且该人不在吃面且叉子为 dirty，则转让。引入 dirty 标志（每次转让后置 false，重新拿起后置 true），避免叉子在两哲学家间反复转让导致活锁。

小结

  • 原子操作（CAS/TAS）是锁的底层基础；锁、信号量、乐观锁、分布式锁分别覆盖单机互斥、N 线程并发、版本冲突、跨进程临界区。
  • 调度从 FCFS、SJF 演进到优先级队列 + 抢占 + 多级队列，兼顾公平性、平均等待时间与紧急任务。
  • 死锁需同时满足四条件；可通过定时释放（tryLock）、统一加锁顺序、资源转让模型化解；活锁需靠状态标志避免无限反复。