CMP操作系统技术
- 格式：doc
- 大小：37.50 KB
- 文档页数：6
运“芯”帷幄 —CMP的操作系统技术
单芯片多处理器（CMP），特别是在一个芯片上集成了多个相同通用处理器的单芯片对称多处理器（同构CMP）的发展，是上世纪90年代以来集成电路制造工艺的进步与微处理器体系结构的发展所带来的必然发展方向。
和目前在服务器领域广泛采用的对称多处理器（Symmetric Multi-Processor, SMP）结构类似，在CMP系统中，位于同一个芯片内部所有处理器内核以平等的身份参与任务调度和中断处理，共享内存和外部设备，而且也可以共享片内的 （部分或全部）高速缓存。
CMP的结构相对简单，可以直接使用现有的处理器内核，因此开发周期与成本相对较低，结构简单带来的另一个好处是更易获得高的主频。由于多个处理器集成在 一块芯片上，且共享cache，微处理器之间的通信延迟会明显降低，有利于提高系统的整体性能。因此，CMP具有良好的发展前景和广泛的应用空间，众多著名大学、科研机构和商业公司都展开了广泛而积极的研究。
而要想真正发挥CMP的优势，软件，特别是操作系统和编译工具等系统软件的支持至关重要，没有这些软件，CMP将处于“空转”状态。因此，每一个CMP系统都需要为其量身打造的系统软件。
CMP对操作系统提出的挑战
系统软件对于CMP广泛、深入的应用有重要的意义，这里我们讨论操作系统。操作系统是计算机系统的基本系统软件，在整个计算机系统中处于核心地位，负责控制、管理计算机的所有软件、硬件资源，是惟一直接和硬件系统打交道的软件，是整个软件系统的基础部分，同时还为计算机用户提供良好的界面。
对于普通用户而言，操作系统是一个资源管理者，通过它提供的系统命令和界面操作等工具，以某种易于理解的方式完成系统管理功能，有效地控制各种硬件资源，组织自己的数据，完成自己的工作并和其他人共享资源。
对于程序员来讲，操作系统提供了一个与计算机硬件等价的扩展或虚拟的计算平台。操作系统提供给程序员的工具除了系统命令、界面操作之外，还有系统调用，系 统调用抽象了许多硬件细节，程序可以以某种统一的方式进行数据处理，程序员可以避开许多具体的硬件细节，提高程序开发效率，改善程序移植特性。
并行是计算机科学与技术的重要分支之一，其核心思想是通过任务的合理划分和分配，使得多个处理器可以同时执行一个或多个任务，以达到系统整体计算能力的大幅度提升。CMP的意义在于能够提供任务并行执行的一个新思路，支持在一个芯片内的多个处理器内核之间任务的划分和分配（也就是调度），而任务的调度则需 要操作系统来完成。
CMP的发展对操作系统提出了新的挑战。首先，如何合理组织、调度任务才能最大程度地发挥CMP结构的性能？其次，如何保持操作系统的外部接口的相对稳定？对于一般用户而言，大家希望的是平滑的过渡，一方面界面最好和以前的操作系统完全相同，另一方面以前能用的应用程序最好还能够不做任何修改就直接在 CMP的机器上直接运行，也就是说CMP对于用户来讲最好是透明的，这需要操作系统在用户界面和编程接口方面都保持不变。
如何更好地组织和调度任务以便将CMP结构的性能发挥到极致是核心的问题，这是人们对CMP最大的期望。要解决这个问题，需要软硬件共同协作，从任务调度、中断分配、资源共享等几个方面入手，硬件方面则要求CMP系统提供全新的同步与互斥、中断分配以及CPU内核之间的中断等机制。
支持CMP操作系统的关键技术
目前国际上对于CMP的研究还处于探索阶段，相关操作系统也处在积极研究时期。研究、分析和借鉴支持CMP操作系统的关键技术对于我们认识、理解和设计用于CMP的操作系统有着非常重要的意义，这里，我们简单介绍支持CMP操作系统的引导和初始化、调度，中断处理和同步、互斥技术。
系统引导和初始化
操作系统的引导和初始化是指从系统加电到能够在多个处理器内核之间平等地进行任务调度的过程，这一过程是建立平等调度实施的基础，对于整个系统的运行具有重要意义。虽然说对称多处理器系统中，各处理器可以平等地并行工作，但这是建立在系统有多个可并行执行任务的基础之上，而在引导和初始化过程中，由于很多工作只能串行地执行，所以在这个阶段处理器内核是不平等的，是有主次之分的。系统加电之后，受到硬件控制，只启动其中一个处理器，称为主CPU或者引导处理器（Booting Processor, BP)，而其他处理器，称为次CPU或者应用处理器(Application Processor, AP)，则处于停机等待状态。
加电启动之后，主CPU跳转到特定的内存地址，通常映射到只读存储器，这里保存着整个计算机的引导程序，其任务是进行简单的硬件检测、初始化环境参数、将操作系统内核装载到内存中，跳转到操作系统的起始地址并开始执行。这段引导过程完全由BP完成。
进入操作系统内核之后，BP需要进行最初的草创性工作，完成运行环境准备、各种初识状态设置、基本读写数据段清零、bootloader传递过来的各种环 境参数保存、内存栈的开辟以及栈指针、全局指针设置。前面这部分工作全部由底层汇编代码完成，之后，BP跳转到由高级语言编写的函数，开始第二个阶段 CPU本身的初始化。
在CPU初始化过程中，BP首先开始自检，收集CPU相关的指令集、存储管理、高速缓存以及协处理器等基本信息。接着为次CPU准备运行环境，同时为AP 准备一个锁，之后唤醒AP，AP转入主CPU设置好的地址，开始锁测试而进入等待状态。唤醒AP之后，BP输出自身信息之后，继续进行内存等各种资源的初始化。
接下来的工作主要有BP进行开发板以及外部设备初始化，之后准备用于所有CPU的空闲进程，这是一个不参与调度的进程，当某个CPU没有需要执行的任务， 就转入这个进程。准备好空闲进程之后，由BP解除对AP的锁，各AP逐个启动，进行各种关于各自CPU的初始化，将自身的状态填写到适当的数据结构，最后相继进入空闲状态。
所有的AP都完成初始化并进入空闲状态后，由BP来完成整个系统最后阶段的初始化，并执行系统的第一个进程，之后真正步入对称多处理器环境，所有的CPU进入正常、平等的调度。
调度
调度系统对于操作系统乃至整个计算机系统的整体性能有非常重要的影响，嵌入式、桌面和高端服务器系统对于调度器的要求是很不一样的。在CMP结构中调度机制的重点在于更好地满足多处理机并行性上，核心思想是通过降低CPU间调度竞争和选择下一个运行进程的开销，以及提高系统整体负载平衡的能力，从而大幅度提高多处理机系统的执行效率。其特性如下：
1.调度算法
在传统单CPU结构的调度系统中，所有就绪进程（状态为TASK_RUNNING）被组织到同一个双向链表之中，称为全局任务队列，调度过程中将遍历此链表中的所有进程，调用计算每一个进程的权值，从中选择权值最大的进程投入运行。由于调度器要遍历所有就绪进程，因此选择下一个运行进程的时间复杂度是O (n)(n为就绪进程的个数)。同时，因为就绪队列是全局性的，对单CPU系统来讲只可能有一个CPU访问这个队列，而在多处理器结构中，必须通过一个全局的自旋锁保证同一时刻只有一个CPU进行访问，这样导致系统中其他CPU的等待。如果就绪进程个数比较多，那么就绪队列就会成为一个明显的瓶颈。
在支持CMP的操作系统中，每个CPU维护一个自己的就绪进程队列，称为局部任务队列，这样大大降低了CPU间的竞争。就绪进程按时间片是否用完分为 active和expired两大类，active类包括那些时间片没用完、当前可被调度的就绪进程，expired类包括那些时间片已用完的就绪进程。 同时，每类中的进程按照其优先级的不同处于不同的优先级链表中。
调度时，active队列中非空的最高优先级链表的第一项被作为候选进程，使得选择下一个运行进程的操作可以在固定时间内完成。同时内核建立了一个位映射数组来对应每一个优先级链表，使用标志位的方式极大降低寻找非空的链表所需要的时间。当一个进程耗尽其时间片后，内核重新计算它的优先级，并把它放置在expired队列的相应优先级链表中。进程优先级的计算过程还可以分散到进程的执行过程中进行。这种将集中计算过程分散的做法，保证了调度器运行的时间上限，降低了不必要的开销；同时在内存中保留更加丰富的信息的做法也加速了候选进程的定位过程。当active队列中没有可调度进程时，内核简单地对调 active和 expired队列，将原来的expired队列作为新的active队列后即可进行新一轮调度。
此调度算法选择下一个运行进程的时间复杂度是O(1)，与就绪进程的个数无关，调度效率大大提高。
2.系统负载平衡
支持CMP操作系统内核的调度系统需要很好地解决进程与CPU之间的“亲和”问题。如果不考虑亲和，一个进程可能在CPU之间比较频繁地迁移，交互式进程（或高优先级的进程）可能还会在CPU之间不断“跳跃”，这样，每一次迁移之后，都可能造成频繁的内存访问，导致整体性能下降。
支持CMP操作系统内核的调度系统尽量使得每个进程一直在固定的CPU上执行，这样可以提高Cache的命中率；但是如果某个CPU的就绪队列过长，不断的进程切换反而造成Cache命中率的下降，而且还造成其他CPU不能充分发挥效能。无论当前CPU是繁忙或空闲，时钟中断每隔一段时间都会启动一次以平衡负载。当然，一旦当前CPU发现自己的就绪队列为空时，也会主动进行负载平衡。
为了进行有效的负载平衡，操作系统内核根据系统结构的特点，引入调度域(struct
sched_domain)的概念将全体CPU一层一层地划分成不同的区域，每个调度域中的CPU分成若干个CPU组，且满足任一CPU惟一存在于一个组 中。每个CPU属于一个基本的调度域（该域至少包括本CPU），但是CPU同时还属于一个或多个更大的调度域。CPU的多个调度域通过构成一个单向链表，且必须满足：1.父调度域是子调度域的超集；2.每个CPU的最高层调度域必须包括系统中的全部处理器。例如在一个支持超线程的CMP系统中，每个逻辑 CPU的基本调度域包含所在传统物理CPU上的全部的逻辑CPU，基本域的每个CPU分组包含一个逻辑CPU；基本调度域的父调度域是这个系统的最高层调度域，它包含系统中所有的逻辑CPU，该域的每个CPU分组包含一个物理CPU上的全部逻辑CPU。
对于CMP系统，每个芯片上的多个核天然地构成一层调度域。一个单芯片CMP系统和一个普通SMP系统的基本调度域的差别仅在于CMP基本调度域的CPU 组包含的对象是一个“CPU核”，而SMP基本调度域的CPU组包含的是一个传统的物理CPU。对于像支持超线程和多核SMP这样复杂的CMP系统，必须 增加一个基于芯片层面的新调度域。
进行负载平衡时，从当前CPU的基本调度域出发，遍历所有的调度域。如果某个域有一段时间没有进行过负载平衡，先寻找域中负载最大的CPU组（CPU组的 负载等于组中所有CPU的负载之和），然后寻找组中最繁忙的CPU（该CPU的负载超过本CPU至少25%），更新双方的负载记录，确定需要迁移的进程数 为源CPU负载与本CPU负载之差的一半（经过更新后的值），然后按照从 expired 队列到 active 队列、从低优先级进程到高优先级进程的顺序进行迁移，但实际上真正执行迁移的进程往往少于计划迁移的数目。
