請(qǐng)求分頁(yè)式系統(tǒng)設(shè)計(jì)的性能保證

劉鐵武,李 峰

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

請(qǐng)求分頁(yè)式系統(tǒng)設(shè)計(jì)的性能保證

劉鐵武,李 峰

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

請(qǐng)求分頁(yè)式是當(dāng)今應(yīng)用最為廣泛的虛擬存儲(chǔ)技術(shù).要保證其獲得良好的性能,僅關(guān)心頁(yè)面置換算法是不夠的,還必須關(guān)注諸如存儲(chǔ)器分配策略、頁(yè)面大小、程序結(jié)構(gòu)等多個(gè)方面.請(qǐng)求分頁(yè)式系統(tǒng)的理論依據(jù)是局部性原理,在此基礎(chǔ)上,結(jié)合已有研究成果,從設(shè)計(jì)者和應(yīng)用者的角度著重就其中幾個(gè)因素進(jìn)行了討論和研究,力求在理論上得出一般性的結(jié)論.

請(qǐng)求分頁(yè);性能;顛簸;全局分配

操作系統(tǒng)中管理分層存儲(chǔ)器體系的存儲(chǔ)管理器的任務(wù)是有效地管理內(nèi)存,即記錄當(dāng)前哪些內(nèi)存正被使用,哪些內(nèi)存是空閑的;對(duì)進(jìn)程的內(nèi)存需求進(jìn)行分配和回收.限于物理內(nèi)存,使用重疊與動(dòng)態(tài)綁定,雖可在程序執(zhí)行時(shí)不需要將整個(gè)程序都加載,但在存儲(chǔ)管理器的設(shè)計(jì)中會(huì)增加很多額外工作,亦會(huì)造成維護(hù)與擴(kuò)展困難.當(dāng)前主流操作系統(tǒng)廣泛采用支持多道程序的虛擬存儲(chǔ)技術(shù),有請(qǐng)求分頁(yè)式、請(qǐng)求分段式和段頁(yè)式等,市場(chǎng)份額最大的是請(qǐng)求分頁(yè)式.

請(qǐng)求分頁(yè)式技術(shù)的要點(diǎn)是僅調(diào)入每個(gè)進(jìn)程的一部分頁(yè).1968年P(guān).Denning提出的局部性原理指出,程序在執(zhí)行時(shí)將呈現(xiàn)時(shí)間局限性和空間局限性.亦即,大多時(shí)候,將要執(zhí)行的頁(yè)可預(yù)知,這為虛擬存儲(chǔ)技術(shù)的實(shí)現(xiàn)提供了理論依據(jù).另一方面,由于僅調(diào)入部分頁(yè),實(shí)際執(zhí)行時(shí)必定產(chǎn)生缺頁(yè),缺頁(yè)處理的效率實(shí)質(zhì)上就是存儲(chǔ)管理器的性能,可用有效訪問(wèn)時(shí)間T衡量.

其中,p是缺頁(yè)率,m是內(nèi)存訪問(wèn)時(shí)間,d是磁盤(pán)訪問(wèn)時(shí)間.硬件特性決定,m和d是不同數(shù)量級(jí)的,m＜＜d可知,有效訪問(wèn)時(shí)間正比于缺頁(yè)率,降低缺頁(yè)率是提高性能的關(guān)鍵.反之,將增加有效訪問(wèn)時(shí)間,大幅延遲進(jìn)程的處理時(shí)間.

頁(yè)面置換算法是決定缺頁(yè)率大小的機(jī)制,正因?yàn)椴皇撬袑⒁獔?zhí)行的頁(yè)面都可預(yù)知,所以任何一個(gè)實(shí)用置換算法并不能保證缺頁(yè)率達(dá)到理論最小,這就為人們研究置換算法提供了空間,人們已研究出許多不同目標(biāo)函數(shù)的置換算法.

實(shí)質(zhì)上,決定缺頁(yè)率大小的除了置換算法還有其它諸多因素,它們是操作系統(tǒng)設(shè)計(jì)者必須考慮的,本文從頁(yè)面、物理塊的分配、頁(yè)面調(diào)入與清除策略、負(fù)載控制、程序的結(jié)構(gòu)等方面進(jìn)行了研究和討論,從理論和實(shí)踐上得出了其一般性結(jié)論.

