虚拟存储器中页面置换算法的实现课程设计_段页式存储管理方式的内存地址为
算法 实现 方式 页面 课程设计 存储管理 置换 内存地址
2023-06-13 09:14:50 时间
- 设计目的
通过请求页式存储管理中页面置换算法模拟程序，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。
- 设计内容
阅读教材《计算机操作系统》第四章，掌握存储器管理相关概念和原理。
模拟实现页式虚拟存储管理的三种页面置换算法（OPT、FIFO和LRU），并通过比较性能得出结论。
前提：
（1）页面分配采用固定分配局部置换。
（2）作业的页面走向和分得的物理块数预先指定。可以从键盘输入也可以从文件读入。
（3）置换算法的置换过程输出可以在显示器上也可以存放在文件中，但必须清晰可读，便于检验。
- 基本原理和解决方案
存储管理是操作系统进行资源管理的一个重要功能。现代操作系统广泛采用虚拟存储的技术对内存进行扩充。实现虚拟存储的一个主要技术手段就是将辅存和主存统一管理，在二者之间进行对换，从而形成物理上两级而逻辑上一级的存储管理系统。一个置换算法的好坏对这个逻辑上的单级虚存的性能起着极其重要的作用，而且会影响处理机的调度性能。
对于本任务规定的前提：页面分配采用固定分配局部置换，则置换发生的时机是作业已经将操作系统分配的固定数目的物理块全部用完且发生缺页的时候。此时必须要将已经装入内存的部分逻辑页面换出以便将所缺的页面调入内存。置换算法就是一个决定将内存中“哪一个”页面换出的算法。
- 实验内容
1.通过随机数产生一个指令序列，共320条指令，指令的地址按下述原则生产：
50％的指令是顺序执行的；
25％的指令是均匀分布在前地址部分；
25％的指令是均匀分布在后地址部分。
2.将指令序列变换成为页地址流
设页面大小为1K；用户内存容量为4页到32页；用户虚存容量为32K。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条至第9条指令为第0页；第10条至19条指令为第1页；…第310条至319条指令为第31页。
3.计算并输出下述各种算法在不同内存容量下的命中率。
(1) 先进先出算法（FIFO）
(2) 最近最少使用算法（LRU）
(3) 最佳使用算（OPT）
命中率＝１－页面失效次数／页地址流长度
本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。
代码：
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n") /*表格控制*/
#define bsize 4 //物理块大小
#define psize 16 //进程大小
typedef struct page
{
int num; /*记录页面号*/
int time; /*记录调入内存时间*/
}Page; /* 页面逻辑结构，结构为方便算法实现设计*/
Page b[bsize]; /*内存单元数*/
int c[bsize][psize]; /*暂保存内存当前的状态：缓冲区*/
int queue[100]; /*记录调入队列*/
int K; /*调入队列计数变量*/
int phb[bsize]={0}; //物理块标号
int pro[psize]={0}; //进程序列号
int flag[bsize] = {0}; //进程等待次数(存放最久未被使用的进程标志)
int i = 0, j = 0,k = 0; //i表示进程序列号,j表示物理块号
int m = -1, n = -1; //物理块空闲和进程是否相同判断标志
int max = -1,maxflag = 0; //标记替换物理块进程下标
int count = 0; //统计页面缺页次数
//随机产生序列号函数
int* build()
{
printf("随机产生一个进程序列号为：\n");
int i = 0;
for(i=0; i<psize; i++)
{
pro[i] = 10*rand()/(RAND_MAX+1)+1;
printf("%d ",pro[i]);
}
printf("\n");
return(pro);
}
//查找空闲物理块
int searchpb()
{
for(j=0; j<bsize; j++)
{
if(phb[j] == 0)
{
m = j;
return m;
break;
}
}
return -1;
}
//查找相同进程
int searchpro()
{
for(j = 0; j < bsize; j++)
{
if(phb[j] == pro[i])
{
n = j;
return j;
}
}
return -1;
}
//初始化内存
void empty()
{
for(i=0;i<bsize;i++)
phb[i]=0;
count=0; //计数器置零
}
//先进先出页面置换算法
void FIFO()
{
for(i = 0; i<psize; i++)
{
m=searchpb();
n=searchpro();
//找flag值最大的
for(j = 0; j < bsize;j++)
{
if(flag[j]>maxflag)
{
maxflag = flag[j];
max = j;
}
}
if(n == -1) //不存在相同进程
{
if(m != -1) //存在空闲物理块
{
phb[m] = pro[i]; //进程号填入该空闲物理块
count++;
flag[m] = 0;
for(j = 0;j <= m; j++)
{
flag[j]++;
}
m = -1;
}
else //不存在空闲物理块
{
phb[max] = pro[i];
flag[max] = 0;
for(j = 0;j < bsize; j++)
{
flag[j]++;
}
max = -1;
maxflag = 0;
count++;
}
}
else //存在相同的进程
{
phb[n] = pro[i];
for(j = 0;j < bsize; j++)
{
flag[j]++;
}
n = -1;
}
for(j = 0 ;j < bsize; j++)
{
printf("%d ",phb[j]);
}
printf("\n");
}
printf("缺页次数为：%d\n",count);
printf("\n");
}
/*初始化内存单元、缓冲区*/
void Init(Page *b,int c[bsize][psize])
{
int i,j;
for(i=0;i<psize;i++)
{
b[i].num=-1;
b[i].time=psize-i-1;
}
for(i=0;i<bsize;i++)
for(j=0;j<psize;j++)
c[i][j]=-1;
}
/*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/
int GetMax(Page *b)
{
int i;
int max=-1;
int tag=0;
for(i=0;i<bsize;i++)
{
if(b[i].time>max)
{
max=b[i].time;
tag=i;
}
}
return tag;
}
/*判断页面是否已在内存中*/
int Equation(int fold,Page *b)
{
int i;
for(i=0;i<bsize;i++)
{
if (fold==b[i].num)
return i;
}
return -1;
}
/*LRU核心部分*/
void Lruu(int fold,Page *b)
{
int i;
int val;
val=Equation(fold,b);
if (val>=0)
{
b[val].time=0;
for(i=0;i<bsize;i++)
if (i!=val)
b[i].time++;
}
else
{
queue[++K]=fold;/*记录调入页面*/
val=GetMax(b);
b[val].num=fold;
b[val].time=0;
for(i=0;i<bsize;i++)
if (i!=val)
b[i].time++;
}
}
void LRU()
{
int i,j;
K=-1;
Init(b, c);
for(i=0;i<psize;i++)
{
Lruu(pro[i],b);
c[0][i]=pro[i];
/*记录当前的内存单元中的页面*/
for(j=0;j<bsize;j++)
c[j][i]=b[j].num;
}
/*结果输出*/
printf("内存状态为：\n");
Myprintf;
for(j=0;j<psize;j++)
printf("|%2d ",pro[j]);
printf("|\n");
Myprintf;
for(i=0;i<bsize;i++)
{ for(j=0;j<psize;j++)
{
if(c[i][j]==-1)
printf("|%2c ",32);
else
printf("|%2d ",c[i][j]);
}
printf("|\n");
}
Myprintf;
printf("\n调入队列为:");
for(i=0;i<K+1;i++)
printf("%3d",queue[i]);
printf("\n缺页次数为：%6d\n缺页率：%16.6f",K+1,(float)(K+1)/psize);
}
void main()
{
int sel ;
do{
printf("\t\t\t--------------------------------------\t\t\t");
printf("\t\t\t 欢迎进入操作系统界面 \t\t\t");
printf("\t\t\t--------------------------------------\t\t\t\n");
printf("\t\t\t 虚拟内存 \t\t\t");
printf("\t\t\t -------------------------------- \t\t\t");
printf("\t\t\t 1、产生随机序列 \t\t\t");
printf("\t\t\t --------------------------------\t\t\t");
printf("\t\t\t 2、最久未使用(LRU) \t\t\t");
printf("\t\t\t --------------------------------\t\t\t");
printf("\t\t\t 3、先进先出(FIFO) \t\t\t");
printf("\t\t\t--------------------------------\t\t\t");
printf("\t\t\t 4、两种算法的比较() \t\t\t");
printf("\t\t\t--------------------------------\t\t\t");
printf("\t\t\t 0、退出(Exit) \t\t\t");
printf("<请选择所要执行的操作:(0)(1)(2)(3)(4)(5)>");
scanf("%d",&sel);
switch(sel)
{
case0:printf("\t\t\t再见 \t\t\t\n");system("pause");break;
case 1:build();break;
case 2:printf("最久未使用算法\n");LRU();empty();printf("\n");break;
case 3:printf("先进先出算\n");FIFO();empty();printf("\n");break;
case 4:printf("先进先出算法\n");FIFO();empty();
printf("最久未使用算法\n");LRU();empty();break;
default: printf("请输入正确的选项号");printf("\n\n");break;
}
}while(sel!=0);
}运行结果：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
相关文章
- 哈希算法 数据结构_实现哈希表构造和查找算法
- Gamma校正算法原理及实现
- 大数运算的算法设计和C++实现[通俗易懂]
- 如何使用优雅精准算法实现假装商品抢购繁忙的效果
- 前端常见算法(js)「建议收藏」
- SM2 (含SM3、SM4)国密算法工具QT版，彻底搞懂sm2算法的使用
- 数据结构与算法之二叉搜索树
- nginx负载均衡的五种算法
- KMP算法的实现详解
- DeepMind 发布强化学习通用算法 DreamerV3，AI 成精自学捡钻石
- 推荐几个算法可视化网站！
- PTA 数据结构与算法题目集（中文）7-14 电话聊天狂人 (25分) 题解
- 人工智能算法：基于Matlab遗传算法的实现示例
- 清华大一Python作业太难上热榜！只上3节课，手撸AI算法，网友：离本科毕设只差一篇万字论文
- OpenAI再获100亿美元？DoNotPay力砸100万仅为AI律师辩护复述；新冠四种亚型被机器学习算法进行归纳
- Bellman-Ford算法--解决负权边问题
- 算法-链表实现栈详解手机开发
- 决策树—ID3算法（介绍及Python实现）详解大数据
- 人脸识别的主要算法以及原理详解大数据
- 算法-数组中只出现一次的数字详解编程语言
- Go语言实现二分查找算法
- SQL Server中数据相加算法实现（sqlserver 相加）
- 使用SQLserver算法获取日期的星期信息（sqlserver取星期）