多核操作系统

1、多核操作系统摘要 : 对多核操作系统的发展状况进行了综述，指出了多核操作系统的发展滞后于多核技术发 展的现状，介绍了多核操作系统的起源和国内外研究状况，分析了多核操作系统研究中面临的 一些主要问题及已有的研究成果, 对多核操作系统的一些研究方法进行了总结，最后，设计了一种异构多核处理器的操作系统。关键词 : 多核操作系统 ; 操作系统模型 ; 任务调度 ; 存储器管理 ; 内核同步； HMP第一章 引言操作系统构建于硬件设备之上，目的在于最大限度发挥硬件的工作性能，同时也受限于硬 件设备的工作能力和方式。所以操作系统的发展，首先是来源于硬件的发展，而硬件中的核心 就是处理器。提高处理器的性能从

2、根本上来说有两种办法 : 通过改进制造工艺来提高CPU 的主频；提高指令的执行效率，即提高IPC( instructions per cycle)。从提高主频的角度来看，高主频会带来巨大的功耗问题。以 NetBurst 架构的处理器为例，当运行主频达到最高 3.8 GHz 的情况 下，发热功耗会达到 115 W。很显然，要解决高主频带来的功耗问题并不是一件容易的事情。 与此同时， 制造工艺在提高 CPU 主频的过程中也会引入严重的漏电流问题， 漏电流问题是制约 CPU 主频提高的最重要因素。从提高指令执行效率的角度来看，指令流水线、超长指令字、超 标量结构、超线程技术等都在提高指令执行效率上起

3、到了一定的作用，但是均受限于单核处理 器的执行能力，并不能从根本上显著提升 CPU 系统的整体性能。对于单核处理器在性能提升中遇到的瓶颈，近年来，AMD、IBM、Intel、SUN 等公司纷纷推出了自己的多核处理器或多核架构设计1 。多核处理器的出现， 使处理器的主频大幅度降低，同时也提升了指令执行效率，普遍认为多核处理器将会是今后处理器发展的方向。但是与处理 器发展不相适应的是，基于多核处理器之上的操作系统和软件对于多核的支持并不完美。微软 Windows 核心操作系统部门内核设计师 Dave Probert 提到了关于多核技术发展的一些 问题。芯片厂商在生产多核处理器时一厢情愿地认为软件开

4、发者将为多核处理器开发软件，问 题是目前的桌面系统软件不能有效地利用多核处理器，因为开发者需要利用并行编程技术才能 充分利用多核处理器的处理能力。除专业的科学计算软件外，并行软件并不普及，而且并行编 程技术也相对难以掌握。 一种更好的方法是重新考虑操作系统管理多核处理器的方式， “问题不 在于并行编程， 而在于操作系统如何管理处理器” ，微软正在开发针对多核处理器的全新一代多 核操作系统。 从目前来看， 多核操作系统滞后于多核处理器的发展， 而多核技术作为一个系统， 其中的“短板”将严重制约计算机整体性能的提升。可以说，多核操作系统技术的突破，将会 带来从嵌入式领域到桌面计算机、服务器等所有计

5、算机系统的性能的一个整体性提高，因此对 于多核操作系统的研究意义非常重大。 第二章 多核操作系统的研究进程国外研究进程虽然多核是近年来才出现的新概念， 涵义是指在一个芯片上， 集成了多个 CPU 的内核以达 到多内核协同工作，提高处理器性能的目的。但是从操作系统的角度来说，早在 20 世纪 70 年 代出现的多处理器操作系统可以说是多核操作系统的前身。因此，多核操作系统的思想最早可 以追溯到1974年由卡内基梅隆大学提出的HYDRA操作系统2。HYDRA内核是最早针对多处理器系统设计的操作系统之一，并且能在 c.mmp 硬件上运行。 HYDRA 内核把“对象”的概念引 入操作系统中，将物理上的

