頁面置換算法課程設(shè)計(jì)

操作系統(tǒng)課程設(shè)計(jì)報(bào)告題 目 頁面置換算法 專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 小組成員： 目錄 1.設(shè)計(jì)目的22.課設(shè)要求23.系統(tǒng)分析34.系統(tǒng)設(shè)計(jì)34.1問題分析34.2程序整體框圖54.3 FIFO算法54.4 LRU算法64.5 OPT算法75.功能與測(cè)試85.1開始界面85.2 FIFO算法95.3 LRU算法105.4 OPT算法106.結(jié)論117.附錄12I 1.設(shè)計(jì)目的1、存儲(chǔ)管理的主要功能之一是合理地分配空間。請(qǐng)求頁式管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。本次設(shè)計(jì)的目的是通過請(qǐng)求頁式存儲(chǔ)管理中頁面置換算法模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握請(qǐng)求頁式管理的頁面置換算法。2、提高自己的程序設(shè)計(jì)能力、 提高算法設(shè)計(jì)質(zhì)量與程序設(shè)計(jì)素質(zhì)；2.課設(shè)要求設(shè)計(jì)一個(gè)請(qǐng)求頁式存儲(chǔ)管理方案。并編寫模擬程序?qū)崿F(xiàn)之。要求包含：1過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令。其地址按下述原則生成：50%的指令是順序執(zhí)行的；25%的指令是均勻分布在前地址部分；25%的指令是均勻分布在后地址部分；具體的實(shí)施方法是：在0，319的指令地址之間隨機(jī)選區(qū)一起點(diǎn)M;順序執(zhí)行一條指令，即執(zhí)行地址為M+1的指令；在前地址0，M+1中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為M;順序執(zhí)行一條指令，其地址為M+1；在后地址M+2，319中隨機(jī)選取一條指令并執(zhí)行；重復(fù)AE，直到執(zhí)行320次指令。2指令序列變換成頁地址流設(shè)：（1）頁面大小為1K；用戶內(nèi)存容量為4頁到32頁；用戶虛存容量為32K。在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為： 第0條第9條指令為第0頁（對(duì)應(yīng)虛存地址為0，9）； 第10條第19條指令為第1頁（對(duì)應(yīng)虛存地址為10，19）； 。 第310條第319條指令為第31頁（對(duì)應(yīng)虛存地址為310，319）；按以上方式，用戶指令可組成32頁。3. 計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率。FIFO先進(jìn)先出的算法LRU最近最少使用算法OPT最佳淘汰算法（先淘汰最不常用的頁地址）3.系統(tǒng)分析在多道程序環(huán)境下，要使程序運(yùn)行，必須先為之創(chuàng)建進(jìn)程。而創(chuàng)建進(jìn)程的第一步是將程序和數(shù)據(jù)裝入內(nèi)存。存儲(chǔ)器實(shí)現(xiàn)的功能主要是內(nèi)存分配等功能，本模擬系統(tǒng)所要實(shí)現(xiàn)的就是將進(jìn)程的程序和數(shù)據(jù)裝入內(nèi)存（物理塊）。具體需要實(shí)現(xiàn)的功能如下：1、讀入進(jìn)程大小，進(jìn)行分頁，確定每一頁的指令地址范圍；2、讀入一個(gè)指令，確定其所在頁面，讀入內(nèi)存物理塊中。物理塊空閑直接讀入，物理塊已滿，指向下步操作。3、物理塊已滿，將要淘汰原來首先進(jìn)入到內(nèi)存中的頁面，即換出；然后將現(xiàn)在的指令地址頁面讀入物理塊中，即換入。4.系統(tǒng)設(shè)計(jì)4.1問題分析分頁存儲(chǔ)管理，是將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片，稱為頁面或頁，并為各頁加以編號(hào)。相應(yīng)地，也把內(nèi)存空間分成與頁面相同大小的若干個(gè)存儲(chǔ)塊，稱為物理塊，在為進(jìn)程分配內(nèi)存時(shí)，以塊為單位將進(jìn)程中的若干個(gè)頁分別裝入到多個(gè)可以不相鄰接的物理塊中系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)頁表，頁表給出邏輯頁號(hào)和具體內(nèi)存塊號(hào)相應(yīng)的關(guān)系。一個(gè)頁表中包含若干個(gè)表目，表目的自然序號(hào)對(duì)應(yīng)于用戶程序中的頁號(hào)，表目中的塊號(hào)是該頁對(duì)應(yīng)的物理塊號(hào)。請(qǐng)求頁式存儲(chǔ)管理方式是一種實(shí)現(xiàn)虛擬存儲(chǔ)器的方式，是指在進(jìn)程開始運(yùn)行之前，不是裝入全部頁面，而是裝入一個(gè)或零個(gè)頁面，之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其它頁面。當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁面，以便裝入新的頁面。請(qǐng)求頁式存儲(chǔ)管理主要需要解決以下問題：系統(tǒng)如何獲知進(jìn)程當(dāng)前所需頁面不在主存；當(dāng)發(fā)現(xiàn)缺頁時(shí)，如何把所缺頁面調(diào)入主存；當(dāng)主存中沒有空閑的頁框時(shí)，為了要接受一個(gè)新頁，需要把老的一頁淘汰出去，根據(jù)什么策略選擇欲淘汰的頁面。4.2程序整體框圖Main()函數(shù) OPT 算法 LRU 算法 FIFO 算法 圖4-1 程序整體框圖由于該算法規(guī)模較小，可以將該系統(tǒng)劃分為三塊，分別是： FIFO算法模塊、LRU算法模塊、OPT算法模塊。4.3 FIFO算法基于程序總是按線形順序來訪問物理空間這一假設(shè)，總是淘汰最先調(diào)入主存的頁面，即淘汰在主存中駐留時(shí)間最長的頁面。開始初始化函數(shù) 還有指令在隊(duì)列中查找 將數(shù)組中第一個(gè)數(shù)據(jù)移除，并置標(biāo)志位 找到了嗎 將新加入的指令加入數(shù)組尾部結(jié)束 N YY N 4.4 LRU算法LRU置換算法，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。由于無法預(yù)測(cè)各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。該算法賦予每個(gè)頁面一個(gè)訪問字段，用來記錄一個(gè)頁面自上次被訪問以來所經(jīng)歷的次數(shù)count,，當(dāng)須淘汰一個(gè)頁面時(shí)，選擇現(xiàn)有頁面中其count值最大的，即最近最久未使用的頁面予以淘汰。NYY是否有空閑頁面？找到？在頁面中查找是否存在開始還有指令嗎？計(jì)算出頁號(hào)count=0將該頁導(dǎo)入內(nèi)存頁面，count=0所有頁面count+1從內(nèi)存頁面找出count最大的頁面做空閑頁面計(jì)算出命中率結(jié)束NNY4.5 OPT算法當(dāng)要調(diào)入一頁而必須淘汰舊頁時(shí)，應(yīng)該淘汰以后不再訪問的頁，或距現(xiàn)在最長時(shí)間后要訪問的頁。它所產(chǎn)生的缺頁數(shù)最少。這只是一種理想的情況。NY是否有空閑頁面？按早指令隊(duì)列查找以后指令出每一面命中的距離，找出最大的或沒命中的當(dāng)空閑頁面找到？在面中查找是否存在開始還有指令嗎？計(jì)算出頁號(hào)將該頁導(dǎo)入空閑頁面計(jì)算出命中率結(jié)束NYYN 圖4-4 OPT算法程序流程圖5.功能與測(cè)試5.1界面用戶進(jìn)入系統(tǒng)之后，會(huì)有一個(gè)選擇算法的界面，如下圖所示：選擇內(nèi)存容量，然后點(diǎn)擊“隨機(jī)生成頁地址流”按鈕，生成頁地址流與頁面走向，如下圖所示：圖5-1 選擇界面5.2 FIFO算法用戶點(diǎn)擊“FIFO算法”按鈕，如下圖所示：5.3 LRU算法用戶點(diǎn)擊“LRU算法”按鈕，如下圖所示：5.4 OPT算法用戶點(diǎn)擊“OPT算法”按鈕，如下圖所示：6.結(jié)論對(duì)于頁面算法，我們平時(shí)上課時(shí)，只是知道了頁面置換算法是怎么做的，并沒有想如何去實(shí)現(xiàn)這些算法。在真正要做的時(shí)候才發(fā)現(xiàn)了問題。在這次課程設(shè)計(jì)的過程中，由于之前大家對(duì)可視化程序設(shè)計(jì)不怎么熟悉，在寫代碼的時(shí)候有了許多的麻煩。最后，在小組成員耐心看了一些C#的書，并且多方實(shí)踐，終于完成了這次課程設(shè)計(jì)。通過該設(shè)計(jì)，我們學(xué)會(huì)了存儲(chǔ)器的管理內(nèi)容，利用C#語言實(shí)現(xiàn)進(jìn)程裝入內(nèi)存的的過程，同時(shí)也對(duì)存儲(chǔ)器管理的多種裝入方式及內(nèi)存分區(qū)有了更深的了解，特別是頁面置換算法的應(yīng)用。但也應(yīng)看到對(duì)于實(shí)際的存儲(chǔ)器應(yīng)用還有很多地方不能實(shí)現(xiàn)真實(shí)，在今后的學(xué)習(xí)中應(yīng)對(duì)所學(xué)知識(shí)做更深入的挖掘，對(duì)于各種算法應(yīng)用更好的利用。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 public 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+) comboBox1.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, m + 1); addressi+ = m_ + 1; addressi+ = ram.Next(m_+2,319); for (int j = 0; j 320; j+) /將頁地址流轉(zhuǎn)換為頁面走向并輸出 pagej = addressj / 10; this.rtboxAddress.Text += addressj.ToString() + t; this.rtboxPage.Text += pagej.ToString() + t; this.btnFCFS.Visible = true; this.btnLRU.Visible = 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+) /初始化結(jié)構(gòu)體 struPagei.pageNum = i; struPagei.flag = 0; struPagei.count = 0; struPagei.distance = 320; int pageReplaceNum = 0;/替換的頁面數(shù) double shootRate;/命中率 int memorySize = Int32.Parse(comboBox1.Text);/內(nèi)存的容量 String outputString = ;/每次替換后的內(nèi)存狀態(tài) int pageLoadedNum = 0;/已裝入內(nèi)存的頁面數(shù) int array = new intmemorySize;/暫存已裝入內(nèi)存的頁面號(hào) for (int i = 0; i memorySize; i+) arrayi = -1; for (int j = 0; j 320; j+) if (struPagepagej.flag = 0) pageReplaceNum+; if (pageLoadedNum = memorySize)/內(nèi)存空間已滿 struPagearray0.flag = 0; for (int k = 0; k memorySize - 1; k+) arrayk = arrayk + 1; arraypageLoadedNum - 1 = pagej; struPagepagej.flag = 1; else/內(nèi)存空間還有空閑 struPagepagej.flag = 1; arraypageLoadedNum+ = pagej; for (int i = 0; i memorySize; 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; private void btnLRU_Click(object sender, EventArgs e) for (int i = 0; i 32; i+) /初始化結(jié)構(gòu)體 struPagei.pageNum = i; struPagei.flag = 0; struPagei.count = 0; struPagei.distance = 320; int pageReplaceNum = 0;/替換的頁面數(shù) double shootRate;/命中率 int memorySize = Int32.Parse(comboBox1.Text);/內(nèi)存的容量 String outputString = ;/每次替換后的內(nèi)存狀態(tài) int pageLoadedNum = 0;/已裝入內(nèi)存的頁面數(shù) int array = new intmemorySize;/暫存已裝入內(nèi)存的頁面號(hào) for (int i = 0; i memorySize; i+) arrayi = -1; for (int j = 0; j 320; j+) struPagepagej.count = 0; if (struPagepagej.flag = 0)/頁面未曾裝入內(nèi)存 pageReplaceNum+; if (pageLoadedNum = memorySize)/內(nèi)存空間已滿 int max = 0; for (int k = 1; k struPagearraymax.count) max=k; /進(jìn)行頁面替換 struPagearraymax.flag=0; struPagepagej.flag=1; arraymax=pagej; for(int n=0;npageLoadedNum;n+ ) struPagearrayn.count+; else/內(nèi)存還有空閑 struPagepagej.flag=1; arraypageLoadedNum+ = pagej; for(int s=0;spageLoadedNum;s+) struPagearrays.count+; else/頁面已轉(zhuǎn)入內(nèi)存 for(int t=0;tpageLoadedNum;t+) struPagearrayt.count+; for (int i = 0; i memorySize; 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; private void btnOPT_Click(object sender, EventArgs e) for (int i = 0; i 32; i+) /初始化結(jié)構(gòu)體 struPagei.pageNum = i; struPagei.flag = 0; struPagei.count = 0; struPagei.distance = 320; int pageReplaceNum = 0;/替換的頁面數(shù) double shootRate;/命中率 int memorySize = Int32.Parse(comboBox1.Text);/內(nèi)存的容量 String outputString=;/每次替換后的內(nèi)存狀態(tài) int pageLoadedNum = 0;/已裝入內(nèi)存的頁面數(shù) int array = new intmemorySize;/暫存已裝入內(nèi)存的頁面號(hào) for (int i = 0; i memorySize; i+) arrayi = -1; for (int j = 0; j 320; j+) if (struPagepagej.flag = 0)/頁面未曾裝入內(nèi)存 pageReplaceNum+; if (pageLoadedNum = memorySize)/內(nèi)存空間已滿 int max = 0; for (int k = 1; k struPagearraymax.distance) max = k; /進(jìn)行頁面替換 st