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

课程设计汇报

题 目： 模拟请求页式管理

课程名称： 计算机操作系统
学 院： 信息工程学院
专 业： 计算机科学和技术
班 级： 14计本（1）
学生姓名： * * *
学 号： 03031**
指导老师： * *
成 绩：
开课时间： - 年 一 学期

模拟请求页式管理
第1章 需求分析
1.1设计要求
请求页式管理是一个常见虚拟存放管理技术。本设计经过请求页式存放管理中页面置换算法模拟设计，了解虚拟存放技术特点，掌握请求页式管理页面置换算法。本试验要求用Vc＋＋或其它高级语言编写和调试。
编写程序实现：  （1）优异先出页面置换算法（FIFO） （2）最近最久未使用页面置换算法（LRU） 最好置换页面置换算法（OPT） 设计一个虚拟存放区和内存工作区，编程序演示以上三种算法具体实现过程，并计算访问命中率。
1.2处理方案
首先确定实现语言使用c#实现图形化界面，后确定要实现哪些功效，比如算法选择，页面添加，模拟控制。然后确定输出结构方便于程序测试和验证。将基础框架建立后再进行编程。编程前进行算法结构分析最终编程实现。
1.3算法实现原理
1、优异先出置换算法（FIFO）：
发生缺页中止时根据页面进入内存次序总是淘汰最优异入内存页面。
2、最近最久未使用置换算法（LRU）：
发生缺页中止时总是淘汰存在内存中最长时间未被使用页面。
3、最好置换算法（OPT）：
发生缺页中止时若一个或多个页面未来将不会被调用则按优异先出标准淘汰页面，若未来全部有调用则比较调用时刻选择最远时刻页面淘汰。
4、缺页率：缺页次数占页面调用次数百分比。