6、或者虚拟的资源都当作对象进行处理。另外，HYDRA还提供了一种灵活的保护策略，针对不同的对象可以提供不同的保护机制。随后，在1979 年，卡内基梅隆大学又推出了一个多处理器操作系统StarOS3 。 StarOS 继承了部分 HYDRA 的思想， 提出了如模块、功能、模块调用等新的概念。 这些概念在后来的很多基于面向对象的操作系统中得到应用， 如iMAX、Choice、CHAO等。由于UNIX操作系统的流行，从 20世纪80年代开始，逐 渐出现了一些类 UNIX的多处理器操作系统。包括DYNlX7、UMAX8、ChrysaliS9、RP310等。这些操作系统的综合特性包括支持多用户，支持多线程

7、和进程，基于优先级的进程调度，可抢占 调度，基于锁、信号量、事件的进程同步，支持虚拟内存等。从1996 年多核处理器架构提出开始，斯坦福大学、卡内基梅隆大学、麻省理工学院等院校最早开始了关于多核操作系统的研 究，并推出了自己的多核操作系统。随着多核技术的迅猛发展，IBM、 SUN 等商业公司也发现了多核技术的发展潜力，纷纷投入多核技术的研究。为了保证多核技术的健康发展，多核协会 ( Multicore Association) 在 2005 年成立。多核协会是一个开放性的非营利组织，由不同的工作 组负责多核处理器、操作系统、开发调试工具、应用程序等不同类别的研究，致力于解决多核 技术发展中的问

8、题，制定相关的标准。国内研究进程 国内在多核操作系统方面的研究主要集中在一些学术机构中，而且研究机构比较少，起步 也相对比较晚，这与多核技术的巨大发展潜力不相适应。浙江大学在2008 年设计实现了一个支持异构多核的嵌入式实时操作系统SmartOSEK OS-M1，实现了多核之间的同步与通信，并设计了一种多 核操作系 统之上的 编程模型 。电子科 技大学在 2009 年实 现了在 四核处理器 PB11MPCore上的操作系统 aCoral12，并且通过改进的位图映射优先级调度算法，将优先级队 列查找复杂度控制在 O(1) ，以保证多核系统的实时性能。 复旦大学联合西安交通大学以及麻省 理工学院和

9、微软亚洲研究院在2008年共同开发出多核操作系统Corey。Corey的设计思想是“应用程序控制数据的共享” 13，即通过应用程序对内核间共享资源的控制，减少多核之间不必要 的资源传递和更新，以达到更高效利用多个内核的目的。实验表明这种思想对系统整体性能提 升的效果明显，在 16核的系统上，Corey系统的Map Reduce性能比Linux提高了 25%。第三章多核操作系统的关键问题多核操作系统应该包含传统单核操作系统的所有功能，然而由于内核数量的增加，多核操作系统的复杂性和设计的可能性也急剧增加14。多核操作系统的关键问题主要有以下四方面：a）既然处理器有同构多核和异构多核，那么让所有内核

10、运行同一个操作系统的代码映像，还是各个内核根据自己不同的特点运行不同的操作系统？b）如何决定任务的调度机制和策略，使每个内核都充分发挥自己的性能并且保证所有内核的负载均衡？c）在多核环境下，存储器成为了多个内核共享的临界资源，如何解决多内核系统存储器管理的问题？d）如何保证多个内核之间在任务处理过程中的同步？3.1多核操作系统的运行模式针对多核环境，一种很显然的操作系统运行模式是每个内核都运行同一个操作系统的镜像，从而使每个内核都能够工作起来。然而这种办法对于发挥多核技术的性能并不是很有利，CPU的内核数量会不断增加，内核的异构性也是一大发展趋势，传统的操作系统并不能够适应多核 技术的高速发展

11、。因此，有一些新的操作系统运行模式被提出。主从式（master-slave）多核操作系统模型15，如图1所示。这种模型为多核的负载均衡以及资源管理问题带来了一个新的思路。其主要思想是系统总是从一个主内核启动，主内核负责整个系统的初始化以及创建其他的从内 核。运行过程中，只有主内核能够访问系统的所有资源，如果从内核要对系统资源进行访问， 必须通过主内核。从内核只能执行自己的用户程序，并且可以直接访问自己的高速缓存，从内 核之间的通信需要通过主内核完成。coreOcore23coieNIc&che LIcache LIcache Llk*Icache LI111*bzihE 臣cache Tj2|

