调度器可以理解成决定“现在谁运行、谁暂停、谁等待、谁恢复”的管理者。如果没有调度器协程、线程、事件循环都只是一堆零件。调度器负责把它们组织起来。一、最直观的理解假设有三个任务任务 A等网络数据 任务 B处理计算 任务 C等定时器如果 A 暂时没数据继续让 A 占着 CPU 就浪费了。调度器会做A 没数据 - 挂起 A 运行 B C 定时器到了 - 恢复 C A 网络数据到了 - 恢复 A所以调度器的核心职责是让能运行的任务运行 让不能运行的任务等待 当等待条件满足后把任务重新放回可运行队列。二、调度器有很多层“调度器”这个词不只一种。常见有三类类型谁实现调度对象操作系统调度器内核线程 / 进程事件循环调度器程序 / 框架fd 事件、定时器、回调协程调度器程序 / 协程库协程操作系统调度器负责调度线程。epoll事件循环负责调度 I/O 事件。ucontext或 C coroutine 调度器负责调度协程。你前面问的这些东西拼起来通常是epoll 负责发现 I/O 就绪 ucontext 负责保存/恢复协程上下文 调度器负责决定恢复哪个协程三、操作系统线程调度器操作系统调度器是内核的一部分。它调度的是线程或进程。比如有多个线程Thread A Thread B Thread C但是 CPU 核心有限操作系统要决定现在让哪个线程跑 跑多久 什么时候切换 优先级怎么处理这是抢占式调度。也就是说线程自己不主动让出 CPU操作系统也可以强行把它切走。例如Thread A 正在运行 时间片到了 内核暂停 A 恢复 Thread B这个切换对用户代码通常是透明的。四、协程调度器协程调度器通常是用户态实现的。它调度的是协程不是线程。比如Coroutine A Coroutine B Coroutine C它们可能都运行在同一个 OS 线程里。协程调度通常是协作式的协程主动 yield 调度器才切换到其他协程也就是说协程如果不主动让出执行权调度器通常不能强行切走它。比如void taskA() { while (true) { // 如果这里永远不 yield // 其他协程就没机会运行 } }这就是协作式调度的风险某个协程如果写坏了会饿死其他协程。五、调度器最基本的数据结构一个协程调度器通常需要这些东西struct Task { ucontext_t ctx; std::vectorchar stack; bool finished; };以及std::queueTask* ready_queue; Task* current; ucontext_t scheduler_ctx;其中ready_queue可运行队列里面放着可以马上运行的协程。current当前正在运行的协程。scheduler_ctx调度器自己的上下文。协程状态一般有enum class State { Ready, // 可以运行 Running, // 正在运行 WaitingIO, // 等 I/O Sleeping, // 等定时器 Finished // 已结束 };六、 最简单的调度逻辑一个最小调度器可以这样while ready_queue 不为空: 取出一个协程 切换到它 它 yield 或结束后回到调度器伪代码void Scheduler::run() { while (!ready_queue.empty()) { Task* task ready_queue.front(); ready_queue.pop(); current task; task-state State::Running; swapcontext(scheduler_ctx, task-ctx); if (task-finished) { destroy(task); } else if (task-state State::Ready) { ready_queue.push(task); } } }这里的关键是swapcontext(scheduler_ctx, task-ctx);从调度器切到协程。协程里如果调用yield();就会swapcontext(task-ctx, scheduler_ctx);从协程切回调度器。七、yield 在调度器里的作用yield就是协程主动说我先不跑了把执行权交回调度器。例如void yield() { current-state State::Ready; ready_queue.push(current); swapcontext(current-ctx, scheduler_ctx); }这样当前协程会回到队列尾部其他协程有机会运行。执行过程像这样调度器 - A A yield - 调度器 调度器 - B B yield - 调度器 调度器 - C C yield - 调度器 调度器 - A这叫轮转调度round-robin。八、调度器和 epoll 的结合只会yield的调度器还不够强。如果协程要等网络数据不能一直空转while (true) { int n recv(fd, buf, size, 0); if (n 0 errno EAGAIN) { yield(); } }这样虽然不会阻塞线程但会不断被调度起来检查浪费 CPU。更好的做法是如果 fd 没数据 把当前协程挂到 fd 的等待表里 用 epoll 监听这个 fd yield 回调度器 等 epoll 通知 fd 可读 把等待这个 fd 的协程放回 ready_queue这样调度器就变成了协程调度器 I/O 调度器九、一个 co_recv 的逻辑假设 socket 是非阻塞的。协程里想读数据ssize_t co_recv(int fd, char* buf, size_t size) { while (true) { ssize_t n recv(fd, buf, size, 0); if (n 0) { return n; } if (errno EAGAIN || errno EWOULDBLOCK) { scheduler.wait_read(fd); scheduler.yield(); continue; } return -1; } }这段代码表面看起来像同步auto n co_recv(fd, buf, size);但底层是recv 发现没数据 注册 epoll 读事件 挂起当前协程 调度其他协程 fd 可读后恢复当前协程 继续 recv这就是协程调度器的威力。十、调度器里通常有什么队列一个完整调度器一般不止一个队列。常见结构ready_queue马上可以运行的协程 waiting_read等待 fd 可读的协程 waiting_write等待 fd 可写的协程 sleeping_tasks等待定时器的协程 finished_tasks需要回收的协程比如std::dequeTask* ready_queue; std::unordered_mapint, Task* read_waiters; std::unordered_mapint, Task* write_waiters; std::priority_queueTimer timers;如果任务调用co_sleep(1000);调度器就把它放进定时器堆里1 秒后再恢复如果任务调用co_recv(fd, ...)但没数据就放进read_waiters[fd]等epoll通知可读。十一、调度器主循环一个带epoll和定时器的调度器主循环大概是while 还有活着的任务: 如果 ready_queue 不空: 取一个 ready task 运行 否则: 计算最近定时器还有多久到期 epoll_wait 等 I/O 或定时器超时 把就绪 fd 对应的协程放入 ready_queue 把到期定时器对应的协程放入 ready_queue伪代码void Scheduler::run() { while (!done()) { while (!ready_queue.empty()) { Task* task ready_queue.front(); ready_queue.pop_front(); resume(task); } int timeout compute_timer_timeout(); int n epoll_wait(epfd, events, max_events, timeout); handle_io_events(events, n); handle_expired_timers(); } }这里的调度器就像一个总控台能跑的先跑 没人能跑就睡在 epoll_wait I/O 或定时器来了再唤醒对应协程。十二、调度器为什么需要 epoll_wait 的 timeout如果没有 ready task调度器不能空转。它应该睡眠epoll_wait(epfd, events, 1024, timeout);但如果有定时器例如协程 A 要 100ms 后恢复 协程 B 要 500ms 后恢复那么epoll_wait最多只能睡 100ms。所以 timeout 应该取最近定时器的时间timeout 最近一个 timer 的到期时间 - 当前时间这样就能同时处理I/O 事件 定时器事件十三、调度策略调度器不只是“能跑就跑”还涉及策略。最简单的是 FIFO谁先进入 ready_queue谁先运行。也可以是 round-robin每个任务运行一小段yield 后排到队尾。还可以加优先级高优先级任务先运行。或者加权调度重要任务多分配运行机会。操作系统线程调度器会考虑很多复杂因素优先级时间片CPU 亲和性I/O 等待公平性实时性用户态协程调度器通常简单很多。
调度器可以理解成决定“现在谁运行、谁暂停、谁等待、谁恢复”的管理者。如果没有调度器协程、线程、事件循环都只是一堆零件。调度器负责把它们组织起来。一、最直观的理解假设有三个任务任务 A等网络数据 任务 B处理计算 任务 C等定时器如果 A 暂时没数据继续让 A 占着 CPU 就浪费了。调度器会做A 没数据 - 挂起 A 运行 B C 定时器到了 - 恢复 C A 网络数据到了 - 恢复 A所以调度器的核心职责是让能运行的任务运行 让不能运行的任务等待 当等待条件满足后把任务重新放回可运行队列。二、调度器有很多层“调度器”这个词不只一种。常见有三类类型谁实现调度对象操作系统调度器内核线程 / 进程事件循环调度器程序 / 框架fd 事件、定时器、回调协程调度器程序 / 协程库协程操作系统调度器负责调度线程。epoll事件循环负责调度 I/O 事件。ucontext或 C coroutine 调度器负责调度协程。你前面问的这些东西拼起来通常是epoll 负责发现 I/O 就绪 ucontext 负责保存/恢复协程上下文 调度器负责决定恢复哪个协程三、操作系统线程调度器操作系统调度器是内核的一部分。它调度的是线程或进程。比如有多个线程Thread A Thread B Thread C但是 CPU 核心有限操作系统要决定现在让哪个线程跑 跑多久 什么时候切换 优先级怎么处理这是抢占式调度。也就是说线程自己不主动让出 CPU操作系统也可以强行把它切走。例如Thread A 正在运行 时间片到了 内核暂停 A 恢复 Thread B这个切换对用户代码通常是透明的。四、协程调度器协程调度器通常是用户态实现的。它调度的是协程不是线程。比如Coroutine A Coroutine B Coroutine C它们可能都运行在同一个 OS 线程里。协程调度通常是协作式的协程主动 yield 调度器才切换到其他协程也就是说协程如果不主动让出执行权调度器通常不能强行切走它。比如void taskA() { while (true) { // 如果这里永远不 yield // 其他协程就没机会运行 } }这就是协作式调度的风险某个协程如果写坏了会饿死其他协程。五、调度器最基本的数据结构一个协程调度器通常需要这些东西struct Task { ucontext_t ctx; std::vectorchar stack; bool finished; };以及std::queueTask* ready_queue; Task* current; ucontext_t scheduler_ctx;其中ready_queue可运行队列里面放着可以马上运行的协程。current当前正在运行的协程。scheduler_ctx调度器自己的上下文。协程状态一般有enum class State { Ready, // 可以运行 Running, // 正在运行 WaitingIO, // 等 I/O Sleeping, // 等定时器 Finished // 已结束 };六、 最简单的调度逻辑一个最小调度器可以这样while ready_queue 不为空: 取出一个协程 切换到它 它 yield 或结束后回到调度器伪代码void Scheduler::run() { while (!ready_queue.empty()) { Task* task ready_queue.front(); ready_queue.pop(); current task; task-state State::Running; swapcontext(scheduler_ctx, task-ctx); if (task-finished) { destroy(task); } else if (task-state State::Ready) { ready_queue.push(task); } } }这里的关键是swapcontext(scheduler_ctx, task-ctx);从调度器切到协程。协程里如果调用yield();就会swapcontext(task-ctx, scheduler_ctx);从协程切回调度器。七、yield 在调度器里的作用yield就是协程主动说我先不跑了把执行权交回调度器。例如void yield() { current-state State::Ready; ready_queue.push(current); swapcontext(current-ctx, scheduler_ctx); }这样当前协程会回到队列尾部其他协程有机会运行。执行过程像这样调度器 - A A yield - 调度器 调度器 - B B yield - 调度器 调度器 - C C yield - 调度器 调度器 - A这叫轮转调度round-robin。八、调度器和 epoll 的结合只会yield的调度器还不够强。如果协程要等网络数据不能一直空转while (true) { int n recv(fd, buf, size, 0); if (n 0 errno EAGAIN) { yield(); } }这样虽然不会阻塞线程但会不断被调度起来检查浪费 CPU。更好的做法是如果 fd 没数据 把当前协程挂到 fd 的等待表里 用 epoll 监听这个 fd yield 回调度器 等 epoll 通知 fd 可读 把等待这个 fd 的协程放回 ready_queue这样调度器就变成了协程调度器 I/O 调度器九、一个 co_recv 的逻辑假设 socket 是非阻塞的。协程里想读数据ssize_t co_recv(int fd, char* buf, size_t size) { while (true) { ssize_t n recv(fd, buf, size, 0); if (n 0) { return n; } if (errno EAGAIN || errno EWOULDBLOCK) { scheduler.wait_read(fd); scheduler.yield(); continue; } return -1; } }这段代码表面看起来像同步auto n co_recv(fd, buf, size);但底层是recv 发现没数据 注册 epoll 读事件 挂起当前协程 调度其他协程 fd 可读后恢复当前协程 继续 recv这就是协程调度器的威力。十、调度器里通常有什么队列一个完整调度器一般不止一个队列。常见结构ready_queue马上可以运行的协程 waiting_read等待 fd 可读的协程 waiting_write等待 fd 可写的协程 sleeping_tasks等待定时器的协程 finished_tasks需要回收的协程比如std::dequeTask* ready_queue; std::unordered_mapint, Task* read_waiters; std::unordered_mapint, Task* write_waiters; std::priority_queueTimer timers;如果任务调用co_sleep(1000);调度器就把它放进定时器堆里1 秒后再恢复如果任务调用co_recv(fd, ...)但没数据就放进read_waiters[fd]等epoll通知可读。十一、调度器主循环一个带epoll和定时器的调度器主循环大概是while 还有活着的任务: 如果 ready_queue 不空: 取一个 ready task 运行 否则: 计算最近定时器还有多久到期 epoll_wait 等 I/O 或定时器超时 把就绪 fd 对应的协程放入 ready_queue 把到期定时器对应的协程放入 ready_queue伪代码void Scheduler::run() { while (!done()) { while (!ready_queue.empty()) { Task* task ready_queue.front(); ready_queue.pop_front(); resume(task); } int timeout compute_timer_timeout(); int n epoll_wait(epfd, events, max_events, timeout); handle_io_events(events, n); handle_expired_timers(); } }这里的调度器就像一个总控台能跑的先跑 没人能跑就睡在 epoll_wait I/O 或定时器来了再唤醒对应协程。十二、调度器为什么需要 epoll_wait 的 timeout如果没有 ready task调度器不能空转。它应该睡眠epoll_wait(epfd, events, 1024, timeout);但如果有定时器例如协程 A 要 100ms 后恢复 协程 B 要 500ms 后恢复那么epoll_wait最多只能睡 100ms。所以 timeout 应该取最近定时器的时间timeout 最近一个 timer 的到期时间 - 当前时间这样就能同时处理I/O 事件 定时器事件十三、调度策略调度器不只是“能跑就跑”还涉及策略。最简单的是 FIFO谁先进入 ready_queue谁先运行。也可以是 round-robin每个任务运行一小段yield 后排到队尾。还可以加优先级高优先级任务先运行。或者加权调度重要任务多分配运行机会。操作系统线程调度器会考虑很多复杂因素优先级时间片CPU 亲和性I/O 等待公平性实时性用户态协程调度器通常简单很多。
)
