（计算机科学与技术专业论文）kylin操作系统线程机制研究与实现.pdf

国防科学技术大学研究生院学位论文 摘要 线程机制为操作系统提供一种易用的并行处理模型，充分发挥在多处理机环境，特别 是s m p 环境下的多处理机的处理能力。实现一个高效率的线程机制，可以有效提高操作系 统的整体性能，这对改善国产服务器操作系统的市场生存环境有着重大意义。本文阐述了 国产服务器操作系统k y l i n 中基于多对多线程模型线程机制的设计思想和实现技术；并且， 通过这样一个具体问题的解决，在理论上对现有的线程模型机制进行了比较和分析，对线 程机制进一步的发展方向进行了讨论。 本文首先介绍了多对一，一对一和多对多三种线程模型的特点及实现技术，并对k y l i n 系统所采用的多对多模型进行了详细分析，表明其优势和存在的问题，为k y l i n 系统线程 机制的设计和实现做好了铺垫。 然后，基于多对多线程模型的设计思想，本文详细阐述了k y l i n 线程机制的总体结构， 重点介绍了基于多对多线程模型的两级调度模型；并针对传统多对多模型存在的问题，提 出了k y l i n 系统线程机制的优化方法，主要包含三个部分：两级调度器通信，内核调度优 化和用户级调度器优化。 接下来，由于k y l i n 操作系统需要对l i n u x 应用程序二进制兼容，本文介绍了k y l i n 系统线程机制提供的k y t h 线程库对原有l i n u x t h r e a d s 线程库的兼容技术，主要包含三个 方面：线程库版本兼容，系统调用兼容处理和信号兼容处理。 最后，本文对k y l i n 系统线程机制的性能和兼容性两个方面进行了测试，验证课题工 作的有效性和可用性。 关键词：多线程，线程模型，线程库，k y i n 第1 页 国防科学技术大学研究生院学位论文 a b s t r a c t m u l t “h r e a d i n gp r o v i d e st l i eo p e m t i n gs y s t e mw i mau s e f i l l 曲s t r a c t i o no fc o n c u n t e x e e u i o n ，a n d 出a w so u t 也ep c e 焱n gc a p a c i t yo ft b 嚣瑚u l t t p f o c e s s o r 。n v i 啪e n ，辨e c i a 珏yo f t h os m pe n v i r o 舳髓t ah i 酶e 艨c c l l e ti m p l e m e n t 8 t i o no fm u l t i m a d i n gw mp u s hu p 也e p e r f o 珊a 1 1 c eo ft 1 1 eo p e r a t i n gs y s t e m ，w h i c hi 8t l l em 0 8 ti m p o r t a n ta b i l i t yt om a l 【ek y l i ns l l r v i v e 泌攮em a 救蠛硅e 娜l t i 翻零藤i 珏g 黼e c h 孤 g 撒餐l ep 鞫s eo f 秣sp a p 嚣i s 协d e s c 纛b e | l 摊d e s i 辨 a _ n d i m p l e m e n t a t i o n o fm u l t i t h r e a d i n gi n k y l i no p e r a t i n gs y s t e m f l 玳h e 咖o m ，t m sp a p e r e o 糙p a r 耐a 嬲越& l 融璁噻ee x i s 褪酗瑚【d i 遐m o d e l s 浊如s i 黟8 娃o f 幽燃成n g 懿确滟e 魑 幽e nd i s c u s st h em a i nd i r c c t i o no f m em u l t i 懒r e a d i n gd e v e l o p m e n t f i r s t ，t 1 1 i sp 印e ri n 胁d u c e dm ei n 驴l 锄粕tt e c h n o l o g yo ft h r e a de x i s t e d 幽r e a d i l l g 黼d e l s 洫 e 辨积o no f 氆r e 斑穗g v i r o n m 锨t ：m ：lh d ，l ：lm o d l e 黝燃m o d l e 虢a l l y s e d 斑em ：n m o d l ew h i c hi su s e d 触k y h no p e r a t i n gs y s t 廿ni nd 眈a i l ，f o rp o i m i l l go u t 也ea d v 删t a g ea i l d 巍。嫩程峻堪旺娃矗s 斑r 龆妇毽氆礴l 吞 t h e n ，t h i sp 印c rd i s c u s s e dt l l ea r c i l i t e c t u r a la n di m p l 蝴e m a t i o nd e t a i l so f t h em u l t i n l r e a d i n g i nk ，l i nw 撼c hb a s eo nm em ：nt h r e 删n g 撙o d l e s p e c i a l l ya b o u t 也ec o u p l ed e g r e es c h e d u l 嚣 m o d l e f l l n h e 彻o f e ，w ei n t r o d u c o d 氆eo p t i m i z 曲l et e c h n o 】o g yo ft h em u l t i t h r d i n gmk y l 酶 w h i e hc o n t a i n st h r e ep a r t s ：c o 瑚喇u m c a t i o nm e c h a i l i s mb e 船e e nk e n l e ls c h e d u l e r 丑i l du s e d a n d s 凉。蠢l e f ， ( o m e ls 盎髭滋嚣o p t i m i z 采i o 毪撑s 藤鞠硅s 巍弱毽l c ro p 蛀辩i z a l i 曲 a f i e rt h a t ，t h i sp a p e re l a b o r a f e dt 1 1 et e c h n i q u e so f b i n a r yc o m p a t i b i l i t yb e n v e e nk y mt h r e a d l 弛糯了a 珏dl i n u x m e 嬲st h f e a dl i b 怒葛w h i g h 采c o 嫩班捂t h r e ep a n s ：c o 艄p 鑫鞋b i l i 移娃l 南r 田 v c r s i o n ，c o m p a t i b i l i t yo f s y s t e mc a l l sa 1 1 dc o r n p a t i b i l i i y “s i g n a lm e c h a n i s m a tl a s t ，m i sp a p e rp r e s e m e dt h er e s u l l 嚣o fp e r f o f m a 玎c et e s t i n ga 1 1 db i n a f ) rc 0 “节a t i b i l i t ) ， t e s t i n g 协d e 嫩。搬；t r 蠹ee 摄卺c t k i t y 辍癍璐e 氩娥s s 醴 鞋sw 髓k 。 至( 铐轷o f d s ：姒拄l 重i 接辩娃i 氅，t 纛矬a d 镪gm 稚l 嚣，t h 聪砖l 巍强秽，i ( y l 融 第1 i 页 国防科学技术大学研究生院学位论文 图目录 图2 1 多处理机系统发展过程4 图2 2 线程系统的演进6 图2 3 由传统进程支持实现用户级多线程8 图2 4 由操作系统内核支持实现进程内多线程9 图2 5 由用户多线库和内核混合支持的多线程1 2 图2 6 线程库位置1 5 图3 1k y li n 系统线程机制总体机制一2 0 图3 2k y l i n 系统线程相关数据结构对应关系2 7 图3 3 用户调度队列结构2 8 图4 1u p c a l l 机制相关数据结构对应关系3 4 图4 2 用户级调度器激活过程3 5 图4 3u p c a l1 与备用线程绑定过程3 6 图4 4 用户调度示意图3 6 图4 5 阻塞解除后线程返回用户态示意图3 7 图4 6 线程由核心态返回用户态示意图3 7 图5 1k y t h 线程库位置4 3 图5 2 信号的检测与处理流程图5 1 图6 1 线程创建销毁开销5 5 图6 2 单处理机环境下线程切换开销5 6 图6 34 c p u s m p 环境下线程切换开销5 6 图6 4 超线程模拟8 c p u s m p 环境下线程切换开销5 6 第j v 页 国防科学技术大学研究生院学位论文 表目录 表2 1 在s p a r c 工作站上不同线程，进程操作开销比较1 1 表3 1 进程结构关键域说明2 l 表3 2 用户线程数据结构关键域说明2 2 表3 3 核心线程数据结构关键域说明2 3 表3 4 用户调度实体数据结构关键域2 4 表3 5 内核调度实体数据结构关键域说明2 5 表3 6k s e g 数据结构关键域说明2 6 表4 1u p c a l l 数据结构关键域说明3 4 表6 1 分项性能测试结果5 4 表6 2 综合性能测试结果5 7 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：! z ! i ! 握佳蠢统堡焦扭剑煎窀兰塞墨 学位论文作者签名：迷塑量日期：训广年工月二? 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：基￥! i ! 握住圣统堡壁拯剑盈盔盏塞理 学位论文作者签名： 一搅量 作者指导教师签名：兰圣丝 日期：) 峨 年j 2 月】p 日 日期：冽乙月吵日 国防科学技术大学研究生院学位论文 第一章绪论 1 1 引言 通常来说，对计算机系统整体性能的要求和用户对于易用性的要求存在着一定的矛 盾，而计算机体系结构的研究者一直在致力于解决这一矛盾，体系结构的发展史实际上可 以看作是两者不断折中的过程。操作系统在如何充分发挥体系结构的高性能，同时又提供 易用的用户界面方面起着非常关键的作用，其中一个重要表现就是操作系统的执行模型。 线程，作为目前绝大多数操作系统的执行实体，它的运行环境的变化直接反映了操作系统 的变化。 线程是进程的执行体，同一个进程中的所有线程能够共享进程的资源，提供最大化的 并行，在多处理机环境，特别是s m p 环境下能充分发挥多处理机的处理能力。在目前的 主流操作系统中，线程是应用程序主要的编程接口。 为了支持用户进程内多线程，传统有两种典型的线程的实现方法，即多线库支持线程 实现和核心支持线程实现。多线库支持的进程内多线程是在原操作系统不作更改的情形 下，由库程序实现多线程管理，多线库实现的多线程分时地在进程中运行，由多线库线程 调度器负责线程的调度与切换，在内核看来，该进程运行着用户的程序而完全不知何时在 用户多线程中切换。核心支持线程实现是在多处理系统出现后，因多线库支持的进程内多 线程并不能够同时在多个处理机上运行，需要操作系统见到进程内多线程的存在，并为 这些线程占用处理机运行。我们把多线库支持的线程称作用户级线程，把核心支持的线程 称作核心级线程，或轻权进程l w p 。在现代操作系统中，往往采用新的混合策略，结合 这两种实现方法的优势，以满足用户方便地进行多任务程序设计且使多任务高效地占用多 处理机运行。 本文将详细讨论k y l i n 系统中基于多对多线程模型混合策略线程机制的设计思想和实 现技术。 1 2 课题背景 本次课题来源于国家8 6 3 重大软件专项课题“服务器操作系统内核”。 操作系统作为软件体系中最重要的部分，是建立自主基础性软件技术体系的关键，是 软件产业核心竞争力的体现，是信息系统安全的重要保证。k y l i n ( 麒麟) 是在国家8 6 3 计 第l 页 国防科学技术大学研究擞院学位论文 划支掩下，密謇蠹在操 誊系统领域有筏麓蔌繁熬国防群大、孛软总公司，联会在豢 棼系统 推广方面有市场优势的联想、浪潮和中科院软件所合作开发的自主服务器操作系统内核。 课题历时3 年，先后推出4 个版本，完成源代码2 5 0 万行，参照瀚际主流标准，借鉴u n 操穆系统窝微内核操佟系统鲍设计愚怒，具蠢垂主舨投，支持多荦孛c p u 芯片窥多摹孛诗算 机体系结构的，具脊高性能、高诃用性与高安全性，并与l i n u x 皮用和设备驱动二谶制兼 容。 线程玮境是操作系统与应用的结会点，一方匿楚充分发挥操作系统性能、特别是s m p 性能的关键，另一方面又是操作系统的重要编程接口，体现着可扩展性和可移植性等多个 易用瞧要求。 k v l i n 系统最初采用l i n u x 操作系统的线穗机制，并使用l i n u x 操作系统上的 l i n u x t h r e a d s 线程库作为系统默认线穰库。“n u x m e a d s 线程库采用一对一线程模型弼， 一令线程实体对应一个核心轻鬃级进程，调度交给核心，薅在薅户级实凌一令包括露号处 理在内的线程管理机制。这种线程机制主要存在以下几个问题： 一对一线程模型需要搽作系统维护核心级绫程静备种管疆表格，负责线程巍处理 机上的调度和切换，占用系统窆同及资源，创建歼销巨大，限制了系统的并行性。 管理线程霖易成为瓶颈，这是这种结构的通病：同时，管理线程还负费用户线程 约铡建蠢溃理王终，嚣魏，一量警毽线程意步 死亡，震户线程虢不褥不手工清理 了，而且用户线程并不知道管理线程的状态，之后的线糕创建等请求将无人处理。 l i 蝴x 1 耐e a d s 并不是完全p 0 s 兼容的，这在它的发行版的r 嚣a d m e 中有说明。 赈有的线程极铡严重影响了x - y l 巍搽终系统毂熬体蛙熊；恧p g s 燕骞憋主毂润题， 也阻碍了k y l i n 上的跨平台应用采用多线程设计，从而使得k y l i n 上的线程应用一直保持 在 匕较低鹃窳平。蠲诧，实现一稀垒掰的离教酌线程视铡麓k y l i n 操作系统静迫切需求。 1 3 课题研究的内容和完成的工作 本次谋题研究了国产服务器操作系统i 【y l i n 多线程机制实现技术。课题的工作主要包 括以下几令方瑟： 研究了各种线程模型的特点及实现技术，重点针对较新的多对多模型的问题进行 了分析； 总缋了当前主流操作系统线程机制的实现技术，对k y l i n 操作系统原商线程机制 性能低下的问题提出了解决方法； 设诗了x y l i 珏系绞基于多对多模垄线程凝铡戆总髂框架； 针对多对多线程模型的问题，程k y l i n 系统上实现了基于u p c a u 机制的两级调度器 第2 页 国防科学技术大学研究生院学位论文 通信： 口根据k y l i i l 操作系统的特点，分别对用户调度器和内核调度器进行了优化； 研究了当前主流线程标准，并在k y l i n 系统上实现了k y t l l 线程库为用户提供了线 程相关a p i ； 研究了操作系统共享库实现技术和k y l i n 对l i 肌x 应用的二进制兼容技术，成功的 用硒他线程库取代了原有的l i n u x t h r c a d s 线程库，实现对原有“n u x 应用程序二 进制兼容。 相关研究工作整理成论文“m u l 枷1 r e a d i n gi nt h ek y l i no p e r a t i n gs y s t e mf i ) rh i 曲e n d c o m p u t 咄”和“k y l i n 服务器操作系统多线程机制的研究与实现”，分别发表在t l l e8 m i n t e n l a t i o n a lc o n 矗玳n c eo nh i g l lp e r f o 咖a l l c ec o m p u t i n gi i la s i ap a c i f i cr e g i o n 会议和 2 0 0 5 信息存储会议上。 1 4 论文的组织 全文共分七章，结构如下： 第一章“绪论”，介绍了线程机制相关概念，以及本次课题的基本情况。 第二章“多处理机系统线程环境”，回顾了线程环境的发展历程，总结了当前各种线 程模型的特点，重点针对多对多模型进行了分析，介绍了主流的线程标准，最后对线程机 制的研究进行了总结。 第三章“k y l i n 操作系统多线程机制设计与实现”，介绍了k y l i l l 中基于多对多模型线 程机制设计思想和总体结构，以及基于此机制的两级调度模型。 第四章“k y l i n 操作系统线程机制优化技术”，介绍了基于u p c a l l 机制的两级调度器通 信的解决方法，和对两级调度器分别进行的优化技术。 第五章“k y f h 线程库二进制兼容技术”，论述了k y t h 线程库替代原有l i n u x m e a d s 线程库，并对应用程序二进制兼容的解决方法，主要包含三个部分：库版本信息加入，系 统调用处理和信号处理。 第六章“k y l i n 系统线程机制评估”，分别从性能和兼容性两个方面对k y l i n 线程机制 进行了测试，验证课题工作的有效性和可用性。 第七章“总结与展望”，是对本文工作的总结和下一步工作的设想。 第3 页 宦堕型堂垫查奎堂竺塑生堕兰竺笙苎 第二章多处理机系统线程环境 2 1 多处理机系统发展 计算机系统是从单处理机发展起来的，对提高系统性能最直接的解决办法就是增加处 理机的数量。从单处理机系统演进到多处理机系统，是计算机体系结构上的一次飞跃，也 引起了操作系统领域的一次革命。 在多处理机系统发展过程中，随着处理机数目的增加，处理机之间的通讯、处理机与 内存之间的通讯越来越频繁，这就要求更大的通讯带宽和访存带宽，而在现有的技术条件 下，带宽是存在上限的。设计更高性能的多处理机系统，要么就努力提高带宽，从而能够 容纳更多的处理机；要么，就在结构上做文章，继续增加处理机数量，同时分散通讯流量。 对称多处理机系统( s m p ) 是沿着前一条路发展下来的，各大计算机厂商都有成熟的 产品。与s m p 系统的集中式处理方式相对应，多处理机系统的另一个发展方向就是分布 式处理，即节点间采用松耦合方式，使用消息传递来联系较为独立的节点操作系统。典型 的大规模并行系统( m p p ) 通常由异构的计算节点和i o 节点通过高速网络连接而成，不 同角色的操作系统分别运行于各个节点之上。因为这种结构最大程度地降低了节点间的通 讯，因此它能集成更多的处理机。但m p p 系统的执行模型与直观的程序运行大相径庭， 应用软件的开发和维护都比较困难，因此一直以来都在易用性上饱受诟病。两种思路的折 中即是当前主流高性能计算平台之一的n 1 订a ( 非一致性内存访问，n o n u n i f o 珊m e m o n r a c c e s s ) 【3 6 】。下图显示了多处理机的发展概况： 并行向量机铆p 图2 1 多处理机系统发展过程 第4 页 嚣茨释学致零大学研究生茨掌经论文 s m p 的全称怒对称多处理枫”( s y m m e 砸c a 】m u l t i m p r o c e s s i n 曲，是指在一个计算机上汇 集了一组处理器，各c p u 之间共事内存子系统以及总线结构。在这种架构中，台电脑不 再由单个c p u 缎成，而嗣时由多个处理器运行操作系统，而且共同使用内存和其他资源。 虽然同时馒鼹多个c p u ，但是对用户来说，它粕豹表现就像一台单枧一榉。系统将强务分 配绘多令c p 珏，跌蠢疆裹了整个系统豹数据筵瑾力。程鼹稼多照瑾系统审，系统资源被 系统中所有的溯u 共享，工作负载熊够均匀地分配至i 所宥可用处理器之上。 这种机器的好处在于它的使用方式和普通计算机的隧另不大，编程的巍化相对来说比 较小，原来用普通计算机编写的程序如果要移植到s m p 机器上使用，改动越来也相对比 较容易。 s m p 褪关按零琏：较藏熟，穗疲斡载徉也跨较多，嚣鼗凌在国内帝殇上接爨酶荠行梳大 都是这一种。p c 服务器中最常见的时称多处理系统通常采用2 路、4 路、6 路或8 路处理 器。作为服务器操作系统，k y l i 将燕要面向这一平台进行开发。 2 。2 线程嚣境酶发震 2 2 1 线程概念的撰出 操作系统作为计算机硬件的管理者和“第一个”使用者，总是随着硬件结构的变化而 变化。 早在多处理枫系统出现以翦，多邋程序设计就已经广泛应耀予单处理枫繁统之上。由 子1 0 速度譬逮谩予处瑾瓿速度，将多个应恁的l o 霹瓣秘c p u 露藏重叠纛皋，可戮春效 地发挥系统的处璃能力。单处理枫系统上的任务并行藏怒采用这样的办法来宓现的。 在操作系统中，可以用“进程”来描述任务。进程怒计算机资源管理的燕体，对处理 器和内存进行了软件级的抽象。从系统外部看，并发的邀程似乎是在独立的处理机+ 内存 上运 亍， o 设搭蓑l 共享使翅。“进簇”瓣弓| 入是搡终系统设计领域孛豹又一个墨程薅，它 给搡俸系统设诗滋及编翟恶路嚣带来鹣影豌一童延续至l 璇在。 但随着处理器本身技术的飞速发展，处理器速度已缀远远超过了内存访问的速度，而 且目前的趋势是麓距会越来越大【1 0 】，对于多处理机系统( 不管是s m p 还是其他内存结构) ， 这种差距尤其明艇。在进程模式中，处理机和内存绑定襁一起，访存延迟对进程的运行效 率畜穰夫豹影豌，歪翅“遂程”豹零| 入胃酸隳藏著行任务鹣站延迟一撵，“线程”效g | 入 揉彳乍系统翡撬行模型之中，班使更好壹| 煞隐藏访存延迟。 线程是进稔的执行体，是对处瑷机的抽象，是进一步分离操作与数据的产物。在线程 模型中，进程魑资源管理的最小单位，线程是程序执行的最小单位，同一谶穰内所有线程 共享进程的内存资源。 燕5 页 国防科学技术大学研究生院学位论文 多线程技术最早出现于用户程序设计技术中，在多处理机环境下，核外的线程无法充 分利用多处理机资源，存在着先天的不足。九十年代以来，将线程模型引入操作系统普遍 成了各种操作系统的研究热点。 l 眵 多道程l 序环鼍f ：函 1 一融竺生 上 j 一一 ll 编程模型内棱组织 汐 图2 2 线程系统的演进 在s m p 系统中，进程的所有资源都可以由线程共享，多个执行体可以并发地在多个 处理器上运行，只要应用程序协调好多个线程之间的同步，对应用程序性能的提高非常明 显。可以说，s m p 是线程模型最合适的运行平台。目前的中端市场上s m p 系统应用范围 越来越广，操作系统必须提供对s m p 系统的高效支持。多线内核，线程模型，这些都成 为操作系统设计中一个不可避免的问题。各大商用计算机厂商，如今都在核内不同程度地 实现了多线程技术，从1 9 9 1 年绝大多数操作系统都没有线程支持，到1 9 9 7 年，包括i b m a 、d e cd i g i t a lu n i x 、h ph p u x 和s l l i ls o l a r i s ，以及m i c m s o f cw i n d o w s 在内的主流 操作系统，都提供了核心线程支持，这个从无到有的过程仅仅6 年。 2 2 2 不同体系结构下线程环境嘲 线程环境的设计直接植根于硬件体系结构而服务于应用程序，在单处理机系统中，线 程实际上是属于应用层的技术，多线程所实现的功能，同样也可以在进程内部通过调整程 序执行顺序来实现，使用线程只是使得程序设计更加清晰。 在基于消息传递的系统中，因为节点机操作系统相对独立，而线程模型是以处理机为 第6 页 国防科学技术大学研究生院学位论文 抽象对象的，所以并不能直接应用于全系统的处理机集合上，仅能影响节点机内部，全系 统中发挥并行作用的执行模型还是以进程甚至更大粒度的“任务”为基础的。 线程环境研究的重点在s m p 平台，绝大多数涉及到的问题都是针对或者首先针对s m p 环境提出的。对于s m p 系统的线程环境来说，最关键，也是最具代表性的问题就是如何 在多个对称的处理机上分配和调度线程。基于s m p 的处理机分配算法、线程调度算法研 究一直相当活跃，基于负载平衡原则而进行的线程迁移研究也是s m p 系统下线程环境研 究的热点。 2 0 世纪9 0 年代中期以来，围绕m j m a 的局部性开发研究就逐渐热起来，特别是页迁 移( 静态的或者是动态的) 技术，提出了很多算法和机制。但是，到目前为止，绝大多数 m 乃订a 下的操作系统研究都集中在数据分布问题上，而置数据使用者( 即线程) 于不顾。 实际上，局部性开发是数据及其使用者交互的过程优化【3 4 l ，仅仅考虑静态的数据，而不考 虑动态的线程环境，要想取得很好的效果是比较困难的。 在局部性开发的数据分布研究领域，很多研究成果和研究方向都强调用户( 应用程序) 的适度参与，操作系统和编译器需要用户提供的数据分布信息来优化执行和调度。m n 讧a 平台上的线程环境研究中，这一方向也同样具有相当大的吸引力。 不同的体系结构对于线程环境有不同的要求。目前的线程环境主要是针对s m p 系统 设计的。由于线程环境实际上是操作系统运行控制机制中的核心环节，它对系统整体性能 的影响不可低估。 2 3 线程模型研究 在操作系统实现上，用户线程需要映射到内核的执行体上才能得到运行【3 4 】，根据映射 方式的不同，线程环境的组成结构也有所不同，通常可分为多对一、一对一、多对多三类， 分别表示“多个用户线程对应一个内核执行体( 可能是线程，也可能是进程或轻量进程， 与具体的内核执行模型有关) ”、“一个用户线程对应一个内核执行体”和“多个用户线程 可挂靠多个内核执行体运行”三种不同的线程模型。 2 3 1 传统线程模型 2 3 1 1 多对一线程模型与用户级线程实现 多线库支持的进程内多线程，即多对一模型，没有操作系统内核的支持 完全在用户 级提供一个库程序来实现多线程。线程库提供了创建，同步，调度与管理线程的所有功能， 无需操作系统特别支持，由于对线程的所有操作都不涉及内核，因此，用户级线程的创建， 结束，调度，现场保护与切换开销非常少，图2 3 给出了在传统操作系统进程基础上实现 第7 页 壁堕型兰垫查查兰塑茎生堕兰垡堡苎 用户级线程示意图，p 是传统操作系统进程【2 0 】。 进授2 图2 3 由传统进程支持实现用户级多线程 从图2 3 的示意图可以看出，用户级线程的所有管理控制全部由多线库承担，所有线 程的管理控制用表格都存放于进程的用户空间；操作系统只感觉到进程存在，除在进程创 建及安排初始程序执行时由操作系统过问外，进程以后在各线程的切换，产生及结束线 程，操作系统全然不知，操作系统进程调度程序安排进程占用处理机，而不管多线程对进 程的占用。 一个由用户利用多线库编写的多任务程序，象一般的用户程序一样作为执行文件存放 于外存中，在进程创建时由操作系统将程序与数据段映射到用户进程虚空问，并从初始入 口开始执行，这时初始程序作为主线程在进程中运行，当需要产生新线程去运行并行任务 时，主线程程序安排一个多线库调用产生一个线程，并说明要执行的过程段或函数及初始 数据，多线库会建立好新线程的所有管理表格，分配栈空间和线程私有存储空间，当用户 线程将控制交给多线库后，多线库会在处理完线程请求之后作线程调度，如果没有线程切 换，则控制返回到调用者线程，当需要进行线程切换时，多线库为原运行的线程保护好处 理机运行现场，选取由它管理的一个就绪线程，并恢复新线程的处理机运行现场。 多线程库对传统进程创建后所运行的初始程序序列看作主线程，主线程的栈区是沿用 原来进程用户栈的约定空间，多线库程序第一次运行时会分配好主线程被切换时所需的保 护现场的空间，以后线程的创建，则由多线库在用户虚空间分配好管理表格空间及栈，私 有存储区等空间。 基于这种模型的线程库有m a c h 操作系统的c t 1 1 r e a d s 库和f r e c b s d 操作系统中的 l i b cr 库。使用这种模型有以下几方面的优势： 为用户提供一个简明的同步并行编程环境如多线库可为用户提供同步i ，o 请 求，而多线库利用操作系统的异步工o 支持，当请求i ，o 的线程在同步等待i ，o 第8 页 国防科学技术大学研究生院学位论文 完成时，多线库向操作系统发送异步i 0 ，在操作系统收到异步i ，o 请求后控制 返回多线库程序时，多线库把请求同步工，o 的线程阻塞，调用其它线程运行，等 到操作系统i ，o 完成后，多线库才将阻塞的线程变到就绪状态，多线库把用户 的同步请求转化成了对操作系统的异步请求 开销小线程的建立、结束、切换，管理都由多线库完成，多线库是在用户态执 行的程序，所有管理数据结构也都在用户空间中，无需操作系统内核作任何支 持，因此没有运行模式切换的开销 无需改变操作系统核心，用户级线程完全由用户级库程序实现，实现非常方便 用户可以根据应用的并行度，申请足够多的线程而无限制 其缺点也很明显： 不能做到进程内线程在多处理机上真正并行运行，如果系统拥有多个处理机，操 作系统调度进程占用处理机运行，它无法感知进程内多线程存在，因而无法让用 户进程在多个处理机上同时运行 如果用户级线程发系统调用或中断进入操作系统，因某种原因其所在进程被阻 塞，多线库无法知道刚运行的线程被阻塞，因此也不能够转到其它线程运行这 种情形下可以对多线库加以改进，让可能引起阻塞的系统调用统统经过多线库 转发，使多线库能够根据情况调度其它线程运行。 2 3 1 2 一对一线程模型与核心级线程实现 核心级线程是由操作系统支持实现的线程，又称为一对一模型。操作系统维护核心级 线程的各种管理表格，负责线程在处理机上的调度和切换。操作系统提供了一系列系统调 用界面让用户程序请求操作系统作线程创建，结束等操作，这种核心级线程在许多地方又 称轻权进程，简称l w p 【2 0 1 。 ：迸程2 图2 4 由操作系统内核支持实现进程内多线程 第9 页 国防科学技术大学研究生院学位论文 鹜2 ，毒绘密了核心缀线程实瑷示意鬻，图孛毛是理瞪瓣臻写，捉表了搽锋系统表 示、管理的核心级线程的数据结构每个进程可以有多个核心级线程，核心级线程用于运 行并彳亍执行的用户任务，当它被夕 部中断打断或自酸进入操终系统时，也运于亍操作系统内 榱程序。 当个进程被创建时，系统同时创建个核心级线程，用户初始穰序即在该核心级线 稔主运行，我稻称之魏圭棱心线程，当嚣蒺餐建薪鹣线程去遮霄并行强务辩，差核心线程 邋行的程序安排一个线程创建系统调用产生一个新的核心级线程，并说明要执行的过程段 袋邈数及拐始数据，嬲隧遣要麓该线程掇供一个髑户搜空闯，线程戆翅户我空阕帮在进程 厢户虚空间区，除第一个线程栈空间在线程初始化时按约定颈留外，菇它线程栈空间由用 户态运行程序自行分配内核建好核心级线程的线程控制块t c b 等镑理数据结构，为线 稳分配一个孩心棱空瓣i 线程巍运行蘑户程序辩在掰户筏上王俸，当审断或鸯陷遴入搡终 系统核心运行时，则转到核心栈上工作。 攥 筝系绞蠹孩必须必每令线程保存系刭搐逮信塞，线稷被曩终魅淫凝熬扶学单蕴， 操作系统对处理机分配改为以线程为对象因此核心级线程可以完全并行地在系统的不同 处理枧上逡行，操作系统可以支持核心级线程与物理处理器之闻豹捆绑，让用户干预核心 缀线程选定处理祝运行，当核心缀线程获用户程序转操作系统核心程澎运行后，如果有彭 o 请求或等事件同步引起线程阻塞，或者有更高优先级的线程可以运彳予，操作系统线程调 凌撵亭会终线程甥抉楚毽，瑷场保护嚣滚笺舔在线疆提关懿数黎结稳之牵进行。 利用操作系统核心支持的核心级线稷实现的线程库比较麒型的就魑l i 删x 操作系统的 p 娃黼a d 线稳蓐窝臻l 线程瘁。这秘模型的特点如下： 可隧支持进獠肉多线稔在多处理桃上真正并行执行，这是因为核心处理桃调度程 序烧以线程为单位，调度程序可以选定同一进程的线程同时占用处理机具体实 瑶辩，调度程序选取闲透程牵髂就绪线糕，据它稻放在各懿遴税等符运行豹位 鼍，通过机间中断通知各处理机邋行线程切换程序，各处理机即可切换剜同一进 程熬线程上运簿。 不套出现用户级线程实现方式下，线程在内核被阻塞但多线库调度器一无所知 由予线程调度在核内进行，如果线程困等事件阻塞，犊心即可将处理枫切换到其 它线程上运行。 核心机线程的性能，虽然较传统进程存在着优势，但与最好的用户缎线程比越来，仍 然存在着数鬟级上敢纛踅，下甏是蘧产缀线翟，核心缀线程及遴程豹裁建与露多秀锖： 第1 0 页 国防科学技术大学研究生院学位论文 表2 1 在s p a r c 工作站上不同线程，进程操作开销比较 操作用户级核心级进程 创建 5 2 3 5 01 7 0 0 使用信号量同步 6 63 9 02 0 0 0 这种性能上的差距主要来自于以下两个方面【i 】： 访问线程管理操作的消耗：对于内核线程，甚至当处理器在同一地址空间上切换 线程时，程序必须为每个线程操作施加额外的保护边界。这不仅产生了额外的内 核陷阱o ( e m e l 仃a p ) ，还使得内核必须复制和检查参数，以便在面对有错或恶意程序 时能够保护自身。与此相反，特别是在编译技术被可以用来内联展开代码和高精 细的寄存器分配之后，调用用户级线程操作是相当廉价的。进一步来说，安全性 也不会受到损失：地址空间边界会将用户级线程系统在程序中产生的误操作隔离。 通用性的消耗：在内核线程管理中，所有的应用程序都使用一个基本执行体。为 了适应多用途，内核线程系统必须向所有可能出现的应用程序提供所有会被需要 的特征。这会给那些不需要特定特征的应用程序带来负担。相反地，用户级线程 系统所提供的工具能够最接近地匹配那些有特殊需求的程序。这是因为不同的应 用程序能够被链接到不同的用户级线程库上。例如：绝大部分内核线程系统都采 用抢占式优先级调度，但也有许多并行应用程序使用诸如：先进先出这样的简单 策略。 另外，核心级线程占用系统空间及资源，并不适合用户根据其任务的并行度来创建相 应多的核心级线程如果用户任务并行度很高，为每个并行任务申请一个核心级线程，若 系统中存在许多这种用户，系统资源会马上消耗光。 2 3 2 多对多线程模型与混合策略 用户级线程和核心级线程实现方式各有其优缺点，摄早由s u n 公司在s o l a r i s 2 ，o 操作系 统中提出的多对多线程模型正是希望能结合两方面的优势。图2 5 给出了这种线程模型的 示意图f 2 0 】。 第1 1 页 国防科学技术大学研究生院学位论文 图2 5 由用户多线库和内核混合支持的多线程 在这种实现系统中，用户利用多线库提供的并行程序设计界面编写用户并行程序，可 以根据用户应用并行度的需要产生足够的用户级线程核心级线程的操作系统调用界面只 提供给多线库使用，用户可以完全不知多线库使用了几个核心级线程，也可以通过多线库 的接口申请更多的核心级线程，所有核心级线程都由多线库管理使用，由多线库选择用户 级线程在哪一个核心级线程上运行 用户利用多线库函数编写的并行程序作为用户执行文件，在进程创建时，被映射到进 程用户虚空间中，第一个核心级线程随进程同时被创建，用户程序的主函数在该线程上运 行，随后，用户程序可以调用多线库创建新的用户级线程，也可以请求多线库到核心去申 请更多的核心级线程，每当多线库申请创建一个核心级线程，多线库让该核心级线程运行 与核心级线程相关的初始化工作后即转到用户线程调度程序运行，在该核心级线程上运行 的多线库调度程序即可以再调度用户级线程，将控制交给被调用户线程。 进程内使用多少个核心级线程可以由系统提供省缺值，多线库在第一次运行时按省缺 值到内核申请创建核心级线程，也可以由用户动态提出申请一般来说，核心级线程个数 与系统处理机个数相当为宜，太多的话占用系统资源太多，太少的话不能让进程内多任务 真正在多处理机上最大程度地并行 ， 多对多线程模型提供了更大的灵活性和优越性。当应用不需要并发运行时，可以利用 单线程进程结构；当程序设计需要表示并发丽不真正需要多线程并行执行时，可以建立多 个用户线程，对应于一个内核线程；当应用需要全面并行，则建立多个内核线程，采用两 级调度器，尽量避免开销较大的内核级线程切换。 第1 2 页 国防科学技术大学研究生院学位论文 2 3 3 多对多线程模型的问题与s a 论文 尽管多对多线程模型提供了更大的灵活性和优越性，但同时也带来了设计上的复杂性 和隐含的性能瓶颈嘲。对于这个问题，t h o m a se a n d e r s o n 等人在a c m 上发表的”s c h e d u l e r a c t i v a t i o n s ：e f f e c t i v ek e r n e l s u p p o r t f o rt h eu s e r 一1 e v e l m a n a g e m e n to f p a r a l l e l i sm 【“”一文中进行了详细的论述。 传统的多对多线程模型主要存在以下两个方面的问题： 用户级调度器无法感知内核线程的行为变化，内核线程的阻塞，恢复和抢占不会 通知用户级。 内核线程的调度，不会考虑到用户级线程的状态。 一般情况下，使用多对多线程模型的系统中，用户级线程系统通常需要创建与系统中 物理处理器一样多的内核级线程来做为“虚拟处理器”，并在其上运行用户级线程。当一 个用户级线程发出一个阻塞i o 请求或者产生缺页时，作为它的虚拟处理器的内核线程也 会被阻塞。因此，当i o 请求被挂起时，物理处理器将不再运行在该地址空间，因为没有 内核线程能在刚刚空闲的处理器上运行其他用户级线程。这样实际上没有发挥出系统最大 的并行性，完全没有体现出多对多线程模型灵活绑定的优势。 一种似是而非的解决方案是创建比物理处理器还多的内核线程；当一个内核线程由于 它的用户级线程在内核被阻塞，另一个内核线程将允许在那个处理器上运行用户级线程。 但是，当完成i 0 操作或者缺页返回后，由于内核调度器无法考虑用户线程的状态，难题 就产生了：会存在着比处理器数目更多的就绪态内核线程，每个内核线程中都在运行一个 用户级线程。在决定哪个内核线程会分配到处理器后，操作系统会盲目地将用户级线程分 配给处理器。 另外，在传统系统中，当存在比处理器更多的线程时，操作系统会采用某种类型的时 间片策略去保证每个线程的运行。当用户级线程运行在内核线程上时，时间片会导致一些 问题。例如，当用户级线程持有一个自旋锁( s p i n l o c k ) 时，内核线程将会被抢占；任何 访问锁的用户级线程都将处于自旋等待( s p i n w a i t ) ，直到锁的持有者被重新调度。 z a h o r j a ne ta 1 已经证明在自旋锁存在的前提下，时间片会导致低下的性能。另一个例 子是，一个运行着用户级线程的内核线程会被另一个在用户级调度器处于空闲的内核线程 抢占。或者，一个运行着高优先级用户线程的内核线程会因对一个运行着低优先级用户线 程的内核线程有利，而被剥夺调度资格。 因此，多对多线程模型主要要解决是两级调度器的通信问题，如何实现一个高效的调 度器通信机制是提高多对多模型性能的关键。 第1 3 页 旦堕型兰垫查奎堂堕窒生堕兰竺笙苎 2 4 线程标准与线程库眈2 1 2 4 l 当前主流线程标准 目前，有三种主流的线程标准： 1 w i n 3 2 2 0 s 2 3 p o s i x 前两种线程都只能应用于他们各自平台：w i n 3 2 线程只能运行于n t 和w i n d o w s 系列操 作系统上，0 s 2 线程只能在0 s 2 平台上。 p o s i x 规范( i e e e