对应路线图：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 次数）。
评论 (0)