大學設(shè)計方案方案工作集在頁面設(shè)置過程中應(yīng)用與分析

1、學號：20095101250本科畢業(yè)論文（設(shè)計）學院計算機與信息技術(shù)學院專業(yè) 計算機科學與技術(shù)專業(yè)年級2009級姓名 肖志英論文（設(shè)計）題目工作集在頁面設(shè)置過程中的應(yīng)用與分析指導教師柳春華職稱講師2013年5月4日目錄摘要 2Abstract2引論 21. 頁面置換算法 32. 工作集算法 32.1 研究背景與意義3抖動現(xiàn)象 3局部性原理 32.2 工作集頁面置換算法43. 工作集在頁面置換算法中的應(yīng)用 4 3.1 工作集頁面置換算法 4工作集模型 4工作集的性質(zhì)5工作集頁面置換算法的實現(xiàn)63.2 工作集時鐘頁面置換算法8參考文獻 9工作集在頁面設(shè)置過程中的應(yīng)用與分析學生姓名：肖志英學號： 2

2、0095101250計算機與信息技術(shù)學院計算機科學與技術(shù)專業(yè)指導教師：柳春華職稱：講師摘要： 操作系統(tǒng)的內(nèi)存管理一直是計算機領(lǐng)域研究的一個重要方向。文中分析了幾種常用內(nèi)存管理中的頁面置換算法極其存在的問題，提出了工作集頁面置換算法的操作系統(tǒng)內(nèi)存管理中的比較完美的一種頁面置換算法，并闡述了實現(xiàn)該頁面置換算法的原理及應(yīng)用。關(guān)鍵詞： 工作集模型；頁面置換；內(nèi)存管理；.Abstract:Memory management of operating system is a very important research direction in computer science field.In the

3、 paper,several widely-used page-replacement algorithms are introduced and their advantages/disadvantagesare analyzed.The research indicates that working set page-replacement is very close to the ideal one in memory management of operating system.Based on working set,which is used to relize the worki

4、ng set clock algorithms,is introduced and discussed in detail.Keywords:The working set model。 page replacement algorithm of the 。 memory management引論操作系統(tǒng)的內(nèi)存管理一直是計算機領(lǐng)域研究的一個重要方向，而內(nèi)存的虛存管理是存儲管理的核心。其原因在于內(nèi)存的價格昂貴，用大量的內(nèi)存存儲所有被訪問的程序與數(shù)據(jù)段是不可能的；而外存盡管訪問速度較慢，但價格便宜，適合于存放大量的信息。因此，在內(nèi)存有限的情況下，擴展一部分內(nèi)存作為虛擬內(nèi)存，真正的內(nèi)存只存儲當前運行

5、時所用得到的信息，這無疑咳咳大大擴充內(nèi)存的功能，并大大提高計算機的并發(fā)度。虛擬頁式存儲管理，就是將進程所需空間劃分為多個頁面，內(nèi)存中只存放當前所需頁面，其余頁面放入外存的管理的一種假內(nèi)存擴充方式。在程序執(zhí)行時，如果發(fā)現(xiàn)要訪問的頁面不在內(nèi)存，則系統(tǒng)產(chǎn)生缺頁中斷。缺頁中斷服務(wù)程序?qū)⒇撠煱盐挥诖疟P上的數(shù)據(jù)加載到物理內(nèi)存。虛擬頁式存儲管理雖然在某些程度上可以減少進程所需的內(nèi)存空間，但同時也會帶來運行時間變長的問題。進程在運行的過程中，不可避免地要把外存中存放的一些信息和內(nèi)存中已有的數(shù)據(jù)進行交換，由于內(nèi)外存運行速度的差異，這一步驟所發(fā)費的時間一般不可忽略，因而必須采取盡量好的算法來減少讀取外存的次數(shù)。1

6、. 頁面置換算法對于虛擬頁式存儲，內(nèi)外存信息的替換是以頁面為單位進行的。在進程運行過程中，若其所要訪問的頁面不在內(nèi)存時，就會產(chǎn)生缺頁中斷。當發(fā)生缺頁中斷時，需把所需頁調(diào)入內(nèi)存。若內(nèi)存已無空閑空間時，為了保證該進程能正常運行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送磁盤的對換區(qū)中，以便為即將調(diào)入的頁面但應(yīng)騰出空間。將哪個頁面調(diào)出，需根據(jù)一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法。2. 工作集算法2.1 研究背景與意義抖動現(xiàn)象頁面置換算法的好壞，直接影響系統(tǒng)的性能。若選用的算法不合適，可能會出現(xiàn)這樣的現(xiàn)象：剛被淘汰出去的頁，不久又要被訪問，又需把它調(diào)入而將另一頁淘汰出去，很可能又把

