1、 棗 莊 學 院信息科學與工程學院課程設計任務書 題目： 頁面置換算法 學 號： 201012110128 姓 名： 秦云 （武艷飛、孔軍利、李璐、姜曉美） 專 業： 計算機科學與技術 課 程： 操作系統 指導教師： 劉彩霞 職稱： 講師 完成時間： 2012年5月-2012年6月棗莊學院信息科學與工程學院制課程設計任務書及成績評定課程設計的任務和具體要求：課程設計的任務：用所學方法設計頁面置換算法課程設計的具體要求：（1） 分析設計法案，給出解決方案；（2） 對程序有詳細的設計說明；（3） 畫出流程圖；（4） 設計的心得體會 指導教師簽字： 日期： 指導教師評語： 成績： 指導教師簽字： 日

2、期： 課程設計所需軟件、硬件等硬件 cpu：intel t2080d-0 內存：2g 硬盤空間：320g軟件 操作系統：windows xp linux虛擬機課程設計進度計劃起至日期工作內容備注2012.5.1-2012.5.72012.5.8-2012.5.152012.5.16-2012.5.312012.6.1-2012.6.10 確定課題并搜集資料 設計方案練習編寫程序程序設計系統測試并寫設計說明書參考文獻、資料索引序號文獻、資料名稱編著者出版單位1 李善平等. linux內核2.4版源代碼分析大全. 北京：機械工業出版社，2002.12 陳莉君. 深入分析linux內核源代碼. 北京

3、：人民郵電出版社，2002.83 陳向群 編著.操作系統教程.北京：北京大學出版社，2007.014 羅宇 等編著.操作系統課程設計.北京：機械工業出版社，2005.95 gary nutt.linux操作系統內核實習. 北京：機械工業出版社，2002.1 摘 要在地址映射過程中，若在頁面中發現所要訪問的頁面不再內存中，則產生缺頁中斷。當發生缺頁中斷時操作系統必須在內存選擇一個頁面將其移出內存，以便為即將調入的頁面讓出空間。而用來選擇淘汰哪一頁的規則叫做頁面置換算法。在進程運行過程中，若其所要訪問的頁面不在內存需把它們調入內存，但內存已無空閑空間時，為了保證該進程能正常運行，系統必須從內存中調

4、出一頁程序或數據，送磁盤的對換區中。但應將哪個頁面調出，所以需要根據一定的算法來確定。常用的算法有先進先出置換算法（fifo）, 最近最久未使用置換算法（lru）和最佳置換算法（opt），該設計是在vc+6.0環境下分別用lru和fifo來實現頁面置換算法的模擬程序，并測試。關鍵詞：操作系統; 頁面置換算法模擬; 進程調度; fifo; lru 目 錄第1章 課題背景11.1 關于頁面置換算法11.1.1頁面置換算法及其分類11.1.2關于頁面置換算法模擬程序問題的產生11.2相關知識21.2.1虛擬存儲器的引入21.2.2虛擬存儲器的定義21.2.3虛擬存儲器的實現方式21.2.4頁面分配2

5、第2章 設計簡介及設計方案論述32.1程序運行平臺32.2設計思想32.3總體實驗流程圖4第3章 實驗程序53.1 fifo算法53.2 lru算法6第4章 實驗結果84.1 fifo(四內存塊)84.2 lru(五內存塊)8總 結9參考文獻10第1章 課題背景1.1 關于頁面置換算法1.1.1頁面置換算法及其分類在地址映射過程中，若在頁面中發現所要訪問的頁面不再內存中，則產生缺頁中斷。當發生缺頁中斷時操作系統必須在內存選擇一個頁面將其移出內 存，以便為即將調入的頁面讓出空間。而用來選擇淘汰哪一頁的規則叫做頁面置換算法。 常見的置換算法有： 1最佳置換算法（opt）（理想置換算法） 2先進現出

6、置換算法（fifo）： 3最近最久未使用（lru）算法 4clock置換算法（lru算法的近似實現） 5最少使用（lfu）置換算法 6頁面緩沖置換算法1.1.2關于頁面置換算法模擬程序問題的產生在各種存儲器管理方式中，有一個共同的特點，即它們都要求將一個作業全部裝入內存方能運行，但是有兩種情況：（1） 有的作業很大，不能全部裝入內存，致使作業無法運行；（2） 有大量作業要求運行，但內存容量不足以容納所有這些作業。而虛擬內存技術正式從邏輯上擴充內存容量，將會解決以上兩個問題。從內存中調出一頁程序或數據送磁盤的對換區中，通常，把選擇換出的頁面的算法稱為頁面置換算法（page-replacement

