劉鐵武,張鐵楠,馮 劍

(湖南工程學(xué)院計算機與通信學(xué)院,湘潭411104)

Linux因其穩(wěn)定性、安全性、源代碼開放等特點而成為當(dāng)今最具發(fā)展?jié)摿Φ牟僮飨到y(tǒng).存儲管理作為Linux的核心部分,直接關(guān)系整個計算機系統(tǒng)的性能.

Linux采用了請求分頁式存儲管理,其內(nèi)存管理部件與交換子系統(tǒng)都是以頁為操作粒度的.

Linux請求分頁的思想很簡單:一個進程并不要全部在內(nèi)存中,僅只用戶結(jié)構(gòu)和頁表.如果它們存在于內(nèi)存,對應(yīng)進程就被認(rèn)為“在內(nèi)存中”,代碼、數(shù)據(jù)和棧段的頁面是僅僅當(dāng)其被引用時動態(tài)載入的.如此,從邏輯上實現(xiàn)了對內(nèi)存容量的擴充.

因為頁面的動態(tài)載入,勢必將產(chǎn)生缺頁而需要在內(nèi)、外存間進行頁面置換.如果進程運行過程中因為缺頁而頻繁在內(nèi)外存間進行頁面交換,則主要執(zhí)行I/O操作而CPU利用率極低,進程幾乎沒有完成有效的工作,這種狀態(tài)就是顛簸.本文從理論上分析了顛簸的形成機制、刻劃了它的特征.在此基礎(chǔ)上,討論了顛簸的處理策略.

1 顛簸的形成機制

1.1 進程擁有的物理塊不足

與局部置換相比,頁面的全局置換能提高請求分頁式系統(tǒng)性能[4].實際上,一般操作系統(tǒng)都采用了此種策略.但另一方面,這種置換策略決定了:如果增加某個進程的物理塊數(shù)目,可能直接導(dǎo)致另一進程的物理塊數(shù)目減少.當(dāng)整個系統(tǒng)的物理塊不能滿足諸進程的需要時,缺頁率將持續(xù)維持于一高水平值,意味著顛簸已實際形成.其具體表現(xiàn)形式如下:

(1)進程競爭臨界資源.考慮這樣的情況:系統(tǒng)中已不存在空閑物理塊,而進程A卻要求增加物理塊,于是,中斷處理程序只得將原屬于進程B的物理塊分配給進程A;同樣地,進程B又分配到原屬于進程C的物理塊,如此等等.一定時候,各缺頁進程都將被阻塞,就緒隊列為空,顛簸從此形成[9].

(2)增加多道程序度[5].當(dāng)CPU利用率處于低水平時,為提高多道程序度,調(diào)度程序要求從后備輸入隊列選擇進程加載內(nèi)存.

圖1 多道程序度與CPU利用率的關(guān)系

圖1 可清楚地說明這種情形下顛簸的形成原因.首先,隨著多道程序度的增加,CPU利用率隨之增加而達到一個理論極值.但在極值點右邊,再增加多道程序度,因為進程事實上只能從已加載的進程處獲得物理塊,從而使得更多的進程因缺頁而阻塞,隨著更多的進程執(zhí)行內(nèi)外存的I/O操作,CPU利用率反而更低;為提高CPU利用率,調(diào)度程序又要求調(diào)入新進程.如此形成惡性循環(huán),系統(tǒng)諸進程都將缺頁,顛簸形成.

(3)內(nèi)存分配機制引起顛簸.由于異構(gòu)硬件的限制,物理內(nèi)存并沒被同等對待.Linux有三種內(nèi)存區(qū)域:ZONE_DMA;ZONE_NORMAL;ZONE_HIGHMEM.前兩種是內(nèi)核和內(nèi)存映射,被“釘”在內(nèi)存中(頁面從不換出).當(dāng)應(yīng)用進程請求分配內(nèi)存時,采用“伙伴算法”[6]由頁面分配器予以分配.該算法可能導(dǎo)致大量的內(nèi)存碎片;而另一方面,Linux的虛擬地址空間被分割成同構(gòu)連續(xù)的頁面對齊的區(qū)域.則可能實際空閑空間具備卻沒一塊連續(xù)的空間來滿足任一進程的需求,各進程都將阻塞.

1.2 因頁面置換算法而形成