7、剛調(diào)入的或很快要用的頁淘汰出去了。如此反復頻繁地更換頁面，以致系統(tǒng)的大部分時間都花在頁面的調(diào)度和傳輸上了。系統(tǒng)的實際效率很低，這種現(xiàn)象稱為“抖動”。局部性原理通過對程序特性的觀察，發(fā)現(xiàn)進程對主存的訪問不是均勻的，而是高度地表現(xiàn)出局部性。它包含兩方面的內(nèi)容：時間局部性和空間局部性。（ 1）時間局部性：是指某個位置最近被訪問了，那么往往很快又要被再次訪問。這一特性可通過程序中的循環(huán)，常用子程序，堆棧，常用變量這類程序結(jié)構(gòu)來說明。（ 2）空間局部性：是指某個位置最近被訪問了，那么它最近的位置也要被訪問。這一特性可通過程序中數(shù)組處理、順序代碼的執(zhí)行，以及程序員傾向于將常用的變量存放在一起等特點來說明。

8、2.2 工作集頁面置換算法現(xiàn)代計算機系統(tǒng)中內(nèi)存的訪問速度遠遠高于外存的訪問速度，如果系統(tǒng)中不產(chǎn)生缺頁中斷，則訪問數(shù)據(jù)的時間約等于內(nèi)存訪問時間。但是如果發(fā)生缺頁中斷，則需要從外存中將該頁調(diào)入，在調(diào)頁過程中，進程由就緒狀態(tài)轉(zhuǎn)為等待狀態(tài)，因此會大大降低系統(tǒng)性能。如果缺頁頻率高，不但進程運行的速度很慢，大大增加了CPU 非生產(chǎn)機時的開銷，更增加了通道和外部設(shè)備的沉重負擔，從而降低了系統(tǒng)效率，甚至引起系統(tǒng)抖動，直至癱瘓。通過對缺頁率的長期研究， Denning 于 1968 年提出了工作集理論。由于程序在運行時對頁面的訪問是不均勻的 ( 即局部性 ) ，如果能夠預(yù)知程序在某段時間內(nèi)要訪問那些頁面，并將它

9、們提前調(diào)入內(nèi)存，這將降低缺頁率，提高CPU利用率。用來描述駐留在物理內(nèi)存中的虛擬頁面子集的術(shù)語叫做“工作集”。3.工作集在頁面置換算法中的應(yīng)用基于工作集的頁面置換算法有兩種，工作集頁面置換算法和工作集時鐘頁面置換算法。3.1 工作集頁面置換算法工作集模型在單純的分頁系統(tǒng)里，剛啟動進程時，在內(nèi)存中并沒有頁面。在CPU 試圖取第一條指令時就會產(chǎn)生一次缺頁中斷，使操作系統(tǒng)裝入含有第一條指令的頁面。其他由訪問全局數(shù)據(jù)和堆棧引起的缺頁中斷通常會緊接著發(fā)生。一段時間以后，進程需要的大部分頁面都已經(jīng)在內(nèi)存了，進程開始在較少缺頁中斷的情況下運行。這個策略稱為請求調(diào)頁（demand paging ），因為頁面是

10、在需要時被調(diào)入的，而不是預(yù)先裝入。編寫一個測試程序很容易，在一個大的地址空間中系統(tǒng)地讀所有的頁面，將出現(xiàn)大量的缺頁中斷，因此會導致沒有足夠的內(nèi)存來容納這些頁面。不過幸運的是，大部分進程不是這樣工作的，它們都表現(xiàn)出了一種局部性訪問行為，即在進程運行的任何階段，它都只訪問較少的一部分頁面。例如，在一個多次掃描編譯器中，各次掃描時只訪問所有頁面中的一小部分，并且是不同的部分。一個進程當前正在使用的頁面的集合稱為它的工作集（working set）。如果整個工作集都被裝入到了內(nèi)存中，那么進程在運行到下一運行階段（例如，編譯器的下一遍掃描）之前，不會產(chǎn)生很多缺頁中斷。若內(nèi)存太小而無法容納下整個工作集，那

