一个队列,两颗核
两颗核都醒着了,该回答调度的问题:活怎么分。教科书式的答案有两种。一种是每颗核一条私有的就绪队列,谁队列空了去别家偷活,偷活的雅号叫工作窃取。缓存亲和倒是好:任务留在上回跑过的核上,那颗核的缓存里存的老数据还热着,不用从头再暖一遍了。代价是一堆跨核同步的巧劲。另一种全机的就绪队列只有一条,配的是一把锁,谁有空都可以来抢的。当年的计划书上写的是第一种,连 CPU 亲和性都排了计划,最后落地的是第二种,笔记里留了一句明白话,不搞每核的队列与偷活,留给以后的性能优化。咱们这一遍站在同一道题面前,拍的是同一个答案,理由咱们当面说清:两颗核的教学内核,负载是几个测试任务加一个 shell 而已,锁的争抢在咱们的机器上几乎不存在,而一条队列一个决策点,在一处就能讲清楚所有的调度语义。共享队列换来的是正确,每核一队换来的是性能,偷活属于性能的后一层,登记在明确不做的页上。同页登记的还有票锁,排队发号的公平锁,当年也写了计划没落地:测试置位配一条暂停指令,谁抢到算谁的,对两颗核已经够用了,饥饿一类的富贵病等排队的人多了再治。
队列要上锁了,第一反应是拿队列锁把每个入口一包就完事了,第二反应是发现这么包不得。调度操作是会嵌套的:唤醒别人发生在持锁登记的路上,等孩子退场发生在持锁扫描名册的路上,等待的等待一层叠一层。每层的操作都抢锁,结果自己等自己,当场就死锁了。所以锁的纪律是按核计数:每核的块里存一个嵌套深度,进门后的头一件事是记中断状态、深度加一,只有从零到一那一拍才真的抢锁,内层进了门只数数。出门是对称的,深度归零的那一拍才放锁,再把记下的中断状态还原。咱们把两拍的代码摆出来:
void Scheduler::QueuePolicy::enter(State& state) {
state.irq = arch::SaveAndDisableIrq();
if (local().queue_depth++ == 0) {
state.scheduler.queue_lock_.lock();
}
}咱们在锁上还做了一个伴生的决定:唤醒的广播不在锁里发。往队列里放了一个新任务,别的核可能正睡觉,怎么都得喊一声,喊的方式是中断,这在多核的世界里有个专名:核间中断,行话的缩写是 IPI,一颗核给另一颗核发的软件中断。可持着队列锁发 IPI 是自己堵自己:被喊醒的核要处理这声中断,处理的第一件事又是抢队列锁,而锁还在喊话人手里。所以唤醒的请求落成一面旗,每核的块里占一格,锁内置了旗不发话,最外层放完了锁才看旗行事,看见旗了才广播。发的时候走的还是发启动信号那套本地芯片的握手:等上一单送完,写目标的身份号,写命令字的那一笔。一夜里唤醒了十次,听得见的只有一声广播,省下的九声都归并在旗里。
广播用哪个向量也有它的讲究。选的是 0xE0,躲的是设备中断区,避开本核定时器的 0x30,避开假中断的 0xFF,也给往后设备消息信号那一路留出 0x40 的一带。收到这声中断的核干什么,进门谢过本地芯片,记了一笔数,然后咱们问调度器要不要让位,要的话当场轮换就是了。收信的对象是除自己外全体,广播也不做什么挑选。为什么不查谁闲着只给闲的发,你想,查谁闲这件事本身要读别核的状态,读的那一刻别核可能刚好去睡,追着读的结果是永远差半拍。广播笨而稳:忙着的核多收一声,门口看一眼让位的标志,不满足条件的原样回去,开销不过一条指令而已。空闲的核被它从停机里捞起来,头一眼望的是队列,有什么活干什么活,没活了就接着睡。单核时代的这个广播函数第一行就返回,在线的数不到二,广播也没有什么事可做,豁免就写在函数的第一行。
入册的次序最容易被跳过,跳过了就出事。任务进调度器的那一下,名字、父辈、队列链接、页的世界,一堆元数据等着咱们去填。单核时代这一串填了一半,没什么人看得见,到了双核时代,另一颗核随时可能把队列里的活挑走,挑上一个填了一半的任务,恢复出去的就是残废的寄存器影像。所以入册分两拍:头一拍登记造册,挂上阻塞的牌子,阻塞态的任务任何挑选都跳过。元数据填齐了,状态改成了就绪,这任务才算上了架。叫醒别人的那一拍同时也是发布的拍。初始的 init 线程和 shell 走同一个口子,克隆出来的新任务也走同一个口子。
底座上咱们还顺手办了两件长进。头一件的长进在空闲上,咱们把每核的空闲从凑数的假任务换成了正经的等待:它就是每核自己的启动栈,核在自己的栈上等活,切入切出走的是与任务同一套切换器的进出主上下文原语,头核的主上下文也跟着改成了每核一格的数组。
第二件的活是搬家,咱们把时间片计数、抢占深度、待收尸的暂存位,这些原本住在调度器单间的计数与标记,全数搬进了每核块。看得见的内核那一卷立的调度类插拔一点没动,类注册表还是全机的一份,注册的次序就是挑选的次序,这本来就是全机的家当,现在它名实相符了。
咱们把验收的案子按在这套机制上跑:两颗核真取共享任务,让位的次数各是两百五十六,两边抢的是同一把锁,计数一位都丢不了。还有一桩专门验唤醒的:第二颗核把自己的本地定时器屏蔽了再睡,醒来数的必须是让位中断的计数,不是定时器的,证明叫醒它的就是那一声广播。两颗核都会干活了,可还有一个没答的问题:一个任务在头核上被切下,半路让第二颗核挑了去,会怎么样。下一章专讲的正是这个窗口。