7、 algorithms）。進而頁面置換算法模擬程序能客觀的將其工作原理展現在我們面前。1.2相關知識1.2.1虛擬存儲器的引入局部性原理：程序在執行時在一較短時間內僅限于某個部分；相應的，它所訪問的存儲空間也局限于某個區域，它主要表現在以下兩個方面：時間局限性和空間局限性。1.2.2虛擬存儲器的定義虛擬存儲器是只具有請求調入功能和置換功能，能從邏輯上對內存容量進行擴充的一種存儲器系統。1.2.3虛擬存儲器的實現方式分頁請求系統，它是在分頁系統的基礎上，增加了請求調頁功能、頁面置換功能所形成的頁面形式虛擬存儲系統。 請求分段系統，它是在分段系統的基礎上，增加了請求調段及分段置換功能后，所形成的段

8、式虛擬存儲系統。1.2.4頁面分配平均分配算法，是將系統中所有可供分配的物理塊，平均分配給各個進程。 按比例分配算法，根據進程的大小按比例分配物理塊。考慮優先的分配算法，把內存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據個進程的優先權，適當的增加其相應份額后，分配給各進程。 第2章 設計簡介及設計方案論述2.1程序運行平臺vc+6.0具體操作如下：在vc+6.0的環境下準備用時鐘函數調用庫函數（#include ）、 取時鐘時間并存入t調用庫函數（t=time(null)）、 用時間t初始化隨機數發生器調用 庫函數（srand(t)返回一個110之間的隨機數（x

9、=rand( )%10+1） 。編寫三種算法。2.2設計思想 選擇置換算法，先輸入所有頁面號，為系統分配物理塊，依次進行置換：opt基本思想：是用一維數組pagepsize存儲頁面號序列，memerymsize是存儲裝入物理塊中的頁面。數組nextmsize記錄物理塊中對應頁面的最后訪問時間。每當發生缺頁時，就從物理塊中找出最后訪問時間最大的頁面，調出該頁，換入所缺的頁面。【特別聲明】若物理塊中的頁面都不再使用，則每次都置換物理塊中第一個位置的頁面。fifo基本思想：是用隊列存儲內存中的頁面，隊列的特點是先進先出，與該算法是一致的，所以每當發生缺頁時，就從隊頭刪除一頁，而從隊尾加入缺頁。或者借

10、助輔助數組timemsize記錄物理塊中對應頁面的進入時間，每次需要置換時換出進入時間最小的頁面。lru基本思想：是用一維數組pagepsize存儲頁面號序列，memerymsize是存儲裝入物理塊中的頁面。數組flag10標記頁面的訪問時間。每當使用頁面時，刷新訪問時間。發生缺頁時，就從物理塊中頁面標記最小的一頁，調出該頁，換入所缺的頁面。2.3總體實驗流程圖如圖2-1所示:否調入所訪問的頁面按算法不同淘汰一頁面置缺頁標志flag為*是是否缺頁？查頁表取訪問的頁號輸入頁面訪問序列 圖2-1程序流程圖第3章 實驗程序3.1 fifo算法#include stdio.h#define n 20#

11、define m 4void main()int ymn,i,j,q,memm=0,tablemn;char flag,fn;printf(請輸入頁面訪問序列n);for(i=0;in;i+) scanf(%d,&ymi);printf(n);for(i=0;i0;j-) /淘汰最先調入的頁面調入當前訪問的 memj=memj-1; mem0=ymi; for(j=0;jm;j+) tableji=memj; fi=flag; printf(輸出結果為下表（0代表為空，*代表有缺頁）：n); for(i=0;im;i+) for(j=0;jn;j+)printf(%3d,tableij);pr

12、intf(n); for(i=0;in;i+) printf(%3c,fi);3.2 lru算法#include stdio.h#define n 20#define m 5void main()int ymn,i,j,q,memm=0,tablemn;char flag,fn;printf(請輸入頁面訪問序列n);for(i=0;in;i+) scanf(%d,&ymi);printf(n);for(i=0;i0;j-) memj=memj-1; mem0=ymi; for(j=0;jm;j+) tableji=memj; fi=flag; printf(輸出結果為下表（0代表為空，*代表有

13、缺頁）：n); for(i=0;im;i+) for(j=0;jn;j+)printf(%3d,tableij);printf(n); for(i=0;in;i+) printf(%3c,fi);第4章 實驗結果4.1 fifo(四內存塊)如圖4-1所示:圖4-1四塊內存圖4.2 lru(五內存塊)如圖4-2所示: 圖4-2五塊內存圖總 結通過對頁面置換算法模擬程序的程序設計，讓我對虛擬頁式存儲管理有了更深的了解。剛開始拿到這個題目覺得很難，不知道該怎么下手，因為是自己第一次用c語言編寫操作系統程序。但是搞懂了頁面置換的思想以后，對編程就有了一定的思路。經過幾天的編寫，程序也終于寫出來啊。但是卻遇到了許多困難，程序的調試也出現了許多的錯誤。但是經過幾次上機操作，在老師的指導和幫助下，程序最終還是完成了。通過這次的程序設計，讓我對c語言有了更深一步的了解和認識，編程能力也有了提高，我認到學好計算機要重視實踐操作，只有真正動手了才知道自己