操作系统中的任务调度 & CPU 内存缓存一致性问题

处理器调度（multiprocessor scheduling）

作系统应该如何在多 CPU上调度工作？会遇到什么新问题？

CPU 根据程序寄存器(PC)加载指令,详码,执行,写回,并对程序计数器更新,周而复始。

但是CPU怎么及时响应硬件来的请求呢? 解决方案：中断机制。CPU有一个引脚就是触发中断的。

1、为了接入不同通常会有中断控制器,不同硬件连接到中断控制器上,每个硬件的中断有一个中断编号IRQ。

2、当一个硬件中断发生时,CPU会根据中断编号查到对应的中断服务处理程序,将当前执行上下文压栈,并将程序计数器设为中断处理程序的地址。这样中断处理程序就抢到了CPU。

3、中断处理完成后,再弹栈,跳回到原来的程序继续执行。

计算机中有一种硬件设备叫时钟,用来让程序按照一定的时间间隔执行特定的逻辑。时钟会产生时钟中断。而多任务操作系统把自己的中断服务处理程序注册到了时钟中断上,这样每隔一定间隔。就可以把 CPU从当前的任务手中抢过来,进行上下文切换后,交给另一个任务。这样就支持多任务"同时"执行了。

缓存一致性（cache coherence）问题

在单CPU系统中，存在多级的硬件缓存（hardware cache），一般来说会让处理器更快地执行程序。缓存是很小但很快的存储设备，通常拥有内存中最热的数据的备份。相比之下，内存很大且拥有所有的数据，但访问速度较慢。通过将频繁访问的数据放在缓存中，系统似乎拥有又大又快的内存。

举个例子，假设一个程序需要从内存中加载指令并读取一个值，系统只有一个CPU，拥有较小的缓存（如64KB）和较大的内存。

程序第一次读取数据时，数据在内存中，因此需要花费较长的时间（可能数十或数百纳秒）。处理器判断该数据很可能会被再次使用，因此将其放入CPU缓存中。如果之后程序再次需要使用同样的数据，CPU会先查找缓存。因为在缓存中找到了数据，所以取数据快得多（比如几纳秒），程序也就运行更快。

缓存是基于局部性（locality）的概念，局部性有两种，即时间局部性和空间局部性。时间局部性是指当一个数据被访问后，它很有可能会在不久的将来被再次访问，比如循环代码中的数据或指令本身。而空间局部性指的是，当程序访问地址为x的数据时，很有可能会紧接着访问x周围的数据，比如遍历数组或指令的顺序执行。由于这两种局部性存在于大多数的程序中，硬件系统可以很好地预测哪些数据可以放入缓存，从而运行得很好。

有趣的部分来了：如果系统有多个处理器，并共享同一个内存，如图所示，会怎样呢？

带缓存的单CPU

两个有缓存的CPU共享内存

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

这一普遍的问题称为缓存一致性（cache coherence）问题。