第11章：锁实现与动态存储

---

元数据卡

属性	值
难度等级	(核心)
前置章节	Ch9 并发原语、Ch10 内存模型
后置章节	Ch12 死锁
核心语言	C
差异窗口	Java (java.util.concurrent.locks) / Python (threading.Lock)
内存占用	约28KB（含代码）

---

你在哪

"你注意到地心里有几种更基础的机制在运转——锁的实现和动态内存分配。前者是线程安全的基础，后者是每个 malloc/free 调用背后发生的事。"

你站在一个十字路口。

左边是 CPU 流水线，指令还在乱序执行。右边是进程调度器，随时可能把你踢出核心。脚下是虚拟内存的海面——你刚在第10章学会了内存屏障，但那只是告诉 CPU "别乱序"。现在你需要的，是两样更根本的东西：

1. 让多个线程别同时踩进临界区——锁。
2. 让对象在堆上活着又死得干净——动态存储。

这两件事表面无关，但底层共享一个问题：谁控制资源，怎样控制，代价多少。

---

你的任务

本章分层

• 必读（锁的实现）：从朴素自旋锁到 TAS/CAS 原子操作；mutex 的“快速路径优先”原则
• 必读（内存管理）：free list 分配思路与碎片问题
• 深水区：futex 的两阶段设计；Arena / tcache / SLAB 等 malloc 优化策略 本章不会要求你掌握
• futex 系统调用的完整接口
• jemalloc / tcmalloc 的 arena 分配策略细节
• RCU（Read-Copy-Update）锁

• 实现一个自旋锁（从朴素 TAS 到正确 CAS）
• 理解 futex 如何把自旋变休眠
• 区分读写锁、乐观锁、悲观锁的适用场景
• 动手拆 malloc 的底层思路
• 看清堆 vs 栈、内存池、碎片的血泪史

---

遭遇战 1：自旋锁——最朴素的野蛮

场景：两个线程争一个 int。线程 A 想设为 1，线程 B 也想设。谁先设，谁进临界区。

第一版，直觉写：

// naive_spinlock.c — 看看这段代码哪错了？
volatile int lock = 0;

void acquire() {
    while (lock == 1) { }  // 死等
    lock = 1;
}
void release() {
    lock = 0;
}

爆了。两个线程同时读到 lock == 0，同时闯进去。

第二版，硬件原子操作：TAS

// tas_spinlock.c — 使用 x86 XCHG 指令
void acquire(volatile int *lock) {
    while (__sync_lock_test_and_set(lock, 1) == 1) {
        // 自旋等待
    }
}
void release(volatile int *lock) {
    __sync_lock_release(lock);
}

__sync_lock_test_and_set —— GCC 内置，对应 x86 的 xchg 指令，保证原子化读写。但有个隐形成本：写操作会让其他核心的 cache line 失效（"缓存乒乓"），每次自旋都广播总线信号。

第三版：CAS + PAUSE

// cas_spinlock.c — 读多写少，减少缓存一致性风暴
void acquire(volatile int *lock) {
    while (1) {
        // 先读（共享状态，不写 cache line）
        if (*lock == 0 &&
            __sync_val_compare_and_swap(lock, 0, 1) == 0) {
            break;
        }
        // PAUSE 指令：暗示处理器这是自旋循环
        __builtin_ia32_pause();
    }
}

获得技能：CAS（Compare-And-Swap） 读不写 cache line，只在确认能拿到锁时才触发写（MESI 协议从 S→M）。 __sync_val_compare_and_swap(ptr, expected, new)：如果 *ptr == expected，则写入 new，返回旧值。原子。

🐍 Python 版：

# threading.Lock 内部就是 pyatomic.h 实现的 CAS
# 但 Python 的 GIL 让多线程锁竞争远没 C 剧烈
# 需要真并行 -> multiprocessing.Lock 走 OS 信号量

---

深水区：futex 是 Linux 特有的、高性能锁的实现细节。绝大多数应用开发者不需要理解 futex——pthread_mutex 已经封装好了。

遭遇战 2：futex——别再浪费 CPU 了

自旋锁的问题是：持有锁的时间 > 上下文切换开销时，自旋就是废物。你需要——把线程挂起。

futex（Fast Userspace Mutex） 是 Linux 的答案：

// futex_mutex.c — 我简化了，但骨架在这里
#include <linux/futex.h>
#include <sys/syscall.h>
#include <unistd.h>

typedef struct {
    atomic_int state;  // 0=unlocked, 1=locked, 2=contended
} futex_mutex_t;

