5.13 请求队列与事件循环——协作式非阻塞调度
你只有一个管理员，但有两百个操作要处理
你没有多线程。你没有一个pthread_create。没有FreeRTOS的xTaskCreate。你只有一个main函数里的while循环。
但你需要同时处理：用户在命令行敲下write命令、Flash模拟器在跑读写延迟、compact流程在异步擦写SB、log缓冲区在等待被flush……这些“同时发生“的事情，怎么在一个O(n)的单线程循环里搞定？
答案是事件循环（event loop）。KnotFS的knotfs_run()就是一个微型的调度器——每次被调用时，它推进一小步：让Flash模拟器走一个tick、检查compact是否完成、从请求队列pop一个请求、推进当前请求的状态机一步。全部非阻塞，全部协作式。
knotfs_run() 的"心跳脉搏"：
┌─────────────────────────────────────────────────┐
│ 1. fdev_tick() ← 推进Flash模拟器1步 │
│ 2. 检查compact完成 ← 擦写SB的异步等待 │
│ 3. 如果Flash忙，return ← 等设备空闲 │
│ 4. 当前请求完成？出队下一个 ← 队列调度 │
│ 5. 推进当前请求的状态机 → 1步 │
│ 6. return true/false ← 还有事做吗？ │
└─────────────────────────────────────────────────┘
请求队列：最多4个等待者
KnotFS用一个固定大小的环形缓冲区（circular buffer）实现请求队列：
/* knotfs.c: 全局队列 */
#define Q_CAPACITY (4U)
static kreq_t q[Q_CAPACITY];
static int q_hd, q_tl, q_cnt;
队列容量只有4——这是故意的小容量。因为KnotFS的设计假设是“请求生产和消费的速度大致匹配“，没有积压大量请求的场景。如果队列满了（q_cnt >= Q_CAPACITY），q_push返回-1，调用者需要稍后重试。
static bool q_empty(void) { return q_cnt == 0; }
static bool q_full(void) { return (uint32_t)q_cnt >= Q_CAPACITY; }
static int q_push(kreq_t *r) {
if (q_full())
return ERR_Q_FULL;
memcpy(&q[q_tl], r, sizeof(kreq_t));
q_tl = (q_tl + 1) % Q_CAPACITY;
q_cnt++;
return 0;
}
static void q_pop(kreq_t *r) {
if (q_empty()) {
memset(r, 0, sizeof(*r));
return;
}
memcpy(r, &q[q_hd], sizeof(kreq_t));
q_hd = (q_hd + 1) % Q_CAPACITY;
q_cnt--;
}
入队时写到q_tl，然后q_tl = (q_tl + 1) % Q_CAPACITY。出队时从q_hd取，然后q_hd = (q_hd + 1) % Q_CAPACITY。这是最基础的环形队列操作，时间复杂度O(1)，不需要malloc。
但你可能会发现一个问题：q_cnt是全局的，但没有任何锁保护。在KnotFS里这不是问题——因为在事件循环模型中，所有的操作都发生在同一个调用栈里。用户调用knotfs_write来入队，这时事件循环不在运行。然后用户调用while(knotfs_run())来消费队列，这时不会有其他线程在入队。单线程协作式调度的好处就在这里：你不需要锁。
kreq_t：一个请求就是一张任务单
typedef struct {
knot_op_t op;
knot_st_t st;
int result;
char name[KNOTFS_NAME_LEN];
const void *w_buf;
uint32_t w_sz;
void *r_buf;
uint32_t r_sz;
uint32_t r_off;
uint32_t *r_out;
const void *a_buf;
uint32_t a_sz;
knotfs_entry_t *ls_ents;
uint32_t *ls_cnt;
uint32_t *st_tot;
uint32_t *st_free;
} kreq_t;
这个结构体用了一个不太优雅的设计——所有操作的参数共用一个union-less struct。写操作使用w_buf/w_sz，读操作使用r_buf/r_sz/r_off/r_out，追加操作使用a_buf/a_sz，列表操作使用ls_ents/ls_cnt，统计操作使用st_tot/st_free。在任何一个时刻，只有一种操作在运行，所以这些字段不会冲突。
这在嵌入式编程中是常见模式——节省内存的代价是类型安全。更规范的做法是用union加tag，但union在MISRA C里需要小心处理，有些编码规范禁止在union中混用指针和非指针类型。KnotFS选择了简单。
/* 以 knotfs_write 为例看入队过程 */
int knotfs_write(const char *name, const void *buf, uint32_t size) {
if (!name || !buf || !size || size > KNOTFS_FILE_LIMIT)
return ERR_BAD_PARAM;
if (!q_empty() || cur.op != OP_NONE)
return ERR_Q_FULL;
kreq_t r;
memset(&r, 0, sizeof(r));
r.op = OP_WRT;
r.st = ST_WRT_INIT;
strncpy(r.name, name, KNOTFS_NAME_LEN - 1);
r.w_buf = buf;
r.w_sz = size;
return q_push(&r);
}
注意if (!q_empty() || cur.op != OP_NONE) return -1——如果你在请求被处理完之前尝试提交新请求，它直接拒绝。KnotFS不支持请求堆积。调用者负责等待文件系统空闲（knotfs_is_idle()）后再提交新请求。
事件循环：knotfs_run() 的完整走读
bool knotfs_run(void) {
fdev_tick();
/* handle compact completion */
if (comp_wait && fdev_idle()) {
comp_wait = false;
}
if (!fdev_idle())
return true;
/* if current request done, dequeue next */
if (cur.op != OP_NONE && (cur.st == ST_OK || cur.st == ST_ERR)) {
if (!q_empty())
q_pop(&cur);
else
cur.op = OP_NONE;
}
/* dequeue if idle */
if (cur.op == OP_NONE && !q_empty()) {
q_pop(&cur);
prog = 0;
subst = 0;
memset(scratch, 0, sizeof(scratch));
}
/* advance state machine */
if (cur.op != OP_NONE && cur.st != ST_OK && cur.st != ST_ERR) {
switch (cur.op) {
case OP_FMT: do_format(); break;
case OP_MNT: do_mount(); break;
case OP_WRT: do_write(); break;
case OP_RD: do_read(); break;
case OP_APP: do_append(); break;
case OP_DEL: do_delete(); break;
case OP_LS: do_list(); break;
case OP_ST: do_stats(); break;
default: break;
}
}
return !knotfs_is_idle();
}
让我们逐段拆解：
第1步：fdev_tick() —— Flash模拟器的时钟推进。每个tick递减fdev.ticks_left，当降到0时，真正执行memcpy（读/写）或memset（擦除）。这是事件循环的物理层。
第2步：compact完成检测 —— comp_wait && fdev_idle()。如果compact正在进行（comp_wait=true）且Flash设备空闲（说明擦除/写入操作已经完成），就清除comp_wait标志。compact的finish操作是在状态机中完成的（ST_WRT_COMPACT/ST_APP_COMPACT/ST_DEL_COMPACT），事件循环只负责检测异步I/O的完成。
第3步：设备忙时提前返回 —— if (!fdev_idle()) return true。如果Flash正在做读写操作，整个状态机都不推进——因为状态机里的每一步都依赖Flash操作完成后的结果。这是事件循环中最关键的阻塞点。
第4步：当前请求完成，出队下一个 —— 如果cur的state是ST_OK或ST_ERR，说明当前请求已经处理完毕。从队列中pop下一个请求。如果没有新请求，cur.op = OP_NONE。
第5步：空闲时主动出队 —— 如果没有任何请求在处理（cur.op == OP_NONE）且队列不空，pop一个请求开始处理。同时重置prog、subst和scratch[]。
第6步：推进状态机 —— 核心调度。根据cur.op的值，dispatch到对应的do_xxx()函数。每个do_xxx()函数执行一小步（一个case分支），然后return。下一次knotfs_run()时会再次进入这个switch，处理同一个op的下一个状态。
第7步：return !knotfs_is_idle() —— 如果还有事情做（有请求在处理或Flash在忙），返回true；否则返回false。调用者用这个返回值做轮询：while(knotfs_run());。
串行化的力量与代价
KnotFS的设计保证了：同一时间，只有一个请求在执行。 这不是多线程的互斥保护，而是更根本的——事件循环本身就不允许并发。
这意味着什么？
串行化的好处：
✓ 不需要互斥锁(mutex) —— 没有竞争条件
✓ 不需要原子操作 —— 所有共享变量访问都是安全的
✓ 不需要考虑死锁(deadlock) —— 只有一个执行流
✓ 状态机的中间状态是私有的 —— 不存在"另一个线程读到半完成状态"
✓ 可预测性 —— 你知道每一步在做什么
串行化的代价：
✗ 没有真正的I/O并发 —— 读取不能和写入并行
✗ 请求延迟是累积的 —— 如果队列里有3个请求，第3个要等前2个完成
✗ 无法利用多核 —— CPU利用率低
✗ 长时间操作阻塞整个系统 —— 比如format要擦除16个块，必须全部等你
对于KnotFS的教学场景和嵌入式NOR Flash的实际情况来说，串行化是完全可接受的。Flash设备本身就不是多通道并行的——一次只能做一个操作（读或写或擦除）。真正的并发发生在另一层：网络任务（终端的TCP服务）、Flash I/O任务、文件系统状态机任务——这三者可以运行在不同的FreeRTOS任务上。但那是生产级方案要处理的问题。
调度的时间线：一次完整的“write + read“
让我们把调度过程的tick拆开来看：
tick 0: 用户调用 knotfs_write("hello.txt", "Hello!", 6)
→ q_push, 队列中有1个请求
→ knotfs_write 返回 0
tick 1: knotfs_run()
→ fdev_tick() (空闲)
→ cur.op == OP_NONE, q_pop(&cur) — cur现在是 OP_WRT, ST_WRT_INIT
→ 推进状态机: do_write() → ST_WRT_INIT
→ alloc_node, 计算need=1, scratch[9]=1
→ cur.st = ST_WRT_ALLOC, return
tick 2: knotfs_run()
→ fdev_tick() (空闲)
→ cur.st != ST_OK/ST_ERR, 推进状态机: ST_WRT_ALLOC
→ pick_lowest_wear() → 块2, mark_used
→ subst++=1, cur.st = ST_WRT_DATA (subst>=need), return
tick 3: knotfs_run()
→ fdev_tick() (空闲)
→ 推进状态机: ST_WRT_DATA
→ fdev_write(块2, tmp, 0, 4096) — ticks_left=2
→ subst++=2, return
tick 4: knotfs_run()
→ fdev_tick() — ticks_left=2→1, 设备忙
→ !fdev_idle(), return true
tick 5: knotfs_run()
→ fdev_tick() — ticks_left=1→0, memcpy完成
→ fdev_idle()
→ cur.st=ST_WRT_DATA, 推进: subst(2)>=need(1) → cur.st=ST_WRT_META, return
→ cur.st是ST_WRT_META不是OK/ERR, 不换请求
tick 6: knotfs_run()
→ fdev_tick() (空闲)
→ 推进状态机: ST_WRT_META
→ log_push, compact_erase, comp_wait=true
→ cur.st = ST_WRT_META_FLUSH, return
tick 7~9: compact erase (3 ticks异步等待)
tick 10: knotfs_run()
→ fdev_idle, comp_wait=false
→ 推进状态机: ST_WRT_META_FLUSH
→ compact_write, cur.st = ST_WRT_COMPACT
tick 11~12: compact write (2 ticks)
tick 13: knotfs_run()
→ fdev_idle
→ 推进状态机: ST_WRT_COMPACT
→ compact_finish, log_commit, cur.st = ST_OK
tick 14: knotfs_run()
→ cur.st == ST_OK, q_pop → 队空, cur.op = OP_NONE
→ knotfs_is_idle() == true → return false
13个tick，完成一个6字节的写操作。物理上Flash只需要大约1微秒来做写入——但这里的13个tick是状态机调度引入的延迟。在真实硬件上，Flash的擦除（50ms）和写入（100μs）比状态机调度慢得多，所以状态机开销可以忽略不计。
队列满时的拒绝策略：让调用者重试
if (!q_empty() || cur.op != OP_NONE)
return ERR_Q_FULL;
KnotFS的API在队列忙时直接返回-1。没有阻塞等待、没有自旋锁、没有信号量。 这是因为KnotFS API的设计目标是从FreeRTOS的同步包装层调用——调用者所在的线程可以vTaskDelay(10)然后重试。
在knotfs_test.c中，测试代码不需要重试——因为每次测试调用API后都会立即调用drive()（即while(knotfs_run())），在下一个API调用之前队列已经空了：
static int drive(void) {
int t = 0;
while (knotfs_run()) {
if (++t % 15 == 0)
printf(" tick %d...\n", t);
}
if (t > 0 && t % 15 != 0)
printf(" tick %d... done\n", t);
return knotfs_get_result();
}
drive()是测试程序的同步阻塞包装——一个用轮询实现的“wait until idle“。在生产级部署中，这个轮询会被替换为FreeRTOS的xTaskNotifyWait——任务在没有事件时挂起，事件发生时被唤醒。
⚠️ 教学简化提示：这里KnotFS的请求队列有容量4但没有超时检测。生产级方案的请求队列有超时检测机制——每种操作有独立的超时时间，超时后请求被标记为失败，任务被通知。
如果你来设计
试着回答：如果把KnotFS搬到一个“每次只能做一件事“的真实NOR Flash上，事件循环需要改什么？
答案：只需要换掉fdev_tick()的实现。把RAM模拟器换成真实的Flash HAL调用——比如callback_on_complete模式。事件循环的结构不需要任何改变——它已经假设“Flash是异步的、每次只能做一件事“。
具体来说：fdev_tick()不再递减ticks_left，而是检查硬件状态寄存器（SR）看操作是否完成。fdev_read/write/erase不再设置ticks_left，而是向Flash控制寄存器写入命令并启动操作。事件循环的if (!fdev_idle()) return true等价于“等Flash操作完成再推进状态机“。
这就是KnotFS教学设计的核心价值——事件循环和硬件抽象层是完全解耦的。
下集预告
写了这么多代码，讲了这么多原理，你怎么知道它真的能跑？你怎么知道CoW断电恢复真的有效？你怎么知道CRC校验真的能发现问题？KnotFS附带了一套12个测试用例的自测试程序——format、write、read、append、delete、power-loss recovery……每一步都有代码。下一节，也是本章的最后一节，我们把所有状态机串起来跑一遍，看12个测试用例如何验证我们前面讲过的每一个设计决策。 ./knotfs_test，~474 行测试代码，18 个测试点——全过，是对你这一章所有思考的最好的回答。