（计算机科学与技术专业论文）基于ccnuma的资源配置技术研究与实现.pdf

国防科学技术人学研究生院学位论文 摘要 非一致存储访问( n u m a ，n o n u n i f o r mm e m o wa c c e s s ) 是目前高性能服务器的主流 体系结构之一。与s n i p 相比，n u m a 系统存在着存储器访问延迟不一致的问题，因此对 操作系统各方面有特殊的优化需求。 l i n u x 操作系统中为优化n u m a 系统性能进行的工作主要集中在内核层，例如不连续 内存支持、a c p l 支持、页迁移和页复制技术以及页配置技术。本课题从用户层的角度出 发，借鉴了s g i 的c p u m e m s e t s ，提出资源配置的思想。资源配置技术主要面向特权用户 和应用程序，指定任务调度和内存分配到特定的系统资源( 处理器、存储块等) 上，实现 了局部资源调度。 本文首先介绍了课题相关背景知识和各种n u m a 存储优化技术，然后提出了资源配 景的思想，阐述了资源配置技术的基本原理，并详细分析了l i n u x 操作系统中资源配置技 术c p u m e m s e t s 的实现机制，发现c p u m e m s e t s 缺少系统资源拓扑信息等决策信息指导配 置的缺陷。针对这种不足，分别从内核层和用户层两个方面进行改进和优化。 在内核层方面，提出并实现了一种基于n u m a 拓扑结构的分级调度算法。该算法从 内核任务调度方面加强操作系统对n u m a 的支持，较好地实现了具有结点亲近能力的 n u m a 调度，提高了数据访问的局部性。 在用户层方面，提供了用户可用的用户级库函数，并提出了具有多种决策信息指导的 资源配置策略，有效解决了用户由于不能感知资源拓扑信息而做出不当配置选择的问题。 最后，通过在s m p 机器上模拟了n u m a 环境并得出实验结果，验证了资源配置技术 和具有结点亲近能力n u m a 调度的有效性和可用性。 关键词：n u m a ，资源配置，拓扑信息，分级调度。决策信息 国防科学技术大学研究生院学位论文 a b s t r a c t n o w a d a y s ，n u m a ( n o n u n i f o r mm e m o r ya c c e s s ) b e c o m e st h em a i n s t r e a ma r c h i t e c t u r e i nt h eh i g hp e r f o r m a n c es e r v e r , c o m p a r ew i t hs m p , n u m ah a sac h a r a c t e r i s t i co fd i f f e r e n t m e m o r ya c c e s sl a t e n c y , a n dh a sas p e c i a lo p t i m i z er e q u i r e m e n t t oo p e r a t i o ns y s t e m l i n u xo p e r a t i o ns y s t e m sw o r kc o n t e n t r a t e so nt h ek e r n e li no r d e rt oo p t i m i z et h e p e r f o r m a n c eo fn u m a ，f o ri n s t a n c e ，t h es u p p o r to fd i s c o n t i gm e m o r y , t h es u p p o r to fa c p i ， p a g em i g r a t e ，p a g er e p l i c a t ea n dp a g ep l a c e m e n t f r o mt h ep o i n to f v i e wo fu s r - l e v e l ，o u rw o r k p u t sf o r w o r dt h ec o n c e p t i o no fr e s o u r c ep l a c e m e n t ，i tp l a c e st a s ks c h e d u l i n ga n dm e m o r y a l l o c a t i o no n t os p e c i f i cs y s t e mr e s o u r c e s ( p r o c e s s o r sa n dm e m o r yb l o c k se t c ，) f o rr o o tu s e ra n d a p p l i c a t i o n f i r s to fa l l ，t h i sp a p e ri n t r o d u c e st h ec o r r e l a t i v eb a c _ k g r o u n dk n o w l e d g eo fo u rw o r ka n da l l k i n d so fm e m o r yo p t i m i z a t i o nt e c h n o l o g yf o rn u m a ，t h e nb r i n g sf o r w o r dt h ec o n c e p t i o no f r e s o u r c ep l a c e m e n ta n di t sf u n d a m e n t a l ，a n a l y z e st h ei m p l e m e n tm e c h a n i s mo fc p u m e m s e t s o nl i n 峨o p e r a t i o ns y s t e m ，a a do b s e r v e sc p u m e m s e t s sf a u l to fl a c ko ft h es y s t e mr e s o l l i c e s t o p o l o g yi n f o r m a t i o n t h u s ，o u rw o r kc o m m e n c e s o nk e r n e l l e v e la n du s e r l e v e lr e s p e c t i v e l yf o r i m p r o v e st h ep e r f o r m a n c eo fs y s t e m 。 o nk e r n e l _ l e v e l ，w ep r e s e n tah i e r a r c h i c a ls c h e d u l i n ga l g o r i t h mb a s eo nn u m a t o p o l o g y , w h i c hi ss t r e n g t h e n st h eo p e r a t i o ns y s t e m sn u m a s u p p o r tf r o mt h ea s p e c to f t a s ks c h e d u l i n gi n k e r n e l ，a n dr e a l i z e sn u m aa f f i n i t ys c h e d u l i n g ，i m p r o v e sd a t aa c c e s sl o c a l i t ya n ds y s t e m p e r f o r m a n c e o nt h eo t h e rh a n d ，w ep r o v i d eu s a b l ec p u m e m s e t su s e r - l e v e ll i b r a r y , a n dp r e s e n ta m u l t i d e c i s i o n - m a k i n gi n f o r m a t i o ng u i d e dr e s o u r c ep l a c e m e n tp o l i c y , t h i sp o l i c yr e s o l v e st h e p r o b l e mo f i m p r o p e rp l a c e m e n tb e c a u s eo f i g n o r a n to f t o p o l o g yi n f o r m a t i o ne f f i c i e n t l y f i n a l l y , v a l i d a t e st h eu s a b i l i t ya n dv a l i d i t yo fr e s o u r c ep l a c e m e n tt e c h n o l o g ya n dn u m a a f f i n i t ys c h e d u l i n gb ys i m u l a t e sn u m a e n v i r o n m e n to nas m pm a c h i n e k e y w o r d s ：n u m a ，r e s o u r c ep l a c e m e n t ，t o p o l o g yi n f o r m a t i o n ，h i e r a r c h i c a ls c h e d u l i n g ， d e c i s i o n - m a k i n gi n f o r m a t i o n 国防科学技术大学研究生院学位论文 国防科学技术大学研究生院学位论文 表目录 表3 1 子进程h o m e 结点选择方式 表4 1s r a t 中的c p u 和内存段信息， 表4 2 新旧o ( 1 ) 调度算法比较 表4 3 平均执行时间比较 表5 1 c p u n o d e 映射关系表 表5 2 远程访问一个字的延迟时间 表5 3o r i g i n 2 0 0 0 访问存储器的延迟时间 2 3 2 8 3 6 3 7 4 3 4 7 4 8 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：基士g 二! 女坠的瓷塑壅量挂盎丛究皇塞理 学位论文作者签名：盔至 日期： 砌年l 月m 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构迭交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书) 学位论文题目：基= ! ! 坠曲资逻螯星撞查婴容量塞理 学位论文作者签名：盘垦 作者指导教师签名：翌玉 日期：z 妒毕年f 月j d 日 日期：炒年，上月，口日 国防科学技术大学研究生院学位论文 第一章绪论 随着大规模分布式共享存储器系统的蓬勃发展，存储性能优化一直是值得深入研究的 热点问题【1 】【2 1 。为了解决c c n u m a ( c a c h e c o h e r e n tn o n u n i f o r mm e m o r ya c c e s s ) 系统 中不同结点存储访问延迟不一致的问题，需要采用各种存储优化技术来开发提高数据访问 的局部性，达到改善系统性能的目的。我们提出的资源配置技术正是着眼于这需求，是 存储优化技术之一。 本章主要介绍了课题研究的背景和意义、研究现状、研究内容、研究成果以及论文的 组织安排。 1 1 课题研究背景与意义 按照f l y n n 分类法，根据计算机中指令和数据的并行状况可把计算机分成单指令流单 数据流( s i s d ) 、单指令流多数据流( s i m d ) 、多指令流单数据流( m i s d ) 和多指令流 多数据流( m i m d ) 四类。目前，m i m d 显然已成为多处理机体系结构的选择，并且可把 现有的m i m d 机器分为两类，分别称为集中式共享存储器结构( c e n t r a l i z e ds h a r e d m e m o r y a r c h i t e c t u r e ) 和分布式共享存储器结构( d i s m b m e ds h a r e d m e m o r ya r c h i t e t u r e ) ，每一类 代表了一种存储器的结构和互连策略。其中，非一致存储访问( n u m a ) 属于分布式共享 存储器结构一类j 。 由于科学计算、事务处理对计算机性能要求的不断提高，对称多处理器( s m p ) 系统 的应用越来越广泛。规模也越来越大。但是，传统s m p 系统中所有处理器都共享系统总 线，因此当处理器的数目增大时，系统总线的竞争冲突加大，系统总线将成为瓶颈，所以 目莳s m p 系统的c p u 数目一般只有数十个，可扩展能力受到极大限制。n u m a 系统同 时结合了s m p 系统易编程性和分布式存储系统高可扩展性的优点，已成为当今高性能服 务器的主流体系结构之一】 6 】。 图1 1c c n u m a 体系结构 第i 页 国防科学技术大学研究生院学位论文 如图1 1 所示，为了解决存储一致性问题，s g i 采用高速缓存一致性( c a c h ec o h e r e n t ) 技术，使碍远程数据能够进入本地c a c h e ，减少远程访问的频率。这种结构称为c c n u m a 体系结构。 c c n u m a 系统具有如下特征： 1 访问时间依赖于数据在存储器中的存放位置。存储器在物理上是分布的，即内存 模块分布在各个结点上，并通过高速互联网络互连。 2 单一内存地址空间。尽管内存模块分布在各个结点上，但是所有的内存模块都由 硬件进行统一编址，易于编程。 3 通常采用基于目录的c a c h e 一致性协议来保证各结点的局部c a c h e 数据和存鳍器 中数据的一致性。 4 提供对多种并行编程模式的支持。 c c - n u m a 系统在性能、灵活性、可用性方面都能适合用户多种应用的要求，它已成 为当今主流的体系结构，在科学计算和商业服务等领域有着良好的发展前景，是今后几年 大型服务器发展的重要方向1 7 】【引。典型的c c n u m a 系统包括c o n v e x 的e x e m p l a r ，h p v 2 6 0 0 n u m a 系列，i b m 的n u m a q 和s g i 的o r i g i n 系列。 由于远端数据访问必须通过高性能互联网络访问远程结点内存模块，而本地数据访问 只需要直接访问局部内存模块，使得远程主存访问延迟远高于本地主存访问延迟，产生了 多个处理器共享同一存储单元的存储不一致性问题1 9 【l o j 。并且，由于n u m a 系统各个结点 的c a c h e 只能缓存本地数据或私有数据，使得数据局部性成为影响系统性能的主要因素， 因此有必要开发各种存储优化技术来优化n u m a 系统性能。 l i n u x 操作系统中为优化n u m a 系统性能进行的工作主要集中在内核层，例如不连续 内存支持、a c p l 支持、页迁移和页复制技术以及页配置技术。本课题从用户层的角度出 发，借鉴了s g i 的c p u m e m s e t s ，提出资源配置( r e s o u r c ep l a c e m e n t ) 的思想。资源配置 技术通过强制在某个资源子集中进行进程调度和内存分配，实现应用程序的局部资源调 度。 合理的资源配置一方面部分消除了多个应用程序在同一处理器上运行的c a c h e 相关 性，降低了结点间通信、同步和负载不平衡等_ 丌销；另一方面也减少远程结点数据访问次 数，缩短访问距离，从而有效减少了远程存储访问延迟，提高了数据访问的局部陛。 1 。2 课题研究现状 如图1 2 所示，操作系统中多个进程共享一个全局虚拟内存，通过统一的内存管理系 统进行数据访问，数据访存时如果出现页失效，首先访问本地( 结点内) 地址空内存间， 然后再访问远程( 结点外) 地址空间内存。 虽然c c n u m a 系统在硬件上提供c a c h e 的一致性维护和全局地址空间的访问，但仍 然存在着结点间不同存储访问延迟的特性，即访问本地结点存储器的速度要快于访问远程 第2 页 国防科学技术大学研究生院学位论文 结点存储器，因此远程结点数据访问必然带来相当多的系统性能开销，严重影响了系统性 能，所以提高数据局部性成为c c - n u m a 系统存储优化的重要内容。 图l 。2c c - n u m a 系统的远程存储访问 为了充分利用c c n u m a 系统良好的局部性和可扩展性特点，国内外很多学者和研究 机构致力于研究和探索在l i n u x 操作系统中更好的支持n u m a 系统的这种特性。 目前，l i n u x 操作系统中c c - n u m a 系统存储优化技术主要有如下几种： i ) 页迁移( p a g em i g m t e ) 和页复g 0 ( p a g er e p l i c a t e ) 技术 页迁移和页复制技术的原理是：如果一个远程结点频繁地访问本地结点的某页，则利 用本地结点内存中的页访问计数器计数，由一个竞争算法自动地决定是否迁移或复制这页 i t 8 1 19 1 【2 0 1 【2 1 1 。页迁移与页复制是对数据进行动态局部性优化的主要方法之一，其实质是- - t o e 预测技术，根据收集到的信息预测将来对页面的访问情况，然后作出迁移或复制页面的决 策。采用适当的页复制与页迁移策略可以减小c a c h e 容量和冲突失效，平衡远程和本地访 问延迟的不一致，达到优化n u m a 系统性能的目的。v e l ! g h e s e 等人提出了面向c c n u m a 系统和c c n o w 系统内核页迁移和页复制技术实现机制【4 ，对我们的工作非常有借鉴意 义：b a y l o r 等人提出了一种l a z yh o m em i g r a t i o n 的动态宿主结点迁移技术1 1 6 1 ，使得页迁移 和页复制都变成了局部行为，但需要较多的硬件支持；n i k o l o p o u l o s 等人提出了用户级动 态页迁移机制以进程迁移或抢先为触发，具有较好的准确性和及时性，但他们的实现是在 用户级运行时间库“。 虽然页迁移和复制技术有效地减少了远程结点存储访问延迟带来的访问开销，降低了 本地结点的c a c h e 失效率，但实际操作系统的动态页迁移和页复制实现并没有期望中有效 1 2 2 1 。除了需要硬件的c a c h e 一致性保证和访问计数器等硬件开销外，操作系统的不具备通 用性( 及时性和精确性不同) ，以及页迁移和页复制决策信息的收集和处理带来了额外的 第3 页 国防科学技术大学研究生院学位论文 软件开销都严重影响了系统性能的提升，因此不少研究人员开发了页配置技术。 2 ) 页配置技术( p a g ep l a c e m e n t ) 页配置技术是另外一种存储优化技术，它采用页迁移和页复制技术不同的策略。 m a r c h e t t i 研究了在硬件或软件保证c a c h e 一致性的情况下，简单行为驱动页配置策略对性 能的影响【7 ”。他发现，对那些负载较轻的应用程序，通过允许局部内存的容量失效减少失 效开销，动态页配置技术相对于动态页迁移和页复制技术，即使非常简单的配置策略也能 获得更高的性能，而且设计有效页配置策略时不需要复杂硬件支持。s a r a ha m t a l b o t 和 p a u lh j k e l l y 的研究表明，当多个结点同时访问一个宿主结点( h o m en o d e ) 的数据时，使用 不恰当的方式选择宿主结点的页配置机制严重降低了应用程序的性能，同时，现有的两种 选择方式“f i r s t t o u c h ”方式和“r o u n d r o b i n ”方式并不能满足所有应用程序的需求 2 3 1 。 于是，他们提出利用代理机制来减少对宿主结点的竞争，如图1 3 。代理是标准分布式目 录c a c h e 一致性协议的扩展，为减少结点控制器竞争而设计。通常，读请求消息根据其需 要访问的物理页地址送到宿主结点位置，有了代理作为中介，个读请求就能有指导地更 替到不同的结点控制器。如何划分代理子集是通过实验而来，取仿真系统中代理结点竞争 和整合程度之间的最优平衡。每个到代理结点的数据块映射确保了后继数据块的请求由不 同代理服务，这样又平衡了通过所有结点控制器输入缓冲栈的读请求消息队列，即各结点 的负载平衡。 ( a ) 没有代理节点时( b ) 使用两个代理节点时 ( r e a dl i n e f ) 。o 尸。 弋。 。 。f 。 。 7 ；9 9do oo 。癍霉 渺i 。， 。 z 。 ：疋： 。7 。 ( c ) 谤入下一个数据块时 ( i f r e a dl i n e f + 1 ) 图1 3 通过代理机制减少宿主结点竞争 3 ) 资源配置( r e s o u r c ep l a c e m e n t ) 技术 资源配置技术主要研究如何合理的配置c c n u m a 系统资源，如何将资源配置信息和 系统拓扑信息反映给用户以及如何让应用程序在感知c c n u m a 体系结构的情况下达到更 优的运行性能等问题。纵观现有的资源配置技术中，为提供对n u m a 局部性优化和支持 雨开发的各种程序和补丁，我们大致可以分为三类： 最常见的做法。程序或补丁试图在应用程序无法感知n u m a 存在的前提下提高由 n u m a 硬件支持的l i n u x 操作系统的性能和可用性，从l i n u x 内核2 5 版本丌始采用的与 蛸4 虻 国防科学技术火学研究生院学位论文 n u m a 相关的o ( 1 ) 调度器正是这种做法。但是，由于无法感知n u m a 体系结构的具体拓 扑信息，o ( 1 ) 调度器并不能真正开发n u m a 数据局部性。为了给n u m a 系统提供良好的 支持，l i n u x 操作系统有必要在许多方面进行调整，以使新模型更具效率。例如，建立一 个内部拓扑a p i ，以使内核知道处理器和内存以及其他i o 设备间的相互关系。有了内部 拓扑a p i 的支持，l i n u x 操作系统的o ( 1 ) 调度器可以理解这些关系，并且会尝试优化应用 程序的任务以达到最佳的本地资源使用。 简单绑定。程序或补丁允许简单的手动控制处理器和内存配置。如i b m 的n u m a q 中内核级n u m a 的a p i 设计。 抽象绑定。程序或补丁允许更抽象的复杂应用程序元素和底层硬件资源关联的描述， 这种方法能具体到面向内核、进程和虚存区完成资源配置，如s g i 的c p u m e m s e t s 2 4 i c p u s e t 等。 另外，还开发了一些n u m a 相关的a p i 工具： d l o o k 命令能显示指定进程的内存映射和c p u 使用的详细信息，例如给出进程的 名称( p e e k ：s l e e p ) 、进程i d 号、唤醒的时间和同期以及内存映射信息等，提供 所有用户和系统进程c p u 占用时间( s ) 。另外，它可以显示m p i 程序每个线程的 内存映射。 d p l a c e 命令允许用户指定一个进程到某个处理器上运行，能唤醒一个内核钩子 ( h o o k ) 函数p a g g 创建一个c p u m e m s e t s 的可配置资源容器( c o n t a i n e r ) ，任 务调度和内存配置策略由d p l a c e 命令的参数决定。 1 3 1 工程环境 1 3 课题简介 本课题来源于8 6 3 课题“服务器操作系统内核”( 2 0 0 2 a a l z 2 1 0 1 ) 及“操作系统新 技术研究”( 2 0 0 3 a a l z 2 0 6 0 ) 。结合工程需求，我们的具体实现基于i n t e l 的i a 6 4 处理 器和l i n u x2 4 1 8 - n u m a 内核。 i a - 6 4 是i n t e l 的6 4 位多处理器体系结构。它克服了传统体系结构的许多限制，并提 供了极大的可扩展空间，而l i n u x2 4 1 8 内核加上n u m a 补丁已经较好地实现了固件层支 持、不连续内存支持和0 ( 1 ) 调度算法等，有利于相关工作的展开【l l 】 2 5 1 1 2 6 】。 1 3 2 研究内容和主要成果 本课题的主要研究内容包括： 1 ) 研究和分析了c p u m e m s e t s 的实现机制并阐述了资源配置技术的基本原理。结论： c p u m e m s e t s 不仅能作为n u m a 系统资源管理的公共平台，而且有效的减少了结 第5 负 国防科学技术大学研究生院学位论文 点间存储访问延迟，提高了n u m a 系统的性能。 2 ) 深入分析了l i n u x 操作系统传统任务调度算法的工作流程，并简单介绍了新调度 算法o ( 1 ) 调度算法的优点以及对n u m a 系统的支持。 基于以上研究，我们取得以下成果： 1 提出了一种基于n u m a 拓扑结构的分级调度算法。该算法从内核任务调度方面加 强操作系统对n u m a 的支持，较好地实现了具有结点亲近能力的n u m a 调度， 提高了数据访问的局部性。 2 提供用户可用的c p u m e m s e t s 用户级库函数，主要包括c p u b i n d 0 、n o d e b i n d o 和 r h n o n o 等等。 3 提出具有多种决策信息指导的资源配置策略，决策信息包括系统资源拓扑信息、 系统负载信息等，并通过p r o c 文件系统反映给用户。 4 提供优化的初始化启动脚本。优化的初始化启动脚本根据决策信息的指导利用 c p u m e m s e t s 用户级库函数，设置默认的系统痦动资源子集。 5 由于缺少实际n u m a 环境的支持，我们在s m p 机器上模拟了n u m a 环境并得出 实验结果，验证了资源配置技术和具有结点亲近能力n u m a 调度的有效性和可用 性。 本课题的技术亮点有： 提出资源配置的思想，区别于资源调度和资源划分的思想 调度主要指处理器进程调度或页分配，属于动态的行为；配置多指强制性和约束性资 源划分，属于静态的行为。从概念上来蜕，资源调度和资源配置可以类比于页迁移页复制 和页配置。但是，为什么不是资源划分呢? 因为它和资源划分又有区别，划分的概念没有 配置的概念细，不会涉及到具体底层资源( 比如与进程、虚存区等的绑定) ，同时也缺乏 强制性的特征。 提出基于n u m a 拓扑结构的分级调度算法中采用量化的方法分析n u m a 调度 由于结点数目众多、拓扑结构复杂，负载平衡或结点调度的时候仅仅通过“奖励”措 施倾向于首先选择本地结点的处理器进行负载平衡和结点选择，缺乏量化的距离评估，已 经渐渐不能适应大规模n u m a 系统服务器的要求，基于n u m a 拓扑结构的分级调度算法 很好地解决了这个问题。 1 4 论文结构 全文共分为七章： 第一章绪论。介绍了课题的研究背景和研究现状，概述了针对c c - n u m a 系统特性 提出的存储优化技术，给出了课题的工程环境、研究内容以及主要成果。 第二章资源配置技术研究与分析。研究了资源配置技术的基本原理和实现机制，分 析了l i n u x 操作系统中c p u m e m s e t s 的内核实现机制，总结了c p u m e m s e t s 存在的不足并 第6 页 国防科学技术大学研究生院学位论文 提出改进设想。 第三章操作系统任务调度算法研究。首先分析了传统任务调度算法的基本流程和局 限性，然后介绍了o ( 1 ) 调度算法的优点和对n u m a 的支持a 第四章n u m a 任务调度算法设计与实现。基于0 0 ) 调度算法对n u m a 的支持部分， 提出了具有结点亲近能力的n u m a 分级任务调度算法，并给出具体实现方案。通过在s m p 机器上模拟n u m a 环境并得出实验结果，验证了具有结点亲近能力n u m a 调度提供了系 统访问局部性，在一定程度上提高了系统性能。 第五章c p u m e m s e t s 优化与实现。首先设计并实现了用户级库函数，然后针对资源配 置技术c p u m e m s e t s 用户指导不足等缺点进行了完善和改进，提出具有多种决策信息指导 的资源配置策略。最后，通过系统模拟，验证了资源配置技术的性能优势。 第六章结论与展望。总结了论文的主要工作，并对今后的研究进行了展望。 论文结构如图1 4 。 研究实现 l 第二章资源配置技术 第五章c p u m e m s e t s | 第 | 研究与分析 优化与实现 、 六 目 论 7 与 展 童 卜n 第三章操作系统任务1第四章n u m a 调度算 ， 望 绪 论 调度算法研究法设计与实现 图1 4 论文结构图 第7 负 国防科学技术大学研究生院学位论文 第二章资源配置技术分析与研究 目前，操作系统对大规模系统中各种资源进行有效管理成为一个非常活跃的研究领 域，资源配置( r e s o u r c ep l a c e m e n t ) 技术即通过强制在某个资源子集中进行进程调度和内 存分配，实现应用程序的局部系统资源调度和有效管理。同时，通过在内核中添加足够的 基本数据结构，提供基本a p i 函数，可以根据用户需求和应用程序需求，指定应用程序与 系统底层资源( 处理器、存储器等) 的亲近关系，减少存储访问延迟，提高系统性能。 本章首先阐述了资源配鼍技术的基本原理，然后详细分析了l i n u x 操作系统中 c p u m e m s e t s 的内核实现机制，最后总结了c p u m e m s e t s 存在的不足并提出改进设想。 2 1 资源配置技术的基本原理 在n u m a 系统中，由于单结点工作负载能力有限，在单结点中运行大规模并行科学 计算、大型数据库和网络通信等复杂应用程序会带来非常高的c a c h e 失效率，严重影响了 应用程序的正常运行，所以要求先将复杂任务分解为子任务，然后再将子任务分配到多个 处理器或者结点上运行。然而，n u m a 系统构造的特性使得应用程序的加速比随着处理器 或资源个数的增多呈下降趋势，而在较小的处理器或资源子集中运行复杂应用程序反而能 获得更高的资源利用率和系统整体性能1 2 7 1 。 对于大规模n u m a 系统，结点数目众多导致存储访问延迟不致的问题更加严重， 资源配置技术试图将进程调度和内存分配强制限制在一个系统资源( 处理器、存储块等) 子集中，然后采用某种简单资源配置策略使应用程序能在当前系统资源子集中进行局部资 源调度。根据采用资源配置策略的不同，该局部资源子集的划分呈现出不同的特性：或者 本着就近原则( 1 0 c a l ) 划分：或者采用平均分配原则划分。总之，合理的资源配置一方面 部分消除了多个应用程序在同一处理器上运行的c a c h e 相关性，降低了结点间通信、同步 和负载不平衡等开销；另方面也减少远程结点数据访问次数，缩短访问距离，从而有效 减少了远程存储访问延迟，提高了数据访问的局部性。 资源配置技术与资源调度有所不同，资源调度主要指处理器进程调度或页分配，属于 动态的行为：而资源配置强调强制性和约束性资源划分，属于静态的行为。从概念上来说， 资源调度和资源配置可以类比于页迁移页复制和页配置。同时，资源配置和资源划分又有 区别，资源划分虽然也是在某个资源子集中运行应用程序，但不会涉及到具体底层资源( 比 如与进程、虚存区等) ，也缺乏强制性的绑定操作。 2 2c p u m e m s e t s 简介 资源配置技术的典型实现是s g i 公司开发的c p u m e m s e t s a 钔。c p u m e m s e t s 不仅可以 作为n u m a 系统资源管理的公共平台，而且通过c p u m e m s e t s 的台理资源配置，可以有 第8 负 国防科学技术大学研究生院学位论文 效减少存储访问延迟，提高系统性能。 2 2 1 项目简介 c p u m e m s e t s 是s g i 公司的一个开放源码项目，2 0 0 1 年7 月2 日启动，主要项目成员 有：p a u lj a c k s o n ，s a m u e l0 r t i z ，j e r e m yb r o w n ，l i m i ng u 等。 1 设计目标： i 优化n u m a 体系结构下的l i n u x 操作系统性能 试 提供丰富的l i n u x a p i 和内核实现 n支持处理器和存储块的配置语义，能指定系统资源( 处理器、存储块等) 面向内核、任务以及虚存区的配置 i v 提供对o p e n m p 和m p i 等多种并行编程模式的支持 2 设计原则： v 为融入l i n u x 主流，提供“厂商中立”的内核a p i v i 遵循传统的内核用户界限 v 试 提供各种适用于主流l i n u x 内核版本的补丁 v i i i 尽量使用足够的、基本的、最少的原语 3 基本概念( 原语) i 处理器( c p u ) ：承载任务调度的物理处理器，不包括d m a 设备和向量处 理器等专用处理器。 试 存储块( m e m ) ：指n u m a 与s m p 和u p ( u n i p r o c e s s o r ) 最大的不同一 一分布式存储单元，不包括具有速度差异的特殊存储器，如i o 缓冲和帧 缓冲等。 i i i 任务( t a s k ) ：类似于操作系统中进程的概念，一个任务在任一时刻都只有 两种情况，或者在等待事件、资源和中断，或者正在处理器上运行。 i v 虚存区( v i r t u em e m o r ya r e a ) ：内核为每个任务维护的多个虚拟地址区域， 可为多个任务共享。虚存区的页或者没有分配，或者已分配但没被换出， 或者己分配且在内存中，可以指定允许分配给某个虚存区的存储块和分配 顺序。 v ， 结点( n o d e ) ：包括多种资源的集合，可以细分为多个子结点( s u b n o d e ) ， 从而组成超结点，是一个不稳定的概念。 2 2 2 基本数据结构及其关系 c p u m e m s e t s 的主要包括三个基本数据结构：c p u m e n u n a p 、c p u m e m s e t 和 c m s _ m e m o r y _ l i s t ，具体定义在i n c l u d e l i n u x c p u m e m s e t h 文件中。以一个包含四个节点的 第9 页 国防科学技术大学研究生院学位论文 n u m a 系统为例简单说明这三个基本数据结构的使用。假设每个节点由四个处理器和一个 内存块组成，1 6 个处理器的系统号依次是：c o 、c l 、c 1 5 ，4 个内存块的系统号依次是 r o b 0 、m b l 、m b 2 、r o b 3 。构造一个只包含第2 和第3 节点的处理器和内存块c p u m e m m a p ， 并且把某个应用绑定在奇数号的处理器上。同时以本地优先的方式分配内存块。数据结构 关系图如图2 1 所示：c p u m e m m a p 中的c p u s 和m e m s 域分别指向一组系统处理器号和一组 系统内存块号，实现应用的资源号( 数组下标) 与系统的资源号( 数组元素值) 的映射。 c p u r n e m s e t 通过c m r r l 域与相应的c p u m e m m a p 建立关联，c p u s 域指向一组应用处理器号， 而i t l e m s 域指向一组c m sm e m o r y 类型的内存块列表。每个内存块列表描述了一组应1ist t 用内存块号以及享有该列表的一组应用处理器号，内存块分配策略由c p u l i l e l n s e t 中的p o l i c y 域决定，缺省使用本地内存优先方式。 c m s _ m e m o r y i i s t 图2 、1基本数据结构关系 2 3c p u m e m s e t s 实现机制 根据资源配置技术的基本原理，c p u m e m s e t s 提出了一种面向c c o n u m a 系统的底层 资源管理方式。主要目的有两个，是作为n u m a 系统资源管理的公共平台，二是支持 第1 0 页 国防科学技术大学研究生院学位论文 底层资源面向内核、任务( 进程) 以及虚存区的配置，进而优化n u m a 系统性能。基于 此目的，c p u m e m s e t s 提供了一系列支持处理器和存储决配置语义的a p i 函数和实现，并 且提供对o p e n m p 和m p i 等多种并行编程模式的支持，研究分析表明，c p u m e m s e t s 具有 模块性、强制性、灵活性和隐蔽性的特点 2 8 】。 2 3 1 c p u m e m s e t s 的内核实现 内核实现是c p u m e m s e t s 资源配置的执行实体，它与传统资源管理方式有着明显的区 别：传统资源管理集中于将应用程序指派到某些适合调度的结点上去运行，而c p u m e m s e t s 支持底层资源的配置，即能指定具体的系统处理器和存储块面向内核、任务以及虚存区的 配置。 1 ) 内核c p u m e m s e t s 构成 内核层实现主要由四部分构成： 内核级a p i 函数：提供控制处理器和存储块面向任务、任务以及虚存区的资源配 置的a p i 函数。现有的内核级a p i 函数主要包括查询内核c p u m e m m a p 结构字节数、 查询内核c p u m e m s e t 结构字节数、查询当前内核、进程或子进程的c p u m e m m a p 和 c p u m e m s e t 、设置当前内核、进程或子进程的c p u m e m m a p 和c p u m e m s e t 。 c p u m e m s e t ( c m s ) ：位于c p u m e m m a p 之上的一层，负责说明允许把任务调度到哪 些应用处理器号所对应的处理器上以及可以从哪些与内核或虚存区相关的应用存 储块号所对应的存储块中为它们分配内存页。每个进程都拥有两个c m s ： c u r r e n tc r r l s 影响自己的处理器分配和虚存区创建，而c h i l dc m s 继承给自己f b r k 的子进程。每个新建进程的c u r r e n tc m s 和c h i l de m s 都继承自父进程的c h i l dc m s 。 c p u m e m m a p ( c m m ) ：提供系统处理器号和系统存储块号到应用处理器号和应用存储 块号的映射。资源的系统号供内核进程调度和内存分配时使用，资源的应用号供 应用程序操作c m m & c m s 时使用。系统号在启动期间全系统范围内有效，而应用号 仅仅相对于共享同一c r n m 的所有用户有效，由于负载平衡和热插拔引发的资源物 理编号变化对应用号是不可见的。c p u m e m m a p 中不允许有空洞，例如，假设 c p u m e m m a p 的大小为n ，则映射的应用号必须从0 到n 1 。 进程调度和内存分配：为了保证对现有的或将来的调度器和分配器代码的影响降 低到最小，l i n u x 内核采用了资源系统号到资源应用号的映射，以及特定的数据结 构( c p u sa l l o w e d 、m e m sa l l o w e d 和z o n e l i s t 等) 。c p u sa l l o w e d 和m e m sa l l o w e d 是t a s ks t r u c t 数据结构中的两个字段，位图中的某一位为1 就表示允许进程可接受 调度到系统处理器号相应的c p u 上运行或可从系统存储块号相应的存储块分配页 面。不管是进程调度还是内存分配时，首先就是判断c p u s 和_allowed m e m sa l l o w e d 是否满足要求。内核中还包括一种线程迁移机制，在操作系统启动的时候就为每 个处理器建立个线程迁移队列，当用户改变c p u位向量时，线程迁移机_allowed 第1 1 页 国防科学技术大学研究生院学位论文 制将发生作用。例如，当第i 位设为0 时，处理器i 的所有进程将重新选择合适的 处理器进行调度，但不是将所有进程次性调度某个处理器上，而是先将进程挂 入线程迁移队列，然后，负载平衡机制会选择合适的处理器在线程迁移队列中选 择合适的线程完成进程迁移工作。 2 ) 内核c p u m e m s e t s 处理流程 为提高应用程序在c c - n u m a 系统中的运行效率，用户请求对应用程序所需资源进行 合理配置，从而产生了资源配置请求。内核c p u m e m s e t s 处理资源配置请求的处理流程如 图2 2 所示。 c m n c n l s 禽h 0 设竭! 图2 , 2 资源配置的处理流程 用户级a p i 函数的参数( a r g u m e n t s ) 必须经过打包操作( p a c k e