提高Linux桌面交互性能的主動頁面換出算法

1、提高Linux桌面交互性能的主動頁面換出算法第32卷go1.32第l7期17計算機(jī)工程ComputerEngineering2006年9月September2006?軟件技術(shù)與數(shù)據(jù)庫?文章編號:1000-3428(2006)17113文獻(xiàn)標(biāo)識碼:A中圈分類號:TP311提高Linux桌面交互性能的主動頁面換出算法吳邦欲,陳左寧,顧明,孫家廣(1清大學(xué)計算機(jī)科學(xué)與技術(shù)系,北京l00084;2.江南計算技術(shù)研究所,無錫214083)攮要:Linux系統(tǒng)正逐步山效勞器領(lǐng)域步入桌面領(lǐng)域,由于Linux繼承了傳統(tǒng)的Unix的體系結(jié)構(gòu)和算法,它能否為桌面應(yīng)用提供好的交互性能是一個迫切需要研究的問題.該義分

2、析了現(xiàn)有的Linux存儲管理頁面換出機(jī)制在交互式桌面應(yīng)用中的缺乏,提出了符合交互式應(yīng)用特點(diǎn)的主動頁面換flJ算法該算法基于頁面狀態(tài)等價關(guān)系優(yōu)化了原系統(tǒng)中頁面狀態(tài)轉(zhuǎn)換自動機(jī)模型,使得系統(tǒng)在內(nèi)存壓力大的情況F有條件緊急回收內(nèi)存頁面,從提高桌面系統(tǒng)的交互性能.關(guān)健詞:桌而應(yīng)用;存儲管理;交互性能;面換出;啟動延遲ActivePageSwapoutAlgorithmforImprovingInteractivePerformanceDesktopLinuxtornceOtestOLInuxUWUBangyu.CHENZuoning.GUMing.SUNJiaguang(1.DepartnlentofC

3、omputerScienceandTechnology,TsinghuaUniversity,Beiing100084;2,JiangnanInstituteofComputingTechnology,Wuxi214083)AbstractLinuxisincreasinglysteppingintodesktnpfieldfromserver.WiththearchitectureandalgorithmdesignedbasedontraditionalUnixitisimportanttoinvestigatewhetherLinuxcanprovideefficientinteract