1 頁(yè) 面

面的大小應(yīng)適當(dāng);應(yīng)支持頁(yè)面共享.

1.1 頁(yè)面的大小

最佳頁(yè)面的大小是由幾個(gè)互相矛盾的因素決定的,故不存在全局最優(yōu).一方面,對(duì)于任一進(jìn)程,其正文段、數(shù)據(jù)段和堆棧段不恰好裝滿(mǎn)頁(yè)面,平均情形下,有一半是空的,所以選擇小頁(yè)面內(nèi)部碎片較小.但另一方面,頁(yè)面小意味著需要更多的頁(yè)面,所需要的頁(yè)表項(xiàng)更多,頁(yè)表也更長(zhǎng);并且與外存交換頁(yè)面的次數(shù)相對(duì)更多,因?yàn)槊看蝺?nèi)外存交換大部分時(shí)間用于尋道和旋轉(zhuǎn)延遲,所以時(shí)間開(kāi)銷(xiāo)更大.下面的數(shù)學(xué)分析可得出理論上的頁(yè)面最佳值.

設(shè)進(jìn)程的平均大小為s字節(jié),頁(yè)面大小為p字節(jié),每頁(yè)表項(xiàng)占e字節(jié),k為總開(kāi)銷(xiāo),則 k=se/p+p/2

我父親說(shuō)，從前——幾世紀(jì)還是幾年以前——巴比倫的彩票是帶有平民性質(zhì)的賭博。他說(shuō)（我不知道是否真實(shí)），理發(fā)師發(fā)售彩票，收的是銅幣，給的是繪有符號(hào)的長(zhǎng)方形骨片或羊皮紙。大白天抽簽開(kāi)彩：中彩的人憑票領(lǐng)取銀幣。顯而易見(jiàn)，手續(xù)非常簡(jiǎn)單。

對(duì)p一階求導(dǎo),令右邊等于0得極值

現(xiàn)在CPU速度越來(lái)越快,為減少外存訪問(wèn)次數(shù),采用較大的分頁(yè)可能是更好的選擇.

1.2 頁(yè)面共享

多道系統(tǒng)中,不同的用戶(hù)運(yùn)行同一程序是很常見(jiàn)的.顯然,在內(nèi)存中保存多個(gè)副本不是好方法,頁(yè)面共享效率更高.但并非所有的頁(yè)面都適合共享,如只讀的頁(yè)面可共享而數(shù)據(jù)頁(yè)面卻不需要共享.

共享的實(shí)現(xiàn)方法可多種,PDP-11就是一范本.其主要思想是將指令空間和數(shù)據(jù)空間分離,多個(gè)進(jìn)程使用相同的指令空間頁(yè)表和不同的數(shù)據(jù)空間頁(yè)表以實(shí)現(xiàn)共享.

2 物理塊的分配

2.1 最少物理塊數(shù)

保證進(jìn)程能運(yùn)行的最少物理塊數(shù)目是由CPU的結(jié)構(gòu)和指令的結(jié)構(gòu)所決定的.指令由操作碼和操作數(shù)構(gòu)成.一般的微計(jì)算機(jī)的指令的存儲(chǔ)位不超過(guò)8位,但某些功能強(qiáng)大的計(jì)算機(jī)其指令超過(guò)256,亦即指令存儲(chǔ)位可能是2個(gè)甚至更多的字節(jié),則指令本身可能跨越2個(gè)頁(yè)面.而一條指令又可以有多個(gè)操作數(shù)(如0,1,2,3等),如采用間接尋址方式,每個(gè)操作數(shù)需要2個(gè)頁(yè)面.所以,進(jìn)程所需最少物理塊數(shù)就是一條指令可能跨越的頁(yè)面數(shù)的最大值.如對(duì)一般的微計(jì)算機(jī),指令最多有3個(gè)操作數(shù)時(shí)所需的最少物理塊為7.

2.2 局部分配與全局分配