11、么進程的運行過程中會產(chǎn)生大量的缺頁中斷，導致運行速度也會變得很緩慢，因為通常只需要幾個納秒就能執(zhí)行完一條指令，而通常需要十毫秒才能從磁盤上讀入一個頁面。如果一個程序每 10ms 只能執(zhí)行一到兩條指令，那么它將會需要很長時間才能運行完。若每執(zhí)行幾條指令程序就發(fā)生一次缺頁中斷，那么就稱這個程序發(fā)生了顛簸。在多道程序設(shè)計系統(tǒng)中，經(jīng)常會把進程轉(zhuǎn)移到磁盤上（即從內(nèi)存中移走所有的頁面），這樣可以讓其他的進程有機會占有 CPU。有一個問題是，當該進程再次調(diào)回來以后應(yīng)該怎樣辦？從技術(shù)的角度上講，并不需要做什么。該進程會一直產(chǎn)生缺頁中斷直到它的工作集全部被裝入內(nèi)存。然而，每次裝入一個進程時都要產(chǎn)生 20、100

12、甚至 1000次缺頁中斷，速度顯然太慢了，并且由于 CPU需要幾毫秒時間處理一個缺頁中斷，因此有相當多的 CPU時間也被浪費了。因此，如果能預(yù)知程序在某段時間間隔中所要訪問的那些頁，并在該段時間前就將該頁調(diào)入主存，至該段時間終了時，再將其中在下一段時間里不再訪問的那些頁調(diào)出主存。這樣可以大大減少頁的調(diào)入和調(diào)出工作，縮短等待調(diào)頁時間，降低缺頁頻率，從而能大大提高系統(tǒng)效率。工作集的性質(zhì)Denning 所提出的工作集，粗略的說，是進程在某段時間里實際上要訪問的頁的集合。 Denning 認為，程序要有效的運行，其工作集必須在主存中，但是如何確定一個進程在某個時間的工作集呢？實際上，計算機無法預(yù)知程序

13、的行為，也就是無法預(yù)知要訪問哪些頁。我們只能依據(jù)進程過去的行為來估計它未來的行為（這種估計的依據(jù)就是程序行為的局部化特性，決定了工作集的變化是緩慢的）。所以把一個運行進程在t-w 到 t 這個時間間隔內(nèi)所訪問的頁的集合稱為該進程在時間t 的工作集，記為W(t,w) 。并把變量 w 記為“工作集窗口尺寸”。通常還把工作集中所包含的頁面數(shù)目稱為“工作集尺寸”，記為W(t,w) ?？梢钥闯?，工作集W是二元函數(shù)。首先W是 t 的函數(shù)，即隨著時間不同，工作集頁不同。這包含兩方面的含義：（ 1）不同時間工作集所包含的頁面數(shù)可能不同，也就是工作集尺寸不同。（ 2）不同時間工作集所包含的頁面也可能不同。其次，

14、工作集 W也是工作集窗口尺寸 w 的函數(shù)。工作集尺寸 W是工作集窗口尺寸 w 的單調(diào)遞增函數(shù)，且滿足蘊含特性，即 W(t,w) W(t,w+a) , 其中a>0。圖 1描述了作為 t 的函數(shù)的工作集的大小。正確的選擇工作集窗口尺寸的大小對工作集存儲管理策略的有效工作是有很大影響的。如果w 選取過大，甚至把整個作業(yè)地址空間全部包含在內(nèi)，就失去了虛存的意義。 W選取過小，則將引起頻繁缺頁，降低了系統(tǒng)效率。 W(k,w) t圖 1 工作集是從 t-w 到 t 過程中所訪問過的頁面的集合，函數(shù) W(t,w) 是在時刻 t 時工作集的大小正確的策略并不是消除缺頁現(xiàn)象，而應(yīng)使缺頁間隔時間保持在合理水

