2. BFS调度器核心思想：O(1)调度、全局运行队列、虚拟截止时间、公平性分析

BFS（Brain Fuck Scheduler）是Con Kolivas为桌面交互场景设计的调度器，其设计哲学与主流CFS完全相反：追求极低调度延迟与交互响应确定性，放弃多核负载均衡的复杂性。本章深入剖析BFS的四大核心支柱。

2.1 O(1)调度：无红黑树的就绪队列

BFS摒弃了CFS的红黑树（O(log n)），采用双链表 + 优先级位图实现O(1)调度。每个优先级（0~139）对应一个链表头，调度时通过位图扫描找到最高优先级非空链表，取出队首任务。

2.2 全局运行队列：单队列模型

BFS使用单一全局运行队列（rq），所有CPU核心共享同一个就绪链表集合。这与CFS每个CPU独立运行队列的设计截然不同。

2.3 虚拟截止时间（Virtual Deadline）

BFS不使用CFS的虚拟运行时间（vruntime），而是引入虚拟截止时间（Virtual Deadline, VD）作为调度决策依据。每个任务被赋予一个VD值，调度器总是选择VD最小的任务执行。

VD计算规则

/* BFS虚拟截止时间计算（简化伪代码） */
void update_deadline(struct task_struct *p) {
    if (p->policy == SCHED_NORMAL || p->policy == SCHED_BATCH) {
        /* 交互任务：vd = 当前时间 + 短时间片 */
        if (p->interactive)
            p->deadline = now + (p->prio_ratio * 6);
        else
            p->deadline = now + (p->prio_ratio * 20);
    }
}

/* 调度决策：选vd最小的任务 */
struct task_struct *pick_next_task(void) {
    struct task_struct *best = NULL;
    u64 min_deadline = ULLONG_MAX;
    
    for_each_task_in_global_queue(p) {
        if (p->deadline < min_deadline) {
            min_deadline = p->deadline;
            best = p;
        }
    }
    return best;
}

2.4 公平性分析：交互优先 vs 时间公平

BFS的公平性定义与CFS完全不同：BFS追求的是“交互公平”而非“时间公平”。即：交互型任务（如GUI应用、音频播放）获得不成比例的CPU时间，以确保用户感知的流畅性。

公平性对比表

2.5 核心思想总结

1. O(1)调度： 双链表+位图，调度延迟与任务数无关，适合桌面负载规模。
2. 全局运行队列： 消除负载均衡开销，但引入全局锁竞争。
3. 虚拟截止时间： 以VD最小为选择依据，交互任务VD增长慢，获得更多CPU机会。
4. 交互优先公平： 牺牲CPU密集型任务的吞吐量，换取交互响应确定性。