一般地,在討論頁(yè)面置換算法時(shí),都回避了怎樣在相互競(jìng)爭(zhēng)內(nèi)存的進(jìn)程間分配內(nèi)存這一問(wèn)題,如當(dāng)產(chǎn)生缺頁(yè)中斷時(shí),淘汰頁(yè)到底從本進(jìn)程產(chǎn)生還是從系統(tǒng)的所有的進(jìn)程中產(chǎn)生值得商榷,理論上,每個(gè)進(jìn)程分配的物理塊更多,其缺頁(yè)率更低,但當(dāng)達(dá)到一定數(shù)量后,再繼續(xù)增加進(jìn)程的物理塊并不能顯著地改善其缺頁(yè)率,我們稱(chēng)這時(shí)進(jìn)程物理塊富余.進(jìn)程實(shí)際運(yùn)行時(shí),工作集的大小可能隨時(shí)間發(fā)生變化,如采用局部分配,進(jìn)程可能有時(shí)物理塊富余,而有時(shí)又物理塊緊張而導(dǎo)致抖動(dòng).

所以,一般全局分配方式性能更優(yōu),可以增加許多分頁(yè)替換的選擇,平衡系統(tǒng)資源.

3 頁(yè)面調(diào)入與清除

3.1 頁(yè)面調(diào)入策略

進(jìn)程開(kāi)始運(yùn)行,必須調(diào)入待執(zhí)行的頁(yè).有兩種調(diào)頁(yè)策略:一是當(dāng)進(jìn)程執(zhí)行,發(fā)現(xiàn)所需頁(yè)面不在內(nèi)存時(shí),由系統(tǒng)將對(duì)應(yīng)頁(yè)面調(diào)入的請(qǐng)求調(diào)頁(yè);另一種是根據(jù)預(yù)測(cè),將可能要執(zhí)行的一批頁(yè)面預(yù)先調(diào)入的預(yù)調(diào)頁(yè).

請(qǐng)求調(diào)頁(yè)能保證調(diào)入的頁(yè)面會(huì)馬上執(zhí)行,并且容易實(shí)現(xiàn).但每次僅調(diào)入一頁(yè),增加了磁盤(pán)啟動(dòng)的頻率,開(kāi)銷(xiāo)大.預(yù)調(diào)頁(yè)每次調(diào)入一批頁(yè)面,磁盤(pán)啟動(dòng)次數(shù)較少,又因?yàn)槊看握{(diào)入的是相鄰的頁(yè)面,磁盤(pán)尋道時(shí)間少,當(dāng)然其前提是預(yù)測(cè)的命中率.高命中率的預(yù)調(diào)頁(yè)算法是值得我們研究的.

3.2 清除策略

當(dāng)頁(yè)面被選中為淘汰頁(yè)時(shí),該頁(yè)在前面過(guò)程中可能被引用,也可能尚未被引用.而被引用的頁(yè)可能被修改也可能沒(méi)有.一般說(shuō)來(lái),如果頁(yè)面未被修改,直接覆蓋該淘汰頁(yè)即可,而如果修改過(guò),則應(yīng)將其寫(xiě)回磁盤(pán).總之,應(yīng)有一數(shù)據(jù)結(jié)構(gòu)記錄當(dāng)前頁(yè)面的使用情況.

4 負(fù)載控制

當(dāng)CPU使用率較低時(shí),CPU調(diào)度器為提高CPU利用率,通常是提高系統(tǒng)的多道程序度,也就是根據(jù)調(diào)度準(zhǔn)則,從后備輸入隊(duì)列中選擇一個(gè)進(jìn)程加載到內(nèi)存中.而正是因?yàn)檫@一進(jìn)程的加入,會(huì)導(dǎo)致系統(tǒng)缺頁(yè)率的上升.以物理塊的全局分配為例來(lái)看,新加載的進(jìn)程可能會(huì)搶占其它進(jìn)程的物理塊,以求得正常運(yùn)行.不難想到,如果一味追求CPU利用率,不斷增加多道程序度,系統(tǒng)必然產(chǎn)生顛簸現(xiàn)象.

一般地,多道程序度增多,CPU利用率隨之增長(zhǎng).但到了一定時(shí)候,增長(zhǎng)幅度趨緩;如再繼續(xù)增加多道程序度,將發(fā)生顛簸現(xiàn)象,CPU利用率急劇下降.一旦發(fā)生顛簸,最好的方法是將一部分進(jìn)程交換到磁盤(pán),這時(shí)多道程序度降低了.值得一提的是,將哪個(gè)進(jìn)程交換出去,不光要考慮進(jìn)程的大小和缺頁(yè)率,還要考慮其它特性,如它是CPU密集型還是I/O密集型的等.