第2章 概要设计
2.1数据设计
常变量：调用页面最大数量（MaxN），内存最大页面数（MaxM）
待调用页面数组：page_dd[MaxN]存放等候调用页面号
页面数组专用指针 page_p，用于指向page_dd数组中正需调入内存页号
内存块数组：Memery[MaxM]，存放内存目前存放页号
缺页计数器：count，统计缺页次数
内存块状态数组：M1[MaxN],M2[MaxN],M3[MaxN]，统计每次页面调用结束后内存各块状态
缺页统计数组s[MaxN]，用于统计页面调用时是否产生缺页中止，初始化为是
2.2函数设计
1、页面添加函数：void btnAdd_Click(object sender, EventArgs e)
用于实现经过点击按钮实现数据输入。
2、内存初始化函数：init(int[] a, int[] b,int []m1,int[]m2,int[]m3)
参数有页面数组、内存数组、状态数组，采取优异先出算法对内存优异行装满
服务于优异先出页面置换函数和最好置换函数。
3、 输出函数：void display(int[]a,int[]m1,int[]m2,int[]m3,char[]c)用于输出模拟结果，参数有页面数组，内存数组，状态数组，缺页统计数组。再模拟以后调用。
4、模拟控制函数：void btnmo_Click(object sender, EventArgs e）用于实现经过单击模拟按钮，依据用户所选算法进行模拟并显示结果。
5、优异先出算法模拟函数：
void FIFO(int[] a, int[] b,int[]m1,int[]m2,int[]m3,char[] s)用于实现优异先出算法模拟，参数有页面数组，内存数组、内存状态统计数组，缺页统计数组。在模拟函数中调用。
6、 最近最久未使用算法模拟函数：
void LRU(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s)用于实现最近最久未使用算法模拟，参数有页面数组，内存数组，内存状态统计数组，缺页统计数组。在模拟函数中被调用。
7、 最近最久未使用函数辅助函数：void LUR_I(int[] a,int e)用于对最近最久未使用算法中所用辅助数组（统计页面存在时长）进行调整，参数有辅助数组及需调整数据下标。在最近最久未使用函数中调用。
8、最好置换算法模拟函数：
void OPT(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s)用于模拟最好置换算法。参数有页面数组，内存数组，内存状态统计数组，缺页统计数组。在模拟函数中被调用。
9、 最好置换算法辅助函数：void OPT_F(int[] a, int e)用于对最好置换算法中辅助数组进行调整。参数有辅助数组，需调整数据下标。在最好置换算法中被调用。
10、 重置函数：void btncz_Click(object sender, EventArgs e)用于重新选择算法进行新模拟。
2.3关键算法设计
1、初始化函数算法：
第一步：将第一个页面调入内存，调整最好置换算法辅助数组，缺页计数器加一，保留内存数组状态。
第二步：调用下一个页面并判定内存中是否有本页面有转第三步，无转第四步。
第三步：更改缺页数组对应下标值，统计目前内存状态，调整最好置换算法辅助数组，页面指针指向下一页。
第四步：将页面调入内存，调整最好置换算法辅助函数，缺页计数器加一，保留内存数组状态。若内存尚不满转第一步。
具体见图1初始化算法步骤图。

图1 初始化算法步骤图

2、 优异先出页面置换算法：
第一步：检验内存中是否已经有需调用页面，有则转第二步，无则转第三步。
第二步：统计目前内存状态，修改缺页数组对应下标值。
第三步：内存中无需要调用页面，进行出队操作，然后进行入队操作，统计内存块状态，缺页计数器加一。
第四步：若页面数组未被调用结束转第一步。
具体见图2优异先出算法步骤图。

图2 优异先出算法步骤图

3、 最近最久未使用置换算法：
第一步：将页面调入内存，统计内存状态，缺页计数器加一，调整辅助数组，页面指针加一。
第二步：检验内存中是否已经有所需页面，有转第三步，无转第一步。
第三步：修改缺页数组对应下标统计，统计内存状态，调整辅助数组，页面指针加一。
第四步：内存是否已满，无则转第一步，是则转第五步。
第五步：检验内存中是否有所需页面，有则统计目前内存状态，修改缺页数组对应下标值。无则转第六步。
第六步：检验辅助数组找出最大值并统计其下标，置换内存中对应下标数据，调整辅助数组，缺页计数器加一。
第七步：页面是否调用结束未结束则转第五步。
具体见图3最近最久未使用算法步骤图。

图3 最近最久未使用算法

4、 最好置换算法：
第一步：检验内存中是否已经有所需页面，有则统计内存状态，修改缺页数组对应下标数值。无则转第二步。
第二步：判定内存中各页面未来调用情况，统计是否还有调用，若有则统计调用时刻。
第三步：分析调用情况，内存中页面全部在未来不会被调用转第四步，有一个被调用转第五步，有两个被调用转第六步，全被调用转第七步。
第四步:查找辅助数组找到内存中存在时间最长页面进行置换，修改内存状态，缺页计数器加一，修改辅助数组。
第五步：查找到不会被调用页面，并依据辅助数组选择最早进入内存页面将其置换。修改内存状态，缺页计数器加一，修改辅助数组。
第六步：查找辅助数组找到未来不需要在调用页面将其置换，修改辅助数组，统计内存状态，缺页计数器加一。
第七步：查找辅助数组，找寻最晚被调用页面，将其置换。统计内存状态，修改辅助数组，缺页计数器加一。
第八步：页面是否调用完成，不然转第一步。
具体见图4最好置换算法步骤图

图4 最好置换算法步骤图

2.4界面设计
采取c# 设计windows窗体应用程序，使用下拉列表框选择算法，经过按钮添加待调用页面。经过文本控件显示模拟结果。
显示样式：第一行：算法名称；
第二行：调用页面次序；
第三行至第五行显示内存在每调用一次页面后状态；
第六行：是否缺页；
最终一行显示缺页率；

第3章 具体设计和实现
3.1函数设计
1、添加按钮功效实现代码
关键功效：实现单击一次添加一个调用页面，并给出对应提醒，如正在输入是第几次调度页面，在输入为空时能够弹出对话框提醒用户，在输入完成时为避免数组越界应在输入完成时隐藏；输入过程中一直确保时输入焦点。
private void btnAdd_Click(object sender, EventArgs e)
{
if (txtAdd.Text != "")//输入不为空才能继续输入
{
page_dd[i_add] = Convert.ToInt32(txtAdd.Text);
/*将输入值赋值给页面数组*/
txtShow.Text += txtAdd.Text + " ";
/*显示供用户查阅*/
i_add++;
txtAdd.Clear();
/*清空*/
if (i_add == MaxN)//输入结束时
{
txtAdd.ReadOnly = true;//不许可继续输入
btnAdd.Hide();//按钮隐藏
return;
}
txtAdd.Focus();//设置为输入焦点
label2.Text = "第" + (i_add + 1) + "次调度页面：";
/*提醒用户正在输入是第几次调度页面*/
}
/*输入为空则弹出对话框提醒用户输入为空*/
else
{
MessageBox.Show("请输入调用页面！", "输入为空", MessageBoxButtons.OK, MessageBoxIcon.Warning);
txtAdd.Focus();
}
}

2、 初始化函数
关键功效：将内存一优异先出方法填满，并统计每个页面进入时间，服务于优异先出页面置换算法和最好置换算法。
void init(int[] a, int[] b,int []m1,int[]m2,int[]m3)
{
/*内存未满时循环*/
for (int i = 0; i < MaxM&&page_p <MaxN ; i++)
{
b[i] = a[page_p];//调入内存
//调整辅助数组将刚进入内存页面对应时间
OPT_F (O_Q ,i)；
count++;//缺页计数器加一
m1[page_p] = b[0];//保留内存状态
m2[page_p] = b[1];
m3[page_p] = b[2];
page_p++;//调用下一页面
//检验内存中是否原先就有需要页面；
for (int j = 0; j <= i&&page_p <MaxN ; j++)
{
if (b[j] == a[page_p])
{//找到这么页面
s[page_p] = 'F';//缺页数组对应数据更改
m1[page_p] = b[0];//统计内存状态
m2[page_p] = b[1];
m3[page_p] = b[2];
OPT_F(O_Q, -1);//调整最好置换算法辅助函数
page_p++;//调用下一页
j = -1;//重新开始寻求
}
}
}
}

3、 优异先出页面置换函数
关键功效：依据优异先出算法要求在产生缺页中止时采取优异先出方法确定淘汰页面，并在每次页面调用时统计下内存状态，缺页次数；采取循环队列使得每次出队一定是最优异入内存。
private void FIFO(int[] a, int[] b,int[]m1,int[]m2,int[]m3,char[] s)
{
int Fpage_p = page_p;
int front, rear;
//定义队列对手和对尾指针并初始化
front = 0;
rear = MaxM - 1;
int sa;
//定义页面处理标志为1则表明此页面已处理
for (; Fpage_p < MaxN; Fpage_p++)
{
//从目前位置开始往后扫描
sa = 0;
for (int i = 0; i < MaxM; i++)
//检验内存中是否已经有要调用页面。
{
//有需要页面则保留内存状态，修改缺页数组对应位值
if (b[i] == a[Fpage_p])
{
m1[Fpage_p] = b[0];
m2[Fpage_p] = b[1];
m3[Fpage_p] = b[2];
s[Fpage_p] = 'F';
sa = 1;
break;
//找到就退出应为只可能有一个符合页面
}
}
if (sa == 0)
{
//未找到一致页面产生缺页中止进行出队操作淘汰最早进入内存页面
//并统计内存状态，计数器加一。
front = (front + 1) % MaxM;
rear = (rear + 1) % MaxM;
b[rear] = a[Fpage_p];
m1[Fpage_p] = b[0];
m2[Fpage_p] = b[1];
m3[Fpage_p] = b[2];
count++;
}
else continue;
//内存原有一样页面则结束此次循环
}
}

4、 最近最久未使用函数
关键功效：实现对最近最久页面置换算法模拟，统计缺页次数和每次页面对应内存状态。
private void LRU(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s)
{
int[] L_Q = new int[MaxM]{3,3,3};
//辅助数组统计页面存在时间，初始值全部是3，每次对应位置有新页面进入就刷//新为1，比原来值小加一大于原来值得不变
int sa;
//页面已调用标志
for (int i = 0; i < MaxM && page_p < MaxN; i++)
{
//内存不满时实施将内存装满因其于优异先出不符合故不能调用初始化函数
b[i] = a[page_p];//调入内存
count++;
m1[page_p] = b[0];//保留内存状态
m2[page_p] = b[1];
m3[page_p] = b[2];
LUR_I(L_Q, i);
//调整辅助数组
page_p++;
for (int j = 0; j <= i && page_p < MaxN ; j++)
{
//判定已在内存中页面中是否有和将要调用页面一致页面
if (b[j] == a[page_p])
{
//有则修改缺页状态函数并统计目前内存状态
s[page_p] = 'F';
m1[page_p] = b[0];
m2[page_p] = b[1];
m3[page_p] = b[2];
LUR_I(L_Q, j);
page_p++;
j = -1;
}
}
}
for (; page_p < MaxN; page_p++)
{
//内存装满后从目前位置向后调用页面
sa = 0;
for (int i = 0; i < MaxM; i++)
//检验内存中是否已经有要调用页面。
{
if (b[i] == a[page_p])
{
//有则统计内存状态修改缺页数组调整辅助函数
m1[page_p] = b[0];
m2[page_p] = b[1];
m3[page_p] = b[2];
s[page_p] = 'F';
LUR_I(L_Q, i);
sa = 1;
break;
}
}
if (sa == 0)
{
for (int i = 0; i < MaxM; i++)
{
//产生缺页中止
if (L_Q[i] == 3)
//查找辅助数组找到值为3位置对应下标并
{
//替换此下标代表内存块页面并统计内存状态，调整辅助函数，计数器加一
b[i] = a[page_p];
m1[page_p] = b[0];
m2[page_p] = b[1];
m3[page_p] = b[2];
LUR_I(L_Q, i);
break;
}
}
count++;
}
else continue;
}
}
5、 最好置换算法
关键功效：模拟实现最好页面置换算法，淘汰内存中永远不会调用页面，假如有多个则采取优异先出标准进行置换，若多个页面在以后全部有调用则淘汰最终被调用页面，统计每次页面调用后内存状态，统计缺页中止数
private void OPT(int[]a,int[]b,int[]m1,int[]m2,int[]m3,char[]s)
{
int sa;//页面调用处理标志
int O_p;//页面数组辅助指针
int Ocount;//辅助计数变量
int[] OPT_I=new int [MaxM ]{-1 ,-1 ,-1 };
//辅助数组统计页面未来调用是否
int[] OPT_J=new int [MaxM]{MaxN ,MaxN ,MaxN };
//辅助数组统计页面未来被调用时刻
for (; page_p < MaxN; page_p++)
{
for (int i = 0; i < MaxM; i++)
{
OPT_I[i] = -1;//刷新状态数组
OPT_J[i] = MaxN;
}
sa = 0;
for (int i = 0; i < MaxM; i++)//检验内存中是否已经有要调用页面。
{
//将要调用页面存在于内存中
if (b[i] == a[page_p])
{
//统计内存状态修改缺页数组，调整辅助数组
m1[page_p] = b[0];
m2[page_p] = b[1];
m3[page_p] = b[2];
OPT_F(O_Q,-1);
s[page_p] = 'F';
sa = 1;
break;
}
}
if (sa == 0)//缺页
{
Ocount = 0;
for (int i = 0; i < MaxM; i++)
{
//向后查找页面调用情况用辅助数组统计
O_p = page_p + 1;
for (; O_p < MaxN; O_p++)
{
if (b[i] == a[O_p])
{
Ocount++;
OPT_I[i] = 1;
//表示下标代表页面未来会被调用
OPT_J[i] = O_p;
//表示其调用时刻
break;
}
}
}
switch (Ocount)
{
case 0:
//全部页面以后全部不会再度调用，查找辅助函数替换最优异入内存数组
int temp = 0;
for (int i = 0; i < MaxM; i++)
{
if (O_Q[i] > O_Q[temp])
temp = i;
}
b[temp] = a[page_p];
m1[page_p] = b[0];
m2[page_p] = b[1];
m3[page_p] = b[2];
OPT_F (O_Q ,temp);
count++;
break;
case 1:
//有一个页面将在以后调用，比较两个不会被调用页面谁优异入内存并置换之
temp = 0;
for (int i = 0; i < MaxM; i++)
{
if (OPT_I[i] != 1 && O_Q[i] > O_Q[temp])
temp = i;
}
b[temp] = a[page_p];
m1[page_p] = b[0];
m2[page_p] = b[1];
m3[page_p] = b[2];
OPT_F (O_Q ,temp);
count++;
break;
case 2:
//有两个页面将在以后被调用，直接淘汰未来不会调用那个
for (int i = 0; i < MaxM; i++)
{
if (OPT_I[i] == -1)
{
b[i] = a[page_p];
m1[page_p] = b[0];
m2[page_p] = b[1];
m3[page_p] = b[2];
OPT_F(O_Q, i);
count++;
}
}
break;
case 3:
//全部页面全部将被调用，查找辅助函数，得到最晚被调用页面并淘汰之
int p = 0;
for (int i = 0; i < MaxM; i++)
{
if (OPT_J[i] >OPT_J[p])
p = i;
}
b[p] = a[page_p];
m1[page_p] = b[0];
m2[page_p] = b[1];
m3[page_p] = b[2];
OPT_F(O_Q, p);
count++;
break;
}
}
}
}

6、 输出函数
关键功效：按既定形式输出模拟结果，并计算缺页率并输出
private void display(int[]a,int[]m1,int[]m2,int[]m3,char[]c)
{
lblshow.Text = "";
lblshow.Text =comboBox1.Text + ":\n";
//输出算法名称
for (int i = 0; i < MaxN; i++)
{
//输