（计算机系统结构专业论文）多核系统中的内存管理系统优化研究.pdf

摘要 摘要 多年以来，主流的处理器生产厂商用来提高处理器性能的传统方法如提升时 钟速度和指令吞吐量等，似乎已经走到了尽头。多核多线程已经成为当今处理器 发展的潮流和趋势。多线程( 如同时多线程s m t ) 能充分发挥单个内核的性能， 而多核能更好地发挥整个系统的性能。多核时代的来临，意味着处理器能有更低 的功耗，更强的效能，更高的并行性。多核技术的发展不仅是硬件行业的任务， 要从其中获得充分的效益，软件行业的共同进步是必不可少的，这意味着习惯了 在单核环境中编程的软件开发人员必须转变思想，拥抱变化，软件开发史上的又 一次重大变革不可避免地即将来临。 相比较单核处理器而言，多核对软件带来的挑战主要是多核能实现真正的线 程级的并行。要编写正确的高效的支持多核的软件，开发人员必须更小心地划分 私有数据和共享数据，并妥善解决共享数据可能产生的争用。本文探讨了多核处 理器的一些典型特征以及多核系统对软件带来的新的挑战。 操作系统作为计算机软件的核心，要使多核处理器的性能得到充分发挥，操 作系统必须要提供足够的支持。从软件角度来看，多核( 单芯片多处理器，c m p ) 与对称多处理器( s m p ) 几乎是一样的，那些提供了s m p 支持的操作系统同样可 以提供对多核的有效支持。 内存管理系统作为操作系统内核的核心组成部分之一，对整个系统的性能有 着决定性的影响。本文深入探讨了l i n u x 内存管理系统的框架，设计思想以及实现 细节，仔细研究了地址映射，物理页的分配和释放，内存管理区及伙伴系统，s l u b 系统，进程地址空间的分配和释放，页框的回收和交换等子模块的设计和实现。 本文提出了对s l u b 系统和伙伴系统在多核环境下的改进思路和方法。此外， 本文还对作为实现多核互斥基础的自旋锁提出了使用m c s 自旋锁的改进。 关键词：多核，内存管理系统，l i n u x ，s l u b ，伙伴系统，m c s 自旋锁 a b s tr a c t t h em a j o rp r o c e s s o rm a n u f a c t u r e sh a v e 砌o u to fr o o mw i t hm o s to ft h e i r t r a d i t o n a la p p r o a c h e st ob o o s t i n gp r o c e s s o rp e r f o r m a n c es u c h 嬲p r o m o t i n gc l o c ks p e e d a n dt h r u p u to fi n s t r u c t i o n s m u l t i c o r ea n dm u t l i t h r e a dh a v eb e c o m et h e t r e n do f d e v e l o p i n go fm o d e r np r o c e s s o r s m u l t i t h r e a d ( f o re x a m p l e ，s i m u l t a n e o u s m u l t i t h r e a d ) c a n g i v ef u l lp l a yt ot h es i n g l e c o r ep e r f o r m a n c e ，a n dm u l t i e o r ec a n b e t t e ro v e r a l ls y s t e m p e r f o r m a n c e t h ea p p r o a c ho ft h em u l t i c o r ee r am e a n st h a tt h ep r o c e s s o rm a yh a v e l o w e rp o w e r c o n s u m p t i o n ，b e t t e rp e r f o r m a n c e a n dh i g h e r p a r a l l e l i s m m u l t i c o r e t e c h n o l o g yd e v e l o p m e n ti st h em i s s i o nn o to n l yo f h a r d w a r ei n d u s t r yb u ta l s oo ft h e s o f t w a r ei n d u s t yt ot a k ef u l la d v a n t a g eo ft h eb e n e f i t s t h i sm e a n st h a tt h es o f t w a r e d e v e l o p e r sw h oa r ec u s t o m a r yi n t h es i n g l e c o r ep r o g r a m m m ge n v i r o n m e n tm u s t c h a n g e t h e i rt h i n k i n g ，e m b r a c ee h a n g e a ni m p o r t a n t r e f o r mo ft h es o f t w a r e d e v e l o p m e n th i s t o r yi si n e v i t a b l yc o m i n g m u l t i c o r ep r o c e s s o rb f i n g sm a n ye h a l l e n g e st os o f t w a r ed e v e l o p m e n tc o m p a r et o s i n g l e c o r ep r o c e s s o rb e c a u s ei sr e a l i z et h ec o m p l e t et h r e a dl e v e lp a r a l l e l i s m i no r d e r t od e v e l o pc o r r e c ta n de f f i c i e n ts o f t w a r et os u p p o r tm u l t i c o r e ，d e v e l o p e r sm u s tb em o r e c a r e f u ld e l i n e a t i o no fp r i v a t ed a t aa n ds h a r e dd a t e ，a n dp r o p e r l yr e s o l v et h ep o s s i b l e c o n t e n t i o no fs h a r dd a t e t h i st h e s i sd i s c u s s e ss o m et y p i c a lc h a r a c t e r i s t i c so fm u l t i c o r e p r o c e s s o r sa n dn e wc h a l l e n g e st h em u l t i c o r es y s t e mb r i n gt os o f t w a r e a st h ec o r eo fc o m p u t e rs o f t w a r e ，o p e r a t i o ns y s t e mm u s tp r o v i d ee n o u g hs u p p o r t t o m u l t i c o r ep r o c e s s o r st o “1 ye x e r tt h e i rp e r f o r m a n c e f r o mt h es o f t w a r ep e r s p e c t i v e ，也e m u l t i c o r e ( c h i pm u l t i p r o c e s s o r , c m p ) a n ds y m m e t r i cm u l t i p r o c e s s o r ( s m p ) a r ea l m o s t t h es a m e t h eo p e r a t i o ns y s t e m sw h i c hp r o v i d es m ps u p p o r ta l s op r o v i d ee f f e c t i v e s u p p o r tt om u l t i c o r e a sac o r ec o m p o n e n to ft h eo p e r a t i o ns y s t e m ，m e m o r ym a n a g e m e n ts y s t e mh a s d e c i s i v ei n f l u e n c eo nt h ep e r f o r m a n c eo fe n t i r es y s t e m t h i st h e s i sd e e p l ye x p l o r a t i o n i n t ot h el i n u xm e m o r ym a n a g e m e n tf r a m e w o r k ，d e s i g nt h e o r ya n di m p l e m e n t a t i o n 捌l s i ta l s od e e p l ym s e a r c ht h ed e s i g na n di m p l e m e n t a t i o no ft h e s es u b m o d u l e so f l i n u xi n c l u d i n ga d d r e s sm a p p i n g ，d i s t r i b u t i o na n dr e l e a s eo fp h y s i c a lp a g e s ，m e m o r y i i i j 塑坠l 一 ? a g 锄2 趵觚d h d d ys y s t e m ，s l u bs y s t e m ，t h ea l l o c a t i 。na l l dr e l e a s e o f p r o c e s s 训= 印岛蛾l a i m 撕叻a n d s w a p p i n go fp a g e s ，1t 1 ：廿1 。8 1 8 p p o m et h i n k i n ga n d m e 1 0 d 。fi m p r o v e m e n to ft h es l u bs y s t 锄 冀三，d d y s y s 锄h 廿1 em u l t i c o r ee n v i r o n m e n t f u 吡踟n 。r e , i t a l s 。p u tf 0 硒，a 二也e 了c ，s p i n l o c k 私也c i l n p r o v e m 姐t 。ft 1 1 e s p i n l 。c kw h a ti st l l ef o u n d a t i o n “o ft h e l m p l e i i l e n t a t i o no f m u l t i c o r e m u t u a l l ye x c l u s i o n k e y w 。r d s ：m u l t i c o r e , m e m 。r ym a n a g e m e n t s y s t e m ，l i n u x ，s l u b ，b u d d ys ”t e m ，m c s i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：城辞日期：沙听年月了e t 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：垒叁鱼导师签名： 套数似 日期：2 口q 年6 月弓e t 第一章引言 第一章引言 计算机体系结构，微电子工艺技术以及软件应用需求从来都是互相影响，互 相促进，共同发展的。随着超大规模集成电路技术以及计算机系统结构的迅猛发 展，计算机系统的性能和容量飞速增长。硬件性能的迅速提高使得计算机不断被 应用到更多的，要求更高的领域，使得许多以往难以解决的问题得以解决，同时 人们希望能用计算机来解决新的更难的问题。软件应用领域的扩大和深化又对硬 件提出了更高的要求，发过来促使硬件更快的发展，对计算机体系结构提出了更 多更高的要求。许多应用领域需要并行计算机体系结构，如科学和工程计算和高 端的商业计算等【l j 。 对于并行机系统来说，各处理器间的通信和协调问题是关键的技术问题。共 享内存的多处理器是并行系统中最重要的一种，这种体系结构的关键特性就是通 过内存访问指令实现处理器之间的通信和协调。如对称多处理器( s m p ) 是共享 内存多处理器中广泛使用的体系结构。在s m p 结构中，每个处理器访问所有内存 单元的代价都是一样的。因此限制s m p 结构的处理器个数的主要因素是存储带 宽。另一种非统一内存访问( n u m a ) 结构则是把内存和存储器分为若干个节点， 每个节点的处理器访问本节点内存要快于访问其他节点的内存【2 】。 现在微处理器的发展趋势是多核处理器，其实是将两个或多个处理器核心封 装到一个芯片中，也可称为c m p ( c h i pm u l t i p r o c c s s o r s ) 。其实多核与s m p 的思 想比较类似，都是通过增加并行性来提高处理器性能，实际上s m p 系统中的每个 处理器也可以是多核处理器【4 j 。 存储器是计算机系统中最要的组成部分之一，存储器的访问时延和容量等性 能对增个计算机系统的性能有极其重要的影响。现代体系结构中存储器一般会分 为几个层次，如c e c h e ( 可能有多级) ，内存，外存等。对软件开发人员来说，c a c h e 可以是透明的，其提取，刷新，同步，交换等操作由硬件完成。而对内存，现代 处理器都提供了分段分页等功能。 内存是操作系统所管理的最宝贵的资源之一。操作系统对动态内存的有效管 理是决定系统性能的最重要的因素之一。内存管理也是操作系统内核中最重要的 组成部分之一。现代的操作系统基本上都是多任务的，多个任务会竞争使用内存， 内存管理系统要尽量做到按需分配，不需要时释放，而且要尽可能的高效【3 j 。 电子科技大学硕士学位论文 1 1 本论文的研究意义 内存管理系统是操作系统的核心组成部分。内存管理系统主要是对系统的动 态内存进行管理，包括分页，交换，内存的分配与回收，对进程地址空间的分配， 管理等。不仅用户空间需要使用动态内存，内核自身也需要使用动态内存，而在 内核空间分配和使用内存以及处理相关的内存错误要比在用户空间难得多，因此 内核的内存分配机制和用户空间的有许多不同之处。 在多核系统中，多个处理核心可以并行地访问内存，而对当前的基于统一内 存访问( u m a ) 的多核系统来说，所有核心都能访问同样的内存单元。为了使每个 核心的访存动作都可以正确地完成，在某核心访问共享的内存时，需要使用自旋 锁之类的技术来对访存动作进行同步。而获取释放锁总是会影响系统的性能，因 此如何减少访存时对锁的竞争，如何提高获取释放锁的速度，是提供多核系统中 内存管理系统性能的关键所在。 本文针对以上讨论的几个方面，对多核处理器的发展和特性以及多核系统对 软件开发尤其是操作系统开发带来的新的要求和挑战进行了探讨。在对现有的 l i n u x 的内存管理系统进行了分析和研究之后，探讨了一些对内存管理系统改进 其性能的方法。 1 2 国内外发展研究现状 多核化趋势正在改变计算机软件开发的面貌。跟传统的单核c p u 相比，多核c p u 带来了更强的并行处理能力、更高的计算密度和更低的时钟频率，以及更低的散 热和功耗。不过，尽管多核处理器出现的时间已经不短了，但是现在多数软件仍 是针对单核开发的，还不能从多核c p u 获益。因此，将软件开发的思路转移到针 对多核上来是必需的，作为软件的核心的操作系统自然不例# b t 4 1 。 当前，多核系统中各个内核共享内存时，每个内核对内存的分配，访问，释放 都需要由内存管理器集中控制处理，这其中不免要牵涉到锁的请求和释放等问题， 从而降低了多核系统的并发程度和处理效率。当多核系统中存在多个进程线程进 行频繁的内存分配释放时，情况就会更加的严重。 针对对称多处理机( s m p ) 进行过优化的程序可以立即从多核系统中获得优化 好处。同样多核系统对软件带来的挑战也和对s m p 类似。当前l i n u x 内核已经针 对s h i p 做了许多工作，有针对多核的c o n f i g s m p 编译配置选项，能较好地支持多 2 第一章引言 核系统。就内存管理系统而言，新的内核通过每c p u 页框高速缓存，新的s l u b 系统等功能对多核系统进行了优化。 1 3 章节安排 本文共五章。 第一章为引言，概述了课题的研究背景及意义。 第二章讨论了多核系统的现状以及其对软件提出的要求与挑战。 第三章深入研究了l i n u x 内存管理系统的实现。 第四章提出了对l i n u x 内存管理系统的优化思路。 第五章对全文进行了总结，对进一步的研究工作提出了展望。 3 电子科技大学硕士学位论文 第二章多核系统相关研究 2 1 微处理器发展简史 摩尔定律由g o r d e nm o o r e 于1 9 6 5 年提出，它指出单个处理器上可容纳的晶 体管数量大约每隔1 8 或2 4 个月就会翻一番，性能也将提升一倍。在过去的四十 多年间，摩尔定律准确地预测到了半导体芯片业的发展趋势，推动了信息技术产 业的不断发展。 在各c p u 厂商中，i n t e l 公司的c p u 发展历程很大程度上可以代表c p u 的发 展历程，因此基于i n t e l 公司的c p u 简单介绍一下c p u 的演化过程【5 1 。 1 9 7 1 年，i n t e l 公司推出了i n t e l4 0 0 4 ，该c p u 集成了2 3 0 0 个晶体管，时钟 频率为7 4 0 k h z 。 1 9 7 8 你，i n t e l 生产出第一款1 6 位处理器i 8 0 8 6 和数学协处理器i 8 0 8 7 ，并首 次推出了x 8 6 指令集。 1 9 7 9 年，i n t e l 推出首个用于个人电脑的处理器8 0 8 8 ，它集成了2 9 0 0 0 个晶 体管，时钟频率4 7 7 m h z 。 1 9 8 2 年，i n t e l 推出8 0 2 8 6 芯片，集成了1 3 4 万个晶体管，时钟频率由6 m h z 到2 0 m h z 。 1 9 8 5 年，i n t e l 推出第一款3 2 位处理器8 0 3 8 6 ，集成了2 7 5 个晶体管，时钟 频率由1 2 5 m h 逐步提高到4 0 m h z 。 1 9 8 9 年，i n t e l 推出了8 0 4 8 6 ，它集成了1 2 0 万个晶体管，时钟频率从2 5 m h z 到5 0 m h z 。 1 9 9 3 年，i n t e l 推出新一代处理器p e n t i u m ，它集成了3 1 0 万个晶体管，其时 钟频率从6 6 m h z 到2 0 0 m h z 不等。 1 9 9 6 年，i n t e l 推出为服务器和工作站设计的新处理器p e n t i u mp r o ，它集成 了5 5 0 万个晶体管，内部时钟频率为1 3 3 m h z 。 1 9 9 6 年底，i n t e l 推出p e n t i u mm m x ，增加了5 7 条m m x 指令，强化了影音 图文和通信方面的能力。 1 9 9 7 年5 月，i n t e l 推出p e n t i u mi i ，它集成了7 5 0 万个晶体管，主频从2 3 3 m h z 4 第二章多核系统相关研究 到3 3 3 m h z 。 1 9 9 9 年1 0 月，i n t e l 推出了p e n t i u mi i i ，集成了2 8 0 0 万个晶体管，主频可达 8 0 0 m h z ，并增加了7 1 条s s e 指令。 2 0 0 0 年，i n t e l 推出了w i l l a m c t t e 核心的p e n t i u mi v 处理器，它集成了4 2 0 0 万个晶体管，初始频率高达1 5 5 g h z 。改进版的n o r t h w o o d 核心的p e n t i u mi v 更 是集成了5 5 0 0 万个晶体管。 2 0 0 4 年2 月，i n t e l 推出了9 0 n m 工艺的p r e s c o t t 核心的p c n t i u mi v ，它集成 了1 亿2 5 0 0 万个晶体管，其频率最高可达4 g 。 2 0 0 5 年，i n t e l 推出了第一款双核处理器p c n t i u md ，它其实是将两个p r e s c o t t 核心的处理其封装到一个芯片里，两个处理器有独立的一级和二级c a c h e ，通过 前端总线( f s b ) 进行通信。 在p c n t i u md 之后，i n t e l 公司的处理器正式进入了多核时代，推出了多款酷 睿( c o r e ) 微架构的处理器：c o r es o l o 酷睿单核处理器；c o r ed u o 第一代酷睿双 核处理器；c o r e2d u o 酷睿2 代双核处理器；c o r e2q u a r d 酷睿2 代四核处理器等。 i n t e l 的新一代微处理器是c o r ei 7 系列，基于全新的n e h a l e m 架构，内部封装 2 8 个处理核心。 2 2 多核微处理器 现在市面上流行的多核处理器包括i n t e l 的p e n t i u md ，c o r e2d u o ，c o r e2 q u a r d 系列，a m d 的p h o n e m ，o p t e r o n 系列，i b m 的p o w e r 和c e l l 系列，s u n 的u l t r a s p a r c 等。下面简单介绍一下i n t e l 的几款多核处理器。 2 2 1p e n tiu md 处理器 p e n t i u md 内核实际上由两个独立的p r e s c o t t 核心组成。图2 1 展示了p c n t i u m d 架构的拓扑图。 如图，p e n t i u md 的两个核心有各自独立的l 2 缓存，两个核心通过前端总线 f s b 进行通信，由北桥芯片控制和协调。由于需要北桥芯片的处理，会带来一定 的延迟。进一步讲，p e n t i u md 不是真正意义上的双核处理器，它是i n t e l 为了跟 a m d 抢夺多核处理器市场，直接将两个独立的p e n t i u mi v 处理器封装到一起就 推出的。它的一个优点就是设计比较简单，而且当一个核心坏了之时，另一个核 5 电子科技大学硕士学位论文 心还可以正常工作。 2 2 2c o r e 系列处理器 图2 - 1p e n f i u md 架构图 现在市面上的i n t e l 处理器大部分都是基于c o r e 微架构的。在p e n t i u md 和 p e n t i u mi v 时代，i n t e l 遭遇了滑铁卢。通过n e t b u r s t 架构，p e n t i u mi v 的频率早 早超过了3 g ，在那个频率至上的时代，i n t e l 原打算使用该架构直至频率超过1 0 g ， 然而随着n e t b u r s t 架构的改进，频率的提高，功耗，发热，内部电子迁移等问题 一直难以解决，原本计划好的频率达到4 g ，5 g 的处理器胎死腹中。而且，为了 达到高频率，i n t e l 使用了超长的流水线级数( p r e s c o t t 核心的流水线级数高达3 1 级) ，对性能也有不利的影响。与a m d 的k 8 架构相比，n e t b u r s t 架构的高频低 能现象非常突出。为了从a m d 手中夺回性能王座，i n t e l 推出了c o r e 架构。该架 构是由位于以色列海法的研发团队设计的，其设计目标就是低功耗，高效能【6 】。 c o r e 微架构的典型特点有如下几个： 1 4 级流水线，鉴于n e t b u r s t 为追求高频率采用超长流水线带来的问题，故 c o r e 架构设计了1 4 级的流水线，其指令执行速度更快，对于效能和速度达到了很 好的兼顾。 6 第二章多核系统相关研究 4 宽区动态执行，大大提升了每个时钟周期完成的指令数，从而显著提高了 执行能力。 4 组指令编码器和3 个算术逻辑单元。c o r e 微架构为了加强指令执行能力， 改进了编码器和算术逻辑单元的设计。此外还加入了宏融合，宽动态执行，微操 作融合等功能，提供了执行效率。 智能内存访问，如图2 2 示。c o r n 微架构通过共享l 2 高速缓存，交换核心 之间的数据。智能内存访问包括内存消歧和增强的预取器。智能消歧会判断内存 中将要用到的数据以减少等待时间，通过消歧后，预取器可以先将需要的数据取 入缓存，这样能优化总线的使用。 内核1 指令缓存预先译码 ， 指令缓存 共享二级 ，一、 缓存 微+ ( 8 6 架构) ( 4 仍) 代 刊 译码 码 i r o m 1 重命名地址分配 jlji 舌爿 良罐毒百，d n d 、l 2 ”。碾丌匕二“” 1 1 一 内核2 + 调度器 ， 0 ， a l u 分a l u 分a l u 分 支支支 m s s埘x s s眦x s s 加存 eee 载储 f p 移动f p 移动f p 移动 上上 一级数据缓存一级数据t l b 图2 - 2 c o r e 微架构示意图 高级数字媒体增强功能，c o i e 微架构对s s e 指令集进行了改进，显著地提高 了对数字媒体的处理效率。 7 电子科技大学硕士学位论文 2 2 3 新的c o r e 7 处理器 i n t e l 刚刚推出了新一代处理器c o r ei 7 ，使用了新的n e h a l c m 微架构，如图2 3 所示。n e h m c m 使用了许多新技术来降低功耗，提高效能。n e h a l c m 使用了“模 块化 的设计，由内核和和核外部分组成。 内核实际上是基础的计算引擎，核外则是支持内核的基础元件，包括内存控 制器，q p i ，f o ，时钟，电源等。由于使用了q p i 总线技术，n e h a l e m 可以根据 需要选择安装不同的支持模块。n e h a l e m 还采用了许多先进技术，如新增的s s e 4 2 指令集，s m t 同时多线程技术，3 级c a c h e ，集成内存控制器，更好的分支预测， 更快的虚拟化等。 图2 - 3n e h a l e m 微架构示意图 2 3 计算机体系结构的发展 计算机体系结构包括指令集的设计以及为了实现某些目标和功能需求对硬件 和硬件组织的设计【刀。 计算机性能的迅速发展得益于两个方面：一是硬件技术的发展，如最底层的 超大规模集成电路技术的发展，制造工艺的发展，半导体材料技术的发展等。另 一个是计算机体系结构的不断改进。在过去，c p u 设计者主要从三个方面提高 c p u 性能：时钟速度，执行优化和缓存。 计算机对存储器的要求包括：容量大，速度快，价格低。这几个要求某种程 第二章多核系统相关研究 度上是彼此矛盾的。计算机界有著名的局部性原理：程序中9 0 的访问限于1 0 的存储区域。局部性原理包括两个方面：空间局部性原理，如果一个存储区域被 访问，则它邻近的区域很可能很快被访问，程序的顺序性结构和数组的存在就会 导致这个原理的成立；时间局部性原理，被访问过的存储区域很可能很快再被访 问，程序的循环结构以及堆栈等就会导致这个原理的成立。为了解决存储器几个 要求的矛盾，根据局部性原理，提出了多级存储体系来解决这个问题，如图2 4 所示。从c p u 内部的寄存器，到高速缓存，到内存，再到外存，速度和价格逐步 下降，容量逐步上升。 图2 - 4 存储体系结构示意图 现代c p u 都引入了1 级高速缓存，2 级，3 级甚至更多级的片内高速缓存， 通过多级速度不一的缓存来缓解处理器和内存间的速度的矛盾。现代c p u 拥有越 来越大的高速缓存，c a c h e 已经占用了芯片的大部分面积。 一直以来，加强并行性都是提高c p u 时钟速度的最重要的方法之一。并行性 包括指令级并行性和线程级并行性。 处理器速度飞速提升的一大因素就是指令级并行( i n s t r u c t i o n 1 e v e l p a r a l l e l i s m ，即i l p ) 技术的发展。i l p 技术实际上是把指令的执行分成若干个环 节，指令执行形成多步操作的流水线，同一时刻多条指令可以在不同的步骤同时 执行，这样宏观上相当于多条指令同时执行。流水线级数越多，意味着理想情况 下c p u 的频率越高。为了更好发挥流水线的功效，减少流水线回退或阻塞，还发 展出诸如分支预测，超长指令字，动态执行，乱序执行等技术。 指令级并行技术的发展使单个处理器速度飞速发展，但仅依靠指令级并行技 9 电子科技大学硕士学位论文 术来提高处理器速度也越来越难：处理器功耗越来越高，流水线阻塞和回退的损 失越来越大，工艺将达到极限等。提高线程级的并行度将是处理器性能持续稳定 发展的重要方向。 现在，提高c p u 性能主要有几个方面：超线程技术，它能更充分地利用计算 机系统的各功能部件【8 1 ；多核，它通过将多个执行核心封装在一个芯片中实现了 线程级并行【9 】；缓存，更大和更快的高速缓存仍是提高c p u 性能的重要手段【1 0 1 。 在多核系统越来越成为主流之时，多个核心的c a c h e 的一致性和持久性等问 题是需要很好地解决的【1 1 】。当前主流的多核处理器各个核心有自己独立的1 级高 速缓存，并共享2 级高速缓存，新的处理器还有引入了n u m a 技术的。共享2 级高速缓存的多核处理器类似于s m p 系统。各核心之间通过2 级高速缓存进行通 信，速度更快。采用多级存储体系会导致数据一致性问题，一般使用回写或写直 达的方法解决。 在多核系统中，c a c h e 的一致性和持久性有新的特点：多个核心可以在同一 时刻并行运行，每个核心有自己的独立的1 级高速缓存，每个核心占有共享的内 存和自己私有的内存，各核心通过2 级高速缓存通信。所以除了类似前面的内存 和高速缓存有可能不一致，各个核心独立的1 级高速缓存也可能不一致。 产生c a c h e 不一致的原因包括： 设核心a 和b 共享了某个可写的数据，在某个时刻核心a 修改了该数据， 它可能用写直达方式直接将新数据同步到外存上，或者用回写方式暂时只更新本 地高速缓存，这两种情况下核心b 的本地高速缓存中保存的数据与核心a 的高速 缓存中的数据都会不一致；进程迁移，如果用回写方式，当某个进程p 从核心a 迁移到核心b 时，核心a 的高速缓存保存了新数据，而核心b 的高速缓存保存 的是旧数据，产生了不一致，如果用写直达方式，当进程再从b 迁移到a 时，也 会出现不一致；还有不经过高速缓存的f o 操作如d m a ，会造成高速缓存和内存 中的数据不一致l l 引。 解决c a c h e 一致性的方法包括两大类：以硬件为基础的方法包括基于侦听的 高速缓存一致性协议和基于目录的高速缓存一致性协议等；软件为基础的方法主 要是由编译器对程序逻辑进行分析，把数据分为可缓存的和不可缓存的【1 3 儿1 4 】。 2 4 多核系统对软件的要求和挑战 多核系统中多个执行线程能够真正地并行执行，它与以往的单处理器单线程 1 0 第二章多核系统相关研究 和单处理器多线程环境有本质的不同。它对应用程序，编译器，操作系统等各层 次的软件的开发都提出了新的要求和挑战 1 5 1 。正如h e r bs h u t t e r 所说1 6 1 ，免费的 午餐已经结束，软件开发历史性地向并发并行模式靠拢。现在多核处理器已经成 为市场的主流，同时许多软件是针对单核环境而开发的，这些软件还无法或很少 能从多核系统中获取足够的好处【1 7 18 1 。 在当前主流的多核系统都是基于共享存储的，要编写正确高效的程序需要正 确理解所谓的内存一致性模型。内存一致性模型是指读写内存指令操作执行的顺 序，它的原始定义由c c n s i c r 和f c a u t r i c r 给出，简单的说就是一个读内存指令应 该读到最近的对同一地址写指令的结剁1 9 1 。 内存一致性模型主要包括以下几种【2 0 埘】： 严格一致性模型，它对一致性的要求最为严格，它的要求是：所有对某个内 存位置的读操作都应该返回该位置最近的写操作所写的值。 顺序一致性模型，它的要求比严格一致性模型要弱上一点，它对存储器提出 了两点要求： ( 1 ) 所有进程其本地的运行流程都是固定的； ( 2 ) 如果全部进程都会访问某个存储器位置，那么，它们应该有一定的访问顺序， 所有进程要遵守这个访问顺序。 因果一致性模型，它比顺序一致性模型的要求又要弱上一点，只是需要那些 有潜在因果关系的操作间保持一致的顺序。 管道一致性模型，它比因果一致性模型的要求又要弱上一点，它的要求包括： 每个进程进行的写访问的影响都能为系统中全部的进程基于一致的顺序接受，由 不同的进程提交的写访问能够不必遵守固定的顺序。 弱一致性模型，它引入了同步变量。这个模型对存储器实现提出了如下的几 个要求： ( 1 ) 访问同步变量必须要一致。 ( 2 ) 在访问同步变量操作前的写操作必须先完成。 ( 3 ) 访问共享数据必须跟在访问同步变量的后面。 释放一致性模型，它对存储器有以下要求： ( 1 ) 必须先成功地获取到同步变量，然后可以正确的完成对由同步变量保护的数 据的访问。 ( 2 ) 同步变量的释放在对由其保护的数据的访问操作完成之后。 ( 3 ) 同步变量的获取和释放要满足一致的顺序。 电子科技大学硕士学位论文 单项一致性模型，它对存储器提出了以下要求： 想要获取某个同步变量，必须要等到在该同步变量保护的数据上执行的访问 完成之后。 ( 1 ) 当某个同步变量被互斥持有的时候，所有想要互斥的获取该同步变量的操作 都必须等到该变量被释放才能够成功。 ( 2 ) 当某个同步变量被互斥持有的时候，如果同时又出现了相应非互斥的获取该 同步变量的操作请求，那么这些操作请求都必须等待该变量被其持有者释放之后， 否则不能成功。 对于传统的单处理器软件开发人员来说，我们可能认为：每个处理器核心的 读写内存操作都会按我们编程时的顺序进行，在某一时刻只会有一个核心访问内 存，这是以往单处理器核心系统中典型的内存模型。然而，在多核系统中，这个 内存模型遭到了破坏，编译器和c p u 的优化都可能使按这种模型开发的程序不能 正确地工作。现代c p u 基本上都有乱序执行，多指令流，内存重排序缓冲等功能， 使得实际执行时的读写顺序可能不是我们编程时指定的。当然，在单核系统中， 这种重排序是不影响程序的正确性的。然而，在多核系统中，一切都有所不同， 核，l 、z 日- , 匕v , 够保证本地线程的重排序执行是正确的，但无法顾及其他核心上的线程。 此外，现代编译器的很多优化技术，如代码迁移，寄存器分配，公共子表达式消 除，软件流水线等也会使读写的执行顺序被打乱，甚至可能消除读写指令而将 数据读入寄存器中。这种乱序执行可能导致在单核系统中运行良好的软件在多核 系统中出错f 2 5 】f 2 6 1 。 因此在现代c p u 上，如果需要确保读写指令的执行顺序是自己定义的，需 要使用一些内存屏障如m f e n c e ，b a r r i e r ，i f e n c e ，s f c n c e 之类的指令，这些指令是 c p u 提供的，可以阻止编译器和c p u 对指令进行重排序。 在单核系统中，某一时刻只会有一个线程在执行，对于线程之间共享的数据， 只要关闭中断和禁止抢占即可确保不会出现另一个线程的竞争。然而在多核系统 中，各线程能够真正地并行执行，这样线程间共享的数据需要使用锁信号量之类 的同步互斥技术来消除数据竞争。 现代操作系统如s o l a r i s 2 7 1 ，f r e c b s d 2 9 1 ，l i n l l 】【2 8 】等能通过支持s m p 系统的 版本从而支持多核系统。如在l i n u x 中，有许多带有s m p 前缀的变量和函数，编 译内核时通过设置来激活支持，而在c o n f i gs m ps m p单核系统中，这些变量 和函数会被展开为空，不会带来性能上的损失。l i n u x 使用原子变量和原子操作， 自旋锁以及基于自旋锁实现的信号量对多核多处理器做了进一步的支持。 1 2 第二章多核系统相关研究 2 5 小结 本章首先简述了i n t e l 微处理器的发展历程，重点介绍了i n t e l 多核微处理器 的架构。然后介绍了计算机体系结构的发展。最后讨论了多核系统对软件开发提 出的新的要求和挑战。 1 3 电子科技大学硕士学位论文 第三章lin u x 内存管理系统研究 下面对i n t e lx 8 6 3 2 平台的l i n u x 2 6 2 8 7 内核的内存管理系统进行研究和探 讨，本章主要参考了文献 3 0 一4 0 。 3 1lin o r 内核概论 操作系统内核提供了对硬件平台的抽象，提供了对软硬件资源的管理和分配 功能。操作系统内核一般有两种类型：微内核和单内核。在微内核中，系统功能 被划分为多个模块，每个模块实现为一个进程，模块之间的通信要使用进程间通 信( i p c ) 机制。微内核中的各个功能模块彼此独立，一个失效不会影响到其他。 微内核可以通过更换功能模块方便地改变系统提供的服务。但是微内核的各功能 模块运行涉及到 p c 机制以及核心态和用户态切换，性能上有所损失。单内核是 把内核作为一个整体设计，各功能模块之间可以通过函数调用直接通信。单内核 的好处是比较简单，效率较高【4 1 1 。 l i n u x 内核采用了单内核设计，同时通过支持动态模块加载实现了类似微内 核的功能。l i n u x 内核有几个主要的子系统，如图3 1 所示： 图3 - 1l i n u x 内核结构示意图 1 4 第三章l i n u x 内存管理系统研究 3 2l i n u x 内存管理系统概论 l i n u x 内存管理系统可以大致分为几个模块，如图3 2 所示。 图3 - 2l i n u x 内存管理系统模块结构示意图 其中，页框管理模块实现对物理页的管理，分配和回收，它是其他模块的基 础；回收和交换模块可以把某些页换到外存，也可以把换到外存的页再换进内存， 它还可以回收某些满足条件已分配的页使其变为空闲；内存映射模块负责实现虚 拟地址和物理地址间的转换；系统调用接口是内核提供给应用软件开发人员使用 的接口；通过体系相关模块，可以使用某些体系结构的m m u 提供的特有的功能。 3 3 内存寻址 x 8 6 处理器为存储系统提供了分段和分页的功能。相应的，内存地址可以分 为三种：逻辑地址，线性地址和物理地址。 逻辑地址是启用了分段功能时的地址，它由段标识符和偏移量两部分组成。 而段标识符又由段索引，表指示器t 1 和特权级r p l 3 部分组成。根据段索引和 g d t r 或l d t r 寄存器中存放的全局段描述符表( g d t ) 或局部描述符表( l d t ) 的 地址，即可求出所用段的段基址，再加上偏移量及得出逻辑地址对应的线性地址。 线性地址是在分页机制下使用的地址。线性地址被分为固定长度的页，线性 地址到物理地址的映射被保存在页表中。页的大小一般是4 k b ，在扩展分页的情 电子科技大学硕士学位论文 况下页大小也可能为4 m b ，在物理地址扩展( p a e ) 的机制中页大小可为2 m b 。 从逻辑地址到线性地址和从线性地址到物理地址的转换都是由硬件完成的。 3 4 物理内存的描述 我们用页框来表示内存的一个物理划分，用页来表示线性地址的固定划分及 包含在这组地址中的内容。 内存被划分为固定大小的页框，内核使用页描述符来记录每个页框的状态。 页描述符是被定义为结构体p a g e ，定义在i n c l u d e l i n u x m m _ t y p e s h 中： 页描述符中的各字段说明如表3 1 。 表3 1 页描述符中的字段说明 类型字段说明 u n s i g n e dl o n gf l a g s 页标志，描述页框状态 a t o m i ctc o u n t 页框的引用计数 a t o m i ct j m a p c o u n t 被映射的页表项的数目 u 1 6l n u s e 用于s l u b ，表示已分配对象数目 u 1 6 o b j e c t s用于s l u b ，表示对象数目 u n s i g n e dl o n g p f i v a t e 可被用于页缓冲或页交换或伙伴系统 a d d r e s s _ s p a c e 拳m a p p