12、cacheschedulerserversIcachc L2shorttermMchcduJKrnrtterm-hsiDHll 片|prkemd3| L-kwnd图1主从式多核操作系统模型在解决多内核的异构性方面，文献16提出了一种新的操作系统模型multikernel，其结构如图2所示。这种模型中的每个内核都运行自己的操作系统，更好地支持了内核的异构性。同时 multikernel继承了分布式系统的思想，将各个内核作为独立单元，而这些单元组成一个网络”，这种模型带来更好的模块化性能，而且使得分布式“网络”中的内核通过消息传递进行通信。算法可以直接应用到多内核系统当中。图 2 Multiker

13、nel3.2内核的管理与调度如何通过恰当的调度机制和策略保证多核的负载均衡，并充分发挥各个内核的性能特点、 提高整个系统的吞吐量和实时性，是多核操作系统研究中的核心问题。当前关于多核的任务调 度机制主要有全局队列调度、局部队列调度和共生队列调度 17三种方式。a）全局队列调度是指操作系统维持一个全局的任务等待队列，当任意内核出现空闲时，就从任务等待队列中取出任务执行，这样的好处是保证了各个内核的利用率。由于全局队列调度 实现相对简单，也能够在一定程度上保证多个内核的充分利用，目前多数的多核操作系统采用 的是全局队列的任务调度机制18。b）局部队列调度是指操作系统为每个CPU内核都维护一个局部的

14、任务等待队列，每个内核都从自己的任务等待队列中取出任务执行，局部队列调度的优点是任务基本上无须在各个内核之间进行切换，这样就提高了内核缓存的命中率，但缺点是内核的利用效率较低。c）共生队列调度的思想是将访问共享资源较多的任务和访问共享资源较少的任务调度到 同一时刻执行，从而最大程度地减少资源冲突的可能性。在任务调度策略上，已有的操作系统调度算法如先来先服务（FCFS）、短作业优先（SJF）、优先级调度、时间片轮转（RR）、多级队列调度以及多级队列反馈调度等均适用于多内核的系统 中。但是旧有的调度算法一个普遍的特点是算法的关注点是任务，因为这些算法的产生都是基 于单处理器的条件下，而在多内核系统

15、中，不仅任务是多样性的，需要不同的调度策略，而且 内核也是多样性的。为了充分利用内核的重复性或多样性，更好地发挥多内核系统的性能，出 现了一些新的针对多内核系统的调度思想或算法。更快内核优先调度（faster core first scheduling）算法的主要思想是让性能更好的内核优先执行任务，而且允许线程动态迁移到更快内核上执行。这种算法的使用需要考虑到系统的负载均 衡以及线程迁移的开销预测。针对异构多核的特点，文献19 提出了动态的调度策略优于静态调度的观点，并通过动态的调度算法对其进行了验证。动态调度更符合运行线程状态会动态变化 的特点，而且动态调度能够最大限度地利用异构内核中性能较

16、高的内核。文献20 提出了一种针对异构多核的自适应性能优化算法 RL( reinforcement learning) ，其算法的思想是根据系统状态 的不断变化，系统能够不断地学习并找到更优化的任务调度策略。文献 21 指出一些基于动态性 能监测的异构多核调度策略在内核数量和异构性增加的情况下会产生局限性，提出了基于任务 本身对内核进行任务分配的想法， 即对应用程序添加体系结构签名 ( architectural signatures) ，而 系统通过签名的不同，将不同特点的任务分配给不同的内核执行。存储器管理 虽然多核技术使得更多的任务可以同时进行，但是对于内存的访问始终是整个系统性能提 升

17、的瓶颈 22 。多内核系统中，内存带宽是共享的，这使得内存成为了临界资源，于是带来了存 储器延迟、系统复杂性、饥饿等问题。另外，根据多核体系架构的不同，还可能带来 cache 的 管理问题。传统的存储器管理策略如虚拟存储器、分页存储管理、分段存储管理、段页式存储 管理仍可用于多内核系统中。但是，在新的多核架构下，应该寻找可以改善旧有的存储器管理 方式的办法，甚至推翻旧有的思路，建立起新的存储器管理机制。内核同步 多内核系统中，代码可以在多个内核上同时执行，这意味着如果不对线程进行同步，就有 可能发生各个线程之间相互覆盖共享数据的情况，造成访问数据处于不一致的状态，这是使系 统不稳定的一大隐患。