所以,一定要合理控制系統(tǒng)的的負(fù)載.Denning于1980年就提出了"L=S準(zhǔn)則",用以調(diào)整和決定多道程序度,許多研究人員已證明了這一準(zhǔn)則的價(jià)值.

5 其它考慮

5.1 程序的結(jié)構(gòu)

系統(tǒng)的性能不但與設(shè)計(jì)者有密切關(guān)系,實(shí)際上還與應(yīng)用者有關(guān).程序員如能設(shè)計(jì)恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu),將增加進(jìn)程的局部性,從而降低缺頁(yè)率.這從下面的實(shí)例來(lái)說(shuō)更明確.設(shè)分頁(yè)大小為1K,對(duì)于一512512的整型數(shù)組,每個(gè)元素占2字節(jié),如果是按行優(yōu)先順序存儲(chǔ),則每行占用一個(gè)分頁(yè),共占用512個(gè)分頁(yè).下圖是對(duì)其初始化的C程序段.

內(nèi)存循環(huán)在一個(gè)頁(yè)面內(nèi)工作,雙層循環(huán)共發(fā)生了512頁(yè)置換;但如果改為a[j][i]=0,則共有512×512次頁(yè)面置換.

5.2 實(shí)時(shí)系統(tǒng)

實(shí)時(shí)任務(wù)要求進(jìn)程在取得CPU執(zhí)行權(quán)后,在規(guī)定的時(shí)限下完成.但虛擬存儲(chǔ)機(jī)制下,進(jìn)程執(zhí)行過(guò)程中,必須等待某些頁(yè)置換入內(nèi)存,而這種置換還與系統(tǒng)的其它進(jìn)程有關(guān).換言之,其時(shí)間延遲不可預(yù)知.所以,實(shí)時(shí)系統(tǒng)不宜采用虛擬存儲(chǔ)系統(tǒng).

6 結(jié)束語(yǔ)

請(qǐng)求分頁(yè)式存儲(chǔ)管理技術(shù)是現(xiàn)代操作系統(tǒng)主流的虛擬存儲(chǔ)技術(shù),其理論依據(jù)是P.Denning的局部性原理.提高系統(tǒng)的性能是設(shè)計(jì)者和應(yīng)用者始終追求的目標(biāo),究其根本,其性能就是缺頁(yè)率的高低.它本身是由多個(gè)因素決定的,既依賴(lài)于設(shè)計(jì)者,還與應(yīng)用者有關(guān).它們都是性能提升的必要條件,僅對(duì)某一方面孜孜以求,結(jié)果將是“大馬拉小車(chē)”.

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

[2]Liu Huai,Fei Shu-min.A Fault-tolerant Scheduling Algorithm Based on EDF for Distributed Control Systems[J].Journal of Software,2003,14(8):1371-1378.

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

[4]薛智文.操作系統(tǒng)[M].北京:中國(guó)鐵道出版社,2003.

[5]湯子瀛,哲風(fēng)屏,湯小丹.計(jì)算機(jī)操作系統(tǒng)[M].陜西:西安電子科技大學(xué)出版社,1996.

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

[7]Inline Assembly for X86 in Linux http://www-106.ibm.com/developerworks/Linux/library/l-ia.html[EB/OL].

The Performance Guaranty of Demand Paging System

LIU Tie-wu,LI Feng

(Computer and Communication School,Hunan Institute of Engineering,Xiangtan 411104,China)

T he demand paging is the most widely used virtual memory technology today.To get the better performance,it not only needs caring for the page replacement algorithm,but also needs paying attention to other aspects such as allocating policy of memory,size of page and program structure.Based on the local principle and combined with the existing research results,some inner factors are discussed and analysed from the perspective of designer and utilizer,striving to get the general conclusion in theory.

demand paging;performance;thrashing;global allocation

TP302

A

1671-119X(2011)02-0046-03

2010-09-26

湖南省教育廳科研資助項(xiàng)目(09C271)

劉鐵武(1966-),男,高級(jí)講師,研究方向:數(shù)據(jù)結(jié)構(gòu)與算法.