15、平。當此間隔時間過小時，應(yīng)增加其頁框數(shù)。過大則應(yīng)增加多道程序，減少分給進程的頁框數(shù)，以提高整個系統(tǒng)的效率。因此應(yīng)把缺頁的間隔時間控制在合理的范圍，使分給進程的頁面數(shù)保持在上、下限之間。工作集頁面置換算法的實現(xiàn)基于工作集的頁面置換算法，基本思路就是找出一個不在工作集中的頁面并淘汰它。在圖 2中讀者可以看到某臺機器的部分頁表。因為只有那些在內(nèi)存中的頁面才可以作為候選者被淘汰，所以該算法忽略了那些不在內(nèi)存中的頁面。每個表項至少包含兩條信息：上次使用該頁面的近似時間和R（訪問）位?？瞻椎木匦伪硎驹撍惴ú恍枰钠渌?，如頁框號、保護位、M（修改）位。2204當前實際時間一個頁面的信息R(訪問 )位208

16、41上次使用的時間20031198011213020141202012032116200掃描所有頁面檢查R 位：若（ R= =1）設(shè)置上次使用時間為當前實際時間若（ R= =0 且生存時間w）移出這個頁面若（ R= =0 且生存時間w）記住最小時間圖 2工作集頁面置換算法該算法工作方式如下。如前所述，假定使用硬件來置R 位和 M 位。同樣，假定在每個工作集窗口尺寸中，有一個定期的時鐘中斷會用軟件方法來清除R位。每當缺頁中斷發(fā)生時，掃描頁表以找出一個合適的頁面淘汰之。在處理每個表項時，都需要檢查R 位。(1) 如果它是 1，就把當前實際時間寫進頁表項的“上次使用時間”域，以表示缺頁中斷發(fā)生時該頁

17、面正在被使用。既然該頁面在當前工作集窗口尺寸中已經(jīng)被訪問過，那么很明顯它應(yīng)該出現(xiàn)在工作集中，并且不應(yīng)該被刪除（假定t 橫跨多個時鐘滴答）。(2) 如果 R 是0，那么表示在當前時鐘滴答中，該頁面還沒有被訪問過，則它就可以作為候選者被置換。為了知道它是否應(yīng)該被置換，需要計算它的生存時間（即當前實際運行時間減去上次使用時間），然后與w 做比較。如果它的生存時間大于w，那么這個頁面就不再在工作集中，而用新的頁面置換它。掃描會繼續(xù)進行以更新剩余的表項。(3) 如果 R 是0同時生存時間小于或等于 w，則該頁面仍然在工作集中。這樣就要把該頁面臨時保留下來，但是要記錄生存時間最長（“上次使用時間”的最小值

18、）的頁面。如果掃描完整個頁表卻沒有找到適合被淘汰的頁面，也就意味著所有的頁面都在工作集中。在這種情況下，如果找到了一個或者多個R 0的頁面，就淘汰生存時間最長的頁面。在最壞情況下，在當前時間滴答中，所有的頁面都被訪問過了（也就是都有 R1），因此就隨機選擇一個頁面淘汰，如果有的話最好選一個干凈頁面。3.2 工作集時鐘頁面置換算法當缺頁中斷發(fā)生后，需要掃描整個頁表才能確定被淘汰的頁面，因此基本工作集算法是比較費時的。有一種改進的算法，它基于時鐘算法，并且使用了工作集信息，稱為WSClock（工作集時鐘）算法（ Carr 和 Hennessey，1981）。由于它實現(xiàn)簡單，性能較好，所以在實際工作

19、中得到了廣泛應(yīng)用。它所需的數(shù)據(jù)結(jié)構(gòu)是一個以頁框為元素的循環(huán)表，參見圖3-21a 。最初，該表是空的。當裝入第一個頁面后，把它加到該表中。隨著更多的頁面的加入，它們形成一個環(huán)。每個表項包含來自基本工作集算法的上次使用時間，以及 R 位（已標明）和 M位（未標明）。2204當前實際時間16200162002084120321208412032120031202012003120201198012014119801201401213 0上次使用時間R 位12130(a)(b)162001620020841208412032120321200312003120201202011980119801201

20、4120140220411213新頁面0(c)(d)圖 3工作集時鐘頁面置換算法的操作：(a) 和(b)給出在 R=1 時所發(fā)生的情形；(c)和(d)給出 R=0 的例子每次缺頁中斷時，首先檢查指針指向的頁面。如果R 位被置為 1，該頁面在當前時鐘滴答中就被使用過，那么該頁面就不適合被淘汰。然后把該頁面的R位置為 0，指針指向下一個頁面，并重復該算法。該事件序列之后的狀態(tài)參見圖 3-21b ?，F(xiàn)在來考慮指針指向的頁面在R=0時會發(fā)生什么，參見圖3-21c 。如果頁面的生存時間大于t 并且該頁面是干凈的，它就不在工作集中，并且在磁盤上有一個有效的副本。申請此頁框，并把新頁面放在其中，如圖3-21

