操作系统实验报告虚拟内存Word文件下载.docx
- 文档编号:8126455
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:29
- 大小:273.44KB
操作系统实验报告虚拟内存Word文件下载.docx
《操作系统实验报告虚拟内存Word文件下载.docx》由会员分享,可在线阅读,更多相关《操作系统实验报告虚拟内存Word文件下载.docx(29页珍藏版)》请在冰点文库上搜索。
2.指令序列变换成页地址流
设:
(1)页面大小为1K;
(2)用户内存容量为4页到32页;
(3)用户虚存容量为32K。
在用户虚存中,按每K存放10条指令排列虚存地址,即320条指令在虚存中的存放方式为:
第0条—第9条指令为第0页(对应虚存地址为[0,9]);
第10条—第19条指令为第1页(对应虚存地址为[10,19]);
……………………第310条—第319条指令为第31页(对应虚存地址为[310,319]);
按以上方式,用户指令可组成32页。
3.计算并输出下述各种算法在不同内存容量下的命中率。
A.先进先出(FIFO)页面置换算法
B.最近最久未使用(LRU)页面置换算法--最近最少使用算法
C.最少使用(LFR)页面置换算法
D.最佳(Optimal)页面置换算法
三、实验环境
(说明本实验需要的环境)
Vscode+ubuntun
四、实验过程描述
本实验需要分几个步骤完成。
本实验所定义的数据结构:
#define
I_NUM
320
CONST
1000
//页表
typedef
struct
pagetable
{
int
p_num;
//页号
access_time[32];
//记录访问的时间
bool
status[32];
//状态位(是否写入内存)
写入1
未写入0
m_num[32];
//存入的内存块号
}PageTable;
//队列的结构
count;
//计数
front;
//头指针
rear;
//尾指针
*data;
//数据域
size;
//大小
}
CirQueue;
ins[I_NUM];
//指令数组
visit_times[32];
//每一个页面访问次数的数组
步骤一:
按要求产生指令序列。
这部分按照指导书上做就ok了。
具体实现:
void
initIns()
for
(int
i
=
0;
<
I_NUM;
+=
4)
m
rand()
%
//0到319的随机数
ins[i]
(m
+
1)
//执行地址为m+1的指令
m1
2);
//随机选取一条指令并执行
ins[i
1]
m1;
2]
(m1
//执行地址为m1+1的指令
3]
(I_NUM
-
2)
2;
}
步骤二:
指令序列变换成页地址流
只需将指令所在的位置整除10即可得到页号。
步骤三:
实现各种算法
首先是FIFO算法。
相关原理:
该算法总是淘汰最新进入内存的页面,即选择在内存中驻留时间最久的页面予
以淘汰。
该算法实现简单,只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。
思路:
先检查内存是否还有空间,如果还有则直接插入,否则调用此算法,将先出队再入队来完成页面置换。
实现:
FIFO(int
f_num,
PageTable
*pagetable)
p_fault
CirQueue
*queue
(CirQueue
*)malloc(sizeof(CirQueue));
initPage(pagetable,
f_num);
initQueue(queue,
i;
i_num
320;
i_num++)
if
(!
isHitted(f_num,
i_num,
pagetable))
//没命中
p_fault++;
//页表内没有查询到当前指令所属的页
(i
pagetable->
i++)
(pagetable->
status[i]
==
0)
break;
p_num)
//内存未满
让新的页进来
true;
m_num[i]
ins[i_num]
/
10;
Enqueue(queue,
(ins[i_num]
10));
//同时
此页进队
else
//内存已满
开始置换
last_page
Dequeue(queue);
last_page)
//新的页号进队
double
p_fault_r
(double)p_fault
printf("
%f\t"
1
p_fault_r);
其次是LRU算法。
最近最久未使用(LRU)页面置换算法,是根据页面调入内存后的使用情况进行决策的。
由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似,因此,LRU置换算法是选择最近最久未使用的页面予以淘汰。
该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t,当需淘汰一个页面时,选择现有页面中其t值最大的,即最近最久未使用的页面予以淘汰。
同样先判断内存是否为满。
如果未满则直接插入,否则调用该算法。
该算法需要一个记录访问时间的数组access_time[],当需要置换时,选择数组中元素最大的元素,将其置换出去,然后将新页面放进来。
每次访问时将未访问的页面的access_time加一。
实现:
//lru算法
LRU(int
k;
(k
k
k++)
status[k]
false)
p_num)
m_num[k]
//所有页的访问次数自增
incTime(pagetable,
else
index
LeastUsed(pagetable,
access_time[index]
m_num[index]
//所有页的访问时间自增
incTime(PageTable
*pagetable,
f_num)
f_num;
true)
access_time[i]++;
LeastUsed(PageTable
f_num)
//选择现有页面中其
t
值最大的,即用的最少的页
access_time[0];
max
access_time[i]
>
k)
access_time[i];
return
max;
然后是LFR算法。
在采用该算法时,应为在内存中的每个页面设置一个移位寄存器,用来记录页面被访问的频率。
该置换算法选择在最近使其使用最少的页面作为淘汰页。
需要一个数组visit_times[]来记录每个页面访问的次数,即为频率。
选择频率最低的页面,将其置换出去,然后将新页面放进来。
//lfr算法
LFR(int
i<
visit_times[ins[i_num]
10]++;
所有页的访问次数自增
min_index
min
CONST;
32;
true)
//寻找在内存中的被访问次数最少的页面换出
(visit_times[k]
min)
visit_times[k];
m_num[min_index]
最后是OPT算法。
该算法选择的被淘汰页面,将是以后永远不使用的,或许是在最长(未来)时间内不再被访问的页面。
采用该算法,通常可保证获得最低的缺页率。
但由于人们目前
还无法预知一个进程在内存的若干个页面中,哪一个页面是未来最长时间
由于本模拟实验已经知道将来会有那些序列被放进内存,所以该算法可以实现。
该算法需要数组distance[]表示该页到未来最近一次的距离。
需要置换时,选择距离被使用的页面将其置换,然后将新页面置换进来。
OPT(int
//检查当前内存里的页哪个最久会被使用
*distance
*)malloc(sizeof(int)
*
//暂存距离的数组
//初始化
distance[i]
l
l++)
m_num[l];
i_num;
(ins[k]
i)
distance[l]
l;
//找出之后最远被使用的
distance[0];
j
j++)
(distance[j]
distance[j];
j;
m_num[max]
五、实验结果
运行结果如下:
随着物理内存的增加,命中率逐渐上升。
4种算法的命中率差别不大。
六、附件
6.1附件1:
源代码
Vm.h
#include
stdio.h>
stdlib.h>
time.h>
initQueue(CirQueue*
queue,int
i);
isEmpty(CirQueue*
queue);
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统 实验 报告 虚拟内存