当一个 CPU 需要读一个存储器字 (memory word) 时,它首先检查总线忙否。 如果总线空闲,该 CPU 把所需字的地址放到总线上,发出若干控制信号,然后等待存储器把所需的字放到总线上。当 CPU 核数上升时,效率下降严重。
解决方案是为每个 CPU 添加一个高速缓存
高速缓存可以位于 CPU 芯片的内部、 CPU 附近、在处理器板上或所有这三种方式的组合
高速缓存 不以单个字为基础,而是以 32 字节或 64 字节块为基础
高速缓存一致性协议
CPU 试图在一个或多个远程高速缓存中写入一个字,总线硬件检测到写,并把一个信号放到总线上通知所有其他的高速缓存。如果其他高速缓存有个“干净"的副本,也就是同存储器内容完全一样的副本,那么它们可以丢弃该副本井让写者在修改之前从存储器取出高速缓存块。如果某些其他高速缓存有"脏"(被修改过)副本,它必须在处理写之前把数据写回存储器或者把它通过总线直接传送到写者上。
在这种模型中,操作系统的一个副本及其数据表都在 CPU 1 上,而不是在其他所有 CPU 上。为了在该 CPU 1 上进行处理,所有的系统调用都重定向到 CPU 1 上。如果有剩余的 CPU 时间,还可以在 CPU 1 上运行用户进程。这种模型称为主从模型( master-slave), 因为 CPU 1 是主 CPU,而其他的都是从属 CPU。
主从模型解决了在第一种模型中的多数问题。有单一的数据结构(如一个链表或者一组优先级链表)用来记录就绪进程。当某个 CPU 空闲下来时,它向 CPU 1 上的操作系统请求一个进程运行,并被分配一个进程。这样,就不会出现一个 CPU 空闲而另一个过载的情形。类似地,可在所有的进程中动态地分配页面,而且只有一个缓冲区高速缓存,所以决不会出现不一致的情形。
这个模型的问题是,如果有很多的 CPU, 主 CPU 会变成一个瓶颈。
对称对处理机
消除了上述的不对称性。在存储器中有操作系统的一个副本,但任何 CPU 都可以运行它。在有系统调用时,进行系统调用的 CPU 陷入内核并处理系统调用
任何 CPU 都可以运行操作系统,但在任一时刻只有一个 CPU 可运行操作系统
可以把操作系统分割成互不影响的临界区。每个临界区由其互斥信号量保护,所以一次只有一个 CPU 可执行它。采用这种方式,可以实现更多的井行操作。
在多处理机中,禁止中断的操作只影响到完成禁止中断操作的这个 CPU,其他的 CPU 继续运行并且可以访问临界表。因此,必须采用一种合适的互斥信号量协议,而且所有的 CPU 都遵守该协议以保证互斥工作的进行。
任何实用的互斥信号量协议的核心都是一条特殊指令, 该指令允许检测一个存储器字并以一种不可见的操作设置。指令 TSL (Test and Set Lock 做的是,读出一个存储器字并把它存储在一个寄存器中。同时,它对该存储器字写入一个 1 (或某些非零值)。当然,这需要两个总线周期来完成存储器的读写。在单处理机中,只要该指令不被中途中断,TSL 指令就始终照常工作。
为了阻止多个 CPU 同时访问同一个存储器字,SL 指令必须首先锁住总线,阻止其他的 CPU 访问它,然后进行存储器的读写访问,再解锁总线。
如果正确地实现和使用 TSL,它能够保证互斥机制正常工作。但是这种互斥方法使用了自旋锁(spin lock), 因为请求的 CPU 只是在原地尽可能快地对锁进行循环测试。这样做不仅完全浪费了提出请求的各个 CPU 的时间,而且还给总线或存储器增加了大量的负载,严重地降低了所有其他 CPU 从事正常工作的速度。
在获取锁之前先观察锁是否空闲,可以减少竞争,避免高速缓存颠簸。
另一个减少总线流量的方式是使用著名的以太网二进制指数回退算法
一个更好的想法是,让每个打算获得互斥信号量的 CPU 都拥有各自用于测试的私有锁变且
自旋与同步
假设一些 CPU 是空闲的,需要访问共享的就绪链表(ready list) 以便选择一个进程运行。如果就绪链表被锁住了,CPU 必须保持等待直到能够访问该就绪链表。
然而,在另外一些情形中,却存在着别的选择。例如,如果在一个 CPU 中的某些线程需要访问文件系统缓冲区高速缓存,而该文件系统缓冲区高速缓存正好锁住了,那么 CPU 可以决定切换至另外一个线程而不是等待。
假设自旋和进行线程切换都是可行的选择,则可进行如下的权衡。自旋直接浪费了 CPU 周期。重复地测试锁并不是高效的工作。不过,切换也浪费了 CPU 周期,因为必须保存当前线程的状态,必须获得保护就绪链表的锁,还必须选择一个线程,必须装入其状态,并且使其开始运行。花费在这两个线程间来回切换和所有高速缓存未命中的周期时间都浪费了。
由所有 CPU 使用的单个调度数据结构分时共享这些 CPU,正如它们在一个单处理机系统中那样。它还支持自动负载平衡,因为决不会出现一个 CPU 空闲而其他 CPU 过载的情况。不过这一方法有两个缺点,一个是随着 CPU 数量增加所引起的对调度数据结构的潜在竞争,二是当线程由于 I/O 阻塞时所引起上下文切换的开销(overhead)。
接口板上可以有一个或多个 DMA 通道,甚至在板上有一个完整的 CPU (乃至多个 CPU)。通过请求在系统总线上的块传送, DMA 通道可以在接口板和主 RAM 之间以非常高的速率复制包,因而可以一次性传送若干字而不需要为每个字分别请求总线
很多接口板上有一个完整的 CPU, 可能另外还有一个或多个 DMA 通道。它们被称为网络处理器, 并且其功能日趋强大。这种设计意味着主 CPU 将一些工作分给了网卡,诸如处理可靠的传送、多播、压缩/解压缩、加密/解密以及在多进程系统中处理安全事务等。但是,有两个 CPU 则意味着它们必须同步,以避免竞争条件的发生,这将增加额外的开销,井且对千操作系统来说意味着要承担更多的工作。
每台机器有其自己的虚拟内存和页表。当一个 CPU 在一个它并不拥有的页面上进行 LOAD 和 STORE 时,会陷入到操作系统当中。然后操作系统对该页面进行定位,并请求当前持有该页面的 CPU 解除对该页面的映射并通过互连网络发送该页面。在该页面到达时,页面被映射进来,于是出错指令重新启动。事实上,操作系统只是从远程 RAM 中而不是从本地磁盘中满足了这个缺页异常。对用户而言,机器看起来拥有共享存储器。
多计算机调度
维护就绪进程的一个中心链表,每个进程只能在其当前所在的 CPU 上运行。不过,当创建一个新进程时,存在着一个决定将其放在哪里的选择,例如,从平衡负载的考虑出发。
负载平衡
图论确定算法:有一类被广泛研究的算法用干下面这样一个系统,该系统包含已知 CPU 和存储器需求的进程,以及给出每对进程之间平均流量的已知矩阵。如果进程的数众大于 CPU 的数量 k, 则必须把若干个进程分配给每个 CPU。其想法是以最小的网络流量完成这个分配工作。
发送者发起的分布式启发算法:当进程创建时,它就运行在创建它的节点上,除非该节点过载了。过载节点的度量可能涉及太多的进程,过大的工作集,或者其他度量。如果过载了,该节点随机机选择另一个节点井询问它的负载情况。如果被探查的节点负载低于某个阈值,就将新的进程送到该节点上。如果不是,则选择另一个机器探查。探查工作并不会永远进行下去。在 N 次探查之内,如果没有找到合适的主机,算法就终止,且进程继续在原有的机器上运行。整个算法的思想是负载较重的节点试图甩掉超额的工作。应该看到在负载重的条件下,所有的机器都会持续地对其他机器进行探查,徒劳地试配找到一台愿意接收更多工作的机器。几乎没有进程能够被卸载,可是这样的尝试会带来巨大的开销 。
接收者发起的分布式启发算法:在这个算法中,只要有一个进程结束,系统就检查是否有足够的工作可做。如果不是,它随机选择某台机器井要求它提供工作。如果该台机器没有可提供的工作,会接若询问第二台,然后是第三台机器。如果在 N 次探查之后,还是没有找到工作,该节点暂时停止询问,去做任何已经安排好的工作,而在下一个进程结束之后机器会再次进行询问。如果没有可做的工作,机器就开始空闲。在经过固定的时间间隔之后,它又开始探查。
Linda: 耶鲁大学研发的用干通信和同步的新系统。在 Linda 系统中,相互独立的进程之间通过一个抽象的元组空间进行通信。对整个系统而言,元组空间是全局性的,在任何机器上的进程都可以把元组插入或移出元组空间,而不用考虑它们是如何存放的以及存放在何处。对于用户而言,元组空间像一个巨大的全局共享存储器