4、iveperformancefordesktopapplication.SomedisadvantagesofpageswapoutmechanisillareanalyzedinLinuxmemorynlanagementforinteractiveapplication.Anewalgorithmofactivepageswapoutsuitableforthecharactelistics(1finteractiveapplicationi,ptesented.Thealgolithmoptimizesthestatemachinebasedonequivalencerelationof

5、pagestate,anditallowstheapplicationitselftOswapOUmenloryifnecessary.himprovestheinteractiveperformancebyreclaimingabundantmemoutosatisfyapplicationundermemolYpleSStlFeKeywordslDesktopapplication;Memorynlanagenlent,hiteractionperformance;Pageswapout;Startuplatencyl概述隨著Linux系統(tǒng)在個人桌面應(yīng)用領(lǐng)域的推進(jìn),逐步暴露出存在的問題,特

6、別是與主流桌面操作系統(tǒng)相比,交互性能不夠高,用戶使用不夠流暢.原閃之一在于Linux在體系結(jié)構(gòu)和算法上秉承了傳統(tǒng)的適合效勞器的Unix操作系統(tǒng),在系統(tǒng)設(shè)計時強(qiáng)調(diào)整體吞吐,資源管理策略強(qiáng)調(diào)公平公正.桌面應(yīng)用屬于典型的交互式系統(tǒng),比分時共享系統(tǒng)更強(qiáng)調(diào)人機(jī)交互性能,特別是人的直觀感受;但由于人的行為和思維的延遲特性,桌面系統(tǒng)又不及實時系統(tǒng)對事件的實時響應(yīng)強(qiáng)度要求高,這種特點(diǎn)對傳統(tǒng)操作系統(tǒng)結(jié)構(gòu)和算法提出了新的要求.在桌面系統(tǒng)中,窗口和圖形界面是最主要的操作方式,應(yīng)用軟件的工作集大,對內(nèi)存資源高度敏感.桌面環(huán)境下內(nèi)存的配置干差萬別,CPU的飛速開展導(dǎo)致CPU性能與磁盤性能的差距越來越大,兇此不同條件下如

7、何發(fā)揮內(nèi)存資源的性能成為影響Linux在桌面應(yīng)用的關(guān)鍵因素.本文分析了Linux存儲管理頁面換出機(jī)制在桌面應(yīng)用中存在的問題,基于原有的存儲管理框架,提出了主動頁面換出算法APS(ActivePageSwapout).APS優(yōu)化了傳統(tǒng)的存儲管理中頁面被動換出的思想,由應(yīng)用程序主動提出換出請求.基于該算法,進(jìn)程調(diào)度可以實現(xiàn)進(jìn)程狀態(tài),進(jìn)程優(yōu)先級與存儲資源分配的一致性,用戶程序釋放近期不需使用的內(nèi)存,將內(nèi)存出讓給急需資源的桌面應(yīng)用.一J122Linux存儲管理頁面換出策略和狀態(tài)轉(zhuǎn)換分析2.1頁面換出策略Linux存儲管理采用傳統(tǒng)的按需頁面分配(demandpaging)算法,當(dāng)內(nèi)存不夠時,系統(tǒng)才以所有

8、進(jìn)程占用的物理空間作為統(tǒng)一的工作集,按照LRU原那么選擇頁面換出到磁盤.Linux系統(tǒng)的頁面換出策略在以下幾個方面不適合桌面交互式應(yīng)用:(I)頁面換出行為屬于被動觸發(fā),僅當(dāng)內(nèi)存資源低于一定的閥值時才啟動頁面換出進(jìn)程(kswapd).(2)頁面換出策略與進(jìn)程優(yōu)先權(quán)無關(guān).首先,調(diào)度算法雖然給優(yōu)先權(quán)高的進(jìn)程足夠的時間片,但如果進(jìn)程缺乏運(yùn)行依賴的資源條件,會降低CPU的利用率,掩蓋其調(diào)度的優(yōu)勢.其次,允許進(jìn)程長時間睡眠期問仍然占用內(nèi)存資源,頁面換出調(diào)度與CPU調(diào)度不一致.(3)頁面換出策略面向全局,所有進(jìn)程同等對待,LRU算法在選擇被換出的頁面時僅了解頁面最近是否被訪問,并不了解該頁面的其它屬性以及所

9、屬進(jìn)程的運(yùn)行狀態(tài).基金工程:國家973方案基金資助工程現(xiàn)代設(shè)計大型應(yīng)用軟件的共性根底(2004CB719406)作者簡介:吳邦欲(1973一),女,博士生,主研方向:操作系統(tǒng),分布式處理;陳左寧,工程院院士;顧明,副教授;孫家廣,工程院院:仁收稿日期:2005一I1一O9E-mail: 2.2頁面換出的狀態(tài)轉(zhuǎn)換根據(jù)Linux系統(tǒng)的LRU算法實現(xiàn),一個頁面從被選中到真正能夠換出到磁盤,需要經(jīng)歷漫長的狀態(tài)轉(zhuǎn)換過程,每一次狀態(tài)轉(zhuǎn)換都需要kswapd被調(diào)度運(yùn)行.圖1是分析內(nèi)核版本2.4.22源代碼得到的內(nèi)存頁面的有限狀態(tài)機(jī)M1.要換出一個頁面,需要kswa

10、pd被調(diào)度足夠的次數(shù),每一次調(diào)度驅(qū)動頁面狀態(tài)向前逼近一步.因此,Linux系統(tǒng)的頁面換出機(jī)制不能以較快的速度緩解內(nèi)存壓力,從而影響桌面應(yīng)用的交互性能.Iateransitot/otpagev,apouttheothersltteIransilionofpagePTE:pagetableentry,建立虛實空間映射的頁表項.activelist:活動頁面隊列,存放最近被訪問過的物理頁面.inactivelist:非活動頁面隊列,存放最近未被訪問過的物理頁面.圖1頁面挾出狀態(tài)機(jī):M13主動頁面換出算法APSAPS算法將頁面換出過程主要劃分為3個階段,并以此建_上了優(yōu)化的頁面換出狀態(tài)機(jī)模型,利用事件

11、驅(qū)動機(jī)制異步完成各階段狀態(tài)轉(zhuǎn)換.其中,寫盤作為一個關(guān)鍵階段,寫盤前為頁面預(yù)處理階段,寫盤后為頁面回收階段.在第一階段,應(yīng)用進(jìn)程根據(jù)頁面換出策略主動提出換出請求,系統(tǒng)核心進(jìn)行空間預(yù)處理,以較快的速度完成前期狀態(tài)轉(zhuǎn)換;在第二階段中,核心在監(jiān)測到系統(tǒng)空閑時將頁面內(nèi)容寫入swap磁盤空間;第三階段的目標(biāo)為,完成寫盤的頁面處于準(zhǔn)回收狀態(tài),當(dāng)存儲資源緊張時,系統(tǒng)迅速釋放已完成寫盤的物理頁面.其中,預(yù)處理和寫盤盡可能提前,頁面回收盡可能滯后.3.1APS中優(yōu)化的頁面換出有限狀態(tài)機(jī)模型M1將所有的頁面狀態(tài)同等對待,沒有考慮某些狀態(tài)的特殊性.實際上,swap寫盤,物理頁的回收以及寫盤前的一系列狀態(tài)顯然存在本質(zhì)的

12、區(qū)別,系統(tǒng)花費(fèi)的CPU時間和進(jìn)行的操作是不同的.APS的頁面換出狀態(tài)轉(zhuǎn)換自動機(jī)模型M2簡化了M1,如圖2所示.首先基于M1劃分頁面狀態(tài)的等價關(guān)系,將屬于同一階段具有同等屬性的狀態(tài)劃分為一個等價類.T1:頁面初始空閑狀態(tài);T2:預(yù)處理狀態(tài);T3:寫盤狀態(tài);T4:等待釋放狀態(tài);其它與頁面換出無關(guān)的狀態(tài)保持不變.那么有T1=S1;T2=S5,S6,S7,S8:T3=S9,S1O,S11;T4=S12,S13.當(dāng)應(yīng)用進(jìn)程主動提出換出請求后,狀態(tài)機(jī)由s4進(jìn)入T2,執(zhí)行預(yù)處理,如果頁面足1:凈的(clean),直接轉(zhuǎn)入準(zhǔn)釋放狀態(tài)(T4);如果頁面臟(dilty),CPU空閑時進(jìn)行寫盤相關(guān)處理(T3);完成

13、寫盤后,狀態(tài)轉(zhuǎn)換刨T4;當(dāng)內(nèi)存緊張時,處于準(zhǔn)釋放狀態(tài)(T4)的物理頁披回收,頁面州糾初始狀態(tài)(T1).圖2優(yōu)化的頁面挾出狀態(tài)機(jī):M23.2階段1:頁面狀態(tài)預(yù)處理頁面主動換出算法由應(yīng)用程序主動提f_f;換出請求,這種面向進(jìn)程空間的頁面換出思想使得頁面搜索不需要無目的地在全局隊列中進(jìn)行,也不會讓被換出的頁面無規(guī)律地分布在所有的進(jìn)程空間.基于APS,可以制定靈活的進(jìn)程空間頁面換出策略.(1)頁面換出策略同進(jìn)程調(diào)度以及進(jìn)程優(yōu)先級保持一致.使得睡眠的進(jìn)程僅擁有進(jìn)程實體,不占用CPU的進(jìn)程同時也沒有必要占用內(nèi)存,優(yōu)先級低的進(jìn)程仃義務(wù)將數(shù)據(jù)換出到磁盤,將內(nèi)存讓給優(yōu)先級高的進(jìn)程.(2)應(yīng)用進(jìn)程能直接控制頁面換

14、出.例如,支持占用內(nèi)存多的胖進(jìn)程在適宜的時機(jī)提出請求,從而將資源出讓給急需內(nèi)存的其它桌面應(yīng)用;初始化完成的進(jìn)程可以將初始化期間的代碼段,數(shù)據(jù)段換出到磁盤;進(jìn)程還可以將存在泄漏的內(nèi)存轉(zhuǎn)移到swap空間.按照一定策略選擇被換ffI的進(jìn)程空間后,核心執(zhí)行第一階段的頁面狀態(tài)預(yù)處理,使頁面狀態(tài)到達(dá)M2中的狀態(tài)T2,進(jìn)程單獨(dú)占用的物理空問頁面從activelist隊列轉(zhuǎn)移到inactivelist隊列.3.3階段2:輕量級頁面換出寫盤機(jī)制寫盤屬于耗時的1/0操作,Linux系統(tǒng)的頁面換出寫操作同其它換出處理操作一樣,發(fā)生在內(nèi)存資源異常緊張的狀態(tài)下,使得資源耗盡的系統(tǒng)又忙于I/O操作.因此需要設(shè)計一個輕量級

15、的調(diào)度機(jī)制在系統(tǒng)負(fù)載較輕時提前將頁面內(nèi)容寫入磁盤.由于桌面系統(tǒng)將近90%的時間處于空閑狀態(tài)l,可以利用這種特性以提高交互式響應(yīng)速度為目的進(jìn)行自身的性能優(yōu)化.APS對系統(tǒng)的狀態(tài)進(jìn)行細(xì)粒度采樣,周期性監(jiān)測系統(tǒng)的空閑狀況,按空閑時問呈超指數(shù)分布的規(guī)律,根據(jù)歷史記錄推測下一時間段系統(tǒng)空閑的慨率,決定是否進(jìn)行swap寫盤.輕量級調(diào)度機(jī)制必須盡可能增強(qiáng)空閑狀態(tài)可預(yù)測性,同時義不能增加原系統(tǒng)調(diào)度模塊的軟件開銷和復(fù)雜性.3.4階段3:延遲的緊急頁面回收機(jī)制Linux系統(tǒng)每次回收的頁面數(shù)很有限,而且頁面的回收與其它頁面換出行為同時按部就班執(zhí)行,岡此無論從時間還是空間上都無法很快滿足當(dāng)時急需內(nèi)存的應(yīng)用進(jìn)程的運(yùn)行.

16、APS改良了頁面的釋放回收機(jī)制,允許系統(tǒng)在內(nèi)存資源緊張時緊急大批量回收物理頁面.即當(dāng)系統(tǒng)分配物理頁面時,一l】3一如果發(fā)現(xiàn)空閑頁面數(shù)低于某一指定的閥值,那么直接回收已完成swap寫盤的頁面,保證系統(tǒng)在較短的時間內(nèi)獲得大量的空閑頁面.3.5結(jié)構(gòu)與原型實現(xiàn)APS原型系統(tǒng)的總體結(jié)構(gòu)如圖3所示.主要包括4個組件:頁面狀態(tài)預(yù)處理模塊(PP:pagepreprocess),CPU空閑監(jiān)測器(CM:CPUmonitor),寫盤效勞(SD:swapouttodisk)以及空閑頁面緊急釋放模塊(FM:freeingpagesurgently).PP由用戶態(tài)程序和操作系統(tǒng)核心共同完成,包括核心向應(yīng)用程序提供的系統(tǒng)

17、調(diào)用原語self_swapping(),使用系統(tǒng)調(diào)用原語的用戶層庫函數(shù);只有庫函數(shù)及相關(guān)的調(diào)用位于用戶態(tài),APS的其它局部均運(yùn)行在核心態(tài),在PP模塊中,應(yīng)用程序通過self_swapping()向系統(tǒng)提出頁面主動換出請求.CM監(jiān)測系統(tǒng)的忙閑情況,預(yù)測下一時間段的空閑狀態(tài),當(dāng)CM預(yù)測下一階段空閑,那么調(diào)度SD運(yùn)行.SD負(fù)責(zé)在CPU宅閑時將預(yù)處理完成的頁面寫入swap磁盤.然后由FM負(fù)責(zé)內(nèi)存緊張時回收完成swapout寫盤的物理頁面.kernelmode舉二:except,onsystemcall:self-swppi)JICPUmonitorJrpagefaultJe,isscaIcepagep

