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

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

2、析了現(xiàn)有的Linux存儲管理頁面換出機制在交互式桌面應用中的缺乏,提出了符合交互式應用特點的主動頁面換flJ算法該算法基于頁面狀態(tài)等價關系優(yōu)化了原系統(tǒng)中頁面狀態(tài)轉換自動機模型,使得系統(tǒng)在內存壓力大的情況F有條件緊急回收內存頁面,從提高桌面系統(tǒ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)在個人桌面應用領域的推進,逐步暴露出存在的問題,特

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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