1、精選優質文檔-傾情為你奉上 操作系統課程設計報告題 目 頁面置換算法 專 業 計算機科學與技術 小組成員：專心-專注-專業目錄 1.設計目的22.課設要求23.系統分析34.系統設計34.1問題分析34.2程序整體框圖54.3 FIFO算法54.4 LRU算法64.5 OPT算法75.功能與測試85.1開始界面85.2 FIFO算法95.3 LRU算法105.4 OPT算法106.結論117.附錄121.設計目的1、存儲管理的主要功能之一是合理地分配空間。請求頁式管理是一種常用的虛擬存儲管理技術。本次設計的目的是通過請求頁式存儲管理中頁面置換算法模擬設計，了解虛擬存儲技術的特點，掌握請求頁式管

2、理的頁面置換算法。2、提高自己的程序設計能力、 提高算法設計質量與程序設計素質；2.課設要求設計一個請求頁式存儲管理方案。并編寫模擬程序實現之。要求包含：1過隨機數產生一個指令序列，共320條指令。其地址按下述原則生成：50%的指令是順序執行的；25%的指令是均勻分布在前地址部分；25%的指令是均勻分布在后地址部分；具體的實施方法是：在0，319的指令地址之間隨機選區一起點M;順序執行一條指令，即執行地址為M+1的指令；在前地址0，M+1中隨機選取一條指令并執行，該指令的地址為M;順序執行一條指令，其地址為M+1；在后地址M+2，319中隨機選取一條指令并執行；重復AE，直到執行320次指令。

3、2指令序列變換成頁地址流設：（1）頁面大小為1K；用戶內存容量為4頁到32頁；用戶虛存容量為32K。在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為： 第0條第9條指令為第0頁（對應虛存地址為0，9）； 第10條第19條指令為第1頁（對應虛存地址為10，19）； 。 第310條第319條指令為第31頁（對應虛存地址為310，319）；按以上方式，用戶指令可組成32頁。3. 計算并輸出下述各種算法在不同內存容量下的命中率。FIFO先進先出的算法LRU最近最少使用算法OPT最佳淘汰算法（先淘汰最不常用的頁地址）3.系統分析在多道程序環境下，要使程序運行，必須先為之

4、創建進程。而創建進程的第一步是將程序和數據裝入內存。存儲器實現的功能主要是內存分配等功能，本模擬系統所要實現的就是將進程的程序和數據裝入內存（物理塊）。具體需要實現的功能如下：1、讀入進程大小，進行分頁，確定每一頁的指令地址范圍；2、讀入一個指令，確定其所在頁面，讀入內存物理塊中。物理塊空閑直接讀入，物理塊已滿，指向下步操作。3、物理塊已滿，將要淘汰原來首先進入到內存中的頁面，即換出；然后將現在的指令地址頁面讀入物理塊中，即換入。4.系統設計4.1問題分析分頁存儲管理，是將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，并為各頁加以編號。相應地，也把內存空間分成與頁面相同大小的若干

5、個存儲塊，稱為物理塊，在為進程分配內存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中系統為每個進程建立一個頁表，頁表給出邏輯頁號和具體內存塊號相應的關系。一個頁表中包含若干個表目，表目的自然序號對應于用戶程序中的頁號，表目中的塊號是該頁對應的物理塊號。請求頁式存儲管理方式是一種實現虛擬存儲器的方式，是指在進程開始運行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根據進程運行的需要，動態裝入其它頁面。當內存空間已滿，而又需要裝入新的頁面時，則根據某種算法淘汰某個頁面，以便裝入新的頁面。請求頁式存儲管理主要需要解決以下問題：系統如何獲知進程當前所需頁面不在主存；當發現缺

6、頁時，如何把所缺頁面調入主存；當主存中沒有空閑的頁框時，為了要接受一個新頁，需要把老的一頁淘汰出去，根據什么策略選擇欲淘汰的頁面。4.2程序整體框圖Main()函數 OPT 算法 LRU 算法 FIFO 算法 圖4-1 程序整體框圖由于該算法規模較小，可以將該系統劃分為三塊，分別是： FIFO算法模塊、LRU算法模塊、OPT算法模塊。4.3 FIFO算法基于程序總是按線形順序來訪問物理空間這一假設，總是淘汰最先調入主存的頁面，即淘汰在主存中駐留時間最長的頁面。開始初始化函數 還有指令在隊列中查找 將數組中第一個數據移除，并置標志位 找到了嗎 將新加入的指令加入數組尾部結束 N YY N 4.4

