（计算机科学与技术专业论文）线程调度方法与测试工具的研究与实现.pdf

r e s e a r c ha n d i m p l e m e n t a t i o nt e c h n i q u e s o nt h r e a ds c h e d u l i n gm e t h o da n di t s t e s t i n gt o o l s c a n d i d a t e ：j i a n gb o a d v i s o r ：p r o f y a n ggu o g u i at h e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t s f o rt h ep r o f e s s i o n a ld e g r e eo fm a s t e ro fe n g i n e e r i n g i nc o m p u t e rt e c hn o l o g y 一 一一 g r a d u a t es c h o o lo fn a t i o n a lu n i v e r s i t yo fd e f e n s et e c h n o l o g y c h a n g s h a , h u n a n ，p r c h i n a ( j u n e ，2 0 1 0 ) 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文作者签名：簋选 日期：抄加年月7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目： 学位论文作者签名： 荟次 日期：抄，口年月7 日 作者指导教师签名：型旦垄趔芘) 日期： 矽口年月夕日 国防科学技术大学研究生院t 程硕士学位论文 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 线程调度概述1 1 2 课题背景与研究意义2 1 3 研究内容和主要工作。3 1 4 论文组织结构3 第二章线程调度相关研究与分析5 2 1 多片多核体系结构5 2 2 调度器的发展及关键技术分析6 2 2 1l i n u x 2 4 的o ( n ) 调度器7 2 2 2l i n u x 2 6 的o ( 1 ) 调度器8 2 2 3s d 、r s d l 与c f s 调度器1 l 2 2 4 调度器性能优化分析1 9 2 3 相关测试方法2 1 2 4 相关测试工具2 l 2 3 1l m b e n c h 2 2 2 3 2s y s b e n c h 2 4 2 3 3t p c c 2 5 2 5 本章小结2 6 第三章线程调度性能评测方法研究与建模2 8 3 1 性能评价指标2 8 3 1 1 线程切换代价2 8 3 1 2 调度器的扩展性2 9 3 1 3 周转时间公平性。3 0 3 1 4 综合效率3 2 3 1 5 其它指标3 3 3 2 选择测试程序3 3 3 3 测试框架模型3 4 3 4 测试运行规则3 5 3 5 本章小结3 6 第1 页 国防科学技术大学研究生院1 二程硕士学位论文 第四章线程调度性厶。l a - i l ，1 1 1 试工具设计与实现3 8 4 1 线程切换代价分析工具设计与实现一3 8 4 1 1 延时测量算法3 8 4 1 2 同步机制设计4 0 4 1 3 负载模式设计。4 l 4 1 4 调度策略设计4 2 4 1 5 切换模型及实现4 2 4 1 6 测试统计自动化。4 5 4 2 调度器体系结构扩展性分析工具b l t 设计与实现4 7 4 2 1 任务分配特性分析4 7 4 2 2 测试模型实现4 8 4 2 3 缓存负载设计。4 9 4 2 4 控制调度范围。5 0 4 2 5 测试统计自动化。5 l 4 - 3 本章小结5 4 第五章线程调度性能评测与分析5 5 5 1 测试环境5 5 5 1 1 硬件体系结构。5 5 5 1 2l i n u x 内核5 5 5 1 3 数据库5 5 5 2 切换代价评测。5 6 5 2 1 额外开销分析一5 6 5 2 2 多负载环境线程切换代价分析5 6 5 2 - 3 调度器线程切换代价对比分析。5 9 5 3 任务分配策略评测6 2 5 4 周转时间与公平性评测6 4 5 5t p c c 综合性能评测6 5 5 6 本章小结6 6 第六章结束语一6 7 6 1 工作总结6 7 6 2 工作展望6 7 致谢6 8 参考文献6 9 第1 i 页 国防科学技术大学研究生院t 程硕+ 学位论文 作者在学期间取得的学术成果7 2 第1 i i 页 国防科学技术大学研究生院工程硕士学位论文 表目录 表3 1 测试层次模型关系表3 4 表4 1l t c 自动化测试统计过程4 6 表4 2b l t 自动化测试统计过程5 2 表5 1 测试环境硬件配置。5 5 表5 2 基于管道和信号量的额外开销比较5 6 表5 3l t c 线程切换代价测试说明5 7 表5 4b l t 测试说明。6 2 表5 5s y s b e n c h 线程调度性能测试说明6 4 表5 6s y s b e n c h 测试结果6 4 表5 7t p c c 测试说明6 5 表5 8t p c c 测试结果6 5 第1 v 页 国防科学技术大学研究生院t 程硕十学位论文 图目录 图1 1 线程调度模型1 图2 1 英特尔n e h f l e m 微体系架构6 图2 2l i n u x2 6 调度器进程队列结构1 0 图2 3r s d l 算法m i n o rr o t a t i o n 过程13 图2 4r s d l 算法循环过程1 3 图2 5s c h e d u l e rt i c k 函数功能及调用过程1 5 图2 6s c h e d u l e 函数的功能和调用过程1 7 图2 7 基于微状态信息的线程调度模型2 0 图2 8l m b e n c h 测试框架流程。2 3 图2 9 数据库服务线程2 6 图4 1 时间戳函数结构。3 9 图4 2 线程切换模型4 3 图4 3l t c 测试信息数据结构4 4 图4 4l t c 计算额外开销主要算法4 4 图4 5l t c 工作线程循环算法_ 。4 5 图4 6l t c 主线程准备过程4 5 图4 7l t c 主线程循环算法4 5 图4 8l t c 测试结果曲线图示例。4 7 图4 9 双线程交替运行逻辑图4 8 图4 1 0p l a y e r 线程数据结构。4 9 图4 1 1 两个c o r e 的共享缓存负载模式5 0 图4 1 2p l a y e r 线程绑定范围数据结构5 l 图5 1k e m e l 2 6 1 8d e f a u l t 测试结果5 8 图5 2k e m e l 2 6 1 8s i n g l e 测试结果5 8 图5 3k e m e l 2 6 18u n i q u e 测试结果5 9 图5 4k e r n e l 2 6 2 9d e f a u l t 测试结果6 0 图5 5k e r n e l 2 6 2 9s i n g l e 测试结果6 0 图5 6k e r n e l 2 6 2 9u n i q u e 测试结果6 1 图5 7k e r n e l 2 6 18b l t 测试结果6 3 图5 8k e r n e l 2 6 2 9b l t 测试结果6 3 第v 页 国防科学技术大学研究生院工程硕十学位论文 第页 国防科学技术大学研究生院下程硕十学位论文 摘要 随着多核技术的发展，多片多核体系结构正在成为中高端服务器市场的主流。 基于软件和硬件的多线程技术为并行计算，特别是事务处理应用提供了有效手段。 随着处理器片数和核数的不断增加，多片多核体系结构给操作系统调度程序的设 计以及性能优化带来了新的挑战，操作系统线程调度技术的可扩展性和性能优化 成为新的研究热点，同时也对线程调度技术的分析和评测方法提出了新的要求。 论文首先分析了现有主要调度器的实现原理及关键技术，阐述了线程调度技 术的发展趋势，总结和归纳了调度性能优化的主要途径；在此基础上，重点研究 了操作系统线程调度技术的评测方法，分析了四个重要的性能评价指标，针对每 个性能指标提出了具体的评测方法，设计了三个层次的测试框架模型，包括微观 层、组件层和应用层。 设计和实现了新的线程切换代价测试程序( l a t e n c yo f t h r e a dc o n t e x t - s w i t c h ， l t c ) ，用信号量作为令牌进行通信和同步，减少额外开销，提高测试结果的精度 和稳定性：通过集成多种调度策略、共享方式和负载量，可以从不同的场景分析 线程切换时的间接延迟。设计实现了评测调度器对体系结构可扩展性的分析工具 ( b i n d1 0 a dt e s t ，b l t ) ，通过集成了多种负载模式和绑定策略，可以对不同的调 度器进行各种负载及绑定模式下调度分配特性的对比分析。 利用l t c 、b l t 、s y s b e n c h 、d b t 2 构造了一组测试程序集模拟不同层次的线 程竞争模型，用于测试操作系统调度器的性能，通过对0 0 ) 和c f s 调度器进行对 比测试，验证了理论上的性能分析，表明在底层操作上o ( 1 ) 比c f s 调度器微观操 作性能好，但c f s 由于调度粒度不同对于高负载下的综合性能表现更好。同时提 出一些提高线程调度性能的算法设计和调度策略优化设计原则，在算法设计上， 不仅要考虑单次调度切换的代价，还要重视面向事务处理应用的高负载下的调度 效率。在调度分配策略上的优化原则：一是使同一应用程序的线程或是相关度比 较高的线程尽量在一个核上执行；二是共享数据量少或者没有数据共享的任务尽 量在不同的核上运行。这样，可以显著地降低c a c h e 的失效率，并尽可能的提高 硬件资源利用率，进而在很大程度上提升系统的整体性能。 论文中提出的测试方法和所实现的测试工具为多片多核系统下的线程调度性 能测试与分析提供了有效手段，可以为操作系统调度技术研究提供参考和评价依 据。本课题研究得到国家8 6 3 计划“高端容错计算机总体技术研究 项目的资助。 主题词：多片多核，线程调度，评价方法，性能测试 第i 页 国防科学技术大学研究生院工程硕士学位论文 a b s t r a c t w i t l lt h ed e v e l o p m e n to fm u l t i - c o r et e c h n o l o g y ，m u l t i c h i pm u l t i c o r ea r c h i t e c t u r e h a sg a i n e dm o r ea n dm o r ep o p u l a r i t yo nm o d e mc o m m e r c i a lm i d d l eo rh i g h - e n ds e r v e r s m u l t i t h r e a d t e c h n i q u e sb a s e d o ns o f t w a r ea n dh a r d w a r e p r o v i d e sa l l e f f e c t i v e m e c h a n i s mf o rp a r a l l e lc o m p u t i n g ，e s p e c i a l l yf o rt r a n s a c t i o np r o c e s s i n ga p p l i c a t i o n s w 油t h ei n c r e a s i n gn u m b e ro fp r o c e s s o rc h i p sa n dc o r e s t h en e wa r c h i t e c t u r eb r i n g s a b o u tan e wc h a l l e n g eo nt h e d e s i g no ft h eo p e r a t i n gs y s t e ms c h e d u l e ra n dt h e o p t i m i z a t i o no ft h ep e r f o r m a n c e t h es c a l a b i l i t ya n dp e r f o r m a n c eo p t i m i z a t i o no f t h r e a d s c h e d u l i n gt e c h n o l o g yh a sb e c o m ear e s e a r c hh o t s p o t 。刀掐a n a l y s i sa n d e v a l u a t i o nm e t h o do nt h r e a ds c h e d u l i n gf a c e sn e w r e q u i r e m e n t s i nt h i sp a p e r , t h ep r i n c i p l eo fm a j o rs c h e d u l e r sa n di t sk e yt e c h n o l o g yi sa n a l y z e d f i r s t l y 1 1 1 ef o l l o w i n gi sd e v e l o p m e n tt r e n do ft h r e a ds c h e d u l i n g 。a tt h es a m et i m e t h e a p p r o a c ht op e r f o r m a n c eo p t i m i z a t i o no ft h r e a ds c h e d u l i n gi ss u m m a r i z e d b a s e do n t h e s ed i s c u s s i o n s ，t h et h r e a ds c h e d u l i n ge v a l u a t i o nm e t h o di sd e e p l yd i s c u s s e d f o u r p e r f o r m a n c ee v a l u a t i o na s p e c t sa r ep r e s e n t e d ad e t a i l e de v a l u a t i o nm e t h o di sp r o p o s e d a c c o r d i n gt oe a c ha s p e c t at h r e eh i e r a r c h i c a lt e s t i n gm o d e l ，a tm i c r o s t r u c t u r e ，m o d u l a r c o n s t r u c t i o na n da p p l i c a t i o np r o g r a ml e v e li sd e s i g n e d an e wt e s tp r o g r a mc a l l e dl t ca i mt o t e s tt h et h r e a dc o n t e x ts w i t c h i n gc o s ti s d e s i g n e da n di m p l e m e n t e d i no r d e rt od e c r e a s ea d d i t i o n a lo v e r h c a da n dt oi m p r o v et h e a c c u r a c ya n ds t a b i l i t y o ft h et e s t r e s u l t ，l t cu s e ss e m a p h o r et or e a l i z et h e c o m m u n i c a t i o na n dt h em u l t i t h r e a ds y n c h r o n i z a t i o n n 圮c o n t e x ts w i t c hl a t e n c yc a nb e a n a l y z e di nv a r i e ds i t u a t i o n sb yt u n i n gt h es c h e d u l i n gs t r a t e g i e s ，s h a r i n gm o d e l sa n d w o r k l o a d s a n o t h e r a n a l y s i s t o o l sn a m e db l ti s i m p l e m e n t e d t oe v a l u a t et h e s c a l a b i l i t i e so fs c h e d u l e r s m a n yw o r k l o a da n db i n d i n gs t r a t i f i e sa r ea l s oi n t e g r a t e di n t o t h eb l t t h ec o m p a r a t i v er e s u l tc a l lb ea c h i e v e db y m o d i f y i n gt h ei n t e g r a t e ds t r a t e g i e s o f b l t b a s eo nl t c ，b l t ，s y s b e n c ha n dd b t 2 ，as e to ft e s tp r o g r a m ss i m u l a t i n gt h e t h r e a dc o m p e t i t i v em o d e li sm a d eu po ft ot e s ts c h e d u l i n gp e r f o r m a n c e t h et h e o r e t i c a l p e r f o r m a n c ea n a l y s i si sf u r t h e rv e r i f i e db yt h et e s tr e s u l to n0 ( 1 ) a n dc f ss c h e d u l e r s o m eo p t i m i z a t i o nd e s i g nc r i t e r i ao ns c h e d u l i n ga l g o r i t h ma n ds t r a t e g ya r ep u tf o r w a r d f o rs h e c h u l ea l g o r i t h m s ，i ti sn o to n l yt h ec o s to fas i n g l ec o n t e x ts w i t c h , b u ta l s ot h e a p p l i c a t i o nf o rt r a n s a c t i o ns c h e d u l i n ge f f i c i e n c yu n d e rh e a v yl o a ds h o u l db ec o n s i d e r e d 砀es c h e d u l i n go p t i m i z a t i o ns t r a t e g ya m o n gm a n yc o r e si sa l s oo fi m p o r t a n c e 刃 e s a m ea p p l i c a t i o nt h r e a d so rv e r yr e l e v a n tt h r e a d s 咖o nt h es a m ec o r ea sf a ra s p o s s i b l e t a s k ss h a r i n gn od a t ao rl e s sd a t a , s h o u l dr u no nd i f f e r e n tc o r e s u n d e rs u c h d i s t r i b u t i n gd i s c i p l i n e ，t h em i s sr a t eo fc a c h ei sr e d u c e d , t h eh a r d w a r er e s o u r c e u t i l i z a t i o nc a nb ei n e r e a s e d , a n dt h eo v e r a l ls y s t e mp e r f o r m a n c ew i l lb e l a r g e l y 第i i 页 国防科学技术大学研究生院t 程硕十学位论文 i m p r o v e d t h et e s tm e t h o da n dt o o l sp r o v i d ear e f e r e n c ea n da l le f f e c t i v em e a s u r ef o r s c h e d u l i n gt e c h n o l o g yr e s e a r c ha n da n a l y s i s o nm u l t i - c h i pm u l t i - c o r e s y s t e m t h e r e s e a r c hi s s u p p o r t e db y “r e s e a r c h o n h i g h - e n df a u l t - t o l e r a n t o fc o m p m e r a r c h i t e c t u r e ”p r o j e c tu n d e rn a t i o n a lh i g ht e c h n o l o g yr e s e a r c ha n dd e v e l o p m e n t p r o g r a m ( 8 6 3p r o g r a m ) k e yw o r d s ：m u l t i c h i pm u l t i - c o r e ，t h r e a ds c h e d u l i n g ，e v a l u a t i o nm e t h o d o l o g y ， p e r f o r m a n c e t e s t 第i i i 页 国防科学技术大学研究生院工程硕士学位论文 国防科学技术大学研究生院工程硕士学位论文 第一章绪论 1 1 线程调度概述 线程调度是现代操作系统的核心功能，它完成逻辑计算实体( 进程线程) 到 物理计算单元( c p u 核心物理线程) 的分配与调度，采用时分和空分等多种形式， 实现逻辑计算实体对物理计算资源的高效共享使用。多核多芯片计算机系统采用 多块片上多核芯片、通常以共享c a c h e 和主存方式组建而成，其性能的发挥与操 作系统线程调度的关系更为密切，多片多核下的线程调度模型如图1 1 所示。 用户线程 圆圆 ( 调度器 ) 弋 o 叫t e o l l c o r t ll c o 髓ol i c o r e tl l l 如ib ik i虹l 睇l l 2 c 妇 ：l 2 c a c h e 多核c p u多梭c p u 塑翌二二二二二二 图1 1 线程调度模型 随着多核处理器的发展，对软件开发有非常大的影响，而且核心的瓶颈在软 件上。软件开发在多核环境下的核心是多线程开发。这个多线程不仅代表了软件 实现上多线程，要求在硬件上也采用多线程技术。可以说多核提供了可以大幅提 升性能的新机制，多核软件面临如何发挥该硬件资源优势的新挑战，只有与多硬 件相适应的软件，才能真正地发挥多核的性能。多核对软件的要求包括对多核操 作系统的要求和对应用软件的要求。任务的分配是多核时代提出的新概念。在单 核时代，没有核的任务分配的问题，一共只有一个核的资源可被使用。而在多核 体系下，有多个核可以被使用。如果系统中有几个进程或线程需要分配，是将他 们均匀地分配到各个处理器核，还是一起分配到一个处理器核，或是按照一定的 算法进行分配。并且这个分配还受底层系统结构的影响，系统是s m p 构架还是 ：m p 构架，在c m p 构架中会共享一级缓存的核的数量，这些是影响分配算法的 马子。线程分配结束后，需要考虑线程的调度。对于不同的核，每个处理器核可 第1 页 国防科学技术大学研究生院工程硕士学位论文 以有自己独立的调度算法柬执行不刚的任务( 实时任务或者交互性任务) ，也可以使 用一致的调度算法。此外，还可以考虑一个线程上一个时间运行在一个核上，下 一个时间片是选择继续运行在这个核上，还是进行线程迁移；怎样直接调度实时 任务和普通任务；系统的核资源是否要进行负载均衡等等。多片多核线程任务调 度是目前研究的热点之一。 在单核处理器中，常见的调度策略有先到先服务( f c f s ) ，最短作业调度( s j f ) ， 优先级调度( p f i o d 够s c h e d u l i n g a l g o r i t h m ) ，轮转法调度( r o u n d r o b i n ，r r ) ，多 级队列调度( m u l t i l e v e lq u e u e s c h e d u l ea l g o r i t h m ) 等。例如在l i n u x 操作系统中对 实时任务主要采取f c f s 和r r 两种调度，普通任务调度主要采取优先级调度。 对于多片多核处理器系统的调度，目前还没有明确的标准与规范。由于系统 有多个处理器核可用，必须进行负载分配，有可能为每个处理器提供单独的队列。 在这种情况下，一个具有空队列的处理器就会空闲，而另一个处理器会很忙。所 以如何处理好负载均衡问题是这种调度策略的关键问题所在。调度算法的研究与 设计需要解决这些问题，以提高线程调度的性能。 不仅如此，如何测试和评价调度器的性能也面临新的问题，间接延迟的测量 比单处理器时更为复杂。考虑到目前主流服务器的发展和应用情况，线程调度和 评测技术主要针对事务处理应用。 1 2 课题背景与研究意义 随着多片多核体系结构的发展，软件在线程级和进程级上的粗粒度并行性能 主要取决于高效的操作系统调度策略和同步通信机制，多片多核的操作系统调度 已成为现代操作系统的五大热点问题之一【l 】。多片多核带来的线程调度器的可伸缩 性问题、对二级c a c h e 的竞争问题、c a c h e 的访问与延迟问题( n u c a 结构) 、线 程调度的性能测试与评价等新问题引起了国际上的广泛关注。在线程调度的性能 测试与评价方面，一般都用单一的压力负载测试程序，还没有形成系统的评测验 证方法。而且一些相关的测试程序没有很好的针对多片多核线程调度的特点进行 多负载模型设计。在与c a c h e 有关的调度器线程切换代价分析方面，线程场景的 恢复除了线程相关的系统寄存器以外，由于还受到体系结构流水线、c a c h e 数据失 效等因素的影响，这方面的代价也是由于线程切换导致的，也不能被忽视。不然， 仅仅考虑寄存器的保存和恢复时间，就会与实际的复杂体系结构下系统在线程切 换方面所花的时间严重不一致，这也正是线程切换代价测量程序的难点。 为此，本文对线程调度方法与性能评测方法进行研究，通过研究调度器的关 键技术和发展趋势，根据已有的基准测试程序结合多片多核调度特点设计和实现 能体现应用领域特性的线程调度测试程序集，使所形成的测试方法和测试基准程 第2 页 国防科学技术大学研究生院工程硕士学位论文 序可以用于不同调度器的性能测试和对比分析，对操作系统的线程调度程序设计 与优化具有指导性意义。 本课题基于国家“8 6 3 ”计划“高端容错计算机总体技术研究 项目中的操作 系统多核多处理器线程调度技术研究。 1 3 研究内容和主要工作 本文研究多片多核体系结构下操作系统线程调度技术及其评测方法，首先分 析现有主要调度器的原理及关键技术，阐述了线程调度技术的发展趋势，提出调 度性能优化的途径，同时研究线程调度技术的评测方法，从多个层次分析了相关 的基准测试程序，重点研究其中几种线程基准测试工具的测试原理和程序流程， 在此基础上依据多线程测试特点设计与实现新的线程切换代价测试程序( l a t e n c y o f t h r e a dc o n t e x t - s w i t c h ，l t c ) 和评测调度器对体系结构可扩展性的分析工具( b i n d l o a dt e s t ，b l t ) ，构造了一组测试程序集模拟不同层次的线程竞争模型，用于测 试操作系统调度器的性能，根据测试结果验证多线程调度性能的优化设计，为多 片多核下操作系统调度技术研究及线程调度程序的性能评测提供参考和依据。 主要工作体现在以下几个方面： ( 1 ) 研究了多片多核下操作系统线程调度的关键技术及发展趋势，分析了性 能优化的途径。 ( 2 ) 研究了线程调度性能的评价指标，主要包括线程切换代价、体系结构扩 展性、周转时间公平性和综合效率。 ( 3 ) 结合多片多核体系特点设计和实现了线程切换代价测试工具l t c ，为多 核系统下的线程切换代价测试与分析提供了有效手段。 ( 4 ) 通过集成多类型可定制负载和线程调度方式控制功能，设计和实现了 b l t 测试程序，用于测试l i n u x 操作系统中与体系结构特点相关的线程调度性能。 ( 5 ) 构建了多层次的线程评测方法，用微观测试程序测试线程库原语操作性 能，用组件级测试程序测试内核调度组件的性能，用应用级测试程序测试线程调 度程序对事务处理性能的影响，从多层结果分析和验证线程调度程序的性能影响， 使所形成的测试方法和测试程序集可以用于不同调度器的性能测试和对比分析， 对操作系统的线程调度程序设计与优化具有指导性意义。 ( 6 ) 运用研究和设计的评测工具对0 0 ) 和c f s 调度器进行了对比测试，得到 了与理论分析相一致的测试结果。 1 4 论文组织结构 第3 页 国防科学技术大学研究生院工程硕士学位论文 本文内容组织结构如下： 第一章绪论介绍课题背景、意义及研究内容。 第二章首先介绍体系结构的发展以及多片多核的特点，然后分析和比较l i n u x 调度器发展过程中的几个主要调度算法的原理和性能特点，阐述调度器的发展趋 势和性能优化方面的研究重点，最后介绍相关的线程调度测试方法和测试工具。 第三章研究线程调度性能评价指标，建立测试方法，描述测试模型。 第四章对t l c 和b l t 分别进行设计和实现。 第五章运用研究和设计的评测工具对o ( 1 ) 和c f s 调度器进行了对比测试。 第六章结束语，总结该评测方法的效果和实际应用意义并展望了进一步的工 作。 最后是致谢。 第4 页 国防科学技术大学研究生院t 程硕士学位论文 第二章线程调度相关研究与分析 本章主要讨论体系结构的发展，特别是体系结构的变化对操作系统调度技术 的影响，深入分析和比较了l i n u x 操作系统中调度技术的变化，包括几个主要调度 算法的原理和性能特点，阐述了调度器的性能优化方法和发展趋势，最后讨论相 关的线程调度测试方法和测试工具。 2 1 多片多核体系结构 过去4 0 年c p u 芯片频率一直遵循摩尔定律，高频率c p u 要解决更多功耗和 散热问题，却未给现代应用带来很大的性能提升。“存储墙 是c p u 利用率不 足的主要原因，处理器指令执行时延与访存时延之间的差距还在以每年5 0 的速 度递增【2 】。访存操作浪费大部分c p u 周期导致c p u 基本处于空闲状态，因此， 提高c p u 频率就失去了意义。预取和乱序等技术可以隐藏部分访存延迟，但不 能有效改善访存延迟。乱序执行和分支预测等指令级并行( i l p ) 技术虽然可以在 一定程度上隐藏一级缓存( c a c h e ) 失效造成的短延迟，但是不能缓解二级缓存失 效造成的长延迟p j 。在这种趋势下，主要的处理器厂商更加关注发展芯片的线程级 并行( t l p ) 技术【4 j 。 研究人员先后提出多种利用t l p 技术来提高处理器资源利用率的处理器体系 结构，包括多线程处理器( m u l t i t h r e a d e dp r o c e s s o r ) 、单片多处理器( c h i p m u l t i p r o c e s s o r ，c m p ) l 5 j 和同时多线程( s i m u l t a n e o u sm u l t i t h r e a d i n g ，s m t ) 结构【6 l 。 c m p 就是将多个计算内核集成在一个处理器芯片中，从而提高计算能力。按计算 内核的对等与否，c m p 可分为同构多核和异构多核，每个c p u 核心具有独立的处 理单元和c a c h e ，每个c p u 内核拥有共享的二级或三级c a c h e ，用于保存比较常 用的数据，各个c p u 核心通过交叉开关或片上网络等方式连接在一起，并通过连 接核心的总线进行通信。 2 0 0 5 年s u n 公司提出了片上多线程技术( c h i pm u l t i p l et h r e a d i n g ，c m t ) 7 1 邛j ， c m t 实际上就是用c m p 技术集成多个s m t 的处理内核，在一个c m t 处理 器中，多个内核共享二级缓存( 有的还共享三级缓存，将二级缓存分区共享，) 以及前端总线等资源；在各处理内核中，多个硬件线程则共享核内的功能部件、 流水线和一级缓存等资源。c m t 技术能够将更多的晶体管压缩到一个芯片中，同 时能够简化每一个c p u 的设计，把更多的c p u 核压在一个芯片当中以提高整个芯 片处理交易事务的能力。鉴于此，大多数c p u 厂商选择芯片级多线程( c h i p m u l t i t h r e a d e d ，c m t ) 技术。图2 1 为运用c m t 技术的i n t e ln e h a l e m 微体系架构， 第5 页 国防科学技术大学研究生院工程硕士学位论文 支持每个处理器内核的i 司步多线程。 图2 1 英特尔n e h a l c m 微体系架构 当前主流服务器厂商还提供了利用s m p ( 对称多处理) 技术集成多个c m t 的系统，组成了多片多核的体系结构，基于多路四核乃至八核的商用服务器现在 已随处可见。因其具有较高的吞吐率，正在被越来越广泛地应用于现代商业应用 领域。这些体系结构的发展给调度器的设计与改进提出了新的挑战。 2 2 调度器的发展及关键技术分析 为了分析和评测调度算法的性能，本节首先介绍调度器发展历史上的主要调 度算法【9 】，分析多片多核下操作系统线程调度的关键技术及发展趋势。 进程线程调度是操作系统的核心功能。调度器只是调度过程中的一部分，进 程线程调度是一个非常复杂的过程，需要多个子系统间的协同工作才能完成。调 度器的核心工作是在所有可运行线程( 就绪线程) 队列中选择最合适的一个加以 运行。根据不同的应用需求，应当提供不同类别的调度算法。下面主要分析l i n u x 内核中的调度器技术。在调度器中将进程分为交互式进程、批处理进程和实时进 程三类： 交互式进程需要进行大量的人机交互，因此进程不断地处于睡眠状态，等待 用户输入。典型的应用比如编辑器“。此类进程对系统响应时间要求比较高，否 则用户会感觉系统反应迟缓。 批处理进程不需要人机交互，在后台运行，需要占用大量的系统资源。但是 第6 页 国防科学技术大学研究生院t 程硕十学位论文 能够忍受响应延迟。比如编译器。 实时进程对调度延迟的要求最高，这些进程往往执行非常重要的操