18、reprccess-一噬.=-_.1圈3頁面主動換出算諸結(jié)構(gòu)4實驗結(jié)果及分析桌面應(yīng)用是典型的交互式應(yīng)用,事件處理延遲是交互性能的重要表現(xiàn).但傳統(tǒng)的benchmark測試方法不能反映用戶所感受到的實際交互性能I.本文受文獻(xiàn)【5】的啟發(fā),利用真實桌面應(yīng)用的事件處理延遲來反映桌面的交互性能.而在眾多的交互事件中,來自用戶和社區(qū)的資料顯示,軟件啟動引起了用戶和開發(fā)人員的廣泛重視.本文以軟件啟動事件作為實驗對象,分別測試基于系統(tǒng)原有和改良的swap算法,內(nèi)存變化對啟動延遲性能的影響.測試采用了桌面Linux常用的應(yīng)用軟件,Evolution和Openoffice.測試系統(tǒng)硬件環(huán)境為2.4GHzPenti

19、um4處理器,5l2MB主存,操作系統(tǒng)為RedHat9.0簡體中文版,內(nèi)核版本2.4.22.圖4說明,原系統(tǒng)的啟動延遲不斷呈增長趨勢,啟動延遲過大,而利用了APS后的啟動延遲根本處于穩(wěn)定狀態(tài).Linux操作系統(tǒng)的swap操作首先由存儲管理模塊中的核心算法挑選頁面,然后將頁面內(nèi)容讀寫請求交給負(fù)責(zé)I/O操作的swap設(shè)備管理模塊.設(shè)為頁面swap讀寫的總時間,為存儲管理模塊的處理時間開銷,為swap模塊的處理時間開銷,表示啟動延遲,表示沒有swap發(fā)生時的啟動時間,那么有P=+7;且T,vap=mmPTo;根據(jù)上述兩式得到Tm=一一丁l14一那么在swap操作中占用的時間開銷比例為P:(一7D一7

20、)/(.一)實驗說明,Linux的swap所導(dǎo)致的軟件開銷非常大,APS的作用在于降低了swap的軟件開銷.一startuplatencybasedonstandardLinuxstartuolatencybasedonAPS2】-2(X)互l1一l【I15078910l】13l415swaps/MB薯4o0350faEvolution25f30354o4550spIn,M3(b)Openoffice田4桌面應(yīng)用軟件的啟動延遲5結(jié)論本文提出了主動頁面換出算法APS(ActivePageSwapout).APS優(yōu)化了傳統(tǒng)的存儲管理中頁面被動換出的思想,由應(yīng)用程序主動提出換出請求,使得系統(tǒng)在內(nèi)存壓力大的情況下迅速回收內(nèi)存頁面,從而提高桌面系統(tǒng)的交互性能.參考文獻(xiàn)1EvansS,ClarkeK.OptimizingUnixResourceSchedulingforUserInteractionC,ProceedingsoftheUSENIXSummerTechnicalConference,199