7、 LRU算法LRU置換算法，是根據頁面調入內存后的使用情況進行決策的。由于無法預測各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經歷的次數count,，當須淘汰一個頁面時，選擇現有頁面中其count值最大的，即最近最久未使用的頁面予以淘汰。NYY是否有空閑頁面？找到？在頁面中查找是否存在開始還有指令嗎？計算出頁號count=0將該頁導入內存頁面，count=0所有頁面count+1從內存頁面找出count最大的頁面做空閑頁面計算出命中率結束NNY4.

8、5 OPT算法當要調入一頁而必須淘汰舊頁時，應該淘汰以后不再訪問的頁，或距現在最長時間后要訪問的頁。它所產生的缺頁數最少。這只是一種理想的情況。NY是否有空閑頁面？按早指令隊列查找以后指令出每一面命中的距離，找出最大的或沒命中的當空閑頁面找到？在面中查找是否存在開始還有指令嗎？計算出頁號將該頁導入空閑頁面計算出命中率結束NYYN 圖4-4 OPT算法程序流程圖5.功能與測試5.1界面用戶進入系統之后，會有一個選擇算法的界面，如下圖所示：選擇內存容量，然后點擊“隨機生成頁地址流”按鈕，生成頁地址流與頁面走向，如下圖所示：圖5-1 選擇界面5.2 FIFO算法用戶點擊“FIFO算法”按鈕，如下圖所

9、示：5.3 LRU算法用戶點擊“LRU算法”按鈕，如下圖所示：5.4 OPT算法用戶點擊“OPT算法”按鈕，如下圖所示：6.結論對于頁面算法，我們平時上課時，只是知道了頁面置換算法是怎么做的，并沒有想如何去實現這些算法。在真正要做的時候才發現了問題。在這次課程設計的過程中，由于之前大家對可視化程序設計不怎么熟悉，在寫代碼的時候有了許多的麻煩。最后，在小組成員耐心看了一些C#的書，并且多方實踐，終于完成了這次課程設計。通過該設計，我們學會了存儲器的管理內容，利用C#語言實現進程裝入內存的的過程，同時也對存儲器管理的多種裝入方式及內存分區有了更深的了解，特別是頁面置換算法的應用。但也應看到對于實際

10、的存儲器應用還有很多地方不能實現真實，在今后的學習中應對所學知識做更深入的挖掘，對于各種算法應用更好的利用。7.附錄程序源代碼using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Linq;using System.Text;using System.Windows.Forms;namespace PageReplace public partial class Form1 : Form publi

11、c int page=new int320; public struct StruPage public int pageNum; public int flag; public int count; public int distance; public StruPage struPage = new StruPage32;/外存上的頁面 public Form1() InitializeComponent(); comboBox1.DropDownStyle = ComboBoxStyle.DropDownList; for (int i = 4; i <= 32; i+) comb

12、oBox1.Items.Add(i); private void btnRand_Click(object sender, EventArgs e) int address = new int320; this.rtboxAddress.Text = "" this.rtboxPage.Text = "" Random ram = new Random(); for (int i = 0; i < 317; ) /生成頁地址流 int m = ram.Next(319); addressi+ = m+1; int m_ = ram.Next(0,

13、m + 1); addressi+ = m_ + 1; addressi+ = ram.Next(m_+2,319); for (int j = 0; j < 320; j+) /將頁地址流轉換為頁面走向并輸出 pagej = addressj / 10; this.rtboxAddress.Text += addressj.ToString() + "t" this.rtboxPage.Text += pagej.ToString() + "t" this.btnFCFS.Visible = true; this.btnLRU.Visible =

14、 true; this.btnOPT.Visible = true; private void btnFCFS_Click(object sender, EventArgs e) / this.btnFCFS.BackColor = Color.Yellow; for (int i = 0; i < 32; i+) /初始化結構體 struPagei.pageNum = i; struPagei.flag = 0; struPagei.count = 0; struPagei.distance = 320; int pageReplaceNum = 0;/替換的頁面數 double sh

