从零写 OS 内核-第十七篇：调度器 —— 让多任务真正“并发”起来！

从零写 OS 内核-第十七篇：调度器 —— 让多任务真正"并发"起来！

"协作式多任务依赖程序主动让出 CPU，一旦死循环，系统就卡死。
今天，我们引入时钟中断，实现抢占式调度器，让多任务真正公平运行！"

在第六篇中，我们实现了协作式多任务，进程通过 yield() 主动切换。
但这有个致命缺陷：一个死循环的用户程序会让整个系统无响应！

真正的操作系统必须能强制剥夺 CPU，在多个任务间公平分配时间——
这就是 抢占式调度（Preemptive Scheduling）。

今天，我们就来：
✅ 启用时钟中断（PIT）
✅ 实现时间片轮转（Round-Robin）调度器
✅ 支持进程优先级与睡眠队列

让你的 OS 拥有真正的并发能力！

⏱️ 一、为什么需要抢占式调度？

协作式调度的痛点：

抢占式调度的优势：

公平性：每个进程获得固定时间片（如 10ms）
响应性：即使有死循环，系统仍可响应
可控性：通过优先级控制任务执行顺序

💡 调度器是操作系统的"交通警察"，决定谁在何时使用 CPU。

🕰️ 二、时钟中断：调度器的心跳

x86 PC 通过 PIT（Programmable Interval Timer） 产生周期性中断。

PIT 初始化：

#define PIT_CHANNEL0 0x40
#define PIT_COMMAND  0x43
#define PIT_HZ       100  // 100 Hz = 每 10ms 一次中断

void pit_init() {
    // 设置 PIT 频率：1193180 / freq
    uint32_t divisor = 1193180 / PIT_HZ;
    outb(PIT_COMMAND, 0x36); // Channel 0, LSB/MSB, mode 3, binary
    outb(PIT_CHANNEL0, divisor & 0xFF);
    outb(PIT_CHANNEL0, (divisor >> 8) & 0xFF);
}
  

注册时钟中断处理程序：

// IDT 中注册 IRQ0（PIT 中断向量 = 32）
idt_set_gate(32, (uint32_t)timer_handler, 0x08, 0x8E);

void timer_handler() {
    // 1. 发送 EOI 到 PIC
    outb(0x20, 0x20);
    
    // 2. 更新系统时间
    ticks++;
    
    // 3. 触发调度（关键！）
    scheduler_tick();
}
  

🔑 每次时钟中断，都是调度器检查是否需要切换任务的机会！

🔄 三、时间片轮转调度器

1. 进程 PCB 增加调度字段

typedef struct task {
    // ... 其他字段
    int priority;           // 优先级（暂未使用）
    int time_slice;         // 当前剩余时间片
    int default_time_slice; // 默认时间片（如 5）
    struct task *next;      // 运行队列链表
} task_t;
  

2. 调度器核心：scheduler_tick

void scheduler_tick() {
    task_t *current = current_task;
    
    // 1. 减少当前进程时间片
    current->time_slice--;
    
    // 2. 如果时间片用完，标记需要调度
    if (current->time_slice <= 0) {
        need_resched = 1;
    }
}
  

3. 任务切换：schedule

void schedule() {
    if (!need_resched) return;
    
    need_resched = 0;
    
    // 1. 将当前进程放回运行队列尾部
    if (current_task->state == TASK_RUNNING) {
        append_to_run_queue(current_task);
    }
    
    // 2. 从运行队列头部取下一个进程
    task_t *next = get_next_runnable_task();
    if (!next) return; // 没有可运行进程
    
    // 3. 重置时间片
    next->time_slice = next->default_time_slice;
    
    // 4. 切换进程
    switch_to_task(next);
}
  

✅ 时间片用完 → 当前进程排队 → 切换到下一个进程

🛌 四、睡眠与唤醒：支持阻塞操作

进程可能因 I/O（如读键盘）而主动睡眠，此时不应占用 CPU。

1. 睡眠队列

struct sleep_queue {
    struct task *head;
    struct task *tail;
};

// 按事件类型组织睡眠队列（简化：全局一个）
struct sleep_queue global_sleep_queue;
  

