1
// C++ 中的 CAS
2
std::atomic<int> value{0};
3

4
int expected = 0;
5
int desired = 42;
6
bool success = value.compare_exchange_strong(expected, desired);
7
// success == true:  value 从 0 变为 42
8
// success == false: expected 被更新为 value 的当前值
9

10
// CAS 循环 —— 无锁自增的标准模式
11
void lock_free_increment(std::atomic<int>& val) {
12
    int old_val = val.load();
13
    while (!val.compare_exchange_weak(old_val, old_val + 1)) {
14
        // compare_exchange_weak 失败时 old_val 自动更新为当前值
15
        // weak 版本允许虚假失败（在循环中用更高效）
16
    }
17
}

1
// 基于 Test-And-Set 的自旋锁
2
class SpinLock {
3
    std::atomic_flag _flag = ATOMIC_FLAG_INIT;  // 初始化为 false
4
public:
5
    void lock() {
6
        while (_flag.test_and_set(std::memory_order_acquire)) {
7
            // test_and_set: 原子地 { old = _flag; _flag = true; return old; }
8
            // 如果 old == false → 获得锁 → 退出循环
9
            // 如果 old == true  → 锁被占 → 继续旋转（忙等）
10
        }
11
    }
12
    void unlock() {
13
        _flag.clear(std::memory_order_release);
14
    }
15
};

1
#include <semaphore>
2
#include <mutex>
3
#include <array>
4

5
constexpr int BUFFER_SIZE = 8;
6

7
std::array<int, BUFFER_SIZE> buffer;
8
int in_idx = 0, out_idx = 0;
9

10
std::counting_semaphore<BUFFER_SIZE> empty_slots(BUFFER_SIZE);  // 空位数
11
std::counting_semaphore<BUFFER_SIZE> filled_slots(0);           // 已填数
12
std::mutex buffer_mutex;  // 保护 buffer 和下标
13

14
void producer(int item) {
15
    empty_slots.acquire();              // 等待空位 (P)
16
    {
17
        std::lock_guard lock(buffer_mutex);
18
        buffer[in_idx] = item;
19
        in_idx = (in_idx + 1) % BUFFER_SIZE;
20
    }
21
    filled_slots.release();             // 增加已填数 (V)
22
}
23

24
int consumer() {
25
    filled_slots.acquire();             // 等待数据 (P)
26
    int item;
27
    {
28
        std::lock_guard lock(buffer_mutex);
29
        item = buffer[out_idx];
30
        out_idx = (out_idx + 1) % BUFFER_SIZE;
31
    }
32
    empty_slots.release();              // 增加空位 (V)
33
    return item;
34
}

1
// ❌ 可能死锁：两个线程以不同顺序加锁
2
void thread1() { lock(m1); lock(m2); /* ... */ }
3
void thread2() { lock(m2); lock(m1); /* ... */ }  // 顺序相反！
4

5
// ✅ 方案 1：固定加锁顺序
6
void thread1() { lock(m1); lock(m2); /* ... */ }
7
void thread2() { lock(m1); lock(m2); /* ... */ }  // 相同顺序
8

9
// ✅ 方案 2：std::scoped_lock（C++17，自动处理顺序）
10
void safe_transfer(Account& a, Account& b, int amount) {
11
    std::scoped_lock lock(a.mutex, b.mutex);  // 内部用 std::lock 避免死锁
12
    a.balance -= amount;
13
    b.balance += amount;
14
}
15

16
// ✅ 方案 3：try_lock + 重试
17
void try_approach() {
18
    while (true) {
19
        m1.lock();
20
        if (m2.try_lock()) {  // 尝试获取，不阻塞
21
            break;  // 两把锁都拿到了
22
        }
23
        m1.unlock();  // 拿不到 m2 就释放 m1
24
        std::this_thread::yield();  // 让出 CPU，避免活锁
25
    }
26
    // 临界区...
27
    m2.unlock();
28
    m1.unlock();
29
}

1
银行家算法 (Banker's Algorithm)：
2

3
思想：在分配资源前，先模拟分配，看是否存在一条「安全序列」，
4
     即每个进程都能获得足够资源完成并释放。如果存在，就分配；否则等待。
5

6
例子：
7
系统有 10 个单位的资源 R
8
进程 A：最大需要 8，已分配 3，还需 5
9
进程 B：最大需要 5，已分配 2，还需 3
10
进程 C：最大需要 3，已分配 2，还需 1
11
当前剩余 = 10 - 3 - 2 - 2 = 3
12

13
安全序列：C(需 1,释放后 4) → B(需 3,释放后 7) → A(需 5,释放后 10) ✅
14

15
实际应用：主要在数据库中使用。游戏引擎中开销太大，不实用——
16
但面试会考银行家算法的思想和过程。

1
游戏引擎的线程通信场景：
2
- 主线程 → 渲染线程：渲染命令队列 (每帧几千条)
3
- 网络线程 → 主线程：网络消息队列 (收包)
4
- 主线程 → 音频线程：音频事件队列
5

6
这些队列的特点：
7
1. 高频：每帧都在读写
8
2. 低延迟要求：队列操作必须极快
9
3. 大多是 SPSC（单生产者-单消费者）
10

11
用 mutex 保护队列的问题：
12
❌ 优先级反转：渲染线程持锁 → 逻辑线程等锁 → 帧延迟
13
❌ 最坏情况不可预测：持锁线程被调度走 → 其他线程全部阻塞
14
❌ 锁竞争在高频场景下成为瓶颈
15

16
无锁队列的优势：
17
✅ 无阻塞：push/pop 永远不会挂起线程
18
✅ 最坏情况可预测：每次操作都是有限步骤
19
✅ 没有优先级反转风险