操作系统课程设计存储管理.docx
《操作系统课程设计存储管理.docx》由会员分享，可在线阅读，更多相关《操作系统课程设计存储管理.docx（25页珍藏版）》请在冰点文库上搜索。
操作系统课程设计存储管理
河南城建学院
《操作系统》课程设计说明书
设计题目：
存储管理
专业：
计算机科学与技术
指导教师：
邵国金、薛冰、郭猛
班级：
0814102
学号：
081410219
姓名：
李二萌
同组人：
杨森林、杨鹏飞、王伟超
计算机科学与工程系
2013年01月10日
前言
本模拟系统实现了先进先出页面淘汰算法（FIFO）、最近最少使用LRU页面淘汰算法、最近未使用算法NUR、最少访问页面算法LFU和最佳淘汰算法OPT。
同时系统可以随意设置当前分配给作业的物理块数。
系统运行时，任意输入一个页面访问序列，可以设定不同的页面置换算法和物理块数，输出其页面淘汰的情况，计算其缺页次数和缺页率。
系统结束后，比较同一个页面访问序列，可以得出在不同的页面置换算法和物理块数的情况下，其产生的缺页次数和缺页率。
使用FIFO算法，由于测试数据相同的页面比较少，所以采用FIFO算法时，需要置换的页面多，比较繁琐，没有优化效果，所以FIFO算法性能不好。
使用LRU的算法，此组数据显示LRU的算法使用比较繁琐，总的来说，NUR、LFU、LRU算法介于FIFO和Optimial之间。
通过系统模拟得出，optimal算法的性能高，LRU、NUR、LRU算法的性能次之，FIFO的算法性能最差，较少应用；由于optimal算法在实际上难于实现，所以实际应用一般用LRU算法。
本设计的目的是是熟悉存储管理的设计方法，加深对请求分页式存储管理的
认识。
设计中用到了数据结构中的相关知识，链表的操作，通过本设计可以加深的数据结构的理解。
设计代码语言用到的是C语言，使用起来比较方便，可以在虚拟机和VC上直接运行。
一、系统环境
1.1、硬件环境
PC机一台，内存，2.0GHZ主频
1.2、软件环境
设计和实验将Windows环境下，gcc和虚拟机软件VMWare。
二、设计目的
存储管理的主要功能之一是合理地分配空间。
请求页式管理是一种常用的虚拟存储管理技术。
本设计的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。
要求：
（1）通过随机数产生一个指令序列，共320条指令。
指令的地址按下述原则生成：
①50%的指令是顺序执行的；②25%的指令是均匀分布在前地址部分；③25%的指令是均匀分布在后地址部分。
具体的实施方法是：
①在[0，319]的指令地址之间随机选取一起点m；②顺序执行一条指令，即执行地址为m+l的指令；③在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m’；④顺序执行一条指令，其地址为m’+1；⑤在后地址[m’+2，319]中随机选取一条指令并执行；⑥重复上述步骤①~⑤，直到执行320次指令。
（2）将指令序列变换成为页地址流。
设:
①页面大小为1K；②用户内存容量为4页到32页；③用户虚存容量为32K。
在用户虚存中，按每页存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条~第9条指令为第0页（对应虚存地址为[0，9]）；
第10条~第19条指令为第1页（对应虚存地址为[10，19]）；
………
第310条~第319条指令为第31页（对应虚存地址为[310，319]）。
按以上方式，用户指令可组成32页。
（3）计算并输出下述各种算法在不同内存容量下的命中率（要为以下各种算法定义数据结构）。
①先进先出的算法（FIFO）；
②最近最少使用算法（LRU）；
③最近最不经常使用算法（NUR/NRU/CLOCK）。
三、总体设计
3.1、程序设计组成框图
Initialize（）初始化函数
Main（）
FIFO
算法
模块
LRU
算法
模块
LFU
算法
模块
NUR
算法
模块
OPT
算法
模块
程序设计组成框图
3.2、流程图
开始
还有指令吗
结束
计算出命中率
在实存队列查找该页号
计算出页号
FIFOLRU
开始
还有指令吗
计算出页号
把新页放入栈顶，同时向下移动其余页号
Y
Y
Y
在实存堆栈中查找该页号
Y
新页号按序加入实存队列
N
结束
计算出命中率
找到了吗
找到了吗
新页块压入栈顶，栈底页号移出
LRU算法
N
Y
Y
是否有空闲页面？
找到？
在面中查找是否存在
开始
还有指令吗？
计算出页号
count++
将该页导入内存页面，count=1
从内存页面找出使用最少的页面当空闲页面
计算出命中率
结束
N
Y
N
NUR算法
N
Y
Y
是否有空闲页面？
找到？
在页面中查找是否存在
开始
还有指令吗？
计算出页号
count=1
将该页导入内存页面，count=1
从内存页面找出最近未使用的页面当空闲页面
计算出命中率
结束
N
Y
N
OPT算法
N
Y
是否有空闲页面？
按早指令队列查找以后指令出每一面命中的距离，找出最大的或没命中的当空闲页面
找到？
在面中查找是否存在
开始
还有指令吗？
计算出页号
将该页导入空闲页面
计算出命中率
结束
N
Y
Y
N
四、详细设计
本程序设计基本按照题目的要求进行。
即首先用srand（）和rand（）函数定义和产生指令序列，然后将指令序列变成相应的页地址流，并针对不同的算法计算出相应的命中率。
4.1、数据结构
4.1.1页面类型
Typedefstruct{
Intpn,pfn,count,time;
}pl_type;
其中pn为页号,pfn为面号,count为个周期内访问该页面次数time为访问时间。
4.1.2页面控制结构
pfc_struct{
intpn,pfn;
structpfc_struct*next;
}
typedefstructpfc_structpfc_type;
pfc_typepfc[xy],*free_head,*busy_head;
pfc_type*busy_tail;
其中：
pfc[xy]定义用户进程虚页控制结构,
*free_head为空页面头的指针,
*busy_head为忙页面头的指针,
*busy_tail为忙页面尾的指针。
4.2.函数定义
（1）voidinitialize（）:
初始化函数,给每个相关的页面赋值。
（2）voidFIFO（）:
计算使用FIFO算法时的命中率。
（3）voidLRU（）:
计算使用LRU算法时的命中率。
（4）voidOPT（）:
计算使用OPT算法时的命中率。
（5）voidLFU（）:
计算使用LFU算法时的命中率。
（6）voidNUR（）:
计算使用NUR算法时的命中率。
4.3.变量定义
（1）inta[zllc];指令流数据组。
（2）intpage[zllc];每条指令所属页号。
（3）intoffset[zllc];每页装入10条指令后取模运算页号偏移值。
（4）intpf:
用户进程的内存页面数。
（5）intzhihuan:
页面失效次数。
4.4.算法分析
先进先出算法，即FIFO算法（First-InFirst-Outalgorithm）。
这种算法选择最先调入主存储器的页面作为被替换的页面。
它的优点是比较容易实现，能够利用主储存器中页面调度情况的历史信息，但是没有反应程序的局部性。
因为最先调入主存的页面，很有可能是经常使用的页面。
最近最少使用算法，即LFU（LeastFrequentlyusedalgorithm）。
这种算法选择近期最少访问的页面作为被替换的页面。
显然这是一种非常合理的算法，因为到目前为止最少使用的页面，和可能也是将来最少访问的页面。
该算法即充分利用了主存中吗调度的历史信息，又正确反映了程序的局部性。
但是这种算法实现起来非常的困难，它要为每个页面设置一个很长的计数器，并且要选择一个固定的时钟为每个计数器定时计数。
在选择被替换页面时，要从所有的计数器中选择一个计数值最大的计数器。
因此，通常使用如下一种简单的方法。
最久没有使用算法。
即LRU（LeastRecentlyUsedAlgorithm）。
这种算法把近期最久没有被访问的页面作为被替换的页面。
它把LFU算法中要记录数量上的多与少简化成判断有于无，因此实现起来比较容易。
NUR算法在需要淘汰一页时，从哪些最近一个时期内未被访问的页面中任选一页淘汰。
只要在页面中增加一个访问位即可实现。
当某页被访问时，访问位置1.否则，访问位置0.系统周期性第对所有的引用位清零。
当须淘汰一页时从那些访问位为0的页中选择一页进行淘汰。
如果引用位全为1或0，NRU算法退化为FIFO算法。
最优替换算法，即OPT（OptimalReplacementAlgorithm）.s上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。
当然这种假设不总是正确的。
最好的算法是选择将来醉酒不被访问的页面作为被替换的页面，这种算法的命中率是最高的，它就是最有替换算法。
要实现OPT算法，唯一的办法就是让程序先执行一遍，记录下实际的页地址流情况。
根据这个页地址流才能找到药被替换的页面。
显然这样做是不现实的。
因此OPT算法只是一种理想化的算法，然而它也是一种很用的算法。
实际上，经常把这种算法作为评价其他页面替换算法好坏的标准。
在其他条件相同的情况下，哪一种算法的命中率与OPT算法最接近，那么，它就是一种比较好的页面替换算法。
五、调试与测试
5.1、调试方法
利用Vware虚拟机的命令，用touch创建文件，vi进入文件，然后编写代码，运行程序。
2、测试结果的分析与讨论
调试运行结果图
5.2、测试结果的分析与讨论
使用FIFO算法需要置换的页面多，比较繁琐，没有优化效果，所以FIFO算法性能不好。
LRU的算法，此组数据显示LRU的算法使用比较繁琐，总的来说，NUR、LFU、LRU算法介于FIFO和Optimial之间。
通过系统模拟得出，optimal算法的性能高，LRU、NUR、LRU算法的性能次之，FIFO的算法性能最差，较少应用；由于optimal算法在实际上难于实现，所以实际应用一般用LRU算法。
六、设计中遇到的问题
本次课程设计中我们遇到的问题是，一开始没有弄清楚rand和sand函数的使用方法，以至于运行时的到的结果与实际算起来的不相符，后来查阅资料，上网浏览搜索相关信息后，终于弄明白了是怎么回事。
函数rand（）是真正的随机数生成器，而srand（）会设置供rand（）使用的随机数种子。
如果你在第一次调用rand（）之前没有调用srand（），那么系统会为你自动调用srand（）。
而使用同种子相同的数调用srand（）会导致相同的随机数序列被生成。
srand（（unsigned）time（NULL））则使用系统定时/计数器的值做为随机种子。
每个种子对应一组根据算法预先生成的随机数，所以，在相同的平台环境下，不同时间产生的随机数会是不同的，相应的，若将srand（unsigned）time（NULL）改为srand（TP）（TP为任一常量），则无论何时运行、运行多少次得到的“随机数”都会是一组固定的序列，因此srand生成的随机数是伪随机数。
还有就是开始代码编写完了之后，运行时OPT算法结果出错。
这个问题是在我们讨论并仔细查看OPT算法的内容后修改的。
七、源程序清单
#include
#include
#include
#defineTRUE1
#defineFALSE0
#defineINVALID-1
#definezllc320//指令流长
#definexy32//虚页长
#defineclear50//清零周期
typedefstruct//页面结构
{
intpn;//页号
intpfn;//页面框架号
intcount;//计数器
inttime;//时间
}pc;
pcpl[xy];//页面线性结构
typedefstructpfc_struct//页面控制结构，调度算法的控制结构
{
intpn;
intpfn;
structpfc_struct*next;
}pfc_type;
pfc_typepfc[xy],*free_head,*busy_head,*busy_tail;
intzhihuan,a[zllc];//a[]为指令序列
intpage[zllc],offset[zllc];//地址信息
intinitialize（int）;//初始化模块
intFIFO（int）;//FIFO调度算法
intLRU（int）;//LRU调度算法
intLFU（int）;//LFU调度算法
intNUR（int）;//NUR调度算法
intOPT（int）;//OPT调度算法
/*主函数*/
intmain（）
{
ints,i;
srand（（unsigned）time（NULL））;
s=rand（）%320;
for（i=0;i{
if（s<0||s>319）
{
printf（"Wheni==%d,Error,s==%d",i,s）;
exit（0）;
}
a[i]=s;
a[i+1]=a[i]+1;
a[i+2]=rand（）%（a[i+1]+1）;
a[i+3]=a[i+2]+1;
s=rand（）%（319-a[i+3]）+a[i+3]+1;
if（a[i+2]>318||s>319）
{
printf（"a[%d+2],anumberwhichis:
%dands==%d\n",i,a[i+2],s）;
}
}
for（i=0;i{
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
for（i=4;i<=32;i++）
{
printf（"%2dpageframes:
\t",i）;
FIFO（i）;
LRU（i）;
LFU（i）;
NUR（i）;
OPT（i）;
}
return0;
}
/*初始化相关的数据结构，pf表示内存的块数*/
intinitialize（intpf）
{
inti;
zhihuan=0;
for（i=0;i{
pl[i].pn=i;
pl[i].pfn=INVALID;//质页面控制结构中的页号，页面为空
pl[i].count=0;//页面控制结构中访问次数
pl[i].time=-1;//访问时间
}
for（i=0;i{
pfc[i].next=&pfc[i+1];
pfc[i].pfn=i;
}
pfc[pf-1].next=NULL;
pfc[pf-1].pfn=pf-1;
free_head=&pfc[0];//空页面队列的头指针为pfc[0]
return0;
}
/*先进先出算法，pf为用户进程的内存页面数*/
intFIFO（intpf）
{
inti;
pfc_type*p;//中间变量
initialize（pf）;//初始化数据结构
busy_head=busy_tail=NULL;//忙页面头队列，为队列链接
for（i=0;i{
if（pl[page[i]].pfn==INVALID）//页面失效
{
zhihuan++;//失效次数
if（free_head==NULL）//无空闲页面
{
p=busy_head->next;//保存忙页面的下一个页面
pl[busy_head->pn].pfn=INVALID;//把这个页面换出，更新它的数据成员
free_head=busy_head;//释放忙页面队列的第一个页面
free_head->next=NULL;//表明此页面是空的组后一面
busy_head=p;//更新页面的头队列指针
}
p=free_head->next;
free_head->pn=page[i];
pl[page[i]].pfn=free_head->pfn;
free_head->next=NULL;//使busy的尾为空
if（busy_tail==NULL）
{
busy_tail=busy_head=free_head;
}
else
{
//把刚刚换进来的接在busy_tail的后面
busy_tail->next=free_head;
busy_tail=free_head;
}
free_head=p;//下一个空页面
}
}
printf（"FIFO:
%6.4f|",1-（float）zhihuan/320）;
return0;
}
/*最近最久未使用算法*/
intLRU（intpf）
{
intmin,minj,i,j,present_time;//minj为最小值下标
initialize（pf）;
present_time=0;
for（i=0;i{
if（pl[page[i]].pfn==INVALID）//页面失效
{
zhihuan++;
if（free_head==NULL）//无空闲页面
{
min=32767;//设置最大值
for（j=0;j{
if（min>pl[j].time&&pl[j].pfn!
=INVALID）
{
min=pl[j].time;
minj=j;
}
}
free_head=&pfc[pl[minj].pfn];//腾出一个单元
pl[minj].pfn=INVALID;
pl[minj].time=0;
free_head->next=NULL;
}
pl[page[i]].pfn=free_head->pfn;//有空闲页面改为有效
pl[page[i]].time=present_time;
free_head=free_head->next;//减少一个free页面
}
else
{
pl[page[i]].time=present_time;//命中则增加该页面的访问次数
}
present_time++;
}
printf（"LRU:
%6.4f|",1-（float）zhihuan/320）;
return0;
}
/*最近未使用算法*/
intNUR（intpf）
{
inti,j,dp,cont_flag,old_dp;//这个算法用count用于访问位
initialize（pf）;
dp=0;
for（i=0;i{
if（pl[page[i]].pfn==INVALID）//页面失效
{
zhihuan++;
if（free_head==NULL）//无空闲页
{
cont_flag=TRUE;
old_dp=dp;
while（cont_flag）//找到一访问位count为0的页面
{
if（pl[dp].count==0&&pl[dp].pfn!
=INVALID）
{
cont_flag=FALSE;
}
else//下一个页面
{
pl[dp].count=0;
dp++;
if（dp==xy）//32个页面找一遍，开始新的循环
dp=0;
}
}
free_head=&pfc[pl[dp].pfn];
pl[dp].pfn=INVALID;
free_head->next=NULL;
}
pl[page[i]].pfn=free_head->pfn;
pl[page[i]].count=1;
free_head->pn=page[i];
free_head=free_head->next;
}
else
{
pl[page[i]].count=1;
}
if（i%clear==0）
for（j=0;jpl[j].count=0;
}
printf（"NUR:
%6.4f|",1-（float）zhihuan/320）;
return0;
}
/*最少访问页面算法*/
intLFU（intpf）
{
inti,j,min,minpage;
initialize（pf）;
for（i=0;i{
if（pl[page[i]].pfn==INVALID）//页面失效
{
zhihuan++;
if（free_head==NULL）//无空闲页面
{
min=32767;//获取count的使用频率最小的内存
for（j=0;j{
if（min>pl[j].count&&pl[j].pfn!
=INVALID）
{
min=pl[j].count;
minpage=j;
}
}
free_head=&pfc[pl[minpage].pfn];
pl[minpage].pfn=INVALID;
pl[minpage].count=0;
free_head->next=NULL;
}
pl[page[i]].pfn=
升级会员 