操作系统课程设计报告.doc

上海电力学院计算机操作系统原理课程设计报告 题目名称： 编写程序模拟虚拟存储器管理姓 名： 杜志豪.学 号：20121798 班 级： 2012053班 . 同组姓名： 孙嘉轶 课程设计时间： 2014.6.302014.7.4 评语： 成绩： 目录一、 设计内容及要求 4 1. 1 设计题目412 使用算法分析： 412.1 FIFO算法（先进先出淘汰算法） 412.2 LRU算法（最久未使用淘汰算法） 51. 2.3 OPT算法（最佳淘汰算法） 5 1.3 分工情况 5 二、 详细设计62.1 原理概述 62.2主要数据结构(主要代码)62.3算法流程图 9 2.3.1 主流程图9 2.3.2 Optimal算法流程图10 2.3.3 FIFO算法流程图10 2.3.4 LRU算法流程图112.41源程序文件名112.4. 2执行文件名 11三、实验结果与分析11 3.1 Optimal页面置换算法结果与分析 11 3.2 FIFO页面置换算法结果与分析 16 3.3 LRU页面置换算法结果与分析 20四、设计创新点24五、设计与总结27六、代码附录27课程设计题目一、 设计内容及要求1.1 编写程序模拟虚拟存储器管理。假设以M页的进程分配了N块内存（NM）。输入：设定系统分配的块数，以及进程页面引用序列（也可随即产生）。输出：显示每一次页面引用内存状态，最终显示产生缺页中断的次数及页面置换的次数（假设初始状态内存没有装入任何页面）。必须分别使用以下置换算法完成模拟：(1) FIFO页面置换算法;(2) LRU页面置换算法;(3) 最佳（Optimal）页面置换算法。1.2 使用算法分析：1.2.1 FIFO页面置换算法：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法并不是都适合实际情况，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数，例程等得页面，FIFO算法并不能保证这些页面不被淘汰。1.2.2 LRU页面置换算法：最近最久未使用（LRU）的页面置换算法是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择有页面中t值最大的，即最近最久为使用的页面以淘汰。1.2.3 最佳（Optimal）页面置换算法：Optimal算法是一种理论的算法，其所选择的被淘汰页面将是以后永久不使用的，或许是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其他算法。 1.3 分工情况：共同讨论并构思，杜志豪负责FIFO和LRU算法的编程，孙嘉轶负责窗体界面和OPT算法的编写。编程中遇到困难共同讨论并解决。二、 详细设计2.1 原理概述定义一个整型变量int buffer=0来记录内存分块数，定义一个string 类型的算法 string suanfa来选择具体的算法；用一个数组intxulie来存储页面序列，长度为20；用一个数组intkuai来存储内存分配的物理块个数，长度为5；用int s来记录具体的步骤数，用int num来记录页面中断次数。空白表示物理块没有被使用。2.2 主要数据结构（代码）结构体：输入的页面序列号： public Form1() /输入页面序列号 InitializeComponent(); for (int i = 0; i xulie.Length; i+) xuliei = -1; for (int i = 0; i kuai.Length; i+) kuaii = -1; 选择内存分块数目 private void fenkuai3_CheckedChanged(object sender, EventArgs e) /分块3按钮 buffer = 3; private void fenkuai4_CheckedChanged(object sender, EventArgs e) buffer = 4; private void fenkuai5_CheckedChanged(object sender, EventArgs e) buffer = 5; private void fifon_CheckedChanged(object sender, EventArgs e) /算法按钮 suanfa = fifo; private void lrun_CheckedChanged(object sender, EventArgs e) suanfa = lru; private void optn_CheckedChanged(object sender, EventArgs e) suanfa = opt; ： 输入页面顺序数： private void input_TextChanged(object sender, EventArgs e) /输入页面顺序数 zhuangtai.Visible = true; zhuangtai.Text = 输入页面顺序数： + input.Text.Length; 返回中断次数： public RichTextBox text() /返回中端次数 return x; public int num1() return num; public void clean() /清零函数 z = 4; z1 = 5; z2 = 6; w = 0; wu = 0; succeed = false; num = 0; public class len /返回入块页面数 public int leng(int x) int i = 0; for (i = 0; i x.Length; i+) if (xi = -1) break; return i; 结构体存储队列页面相关变量参数： int buffer = 0;/内存分块数 string suanfa;/选择算法 int xulie = new int20;/页面序列 int kuai = new int5; int s = 0;/步骤数 int num;/中断次数 len leng1 = new len();2.3 算法（流程图）：根据模拟虚拟管理器管理界面画的流程图2.4 源程序文件名：虚拟存储器管理.cpp执行文件名：虚拟存储器管理.exe三、 实验结果与分析（要有结果截图）3.1 Optimal页面置换算法结果与分析最佳页面置换算法是指：其选择的被淘汰的页面将是以后永不使用，或许是在最长时间内不被访问的页面。3.1.1 假设系统分配了3块物理块，读取一个页面顺序：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 前面三个直接进入内存即：7 0 1。由于7是未来最长时间不被使用，因此把7置换成2即为：2 0 1。由于0已经在内存里面，不需置换。1是未来最长时间不被使用的，所以把1置换成3得到：2 0 3。由于0在已经在内存里面，不需置换。0是未来最长时间不被使用的，所以把0换成4得到：2 4 3。由于2、3已经在内存里面，所以不用置换。由于4以后不被使用，所以把4置换成0得到：2 0 3。又由于3、2已在里面无需置换。由于3以后不被使用，把3置换成1得到：2 0 1。又因为2、0、1已在内存里面，所以无需置换。又由于2以后不被使用，所以把2置换成7得到：7 0 1。又因为0、1已经在内存里面，所以不用置换。分配完成。页面中断次数为6。实验结果与猜想一致，成功。3.1.2 假设系统分配了4块物理块，读取一个页面顺序：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1前4个直接进入内存即为：7 0 1 2。由于2已经在内存中，所以不需置换。由于7是未来最长时间不被使用的，所以把7置换成3得到：3 0 1 2。由于0已在内存里面，无需置换。由于1是未来最长时间不被使用，所以把1置换成4得到：3 0 4 2。由于2、3、0、3、2已经在内存里面，所以无需置换。由于3是未来不被使用，所以把3置换成1得到：1 0 4 2。又因为2、0、1已在内存里面，无需置换。由于4是未来时间不被使用，所以把4置换成7得到：1 0 7 2。因为0、1已在内存里面，所以无需置换。分配完成。页面中断次数为4。实验结果与猜想一致，成功。3.1.3 假设系统分配了5块物理块，读取一个页面顺序：7 0 1 2 3 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 前面5个数直接填满即为：7 0 1 2 3。由于3、0已经在内存里面，所以无需置换。由于7是在未来最长时间不被使用，所以把7置换成4得到：4 0 1 2 3。由于2、3、0、3、2、1、2、0、1已经在内存中，无需置换。由于4是未来不被使用的，所以把4置换成7得到：7 0 1 2 3。由于0、1已在内存里面，不需置换。分配完成。页面中断次数为2。实验结果与猜想一致，成功。3.2 FIFO页面置换算法结果与分析: 先进先出页面置换算法，就是总淘汰最先进入内存的页面。3.2.1 假设系统分配了3块物理块，读取一个页面顺序：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 前三个没有重复的，直接填满即：7 0 1，下一个数为2，不在内存中，则根据FIFO算法原则，将7换成2即：2 0 1。接下来进来的是一个0，在内存中，则不用置换。3要进来了，由于0是最先进来的，所以将0替换成3得到：2 3 1。1变成最先进来的了，则把1换成0，得到：2 3 0。这时2成了最先进来的，则把2换成4即：4 3 0。由于3最先进来，则把3换成2变成：4 2 0。由于0是最先进来的，把0换成3即：4 2 3。此时4变成最先进来的，把4换成0即：0 2 3。接下来进来的是2，在内存里面，不需置换，3同理可得不用置换即为：0 2 3。由于2是最先进来的，则把2置换成1得到：0 1 3。此时3为最先进来的，则把3置换成2即为：0 1 2。由于0，1已在里面，不需置换。由于0最先进入内存，则把0置换成7得到：7 1 2。由于1最先进入，则把1置换成0得到：7 0 2。由于2最先进入内存，则把2置换成1得到：7 0 1。分配完成。此时显示页面中断次数为12次。得到的实验结果与猜想的一样，猜想成功。3.2.2 假设系统分配了4块物理块，读取一个页面顺序：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1前面4个数没有出现重复，直接填满即：7 0 1 2。0在里面无需置换。由于7最先进入，则把7置换成3得到：3 0 1 2。由于0在里面，无需置换。此时0为最先进入，则把0置换成4得到：3 4 1 2。由于接下来进来的页面数2，3都在里面，则无需置换。此时1为最先进入，则把1置换成0即为：3 4 0 2。由于接下来进来的页面数3，2都在里面，则无需置换。此时2为最先进入，则把2置换成1得到：3 4 0 1。3为最先进入，则把3置换成2得到：2 4 0 1。由于接下来进来的页面数0,1都在里面，则无需置换。此时最先进入的为4，则把4置换成7得到：2 7 0 1。由于接下来进来的页面数0,1都在里面，则无需置换。分配完成，此时显示页面中断次数为6次。得到的实验结果与猜想的一致，成功。3.2.3 假设系统分配了5块物理块，读取一个页面顺序：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1前面四个直接进入内存即为：7 0 1 2。因为0已在内存中，不需置换。由于不在里面3直接进入得到：7 0 1 2 3。由于0在内存中，不需置换。由于7最先进入，则把7置换成4得到：4 0 1 2 3。由于2、3、0、3、2、1、2、0、1都在内存里面，不需置换。由于0最先进入，则把0置换成7得到：4 7 1 2 3。由于1为最先进入，则把1置换成0得到：4 7 0 2 3。由于2最先进入，则把2置换成1得到：4 7 0 1 3。分配完成。页面中断次数为：3。实验结果与猜想一样，成功。3.3 LRU页面置换算法结果与分析 LRU是选择最近最久未使用的页面予以淘汰。该算法富裕每个页面一个访问字段。用来记录一个页面自上次被访问以来所经历的时间a，当淘汰一个页面时，选择现有页面中其a值最大的，即最近最久未使用的页面予以淘汰。 3.3.1 假设系统分配了3块物理块，读取一个页面顺序：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1前三个直接进入内存即为：7 0 1。由于7最近最久未使用，则把7置换成2得到：2 0 1。由于0在内存里面，不需置换。由于1最近最久未使用，则把1置换成3得到：2 0 3。由于0 在内存中，不需置换。由于2最近最久未使用，则把2置换成4得到：4 0 3。由于3最近最久未使用，则把3置换成2得到：4 0 2。由于0最近最久未使用，则把0置换成3得到：4 3 2。由于4最近最久未使用，则把4置换成0得到：0 3 2。由于3、2已在内存中，不需置换。由于0最近最久未使用，则把0置换成1得到：1 3 2。由于2在内存中，不需置换。由于3最近最久未使用，则把3置换成0得到：1 0 2。由于1已在内存中，不需置换。由于2最近最近未使用，则把2置换成7得到：1 0 7。由于0、1已在内存中不需置换。分配完成。页面中断次数为9.实验结果与猜想一致，成功。 3.3.2 假设系统分配了4块物理块，读取一个页面顺序：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1前面四个直接填满即为：7 0 1 2。由于0在内存中不需置换。由于7是最近最久未使用，则把7置换成3得到：3 0 1 2。由于0已在内存中，不需置换。由于1最近最久未使用，则把1置换成4得到：3 0 4 2。由于2、3、0、3、2已在内存中，不需置换。由于4最近最久未使用，则把4置换成1得到：3 0 1 2。由于2、0、1已在内存中，不需置换。由于3最近最久未使用，则把3置换成7得到：7 0 1 2。由于0、1已在内存中，不需置换。分配完成。中断次数为4。实验结果和猜想一致。成功。3.3.3 假设系统分配了5块物理块，读取一个页面顺序：7 0 1 2 3 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1前面5个直接填满即为：7 0 1 2 3。由于3、0已在内存中不需置换。由于7最近最久未使用，则把7置换成4得到：4 0 1 2 3。由于2、3、0、3、2、1、2、0、1已在内存中，不需置换。由于4最近最久未使用，则把4置换成7得到：7 0 1 2 3。由于0、1已在内存中，不需置换。分配完成。页面中断次数为2。实验结果与猜想一致，成功。四、 程序创新点我们用C#语言编程，设计一个模拟虚拟存储器管理界面如上图所示。namespace WindowsFormsApplication1 partial class Form1 / / 必需的设计器变量。 / private System.ComponentModel.IContainer components = null; / / 清理所有正在使用的资源。 / / 如果应释放托管资源，为 true；否则为 false。 protected override void Dispose(bool disposing) if (disposing & (components != null) components.Dispose(); base.Dispose(disposing); #region Windows 窗体设计器生成的代码 / / 设计器支持所需的方法 - 不要 / 使用代码编辑器修改此方法的内容。 / private void InitializeComponent() this.label1 = new System.Windows.Forms.Label(); this.label2 = new System.Windows.Forms.Label(); this.input = new System.Windows.Forms.TextBox(); this.fenkuai3 = new System.Windows.Forms.RadioButton(); this.fenkuai4 = new System.Windows.Forms.RadioButton(); this.fenkuai5 = new System.Windows.Forms.RadioButton(); this.display1 = new System.Windows.Forms.RichTextBox(); this.xiayibu = new System.Windows.Forms.Button(); this.start = new System.Windows.Forms.Button(); this.button3 = new System.Windows.Forms.Button(); this.groupBox1 = new System.Windows.Forms.GroupBox(); this.optn = new System.Windows.Forms.RadioButton(); this.lrun = new System.Windows.Forms.RadioButton(); this.fifon = new System.Windows.Forms.RadioButton(); this.statusStrip1 = new System.Windows.Forms.StatusStrip(); this.toolStripStatusLabel1 = new System.Windows.Forms.ToolStripStatusLabel(); this.zhuangtai = new System.Windows.Forms.ToolStripStatusLabel(); this.groupBox1.SuspendLayout(); this.statusStrip1.SuspendLayout(); this.SuspendLayout();该界面可以实现的功能有：手动输入一个页面顺序和随机生成一个页面顺序。在算法中用了for循环语句不断嵌套，if条件选择语句不断对条件进行筛选，从而到达一个想要选择的目的。break跳出查询语句：要是条件不符合则跳出循环。定义了一个temp变量来记录三元算法结果，定义一个select变量选择记录的数组数。 int temp = r0 r1 ? r0 : r1; select = temp r2 ? temp : r2; if (select = r0)定义一个变量time记录进入物理块里面的时间间隔数。static int time = new int5;if(time0=0) time0=0; if (leng1.leng(kuai) = 1) / bu = 0; x.Text += n + s + + kuai0; for (int a = 0; a leng1.leng(kuai); a+) if (in + 1 = kuaia) n+; bu+; break; else if (bu = 0 & a = leng1.leng(kuai) - 1) bu = 0; kuai1 = in + 1; time1 = s; 实现了比如在内存块不满且进来是连续的页面顺序数时只占用一个内存块的设计即消除了特殊情况下输入特定的页面顺序数现象。五、 设计与总结我在组中负责代码的具体实现，在实现的过程总会遇到这样或那样的问题，比如因为马虎造成的数组下标错误，有时候因为一个算法，互相讨论，根据自己的理解和语言叙述，根据书中所给的例题去理解，查阅参考书以及上网查阅。用C#的原因是这学期我们学了C#课，而且做界面比较方便。在用代码实现的过程中，用了很多静态变量去完成按一次一步的要求，同时一边编程一边更深一步理解OPT、FIFO、LRU的算法。但是在编程过程中遇到了很多困难，经常重新再去除了查代码之外，还有结合现实情况去克服困难，不断重复，最终完成了更合适实际情况的编程。在编程过程中，讨论和思考是很必要的，思路会越来越清晰，代码会不断优化，越来越简洁，达到精简易读的效果。五天来,我们加深了对虚拟存储的认识,了解了操作系统中各种资源分配算法的实现,特别是对页面置换有了深入的了解,并能够用高级语言进行模拟演示。我们觉得这些付出都是值得的，因为我学到了很多关于编程的实现方法。六、 详细代码附录C#界面代码：（部分）namespace WindowsFormsApplication1 partial class Form1 / / 必需的设计器变量。 / private System.ComponentModel.IContainer components = null; / / 清理所有正在使用的资源。 / / 如果应释放托管资源，为 true；否则为 false。 protected override void Dispose(bool disposing) if (disposing & (components != null) components.Dispose(); base.Dispose(disposing); #region Windows 窗体设计器生成的代码 / / 设计器支持所需的方法 - 不要 / 使用代码编辑器修改此方法的内容。 / private void InitializeComponent() this.label1 = new System.Windows.Forms.Label(); this.label2 = new System.Windows.Forms.Label(); this.input = new System.Windows.Forms.TextBox(); this.fenkuai3 = new System.Windows.Forms.RadioButton(); this.fenkuai4 = new System.Windows.Forms.RadioButton(); this.fenkuai5 = new System.Windows.Forms.RadioButton(); this.display1 = new System.Windows.Forms.RichTextBox(); this.xiayibu = new System.Windows.Forms.Button(); this.start = new System.Windows.Forms.Button(); this.button3 = new System.Windows.Forms.Button(); this.groupBox1 = new System.Windows.Forms.GroupBox(); this.optn = new System.Windows.Forms.RadioButton(); this.lrun = new System.Windows.Forms.RadioButton(); this.fifon = new System.Windows.Forms.RadioButton(); this.statusStrip1 = new System.Windows.Forms.StatusStrip(); this.toolStripStatusLabel1 = new System.Windows.Forms.ToolStripStatusLabel(); this.zhuangtai = new System.Windows.Forms.ToolStripStatusLabel(); this.groupBox1.SuspendLayout(); this.statusStrip1.SuspendLayout(); this.SuspendLayout(); / / label1 / this.label1.AutoSize = true; this.label1.Location = new System.Drawing.Point(21, 9); this.label1.Name = label1; this.label1.Size = new System.Drawing.Size(137, 12); this.label1.TabIndex = 0; this.label1.Text = 请输入一个页面读取顺序; / / label2 / this.label2.AutoSize = true; this.label2.Location = new System.Drawing.Point(21, 55); this.label2.Name = label2; this.label2.Size = new System.Drawing.Size(101, 12); this.label2.TabIndex = 1; this.label2.Text = 请选择内存分块数; / / input / this.input.Location = new System.Drawing.Point(181, 6); this.input.Name = input; this.input.Size = new System.Drawing.Size(183, 21); this.input.TabIndex = 2; this.input.TextChanged += new System.EventHandler(this.input_TextChanged); / / fenkuai3 / this.fenkuai3.AutoSize = true; this.fenkuai3.Location = new System.Drawing.Point(181, 53); this.fenkuai3.Name = fenkuai3; this.fenkuai3.Size = new System.Drawing.Size(29, 16); this.fenkuai3.TabIndex = 3; this.fenkuai3.TabStop = true; this.fenkuai3.Text = 3; this.fenkuai3.UseVisualStyleBackColor = true; this.fenkuai3.CheckedChanged += new System.EventHandler(this.fenkuai3_CheckedChanged); / / fenkuai4 / this.fenkuai4.AutoSize = true; this.fenkuai4.Location = new System.Drawing.Point(253, 53); this.fenkuai4.Name = fenkuai4; this.fenkuai4.Size = new System.Drawing.Size(29, 16); this.fenkuai4.TabIndex = 4; this.fenkuai4.TabStop = true; this.fenkuai4.Text = 4; this.fenkuai4.UseVisualStyleBackColor = true; this.fenkuai4.CheckedChanged += new System.EventHandler(this.fenkuai4_CheckedChanged); / / fenkuai5 / this.fenkuai5.AutoSize = true; this.fenkuai5.Location = new System.Drawing.Point(321, 53); this.fenkuai5.Name = fenkuai5; this.fenkuai5.Size = new System.Drawing.Size(29, 16); this.fenkuai5.TabIndex = 5; this.fenkuai5.TabStop = true; this.fenkuai5.Text = 5; this.fenkuai5.UseVisualStyleBackColor = true; this.fenkuai5.CheckedChanged += new System.EventHandler(this.fenkuai5_CheckedChanged); / / display1 / this.display1.Location = new System.Drawing.Point(12, 100); this.display1.Name = display1; this.display1.Size = new System.Drawing.Size(352, 228); this.display1.TabIndex = 6; this.display1.Text = ; / / xiayibu / this.xiayibu.Location = new System.Drawing.Point(427, 345); this.xiayibu.Name = xiayibu; this.xiayibu.Size = new System.Drawing.Size(75, 23); this.xiayibu.TabIndex = 7; this.xiayibu.Text = 下一步; this.xiayibu.UseVisualStyleBackColor = true; this.xiayibu.Click += new Syste