院系：計算機學院
實驗課程：計算機作業系統實驗
實驗名稱：模擬作業系統的頁面置換
指導老師：陳紅英
開課時間：2011 ～ 2023年度第 2學期
專業：網路工程
班級：10 級5班
學生：袁沛權
學號：20102100109
華南師範大學教務處
實驗二模擬作業系統的頁面置換
一、實驗目的
1、通過這次實驗，加深對虛擬記憶體頁面置換概念的理解，進一步掌握先進先出fifo，最佳置換opi和最近最久未使用lru頁面置換演算法的實現方法。
2、掌握作業系統的頁面置換過程，加深理解頁式虛擬儲存器的實現原理。
3、掌握用隨機數生成滿足一定條件的指令位址流的方法。
4、掌握頁面置換的模擬方法。
二、實驗內容與主要設計思想
1、 採用一種熟悉的語言，如c、pascal 或c++等，編制程式，最好關鍵
**採用c/c++，介面設計可採用其它自己喜歡的語言。
2、 模擬作業系統採用opt、fifo 和lru 演算法進行頁面置換的過程。
3、 設程式中位址範圍為0 到32767，採用隨機數生成256 個指令位址，滿
足50%的位址是順序執行，25%向前跳，25%向後跳。為滿足上述條件，
可採取下列方法：設d0=10000，第n個指令位址為dn，第n+1 個指令位址
為dn+1，n的取值範圍為0 到255。每次生成乙個1 到1024 範圍內的隨機
數a，如果a落在1 到512 範圍內，則dn+1=dn+1。如果a落在513 到768
範圍內，則設定dn+1為1 到dn範圍內乙個隨機數。如果a落在769 到1024
範圍內，則設定dn+1為dn到32767 範圍內乙個隨機數。
例如：srand();初始化乙個隨機函式。
a[0]＝10*rand()/32767*255+1;a[1]=10*rand()/32767*a[0]…語句可用來
產生a[0]與a[1]中的隨機數。
或採用以下方式：（1）通過隨機數產生乙個指令序列，共320 條指令。指令的
位址按下述原則生成：
a：50%的指令是順序執行的
b：25%的指令是均勻分布在前位址部分
c：25%的指令是均勻分布在後位址部分
具體的實施方法是：
a：在[0，319]的指令位址之間隨機選取一起點m
b：順序執行一條指令，即執行位址為m+1 的指令
c：在前位址[0,m+1]中隨機選取一條指令並執行，該指令的位址為m'
d：順序執行一條指令，其位址為m'+1
e：在後位址[m'+2，319]中隨機選取一條指令並執行
f：重複步驟a-e，直到320 次指令
（2）將指令序列變換為頁位址流
設：頁面大小為1k；
使用者記憶體容量4 頁到32 頁；
使用者虛存容量為32k。
在使用者虛存中，按每k 存放10 條指令排列虛存位址，即320 條指令在虛存中的
存放方式為：
第 0 條-第 9 條指令為第0 頁（對應虛存位址為[0，9]）
第10 條-第19 條指令為第1 頁（對應虛存位址為[10，19]）
第310 條-第319 條指令為第31 頁（對應虛存位址為[310，319]）
按以上方式，使用者指令可組成32 頁。
4、 頁面大小的取值範圍為1k，2k，4k，8k，16k。按照頁面大小將指令
位址轉化為頁號。對於相鄰相同的頁號，合併為乙個。
三、需求分析
設計程式模擬先進先出fifo，最佳置換opi和最近最久未使用lru頁面置換演算法的工作過程。假設記憶體中分配給每個程序的最小物理塊數為m，在程序執行過程中要訪問的頁面個數為n，頁面訪問序列為p1, … ,pn，分別利用不同的頁面置換演算法排程程序的頁面訪問序列，給出頁面訪問序列的置換過程，計算每種演算法缺頁次數和缺頁率。
程式的設計主要是測試先進先出fifo，最佳置換opi和最近最久未使用lru頁面置換演算法的效率以及過程，對於程式設計師設計有很多幫助，不同的場合用不同的演算法可以提高程式的效率。
四、程式流程圖
1. 產生訪問頁面的序列，儲存在佇列裡面中
2. fifo（先進先出）演算法
由佇列產生乙個陣列
mm為缺頁計數器
圖 13．lru（最近最久未使用）演算法
由佇列產生乙個陣列
mm為缺頁計數器
用乙個函式產生最近最久未使用的陣列
4．opt演算法
由佇列產生乙個陣列
mm為缺頁計數器
用乙個函式產生最近最久未使用的陣列
五、實驗測試
開始前：
生成序列
opt演算法
fifo演算法
lru演算法
六、實驗心得
本次實驗主要是利用mfc圖形介面來實現模擬作業系統的頁面置換的功能。在這次實驗中，我在同一工作區中建立了乙個對話方塊，主要顯示輸入，產生隨機序列，頁面置換過程，3種演算法選擇。本次實驗的演算法理解不難，但是因為對於c++系統函式和圖形介面設計的不熟悉，導致在設計程式的過程中遇到了很多的困難。
本次實驗有遇到不懂的地方，如到底是用佇列還是用列表儲存資料，listbox的用法我還不熟悉，開始以為顯示乙個字串用addstring()函式就可以了，結果發現，如果直接呼叫這個函式，顯示的結果會按序列的大小自動排序，而達不到我想要的效果，然後我改為了setstring()，用引數指明在哪一列顯示字串。發現結果如我所想。另外，在設計opt演算法的時候，考慮了很久如果記錄哪個頁面是以後最久出現的，最後，使用了乙個陣列記錄，加多乙個函式生成兩個相同頁面的距離。
通過此次實驗，使我加深理解模擬作業系統的頁面置換以及三種置換演算法，也使我的程式設計能力有了一定的提高。
作業系統頁面置換課程設計
數學與計算機學院 課程設計說明書 課程名稱 作業系統原理 課程設計 課程 題目 頁面置換演算法模擬程式 年級 專業 班 學生姓名 學號開始時間 2010 年月日 完成時間 2011 年月日 課程設計成績 指導教師簽名年月日 目錄 1 引言 1 1.1 問題的提出 1 1.2國內外研究的現狀 1 1....
頁面置換演算法模擬設計
課程設計報告 課程名稱作業系統 課題名稱頁面置換演算法模擬設計 專業通訊工程 班級學號 姓名指導教師 2014年 6 月 29 日 湖南工程學院 課程設計任務書 課程名稱作業系統 課題頁面置換演算法模擬設計 專業班級 學生姓名 學號指導老師 審批任務書下達日期 2014 年 6 月 23 日 任務完...
作業系統之頁置換演算法
方法有二 1 計數器法 最為簡單的情況為，為每個頁表關聯乙個時間域 在我開來就是在原結構體中再增加乙個變數 並為cpu增加乙個邏輯時鐘或計數器。對每次記憶體引用，計數器都會增加。每次記憶體引用時，時鐘暫存器的內容會複製相應所對應的頁表項的使用時間域內。置換具有最小時間的頁。不過過這種搜尋頁表以查詢l...