18、为了解决这一问题，自旋锁、读写锁、屏障锁、信号量、邮箱、消息 等数据结构都可以被同步机制利用，实现内核的同步。对于多内核系统来说，一个理想的同步机制包括以下五个特点 23:细粒度 ( fine-grain) 。一个并行计算系统所能够达到的并行程度，受限于同步的粒度 ;低延迟 ( low-latency) 。同步机制带来的延迟相对于执行时间要少 ;自由竞争 ( contention-free) 。一个理想的同步机制应该允许不同的运行元素自由竞争 ;可扩展性 ( scalability) 。随着系统内核数量的增长，同步机制也可以进行扩展 ;灵活性 ( flexibility) 。同步机制应当独立于

19、应用程序而存在。 文献 24指出了传统同步机制 在延迟、 资源竞争和同步粒度等方面的问题， 回顾了一些典型同步机制 ( cache and register-based、 transactional memory 、 synchronization buffer 25 、synchronized pipelined parallelism model 26) ， 同时指出了这些同步机制在多内核系统中存在的问题。最后，作者提出了一个自己的解决方案 RSF(request-store-forward) ，并验证了这种方案在多内核系统中符合理想同步机制的五个特点。第四章 一种异构多核处理器操作系统的

20、设计提出了一种适用异构多核处理器HMP27 的多主模式实时操作系统构架。 这种构架将通信总线中的多主模式引入多核操作系统构架中 , 采用对称式结构及组件模式设计操作系统模型 , 使 多核处理器中每个内核都可以作为主核实现对资源、 任务的实时管理 , 提高系统性能 , 同时可以 解决主从式操作系统存在的由于处理器核增多而带来的主内核不能满足系统性能要求的瓶颈问 题。4.1 HMP 构架参考模型对于 HMP 来说 , 主要存在两种不同的处理器构架 , 一种是完全异构的多核处理器 , 这种处 理器的不同核在构架、 时钟频率、 指令等方面存在差异 , 在不同的处理器核上程序的运行方式、 指令的多少、存

21、储方式、运行时间等可能不同，如：TI的OMAP系列、MS320DM644X SoC等；另 外一种是部分异构的多核处理器 , 这种处理器中存在多种构架的处理器 , 每种相同构架的处理 器核有多个 ， 一般主处理器核和从处理器核存在异构性 ， 因此在这种多核处理器中只有局部是 同构的 ， 而总体上是异构的 ， 如 IBM CELL 。为了更好地利用各个处理器核和使其协调工作， 未来的 HMP 除了采用共享内部高速总线访问共享设备外 ， 一般还设计了用于核间消息传递的专 用总线和外设 ， 各个处理器配置有核间通信接口模块用于通信 ， 这种总线与高速总线结合 ， 对 于数据量较大的数据交互通过高速总线

22、进行传递 ， 然后通过核间通信总线发送消息通知相应的 处理器核 ， 同时可以采用中断机制 ， 使消息快速响应 ， 从而实现消息数据的实时交互 28。因此我 们主要是针对第二种异构多核处理器进行操作系统的设计。4.2 操作系统构架设计将操作系统内核分为单主内核和多主内核 ， 采用统一构架 ， 只是存在功能不同。 每个处理器 核运行一个操作系统内核 ， 根据处理器核功能的需要配置内核 ， 异构核中采用单主模式 ， 在同 构核中采用对称多主模式 29。在不同构架的核中的操作系统内核可以在功能上存在差异，以满足处理器核的需要 ， 同构核中的每个内核可以作为主内核来管理资源和任务调度， 以消除单主核模式

23、中由于处理器核增多带来的主核负载瓶颈问题。在单核操作系统中， 内核负责任务管理、资源管理、 中断管理、 事件处理及通信管理等工作。 在多核操作系统中 ， 这些功能同样具有 ， 除 此之外 ， 还包括核间通信与同步、核间任务调度管理、共享资源及设备管理等部分。构架根据功能将操作系统分为 4 个层次 ： 应用层 ( Application Lay er) 、操作系统内核 ( OS Ker nel) 、本地硬件抽象层 ( LH AL Local H ardwa re Abstract Lay er) 和全局板级支持包 ( GBSPGlo bal boa rd suppor t package) 。应

