现代操作系统之多处理机系统（上）

多处理机

共享存储器多处理机是有两个或更多的CPU全部共享访问的一个公用的RAM，运行在任何一个COu上的程序都看到一个普通的（通常是分页）的虚拟地址空间。这个系统唯一特别的性质是，CPU可对存储器字写入某个值，然后读会这个字，得到一个不同的值（因为另一个CPU改写了它）。

最重要的部分，多处理机操作系统至少普通的操作系统。不过在某些领域它们有一些特殊的性质

多处理机硬件

所有多处理机都具有可访问全部存储器的性质，而有些多处理机仍有一些其它的性质，即读出每个存储器字的速度是一样快的。这种及其称为UMA（统一存储器访问）多处理机，而另一种则称为NUMA（肺移植存储器访问）多处理机。

基于总线的UMA多处理机体系结构

通过给每个CPU添加一个高速缓存（cache），这个高速缓存可以位于CPU芯片内部，CPU附近，处理器板上或所有三种方式的组合。因为许多读操作可以在高速缓存中得到满足，总线流量被大大减少了，这样系统就能支持更多的CPU。

每一个高速缓存块或者被标记为只读（此时可以存在与多个告诉缓存中），或者被标记为读写（不能出现在多个高速缓存）。如果CPU试图在一个或多个远程高速缓存中写入一个字，总线硬件检测到写，并把一个信号放到总线上通知所有其它的高速缓存。 如果某些其它高速缓存中有“脏”副本，它必须在处理写之前把数据写回存储器或者它通过总线直接传送到写者上。高速缓存这一套规则被称为高速缓存一致性协议。

使用交叉开关的UMA多处理机

即使拥有最好的高速缓存，单个总线的使用还是把UMA多处理机的数量限制在16个到32个CPu，连接n个CPU到k个存储器的最多简单的电路是交叉开关。

交叉开关最好的一个特性是它是一个非阻塞网络，即不会因有些交叉点或连线已经被占据而拒绝连接。

交叉开关最差的一个特性是，交叉点数量以n的平方速度上涨。无论如何对于中等规模的系统而言，交叉开关的设计是可用的。

使用多级交换的UMA多处理机

需要log2 n级，没几n／2个开关，总数为n/2 * log 2 你个开关。Omega网络称为全混洗，因为每一级信号的混合就像把一副牌分成两半。

在消息通过交换网络后，模块号左端的值就不再需要了。它们可以用作应答消息找回返回路径。

若发生冲突，则其中一个必须等待。Mnerga网络是一种阻塞网络。

可以在多个莫垮肩均匀地分散对存储器的引用。一种常用的奇数是把地位作为模块好。然后连续的字会放在连续的模块中。而连续字被放在不同模块里的存储器系统称作交叉存储器系统。

NUMA多处理机

这种机器为所有CPu提供一个统一的地址空间，但是访问本地存储器模块快于访问远程存储器模块。因此，在NUMA机器傻姑娘运行的所有UMA程序无须做任何改变，但是相同的时钟速率下其性能不如UMA机器傻姑娘的性能。

在对于远程存储器的访问时间不被隐藏时（因为没有高速缓存），系统被称为NC-NUMA（无高速缓存NUMA）。在有一致性高速缓存时，系统被称为CC-NUMA（高速缓存一致NUMA）

目前构造大小CC-NUMA多处理机最常见的方法是基于目录的多处理机。其基本思想是，维护一个数据库来记录高速缓存行的位置机器状态，当一个高速缓存被引用时，查询数据库找出高速缓存行的位置以及他是否感觉。必须配有专门的硬件来提速。

即使在一个所谓的“”共享存储器多处理机，在下层仍然有大量的消息传递。

该设计有一个明显的限制，级一行只能被一个节点高速缓存。要想允许一行能够在多个节点上被高速缓存，我们需要某种对所有行定位的方法。

多核芯片

虽然CPU可能共享或不共享高速缓存，但是它们必然共享内存。考虑到每个内存总是有唯一的值，这些内存是一致的。特殊的硬件电路可以确保一个字同时出现在两个或都给高速缓存中的情况下，当其中某个CPU修改来该字，所有其它高速缓存中的该字都会被自动地并且原子性删除以保证一致，这个过程称为窥探。