void futex_lock(futex_mutex_t *m) {
    int expected = 0;
    // 尝试快速路径：CAS，期望无竞争
    if (atomic_compare_exchange_strong(&m->state, &expected, 1)) {
        return;  // 拿到锁，0 次系统调用
    }
    // 慢路径：有人持有，标记竞争并进内核睡眠
    if (atomic_exchange(&m->state, 2) != 2) {
        // 做一次 sys_futex(FUTEX_WAIT)
        syscall(SYS_futex, &m->state, FUTEX_WAIT, 2, NULL, NULL, 0);
    }
}

💡 关键洞察：无竞争时零系统调用 这是 "快速路径优先" 的原则。futex 的名字出卖了一切——大部分操作在用户空间完成，只在真需要时才进内核。

Java 版：

// AbstractQueuedSynchronizer (AQS) —— Java 的 futex 等价物
// ReentrantLock 内部通过 AQS + LockSupport.park() 实现
// 差异：AQS 更复杂（支持可重入/条件变量），但核心思想相同

---

遭遇战 3：读写锁与乐观锁

场景： 一个配置表。99% 的操作是读，1% 是写。自旋锁会无差别地让所有读者互斥——愚蠢。

读写锁：

// rwlock.c — 简单实现：读者计数
typedef struct {
    atomic_int readers;
    atomic_int writer;
} rwlock_t;

void read_lock(rwlock_t *rw) {
    int expected;
    do {
        expected = atomic_load(&rw->readers);
    } while (expected < 0  // 有人写？
        || !atomic_compare_exchange(&rw->readers, &expected, expected + 1));
}

void write_lock(rwlock_t *rw) {
    // 把 readers 设为 -1 标记写锁
    int expected = 0;
    while (!atomic_compare_exchange(&rw->readers, &expected, -1)) {
        expected = 0;
    }
}

乐观锁： 不锁，冲突再说。

// optimistic.c — 版本号控制
typedef struct {
    atomic_int version;
    char data[64];
} optimistic_t;

void *read_begin(optimistic_t *obj) {
    int v1 = atomic_load(&obj->version);
    if (v1 & 1) return NULL;    // 正在写，失败
    atomic_thread_fence(memory_order_acquire);
    // — 读 data —
    int v2 = atomic_load(&obj->version);
    if (v1 != v2) return NULL;  // 版本变了，重试
    return obj->data;
}

获得技能：乐观 vs 悲观

• 悲观锁：你一定会搞破坏，进临界区前就锁。
• 乐观锁：你大概率不搞破坏，先做事，冲突再回滚。
• 适用法则：冲突率高 → 悲观；冲突率低 → 乐观。选错了，性能倒挂。

---

---

💡 本章内容提示：本章其实包含两个独立话题——"锁是怎么实现的"和"malloc 是怎么管理内存的"。它们底层共享同一组问题，但理解其中一个不需要先理解另一个。下面先讲锁实现，再讲内存管理。

常见陷阱（第一部分）：锁的实现

如标题所述，这部分深入"锁到底是怎么工作的"。如果你只想知道怎么用锁而不是怎么造锁，可以跳过这部分直接进入第二部分"malloc"。

---

常见陷阱（第二部分）：malloc——内存的"批发与零售"

现在，你从锁的世界游荡到了堆的世界。底层的问题是同一个：多个分配者怎么不打架？

朴素 malloc 思路

// 极度简化的 free list malloc — 了解思路，不是生产就绪
typedef struct block {
    size_t size;
    struct block *next;
    int free;
    char data[0];  // flexible array member
} block_t;

static block_t *free_list = NULL;
static pthread_mutex_t heap_lock = PTHREAD_MUTEX_INITIALIZER;

void *my_malloc(size_t size) {
    pthread_mutex_lock(&heap_lock);

    block_t *prev = NULL, *curr = free_list;
    while (curr) {
        if (curr->free && curr->size >= size) {
            // 分割：如果剩余空间够大，分裂
            if (curr->size > size + sizeof(block_t) + 8) {
                block_t *new_block = (block_t *)((char*)curr + sizeof(block_t) + size);
                new_block->size = curr->size - size - sizeof(block_t);
                new_block->free = 1;
                new_block->next = curr->next;
                curr->size = size;
                curr->next = new_block;
            }
            curr->free = 0;
            pthread_mutex_unlock(&heap_lock);
            return curr->data;
        }
        prev = curr;
        curr = curr->next;
    }

    // free list 不够 -> sbrk 或 mmap 向 OS 申请
    void *ptr = sbrk(size + sizeof(block_t));
    // ... 初始化 block header ...
    pthread_mutex_unlock(&heap_lock);
    return ((block_t*)ptr)->data;
}