24、用层是各种用户程序集合。操作系统内核是操作系统核心部分，提供应用层编程调用接口、 任务管理、 任务调度、 设备管理、 通信与同步、 内存管理等功能 ， 在 内核中 ， 为了便于本地设备和共享设备统一管理 ， 通过虚拟设备管理模块将本地设备及共享 设备、本地任务及全局任务等部分统一映射到本地进行访问，如内存映射、 外设映射、 I/ O 映射、任务映射等 ， 内核通过虚拟设备层来访问各种资源时就像访问本地资源一样， 便于操作系统实现对全局和本地资源的统一。管理访问共享设备与本地设备、核间通信与核内通信及任务调度 是虚拟设备层的主要功能。 而 LHAL 主要是各个处理器核本地硬件及其外设的抽象层 ,

25、 可屏蔽本 地通用硬件特性。 异构核虽然存在结构上的不同 , 但可共享一些资源 , 如内存、外设等 , 因此 , 设 计一个 GBSP 抽象通用共享设备、系统启动以及根据对应的内核配置信息将 OS 拷贝到各个处 理器核中。单主内核和多主内核采用相同的结构 , 只是在功能构成上存在差别。单主内核主要运行在 异构核上 , 与多主内核相比结构相同但功能存在差异 , 除了基本功能以外 , 还包括人机交互、控 制等功能 , 如文件系统、网络管理、 GUI 等功能 30 。由于单主内核和多主内核之间的处理器核 构架不同 , 因此 , 它们之间的任务不能实现动态调度 , 所以单主内核需要在运行前事先分配和

26、加载指定的任务 , 在本地进行任务调度。除此之外 , 当单主内核和多主内核任务进行同步时 , 还 需要对多主内核中的任务进行调度管理 , 因此还需设计一个全局调度模块。如果单主内核需要 与多主内核的任务进行通信和同步 , 可以通过通信与同步功能模块与虚拟设备管理共同实现,这种操作系统模型采用统一结构的内核 , 通过功能配置为单主内核和多主内核 , 便于操作系统设 计和应用编程。多主内核一般运行在异构多核处理器的同构核中 , 单主内核相比少了人机交互 和控制等功能模块 , 主要负责同构核间的任务调度与管理、共享设备管理、共享内存管理以及 核间通信与事件处理等功能。多主内核的每个核中都有这些相同的

27、模块 , 相当于将传统的一个 操作系统内核简化后分布在各个同构核中实现 , 以实现内核功能的分布式处理 , 降低对某一个 处理器核的依赖性 , 提高任务调度的实时性。第五章 结束语多核技术的快速发展给操作系统的研究带来了重大的挑战和机遇。从当前的情况来看，在 多核技术方面的研究，操作系统的发展大大滞后于半导体技术，而作为一个技术系统，没有操 作系统的支持，硬件资源的简单叠加无法最大限度地发挥其功能，实际上是一种资源的浪费。 依照目前多核处理器发展的速度来看，随着多核处理器技术的成熟和广泛应用，必定会带来多 核操作系统的需求 ; 而且随着多核处理器的逐渐复杂化和异构化，多核操作系统的研究范围也

28、将变得更加广泛。目前对于多核操作系统的研究方法主要集中在以下三个方面: a) 改进传统操作系统的一些研究成果，以适应多核的体系结构， 这也是应用最为广泛的研究方法 ; b) 在多核的体系结构下， 引入一些其他领域的研究成果，如面向对象和分布式系统的思想; c) 重新针对多核系统设计新的操作系统解决方案， 如前面提到的针对 TriBA 多核结构而提出了新的存储器体系结构 HSM 和 新的存储器访问机制 FDP。无论哪一种方法，目的都是为了解决多核技术给操作系统带来的新 的要求和问题，并没有优劣之分，在多核操作系统的研究过程中，需要根据实际的研究对象选 择恰当的研究思路。虽然在过去的一段时间里，计

