（计算机应用技术专业论文）基于smp架构的半虚拟化cpu调度算法研究.pdf

摘要 随着虚拟化技术的高速发展，其已广泛应用到服务器整合、集群计算、 多操作系统配置、硬件及内核开发等领域。调度算法是虚拟化技术中分配处 理器资源的重要方法，对虚拟机的磁盘读写速度、网络吞吐量及c p u 分配精 度等性能有很大影响。因此，对调度算法研究具有重要理论价值和应用价值。 本文通过对x e n 内核源代码的深入研究，分析了x e n 使用的b v t 、s e d f 、 c r e d i t 三种调度算法的实现原理；并在s e d f 调度算法的基础上，结合c r e d i t 算法提出了一种基于s m p 架构的动态负载平衡调度算法| i e d f 算法。该算 法能够实时跟踪s m p 中当前各处理器的负载情况，动态地将不同v c p u 合 理分派到负载较小的处理器中；当一个v c p u 结束运行时，调度程序将根据 v c p u 的运行情况动态地调整其下次的运行参数；在v c p u 调度过程中，能 够在绝对截止期限前完成运行的v c p u 将会被优先调度；在一个处理器进入 空闲状态前，将考虑其它处理器以从中迁移一个就绪的v c p u 到该处理器上 运行。 在分析s c h e d s i m 模拟器设计原理的基础上，设计并实现了基于s m p 架 构的s e d f 算法和i e d f 算法仿真。并对这两种调度算法进行了性能测试、 对比和分析。测试结果表明，i e d f 调度算法性能有较大的提升。 关键词：负载平衡；半虚拟化；对称多处理器；调度算法 哈尔滨工程大学硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fv i r t u a l i z a t i o nt e c h n o l o g y , i th a sb e e nw i d e l y a p p l i e di nt h e a r e a so fs e r v e rc o n s o l i d a t i o n ，c l u s t e rc o m p u t i n g ，m u l t i p l eo s c o n f i g u r a t i o n s ，h a r d w a r ea n dk e r n e ld e v e l o p m e n t ，e r e t h ec p us c h e d u l e ri sa l l i m p o r t a n ta p p r o a c ht oa l l o c a t et h ep r o c e s s o r si nv i r t u a l i z a t i o nt e c h n o l o g y t h e p e r f o r m a n c eo fs c h e d u l e rp l a y sak e yr o l ei nt h er a t eo fd i s kr e a d i n g w r i t i n g ， n e t w o r kt h r o u g h p u t ，c p ua l l o c a t i o na c c u r a c ya n ds oo n t h e r e f o r e ，t h er e s e a r c h o nt h es c h e d u l e rw i l lh a v eb o t hi m p o r t a n tt h e o r e t i c a la n di m p o r t a n ta p p l i c a t i o n a l v a l u e b a s e do nt h et h o r o u g h l yr e s e a r c ho fk e m e lo fx e n ，t h i sp a p e ra n a l y z e st h e i m p l e m e n t a t i o np r i n c i p l eo ft h ee x i s t i n gt h r e es c h e d u l e r s ，w h i c ha r eb v t , s e d f a n dc r e d i t c o m b i n i n gw i t ht h es e d fa n dc r e d i ts c h e d u l e r s ，t h e p a p e rp r o p o s e sa s c h e d u l e rw i t l lt h en a m eo fi e d ft h a tc a ni m p l e m e n tt h eg l o b a ld y n a m i cl o a d b a l a n c i n go ns m p t h es c h e d u l e rc a nd y n a m i c a l l ya l l o c a t et h ev c p u st ot h e l i g h t l o a d e dp r o c e s s o r sb yr e a l t i m em o n i t o r i n gt h ec u r r e n tl o a do fp e rp r o c e s s o r ； w h e nav c p uf i n i s h e si t sn m n i n g ，t h es c h e d u l e rc a nd y n a m i c a l l ya d j u s tv c p u p a r a m e t e r sb a s e do ni t s r u n n i n gs t a t u s ；i nt h ep r o c e s so fv c p us c h e d u l i n g ，t h e v c p u st h o s ec a nb ef i n i s h e db e f o r ei t sa b s o l u t ed e a d l i n ew i l lt a k ep r e c e d e n c e o v e ro t h e rv c p u s ；b e f o r eap r o c e s s o rg o e si d l e ，i tw i l lc o n s i d e ro t h e rp r o c e s s o r s i no r d e rt om i g r a t ea r e a d yv c p u t ot h ep r o c e s s o r b a s e do nt h ed e s i g no fs c h e d s i ms c h e d u l i n gs i m u l a t o r , t h e p a p e rd e s i g n sa n d r e a l i z e si e d fs c h e d u l e ra n ds e d fs c h e d u l e ro ns m e r o u n d l yp e r f o r m a n c et e s t s a n dc o m p a r i s o nh a v eb e e nd o n ef o rt h et w os c h e d u l e r s t h er e s u l t sm a n i f e s tt h a t t h ei e d fs c h e d u l e rc a n g r e a t l yi m p r o v et h ep e r f o r m a n c e k e yw o r d s ：l o a db a l a n c i n g ；p a r a v i r t u a l i z a t i o n ；s m p ；s c h e d u l e r 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用己在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。口 作者( 签字) ：尕帛彬 日期： k 罚年3 月r 日 l 。 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后口解 密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 l 一7r 作者( 签字) ：翱彬侈导师( 签字) ：盔以氇形入 i ， 日期： 砂即年；胁日凇硝年；月厂日 l 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 课题研究的目标和意义 随着信息技术的高速发展，计算机系统规模不断扩展、处理能力快速提 高、资源种类日益丰富、应用需求更加灵活多样。但是，计算机系统资源管 理工具一操作系统发展却相对滞后。当前，操作系统将各种应用综合到一台 计算机上仍面临两大问题：一是无法解决应用程序间的干扰或冲突问题；二 是不能满足用户独立拥有系统环境的需求的问题。因此，许多计算机用户不 得不通过增加计算机的数量来满足不同的应用需求。与此同时，当前针对这 些应用的计算机的平均利用率却不到3 0 ，导致计算机资源大量过剩。由此 产生了计算机硬件性能快速提高带来的资源相对过剩与用户渴望隔离环境并 能共享系统资源的大量需求之间的矛盾 1 1 。 虚拟化技术正是解决这一矛盾的主要方法之一。该技术通过软件模拟的 方式在某种类型的计算机( 或其它硬件平台) 及操作系统( 或其它相应的软件操 作平台) 的基础上，实现对另外一种计算机( 或其它硬件平台) 及操作系统( 或相 应的软件平台) 的模拟。当前，虚拟化技术已广泛应用到服务器整合 2 - 3 、集群 计算眇】、资源动态迁移 1 0 1 1 3 、计算机安全1 1 4 q 5 ) 、多操作系统配置、硬件及操作 系统内核开发等领域h 7 - 1 s l 。2 0 0 6 年初发布的国家中长期科学与技术发展规 划纲要将计算系统虚拟化的核心机理作为支撑信息技术发展的五大重要科 学基础之一，以及信息技术领域的优先主题。2 0 0 8 年，研究顾问咨询公司 g a r t n e r 在其2 0 0 9 年i t 行业十大战略技术报告中将虚拟化技术列为2 0 0 9 年i t 行业十大战略技术之首。可以预见，虚拟化技术是计算机技术发展的一 种必然趋势，它将给信息产业带来极大的变革。 作为虚拟化技术的一个重要分支一半虚拟化技术( p a r a v i r t u a l i z a t i o n ，或称 为部分虚拟化、准虚拟化、泛虚拟化) 通过消除硬件特性和特权指令极大的简 化了虚拟化过程。与其它类型虚拟化技术相比，该技术提供了最小的性能损 失【1 9 】。但是，半虚拟化技术环境的复杂性也为资源管理带了更大的挑战。在 哈尔滨工程大学硕士学位论文 半虚拟化系统环境中，系统工作量更大；系统中每个虚拟机只能占用有限的 资源并且其对资源的要求随着商业需求改变而不断的变化；同时，虚拟机在 保证拥有良好性能的前提下还需实现虚拟机间应用错误、性能和资源的完全 隔离【2 0 】。 目前，对半虚拟化技术中的资源管理还没有有效的方法，严重依赖于虚 拟机下层资源分配机制的特性。如何合理、有效地分配系统资源仍是该技术 中一个很大的难题1 1 6 - 2 0 1 。其中，半虚拟化技术的c p u 调度算法对保证虚拟机 间公平共享处理器资源和提高系统的整体性能起着至关重要的作用。在对半 虚拟化技术的研究中，由于其c p u 调度算法对系统的网络吞吐量、磁盘读写 速度及c p u 分配精度有很大的影响；调度算法的算法特性及运行情况直接影 响到计算机系统的性能和安全；从而，逐渐成为半虚拟化技术的热点研究领 域之一。开展对半虚拟化技术中c p u 调度算法的研究，进一步研究及设计调 度算法在对称多处理器( s m p ：s y m m e t r i cm u l t i p r o c e s s o r ) 上性能优化策略和 相关支持技术，对加速我国半虚拟化技术的发展和拥用自主知识产权的信息 产业的发展，保障国家信息安全，具有重要的学术、经济和社会意义。 1 2 国内外研究现状 当前，半虚拟化技术应用的典型例子是d e n a l i 和x e n 虚拟机管理器 ( v m m ：v i r t u a lm a c h i n em o n i t o r ) 。其中，d e n a l i 由华盛顿大学的d e n a l i 项目 组开发，该v m m 提供了一种轻量级虚拟机的实现方式。但是，由于d e n a l i 不支持在单个操作系统中实现多路复用、多址空间及存储管理中的虚拟层的 功能，导致在其上运行的每个虚拟机只能运行一些单用户单进程的操作系统。 从而，使得d e n a l i 的应用受到很大的限制。而x e n 虚拟机管理器由于其开源 及具有良好的性能而受到广大用户的欢迎 2 1 1 。现有的调度算法按进程( 或其它 调度的基本单位) 能否在处理器空闲时获得额外处理器份额可分为工作保养 模式( w e - - m o d e ：w o r k c o n s e r v i n g ) 和非工作保养模式( n w c - m o d e ：n o n w o r k c o n s e r v i n g ) 。其中，算法运行在工作保养模式时，进程( 或其它调度的 基本单位) 能够获得除系统分配的处理器份额外的额外份额；而运行在非工作 保养模式时则不能。在x e n 中，虚拟c p u ( v c p u ：v i r t u a lc p u ) 类似于操作 2 哈尔滨工程大学硕士学位论文 系统中的进程，各虚拟机以v c p u 为调度的基本单位。其使用了以下三种调 度算法来实现对v c p u 的调度： 1 、b v t ( b o r r o w e dv i r t u a lt i m e ) 算法 b v t 算法是由k e n n e t hj 。d u d a 在1 9 9 9 年提出，该算法将虚拟时间思想 引入进程调度当中，将时间分为真实时间和虚拟时间。其中，真实时间为硬 件计时器显示的时间值；虚拟时间为对实际时间经过某种规则计算后得到的 时间值。该算法用虚拟时间来监控进程的执行，每次总是调度具有最早的有 效虚拟时i 百j ( e v t ：e f f e c t i v ev i r t u a lt i m e ) 的进程 2 2 1 。当前， b v t 算法存在在 多处理器上运行时不能保证进程公平共享处理器资源的问题。a b h i s h e k c h a n d r a 针对此问题提出了一种应用在多处理器上的s f c ( s u r p l u sf a i r s c h e d u l i n g ) 调度算法【2 3 】，该算法能够实时地调整每个进程的权重( 或称w e i g h t ) 以使处于“饥饿”状态的进程尽快运行；t r a c yk i m b r e l 针对b v t 算法中进 程在多处理器上因频繁迁移而导致性能急剧下降的问题，提出了一种减少在 对称多处理器中进程迁移次数的算法洲；此外，s r i r a mg o v i n d a n 专门针对 b v t 算法在x e n 虚拟机管理器中对应用通信无法感知的缺陷，将虚拟机下层 的i o 行为加进v c p u 调度决策制定中，提出了一种具有通信感知能力的调 度算法【2 5 】。 2 、c r e d i t 算法 c r e d i t 调度算法是e i x e n 3 0 版本以来使用的缺省的调度算法，其为一种按 比例公平共享的非抢占式调度算法。每个v c p u 都用一个c r e d i t 值设定其优先 级。当c r e i d t 为负值时，其优先级为o v e r ；否则，优先级为u n d e r 。每个处理器 都在本地维护着一个就绪v c p u 队列，该队列以v c p u 的优先级由高到低排 序。系统每次调度处于队首且优先级为u n d e r 的v c p u 运行。当一个处理器空 闲时或该处理器的就绪v c p u 队列中无u n d e r 优先级的v c p u 时，它将查看其它 处理器以找到一个可运行的v c p u 至i j 本处理器上运行。目前，对c r e d i t 算法的 研究主要集中在该算法对系统性能影响方面。其中，l u d m i l ac h e r k a s o v a y c 寸该 算法在x e n 虚拟机管理器中上应用时的磁盘读写速度，网络吞吐量和c p u 分配 精度的影响进行了分析 2 6 - 2 7 1 ：d i e g oo n g a r o 分析t c r e d i t 算法对x e n 上虚拟机i o 性能的影响【2 川。 3 哈尔滨工程大学硕士学位论文 3 、s e d f ( s i m p l ee a r i e s td e a d l i n ef i r s t ) 算法 s e d f 算法源于c l l i u 在1 9 7 3 年提出的最早截止期限( e d f ：e a r l i e s t d e a d l i n e f i r s t ) 调度算法【2 9 】。x e n 中的每个v c p u 在初始化时，将由调度算法 为该v c p u 设定一个截止期限作为其被调度时的参考因素。当进行v c p u 调度 时，调度程序将优先调度截止期限最早的v c p u 。与c r e d i t 算法一样，当前对 s e d f 算法的研究还仅限于对配置有该算法的x e n 的性能( 磁盘读写速度、网络 吞吐量、c p u 分配精度、i o 性能) 影响进行了分析 2 6 - 2 8 。 在国内，由浙江大学何钦铭教授主导的“计算系统虚拟化基础理论与方 法研究 项目( 9 7 3 计划) 子课题虚拟计算系统评测理论与方法研究中已经 展开了在服务整合情况下，对虚拟机管理器所用的调度算法对网络性能影响 的研究。通过评估不同调度算法在不同网络负载时的性能，在公平共享c p u 资源的前提下提高了网络带宽分配的公平性，但尚无对以上三种调度算法的 改进措施。 综上，半虚拟化中c p u 调度算法正朝着能支持s m p 架构的多处理器间负 载平衡；能同时支持工作保养模式和非工作保养模式及具备很高的c p u 分配 精度的方向发展。由于半虚拟化技术中c p u 调度的特殊性，以上算法虽有所 改进，但仍面临着以下问题： 1 ) b v t 算法：不支持非工作保养型模式，且v c p u 的调度参数配置非常 困难； 2 ) s e d f 算法：不支持v c p u 的在s m p 上处理器间的负载平衡；当系统过 载时，其吞吐量将会急剧下降；此外，v c p u 的调度参数( 周期、最坏执行时 间) 在初始化后不能根据该v c p u 的运行情况动态调整； 3 ) c r e d i t 算法：全局负载平衡策略过于简单，仍易导致处理器因进程未 就绪而空闲的情况；此外，该算法还不能保证紧急v c p u 的实时性。 1 3 研究内容 本文在深入分析x e n 内核源代码的基础上，针对x e n 中s e d f 及c r e d i t 调度算法当前存在的问题，提出了一种基于s m p 架构的半虚拟化c p u 调度算 法，即i e d f ( i m p o r v e de a r i e s td e a d l i n ef i r s t ) 算法。该算法能够在进行v c p u 4 哈尔滨工程大学硕士学位论文 分派时就能综合考虑s m p 中各处理器的负载情况及c a c h e 的命中率，将新 创建的v c p u 分配到其上次运行或负载较轻的处理器中；在v c p u 调度时， 能够兼顾其绝对截止期限及完成率；当系统某个处理器空闲时，其将从其它 处理器的就绪v c p u 队列迁移一个最紧急的v c p u 到当前处理器上运行。此 外，该算法根据v c p u 运行情况动态的调整其运行参数。 在现有s c h e d s i m 调度模拟器的基础上，本文设计并实现了s e d f 和i e d f 算法的调度模拟器；并对i e d f 算法及s e d f 算法进行了模拟实验，将实验 结果进行了对比、分析。实验结果表明i e d f 算法相对s e d f 算法的性能有 较大的提升。 1 4 论文组织结构 论文分四章，文章其余部分内容按如下方式组织： 第二章相关背景技术 阐述了半虚拟化技术及x e n 的系统模型；介绍了s m p 的结构特征及x e n 对s m p 的支持；通过对x e n 内核源代码的深入分析，总结了x e n 中b v t 、 c r e d i t 和s e d f 三种调度算法的实现原理；并分析了三种算法存在的缺陷。 第三章基于s m p 负载平衡调度算法设计 进行了s m p 调度算法的需求分析；针对当前x e n 中s e d f 及c r e d i t 调 度算法存在的缺陷，设计了一种基于s m p 负载平衡调度算法。该算法包括 v c p u 参数的动态调整模块、进程分派模块、进程调度模块及负载平衡模块。 第四章算法模拟与实验 在s c h e d s i m 调度模拟器基础上，设计并模拟实现了i e d f 算法和s e d f 算法；配置了s e d f 算法及i e d f 算法调度模拟器的运行环境；分别以1 0 个、2 0 个、4 0 个和6 0 个进程为例模拟实现了s e d f 、i e d f 两种算法的调度 过程；对此两种算法进行了性能测试、对比及分析；并做了客观的性能评价。 5 哈尔滨工程大学硕士学位论文 第2 章相关背景技术 2 1 半虚拟化技术 虚拟化技术通过对计算机系统结构相关层中资源的模拟，实现对该层中资 源的划分，并将这些资源透明、公平的映射到其上层的虚拟机中。在虚拟机运 行时，利用虚拟机管理器实时监控虚拟机对其下层资源的调度；检测调度的合 法性；并按照相应的资源分配算法分配这些资源，保证对虚拟机下层资源和特 权指令的绝对控制【2 1 】f 3 0 】。现有的虚拟化技术与计算机体系结构的层次对应关系 如图2 1 所示： 虚拟化技术分类 硬件级虚拟化 ( 半虚拟化、全虚拟化) 指令级虚拟化 计算机系统结构层次 应用语言级机器m 5 ( 应用语言) 高级语言级机器m 4 ( 高级语言) 汇编语言级机器m 3 ( 汇编语言) 操作系统机器m 2 ( 作业控制语言系统) 传统机器m i ( 机器指令系统) 微程序级机器m o ( 微指令系统) 图2 1 虚拟化技术分类与计算机系统结构层次对应关系图 现有的虚拟化技术可分类为应用程序级虚拟化、操作系统级虚拟化、硬 件级虚拟化和指令级虚拟化【3 1 1 。其中，硬件级虚拟化技术又可分为半虚拟化 技术和全虚拟化技术。全虚拟化技术实现了对真实硬件中各部分完全的软件 模拟。该技术的优点在于不需要修改虚拟机中运行的操作系统的内核，兼容 6 哈尔滨工程大学硕十学位论文 性较好。但采用这种技术系统运行开销较大。 半虚拟化技术通过对系统中缺陷指令的替换，避免了全虚拟化技术中如” “动态指令重写”这种开销较大的方法，性能得到了很大提升。与全虚拟化 不同，使用半虚拟化技术的虚拟机能够感知其底层硬件的存在。现有的虚拟 机管理器软件d e n a l i 和x e n 已经实现了x 8 6 平台上的半虚拟化，并且在其上运 行的虚拟机具有比全虚拟化技术更高的性能。随着支持i n t e l v t 和a m d v 技术处理器的诞生，已经实现了虚拟机中的操作系统不经修改就可在采用半 虚拟化技术的虚拟机管理器上直接运行，从而使半虚拟化技术能同时支持半 虚拟化和全虚拟化两种技术中的虚拟机管理器【3 2 】【3 5 】。 2 2x e n 系统模型 x e n 是在2 0 0 2 年由英国剑桥大学i a np r a t t 发起研制的一种基于半虚拟化 技术的开源虚拟机管理器( 或称x e nh y p e r v i s o r ) 。其能够支持包括w i n d o w s 、 l i n u x 、s o l a r i s 及各种版本的b s d 操作系统，及多达1 0 0 多个操作系统同时 运行 3 3 1 。其系统模型如图2 2 所示： 图2 2 x e n 的系统模型 7 哈尔滨- t 程大学硕士学位论文 x e n 系统模型中最下层为物理硬件层( c p u 、物理内存、网卡、块设备) ； 最上层为虚拟机层；x e n 通过在物理硬件层上添加了一个虚拟机管理器层实 现了对物理硬件层的模拟，并向管理器层上的虚拟机层提供了硬件抽象。在 虚拟机层中，d o m a i n 表示一个运行的虚拟机执行的上下文；客户操作系统 ( g u e s to s ：g u e s to p e r a t i n gs y s t e m ) 表示在d o m a i n 中运行的操作系统。每个 d o m a i n 在创建时，系统将会为其分配一个i d 号。其中，d o a m i n o 在系统启 动时创建，其能够利用虚拟机管理器层的d o m a i n 0 控制接口对其它d o m a i n 进行一些应用级的管理控制，具体包括：其它d o m m n 的创建、终止；调度 参数的配置；c p u 、物理内存、网卡、块设备的访问及虚拟设备控制和管理。 系统中的各d o m a i n 间通过事件通道进行通信。x e n 将设备驱动程序分为前 端和后端两部分：前端负责收集、封装用户请求，并将请求通过事件通道转 发给后端；后端在接受用户请求后，根据请求的特征调用相应的标准设备驱 动程序为之服务。通过前后端的交互，使应用程序看起来好象自身直接在其 对应的实体计算机上 3 3 - 3 7 1 。 2 3x e n 对s m p 系统结构的支持 对称多处理器是一种典型的应用于企业服务器中的多处理器架构。其通 过包含两个或多个相连的处理器来实现对同一套进程的协同处理。通常， s m p 中采用完全相同的处理器( 包括型号、缓存、总线等) ；每个处理器拥有 独占的高速缓冲存贮器( c a c h e ) ；处理器间通过一条总线实现内存等其他系统 资源的共享。s m p 的结构如图2 3 所示p s ： 图2 3s 结构图 8 哈尔滨工程大学硕士学何论文 在s m p 中，每个处理器( 或称p r o c e s s o r 、c v u ) 内部实现了对本地高级可 编程中断控制器( l a p i c ：l o c a la d v a n c e dp r o g r a m m a b l ei n t e r r u p tc o n t r o l l e r ) 和输入输出高级可编程中断控制器0 _ oa p i c ：i n p u t o u t p u ta d v a n c e d p r o g r a m m a b l ei n t e r r u p tc o n t r o l l e r ) 的中断处理；每个处理器通过内存映射 i o ( m m i o ：m e m o r ym a p p e di n p u t o u t p u t ) 方式访问l a p i c 和i o a p i c 处理 器间通过i p i ( i n t e r p r o c e s s o ri n t e r r u p t ) 来进行异步通信，允许处理器向某些 甚至全部处理器发出中断请求。 x e n 通过两种途径来实现对s m p 的支持。第一，允许其上d o m a i n 拥有 多个v c p u ，它们地位平等( 每个d o m a i n 中v c p u 数目在该d o m a i n 创建时 通过其配置文件指定，不受s m p 中实际处理器数目的限制) ；第二，x e n h y p e r v i s o r 基于实际物理平台的处理器实现了s m p ，其处理器间通信使用物 理i p i 。当一个d o m a i n 在创建时将由系统生成相应的m p ( m u l t i - - p r o c e s s o r s ) 表或a c p i ( a d v a n c e dc o n f i g u r a t i o n & p o w e ri n t e r f a c e ) 表，供b i o s ( b a s i ci n p u t o u t p u ts y s t e m ) 或操作系统使用以识别系统中的多处理器资源。当x e n 内核装 载时，通过读取操作系统内m p 表或a c p i 表，获取s m p 上处理器的相关信 息。每个v c p u 内实现了虚拟的l a p i c ( v l a p i c ：v i r t u a ll a p i c ) 和虚拟的 i o a p i c ( v i r u a l l j oa p i c ：v i r t u a li n p u t o u t p u ta d v a n c e dp r o g r a m m a b l e i n t e r r u p tc o n t r o l l e r ) ，它们由下层的x e nh y p e r v i s o r 来请求发出虚拟的设备中 断。这样，使x e n 上层的虚拟机对i p i 的处理等效于实际物理机器上的i p i 处理，从而能够使支持s m p 的操作系统运行在虚拟机上时就如同在实际物 理机器上一样地使用i p i 进行通信【3 9 】。 2 4x e n 调度算法 x e n 以v c p u 为调度的基本单位。当一个d o m i a n 被创建时，系统将按 其配置文件指定的个数生成相应数目的v c p u ，并统一设置为暂停状态。在 d o m a i n 运行过程中，当一个应用程序准备运行时，系统将从该d o m a i n 的 v c p u 数组中分配一个v c p u 来运行该应用程序，并将该v c p u 添加到系统 中某一处理器的v c p u 队列上。x e n 内核中用s c h e d u l e r s 数组存储其内使用 的调度算法，开发人员可向该数组内添加自定义的调度算法。 9 哈尔滨- t 程大学硕士学位论文 图2 4v c p u 通用调度流程图 x e n 中每个处理器都在本地维护着一个就绪的v c p u 队列。每个处理器 用一个s c h e d u l ed a t a 结构体记录其当前状态。s c h e d u l ed a t a 共有四个参数： c u r t 指针，指向相应处理器上正在运行的v c p u ；i l d e 指针，指向着相应处 理器v c p u 队列中的空闲v c p u ；s c h e d u l el o c k 自旋锁，用于保护c u r r 所指 v c p u ，以防止c u r r 在v c p u 调度期间被恶意行为干扰，实现对c u r t 的互斥 共享操作；st i m e r 定时器，用于记录该处理器下次进行v c p u 调度的时间。 现假定系统中处理器个数为n 个，n i ；处理器集合为c p u s e p 1 0 哈尔滨工程大学硕士学位论文 ( p r o c e s s o r i10 鱼剑) 。处理器p r o c e s s o r i 中v c p u 通用调度流程如图2 4 所 示。 其中，姗，z 垤、r u n n a b l e 、b l o c k e d 和。汐i n e 为v c p u 的四种状态。其含 义如下：r u n n i r l g 表示v c p u 正在某处理器上运行；r u n n a b l e 表示v c p u 可 以运行，但还没被处理器调度运行；b l o c k e d 表示v c p u 被阻塞状态；o f f l i n e 表示v c p u 处于离线状态。 2 4 1b v t 算法 b v t 算法由k e n n e t hj d u d a 于1 9 9 9 年提出。该算法将时间分为实际时 间和虚拟时间：真实时间为硬件计时器记录的时间；虚拟时间为对真实时间 经过某种规则计算后得到的时间值。该算法用虚拟时间来监控进程的执行时 间，每次总是调度具有最早的有效虚拟时间的v c p u 。在系统初始化时，每 个v c p u 将分配一个权值来代表该v c p u 能获得的处理器份额。v c p u 根据 其权值来实现处理器的公平共享。系统用实际虚拟时间和有效虚拟时间来记 录v c p u 运行状态。其计算方式如式( 2 1 ) 、( 2 2 ) 所示： 彳，=彳f +f w f ( 2 1 ) 岛卜a i 一( w a r p ? ：0 )( 2 2 ) 其中，表示v c p u 实际运行时长( 由真实时间计算) ；w f 表示该v c p u 的权值大小；巨表示有效虚拟时间；4 表示实际虚拟时间；w a r p 为时间偏 移标记，表示v c p u 能否提前运行；为v c p u 能提前运行的虚拟时间长 度。 b v t 算法是一种抢占式的工作保养模式算法。该算法通过w r a p 值来调 整e v t 使v c p u 获得处理器的时间提前，即v c p u 从预定的有效虚拟时间 中借用了一定的虚拟时间以获得更高的调度优先级。此外，该算法还用厶和 来限制v c p u 的w a r p 值的大小及进行w a r p 操作的频率，以防止进程过度 借用虚拟时间【2 2 】。 b v t 算法在多处理器和单处理器中执行时代价都很低；其能够满足i o 密集型及实时应用的低时延要求。但是，由于它缺乏对非工作养模式的支持； 算法的效率依赖于算法中参数的配置，增加了算法实现的难度；这些因素都 哈尔滨工程大学硕士学位论文 限制了该算法在许多环境中的应用。 2 4 2c r e d i t 调度算法 c r e d i t 算法由e m m a n u e la c k a o u y 设计并实现，是一种按比例共享的非抢 占式调度算法。该算法主要优点为：既能支持工作保养模式又支持非工作保 养模式；支持s m p 架构中处理器间的负载平衡；所有v c p u 都具有公平的 机会获得处理器。 2 4 2 1 相关数据结构 v c p u ：与调度相关的参数包括c r e i d t 、d o m a i n 、c p ua f f i n i t y 和p h 。其 中，c r e d i t 用于评估v c p u 优先级，初始值为3 0 0 ；调度程序每隔3 0 m s 对所 有可运行的v c p u 的c r e d i t 值减少1 0 0 ；d o m a i n 表示该v c p u 所在的d o m i a n ； c p ua f f i n i t y 表示能运行该v c p u 的处理器集合；p r i 记录着v c p u 的优先级。 c r e d i t 算法中的v c p u 共有b o o s t 、u n d e r 、o v e r 、i d l e 四种优先级。 当一个v c u p 刚被唤醒时，其优先级将被设置为b o o s t ，优先级最高；c r e d i t 为正数时v c p u 优先级为u n d e r ；c r e d i t 为负数时v c p u 优先级为o v e r ； v c p u 空闲时优先级设置为i d l e ，该优先级最小。系统中只有优先级为 b o o s t 和u n d e r 的v c p u 才能被调度运行。若一个处理器的就绪队列中 的v c p u 优先级小于u n d e r ，调度将对该处理器中的所有v c p u 的c r e d i t 值进行重新分配，并更新其砂f 值 4 0 4 2 1 。 c s c h e d 研v ：用于监控着整个系统的运行情况，其主要参数有 、 、_ l o c k i d l e a c t i v e s d o m 。其中，l o c k 为调度自旋锁，用来在c s c h e dp r i v 更新时对其施加 保护，可有效避免多个并发操作对其竞争；i d l e 记录着整个系统中空闲处理 器集合；a c t i v e s d o m 为双链表队列，其记录着当前系统中活跃的d o m m n 。 r u n q 队列：记录每个处理器内就绪v c p u 的双链表队列。该队列按照 v c p u 的优先级排序，处于相同优先级的v c p u 插入队列越早，位置越靠前。 a c t i v e _ v c p u 队n - 记录每个d o m a i n 中活跃v c p u 的双链表队列。其按 照v c p u 被解除暂停状态的顺序从前向后依次排列。 1 2 哈尔滨工程大学硕士学位论文 2 4 2 2c r e d i t 调度过程 当处理器上正在运行的v c p u 用完其时间片( 3 0 m s ) 时，系统将对该处理器 进行v c p u 调度操作。若处理器上的r u n q 中有优先级大于o v e r 的v c p u ，将 调度该处理器中m n q 队首v c p u j , 云_ 行；否则，对该处理器进行负载平衡，以从 其它处理器上的m n q 中获取一个合适的v c p u 至u 该处理器上运行。 在c r e d i t 算法的调度流程中，需要对r u n q ，队列进行更新，并重新设置 c s c h e dp r i v 中的i d l e 参数。此外，还可能涉及到对处理器间的负载平衡操作。 p r o c e s s o r t 将从其它处理器的r u n q 队列中找一个优先级大于o v e r 的v c p u 到p r o c e s s o r i 上运行。其具体实施方法为： 步骤l ：以p r o c e s s o r i 为起点，找到下一个空闲且可用的处理器； 步骤2 ：若对找到的处理器的s c h e d u l ed a t a 实施自旋锁成功，且该处理 器的r u n q 队列上存在一个v c p u 的优先级大于o v e r ，将该v c p u 从其所 在的r u n q 中删除，执行步骤4 ；否则，执行步骤3 ； 步骤3 ：以该处理器为起点接着找下一个空闲且可用的处理器，执行步 骤2 ； 步骤4 ：将找到的v c p u 置于处理器上p r o c e s s o r f 运行，负载平衡结束。 2 4 2 3c r e d i t 算法的不足 c r e d i t 算法的不足之处在于： 1 、配置有c r e d i t 算法的x e n 运行还不太稳定，其c p u 分配错误率大约 在 1 ，3 0 】区间，远高于x e n 中其它的v c p u 调度算法； 2 、配置有c r e d i t 算法的x e n 除其在单处理器上的工作保养模式下的磁 盘读吞吐量稍好于配置s e d f 算法外，其磁盘读写速度，网络吞吐量和c p u 分配精度总体上都不及运行在s e d f 算法下时闻； 3 、由于c r e d i t 算法的非抢占特性及较为简单的负载平衡策略，使得其不 能保证紧急应用的实时性要求。 1 3 哈尔滨工程大学硕士学位论文 2 4 3s e d f 调度算法 自x e n 3 0 版本以来，s e d f 算法和c r e d i t 算法为x e n 中可选的两种调度 算法。s e d f 算法为一种动态优先级调度算法。v c p u 的优先级随着其绝对 截止期限的变化而改变。在任何时刻，具有最早绝对截止期限的v c p u 优先 级最高。当处理器进行v c p u 调度时，将总是调度具有最早绝对截止期限的 v c p u 到该处理器上运行。 s e d f 算法优点在于：效率很高、实现容易；易于推断及计算；能支持工 作保养模式和非工作保养模式；支持实时性较强的应用；当系统负载较轻时， 其处理器的利用率最高可达1 0 0 【2 6 1 。 2 4 3 1 相关数据结构 与调度相关的参数有p e r i o d 、s l i c e 、e x t r a 、d e a d la b s 、c p u t i m e 、d o m a i n 、 s c o r e p e n 、s c o r e u t i l 、e x t r a w e i g h t 、s h o r tb l o c kl o s tt o t 、n p e r b e g 和 s e d f。其中，表示的相对截止时间，其与该周_cpui n f o p e r i o d v c p uv c p u 期大小相等；s l i c e 表示v c p u 在最坏情况下的执行时间；d e a d la b s 表示v c p u 的绝对截止期限；e x t r a 用于标识为v c p u 运行模式的逻辑标识符，当e x t r a 为真时，表示v c p u 运行在工作保养模式下；否则，表示其运行在非工作保 养模式下；c p u t i m e 用于记录v c p u 在当前周期内运行的时长；d o m a i n 表 示v c p u 所属的d