锁与并发控制

1. 锁的基本思想

锁是用于保护临界区的工具，确保临界区代码以原子方式执行，防止多个线程同时访问共享资源。锁通过在临界区前后添加lock()和unlock()操作，保证互斥性。

示例：保护共享变量

以下代码展示如何使用锁保护对共享变量balance的更新：

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

锁的状态：锁变量（如mutex）记录锁的状态：
- 可用（unlocked/free）：无线程持有。
- 占用（locked/held）：某线程持有，处于临界区。
锁的语义：
- lock()：尝试获取锁。若锁可用，线程获取锁并进入临界区；若锁被占用，线程等待。
- unlock()：释放锁，使锁重新可用。若有等待线程，其中一个将获取锁。

锁的作用

锁为程序员提供调度控制，将操作系统的无序调度转化为可控状态，确保临界区的互斥执行。

2. POSIX 线程锁（Pthread Mutex）

POSIX 库使用互斥量（mutex）实现锁，提供线程间的互斥。以下是Pthread的锁代码：

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
Pthread_mutex_lock(&lock); // 获取锁
balance = balance + 1;
Pthread_mutex_unlock(&lock); // 释放锁

特点：支持细粒度锁策略，即用不同锁保护不同变量，提高并发性。
优势：相比单一粗粒度锁，细粒度锁允许更多线程同时进入不同临界区。

3. 锁的实现

实现高效锁需要硬件和操作系统的支持。以下介绍几种实现方法及其硬件原语。

关键问题

硬件支持：需要原子指令（如测试并设置、比较并交换）。
操作系统支持：提供调度和队列管理（如休眠/唤醒机制）。
目标：实现高效、公平的互斥原语。

评价锁的标准

正确性（Correctness）：能否保证互斥，防止多个线程同时进入临界区？
公平性（Fairness）：每个线程是否有平等机会获取锁？是否避免线程饿死？
性能（Performance）：
- 无竞争：单一线程获取/释放锁的开销。
- 单CPU竞争：多线程在单处理器上的性能。
- 多CPU竞争：多线程在多处理器上的性能。

4. 实现方法一：控制中断

在单处理器系统中，最早的互斥方法是关闭中断：

void lock() {
    DisableInterrupts();
}
void unlock() {
    EnableInterrupts();
}

工作原理

关闭中断确保临界区不被中断，代码原子执行。
打开中断后，恢复正常调度。

优缺点

优点：简单，易于实现。
缺点：
- 要求线程具有特权操作权限，可能被滥用（如独占CPU或死循环）。
- 不支持多处理器，线程可在其他CPU上进入临界区。
- 可能导致中断丢失，影响系统功能（如磁盘I/O）。
- 效率较低，现代CPU处理中断切换较慢。

适用场景

操作系统内部使用（如访问内核数据结构），因其可信且无需外部程序干预。

5. 实现方法二：测试并设置（Test-and-Set）

测试并设置（test-and-set）是硬件提供的原子指令，用于构建自旋锁（spin lock）。以下是其C语言伪代码：

int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr;
    *old_ptr = new;
    return old;
}

自旋锁实现

以下是基于测试并设置的自旋锁：

typedef struct lock_t {
    int flag;
} lock_t;

void init(lock_t *lock) {
    lock->flag = 0; // 0表示锁可用，1表示占用
}

void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1)
        ; // 自旋等待
}

void unlock(lock_t *lock) {
    lock->flag = 0;
}

工作原理

TestAndSet原子地返回旧值并设置新值。
若flag=0（锁可用），线程获取锁并设置flag=1。
若flag=1（锁占用），线程自旋直到锁释放。

评价

正确性：通过原子操作保证互斥。
公平性：无公平性保证，可能导致线程饿死。
性能：
- 单CPU：性能差，持有锁的线程被抢占时，其他线程浪费时间片自旋。
- 多CPU：性能较好，临界区短时自旋开销小（线程数接近CPU数）。

局限性

单CPU上需抢占式调度器，否则自旋线程无法让出CPU。

6. 实现方法三：比较并交换（Compare-and-Swap）

比较并交换（compare-and-swap）是更强大的硬件原语：

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

自旋锁实现

只需替换lock()函数：

void lock(lock_t *lock) {
    while (CompareAndSwap(&lock->flag, 0, 1) == 1)
        ; // 自旋
}

特点

与测试并设置行为类似，适用于简单自旋锁。
更强大，可用于无等待同步（wait-free synchronization）。

7. 实现方法四：链接的加载和条件式存储（Load-Linked/Store-Conditional）

链接的加载（load-linked）和条件式存储（store-conditional）是一对指令，常用于MIPS、ARM等架构：

int LoadLinked(int *ptr) {
    return *ptr;
}

int StoreConditional(int *ptr, int value) {
    if (no one has updated *ptr since the LoadLinked to this address) {
        *ptr = value;
        return 1; // 成功
    } else {
        return 0; // 失败
    }
}