你看到了什么？一个全局锁保护整个堆。这在单核时代没问题，多核时代——锁竞争能把吞吐打成个位数。

实战 malloc 是怎么做的

策略	描述
Arena	每个 CPU 核心有独立内存池，减少锁争用（glibc main_arena → arena_get）
tcache	per-thread cache，无锁分配热点对象（glibc 2.26+）
SLAB	Linux 内核做法：按对象大小分区，每个 slab 只放一种大小
伙伴系统	2 的幂分割合并，碎片少，分配快但不灵活

获得技能：内部碎片 vs 外部碎片

• 外部碎片：有空闲内存，但每个碎片太小，连续分配失败。free list 的癌。
• 内部碎片：你申请 17 字节，分配器给你 32 字节块（对齐/元数据）。浪费的那 15 字节就是内部碎片。
• 取舍：外部碎片杀性能（分配失败后触发的 compaction 或者更大范围的 defrag，可能遍历整个堆）；内部碎片杀利用率（程序 Rss 比实际使用的数据量大很多）。选哪个都是 trade-off。

这不是一个能优化到零的问题。分配器的作用是让碎片不要大到影响可用性。就像城市管理——你不能消除垃圾，只能让垃圾不要堵住马路。

---

通关挑战

1. 手写一个公平的自旋锁——用 ticket lock 思路（每个线程拿号排队）。
2. 读写锁降级：写着能不能在完成写后自动降级为读者？怎么保证安全？
3. 用 mmap + 自定义 free list 实现一个 128KB 的固定大小内存池。不调用 sbrk，只在初始化时一次 mmap。
4. 实测：写 microbenchmark 对比自旋锁和 pthread_mutex 在持有时间 1us / 100us / 10ms 时的性能拐点。

---

验收标准

检查项	描述
能说清 TAS 和 CAS 的区别	TAS 每次都写（MESI 打邻居），CAS 先读再写
理解 futex 的两阶段设计	用户空间快速路径 + 内核唤醒慢路径
分清读写锁和互斥锁的场景	读多写少用读写锁，否则互斥锁
能画 malloc 的 free list 分割图	画在纸上，arrow 标出 prev 和 next
分清内外碎片	外部=碎片间空洞，内部=对齐/元数据浪费

---

常见卡点

卡点	说明
TAS 自旋为什么慢	每次 xchg 都写，MESI 协议让所有其他核心的 cache line 失效——广播风暴
CAS 自旋不也是 while？	是，但它先读（共享），只在写时触发失效。单次自旋代价低一个数量级
futex 真的比自旋快？	竞争激烈时是。但 1-2 个核自旋可能更快，因为 syscall 有 ~100ns 开销
空闲列表分配一定慢？	小对象频繁分配时碎片化严重（malloc 碎片综合征），tcache 就是为了解决这个
内存池和 malloc 什么关系	内存池是上层抽象。游戏/嵌入式常用：预分配一大块，应用层做分配策略

---

现在不需要理解

• RCU（Read-Copy-Update）：Linux 内核的免读锁机制，比读写锁更激进。适合链表遍历，会在 Ch15 内核之旅展开。
• jemalloc / tcmalloc 的 arena 分配策略细节。读完本章你已掌握核心思想；具体实现是几十个文件的工程博弈。
• NUMA-aware 分配：内存和 CPU 的距离影响性能，这是 Ch17 硬件架构的话题。

---

旅人笔记

锁是让并发变串行的艺术品。一个好的锁不是什么"让你的代码跑得更快"，而是"让你的代码在竞争时还能跑对"。最快的锁是没有争用的锁。

而内存分配的故事，说到底是一个真理：内存不是无限的，碎片也不是免费就能避免的。每一个 malloc 背后都藏着一颗棋——这颗棋决定你的程序在多长时间内不爆炸。

如果你只有一个 64 字节的 cache line，那你写的每一行代码都要敬畏它。

---

→ 下一站预告

第12章——死锁：四骑士的诅咒。

你以为你学会了用锁？那你还没见过四个进程互相掐住对方喉咙不放的样子。死锁条件、银行家算法、哲学家就餐的完美对称性崩溃、lockdep 教你做人。

准备好，下一个比你更聪明的程序员已经掉进坑里了。