支持多核处理器的RTOS.doc

支持多核处理器的RTOS的关键技术1、体系结构支持多核处理器的OS可能有几种结构：主从结构、粗加锁方式、细加锁方式。（1）主从结构：修改一个OS内核使其支持多处理器系统的最简单的方法，是将整个OS视为一个不可分割的整体，并限定所有内核模式的操作均运行于同一个处理器（即主处理器）上，而另一个处理器（即从处理器）只用来执行用户模式的操作，这样得到的软件结构就不再是对称的。系统维持两个队列：一个用来管理申请在主处理器上执行的任务，另一个用来管理申请在任意一个从处理器上执行的任务，都必须由旋转锁保护。只有大多数任务都以用户模式运行时，这种结构才能体现其优越性。（2）粗加锁结构：是将整个OS当作一个由旋转锁保护的整体单片电路，但又不会将内核模式的操作局限在某一个特定的处理器上。任何一个要求内核模式操作的任务都可以获得粗加锁，并且继续在它正在使用的处理器上运行。但在某个特定的时刻，这种内核模式的操作仍然只能在某一个处理器上运行。当某项任务占用着粗加锁时，其它所有等待获得内核服务的任务都只能空闲。粗加锁的问题在于如果有几个任务都在等待获得内核服务，那么这些任务将像在单处理器系统中一样一个接一个地连续运行。（3）内核细加锁：设计内核细加锁（fine-grained locking）结构的目的是为了让不同处理器上运行的任务能够同时执行内核模式操作，采用这种结构的内核叫做线程化内核（threaded kernel），这是通过对不同的内核子系统分别采用旋转锁来实现的，以便企图访问这些子系统的任务能够并发执行。 加锁机制的粒度（granularity）决定了最大可并发执行的内核线程数。2、系统引导和初始化OS的引导和初始化是指从系统加电到能够在多个处理器内核间平等地进行任务调度的过程，是建立平等调度实施的基础。虽然说SMP系统中，各处理器可以平等地并行工作，但这是建立在系统有多个可并行执行任务的基础上；而在引导和初始化过程中，由于很多工作只能串行执行，在这个阶段处理器内核是不平等的，有主次之分。系统加电后，受到硬件控制，只启动其中一个处理器，称为主CPU或引导处理器（Booting Processor，BP），而其它处理器称为次CPU或应用处理器（Application Processor，AP），处于停机等待状态。加电启动后，主CPU跳转到特定的内存地址（复位地址），通常映射到只读存储器，保存着整个计算机的引导程序（Bootloader），其任务是进行简单的硬件检测、初始化环境参数、将OS内核装载到内存中，跳转到OS的起始地址（这是在哪里呢，类似于NiosII Boot中的_start，.text段的入口地址）开始并执行。这段引导过程完全由BP完成。进入OS内核后，BP需要进行最初的草创性工作，完成运行环境准备、各种初识状态设置、基本读写数据段清零、Bootloader传递过来的各种环境参数保存、内存栈的开辟及栈指针、全局指针设置，前面这部分工作全部由底层汇编代码完成（_start至alt_main()之间的代码），之后BP跳转到由高级语言编写的函数，开始第二个阶段CPU本身的初始化（alt_main()函数）。在CPU初始化过程中，BP首先自检，收集CPU相关的指令集、存储管理、高速缓存及协处理器等基本信息，接着为AP准备运行环境，同时为AP准备一个锁，之后唤醒AP，AP转入主CPU设置好的地址，开始锁测试而进入等待状态。唤醒AP后，BP输出自身信息后，继续进行内存等各种资源的初始化。接下来的工作主要有BP进行开发板及外部设备初始化，之后准备用于所有CPU的空闲进程，这是一个不参与调度的进程。当某个CPU没有需要执行的任务，就转入这个进程。准备好空闲进程后，由BP解除对AP的锁，各AP逐个启动，进行各种关于各自CPU的初始化，将自身的状态填写到适当的数据结构，最后相继进入空闲状态。所有的AP都完成初始化并进入空闲状态后，由BP来完成整个系统最后阶段的初始化，并执行系统的第一个进程，之后真正步入SMP环境，所有的CPU进入正常、平等的调度。3、进程调度在CMP结构中，调度机制的重点在于更好地满足多处理机并行性上，核心思想是通过降低CPU间调度竞争和选择下一个运行进程的开销，以及提高系统整体负载平衡的能力，从而大幅度提高多处理机系统的执行效率。（1）调度算法：在支持CMP的OS中，每个CPU维护一个自己的就绪进程队列，称为局部任务队列。就绪进程按时间片是否用完分为active和expired两大类，active类包括那些时间片没用完、当前可被调度的就绪进程，expired类包括那些时间片已用完的就绪进程。同时，每类中的进程按照其优先级的不同处于不同的优先级链表中。调度时，active队列中非空的最高优先级链表的第一项被作为候选进程，使得选择下一个运行进程的操作可在固定时间内完成；同时内核建立了位映射数组对应每一个优先级链表，使用标志位极大降低了寻找非空链表的时间。当一个进程耗尽其时间片后，内核重新计算它的优先级，并把它放置在expired队列的相应优先级链表中。当active队列中没有可调度进程时，内核简单地对调active和expired队列，将原来的expired队列作为新的active队列后即可进行新一轮调度。此调度算法选择下一个运行进程的时间复杂度是O(1)。（2）系统负载平衡：支持CMP的OS内核的调度系统需要很好地解决进程与CPU间的“亲和”问题，尽量使得每个进程在固定CPU上执行，提高Cache命中率。无论当前CPU繁忙/空闲，时钟中断每隔一段时间都会启动以平衡负载。一旦当前CPU发现自己的就绪队列为空，也会主动进行负载平衡。 OS内核根据系统结构的特点，引入调度域的概念将全体CPU一层一层地划分成不同的区域，每个调度域中的CPU分成若干个CPU组，且满足任一CPU惟一存在于一个组中。每个CPU属于一个基本的调度域（该域至少包括本CPU），但是CPU同时还属于一个或多个更大的调度域。每个CPU的最高层调度域必须包括系统中的全部处理器。对于CMP系统，每个芯片上的多个核天然地构成一层调度域。一个单芯片CMP系统和一个普通SMP系统的基本调度域的差别仅在于CMP基本调度域的CPU组包含的对象是一个“CPU核”，而SMP基本调度域的CPU组包含的是一个传统的物理CPU。负载平衡时，从当前CPU的基本调度域出发，遍历所有的调度域。如果某个域有一段时间没有进行过负载平衡，先寻找域中负载最大的CPU组，再寻找组中最繁忙的CPU，更新双方的负载记录，确定需要迁移的进程数为源CPU负载与本CPU负载之差的一半，然后按照从expired队列到active队列、从低优先级进程到高优先级进程的顺序进行迁移。4、中断处理传统的单处理器通常都采用一个外部中断控制器来解决外部设备到CPU的通信。对多处理器系统，处理器之间也需要通过中断方式通信。对CMP而言，多处理器的本地中断控制器需要和处理器一起封装到芯片内部，还需要一个全局中断控制器负责各个处理器内核间的中断分配，也要设计在芯片内部。（1）中断分配：全局中断控制器担负着把来自外部设备的中断请求提交和分配给片内各CPU的任务。对于每个中断向量，可采用静态和动态两种模式之一。如果某个中断向量是静态分配的，控制器把这种中断请求提交给预设的一个或多个CPU；动态模式则可以发送给所有CPU，或随机发送给某个处理器。本地中断控制器处理本地处理器内部产生的中断请求、来自外部中断控制器的中断请求及其它处理器发送过来的中断请求。（2）处理期间中断：在CMP系统中，芯片内部一个处理器常常要有目标地向系统中的其它处理器发出中断请求，这种中断被称为处理期间中断（IPI，Inter Processor Interrupt）。IPI至少应该包含两种：一、“重新调度”中断：当前CPU可以发送该中断来指示目标CPU可能需要一次进程调度，至于目标CPU在处理完该中断以后是否进行进程调度，得看事先或者在处理中断的过程中是否把当前进程设置为需要调度。二、“请求执行”中断：这个中断被用来请求目标CPU执行一个指定的函数，因为这些函数必须由目标CPU才能完成，而不能由别的CPU代替。（3）时钟中断：每个处理器都有自身的时钟发生器。在系统初始化阶段，系统先设置一个外部时钟中断源供所有CPU共享，并以此为基准测算各个CPU的运算速度，并校准自身的时钟中断发生间隔。所有CPU有基本相同的时钟脉冲周期，为了不让所有处理器都在同一时刻发生时钟中断，OS应该使各个CPU的时钟中断在相位上相互错开，把这些中断均匀地分布在时钟中断的周期中。5、同步与互斥技术同步与互斥机制需要底层硬件提供“读-修改-写”类型的访存原子操作，这样的操作能够让CPU从主存储器中读取一个值，修改之，再将修改过的值保存到存储器的相同位置中。整个过程是一次完整的总线交易，不能被其他CPU内核的访存操作所打断。“读-修改-写”类型的原子操作有多种实现方式，最常见的包括：test_and_set，swap，load-linked/store-conditional等方式。典型的支持多核处理器的RTOS1、 基于同步原语扩展的实时操作系统：在多核处理器的每一个处理器核上都运行一个完全相同的RTOS，然后提供扩展的组件库，这种组件库提供相应的同步原语以支持处理器核间的通信。Eg：VxWorks、RealOS。通过MP Extended Library同步原语库扩展，运行在一个处理器核（Processor Element）上的任务不仅能和运行在同一PE上的任务通信，还能和运行在不同PE上的任务通信，这样任务间就可以协同通信而完成特定的应用。通过将应用划分成不同的可以并行运行的任务而运行在不同的PE核上就可以并行的处理数据，从而达到提高系统性能的目的。在这样的架构中，运行在每个PE上的RealOS和运行在单核上的RealOS没有任何区别，主要扩展在于MP Extended Library的实现，它提供了一种跨核通信的手段，使运行在不同核上的任务能够同步和传输交换数据。通过同步原语库的扩展来实现对多核处理器的支持，是一种常见的对RTOS的扩展，不需要对现行的RTOS做太大修改，只需要增加一个相对独立的扩展库，就可以实现对于多核处理器的支持；同时多核的机制对应用程序不透明，应用需要根据需求安排多任务在多核上运行。这样的机制使一份RTOS在系统存储器中拷贝了多份，浪费了一定的存储空间；同时由于对应用程序不透明，需要设计多任务在多核处理器上的调度和运行，增加了应用程序的复杂度，同时需要更多的时间来调试和移植多核处理器程序。2、 基于微内核和分布式技术的实时操作系统：eg：QNX QNX是由加拿大QNX软件系统公司推出的实时操作系统。QNX Nuetrnio是一种微内核的操作系统，每一个驱动程序、应用程序、协议栈、GUI服务、文件系统都在受保护的地址空间中运行。任何一个模块都可能出现错误，也有可能重新启动运行，但都不会影响到其他模块及内核的运行。在QNX Nuetrino中，OS内核只提供最基本的服务，如线程调度、进程间通信、同步，所有其他OS服务、驱动程序、应用程序都作为单独的运行进程，通过同步消息传递与内核进行通信，这种消息传递机制形成了一条软总线，可以根据需要动态地插拔服务程序。因此，可以在系统运行中更换或重新启动几乎所有的模块，甚至是设备驱动程序。QNX对多核处理器的支持基于其微内核结构，通信被集成到QNX消息传递原语，本地的IPC和远端节点间的IPC一样。在单CPU上运行的进程分布到多CPU上时，可以同样通信，源代码和运行代码都不需要改动。3、 传统的SMP结构的实时操作系统：由Linux发展而来的各种RTOS一般采用这种方法，由一个RTOS调度运行各个任务在各处理器核上运行。在这种系统结构中，所有的CPU在运行时（除系统引导和初始化外）都是对称的，没有主次之分，通常物理上也采用同一种CPU。所有的CPU通过同一条总线共享同一个内存及所有的外设。为减少访问内存的冲突，SMP结构中的各个CPU通常都有自己的Cache。SMP实现的关键技术SMP系统的实现需要软件和硬件协同完成。作为硬件来说，组成SMP系统的CPU需要支持处理器间的通信，需要硬件提供机制来维护CUP之间Cache内容的一致性等；而作为软件的OS来说，需要配合硬件来实现进程在各个CPU间的调度，处理各种外部中断等工作。（1）处理器间的同步与互斥：进程间的同步实际上可以归结为对临界资源的互斥操作。在单处理器结构中，只要能保证在对临界资源的操作中不会发生进程调度，并且不会发生中断，或者即使发生了中断也与操作的对象无关，就保证了操作的互斥性。即使在极端的情况下（例如不允许关中断），只要对临界资源的操作能在单条指令中完成，那也保证了操作的互斥性，因为中断只能发生于指令之间，而不会发生在执行一条指令的中途。一般而言，只要能保证对临界资源操作的“原子性”，互斥性就可保证，单处理器系统正是基于这样的机理；在单处理器系统中，能够在单条指令中完成的操作被认为是“原子操作”。但在SMP结构中，由于系统中有多个处理器在独立运行，即使能在单条指令中完成的操作也可能受到干扰。与单处理器结构相比，SMP结构对互斥操作的微观“分辨率”需更高，有些在单处理器结构中的“原子操作”在SMP结构中不再是原子的了。解决办法：单纯的读或写本来就是原子的，问题在于一些既要读又要写，需要两个或以上的微操作才能完成的指令，i386 CPU提供了在指令执行期间对总线加锁的手段。CPU芯片上有一条引线LOCK，如果汇编程序中在一条指令前加上前缀“LOCK”，汇编后的机器代码就会使CPU在执行这条指令时把引线LOCK的电位拉低，从而把总线锁住，同一总线上别的CPU就暂时不能通过总线访问内存了。有个特例：在执行指令xchg时CPU会自动将总线锁住，而不需要在程序中使用前缀“LOCK。xchg指令将一个内存单元中的内容与一个寄存器的内容对换，因此常常用于对内核信号量(semaphore)的操作。（2）Cache与内存间的一致性问题：Cache在SMP结构中，情况相对于单处理器系统更为复杂，因为一个CPU并不知道别的CPU会在何时改变内存的内容。Cache写操作有两种模式：“穿透”(Write-Through)模式，Cache对写操作好像不存在一样，每次写时都直接写到内存中，实际上只是对读操作使用Cache，因而效率相对较低；“回写”(Write-Back)模式，写的时候先写入Cache，然后由Cache硬件在周转时使用缓冲线自动写入内存，或由软件主动地“冲刷”有关的缓冲线。因此在改变了缓冲页面的内容，并启动DMA写操作将其写入磁盘前要先“冲刷”Cache中有关的缓冲线，因为改变了的内容可能还没有回写到内存缓冲区中。在Intel Pentium CPU中有个寄存器，称为“存储类型及范围寄存器”(Memory Type Range Register，MTRR)，通过这个reg可以将内存中的不同区间设置成使用或不使用Cache，以及对于写操作采用穿透模式或回写模式。Cache的运用有可能改变对内存操作的次序。假定有两个观察者，一个观察CPU内部Cache受到访问的次序，另一个观察内存受到访问的次序，则二者可能会有相当大的差异。前者就是程序中编排好的次序，称作“指令序”(program ordering)，后者则是实际出现在处理器外部，即系统总线上的次序，称作“处理器序”(process ordering)。不使用Cache时二者相同，如果使用Cache要看具体的情况和操作。如果保证“处理器序”与“指令序”相同，称作“强序”(strong ordering)；反之，如果“处理器序”有时候可能不同于“指令序”，称作“弱序”(weak ordering)。对于单处理器结构的系统，这二者的不同并不成什么问题，然而对SMP结构的系统却可能成为问题。单处理器系统中的DMA操作都是由设备驱动程序主动地启动的，所以设备驱动程序知道什么时候应该丢弃哪些缓冲线的内容，什么时候应该冲刷哪些缓冲线的内容。可在SMP结构中，每个CPU都可能改变内存中的内容，且异步改变，每个CPU都只知道自己何时会改变内存的内容，但不知道别的CPU什么时候改变内存的内容，也不知道本地Cache中的内容是否已经与内存中不一致，每个CPU也可能因为改变了内存的内容而使其他CPU的Cache变得不一致。解决办法：对于Cache中的内容，一般只有数据才有一致性的问题，因为对指令一般都是只读，不在运行的过程中动态地加以改变。Intel在Pentium CPU中为已经装入Cache的数据提供了一种自动与内存保持一致的机制，称为“窥探”(Snooping)。每个CPU内部有一部分专门的硬件，一旦启用了Cache后就时刻监视系统总线上对内存的操作。由于对内存的操作定要经过系统总线，没有一次实际访问内存的操作能够逃过监视。如果发现有来自其他CPU的写操作，而本CPU的Cache中又缓冲存储着该次写操作的目标，就会自动把相应的缓冲线废弃，使得在需要用到这些数据时重新将其装入Cache，达到二者一致。这样，SMP结构中Cache与内存的数据一致性问题对软件而言就透明了。（3）中断处理：在单处理器结构中，整个系统只有一个CPU，所有的中断请求都由这个CPU响应和处理，而SMP结构不能固定让其中的某一个CPU处理所有的中断请求，否则其他CPU连时钟中断不能处理，这样如果在那些CPU上运行的进程陷入了死循环，就永远没有机会进行系统调用，这些CPU将永远不会有进程调度。另外，如果是让所有的CPU轮流处理中断，或谁空闲谁处理，中断请求的分配将如何处理，这些都需要软件和硬件协同来完成。传统的i386处理器采用8259A中断控制器。一般而言，8259A的作用是提供多个外部中断源与单一CPU