页面置换算法课程设计

《页面置换算法课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、操作系统课程设计报告题目页面置换算法专业计算机科学与技术小组成员：目录1.设计目的22.课设要求23.系统分析34.系统设计34.1问题分析34.2程序整体框图54.3FIFO算法54.4LRU算法64.5OPT算法75.功能与测试85.1开始界面85.2FIFO算法95.3LRU算法105.4OPT算法106.结论117.附录12I1.设计目的1、存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本次设计的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术

2、的特点，掌握请求页式管理的页面置换算法。2、提高自己的程序设计能力、提高算法设计质量与程序设计素质；2.课设要求设计一个请求页式存储管理方案。并编写模拟程序实现之。要求包含：1．过随机数产生一个指令序列，共320条指令。其地址按下述原则生成：①50%的指令是顺序执行的；②25%的指令是均匀分布在前地址部分；③25%的指令是均匀分布在后地址部分；具体的实施方法是：在[0，319]的指令地址之间随机选区一起点M;顺序执行一条指令，即执行地址为M+1的指令；在前地址[0，M+1]中随机选取一条指令并执行，该指令

3、的地址为M’;顺序执行一条指令，其地址为M’+1；在后地址[M’+2，319]中随机选取一条指令并执行；重复A—E，直到执行320次指令。2．指令序列变换成页地址流设：（1）页面大小为1K；用户内存容量为4页到32页；用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：18第0条—第9条指令为第0页（对应虚存地址为[0，9]）；第10条—第19条指令为第1页（对应虚存地址为[10，19]）；。。。。。。。。。。。。。。。。。。。。。第310条—第319

4、条指令为第31页（对应虚存地址为[310，319]）；按以上方式，用户指令可组成32页。3.计算并输出下述各种算法在不同内存容量下的命中率。FIFO先进先出的算法LRU最近最少使用算法OPT最佳淘汰算法（先淘汰最不常用的页地址）3.系统分析在多道程序环境下，要使程序运行，必须先为之创建进程。而创建进程的第一步是将程序和数据装入内存。存储器实现的功能主要是内存分配等功能，本模拟系统所要实现的就是将进程的程序和数据装入内存（物理块）。具体需要实现的功能如下：1、读入进程大小，进行分页，确定每一页的指令地址范围

5、；2、读入一个指令，确定其所在页面，读入内存物理块中。物理块空闲直接读入，物理块已满，指向下步操作。3、物理块已满，将要淘汰原来首先进入到内存中的页面，即换出；然后将现在的指令地址页面读入物理块中，即换入。4.系统设计4.1问题分析18分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为物理块，在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中系统为每个进程建立一个页表，

6、页表给出逻辑页号和具体内存块号相应的关系。一个页表中包含若干个表目，表目的自然序号对应于用户程序中的页号，表目中的块号是该页对应的物理块号。请求页式存储管理方式是一种实现虚拟存储器的方式，是指在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面。当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。请求页式存储管理主要需要解决以下问题：系统如何获知进程当前所需页面不在主存；当发现缺页时，如何把所缺页面调入主存；当主存中没有空

7、闲的页框时，为了要接受一个新页，需要把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。4.2程序整体框图Main()函数OPT算法LRU算法FIFO算法图4-1程序整体框图由于该算法规模较小，可以将该系统划分为三块，分别是：FIFO算法模块、LRU算法模块、OPT算法模块。184.3FIFO算法基于程序总是按线形顺序来访问物理空间这一假设，总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面。开始初始化函数还有指令在队列中查找将数组中第一个数据移除，并置标志位找到了吗将新加入的指令加入数组尾部结束

8、NYYN4.4LRU算法LRU18置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的次数count,，当须淘汰一个页面时，选择现有页面中其count值最大的，即最近最久未使用的页面予以淘汰。NYY是否有空闲页面？找到？