1006大设计翻译版嵌入式hypervisor内存管理的调度策略

Author:XuLi-binTutor:BaiYue-Withthepromotionofperformanceabilityofcomputer,andthedevelopmentofvirtualization,embeddedvirtualizationisgrowingrapidly.Embeddeddeviceshavebeencommonlyassociatedwithinsufficientmemoryresourcebecauseseveraloperatingsystemsrunatthesametimeinanembeddedsystem,andsomeoperatingsystemsneedtosupportafewapplications.Therefore,itisimportanttomanagethememorydynamically.Totheissuesabove,inthisthesiswestudyandimplementamemory-schedulingstrategy,testandverifyitonOKL4architecture.Themaincontributionsofthisthesisareasfollows:ThemechanismofmemorymanagementinOKL4wasstudied,andbyusingthe“white-box”methodvirtualmachinemonitoringmodulewasdesignedandimplemented.Consequently,itcanmonitorthememoryusedbyvirtualmachineinrealtimeandpreciselyestimatetheneedofmemoryinthenexttime.Bycombiningclassicalfeedbackcontrolsystem,thelocalschedulingalgorithmwasdesignedandimplemented.Thealgorithmusesfeedbacksystemtorestraindisturbanceandeliminatedeviation,whichmakesthememoryusageratethevirtualmachineoccupiesinacertainlevel,thusguaranteeinggoodperformance.BycombiningtheknowledgeofGameTheoryandusingNashEquilibriumStrategy,globalschedulingalgorithmwasdesignedandimplemented.Induetime,itwillredistributememoryresourcebasedonweightandeagernessforresources,whichmakessurethatmemoryisusedbyneed.Intheend,aftercarryingoutexperiments,weconcludedthatthealgorithmsare：embededvirtualization,virtualmachinemonitor,feedback 绪 研究背 国内外研究现 内存资源的动态分配策 基于虚拟化的内存管理技术的研究目标与内 课题来 的组织结 相关技术现 CPU虚拟化与内存虚拟 三种CPU虚拟化技 内存虚拟化技 虚拟机程序 OKL4系 OKL4系统简 Hypercell技 iguana操作系统服务 本章小 程序设 选择合适的方 内存信息的量化描 粗粒度内存信息 细粒度内存信息 程序的实 本章小 基于控制论的局部调度策略设 反馈控制系 反馈控制系统原 两种反馈控制系 基于控制理论的局部调度策略的设 局部调度策略的设计依 增量的量化处 局部调度算 本章小 基于博弈论的全局调度策略设 博弈论简 相关的重要概 问题描述与解决策 全局调度算 本章小 系统实 实验环 测试工 LMbench的主要特 主要技术参数说 功能实 实验目 实验过 本章小 总结与展 工作总 工作展 致 参考文 附录相关 绪上可以同时运行多个操作系统，并且为应用程序的运行提供了相互的运行环境，显叫做虚拟机器（VMM,VirtualMachineMonitor，取代了以往的操作系统而直接在机上运行（针对Ⅰ型虚拟机程序情况。虚拟机程序创建一个底层硬件平台抽象，这样，一个或多个虚拟机（VM）无需知道它们共享平台即可使用这个底层硬件ii术满足hypervisor系统对客户操作系统的支持。1.1VMware和KVM都已经或计划推出嵌入式平台的虚拟机。基于关键数据的内存资源自治调度：由Oracle公司的相关小组在Xen上提出[3]，Xentarget基于应用反馈的内存资源动态分配：由VMware公司的员工和大学的一些研究学者一种在服务整合环境中内存资源动态控制的机制[4]。其具体实现主要由此时运行在虚拟机里的多个应用程序开始工作，并将它们的运行性能数据通过插入基于建模评估的内存资源动态分配：由IBM研究团队提出，具体实现名为.2基于虚拟化的内存管理技术的这是因为，在引入hypervisor之后，传统的操作系统不再直接作用在物理内存资源上，于是物理内存资源变成了由现在的hypervisor来管理。但是应用程序对内存资源的使用化域了系，分hprvior均采取在虚拟机运行前便动态内存管理技术成为关注的热点，并提出了气球驱动和内存热插拔等相关管理技术。气球驱动[6]由wre增倾定hprvior当中。利用效率，如图3.1.1所示。其中，内存信息部分负责收集系统及各个虚拟机中与1.2（即某些虚拟机的空闲内存以供内存紧缺的虚拟机使用。在这里，我们引入了反馈调节，根据当前内存利用率和期题第二章主要介绍了在设计相应内存资源器和调度器时要使用到的相关 及实现了程序的算法。相关技术现ARM处理器主机上运行为仿真，因此速度会减慢100倍甚至1000倍。2.1hypervisor在客户操作系统和底层硬件之间进行协调。引hypervisor后，底层硬件并不由操作系统所拥有，而是在hypervisor的管理下由多个操作系统共享，并且，特定受保护的指令必须获下来并在hypervisor中进行处理。题，比如需要VMM处理的一些特定敏感指令并没有获。因此，hypervisor必须要动态扫描并捕获这些模式代码来解决这一问题。2.2拟化技术的一个缺点，但是提供了与虚拟化的系统接近的性能。2.3除了CPU虚拟化，另外一个重要的虚拟化就是内存虚拟化。虚拟机的内存虚拟化现在所有的x86CPU都包含内存管理单元MMU（MemoryManagementUnit）和TLB(TranslationLookasideBuffer)MMUTLB来优化虚拟内存的性能。内存物理地址的映射，但是客户操作系统不能直接实际机器内存。VMM负责映射拟内存到物理内存的映射表，VMM也会更新页表来启动直接查询。另外，VMM使用TLB硬件来映射虚拟内存直接到机器内存，从而避免了每次进行两次翻译。2.4虚拟机监视器（VMM），又称hypervisor，它作为一款轻量级软件，向上层的虚拟机等价性VMM下的程序，其行为应与直接运行于等价物理机上的相同程序的行效率性在引入VMM之后，GuestOS通过VMM实际的物理硬件。VMM运行在运行。同时VMM也为每个虚拟机虚拟出一套与真实硬件无关的虚拟硬件环境。作系统必须通过VMM来物理硬件，在性能上的损失较大。该模式的VMM的位置如图所示。2.5宿主模式的VMM独立模式（Stand-AloneHypervisor独立模式下，VMM直接运行于硬件之上，有最高的级别，可直接使用硬GuestOSVMMVMM的位置如图图2.6独立模式的VMM示意混合模式（Hybrid混合模式结构上与独立模式近似，VMM在最高级别上运行，是直接在物理硬件上运行的，虚拟机则是运行在VMM之上的。与其他模式相比，这个模式里的2.7混合模式的VMM统环境的VMM设计。针对嵌入式系统，VMM的设计应该考虑到嵌入式系特的隔码性能以及有效地满足实时性变得，也导致了整体性能降低。在InVT系统中，需要运行没有分页的客体(guest)，减少客体(guest)之间的。在通用环境中，这是不可接受的，但是在一些嵌入式环境中，可能是优先选择的。第二个，I／0性能对于一个嵌入式系统的成功与否可能至导致一些VMM厂家允VM直接进行内存(DMA)。这样提高了性能，但是也允许应用或设备驱动读写系统上的特定的核和特定的内存区域往往被VMM的设计者采用，这样做可以减少操作系统中的动态调度和动态内存管理。针对调度策略和内存管理策略，嵌入式系统在VMM的设计核之间的调度得以简化。其次，在内存管理的设计方面，地针对可配置性而不是动态分配。VMM设计者会预先规划分配给每个虚拟机的内存区域，这样简化了内存管理程或线程占用指定处理器的时间。传Windowslinux操作系统采用的是基于优先级没有任务能另一任务的进程。在虚拟化环境中支持实时任务是一个，因为VMMRTOS中运行单个任务，也不知道它们的优先级。解决方案是在处理器核上RTOS，或者只允许RTOS与GPOS共个核并且给RTOS严格的，高于GPOS的优先级。的研究平台是OKL4。2006年，OpenKernelLabs(OKLabs)创立，致力于为嵌入式系统开发微核和虚拟机程序。OKL4是一个基于微内核技术的软件平台，它支持系（TCB系统中使用轻量级保护单元进行错误。它可以作为全功能或单独功能的操作系统。OKL4可以提供用于移动设备，消费者电子，工厂自动化，医疗电子以及电子/数据通信基础设施的系统的虚拟化[10]。OKL4是建立在L4的微内核之上，并且基于PistachioOKL4构架的体系结构，它实现了名为安全单元的分区，一个具有虚拟化microvisor，以及高效的进程间通信。OKLabs提供了对几个半虚拟化的操作系统的支持，这些操作系统包括：OK:Linux、OK:Android和OK:Symbian。图 其中，OKLinuxLinuxOKL4上运行客户操作系统。虚拟化系统有两种技术类型：完全虚拟化（hypervisor负责捕获序接口hypercall来替换所有的指令，以修改客户操作系统。OKL4使用的就是半虚拟机体系结构了客户操作系统的错HypercellOKLabs使用的体系结构叫做安全的超细胞技术，它为开发和配置可信的嵌入式系统提供了环境。图所示的OKL4系统拥有不同的分区（细胞，它们之间相互隔离，每个细胞可能包含任何的系统组件，或者一个完整的操作系统环境（虚拟机，操式下的代码，用来提供虚拟化，分区，IPC机制等服务。由于系统的其他部分都不可以以模式，因此系统的完整性可以避免任意细胞里代码的破坏。系统组件在代码和代码。权限（capability）用来子系统对资源的。iguana OKL4 OKL4iguanaOKL4的OKL4CPOSIXPSE51用于内核原OKL4OKL4OKL4编译工具,IDL(magpie),系统配置工具其中，Iguana是一个小型的操作系统，专门为实现安全和可靠的嵌入式系统开发，它运行L4微内核上，支linux的运行，并将其作为一个应用程序。Iguana提供一系列用OKL4原语的方便的方法。Threads线程：执行和调度的基本单元。IguanaL4L4的原语以及iguana定义的原语调用。Protections保护域：为不同程序的线程提供内存保护，大体上相当于任务或linux中的进程不同，所有的保护域都共享相同的虚拟地址空间。如图所示。Memorysections内存片：虚拟内存分配和保护的单元。一个内存片是一组连续的虚pages线程可以共享对内存片的。2.10Memorypools内存池：iguana允许物理内存和虚拟内存组织成的内存池。每个一旦被建立，它将被用来创建physmem对象。如下图所示：Physmem物理内存：描述了一串连续范围的物理内存页面（physicalpages，通过mapmemorysectionsphysmempoolphysicalA，分别是默认物理内存池和用户定义的内存池。它们分配了两个physmem，并映射到两个memsection。2.1CPU虚拟化技术以及内存虚拟化的技术。2.2节介绍并分因素。2.3OKL4的具体情况，以及其专门为嵌入式开发的操作系统iguana的相关接口API。3程序设步导致了对虚拟机的内存资源的使用情况进行实时变得很，并且要准确预估虚情况[12]。相比之下，“白盒”方式的优点是能够及时获得虚拟机的运行信息，对内存需求的评估更加准确。缺点是对虚拟机操作系统的“”较大，有的需要修改虚拟机OKL4系统，OKL4iguana服务iguana上对各个虚拟机进行实时，这样不仅能够对直接，及时的获得虚拟机的同时，修改iguana操作系统造成对其的“”较大，有可能影响其运行。本文中 3.1commitlinuxwindows等，程序对内存变得可用而做的一个到实际物理的一个映射[13]UsedfreeC，表示当前分配给虚拟机的可用物理内存大小，两者它通过改变自身占用物理内存的大小改变虚拟机当前可用内存大小C（注意，虚拟机可3.2表 参数进行预测。由于界限值的存在，必须对CiHiLi之间，如果超出范围则取边界值，这样得到的值便是MCi。者的基础上，便可以对整个系统所需的内存值进行评估。Ni为当前分配给某虚拟机的内存值，于是(MCiNi便是所有虚拟机（即整个系统）未来（下一时刻）Fh(MCiNi，说明物理机上的空闲内存可以满足所有虚拟机对内存的需Fh(MCiNi，说明物理机上的空闲内存已经所有虚拟机对内存程序3.1pd_pm_size{uintptr_tpaddr,psize;TAILQ_FOREACH_SAFE(pm,&ms->pm_list,pm_list,}return}TAILQ_FOREACH_SAFE是宏定义，用来安全的遍历所指定的双向链表；physmem_infoiguanaAPI，psize是传出参程序 Staticstructpd*pds[20];//thesetofalliguanaStaticintcount;//thenumberoftheset{structpd_nodefor(ppd=pd->pds.first;ppd->next!=pd->pdsfirst;ppd=ppd-{pds[count++]=ppd;}return}静态数据区的变量pds和count，用来记录所有保护域的指针和数目。程序3.3iguana_pm_size{return}为iguana里的保护域才是嵌入式系统中的虚拟机。本章主要介绍了虚拟机内存器的设计思路过程。首先分析讨论了虚拟机内存的两种状态；最后给出了程序的具体实现。基于控制论的局部调度策略4.1负反馈（negative正反馈（positivefeedback在本次设计的控制系统中，根据内存期望的利用率rdes与当前内存的利用率r之间的利用率rdes回归。IO密集型应用往往都对运行环境中的空闲物理内存具有严换空间不停地调页造能下降。基于此，在对内存利用率进行过程中，我们引入了控制理论中的反馈调节，根合理的范围之内。如图所示，有两个基本参数：输入参数：期望的内存利用率ΔU，则下一时刻内存的估计值就为：UnewUold4.2综合以上两点考虑，我们给出如下的增量控制公式(r2r2Uoldr

r dU

r

Uoldr

rd4.1当r小于des时，系统资源的内存调节的增量是负的，说明此时是负反馈，应该减少r大于rdes当内存利用率r大于系统期望内存利用率rdes时，系统资源处于短缺状态。因此增应该较大，所以调整参数1与公式的其他部分是乘法的关系（前提是1与2均为大11020之间；当内存利用率r源造成的性能下降，释放资源的力度增量应该较小，于是调整参数2与公式的其对于控制参数1和2即调整的粒度（或幅度。具体的值在后续的实验中进行试探与调整算法输入参数： rde 输出参数：获取内存利用率r，前内存值WhileIfIfrrdes设置U的值为Uoldrr

(r2r2设置U的值为Uoldr rdes

设置目标调节内存值TargetMemMin(max(lower_bound,U由气球驱动根据TargetMem本章介绍了局部调度算法的实现。其中，4.1基于博弈论的全局调度策略5.1 本章介绍的全局调度借鉴了博弈论的相关知识，利用均衡原理对所讨论的问题theory1944年冯与合著《博弈论与经济行为》，标志着现代系统博20世纪经济学最伟大的成果之一。目前在生物学、经济学、国际G：输赢的（游戏，，比赛，竞争）格局。博弈的三要素参与者：博弈的决策主体，通常又称为参与人或局中人，一般记为参与者,,n行动与：行动时博弈参与者i在决策时可供选择的动作，一般记为ai。全不行动的参与者所选择的行动做出对应的行动安排，一般用si表示。用Si表示空间，即Si{si}。此，静态博弈中si和行动ai是相同的。身行动时就应该做出针对性的反应。因此，动态博弈中参与者i的si就与他所掌的信息以及他可供选择的行动ai相关收益：在一个特定的组合(s1,s2,,sn)下参与者i得到的效用（常表现为博弈中参i的输赢，得失，盈亏i的收益通常记为ui(s1s2sn，简记为ui。由于参与者i的效益ui(s1,s2,,sn)是随着组合(s1,s2,.,sn)的不同而改变，因此收S1,S2Sn，各个参与者的收益函数分别为u1(s1,s2sn)u2(s1,s2sn)，..un(s1,s2,,sn)。那么，博弈G的式表述记GS1S2Snu1,u2,.un}均衡：一个博弈的所有参与者的 的组合，一般记为r*(r*,r*,...,r*,.,r*)。 i相互影响的决策，或者说是互动决策，因此，最优r*通常依赖于其他参与者的ii 均衡：在n个参与者的式表述博弈G={S1,S2,...,Sn；u1,u2,...un}中，如果对于每一个参与者i，他选择的s*是针对其他n-1个参与者所选组合is* s*,...,s*的最优反应，即s* i1 maxu(sS*)maxu s*,...,s*，i=1,2,...,n i1 那么，组合s*(s*,...,s*)称为博弈G的均衡[17] 这里均衡定义揭示了每一个参与者的最优选择的均衡s*

都在追求自身收益u i1 如果空间Si是连续空间，定义中最优化问题的求解，利用微积分求极值的方法u(s,s*,...,s*1 n

u(s*,s,s*,...,s*2 n

u(s*,s*,...,s*,s*n n

个参与者所选组合(s*,...,s*,s*,...,s*)的最优选择应满足的关系其余方程含义类同 i1 均衡，从而构成博弈的结果均衡s*(s*,...,s* 均衡虽然给出了博弈参与者一致的对博弈的结果的预测，但并不表示均衡一结果最可能出现，往往涉及到文化，心理和经验等方面的知识和信息。依据上述原理以及相关概念，我们针对系统具体的问题进行建模，然后利用均 riiNri[0,1]来代表虚iRmiri，其中m 销。假设用P表示系统性能，则P是系统内存利用率R的函数PP(R)P 现在，我们用均衡的静态博弈方法来解决该问题[18]。为了将该问题转化为决ui(Pc)ri(PaR)ricri 其中，c以下我们只要求得一个策略组合(r*,r*,...,r*,...,r*)，其中r*[0,1]是虚拟机i 他n-1个虚拟机的策略s*,s*,...,s*,...,s*的最佳对策，那么便求得均衡， u(r*,r*,...,r*,...,r*)u(r*,r*,...,r*,r*,r*,...,r*) i i1 ir*[0,1]，i i为了求得(r*,r*,...,r*,...,r*)，须解决以下的最优化问 为了简化计算，我们假设分配给各个虚拟机的物理内存mi是相同的，即mim，Rmiri mrbr，其中bm (3.4.4)Pcabrj2abri0 jN因此求得r

Pc

jN\{i} 2ab

Pc

r*Pc iab(ni在这个均衡的情况下，性能则P*Pabnr*P n在这 u*(P*c)r*M(P

(

am(n算法输入参数 (r1r2,...,ri,...,rn 设置r*的值Pab(nWhileIfForiN设置内存利用率增量的值为rr 设置TargetMem的值为m*

由气球驱动根据TargetMem

本章介绍了全局调度算法的实现。5.1节介绍了博弈论和均衡的相关原理。5.2节对实际问题进行了分析建模，并总体概述了全局调度算法的设计思路。5.3介绍了系系统实前三章分别介绍了虚拟机程序，基于控制理论的局部调度，基于博弈论的全局验，实施实验并分析，验证本系统的可用性。 (R)Core(TM)2Quad OKL4合ANSI/C标准为UNIX/POSIX而制定的微型工具，一般来说，它衡量两个关键LMbenchTLB表的未命中延迟。另外，缓存的大小可以被正确划分成一些结果集并新的工lmbench的参数有很多，包括系统基本的参数，处理器与进程的操作时间，基表 lmbench技术参数参数具体参数详BasicsystemTlbTLB（TranslationBuffer）的页面Cachelinecache的行字节数MemoryparallelismScal并行的lmbenchProcessor,Null简单系统调用（取进程号Null简单IO操作（空读写的平均取文档状态的操Open打开然后立即关闭关闭文档操Sig捕获File&VMsystemFileCreate&创建并删除文档MMap内存映Page缺100fd对100个文档描述符配置selectLocalCommunication管道操File文档重复MMap内存映射重复读Mem内存Mem内存内存拷内存拷MemoryMain连续内Rand内存随机延程序staticpage_alloc(int{intphysmem_ref_t }}该函数有一个参数n_pages，表示要分配的页面个数，这个参数用来控制虚拟机占用内存的大小。具体算法中，我们在指定的保护域other_pd_cap[0].ref.pd中分配n_pages个虚拟页，每个虚拟页的大小是预先设定的宏PAGE_SIZE。其中，pd_create_memsectioniguanaAPI，用来在指定的保护域中分配一块虚拟内6.2{pd_ref_tiguana_pd;inti;printf("Scheduletestisstarting...\n");/*pd*/for(i=0;i<PD_NUM;i++){other_pd_cap[i]=pd_create_ne}/*每个一定时间一次物理内存，并进行相应调度*/}return}主函数首先调用create_pd函数创建PD_NUM个保护线程（用函数create_thread），该线程调用上面介绍的页面分配函数每个一段时间，运行虚拟机程序，并显示程序的运行结果，即各个虚拟机的物理内存占用大小，通过调用函数show_physmem()。然后，show_resultflag用率随着时间的变化而发生的动态变化关系。在进试时，我们只开启一台虚拟验证实验的有效，进行局部调节和静态分配一定物理页做对比，证明算法的展示的是测试时虚拟机物理内存的占用量以及相应的内存利用率。实验中，我rdes80%，10.5，220，然后进行观测与。从图中可.2为局部调节有效性的实验验证，给出了采用局部调节的内存占用量与不同rdes的对60%（rdes.3中可以看出，两种情况下，内存利用率都比较稳定，这是由于局部rdes160%时，内存利用率的变化幅度小，即方rdes270%时，变化的幅度比较大。说明期望的内存利用率相对低一不同的对1情况，如图所示，其中●标注的是1为1.5时的情况，+标注的是1为0.5的情6.4不同λPD_NUM=2以简化问题，内存利用率rh和最小内存利用率rl的正中。启动全局调节，观察两个虚拟机物理内.6从图中可以看出，在最初的50s内，由于两个虚拟机的物理内存利用率均不高，此1的负载迅速上没有变化。在70-90s时，由于虚拟机2的负载量继续上升，虚拟机1的负载量迅速降低系统为1分配的物理内存降低的部分流动到虚拟2中。总机B）内存使用率极低的情况下，空闲的内存会逐渐由B转向A（前提是空闲的内存逐渐增长，由博弈理论计算出的均衡状态下的内存利用率降低的十分明显，在总结与展应用程序。因此，内存资源的动态管理，对于虚拟化系统来说非常重要。本文针对提高系统的实时性。在设计程序的时候，我们采用了每隔一段时间进行监提高系统的安全