lllllan's blog

第 28 章 锁

8分钟阅读

第 28 章 锁

并发编程的核心挑战是保证指令序列的原子性执行。锁（lock）通过保护临界区，确保其像单条原子指令一样执行。

1. 锁的基本概念

锁的基本思想

锁用于保护临界区（如更新共享变量）：

lock_t mutex; // 全局锁变量
... 
lock(&mutex); 
balance = balance + 1; // 临界区
unlock(&mutex);

锁是一个变量，保存当前状态：

  • 可用（available/unlocked）：无线程持有。
  • 被占用（acquired/locked）：有线程持有并处于临界区。

内部可能还包含持有者信息或等待队列。

语义：

  • lock()：尝试获取锁。如果可用则获取并进入临界区；如果被占用则阻塞，直到锁被释放。
  • unlock()：释放锁。如果没有等待者则设为可用；如果有等待者则唤醒其中一个。

锁为程序员提供了最小程度的调度控制，确保同一时间只有一个线程在临界区内活跃。

Pthread 锁

POSIX 将锁称为互斥量（mutex）。

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER; 
 
Pthread_mutex_lock(&lock); 
balance = balance + 1; 
Pthread_mutex_unlock(&lock);

通过传入不同的锁变量，可以实现细粒度（fine-grained）锁策略，保护不同的数据，提高并发度。

实现目标与评价标准

关键问题：如何构建高效的锁？

我们需要哪些硬件和操作系统支持，以低成本实现互斥？

评价锁实现的三个主要标准：

  1. 互斥（Mutual Exclusion）：最基本的要求。锁能否有效阻止多个线程同时进入临界区？
  2. 公平性（Fairness）：竞争线程是否有公平的机会获得锁？是否会发生饿死（starvation）？
  3. 性能（Performance）：使用锁的时间开销（无竞争、单 CPU 竞争、多 CPU 竞争）。

2. 早期解决方案

控制中断

最早的互斥方案之一是在临界区关闭中断（仅适用于单处理器）。

void lock() { DisableInterrupts(); } 
void unlock() { EnableInterrupts(); }
  • 优点：简单。
  • 缺点：安全性差（需特权操作）、多处理器失效、可能丢失中断、效率低。
  • 适用场景：仅限于操作系统内部使用（如访问内核数据结构）。

纯软件算法

早期的纯软件互斥算法（如 Dekker 和 Peterson 算法）仅依赖 load 和 store 指令。

Peterson 算法示例（双线程）：

// flag[self] = 1 表示意图获取锁; turn = 1 - self 表示让出优先权
while ((flag[1-self] == 1) && (turn == 1 - self)) ; // 自旋等待

现状：由于现代硬件的松散内存一致性模型，这些算法在现代机器上无法正确运行，且已被硬件辅助锁取代。

3. 硬件原语与自旋锁

为了支持多处理器并发，硬件提供了原子指令。

测试并设置 (Test-and-Set)

硬件指令 TestAndSet（或 xchg）能原子地读取旧值并设置新值。

尝试 1：使用简单标志（失败） 如果仅用普通标志位，TEST 和 SET 之间可能发生中断，导致两个线程同时进入临界区（缺乏原子性）。

尝试 2：自旋锁（成功） 利用原子指令实现正确的自旋锁：

void lock(lock_t *lock) { 
    // 原子地检查并设置：如果 flag 原为 0，返回 0 -> 获取锁；否则自旋
    while (TestAndSet(&lock->flag, 1) == 1) 
        ; // spin-wait 
}

比较并交换 (Compare-and-Swap)

CAS 指令比 Test-and-Set 更强大，是无等待同步的基础。

int CompareAndSwap(int *ptr, int expected, int new) { 
    int actual = *ptr; 
    if (actual == expected) *ptr = new; 
    return actual; 
}

链接加载与条件存储 (LL/SC)

MIPS、ARM 等架构提供的指令对。只有当 ptr 在 LoadLinked 后未被更新时，StoreConditional 才会成功。

void lock(lock_t *lock) { 
    while (LoadLinked(&lock->flag) || !StoreConditional(&lock->flag, 1)) 
        ; // spin 
}

获取并增加 (Fetch-and-Add) 与 Ticket Lock

FetchAndAdd 能原子地返回旧值并让该值自增。利用它可以实现 Ticket Lock（票据锁）：

void lock(lock_t *lock) { 
    int myturn = FetchAndAdd(&lock->ticket); 
    while (lock->turn != myturn) ; // spin 
} 
void unlock(lock_t *lock) { FetchAndAdd(&lock->turn); }

特性：保证了公平性（FIFO），避免饿死。

评价自旋锁

  1. 正确性：是。能够保证互斥。
  2. 公平性：普通自旋锁不公平（可能饿死），Ticket Lock 公平。
  3. 性能：
    • 单 CPU：开销大（持有锁线程被中断时，其他线程浪费时间片）。
    • 多 CPU：性能良好（若临界区较短）。

4. 解决自旋问题：操作系统支持

关键问题：怎样避免自旋？

自旋锁在单处理器上效率极低，如何让锁不会不必要地自旋，浪费 CPU 时间？

方法 1：让出 CPU (Yield)

当发现锁被占用时，主动放弃 CPU (yield)。

方法 2：使用队列休眠 (Solaris)

使用 park()（休眠）和 unpark()（唤醒）显式控制等待队列。

void lock(lock_t *m) { 
    if (m->flag == 0) {
        m->flag = 1; // 获取锁
    } else { 
        queue_add(m->q, gettid()); 
        park(); // 睡眠
    } 
}

注：实际代码需配合 guard 锁保护队列操作，并处理唤醒竞争。

方法 3：两阶段锁与 Linux Futex

Linux 提供了 futex，结合用户态检查和内核态睡眠。

两阶段锁 (Two-Phase Lock) 策略：

  1. 第一阶段：自旋一段时间（希望很快获取锁）。
  2. 第二阶段：如果自旋失败，则调用系统调用（如 futex）睡眠。

这种方法结合了自旋锁（低开销）和互斥锁（避免浪费 CPU）的优点。

5. 小结

实现高效的锁需要硬件和操作系统的协同：

  • 硬件：提供原子指令（Test-and-Set, CAS, LL/SC, Fetch-and-Add）实现基础互斥。
  • 操作系统：提供睡眠/唤醒原语（park/unpark, futex）以解决自旋浪费问题。
  • 最佳实践：结合自旋和睡眠（两阶段锁）以适应不同竞争场景。

Flashcards

Loading cards...