29、算机的性能已经有了让人吃惊的飞速提升， 但是人们对于计算机的性能需求并没有得到满足，而多核技术作为目前公认的提升计算机性能 的发展方向，必将在计算机的发展历史上扮演重要的角色。多核操作系统作为多核技术的重要 部分，需要引起更多的重视，进行更为深入的研究，以保证多核技术的持续发展。参考文献GEER D.Chip makers turn to multicore processorJ IEEE Computer， 2006， 38( 5) : 11-13 WULF W， COHEN E， CORWIN W, et al. HYDRA: the kernel of a multiprocessor

30、operating systemJ.Communications of ACM ， 2009， 17( 6) : 337-345JONES A K，CHANSLER R，JDURHAM J R I，et al StarOS: a multiprocessor operating system for the support of task forcesC/ /Proc of the 7th ACM Symposium on Operating System Principles NewYork: ACM Press， 2008: 117-127 KAHN K C， CORWIN W M， DE

31、NNIS T D，et al. iMAX: a multiprocessor operating system for an object-based computerC/ /Proc of the 8th Symposium on Operating System Principles 2009: 127-136CAMPBELL R， JOHNSTON G，RUSSO V Choices ( class hierarchical open interface for custom embedded systems) J ACM Operating Systems Review， 2009，

32、21( 3) : 9-17SCHWAN K， GOPINATH P，BO W CHAOS: kernel support for objects in the real-time domainJ IEEE Trans on Computers， 2007， C-36( 8) : 904-916MUKHERJEE B，SCHWAN K，GOPINATH P A survey of multiprocessor operating system kernels ， GIT-CC-92 /05J Atlanta: College of Computing ， Georgia Institute of

33、 Technology ，2006 MOORE R， NAASI I， NEIL J O，et al The encore multimax: a multi-processor computing environment ，ETR 86-004J FortLauderdale: Encore Computer Corporation ，2008MILLIKEN W et al Chrysalis programmer s manual version 2 2R: BBNLaboratories2006 BRYANT R ， CHANG H Y， ROSENBURG B Experience

34、developingthe RP3 operating systemJComputing Systems， 1991 ， 4( 3) :183-216 Nakajima,T Kinebuchi,Y Courbot,A Shimada,H Tsung-Han Lin Mitake,H.Composition Kernel:A Multi-core Processor Virtualization Layer for Highly Functional Embedded SystemsA.In:Dependable Computing (PRDC), 2010 IEEE 16th Pacific

35、Rim International Symposium onC.Japan,2010,223-224.Vallina,F.M Jachimiec,N Saniie,J.Multiprocess and operating system design for signal processing on an FPGAA.In: Electro/Information Technology, 2007 IEEE International Conference on C.Chicago,2007,378-383.Ke Pei Gang Zhang Qing Chang.OS-Level IPC Im

36、plementation in Complementary Multi-processor SystemA.In: Wearable Computing Systems (APWCS), 2010 Asia-Pacific Conference onC.China,2010,74-77.Sindhwani,M Srikanthan,T.Framework for Automated Application-Specific Omptimization of Embedded Real-Time Operating SystemsA.In: Information, Communications

37、 and Signal Processing, 2005 Fifth International Conference onC. Singapore,2005,1416-1420.Tomiyama,H Honda,S Takada,H.Real-time operating systems for multicore embedded systemsA.In: SoC Design Conference, 2008. ISOCC 08. InternationalC.Japan,2008,I-62-I-67.Bilavarn S., Belleudy C., Auguin M.et al, E

38、mbedded Multicore Implementation of a H.264 Decoder with Power Management ConsiderationsM, 2008: 124-130.Youngho Ahn, Young-Si Hwang, Ki-Seok Chung, Flexible framework for dynamic management of multi-core systemsM, 2009: 237-240.Ning Hou, Duoli Zhang, Gaoming Duet al, Improved on-chip communication architecture for multi-core embedded systemM, 2010: 343-346.Bini E., Buttazzo G., Eker J.et al. Resource Management on Multicore Systems: The ACTORS ApproachJ. Micro, IEEE, 2011, 31（3）: 72-81.Su A. P., Kuo J., Kuen-Jong Leeet al, Multi-core software/hardware co-debug pla