这样设计的结果是多核芯片就相当于小的多处理机。实际上，多核芯片时常被称为片级多处理机（CMP）

CPM跟更大的多处理机之间的一个差异是容错。CPM的一个共享模块失效可能导致许多CPU同时出错，而这样的情况在传统多处理机上是很少出现的。

除了所有核都是对等的对称多核芯片，还有一类多核芯片被称为片上系统。这些芯片含有一个或者多个主CPU，但同时海包含若干个专用核，例如视频和音频解码器，加密芯片或者网络接口。这些和共同构成来完整的片上计算机系统。

多处理机操作系统类型

每个CPU有自己的操作系统

静态地把存储器划分成和CPU一样多的各个部分，为每个CPU提供其素有存储器以及操作系统的各自私有副本。这样的明显优点是，允许所有CPu共享操作系统的代码，而且只需要提供数据的私有副本。

这样要比有n个分离的计算机好得多，因为它允许所有机器共享一套磁盘和其它的IO设备，他还允许灵活的共享存储器。 进程之间可以高效通信，而且从操作系统的角度上看，每个CPu都有自己的操作系统非常自然。

该设计涉及4个方面（P302）

这个模型已经很少使用了

主从多处理机

在这种模型下，操作系统的一个副本机器数据表都在一个CPU上，所有的系统调用都重定向到CPU1上。如果有剩余的CPu时间，还可以在CPU1上运行用户进程。这种模型称为主从模型。

当某个CPU空闲下来时，它向CPU1上的操作系统请求一个进程运行，并被分配一个进程。

这个模型的问题是，如果有很多CPU，那么出CPU会称为瓶颈。

对称多处理机

在存储器中有操作系统的一个副本，但任何CPU都可以运行它。在有系统调用时，进行系统调用但CPU陷入内核并处理系统调用。

当一个COU要运行操作系统时，它必须首先获得互斥信号量。如果互斥信号量被锁住。就得等待。按照这种方式，任何CPu都可以运行操作系统，但任意时刻只有一个CPU可运行曹旭哦系统。

这样就需要把操作系统分割成互不影响但临界区。每个临界区由其互斥信号量保护，所以一次只能有一个CPU运行它。

大多数但现代多处理机都采用这种安排。为这类机器编写操作系统但苦难不在于实际代码，而在于如何将其划分成可以由不同但CPU冰箱指向但临界区而互不干扰。

更进一步，要尽量避免死锁。

理论上，所有但表都可以被赋予整数值，而且其所有但临界区都应该以升序但方式获得表。

多处理机同步

在多处理机中，禁止中断的操作只影响到完成禁止中断操作的这个CPU，其它的CPU继续运行并且可以访问邻接表。因此需要合适和互斥协议。

任何实用的胡吃遍了核心都是一条特殊治疗，该指令允许检测一个存储器字并以一种不可见的操作设置。

TSL指令必须首先锁住总线，阻止其它CPU访问他，然后进行存储器的读写访问，再解锁总线。对总线枷锁的典型做法是，先使用通风的总线协议请求总线，然后申明已拥有某些特定的总线线路，直到两个周期全部完成。只要始终保持拥有这一特性的总线线路，那么其他CPu就不会得到总线的访问权。这个指令只有在拥有必要的线路和使用它们的协议上才能实现。

如果正确的实现和使用TSL，就能保证互斥机制正常工作。但是这种互斥方法使用了自旋锁。因为请求的CPU只是在原地尽可能快得对锁进行循环测试。

当两者同时看到锁是空闲的，于是同时也哦那个TSL指令去获得他。只有一个会成功，所以这里没有竞争条件，因为真正的获取是由TSL指令进行的，这条指令是原子性的。即使看到了锁空闲，然后历史用TSL指令试图获得它，也不能保证真正得到它。

另一个减少总线流量的方式是泗洪柱面的以太网二进制指数补偿算法。不采用轮询，而将一个延迟插入轮询之间，每次延迟时间加倍。

一个更好的思想是，让每个打算获得互斥信号量的CPU都拥有歌词用于测试的私有锁变量。 给一个未能活动的锁的CPu分配一个锁变量并且把它负载等待该锁的CPU链表的末端。在当前锁的持有者退出临界区时，它释放链表中的首个CPU正在测试的似有所，然后在CPU进入临界区

