（计算机系统结构专业论文）多处理器系统中的线程调度研究.pdf

一 - b n 镰 k 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 塑盏垄l 笔日期：矽口年5 月a 1 日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：蕴2 盏雏 导师签名：套数 占锨 日期：知o 年歹月叫日 l l _ _ - _ 。一 o p 0 。t - 噜 k 摘要 摘要 随着超线程和多核等新兴技术不断涌现，当前的s m p 系统硬件结构更加复杂， 系统硬件性能也更加强劲，随之而来的问题是：传统的s m p 操作系统已不能充分 发挥现代s m p 硬件系统性能，为了适应当前硬件技术的这种变化，我们有必要在 研究传统s m p 系统的基础上，对操作系统中那些不适应的部分加以改进或用新的 算法替换，从而使软件系统能最大限度地发掘硬件系统的潜在性能。 本论文首先介绍了课题研究背景和研究意义，简要阐述了目前在单个处理器 物理封装中实现多个进程或线程并行执行的两大主流技术：同时多线程技术 ( s i m u l t a l l e o u sm u l t i m e a d i n g ，s m t ) 和多核技术( c h i pm u l t i p r o c e s s o r ，c m p ) ， 另外论文还概要介绍了l i n u ) ( 操作系统以及该系统在研究s m p 系统调度时的重要 作用。其次，论文剖析了经典的s i n p 系统组织结构以及各种操作系统中常用的一 些经典进程调度算法，这些硬件架构知识和软件概念都为我们后面研究s m p 操作 系统进程调度算法打下了坚实基础。接下来论文将理论联系实际，以最新版本的 “n u x 内核作为研究对象，详细剖析了它的进程调度系统。当前的“n u x 内核采用 了一种全新的名为完全公平调度( c o m p l e t e l yf a i rs c h e d u l e ，c f s ) 的进程调度策 略，为了能够理解c f s 的调度原理以及它对s m p 系统的相关支持，论文在详细介 绍c f s 调度原理的同时，剖析了对应的c f s 调度源代码。论文最后章节总结了影 响s m p 调度系统性能的几大关键因素，并分析了我们在设计s m p 调度系统时应注 意的设计要点，以这些理论分析为基础，论文提出了一个高效的s m p 调度系统模 型。 在前面章节理论分析的前提下，论文还以一个针对l i n u x 内核的s m p 系统进 程调度优化作为结尾，介绍了我们应当如何对s m p 调度系统优化进行思考以及在 有了优化方案后如何把方案应用于实践并做出实验及验证分析。 关键词：多处理器，s m p ，l i n u x 进程调度，完全公平调度，调度优化 【一 一 。 k h i a b s t r a c t a b s t r a c t w i t ht h ee n l 盯g e n c eo f h y p e r - 缸e a d i n ga i l dm u l t i c o r ep r o c e s s o r s ，c u r r e n ts m p s y s t e mh a r d w a r es t m c t u r eb e c o m e sm u c hm o r ec o m p l e xa n dm o r ep o w 瓶l ，t h e e n s u i n gq u e s t i o ni s ：t r a d i t i o n a ls m po p e r a t i n gs y s t 锄sn ol o n g e r 百v e 向l lp l a yt om e p e r f o 册a 1 1 c eo fm o d 锄s m ph a r d w a r e ，i no r d e rt oa d 印tt ot h i sc h a n g e ，w en e e dt o s t u d y 仃a d i t i o n a ls m ps y s t 锄a n di m p r o v et h o s ep a i r t st h a ta r en ol o n g e rs u i t a b l ew i m n e wa 1 9 0 r i m m s w eh o p es o r w a r ec o u l dg a i nm a x i m u mp e r f b m l a n c eb yt h e s es t u d y f i r s t ，t 1 1 i sp 印e rf i r s ti n t r o d u c e st h er e s e a r c hb a c k g r o 帅da n dr e s e a r c hs i 盟i f i c a l l c e ， 百v e sb r i e fd e s c r i p t i o no f 觚om a i nt e c l l l l i q u e st oa c h i e v ep a r a l l e le x e c u t i o no fm u l t i p l e p t o c e s s e s0 rt h r e a d s i nas i n 雷ep r o c e s s o rp a c k a g e ：s i n m l t a n e o u sm u l t i t 1 1 r e a d i n g t e c h l l 0 1 0 9 y ( s m t ) a n dm u l t i c o r et e c h n 0 1 0 9 y ( c m p ) ，i na d d i t i o n a l ，p a p e ra l s oo u t l i n e s m el i n u xo p e r a t i n gs y s t e l t la n di t si m p o r t a n tr o l ei nt h es t u d yo fs m ps y s t e m s e c o n d ， p a p e ra n a l y z e st h eo r g a n i z a t i o n a ls t m c t u r eo fc l a s s i cs m ps y s t e ma 1 1 d i n t r o d u c e sa v 撕e t yo fp r o c e s ss c h e d u l i n ga l g o 订t 1 1 1 1 1 s ；l ( 1 l o w l e d g eo ft h e s eh a r d w a r ea r c h i t e c t i j r ea 1 1 d s o r w a r ec o n c 印t sg i v e su ss o l i df o u n d a t i o ni n如r t h e rs t u d yo fs m po p e r m i n g s y s t 锄t h i r d ，p a p e ru s e st h el a t e s tv e r s i o no fl i l l u xk e n l e la sa no b j e c to fs t l l d ya n d g i v e sd e t a i l e da n a l y s i so fi t sp r o c e s ss c h e ( 【u l i n gs y s t e m t h ec u r r e n tl i n u xk e m e lu s e s a 1 1e n t i r e l yn e ws c h e d u l e rc a l l e dc o m p l e t e l yf a i rs c h e d u l e r ( c f s ) ，i no r d e rt ou n d e r s t a n d i t sp r i n c i p l e sa 1 1 dr e l a t e ds u p p o r tf o rs m ps y s t e m s ，p a p e r 百v e sd e t a i l e da n a l y s i so f c f s ss o u r c ec o d e f i n a l l 弘p a p e rs u m m a n z e ss e v e m lk e yf a c t o r si nt h ed e s i g no fs m p s c h e d u l i n gs y s t e h la n dp r e s e n t sa ne 衔c i e n ts c h e d u l i n gm o d e l b a s e do nt h e o r e t i c a l a n a l y s i s i n p r e v i o u sc h 印t e r s ，p 印e r a l s o p r e s e n t s a 1 1 o p t i m i z a t i o np r o p o s a lf o rs m ps y s t 锄a n ds e ta 1 1e x 锄p l ef o rh o w t om a l ( eo p t i m i z a t i o n t os m ps y s t e ma n dh o wt or e a l i z ey o u ro p t i m i z a t i o np r o p o s a l k e y w o r d s ：m u l t i p r o c e s s o r s m p ，“n u xp r o c e s ss c h e d u l c o m p l e t e l yf a i rs c h e d u l e ， s c h e d u l eo p t i m i z a t i o n i i 、 j ， 0 k 第三章l i n u x 调度系统及c f s 剖析2 2 3 1l i n u x 内核调度器简史2 2 3 2o ( 1 ) 调度器概要2 3 3 3 完全公平调度器概要2 4 3 3 1 模块化的调度器接口2 4 3 3 2c f s 调度器2 4 3 3 3c f s 组调度2 5 3 4c f s 实现核心2 5 h l 3 5 红黑树介绍2 6 3 6c f s 关键数据结构2 7 3 6 1s 仃u c tt a s k - s t m c t 的变化2 8 3 6 2s n l l c ts c h e d - e 1 1 t i t y 结构体2 8 3 6 3s 仇l c ts c h e d - c l a s s 结构体2 9 3 6 4s t m c tc 鼓- r q 结构体3 0 3 6 5s t m c tt a s k - g r o u p 纬陶体3 1 3 7c f s 核心代码剖析3 2 3 7 1s c h e d u l 吖i c k ( ) 函数3 2 3 7 2t a s k _ t i c k _ - f a i r ( ) 函数3 3 3 7 3e i l t i t y c k ( ) 函数3 3 3 7 4u p d a t e c u 盯( ) 及_ u p d a t e - c u r r ( ) 相关函数3 3 3 7 5c h e c k _ p r e 锄p t - t i c k ( ) 函数3 5 3 7 6s c h e d u l e ( ) 函数3 6 3 7 7p u u r e v j a s k _ f a i r ( ) 及相关函数3 7 3 7 8p i c l ( - 1 1 e x t - t a s k _ f a i “) 及相关函数3 8 3 8 源代码分析总结3 8 3 9c f s 组调度支持3 8 3 1 0c f s 与s m p 3 9 3 1 0 1 调度域4 l 3 1 0 2l i i m xs m p 系统调度层级结构4 3 3 1 0 3c f s 之s m p 负载平衡4 4 3 1 1 本章小结4 8 第四章高性能s m p 调度系统研究4 9 4 1s m p 调度基础。4 9 4 1 1 同步机制4 9 4 1 2 局部性原理5 0 4 1 3s m p 负载均衡策略5 l 4 1 4 调度策略5 2 i v ， k k 目录 4 2 高效s m p 调度系统分析5 3 4 2 1 较小粒度的锁5 3 4 2 2 独立的运行队列5 3 4 2 3 分级的负载平衡机制5 4 4 2 4 高效s m p 调度系统图例5 5 4 3l i n u xs m p 调度优化5 7 4 3 1 优化原理分析5 8 4 3 2f u t e x 概要原理5 9 4 3 3 内核改动分析及实现6 0 4 3 4 简单验证及分析6 2 4 4 本章小结6 4 第五章总结与展望6 5 致谢6 6 参考文献6 7 攻硕期间取得的研究成果7 0 v 、i q 第一章绪论 1 1 课题研究背景 第一章绪论 随着科技的发展，现代计算机系统架构正从传统的单处理器系统转向多处理 器系统。传统上，大多数多处理器系统都是所谓的对称多处理机系统( s n m e t r i c m u l t i p r o c e s s o r s ，s m p ) ，这样的系统通常是由两个或多个处理器芯片组成，这些 处理器芯片对系统内存和其它外设有着相同的访问能力和代价。但是，当前流行 的多处理器系统在架构上有着不一样的设计思想，它主要是指现在很多厂家生产 的单个处理器封装都具有同时执行多个进程或线程的能力。 要使单个处理器具有同时执行多个线程或进程的能力，可以采用两项新兴技 术。第一项是同时多线程技术( s i m u l t a i l e o u sm u l t i t l l r e a d i n g ，s m t ) 1 ，该技术 通过在多个执行线程间共享处理器硬件资源来达到充分利用处理器能力的目的， 共享的资源包括指向指令流中当前指令的程序计数器、线程的c p u 状态信息以及 其他一些资源，比如堆栈等。同时多线程技术已在一些主流处理器厂商的处理器 中出现，比如i n t e l 的用于桌面系统的奔腾( p e n t i u m ) 4 处理器和用于高端服务器 的至强( x e o n ) 处理器，以及s o n y i b m 的c e n 处理器 2 】。 第二项技术就是目前最为流行的多核技术( c h i pm u l t i p r o c e s s o r ，c m p ) 【3 】， 该技术在一个传统的处理器封装内集成了两个或多个独立的处理器核心，这就意 味着，多核处理器中的每个核心都拥有独立的物理资源，每个处理单元的资源相 当于静态分配的，而在同时多线程技术中则是共享的处理器资源，每个逻辑处理 单元的资源被动态分配。多核技术和同时多线程技术的基本思路类似：它们都是 通过使用多个简单的处理单元( 物理上的或逻辑上的) 来以最小的能耗获得最佳 的性能，这和只使用一个较复杂的处理单元相比要高效得多，后者无论从能耗或 设计难度上来说，都远远比不上前者。目前世界上的一些主流生产厂商比如i n t e l 和a m d 都推出了自己的多核处理器，i b m 则在2 0 0 1 年就推出了采用双核架构的 处理器p o w e r 4 1 。 s m t 技术和c m p 技术给现代处理器设计注入了新的活力，它从另一个角度做 出改进，解决了长期以来困扰处理器设计者的难题。长期以来，处理器设计者主 要是通过不断提高处理器主频来获得更高的性能，但处理器主频的提高，必然会 电子科技大学硕士学位论文 使处理器产生更大的能耗和散发出更多的热量，功耗和散热问题长期是处理器设 计中最令人头疼的问题，这就给处理器的进一步性能提升带来了不小的阻碍。有 了s m t 和c m p 技术之后，主频不再是衡量处理器性能的唯一标准，人们不再以 提高主频作为提高系统性能的关键点，并且采用这两项技术也不会产生过高的能 耗和热量，我们还可以通过配置使处理器能够根据系统负载自动调节处理器频率 或者及时关闭或打开某个核心。由于s m t 和c m p 是两种完全不相冲突的技术， 单个处理器封装在设计时完全可以同时采用这两种技术以获得更高的性能。比如， i b m 公司生产的p o w e r 5 5 系列处理器就同时采用了c m p 和s m t 技术。有了这 些技术做为支撑之后，在今后的对称多处理机系统中，它的每一个物理处理器都 可以采用s m t 和c m p 技术，具有并行运行多个线程的能力，这将会进一步提高 对称多处理机系统的整体性能。 处理器结构发生了变化，产生直接影响的莫过于运行于处理器上与处理器直 接打交道的操作系统了。拥有多个线程并行执行能力的处理器对操作系统的影响 是多方面的：其一是多线程方面，虽然在传统的单处理机操作系统中我们也可以 实现多线程技术，但从微观上看那并不是真正的并行，只有在拥有多个处理单元 的机器上我们才能获得真正的并行，而真正的并行会给操作系统带来一些在传统 单处理器机器上不会出现的问题，比如多个操作系统线程并行修改共享数据，此 时我们需要使用互斥机制。另外一个影响比较大的是进程调度系统，这也是本论 文讨论的重点，在传统单处理机操作系统中，由于系统中只有一个处理单元，系 统中的进程通过调度程序简单地共享该处理器资源即可，但在有多个执行单元的 处理器中，进程可以选择运行在任何一个执行单元上，如何调度进程占用这些执 行单元才能获得系统性能最大化呢? 这成为了操作系统调度程序设计者的一大难 题，另外，在多处理器系统中，我们总是希望各个处理单元都有事可做，希望各 个处理单元的负载尽量平衡，这就涉及到一个在各个处理单元之间进行负载平衡 的问题，但负载平衡意味着进程会在各个执行单元之间进行迁移，这会导致进程 访问处理器高速缓存命中率的下降，如何提高执行单元的高速缓存命中率呢? 这 也是一个设计难点，所有这些调度问题都是传统的单处理机操作系统没有碰见的， 值得庆幸的是，经过几十年来的研究，这些问题在对称多处理操作系统( s m p ) 中差不多都有了不错的解决方案，因此研究s m p 系统调度算法对我们设计现代操 作系统有着非常重大的意义。另一方面我们也应该认识到，传统的s m p 系统又与 现在采用s m t 和c m p 技术的多处理器系统有着稍微不同的架构，因此我们应该 在传统s m p 操作系统调度策略的基础上做出改进，以使它即能适应传统的s m p 2 第一章绪论 系统，也能适用于于采用了s m t 和c m p 技术的处理器，最极端的情况是如果系 统硬件系统同时支持s m p 、s m t 和c m p ，我们的调度系统也应当有着最优的调度 性能。 l i n l d 【操作系统作为开源软件，深受开发者的喜爱和追捧，这个系统为我们提 供了一个学习和实践操作系统各方面知识的平台，该系统符合p o s i x ( 可移植操 作系统接口) 规范，支持i 3 8 6 、a l p h a 、s p a e c 和p o w e r p c 等处理器。l i n u x 内核 从2 o 版本开始支持s m p 系统，目前l i n u x 内核已发展到版本2 6 3 x 系列，和最 初支持s m p 系统的版本相比，当前的内核版本有了更好的扩展性和调度性能，这 在很大程度上归功于其调度系统的不断进化。以l i n u x2 4 版本内核和2 6 版本内 核为例，对s m p 系统而言，在2 4 版本内核中所有进程都处于一个共享队列上， 调度程序不断地从这个队列上选择程序到各个处理器上执行，当系统中处理器较 多时，对共享队列的访问竞争加剧，系统的处理器扩展性受到限制；而在2 6 内核 中，多处理器系统的每一个处理器都拥有独立的可运行进程队列，调度程序在各 个处理器上的调度竞争大大减少，系统可扩展性有了很大提高。另外，在最先版 本的2 6 内核中采用了名为o ( 1 ) 的调度算法，该算法大大降低了每个处理器调 度进程的时间复杂度，而从l i n u x 内核2 6 2 3 开始引入了完全公平调度算法( c f s ) 6 】来取代o ( 1 ) 调度器，c f s 调度器能够保证调度更加公平，同时它的时间复杂 度也不会很高。l i n u x 内核在支持传统s m p 系统的同时，也保持了与时俱进的特 点，它的调度程序在调度时会感知系统是否支持s m t 和c m p 架构，以便做出更 好的抉择以提供更高效的调度性能，因此，如果我们要研究具有s m t 和c m p 特 性的s m p 系统线程调度机制，以l i 肌x 平台为基础是一个不错的选择。 1 2 论文的主要工作 在传统单处理器系统发展渐缓的今天，多处理器的引入和并行处理必将带来 深远的影响。本文试图把握和理解多处理机系统的脉络，在新型多处理机( 具有 s m t 和c m p 特性) 线程调度方面做出贡献。本论文把重点放在了研究最新的l i n u x 内核在s m p 系统上的线程调度机制上，论文的主要工作有如下几点： 1 、介绍s m p 系统和调度程序基础知识。 2 、介绍“n u x 内核调度算法的发展历程。 3 、剖析了“n u ) 【内核最新的完全公平调度算法。 4 、总结并提出了一个高效的s m p 调度系统模型，并对l i n u x 在s m p 调度方 4 第二章s m p 系统及线程调度 2 1s m p 系统 第二章s m p 系统及线程调度 随着人们对计算机处理能力的要求不断提高，单纯地靠提高系统处理器主频 已不能满足人们日益增长的使用需要，并且处理器主频的不断提高必然会带来难 以解决的散热问题，因此人们开始从改善系统架构的角度出发来提升系统整机性 能，于是就有了多处理机系统的诞生。所谓多处理机系统就是一个含有多个处理 器的计算机系统【9 】，从处理器与系统内存的关系来说，多处理机系统又可分对称 多处理机( s 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 s y m m e 砸c m u l t i p r o c e s s o r a s m p ) 系统两种，我们在本小节中重点关注对称多处理机系统。 对称多处理机( s m p ) 系统作为多处理机系统的一个特殊类别，其架构相对比较 简单，它的典型特点在于为系统中的所有处理器提供了等同的内存访问能力和代 价，因此对称多处理机系统也被叫着一致性内存访问( u n i f o 肌m e n l o r ya c c e s s ， u m a ) 系统，相应地，非一致性内存访问( n o n u n i f o 咖m 啪o r y a c c e s s ，n u m a ) 系统就不具有这个特性了，它的每一个处理器访问不同系统内存节点的性能和代 价都不一样。另外，就s m p 系统而言，根据其系统内部各个部件之间不同的连接 方式，又可分为基于总线的s m p 、基于交叉开关的s m p 以及基于多级交换网络的 s m p 这三种类别。 2 1 1 基于总线的s m p 这是最简单也是最常用到的一种s m p 系统部件连接方式，在这种情况下，系 统中所有的部件都挂接在同一组系统总线上进行通信，如图2 1 所示。每当一个处 理器想从内存读取数据时，它都会首先检查系统总线是否空闲，若总线空闲，处 理器就会把想读的数据地址放到总线上并且发出读取信号，然后等待内存把数据 准备好；相反，若处理器发现当前总线忙，则它就会一直等待直到总线空闲下来， 这样一来就会浪费掉不少的处理器时间，随着系统中处理器数量的不断增加，各 个处理器对总线的竞争将变得更加激烈，系统整机性能必定会急剧下降，这样的 s m p 系统的最大瓶颈就在于其总线带宽。 5 数据块可能不允许同时存在多个c a c h e 中。当一个处理器修改一个存在于多个处理 器 理 据 数 中 存 现 统 h 第二章s m p 系统及线程调度 系统总线 图2 2 带c a c h e 的s m p 结构图 除了给处理器添加c a c h e 外，另外还有其它方法来进一步减少处理器对系统总 线的竞争，给系统中每个处理器添加一块仅供该处理器访问的私有内存便是很好 的解决方法，此时系统结构图如图2 3 所示。私有内存从只能被对应的处理器通过 专有总线来访问，因此该私有总线不存在访问冲突的问题，但是世上觉没有完美 的解决方案，这种系统架构要得到应用就必须得到编译器的支持，编译器应当把 程序的数据段、字符串常量、只读数据及程序堆栈等放到私有内存中，而共享的 系统内存应当用来存放那些需要修改的共享变量。在大多数情况下，这种精心的 安排确实能带来大幅度的性能提升，不过由于现实世界中很多编译器不支持这个 特性，因此这样的系统应用不是特别广泛。 系统总线 图2 3 带私有内存的s m p 系统 2 1 2 基于交叉开关的s m p 尽管在基于总线的s m p 系统中引入c a c h e 和私有内存能减少处理器对系统公 共总线的竞争，但在这样的s m p 系统中其总线始终是整机性能的瓶颈，采用这种 7 电子科技大学硕十学位论文 架构限制了系统中处理器的数量，这样的系统中采用的处理器一般最多为3 2 个。 为了使s m p 系统能支持更多的处理器，我们应该用更优的信息交换结构来取代总 线，采用交叉开关结构来取代系统总线无疑是最简单的一种连接形式，这种结构 可以高效地把n 个处理器连接到m 个内存快上，其结构如图2 4 所示，该图展示 了一个有着四个处理器和四块内存的s m p 系统。交叉开关结构在电话交换方面已 经使用了多年，它被用来以任意的方式连接一组输入线路到一组输出线路。 系统内存 系 统 处 理 器 园囝图囹 ， 、，一- 、厂，、，一 厂、厂、厂 、，一 ，一、 一、 ， 、 ， 厂。、厂、厂 交 叉 开 关 图2 _ 4 基丁交叉开关结构的s m p 系统 在该示意图中，每一根横线代表一条从处理器发出的访问，每一根竖线代表 进入内存的访问，两根线的交叉点为一个交叉开关，所谓交叉开关是指一种能通 过电信号打开或关闭的小型开关，交叉开关的打开或关闭是根据图中横线和竖线 是否需要连通来决定的。 交叉开关的最大特性在于它是一种非阻塞的交换网络，这就意味着，只要系 统内存模型允许，s m p 系统中的处理器不会因为某些内存被占用了而不能访问剩 下的内存。当然，基于交叉丌关的s m p 系统也有一个很大的缺点：系统内部交叉 开关的数量会随着系统中处理器和内存的数量成倍( 比如有n 个处理器和n 块内 存，则需要刀2 个交叉开关) 地增长，以我们的示意图为例，系统中只有4 个处理 器和4 块内存，而我们需要的交叉开关数量却达到了1 6 个，对于那些用到上千个 处理器的系统而言，使用的交叉开关结构会达到上百万个，这样的系统结构是不 现实的，因此，基于交叉开关的s m p 系统比较适合于中等规模的系统。 囝囝圆囝 第二章s m p 系统及线程调度 2 1 3 基于多级交换网络的s m p 鉴于采用交叉开关的s m p 系统的缺陷，一种新的基于普通的2 2 交换器的 s m p 系统诞生了。普通的2 2 交换器如图2 5 所示，这种交换器有两个输入端口 和两个输出端口，当消息到达任意一个输入端口，它可以被交换到任意一个输出 端口。对我们的s m p 系统而言，消息将包含四个部分，如图2 5 所示，其中，模 块指明了要访问哪个内存，地址指明了内存中的地址，操作码指明了当前是什么 操作，比如读或者写操作，这是一个是可选项，值可能包含一个操作数，比如内 存写入一个3 2 位字长的数据等。交换器检查消息的模块字段，以决定将消息发往 哪个目标输出端口。 输 入 莹区卫丑困值 2 2 交换器 消息结构 图2 52 2 交换器及消息结构 这种2 2 交换器可以以很多方式来组成大型的多级交换网络，图2 6 展示了 一种比较高效节约的组合方式，我们用这个多级交换网络把八个处理器连接到了 八个内存系统上，同时我们只使用了1 2 个交换器，如果采用交叉开关结构，则需 要6 4 个交叉开关。一般而言，如果用2 2 交换器把n 个处理器连接到n 个内存 系统上，我们需要把连接结构分成l o g ，以级，每一级需要吡个2 2 交换器，一 共是( r 此) l o g ：”个2 2 交换器，在n 值较大时，这个数值跟以2 相比规模要小很 多。 虽然说这种结构的s m p 系统可以使用少量的交换器，但和基于交叉开关的 s m p 系统相比，它的交换网络是阻塞型的，因此系统中某些处理器发出访存请求 时可能需要等待。从整体性能而言，使用多级交换网络的s m p 系统在支持大量( 比 如干数级) 处理器时仍然表现良好，它成为了构建大型乃至超大型s m p 系统的首 选通信结构。 9 2 2 1 进程概念及原理 念 统 ， 概 即使是使用单处理器，现代计算机系统都可以同时做几件事，比如在运行用 户文本处理程序的同时还能在用户磁盘上读写数据，这一切归功于处理器不断地 在各个任务之间切换执行，从宏观而言，我们看到的是多个程序的同时运行，但 从微观上看，每个固定的时间点只有一个程序在处理器上执行。人们常常把这种 情况称为并发或者伪并行，以便和使用多处理器系统的程序并行运行相区别。我 们知道，计算机并不是十分聪明的，它只能根据我们的指令执行相关操作，为了 能使计算机能区别不同的程序并能自动地切换程序，人们把程序的运行实体抽象 出来，这个抽象实体就是进程。所谓进程，即是指硬盘上的程序的一个执行实体， 1 0 第二章s m p 系统及线程调度 它包含了该程序执行所需要的一切资源，包括硬件资源如处理器寄存器、内存等 和软件资源如程序代码、数据等，传统意义而言，进程是整个系统的调度实体和 资源分配的最基本单元。从进程本身来说，它认为自身完全占用了系统处理器和 其它一些硬件资源，而实际情况是：系统处理器在不同的进程之间来回切换，进 程对其它一些共享资源也要竞争访问。进程概念的提出，极大地简化了我们对系 统的理解，现在我们不必过多关心处理器是如何在程序之间来回切换，而只需要 知道系统中有多少个进程在并发运行即可，这种多个进程的并发执行也被称为多 道程序，图2 7 展示了个有4 个进程同时执行的系统。 进程切换 d + c 一 薹b 一一 al 时间+ 图2 7 多进程系统运行示意图 在该示意图中，四个进程都有自己的逻辑程序计数器，当处理器需要切换进 程时，它会保存当前进程的逻辑程序计数器并把下一个要运行的进程程序计数器 装入处理器的物理程序计数器，然后执行进程切换，进程切换包含软件资源和硬 件资源的切换。从示意图右边图例可以看出，总体上而言系统中所有进程都在不 断向前推进，但在某一个固定时刻系统中仅有一个进程在处理器上执行。 由于在进程的运行过程中，处理器会不断地在各个进程之间来回切换，因此 我们的进程运行过程是无法重现的，进程的总体运行时间也是无法预知的，我们 不应当在设计程序时对程序的执行时间和过程做出任何假设。 进程也是有状态的，在计算机系统中总是存在这样或那样的竞争关系，进程 常常因为这些竞争而不得不放弃处理器暂停执行直至某个条件为真，为了区分进 程的这些不同特性，我们给进程赋予不同的状态标识，进程在整个运行过程就是 不断地在这些状态之间来回切换，图2 8 展示了一个简单的进程状态切换图。图中 1 号状态转换一般发生在进程发现自己需要获取某个资源而得不到满足的时候，此 时进程一般需要执行某个调用将自己挂到资源等待队列上阻塞起来；2 号和3 号状 态转换是由系统调度程序引起的，举例来说，在分时操作系统中，每当一个进程 进程集两大不同的功能于一体：它既是系统资源分配的基本单位，又是系统调度 的基本单位。有时候，把这两大功能分开更能提高系统效率，因此人们就在操作 系统中引入了线程的概念，有了线程之后，进程仅仅作为系统资源分配的基本单 元，进程此时仍然拥有独立的地址空间和系统资源，包括打开的文件、子进程、 挂起的信号、记账信息等；但进程不再作为系统调度的最小单元，进程此时可以 包含一个或多个执行单元，这个执行单元就是线程。每个线程都有自己独立的程 序计数器用来标识线程下一条需要执行的指令，线程还有自己独立的堆栈，用来 存放线程当前工作变量及函数调用栈帧。 操作系统引入线程的目的在于能使一个进程中同时存在多个独立的执行实 体。在一个进程中存在多个独立的运行实体就和在一个计算机系统中存在多个独 立的执行进程一样。对于前者，所有的运行实体共享相同的地址空间、打开的文 件以及其它一些进程软件资源；对于后者，系统中所有的进程共享物理内存、磁 盘以及打印机等硬件资源。由于线程具有了进程的一些特性，它们有时候也被称 1 2 第二章s m p 系统及线程调度 勺轻型进程，所谓的多线程也用来描述在同一个进程中存在多个执行线程。 进程线程进程 线程 t 。、，_、 间t 三愆用户空间 h 舻蜘 u 内核窄问 内核窄间 在图2 9 图左边系统中，一共包含两个传统进程，每个进程内只有一个执行线 程，这2 个线程有独立的地址空间和系统资源；在图2 9 右边系统中，包含一个传 统进程，该进程包含3 个执行线程，这3 个线程共享该进程地址空间和系统资源。 虽然现代操作系统都引入了线程的概念，但各个系统在实现线程时可以采用不同 的策略，下面我们看看内核态线程和用户态线程以及它们的关系。 2 2 2 1 内核态线程 内核线程是指由操作系统在内核态创建并进行调度和管理的一类线程，使用 内核线程，我们常常可以获得与使用进程相同的性能，另外使用内核线程时，我 们不需要对那些共享地址空间的线程进行访存保护，我们也不需要在每次线程切 换时都进行内存刷新。内核线程可以用来实现很多传统的进程，比如p a g e d e 锄o n 进程、运行于s o l 碰s 系统上的网络守护进程等等。在多处理环境中，使用内核线 程我们可以使单个进程获得真正意义上的并行。内核线程可以在不同处理器之间 来回切换，也可以被静态指定到某个处理器上执行。 内核态线程最大的缺点在于，线程的创建、销毁和调度以及线程之间的同步 等都需要通过系统调用来实现，这在一定程度上增加了系统的开销。另外，如果 需要在线程之间频繁地进行切换，或者线程之间需要共享数据和同步操作，那么 内核线程将不是一个很好的选择 1 3 。 2 2 2 2 用户态线程 用户态线程提供了在用户空间创建、销毁、调度线程以及线程间通信的机制。 内核根本不会感觉到用户态线程的存在，因此使用用户态线程，我们还可以在不 支持线程调度的操作系统上创建出多线程环境。 电子科技人学硕士学位论文 用户态线程一般通过线程库的方式来实现，线程库通过抽象操作系统内核来 完成其功能。线程的一切资源，比如堆栈、程序计数器等都由线程库在用户空间 创建和管理，并且线程之间的切换也是在用户空间完成的，不会引起任何内核调 用开销，因此用户态线程之间的切换将会十分迅速。用户态线程最大的好处在于： 和内核态线程相比，它的性能十分优越，下面表2 1 【1 4 清晰地展示了用户态线程 带来的好处，下表中的时间以毫秒为单位。 表2 1 内核态线程与用户态实例比较 线程创建时间线程同步时间 用户态线程 5 26 6 内核态线程 3 5 03 9 0 虽说内核无法感知用户态线程的存在，但用户态线程始终要经过内核才能获 得处理器，下面图2 1 0 描述了一种用户态线程实现机制，用户态的线程库通过内 核线程来实现用户态线程，这就是所谓的多对多模型，即用户态的多个用户态线 程对应多个内核线程。 线程线程 ： 线程 线程线程 ： 线程线程 ： 粤、：弋：、止一： 空 间 线程库 f j ，。，7 。7 7 、? 、j h ? 、 间 一 、。 、 ， ? 、 ? 2 2 2 3lin u x 的线程模型 l i n u ) 【系统对线程的支持也有两种：内核态线程和用户态线程。在l i 肌x 内核 1 4 一 一 第二章s m p 系统及线程调度 内部，系统对内核线程不进行特殊对待，它仅仅把线程看着是一种特殊的进程， 这种进程和其它进程共享某些资源，因此l i n u x 内核线程和进程的概念差不多。由 于l i n u x 内核线程不需要访问用户空间内存，它的进程控制块里面的用户空间内存 指针可以为空，这说明l i n u x 内核线程在切换时不需要刷新用户空间内存，这样一 来l i n u x 内核线程的切换速度比其它进程的切换速度要快得多。 至于用户态线程，早期的“n u x 是通过提供c l o n e ( ) 系统调用提供支持的，c l o n e ( ) 能够创建调用进程的一份拷贝，并且新创建的拷贝是和调用进程共享地址空间的。 不幸的是，通过这种方式实现用户态线程有很多不足之处，特别是在信号处理、 调度和线程间同步等方面 1 6 】，另外，用这种方式实现的“n u x 线程机制还不能完 全符合p o s 规范。想要改进这些缺陷以提高l i n u x 的用户态线程性能，l i n u x 用 户态线程需要得到内核的支持，因此开源社区出现了两个开发团体来分别开发新 版本的用户态线程库，一个是由i b m 发起的名为n g p t ( n e x t g e n e r a t i o np o s i x t l = 嘴a d s ) 的项目，另一个是由开源巨头红帽发起的n p t l ( n a t i v ep o s i xt l l r e a d l i b r a r y ) 项目，直到2 0 0 3 年中期，n g p t 项目被终止了，现在最新的“n u x 用户 态线程库就是n p t l ，该线程库基本符合p o s i x 规范。 n p t l 使用了与早期线程库相类似的实现方法，内核感知的线程抽象仍然为一 个进程，新线程的创建也是通过c l o n e ( ) 系统调用实现的，不同之处在于，n p t l 要 求内核对例如在竞争情况下可能会引起线程睡眠或被唤醒的同步机制予以支持， 为此内核提供了觚e x ( ) 系统调用。n p t l 也被称为1 对1 的线程模型，所谓1 对1 是指用户态创建的线程( 使用库函数p t h r e a dc r e a t e (