第十二章 CPU多核调度
CPU多核调度概述
单队列多核调度
- 缺乏可扩展性：多个CPU核均对一个就绪队列进行读写操作；
- 缺乏缓存亲和性：CPU核对进程的缓存不能得到有效利用；
如下图，4个CPU核对5个进程的调度：
为了提高调度算法的缓存亲和性，尽量让进程在同一个CPU核上运行(在保持对该进程的缓存亲和性时，可能会牺牲其他进程的缓存亲和性)；如下图所示：
多队列多核调度
- 每个CPU核维护一个就绪队列，各CPU核之间的调度相互独立；
- 会出现负载不均衡；
如下图，开始给进程A、C分配CPU核0，给进程B、D分配CPU核1；
一段时间之后，进程C结束，进程A独占CPU核0；
一段时间之后，进程A结束，CPU核0处于空闲状态，而CPU核1还在运行着两个进程，此时就出现了负载不均衡；
为了解决出现的负载不均衡问题，就要将繁忙的CPU核上的进程迁移到空闲的CPU核上去；比如上幅图，可以将进程B移到CPU核0上，然后系统负载均衡；而对于进程A独占CPU核0的情形，调度就比较复杂，此时操作系统该如何决定发起迁移？
一般采用一种叫做”工作窃取”的技术；让执行的进程数目少的CPU核”不定期”地查看其他CPU核的就绪队列，从那些长的就绪队列中”拉取”一个或多个进程，从而实现负载均衡。而这个查看的时刻一般选在CPU核的进程进行切换的时候。
O1调度器
Linux系统中进程有140种优先级，使用长140的比特数组来记录优先级；每个(优先级)比特对应该优先级的FIFO进程队列(若一个优先级下有进程队列，则这个优先级对应的bit位置1)，其中run比特数组管理还未运行的就绪态进程，expired比特数组管理运行过的进程；给每个CPU核维护上述两个数组。
对于调度时对数组进行的3种基本操作：访问(最高优先级就绪态进程)、(在expired比特数组对应的优先级队列中)插入(刚刚运行过的进程)、(在expired比特数组对应的优先级队列中)删除(刚刚运行过的进程)；分析这些操作的复杂度：
- 访问：在切换进程时，会寻找最高优先级的就绪态进程，而这等价于寻找一个比特数组中为1的最高位比特，CPU可在O(1)时间内找出一个字节中为1的最高位比特；因此，随机访问的复杂度为O(1)；
- 插入：在队尾插入，复杂度O(1)；如果插入前在expired数组的该优先级下没有进程队列，则将expired数组的该优先级对应的比特置1；
- 删除：在队头删除，复杂度O(1)；如果删除后在run数组的该优先级下没有进程队列，则将run数组的该优先级对应的比特置0；如果run数组所有比特均为0，则交换run数组与expired数组；并且，每个CPU核不定期检查自己的负载，如果自己负载较其他CPU核轻，则”拉取”其他CPU核上的就绪态进程；
CFS调度
完全公平的调度。通过进程消耗的CPU时间(标准化之后的虚拟CPU时间)来确定调度哪个进程；
分配给进程的运行时间=调度周期×进程权重/所有进程权重之和；但是调度周期一直处于动态变化中，通过这个式子确定分配给进程的运行时间比较麻烦，因此引入虚拟运行时间vruntime=实际运行时间×1024/进程权重；这样既考虑到分配CPU运行时间较少的进程(对它给予一定补偿)，有考虑到高优先级的进程。
Linux系统(每个CPU核)采用红黑树来维护进程的vruntime，需要调度时，从红黑树中选取vruntime最小的进程投入CPU中执行。
为避免已经运行一段时间的进程在新的进程进入后出现”饥饿”现象=>不能将新进程的vruntime设置为0，而应该设置为红黑树中就绪态进程的最小vruntime。
对于休眠了一段时间的进程，由于其他进程的vruntime一直增加而休眠进程的vruntime并未增加，因此在休眠进程被唤醒后可能会长时间抢占其他进程的CPU资源=>在休眠进程被唤醒后应该以红黑树中就绪态进程的最小vruntime为基准重新设置其vruntime值。
在负载轻的CPU核”拉取”负载重的CPU核上的就绪态进程时，它的vruntime需要进行调整以”适应新的环境”=>记进程的vruntime为vrt，它所在CPU核的红黑树中就绪态进程的最小vruntime记为min_vrt_1，”拉取”此进程的CPU核的红黑树中就绪态进程的最小vruntime记为min_vrt_2，则此进程新的vruntime=vrt-min_vrt_1+min_vrt_2；
由计算vruntime的式子可以看到，CPU的运行时间长了之后，各进程的实际运行时间也会很长，这是算出的vruntime值可能会产生溢出，考虑到vruntime的作用是作为调度的依据——选择最小vruntime的进程=>填在红黑树中的节点值实际上是每个进程的vrt-min_vrt；
BFS调度算法
BFS调度算法是时间片轮转算法的变种。大致形式如下图：
BFS算法在多核CPU的情形下使用单就绪队列(链表)，增加了队列互斥访问的开销，但减少了维护负载均衡的开销。
BFS算法设定了103个优先级(100个静态的实时优先级与3个普通的优先级)，每个优先级维护一个就绪进程队列。每个CPU核计算进程的虚拟截止时间时，对于进程上一次执行的CPU核，会适当减小其虚拟截止时间。