操作系统页面置换算法课程设计
- 格式：doc
- 大小：32.00 KB
- 文档页数：4
操作系统课程设计报告书
一、设计目的
学习计算机软件技术，特别是计算机操作系统技术，除了需要刻苦努力外，还需要掌握软件和操作系统的原理与设计技巧。本设计木的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。
二、设计任务
1、 通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：50%的指令是顺序执行的；25%的指令是均匀分布在前地址部分；25%的指令是均匀分布在地址部分。
2、 将指令序列换成为页地址流。
3、 计算并输出下述各种算法在不同内存容量下的命中率。
（1） 先进先出的算法（FIFO）；
（2） 最近最少使用算法（LRU）；
（3） 最近最不经常使用算法（NUR）；
三、设计内容与步骤
分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。
1、调页策略
1)何时调入页面
2)请求调页策略
2、从何处调入页面
(1) 系统拥有足够的对换区空间，这时可以全部从对换区调入 所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。
(2) 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出时，以后需要时，再从对换区调入。
(3) UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都从文件区调入。而对于曾经运行过但又被换出的页面，由于被放在对换区，因此在下次时，应从对换区调入。由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。
3、页面调入过程
四、页面置换算法
在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪 个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。
1 、 先进先出(FIFO)页面置换算法： 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。
2、 最近最久未使用页面置换算法LRU（least recently used）：
算法的基本思想：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问
3 、 最不经常使用页面淘汰置换算法(LFU:Least Frequently Used)：
在采用该算法时，应为在内存中的每个页面设置一个移位寄存器骼来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面为淘汰页。
4、 最近没有使用页面淘汰NUR置换算法的描述：
该算法在需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。 只要在页表中增设一个访问即可实现。当某页被访问时，访问位置1，否则，访问位置0。系统周期性地对所有引用位清零。当需淘汰一页时，从那些访问位为零的页中选一页进行淘汰。
FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
5、 程序执行是稳定的，高效的。在LRU算法中，要找出最近最久未使用的页面的话，就必须设置有关的访问记录项，且每一次访问这些记录项，页面都必须更新这些记录项。这个记录项在此程序中为
如此显然要花费较大的系统开销(包括时间和空间上的)，这也是实际系统中不直接采用LRU算法作为页面置换算法的直接原因，但由于其在页面置换的优越性，实际系统常使用LRU的近似算法。
6、 由于程序旨在页面置换算法的模拟，程序并没有设计自动执行的功能，这也是本设计的缺陷。
五.程序设计
1、数据结构
(1) 页面类型
typedef sruct{
int pn,pfn,counter,time;
}p1_type;
其中pn为页号，pfn为面号，counter为个周期内访问该页面次数time为访问时间。
(2)页面控制结构
pfc_struct{
int pn,pfn;
struct pfc_struct *next; }
typedef struct pfc_struct pfc_type;
pfc_type pfc[total_vp],*freepf_head,*busypf_head;
pfc_type *busypf_tail;
其中pfc[total_vp] 定义用户进程虚页控制结构，
*freepf_head为空页面头的指针，
许busypf_head为忙页面头的指针,
提busypf_jail为忙页面尾的指针。
2、 函数定义
(1) void initialize():初始化函数，给每个相关的页面赋值。
(2) void FIFO()：计算使用FIFO算法时的命中率。
(3) void LRU(): 计算使用LRU算法时的命中率.
(4) void LFU():计算使用LFU算法时的命中率.
(5) void NUR():计算使用NUR算法时的命中率。
3、 变量定义
(1) int a[tatal_instruction]:指令流数据组。
(2) int page[total_instruction]:每条指令所属页号。
(3) int ofthet[total-instruction]:每页装入10条指令后取模运算页号偏移值。
(4) int total_pf:拥护进程的内存页面数。
(5) int disaffect:页面失效次数。
4、 程序
void LRU(total_pf)
int total_pf;
{int min,minj,i,j,present_time;
initialize(total_pf);present_time=0;
for(i=0;i
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect++;
if(freepf_head==NUL) /*无空闲页面*/
{
min=32767;
for(j=0;j
if(min>pl[j].time&&pl[j].pfn!=INVALID)
{
min=pl[j].time;
minj=j;
}
freepf_head=&pfc[pl[minj].pfn];
pl[minj].pfn=INVALID;
pl[minj].time=-1;
freepf_head->next=NUL; }
pl[page[i]].pfn=freepf_head->pfn;
pl[page[i]].time=present_time;
freepf_head=freepf_head->next;
}
else
pl[page[i]].time=present_time;
present_time++;
}
printf("LRU:%6.4f",1-(float)diseffect/320);
}
六、执行结果
结果分析：上述结果可知，在内存页面数较少（4~5页面）时，3种算法的命中率差别不大，可是50%左右。在内存页面为7~25个页面之间时，3种算法的访内命中率大致在52%至87%
之间变化。在内存页面为25~32个页面时，由于用户进程的所有指令基本上都已装入内存，从而命中率已较大。从而算法之间的差别不大。
七、实验心得
经过一个星期的上机实践学习，使我对操作系统这门课程有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能更好地学习它，通过实践，我也发现我的好多不足之处，首先是以前的C语言基础没打好，一些基本常识性东西都不知道，再有操作时有很多很生疏的东西，虽然在学习课本知识的时感觉什么东西都很简单，但真正操作起来确实如此之难，语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。通过实践的学习，我认到学好计算机要重视实践操作，不仅仅是学习操作系统，还是其它的课程，以及其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注视实践操作，使自己更好地学好计算机。回顾起此次单片机课程设计，至今我仍感慨颇多，的确，从选题到定稿，从理论到实践，在整整一星期的日子里，可以说得是苦多于甜，但是可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，不过设计终于顺利完成了，在设计中遇到了很多编程问题，最后在老师的辛勤指导下，终于游逆而解。同时，在老师的身上我学得到很多实用的知识，再次我表示感谢！同时，对给过我帮助的所有同学和各位指导老师再次表示忠心的感谢！
