P0-04 · 无锁编程入门：从 CAS 到 MPSC 队列 对应路线图：Phase 0 (Day 1-21) ｜ 内核 v6.6 ｜ 上一篇：P0-03 PCIe ｜ 下一篇：P0-05 perf一句话定位无锁编程 = CAS 抢位置 + 内存屏障保证可见性。多生产者竞争时，CAS 保证只有一个线程抢到 slot；抢到之后数据怎么"安全地"被消费者看到，靠的是 release/acquire 语义。这套范式放大 100 倍，就是 DPDK rte_ring。真实源码精读：有锁 vs 无锁先看实验室的定量对比（source/dpdk-labs/04-lockfree/lockfree_demo.c）：void *locked_worker(void *arg) { (void)arg; for (int i = 0; i < ITERATIONS; i++) { pthread_mutex_lock(&lock); locked_counter++; pthread_mutex_unlock(&lock); } return NULL; } // lockfree_demo.c:19-28 void *lockfree_worker(void *arg) { for (int i = 0; i < ITERATIONS; i++) { uint64_t old, new_val; do { old = atomic_load(&atomic_counter); new_val = old + 1; } while (!atomic_compare_exchange_weak(&atomic_counter, &old, new_val)); } return NULL; } // lockfree_demo.c:33-44CAS 循环是 lockfree_demo.c:41 那一行：compare_exchange_weak 失败时会把最新的值写回 old，循环自然重试。这里有个关键认知（README 04-lockfree:76-77）：低竞争下无锁更快，高竞争下 CAS 疯狂重试可能反而不如锁——所以 DPDK 热路径的终极答案永远是"每核私有数据结构"，无锁只是兜底。MPSC 队列：我的 Day 4 编码题code/Phase0/mpsc-queue/mpsc_queue.c 是路线图规划的编码题模板——结构体和算法注释已给全，mpsc_queue_create/mpsc_enqueue/mpsc_dequeue 三个函数是 TODO（mpsc_queue.c:54-57, 81-84, 114-117），要自己填。先把模板里"已经替你设计好"的部分读透：typedef struct { // ===== producer 写的区域 (cache line 0) ===== alignas(CACHE_LINE) _Atomic uint32_t head; // 所有 producer CAS 抢这个 char _pad1[CACHE_LINE - sizeof(_Atomic uint32_t)]; // ===== consumer 读写的区域 (cache line 1) ===== alignas(CACHE_LINE) _Atomic uint32_t tail; // consumer 更新, producer 只读 char _pad2[CACHE_LINE - sizeof(_Atomic uint32_t)]; // ===== 共享数据 ===== uint32_t mask; // size - 1, 用于取模 void *ring[]; // FAM (Flexible Array Member): 环形数组 } mpsc_queue_t; // mpsc_queue.c:30-42head/tail 分居两个 cache line——这正是 P0-01 false sharing 的工程应用。enqueue 的算法注释是整道题的核心（mpsc_queue.c:60-80）： * 1. atomic_load head (acquire) → 拿到当前队尾位置 * 2. atomic_load tail (acquire) → 看队列满没满 * 3. if (head - tail == size) → 队列满，返回 false * 4. new_head = head + 1 * 5. CAS(&q->head, head, new_head) → 抢 slot * - 成功: 跳出循环 * - 失败: head 被更新为当前最新值 → 回第 1 步重试 * 6. ring[head & mask] = data → 写入数据 (此时只有我能写这个位置!)注释里的自问自答值得抄进笔记（mpsc_queue.c:75-80）：数据写入必须在 CAS 之后——先 CAS 抢 slot 保证自己是唯一写 ring[head] 的人，再写数据就无竞争；"CAS 的 release 语义保证 consumer 看到 head 更新时数据已就绪"。dequeue 的方案 B 简化实现也有讲究（mpsc_queue.c:107-112）：consumer 发现 ring[tail & mask] == NULL 说明 producer 抢到了 head 但还没写完，返回空即可，不需要锁也不需要等待。测试验收标准是硬性的：2 个 producer 各入队 100 万，consumed == 2000000 才算 PASS（mpsc_queue.c:134-135, 193-196）。🐧 内核对照：RCU 是另一种"免锁"内核最著名的免锁机制是 RCU。include/linux/rculist.h：static inline void __list_add_rcu(struct list_head *new, struct list_head *prev, struct list_head *next) // rculist.h:76 { if (!__list_add_valid(new, prev, next)) return; new->next = next; new->prev = prev; rcu_assign_pointer(list_next_rcu(prev), new); // rculist.h:84 next->prev = new; } static inline void list_add_tail_rcu(struct list_head *new, struct list_head *head) // rculist.h:125 { __list_add_rcu(new, head->prev, head); }先把自己的前后指针接好，最后用 rcu_assign_pointer（含 release 屏障）发布——读者任何时刻看到的都是完整节点。写者延迟回收：void call_rcu(struct rcu_head *head, rcu_callback_t func)（kernel/rcu/tree.c:2835）注册回调，等所有读者度过宽限期后再释放。队列无锁是"生产者-消费者互不阻塞"，RCU 无锁是"发布-订阅、读者零开销"——面试能讲出这个区别是加分项。实验怎么跑cd source/dpdk-labs/04-lockfree gcc -O2 -o lockfree_demo lockfree_demo.c -lpthread ./lockfree_demo # 对比 [locked] 与 [lockfree] 的 cycles/op cd ../../code/Phase0/mpsc-queue gcc -std=c11 -pthread -O2 -Wall -Wextra -o mpsc_test mpsc_queue.c ./mpsc_test # 验收：consumed == 2000000 且 PASS变化 N_THREADS（lockfree_demo.c:13）观察竞争强度与两方案胜负关系，验证"低竞争无锁赢、高竞争锁赢"的边界（README 04-lockfree:73-77）。面试 3 问MPSC 入队为什么先 CAS 后写数据？ → 先 CAS 抢 slot 保证唯一写者，后写数据无竞争；且 CAS 的 release 语义让数据先于 head 发布可见（mpsc_queue.c:75-80 注释原文）。MPSC 和 SPSC 的实现差异在哪？ → SPSC 的 head 只有一个人写，普通 store 即可；MPSC 必须 CAS（对比 lockfree_demo.c:22-25 的 mutex 版与 :38-41 的 CAS 循环）。DPDK ring 用 RING_F_SP_ENQ 标志区分（README 04-lockfree:84）。无锁队列与 RCU 的区别？ → 队列免锁解决生产消费互斥，读者拿不到就返回；RCU 是发布-订阅，rcu_assign_pointer 发布（rculist.h:84）、call_rcu 延迟回收（tree.c:2835），读者永远无锁无阻塞。数据落点perf-data/P0/04-lockfree/：lockfree_demo.txt（锁 vs CAS 矩阵）、mpsc_test.txt（PASS 记录 + spins 次数）。