10.1 背景：多处理器架构

多处理器与单CPU的基本区别：核心在于对硬件缓存(cache)的使用，以及多处理器之间共享数据的方式。

  • 缓存是基于局部性的概念：时间局部性和空间局部性。

时间局部性：当一个数据被访问后，它可能不久后被再次访问，比如循环代码中的数据或指令本身。

空间局部性：当访问地址为x的数据时，可能会紧接着访问x周围的数据，比如遍历数组或指令的顺序执行。

image.png

  • 缓存一致性：

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

总线窥探：每个缓存都通过监听链接所有缓存和内存的总线，来发现内存访问。如果CPU发现对它放在缓存中的数据的更新，会作废本地副本(从缓存中移除)，或更新它。

10.3 缓存亲和度

  • 缓存亲和度

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

10.4 单队列调度

  • SQMS(单队列多处理器调度)

多处理器系统的调度，最基本的方式是复用单处理器调度的基本架构

然而有几个明显短板：缺乏可扩展性，需要加锁，于是便会浪费性能；假设每个工作依次执行一个时间片，然后选择另一个工作，因此每个工作都不断在不同CPU之间转移，这违背了缓存亲和。

10.5 多队列调度

  • MQMS(多队列多处理器调度)

每个CPU一个队列。当一个工作进入系统后，系统会依照某个规则将其放入某个调度队列。

MQMS也有问题：负载不均衡
image.png

解决方案：迁移。通过工作的跨CPU迁移，真正实现负载均衡

如果太频繁的检查其他队列，就会带来较大的开销