目录

上下文切换的成本不仅仅来自保存和恢复少量寄存器的操作系统操作。程序运行时，它们在CPU高速缓存、TLB、分支预测器和其他片上硬件中建立了大量的状态。切换到另一个工作会导致此状态被刷新，且与当前运行的作业相关的新状态被引入，这可能导致显著的性能成本。

MLFQ 单CPU调度

● 规则1：如果A的优先级 > B的优先级，运行A（不运行B）。

● 规则3：工作进入系统时，放在最高优先级（最上层队列）。

● 规则5：经过一段时间S，就将系统中所有工作重新加入最高优先级队列。

多CPU缓存一致性

多CPU的情况下缓存要复杂得多。例如，假设一个运行在CPU 1上的程序从内存地址A读取数据。由于不在CPU 1的缓存中，所以系统直接访问内存，得到值D。程序然后修改了地址A处的值，只是将它的缓存更新为新值D'。将数据写回内存比较慢，因此系统（通常）会稍后再做。假设这时操作系统中断了该程序的运行，并将其交给CPU 2，重新读取地址A的数据，由于CPU 2的缓存中并没有该数据，所以会直接从内存中读取，得到了旧值D，而不是正确的值D'。哎呀！这一普遍的问题称为缓存一致性（cache coherence）问题。

通过监控内存访问，硬件可以保证获得正确的数据，并保证共享内存的唯一性。在基于总线的系统中，一种方式是使用总线窥探（bus snooping）[G83]。每个缓存都通过监听链接所有缓存和内存的总线，来发现内存访问。如果CPU发现对它放在缓存中的数据的更新，会作废（invalidate）本地副本（从缓存中移除），或更新（update）它（修改为新值）。

多处理器系统的调度

有个问题.MLFQ在单cpu下该模型比较好理解，如果是多cpu下，多个cpu是去一起消费这个多级队列中的进程任务吗?那么一个进程可能会在不同的cpu上运行，不同cpu之间的上下文参数是互通的吗?如果不是互通的那么进程在多个cpu之间辗转运行就会损失大量资源（除非进程bind cpu)

缓存亲和

一个进程在某个CPU上运行时，会在该CPU的缓存中维护许多状态。下次该进程在相同CPU上运行时，由于缓存中的数据而执行得更快。相反，在不同的CPU上执行，会由于需要重新加载数据而很慢（好在硬件保证的缓存一致性可以保证正确执行）。因此多处理器调度应该考虑到这种缓存亲和性，并尽可能将进程保持在同一个CPU上。

SQMS

最基本的方式是简单地复用单处理器调度的基本架构，将所有需要调度的工作放入一个单独的队列中，我们称之为单队列多处理器调度（Single Queue MultiprocessorScheduling，SQMS）

多队列调度

比如每个CPU一个队列。我们称之为多队列多处理器调度（Multi-Queue MultiprocessorScheduling，MQMS）在MQMS中，基本调度框架包含多个调度队列，每个队列可以使用不同的调度规则，比如轮转或其他任何可能的算法。当一个工作进入系统后，系统会依照一些启发性规则（如随机或选择较空的队列）将其放入某个调度队列。这样一来，每个CPU调度之间相互独立，就避免了单队列的方式中由于数据共享及同步带来的问题。

Linux 多处理器调度

O(1) CFS采用多队列，而BFS采用单队列，这说明两种方法都可以成功。当然它们之间还有很多不同的细节。例如，O(1)调度程序是基于优先级的（类似于之前介绍的MLFQ），随时间推移改变进程的优先级，然后调度最高优先级进程，来实现各种调度目标。交互性得到了特别关注。与之不同，CFS是确定的比例调度方法（类似之前介绍的步长调度）。BFS作为3个算法中唯一采用单队列的算法，也基于比例调度，但采用了更复杂的方案，称为最早最合适虚拟截止时间优先算法（EEVEF）[SA96]读者可以自己去了解这些现代操作系统的调度算法，现在应该能够理解它们的工作原理了！

知乎 有问题，就会有答案。 https://wjrsbu.smartapps.cn/zhihu/article?_swebFromHost=baiduboxapp&id=456630757&isShared=1&_ swebfr=1