实验报告
课程名称 计算机操作系统
实验名称 存储管理
专业班级 计1103
学生姓名 贾梦洁
指导教师 王潇潇
实 验 报 告
课程名称 操作系统原理 实验名称 实验二 存储管理
姓 名 贾梦洁 学 号 201107010330 专业班级 计1103
实验日期 2014 年 5月15 日 成绩 指导教师 王潇潇
一.实验内容:
模拟请求页式存储管理中硬件的地址转换和缺页中断,并用先进先出调度算法(FIFO)处理缺页中断;
二.实验要求:
① 指令序列的设定可以执行拟定,格式如表3;
② 在完成了FIFO换页策略后,可以选做LRU的换页策略,并进行比较;
③ 作业允许的页架数m在不同情况下的缺页中断率;
④ 程序运行时显示地址转变和页面调入调出过程。
三.实验步骤:
①设计一个地址转换程序半模拟硬件的地址转换和缺页中断。
当访问的页在主存时则形成绝对地址,但不去模拟指令的执行,可以输出转换后的绝对地址来表示一条指令已执行完成。当访问的页不在主存中时,则输出“*页号”来表示硬件产生了一次缺页中断。模拟地址转换流程见图1.1。
② 设计FIFO页面调度程序;
FIFO页面调度算法总是先调出作业中最先进入主存中的哪一页。因此可以用一个数组来表示(或构成)页号队列。数据中每个元素是该作业已在主存中的页面号,假定分配给作业的页(架)数为m,且该作业开始的m页已装入主存,则数组可由m个元素构成。
P[0],P[1],P[2],…,P[m-1]
它们的初值为P[0]:=0,P[1]:=1,P[2]:=2,…,P[m-1]:=m-1
用一指针K指示当要调入新页时应调出的页在数组中的位置,K的初值为“0”,当产生缺页中断后,操作系统总是选择P[K]所指出的页面调出,然后执行。
③ 设计输入数据和输出格式;
如: 假定主存中页架大小为1024个字节,现有一个共7页的作业,其副本已在磁盘上。系统为该作业分配了4个页架,且该作业的第0页至第3页已装入内存,其作3页未主存,该作业的页表如下:
如果该作业依次执行的指令序列如附表3所示:
依次执行上述指令调试你所设计的程序(仅模拟指令的执行,不考虑序列中具体操作的执行)。
四.实验具体操作
① 新页号算法实现K:=(k+1)mod m,k = (k + 1) % 4;
② 绝对地址算法求法:页架号*1024+页内偏移。,pageTable[x][2] * 1024 + y;
③ 具体代码实现如下:
#include <stdio.h>
#include <stdlib.h>
void main(void)
{
int pageTable[7][5]={
{0, 1, 5, 0, 011},
{1, 1, 8, 0, 012},
{2, 1, 9, 0, 013},
{3, 1, 1, 0, 021},
{4, 0, -1, 0, 022},
{5, 0, -1, 0, 023},
{6, 0, -1, 0, 121}};//初始化页表值
int p[4] = {0, 1, 2, 3};//已在内存的页号
int k = 0;
int h, x, y, j = 1;
while(j != -1)
{
printf("请输入当前指令要访问的页号: ");
scanf("%d", &x);
if(x < 0 || x > 6)
{
printf("输入的页号有错误,请输入页号范围内的一个数(1~6)\n");
printf("要访问的%d页不在内存中!!\n", x);
//exit(0);
//break;
}
if(pageTable[x][1] == 1)
{
printf("请输入当前指令要访问的页内地址: ");
scanf("%d", &y);
printf("请输入当前指令的类型(1代表存指令,0代表非存指令): ");
scanf("%d", &h);
if(h != 1 && h != 0)
{
printf("指令参数出错,请输入指定的参数0或1\n");
printf("请输入当前指令的类型(1代表存指令,0代表非存指令): ");
scanf("%d", &h);
//exit();
}
else if(h == 1)
{
pageTable[x][3] = 1;
}
printf("要访问的物理地址为: %d\n", pageTable[x][2] * 1024 + y);
}
else
{
//printf("要访问的%d页不在内存中!!\n", x);
if(pageTable[p[k]][3] == 1)
{
//printf("OUT %d\n", p[k]);
printf("IN %d\n", x);
}
else
printf("OUT %d\n", p[k]);
pageTable[x][2] = pageTable[p[k]][2];//将标志为0的付给x
pageTable[p[k]][1] = 0;//修改0号页号标志为0
pageTable[p[k]][2] = -1;//将叶架号改为-1
p[k] = x;//修改p[k]初始值{x123}
pageTable[x][1] = 1;//进入内存标志
k = (k + 1) % 4;//获取x叶架号
}
printf("是否还有指令(1代表还有指令,0代表没有了): ");
scanf("%d", &j);
if(j != 1 && j != 0)
{
printf("输入参数错误\n");
printf("请输入指定的参数1或0!");
printf("是否还有指令(1代表还有指令,0代表没有了): ");
exit(0);
}
else if(j == 0)
exit(0);
}
}
四.实验运行结果:
五.实验心得总结
通过这次实验,我掌握了存储管理部分的相关知识。懂得如何通过编写程序使得程序运行时显示地址转变和页面调入调出过程。不得不说网络是一个很强大的东西,每当有不会的时候只要通过网络搜索一下就能得到自己想要的答案。其次,同学之间的讨论互助也是必不可少的。每次只要做的实验和编程有关系我总要依靠同学,问他们。即便程序不是自己亲手编写的,也要把它都弄懂,至少要知道它每一步是做什么用的。我觉得这样与我而言也是一种提高。对我以后的深入学习也是一种铺垫,打下了自己编写程序的基础。
第二篇:实验四 操作系统存储管理实验报告
实验四 操作系统存储管理实验报告
一、实验目的
存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法。
二、实验内容
(1)
通过计算不同算法的命中率比较算法的优劣。同时也考虑了用户内存容量对命中率的影响。
页面失效次数为每次访问相应指令时,该指令所对应的页不在内存中的次数。
在本实验中,假定页面大小为1k,用户虚存容量为32k,用户内存容量为4页到32页。
(2) produce_addstream通过随机数产生一个指令序列,共320条指令。
A、 指令的地址按下述原则生成:
1) 50%的指令是顺序执行的
2)25%的指令是均匀分布在前地址部分
3) 25%的指令是均匀分布在后地址部分
B、 具体的实施方法是:
1) 在[0,319]的指令地址之间随机选取一起点m;
2) 顺序执行一条指令,即执行地址为m+1的指令;
3) 在前地址[0,m+1]中随机选取一条指令并执行,该指令的地址为m’;
4) 顺序执行一条指令,地址为m’+1的指令
5) 在后地址[m’+2,319]中随机选取一条指令并执行;
6) 重复上述步骤1)~5),直到执行320次指令
C、 将指令序列变换称为页地址流
在用户虚存中,按每k存放10条指令排列虚存地址,即320条指令在虚存中的存放方式为:
第0条~第9条指令为第0页(对应虚存地址为[0,9]);
第10条~第19条指令为第1页(对应虚存地址为[10,19]);
。。。。。。
第310条~第319条指令为第31页(对应虚存地址为[310,319]);
按以上方式,用户指令可组成32页。
(3)计算并输出下属算法在不同内存容量下的命中率。
1)先进先出的算法(FIFO);
2)最近最少使用算法(LRU);
3)最佳淘汰算法(OPT);
4)最少访问页面算法(LFR);
其中3)和4)为选择内容
三、系统框图
五 运行结果
首先打印出产生的指令信息,第一列为指令序列号,第二列为指令地址,第三列为 指令所在的虚页号
选择FIFO调度算法,并且内存从3也开始逐渐增加到32页,打印出缺页次数缺页率,命中率
选择LRU调度算法,并且内存从3也开始逐渐增加到32页,打印出缺页次数缺页率,命中率
选择OPT调度算法,并且内存从3也开始逐渐增加到32页,打印出缺页次数缺页率,命中率
六 实验程序
产生指令流文件produce_addstream.h
#ifndef PRODUCE_ADDSTREAM_H
#define PRODUCE_ADDSTREAM_H
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<iomanip.h>
#include<vector>
using namespace std;
#define random(x) (rand()%x)
#define MAX_LENGTH 320
struct produce
{
int num; //指令序号
int zhiling; //指令地址
int virtualpage; //指令虚页号
produce *next;
};
struct produce*creatlist();
void insert(struct produce *first,struct produce *s); //插入一个节点(尾插法)
void print(struct produce *first); //打印函数
int max(vector<vector<int> >,int );
struct produce*creatlist()
{
srand((int)time(0));
struct produce*first=new produce;
first->next=NULL;
int m=0,m1=0;
/*
int yanzheng[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
for (int i=0;i<(MAX_LENGTH/4);i++)
{
struct produce *s0;
s0=new produce;
s0->num=i*4+0;
s0->zhiling=yanzheng[i*4+0];
s0->virtualpage=s0->zhiling;
insert(first,s0);
struct produce *s1;
s1=new produce;
s1->num=i*4+1;
s1->zhiling=yanzheng[i*4+1];
s1->virtualpage=s1->zhiling;
insert(first,s1);
struct produce *s2;
s2=new produce;
s2->num=i*4+2;
s2->zhiling=yanzheng[i*4+2];
s2->virtualpage=s2->zhiling;
insert(first,s2);
struct produce *s3;
s3=new produce;
s3->num=i*4+3;
s3->zhiling=yanzheng[i*4+3];
s3->virtualpage=s3->zhiling;
insert(first,s3);
}
//*/
//*
for (int i=0;i<(MAX_LENGTH/4);i++)
{
struct produce *s0;
s0=new produce;
m=random(MAX_LENGTH);
s0->num=i*4+0;
s0->zhiling=m+1;
s0->virtualpage=s0->zhiling/10;
insert(first,s0);
m1=random(m+1);
struct produce *s1;
s1=new produce;
s1->num=i*4+1;
s1->zhiling=m1;
s1->virtualpage=s1->zhiling/10;
insert(first,s1);
struct produce *s2;
s2=new produce;
s2->num=i*4+2;
s2->zhiling=m1+1;
s2->virtualpage=s2->zhiling/10;
insert(first,s2);
struct produce *s3;
s3=new produce;
s3->num=i*4+3;
s3->zhiling=random(MAX_LENGTH-m1-2)+m1+2;
s3->virtualpage=s3->zhiling/10;
insert(first,s3);
}//*/
return first;
}
void insert(struct produce *first,struct produce *s)
{
struct produce *r=first;
struct produce *p;
while(r){p=r;r=r->next;}
p->next=s;p=s;
p->next=NULL;
}
void print(struct produce *first) //打印函数
{
struct produce *p;
p =first->next;
cout<<"随机产生的指令的信息如下"<<endl;
cout<<"指令序号 "<<"指令地址 "<<"指令虚页号"<<endl;
while (p)
{
cout<<p->num<<'\t'<<p->zhiling<<setw(14)<<p->virtualpage<<endl;
p=p->next;
}
}
int max(vector<vector<int> > page,int Maxpage)
{
int a=0,position=0;
for (int i=0;i<Maxpage;i++)
{
if (page[i][1]>a)
{
a=page[i][1];
position=i;
}
}
return position;
}
#endif
先来先出调度算法:fifo.h
#ifndef FIFO_H
#define FIFO_H
void fifo(struct produce *first,int Maxpage)
{
vector<int> page(Maxpage);//
for (int i=0;i<Maxpage;i++)page[i]=-1;
int rear=0;//定义一个变量,指向要被替换的位置
int pages;//定义变量保存当前指令的所在的地址
int count1=0;//
int count2=0;//缺页次数
int find=1;
struct produce *p=first->next;
while (p)
{
pages=p->virtualpage;
for(int i=0;i<Maxpage;i++)
{
if (page[i]==-1||count1<Maxpage)
{
page[i]=pages;
count1 ++;
count2 ++;
find =1;
break;
}
else if (page[i]==pages)
{
find =1;
break;
}
find=0;
}
if (find==0)
{
page[rear]=pages;
rear ++;
rear=rear%Maxpage;
count2 ++;
}
p=p->next;
}
cout<<"FIFO调度算法缺页次数 缺页率 命中率"<<endl;
cout<<count2<<setw(25)<<double(count2)/MAX_LENGTH<<setw(10)<<1-double(count2)/MAX_LENGTH<<endl;
}
#endif FIFO_H
LRU调度算法lru.h
#ifndef LRU_H
#define LRU_H
#include<vector>
using namespace std;
//int max(vector<vector<int> >,int );
void lru(struct produce*first,int Maxpage)
{
struct produce*p=first->next;
vector<vector<int> > page2(Maxpage, vector<int>(2));
int count1=0; //定义内存已经被占用的页数
int count2=0; //定义记录缺页次数
int equal=0; //定义判断如果当前页数与比较的页数,如果相等则为1,否则为0
int place=0; //定义要替换的位置
for (int i=0;i<Maxpage;i++)
{
page2[i][0]=-1;page2[i][1]=0;
}
while (p)
{
if (count1<Maxpage)
{
for (int i=0;i<Maxpage;i++)
{
page2[i][1]=page2[i][1]+1;
if (page2[i][0]==-1)
{
page2[i][0]=p->virtualpage;
count2++;
break;
}
else if (page2[i][0]==p->virtualpage)
{
page2[i][1] =1;
}
}
count1++;
}
else
{
for (int i=0;i<Maxpage;i++)
{
page2[i][1] +=1;
if (page2[i][0]==p->virtualpage)
{equal=1;place=i;break;}
}
if (equal==1)
{
page2[place][1] =1;
equal=0;
}
else
{
place = max(page2,Maxpage);
page2[place][1]=1;
page2[place][0]=p->virtualpage;
count2++;
}
}
p=p->next;
}
cout<<"LRU调度算法缺页次数 缺页率 命中率"<<endl;
cout<<count2<<setw(24)<<double(count2)/MAX_LENGTH<<setw(10)<<1-double(count2)/MAX_LENGTH<<endl;
}
#endif LRU_H
OPT调度算法opt.h
#ifndef OPT_H
#define OPT_H
#include<vector>
using namespace std;
int search(struct produce*place,int position);
void opt(struct produce*first,int Maxpage)
{
struct produce*p =first->next;
vector<vector<int> > page3(Maxpage, vector<int>(2));
int count1=0; //定义内存已被使用的页数
int count2=0; //定义缺页次数
int current=0; //定义当前工作位置
int equal=0; //定义判断如果当前页数与比较的页数,如果相等则为1,否则为0
int place=0; //定义要替换的位置
for (int i=0;i<Maxpage;i++)
{
page3[i][0]=-1;page3[i][1]=0;
}
while (p)
{
//cout<<1111<<endl;
if (count1<Maxpage)
{
for (int i=0;i<Maxpage;i++)
{
if (page3[i][0]==-1)
{
page3[i][0]=p->virtualpage;
page3[i][1]=search(p,current);
count2++;
break;
}
else if (page3[i][0]==p->virtualpage)
{
page3[i][1]=search(p,current);
}
}
count1++;
}
else
{
for (int i=0;i<Maxpage;i++)
{
if (page3[i][0]==p->virtualpage)
{equal=1;place=i;break;}
}
if (equal==1)
{
page3[place][1] =search(p,current);
equal=0;
}
else
{
place = max(page3,Maxpage);
page3[place][1]=search(p,current);
page3[place][0]=p->virtualpage;
count2 +=1;
}
}
p=p->next;
current +=1;
}
cout<<"OPT调度算法缺页次数 缺页率 命中率"<<endl;
cout<<count2<<setw(25)<<double(count2)/MAX_LENGTH<<setw(10)<<1-double(count2)/MAX_LENGTH<<endl;
}
int search(struct produce*place,int position)
{
struct produce*p=place->next;
int current=place->virtualpage;
int position1=position+1;
while(p)
{
if (current==p->virtualpage)
{
return position1;
}
position1++;
p=p->next;
}
return position1;
}
#endif
主函数控制台ccglmain.cpp
#include<iostream.h>
#include "produce_addstream.h"
#include "fifo.h"
#include "lru.h"
#include "opt.h"
void main()
{
int S; //定义变量记录用户选择
char again; //定义变量用户选择继续还是退出
cout<<"开始产生内存指令"<<endl;
struct produce *first=creatlist();//产生随机指令
cout<<"打印产生的指令信息"<<endl;
print(first);//打印产生的指令信息
while (1)
{
int Maxpage=3;//定义内存最大页面数
cout<<"输入你的选择"<<endl;
cout<<"1:FIFO(先进先出)调度算法\n"<<"2:LRU(最近最少使用算法)\n"<<"3:OPT(最佳淘汰算法)\n"<<"4:清屏"<<endl;
cin>>S;
while(S>4||S<1)
{
cout<<"输入错误重新输入"<<endl;
cin>>S;
}
if (S!=4)
{
while(Maxpage<=32)
{
switch(S)
{
case 1:fifo(first,Maxpage);break;
case 2:lru(first,Maxpage);break;
case 3:opt(first,Maxpage);break;
default:break;
}
Maxpage++;
}
cout<<"是否继续调用其他算法?是请按y/Y,否请按其它键"<<endl;
cin>>again;
if(again=='y'||again=='Y')
{
continue;
}
else break;
}
else system("cls");
}
}