页面置换算法课程设计.pdf
页面置换算法课程设计 1/19 操作系统课程设计报告 题 目 页面置换算法 专 业 计算机科学与技术 小组成员：页面置换算法课程设计 I/19 目录 1.设计目的.2 2.课设要求.2 3.系统分析.3 4.系统设计.3 4.1 问题分析.3 4.2 程序整体框图.5 4.3 FIFO 算法.5 4.4 LRU 算法.6 4.5 OPT 算法.7 5.功能与测试.8 5.1 开始界面.8 5.2 FIFO 算法.9 5.3 LRU 算法.10 5.4 OPT 算法.10 6.结论.11 7.附录.12 页面置换算法课程设计 2/19 1.设计目的 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条指令在虚存中的存放方式为：页面置换算法课程设计 3/19 第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/19 若干个存储块，称为物理块，在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中 系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系。一个页表中包含若干个表目，表目的自然序号对应于用户程序中的页号，表目中的块号是该页对应的物理块号。请求页式存储管理方式是一种实现虚拟存储器的方式，是指在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面。当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。请求页式存储管理主要需要解决以下问题：系统如何获知进程当前所需页面不在主存；当发现缺页时，如何把所缺页面调入主存；当主存中没有空闲的页框时，为了要接受一个新页，需要把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。4.2 程序整体框图 图 4-1 程序整体框图 由于该算法规模较小，可以将该系统划分为三块，分别是：FIFO 算法模块、LRU算法模块、OPT 算法模块。Main()函数 FIFO 算法 LRU 算法 OPT 算法 页面置换算法课程设计 5/19 4.3 FIFO 算法 基于程序总是按线形顺序来访问物理空间这一假设，总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面。N Y Y N 4.4 LRU 算法 LRU 置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU 置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每开始 初始化函数 还有指令 在队列中查找 将数组中第一个数据移除，并置标志位 找到了吗 将新加入的指令加入数组尾部 结束 页面置换算法课程设计 6/19 个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的次数count,，当须淘汰一个页面时，选择现有页面中其 count值最大的，即最近最久未使用的页面予以淘汰。Y N Y Y 是否有空闲页面？找到？在页面中查找是否存在 开始 还有指令计算出页count=0 将该页导入内存页面，count=0 所有页面 count+1 从内存页面找出 count 最大的页面做空闲页面 计算出命中率 结束 N N 页面置换算法课程设计 7/19 4.5 OPT 算法 当要调入一页而必须淘汰旧页时，应该淘汰以后不再访问的页，或距现在最长时间后要访问的页。它所产生的缺页数最少。这只是一种理想的情况。图 4-4 OPT 算法程序流程图 N Y 是否有空闲页面？按早指令队列查找以后指令出每一面命中的距离，找出最大的或没命中的当空闲页面 找到？在面中查找是否存在 开始 还有指令计算出页号 将该页导入空闲页计算出命中率 结束 N Y Y N 页面置换算法课程设计 8/19 5.功能与测试 5.1 界面 用户进入系统之后，会有一个选择算法的界面，如下图所示：选择内存容量，然后点击“随机生成页地址流”按钮，生成页地址流与页面走向，如下图所示：图 5-1 选择界面 页面置换算法课程设计 9/19 5.2 FIFO 算法 用户点击“FIFO 算法”按钮，如下图所示：5.3 LRU 算法 用户点击“LRU 算法”按钮，如下图所示：页面置换算法课程设计 10/19 5.4 OPT 算法 用户点击“OPT 算法”按钮，如下图所示：页面置换算法课程设计 11/19 6.结论 对于页面算法，我们平时上课时，只是知道了页面置换算法是怎么做的，并没有想如何去实现这些算法。在真正要做的时候才发现了问题。在这次课程设计的过程中，由于之前大家对可视化程序设计不怎么熟悉，在写代码的时候有了许多的麻烦。最后，在小组成员耐心看了一些 C#的书，并且多方实践，终于完成了这次课程设计。通过该设计，我们学会了存储器的管理内容，利用 C#语言实现进程装入内存的的过程，同时也对存储器管理的多种装入方式及内存分区有了更深的了解，特别是页面置换算法的应用。但也应看到对于实际的存储器应用还有很多地方不能实现真实，在今后的学习中应对所学知识做更深入的挖掘，对于各种算法应用更好的利用。页面置换算法课程设计 12/19 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)页面置换算法课程设计 13/19 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=;/每次替换后的内存状态 页面置换算法课程设计 14/19 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;页面置换算法课程设计 15/19 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 struPagearraymax.count)max=k;/进行页面替换 struPagearraymax.flag=0;struPagepagej.flag=1;arraymax=pagej;for(int n=0;npageLoadedNum;n+)struPagearrayn.count+;else/内存还有空闲 struPagepagej.flag=1;arraypageLoadedNum+=pagej;for(int s=0;spageLoadedNum;s+)struPagearrays.count+;else/页面已转入内存 页面置换算法课程设计 16/19 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+)/初始化结构体 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+;页面置换算法课程设计 17/19 if(pageLoadedNum=memorySize)/内存空间已满 int max=0;for(int k=1;k 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;页面置换算法课程设计 18/19 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;
