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

2、0095101250計算機與信息技術學院計算機科學與技術專業指導教師：柳春華職稱：講師摘要： 操作系統的內存管理一直是計算機領域研究的一個重要方向。文中分析了幾種常用內存管理中的頁面置換算法極其存在的問題，提出了工作集頁面置換算法的操作系統內存管理中的比較完美的一種頁面置換算法，并闡述了實現該頁面置換算法的原理及應用。關鍵詞： 工作集模型；頁面置換；內存管理；.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引論操作系統的內存管理一直是計算機領域研究的一個重要方向，而內存的虛存管理是存儲管理的核心。其原因在于內存的價格昂貴，用大量的內存存儲所有被訪問的程序與數據段是不可能的；而外存盡管訪問速度較慢，但價格便宜，適合于存放大量的信息。因此，在內存有限的情況下，擴展一部分內存作為虛擬內存，真正的內存只存儲當前運行

5、時所用得到的信息，這無疑咳咳大大擴充內存的功能，并大大提高計算機的并發度。虛擬頁式存儲管理，就是將進程所需空間劃分為多個頁面，內存中只存放當前所需頁面，其余頁面放入外存的管理的一種假內存擴充方式。在程序執行時，如果發現要訪問的頁面不在內存，則系統產生缺頁中斷。缺頁中斷服務程序將負責把位于磁盤上的數據加載到物理內存。虛擬頁式存儲管理雖然在某些程度上可以減少進程所需的內存空間，但同時也會帶來運行時間變長的問題。進程在運行的過程中，不可避免地要把外存中存放的一些信息和內存中已有的數據進行交換，由于內外存運行速度的差異，這一步驟所發費的時間一般不可忽略，因而必須采取盡量好的算法來減少讀取外存的次數。1

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

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

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

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

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

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

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

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

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

15、平。當此間隔時間過小時，應增加其頁框數。過大則應增加多道程序，減少分給進程的頁框數，以提高整個系統的效率。因此應把缺頁的間隔時間控制在合理的范圍，使分給進程的頁面數保持在上、下限之間。工作集頁面置換算法的實現基于工作集的頁面置換算法，基本思路就是找出一個不在工作集中的頁面并淘汰它。在圖 2中讀者可以看到某臺機器的部分頁表。因為只有那些在內存中的頁面才可以作為候選者被淘汰，所以該算法忽略了那些不在內存中的頁面。每個表項至少包含兩條信息：上次使用該頁面的近似時間和R（訪問）位。空白的矩形表示該算法不需要的其他域，如頁框號、保護位、M（修改）位。2204當前實際時間一個頁面的信息R(訪問 )位208

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

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

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

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

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

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

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

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

24、 ： 13-188 張曉東，柴躍廷，任守榘 . 基于業務規則的事件驅動建模方法J. 清華大學學報，1999； 399 汪利寶，王更生，李宋 . 數據庫加密設計及其安全體系研究 J. 江西南昌 : 計算機與現代化.2004.6,23-2410 鄭惠生，宋秀琴，郝長勝 . 基于 ASP 的網絡學生信息管理系統 J. 遼寧阜新：遼寧工程技術大學學報 ( 自然科學版 ).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