请求页式存储管理模拟实验源代码及实验报告.doc
请求页式存储管理模拟实验源代码及实验报告
//请求页式存储管理模拟实验源代码及实验报告
//自己写的，程序写得比较简单，只为方便学弟学妹们 呵呵^ ^
//dlnu.
#include<iostream>
#include<process.h>
#include<stdlib.h>
#include <ctime>
#include <cstdlib>
using namespace std; int yemianliu[32]={0};//全局变量数组，地址流 int p; //全局变量 p 是一共有多少地址流
void chushihua()//初始化函数
{
int t;
srand(time(0));//随机产生指令序列
p=12+rand()%32;
cout<<"地址流序列:";
for(int i=0;i<p;i++)
{
t=1+rand()%9;
yemianliu[i]=t;//将随机产生的指令数存入页面流
cout<<t<<" ";
}
cout<<endl;
}
void FIFO(int n) //FIFO 算法，n 是 M 的值 {
int i;
int q=p;
int e;
int queye=0;
int flag;
int fifo[32]={0};
while(q--)
{
flag=0;
e=q;
for(i=0;i<n;i++)
{
if(fifo[i]==yemianliu[q])
{
flag=1;
break;
1
}
}
if(flag==0)
{
int m=n-1;
int k=m;
while(m--)
{
fifo[k]=fifo[k-1];
k--;
}
fifo[0]=yemianliu[e];
queye++;
}
}
cout<<"M="<<n<<"时 FIFO 的命中率为:"<<(1-((double)queye/p))*100<<"%"<<" ";
}
void LRU(int n)//LRU 算法 {
int i;
int q=p;
int e;
int queye=0;
int flag;
int flag1,;
int y;
int lru[32]={0};
while(q--)
{
flag=0;
e=q;
for(i=0;i<n;i++)
{
if(lru[i]==yemianliu[q])
{
flag=1;
flag1=i;
break;
}
}
if(flag==0)
{
int m=n-1;
2
int k=m;
while(m--)
{
lru[k]=lru[k-1];
k--;
}
lru[0]=yemianliu[e];
queye++;
}
else if(flag==1)
{
y=flag1;
while(y--)
{
lru[flag1]=lru[flag1-1];
flag1--;
}
lru[0]=yemianliu[e];
}
}
cout<<"M="<<n<<"时 LRU 的命中率为:"<<(1-((double)queye/p))*100<<"%"<<endl;
}
void main()
{
chushihua();
for(int i=3;i<33;i++)
{
FIFO(i);
LRU(i);
}
}
3
报告,
××××大学
计算机科学与工程学院实验报告 实验题目: 请求页式存储管理模拟
课程名称: 计算机操作系统
实验类型:?演示性 ?验证性 ?操作性 ?设计性 ?综合性 专业: 班级: 姓名: 学号: 实验日期:2012 年 5 月 24 日 实验地点: 实验学时: 实验成绩:
指导教师签字: 年 月 日
4
实验题目: ........................................................................................ 错误～未定义书签。
实验要求: ........................................................................................ 错误～未定义书签。
一、方案设计..................................................................................... 错误～未定义书签。
1.技术方案: .............................................................................. 错误～未定义书签。
(1)先进先出法(First In First Out): ....................... 错误～未定义书签。
(2)最近最久未使用(Least Recently Used): .............. 错误～未定义书签。
2.功能设计: .............................................................................. 错误～未定义书签。
(1)chushihua()函数的功能: ....................................... 错误～未定义书签。
(2)FIFO()的功能:....................................................... 错误～未定义书签。
(3)LRU()的功能: ........................................................ 错误～未定义书签。
二、结构设计..................................................................................... 错误～未定义书签。
1、数据结构设计 ........................................................................ 错误～未定义书签。
2、程序结构设计 ........................................................................ 错误～未定义书签。
三、程序设计..................................................................................... 错误～未定义书签。
1.FIFO()函数流程图; .............................................................. 错误～未定义书签。
2.LRU()函数流程图: ............................................................ 错误～未定义书签。
四、编码调试..................................................................................... 错误～未定义书签。
主要问题及解决方法: ............................................................... 错误～未定义书签。
五、实验总结..................................................................................... 错误～未定义书签。
六、程序清单..................................................................................... 错误～未定义书签。
源代码:..................................................................................... 错误～未定义书签。
运行结果: ................................................................................. 错误～未定义书签。
5
实验题目:
请求页式存储管理模拟
实验要求:
设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。
(1) 先进先出的算法(FIFO)
(2) 最近最久未用算法(LRU)
(3) 最近最不经常使用算法(NUR)*(选做) (4) 最佳淘汰算法(OPT)*(选做)
(5) 最少访问页面算法(LFU)*(选做)
命中率=1-页面失效次数/页面地址流长度
程序设计中，首先用 Srand()和 Rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，针对不同的算法计算出相应的命中率。
6
一、方案设计
1.技术方案:
(1)先进先出法(First In First Out):
该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。
在该算法的模拟过程中，每当页面需要被置换进入内存时，最先进入内存的内容们都依次向底移一位，需要访问的内容存入数组 0 号单元，即最顶部，这时缺页数加 1;当不需要进行页面置换，即所需访问的内容在内存中时，不需要操作，继续读下一条指令。这样就实现了总是淘汰最先进入内存的页面，选择了在内存中驻留时间最久的页面予以淘汰。
(2)最近最久未使用(Least Recently Used):
该算法将过去最长一段时间里不曾被使用的页面置换掉。
在该算法的模拟过程中，每当页面需要被置换进入内存时，最先进入内存的内容们都依次向底移一位，需要访问的内容存入数组 0 号单元，即最顶部，这时缺页数加 1;当不需要进行页面置换，即所需访问的内容在内存中时，将要访问的指令移到内存顶部，其他指令依次向下移一位，这样就把最久不用的指令沉到了底部，有必要时淘汰，即实现了总是淘汰最近最久未使用的指令。
2.功能设计:
(1)chushihua()函数的功能:
先由 Srand()和 Rand()函数定义和随机产生指令序列，然后将指令序列变换成相 应的页地址流存入地址流数组里。
(2)FIFO()的功能:
实现 FIFO 算法，淘汰最先进入内存的页面并根据缺页数算出命中率。
(3)LRU()的功能:
实现 LRU 算法，淘汰最近最久未使用的页面并根据缺页数算出命中率。
二、结构设计
1、数据结构设计
本程序使用了三个一维数组:
yemianliu[]存放地址指令流序列;
fifo[]存放 FIFO 算法时的内存指令;
lru[]存放 LRU 算法时的内存指令。
2、程序结构设计
7
开始
主函数
Chushihua() FIFO() LRU()
结束
三、程序设计
1.FIFO()函数流程图;
开始
得到执行的指令
指令是否 在内存中 否
queye 加 1，指令 是 存入内存，最先 存入指令被淘汰
是 下面是否 还有指令
否
得出命中率
结束
8
2.LRU()函数流程图:
开始
得到执行的指令
指令是否 在内存中
否
是
queye 加 1，指令 将指令移到数存入内存，淘汰 数组底部指令 组顶部，其他 依次下移一位
是 下面是否
还有指令
否
得出命中率
结束
9
四、编码调试
主要问题及解决方法:
刚开始老师的例题看不懂，虽然知道 FIFO 和 LRU 的原理，但不知道从何下手。我觉得老师的那个例题太复杂了，如果我也写那么复杂程序肯定崩溃得一塌糊涂，所以我觉 ，老师的例题和网上定按自己的理解写。我也搜了很多例题，但都和题目要求不太一样 的例题都用到了结构体数组，在内存的指令旁都附加了一个累加器，以访问次数和时间决定要淘汰的指令，而我是每访问一次后，按访问次数冒泡排序一次，这样最近被访问的就在数组的最顶上，最远被访问的在内存数组的最底部，没有用到循环队列，但也能实现功能。这次我没有用到结构体数组，也没有用到指针(有点遗憾)，不过测试了好几组数据，结果都和我用笔算的一样。在编程中，因为定义的变量太多了，取名也有点混乱，弄得我很晕，刚开始一直崩溃，后来我把程序的运行过程一步步的 cout 出来和调试，终于发现了错误的地方。开始我一直用 for()语句来控制循环，但是都找不到适合的让它结束循环的方法，后来才想到了可以用while(n--)来控制，效果还不错。还有就是第一次使用随机函数，有点陌生，上网查了些资料，终于会应用它了。这次试验大概就遇到了以上问题，都一一解决了，当然程序还是存在一些问题的，但是收获很多～
五、实验总结
通过本次实验，我对操作系统这门课程有了更进一步的认识和了解，通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解，也知道了几种算法的效率，也验证了 LRU 算法的命中率平均的比FIFO 算法的高。
过程中，用到了许多 C++的基本知识和操作系统的基本原理，是对平时所学在本次设计 知识的一次考验，尽管这些知识都学过，但运用到实际时，却不知从何下手，而且错误不断，往往为了找一个错误而花了大量的时间，这是专业知识掌握不够，缺乏实践动手能力的表现。在设计的过程中我们发现了许多自己的不足之处。
通过该实验，我收获了很多。我了解到编写程序不是首要任务，而是一种实现手段。我们最重要的是如何做好需求分析和理清思路，做出正确、简洁的流程设计，这样可以达到事半功倍的效果。
10
六、程序清单
源代码:
#inclu#include<iostream> de<process.h>
#include<stdlib.h>
#include <ctime>
#include <cstdlib>
using namespace std; int yemianliu[32]={0};//全局变量组数,地址流 int p; //全局变量 p 是一共有多少地址流
void chushihua()//初始化函数
{
int t;
srand(time(0));//随机产生指令序列
p=12+rand()%32; cout<<"地址流序列,";
for(int i=0;i<p;i++) {
t=1+rand()%9;
yemianliu[i]=t;//将随机产生的指令数存入页面流
cout<<t<<" ";
}
cout<<endl;
}
void FIFO(int n) //FIFO 算法,n 是 M 的值 {
int i;
int q=p;
int e;
int queye=0;
int flag;
int fifo[32]={0}; while(q--)
{
flag=0;
e=q;
for(i=0;i<n;i++)
{
if(fifo[i]==yemianliu[q])
{
flag=1;
11
break;
}
}
if(flag==0)
{
int m=n-1;
int k=m;
while(m--)
{
fifo[k]=fifo[k-1];
k--;
}
fifo[0]=yemianliu[e];
queye++;
}
}
cout<<"M="<<n<<"时 FIFO 的命中率为,"<<(1-((double)queye/p))*100<<"%"<<" ";
}
void LRU(int n)//LRU 算法 {
int i;
int q=p;
int e;
int queye=0;
int flag;
int flag1,;
int y;
int lru[32]={0};
while(q--)
{
flag=0;
e=q;
for(i=0;i<n;i++)
{
if(lru[i]==yemianliu[q])
{
flag=1;
flag1=i;
break;
}
}
if(flag==0)
{
12
int m=n-1;
int k=m;
while(m--)
{
lru[k]=lru[k-1];
k--;
}
lru[0]=yemianliu[e];
queye++;
}
else if(flag==1)
{
y=flag1;
while(y--)
{
lru[flag1]=lru[flag1-1];
flag1--;
}
lru[0]=yemianliu[e];
}
}
cout<<"M="<<n<<"时 LRU 的命中率为,"<<(1-((double)queye/p))*100<<"%"<<endl;
}
void main()
{
chushihua();
for(int i=3;i<33;i++)
{
FIFO(i);
LRU(i);
}
}
13
运行结果:
14
上一篇：红旗团委申报材料