21、d 所示。另一方面，如果此頁面被修改過，就不能立即申請頁框，因為這個頁面在磁盤上沒有有效的副本。為了避免由于調(diào)度寫磁盤操作引起的進程切換，指針繼續(xù)向前走，算法繼續(xù)對下一個頁面進行操作。畢竟，有可能存在一個舊的且干凈的頁面可以立即使用。原則上，所有的頁面都有可能因為磁盤I/O 在某個時鐘周期被調(diào)度。為了降低磁盤阻塞，需要設(shè)置一個限制，即最大只允許寫回n 個頁面。一旦達到該限制，就不允許調(diào)度新的寫操作。如果指針經(jīng)過一圈返回它的起始點會發(fā)生什么呢？這里有兩種情況：（ 1) 至少調(diào)度了一次寫操作。（ 2) 沒有調(diào)度過寫操作。對于第一種情況，指針僅僅是不停地移動，尋找一個干凈頁面。既然已經(jīng)調(diào)度了一個或者

22、多個寫操作，最終會有某個寫操作完成，它的頁面會被標記為干凈。置換遇到的第一個干凈頁面，這個頁面不一定是第一個被調(diào)度寫操作的頁面，因為硬盤驅(qū)動程序為了優(yōu)化性能可能已經(jīng)把寫操作重排序了。對于第二種情況，所有的頁面都在工作集中，否則將至少調(diào)度了一個寫操作。由于缺乏額外的信息，一個簡單的方法就是隨便置換一個干凈的頁面來使用，掃描中需要記錄干凈頁面的位置。如果不存在干凈頁面，就選定當前頁面并把它寫回磁盤。參考文獻：1 屠立德 . 操作系統(tǒng)基礎(chǔ)M. 北京：清華大學出版社，1987.11:133-136.2 湯小丹，梁紅兵，哲鳳屏，湯子灜. 計算機操作系統(tǒng) M.3 版 . 西安：西安電子科技大學出版社， 2

23、007.5:142-155.3 陳向群，馬洪兵 . 現(xiàn)代操作系統(tǒng) M.3 版 . 北京：機械工業(yè)出版社， 2009:118-120.4 龐麗萍 . 操作系統(tǒng)原理 M.3 版 . 武漢：華中科技大學出版社， 1988： 162-164.5 劉道斌 , 白碩 . 基于工作流狀態(tài)的動態(tài)訪問控制 J. 計算機研究與發(fā)展， 2003， 40417-421.6 李東波，徐平，韓祥蘭 . 基于專家系統(tǒng)的工作流管理系統(tǒng)模型研究 J. 南京理工大學學報，2001； 25(1) ： 96-997 曹化工，楊曼紅 . 基于對象 Petri 網(wǎng)的工作流過程定義 J. 汁算機軸助設(shè)計與圖形學學報， 2001：13(1)

24、 ： 13-188 張曉東，柴躍廷，任守榘 . 基于業(yè)務(wù)規(guī)則的事件驅(qū)動建模方法J. 清華大學學報，1999； 399 汪利寶，王更生，李宋 . 數(shù)據(jù)庫加密設(shè)計及其安全體系研究 J. 江西南昌 : 計算機與現(xiàn)代化.2004.6,23-2410 鄭惠生，宋秀琴，郝長勝 . 基于 ASP 的網(wǎng)絡(luò)學生信息管理系統(tǒng) J. 遼寧阜新：遼寧工程技術(shù)大學學報 ( 自然科學版 ).2006Vol.2511WorkflowManagementCoalition,WfMC-TC-1019,WorkflowSecurityConsiderationsWhitePaperS. 1998.12WorkflowManage

25、mentCoalition,WfMC-TC00-1003,the Workflow Reference ModelS.1995.13DiimitriosGeorgakopoulos,MarkHornick,AmitSheth.Anoverviewofworkflowmanagmanagement: from Process modeling to workflow automation infrastructureJ.Distributed and Parallel Databases,1995, 3(2):119153.14Sandhu R, Samarati. Access control principle and practiceJ. Communications Magazine, IEEE, 1994. 32(9): 4048.15Department of Defense. DOD5200.28-STD, Trusted