【VC++开源代码栏目提醒】:文章导读:在新的一年中,各位网友都进入紧张的学习或是工作阶段。
网学会员整理了VC++开源代码-基于SMP架构的半虚拟化CPU调度算法研究 - 硕士论文的相关内容供大家参考,祝大家在新的一年里工作和学习顺利!
H丫/I/IJl l /IJl4l l fl3/lIH/8H/l lol lf//9/Hl l2/I///1 分类号:—— 密级:—— C:—— U D 编号:—— 工学硕士学位
论文 基于SMP架构的半虚拟化OPU调度算法研究 硕士研究生: 郑兴杰 指导教师: 姚文斌教授 学位级别: 工学硕士 学科、专业: 计算机应用技术 所在单位: 计算机科学与技术学院
论文提交日期: 2009年1月
论文答辩日期: 2009年3月 学位授予单位: 哈尔滨工程大学 摘 要 随着虚拟化技术的高速发展,其已广泛应用到服务器整合、集群计算、多操作系统配置、硬件及内核开发等领域。
调度算法是虚拟化技术中分配处理器资源的重要方法,对虚拟机的磁盘读写速度、网络吞吐量及CPU分配精度等性能有很大影响。
因此,对调度算法研究具有重要理论价值和应用价值。
本文通过对Xen内核源
代码的深入研究,分析了Xen使用的BVT、SEDF、Credit三种调度算法的实现原理;并在SEDF调度算法的基础上,结合Credit算法提出了一种基于SMP架构的动态负载平衡调度算法—|IEDF算法。
该算法能够实时跟踪SMP中当前各处理器的负载情况,动态地将不同VCPU合理分派到负载较小的处理器中;当一个VCPU结束运行时,调度程序将根据VCPU的运行情况动态地调整其下次的运行参数;在VCPU调度过程中,能够在绝对截止期限前完成运行的VCPU将会被优先调度;在一个处理器进入空闲状态前,将考虑其它处理器以从中迁移一个就绪的VCPU到该处理器上运行。
在分析Schedsim模拟器设计原理的基础上,设计并实现了基于SMP架构的SEDF算法和IEDF算法仿真。
并对这两种调度算法进行了性能测试、对比和分析。
测试结果表明,IEDF调度算法性能有较大的提升。
关键词:负载平衡;半虚拟化;对称多处理器;调度算法 哈尔滨工程大学硕士学位
论文 Abstract With the rapid development of virtualization technology,it has been widely applied in the areas of server consolidation,cluster computing,multiple OS configurations,hardware and kernel development,ere.The CPU scheduler iS all important approach to allocate the processors in virtualization technology.The performance of scheduler plays a key role in the rate of disk reading/writing, network throughput,CPU allocation accuracy and SO on.Therefore,the research on the scheduler will have both important theoretical and important applicational value. Based on the thoroughly research of kemel of Xen,this paper analyzes the implementation principle of the existing three schedulers,which are BVT,SEDF and Credit.Combining with the SEDF and Credit schedulers,the paper proposes a scheduler witll the name of IEDF that Can implement the global dynamic loadbalancing on SMP.The scheduler Can dynamically allocate the VCPUs to thelight—loaded processors by Real—Time monitoring the current load of per processor;When a VCPU finishes its nmning,the scheduler Can dynamically adjust VCPUparameters based on its’running status;In the process of VCPU scheduling,theVCPUs those Can be finished before its absolute deadline will take precedenceover other VCPUs;Before a processor goes idle,it will consider other processorsin order to migrate a ready VCPU to the processor. Based on the design of Schedsim scheduling simulator,the paper designs andrealizes IEDF scheduler and SEDF scheduler on SME Roundly performance testsand comparison have been done for the two schedulers.The results manifest thatthe IEDF scheduler Can greatly improve the performance.Key words:load balancing;paravirtualization;SMP;scheduler 哈尔滨工程大学 学位
论文原创性声明 本人郑重声明:本
论文的所有工作,是在导师的指导下,由作者本人独立完成的。
有关观点、方法、数据和文献的引用己在文中指出,并与参考文献相对应。
除文中已注明引用的内容外,本
论文不包含任何其他个人或集体已经公开发表的作品成果。
对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。
本人完全意识到本声明的法律结果由本人承担。
口 作者(签字):尕帛彬 日期: k罚年3月r日 ‘ 。
l 哈尔滨工程大学 学位
论文授权使用声明 本人完全了解学校保护知识产权的有关规定,即研究生在校攻读学位期间
论文工作的知识产权属于哈尔滨工程大学。
哈尔滨工程大学有权保留并向国家有关部门或机构送交
论文的复印件。
本人允许哈尔滨工程大学将
论文的部分或全部内容编入有关数据库进行检索,可采用影印、缩印或扫描等复制手段保存和汇编本学位
论文,可以公布
论文的全部内容。
同时本人保证
毕业后结合学位
论文研究课题再撰写的
论文一律注明作者第一署名单位为哈尔滨工程大学。
涉密学位
论文待解密后适用本声明。
本
论文(口在授予学位后即可口在授予学位12个月后口解密后)由哈尔滨工程大学送交有关部门进行保存、汇编等。
L一7 r’ \’ 作者(签字):翱彬侈 ^ I , 导师(签字):盔以氇形入 ^ 日期: 砂即年;胁日凇硝年;月厂日 / l 哈尔滨工程大学硕士学位
论文 第1章绪论1.1课题研究的目标和意义 随着信息技术的高速发展,计算机系统规模不断扩展、处理能力快速提高、资源种类日益丰富、应用需求更加灵活多样。
但是,计算机系统资源管理工具一操作系统发展却相对滞后。
当前,操作系统将各种应用综合到一台计算机上仍面临两大问题:一是无法解决应用程序间的干扰或冲突问题;二是不能满足用户独立拥有系统环境的需求的问题。
因此,许多计算机用户不得不通过增加计算机的数量来满足不同的应用需求。
与此同时,当前针对这些应用的计算机的平均利用率却不到30%,导致计算机资源大量过剩。
由此产生了
计算机硬件性能快速提高带来的资源相对过剩与用户渴望隔离环境并能共享系统资源的大量需求之间的矛盾〔11。
虚拟化技术正是解决这一矛盾的主要方法之一。
该技术通过软件模拟的方式在某种类型的计算机(或其它硬件平台)及操作系统(或其它相应的软件操作平台)的基础上,实现对另外一种计算机(或其它硬件平台)及操作系统(或相应的
软件平台)的模拟。
当前,虚拟化技术已广泛应用到服务器整合〔2-3〕、集群计算眇】、资源动态迁移〔10113〕、计算机安全114q5)、多操作系统配置、硬件及操作系统内核开发等领域h7-1sl。
2006年初发布的《国家中长期科学与技术发展规划纲要》将计算系统虚拟化的核心机理作为支撑信息技术发展的五大重要科学基础之一,以及信息技术领域的优先主题。
2008年,研究顾问咨询公司Gartner在其《2009年IT行业十大战略技术》
报告中将虚拟化技术列为2009年IT行业十大战略技术之首。
可以预见,虚拟化技术是计算机技术发展的一种必然趋势,它将给信息产业带来极大的变革。
作为虚拟化技术的一个重要分支一半虚拟化技术(Paravirtualization,或称为部分虚拟化、准虚拟化、泛虚拟化)通过消除硬件特性和特权指令极大的简化了虚拟化过程。
与其它类型虚拟化技术相比,该技术提供了最小的性能损失【19】。
但是,半虚拟化技术环境的复杂性也为资源管理带了更大的挑战。
在 哈尔滨工程大学硕士学位
论文 半虚拟化系统环境中,系统工作量更大;系统中每个虚拟机只能占用有限的 资源并且其对资源的要求随着商业需求改变而不断的变化;同时,虚拟机在 保证拥有良好性能的前提下还需实现虚拟机间应用错误、性能和资源的完全 隔离【20】。
目前,对半虚拟化技术中的资源管理还没有有效的方法,严重依赖于虚 拟机下层资源分配机制的特性。
如何合理、有效地分配系统资源仍是该技术 中一个很大的难题116-201。
其中,半虚拟化技术的CPU调度算法对保证虚拟机 间公平共享处理器资源和提高系统的整体性能起着至关重要的作用。
在对半虚拟化技术的研究中,由于其CPU调度算法对系统的网络吞吐量、磁盘读写速度及CPU分配精度有很大的影响;调度算法的算法特性及运行情况直接影响到计算机系统的性能和安全;从而,逐渐成为半虚拟化技术的热点研究领域之一。
开展对半虚拟化技术中CPU调度算法的研究,进一步研究及设计调度算法在对称多处理器(SMP:Symmetric Multi.Processor)上性能优化策略和相关支持技术,对加速我国半虚拟化技术的发展和拥用自主知识产权的信息产业的发展,保障国家信息安全,具有重要的学术、
经济和社会意义。
1.2国内外研究现状 当前,半虚拟化技术应用的典型例子是Denali和Xen虚拟机管理器(VMM:Virtual Machine Monitor)。
其中,Denali由华盛顿大学的Denali项目组开发,该VMM提供了一种轻量级虚拟机的实现方式。
但是,由于Denali不支持在单个操作系统中实现多路复用、多址空间及存储管理中的虚拟层的功能,导致在其上运行的每个虚拟机只能运行一些单用户单进程的操作系统。
从而,使得Denali的应用受到很大的限制。
而Xen虚拟机管理器由于其
开源及具有良好的性能而受到广大用户的欢迎〔211。
现有的调度算法按进程(或其它调度的基本单位)能否在处理器空闲时获得额外处理器份额可分为工作保养模式(we--mode:Work.Conserving)和非
工作保养模式(NWC-mode:NonWork—Conserving)。
其中,算法运行在工作保养模式时,进程(或其它调度的基本单位)能够获得除系统分配的处理器份额外的额外份额;而运行在非工作保养模式时则不能。
在Xen中,虚拟CPU(VCPU:Virtual CPU)类似于操作 2 哈尔滨工程大学硕士学位
论文 系统中的进程,各虚拟机以VCPU为调度的基本单位。
其使用了以下三种调 度算法来实现对VCPU的调度: 1、BVT(Borrowed Virtual Time)算法 BVT算法是由Kenneth J。
Duda在1999年提出,该算法将虚拟时间思想 引入进程调度当中,将时间分为真实时间和虚拟时间。
其中,真实时间为硬件计时器显示的时间值;虚拟时间为对实际时间经过某种规则计算后得到的 时间值。
该算法用虚拟时间来监控进程的执行,每次总是调度具有最早的有效虚拟时I’百J(EVT:Effective Virtual Time)的进程〔221。
当前, BVT算法存在在 多处理器上运行时不能保证进程公平共享处理器资源的问题。
AbhishekChandra针对此
问题提出了一种应用在多处理器上的SFC(Surplus FairScheduling)调度算法【23】,该算法能够实时地调整每个进程的权重(或称weight) 以使处于“饥饿”状态的进程尽快运行;Tracy Kimbrel针对BVT算法中进程在多处理器上因频繁迁移而导致性能急剧下降的问题,提出了一种减少在对称多处理器中进程迁移次数的算法洲; 此外,Sriram Govindan专门针对BVT算法在Xen虚拟机管理器中对应用通信无法感知的缺陷,将虚拟机下层的I/O行为加进VCPU调度决策制定中,提出了一种具有
通信感知能力的调度算法【25】。
2、Credit算法 Credit调度算法是EIXen3.0版本以来使用的缺省的调度算法,其为一种按比例公平共享的非抢占式调度算法。
每个VCPU都用一个Credit值设定其优先级。
当creidt为负值时,其优先级为over;否则,优先级为under。
每个处理器都在本地维护着一个就绪VCPU队列,该队列以VCPU的优先级由高到低排序。
系统每次调度处于队首且优先级为under的VCPU运行。
当一个处理器空闲时或该处理器的就绪VCPU队列中无under优先级的VCPU时,它将查看其它处理器以找到一个可运行的VCPU至IJ本处理器上运行。
目前,对Credit算法的研究主要集中在该算法对系统性能影响方面。
其中,Ludmila CherkasovaYc寸该算法在Xen虚拟机管理器中上应用时的磁盘读写速度,网络吞吐量和CPU分配精度的影响进行了分析〔26-271:Diego Ongaro分析TCredit算法对Xen上虚拟机I/O性能的影响【2川。
3 哈尔滨工程大学硕士学位
论文 3、SEDF(Simple Eariest Deadline First)算法 SEDF算法源于c.L.Liu在1973年提出的最早截止期限(EDF:EarliestDeadline First)调度算法【29】。
Xen中的每个VCPU在初始化时,将由调度算法 为该VCPU设定一个截止期限作为其被调度时的参考因素。
当进行VCPU调度 时,调度程序将优先调度截止期限最早的VCPU。
与Credit算法一样,当前对SEDF算法的研究还仅限于对配置有该算法的Xen的性能(磁盘读写速度、
网络吞吐量、CPU分配精度、I/O性能)影响进行了分析〔26-28〕。
在国内,由浙江大学何钦铭教授主导的“计算系统虚拟化基础理论与方法研究”项目(973计划)子课题《虚拟计算
系统评测理论与方法研究》中已经展开了在服务整合情况下,对虚拟机管理器所用的调度算法对网络性能影响的研究。
通过评估不同调度算法在不同网络负载时的性能,在公平共享CPU资源的前提下提高了网络带宽分配的公平性,但尚无对以上三种调度算法的改进措施。
综上,半虚拟化中CPU调度算法正朝着能支持SMP架构的多处理器间负载平衡;能同时支持工作保养模式和非工作保养模式及具备很高的CPU分配精度的方向发展。
由于半虚拟化技术中CPU调度的特殊性,以上算法虽有所改进,但仍面临着以下问题: ‘ 1)BVT算法:不支持非工作保养型模式,且VCPU的调度参数配置非常困难; 2)SEDF算法:不支持VCPU的在SMP上处理器间的负载平衡;当系统过载时,其吞吐量将会急剧下降;此外,VCPU的调度参数(周期、最坏执行时间)在初始化后不能根据该VCPU的运行情况动态调整; 3)Credit算法: 全局负载平衡策略过于简单,仍易导致处理器因进程未就绪而空闲的情况;此外,该算法还不能保证紧急VCPU的实时性。
1.3研究内容 本文在深入分析Xen内核源
代码的基础上,针对Xen中SEDF及Credit调度算法当前存在的问题,提出了一种基于SMP架构的半虚拟化CPU调度算法,即IEDF(Imporved Eariest Deadline First)算法。
该算法能够在进行VCPU 4 哈尔滨工程大学硕士学位
论文分派时就能综合考虑SMP中各处理器的负载情况及Cache的命中率,将新创建的VCPU分配到其上次运行或负载较轻的处理器中;在VCPU调度时,能够兼顾其绝对截止期限及完成率;当系统某个处理器空闲时,其将从其它处理器的就绪VCPU队列迁移一个最紧急的VCPU到当前处理器上运行。
此外,该算法根据VCPU运行情况动态的调整其运行参数。
在现有Schedsim调度模拟器的基础上,本文
设计并实现了SEDF和IEDF算法的调度模拟器;并对IEDF算法及SEDF算法进行了模拟实验,将实验结果进行了对比、分析。
实验结果表明IEDF算法相对SEDF算法的性能有较大的提升。
1.4
论文组织结构
论文分四章,文章其余部分内容按如下方式组织: 第二章相关背景技术 阐述了半虚拟化技术及Xen的系统模型;介绍了SMP的结构特征及Xen对SMP的支持;通过对Xen内核源
代码的深入分析,总结了Xen中BVT、Credit和SEDF三种调度算法的实现原理;并分析了三种算法存在的缺陷。
第三章基于SMP负载平衡调度算法设计 进行了SMP调度算法的需求分析;针对当前Xen中SEDF及Credit调度算法存在的缺陷,设计了一种基于SMP负载平衡调度算法。
该算法包括VCPU参数的动态调整模块、进程分派模块、进程调度模块及负载平衡模块。
第四章算法模拟与实验 在schedsim调度模拟器基础上,设计并模拟实现了IEDF算法和SEDF算法; 配置了SEDF算法及IEDF算法调度模拟器的运行环境;分别以10个、20个、40个和60个进程为例模拟实现了SEDF、IEDF两种算法的调度过程;对此两种算法进行了性能测试、对比及分析;并做了客观的性能评价。
5 哈尔滨工程大学硕士学位
论文 第2章相关背景技术 2.1半虚拟化技术 虚拟化技术通过对计算机系统结构相关层中资源的模拟,实现对该层中资源的划分,并将这些资源透明、公平的映射到其上层的虚拟机中。
在虚拟机运行时,利用虚拟机管理器实时监控虚拟机对其下层资源的调度;检测调度的合法性;并按照相应的资源分配算法分配这些资源,保证对虚拟机下层资源和特权指令的绝对控制【21】f30】。
现有的虚拟化技术与计算机体系结构的层次对应关系如图2.1所示: 虚拟化技术分类 计算机系统结构层次 应用语言级机器M5 (应用语言) 高级语言级机器M4 (高级语言) 汇编语言级机器M3 (汇编语言) 操作系统机器M2 (
作业控制语言系统) 硬件级虚拟化 传统机器MI (半虚拟化、全虚拟化) (机器指令系统) 微
程序级机器MO 指令级虚拟化 (微指令系统) 图2.1虚拟化技术分类与计算机系统结构层次对应关系图 现有的虚拟化技术可分类为应用程序级虚拟化、操作系统级虚拟化、硬件级虚拟化和指令级虚拟化【311。
其中,硬件级虚拟化技术又可分为半虚拟化技术和全虚拟化技术。
全虚拟化技术实现了对真实硬件中各部分完全的软件模拟。
该技术的优点在于不需要修改虚拟机中运行的操作系统的内核,兼容 6 哈尔滨工程大学硕十学位
论文性较好。
但采用这种技术系统运行开销较大。
半虚拟化技术通过对系统中缺陷指令的替换,避免了全虚拟化技术中如” “动态指令重写”这种开销较大的方法,性能得到了很大提升。
与全虚拟化不同,使用半虚拟化技术的虚拟机能够感知其底层硬件的存在。
现有的虚拟机管理器软件Denali和Xen已经实现了x86平台上的半虚拟化,并且在其上运行的虚拟机具有比全虚拟化技术更高的性能。
随着支持Intel—VT和AMD—V技术处理器的诞生,已经实现了虚拟机中的操作系统不经修改就可在采用半虚拟化技术的虚拟机管理器上直接运行,从而使半虚拟化技术能同时支持半虚拟化和全虚拟化两种技术中的虚拟机管理器【32】【35】。
2.2 Xen系统模型 Xen是在2002年由英国剑桥大学Ian Pratt发起研制的一种基于半虚拟化技术的
开源虚拟机管理器(或称Xen Hypervisor)。
其能够支持包括Windows、Linux、Solaris及各种版本的BSD操作系统,及多达100多个操作系统同时运行〔331。
其系统模型如图2.2所示: 图2.2Xen的系统模型 7 哈尔滨-T程大学硕士学位
论文 Xen系统模型中最下层为物理硬件层(cPu、物理内存、网卡、块设备);最上层为虚拟机层;Xen通过在物理硬件层上添加了一个虚拟机管理器层实现了对物理硬件层的模拟,并向管理器层上的虚拟机层提供了硬件抽象。
在虚拟机层中,Domain表示一个运行的虚拟机执行的上下文;客户操作系统(Guest OS:Guest Operating System)表示在Domain中运行的操作系统。
每个Domain在创建时,系统将会为其分配一个ID号。
其中,DoaminO在系统启动时创建,其能够利用虚拟机管理器层的Domain0控制接口对其它Domain进行一些应用级的管理控制,具体包括:其它Dommn的创建、终止;调度参数的配置;CPU、物理内存、网卡、块设备的访问及虚拟设备控制和管理。
系统中的各Domain间通过事件通道进行通信。
Xen将设备驱动程序分为前端和后端两部分:前端负责收集、封装用户请求,并将请求通过事件通道转发给后端;后端.