锁实现

```c void lock(lock_t *lock) { while (1) { while (LoadLinked(&lock->flag) == 1) ; // 自旋直到flag=0 if (StoreConditional(&lock->flag, 1) == 1) return; // 成功获取锁 } }

void unlock(lock_t *lock) {
lock->flag = 0;
}



### 简洁实现
更简洁的写法（布尔短路求值）：

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

工作原理

LoadLinked读取值，StoreConditional仅在无其他线程干扰时更新值。
若条件存储失败，重新尝试。

8. 实现方法五：获取并增加（Fetch-and-Add）

获取并增加（fetch-and-add）原子地增加值并返回旧值：

int FetchAndAdd(int *ptr) {
    int old = *ptr;
    *ptr = old + 1;
    return old;
}

Ticket锁实现

Ticket锁通过ticket和turn变量保证公平性：

typedef struct lock_t {
    int ticket;
    int turn;
} lock_t;

void lock_init(lock_t *lock) {
    lock->ticket = 0;
    lock->turn = 0;
}

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

void unlock(lock_t *lock) {
    FetchAndAdd(&lock->turn);
}

工作原理

线程通过FetchAndAdd获取唯一ticket（顺序号）。
等待turn等于自己的ticket，保证先来先得。
释放锁时，turn递增，唤醒下一个线程。

评价

正确性：保证互斥。
公平性：通过顺序号避免饿死。
性能：与自旋锁类似，单CPU上自旋浪费资源，多CPU上性能较好。

9. 避免自旋：操作系统支持

自旋锁在单CPU上效率低，需操作系统提供休眠/唤醒机制。

方法一：让出CPU（Yield）

通过yield()系统调用主动让出CPU：

void lock() {
    while (TestAndSet(&flag, 1) == 1)
        yield(); // 让出CPU
}

void unlock() {
    flag = 0;
}

优点：单CPU上避免自旋浪费时间片。
缺点：
- 多线程场景下，频繁上下文切换成本高。
- 可能导致饿死，线程反复让出而无法获取锁。

方法二：队列+休眠

使用队列管理等待线程，结合park()和unpark()实现高效锁：

typedef struct lock_t {
    int flag;
    int guard;
    queue_t *q;
} lock_t;

void lock_init(lock_t *m) {
    m->flag = 0;
    m->guard = 0;
    queue_init(m->q);
}

void lock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1)
        ; // 自旋获取guard
    if (m->flag == 0) {
        m->flag = 1;
        m->guard = 0;
    } else {
        queue_add(m->q, gettid());
        m->guard = 0;
        park();
    }
}

void unlock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1)
        ; // 自旋获取guard
    if (queue_empty(m->q))
        m->flag = 0;
    else
        unpark(queue_remove(m->q));
    m->guard = 0;
}

工作原理：
- guard作为自旋锁，保护flag和队列操作。
- 若锁被占用，线程加入队列并休眠（park）。
- 释放锁时，唤醒队列中的下一个线程（unpark）。
优化：通过setpark()避免唤醒/等待竞争。
优点：避免自旋，减少CPU浪费；队列确保公平性。
缺点：仍需短暂自旋获取guard。

10. Linux Futex锁

Linux通过futex（fast user-space mutex）提供高效锁机制：

void mutex_lock(int *mutex) {
    int v;
    if (atomic_bit_test_set(mutex, 31) == 0)
        return;
    atomic_increment(mutex);
    while (1) {
        if (atomic_bit_test_set(mutex, 31) == 0) {
            atomic_decrement(mutex);
            return;
        }
        v = *mutex;
        if (v >= 0)
            continue;
        futex_wait(mutex, v);
    }
}

void mutex_unlock(int *mutex) {
    if (atomic_add_zero(mutex, 0x80000000))
        return;
    futex_wake(mutex);
}

特点：
- 使用整数记录锁状态（最高位表示锁是否占用，其余位记录等待者数）。
- 优化无竞争场景，仅需少量原子操作。
- 若锁被占用，调用futex_wait休眠；释放时调用futex_wake唤醒。

11. 两阶段锁

两阶段锁结合自旋和休眠：

第一阶段：短暂自旋，期待锁快速释放。
第二阶段：若自旋失败，线程休眠。

特点

适用于锁释放较快的场景，减少休眠开销。
Linux的futex锁即为此类（自旋一次后休眠）。

12. 总结

锁是并发编程的核心工具，通过硬件原子指令（如测试并设置、比较并交换、获取并增加）和操作系统支持（如yield、futex）实现互斥。不同实现方法在正确性、公平性和性能上各有权衡：

自旋锁简单高效，适合多CPU短临界区。
休眠锁（如futex）避免CPU浪费，适合单CPU或长临界区。
Ticket锁保证公平性，适合高竞争场景。
两阶段锁平衡自旋和休眠，适应多种场景。