15、ootRate;/命中率 int memorySize = Int32.Parse(comboBox1.Text);/內存的容量 String outputString = ""/每次替換后的內存狀態 int pageLoadedNum = 0;/已裝入內存的頁面數 int array = new intmemorySize;/暫存已裝入內存的頁面號 for (int i = 0; i < memorySize; i+) arrayi = -1; for (int j = 0; j < 320; j+) if (struPagepagej.flag = 0) p

16、ageReplaceNum+; if (pageLoadedNum = memorySize)/內存空間已滿 struPagearray0.flag = 0; for (int k = 0; k < memorySize - 1; k+) arrayk = arrayk + 1; arraypageLoadedNum - 1 = pagej; struPagepagej.flag = 1; else/內存空間還有空閑 struPagepagej.flag = 1; arraypageLoadedNum+ = pagej; for (int i = 0; i < memorySize

17、; i+) if (arrayi = -1) outputString += " t" else outputString += arrayi.ToString() + "t" outputString += "n" shootRate = 1 - pageReplaceNum / 320.0; this.rtboxMemory.Text = "" this.shootRateBox.Text = shootRate.ToString(); this.rtboxMemory.Text = outputString;

18、 private void btnLRU_Click(object sender, EventArgs e) for (int i = 0; i < 32; i+) /初始化結構體 struPagei.pageNum = i; struPagei.flag = 0; struPagei.count = 0; struPagei.distance = 320; int pageReplaceNum = 0;/替換的頁面數 double shootRate;/命中率 int memorySize = Int32.Parse(comboBox1.Text);/內存的容量 String outp

19、utString = ""/每次替換后的內存狀態 int pageLoadedNum = 0;/已裝入內存的頁面數 int array = new intmemorySize;/暫存已裝入內存的頁面號 for (int i = 0; i < memorySize; i+) arrayi = -1; for (int j = 0; j < 320; j+) struPagepagej.count = 0; if (struPagepagej.flag = 0)/頁面未曾裝入內存 pageReplaceNum+; if (pageLoadedNum = memory

20、Size)/內存空間已滿 int max = 0; for (int k = 1; k < pageLoadedNum; k+)/找出count最小的頁面 if(struPagearrayk.count>struPagearraymax.count) max=k; /進行頁面替換 struPagearraymax.flag=0; struPagepagej.flag=1; arraymax=pagej; for(int n=0;n<pageLoadedNum;n+ ) struPagearrayn.count+; else/內存還有空閑 struPagepagej.flag=

21、1; arraypageLoadedNum+ = pagej; for(int s=0;s<pageLoadedNum;s+) struPagearrays.count+; else/頁面已轉入內存 for(int t=0;t<pageLoadedNum;t+) struPagearrayt.count+; for (int i = 0; i < memorySize; i+) if (arrayi = -1) outputString += " t" else outputString += arrayi.ToString() + "t&quo

22、t; outputString += "n" shootRate = 1 - pageReplaceNum / 320.0; this.rtboxMemory.Text = "" this.shootRateBox.Text = shootRate.ToString(); this.rtboxMemory.Text = outputString; private void btnOPT_Click(object sender, EventArgs e) for (int i = 0; i < 32; i+) /初始化結構體 struPagei.pa

23、geNum = i; struPagei.flag = 0; struPagei.count = 0; struPagei.distance = 320; int pageReplaceNum = 0;/替換的頁面數 double shootRate;/命中率 int memorySize = Int32.Parse(comboBox1.Text);/內存的容量 String outputString=""/每次替換后的內存狀態 int pageLoadedNum = 0;/已裝入內存的頁面數 int array = new intmemorySize;/暫存已裝入內存的頁

24、面號 for (int i = 0; i < memorySize; i+) arrayi = -1; for (int j = 0; j < 320; j+) if (struPagepagej.flag = 0)/頁面未曾裝入內存 pageReplaceNum+; if (pageLoadedNum = memorySize)/內存空間已滿 int max = 0; for (int k = 1; k < pageLoadedNum; k+)/找出distance最遠的頁面 if (struPagearrayk.distance > struPagearraymax.distance) max = k; /進行頁面替換 struPagearraymax.f