（计算机系统结构专业论文）多核处理器体系结构下linux调度机制的研究.pdf

原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成 果。除本文已经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得凼墓直太堂及其他教育机构的学位或证书而使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作7 明确的说明并表示谢意。 学位论文作者签名：重盘 日期：塑! f ：f 指导教师签名：盏 日期： 2 窆f 厶6 ：f 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将 学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允 许编入有关数据库进行检索，也可以采用影印、缩印或其他复制手段保存、汇编学位论文。 为保护学院和导师的知识产权，作者在学期间取得的研究成果属于内蒙古大学。作者今后使 用涉及在学期间主要研究内容或研究成果，须征得内蒙古大学就读期间导师的同意；若用于 发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。 学位论文作者签名：重鱼垒 日期： 毡碰。& ：f 指导教师签名：五丛叁： 日期： 垒! 丝：6 ：z 内蒙古大学硕士学位论文 多核处理器体系结构下l in u x 调度机制的研究 摘要 在最近十几年中，各种各样嵌入式设备快速发展，同时l i n u x 操作系统也得 到了更加广泛的应用。嵌入式设备的应用包括了手机、便携式电脑、g p s 、游戏 机等。虽然不同的嵌入式设备对于运行在其中的l i n u x 操作系统有着不同的要 求，但是l i n u x 操作系统的任务调度器还是在其中起着至关重要的作用。随着 l i n u x 版本的更新，l i n u x 任务调度器也在不断的发展，功能从简单到复杂。 计算机是一个系统，包含了软件和硬件。仅仅对其中的硬件进行修改并不 能使整个系统的性能得到本质的提高，必须有软件的辅助。系统的任务调度器 给与处理器足够的支持，才能使多核处理器在操作系统中发挥出其真正优势。 本文主要研究最新的l i n u x 系统调度器及其对多核处理器的支持。首先，全 面的分析了l i n u x2 6 3 5 版本内核中有关于调度器的源码，理解内核调度器各个 模块的工作原理。其次，重点分析了调度器中负载平衡模块的工作流程及其对 于多核处理器的支持。最后，使用l i n s c h e d 模拟器【3 2 】对c f s 调度器在多核参数 、配置下做了大量的模拟实验，并结合c f s 调度器原理进行了深入的分析，进一 步理解在多核体系结构下内核任务调度器的特性。本文研究了体现c f s 调度器 1 性能的两个方面：吞吐量和进程响应时间，总结它们与性能之间的关系式。进 行实验，分析实验结果获取处理器核数和系统调度粒度这两个因素对调度器性 能的影响。并针对不同实际应用结合前面的实验结果，提出优化面向实际应用 时c f s 调度器性能的方法，通过实验加以验证。实验证明，本文所提出的方法 多核处理器体系结构下l i n u x 调度机制的研究 是可行的。 关键词：l i n u x 任务调度器；多核体系结构；c f s ；l i n s c h e d ；运行时间；调度 器性能 a l t h o u g hd i f f e r e n te m b e d e d d e v i c er e q u i r e sd i f f e r e n tl i n u xs y s t e mt or u n ，l i n u xt a s k s c h e d u l e rs t i l lp l a y sak e yr o l ei nt h el i n u xs y s t e m a st h ev e r s i o no fl i n u xi m p r o v e s ， s od o e st h et a s ks c h e d u l e ra n di t sf o u n c t i o nc h a n g e df r o ms i m p l et oc o m p l e x c o m p m e r i sak i n do fs y s t e m ，i tc o n t a i n sb o t hh a r d w a r ea n ds o f t w a r e t h ee n t i r e p e r f o r m a n c eo fs y s t e mc a nn o tb ei m p r o v e do n l yb y t h ec h a n g eo fh a r d w a r e ，i ta l s o d e p e n d so nt h es u p p o r to ft h es o f t w a r e t ob r i n gt h es t r o n gp o i n to ft h em u l t i c o r e p r o c e s s o r i n t of u l lp l a y , t h ec o o p e r a t i o no ft h et a s ks c h e d u l e ri sr e q u i r e d t h i sp a p e rs t u d i e st h el a t e s tl i n u xs y s t e ms c h e d u l e ra n di t ss u p p o r tf o rm u l t i c o r e p r o c e s s o r s a tf i r s t ，t h i sp a p e rd i dac o m p r e h e n s i v ea n a l y s i so fs o u r c ec o d eo ft h e l a t e s tk e r n e lv e r s i o n2 6 3 5s c h e d u l e rt ou n d e r s t a n dh o wt h em o d u l e so f t h es c h u d e l e r w o r k t h e n ，t h ep a p e ra n a l y z e dt h ep r o c e s so ft h el o a db a l a n c em o d u l ei nt h e s c h e d u l e ra n di t ss u p p o r tt om u l t i c o r ep r o c e s s o r a tl a s t ，l i n s c h e dw h i c hh a db e e n c o n f i g u r e dw i t hv a r y i n gn u m b e ro fc o r e sh a db e e nu s e dt od oal a r g en u m b e ro f e x p e r i m e n tt os i m u l a t et h eb e h a v i o ro ft h ec f ss c h e d u l e r , c o m b i n e dt h ee x p e r i m e n t 多核处理器体系结构下l i n u x 调度机制的研究 r e s u l t sw i t ht h ep r i n c i p l eo ft h es c h e d u l e rt od oai n d e p t ha n a l y s i s ，i nt h ep u r p o s eo f h a v i n gaf u r t h e ru n d e r s t a n d i n gt h ef e a t u r e so ft h es c h e d u l e ru n d e rt h em u l t i c o r e a r c h i t e c t u r e t h ep a p e rs t u d i e dt w oa s p e c t so ft h e p e r f o r m a n c eo fs c h e d u l e r , t h r o u g h p u ta n dr e p o n s et i m et os u m m a r i z e dt h ee q u a t i o no fp e r f o r m a n c ea n dt h e s e t w oa s p e c t s t h e n ，as e to fe x p e r i m e n t sw a sd o n et of i n dh o wt h et w of a c t o r s ，。 n u m b e r so ft h ec o r e sa n ds c h e d u l eg r a n n u l a r i t ye f f e c tt h ep e r f o r m a n c eo ft h e 。s c h e d u l e r i nt h ee n d ，t h ep a p e rp r o p o s e dt h em e t h o do f o p t i m i z e do f c f ss c h e d u l e r b a s e do nt h ef o r m e re x p e r i m e n tr e s u l ta n dp r a c t i c a l a p p l i c a t i o n ，t h e n as e to f e x p e r i m e n t sw a sd o n et op r o v et h ec o r r e c t n e s so ft h ea d v i c e e x p e r i m e n t a lr e s u l t s s h o wt h a tt h em e t h o d p r o p o s e di nt h i sp a p e r i sf e a s i b l e k e y w o r d s ：l i n u xt a s ks c h e d u l e r ；m u l t i c o r e a r c h i t e c t u r e ；c f s ；l i n s c h e d ； r u n n i n gt i m e ；p e r f o r m a n c eo f t h es c h e d u l e r i v 内蒙古大学硕士学位论文 目录 摘| 喜一i a b s t r a c t 。i i i 第一章绪论1 1 1 研究背景1 1 2 研究现状1 1 2 1 多核处理器工业现状1 1 2 2 多核处理器的学术界研究现状l i 3 论文研究内容：2 1 4 论文结构一：j 一2 第二章多核处理器体系结构3 2 1 多核处理器实现相关技术：。j 3 2 2 1s m t 结构3 2 2 2c m p 结构3 2 2 3c m t 结构：一4 2 3 多核线程调度的研究现状4 2 3 1c m p 结构进程调度：4 2 3 2s m t 结构进程调度算法4 2 3 3c m t 结构进程调度5 2 4 现有操作系统对于多核处理器的支持5 2 5 本章小结5 第三章c f s 完全公平调度器分析6 3 1c f s 调度器简介：j 6 3 2c f s 调度器的代码分析j 6 3 2 1 调度器中的重要数据结构j 6 3 2 2 完全公平调度器的工作流程7 3 2 3c f s 组调度。1 2 3 2 4c f s 中s n i p 以及多核的负载平衡1 3 多核处理器体系结构下l i n u x 调度机制的研究 3 3 小结1 8 第四章c f s 完全公平调度器的动态模拟及分析1 9 4 1 实验平台19 4 2 实现设计、实验结果及分析19 4 2 1c f s 调度器调度行为模拟1 9 4 2 2c f s 调度器组调度行为模拟。2 5 4 2 3 多核负载平衡操作模拟实验2 9 4 3 处理器核数及调度粒度变化对c f s 调度器性能的影响3 2 4 3 1 核数变化对c f s 调度器性能的影响3 2 4 3 2 系统调度粒度变化对c f s 调度器性能的影响3 3 4 4c f s 调度器在实际应用中的性能优化3 4 4 5 本章小结3 7 第五章总结及展望_ j 3 8 5 1 总结：3 8 5 2 展望_ 3 8 参考文献3 9 致谢：i 4 2 内蒙古大学硕士学位论文 图表目录 图3 1 周期性调度的代码流程图7 图3 2 取得i d e a ln m t i m e 的代码流程图8 图3 3 主调度函数s c h e d u l e o f f 勺代码流程图：9 图3 4 新生进程调度代码流程图1 0 图3 5c o p y _ _ p r o c e s s 代码流程图。10 图3 6p l a c e _ e n t i t y ( ) i 垂i 数的代码流程图。1 1 图3 7e n q u e u et a s kf a i r 函数的代码流程图，1 1 图3 8t a s k _ g r o u p 层次结构关系图1 3 图3 9 调度域结构图1 4 图3 1 0 调度域层次图。1 5 图3 1 1c p ud o m a i n 示意图1 5 图3 1 2c o r e d o m a i n 示意图。1 5 图3 1 3 建立好的调度域及调度组。1 6 。 图3 1 4 基于时钟中断的负载平衡操作的代码流程图。1 6 图3 1 5l o a db a l a n c e o 代码流程图1 7 图3 1 6m i g r a t i o n _ t h r e a d o i 函数的代码流程图1 8 图4 1 进程集( 1 ) 在不同核数配置下的实验结果2 0 图4 2 进程集( 2 ) 在不同核数配置下的实验结果2 2 图4 3 进程集( 3 ) 在不同核数配置下的实验结果：2 3 图4 4 进程集( 4 ) 在不同核数配置下的实验结果。2 4 图4 5 组调度进程集( 1 ) 在不同核数配置下的实验结果：2 7 图4 6 组调度进程集( 2 ) 在不同核配置下的实验结果2 9 图4 7 处理器核数与吞吐量关系图：。3 2 图4 8 处理器数量与进程平均响应时间关系图3 2 图4 9 调度粒度与吞吐量关系图：3 3 图4 1 0 调度粒度与进程平均响应时间关系图3 3 图4 1 1 处理器核数一效益性能工3 5 图4 1 2 调度粒度性能关系图3 6 多核处理器体系结构下l i n u x 调度机制的研究 表4 1 移动终端优化前后性能比较表3 6 表4 2 网络服务器优化前后性能比较表3 7 内蒙古大学硕士学位论文 1 1 研究背景 第一章绪论 由于l i n u x 的开放性，l i n u x 的调度算法得到了长足的发展与丰富。l i n u x2 6 内核调度 器包括：由c o nk o l i v a s 提出的楼梯调度算法( s d ，s t a i r c a s es c h e d u l e ) 平i 有截止期限的旋转楼 梯调度( r s d l ，t h er o t a t i n gs t a i r c a s ed e a d l i n es c h e d u l e ) ，还有在l i n u x2 6 2 3 内核中发布的 由i n g om o l n a r 设计并实现的完全公平调度算法( c f s ，c o m p l e t e l yf a i rs c h e d u l e ) 。其中c f s 调 度器采用了与以往完全不同的设计理念，试图提高公平性能，对调度器的发展有着深远的影 响。 为了提高并行处理能力，多核处理器体系结构的研究经历了由同时多线程处理器( s m t ， s i m u l t a n e o u sm u l t i t h r e a d e dp r o c e s s o r ) 、单片多处理器( c m p ，c h i pm u l t ip r o c e s s o r ) 至t j 片上多核 多线程处理器( c m t ，c h i pm u l t i t h r e a d i n g ) 1 1 1 。研究人员还在对多核的储存结构和互联结构进 行研究以提高处理器的性能。由于多核处理器有多个处理核心，那么在多核处理器工作时就 存在任务分配、调度、仲裁以及负载平衡等诸多问题。一个调度算法的性能就是充分利用多 核处理器性能优势的关键。 1 2 研究现状 1 2 1 多核处理器工业现状 自从2 0 0 1 年i b m 推出第一个商用多核处理器p o w e r 4 ，到现在已经有如i n t e l 、a m d 、 n v i d i a 、高通、t i 、飞思卡尔、s u n ( o r a c l e ) 等排名世界前列的芯片生产商投入多核处理器的 设计及研发中，每年大量的新产品问世。 1 2 2 多核处理器的学术界研究现状 学术界的研究主要表现在以下几个方面：核心结构的选择，目前多核处理核器的核心结 构主要有两个类型，同构和异构；存储结构的设计，包括对处理器片上的高速缓存和主内存 的研究 5 】；片上通信，多核处理器的片上通信当前有三种方式：总线共享、交叉开关、片上 网络：资源竞争，片上资源竞争包含了各个核心在运行时对于共享资源比如数据总线、高速 多核处理器体系结构下l i n u x 调度机制的研究 缓存的竞争，和多线程在运行时各个线程对于共享资源；低功耗，在多核处理器产生以前， 低功耗主要针对动态消耗和静态消耗技术两方面。由于多核处理器在结构和实现上有了新的 特点，所以研究人员又在新的方面发现了降低功耗的方法：1 ) 异构的结构设计就是利用异构 结构对片上资源的最佳化配置，处理器的执行效率提升，使得处理器不仅具有高性能也降低 了功耗【2 刮。2 ) 动态线程分派与转移技术是利用多核心处理能力，将某个核心上的过多负载转 移到负载小的核心上，从而使处理器在不降低处理性能的情况下，降低处理器功耗【6 - 8 1 。操作 系统的设计：多核之间的任务调度是充分利用多处理器性能的关键。所以要修改现有调度算 法，使操着系统能够高效的支持多核处理器【2 】。应用软件及编程的并行化：多核处理器需要 应用软件能够进行并行处理时，才能发挥其潜能。随着多核的普及各大研究机构和公司也在 并行环境和编程语言的开发上投入了巨大的精力，催生出了如支持共享存储结构的o p e n m p 、 o p e n m p + m p i 的混合编程模型、p t h r e a d 多线程编程模型 9 1 、n v i d i a 公司的e u d a 编程语言。 1 3 论文研究内容 本文对c f s 调度器源码进行了分析，并使用l i n u x 内核调度模拟器l i n s e h e d 对最新的 c f s 调度器的工作进行了功能性模拟。深入理解分析了调度器中各个模块的工作流程及其对 于多核处理器的支持。通过功能性模拟得到多核处理器体系结构下调度器调度特性，结合实 验讨论处理器核数和调度粒度对于调度器性能的影响。定义了用吞吐量和响应时间与调度器 性能的关系式，利用这个关系式讨论针对不同实际任务优化调度器的方法，最后结合实验验 证了方法的可行性。 1 4 论文结构 本文按如下方式组织： 第一章介绍了本文的研究背景及研究内容。 第二章介绍了多核处理器的微体系结构。 第三章介绍了l i n u x 操作系统的调度机制，主要对于最新的c f s 调度器及与其相关的调 度策略进行分析。包括了其思想、算法和数据结构的分析。 第四章介绍了研究所使用的平台及方法。实验设计、实验结果及对其的分析。 第五章全文的总结及展望。 内蒙古大学硕士学位论文 第二章多核处理器体系结构 2 1 多核处理器实现相关技术 在处理器的初期研究过程中，处理器性能的提高主要利用超标量技术( s u p e r s c a l a r ) ，其实现 是每个时钟周期发射爹条指令到功能部件上执行，其目的是利用程序的指令级并行 ( i n s t r u c t i o n l e v e lp a r a l l e l i s m ，几p ) 来提高处理器的处理能力。可是，超标量处理器在单个程 序下，由于i l p 不高所以资源利用率不高，一味增加指令发射宽度只能使情况变差。并行性 不能只限于i l p ，从而线程级并行性( t h r e a d l e v e lp a r a l l e l i s m ，t l p ) 被引入进来。实现包括： 多线程处理器( m u l t i t h r e a d e dp r o c e s s o r ) 、同时多线程( 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 ) 、单 片多处理器( c h i pm u l t ip r o c e s s o r ，c m p ) 。在2 0 0 5 年时，s u n 公司又提出了将c m p 与s m t 一 结合起来的构想，并研制出了c m t ( c h i pm u l t i t h r e a d i l l g ) 处理器【l 0 。 2 2 1s m t 结构 s m t 结构的实现原理是：在一个时钟周期内发射多个线程的指令到功能部件上执行，以 提高线程对于功能部件的利用率。此设计由加利福尼亚大学的t u u s e n 于1 9 9 5 年在华盛顿大 学攻读博士提出，他提出的s m t 结构仅仅对传统超标量处理器结构做了少量的改动，但得到 了明显的性能提升【1 1 1 。因此，一些主流的商业微处理器也采用了这种设计，如d e c a l p h a 2 1 4 6 4 1 2 1 、i n t e lx e o n 【1 3 】。超标量处理器的s m t 设计是基于乱序执行( o u to fo r d e r e x e c u t i o n ) 1 1 1 1 的，这样就解决了大寄存器读写和指令调度在内的具体实现问题。 i n t e l 的研究人员也基于s m t 技术设计了超线程( h y p e r n 鹏a d i n g ，h d 技术【1 4 1 。从硬件上 看只有一个物理处理器，但是从程序运行角度上看，却有多个逻辑处理核心。 2 2 2c m p 结构 片上多处理器( c 1 1 i pm u l t i p r o c e s s o rc 脚) 结构是由斯坦福大学的研究小组提出的【1 5 】。其设 计思想是通过简化超标量结构设计，将多个相对简单的超标量处理器核集成到一个芯片上， 这样就避免了如多处理器s m p 芯片上类似的线延的缺点，从而提高了线程级并行性，改善了 处理器吞吐量。但c m p 处理器还是存在着明显的缺点，它的资源是采用划分方式的，当没有 多核处理器体系结构下l i n u x 调度机制的研究 足够的线程时，资源就浪费了，而高效的调度算法就可以来解决这个问题【婚1 7 1 。 按计算内核的地位对等与否，c m p 可分为同构多核和异构多核。典型的同构多核处理器 是i n t e l 最新的多核处理器架构1 0 r e 微架构【1 引。 典型的异构多核处理器是由索尼、东芝和i b m 共同研发的多核心微处理器e l l 处理 器【1 9 1 。 2 2 3c m t 结构 为了解决c m p 结构中存在的t l p 利用率较低的情况，s u n 公司的研究人员将c m p 与 s m t 两种技术结合了起来，发展出了c m t 技术。c m t 技术继承了两者的优点，既有s m t 的高资源利用率的特点，又有c m p 结构【1 2 】实现的简单性。 s u n 公司宣称在n i a g a r a 处理器【2 1 】中使用这种新的多核多线程技术。 2 3 多核线程调度的研究现状 2 3 1c m p 结构进程调度 现在时间上并没有成熟的c m p 处理结构调度方法，操作系统对于处理器的支持也仅限于 对于系统中运行进程或线程的分配和调度。当进程产生时操作系统会将进程合理的分配到物 理的核上，这种分配基于不同核中进程运行的历史记录和核对资源的使用状况等信息。比较 具有代表性的c m p 调度算法有：优化进程的分配，负载平衡的优化，基于核上温度的调度和 基于优化功耗的调度。 2 3 2s m t 结构进程调度算法 s m t 在运行时需要考虑的问题是s m t 结构上怎样选择线程组并调度到处理器同时执行 2 3 1 。s n a v e l y a 【2 卅首先提出了“共生( s y m b i o t i c ) “概念来解决s m t 结构上调度的问题。“共生 用来描述多个线程在s m t 结构上运行的有效性。s n a v e l ya 2 5 】与t u l l s s e n 随后针对s m t 结构 提出了一种调度算法：s o s ( s a m p l e ，o p t i m i z e ，s y m b i o s i s ) 2 6 1 。由于s o s 没有考虑优先级， s a n v e l y ，t u l l s e n 和v o l k e r 3 1 等又提出了新的适于s m t 的调度算法，保证了进程的优先级。 p a r e k h ，e g g e r s 和l e v y 2 7 等人提出了线程敏感的s m t 调度算法。 内蒙古大学硕士学位论文 2 3 3c m t 结构进程调度 c m t 结构的调度主要是为了达到减少对片上共享硬件资源竞争的目的【2 8 】。主要使用协同 调度，即分配合适的线程到同一个芯片上。协同调度主要分为两类：第一类是基于时间采样 的调度，s m t 的共生调度就是其中之一，c m t 结构继承了s m t 结构的共生策略，并将其应 用于多核系统上。另一种是p r o f i l i n g d i r e c t e d 技术，其思想就是先取得进程的运行信息，然后 根据这些信息决定进程的协同调度。f e d o r o v a 的小组提出了对应用程序分类的调度算法【z 州， 这个算法在一定程度上缓解了进程对片上共享硬件资源竞争。 2 4 现有操作系统对于多核处理器的支持 通用的操作系统都支持多任务的执行，利用单核处理器进行分时处理，给系统中的任务 分给不同长度的时间片，使用时间片轮转算法，从而达到多任务处理。对于多核处理器这种 新的架构，操作系统也不需要做很大的更改。由于许多操作系统本身就对于多路处理器有支 持，基本不用做改变就可以实现对多核处理器的支持。 2 5 本章小结 本章介绍了多核处理器的几种实现技术，包括s m t 、c m p 、c m t 和s m p 等。并且介绍 了多核处理器任务调度研究的现状。最后介绍了现有操作系统对于多核处理器的支持情况。 多核处理器体系结构下l i n u x 调度机制的研究 3 1c f s 调度器简介 第三章c f s 完全公平调度器分析 在l i n u x 2 6 2 3 内核中发布c f s ( c o m p l e t e l y f a i rs c h e d u l e r ) 调度器，它采用了与以往调度 器完全不同的设计理念。c f s 完全公平调度器相对于以前的任务调度器的主要改进在于以下 几个方面： 1 、使用红黑查找树这种数据结构取代了复杂的数学公式，经实验证明这种改变不但没有 导致性能降低，而且在公平性上有了一定的提高。 。 2 、取掉了静态时间片的概念，取而代之的是动态时间片的概念，即v i r t u a lr u n t i m e 。这 样以来，减轻了某些高优先级进程对于处理器的独占情况，保证了调度的公平性。- 3 、增加了组调度这种调度方式，方便用户控制系统资源的分配。也方便管理员根据任务 、 的轻重缓急，对有限的资源进行分配。 4 、调度器的负载平衡模块加强了对多核处理器负载平衡的支持。把负载平衡与处理器功 耗控制联系起来，使多核处理器的功耗控制更加聪明。 3 2c f s 调度器的代码分析 3 2 1 调度器中的重要数据结构 l i n u x 完全公平调度器源代码中有几个比较重要的数据结构，它们对于调度器的工作起了 至关重要的作用，下面我们就逐一分析一下这些数据结构。 1 ) 调度类结构和完全公平调度类结构：调度类结构中声明了调度器的相关操作函数，并 将其分为三类，常用操作、与组调度相关的操作和与s m p 或多核负载平衡相关的操作。完全 公平调度类结构，是与公平调度器工作密切相关的调度类。是调度类的实例化，将其中的函 数替换成完全公平调度器相关的操作函数。 2 ) 运行队列结构和完全公平调度队列：这个结构中包含了进程在运行队列中活动的各种 信息。在系统中每个逻辑c p u 都拥有一个这样的结构。c f sr q 结构就是在进程运行队列中完 全公平调度相关的信息。 内蒙古大学硕士学位论文 3 ) t a s k _ s t r u c t 结构和调度实体结构：这个结构中包含了一个进程的所有信息，所以它又被 称为进程描述符。调度器对于任务的调度就是以对调度实体操作的形式来完成的。 3 2 2 完全公平调度器的工作流程 完全公平调度器的工作主要分为三种情况：周期性调度，即由于t i c k 中断而执行的调度 过程；主调度函数s c h e d u l e o 所执行的调度过程；新建进程的调度。 一、周期性调度( t h ep e r i o d i cs c h e d u l e r ) 图3 1 周期性调度的代码流程图 f i g u r e3 1c o d ef l o wd i a g r a mf o rp e r i o d i c a ls c h e d u l i n g 周期性调度中有两个重要操作，第一个重要操作是u p d a t e，这个函数中的操作对curro 于整个完全公平调度器的工作都起着非常重要的作用。它的任务是计算当前进程的运行时间 并把这个值存于d e l t ae x e c 中。随后把运行时间传给其在完全公平调度类中对应的操作 _ u p d a t e _ c t t r r o 。_ u p d a t e _ c u r r o 会依据运行队列中的进程数来求时间的权重。_ u p d a t e c u r r ( ) i 函 数中调用的c a l e _ d e l t af a i r o 这个计算操作。其原型是c a l c _ d e l t a _ m i n e ( u n s i g n e dl o n gd e l t a _ e x e c ， u n s i g n e dl o n gw e i g h t ，s t r u c tl o a d _ w e i g h t 幸1 w ) 其作用近似于d e l t a 幸= w e i g h t 1 w ，这里的1 w 就是 s e - l o a d 即进程负载值。其作用等价于d e l t a = d e l t a * n i c e0l o a d s e l o a d ，s e l o a d 是表 示n i c e 对应的l o a d 值，n i c e 越低，值越大。高优先级的进程计算出来的d e l t a 值会比低优先级的 多核处理器体系结构下l i n u x 调度机制的研究 进程计算出来的低。因此，根据红黑树的性质，高优先的进程就会位于红黑树的左边，在下次调 度的时候就会被优先调度。 另一个重要操作是c h e c kp r e e m p t，其作用是判断调度实体的抢占条件是否满足。 其原理是：首先，取得内核分配给进程_ 的_ t i c 时k o 间i d e a lr u n t i m e 、进程本次执行的时间d e l t ae x e c 、 进程运行了的总时间e u r r - s u me x e cr u n t i m e 和进程最近一次切上c p u 并运行的时间 c u r r - p r e vs a me x e cr u n t i m e ，并求后两个时间之间的差，把结果赋给d e l t ae x e c 。然后，将 d e l t ae x e c 与i d e a lr u n t i m e 做比较并根据不同的情况进行不同的处理。 取得i d e a lr u n t i m e 的代码流图如图3 2 。 i d e a lr u n t i m e 就是理想情况下内核允许进程运行的时间片的大小，如果进程的运行时间 超过此值，内核就会让调度器重新调度，让其它的满足条件的进程进行抢占操作。i d e a lr u n t i m e 这样获得的：首先系统调用s c h e d 。 调用 函数求出指定进程运s l i c e ( ) s c h e d s l i c e s c h e d ：p e r i o d 行队列中所有的进程进行调度所需的调度周期。其具体操作是：当系统中正在运行的进程数 小于1 1 1 l a t e n c y ，使用系统默认的调度周期。当正在运行的进程数大于d r时使用运行1atency 进程数d r 与最新调度间隔的乘积。最后，遍历系统中所有调度实体，找到指定的调nmning 度实体更新其所在公平队列的负载与调度实体自己的负载，并将新的负载带入计算式d e l t a = d e l t a * s e l o a d w e i g h t c f sr q l o a d 中( 这里的d e l t a 替换为s l i c e ，d e l t a 也就是所求出的 i d e a lt i m e ) 。由式子可得：进程n i c e 值越小，n i