虛擬存儲技術(shù)的理論基礎(chǔ)是P.Denning的局部性原理.即程序在執(zhí)行時將呈現(xiàn)時間局限性和空間局限性.事實上,在結(jié)構(gòu)化程序設(shè)計理論中,已經(jīng)證明采用三大結(jié)構(gòu),可以解決任何復(fù)雜問題.其中順序結(jié)構(gòu)和循環(huán)結(jié)構(gòu)很好地體現(xiàn)了時空局部性,例外的選擇結(jié)構(gòu)在程序中實際占的比重是較小的.

基于局部性原理,幾乎所有的頁面置換算法總是試圖從當(dāng)前正在引用的頁面去＂預(yù)測＂將要引用的頁面,據(jù)此產(chǎn)生淘汰頁和置換頁.大多數(shù)情形下,這種預(yù)測的命中率可以很高.但對于特定的程序(如有大量的轉(zhuǎn)向語句的程序),命中率將很低,其結(jié)果很可能是所選擇的淘汰頁卻是即將要引用的頁;而從外存置換到內(nèi)存的頁面在最近很長時間卻不會被引用.不得已,繼續(xù)進行頁面置換,反反復(fù)復(fù),顛簸形成.

當(dāng)然,我們也容易知道與局部性原理背道而馳的頁面置換算法在大多數(shù)的情形下有可能產(chǎn)生顛簸.

2 顛簸的處理

顛簸一旦形成,CPU得不到有效利用,系統(tǒng)只是反復(fù)進行磁盤-內(nèi)存對換操作這等無用功.為解除之,調(diào)度程序不得已地必須對系統(tǒng)中諸進程重新予以調(diào)度.只能選擇掛起進程或者是撤消進程.這兩種方法的調(diào)度總代價都非常大.因此,首先應(yīng)盡量避免顛簸形成.

2.1 顛簸的預(yù)防

(1)局部置換

如果進程執(zhí)行時發(fā)生缺頁,約定只能從屬于本進程的物理塊中產(chǎn)生淘汰頁,而不允許從其它進程處獲得物理塊.如此,某個進程的顛簸不會引起其它進程的顛簸,可將顛簸框定在一個特定的、較小的范圍內(nèi).

當(dāng)然,這種方法并不理想.全局分配是保證分頁式系統(tǒng)性能的要素,這與局部分配本身是矛盾的;另外,它并不能從根本上防止顛簸,只能局限其范圍.如果某進程處于顛簸狀態(tài),則其將長期處于阻塞隊列,不斷地進行內(nèi)外存交換,又必然會影響其它進程進行缺頁處理.

(2)跟蹤缺頁率

根據(jù)局部性原理,絕大多數(shù)時候,進程是從一個局部區(qū)域轉(zhuǎn)移到另一個局部區(qū)域執(zhí)行.所以,必須有足夠的物理塊供使用,以減少缺頁,避免顛簸.到底應(yīng)為每個進程分配多少物理塊呢?實際上,它是系統(tǒng)擁有總的物理塊數(shù)與當(dāng)前系統(tǒng)實際應(yīng)用相關(guān)的一個經(jīng)驗值.這從缺頁率與所分配的物理塊數(shù)關(guān)系曲線得到證實.在拐點附近,每增加(減少)進程的物理塊數(shù)都能顯著地改變?nèi)表撀?而一定時候以后,即使再增加物理塊,缺頁率變化也不明顯.拐點左邊缺頁率非常高的區(qū)域就是本來的顛簸,拐點就是理想的物理塊數(shù)目.據(jù)此,可對系統(tǒng)中的進程定義其缺頁率的上限和下限閥值,此區(qū)間內(nèi)的物理塊數(shù)是進程擁有的相對合理的物理塊數(shù),缺頁率高于上限時說明其分配到的物理塊太少應(yīng)當(dāng)追加;而當(dāng)缺頁率低于下限時說明該進程所擁有的物理塊數(shù)太多,可收回一部分.

圖2 進程分配的物理塊與缺頁率關(guān)系

(3)調(diào)整頁面置換算法

頁面置換算法與實際應(yīng)用相關(guān),對于大多數(shù)的進程,與置換算法同時吻合了局部性原理,從而缺頁率低;而其余少數(shù)進程因與局部性原理相背,而使＂預(yù)測＂失效,其缺頁率偏高可能引發(fā)顛簸.

