作者：河南省计算机学会
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
计算机研究新进展(2011)试读：
前言
“2011 河南省计算机大会暨学术年会”是河南省计算机学会主办的年度学术交流大会。本次大会由信阳师范学院承办，论文集由电子工业出版社出版。河南省计算机学会按照章程于2010年11月13日顺利地进行了换届选举，第五届理事会成立。第五届理事会继续坚持和发扬第四届理事会的工作精神与工作作风，朝气蓬勃地开展着各项工作，继续努力致力于“三主一家”（即学会要作为河南省计算机学术交流的主渠道，科学普及的主战场，国内外民间学术交流的主要代表，成为会员之家）的建设，在河南省计算机领域的建设中发挥积极的作用。河南省计算机学会 2008 年创办的河南省大学生程序设计竞赛已成功举办了四届，参赛队伍逐年大幅增加，有力地推动了河南省大学生程序设计能力的锻炼与提高，已成为学会的又一品牌项目。学会继续在组织发展、服务会员、学术交流、青少年信息学奥林匹克竞赛等方面积极开展着工作。学会与电子工业出版社的合作进展顺利，陆续出版的《计算机组成与维护》、《Linux 操作系统》、《32 位汇编语言程序设计》、《C/C++程序设计教程——面向过程分册》、《C/C++程序设计教程——面向对象分册》、《Java 程序设计应用教程》、《Access 数据库程序设计》、《MATLAB 基础及应用教程》、《网络安全技术及应用》等教材得到了广泛的应用（其中《计算机组成与维护》、《Access 数据库程序设计》等已推出第二版），取得了良好的社会效益。为办好本次计算机大会，信阳师范学院进行了精心的组织，为保证会议的圆满成功付出了艰辛的劳动。学会表示衷心的感谢。同时学会相信本次会议仍将是一次老友新朋齐相聚、相互交流谋发展的促进会，是推进新技术发展的展示会，是河南省计算机科学技术水平的检阅会，是促进会员之间友好交流的联谊会。学会真诚地希望广大计算机科技工作者及各政府机关、高等院校、企事业单位的领导关心支持河南省计算机学会，积极参与学会的各项活动，进行学术交流，为推进河南省计算机科学与技术的发展共同努力。本论文集是学会与电子工业出版社合作的继续，感谢论文作者对学会工作的支持，感谢为论文审稿、修改的专家学者们，同时也由衷地感谢电子工业出版社的友好支持和大力帮助。河南省计算机学会2011年8月SIMD优化中的指令等价替换实现方法111郭绍忠 ，许瑾晨 ，陈世淼 （1. 解放军信息工程大学信息工程学院，郑州，450002）摘 要：针对因缺少指令或指令性能较低而降低 SIMD 扩展数学函数库性能的问题，提出了一种有效的基于 SIMD 扩展指令的指令等价替换方法。该方法在缺少指令方面，合理应用 Karatsuba 快速乘法思想实现了高 64 位乘法；在指令性能较低方面，利用现有逻辑运算、移位和整理等向量指令替换性能较低的算术右移指令。在实现指令等价替换后函数运行性能有显著提升，改进后函数性能平均提高13%左右。关键词：SIMD技术；指令等价替换；高64位乘；算术右移Implementation of Instruction-equivalent substitutiontechnique in SIMD optimization111Guo Shaozhong, Xu Jinchen, Chen Shimiao(1. Institute of Information Engineering, PLA Information Engineering University, Zhengzhou 450002)Abstract：According to the performance decline problem of SIMD extended mathematic function library due to lack of instructions or bad instruction efficiency, an effective instruction-equivalent substitution technique based on SIMD extended instructions is proposed. With regard to lack of instruction, this technique implements the high 64-bit multiplication applying the Karatsuba Fast Multiplication principle. To solve the problem of low efficiency of instruction, the arithmetic right-shift instruction is substituted with existing vector instructions like logic operation and shift operation. After the equivalent instruction substitution, the performance improvement of the function is increased by 13% on average.Key words：SIMD technique; equivalent instructions substitution; high 64-bit multiplication; arithmetic right-shift operation随着大规模集成电路VLSI工艺的快速发展，计算机体系结构分为精简指令集计算机RISC（Reduced Instruction Set Computer）和复杂指令集计算机CISC（Complex Instruction Set Computer）两个方面，在此过程当中，RISC 以其结构及软件开发上的优越性逐步取得了斗争的胜利，CISC 纷纷转向 RISC设计，[1]目前已有的通用处理器中，90%均采用 RISC 架构。RISC 的设计思想是在通过减小平均指令执行周期CPI值，提高指令执行并行度 ILP（Instruction level parallelism）来获得高性能的CPU。为了实现比CISC更简化的指令系统，通过分析指令的执行频度和计算机结构复杂性之间的关系，采用20%的简单指令的组合实[2][3][4]现不常用的80%的那些指令功能，使处理器的结构更加简单、合理、有效。对于 RISC 包含两层含义：一方面是在不影响指令集完备性的基础上减少指令集中不必要的指令；另一个方面在不影响指令集完备性的基础上简化指令集中某些指令的功能。目前，在基础函数库方面的研究都基于 RISC 结构，在算法设计及实现过程中，往往因为 RISC以上两方面的局限性造成函数库整体性能较低的现象。为了尽可能在算法级提高函数的性能，需要在保证指令性能的同时提出新的替代算法以实现指令的软件化。这方面的工作目前基本没有相关研究。1 乘法指令等价代换在数学函数库实际实现过程中发现由于部分指令的缺失，严重影响了整个函数算法的性能，其中包括64位乘法指令、高64位乘法指令和整数浮点转换指令等，这些指令往往构成了算法中的主要部分。为了有效解决指令缺失问题，需要相应的算法实现指令的软件化，本文以高 64 位乘法指令的实现为例加以说明。本文将多项式的快速乘法思想运用到浮点数的乘法中，实现高精度、高效率的浮点64位乘法运算。[5]Karatsuba 多项式快速乘法算法利用分治法的思想将多项式分成次数相同的2两部分，经过分解、求解和合并的步骤，将算法复杂度由O(n )降低到O(n log n) 2[6][7]，算法如下：利用此算法的思想及良好的时间复杂度，针对浮点数的特点，对算法进行改进以实现适用于浮点数计算的算法。1.1 浮点快速乘法算法此算法适合于存在阶码乘法并需要计算高阶乘法的情况。算法将多项式转化为浮点数，将浮点数分解成位数相同的高低两部分分别计算。在计算过程中，针对浮点数加减法会出现进位/借位的问题，将原来快速乘法三次乘法的计算转化为四次乘法。这样的做法增加了算法的乘法次数，使得时间复杂度有所提高，但在实现过程中简化了对进位的判断，在整体性能上得到了提高。1.2 浮点快速乘法实现现以32位乘法（无符号乘）为基础，实现无符号高64位乘法（64位×64位，取128位结果的高64位），整个过程可以分为三个部分。1．分解：将两个 64 位浮点数（a0，a1），分解为四个 32 位浮点数。利用左右移位操作实现此功能。2．求解：分别计算四个32位浮点数的两两乘积。利用无符号乘法（umulw）指令进行计算。3．合并：将FG右移32位，再加上FG+FG ，将结果右移32位。判断结000110果是否存在加法进位，若存在进位则在结果的第 33 位（即将 1 左移 32 位）加 1，再加上FG；否则直接加FG。其中，利用无符号比较指令（cmpult）来产生1111最高位进位，如果结果比 2 个源操作数（当做无符号数）都小，则表示最高位有进位。2 向量算术右移指令等价代换SIMD 扩展指令集中部分向量指令，因为在功能上具有与之相应的串行指令，且使用频度不高，因此，处理器不提供这部分向量指令。如果要使用这一部分向量指令，只需将向量进行拆分成标量，然后通过与之相应串行指令来实现。这种做法因为增加了冗余的向量拆分与拼接操作，程序性能损失较大。但如果对这一部分指令使用等价的向量指令算法进行替换，就可消除冗余的指令操作，提高程序性能。这就是向量指令等价代换的基本思想。这种优化技术比较典型的应用是向量算术右移指令的等价代换。2.1 串行指令实现的向量算术右移算法在处理器硬件体系结构下，其指令集只提供了整数的算术右移指令 SRA，并没有提供向量算术右移指令。若采用处理器指令集提供的算术右移指令SRA，则只能将向量中的4个分量拆开，分别右移后再将 4 个分量拼接成向量，完成向量的算术右移功能。这种作法性能降低较大，因此需要通过向量指令的等价代换来实现向量的算术右移功能。为了便于问题的分析，从基础数学库程序代码中取出一个具有代表性的示例，其算法流程图如下。图1 利用向量的拆分与拼接实现向量算术右移功能的程序流程图2.2 替换算法分析处理器的 SIMD 扩展结构特性，采用向量的逻辑运算、移位和整理指令等操作减少向量拆分与拼接操作的冗余代码，以此替代串行指令实现的向量右移指令。因为向量算术右移指令是将向量寄存器中 4 个 64 位的分量进行算术右移，此操作将源操作数右移指定位，而在移出的空位补充源操作数的符号位。因此，算术右移指令的执行过程可以看成两个过程：首先对源操作数进行逻辑右移，然后对移出的空位补充源操作数的符号位。根据上述分析，可以得到向量指令等价代换算法的步骤如下：Step1：复制传入的4个参数符号，构造向量V0。Step2：将向量V整体右移32位后与V异或得到向量V。001Step3：根据规则位为1，位为0构造变量a ，并将变量a扩展成向量V ，其中002t为算术右移的位数。Step4：对第2步的向量V中8个32位整数进行判零操作得到结果向量V ，然13后根据V并利用第3步构造的向量V与全0向量进行结果选择得到向量V。324Step5：将传入的参数向量进行整体右移t位得到V ，并跟第3步构造的向量V52做非操作得到向量V ，将向量V和向量V做与操作得到向量V。6567Step6：将向量V和向量V做或操作得到向量算术右移后的结果向量V。4782.3 实验与结果分析本文研究的性能测试方法，是计算被测函数运行的节拍数。在实际环境运算节点上，分别对函数输入定义域内10万个16进制均匀分布的随机浮点数，分别对改进前后的算法进行性能测试，然后运用偏差方法求出 10 万个数据的平均值即为函数单次运行的节拍数，这样提高了性能测试的可靠性。对比分析得到的性能数据，表1列出了优化前后程序性能测试对比。其中性能提升的计算公式是：性能提升=（优化前数性能-优化后性能）/优化后性能×100%表1 向量算术右移指令等价算法性能对比测试从表 1 中的测试结果来看，利用向量指令的等价代换，将串行实现的 4*64 向量算术右移转化成并行实现，减少了冗余向量拆分与拼接操作，性能提升比较明显。3 小结本文从向量右移指令的等价算法和高 64 位乘法替换算法这两个典型实例说明了基础数学库的指令等价替换的性能优化方法。高 64 位乘法等指令是数学函数库函数算法实现过程中必不可少的指令，对于此类指令的软件等价实现具有非常重要的现实意义，此类指令的高效实现有效的解决了因缺少指令致使函数性能降低的问题。算术右移等性能较低的指令是影响函数性能的另一个重要方面。通过 SIMD 整体右移指令和SIMD 逻辑指令来实现 SIMD 算术右移指令功能的等价替换算法，有效地解决了指令性能低的问题，得到了实验验证。下一步可以在此基础上，对指令集中的指令进行全面的分析，确定需要替换的指令，以进一步提高函数性能。同时，可以从理论着手，全面分析验证指令等价替换的可行性。参考文献[1] 张春元，王志英，戴葵. 计算机体系结构[M]. 北京：高等教育出版社，2000.[2] Stallings, W. Reduced instruction set computer architecture[C]. in: Proceedings of the IEEE. New York: IEEE Computer Society, 1988.[3] J. L. Hennessy, D. A. Patterson. Computer Architecture: A Quantitative Approach, third edition[M]. Morgan Kaufmann Publishers, Inc. San Francisco, May 2002.[4] Patterson, D. & Seccombe, S. Complex versus reduced instruction set computers[A]. in: Solid-State Circuits Conference. Digest of Technical Papers[C]. Washington DC:IEEE Computer Society, 1983：218-219.[5] J. Von Zur Gathen, J. Gerhard. Modern Computer Algebra [M].世界图书出版公司, 1999:209-215.[6] 王小非，洪帆，汤学明. 实对称双线性函数与多精度整数的快速乘法[J]. 计算机科学，2007，34(6)：92-97.[7] 张威. 多项式的快速乘法与Toeplitz矩阵[J]. 北华大学学报，2004，5(4)：298-300.一种基于横向-纵向角度的用户偏好挖掘算法（郑州大学信息工程学院，郑州，450052）Mining preference of user from both horizontal perspective and vertical perspectiveFan Baolei, Li Jia, Niu Changyong(School of Information Engineering, Zhengzhou University, Zhengzhou 450052)Abstract：The measurement of similarity between users played a fundamental role in memory-based recommendation algorithms, and influenced the predictive precision directly. This paper proposed a novel method, from both horizontal perspective and vertical perspective, to express preferences of users. This method was able to mine more ratings of extraordinary and made full use of them. From horizontal perspective and vertical perspective, we can get different information about the user preference. The experiments carried on the popular MovieLens dataset by the GroupLens Research group at University of Minnesota showed our method had a better predictive accuracy.Key words：measurement of similarity; mining preference; horizontal perspective; vertical perspective11 引言互联网上海量的信息在带给人们更多选择机会的同时，也使得人们选择自己感兴趣的商品或信息变得更加困难。比如 Amazon 的数百万图书，Netflix 的十多万部电影，淘宝商城的数万亿商品等。推荐算法能够帮助用户走出信息过载的困境，挖掘商品长尾，提高经济效益。推荐算法基于的假设是偏好相似的用户具有相似的选择，因此，选择合适的用户间相似度的度量方法是推荐算法的核心。[1]推荐算法可以分为基于模型和基于存储两类。基于模型的算法不需要存储用户对商品的评分信息，而且模型建好后预测速度比较快，但是模型的建立和更新需要花费较多的时间，不适宜用于评分信息更新比较频繁的任务。与基于模型的算法相比，基于存储的算法需要较大的存储空间和计算量，但能够很好的体现新的评分对预测结果的影响，而且，大量实践表明，基于存储的算法有很好的健壮性，因而得到广泛应用。基于存储的算法需要能够准确的描述用户的真实偏好，准确度量用户间的相似度。常用的用户间相似度的度量方法有：Pearson [2][3]Correlation Coefficient（PCC），vector space model（VS），surprisal-based [4]vector similarity（SVS）等。本文结合PCC和SVS这两种度量方法，提出了CHV（Combine Horizontal-Vertical perspective）相似度度量算法。2 PCC和SVS算法PCC 和 SVS 是两个较常用的相似度度量算法。PCC 从横向角度挖掘用户偏好，充分考虑了用户的评分习惯；SVS从群体角度出发，通过与其他用户的评分进行比较，挖掘用户的偏好。2.1 PCC算法PCC算法根据式（1）计算用户p和用户q的相似度S：p，qr和r分别表示用户p和用户q对商品i的评分。分别表示用户p和p，iq，i用户q所有评分的均值。2.2 SVS算法SVS方法将用户的所有评分信息组织成向量形式，设用户p的评分向量为V，p则其中，Sgn( )为符号函数。I( )表示用户对该商品的喜欢程度。是M个用户对第i个商品评分的平均值。b表示M个用户的评分与的平均偏离量。用户p和q之i间的相似度S，为：p，q3 CHV算法CHV（Combine Horizontal-Vertical perspective）算法结合横向和纵向两个角度挖掘用户的偏好信息，既考虑了用户的个人评分习惯，又兼顾总体信息，且能够挖掘出更多的非平凡评分。3.1 算法思想PCC 从个人角度出发，充分考虑了用户的评分习惯，但忽略了其他用户的态度；SVS 从群体角度出发，通过与其他用户的评分进行比较，挖掘用户的偏好，但忽略了因人而异的用户评分习惯。这两种方法分别从不同角度挖掘用户评分包含的偏好信息。这两种信息在大多数情况下并不矛盾，而且相互补充，因此将这两种信息结合起来能更全面如实地反应用户的偏好。非平凡的评分往往包含用户更多的偏好信息，更能表达用户的偏好。从横向角度分析，用户少数极高（低）的评分为非平凡的评分，表明该用户对这几件（甚至这几类）商品特别喜欢（厌恶）。从纵向角度分析，少数用户对商品极高（低）的评分为非平凡的评分，这样的评分能够将这些用户与其他大多数用户区别出来，反映了用户“与众不同”的偏好。因此，充分挖掘出用户评分中的不平凡评分，对准确描述用户真实偏好很有意义。单用横向方法或纵向方法都有可能丢失不平凡的评分信息。因为有些评分从一个角度看是平凡的，但从另外角度看是非平凡的。我们把用户的评分 r 作为拉普拉斯变量，概率密度函数如式（6）所示。从横向角度来看，评分包含的信息量为 I(r)（见式（7））；从纵向角度来h看，评分包含的信息量为 I(r)（见式（8））。式（9）将横向和纵向得到的信息结v合起来作为该商品包含的用户偏好信息。在结合的过程中可能出现偏好信息冲突的情况，此时，我们无法确定用户对该商品的偏好。3.2 CHV算法描述我们将每个用户的评分组织成向量形式（如式（2）），算法的实现步骤如下：初始化：1．按式（7）横向挖掘每一个评分表达的偏好信息I(r)；h2．按式（8）纵向挖掘每一个评分表达的偏好信息I(r)；v3．按式（9）将I(r)和I(r)结合一起；hv预测：loop：4．将当前用户已知评分信息按步骤1，2，3处理；5．按式（5）计算当前用户与数据库中每个用户的相似度；6．取N个最相似的用户对当前用户的某个未知评分进行预测；end loop；4 实验[6]MovieLens 数据集是明尼苏达大学的公开数据集。这个数据集包含943个用户对1682部电影的100 000个评分信息。电影的评分分 5个等级：1，2，3，4，5。每个用户至少对 20部电影评过分。在实验部分，我们做了多组实验比较我们的方法和PCC及SVS算法的性能。4.1 实验介绍我们从943个用户中随机选取500个用户，然后从这500个用户中选出300（200）个用户作为训练集，对剩余的 200（300）个用户（作为验证集）的评分进行预测。选取验证集中每个用户 5（10， 20 ）个评分作为已知评分，然后对剩余评分进行预测。我们进行了 6 组实验，分别命名为M300Given5，M300Given10，M300Given20，M200Given5，M200Given10。这6组分别代表不同的数据稀疏性。另外一组实验使用除一法[1]（All-but-one），从数据集中各用户的评分中随机选出一个对其进行预测，其余评分都作为已知评分。[7]平均绝对误差（Mean Absolute Error，MAE）是衡量算法预测准确性的最常用方法。MAE的值越小，表示算法的预测准确性越好。计算公式如下：4.2 实验结果在每组实验中，我们在计算某个用户对某个商品的评分时，都取与该用户相似度最高的 35 个相似用户参与预测。3种方法的平均绝对误差（MAE）的对比如表1、表2所示。表1 3种算法的平均绝对误差的比较表2 3种算法的平均绝对误差的比较5 总结CHV（Combine Horizontal-Vertical perspective）算法从横向和纵向两个角度表达用户评分包含的用户偏好信息，能够充分挖掘用户的不平凡评分，更加准确地描述用户的真实偏好，提高用户间相似度的可信度。在MovieLens数据集上的实验结果表明，CHV与PCC和SVS算法相比，有更好的预测准确性。参考文献[1] Breese, J. S., Heckerman, D., & Kadie, C. (1998). Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the fourteenth annual conference on uncertainty in artificial intelligence(pp. 3-52).[2] Resnick, P., Iacovou, N., Suchak, M., Bergstrom, P., & Riedl, J. (1994). Grouplens: an open architecture for collaborative filtering of netnews. InProceedings of the 1994 ACM conference on computer supported cooperative work(pp. 175-186).[3] Soboroff, I., & Nicholas, C. (2000). Collaborative filtering and the generalized vector space model (postersession). InProceedings of the 23rd annual international ACM SIGIR conference on research and developmentin information retrieval (pp. 351-353).[4] H. Luo, C. Niu, R. Shen, and C. Ullrich. A collaborative filtering framework based on both local user similarity and global user similarity. Machine Learning, 72(3):231-245, 2008.[5] Soboroff, I., & Nicholas, C. (2000). Collaborative filtering and the generalized vector space model (postersession). In Proceedings of the 23rd annual international ACM SIGIR conference on research and development in information retrieval (pp. 351-353).[6] http://www.grouplens.org/.[7] Sarwar, B., Karypis, G., Konstan, J., & Reidl, J. (2001). Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th international conference on World Wide Web (pp. 285-295).基于XEN的VCPU调度算法的分析（郑州大学信息工程学院，河南 郑州，450001）1摘 要：在虚拟化环境中，CPU的调度同样重要。本文基于半虚拟化技术XEN，在综合考虑虚拟环境中虚拟CPU调度算法的各种需求的基础上，对XEN中目前使用的基于Credit算法进行详细分析，该算法在处理器密集型应用、多处理器调度、全局均衡管理多个物理 CPU 等方面有明显优势。但是该算法在 I/O 操作、多处理器精确分配方面存在一些不足，本文提出就近原则分配处理器和自旋锁优先的策略来解决这些问题。关键词：XEN；虚拟机；CPU调度；CreditThe Analysis of VCPU Scheduling Algorithm Based on XENZhang Ying, Wang Zhenfei, Li Lun(School of Information Engineering, Zhengzhou University, Zhengzhou, Henan, China, 450001)Abstract：In the virtualized environment, CPU scheduling is equally important.Based on para-virtualization technology XEN, considering the various needs of virtual CPU scheduling algorithm in the vituralized environment, this paper analyzes Credit algorithm in detail which is used by XEN now.The algorithm has obvious advantages in the processor-intensive application, multiprocessing device operation and the global balance of managing multiple physical CPU.But the algorithm has some disadvantage in the I/O operations and the distribution of multi-processor.This paper proposes strategies of processor allocation in proximity principle and spin-locks priority to solve these problems.Key words：XEN; virtual machine; CPU schedule; credit硬件技术的迅速发展和多核处理器的迅速普及，使计算机处理性能不断提高，但是大多数计算机的处理能力并得不到充分的发挥，这个问题在服务器的应用上尤为突出。利用虚拟化技术，在同一企业级的服务器上可以同时运行多个支持不同应用和操作系统的虚拟机，并且使这些虚拟机安全地运行在相互隔离的环境中[1]，能够提高服务器的效率，减少需要管理和维护的服务器数量，降低企业的运营成本。XEN是开源的虚拟化软件，操作系统只需要少量修改就能实现向虚拟平台的[2]移植，避免了大量的开销，并能获得接近物理系统的性能。VCPU 调度算法是指由虚拟机监控器根据一定的策略仲裁当前哪一个VCPU 可以在物理处理器上执行的算法。VCPU的调度决定了运行中的各个虚拟机分配物理CPU 资源的响应时间和轮转时间。虚拟处理器的调度算法经过多年的发展，其性能已经得到了很大的提升，但是还存在很多不足之处。本文通过分析 XEN 中 VCPU 调度算法的实现及不足，提出了算法改进的方向。1 VCPU调度算法的需求CPU 是计算机系统的控制中心，CPU 的调度决定了运行中的各个进程分配 CPU 资源的响应时间和轮转时间。在虚拟化环境中，同一台物理机上同时运行的多台虚拟机，一个虚拟机通常对应一个或多个虚拟CPU（即VCPU），它们共同使用物理机上的一个或多个CPU。虚拟机上的CPU调度是以每一个VCPU作为调度单位分时调度（即决定当前哪一个VCPU可以在真实的物理CPU上运行）。由于VCPU在被调度时必然属于某一个虚拟机，因此在某一特定时刻，虚拟机的调度也就等同于VCPU的调度。在设计VCPU调度算法时，应根据具体应用综合考虑各种情况，从以下5个主要方面说明调度算法的需求：（1）调度的高效性虚拟机技术的最终目标之一就是充分利用物理机处理器资源。为了降低虚拟化带来的性能损耗，使虚拟机性能更接近物理机性能，虚拟机处理器的性能就要尽可能接近物理处理器性能，特别是在多处理器上，如何把多个物理处理器资源分配给多个 VCPU，合理处理算法轮转时间和运行时间片的平衡关系，使每个时间片周期能够处理更多的任务，以提高整个虚拟化环境的运行性能，就是一个很重要的问题。所以要求调度算法要支持连续型的调度。（2）调度的精确性和隔离性虚拟环境中的处理器调度是以 VCPU 为单位进行调度，所以，要求能够精确[3]地对 VCPU 进行调度执行，而且一个CPU的调度执行不能影响其他CPU的调度，即一个VCPU的执行，不能影响其他VCPU的运行性能。这就是虚拟化调度的隔离性。（3）支持抢占性在真实调度过程中，一个VCPU占用物理处理器时，其他VCPU申请CPU资源，如果申请资源的VCPU优先级高于当前VCPU，就需要当前VCPU把处理器资源让给优先级更高的VCPU。另一种方法就是，控制各个VCPU占用物理处理器资源的比例，这样，当优先级更高的VCPU申请处理器资源时，就可以把剩余的处理器资源分配给高优先级VCPU。（4）调度的依赖性XEN 是半虚拟化的代表，只需要少量修改就能实现向虚拟平台的移植，获得接近物理系统的性能。在XEN中，各个非特权级虚拟机Domain U对底层物理资源的调度，主要是依赖特权级虚拟机Domain 0来实现的。Domain U发出底层调用请求，Domain 0会截获这些请求，阻塞Domain U，再向底层发出请求执行Domain U的请求，最终再把执行结果返回给Domain U，实现非特权级虚拟机对底层物力资源的调度执行。（5）多处理器上的负载均衡性目前，多处理器已经得到普及，在多处理器上实现虚拟化，就需要考虑多处理器的负载均衡性，使每个处理器都得到充分利用。以上是 VCPU 调度算法设计时需要考虑的问题。但是，现存的 VCPU 调度算法并不能同时实现以上几点，都有一些不同的不足之处。在进行调度算法改进时，就需要综合以上几点需求，根据实际情况和要求，选择不同的调度算法，以达到公平高效的目标。2 XEN的调度算法分析2.1 3种调度算法介绍随着虚拟化技术的发展，XEN 中使用的调度算法也在不断向更完善的方向发展。XEN 中曾经使用过3种VCPU调度算法：（1）BVT（Borrowed Virtual Time）BVT调度算法是一种公平性优先的调度算法。该算法将时间分为实际时间和虚拟时间：真实时间为硬件计时器记录的时间，虚拟时间为对真实时间经过某种规则计算后得到的时间值。该算法用虚拟时间来监控进程的执行时间，每次总是调度具有最早的有效虚拟时间的 VCPU。这种调度算法考虑到了运行实时的一些 Guest 操作系统，允许这些操作系统在一定范围内将未来分配给它运行的时间片[4]先“借”过来用一段时间。在系统初始化时，每个 VCPU 将分配一个权值来代表该 VCPU 能获得的处理器份额。VCPU根据其权值来实现处理器的公平共享。BVT 调度算法的优点在于：可以将物理时间片公平、均匀地分配给各个 Guest 操作系统，每个Guest操作系统两次被调度的时间间隔不会超过一个真实的时间片。BVT 调度算法的缺点有以下几点。首先，BVT 不支持 non-working-conserving。也就是说，每当当前domain被加载运行时，它将获得整个CPU。用户不能把某个domain对CPU的使用限制在某个比例以下。其次，每个Guest OS只能借用分给它的时间片部分，而不会剥夺其他Guest OS的时间片。（2）SEDF调度算法（simple earliest deadline first）在SEDF调度算法中，XEN中的每个VCPU在初始化时，将由调度算法为该VCPU设定一个截止期限作为其被调度时的参考因素。当进行 VCPU 调度时，调度程序将优先调度截止期限最早的VCPU。SEDF算法为一种动态优先级调度算法。VCPU的优先级随着其绝对截止期限的变化而改变。当处理器进行VCPU调度时，将总是调度具有最早绝对截止期限的VCPU到该处理器上运行。SEDF 算法的优点是：可以通过配置各 Guest 操作系统的配置参数调节它们的优先级。这个算法支持working-conserving和non-working-conserving。SEDF有以下几个主要缺点：一旦VCPU的调度参数被初始化，就不能根据该VCPU的运行状况进行修改。当系统负载极端沉重时，可能使一些进程因错过截止期，来不及处理而夭折。还有一个重要缺点，这种算法只能对单个CPU进行SEDF调度，没有多CPU间负载平衡的控制。（3）Credit算法Credit调度算法是自Xen3.0版本以来使用的默认的调度算法，是一种按比例公平共享的非抢占式调度算法。Credit调度算法为每一个Guest操作系统设置一个credit值，credit值越大，VCPU就越早获得运行。Credit 调度算法的最大优点在于，它可以全局管理多个物理 CPU，从而将 CPU 时间公平高效地分配给各个虚拟CPU。它可以用SMP的方式将各个物理CPU分配给各个虚拟CPU，实现负载平衡。它可以通过调节 Guest 操作系统的参数很好地实现 Non-Working-Conserving（NWC）调度模式，使得管理员可以很容易地控制物理CPU的分配情况。Credit调度算法的缺点在于不能保证实时性。由于全局分配而产生的CPU分配错误率比较高，使得管理更加复杂。2.2 3种调度算法的对比表1 调度算法的对比表1对XEN中使用过的3种调度算法进行了对比。BVT算法能够较好地满足实时性且调度开销较小，SEDF算法能够让I/O 敏感类应用获得更短的延迟响应时间[5]，Credit算法最大的优势在于支持SMP负载均衡，在调度多处理器和QoS控制方面表现更为出色，所以自XEN3.0版本后把它作为默认调度算法。3 Credit的算法实现自XEN3.0以后，Credit的算法就作为默认算法，本节将详细分析该算法的工作流程。3.1 算法调度的对象在虚拟化环境中，处理器的调度单位是 VCPU。一台物理机上同时运行多台虚拟机，每台虚拟机可以有多个 VCPU，所以调度器在执行时，首先要考虑调用哪个虚拟机，再考虑调用该虚拟机上的哪个VCPU。3.2 算法的重要数据结构为了时刻监控每个 VCPU 和每个 Domain 的状态信息，调度算法中分别定义了 csched_vcpu 和csched_dom数据结构，其中包含了VCPU和Domain所包含的一些重要私有信息。这个结构包含了对应的VCPU 的调度队列，还包含了该VCPU 当前的Credit等。试读结束[说明：试读内容隐藏了图片]