1006大設(shè)計(jì)翻譯版嵌入式hypervisor內(nèi)存管理的調(diào)度策略

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 緒 研究背 國(guó)內(nèi)外研究現(xiàn) 內(nèi)存資源的動(dòng)態(tài)分配策 基于虛擬化的內(nèi)存管理技術(shù)的研究目標(biāo)與內(nèi) 課題來(lái) 的組織結(jié) 相關(guān)技術(shù)現(xiàn) CPU虛擬化與內(nèi)存虛擬 三種CPU虛擬化技 內(nèi)存虛擬化技 虛擬機(jī)程序 OKL4系 OKL4系統(tǒng)簡(jiǎn) Hypercell技 iguana操作系統(tǒng)服務(wù) 本章小 程序設(shè) 選擇合適的方 內(nèi)存信息的量化描 粗粒度內(nèi)存信息 細(xì)粒度內(nèi)存信息 程序的實(shí) 本章小 基于控制論的局部調(diào)度策略設(shè) 反饋控制系 反饋控制系統(tǒng)原 兩種反饋控制系 基于控制理論的局部調(diào)度策略的設(shè) 局部調(diào)度策略的設(shè)計(jì)依 增量的量化處 局部調(diào)度算 本章小 基于博弈論的全局調(diào)度策略設(shè) 博弈論簡(jiǎn) 相關(guān)的重要概 問(wèn)題描述與解決策 全局調(diào)度算 本章小 系統(tǒng)實(shí) 實(shí)驗(yàn)環(huán) 測(cè)試工 LMbench的主要特 主要技術(shù)參數(shù)說(shuō) 功能實(shí) 實(shí)驗(yàn)?zāi)?實(shí)驗(yàn)過(guò) 本章小 總結(jié)與展 工作總 工作展 致 參考文 附錄相關(guān) 緒上可以同時(shí)運(yùn)行多個(gè)操作系統(tǒng)，并且為應(yīng)用程序的運(yùn)行提供了相互的運(yùn)行環(huán)境，顯叫做虛擬機(jī)器（VMM,VirtualMachineMonitor，取代了以往的操作系統(tǒng)而直接在機(jī)上運(yùn)行（針對(duì)Ⅰ型虛擬機(jī)程序情況。虛擬機(jī)程序創(chuàng)建一個(gè)底層硬件平臺(tái)抽象，這樣，一個(gè)或多個(gè)虛擬機(jī)（VM）無(wú)需知道它們共享平臺(tái)即可使用這個(gè)底層硬件ii術(shù)滿(mǎn)足hypervisor系統(tǒng)對(duì)客戶(hù)操作系統(tǒng)的支持。1.1VMware和KVM都已經(jīng)或計(jì)劃推出嵌入式平臺(tái)的虛擬機(jī)?；陉P(guān)鍵數(shù)據(jù)的內(nèi)存資源自治調(diào)度：由Oracle公司的相關(guān)小組在Xen上提出[3]，Xentarget基于應(yīng)用反饋的內(nèi)存資源動(dòng)態(tài)分配：由VMware公司的員工和大學(xué)的一些研究學(xué)者一種在服務(wù)整合環(huán)境中內(nèi)存資源動(dòng)態(tài)控制的機(jī)制[4]。其具體實(shí)現(xiàn)主要由此時(shí)運(yùn)行在虛擬機(jī)里的多個(gè)應(yīng)用程序開(kāi)始工作，并將它們的運(yùn)行性能數(shù)據(jù)通過(guò)插入基于建模評(píng)估的內(nèi)存資源動(dòng)態(tài)分配：由IBM研究團(tuán)隊(duì)提出，具體實(shí)現(xiàn)名為.2基于虛擬化的內(nèi)存管理技術(shù)的這是因?yàn)?，在引入hypervisor之后，傳統(tǒng)的操作系統(tǒng)不再直接作用在物理內(nèi)存資源上，于是物理內(nèi)存資源變成了由現(xiàn)在的hypervisor來(lái)管理。但是應(yīng)用程序?qū)?nèi)存資源的使用化域了系，分hprvior均采取在虛擬機(jī)運(yùn)行前便動(dòng)態(tài)內(nèi)存管理技術(shù)成為關(guān)注的熱點(diǎn)，并提出了氣球驅(qū)動(dòng)和內(nèi)存熱插拔等相關(guān)管理技術(shù)。氣球驅(qū)動(dòng)[6]由wre增傾定hprvior當(dāng)中。利用效率，如圖3.1.1所示。其中，內(nèi)存信息部分負(fù)責(zé)收集系統(tǒng)及各個(gè)虛擬機(jī)中與1.2（即某些虛擬機(jī)的空閑內(nèi)存以供內(nèi)存緊缺的虛擬機(jī)使用。在這里，我們引入了反饋調(diào)節(jié)，根據(jù)當(dāng)前內(nèi)存利用率和期題第二章主要介紹了在設(shè)計(jì)相應(yīng)內(nèi)存資源器和調(diào)度器時(shí)要使用到的相關(guān) 及實(shí)現(xiàn)了程序的算法。相關(guān)技術(shù)現(xiàn)ARM處理器主機(jī)上運(yùn)行為仿真，因此速度會(huì)減慢100倍甚至1000倍。2.1hypervisor在客戶(hù)操作系統(tǒng)和底層硬件之間進(jìn)行協(xié)調(diào)。引hypervisor后，底層硬件并不由操作系統(tǒng)所擁有，而是在hypervisor的管理下由多個(gè)操作系統(tǒng)共享，并且，特定受保護(hù)的指令必須獲下來(lái)并在hypervisor中進(jìn)行處理。題，比如需要VMM處理的一些特定敏感指令并沒(méi)有獲。因此，hypervisor必須要?jiǎng)討B(tài)掃描并捕獲這些模式代碼來(lái)解決這一問(wèn)題。2.2擬化技術(shù)的一個(gè)缺點(diǎn)，但是提供了與虛擬化的系統(tǒng)接近的性能。2.3除了CPU虛擬化，另外一個(gè)重要的虛擬化就是內(nèi)存虛擬化。虛擬機(jī)的內(nèi)存虛擬化現(xiàn)在所有的x86CPU都包含內(nèi)存管理單元MMU（MemoryManagementUnit）和TLB(TranslationLookasideBuffer)MMUTLB來(lái)優(yōu)化虛擬內(nèi)存的性能。內(nèi)存物理地址的映射，但是客戶(hù)操作系統(tǒng)不能直接實(shí)際機(jī)器內(nèi)存。VMM負(fù)責(zé)映射擬內(nèi)存到物理內(nèi)存的映射表，VMM也會(huì)更新頁(yè)表來(lái)啟動(dòng)直接查詢(xún)。另外，VMM使用TLB硬件來(lái)映射虛擬內(nèi)存直接到機(jī)器內(nèi)存，從而避免了每次進(jìn)行兩次翻譯。2.4虛擬機(jī)監(jiān)視器（VMM），又稱(chēng)hypervisor，它作為一款輕量級(jí)軟件，向上層的虛擬機(jī)等價(jià)性VMM下的程序，其行為應(yīng)與直接運(yùn)行于等價(jià)物理機(jī)上的相同程序的行效率性在引入VMM之后，GuestOS通過(guò)VMM實(shí)際的物理硬件。VMM運(yùn)行在運(yùn)行。同時(shí)VMM也為每個(gè)虛擬機(jī)虛擬出一套與真實(shí)硬件無(wú)關(guān)的虛擬硬件環(huán)境。作系統(tǒng)必須通過(guò)VMM來(lái)物理硬件，在性能上的損失較大。該模式的VMM的位置如圖所示。2.5宿主模式的VMM獨(dú)立模式（Stand-AloneHypervisor獨(dú)立模式下，VMM直接運(yùn)行于硬件之上，有最高的級(jí)別，可直接使用硬GuestOSVMMVMM的位置如圖圖2.6獨(dú)立模式的VMM示意混合模式（Hybrid混合模式結(jié)構(gòu)上與獨(dú)立模式近似，VMM在最高級(jí)別上運(yùn)行，是直接在物理硬件上運(yùn)行的，虛擬機(jī)則是運(yùn)行在VMM之上的。與其他模式相比，這個(gè)模式里的2.7混合模式的VMM統(tǒng)環(huán)境的VMM設(shè)計(jì)。針對(duì)嵌入式系統(tǒng)，VMM的設(shè)計(jì)應(yīng)該考慮到嵌入式系特的隔碼性能以及有效地滿(mǎn)足實(shí)時(shí)性變得，也導(dǎo)致了整體性能降低。在InVT系統(tǒng)中，需要運(yùn)行沒(méi)有分頁(yè)的客體(guest)，減少客體(guest)之間的。在通用環(huán)境中，這是不可接受的，但是在一些嵌入式環(huán)境中，可能是優(yōu)先選擇的。第二個(gè)，I／0性能對(duì)于一個(gè)嵌入式系統(tǒng)的成功與否可能至導(dǎo)致一些VMM廠(chǎng)家允VM直接進(jìn)行內(nèi)存(DMA)。這樣提高了性能，但是也允許應(yīng)用或設(shè)備驅(qū)動(dòng)讀寫(xiě)系統(tǒng)上的特定的核和特定的內(nèi)存區(qū)域往往被VMM的設(shè)計(jì)者采用，這樣做可以減少操作系統(tǒng)中的動(dòng)態(tài)調(diào)度和動(dòng)態(tài)內(nèi)存管理。針對(duì)調(diào)度策略和內(nèi)存管理策略，嵌入式系統(tǒng)在VMM的設(shè)計(jì)核之間的調(diào)度得以簡(jiǎn)化。其次，在內(nèi)存管理的設(shè)計(jì)方面，地針對(duì)可配置性而不是動(dòng)態(tài)分配。VMM設(shè)計(jì)者會(huì)預(yù)先規(guī)劃分配給每個(gè)虛擬機(jī)的內(nèi)存區(qū)域，這樣簡(jiǎn)化了內(nèi)存管理程或線(xiàn)程占用指定處理器的時(shí)間。傳Windowslinux操作系統(tǒng)采用的是基于優(yōu)先級(jí)沒(méi)有任務(wù)能另一任務(wù)的進(jìn)程。在虛擬化環(huán)境中支持實(shí)時(shí)任務(wù)是一個(gè)，因?yàn)閂MMRTOS中運(yùn)行單個(gè)任務(wù)，也不知道它們的優(yōu)先級(jí)。解決方案是在處理器核上RTOS，或者只允許RTOS與GPOS共個(gè)核并且給RTOS嚴(yán)格的，高于GPOS的優(yōu)先級(jí)。的研究平臺(tái)是OKL4。2006年，OpenKernelLabs(OKLabs)創(chuàng)立，致力于為嵌入式系統(tǒng)開(kāi)發(fā)微核和虛擬機(jī)程序。OKL4是一個(gè)基于微內(nèi)核技術(shù)的軟件平臺(tái)，它支持系（TCB系統(tǒng)中使用輕量級(jí)保護(hù)單元進(jìn)行錯(cuò)誤。它可以作為全功能或單獨(dú)功能的操作系統(tǒng)。OKL4可以提供用于移動(dòng)設(shè)備，消費(fèi)者電子，工廠(chǎng)自動(dòng)化，醫(yī)療電子以及電子/數(shù)據(jù)通信基礎(chǔ)設(shè)施的系統(tǒng)的虛擬化[10]。OKL4是建立在L4的微內(nèi)核之上，并且基于PistachioOKL4構(gòu)架的體系結(jié)構(gòu)，它實(shí)現(xiàn)了名為安全單元的分區(qū)，一個(gè)具有虛擬化microvisor，以及高效的進(jìn)程間通信。OKLabs提供了對(duì)幾個(gè)半虛擬化的操作系統(tǒng)的支持，這些操作系統(tǒng)包括：OK:Linux、OK:Android和OK:Symbian。圖 其中，OKLinuxLinuxOKL4上運(yùn)行客戶(hù)操作系統(tǒng)。虛擬化系統(tǒng)有兩種技術(shù)類(lèi)型：完全虛擬化（hypervisor負(fù)責(zé)捕獲序接口hypercall來(lái)替換所有的指令，以修改客戶(hù)操作系統(tǒng)。OKL4使用的就是半虛擬機(jī)體系結(jié)構(gòu)了客戶(hù)操作系統(tǒng)的錯(cuò)HypercellOKLabs使用的體系結(jié)構(gòu)叫做安全的超細(xì)胞技術(shù)，它為開(kāi)發(fā)和配置可信的嵌入式系統(tǒng)提供了環(huán)境。圖所示的OKL4系統(tǒng)擁有不同的分區(qū)（細(xì)胞，它們之間相互隔離，每個(gè)細(xì)胞可能包含任何的系統(tǒng)組件，或者一個(gè)完整的操作系統(tǒng)環(huán)境（虛擬機(jī)，操式下的代碼，用來(lái)提供虛擬化，分區(qū)，IPC機(jī)制等服務(wù)。由于系統(tǒng)的其他部分都不可以以模式，因此系統(tǒng)的完整性可以避免任意細(xì)胞里代碼的破壞。系統(tǒng)組件在代碼和代碼。權(quán)限（capability）用來(lái)子系統(tǒng)對(duì)資源的。iguana OKL4 OKL4iguanaOKL4的OKL4CPOSIXPSE51用于內(nèi)核原OKL4OKL4OKL4編譯工具,IDL(magpie),系統(tǒng)配置工具其中，Iguana是一個(gè)小型的操作系統(tǒng)，專(zhuān)門(mén)為實(shí)現(xiàn)安全和可靠的嵌入式系統(tǒng)開(kāi)發(fā)，它運(yùn)行L4微內(nèi)核上，支linux的運(yùn)行，并將其作為一個(gè)應(yīng)用程序。Iguana提供一系列用OKL4原語(yǔ)的方便的方法。Threads線(xiàn)程：執(zhí)行和調(diào)度的基本單元。IguanaL4L4的原語(yǔ)以及iguana定義的原語(yǔ)調(diào)用。Protections保護(hù)域：為不同程序的線(xiàn)程提供內(nèi)存保護(hù)，大體上相當(dāng)于任務(wù)或linux中的進(jìn)程不同，所有的保護(hù)域都共享相同的虛擬地址空間。如圖所示。Memorysections內(nèi)存片：虛擬內(nèi)存分配和保護(hù)的單元。一個(gè)內(nèi)存片是一組連續(xù)的虛pages線(xiàn)程可以共享對(duì)內(nèi)存片的。2.10Memorypools內(nèi)存池：iguana允許物理內(nèi)存和虛擬內(nèi)存組織成的內(nèi)存池。每個(gè)一旦被建立，它將被用來(lái)創(chuàng)建physmem對(duì)象。如下圖所示：Physmem物理內(nèi)存：描述了一串連續(xù)范圍的物理內(nèi)存頁(yè)面（physicalpages，通過(guò)mapmemorysectionsphysmempoolphysicalA，分別是默認(rèn)物理內(nèi)存池和用戶(hù)定義的內(nèi)存池。它們分配了兩個(gè)physmem，并映射到兩個(gè)memsection。2.1CPU虛擬化技術(shù)以及內(nèi)存虛擬化的技術(shù)。2.2節(jié)介紹并分因素。2.3OKL4的具體情況，以及其專(zhuān)門(mén)為嵌入式開(kāi)發(fā)的操作系統(tǒng)iguana的相關(guān)接口A(yíng)PI。3程序設(shè)步導(dǎo)致了對(duì)虛擬機(jī)的內(nèi)存資源的使用情況進(jìn)行實(shí)時(shí)變得很，并且要準(zhǔn)確預(yù)估虛情況[12]。相比之下，“白盒”方式的優(yōu)點(diǎn)是能夠及時(shí)獲得虛擬機(jī)的運(yùn)行信息，對(duì)內(nèi)存需求的評(píng)估更加準(zhǔn)確。缺點(diǎn)是對(duì)虛擬機(jī)操作系統(tǒng)的“”較大，有的需要修改虛擬機(jī)OKL4系統(tǒng)，OKL4iguana服務(wù)iguana上對(duì)各個(gè)虛擬機(jī)進(jìn)行實(shí)時(shí)，這樣不僅能夠?qū)χ苯?，及時(shí)的獲得虛擬機(jī)的同時(shí)，修改iguana操作系統(tǒng)造成對(duì)其的“”較大，有可能影響其運(yùn)行。本文中 3.1commitlinuxwindows等，程序?qū)?nèi)存變得可用而做的一個(gè)到實(shí)際物理的一個(gè)映射[13]UsedfreeC，表示當(dāng)前分配給虛擬機(jī)的可用物理內(nèi)存大小，兩者它通過(guò)改變自身占用物理內(nèi)存的大小改變虛擬機(jī)當(dāng)前可用內(nèi)存大小C（注意，虛擬機(jī)可3.2表 參數(shù)進(jìn)行預(yù)測(cè)。由于界限值的存在，必須對(duì)CiHiLi之間，如果超出范圍則取邊界值，這樣得到的值便是MCi。者的基礎(chǔ)上，便可以對(duì)整個(gè)系統(tǒng)所需的內(nèi)存值進(jìn)行評(píng)估。Ni為當(dāng)前分配給某虛擬機(jī)的內(nèi)存值，于是(MCiNi便是所有虛擬機(jī)（即整個(gè)系統(tǒng)）未來(lái)（下一時(shí)刻）Fh(MCiNi，說(shuō)明物理機(jī)上的空閑內(nèi)存可以滿(mǎn)足所有虛擬機(jī)對(duì)內(nèi)存的需Fh(MCiNi，說(shuō)明物理機(jī)上的空閑內(nèi)存已經(jīng)所有虛擬機(jī)對(duì)內(nèi)存程序3.1pd_pm_size{uintptr_tpaddr,psize;TAILQ_FOREACH_SAFE(pm,&ms->pm_list,pm_list,}return}TAILQ_FOREACH_SAFE是宏定義，用來(lái)安全的遍歷所指定的雙向鏈表；physmem_infoiguanaAPI，psize是傳出參程序 Staticstructpd*pds[20];//thesetofalliguanaStaticintcount;//thenumberoftheset{structpd_nodefor(ppd=pd->pds.first;ppd->next!=pd->pdsfirst;ppd=ppd-{pds[count++]=ppd;}return}靜態(tài)數(shù)據(jù)區(qū)的變量pds和count，用來(lái)記錄所有保護(hù)域的指針和數(shù)目。程序3.3iguana_pm_size{return}為iguana里的保護(hù)域才是嵌入式系統(tǒng)中的虛擬機(jī)。本章主要介紹了虛擬機(jī)內(nèi)存器的設(shè)計(jì)思路過(guò)程。首先分析討論了虛擬機(jī)內(nèi)存的兩種狀態(tài)；最后給出了程序的具體實(shí)現(xiàn)?；诳刂普摰木植空{(diào)度策略4.1負(fù)反饋（negative正反饋（positivefeedback在本次設(shè)計(jì)的控制系統(tǒng)中，根據(jù)內(nèi)存期望的利用率rdes與當(dāng)前內(nèi)存的利用率r之間的利用率rdes回歸。IO密集型應(yīng)用往往都對(duì)運(yùn)行環(huán)境中的空閑物理內(nèi)存具有嚴(yán)換空間不停地調(diào)頁(yè)造能下降。基于此，在對(duì)內(nèi)存利用率進(jìn)行過(guò)程中，我們引入了控制理論中的反饋調(diào)節(jié)，根合理的范圍之內(nèi)。如圖所示，有兩個(gè)基本參數(shù)：輸入?yún)?shù)：期望的內(nèi)存利用率ΔU，則下一時(shí)刻內(nèi)存的估計(jì)值就為：UnewUold4.2綜合以上兩點(diǎn)考慮，我們給出如下的增量控制公式(r2r2Uoldr

r dU

r

Uoldr

rd4.1當(dāng)r小于des時(shí)，系統(tǒng)資源的內(nèi)存調(diào)節(jié)的增量是負(fù)的，說(shuō)明此時(shí)是負(fù)反饋，應(yīng)該減少r大于rdes當(dāng)內(nèi)存利用率r大于系統(tǒng)期望內(nèi)存利用率rdes時(shí)，系統(tǒng)資源處于短缺狀態(tài)。因此增應(yīng)該較大，所以調(diào)整參數(shù)1與公式的其他部分是乘法的關(guān)系（前提是1與2均為大11020之間；當(dāng)內(nèi)存利用率r源造成的性能下降，釋放資源的力度增量應(yīng)該較小，于是調(diào)整參數(shù)2與公式的其對(duì)于控制參數(shù)1和2即調(diào)整的粒度（或幅度。具體的值在后續(xù)的實(shí)驗(yàn)中進(jìn)行試探與調(diào)整算法輸入?yún)?shù)： rde 輸出參數(shù)：獲取內(nèi)存利用率r，前內(nèi)存值WhileIfIfrrdes設(shè)置U的值為Uoldrr

(r2r2設(shè)置U的值為Uoldr rdes

設(shè)置目標(biāo)調(diào)節(jié)內(nèi)存值TargetMemMin(max(lower_bound,U由氣球驅(qū)動(dòng)根據(jù)TargetMem本章介紹了局部調(diào)度算法的實(shí)現(xiàn)。其中，4.1基于博弈論的全局調(diào)度策略5.1 本章介紹的全局調(diào)度借鑒了博弈論的相關(guān)知識(shí)，利用均衡原理對(duì)所討論的問(wèn)題theory1944年馮與合著《博弈論與經(jīng)濟(jì)行為》，標(biāo)志著現(xiàn)代系統(tǒng)博20世紀(jì)經(jīng)濟(jì)學(xué)最偉大的成果之一。目前在生物學(xué)、經(jīng)濟(jì)學(xué)、國(guó)際G：輸贏(yíng)的（游戲，，比賽，競(jìng)爭(zhēng)）格局。博弈的三要素參與者：博弈的決策主體，通常又稱(chēng)為參與人或局中人，一般記為參與者,,n行動(dòng)與：行動(dòng)時(shí)博弈參與者i在決策時(shí)可供選擇的動(dòng)作，一般記為ai。全不行動(dòng)的參與者所選擇的行動(dòng)做出對(duì)應(yīng)的行動(dòng)安排，一般用si表示。用Si表示空間，即Si{si}。此，靜態(tài)博弈中si和行動(dòng)ai是相同的。身行動(dòng)時(shí)就應(yīng)該做出針對(duì)性的反應(yīng)。因此，動(dòng)態(tài)博弈中參與者i的si就與他所掌的信息以及他可供選擇的行動(dòng)ai相關(guān)收益：在一個(gè)特定的組合(s1,s2,,sn)下參與者i得到的效用（常表現(xiàn)為博弈中參i的輸贏(yíng)，得失，盈虧i的收益通常記為ui(s1s2sn，簡(jiǎn)記為ui。由于參與者i的效益ui(s1,s2,,sn)是隨著組合(s1,s2,.,sn)的不同而改變，因此收S1,S2Sn，各個(gè)參與者的收益函數(shù)分別為u1(s1,s2sn)u2(s1,s2sn)，..un(s1,s2,,sn)。那么，博弈G的式表述記GS1S2Snu1,u2,.un}均衡：一個(gè)博弈的所有參與者的 的組合，一般記為r*(r*,r*,...,r*,.,r*)。 i相互影響的決策，或者說(shuō)是互動(dòng)決策，因此，最優(yōu)r*通常依賴(lài)于其他參與者的ii 均衡：在n個(gè)參與者的式表述博弈G={S1,S2,...,Sn；u1,u2,...un}中，如果對(duì)于每一個(gè)參與者i，他選擇的s*是針對(duì)其他n-1個(gè)參與者所選組合is* s*,...,s*的最優(yōu)反應(yīng)，即s* i1 maxu(sS*)maxu s*,...,s*，i=1,2,...,n i1 那么，組合s*(s*,...,s*)稱(chēng)為博弈G的均衡[17] 這里均衡定義揭示了每一個(gè)參與者的最優(yōu)選擇的均衡s*

都在追求自身收益u i1 如果空間Si是連續(xù)空間，定義中最優(yōu)化問(wèn)題的求解，利用微積分求極值的方法u(s,s*,...,s*1 n

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

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

個(gè)參與者所選組合(s*,...,s*,s*,...,s*)的最優(yōu)選擇應(yīng)滿(mǎn)足的關(guān)系其余方程含義類(lèi)同 i1 均衡，從而構(gòu)成博弈的結(jié)果均衡s*(s*,...,s* 均衡雖然給出了博弈參與者一致的對(duì)博弈的結(jié)果的預(yù)測(cè)，但并不表示均衡一結(jié)果最可能出現(xiàn)，往往涉及到文化，心理和經(jīng)驗(yàn)等方面的知識(shí)和信息。依據(jù)上述原理以及相關(guān)概念，我們針對(duì)系統(tǒng)具體的問(wèn)題進(jìn)行建模，然后利用均 riiNri[0,1]來(lái)代表虛iRmiri，其中m 銷(xiāo)。假設(shè)用P表示系統(tǒng)性能，則P是系統(tǒng)內(nèi)存利用率R的函數(shù)PP(R)P 現(xiàn)在，我們用均衡的靜態(tài)博弈方法來(lái)解決該問(wèn)題[18]。為了將該問(wèn)題轉(zhuǎn)化為決ui(Pc)ri(PaR)ricri 其中，c以下我們只要求得一個(gè)策略組合(r*,r*,...,r*,...,r*)，其中r*[0,1]是虛擬機(jī)i 他n-1個(gè)虛擬機(jī)的策略s*,s*,...,s*,...,s*的最佳對(duì)策，那么便求得均衡， u(r*,r*,...,r*,...,r*)u(r*,r*,...,r*,r*,r*,...,r*) i i1 ir*[0,1]，i i為了求得(r*,r*,...,r*,...,r*)，須解決以下的最優(yōu)化問(wèn) 為了簡(jiǎn)化計(jì)算，我們假設(shè)分配給各個(gè)虛擬機(jī)的物理內(nèi)存mi是相同的，即mim，Rmiri mrbr，其中bm (3.4.4)Pcabrj2abri0 jN因此求得r

Pc

jN\{i} 2ab

Pc

r*Pc iab(ni在這個(gè)均衡的情況下，性能則P*Pabnr*P n在這 u*(P*c)r*M(P

(

am(n算法輸入?yún)?shù) (r1r2,...,ri,...,rn 設(shè)置r*的值Pab(nWhileIfForiN設(shè)置內(nèi)存利用率增量的值為rr 設(shè)置TargetMem的值為m*

由氣球驅(qū)動(dòng)根據(jù)TargetMem

本章介紹了全局調(diào)度算法的實(shí)現(xiàn)。5.1節(jié)介紹了博弈論和均衡的相關(guān)原理。5.2節(jié)對(duì)實(shí)際問(wèn)題進(jìn)行了分析建模，并總體概述了全局調(diào)度算法的設(shè)計(jì)思路。5.3介紹了系系統(tǒng)實(shí)前三章分別介紹了虛擬機(jī)程序，基于控制理論的局部調(diào)度，基于博弈論的全局驗(yàn)，實(shí)施實(shí)驗(yàn)并分析，驗(yàn)證本系統(tǒng)的可用性。 (R)Core(TM)2Quad OKL4合ANSI/C標(biāo)準(zhǔn)為UNIX/POSIX而制定的微型工具，一般來(lái)說(shuō)，它衡量?jī)蓚€(gè)關(guān)鍵LMbenchTLB表的未命中延遲。另外，緩存的大小可以被正確劃分成一些結(jié)果集并新的工lmbench的參數(shù)有很多，包括系統(tǒng)基本的參數(shù)，處理器與進(jìn)程的操作時(shí)間，基表 lmbench技術(shù)參數(shù)參數(shù)具體參數(shù)詳BasicsystemTlbTLB（TranslationBuffer）的頁(yè)面Cachelinecache的行字節(jié)數(shù)MemoryparallelismScal并行的lmbenchProcessor,Null簡(jiǎn)單系統(tǒng)調(diào)用（取進(jìn)程號(hào)Null簡(jiǎn)單IO操作（空讀寫(xiě)的平均取文檔狀態(tài)的操Open打開(kāi)然后立即關(guān)閉關(guān)閉文檔操Sig捕獲File&VMsystemFileCreate&創(chuàng)建并刪除文檔MMap內(nèi)存映Page缺100fd對(duì)100個(gè)文檔描述符配置selectLocalCommunication管道操File文檔重復(fù)MMap內(nèi)存映射重復(fù)讀Mem內(nèi)存Mem內(nèi)存內(nèi)存拷內(nèi)存拷MemoryMain連續(xù)內(nèi)Rand內(nèi)存隨機(jī)延程序staticpage_alloc(int{intphysmem_ref_t }}該函數(shù)有一個(gè)參數(shù)n_pages，表示要分配的頁(yè)面?zhèn)€數(shù)，這個(gè)參數(shù)用來(lái)控制虛擬機(jī)占用內(nèi)存的大小。具體算法中，我們?cè)谥付ǖ谋Ｗo(hù)域other_pd_cap[0].ref.pd中分配n_pages個(gè)虛擬頁(yè)，每個(gè)虛擬頁(yè)的大小是預(yù)先設(shè)定的宏P(guān)AGE_SIZE。其中，pd_create_memsectioniguanaAPI，用來(lái)在指定的保護(hù)域中分配一塊虛擬內(nèi)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}/*每個(gè)一定時(shí)間一次物理內(nèi)存，并進(jìn)行相應(yīng)調(diào)度*/}return}主函數(shù)首先調(diào)用create_pd函數(shù)創(chuàng)建PD_NUM個(gè)保護(hù)線(xiàn)程（用函數(shù)create_thread），該線(xiàn)程調(diào)用上面介紹的頁(yè)面分配函數(shù)每個(gè)一段時(shí)間，運(yùn)行虛擬機(jī)程序，并顯示程序的運(yùn)行結(jié)果，即各個(gè)虛擬機(jī)的物理內(nèi)存占用大小，通過(guò)調(diào)用函數(shù)show_physmem()。然后，show_resultflag用率隨著時(shí)間的變化而發(fā)生的動(dòng)態(tài)變化關(guān)系。在進(jìn)試時(shí)，我們只開(kāi)啟一臺(tái)虛擬驗(yàn)證實(shí)驗(yàn)的有效，進(jìn)行局部調(diào)節(jié)和靜態(tài)分配一定物理頁(yè)做對(duì)比，證明算法的展示的是測(cè)試時(shí)虛擬機(jī)物理內(nèi)存的占用量以及相應(yīng)的內(nèi)存利用率。實(shí)驗(yàn)中，我rdes80%，10.5，220，然后進(jìn)行觀(guān)測(cè)與。從圖中可.2為局部調(diào)節(jié)有效性的實(shí)驗(yàn)驗(yàn)證，給出了采用局部調(diào)節(jié)的內(nèi)存占用量與不同rdes的對(duì)60%（rdes.3中可以看出，兩種情況下，內(nèi)存利用率都比較穩(wěn)定，這是由于局部rdes160%時(shí)，內(nèi)存利用率的變化幅度小，即方rdes270%時(shí)，變化的幅度比較大。說(shuō)明期望的內(nèi)存利用率相對(duì)低一不同的對(duì)1情況，如圖所示，其中●標(biāo)注的是1為1.5時(shí)的情況，+標(biāo)注的是1為0.5的情6.4不同λPD_NUM=2以簡(jiǎn)化問(wèn)題，內(nèi)存利用率rh和最小內(nèi)存利用率rl的正中。啟動(dòng)全局調(diào)節(jié)，觀(guān)察兩個(gè)虛擬機(jī)物理內(nèi).6從圖中可以看出，在最初的50s內(nèi)，由于兩個(gè)虛擬機(jī)的物理內(nèi)存利用率均不高，此1的負(fù)載迅速上沒(méi)有變化。在70-90s時(shí)，由于虛擬機(jī)2的負(fù)載量繼續(xù)上升，虛擬機(jī)1的負(fù)載量迅速降低系統(tǒng)為1分配的物理內(nèi)存降低的部分流動(dòng)到虛擬2中。總機(jī)B）內(nèi)存使用率極低的情況下，空閑的內(nèi)存會(huì)逐漸由B轉(zhuǎn)向A（前提是空閑的內(nèi)存逐漸增長(zhǎng)，由博弈理論計(jì)算出的均衡狀態(tài)下的內(nèi)存利用率降低的十分明顯，在總結(jié)與展應(yīng)用程序。因此，內(nèi)存資源的動(dòng)態(tài)管理，對(duì)于虛擬化系統(tǒng)來(lái)說(shuō)非常重要。本文針對(duì)提高系統(tǒng)的實(shí)時(shí)性。在設(shè)計(jì)程序的時(shí)候，我們采用了每隔一段時(shí)間進(jìn)行監(jiān)提高系統(tǒng)的安全