自旋和切换

有时对于提出请求的CPU而言，只有等待，不存在其他等待的办法。 然而，在另外一些情形中，却存在着别的选择。

自旋直接浪费了CPU周期，重复地测试锁并不是搞笑的工作。不过，切换也浪费了CPU周期，因为必须保存当前线程的状态，必须获得保护就绪链表的锁，还必须选择一个线程，必须装入其状态，并且使其开始运行。

通过事后算法可以对可行算法进行策略的基准评测标准，

一个未能获得互斥信号量的线程先自旋一段时间，若时间超过某个阙值，则切换。

多处理器调度

线程是内核线程还是用户线程是至关重要的，如果线程是由用户空间库维护，而对内核不肯叫。那么内核不能调度线程。

而对内核线程，是内核选择线程作为调度单位，线程丛书的进程对于调度算法只有很少（乃至于没有）的影响。

在多处理机上，调度是二维的，调度程序必须决定哪一个进程运行以及在哪一个CPU上运行。

另一个造成复杂性的因素是，在与呕血系统中所有的线程是不相关的，而在另外一些系统中它们是承租的，同属于一个应用并且协同曹旭哦，

分时

处理独立线程的最低暗淡算法是，为就绪线程维护一个系统级的数据结构，它可能只是一个链表，但更多但情况下可能是对应不同优先级但一个链表集合。

由所有CPU‘使用但单个调度数据结构分时共享这些CPU，就像还在一个但处理机系统中一样。不过有量缺点——意识随着CPU数量增加引起但对调度数据结构对潜在竞争，而是线程由于IO阻塞而因为对上下文切换对开销。当线程时间片用完时，也可能会发生上下文切换。

为了避免这种情况，一些系统采用智能调度算法。获得自旋锁的进程设置一个进程范围的标志表示它目前拥有自旋锁，当释放时，就清除该标志。这样调度程序就不会停止拥有自旋锁的线程，相反，还会给更多的时间。

有些多处理机使用了亲和调度。其基本思想是，尽量使一个线程在前一次运行过的同一个CPU上运行。创建这种请合理的一个途径是采用一种两级调度算法。 通过试图让一个线程在其生命周期在同一个CPU上运行，高速缓存的亲和力得到最大化。不过，如果某一个CPU没有线程运行，就选择另一个线程运行而不是空转。

两级调度算法有三个优点——将负载大致平均的分配在可用的CPU傻姑娘；尽可能发挥了高速缓存亲和力的有时；为每个CPU提供一个私有的就绪线程链表，使得对就绪线程链表的竞争见到最小，因为试图使用另一个CPU就绪线程链表的机会相对较小

空间共享

在多处理机系统中国年的一个算法是选择需要CPU周期数最少的线程运行，次小的为候选线程。

在这个简单的分区模型中国年，一个线程请求一定数量的CPu，然后全部得到或者等待全部等到。另一种方法是主动管理线程的并行度，关系并行度的一种途径是使用一个中心服务器，用它跟踪哪些线程正在运行，哪些线程希望运行以及所需CPU的最小数量和最大数量

群调度

空间共享的一个明显优点是消除多道程序设计，从而消除了上下文切换的开销。但是统一的一个缺点是当CPU被阻塞或无事可做时时间被良妃了 。

而一个解决方法是群调度，它是协同调度发展的产物。

1. 把一组相关线程作为一个单位，级一个群，一起调度
2. 一个群中国年的所有成员在不同的分时CPU上同时运行
3. 群中的所有成员共同开始和结束其时间片

使群调度正确工作的关键是同步调度所有CPu，这一位这把时间划分为离散的时间片。在每一个新的时间片开始时，所有CPU都重新调度，在每个CPU上都开始一个新的线程。在后续时间片开始是，另一个调度时间发生。在这之间，没有调度行为。如果某个线程被阻塞，则保持CPU空转，直到对应的时间片结束为止。

群调度的思想是，让一个进程的所有线程一起运行，这样，如果其中一个线程想另一个线程发送请求，接收方几乎会立即得到消息，并且几乎能偶立即应答