2. 睡眠（sleep_on）

void sleep_on(struct sleep_queue *q) {
    // 1. 将当前进程加入睡眠队列
    if (!q->head) {
        q->head = q->tail = current_task;
    } else {
        q->tail->next = current_task;
        q->tail = current_task;
    }
    
    // 2. 标记为睡眠状态
    current_task->state = TASK_SLEEPING;
    
    // 3. 触发调度
    schedule();
}
  

3. 唤醒（wake_up）

void wake_up(struct sleep_queue *q) {
    if (!q->head) return;
    
    // 唤醒所有睡眠进程（简化：实际可唤醒一个）
    struct task *task = q->head;
    while (task) {
        task->state = TASK_RUNNING;
        append_to_run_queue(task);
        task = task->next;
    }
    
    q->head = q->tail = NULL;
}
  

4. 系统调用集成：read 阻塞示例

int sys_read(int fd, void *buf, size_t count) {
    // 如果是 stdin 且无数据
    if (fd == 0 && !uart_has_data()) {
        // 睡眠等待数据
        sleep_on(&uart_sleep_queue);
        // 被唤醒后，继续读取
    }
    // ... 实际读取
}
  

💡 中断处理程序中调用 wake_up（如串口收到数据时）

🧪 五、测试：抢占式多任务

用户程序 1（CPU 密集型）：

void cpu_hog() {
    while (1) {
        // 死循环，不主动 yield
        asm volatile ("nop");
    }
}
  

用户程序 2（I/O 密集型）：

void io_task() {
    char c;
    while (1) {
        read(0, &c, 1); // 阻塞读 stdin
        write(1, &c, 1); // 回显
    }
}
  

运行效果：

即使 cpu_hog 死循环，系统仍能响应键盘输入
两个进程交替运行，各占约 50% CPU

✅ 抢占式调度成功！

📊 六、调度策略扩展

1. 优先级调度

// 在 schedule() 中优先选择高优先级进程
task_t *get_next_runnable_task() {
    task_t *best = NULL;
    for (task_t *t = run_queue; t; t = t->next) {
        if (!best || t->priority > best->priority) {
            best = t;
        }
    }
    return best;
}
  

2. 动态优先级

I/O 密集型进程 → 提升优先级（提高响应性）
CPU 密集型进程 → 降低优先级（避免霸占 CPU）

3. 多级反馈队列（MLFQ）

多个优先级队列
时间片用完 → 降级到低优先级队列
I/O 阻塞后唤醒 → 升级到高优先级队列

💡 Linux 的 CFS（完全公平调度器）是更高级的实现。

⚠️ 七、关键注意事项

中断上下文 vs 进程上下文
- 调度器不能在中断处理程序中直接调用 switch_to_task
- 正确做法：设置 need_resched，在中断返回前检查
临界区保护
- 访问运行队列/睡眠队列时，需关闭中断（cli/sti）
空闲进程（idle task）
- 当无任务可运行时，执行 hlt 指令节省功耗
调度延迟
- 时间片太短 → 调度开销大
- 时间片太长 → 响应性差
- 通常 1~10ms 为宜

💬 写在最后

调度器是操作系统的心脏，
它决定了任务如何共享 CPU 这一稀缺资源。
从协作式到抢占式，
不仅是技术的演进，更是设计理念的跃迁。

今天你实现的 scheduler_tick，
正是 Linux 中 scheduler_tick 和 __schedule 的雏形。

🌟 公平、高效、响应迅速——这是调度器永恒的追求。

📬 动手挑战：
实现一个简单的优先级系统，让 I/O 密集型进程获得更高优先级。
欢迎在评论区分享你的调度策略！

👇 下一篇你想看：多处理器（SMP）支持，还是 进程间通信（管道/Pipe）？

#操作系统 #内核开发 #调度器 #抢占式调度 #时钟中断 #PIT #多任务 #从零开始

📢 彩蛋：关注后回复关键词 "scheduler"，获取：

完整抢占式调度器代码（含 PIT 初始化）

睡眠/唤醒机制实现

时间片轮转与优先级调度对比测试