（计算机应用技术专业论文）linux内核调度器分析及模拟.pdf

浙江大学硕士学位论文摘要 摘要 操作系统内核调度算法历来是人们改进系统性能的研究热点。作为主流操作 系统之一的l i n u x ，它的调度算法几经改进，表现出优异的性能，在越来越多的 领域逐渐占据重要地位。而基于l i n u x 调度算法的模拟器则少之又少，已有的模 拟器总是在某些方面表现不足，无法很好的模拟l i n u x 的调度过程。 本文首先分析了l i n u x 发展史上最为重要的三个调度算法。包括2 4 内核中 的o ( n ) 调度算法，2 6 内核中的o ( 1 ) 调度算法以及最新的c f s 调度算法。其中 2 6 的0 ( 1 ) 调度算法的复杂度大大降低，与以往调度算法相比在性能上有了很大 提高。c f s 调度算法引入了模块化的结构，使算法的扩充更加容易。它的设计目 标在于使进程更加公平的共享处理器资源。然后分析了常见的调度算法模拟器， 重点介绍s c h e d s i m 模拟器。 在以上工作的基础上，我们对s c h e d s i m 模拟器进行改进以使其更好的支持 l i n u x 调度算法。这包括对多处理器的改进，全局分派算法的实现以及c f s 调度 器的模拟。对于多处理器的改进，我们使模拟器可以支持不同处理能力的处理器， 同时每个处理器都有自己的运行列队。对于全局分派算法，我们实现了两种简单 的方法，一种是按进程数量分派到处理器，另一种是按处理器的处理能力分派进 程。c f s 调度器则依据l i n u x 内核中的方法实现。最后给出在不同输入组合下模 拟器的输出效果。 关键词：c f s 调度器，s c h e d s i m 模拟器，多处理器，全局分派 浙江大学硕士学位论文 a b s t r a c t o p e r a t i n gs y s t e ms c h e d u l e ri s o n eo ft h em o s th o ts p o t st h a tf o rs y s t e m p e r f o r m a n c ei m p r o v e m e n t l i n u x ，8 8am a i n s t r e a mo p e r a t i n gs y s t e m ，s h o w i n ge x c e l l e n t p e r f o r m a n c ea f t e ri m p r o v i n gf o rm a n yt i m e s i tp l a y sa ni m p o r t a n tr o l ei nag r o w i n g n u m b e ro fa r e a 8g r a d u a l l y t h es i m u l a t o rb a s e do nl i n u xs c h e d u l i n ga l g o r t h r ai s e x t r e m e l yr a r e ，a n dm o s to ft h e mh a v ed i s a d v a n t a g ei ns i m u l a t et h es c h e d u l i n gp r o c e s s o fl i n u x t h i sp a p e ra n a l y z e dt h r e ei m p o r t a n ts c h e d u l i n ga l g o r i t h mi nt h eh i s t o r yo ft h e d e v e l o p m e n to fl i n u x i n c l u d i n gt h eo ( n ) a l g o r i t h mi n2 4k e r n e l ，t h eo ( 1 ) a l g o r i t h mi n 2 6k e r n e la n dt h el a t e s tc f sa l g o r i t h m t h ec o m p l e x i t yo fs c h e d u l i n ga l g o r i t h mi n2 6 k e r n e lh a sb e e n g r e a t l y r e d u c e da n dt h e p e r f o r m a n c e h a sb e e n g r e a t l y i m p r o v e d ，c o m p a r e dw i t ht h ep r e v i o u ss c h e d u l i n ga l g o r i t h m c f sa l g o r i t h mi n t r o d u c e d am o d u l a rs t r u c t r u e ，s ot h a ti t se a s i l yt oa d dn e w a l g o r i t h m t h ed e s i g ng o a li st om a k e t h ep r o c e s s o rr e s o u r c e sm o r ee q u i t a b l eb e t w e e np r o c e s s e s t h e nw ea n a l y z e dc o m m o n s c h e d u l i n ga l g o r i t h ms i m u l a t o r s ，w ef o c u s e do ni n t r o d u c i n gs c h e d s i mw h i c hw eu s e d i no u r p a p e r o nt h eb a s i so fp r e v i o u sw o r k ，w ei m p r o v e ds c h e d s i ms i m u l a t o rt ob e t t e rs u p p o r t t h el i n u xs c h e d u l i n ga l g o r i t h m t h i si n c l u d e st h em u l t i p r o c e s s o ri m p r o v e m e n t s ，t h e g l o b a ld i s p a t c h i n ga l g o r i t h ma n dt h es i m u l a t i o no fc f ss c h e d u l e r f o rm u l t i p r o c e s s o r i m p r o v e m e n t s ，w em a d et h es i m u l a t o rt os u p p o r td i f f e r e n tp r o c e s s o r s ，e a c hp r o c e s s o r h a si t so w nr u n q u e u e f o rt h eg l o b a ld i s p a t c h i n ga l g o r i t h m ，w ea c h i v e dt w os i m p l e m e t h o d s ，o n ei sb a s e do nt h en u m b e ra s s i g n e dt ot h ep r o c e s s o r s ，t h eo t h e ri sb a s e do n t h ep r o c e s s i n gp o w e ro f e v e r yp r o c e s s o r t h ei m p l e m e n t a t i o no fc f ss c h e d u l e rf o l l o w s t h el i n u xk e r n e lm e t h o d f i n a l l y , w es h o wt h ee f f e c tu n d e rd i f f e r e n ti n p u tc o m b i n a t i o n s o ft h en e ws i m u l a t o r k e y w o r d s ：c f ss c h e d u l e r , s c h e d s i ms i m u l a t o r , m u l t i p r o c e s s o r , g l o b a ld i s p a t c h i n g 浙江大学硕士学位论文图目录 图目录 图2 1 运行队列和优先级数组结构图1 1 图3 1 系统的高层结构图2 6 图3 2s c h e d s i m 类结构图一2 9 图3 3s c h e d s i m 效果图3 0 图3 - 4s c h e d s i m 流程图3 1 图4 1 典型多核架构。3 5 图4 2f w d 分派算法4 0 图4 3c f s 调度器处理流程。4 3 图4 4s c h e d s i m 模拟器结构4 4 图5 1 进程选择界面4 7 图5 2 改进s c h e d s i m 效果图4 8 图5 3s g d 分派算法下多处理器的系统性能4 9 图5 4f w d 分派算法下多处理器的系统性能5 0 i l i 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝姿态鲎或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者繇高僧签字隰哪年月汐日 浙江大学硕士学位论文 第一章绪论 1 1 研究背景 第一章绪论 目前，除了w i n d o w s 以外最为流行的操作系统便是基于l i n u x 的操作系统。 l i n u x 在服务器、桌面、移动嵌入式、网络、高端等领域已开始成为主流操作系 统之一，发展异常迅速。在服务器领域，l i n u x 操作系统的市场占有率已达到2 0 以上，与w i n d o w s 操作系统一起，成为了二元技术平台的主流操作系统；而在移 动嵌入式领域，以智能手机为例，l i n u x 尽管遇到了s y m b i a n 、w i n d o w sm o b i l e 以及基于开源“n e tb s d ”的m a c o s x 等嵌入式操作系的激烈竞争，但从目前的 发展来看，已经在竞争中取得了主动。 在过去的2 0 0 7 年，中国l i n u x 软件市场规模总量达到2 亿元，较去年同期增 长2 0 以上，仍在操作系统市场保持较高增速长。近些年来，电信运营商之间的 竞争不断升级，花样翻新的增值业务成为竞争的重要手段：同时，运营商们又需 要控制新建系统的成本。在这样的环境下，l i n u x 服务器产品被越来越多地应用 于电信增值业务系统中。在金融行业，l i n u x 服务器产品前几年已经在替换s c o u n i x 方面成绩斐然。在2 0 0 7 年，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 产品将被越来越多地应用于电信、 金融、政府、能源等关键行业。 调度算法的研究一直是人们关注的焦点。早期大多关注于实时操作系统调度 算法【1 4 】，当时处理器能力较弱，调度算法的优劣对系统性能的影响起着重要的作 用。其中“u 和l a y l a n d 的关于周期性任务的调度分析是最早的相关学术文献【5 】。 l s h a 等人概述了实时调度理论的发展简史【4 】。随着l i n u x 的快速发展，很多研究 浙江大学硕士学位论文第一章绪论 机构都在它的基础上做出改进并应用到商业系统中，应用最多的是裁剪l i n u x 系 统并改进相关部分以适应嵌入式系统。由于调度算法对l i n u x 系统性能起着至关 重要作用，因此在这方面的研究一直是很多科研部门的焦点所在。随着l i n u x 2 6 内核的发布，o ( 1 ) 的调度算法【6 1 取代了旧版本中o ( n ) 调度算法【7 1 ，而新调度算法 c f s ( c o m p l e t ef a i rs c h e d u l i n g ) 嫡9 】也加入到最新的版本中。系统在整体性能上比 过去有了很大的提高。 调度算法的开发与实现并不是一件容易的事，很多情况下需要先对算法进行 模拟测试，然后才能决定是否有必要在真实平台上实现。目前在模拟调度算法方 面存在很多平台，如k e v i nk l e u n g 实现的l i n u x 调度过程模拟器【1 0 1 、c s c i1 5 2 c p u 调度算法模拟器【l l 】、s u k a n y as u r a n a u w a r a t 实现的单c p u 调度算法模拟器【1 2 】 以及开源项目s c h c d s i m 【1 3 】。它们大多都提供了丰富的图形界面，可以很直观的看 到模拟过程，而且还提供各种不同的调度算法，可以自已定制模拟进程等。 1 2 研究内容 由于调度算法在l i n u x 操作系统中具有极为重要作用，本文将研究l i n u x 调度 器的发展过程及在各个阶段所使用的调度算法，重点分析最新调度算法c f s ( c o m p l e t ef a i rs c h e d u l i n g ) ，该算法在内核版本2 6 2 3 中发布，它采用了与以往 调度算法完全不同的思想实现，其目的旨在使运行的进程更加公平的共享c p u 资源。除此以外，本文还将研究调度算法模拟平台，模拟平台在算法的开发中起 到了很重要的作用，好的模拟平台可以方便的实现新的调度算法并能真实模拟出 调度的整个过程，使得算法在实现之前有一个初步的评测。本文将重点分析 s c h e d s i m 平台，详细分析其在支持多处理器架构的缺点并对其做出改进。 c f s 调度算法：c f s 调度算法是l i n u x 最新调度器的一个重要部分。另一个 重要部分是模块化调度核心，模块化是调度器面向对象思想的体现，每个调度器 通过调度类来实现，按照调度类的接口实现自己的调度算法。模块化的引入使得 调度器的扩充更为容易。而c f s 调度算法则是作为一个调度模块来实现的。它使 任务尽量按照自己的需求分配c p u 时间，所有任务在整体上公平的共享c p u 资 2 浙江大学硕士学位论文第一章绪论 源。本文将研究l i n u x 模块化的调度结构以及c f s 调度算法如何实现模块化的调 度接口。 调度算法模拟平台s c h e d s i m ：s c h e d s i m 是一个开源软件项目，实现了通用调 度算法的模拟平台，提供了良好的接口及几种常见的调度算法，可以容易的实现 新的调度算法并可立刻获得直观的结果。它提供了非常直观丰富的图形输出，从 而使得用户对调度过程一目了然。但它对多处理的情况支持太单一，系统中只有 一个就绪队列，仅采用全局调度算法。并且所有处理器的处理能力都一样，不能 很好的模拟a m p 架构【1 4 1 5 1 。本文将对s c h e d s i m 的结构进行分析，重点研究其对 进程的模拟以及模拟流程。在此基础上，对模拟器进行改进，以使其支持多处理 器架构。 1 3 研究目标 l i n u x 调度算法在其发展史上起着非常重要的作用，不同的算法对系统性能 的影响是不一样的。l i n u x 的调度算法主要经历了三个阶段，通过分析l i n u x 发展 史上比较重要的几个算法，对l i n u x 调度器有更为明确清晰的认识。尤其对于新 的c f s 调度算法，通过分析它的代码深入理解该算法背后蕴涵的思想。进一步认 识l i n u x 进程的组织方式。通过分析s c h e d s i m 模拟调度平台的实现，掌握模拟调 度算法的方法，改进s c h e d s i m 模拟器，使它更为真实的反映系统调度过程。其中 包括增加对a m p 体系结构的支持，为每个处理器模拟一个运行队列，添加全局 分派接口及几种简单的全局分派算法，并使其支持c f s 调度算法。 1 4 本文组织结构 根据上述研究内容和研究目标，文章其余部分内容组织如下： 第二章： 介绍了l i n u x 调度器的发展历史，尤其介绍了最为重要的三种调度器，包括 2 4 内核中的o ( 1 ) 调度器，2 6 内核中的o ( n ) 调度器以及最新的c f s 调度器。 第三章： 浙江大学硕士学位论文 第一章绪论 我们介绍了常见的几种调度模拟平台，重点介绍了s c h e d s i m 模拟平台，分析 其系统架构以及它在支持多处理器方面的缺点。 第四章： 在本章中，我们给出了针对s c h e d s i m 的不足改进的地方。这主要包括增加对 多处理器支持，使用户可以定制每个处理器的处理能力，同时增加对于负载过重 情况的考虑，使调度平台可以更加灵活的处理负载状况；增加了全局分派算法， 分派算法对于初始负载状况具有重要作用，好的分派算法可以避免过多的负载均 衡，从而减少系统的额外开销；增加对l i n u x 调度器的支持，尤其是c f s 调度算 法的支持，可以使用户对l i n u x 新调度算法有更清晰的认识。 第五章： 在本章中，我们首先给出了数据的模拟产生方法，包括进程信息、处理器信 息以及调度算法的选择。然后针对不同的组合情况模拟运行，并给出分析结果。 从中可以看到，处理器数目越多其所能负担的进程数目就越大，对于进程数目少 时，处理器的一味增加并不能带来性能的更高提升，这主要是因为此时进程的特 征对性能起重要作用。我们还可以看出，分派算法对系统性能的提升有一定作用。 第六章： 本章对全文内容进行了总括，回顾了本文的主要研究内容，归纳了本文的主 要贡献以及创新点，并指出进一步可以进行研究的内容，作为下个阶段研究的重 点。 1 5 本章小结 在本章中，我们首先介绍了近些年来l i n u x 的兴起以及调度算法在其中所起 的重要作用，然后我们介绍了l i n u x 最新的调度算法c f s ( c o m p l e t ef a i r s c h e d u l i n g ) 和调度模拟平台s c h e d s i m 。c f s 调度算法是在2 6 2 3 内核版本中加 入，它使得运行中的进程可以更加公平的共享c p u 资源。s c h e d s i m 模拟平台提 供了丰富的图形显示，但它也存在很多不足之处需要改进。另外，我们还列出了 本文的主要研究内容，研究目标以及文章的组织结构。 4 浙江大学硕士学位论文第二章i i n u x 调度器 第二章l i n u x 调度器 l i n u x 内核持续不断发展并采用新技术，在可靠性、可伸缩性和性能方面获 得了长足的发展。其调度系统也在一代又一代的新内核中得到更新，使系统整体 性能有了很大的提升。纵观l i n u x 调度器的发展，大致经历了三个阶段：最早期 的o ( n ) 调度算法，从最早的o 1 1 内核一直到2 4 内核都没有大的改变；随后在2 6 内核中发布了由i n g om o l n a r 设计并实现的o ( 1 ) 调度器，该调度器与过去调度器 相比获得了长足的进步；最后就是在2 6 2 3 内核中发布的新调度器，它采用了与 以往调度器完全不同的设计理念，具有革命性的意义。本章在认真阅读相关源代 码的基础上，分析了这三种调度器的相关细节。 2 1l i n u x 2 4 调度器 2 1 1 相关数据结构 在l i n u x 中，进程用t a s ks t r u c t 表示，所有进程被组织到以i n i tt a s k 为表头 的双向链表中，这个链表在系统中只有一个。运行队列链表把所有可运行状态 ( t a s kr l 肘n i n g ) 的进程描述符链接在一起，该运行链表在系统中也只有一 个，调度器总是从中寻找最适合调度的进程。所有c p u 被组织到以s c h e d u l ed a t a 为元素的a l i g n e dd a t a 数组之中。进程与所运行的c p u 之间可以相互访问。以下 将介绍几个关键的数据结构： t a s ks t r u c t ：该数据结构存储了进程的所有信息。在2 4 内核中只有进程，其 中包含轻量级进程。一个进程在核心中使用一个t a s ks t r u c t 结构来表示，其中与 调度器相关的信息主要包括：n e e dr e s c h e d 变量，标志是否需要调度；p o l i c y 变量， 保存调度策略，共有三种可选s c h e df i f o 、s c h e dr r 和s c h e do t h e r ； r tp r i o r i t y 变量，代表进程的静态优先级；c o u n t e r 变量，用于记录进程的剩余时 间片；n i c e 变量，用于计算进程的初始时间片大小；c l a u sa l l o w e d 变量，以位向 5 浙江大学硕士学位论文第二章l i n u x 调度器 量的形式表示可用于该进程运行的c p u ；c p u sr u n n a b l e 变量，以位向量的形式表 示当前运行该进程的c p u ( 相应位为1 ) 。如果不在任何c p u 上运行，则全为1 。 这一属性和c p u s属性结合，可以迅速判断该进程是否能调度到某一allowed c p u 上运行( 位 与”) ；p r o c e s s o r 变量，正执行进程( 如果有) 的c p u 下标；否则， 已执行了进程的最后一个c p u 的下标。 s c h e d u l ed a t a ：在多处理器平台下，除了t a s ks t r u c t 描述进程的信息外，还 应当需要另外的信息来描述每个c p u 正在做什么。在l i n u x 中，另有一个数据结 构对应于c p u ，可以利用它访问到某c p u 上运行的进程，这个数据结构定义为 s c h e d u l ed a t a 结构，包含两个属性：c u r t 指针，指向当前运行于该c p u 上的进程 的t a s ks t r u c t ，通常用c p uc u r r ( c p u ) 宏来访问；l a s ts c h e d u l e 时间戳，记录了上一 次该c p u 上进程切换的时间，通常用l a s ts c h e d u l e ( c p u ) 宏来访问。为了使该数据 结构的访问能与c p u 的c a c h el i n e 大小相一致，s c h e d u l ed a t a 被组织到以 s m pc a c h eb y t e s 为单位的a l i g n e dd a t a 联合数组中，系统中每个c p u 对应 数组上的一个元素。 i n i tt a s k s ：调度器并不直接使用i n i tt a s k 为表头的进程链表，而仅使用其中 的”i d l et a s k ”。该进程在引导完系统后即处于c p ui d l e ( ) 循环中。s m p 系统中，每 个c p u 都分别对应了一个i d l et a s k ，它们的t a s ks t r u c t 指针被组织到 i n i t _ _ t a s k s n r _ c p u s 数组中，调度器通过i d l e _ t a s k ( e p u ) 宏来访问这些”i d l e ”进程。 r u n q u e u eh e a d ：以r u n q u e u e为表头的链表记录了所有处于就绪态的进head 程( 当前正在运行的进程也在其中，但i d l et a s k 除外) ，调度器总是从中选取最 适合调度的进程投入运行。 2 1 2 调度时机 调度时机即在何种情况下需要进行重新调度。一般来讲，调度时机主要有两 种方式：一种是直接调用，即当前正在执行的进程主动放弃c p u ，这种情况可能 是由于时间片用完或者进程所需的资源无法得到满足；另一种是延迟调用，这是 通过把c u r r e n t 的n e e dr e s c h e d 字段设置为1 以延迟的方式调用的。下面我们就来 6 浙江大学硕士学位论文第二章l i n u x 调度器 看一下这两种方式： 直接调用：在核心应用中直接调用s c h e d u l e o 。这通常发生在因等待核心事件 而需要将进程置于挂起( 休眠) 状态的时候，这时应该主动请求调度以方便其他 进程使用c p u 。其过程通常可分为五步： 1 ) 把c u r r e n t 添加到合适的等待队列中 2 ) 把c u r r e n t 当前的状态改变为t a s ki n t e i 汛l 刀叮i b l e 或 t a s k u n i n t e r r u p t i b l e 3 ) 调用s c h e d u l e ( ) 4 ) 检查资源是否可用，如果不可用则转到第2 步 5 1 一旦资源成为可用的，把c u r r e n t 从等待队列中删除。 从上面我们可以看到，内核会反复检查进程所需的资源是否可用，如果不可 用，就通过调用s c h e d u l e 将c p u 让给其他进程。而当它再次获得c p u 资源时， 又要检查资源的可用性。 延迟调用：在系统调用执行结束后，控制由核心态返回到用户态之前，l i n u x 都将在r e tf r o ms y sc a l l 入口检查当前进程的n e e dr e s c h e d 值，如果该值为1 ，则 调用s c h e d u l e ( ) 。因此，只需要设置当前进程( c u r r e n t ) 的n e e dr e s c h e d ，就有机 会启动调度器。延迟调用在以下几种情况下进行： 1 1 当前进程用完它的c p u 时间片时，通过u p d a t ep r o c e s s函数进times 行。u p d a t e _ p r o c e s s _ t i m e s o 数由时钟中断触发，负责管理除0 号进 程( i d l e 进程) 以外的其他各个进程的时间片消耗。 2 ) 当一个进程被唤醒，并且它的优先级高于当前进程的优先级时，此时 需要重新调度以使高优先级进程得到执行。这个任务由 r e s c h e d u l ei d l e 函数执行，而该函数是由w a k eu pp r o c e s s 函数调用。 3 ) 当发出一个s c h e ds e t s e h e d u l e r 或s c h e dy i e l d 系统调用时，从函数名 称上我们就可以看出此时要进行重新调度。 由于启动s c h e d u l e ( ) 的时机实际上由当前进程决定，因此设置了n e e dr e s c h e d 并不意味着就能及时调度。 7 浙江大学硕士学位论文 第二章l i n u x 调度器 2 1 3 调度过程 l i n u x 的调度器主要实现在s c h e d u l e o 函数中。当系统发现需要进行重新调度 时，就调用该函数，其流程可以概括为以下五步： 1 ) 清理当前运行中的进程 2 1 ) 选择下一个投入运行的进程 3 ) 设置新进程的运行环境 4 ) 执行进程上下文切换 5 ) 后期整理 下面将简要介绍其中所涉及到的操作： 相关锁的操作，包括就绪队列锁m n q u q u e _ l o c k ，全局核心锁k e r n e l _ f l a g ，全 局中断锁g l o b a li r ql o c k ，进程列表锁t a s k l i s tl o c k ，这些是用来确保对所涉及到 的全局变量的同步。 n e x t 进程的选择，遍历所有运行队列，从中选择一个优先级最高的进程，首 先要判断该进程是否可调度，通过c p u s _ r u r m a b l e & c p u s a l l o w e d & ( 1 s t a t i c _ _ p r i o ) 2 2 3 调度过程 2 6 调度器依然采用s c h e d u l e 0 函数，与2 4 内核相比，它要更加简单一些， 减少了锁操作，优先级计算也拿到调度器外进行了。当进程要主动放弃c p u 时该 函数将被调用，或者s c h e d u l e rt i c k 0 设置了任务的t 礤n e e dr e s c h e d 标志。 然后s c h e d u l e 0 将会被调用。s c h e d u l e r 查当前运行进程的状态以及c p u 运行队列中的其它进程以决定是否需要调度以 及负载均衡。 调度器做的第一件事是检查处于合适的调度时机。之后禁止抢占并且检查当 前进程运行了多长时间。然后，如果当前进程是一个内核可抢占进程并且有一个 未处理的信号则置其状态为t a s kr u n n i n g ，否则将其从运行队列中删除。 这时，需要寻找另一个可运行的进程，如果在运行队列中没有可运行进程， 则尝试进行负载均衡。如果负载均衡找不到可运行进程，则切换到i d l e 进程。如 果运行队列中有可运行进程但其a c t i v e 优先级数组为空，则互换a c t i v e 和e x p i r e d 优先级数组。 此时在a c t i v e 优先级数组中已经有一个可运行进程。下一步就是查找位图以 寻找优先级最高的进程。这之后，在虚拟s m tc p u 上的依赖睡眠进程将有机会 运行，当前c p u 切换到i d l e 状态，依赖睡眠者可以被唤醒并且执行它的程序。 如果没有切换到i d l e 进程，则检查所选进程是否是实时的以及是否被唤醒。 如果这两者都没有，则增加它的s l e e p 并且重新计算它的动态优先级。_avg 现在s c h e d u l e ( ) 已经准备好实际进程切换了，它先清除换出进程的 t i f n e e d r e s c h e d 标志，更新进程切换统计信息，换出进程的s l e e p _ a v g 减 去它的执行时间。如果s l e e p _ a v g 小于0 则将其调整为0 。检查换出和换进进程是 否是同一个进程，然后进行实际的进程切换，该部分由c o n t e x t函数完成。_switch() 进程切换结束后抢占被允许，这时要检查在抢占禁止期问是否有抢占事件，如果 1 3 浙江大学硕士学位论文 第二章l i n u x 调度器 有则重新调度。 在2 4 系统中，在核心态运行的任何进程，只有当它调用s c h e , i u l e 0 主动放 弃控制时，调度器才有机会选择其他进程运行，因此我们说l i n u x2 4 的内核是 不可抢占运行的。缺乏这一支持，核心就无法保证实时任务的及时响应，因此也 就满足不了实时系统( 即使是软实时) 的要求。2 6 内核实现了抢占运行，没有 锁保护的任何代码段都有可能被中断，它的实现，对于调度技术来说，主要就是 增加了调度器运行的时机。我们知道，在2 4 内核里，调度器有两种启动方式： 主动式和被动式，其中被动方式启动调度器只能是在控制从核心态返回用户态的 时候，因此才有内核不可抢占的特点。2 6 中，调度器的启动方式仍然可分为主 动式和被动式两种，所不同的是被动启动调度器的条件放宽了很多。现在，无论 是返回用户态还是返回核心态，都有可能检查n e e dr e s c h e d 的状态；返回 核心态时，只要p r e e m p tc o u n t 为0 ，即当前进程目前允许抢占，就会根据 n e e dr e s c h e d 状态选择调用s c h e x l u l e 0 。在核心中，因为至少时钟中断是不 断发生的，因此，只要有进程设置了当前进程的n e e dr e s c h e d 标志，当前 进程马上就有可能被抢占，而无论它是否愿意放弃c p u ，即使是核心进程也是如 此。 2 2 4 负载均衡 进程在多数时候总是固定在一个c p u 上的，这是出于高效利用c a c h e 和内存 带宽的考虑。但有的时候一个c p u 上分配到的进程会比较多。例如在一个双处理 器系统中，所有任务都分配到一个处理器上而另一个处理器是完全空闲的，这种 情况是可能存在的。很明显，这不是最优分配策略，解决方案是将部分任务从一 个c p u 迁移到另外的c p u 。负载均衡是多c p u 系统中内核必须考虑的一个重要 部分。在2 4 内核中，进程p 被切换下来之后，如果还有c p u 空闲，或者该c p u 上运行的进程优先级比自己低，那么p 就会被调度到那个c p u 上运行，核心正 是用这种办法来实现负载的平衡。简单是这种负载平衡方式最大的优点，但它的 缺点也比较明显：进程迁移比较频繁，交互式进程( 或高优先级的进程) 可能还 1 4 浙江大学硕士学位论文第二章l i n u x 调度器 会在c p u 之间不断”跳跃”。即使是在s m p 的环境中，进程迁移也是有代价的， 2 4 系统的使用经验表明，这种负载平衡方式弊大于利，解决这一”s m p 亲和”的 问题是2 6 系统设计的目标之一。 2 6 内核会周期性的检查运行队列中的负载是否平衡，如果需要的话，就会 移动一些进程到其它的运行队列中。然而，如果要高效的利用多处理器系统，负 载平衡算法还应当考虑c p u 的拓扑结构。由此在2 6 内核中引入了调度域 ( s c h e d u l i n gd o m i n s ) 的概念，以实现更为高效负载平衡算法。 调度域就是一个c p u 集合，在集合中它的负载是均衡的。一般来讲，调度域 是分等级的，最高层的调度域囊括系统中所有的c p u ，由若干子调度域构成，子 调度域又由若干c p u 集合构成。依赖于调度域的分层结构，工作负载可以高效的 均衡。 负载均衡通过r e b a l a n c e实现，它是由 t 函数调用。_ t i c k o s c h e d u l e r i c k o r e b a l a n c et i c k ( ) 每隔一段时间( b u s yr e b a l a n c et i c k ) 都会启动一次 l o a d 平衡负载。 倾向于尽可能不做负载平衡，因此在判断是_ b a l a n c e o l i n u x2 6 否应该负载均衡的时候做了很多限制：系统最繁忙的c p u 的负载超过当前c p u 负载的2 5 时才进行负载平衡；当前c p u 的负载取当前真实负载和上一次执 行负载平衡时的负载的较大值； 各c p u 的负载情况取当前真实负载和上一次执 行负载平衡时的负载的较小值；对源、目的两个就绪队列加锁之后，再确认一 次源就绪队列负载有没有减小，否则取消负载平衡动作；源就绪队列中以下三 类进程参与负载情况计算，但不做实际迁移：正在运行的进程；不允许迁移到 本c p u 的进程( 根据c p ua l l o w e d 属性)；进程所在c p u 上一次调度事件发 生的时间( r u n q u e u e ：t i m e s t a m p，在时钟中断中取值)与进程被切换下来1ast t i c k 的时间( t a s ks t r u c t ：t i m e s t a m p ) 之差小于某个阀值( c a c h ed e c a y 的_ t i c k s n a n o s e c o n d 值) ，该进程还比较活跃，c a c h e 中的信息还不够凉。找到最繁忙的 c p u ( 源c p u ) 之后，确定需要迁移的进程数为源c p u 负载与本c p u 负载之差的 一半( 都经过了上述历史信息平滑) ，然后按照从e x p i r e d 队列到a c t i v e 队列、 从低优先级进程到高优先级进程的顺序进行迁移。但实际上真正执行迁移的进程 1 5 浙江大学硕士学位论文 第二章l i n u x 调度器 往往少于计划迁移的进程，因为上述三类”不做实际迁移 的情况的进程不参与迁 移。 每个c p u 还有一个迁移线程，这是一个具有高优先级的内核线程，它的工作 是确保运行队列是均衡的。该进程在系统启动时自动加载( 每个e p u 一个) ，并 将自己设为s c h e d f i f o 的实时进程，然后检查r u n q u e u e ：m i g r a t i o n _ q u e u e 中 是否有请求等待处理，如果没有，就在t a s ki n t e i 啄u p t i b l e 中休眠，直至 被唤醒后再次检查。 2 3c f s 调度器 c f s 调度器是由i n g om o l n a r 设计实现的，在2 6 2 3 内核版本中发布。其设 计初衷是让任务更加公平的共享c p u 资源。c f s 8 0 的设计可以总结为一句话： c f s 在真实硬件上实现了一个“理想，精确的多任务c p u 。理想多任务c p u 的 含意是c p u 具有1 0 0 的处理能力并且能以相同速率并行运行每一个任务。例如 有两个任务在执行，则每个任务利用c p u 5 0 的处理能力。 在新内核中添加的调度器的主要特性包括三个方面：模块化的调度器接口， 模块化的意思并不是说调度器能够以可加载模块的方式动态添加，而是在内核代 码中添加；c f s 调度器，这是新内核中最为核心的内容，它确保进程公平共享 c p u ；c f s 组调度，组调度是为了使用户能公平的共享c p u 。 2 3 i 相关数据结构 c f s 为每个c p u 使用一个按时间排序的红黑树结构。之所以使用红黑树， 是因为：红黑树总是平衡的；对红黑树的操作时间复杂度为o ( 1 0 9 n ) ，当进程数少 时其性能表现并不差，只有当进程数比较大时才会有一定性能损失，但对其最左 边节点的存取可以通过c a c h e 来高效实现。 对于每一个运行队列都有个数据结构来与红黑树相关联，这也是c f s 中最 为重要的一个数据结构，它就是s t r u c tc f sr q 。其定义如下： s t r u c tc f sr qf 1 6 浙江大学硕士学位论文 第二章l i n u x 调度器 s t r u e tl o a d _ w e i g h tl o a d ； u n s i g n e dl o n gn r _ r u n n i n g ； u 6 4e x e e _ c l o c k ； u 6 4m i n v r u n t i m e ； s t r u c tr b r o o tt a s k s _ t i m e l i n e ； s t r u c tr b n o d e 掌r b _ l e f l m o s t ； s t r u c tr b n o d e 宰r b _ _ l o a d _ b a l a n c e _ _ c u n ；, s t r u c ts c h e d _ e n t i t y 木c u r t ； u n s i g n e dl o n gn r s p r e a d _ _ o v e r ； # i f d e fc o n f i g f a i r g r o u 瞄c h e d s t r u c tr q 宰r q ；奉c p ur u n q u e u et ow h i c ht h i sc f s _ r qi sa ：t t a c h e d 枣 s t r u c tl i s t h e a dl e a f _ c f s