操作系统专业课程设计方案报告.doc

上海电力学院

计算机操作系统原理
课程设计报告

题目名称： 编写程序模仿虚拟存储器管理
姓 名： 杜志豪　.学 号：　1798
班 级：　 053班 .
同组姓名： 孙嘉轶
课程设计时间： .6.30——.7.4
评语：

成绩：

目录
一、 设计内容及规定……………………………………………… 4
1. 1 设计题目……………………………………………………4
1．2 使用算法分析：…………………………………………… 4
1．2.1 FIFO算法（先进先出裁减算法）……………… 4
1．2.2 LRU算法（最久未使用裁减算法）……………… 5
1. 2.3 OPT算法（最佳裁减算法）……………………… 5
1.3 分工状况…………………………………………………… 5
二、 详细设计…………………………………………………………6
2.1 原理概述…………………………………………………… 6
2.2重要数据构造(重要代码)……………………………………6
2.3算法流程图………………………………………………… 9
2.3.1 主流程图………………………………………………9
2.3.2 Optimal算法流程图…………………………………10
2.3.3 FIFO算法流程图……………………………………10
2.3.4 LRU算法流程图……………………………………11
2.4．1源程序文献名……………………………………………11
2.4. 2执行文献名…………………………………………… 11
三、实验成果与分析……………………………………………………11
3.1 Optimal页面置换算法成果与分析…………………… 11
3.2 FIFO页面置换算法成果与分析……………………… 16

3.3 LRU页面置换算法成果与分析……………………… 20
四、设计创新点………………………………………………………24
五、设计与总结………………………………………………………27
六、代码附录…………………………………………………………27

课程设计题目
一、 设计内容及规定
1.1 编写程序模仿虚拟存储器管理。假设以M页进程分派了N块内存（N<M）。
输入：设定系统分派块数，以及进程页面引用序列（也可随后产生）。
输出：显示每一次页面引用内存状态，最后显示产生缺页中断次数及页面置换次数（假设初始状态内存没有装入任何页面）。
必要分别使用如下置换算法完毕模仿：
(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来选取详细算法；用一种数组int[]xulie来存储页面序列，长度为20；用一种数组int[]kuai来存储内存分派物理块个数，长度为5；用int s来记录详细环节数，用int num来记录页面中断次数。空白表达物理块没有被使用。
2.2 重要数据构造（代码）构造体：
输入页面序列号：
public Form1() //输入页面序列号
{
InitializeComponent();
for (int i = 0；i < xulie.Length；i++)
{
xulie[i] = -1;
}
for (int i = 0；i < kuai.Length；i++)
{
kuai[i] = -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 (x[i] == -1)
break;

}
return i;

}
}
构造体存储队列页面有关变量参数：
int buffer = 0;//内存分块数
string suanfa;//选取算法
int[] xulie = new int[20];//页面序列
int[] kuai = new int[5];
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
{
/// <summary>
/// 必须设计器变量。
/// </summary>
private System.ComponentModel.IContainer components = null;

/// <summary>
/// 清理所有正在使用资源。
/// </summary>
/// <param name="disposing">如果应释放托管资源，为 true；否则为 false。</param>
protected override void Dispose(bool disposing)
{
if (disposing && (components != null))
{
components.Dispose();
}
base.Dispose(disposing);
}

#region Windows 窗体设计器生成代码

/// <summary>
/// 设计器支持所需办法 - 不要
/// 使用代码编辑器修改此办法内容。
/// </summary>
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 = r[0] > r[1] ?r[0] ：r[1];
select = temp > r[2] ?temp ：r[2];
if (select == r[0])

定义一种变量time记录进入物理块里面时间间隔数。
static int[] time = new int[5];

if(time[0]==0)
time[0]=0;
if (leng1.leng(kuai) == 1)
{
// bu = 0;
x.Text += "\n " + s + " " + kuai[0];
for (int a = 0；a < leng1.leng(kuai)；a++)

if (i[n + 1] == kuai[a])
{
n++；bu++;

break;

}
else if (bu == 0 && a == leng1.leng(kuai) - 1)
{
bu = 0;
kuai[1] = i[n + 1];
time[1] = s;

实现了例如在内存块不满且进来是持续页面顺序数时只占用一种内存块设计即消除了特殊状况下输入特定页面顺序数现象。
五、 设计与总结
我在组中负责代码详细实现，在实现过程总会遇到这样或那样问题，例如由于马虎导致数组下标错误，有时候由于一种算法，互相讨论，依照自己理解和语言论述，依照书中所给例题去理解，查阅参照书以及上网查阅。用C#因素是这学期咱们学了C#课，并且做界面比较以便。在用代码实现过程中，用了诸多静态变量去完毕按一次一步规定，同步一边编程一边更深一步理解OPT、FIFO、LRU算法。但是在编程过程中遇到了诸多困难，经常重新再去除了查代码之外，尚有结合现状去克服困难，不断重复，最后完毕了更适当实际状况编程。在编程过程中，讨论和思考是很必要，思路会越来越清晰，代码会不断优化，越来越简洁，达到精简易读效果。
五天来,咱们加深了对虚拟存储结识,理解了操作系统中各种资源分派算法实现,特别是对页面置换有了进一步理解,并可以用高档语言进行模仿演示。咱们觉得这些付出都是值得，由于我学到了诸多关于编程实现办法。
六、 详细代码附录
C#界面代码：（某些）
namespace WindowsFormsApplication1
{
partial class Form1
{
/// <summary>
/// 必须设计器变量。
/// </summary>
private System.ComponentModel.IContainer components = null;

/// <summary>
/// 清理所有正在使用资源。
/// </summary>
/// <param name="disposing">如果应释放托管资源，为 true；否则为 false。</param>
protected override void Dispose(bool disposing)
{
if (disposing && (components != null))
{
components.Dispose();
}
base.Dispose(disposing);
}

#region Windows 窗体设计器生成代码

/// <summary>
/// 设计器支持所需办法 - 不要
/// 使用代码编辑器修改此办法内容。
/// </summary>
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 = "请选取内存分块数";
//