页面置换算法课程设计(共19页).doc
精选优质文档-倾情为你奉上 操作系统课程设计报告题 目 页面置换算法 专 业 计算机科学与技术 小组成员：专心-专注-专业目录 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.课设要求设计一个请求页式存储管理方案。并编写模拟程序实现之。要求包含：1过随机数产生一个指令序列，共320条指令。其地址按下述原则生成：50%的指令是顺序执行的；25%的指令是均匀分布在前地址部分；25%的指令是均匀分布在后地址部分；具体的实施方法是：在0，319的指令地址之间随机选区一起点M;顺序执行一条指令，即执行地址为M+1的指令；在前地址0，M+1中随机选取一条指令并执行，该指令的地址为M;顺序执行一条指令，其地址为M+1；在后地址M+2，319中随机选取一条指令并执行；重复AE，直到执行320次指令。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.系统分析在多道程序环境下，要使程序运行，必须先为之创建进程。而创建进程的第一步是将程序和数据装入内存。存储器实现的功能主要是内存分配等功能，本模拟系统所要实现的就是将进程的程序和数据装入内存（物理块）。具体需要实现的功能如下：1、读入进程大小，进行分页，确定每一页的指令地址范围；2、读入一个指令，确定其所在页面，读入内存物理块中。物理块空闲直接读入，物理块已满，指向下步操作。3、物理块已满，将要淘汰原来首先进入到内存中的页面，即换出；然后将现在的指令地址页面读入物理块中，即换入。4.系统设计4.1问题分析分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为物理块，在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系。一个页表中包含若干个表目，表目的自然序号对应于用户程序中的页号，表目中的块号是该页对应的物理块号。请求页式存储管理方式是一种实现虚拟存储器的方式，是指在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面。当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。请求页式存储管理主要需要解决以下问题：系统如何获知进程当前所需页面不在主存；当发现缺页时，如何把所缺页面调入主存；当主存中没有空闲的页框时，为了要接受一个新页，需要把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。4.2程序整体框图Main()函数 OPT 算法 LRU 算法 FIFO 算法 图4-1 程序整体框图由于该算法规模较小，可以将该系统划分为三块，分别是： FIFO算法模块、LRU算法模块、OPT算法模块。4.3 FIFO算法基于程序总是按线形顺序来访问物理空间这一假设，总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面。开始初始化函数 还有指令在队列中查找 将数组中第一个数据移除，并置标志位 找到了吗 将新加入的指令加入数组尾部结束 N YY N 4.4 LRU算法LRU置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的次数count,，当须淘汰一个页面时，选择现有页面中其count值最大的，即最近最久未使用的页面予以淘汰。NYY是否有空闲页面？找到？在页面中查找是否存在开始还有指令吗？计算出页号count=0将该页导入内存页面，count=0所有页面count+1从内存页面找出count最大的页面做空闲页面计算出命中率结束NNY4.5 OPT算法当要调入一页而必须淘汰旧页时，应该淘汰以后不再访问的页，或距现在最长时间后要访问的页。它所产生的缺页数最少。这只是一种理想的情况。NY是否有空闲页面？按早指令队列查找以后指令出每一面命中的距离，找出最大的或没命中的当空闲页面找到？在面中查找是否存在开始还有指令吗？计算出页号将该页导入空闲页面计算出命中率结束NYYN 图4-4 OPT算法程序流程图5.功能与测试5.1界面用户进入系统之后，会有一个选择算法的界面，如下图所示：选择内存容量，然后点击“随机生成页地址流”按钮，生成页地址流与页面走向，如下图所示：图5-1 选择界面5.2 FIFO算法用户点击“FIFO算法”按钮，如下图所示：5.3 LRU算法用户点击“LRU算法”按钮，如下图所示：5.4 OPT算法用户点击“OPT算法”按钮，如下图所示：6.结论对于页面算法，我们平时上课时，只是知道了页面置换算法是怎么做的，并没有想如何去实现这些算法。在真正要做的时候才发现了问题。在这次课程设计的过程中，由于之前大家对可视化程序设计不怎么熟悉，在写代码的时候有了许多的麻烦。最后，在小组成员耐心看了一些C#的书，并且多方实践，终于完成了这次课程设计。通过该设计，我们学会了存储器的管理内容，利用C#语言实现进程装入内存的的过程，同时也对存储器管理的多种装入方式及内存分区有了更深的了解，特别是页面置换算法的应用。但也应看到对于实际的存储器应用还有很多地方不能实现真实，在今后的学习中应对所学知识做更深入的挖掘，对于各种算法应用更好的利用。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+) /将页地址流转换为页面走向并输出 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+) /初始化结构体 struPagei.pageNum = 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;/暂存已装入内存的页面号 for (int i = 0; i < memorySize; i+) arrayi = -1; for (int j = 0; j < 320; j+) if (struPagepagej.flag = 0) pageReplaceNum+; 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; 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+) /初始化结构体 struPagei.pageNum = 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;/暂存已装入内存的页面号 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 = memorySize)/内存空间已满 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=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" 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.pageNum = 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;/暂存已装入内存的页面号 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.flag = 0; struPagepagej.flag = 1; arraymax = pagej; int n; for (n = j + 1; n < 320; n+) /求出替换页面的distance if (pagen = pagej) break; struPagepagej.distance = n - j; else/内存还有空闲 struPagepagej.flag = 1; arraypageLoadedNum+ = pagej; int m; for (m = j + 1; m < 320; m+) /求出装入页面的distance if (pagem = pagej) break; struPagepagej.distance = m - j; else/页面已转入内存 int t; for (t = j + 1; t < 320; t+) /求出装入页面的distance if (paget = pagej) break; struPagepagej.distance = t - j; 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;