我們可以在一個系統(tǒng)中預(yù)備2種以上不同的選擇淘汰頁和置換頁策略的置換算法,并定義一缺頁率的閥值,處理程序中設(shè)置一開關(guān),當(dāng)缺頁率大于閥值時改用另一種置換算法.

(4)鎖定缺頁進程

具體做法是:在進程進行淘汰或置換時,總是將缺頁進程鎖定,不允許其換出頁,所調(diào)入的頁總是占據(jù)那些暫時得不到運行的進程所有的物理塊,這相當(dāng)于擴大了缺頁進程的工作集.

(5)其它考慮

進程的缺頁率實際上還與應(yīng)用者有關(guān).程序員如能設(shè)計恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu),將增加進程的局部性,從而降低缺頁率.下面的實例能精確說明這一問題.數(shù)組按行優(yōu)先順序存儲還是按列優(yōu)先順序存儲,其換頁次數(shù)是完全不同的.

所以,程序員也應(yīng)考慮程序的結(jié)構(gòu),盡量減少缺頁.

2.2 顛簸的解除

顛簸形成后,系統(tǒng)表現(xiàn)為:CPU利用率低,于是,調(diào)度程序又調(diào)入新的進程,CPU利用率又將變得更低.要解決這種局面,沒有選擇地只能調(diào)節(jié)系統(tǒng)的多道程序度.具體方法是:

(1)掛起進程

在Linux系統(tǒng)中,可設(shè)置CPU利用率的下限閥值,一旦低于此值,即“認(rèn)定”系統(tǒng)處于顛簸狀態(tài),從而檢查進程運行中的內(nèi)存資源使用情況.再根據(jù)某種選擇策略將阻塞隊列中某進程換至外存中掛起,以騰出內(nèi)存空間分配給顛簸的進程.反復(fù)如此,直至顛簸解除.

可每次掛起一批進程,這樣掛起的代價相對較小;較溫和的是每次掛起一個進程,但代價較大.被掛起的進程一般為優(yōu)先權(quán)較低的;當(dāng)內(nèi)存非常擁擠時,也可選擇優(yōu)先權(quán)相對較低卻占用物理塊較多的進程掛起,以便一次釋放較大的內(nèi)存空間;還可選擇尚需執(zhí)行時間最多的進程掛起等.

(2)撤消進程

選擇進程予以撤消,是解除顛簸最簡單最有效的方法,但代價也最大.與掛起進程類似,也可一次撤消一批進程或是一個進程,撤消進程時也應(yīng)考慮選擇策略.

對顛簸進行處理時必須注意兩個問題.其一是掛起(撤消)進程的代價問題.其二是饑餓現(xiàn)象.對于確定的選擇策略,從理論上說,某個進程可能每次都被選擇而被掛起(撤消),該進程將永遠(yuǎn)沒有執(zhí)行的機會.可以設(shè)置進程被選中的上限次數(shù)加以避免.

3 結(jié)束語

Linux是一個請求分頁系統(tǒng),沒有工作集的概念.由于是全局置換,當(dāng)系統(tǒng)總的物理塊數(shù)目不能滿足需要,而諸進程的卻競爭使用;在大多數(shù)時候性能優(yōu)良的頁面置換算法,對于極少數(shù)極端輸入;Linux本身固有的內(nèi)存分配機制都可能引起甚至直接觸發(fā)顛簸.

顛簸一旦形成,解除的代價總是非常大的,掛起或者撤消進程成為不得已的選擇,所以,應(yīng)盡量避免顛簸.

[1]ADAMS,K.,and AGESON.A Comparison of Software and Hardware Technqiues for X86 Virtualization[J].ACM,2006:2-13.

[2]Mark Allen Weiss,Data Structures and Algorithm A-nalysis in C 2nd ed[M].China Machine Press,2004.

[3](荷)Andrew S.Tanenbaum.現(xiàn)代操作系統(tǒng)[M].陳向群,馬洪兵譯,北京:機械工業(yè)出版社,2009.

[4]張堯?qū)W,史美林,張 高.計算機操作系統(tǒng)教程[M].北京:清華大學(xué)出版社,2006.

[5]Tie-nan Zhang,Tie-wu Liu The Cause and Treatment Strategy on Thrashing[C].Advanced M aterials Reasearch,2011,216(3).